Blender V5.3
BLI_heap.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <algorithm>
12#include <cstdlib>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_heap.hh"
17#include "BLI_utildefines.hh"
18
19#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
20
21namespace blender {
22
23/***/
24
25struct HeapNode {
26 float value;
28 void *ptr;
29};
30
37
45#define HEAP_CHUNK_DEFAULT_NUM \
46 uint(MEM_SIZE_OPTIMAL((1 << 16) - sizeof(HeapNode_Chunk)) / sizeof(HeapNode))
47
48struct Heap {
52
53 struct {
54 /* Always keep at least one chunk (never nullptr) */
56 /* when nullptr, allocate a new chunk */
59};
60
61/* -------------------------------------------------------------------- */
64
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)
69
70#if 0 /* UNUSED */
71# define HEAP_EQUALS(a, b) ((a)->value == (b)->value)
72#endif
73
74BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
75{
76 HeapNode **tree = heap->tree;
77 HeapNode *pi = tree[i], *pj = tree[j];
78 pi->index = j;
79 tree[j] = pi;
80 pj->index = i;
81 tree[i] = pj;
82}
83
84static void heap_down(Heap *heap, uint i)
85{
86 /* size won't change in the loop */
87 HeapNode **const tree = heap->tree;
88 const uint size = heap->size;
89
90 while (true) {
91 const uint l = HEAP_LEFT(i);
92 const uint r = HEAP_RIGHT(i);
93 uint smallest = i;
94
95 if (LIKELY(l < size) && HEAP_COMPARE(tree[l], tree[smallest])) {
96 smallest = l;
97 }
98 if (LIKELY(r < size) && HEAP_COMPARE(tree[r], tree[smallest])) {
99 smallest = r;
100 }
101
102 if (smallest == i) [[unlikely]] {
103 break;
104 }
105
106 heap_swap(heap, i, smallest);
107 i = smallest;
108 }
109}
110
111static void heap_up(Heap *heap, uint i)
112{
113 HeapNode **const tree = heap->tree;
114
115 while (i > 0) [[likely]] {
116 const uint p = HEAP_PARENT(i);
117
118 if (HEAP_COMPARE(tree[p], tree[i])) {
119 break;
120 }
121 heap_swap(heap, p, i);
122 i = p;
123 }
124}
125
127
128/* -------------------------------------------------------------------- */
131
133{
134 HeapNode_Chunk *chunk = static_cast<HeapNode_Chunk *>(
135 MEM_new_uninitialized(sizeof(HeapNode_Chunk) + (sizeof(HeapNode) * nodes_num), __func__));
136 chunk->prev = chunk_prev;
137 chunk->bufsize = nodes_num;
138 chunk->size = 0;
139 return chunk;
140}
141
143{
144 HeapNode *node;
145
146 if (heap->nodes.free) {
147 node = heap->nodes.free;
148 heap->nodes.free = static_cast<HeapNode *>(heap->nodes.free->ptr);
149 }
150 else {
151 HeapNode_Chunk *chunk = heap->nodes.chunk;
152 if (chunk->size == chunk->bufsize) [[unlikely]] {
153 chunk = heap->nodes.chunk = heap_node_alloc_chunk(HEAP_CHUNK_DEFAULT_NUM, chunk);
154 }
155 node = &chunk->buf[chunk->size++];
156 }
157
158 return node;
159}
160
161static void heap_node_free(Heap *heap, HeapNode *node)
162{
163 node->ptr = heap->nodes.free;
164 heap->nodes.free = node;
165}
166
168
169/* -------------------------------------------------------------------- */
172
174{
175 Heap *heap = MEM_new_zeroed<Heap>(__func__);
176 /* ensure we have at least one so we can keep doubling it */
177 heap->size = 0;
178 heap->bufsize = std::max(1u, reserve_num);
179 heap->tree = MEM_new_array_zeroed<HeapNode *>(heap->bufsize, "BLIHeapTree");
180
181 heap->nodes.chunk = heap_node_alloc_chunk(
182 (reserve_num > 1) ? reserve_num : HEAP_CHUNK_DEFAULT_NUM, nullptr);
183 heap->nodes.free = nullptr;
184
185 return heap;
186}
187
189{
190 return BLI_heap_new_ex(1);
191}
192
193void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
194{
195 if (ptrfreefp) {
196 uint i;
197
198 for (i = 0; i < heap->size; i++) {
199 ptrfreefp(heap->tree[i]->ptr);
200 }
201 }
202
203 HeapNode_Chunk *chunk = heap->nodes.chunk;
204 do {
205 HeapNode_Chunk *chunk_prev;
206 chunk_prev = chunk->prev;
207 MEM_delete(chunk);
208 chunk = chunk_prev;
209 } while (chunk);
210
211 MEM_delete(heap->tree);
212 MEM_delete(heap);
213}
214
215void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp)
216{
217 if (ptrfreefp) {
218 uint i;
219
220 for (i = 0; i < heap->size; i++) {
221 ptrfreefp(heap->tree[i]->ptr);
222 }
223 }
224 heap->size = 0;
225
226 /* Remove all except the last chunk */
227 while (heap->nodes.chunk->prev) {
228 HeapNode_Chunk *chunk_prev = heap->nodes.chunk->prev;
229 MEM_delete(heap->nodes.chunk);
230 heap->nodes.chunk = chunk_prev;
231 }
232 heap->nodes.chunk->size = 0;
233 heap->nodes.free = nullptr;
234}
235
236HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
237{
238 HeapNode *node;
239
240 if (heap->size >= heap->bufsize) [[unlikely]] {
241 heap->bufsize *= 2;
242 heap->tree = static_cast<HeapNode **>(
243 MEM_realloc_uninitialized(heap->tree, heap->bufsize * sizeof(*heap->tree)));
244 }
245
246 node = heap_node_alloc(heap);
247
248 node->ptr = ptr;
249 node->value = value;
250 node->index = heap->size;
251
252 heap->tree[node->index] = node;
253
254 heap->size++;
255
256 heap_up(heap, node->index);
257
258 return node;
259}
260
261void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr)
262{
263 if (*node_p == nullptr) {
264 *node_p = BLI_heap_insert(heap, value, ptr);
265 }
266 else {
267 BLI_heap_node_value_update_ptr(heap, *node_p, value, ptr);
268 }
269}
270
271bool BLI_heap_is_empty(const Heap *heap)
272{
273 return (heap->size == 0);
274}
275
277{
278 return heap->size;
279}
280
282{
283 return heap->tree[0];
284}
285
286float BLI_heap_top_value(const Heap *heap)
287{
288 BLI_assert(heap->size != 0);
289
290 return heap->tree[0]->value;
291}
292
294{
295 BLI_assert(heap->size != 0);
296
297 void *ptr = heap->tree[0]->ptr;
298
299 heap_node_free(heap, heap->tree[0]);
300
301 if (--heap->size) {
302 heap_swap(heap, 0, heap->size);
303 heap_down(heap, 0);
304 }
305
306 return ptr;
307}
308
310{
311 BLI_assert(heap->size != 0);
312
313 uint i = node->index;
314
315 while (i > 0) {
316 uint p = HEAP_PARENT(i);
317 heap_swap(heap, p, i);
318 i = p;
319 }
320
321 BLI_heap_pop_min(heap);
322}
323
325{
326 if (value < node->value) {
327 node->value = value;
328 heap_up(heap, node->index);
329 }
330 else if (value > node->value) {
331 node->value = value;
332 heap_down(heap, node->index);
333 }
334}
335
336void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr)
337{
338 node->ptr = ptr; /* only difference */
339 if (value < node->value) {
340 node->value = value;
341 heap_up(heap, node->index);
342 }
343 else if (value > node->value) {
344 node->value = value;
345 heap_down(heap, node->index);
346 }
347}
348
350{
351 return heap->value;
352}
353
354void *BLI_heap_node_ptr(const HeapNode *heap)
355{
356 return heap->ptr;
357}
358
359static bool heap_is_minheap(const Heap *heap, uint root)
360{
361 if (root < heap->size) {
362 if (heap->tree[root]->index != root) {
363 return false;
364 }
365 const uint l = HEAP_LEFT(root);
366 if (l < heap->size) {
367 if (HEAP_COMPARE(heap->tree[l], heap->tree[root]) || !heap_is_minheap(heap, l)) {
368 return false;
369 }
370 }
371 const uint r = HEAP_RIGHT(root);
372 if (r < heap->size) {
373 if (HEAP_COMPARE(heap->tree[r], heap->tree[root]) || !heap_is_minheap(heap, r)) {
374 return false;
375 }
376 }
377 }
378 return true;
379}
380bool BLI_heap_is_valid(const Heap *heap)
381{
382 return heap_is_minheap(heap, 0);
383}
384
386
387} // namespace blender
#define HEAP_PARENT(i)
Definition BLI_heap.cc:65
#define HEAP_CHUNK_DEFAULT_NUM
Definition BLI_heap.cc:45
#define HEAP_RIGHT(i)
Definition BLI_heap.cc:67
#define HEAP_LEFT(i)
Definition BLI_heap.cc:66
#define HEAP_COMPARE(a, b)
Definition BLI_heap.cc:68
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define LIKELY(x)
#define MEM_realloc_uninitialized(vmemh, len)
BMesh Iterators.
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)
Definition BLI_heap.cc:271
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
unsigned int BLI_heap_len(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:276
HeapNode * BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:281
unsigned int uint
Definition BKE_text.h:55
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
void void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr) ATTR_NONNULL(1
Definition BLI_heap.cc:336
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
void(*) HeapFreeFP(void *ptr)
Definition BLI_heap.hh:22
static bool heap_is_minheap(const Heap *heap, uint root)
Definition BLI_heap.cc:359
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)
Definition BLI_heap.cc:142
BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
Definition BLI_heap.cc:74
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:286
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
Definition BLI_heap.cc:261
static void heap_node_free(Heap *heap, HeapNode *node)
Definition BLI_heap.cc:161
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
Definition BLI_heap.cc:324
static void heap_down(Heap *heap, uint i)
Definition BLI_heap.cc:84
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:188
static HeapNode_Chunk * heap_node_alloc_chunk(uint nodes_num, HeapNode_Chunk *chunk_prev)
Definition BLI_heap.cc:132
bool BLI_heap_is_valid(const Heap *heap)
Definition BLI_heap.cc:380
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:215
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)
Definition BLI_heap.cc:354
static void heap_up(Heap *heap, uint i)
Definition BLI_heap.cc:111
void void float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:349
HeapNode_Chunk * prev
Definition BLI_heap.cc:32
struct blender::Heap::@075070100225061163037375163234225361134163364140 nodes
HeapNode ** tree
Definition BLI_heap.cc:51