Blender  V3.3
BLI_heap.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include <stdlib.h>
10 #include <string.h>
11 
12 #include "MEM_guardedalloc.h"
13 
14 #include "BLI_heap.h"
15 #include "BLI_strict_flags.h"
16 #include "BLI_utildefines.h"
17 
18 /***/
19 
20 struct HeapNode {
21  float value;
23  void *ptr;
24 };
25 
30  struct HeapNode buf[0];
31 };
32 
40 #define HEAP_CHUNK_DEFAULT_NUM \
41  ((uint)((MEM_SIZE_OPTIMAL((1 << 16) - sizeof(struct HeapNode_Chunk))) / sizeof(HeapNode)))
42 
43 struct Heap {
47 
48  struct {
49  /* Always keep at least one chunk (never NULL) */
51  /* when NULL, allocate a new chunk */
53  } nodes;
54 };
55 
56 /* -------------------------------------------------------------------- */
60 #define HEAP_PARENT(i) (((i)-1) >> 1)
61 #define HEAP_LEFT(i) (((i) << 1) + 1)
62 #define HEAP_RIGHT(i) (((i) << 1) + 2)
63 #define HEAP_COMPARE(a, b) ((a)->value < (b)->value)
64 
65 #if 0 /* UNUSED */
66 # define HEAP_EQUALS(a, b) ((a)->value == (b)->value)
67 #endif
68 
69 BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
70 {
71 #if 1
72  HeapNode **tree = heap->tree;
73  HeapNode *pi = tree[i], *pj = tree[j];
74  pi->index = j;
75  tree[j] = pi;
76  pj->index = i;
77  tree[i] = pj;
78 #elif 0
79  SWAP(uint, heap->tree[i]->index, heap->tree[j]->index);
80  SWAP(HeapNode *, heap->tree[i], heap->tree[j]);
81 #else
82  HeapNode **tree = heap->tree;
83  union {
84  uint index;
85  HeapNode *node;
86  } tmp;
87  SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index);
88  SWAP_TVAL(tmp.node, tree[i], tree[j]);
89 #endif
90 }
91 
92 static void heap_down(Heap *heap, uint i)
93 {
94  /* size won't change in the loop */
95  HeapNode **const tree = heap->tree;
96  const uint size = heap->size;
97 
98  while (1) {
99  const uint l = HEAP_LEFT(i);
100  const uint r = HEAP_RIGHT(i);
101  uint smallest = i;
102 
103  if (LIKELY(l < size) && HEAP_COMPARE(tree[l], tree[smallest])) {
104  smallest = l;
105  }
106  if (LIKELY(r < size) && HEAP_COMPARE(tree[r], tree[smallest])) {
107  smallest = r;
108  }
109 
110  if (UNLIKELY(smallest == i)) {
111  break;
112  }
113 
114  heap_swap(heap, i, smallest);
115  i = smallest;
116  }
117 }
118 
119 static void heap_up(Heap *heap, uint i)
120 {
121  HeapNode **const tree = heap->tree;
122 
123  while (LIKELY(i > 0)) {
124  const uint p = HEAP_PARENT(i);
125 
126  if (HEAP_COMPARE(tree[p], tree[i])) {
127  break;
128  }
129  heap_swap(heap, p, i);
130  i = p;
131  }
132 }
133 
136 /* -------------------------------------------------------------------- */
140 static struct HeapNode_Chunk *heap_node_alloc_chunk(uint nodes_num,
141  struct HeapNode_Chunk *chunk_prev)
142 {
143  struct HeapNode_Chunk *chunk = MEM_mallocN(
144  sizeof(struct HeapNode_Chunk) + (sizeof(HeapNode) * nodes_num), __func__);
145  chunk->prev = chunk_prev;
146  chunk->bufsize = nodes_num;
147  chunk->size = 0;
148  return chunk;
149 }
150 
151 static struct HeapNode *heap_node_alloc(Heap *heap)
152 {
153  HeapNode *node;
154 
155  if (heap->nodes.free) {
156  node = heap->nodes.free;
157  heap->nodes.free = heap->nodes.free->ptr;
158  }
159  else {
160  struct HeapNode_Chunk *chunk = heap->nodes.chunk;
161  if (UNLIKELY(chunk->size == chunk->bufsize)) {
163  }
164  node = &chunk->buf[chunk->size++];
165  }
166 
167  return node;
168 }
169 
170 static void heap_node_free(Heap *heap, HeapNode *node)
171 {
172  node->ptr = heap->nodes.free;
173  heap->nodes.free = node;
174 }
175 
178 /* -------------------------------------------------------------------- */
182 Heap *BLI_heap_new_ex(uint reserve_num)
183 {
184  Heap *heap = MEM_mallocN(sizeof(Heap), __func__);
185  /* ensure we have at least one so we can keep doubling it */
186  heap->size = 0;
187  heap->bufsize = MAX2(1u, reserve_num);
188  heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapNode *), "BLIHeapTree");
189 
191  (reserve_num > 1) ? reserve_num : HEAP_CHUNK_DEFAULT_NUM, NULL);
192  heap->nodes.free = NULL;
193 
194  return heap;
195 }
196 
198 {
199  return BLI_heap_new_ex(1);
200 }
201 
202 void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
203 {
204  if (ptrfreefp) {
205  uint i;
206 
207  for (i = 0; i < heap->size; i++) {
208  ptrfreefp(heap->tree[i]->ptr);
209  }
210  }
211 
212  struct HeapNode_Chunk *chunk = heap->nodes.chunk;
213  do {
214  struct HeapNode_Chunk *chunk_prev;
215  chunk_prev = chunk->prev;
216  MEM_freeN(chunk);
217  chunk = chunk_prev;
218  } while (chunk);
219 
220  MEM_freeN(heap->tree);
221  MEM_freeN(heap);
222 }
223 
224 void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp)
225 {
226  if (ptrfreefp) {
227  uint i;
228 
229  for (i = 0; i < heap->size; i++) {
230  ptrfreefp(heap->tree[i]->ptr);
231  }
232  }
233  heap->size = 0;
234 
235  /* Remove all except the last chunk */
236  while (heap->nodes.chunk->prev) {
237  struct HeapNode_Chunk *chunk_prev = heap->nodes.chunk->prev;
238  MEM_freeN(heap->nodes.chunk);
239  heap->nodes.chunk = chunk_prev;
240  }
241  heap->nodes.chunk->size = 0;
242  heap->nodes.free = NULL;
243 }
244 
245 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
246 {
247  HeapNode *node;
248 
249  if (UNLIKELY(heap->size >= heap->bufsize)) {
250  heap->bufsize *= 2;
251  heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
252  }
253 
254  node = heap_node_alloc(heap);
255 
256  node->ptr = ptr;
257  node->value = value;
258  node->index = heap->size;
259 
260  heap->tree[node->index] = node;
261 
262  heap->size++;
263 
264  heap_up(heap, node->index);
265 
266  return node;
267 }
268 
269 void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr)
270 {
271  if (*node_p == NULL) {
272  *node_p = BLI_heap_insert(heap, value, ptr);
273  }
274  else {
275  BLI_heap_node_value_update_ptr(heap, *node_p, value, ptr);
276  }
277 }
278 
279 bool BLI_heap_is_empty(const Heap *heap)
280 {
281  return (heap->size == 0);
282 }
283 
284 uint BLI_heap_len(const Heap *heap)
285 {
286  return heap->size;
287 }
288 
290 {
291  return heap->tree[0];
292 }
293 
294 float BLI_heap_top_value(const Heap *heap)
295 {
296  BLI_assert(heap->size != 0);
297 
298  return heap->tree[0]->value;
299 }
300 
301 void *BLI_heap_pop_min(Heap *heap)
302 {
303  BLI_assert(heap->size != 0);
304 
305  void *ptr = heap->tree[0]->ptr;
306 
307  heap_node_free(heap, heap->tree[0]);
308 
309  if (--heap->size) {
310  heap_swap(heap, 0, heap->size);
311  heap_down(heap, 0);
312  }
313 
314  return ptr;
315 }
316 
318 {
319  BLI_assert(heap->size != 0);
320 
321  uint i = node->index;
322 
323  while (i > 0) {
324  uint p = HEAP_PARENT(i);
325  heap_swap(heap, p, i);
326  i = p;
327  }
328 
329  BLI_heap_pop_min(heap);
330 }
331 
332 void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value)
333 {
334  if (value < node->value) {
335  node->value = value;
336  heap_up(heap, node->index);
337  }
338  else if (value > node->value) {
339  node->value = value;
340  heap_down(heap, node->index);
341  }
342 }
343 
344 void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr)
345 {
346  node->ptr = ptr; /* only difference */
347  if (value < node->value) {
348  node->value = value;
349  heap_up(heap, node->index);
350  }
351  else if (value > node->value) {
352  node->value = value;
353  heap_down(heap, node->index);
354  }
355 }
356 
357 float BLI_heap_node_value(const HeapNode *heap)
358 {
359  return heap->value;
360 }
361 
362 void *BLI_heap_node_ptr(const HeapNode *heap)
363 {
364  return heap->ptr;
365 }
366 
367 static bool heap_is_minheap(const Heap *heap, uint root)
368 {
369  if (root < heap->size) {
370  if (heap->tree[root]->index != root) {
371  return false;
372  }
373  const uint l = HEAP_LEFT(root);
374  if (l < heap->size) {
375  if (HEAP_COMPARE(heap->tree[l], heap->tree[root]) || !heap_is_minheap(heap, l)) {
376  return false;
377  }
378  }
379  const uint r = HEAP_RIGHT(root);
380  if (r < heap->size) {
381  if (HEAP_COMPARE(heap->tree[r], heap->tree[root]) || !heap_is_minheap(heap, r)) {
382  return false;
383  }
384  }
385  }
386  return true;
387 }
388 bool BLI_heap_is_valid(const Heap *heap)
389 {
390  return heap_is_minheap(heap, 0);
391 }
392 
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
static struct HeapNode * heap_node_alloc(Heap *heap)
Definition: BLI_heap.c:151
bool BLI_heap_is_valid(const Heap *heap)
Definition: BLI_heap.c:388
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr)
Definition: BLI_heap.c:269
void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr)
Definition: BLI_heap.c:344
BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
Definition: BLI_heap.c:69
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
Definition: BLI_heap.c:202
static void heap_down(Heap *heap, uint i)
Definition: BLI_heap.c:92
#define HEAP_PARENT(i)
Definition: BLI_heap.c:60
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp)
Definition: BLI_heap.c:224
bool BLI_heap_is_empty(const Heap *heap)
Definition: BLI_heap.c:279
void BLI_heap_remove(Heap *heap, HeapNode *node)
Definition: BLI_heap.c:317
static void heap_up(Heap *heap, uint i)
Definition: BLI_heap.c:119
uint BLI_heap_len(const Heap *heap)
Definition: BLI_heap.c:284
Heap * BLI_heap_new_ex(uint reserve_num)
Definition: BLI_heap.c:182
static void heap_node_free(Heap *heap, HeapNode *node)
Definition: BLI_heap.c:170
static bool heap_is_minheap(const Heap *heap, uint root)
Definition: BLI_heap.c:367
Heap * BLI_heap_new(void)
Definition: BLI_heap.c:197
static struct HeapNode_Chunk * heap_node_alloc_chunk(uint nodes_num, struct HeapNode_Chunk *chunk_prev)
Definition: BLI_heap.c:140
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr)
Definition: BLI_heap.c:245
float BLI_heap_node_value(const HeapNode *heap)
Definition: BLI_heap.c:357
#define HEAP_CHUNK_DEFAULT_NUM
Definition: BLI_heap.c:40
void * BLI_heap_pop_min(Heap *heap)
Definition: BLI_heap.c:301
#define HEAP_RIGHT(i)
Definition: BLI_heap.c:62
#define HEAP_LEFT(i)
Definition: BLI_heap.c:61
HeapNode * BLI_heap_top(const Heap *heap)
Definition: BLI_heap.c:289
#define HEAP_COMPARE(a, b)
Definition: BLI_heap.c:63
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value)
Definition: BLI_heap.c:332
float BLI_heap_top_value(const Heap *heap)
Definition: BLI_heap.c:294
void * BLI_heap_node_ptr(const HeapNode *heap)
Definition: BLI_heap.c:362
A min-heap / priority queue ADT.
void(* HeapFreeFP)(void *ptr)
Definition: BLI_heap.h:21
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define SWAP(type, a, b)
#define SWAP_TVAL(tval, a, b)
#define MAX2(a, b)
#define UNLIKELY(x)
#define LIKELY(x)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble GLdouble r _GL_VOID_RET _GL_VOID GLfloat GLfloat r _GL_VOID_RET _GL_VOID GLint GLint r _GL_VOID_RET _GL_VOID GLshort GLshort r _GL_VOID_RET _GL_VOID GLdouble GLdouble r
Read Guarded memory(de)allocation.
#define MEM_reallocN(vmemh, len)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
OperationNode * node
void * tree
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
struct HeapNode buf[0]
Definition: BLI_heap.c:30
uint bufsize
Definition: BLI_heap.c:29
struct HeapNode_Chunk * prev
Definition: BLI_heap.c:27
void * ptr
Definition: BLI_heap.c:23
float value
Definition: BLI_heap.c:21
uint index
Definition: BLI_heap.c:22
Definition: BLI_heap.c:43
HeapNode ** tree
Definition: BLI_heap.c:46
struct Heap::@124 nodes
struct HeapNode_Chunk * chunk
Definition: BLI_heap.c:50
uint size
Definition: BLI_heap.c:44
HeapNode * free
Definition: BLI_heap.c:52
uint bufsize
Definition: BLI_heap.c:45
PointerRNA * ptr
Definition: wm_files.c:3480