1 /* Apache License, Version 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
init_keys(unsigned int keys[TESTCASE_SIZE],const int seed)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'. */
TEST(ghash,InsertLookup)61 TEST(ghash, InsertLookup)
62 {
63 GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
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++) {
70 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
71 }
72
73 EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
74
75 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
76 void *v = BLI_ghash_lookup(ghash, POINTER_FROM_UINT(*k));
77 EXPECT_EQ(POINTER_AS_UINT(v), *k);
78 }
79
80 BLI_ghash_free(ghash, NULL, NULL);
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. */
TEST(ghash,InsertRemove)85 TEST(ghash, InsertRemove)
86 {
87 GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
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++) {
94 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
95 }
96
97 EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
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), NULL);
102 EXPECT_EQ(POINTER_AS_UINT(v), *k);
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, NULL, NULL);
109 }
110
111 /* Same as above, but this time we allow ghash to shrink. */
TEST(ghash,InsertRemoveShrink)112 TEST(ghash, InsertRemoveShrink)
113 {
114 GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
115 unsigned int keys[TESTCASE_SIZE], *k;
116 int i, bkt_size;
117
118 BLI_ghash_flag_set(ghash, GHASH_FLAG_ALLOW_SHRINK);
119 init_keys(keys, 20);
120
121 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
122 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
123 }
124
125 EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
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), NULL);
130 EXPECT_EQ(POINTER_AS_UINT(v), *k);
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, NULL, NULL);
137 }
138
139 /* Check copy. */
TEST(ghash,Copy)140 TEST(ghash, Copy)
141 {
142 GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
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++) {
150 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
151 }
152
153 EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
154
155 ghash_copy = BLI_ghash_copy(ghash, NULL, NULL);
156
157 EXPECT_EQ(BLI_ghash_len(ghash_copy), TESTCASE_SIZE);
158 EXPECT_EQ(BLI_ghash_buckets_len(ghash_copy), BLI_ghash_buckets_len(ghash));
159
160 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
161 void *v = BLI_ghash_lookup(ghash_copy, POINTER_FROM_UINT(*k));
162 EXPECT_EQ(POINTER_AS_UINT(v), *k);
163 }
164
165 BLI_ghash_free(ghash, NULL, NULL);
166 BLI_ghash_free(ghash_copy, NULL, NULL);
167 }
168
169 /* Check pop. */
TEST(ghash,Pop)170 TEST(ghash, Pop)
171 {
172 GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
173 unsigned int keys[TESTCASE_SIZE], *k;
174 int i;
175
176 BLI_ghash_flag_set(ghash, GHASH_FLAG_ALLOW_SHRINK);
177 init_keys(keys, 30);
178
179 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
180 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
181 }
182
183 EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
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) {
194 BLI_ghash_insert(ghash, POINTER_FROM_UINT(i * 4), POINTER_FROM_UINT(i * 4));
195 }
196 }
197
198 EXPECT_EQ(BLI_ghash_len(ghash), (TESTCASE_SIZE - TESTCASE_SIZE / 2 + TESTCASE_SIZE / 4));
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, NULL, NULL);
209 }
210