Line data Source code
1 : /*--------------------------------------------------------------------------
2 : *
3 : * test_radixtree.c
4 : * Test module for adaptive radix tree.
5 : *
6 : * Copyright (c) 2024, PostgreSQL Global Development Group
7 : *
8 : * IDENTIFICATION
9 : * src/test/modules/test_radixtree/test_radixtree.c
10 : *
11 : * -------------------------------------------------------------------------
12 : */
13 : #include "postgres.h"
14 :
15 : #include "common/int.h"
16 : #include "common/pg_prng.h"
17 : #include "fmgr.h"
18 : #include "utils/memutils.h"
19 : #include "utils/timestamp.h"
20 :
21 : /* uncomment to use shared memory for the tree */
22 : /* #define TEST_SHARED_RT */
23 :
24 : #define UINT64_HEX_FORMAT "%" INT64_MODIFIER "X"
25 :
26 : /* Convenient macros to test results */
27 : #define EXPECT_TRUE(expr) \
28 : do { \
29 : if (!(expr)) \
30 : elog(ERROR, \
31 : "%s was unexpectedly false in file \"%s\" line %u", \
32 : #expr, __FILE__, __LINE__); \
33 : } while (0)
34 :
35 : #define EXPECT_FALSE(expr) \
36 : do { \
37 : if (expr) \
38 : elog(ERROR, \
39 : "%s was unexpectedly true in file \"%s\" line %u", \
40 : #expr, __FILE__, __LINE__); \
41 : } while (0)
42 :
43 : #define EXPECT_EQ_U64(result_expr, expected_expr) \
44 : do { \
45 : uint64 _result = (result_expr); \
46 : uint64 _expected = (expected_expr); \
47 : if (_result != _expected) \
48 : elog(ERROR, \
49 : "%s yielded " UINT64_HEX_FORMAT ", expected " UINT64_HEX_FORMAT " (%s) in file \"%s\" line %u", \
50 : #result_expr, _result, _expected, #expected_expr, __FILE__, __LINE__); \
51 : } while (0)
52 :
53 : /*
54 : * With uint64, 64-bit platforms store the value in the last-level child
55 : * pointer, and 32-bit platforms store this in a single-value leaf.
56 : * This gives us buildfarm coverage for both paths in this module.
57 : */
58 : typedef uint64 TestValueType;
59 :
60 : /*
61 : * The node class name and the number of keys big enough to grow nodes
62 : * into each size class.
63 : */
64 : typedef struct rt_node_class_test_elem
65 : {
66 : char *class_name;
67 : int nkeys;
68 : } rt_node_class_test_elem;
69 :
70 : static rt_node_class_test_elem rt_node_class_tests[] =
71 : {
72 : {
73 : .class_name = "node-4", /* RT_CLASS_4 */
74 : .nkeys = 2,
75 : },
76 : {
77 : .class_name = "node-16-lo", /* RT_CLASS_16_LO */
78 : .nkeys = 15,
79 : },
80 : {
81 : .class_name = "node-16-hi", /* RT_CLASS_16_HI */
82 : .nkeys = 30,
83 : },
84 : {
85 : .class_name = "node-48", /* RT_CLASS_48 */
86 : .nkeys = 60,
87 : },
88 : {
89 : .class_name = "node-256", /* RT_CLASS_256 */
90 : .nkeys = 256,
91 : },
92 : };
93 :
94 :
95 : /* define the radix tree implementation to test */
96 : #define RT_PREFIX rt
97 : #define RT_SCOPE
98 : #define RT_DECLARE
99 : #define RT_DEFINE
100 : #define RT_USE_DELETE
101 : #define RT_VALUE_TYPE TestValueType
102 : #ifdef TEST_SHARED_RT
103 : #define RT_SHMEM
104 : #endif
105 : #define RT_DEBUG
106 : #include "lib/radixtree.h"
107 :
108 :
109 : /*
110 : * Return the number of keys in the radix tree.
111 : */
112 : static uint64
113 4 : rt_num_entries(rt_radix_tree *tree)
114 : {
115 4 : return tree->ctl->num_keys;
116 : }
117 :
118 2 : PG_MODULE_MAGIC;
119 :
120 4 : PG_FUNCTION_INFO_V1(test_radixtree);
121 :
122 : static void
123 2 : test_empty(void)
124 : {
125 : MemoryContext radixtree_ctx;
126 : rt_radix_tree *radixtree;
127 : rt_iter *iter;
128 : uint64 key;
129 : #ifdef TEST_SHARED_RT
130 : int tranche_id = LWLockNewTrancheId();
131 : dsa_area *dsa;
132 : #endif
133 :
134 2 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
135 : "test_radix_tree",
136 : ALLOCSET_SMALL_SIZES);
137 :
138 : #ifdef TEST_SHARED_RT
139 : LWLockRegisterTranche(tranche_id, "test_radix_tree");
140 : dsa = dsa_create(tranche_id);
141 :
142 : radixtree = rt_create(radixtree_ctx, dsa, tranche_id);
143 : #else
144 2 : radixtree = rt_create(radixtree_ctx);
145 : #endif
146 :
147 : /* Should not find anything in an empty tree */
148 2 : EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
149 2 : EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
150 2 : EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
151 2 : EXPECT_FALSE(rt_delete(radixtree, 0));
152 2 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
153 :
154 : /* Iterating on an empty tree should not return anything */
155 2 : iter = rt_begin_iterate(radixtree);
156 2 : EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
157 2 : rt_end_iterate(iter);
158 :
159 2 : rt_free(radixtree);
160 :
161 : #ifdef TEST_SHARED_RT
162 : dsa_detach(dsa);
163 : #endif
164 2 : }
165 :
166 : /* Basic set, find, and delete tests */
167 : static void
168 60 : test_basic(rt_node_class_test_elem *test_info, int shift, bool asc)
169 : {
170 : MemoryContext radixtree_ctx;
171 : rt_radix_tree *radixtree;
172 : rt_iter *iter;
173 : uint64 *keys;
174 60 : int children = test_info->nkeys;
175 : #ifdef TEST_SHARED_RT
176 : int tranche_id = LWLockNewTrancheId();
177 : dsa_area *dsa;
178 : #endif
179 :
180 60 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
181 : "test_radix_tree",
182 : ALLOCSET_SMALL_SIZES);
183 :
184 : #ifdef TEST_SHARED_RT
185 : LWLockRegisterTranche(tranche_id, "test_radix_tree");
186 : dsa = dsa_create(tranche_id);
187 :
188 : radixtree = rt_create(radixtree_ctx, dsa, tranche_id);
189 : #else
190 60 : radixtree = rt_create(radixtree_ctx);
191 : #endif
192 :
193 60 : elog(NOTICE, "testing node %s with shift %d and %s keys",
194 : test_info->class_name, shift, asc ? "ascending" : "descending");
195 :
196 60 : keys = palloc(sizeof(uint64) * children);
197 4416 : for (int i = 0; i < children; i++)
198 : {
199 4356 : if (asc)
200 2178 : keys[i] = (uint64) i << shift;
201 : else
202 2178 : keys[i] = (uint64) (children - 1 - i) << shift;
203 : }
204 :
205 : /*
206 : * Insert keys. Since the tree was just created, rt_set should return
207 : * false.
208 : */
209 4416 : for (int i = 0; i < children; i++)
210 4356 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
211 :
212 60 : rt_stats(radixtree);
213 :
214 : /* look up keys */
215 4416 : for (int i = 0; i < children; i++)
216 : {
217 : TestValueType *value;
218 :
219 4356 : value = rt_find(radixtree, keys[i]);
220 :
221 : /* Test rt_find returns the expected value */
222 4356 : EXPECT_TRUE(value != NULL);
223 4356 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
224 : }
225 :
226 : /* update keys */
227 4416 : for (int i = 0; i < children; i++)
228 : {
229 4356 : TestValueType update = keys[i] + 1;
230 :
231 : /* rt_set should report the key found */
232 4356 : EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));
233 : }
234 :
235 : /* delete and re-insert keys */
236 4416 : for (int i = 0; i < children; i++)
237 : {
238 4356 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
239 4356 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
240 : }
241 :
242 : /* look up keys after deleting and re-inserting */
243 4416 : for (int i = 0; i < children; i++)
244 : {
245 : TestValueType *value;
246 :
247 4356 : value = rt_find(radixtree, keys[i]);
248 :
249 : /* Test that rt_find returns the expected value */
250 4356 : EXPECT_TRUE(value != NULL);
251 4356 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
252 : }
253 :
254 : /* test that iteration returns the expected keys and values */
255 60 : iter = rt_begin_iterate(radixtree);
256 :
257 4416 : for (int i = 0; i < children; i++)
258 : {
259 : uint64 expected;
260 : uint64 iterkey;
261 : TestValueType *iterval;
262 :
263 : /* iteration is ordered by key, so adjust expected value accordingly */
264 4356 : if (asc)
265 2178 : expected = keys[i];
266 : else
267 2178 : expected = keys[children - 1 - i];
268 :
269 4356 : iterval = rt_iterate_next(iter, &iterkey);
270 :
271 4356 : EXPECT_TRUE(iterval != NULL);
272 4356 : EXPECT_EQ_U64(iterkey, expected);
273 4356 : EXPECT_EQ_U64(*iterval, expected);
274 : }
275 :
276 60 : rt_end_iterate(iter);
277 :
278 : /* delete all keys again */
279 4416 : for (int i = 0; i < children; i++)
280 4356 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
281 :
282 : /* test that all keys were deleted */
283 4416 : for (int i = 0; i < children; i++)
284 4356 : EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
285 :
286 60 : rt_stats(radixtree);
287 :
288 60 : pfree(keys);
289 60 : rt_free(radixtree);
290 :
291 : #ifdef TEST_SHARED_RT
292 : dsa_detach(dsa);
293 : #endif
294 60 : }
295 :
296 : static int
297 3467244 : key_cmp(const void *a, const void *b)
298 : {
299 3467244 : return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
300 : }
301 :
302 : static void
303 2 : test_random(void)
304 : {
305 : MemoryContext radixtree_ctx;
306 : rt_radix_tree *radixtree;
307 : rt_iter *iter;
308 : pg_prng_state state;
309 :
310 : /* limit memory usage by limiting the key space */
311 2 : uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
312 2 : uint64 seed = GetCurrentTimestamp();
313 2 : int num_keys = 100000;
314 : uint64 *keys;
315 : #ifdef TEST_SHARED_RT
316 : int tranche_id = LWLockNewTrancheId();
317 : dsa_area *dsa;
318 : #endif
319 :
320 2 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
321 : "test_radix_tree",
322 : ALLOCSET_SMALL_SIZES);
323 :
324 : #ifdef TEST_SHARED_RT
325 : LWLockRegisterTranche(tranche_id, "test_radix_tree");
326 : dsa = dsa_create(tranche_id);
327 :
328 : radixtree = rt_create(radixtree_ctx, dsa, tranche_id);
329 : #else
330 2 : radixtree = rt_create(radixtree_ctx);
331 : #endif
332 :
333 : /* add some random values */
334 2 : pg_prng_seed(&state, seed);
335 2 : keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
336 200002 : for (uint64 i = 0; i < num_keys; i++)
337 : {
338 200000 : uint64 key = pg_prng_uint64(&state) & filter;
339 200000 : TestValueType val = (TestValueType) key;
340 :
341 : /* save in an array */
342 200000 : keys[i] = key;
343 :
344 200000 : rt_set(radixtree, key, &val);
345 : }
346 :
347 2 : rt_stats(radixtree);
348 :
349 200002 : for (uint64 i = 0; i < num_keys; i++)
350 : {
351 : TestValueType *value;
352 :
353 200000 : value = rt_find(radixtree, keys[i]);
354 :
355 : /* Test rt_find for values just inserted */
356 200000 : EXPECT_TRUE(value != NULL);
357 200000 : EXPECT_EQ_U64(*value, keys[i]);
358 : }
359 :
360 : /* sort keys for iteration and absence tests */
361 2 : qsort(keys, num_keys, sizeof(uint64), key_cmp);
362 :
363 : /* should not find numbers in between the keys */
364 200000 : for (uint64 i = 0; i < num_keys - 1; i++)
365 : {
366 : TestValueType *value;
367 :
368 : /* skip duplicate and adjacent keys */
369 199998 : if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
370 49524 : continue;
371 :
372 : /* should not find the number right after key */
373 150474 : value = rt_find(radixtree, keys[i] + 1);
374 150474 : EXPECT_TRUE(value == NULL);
375 : }
376 :
377 : /* should not find numbers lower than lowest key */
378 40 : for (uint64 key = 0; key < keys[0]; key++)
379 : {
380 : TestValueType *value;
381 :
382 : /* arbitrary stopping point */
383 38 : if (key > 10000)
384 0 : break;
385 :
386 38 : value = rt_find(radixtree, key);
387 38 : EXPECT_TRUE(value == NULL);
388 : }
389 :
390 : /* should not find numbers higher than highest key */
391 20000 : for (uint64 i = 1; i < 10000; i++)
392 : {
393 : TestValueType *value;
394 :
395 19998 : value = rt_find(radixtree, keys[num_keys - 1] + i);
396 19998 : EXPECT_TRUE(value == NULL);
397 : }
398 :
399 : /* test that iteration returns the expected keys and values */
400 2 : iter = rt_begin_iterate(radixtree);
401 :
402 200002 : for (int i = 0; i < num_keys; i++)
403 : {
404 : uint64 expected;
405 : uint64 iterkey;
406 : TestValueType *iterval;
407 :
408 : /* skip duplicate keys */
409 200000 : if (i < num_keys - 1 && keys[i + 1] == keys[i])
410 18002 : continue;
411 :
412 181998 : expected = keys[i];
413 181998 : iterval = rt_iterate_next(iter, &iterkey);
414 :
415 181998 : EXPECT_TRUE(iterval != NULL);
416 181998 : EXPECT_EQ_U64(iterkey, expected);
417 181998 : EXPECT_EQ_U64(*iterval, expected);
418 : }
419 :
420 2 : rt_end_iterate(iter);
421 :
422 : /* reset random number generator for deletion */
423 2 : pg_prng_seed(&state, seed);
424 :
425 : /* delete in original random order */
426 200002 : for (uint64 i = 0; i < num_keys; i++)
427 : {
428 200000 : uint64 key = pg_prng_uint64(&state) & filter;
429 :
430 200000 : rt_delete(radixtree, key);
431 : }
432 :
433 2 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
434 :
435 2 : pfree(keys);
436 2 : rt_free(radixtree);
437 :
438 : #ifdef TEST_SHARED_RT
439 : dsa_detach(dsa);
440 : #endif
441 2 : }
442 :
443 : Datum
444 2 : test_radixtree(PG_FUNCTION_ARGS)
445 : {
446 : /* borrowed from RT_MAX_SHIFT */
447 2 : const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
448 :
449 2 : test_empty();
450 :
451 12 : for (int i = 0; i < lengthof(rt_node_class_tests); i++)
452 : {
453 10 : rt_node_class_test_elem *test_info = &(rt_node_class_tests[i]);
454 :
455 : /* a tree with one level, i.e. a single node under the root node */
456 10 : test_basic(test_info, 0, true);
457 10 : test_basic(test_info, 0, false);
458 :
459 : /* a tree with two levels */
460 10 : test_basic(test_info, 8, true);
461 10 : test_basic(test_info, 8, false);
462 :
463 : /* a tree with the maximum number of levels */
464 10 : test_basic(test_info, max_shift, true);
465 10 : test_basic(test_info, max_shift, false);
466 : }
467 :
468 2 : test_random();
469 :
470 2 : PG_RETURN_VOID();
471 : }
|
