Age Owner Branch data TLA 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
480 tgl@sss.pgh.pa.us 111 :CBC 2 : rt_num_entries(rt_radix_tree *tree)
112 : : {
548 john.naylor@postgres 113 : 2 : return tree->ctl->num_keys;
114 : : }
115 : :
116 : 1 : PG_MODULE_MAGIC;
117 : :
118 : 2 : PG_FUNCTION_INFO_V1(test_radixtree);
119 : :
120 : : static void
121 : 1 : 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 : :
260 135 : 1 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
136 : : "test_radix_tree",
137 : : ALLOCSET_SMALL_SIZES);
548 138 : 1 : radixtree = rt_create(radixtree_ctx);
139 : : #endif
140 : :
141 : : /* Should not find anything in an empty tree */
142 [ - + - - ]: 1 : EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
143 [ - + - - ]: 1 : EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
144 [ - + - - ]: 1 : EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
145 [ - + - - ]: 1 : EXPECT_FALSE(rt_delete(radixtree, 0));
146 [ - + - - ]: 1 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
147 : :
148 : : /* Iterating on an empty tree should not return anything */
149 : 1 : iter = rt_begin_iterate(radixtree);
150 [ - + - - ]: 1 : EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
151 : 1 : rt_end_iterate(iter);
152 : :
153 : 1 : rt_free(radixtree);
154 : :
155 : : #ifdef TEST_SHARED_RT
156 : : dsa_detach(dsa);
157 : : #endif
158 : 1 : }
159 : :
160 : : /* Basic set, find, and delete tests */
161 : : static void
162 : 30 : 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 : 30 : 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 : :
260 177 : 30 : radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
178 : : "test_radix_tree",
179 : : ALLOCSET_SMALL_SIZES);
548 180 : 30 : radixtree = rt_create(radixtree_ctx);
181 : : #endif
182 : :
183 [ + - + + ]: 30 : elog(NOTICE, "testing node %s with shift %d and %s keys",
184 : : test_info->class_name, shift, asc ? "ascending" : "descending");
185 : :
186 : 30 : keys = palloc(sizeof(uint64) * children);
187 [ + + ]: 2208 : for (int i = 0; i < children; i++)
188 : : {
189 [ + + ]: 2178 : if (asc)
190 : 1089 : keys[i] = (uint64) i << shift;
191 : : else
192 : 1089 : 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 [ + + ]: 2208 : for (int i = 0; i < children; i++)
480 tgl@sss.pgh.pa.us 200 [ - + - - ]: 2178 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
201 : :
548 john.naylor@postgres 202 : 30 : rt_stats(radixtree);
203 : :
204 : : /* look up keys */
205 [ + + ]: 2208 : for (int i = 0; i < children; i++)
206 : : {
207 : : TestValueType *value;
208 : :
209 : 2178 : value = rt_find(radixtree, keys[i]);
210 : :
211 : : /* Test rt_find returns the expected value */
212 [ - + - - ]: 2178 : EXPECT_TRUE(value != NULL);
213 [ - + - - ]: 2178 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
214 : : }
215 : :
216 : : /* update keys */
217 [ + + ]: 2208 : for (int i = 0; i < children; i++)
218 : : {
219 : 2178 : TestValueType update = keys[i] + 1;
220 : :
221 : : /* rt_set should report the key found */
480 tgl@sss.pgh.pa.us 222 [ - + - - ]: 2178 : EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));
223 : : }
224 : :
225 : : /* delete and re-insert keys */
548 john.naylor@postgres 226 [ + + ]: 2208 : for (int i = 0; i < children; i++)
227 : : {
228 [ - + - - ]: 2178 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
480 tgl@sss.pgh.pa.us 229 [ - + - - ]: 2178 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
230 : : }
231 : :
232 : : /* look up keys after deleting and re-inserting */
548 john.naylor@postgres 233 [ + + ]: 2208 : for (int i = 0; i < children; i++)
234 : : {
235 : : TestValueType *value;
236 : :
237 : 2178 : value = rt_find(radixtree, keys[i]);
238 : :
239 : : /* Test that rt_find returns the expected value */
240 [ - + - - ]: 2178 : EXPECT_TRUE(value != NULL);
241 [ - + - - ]: 2178 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
242 : : }
243 : :
244 : : /* test that iteration returns the expected keys and values */
245 : 30 : iter = rt_begin_iterate(radixtree);
246 : :
247 [ + + ]: 2208 : 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 [ + + ]: 2178 : if (asc)
255 : 1089 : expected = keys[i];
256 : : else
257 : 1089 : expected = keys[children - 1 - i];
258 : :
259 : 2178 : iterval = rt_iterate_next(iter, &iterkey);
260 : :
261 [ - + - - ]: 2178 : EXPECT_TRUE(iterval != NULL);
262 [ - + - - ]: 2178 : EXPECT_EQ_U64(iterkey, expected);
263 [ - + - - ]: 2178 : EXPECT_EQ_U64(*iterval, expected);
264 : : }
265 : :
266 : 30 : rt_end_iterate(iter);
267 : :
268 : : /* delete all keys again */
269 [ + + ]: 2208 : for (int i = 0; i < children; i++)
270 [ - + - - ]: 2178 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
271 : :
272 : : /* test that all keys were deleted */
273 [ + + ]: 2208 : for (int i = 0; i < children; i++)
274 [ - + - - ]: 2178 : EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
275 : :
276 : 30 : rt_stats(radixtree);
277 : :
278 : 30 : pfree(keys);
279 : 30 : rt_free(radixtree);
280 : :
281 : : #ifdef TEST_SHARED_RT
282 : : dsa_detach(dsa);
283 : : #endif
284 : 30 : }
285 : :
286 : : static int
287 : 1751543 : key_cmp(const void *a, const void *b)
288 : : {
289 : 1751543 : return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
290 : : }
291 : :
292 : : static void
293 : 1 : 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 : 1 : uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
301 : 1 : uint64 seed = GetCurrentTimestamp();
302 : 1 : 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 : :
260 313 : 1 : radixtree_ctx = SlabContextCreate(CurrentMemoryContext,
314 : : "test_radix_tree",
315 : : SLAB_DEFAULT_BLOCK_SIZE,
316 : : sizeof(TestValueType));
548 317 : 1 : radixtree = rt_create(radixtree_ctx);
318 : : #endif
319 : :
320 : : /* add some random values */
321 : 1 : pg_prng_seed(&state, seed);
322 : 1 : keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
323 [ + + ]: 100001 : for (uint64 i = 0; i < num_keys; i++)
324 : : {
325 : 100000 : uint64 key = pg_prng_uint64(&state) & filter;
326 : 100000 : TestValueType val = (TestValueType) key;
327 : :
328 : : /* save in an array */
329 : 100000 : keys[i] = key;
330 : :
331 : 100000 : rt_set(radixtree, key, &val);
332 : : }
333 : :
334 : 1 : rt_stats(radixtree);
335 : :
336 [ + + ]: 100001 : for (uint64 i = 0; i < num_keys; i++)
337 : : {
338 : : TestValueType *value;
339 : :
340 : 100000 : value = rt_find(radixtree, keys[i]);
341 : :
342 : : /* Test rt_find for values just inserted */
343 [ - + - - ]: 100000 : EXPECT_TRUE(value != NULL);
344 [ - + - - ]: 100000 : EXPECT_EQ_U64(*value, keys[i]);
345 : : }
346 : :
347 : : /* sort keys for iteration and absence tests */
348 : 1 : qsort(keys, num_keys, sizeof(uint64), key_cmp);
349 : :
350 : : /* should not find numbers in between the keys */
351 [ + + ]: 100000 : for (uint64 i = 0; i < num_keys - 1; i++)
352 : : {
353 : : TestValueType *value;
354 : :
355 : : /* skip duplicate and adjacent keys */
356 [ + + + + ]: 99999 : if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
357 : 24638 : continue;
358 : :
359 : : /* should not find the number right after key */
360 : 75361 : value = rt_find(radixtree, keys[i] + 1);
361 [ - + - - ]: 75361 : EXPECT_TRUE(value == NULL);
362 : : }
363 : :
364 : : /* should not find numbers lower than lowest key */
365 [ + + ]: 2 : for (uint64 key = 0; key < keys[0]; key++)
366 : : {
367 : : TestValueType *value;
368 : :
369 : : /* arbitrary stopping point */
370 [ - + ]: 1 : if (key > 10000)
548 john.naylor@postgres 371 :UBC 0 : break;
372 : :
548 john.naylor@postgres 373 :CBC 1 : value = rt_find(radixtree, key);
374 [ - + - - ]: 1 : EXPECT_TRUE(value == NULL);
375 : : }
376 : :
377 : : /* should not find numbers higher than highest key */
378 [ + + ]: 10000 : for (uint64 i = 1; i < 10000; i++)
379 : : {
380 : : TestValueType *value;
381 : :
382 : 9999 : value = rt_find(radixtree, keys[num_keys - 1] + i);
383 [ - + - - ]: 9999 : EXPECT_TRUE(value == NULL);
384 : : }
385 : :
386 : : /* test that iteration returns the expected keys and values */
387 : 1 : iter = rt_begin_iterate(radixtree);
388 : :
389 [ + + ]: 100001 : for (int i = 0; i < num_keys; i++)
390 : : {
391 : : uint64 expected;
392 : : uint64 iterkey;
393 : : TestValueType *iterval;
394 : :
395 : : /* skip duplicate keys */
396 [ + + + + ]: 100000 : if (i < num_keys - 1 && keys[i + 1] == keys[i])
397 : 9032 : continue;
398 : :
399 : 90968 : expected = keys[i];
400 : 90968 : iterval = rt_iterate_next(iter, &iterkey);
401 : :
402 [ - + - - ]: 90968 : EXPECT_TRUE(iterval != NULL);
403 [ - + - - ]: 90968 : EXPECT_EQ_U64(iterkey, expected);
404 [ - + - - ]: 90968 : EXPECT_EQ_U64(*iterval, expected);
405 : : }
406 : :
407 : 1 : rt_end_iterate(iter);
408 : :
409 : : /* reset random number generator for deletion */
410 : 1 : pg_prng_seed(&state, seed);
411 : :
412 : : /* delete in original random order */
413 [ + + ]: 100001 : for (uint64 i = 0; i < num_keys; i++)
414 : : {
415 : 100000 : uint64 key = pg_prng_uint64(&state) & filter;
416 : :
417 : 100000 : rt_delete(radixtree, key);
418 : : }
419 : :
420 [ - + - - ]: 1 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
421 : :
422 : 1 : pfree(keys);
423 : 1 : rt_free(radixtree);
424 : :
425 : : #ifdef TEST_SHARED_RT
426 : : dsa_detach(dsa);
427 : : #endif
428 : 1 : }
429 : :
430 : : Datum
431 : 1 : test_radixtree(PG_FUNCTION_ARGS)
432 : : {
433 : : /* borrowed from RT_MAX_SHIFT */
434 : 1 : const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
435 : :
436 : 1 : test_empty();
437 : :
438 [ + + ]: 6 : for (int i = 0; i < lengthof(rt_node_class_tests); i++)
439 : : {
440 : 5 : 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 : 5 : test_basic(test_info, 0, true);
444 : 5 : test_basic(test_info, 0, false);
445 : :
446 : : /* a tree with two levels */
447 : 5 : test_basic(test_info, 8, true);
448 : 5 : test_basic(test_info, 8, false);
449 : :
450 : : /* a tree with the maximum number of levels */
451 : 5 : test_basic(test_info, max_shift, true);
452 : 5 : test_basic(test_info, max_shift, false);
453 : : }
454 : :
455 : 1 : test_random();
456 : :
457 : 1 : PG_RETURN_VOID();
458 : : }
|
