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 " UINT64_HEX_FORMAT ", expected " UINT64_HEX_FORMAT " (%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();
128 : dsa_area *dsa;
129 :
130 : LWLockRegisterTranche(tranche_id, "test_radix_tree");
131 : dsa = dsa_create(tranche_id);
132 : radixtree = rt_create(dsa, tranche_id);
133 : #else
134 : MemoryContext radixtree_ctx;
135 :
136 2 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
137 : "test_radix_tree",
138 : ALLOCSET_SMALL_SIZES);
139 2 : radixtree = rt_create(radixtree_ctx);
140 : #endif
141 :
142 : /* Should not find anything in an empty tree */
143 2 : EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
144 2 : EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
145 2 : EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
146 2 : EXPECT_FALSE(rt_delete(radixtree, 0));
147 2 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
148 :
149 : /* Iterating on an empty tree should not return anything */
150 2 : iter = rt_begin_iterate(radixtree);
151 2 : EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
152 2 : rt_end_iterate(iter);
153 :
154 2 : rt_free(radixtree);
155 :
156 : #ifdef TEST_SHARED_RT
157 : dsa_detach(dsa);
158 : #endif
159 2 : }
160 :
161 : /* Basic set, find, and delete tests */
162 : static void
163 60 : test_basic(rt_node_class_test_elem *test_info, int shift, bool asc)
164 : {
165 : rt_radix_tree *radixtree;
166 : rt_iter *iter;
167 : uint64 *keys;
168 60 : int children = test_info->nkeys;
169 : #ifdef TEST_SHARED_RT
170 : int tranche_id = LWLockNewTrancheId();
171 : dsa_area *dsa;
172 :
173 : LWLockRegisterTranche(tranche_id, "test_radix_tree");
174 : dsa = dsa_create(tranche_id);
175 : radixtree = rt_create(dsa, tranche_id);
176 : #else
177 : MemoryContext radixtree_ctx;
178 :
179 60 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
180 : "test_radix_tree",
181 : ALLOCSET_SMALL_SIZES);
182 60 : radixtree = rt_create(radixtree_ctx);
183 : #endif
184 :
185 60 : elog(NOTICE, "testing node %s with shift %d and %s keys",
186 : test_info->class_name, shift, asc ? "ascending" : "descending");
187 :
188 60 : keys = palloc(sizeof(uint64) * children);
189 4416 : for (int i = 0; i < children; i++)
190 : {
191 4356 : if (asc)
192 2178 : keys[i] = (uint64) i << shift;
193 : else
194 2178 : keys[i] = (uint64) (children - 1 - i) << shift;
195 : }
196 :
197 : /*
198 : * Insert keys. Since the tree was just created, rt_set should return
199 : * false.
200 : */
201 4416 : for (int i = 0; i < children; i++)
202 4356 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
203 :
204 60 : rt_stats(radixtree);
205 :
206 : /* look up keys */
207 4416 : for (int i = 0; i < children; i++)
208 : {
209 : TestValueType *value;
210 :
211 4356 : value = rt_find(radixtree, keys[i]);
212 :
213 : /* Test rt_find returns the expected value */
214 4356 : EXPECT_TRUE(value != NULL);
215 4356 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
216 : }
217 :
218 : /* update keys */
219 4416 : for (int i = 0; i < children; i++)
220 : {
221 4356 : TestValueType update = keys[i] + 1;
222 :
223 : /* rt_set should report the key found */
224 4356 : EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));
225 : }
226 :
227 : /* delete and re-insert keys */
228 4416 : for (int i = 0; i < children; i++)
229 : {
230 4356 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
231 4356 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
232 : }
233 :
234 : /* look up keys after deleting and re-inserting */
235 4416 : for (int i = 0; i < children; i++)
236 : {
237 : TestValueType *value;
238 :
239 4356 : value = rt_find(radixtree, keys[i]);
240 :
241 : /* Test that rt_find returns the expected value */
242 4356 : EXPECT_TRUE(value != NULL);
243 4356 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
244 : }
245 :
246 : /* test that iteration returns the expected keys and values */
247 60 : iter = rt_begin_iterate(radixtree);
248 :
249 4416 : for (int i = 0; i < children; i++)
250 : {
251 : uint64 expected;
252 : uint64 iterkey;
253 : TestValueType *iterval;
254 :
255 : /* iteration is ordered by key, so adjust expected value accordingly */
256 4356 : if (asc)
257 2178 : expected = keys[i];
258 : else
259 2178 : expected = keys[children - 1 - i];
260 :
261 4356 : iterval = rt_iterate_next(iter, &iterkey);
262 :
263 4356 : EXPECT_TRUE(iterval != NULL);
264 4356 : EXPECT_EQ_U64(iterkey, expected);
265 4356 : EXPECT_EQ_U64(*iterval, expected);
266 : }
267 :
268 60 : rt_end_iterate(iter);
269 :
270 : /* delete all keys again */
271 4416 : for (int i = 0; i < children; i++)
272 4356 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
273 :
274 : /* test that all keys were deleted */
275 4416 : for (int i = 0; i < children; i++)
276 4356 : EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
277 :
278 60 : rt_stats(radixtree);
279 :
280 60 : pfree(keys);
281 60 : rt_free(radixtree);
282 :
283 : #ifdef TEST_SHARED_RT
284 : dsa_detach(dsa);
285 : #endif
286 60 : }
287 :
288 : static int
289 3455504 : key_cmp(const void *a, const void *b)
290 : {
291 3455504 : return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
292 : }
293 :
294 : static void
295 2 : test_random(void)
296 : {
297 : rt_radix_tree *radixtree;
298 : rt_iter *iter;
299 : pg_prng_state state;
300 :
301 : /* limit memory usage by limiting the key space */
302 2 : uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
303 2 : uint64 seed = GetCurrentTimestamp();
304 2 : int num_keys = 100000;
305 : uint64 *keys;
306 : #ifdef TEST_SHARED_RT
307 : int tranche_id = LWLockNewTrancheId();
308 : dsa_area *dsa;
309 :
310 : LWLockRegisterTranche(tranche_id, "test_radix_tree");
311 : dsa = dsa_create(tranche_id);
312 : radixtree = rt_create(dsa, tranche_id);
313 : #else
314 : MemoryContext radixtree_ctx;
315 :
316 2 : radixtree_ctx = SlabContextCreate(CurrentMemoryContext,
317 : "test_radix_tree",
318 : SLAB_DEFAULT_BLOCK_SIZE,
319 : sizeof(TestValueType));
320 2 : radixtree = rt_create(radixtree_ctx);
321 : #endif
322 :
323 : /* add some random values */
324 2 : pg_prng_seed(&state, seed);
325 2 : keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
326 200002 : for (uint64 i = 0; i < num_keys; i++)
327 : {
328 200000 : uint64 key = pg_prng_uint64(&state) & filter;
329 200000 : TestValueType val = (TestValueType) key;
330 :
331 : /* save in an array */
332 200000 : keys[i] = key;
333 :
334 200000 : rt_set(radixtree, key, &val);
335 : }
336 :
337 2 : rt_stats(radixtree);
338 :
339 200002 : for (uint64 i = 0; i < num_keys; i++)
340 : {
341 : TestValueType *value;
342 :
343 200000 : value = rt_find(radixtree, keys[i]);
344 :
345 : /* Test rt_find for values just inserted */
346 200000 : EXPECT_TRUE(value != NULL);
347 200000 : EXPECT_EQ_U64(*value, keys[i]);
348 : }
349 :
350 : /* sort keys for iteration and absence tests */
351 2 : qsort(keys, num_keys, sizeof(uint64), key_cmp);
352 :
353 : /* should not find numbers in between the keys */
354 200000 : for (uint64 i = 0; i < num_keys - 1; i++)
355 : {
356 : TestValueType *value;
357 :
358 : /* skip duplicate and adjacent keys */
359 199998 : if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
360 49368 : continue;
361 :
362 : /* should not find the number right after key */
363 150630 : value = rt_find(radixtree, keys[i] + 1);
364 150630 : EXPECT_TRUE(value == NULL);
365 : }
366 :
367 : /* should not find numbers lower than lowest key */
368 18 : for (uint64 key = 0; key < keys[0]; key++)
369 : {
370 : TestValueType *value;
371 :
372 : /* arbitrary stopping point */
373 16 : if (key > 10000)
374 0 : break;
375 :
376 16 : value = rt_find(radixtree, key);
377 16 : EXPECT_TRUE(value == NULL);
378 : }
379 :
380 : /* should not find numbers higher than highest key */
381 20000 : for (uint64 i = 1; i < 10000; i++)
382 : {
383 : TestValueType *value;
384 :
385 19998 : value = rt_find(radixtree, keys[num_keys - 1] + i);
386 19998 : EXPECT_TRUE(value == NULL);
387 : }
388 :
389 : /* test that iteration returns the expected keys and values */
390 2 : iter = rt_begin_iterate(radixtree);
391 :
392 200002 : for (int i = 0; i < num_keys; i++)
393 : {
394 : uint64 expected;
395 : uint64 iterkey;
396 : TestValueType *iterval;
397 :
398 : /* skip duplicate keys */
399 200000 : if (i < num_keys - 1 && keys[i + 1] == keys[i])
400 17972 : continue;
401 :
402 182028 : expected = keys[i];
403 182028 : iterval = rt_iterate_next(iter, &iterkey);
404 :
405 182028 : EXPECT_TRUE(iterval != NULL);
406 182028 : EXPECT_EQ_U64(iterkey, expected);
407 182028 : EXPECT_EQ_U64(*iterval, expected);
408 : }
409 :
410 2 : rt_end_iterate(iter);
411 :
412 : /* reset random number generator for deletion */
413 2 : pg_prng_seed(&state, seed);
414 :
415 : /* delete in original random order */
416 200002 : for (uint64 i = 0; i < num_keys; i++)
417 : {
418 200000 : uint64 key = pg_prng_uint64(&state) & filter;
419 :
420 200000 : rt_delete(radixtree, key);
421 : }
422 :
423 2 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
424 :
425 2 : pfree(keys);
426 2 : rt_free(radixtree);
427 :
428 : #ifdef TEST_SHARED_RT
429 : dsa_detach(dsa);
430 : #endif
431 2 : }
432 :
433 : Datum
434 2 : test_radixtree(PG_FUNCTION_ARGS)
435 : {
436 : /* borrowed from RT_MAX_SHIFT */
437 2 : const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
438 :
439 2 : test_empty();
440 :
441 12 : for (int i = 0; i < lengthof(rt_node_class_tests); i++)
442 : {
443 10 : rt_node_class_test_elem *test_info = &(rt_node_class_tests[i]);
444 :
445 : /* a tree with one level, i.e. a single node under the root node */
446 10 : test_basic(test_info, 0, true);
447 10 : test_basic(test_info, 0, false);
448 :
449 : /* a tree with two levels */
450 10 : test_basic(test_info, 8, true);
451 10 : test_basic(test_info, 8, false);
452 :
453 : /* a tree with the maximum number of levels */
454 10 : test_basic(test_info, max_shift, true);
455 10 : test_basic(test_info, max_shift, false);
456 : }
457 :
458 2 : test_random();
459 :
460 2 : PG_RETURN_VOID();
461 : }
|
