Blender  V3.3
BLI_ghash_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
5 #define GHASH_INTERNAL_API
6 
7 #include "BLI_ghash.h"
8 #include "BLI_rand.h"
9 #include "BLI_utildefines.h"
10 
11 #define TESTCASE_SIZE 10000
12 
13 /* Only keeping this in case here, for now. */
14 #define PRINTF_GHASH_STATS(_gh) \
15  { \
16  double q, lf, var, pempty, poverloaded; \
17  int bigb; \
18  q = BLI_ghash_calc_quality_ex((_gh), &lf, &var, &pempty, &poverloaded, &bigb); \
19  printf( \
20  "GHash stats (%d entries):\n\t" \
21  "Quality (the lower the better): %f\n\tVariance (the lower the better): %f\n\tLoad: " \
22  "%f\n\t" \
23  "Empty buckets: %.2f%%\n\tOverloaded buckets: %.2f%% (biggest bucket: %d)\n", \
24  BLI_ghash_len(_gh), \
25  q, \
26  var, \
27  lf, \
28  pempty * 100.0, \
29  poverloaded * 100.0, \
30  bigb); \
31  } \
32  void(0)
33 
34 /* NOTE: for pure-ghash testing, nature of the keys and data have absolutely no importance! So here
35  * we just use mere random integers stored in pointers. */
36 
37 static void init_keys(unsigned int keys[TESTCASE_SIZE], const int seed)
38 {
39  RNG *rng = BLI_rng_new(seed);
40  unsigned int *k;
41  int i;
42 
43  for (i = 0, k = keys; i < TESTCASE_SIZE;) {
44  /* Risks of collision are low, but they do exist.
45  * And we cannot use a GSet, since we test that here! */
46  int j, t = BLI_rng_get_uint(rng);
47  for (j = i; j--;) {
48  if (keys[j] == t) {
49  continue;
50  }
51  }
52  *k = t;
53  i++;
54  k++;
55  }
56  BLI_rng_free(rng);
57 }
58 
59 /* Here we simply insert and then lookup all keys, ensuring we do get back the expected stored
60  * 'data'. */
61 TEST(ghash, InsertLookup)
62 {
64  unsigned int keys[TESTCASE_SIZE], *k;
65  int i;
66 
67  init_keys(keys, 0);
68 
69  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
71  }
72 
74 
75  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
76  void *v = BLI_ghash_lookup(ghash, POINTER_FROM_UINT(*k));
78  }
79 
80  BLI_ghash_free(ghash, nullptr, nullptr);
81 }
82 
83 /* Here we simply insert and then remove all keys, ensuring we do get an empty,
84  * ghash that has not been shrunk. */
85 TEST(ghash, InsertRemove)
86 {
88  unsigned int keys[TESTCASE_SIZE], *k;
89  int i, bkt_size;
90 
91  init_keys(keys, 10);
92 
93  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
95  }
96 
98  bkt_size = BLI_ghash_buckets_len(ghash);
99 
100  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
101  void *v = BLI_ghash_popkey(ghash, POINTER_FROM_UINT(*k), nullptr);
103  }
104 
105  EXPECT_EQ(BLI_ghash_len(ghash), 0);
106  EXPECT_EQ(BLI_ghash_buckets_len(ghash), bkt_size);
107 
108  BLI_ghash_free(ghash, nullptr, nullptr);
109 }
110 
111 /* Same as above, but this time we allow ghash to shrink. */
112 TEST(ghash, InsertRemoveShrink)
113 {
115  unsigned int keys[TESTCASE_SIZE], *k;
116  int i, bkt_size;
117 
119  init_keys(keys, 20);
120 
121  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
123  }
124 
126  bkt_size = BLI_ghash_buckets_len(ghash);
127 
128  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
129  void *v = BLI_ghash_popkey(ghash, POINTER_FROM_UINT(*k), nullptr);
131  }
132 
133  EXPECT_EQ(BLI_ghash_len(ghash), 0);
134  EXPECT_LT(BLI_ghash_buckets_len(ghash), bkt_size);
135 
136  BLI_ghash_free(ghash, nullptr, nullptr);
137 }
138 
139 /* Check copy. */
140 TEST(ghash, Copy)
141 {
143  GHash *ghash_copy;
144  unsigned int keys[TESTCASE_SIZE], *k;
145  int i;
146 
147  init_keys(keys, 30);
148 
149  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
151  }
152 
154 
155  ghash_copy = BLI_ghash_copy(ghash, nullptr, nullptr);
156 
159 
160  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
163  }
164 
165  BLI_ghash_free(ghash, nullptr, nullptr);
166  BLI_ghash_free(ghash_copy, nullptr, nullptr);
167 }
168 
169 /* Check pop. */
170 TEST(ghash, Pop)
171 {
173  unsigned int keys[TESTCASE_SIZE], *k;
174  int i;
175 
177  init_keys(keys, 30);
178 
179  for (i = TESTCASE_SIZE, k = keys; i--; k++) {
181  }
182 
184 
185  GHashIterState pop_state = {0};
186 
187  for (i = TESTCASE_SIZE / 2; i--;) {
188  void *k, *v;
189  bool success = BLI_ghash_pop(ghash, &pop_state, &k, &v);
190  EXPECT_EQ(k, v);
191  EXPECT_TRUE(success);
192 
193  if (i % 2) {
195  }
196  }
197 
199 
200  {
201  void *k, *v;
202  while (BLI_ghash_pop(ghash, &pop_state, &k, &v)) {
203  EXPECT_EQ(k, v);
204  }
205  }
206  EXPECT_EQ(BLI_ghash_len(ghash), 0);
207 
208  BLI_ghash_free(ghash, nullptr, nullptr);
209 }
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
int BLI_ghash_buckets_len(const GHash *gh)
Definition: BLI_ghash.c:1088
static GHash * ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
Definition: BLI_ghash.c:639
@ GHASH_FLAG_ALLOW_SHRINK
Definition: BLI_ghash.h:56
bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: BLI_ghash.c:827
GHash * BLI_ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:694
GHash * BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:689
bool BLI_ghashutil_intcmp(const void *a, const void *b)
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:734
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:705
unsigned int BLI_ghashutil_inthash_p(const void *ptr)
void * BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:805
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition: BLI_ghash.c:710
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:863
void BLI_ghash_flag_set(GHash *gh, unsigned int flag)
Definition: BLI_ghash.c:875
#define TESTCASE_SIZE
TEST(ghash, InsertLookup)
static void init_keys(unsigned int keys[TESTCASE_SIZE], const int seed)
Random number functions.
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition: rand.cc:58
unsigned int BLI_rng_get_uint(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition: rand.cc:83
struct RNG * BLI_rng_new(unsigned int seed)
Definition: rand.cc:39
#define POINTER_AS_UINT(i)
#define POINTER_FROM_UINT(i)
_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 GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
ATTR_WARN_UNUSED_RESULT const BMVert * v
static unsigned long seed
Definition: btSoftBody.h:39
Definition: rand.cc:33