215 lines
7.4 KiB
C
215 lines
7.4 KiB
C
#include <c_IndexMinPQ.h>
|
||
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
|
||
/**
|
||
* @brief 双向路由置换原子操作（索引优先队列的灵魂核心）
|
||
*
|
||
* 交换堆物理下标 i 和 j 位置的数据时，不仅对调 pq，更要反向刷新两个用户索引在 qp 中的物理坐标指向。
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
void c_IPQ_Swap(c_IndexMinPQ_t* pq, c_size_t i, c_size_t j) {
|
||
c_size_t swap_index_i = pq->pq[i];
|
||
c_size_t swap_index_j = pq->pq[j];
|
||
|
||
pq->pq[i] = swap_index_j;
|
||
pq->pq[j] = swap_index_i;
|
||
|
||
pq->qp[swap_index_i] = j;
|
||
pq->qp[swap_index_j] = i;
|
||
}
|
||
|
||
/**
|
||
* @brief 根据堆物理位置，提取真实 keys 空间对应数据的安全辅助内联
|
||
*/
|
||
C_STATIC_FORCE_INLINE
|
||
char* c_IPQ_GetKeyByHeapPos(const c_IndexMinPQ_t* pq, c_size_t heap_pos) {
|
||
c_size_t user_idx = pq->pq[heap_pos];
|
||
return pq->keys + (user_idx * pq->elem_size);
|
||
}
|
||
|
||
static void c_IndexMinPQ_SiftUp(c_IndexMinPQ_t* pq, c_size_t child) {
|
||
// 因为堆物理下标从 1 开始，子父级关系的自减收缩终止位置是 1。
|
||
// 这在无符号数（child > 1）下是天然绝对安全的，不会爆发 0 - 1 的下溢。
|
||
while (child > 1) {
|
||
c_size_t parent = child >> 1;
|
||
if (pq->cmp(c_IPQ_GetKeyByHeapPos(pq, child), c_IPQ_GetKeyByHeapPos(pq, parent), pq->args) < 0) {
|
||
c_IPQ_Swap(pq, child, parent);
|
||
child = parent;
|
||
} else {
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
static void c_IndexMinPQ_SiftDown(c_IndexMinPQ_t* pq, c_size_t parent) {
|
||
c_size_t num = pq->size;
|
||
while (1) {
|
||
c_size_t left_child = parent << 1;
|
||
if (left_child > num) break;
|
||
|
||
c_size_t smaller_child = left_child;
|
||
c_size_t right_child = left_child + 1;
|
||
|
||
if (right_child <= num) {
|
||
if (pq->cmp(c_IPQ_GetKeyByHeapPos(pq, right_child), c_IPQ_GetKeyByHeapPos(pq, left_child), pq->args) < 0) {
|
||
smaller_child = right_child;
|
||
}
|
||
}
|
||
|
||
if (pq->cmp(c_IPQ_GetKeyByHeapPos(pq, smaller_child), c_IPQ_GetKeyByHeapPos(pq, parent), pq->args) < 0) {
|
||
c_IPQ_Swap(pq, parent, smaller_child);
|
||
parent = smaller_child;
|
||
} else {
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
/* ------------------------------------------------------------------------------------------------------------------ */
|
||
/* */
|
||
|
||
c_err_t c_IndexMinPQ_Init(c_IndexMinPQ_t* self, c_size_t max_elements, c_size_t elem_size, c_SortCompare_t cmp, void* args, c_Allocator_t* allocator) {
|
||
if (!self || max_elements == 0 || elem_size == 0 || !cmp) {
|
||
return C_ERR_PARAM;
|
||
}
|
||
|
||
if (allocator) {
|
||
self->allocator = *allocator;
|
||
} else {
|
||
self->allocator = c_DefaultAllocator;
|
||
}
|
||
|
||
self->max_elements = max_elements;
|
||
self->size = 0;
|
||
self->elem_size = elem_size;
|
||
self->cmp = cmp;
|
||
self->args = args;
|
||
|
||
// 前置逆向除法溢出安全审计：确保三组大空间开辟时不会发生乘法溢出
|
||
if (((c_size_t)-1) / sizeof(c_size_t) < (max_elements + 1)) return C_ERR_NOMEM;
|
||
if (((c_size_t)-1) / elem_size < max_elements) return C_ERR_NOMEM;
|
||
|
||
// 分配堆数组 pq（堆下标从 1 开始使用到 max_elements，方便进行二叉父子节点位移运算）
|
||
self->pq = (c_size_t*)c_Allocator_Alloc(&self->allocator, (max_elements + 1) * sizeof(c_size_t));
|
||
// 分配逆向映射表 qp
|
||
self->qp = (c_size_t*)c_Allocator_Alloc(&self->allocator, max_elements * sizeof(c_size_t));
|
||
// 分配密集优先级数据存储块
|
||
self->keys = (char*)c_Allocator_Alloc(&self->allocator, max_elements * elem_size);
|
||
|
||
if (!self->pq || !self->qp || !self->keys) {
|
||
// 部分失败时原路进行逆向安全解构，斩断漏存
|
||
if (self->pq) c_Allocator_Free(&self->allocator, self->pq);
|
||
if (self->qp) c_Allocator_Free(&self->allocator, self->qp);
|
||
if (self->keys) c_Allocator_Free(&self->allocator, self->keys);
|
||
return C_ERR_NOMEM;
|
||
}
|
||
|
||
// 🌟 核心防下溢舒适区构建：将所有 qp 映射槽初始化填充为 (c_size_t)-1（代表未入队列）
|
||
memset(self->qp, 0xFF, max_elements * sizeof(c_size_t));
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
/**
|
||
* @brief 检查某个唯一用户索引当前是否在队列中有效存在（常数级的时间开销）
|
||
*/
|
||
bool c_IndexMinPQ_Contains(const c_IndexMinPQ_t* pq, c_size_t index) {
|
||
if (!pq || index >= pq->max_elements) return false;
|
||
return pq->qp[index] != (c_size_t)-1;
|
||
}
|
||
|
||
|
||
/**
|
||
* @brief 绑定一个唯一的唯一 index 压入优先级关联数据
|
||
*/
|
||
c_err_t c_IndexMinPQ_Push(c_IndexMinPQ_t* pq, c_size_t index, const void* item) {
|
||
if (!pq || !item) return C_ERR_PARAM;
|
||
if (index >= pq->max_elements) return C_ERR_PARAM;
|
||
if (c_IndexMinPQ_Contains(pq, index)) return C_ERR_EXIST; // 重复索引拦截
|
||
|
||
pq->size++;
|
||
pq->pq[pq->size] = index; // 堆底追加映射
|
||
pq->qp[index] = pq->size; // 注册物理位置
|
||
|
||
// 拷贝优先级数据
|
||
memcpy(pq->keys + (index * pq->elem_size), item, pq->elem_size);
|
||
|
||
// 重建索引最小堆半序
|
||
c_IndexMinPQ_SiftUp(pq, pq->size);
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
/**
|
||
* @brief 弹出当前的绝对最小值元素，并将其关联的唯一用户索引（index）通过 out_index 吐出
|
||
*/
|
||
c_err_t c_IndexMinPQ_Pop(c_IndexMinPQ_t* pq, c_size_t* out_index) {
|
||
if (!pq) return C_ERR_PARAM;
|
||
if (pq->size == 0) return C_ERR_EMPTY;
|
||
|
||
// 堆顶驻留的唯一索引即为全局最小值
|
||
c_size_t min_idx_result = pq->pq[1];
|
||
if (out_index) {
|
||
*out_index = min_idx_result;
|
||
}
|
||
|
||
// 交换堆顶与堆底
|
||
c_IPQ_Swap(pq, 1, pq->size);
|
||
pq->size--;
|
||
|
||
// 触发下沉
|
||
if (pq->size > 0) {
|
||
c_IndexMinPQ_SiftDown(pq, 1);
|
||
}
|
||
|
||
// 将弹出的用户唯一索引解绑销毁注销状态（填充为 -1）
|
||
pq->qp[min_idx_result] = (c_size_t)-1;
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
/**
|
||
* @brief 【图算法核能优化原子操作】：在常数级时间内寻找并修改某个特定 index 的优先级数据
|
||
*
|
||
* 时间复杂度为完美的 O(log N)，而在普通优先队列中为退化的 O(N)！
|
||
*/
|
||
c_err_t c_IndexMinPQ_Change(c_IndexMinPQ_t* pq, c_size_t index, const void* new_item) {
|
||
if (!pq || !new_item || index >= pq->max_elements) return C_ERR_PARAM;
|
||
if (!c_IndexMinPQ_Contains(pq, index)) return C_ERR_EMPTY;
|
||
|
||
// 1. 物理覆写数据
|
||
memcpy(pq->keys + (index * pq->elem_size), new_item, pq->elem_size);
|
||
|
||
// 2. 提取该索引对应的真实物理堆位置（Heap Position）
|
||
c_size_t heap_pos = pq->qp[index];
|
||
|
||
// 3. 联动调整：自适应向上上浮或向下下沉重建单调，保证其瞬间归位
|
||
c_IndexMinPQ_SiftUp(pq, heap_pos);
|
||
c_IndexMinPQ_SiftDown(pq, heap_pos);
|
||
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
/**
|
||
* @brief 观察读取但不弹出最小索引堆的堆顶最小关联索引（Index）
|
||
*/
|
||
c_err_t c_IndexMinPQ_Peek(const c_IndexMinPQ_t* pq, c_size_t* out_index) {
|
||
if (!pq || !out_index) return C_ERR_PARAM;
|
||
if (pq->size == 0) return C_ERR_EMPTY;
|
||
*out_index = pq->pq[1];
|
||
return C_ERR_OK;
|
||
}
|
||
|
||
/**
|
||
* @brief 反初始化并销毁全部路由内存矩阵
|
||
*/
|
||
void c_IndexMinPQ_Destroy(c_IndexMinPQ_t* pq) {
|
||
if (pq) {
|
||
if (pq->pq) c_Allocator_Free(&pq->allocator, pq->pq);
|
||
if (pq->qp) c_Allocator_Free(&pq->allocator, pq->qp);
|
||
if (pq->keys) c_Allocator_Free(&pq->allocator, pq->keys);
|
||
pq->pq = NULL; pq->qp = NULL; pq->keys = NULL;
|
||
pq->size = 0; pq->max_elements = 0;
|
||
}
|
||
} |