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