Merge remote-tracking branch 'origin/master' into blender2.8
[blender.git] / tests / gtests / blenlib / BLI_ghash_test.cc
1 /* Apache License, Version 2.0 */
2
3 #include "testing/testing.h"
4
5 #define GHASH_INTERNAL_API
6
7 extern "C" {
8 #include "BLI_utildefines.h"
9 #include "BLI_ghash.h"
10 #include "BLI_rand.h"
11 }
12
13 #define TESTCASE_SIZE 10000
14
15 /* Only keeping this in case here, for now. */
16 #define PRINTF_GHASH_STATS(_gh) \
17 { \
18         double q, lf, var, pempty, poverloaded; \
19         int bigb; \
20         q = BLI_ghash_calc_quality_ex((_gh), &lf, &var, &pempty, &poverloaded, &bigb); \
21         printf("GHash stats (%d entries):\n\t" \
22                "Quality (the lower the better): %f\n\tVariance (the lower the better): %f\n\tLoad: %f\n\t" \
23                "Empty buckets: %.2f%%\n\tOverloaded buckets: %.2f%% (biggest bucket: %d)\n", \
24                BLI_ghash_len(_gh), q, var, lf, pempty * 100.0, poverloaded * 100.0, bigb); \
25 } void (0)
26
27 /* Note: for pure-ghash testing, nature of the keys and data have absolutely no importance! So here we just use mere
28  *       random integers stored in pointers. */
29
30 static void init_keys(unsigned int keys[TESTCASE_SIZE], const int seed)
31 {
32         RNG *rng = BLI_rng_new(seed);
33         unsigned int *k;
34         int i;
35
36         for (i = 0, k = keys; i < TESTCASE_SIZE; ) {
37                 /* Risks of collision are low, but they do exist.
38                  * And we cannot use a GSet, since we test that here! */
39                 int j, t = BLI_rng_get_uint(rng);
40                 for (j = i; j--; ) {
41                         if (keys[j] == t) {
42                                 continue;
43                         }
44                 }
45                 *k = t;
46                 i++;
47                 k++;
48         }
49         BLI_rng_free(rng);
50 }
51
52 /* Here we simply insert and then lookup all keys, ensuring we do get back the expected stored 'data'. */
53 TEST(ghash, InsertLookup)
54 {
55         GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
56         unsigned int keys[TESTCASE_SIZE], *k;
57         int i;
58
59         init_keys(keys, 0);
60
61         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
62                 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
63         }
64
65         EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
66
67         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
68                 void *v = BLI_ghash_lookup(ghash, POINTER_FROM_UINT(*k));
69                 EXPECT_EQ(POINTER_AS_UINT(v), *k);
70         }
71
72         BLI_ghash_free(ghash, NULL, NULL);
73 }
74
75 /* Here we simply insert and then remove all keys, ensuring we do get an empty, unshrinked ghash. */
76 TEST(ghash, InsertRemove)
77 {
78         GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
79         unsigned int keys[TESTCASE_SIZE], *k;
80         int i, bkt_size;
81
82         init_keys(keys, 10);
83
84         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
85                 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
86         }
87
88         EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
89         bkt_size = BLI_ghash_buckets_len(ghash);
90
91         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
92                 void *v = BLI_ghash_popkey(ghash, POINTER_FROM_UINT(*k), NULL);
93                 EXPECT_EQ(POINTER_AS_UINT(v), *k);
94         }
95
96         EXPECT_EQ(BLI_ghash_len(ghash), 0);
97         EXPECT_EQ(BLI_ghash_buckets_len(ghash), bkt_size);
98
99         BLI_ghash_free(ghash, NULL, NULL);
100 }
101
102 /* Same as above, but this time we allow ghash to shrink. */
103 TEST(ghash, InsertRemoveShrink)
104 {
105         GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
106         unsigned int keys[TESTCASE_SIZE], *k;
107         int i, bkt_size;
108
109         BLI_ghash_flag_set(ghash, GHASH_FLAG_ALLOW_SHRINK);
110         init_keys(keys, 20);
111
112         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
113                 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
114         }
115
116         EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
117         bkt_size = BLI_ghash_buckets_len(ghash);
118
119         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
120                 void *v = BLI_ghash_popkey(ghash, POINTER_FROM_UINT(*k), NULL);
121                 EXPECT_EQ(POINTER_AS_UINT(v), *k);
122         }
123
124         EXPECT_EQ(BLI_ghash_len(ghash), 0);
125         EXPECT_LT(BLI_ghash_buckets_len(ghash), bkt_size);
126
127         BLI_ghash_free(ghash, NULL, NULL);
128 }
129
130 /* Check copy. */
131 TEST(ghash, Copy)
132 {
133         GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
134         GHash *ghash_copy;
135         unsigned int keys[TESTCASE_SIZE], *k;
136         int i;
137
138         init_keys(keys, 30);
139
140         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
141                 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
142         }
143
144         EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
145
146         ghash_copy = BLI_ghash_copy(ghash, NULL, NULL);
147
148         EXPECT_EQ(BLI_ghash_len(ghash_copy), TESTCASE_SIZE);
149         EXPECT_EQ(BLI_ghash_buckets_len(ghash_copy), BLI_ghash_buckets_len(ghash));
150
151         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
152                 void *v = BLI_ghash_lookup(ghash_copy, POINTER_FROM_UINT(*k));
153                 EXPECT_EQ(POINTER_AS_UINT(v), *k);
154         }
155
156         BLI_ghash_free(ghash, NULL, NULL);
157         BLI_ghash_free(ghash_copy, NULL, NULL);
158 }
159
160 /* Check pop. */
161 TEST(ghash, Pop)
162 {
163         GHash *ghash = BLI_ghash_new(BLI_ghashutil_inthash_p, BLI_ghashutil_intcmp, __func__);
164         unsigned int keys[TESTCASE_SIZE], *k;
165         int i;
166
167         BLI_ghash_flag_set(ghash, GHASH_FLAG_ALLOW_SHRINK);
168         init_keys(keys, 30);
169
170         for (i = TESTCASE_SIZE, k = keys; i--; k++) {
171                 BLI_ghash_insert(ghash, POINTER_FROM_UINT(*k), POINTER_FROM_UINT(*k));
172         }
173
174         EXPECT_EQ(BLI_ghash_len(ghash), TESTCASE_SIZE);
175
176         GHashIterState pop_state = {0};
177
178         for (i = TESTCASE_SIZE / 2; i--; ) {
179                 void *k, *v;
180                 bool success = BLI_ghash_pop(ghash, &pop_state, &k, &v);
181                 EXPECT_EQ(k, v);
182                 EXPECT_TRUE(success);
183
184                 if (i % 2) {
185                         BLI_ghash_insert(ghash, POINTER_FROM_UINT(i * 4), POINTER_FROM_UINT(i * 4));
186                 }
187         }
188
189         EXPECT_EQ(BLI_ghash_len(ghash), (TESTCASE_SIZE - TESTCASE_SIZE / 2 + TESTCASE_SIZE / 4));
190
191         {
192                 void *k, *v;
193                 while (BLI_ghash_pop(ghash, &pop_state, &k, &v)) {
194                         EXPECT_EQ(k, v);
195                 }
196         }
197         EXPECT_EQ(BLI_ghash_len(ghash), 0);
198
199         BLI_ghash_free(ghash, NULL, NULL);
200 }