1 /* Apache License, Version 2.0 */
2
3 #include "testing/testing.h"
4 #include <string.h>
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
range_fl(float * array_tar,const int size)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
TEST(heap,Empty)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, NULL);
32 }
33
TEST(heap,One)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, NULL);
48 }
49
TEST(heap,Range)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, NULL);
62 }
63
TEST(heap,RangeReverse)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, NULL);
76 }
77
TEST(heap,RangeRemove)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] = NULL;
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, NULL);
95 MEM_freeN(nodes);
96 }
97
TEST(heap,Duplicates)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, 0);
104 }
105 for (int out_test = 0; out_test < items_total; out_test++) {
106 EXPECT_EQ(0, POINTER_AS_INT(BLI_heap_pop_min(heap)));
107 }
108 EXPECT_TRUE(BLI_heap_is_empty(heap));
109 BLI_heap_free(heap, NULL);
110 }
111
random_heap_helper(const int items_total,const int random_seed)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, NULL);
126 MEM_freeN(values);
127 }
128
TEST(heap,Rand1)129 TEST(heap, Rand1)
130 {
131 random_heap_helper(1, 1234);
132 }
TEST(heap,Rand2)133 TEST(heap, Rand2)
134 {
135 random_heap_helper(2, 1234);
136 }
TEST(heap,Rand100)137 TEST(heap, Rand100)
138 {
139 random_heap_helper(100, 4321);
140 }
141
TEST(heap,ReInsertSimple)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, NULL);
160 MEM_freeN(nodes);
161 }
162
random_heap_reinsert_helper(const int items_total,const int random_seed)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);
179 EXPECT_EQ(out, BLI_heap_top_value(heap));
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, NULL);
185 MEM_freeN(nodes);
186 }
187
TEST(heap,ReInsertRandom1)188 TEST(heap, ReInsertRandom1)
189 {
190 random_heap_reinsert_helper(1, 1234);
191 }
TEST(heap,ReInsertRandom2)192 TEST(heap, ReInsertRandom2)
193 {
194 random_heap_reinsert_helper(2, 1234);
195 }
TEST(heap,ReInsertRandom100)196 TEST(heap, ReInsertRandom100)
197 {
198 random_heap_reinsert_helper(100, 4321);
199 }
TEST(heap,ReInsertRandom1024)200 TEST(heap, ReInsertRandom1024)
201 {
202 random_heap_reinsert_helper(1024, 9876);
203 }
TEST(heap,ReInsertRandom2048)204 TEST(heap, ReInsertRandom2048)
205 {
206 random_heap_reinsert_helper(2048, 5321);
207 }
208