45#define HEAP_CHUNK_DEFAULT_NUM \
46 uint(MEM_SIZE_OPTIMAL((1 << 16) - sizeof(HeapNode_Chunk)) / sizeof(HeapNode))
65#define HEAP_PARENT(i) (((i) - 1) >> 1)
66#define HEAP_LEFT(i) (((i) << 1) + 1)
67#define HEAP_RIGHT(i) (((i) << 1) + 2)
68#define HEAP_COMPARE(a, b) ((a)->value < (b)->value)
71# define HEAP_EQUALS(a, b) ((a)->value == (b)->value)
77 HeapNode *pi = tree[i], *pj = tree[j];
102 if (smallest == i) [[unlikely]] {
115 while (i > 0) [[likely]] {
136 chunk->
prev = chunk_prev;
146 if (heap->
nodes.free) {
178 heap->
bufsize = std::max(1u, reserve_num);
183 heap->
nodes.free =
nullptr;
198 for (i = 0; i < heap->
size; i++) {
206 chunk_prev = chunk->
prev;
211 MEM_delete(heap->
tree);
220 for (i = 0; i < heap->
size; i++) {
227 while (heap->
nodes.chunk->prev) {
229 MEM_delete(heap->
nodes.chunk);
230 heap->
nodes.chunk = chunk_prev;
233 heap->
nodes.free =
nullptr;
263 if (*node_p ==
nullptr) {
273 return (heap->
size == 0);
283 return heap->
tree[0];
297 void *ptr = heap->
tree[0]->
ptr;
326 if (value < node->value) {
330 else if (value >
node->value) {
339 if (value < node->value) {
343 else if (value >
node->value) {
361 if (root < heap->size) {
372 if (r < heap->size) {
#define HEAP_CHUNK_DEFAULT_NUM
#define HEAP_COMPARE(a, b)
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define MEM_realloc_uninitialized(vmemh, len)
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
unsigned int BLI_heap_len(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
HeapNode * BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
void void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr) ATTR_NONNULL(1
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
void(*) HeapFreeFP(void *ptr)
static bool heap_is_minheap(const Heap *heap, uint root)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
static HeapNode * heap_node_alloc(Heap *heap)
BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
static void heap_node_free(Heap *heap, HeapNode *node)
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
static void heap_down(Heap *heap, uint i)
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
static HeapNode_Chunk * heap_node_alloc_chunk(uint nodes_num, HeapNode_Chunk *chunk_prev)
bool BLI_heap_is_valid(const Heap *heap)
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) 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
void * BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
static void heap_up(Heap *heap, uint i)
void void float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
struct blender::Heap::@075070100225061163037375163234225361134163364140 nodes