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