Merge branch 'blender2.7'
[blender.git] / tests / gtests / blenlib / BLI_edgehash_test.cc
1 /* Apache License, Version 2.0 */
2
3 #include "testing/testing.h"
4 #include <vector>
5 #include <algorithm>
6
7 extern "C" {
8 #include "BLI_utildefines.h"
9 #include "BLI_edgehash.h"
10 }
11
12 #define VALUE_1 POINTER_FROM_INT(1)
13 #define VALUE_2 POINTER_FROM_INT(2)
14 #define VALUE_3 POINTER_FROM_INT(3)
15
16 TEST(edgehash, InsertIncreasesLength)
17 {
18         EdgeHash *eh = BLI_edgehash_new(__func__);
19
20         ASSERT_EQ(BLI_edgehash_len(eh), 0);
21         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
22         ASSERT_EQ(BLI_edgehash_len(eh), 1);
23
24         BLI_edgehash_free(eh, nullptr);
25 }
26
27 TEST(edgehash, ReinsertNewIncreasesLength)
28 {
29         EdgeHash *eh = BLI_edgehash_new(__func__);
30
31         ASSERT_EQ(BLI_edgehash_len(eh), 0);
32         BLI_edgehash_reinsert(eh, 1, 2, VALUE_1);
33         ASSERT_EQ(BLI_edgehash_len(eh), 1);
34
35         BLI_edgehash_free(eh, nullptr);
36 }
37
38 TEST(edgehash, ReinsertExistingDoesNotIncreaseLength)
39 {
40         EdgeHash *eh = BLI_edgehash_new(__func__);
41
42         ASSERT_EQ(BLI_edgehash_len(eh), 0);
43         BLI_edgehash_reinsert(eh, 1, 2, VALUE_1);
44         ASSERT_EQ(BLI_edgehash_len(eh), 1);
45         BLI_edgehash_reinsert(eh, 1, 2, VALUE_2);
46         ASSERT_EQ(BLI_edgehash_len(eh), 1);
47         BLI_edgehash_reinsert(eh, 2, 1, VALUE_2);
48         ASSERT_EQ(BLI_edgehash_len(eh), 1);
49
50         BLI_edgehash_free(eh, nullptr);
51 }
52
53 TEST(edgehash, ReinsertCanChangeValue)
54 {
55         EdgeHash *eh = BLI_edgehash_new(__func__);
56
57         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
58         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1);
59         BLI_edgehash_reinsert(eh, 2, 1, VALUE_2);
60         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2);
61         BLI_edgehash_reinsert(eh, 1, 2, VALUE_3);
62         ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_3);
63
64         BLI_edgehash_free(eh, nullptr);
65 }
66
67 TEST(edgehash, LookupExisting)
68 {
69         EdgeHash *eh = BLI_edgehash_new(__func__);
70
71         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
72         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1);
73         ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_1);
74
75         BLI_edgehash_free(eh, nullptr);
76 }
77
78 TEST(edgehash, LookupNonExisting)
79 {
80         EdgeHash *eh = BLI_edgehash_new(__func__);
81
82         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), nullptr);
83
84         BLI_edgehash_free(eh, nullptr);
85 }
86
87 TEST(edgehash, LookupNonExistingWithDefault)
88 {
89         EdgeHash *eh = BLI_edgehash_new(__func__);
90
91         ASSERT_EQ(BLI_edgehash_lookup_default(eh, 1, 2, VALUE_1), VALUE_1);
92
93         BLI_edgehash_free(eh, nullptr);
94 }
95
96 TEST(edgehash, LookupExistingWithDefault)
97 {
98         EdgeHash *eh = BLI_edgehash_new(__func__);
99
100         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
101         ASSERT_EQ(BLI_edgehash_lookup_default(eh, 1, 2, VALUE_2), VALUE_1);
102
103         BLI_edgehash_free(eh, nullptr);
104 }
105
106 TEST(edgehash, LookupPExisting)
107 {
108         EdgeHash *eh = BLI_edgehash_new(__func__);
109
110         void *value = VALUE_1;
111         BLI_edgehash_insert(eh, 1, 2, value);
112         void **value_p = BLI_edgehash_lookup_p(eh, 1, 2);
113         ASSERT_EQ(*value_p, VALUE_1);
114         *value_p = VALUE_2;
115         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2);
116
117         BLI_edgehash_free(eh, nullptr);
118 }
119
120 TEST(edgehash, LookupPNonExisting)
121 {
122         EdgeHash *eh = BLI_edgehash_new(__func__);
123
124         ASSERT_EQ(BLI_edgehash_lookup_p(eh, 1, 2), nullptr);
125
126         BLI_edgehash_free(eh, nullptr);
127 }
128
129 TEST(edgehash, EnsurePNonExisting)
130 {
131         EdgeHash *eh = BLI_edgehash_new(__func__);
132
133         void **value_p;
134         bool existed = BLI_edgehash_ensure_p(eh, 1, 2, &value_p);
135         ASSERT_FALSE(existed);
136         *value_p = VALUE_1;
137         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1);
138
139         BLI_edgehash_free(eh, nullptr);
140 }
141
142 TEST(edgehash, EnsurePExisting)
143 {
144         EdgeHash *eh = BLI_edgehash_new(__func__);
145
146         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
147         void **value_p;
148         bool existed = BLI_edgehash_ensure_p(eh, 1, 2, &value_p);
149         ASSERT_TRUE(existed);
150         ASSERT_EQ(*value_p, VALUE_1);
151         *value_p = VALUE_2;
152         ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2);
153
154         BLI_edgehash_free(eh, nullptr);
155 }
156
157 TEST(edgehash, RemoveExistingDecreasesLength)
158 {
159         EdgeHash *eh = BLI_edgehash_new(__func__);
160
161         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
162         ASSERT_EQ(BLI_edgehash_len(eh), 1);
163         bool has_been_removed = BLI_edgehash_remove(eh, 1, 2, nullptr);
164         ASSERT_EQ(BLI_edgehash_len(eh), 0);
165         ASSERT_TRUE(has_been_removed);
166
167         BLI_edgehash_free(eh, nullptr);
168 }
169
170 TEST(edgehash, RemoveNonExistingDoesNotDecreaseLength)
171 {
172         EdgeHash *eh = BLI_edgehash_new(__func__);
173
174         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
175         ASSERT_EQ(BLI_edgehash_len(eh), 1);
176         bool has_been_removed = BLI_edgehash_remove(eh, 4, 5, nullptr);
177         ASSERT_EQ(BLI_edgehash_len(eh), 1);
178         ASSERT_FALSE(has_been_removed);
179
180         BLI_edgehash_free(eh, nullptr);
181 }
182
183 TEST(edgehash, PopKeyTwice)
184 {
185         EdgeHash *eh = BLI_edgehash_new(__func__);
186
187         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
188         ASSERT_EQ(BLI_edgehash_popkey(eh, 1, 2), VALUE_1);
189         ASSERT_EQ(BLI_edgehash_popkey(eh, 1, 2), nullptr);
190
191         BLI_edgehash_free(eh, nullptr);
192 }
193
194 TEST(edgehash, LookupInvertedIndices)
195 {
196         EdgeHash *eh = BLI_edgehash_new(__func__);
197
198         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
199         ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_1);
200
201         BLI_edgehash_free(eh, nullptr);
202 }
203
204 TEST(edgehash, HasKeyExisting)
205 {
206         EdgeHash *eh = BLI_edgehash_new(__func__);
207
208         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
209         ASSERT_TRUE(BLI_edgehash_haskey(eh, 1, 2));
210         ASSERT_TRUE(BLI_edgehash_haskey(eh, 2, 1));
211
212         BLI_edgehash_free(eh, nullptr);
213 }
214
215 TEST(edgehash, HasKeyNonExisting)
216 {
217         EdgeHash *eh = BLI_edgehash_new(__func__);
218
219         ASSERT_FALSE(BLI_edgehash_haskey(eh, 1, 2));
220
221         BLI_edgehash_free(eh, nullptr);
222 }
223
224 TEST(edgehash, ClearSetsLengthToZero)
225 {
226         EdgeHash *eh = BLI_edgehash_new(__func__);
227
228         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
229         BLI_edgehash_insert(eh, 1, 2, VALUE_2);
230         ASSERT_EQ(BLI_edgehash_len(eh), 2);
231         BLI_edgehash_clear(eh, nullptr);
232         ASSERT_EQ(BLI_edgehash_len(eh), 0);
233
234         BLI_edgehash_free(eh, nullptr);
235 }
236
237 TEST(edgehash, IteratorFindsAllValues)
238 {
239         EdgeHash *eh = BLI_edgehash_new(__func__);
240
241         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
242         BLI_edgehash_insert(eh, 1, 3, VALUE_2);
243         BLI_edgehash_insert(eh, 1, 4, VALUE_3);
244
245         EdgeHashIterator *ehi = BLI_edgehashIterator_new(eh);
246         auto a = BLI_edgehashIterator_getValue(ehi);
247         BLI_edgehashIterator_step(ehi);
248         auto b = BLI_edgehashIterator_getValue(ehi);
249         BLI_edgehashIterator_step(ehi);
250         auto c = BLI_edgehashIterator_getValue(ehi);
251         BLI_edgehashIterator_step(ehi);
252
253         ASSERT_NE(a, b);
254         ASSERT_NE(b, c);
255         ASSERT_NE(a, c);
256         ASSERT_TRUE(ELEM(a, VALUE_1, VALUE_2, VALUE_3));
257         ASSERT_TRUE(ELEM(b, VALUE_1, VALUE_2, VALUE_3));
258         ASSERT_TRUE(ELEM(c, VALUE_1, VALUE_2, VALUE_3));
259
260         BLI_edgehashIterator_free(ehi);
261         BLI_edgehash_free(eh, nullptr);
262 }
263
264 TEST(edgehash, IterateIsDone)
265 {
266         EdgeHash *eh = BLI_edgehash_new(__func__);
267
268         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
269         BLI_edgehash_insert(eh, 1, 3, VALUE_2);
270         BLI_edgehash_insert(eh, 1, 4, VALUE_3);
271
272         EdgeHashIterator *ehi = BLI_edgehashIterator_new(eh);
273         ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi));
274         BLI_edgehashIterator_step(ehi);
275         ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi));
276         BLI_edgehashIterator_step(ehi);
277         ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi));
278         BLI_edgehashIterator_step(ehi);
279         ASSERT_TRUE(BLI_edgehashIterator_isDone(ehi));
280
281         BLI_edgehashIterator_free(ehi);
282         BLI_edgehash_free(eh, nullptr);
283 }
284
285 TEST(edgehash, DoubleRemove)
286 {
287         EdgeHash *eh = BLI_edgehash_new(__func__);
288
289         BLI_edgehash_insert(eh, 1, 2, VALUE_1);
290         BLI_edgehash_insert(eh, 1, 3, VALUE_2);
291         BLI_edgehash_insert(eh, 1, 4, VALUE_3);
292         ASSERT_EQ(BLI_edgehash_len(eh), 3);
293
294         BLI_edgehash_remove(eh, 1, 2, nullptr);
295         BLI_edgehash_remove(eh, 1, 3, nullptr);
296         ASSERT_EQ(BLI_edgehash_len(eh), 1);
297
298         BLI_edgehash_free(eh, nullptr);
299 }
300
301 struct Edge {
302         uint v1, v2;
303 };
304
305 TEST(edgehash, StressTest)
306 {
307         std::srand(0);
308         int amount = 10000;
309
310         std::vector<Edge> edges;
311         for (int i = 0; i < amount; i++) {
312                 edges.push_back({(uint)i, amount + (uint)std::rand() % 12345});
313         }
314
315         EdgeHash *eh = BLI_edgehash_new(__func__);
316
317         /* first insert all the edges */
318         for (int i = 0; i < edges.size(); i++) {
319                 BLI_edgehash_insert(eh, edges[i].v1, edges[i].v2, POINTER_FROM_INT(i));
320         }
321
322         std::vector<Edge> shuffled = edges;
323         std::random_shuffle(shuffled.begin(), shuffled.end());
324
325         /* then remove half of them */
326         int remove_until = shuffled.size() / 2;
327         for (int i = 0; i < remove_until; i++) {
328                 BLI_edgehash_remove(eh, shuffled[i].v2, shuffled[i].v1, nullptr);
329         }
330
331         ASSERT_EQ(BLI_edgehash_len(eh), edges.size() - remove_until);
332
333         /* check if the right ones have been removed */
334         for (int i = 0; i < shuffled.size(); i++) {
335                 bool haskey = BLI_edgehash_haskey(eh, shuffled[i].v1, shuffled[i].v2);
336                 if (i < remove_until) ASSERT_FALSE(haskey);
337                 else                  ASSERT_TRUE(haskey);
338         }
339
340         /* reinsert all edges */
341         for (int i = 0; i < edges.size(); i++) {
342                 BLI_edgehash_reinsert(eh, edges[i].v1, edges[i].v2, POINTER_FROM_INT(i));
343         }
344
345         ASSERT_EQ(BLI_edgehash_len(eh), edges.size());
346
347         /* pop all edges */
348         for (int i = 0; i < edges.size(); i++) {
349                 int value = POINTER_AS_INT(BLI_edgehash_popkey(eh, edges[i].v1, edges[i].v2));
350                 ASSERT_EQ(i, value);
351         }
352
353         ASSERT_EQ(BLI_edgehash_len(eh), 0);
354
355         BLI_edgehash_free(eh, nullptr);
356 }
357
358 TEST(edgeset, AddNonExistingIncreasesLength)
359 {
360         EdgeSet *es = BLI_edgeset_new(__func__);
361
362         ASSERT_EQ(BLI_edgeset_len(es), 0);
363         BLI_edgeset_add(es, 1, 2);
364         ASSERT_EQ(BLI_edgeset_len(es), 1);
365         BLI_edgeset_add(es, 1, 3);
366         ASSERT_EQ(BLI_edgeset_len(es), 2);
367         BLI_edgeset_add(es, 1, 4);
368         ASSERT_EQ(BLI_edgeset_len(es), 3);
369
370         BLI_edgeset_free(es);
371 }
372
373 TEST(edgeset, AddExistingDoesNotIncreaseLength)
374 {
375         EdgeSet *es = BLI_edgeset_new(__func__);
376
377         ASSERT_EQ(BLI_edgeset_len(es), 0);
378         BLI_edgeset_add(es, 1, 2);
379         ASSERT_EQ(BLI_edgeset_len(es), 1);
380         BLI_edgeset_add(es, 2, 1);
381         ASSERT_EQ(BLI_edgeset_len(es), 1);
382         BLI_edgeset_add(es, 1, 2);
383         ASSERT_EQ(BLI_edgeset_len(es), 1);
384
385         BLI_edgeset_free(es);
386 }
387
388 TEST(edgeset, HasKeyNonExisting)
389 {
390         EdgeSet *es = BLI_edgeset_new(__func__);
391
392         ASSERT_FALSE(BLI_edgeset_haskey(es, 1, 2));
393
394         BLI_edgeset_free(es);
395 }
396
397 TEST(edgeset, HasKeyExisting)
398 {
399         EdgeSet *es = BLI_edgeset_new(__func__);
400
401         BLI_edgeset_insert(es, 1, 2);
402         ASSERT_TRUE(BLI_edgeset_haskey(es, 1, 2));
403
404         BLI_edgeset_free(es);
405 }