Blender V5.3
BLI_heap_simple.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
14
15#include <algorithm>
16#include <cstdlib>
17
18#include "MEM_guardedalloc.h"
19
20#include "BLI_heap_simple.hh"
21#include "BLI_utildefines.hh"
22
23#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
24
25namespace blender {
26
27#define HEAP_PARENT(i) (((i) - 1) >> 1)
28
29/* -------------------------------------------------------------------- */
32
34 float value;
35 void *ptr;
36};
37
43
45
46/* -------------------------------------------------------------------- */
49
50static void heapsimple_down(HeapSimple *heap, uint start_i, const HeapSimpleNode *init)
51{
52#if 1
53 /* The compiler isn't smart enough to realize that all computations
54 * using index here can be modified to work with byte offset. */
55 uint8_t *const tree_buf = reinterpret_cast<uint8_t *>(heap->tree);
56
57# define OFFSET(i) (i * uint(sizeof(HeapSimpleNode)))
58# define NODE(offset) (*(HeapSimpleNode *)(tree_buf + (offset)))
59#else
60 HeapSimpleNode *const tree = heap->tree;
61
62# define OFFSET(i) (i)
63# define NODE(i) tree[i]
64#endif
65
66#define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
67
68 const uint size = OFFSET(heap->size);
69
70 /* Pull the active node values into locals. This allows spilling
71 * the data from registers instead of literally swapping nodes. */
72 float active_val = init->value;
73 void *active_ptr = init->ptr;
74
75 /* Prepare the first iteration and spill value. */
76 uint i = OFFSET(start_i);
77
78 NODE(i).value = active_val;
79
80 for (;;) {
81 const uint l = HEAP_LEFT_OFFSET(i);
82 const uint r = l + OFFSET(1); /* right */
83
84 /* Find the child with the smallest value. */
85 uint smallest = i;
86
87 if (LIKELY(l < size) && NODE(l).value < active_val) {
88 smallest = l;
89 }
90 if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
91 smallest = r;
92 }
93
94 if (smallest == i) [[unlikely]] {
95 break;
96 }
97
98 /* Move the smallest child into the current node.
99 * Skip padding: for some reason that makes it faster here. */
100 NODE(i).value = NODE(smallest).value;
101 NODE(i).ptr = NODE(smallest).ptr;
102
103 /* Proceed to next iteration and spill value. */
104 i = smallest;
105 NODE(i).value = active_val;
106 }
107
108 /* Spill the pointer into the final position of the node. */
109 NODE(i).ptr = active_ptr;
110
111#undef NODE
112#undef OFFSET
113#undef HEAP_LEFT_OFFSET
114}
115
116static void heapsimple_up(HeapSimple *heap, uint i, float active_val, void *active_ptr)
117{
118 HeapSimpleNode *const tree = heap->tree;
119
120 while (i > 0) [[likely]] {
121 const uint p = HEAP_PARENT(i);
122
123 if (active_val >= tree[p].value) {
124 break;
125 }
126
127 tree[i] = tree[p];
128 i = p;
129 }
130
131 tree[i].value = active_val;
132 tree[i].ptr = active_ptr;
133}
134
136
137/* -------------------------------------------------------------------- */
140
142{
143 HeapSimple *heap = MEM_new_zeroed<HeapSimple>(__func__);
144 /* ensure we have at least one so we can keep doubling it */
145 heap->size = 0;
146 heap->bufsize = std::max(1u, reserve_num);
147 heap->tree = MEM_new_array_zeroed<HeapSimpleNode>(heap->bufsize, "BLIHeapSimpleTree");
148 return heap;
149}
150
155
157{
158 if (ptrfreefp) {
159 for (uint i = 0; i < heap->size; i++) {
160 ptrfreefp(heap->tree[i].ptr);
161 }
162 }
163
164 MEM_delete(heap->tree);
165 MEM_delete(heap);
166}
167
169{
170 if (ptrfreefp) {
171 for (uint i = 0; i < heap->size; i++) {
172 ptrfreefp(heap->tree[i].ptr);
173 }
174 }
175
176 heap->size = 0;
177}
178
179void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr)
180{
181 if (heap->size >= heap->bufsize) [[unlikely]] {
182 heap->bufsize *= 2;
183 heap->tree = static_cast<HeapSimpleNode *>(
184 MEM_realloc_uninitialized(heap->tree, heap->bufsize * sizeof(*heap->tree)));
185 }
186
187 heapsimple_up(heap, heap->size++, value, ptr);
188}
189
191{
192 return (heap->size == 0);
193}
194
196{
197 return heap->size;
198}
199
201{
202 BLI_assert(heap->size != 0);
203
204 return heap->tree[0].value;
205}
206
208{
209 BLI_assert(heap->size != 0);
210
211 void *ptr = heap->tree[0].ptr;
212
213 if (--heap->size) {
214 heapsimple_down(heap, 0, &heap->tree[heap->size]);
215 }
216
217 return ptr;
218}
219
221
222} // namespace blender
#define HEAP_PARENT(i)
Definition BLI_heap.cc:65
#define HEAP_LEFT_OFFSET(i)
#define OFFSET(i)
#define NODE(offset)
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define LIKELY(x)
#define MEM_realloc_uninitialized(vmemh, len)
BMesh Iterators.
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)
unsigned int uint
Definition BKE_text.h:55
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)
unsigned char uint8_t
Definition BKE_text.h:79
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
HeapSimpleNode * tree