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