27#define HEAP_PARENT(i) (((i) - 1) >> 1)
57# define OFFSET(i) (i * uint(sizeof(HeapSimpleNode)))
58# define NODE(offset) (*(HeapSimpleNode *)(tree_buf + (offset)))
63# define NODE(i) tree[i]
66#define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
72 float active_val =
init->value;
73 void *active_ptr =
init->ptr;
78 NODE(i).value = active_val;
94 if (smallest == i) [[unlikely]] {
100 NODE(i).value =
NODE(smallest).value;
105 NODE(i).value = active_val;
109 NODE(i).ptr = active_ptr;
113#undef HEAP_LEFT_OFFSET
120 while (i > 0) [[likely]] {
123 if (active_val >= tree[p].value) {
131 tree[i].
value = active_val;
132 tree[i].
ptr = active_ptr;
146 heap->
bufsize = std::max(1u, reserve_num);
159 for (
uint i = 0; i < heap->
size; i++) {
164 MEM_delete(heap->
tree);
171 for (
uint i = 0; i < heap->
size; i++) {
192 return (heap->
size == 0);
#define HEAP_LEFT_OFFSET(i)
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define MEM_realloc_uninitialized(vmemh, len)
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
HeapSimple * BLI_heapsimple_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMLoop * l
uint BLI_heapsimple_len(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
void(*) HeapSimpleFreeFP(void *ptr)
static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapSimple * BLI_heapsimple_new() ATTR_WARN_UNUSED_RESULT
float BLI_heapsimple_top_value(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1