Blender  V3.3
BLI_heap_simple.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
13 #include <stdlib.h>
14 #include <string.h>
15 
16 #include "MEM_guardedalloc.h"
17 
18 #include "BLI_heap_simple.h"
19 #include "BLI_strict_flags.h"
20 #include "BLI_utildefines.h"
21 
22 #define HEAP_PARENT(i) (((i)-1) >> 1)
23 
24 /* -------------------------------------------------------------------- */
28 typedef struct HeapSimpleNode {
29  float value;
30  void *ptr;
32 
33 struct HeapSimple {
37 };
38 
41 /* -------------------------------------------------------------------- */
45 static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
46 {
47 #if 1
48  /* The compiler isn't smart enough to realize that all computations
49  * using index here can be modified to work with byte offset. */
50  uint8_t *const tree_buf = (uint8_t *)heap->tree;
51 
52 # define OFFSET(i) (i * (uint)sizeof(HeapSimpleNode))
53 # define NODE(offset) (*(HeapSimpleNode *)(tree_buf + (offset)))
54 #else
55  HeapSimpleNode *const tree = heap->tree;
56 
57 # define OFFSET(i) (i)
58 # define NODE(i) tree[i]
59 #endif
60 
61 #define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
62 
63  const uint size = OFFSET(heap->size);
64 
65  /* Pull the active node values into locals. This allows spilling
66  * the data from registers instead of literally swapping nodes. */
67  float active_val = init->value;
68  void *active_ptr = init->ptr;
69 
70  /* Prepare the first iteration and spill value. */
71  uint i = OFFSET(start_i);
72 
73  NODE(i).value = active_val;
74 
75  for (;;) {
76  const uint l = HEAP_LEFT_OFFSET(i);
77  const uint r = l + OFFSET(1); /* right */
78 
79  /* Find the child with the smallest value. */
80  uint smallest = i;
81 
82  if (LIKELY(l < size) && NODE(l).value < active_val) {
83  smallest = l;
84  }
85  if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
86  smallest = r;
87  }
88 
89  if (UNLIKELY(smallest == i)) {
90  break;
91  }
92 
93  /* Move the smallest child into the current node.
94  * Skip padding: for some reason that makes it faster here. */
95  NODE(i).value = NODE(smallest).value;
96  NODE(i).ptr = NODE(smallest).ptr;
97 
98  /* Proceed to next iteration and spill value. */
99  i = smallest;
100  NODE(i).value = active_val;
101  }
102 
103  /* Spill the pointer into the final position of the node. */
104  NODE(i).ptr = active_ptr;
105 
106 #undef NODE
107 #undef OFFSET
108 #undef HEAP_LEFT_OFFSET
109 }
110 
111 static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
112 {
113  HeapSimpleNode *const tree = heap->tree;
114 
115  while (LIKELY(i > 0)) {
116  const uint p = HEAP_PARENT(i);
117 
118  if (active_val >= tree[p].value) {
119  break;
120  }
121 
122  tree[i] = tree[p];
123  i = p;
124  }
125 
126  tree[i].value = active_val;
127  tree[i].ptr = active_ptr;
128 }
129 
132 /* -------------------------------------------------------------------- */
137 {
138  HeapSimple *heap = MEM_mallocN(sizeof(HeapSimple), __func__);
139  /* ensure we have at least one so we can keep doubling it */
140  heap->size = 0;
141  heap->bufsize = MAX2(1u, reserve_num);
142  heap->tree = MEM_mallocN(heap->bufsize * sizeof(HeapSimpleNode), "BLIHeapSimpleTree");
143  return heap;
144 }
145 
147 {
148  return BLI_heapsimple_new_ex(1);
149 }
150 
152 {
153  if (ptrfreefp) {
154  for (uint i = 0; i < heap->size; i++) {
155  ptrfreefp(heap->tree[i].ptr);
156  }
157  }
158 
159  MEM_freeN(heap->tree);
160  MEM_freeN(heap);
161 }
162 
164 {
165  if (ptrfreefp) {
166  for (uint i = 0; i < heap->size; i++) {
167  ptrfreefp(heap->tree[i].ptr);
168  }
169  }
170 
171  heap->size = 0;
172 }
173 
174 void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr)
175 {
176  if (UNLIKELY(heap->size >= heap->bufsize)) {
177  heap->bufsize *= 2;
178  heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
179  }
180 
181  heapsimple_up(heap, heap->size++, value, ptr);
182 }
183 
185 {
186  return (heap->size == 0);
187 }
188 
190 {
191  return heap->size;
192 }
193 
195 {
196  BLI_assert(heap->size != 0);
197 
198  return heap->tree[0].value;
199 }
200 
202 {
203  BLI_assert(heap->size != 0);
204 
205  void *ptr = heap->tree[0].ptr;
206 
207  if (--heap->size) {
208  heapsimple_down(heap, 0, &heap->tree[heap->size]);
209  }
210 
211  return ptr;
212 }
213 
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define HEAP_LEFT_OFFSET(i)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr)
static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
#define OFFSET(i)
#define NODE(offset)
bool BLI_heapsimple_is_empty(const HeapSimple *heap)
#define HEAP_PARENT(i)
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
HeapSimple * BLI_heapsimple_new_ex(uint reserve_num)
float BLI_heapsimple_top_value(const HeapSimple *heap)
static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
HeapSimple * BLI_heapsimple_new(void)
uint BLI_heapsimple_len(const HeapSimple *heap)
void * BLI_heapsimple_pop_min(HeapSimple *heap)
struct HeapSimpleNode HeapSimpleNode
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp)
A min-heap / priority queue ADT.
void(* HeapSimpleFreeFP)(void *ptr)
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 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
void * tree
define("MAT_AOV_SUPPORT") .image_array_out(6
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
unsigned char uint8_t
Definition: stdint.h:78
HeapSimpleNode * tree
PointerRNA * ptr
Definition: wm_files.c:3480