Blender V5.3
BLI_ghash_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include "testing/testing.h"
6
7#define GHASH_INTERNAL_API
8
9#include "BLI_ghash.hh"
10#include "BLI_rand_c.hh"
11#include "BLI_utildefines.hh"
12
13namespace blender {
14
15#define TESTCASE_SIZE 10000
16
17/* Only keeping this in case here, for now. */
18#define PRINTF_GHASH_STATS(_gh) \
19 { \
20 double q, lf, var, pempty, poverloaded; \
21 int bigb; \
22 q = BLI_ghash_calc_quality_ex((_gh), &lf, &var, &pempty, &poverloaded, &bigb); \
23 printf( \
24 "GHash stats (%d entries):\n\t" \
25 "Quality (the lower the better): %f\n\tVariance (the lower the better): %f\n\tLoad: " \
26 "%f\n\t" \
27 "Empty buckets: %.2f%%\n\tOverloaded buckets: %.2f%% (biggest bucket: %d)\n", \
28 BLI_ghash_len(_gh), \
29 q, \
30 var, \
31 lf, \
32 pempty * 100.0, \
33 poverloaded * 100.0, \
34 bigb); \
35 } \
36 void(0)
37
38/* NOTE: for pure-ghash testing, nature of the keys and data have absolutely no importance! So here
39 * we just use mere random integers stored in pointers. */
40
41static void init_keys(uint keys[TESTCASE_SIZE], const int seed)
42{
43 RNG *rng = BLI_rng_new(seed);
44 uint *k;
45 int i;
46
47 for (i = 0, k = keys; i < TESTCASE_SIZE;) {
48 /* Risks of collision are low, but they do exist.
49 * And we cannot use a GSet, since we test that here! */
50 int j, t = BLI_rng_get_uint(rng);
51 for (j = i; j--;) {
52 if (keys[j] == t) {
53 continue;
54 }
55 }
56 *k = t;
57 i++;
58 k++;
59 }
60 BLI_rng_free(rng);
61}
62
63/* Here we simply insert and then lookup all keys, ensuring we do get back the expected stored
64 * 'data'. */
65TEST(ghash, InsertLookup)
66{
68 uint keys[TESTCASE_SIZE], *k;
69 int i;
70
71 init_keys(keys, 0);
72
73 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
75 }
76
78
79 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
80 void *v = BLI_ghash_lookup(ghash, POINTER_FROM_UINT(*k));
82 }
83
84 BLI_ghash_free(ghash, nullptr, nullptr);
85}
86
87/* Here we simply insert and then remove all keys, ensuring we do get an empty,
88 * ghash that has not been shrunk. */
89TEST(ghash, InsertRemove)
90{
92 uint keys[TESTCASE_SIZE], *k;
93 int i, bkt_size;
94
95 init_keys(keys, 10);
96
97 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
99 }
100
102 bkt_size = BLI_ghash_buckets_len(ghash);
103
104 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
105 void *v = BLI_ghash_popkey(ghash, POINTER_FROM_UINT(*k), nullptr);
107 }
108
109 EXPECT_EQ(BLI_ghash_len(ghash), 0);
110 EXPECT_EQ(BLI_ghash_buckets_len(ghash), bkt_size);
111
112 BLI_ghash_free(ghash, nullptr, nullptr);
113}
114
115/* Same as `InsertRemove`, but this time we allow ghash to shrink. */
116TEST(ghash, InsertRemoveShrink)
117{
119 uint keys[TESTCASE_SIZE], *k;
120 int i, bkt_size;
121
123 init_keys(keys, 20);
124
125 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
127 }
128
130 bkt_size = BLI_ghash_buckets_len(ghash);
131
132 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
133 void *v = BLI_ghash_popkey(ghash, POINTER_FROM_UINT(*k), nullptr);
135 }
136
137 EXPECT_EQ(BLI_ghash_len(ghash), 0);
138 EXPECT_LT(BLI_ghash_buckets_len(ghash), bkt_size);
139
140 BLI_ghash_free(ghash, nullptr, nullptr);
141}
142
143/* Check copy. */
144TEST(ghash, Copy)
145{
148 uint keys[TESTCASE_SIZE], *k;
149 int i;
150
151 init_keys(keys, 30);
152
153 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
155 }
156
158
159 ghash_copy = BLI_ghash_copy(ghash, nullptr, nullptr);
160
163
164 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
167 }
168
169 BLI_ghash_free(ghash, nullptr, nullptr);
170 BLI_ghash_free(ghash_copy, nullptr, nullptr);
171}
172
173/* Check pop. */
174TEST(ghash, Pop)
175{
177 uint keys[TESTCASE_SIZE], *k;
178 int i;
179
181 init_keys(keys, 30);
182
183 for (i = TESTCASE_SIZE, k = keys; i--; k++) {
185 }
186
188
189 GHashIterState pop_state = {0};
190
191 for (i = TESTCASE_SIZE / 2; i--;) {
192 void *k, *v;
193 bool success = BLI_ghash_pop(ghash, &pop_state, &k, &v);
194 EXPECT_EQ(k, v);
195 EXPECT_TRUE(success);
196
197 if (i % 2) {
199 }
200 }
201
203
204 {
205 void *k, *v;
206 while (BLI_ghash_pop(ghash, &pop_state, &k, &v)) {
207 EXPECT_EQ(k, v);
208 }
209 }
210 EXPECT_EQ(BLI_ghash_len(ghash), 0);
211
212 BLI_ghash_free(ghash, nullptr, nullptr);
213}
214
215} // namespace blender
#define TESTCASE_SIZE
Random number functions.
#define POINTER_AS_UINT(i)
#define POINTER_FROM_UINT(i)
#define EXPECT_LT(result, expect)
#define EXPECT_TRUE(result)
BMesh Iterators.
unsigned int uint
Definition BKE_text.h:55
int BLI_ghash_buckets_len(const GHash *gh)
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:735
static void init_keys(uint keys[TESTCASE_SIZE], const int seed)
ATTR_WARN_UNUSED_RESULT const BMVert * v
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:711
TEST(array_store, Nop)
void * BLI_ghash_popkey(GHash *gh, const void *key, GHashKeyFreeFP keyfreefp) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:807
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition BLI_ghash.cc:866
unsigned int BLI_rng_get_uint(struct RNG *rng) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition rand.cc:80
void BLI_ghash_flag_set(GHash *gh, unsigned int flag)
Definition BLI_ghash.cc:878
bool BLI_ghashutil_intcmp(const void *a, const void *b)
@ GHASH_FLAG_ALLOW_SHRINK
Definition BLI_ghash.hh:55
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:706
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
GHash * BLI_ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:695
static GHash * ghash_copy(const GHash *gh, GHashKeyCopyFP keycopyfp, GHashValCopyFP valcopyfp)
Definition BLI_ghash.cc:640
bool BLI_ghash_pop(GHash *gh, GHashIterState *state, void **r_key, void **r_val) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition BLI_ghash.cc:830
GHash * BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:690
unsigned int BLI_ghashutil_inthash_p(const void *ptr)