Blender  V3.3
BLI_heap_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 #include <cstring>
5 
6 #include "MEM_guardedalloc.h"
7 
8 #include "BLI_compiler_attrs.h"
9 #include "BLI_heap.h"
10 #include "BLI_rand.h"
11 #include "BLI_utildefines.h"
12 
13 #define SIZE 1024
14 
15 static void range_fl(float *array_tar, const int size)
16 {
17  float *array_pt = array_tar + (size - 1);
18  int i = size;
19  while (i--) {
20  *(array_pt--) = (float)i;
21  }
22 }
23 
24 TEST(heap, Empty)
25 {
26  Heap *heap;
27 
28  heap = BLI_heap_new();
29  EXPECT_TRUE(BLI_heap_is_empty(heap));
30  EXPECT_EQ(BLI_heap_len(heap), 0);
31  BLI_heap_free(heap, nullptr);
32 }
33 
34 TEST(heap, One)
35 {
36  Heap *heap;
37  const char *in = "test";
38 
39  heap = BLI_heap_new();
40 
41  BLI_heap_insert(heap, 0.0f, (void *)in);
42  EXPECT_FALSE(BLI_heap_is_empty(heap));
43  EXPECT_EQ(BLI_heap_len(heap), 1);
44  EXPECT_EQ(in, BLI_heap_pop_min(heap));
45  EXPECT_TRUE(BLI_heap_is_empty(heap));
46  EXPECT_EQ(BLI_heap_len(heap), 0);
47  BLI_heap_free(heap, nullptr);
48 }
49 
50 TEST(heap, Range)
51 {
52  const int items_total = SIZE;
53  Heap *heap = BLI_heap_new();
54  for (int in = 0; in < items_total; in++) {
55  BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
56  }
57  for (int out_test = 0; out_test < items_total; out_test++) {
58  EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
59  }
60  EXPECT_TRUE(BLI_heap_is_empty(heap));
61  BLI_heap_free(heap, nullptr);
62 }
63 
64 TEST(heap, RangeReverse)
65 {
66  const int items_total = SIZE;
67  Heap *heap = BLI_heap_new();
68  for (int in = 0; in < items_total; in++) {
69  BLI_heap_insert(heap, (float)-in, POINTER_FROM_INT(-in));
70  }
71  for (int out_test = items_total - 1; out_test >= 0; out_test--) {
72  EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
73  }
74  EXPECT_TRUE(BLI_heap_is_empty(heap));
75  BLI_heap_free(heap, nullptr);
76 }
77 
78 TEST(heap, RangeRemove)
79 {
80  const int items_total = SIZE;
81  Heap *heap = BLI_heap_new();
82  HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
83  for (int in = 0; in < items_total; in++) {
84  nodes[in] = BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
85  }
86  for (int i = 0; i < items_total; i += 2) {
87  BLI_heap_remove(heap, nodes[i]);
88  nodes[i] = nullptr;
89  }
90  for (int out_test = 1; out_test < items_total; out_test += 2) {
91  EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
92  }
93  EXPECT_TRUE(BLI_heap_is_empty(heap));
94  BLI_heap_free(heap, nullptr);
95  MEM_freeN(nodes);
96 }
97 
98 TEST(heap, Duplicates)
99 {
100  const int items_total = SIZE;
101  Heap *heap = BLI_heap_new();
102  for (int in = 0; in < items_total; in++) {
103  BLI_heap_insert(heap, 1.0f, nullptr);
104  }
105  for (int out_test = 0; out_test < items_total; out_test++) {
107  }
108  EXPECT_TRUE(BLI_heap_is_empty(heap));
109  BLI_heap_free(heap, nullptr);
110 }
111 
112 static void random_heap_helper(const int items_total, const int random_seed)
113 {
114  Heap *heap = BLI_heap_new();
115  float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__);
116  range_fl(values, items_total);
117  BLI_array_randomize(values, sizeof(float), items_total, random_seed);
118  for (int i = 0; i < items_total; i++) {
119  BLI_heap_insert(heap, values[i], POINTER_FROM_INT((int)values[i]));
120  }
121  for (int out_test = 0; out_test < items_total; out_test++) {
122  EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
123  }
124  EXPECT_TRUE(BLI_heap_is_empty(heap));
125  BLI_heap_free(heap, nullptr);
126  MEM_freeN(values);
127 }
128 
129 TEST(heap, Rand1)
130 {
131  random_heap_helper(1, 1234);
132 }
133 TEST(heap, Rand2)
134 {
135  random_heap_helper(2, 1234);
136 }
137 TEST(heap, Rand100)
138 {
139  random_heap_helper(100, 4321);
140 }
141 
142 TEST(heap, ReInsertSimple)
143 {
144  const int items_total = SIZE;
145  Heap *heap = BLI_heap_new();
146  HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
147  for (int in = 0; in < items_total; in++) {
148  nodes[in] = BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
149  }
150  for (int i = 0; i < items_total; i++) {
151  BLI_heap_node_value_update(heap, nodes[i], (float)(items_total + i));
152  }
153 
154  for (int out_test = 0; out_test < items_total; out_test++) {
155  EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
156  }
157 
158  EXPECT_TRUE(BLI_heap_is_empty(heap));
159  BLI_heap_free(heap, nullptr);
160  MEM_freeN(nodes);
161 }
162 
163 static void random_heap_reinsert_helper(const int items_total, const int random_seed)
164 {
165  Heap *heap = BLI_heap_new();
166  HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
167  for (int in = 0; in < items_total; in++) {
168  nodes[in] = BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
169  }
170  BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, random_seed);
171  for (int i = 0; i < items_total; i++) {
172  BLI_heap_node_value_update(heap, nodes[i], (float)i);
173  }
174  EXPECT_TRUE(BLI_heap_is_valid(heap));
175 
176  for (int out_test = 0; out_test < items_total; out_test++) {
177  HeapNode *node_top = BLI_heap_top(heap);
178  float out = BLI_heap_node_value(node_top);
180  EXPECT_EQ((float)out_test, out);
181  BLI_heap_pop_min(heap);
182  }
183  EXPECT_TRUE(BLI_heap_is_empty(heap));
184  BLI_heap_free(heap, nullptr);
185  MEM_freeN(nodes);
186 }
187 
188 TEST(heap, ReInsertRandom1)
189 {
191 }
192 TEST(heap, ReInsertRandom2)
193 {
195 }
196 TEST(heap, ReInsertRandom100)
197 {
198  random_heap_reinsert_helper(100, 4321);
199 }
200 TEST(heap, ReInsertRandom1024)
201 {
202  random_heap_reinsert_helper(1024, 9876);
203 }
204 TEST(heap, ReInsertRandom2048)
205 {
206  random_heap_reinsert_helper(2048, 5321);
207 }
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
A min-heap / priority queue ADT.
bool BLI_heap_is_valid(const Heap *heap)
Definition: BLI_heap.c:388
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:202
void void float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:357
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:279
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:301
unsigned int BLI_heap_len(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:284
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:294
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition: BLI_heap.c:245
HeapNode * BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: BLI_heap.c:289
Heap * BLI_heap_new(void) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:197
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
static void random_heap_helper(const int items_total, const int random_seed)
static void random_heap_reinsert_helper(const int items_total, const int random_seed)
TEST(heap, Empty)
#define SIZE
static void range_fl(float *array_tar, const int size)
Random number functions.
void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_num, unsigned int seed)
Definition: rand.cc:188
#define POINTER_FROM_INT(i)
#define POINTER_AS_INT(i)
Read Guarded memory(de)allocation.
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static const pxr::TfToken out("out", pxr::TfToken::Immortal)
Definition: BLI_heap.c:43