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, 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
38 john.naylor@postgres 115 :GNC 2 : rt_num_entries(rt_radix_tree * tree)
116 : : {
117 : 2 : return tree->ctl->num_keys;
118 : : }
119 : :
120 : 1 : PG_MODULE_MAGIC;
121 : :
122 : 2 : PG_FUNCTION_INFO_V1(test_radixtree);
123 : :
124 : : static void
125 : 1 : 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 : 1 : 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 : 1 : radixtree = rt_create(radixtree_ctx);
147 : : #endif
148 : :
149 : : /* Should not find anything in an empty tree */
150 [ - + - - ]: 1 : EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
151 [ - + - - ]: 1 : EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
152 [ - + - - ]: 1 : EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
153 [ - + - - ]: 1 : EXPECT_FALSE(rt_delete(radixtree, 0));
154 [ - + - - ]: 1 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
155 : :
156 : : /* Iterating on an empty tree should not return anything */
157 : 1 : iter = rt_begin_iterate(radixtree);
158 [ - + - - ]: 1 : EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
159 : 1 : rt_end_iterate(iter);
160 : :
161 : 1 : rt_free(radixtree);
162 : :
163 : : #ifdef TEST_SHARED_RT
164 : : dsa_detach(dsa);
165 : : #endif
166 : 1 : }
167 : :
168 : : /* Basic set, find, and delete tests */
169 : : static void
170 : 30 : 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 : 30 : int children = test_info->nkeys;
177 : : #ifdef TEST_SHARED_RT
178 : : int tranche_id = LWLockNewTrancheId();
179 : : dsa_area *dsa;
180 : : #endif
181 : :
182 : 30 : 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 : 30 : radixtree = rt_create(radixtree_ctx);
193 : : #endif
194 : :
195 [ + - + + ]: 30 : elog(NOTICE, "testing node %s with shift %d and %s keys",
196 : : test_info->class_name, shift, asc ? "ascending" : "descending");
197 : :
198 : 30 : keys = palloc(sizeof(uint64) * children);
199 [ + + ]: 2208 : for (int i = 0; i < children; i++)
200 : : {
201 [ + + ]: 2178 : if (asc)
202 : 1089 : keys[i] = (uint64) i << shift;
203 : : else
204 : 1089 : 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 [ + + ]: 2208 : for (int i = 0; i < children; i++)
212 [ - + - - ]: 2178 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) & keys[i]));
213 : :
214 : 30 : rt_stats(radixtree);
215 : :
216 : : /* look up keys */
217 [ + + ]: 2208 : for (int i = 0; i < children; i++)
218 : : {
219 : : TestValueType *value;
220 : :
221 : 2178 : value = rt_find(radixtree, keys[i]);
222 : :
223 : : /* Test rt_find returns the expected value */
224 [ - + - - ]: 2178 : EXPECT_TRUE(value != NULL);
225 [ - + - - ]: 2178 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
226 : : }
227 : :
228 : : /* update keys */
229 [ + + ]: 2208 : for (int i = 0; i < children; i++)
230 : : {
231 : 2178 : TestValueType update = keys[i] + 1;
232 : :
233 : : /* rt_set should report the key found */
234 [ - + - - ]: 2178 : EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) & update));
235 : : }
236 : :
237 : : /* delete and re-insert keys */
238 [ + + ]: 2208 : for (int i = 0; i < children; i++)
239 : : {
240 [ - + - - ]: 2178 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
241 [ - + - - ]: 2178 : EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) & keys[i]));
242 : : }
243 : :
244 : : /* look up keys after deleting and re-inserting */
245 [ + + ]: 2208 : for (int i = 0; i < children; i++)
246 : : {
247 : : TestValueType *value;
248 : :
249 : 2178 : value = rt_find(radixtree, keys[i]);
250 : :
251 : : /* Test that rt_find returns the expected value */
252 [ - + - - ]: 2178 : EXPECT_TRUE(value != NULL);
253 [ - + - - ]: 2178 : EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
254 : : }
255 : :
256 : : /* test that iteration returns the expected keys and values */
257 : 30 : iter = rt_begin_iterate(radixtree);
258 : :
259 [ + + ]: 2208 : 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 [ + + ]: 2178 : if (asc)
267 : 1089 : expected = keys[i];
268 : : else
269 : 1089 : expected = keys[children - 1 - i];
270 : :
271 : 2178 : iterval = rt_iterate_next(iter, &iterkey);
272 : :
273 [ - + - - ]: 2178 : EXPECT_TRUE(iterval != NULL);
274 [ - + - - ]: 2178 : EXPECT_EQ_U64(iterkey, expected);
275 [ - + - - ]: 2178 : EXPECT_EQ_U64(*iterval, expected);
276 : : }
277 : :
278 : 30 : rt_end_iterate(iter);
279 : :
280 : : /* delete all keys again */
281 [ + + ]: 2208 : for (int i = 0; i < children; i++)
282 [ - + - - ]: 2178 : EXPECT_TRUE(rt_delete(radixtree, keys[i]));
283 : :
284 : : /* test that all keys were deleted */
285 [ + + ]: 2208 : for (int i = 0; i < children; i++)
286 [ - + - - ]: 2178 : EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
287 : :
288 : 30 : rt_stats(radixtree);
289 : :
290 : 30 : pfree(keys);
291 : 30 : rt_free(radixtree);
292 : :
293 : : #ifdef TEST_SHARED_RT
294 : : dsa_detach(dsa);
295 : : #endif
296 : 30 : }
297 : :
298 : : static int
299 : 1736946 : key_cmp(const void *a, const void *b)
300 : : {
301 : 1736946 : return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
302 : : }
303 : :
304 : : static void
305 : 1 : 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 : 1 : uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
314 : 1 : uint64 seed = GetCurrentTimestamp();
315 : 1 : 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 : 1 : 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 : 1 : radixtree = rt_create(radixtree_ctx);
333 : : #endif
334 : :
335 : : /* add some random values */
336 : 1 : pg_prng_seed(&state, seed);
337 : 1 : keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
338 [ + + ]: 100001 : for (uint64 i = 0; i < num_keys; i++)
339 : : {
340 : 100000 : uint64 key = pg_prng_uint64(&state) & filter;
341 : 100000 : TestValueType val = (TestValueType) key;
342 : :
343 : : /* save in an array */
344 : 100000 : keys[i] = key;
345 : :
346 : 100000 : rt_set(radixtree, key, &val);
347 : : }
348 : :
349 : 1 : rt_stats(radixtree);
350 : :
351 [ + + ]: 100001 : for (uint64 i = 0; i < num_keys; i++)
352 : : {
353 : : TestValueType *value;
354 : :
355 : 100000 : value = rt_find(radixtree, keys[i]);
356 : :
357 : : /* Test rt_find for values just inserted */
358 [ - + - - ]: 100000 : EXPECT_TRUE(value != NULL);
359 [ - + - - ]: 100000 : EXPECT_EQ_U64(*value, keys[i]);
360 : : }
361 : :
362 : : /* sort keys for iteration and absence tests */
363 : 1 : qsort(keys, num_keys, sizeof(uint64), key_cmp);
364 : :
365 : : /* should not find numbers in between the keys */
366 [ + + ]: 100000 : for (uint64 i = 0; i < num_keys - 1; i++)
367 : : {
368 : : TestValueType *value;
369 : :
370 : : /* skip duplicate and adjacent keys */
371 [ + + + + ]: 99999 : if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
372 : 24598 : continue;
373 : :
374 : : /* should not find the number right after key */
375 : 75401 : value = rt_find(radixtree, keys[i] + 1);
376 [ - + - - ]: 75401 : EXPECT_TRUE(value == NULL);
377 : : }
378 : :
379 : : /* should not find numbers lower than lowest key */
380 [ + + ]: 12 : for (uint64 key = 0; key < keys[0]; key++)
381 : : {
382 : : TestValueType *value;
383 : :
384 : : /* arbitrary stopping point */
385 [ - + ]: 11 : if (key > 10000)
38 john.naylor@postgres 386 :UNC 0 : break;
387 : :
38 john.naylor@postgres 388 :GNC 11 : value = rt_find(radixtree, key);
389 [ - + - - ]: 11 : EXPECT_TRUE(value == NULL);
390 : : }
391 : :
392 : : /* should not find numbers higher than highest key */
393 [ + + ]: 10000 : for (uint64 i = 1; i < 10000; i++)
394 : : {
395 : : TestValueType *value;
396 : :
397 : 9999 : value = rt_find(radixtree, keys[num_keys - 1] + i);
398 [ - + - - ]: 9999 : EXPECT_TRUE(value == NULL);
399 : : }
400 : :
401 : : /* test that iteration returns the expected keys and values */
402 : 1 : iter = rt_begin_iterate(radixtree);
403 : :
404 [ + + ]: 100001 : for (int i = 0; i < num_keys; i++)
405 : : {
406 : : uint64 expected;
407 : : uint64 iterkey;
408 : : TestValueType *iterval;
409 : :
410 : : /* skip duplicate keys */
411 [ + + + + ]: 100000 : if (i < num_keys - 1 && keys[i + 1] == keys[i])
412 : 9075 : continue;
413 : :
414 : 90925 : expected = keys[i];
415 : 90925 : iterval = rt_iterate_next(iter, &iterkey);
416 : :
417 [ - + - - ]: 90925 : EXPECT_TRUE(iterval != NULL);
418 [ - + - - ]: 90925 : EXPECT_EQ_U64(iterkey, expected);
419 [ - + - - ]: 90925 : EXPECT_EQ_U64(*iterval, expected);
420 : : }
421 : :
422 : 1 : rt_end_iterate(iter);
423 : :
424 : : /* reset random number generator for deletion */
425 : 1 : pg_prng_seed(&state, seed);
426 : :
427 : : /* delete in original random order */
428 [ + + ]: 100001 : for (uint64 i = 0; i < num_keys; i++)
429 : : {
430 : 100000 : uint64 key = pg_prng_uint64(&state) & filter;
431 : :
432 : 100000 : rt_delete(radixtree, key);
433 : : }
434 : :
435 [ - + - - ]: 1 : EXPECT_TRUE(rt_num_entries(radixtree) == 0);
436 : :
437 : 1 : pfree(keys);
438 : 1 : rt_free(radixtree);
439 : :
440 : : #ifdef TEST_SHARED_RT
441 : : dsa_detach(dsa);
442 : : #endif
443 : 1 : }
444 : :
445 : : Datum
446 : 1 : test_radixtree(PG_FUNCTION_ARGS)
447 : : {
448 : : /* borrowed from RT_MAX_SHIFT */
449 : 1 : const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
450 : :
451 : 1 : test_empty();
452 : :
453 [ + + ]: 6 : for (int i = 0; i < lengthof(rt_node_class_tests); i++)
454 : : {
455 : 5 : 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 : 5 : test_basic(test_info, 0, true);
459 : 5 : test_basic(test_info, 0, false);
460 : :
461 : : /* a tree with two levels */
462 : 5 : test_basic(test_info, 8, true);
463 : 5 : test_basic(test_info, 8, false);
464 : :
465 : : /* a tree with the maximum number of levels */
466 : 5 : test_basic(test_info, max_shift, true);
467 : 5 : test_basic(test_info, max_shift, false);
468 : : }
469 : :
470 : 1 : test_random();
471 : :
472 : 1 : PG_RETURN_VOID();
473 : : }
|
