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