PostgreSQL Source Code git master
test_radixtree.c
Go to the documentation of this file.
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 */
57
58/*
59 * The node class name and the number of keys big enough to grow nodes
60 * into each size class.
61 */
63{
65 int nkeys;
67
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 */
110static uint64
111rt_num_entries(rt_radix_tree *tree)
112{
113 return tree->ctl->num_keys;
114}
115
117
119
120static 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
137 "test_radix_tree",
139 radixtree = rt_create(radixtree_ctx);
140#endif
141
142 /* Should not find anything in an empty tree */
143 EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
144 EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
145 EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
146 EXPECT_FALSE(rt_delete(radixtree, 0));
147 EXPECT_TRUE(rt_num_entries(radixtree) == 0);
148
149 /* Iterating on an empty tree should not return anything */
150 iter = rt_begin_iterate(radixtree);
151 EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
152 rt_end_iterate(iter);
153
154 rt_free(radixtree);
155
156#ifdef TEST_SHARED_RT
157 dsa_detach(dsa);
158#endif
159}
160
161/* Basic set, find, and delete tests */
162static void
163test_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 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
180 "test_radix_tree",
182 radixtree = rt_create(radixtree_ctx);
183#endif
184
185 elog(NOTICE, "testing node %s with shift %d and %s keys",
186 test_info->class_name, shift, asc ? "ascending" : "descending");
187
188 keys = palloc(sizeof(uint64) * children);
189 for (int i = 0; i < children; i++)
190 {
191 if (asc)
192 keys[i] = (uint64) i << shift;
193 else
194 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 for (int i = 0; i < children; i++)
202 EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
203
204 rt_stats(radixtree);
205
206 /* look up keys */
207 for (int i = 0; i < children; i++)
208 {
210
211 value = rt_find(radixtree, keys[i]);
212
213 /* Test rt_find returns the expected value */
214 EXPECT_TRUE(value != NULL);
216 }
217
218 /* update keys */
219 for (int i = 0; i < children; i++)
220 {
221 TestValueType update = keys[i] + 1;
222
223 /* rt_set should report the key found */
224 EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));
225 }
226
227 /* delete and re-insert keys */
228 for (int i = 0; i < children; i++)
229 {
230 EXPECT_TRUE(rt_delete(radixtree, keys[i]));
231 EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
232 }
233
234 /* look up keys after deleting and re-inserting */
235 for (int i = 0; i < children; i++)
236 {
238
239 value = rt_find(radixtree, keys[i]);
240
241 /* Test that rt_find returns the expected value */
242 EXPECT_TRUE(value != NULL);
244 }
245
246 /* test that iteration returns the expected keys and values */
247 iter = rt_begin_iterate(radixtree);
248
249 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 if (asc)
257 expected = keys[i];
258 else
259 expected = keys[children - 1 - i];
260
261 iterval = rt_iterate_next(iter, &iterkey);
262
263 EXPECT_TRUE(iterval != NULL);
264 EXPECT_EQ_U64(iterkey, expected);
265 EXPECT_EQ_U64(*iterval, expected);
266 }
267
268 rt_end_iterate(iter);
269
270 /* delete all keys again */
271 for (int i = 0; i < children; i++)
272 EXPECT_TRUE(rt_delete(radixtree, keys[i]));
273
274 /* test that all keys were deleted */
275 for (int i = 0; i < children; i++)
276 EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
277
278 rt_stats(radixtree);
279
280 pfree(keys);
281 rt_free(radixtree);
282
283#ifdef TEST_SHARED_RT
284 dsa_detach(dsa);
285#endif
286}
287
288static int
289key_cmp(const void *a, const void *b)
290{
291 return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
292}
293
294static void
296{
297 rt_radix_tree *radixtree;
298 rt_iter *iter;
300
301 /* limit memory usage by limiting the key space */
302 uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
304 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
317 "test_radix_tree",
319 sizeof(TestValueType));
320 radixtree = rt_create(radixtree_ctx);
321#endif
322
323 /* add some random values */
324 pg_prng_seed(&state, seed);
325 keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
326 for (uint64 i = 0; i < num_keys; i++)
327 {
328 uint64 key = pg_prng_uint64(&state) & filter;
330
331 /* save in an array */
332 keys[i] = key;
333
334 rt_set(radixtree, key, &val);
335 }
336
337 rt_stats(radixtree);
338
339 for (uint64 i = 0; i < num_keys; i++)
340 {
342
343 value = rt_find(radixtree, keys[i]);
344
345 /* Test rt_find for values just inserted */
346 EXPECT_TRUE(value != NULL);
347 EXPECT_EQ_U64(*value, keys[i]);
348 }
349
350 /* sort keys for iteration and absence tests */
351 qsort(keys, num_keys, sizeof(uint64), key_cmp);
352
353 /* should not find numbers in between the keys */
354 for (uint64 i = 0; i < num_keys - 1; i++)
355 {
357
358 /* skip duplicate and adjacent keys */
359 if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
360 continue;
361
362 /* should not find the number right after key */
363 value = rt_find(radixtree, keys[i] + 1);
364 EXPECT_TRUE(value == NULL);
365 }
366
367 /* should not find numbers lower than lowest key */
368 for (uint64 key = 0; key < keys[0]; key++)
369 {
371
372 /* arbitrary stopping point */
373 if (key > 10000)
374 break;
375
376 value = rt_find(radixtree, key);
377 EXPECT_TRUE(value == NULL);
378 }
379
380 /* should not find numbers higher than highest key */
381 for (uint64 i = 1; i < 10000; i++)
382 {
384
385 value = rt_find(radixtree, keys[num_keys - 1] + i);
386 EXPECT_TRUE(value == NULL);
387 }
388
389 /* test that iteration returns the expected keys and values */
390 iter = rt_begin_iterate(radixtree);
391
392 for (int i = 0; i < num_keys; i++)
393 {
394 uint64 expected;
395 uint64 iterkey;
396 TestValueType *iterval;
397
398 /* skip duplicate keys */
399 if (i < num_keys - 1 && keys[i + 1] == keys[i])
400 continue;
401
402 expected = keys[i];
403 iterval = rt_iterate_next(iter, &iterkey);
404
405 EXPECT_TRUE(iterval != NULL);
406 EXPECT_EQ_U64(iterkey, expected);
407 EXPECT_EQ_U64(*iterval, expected);
408 }
409
410 rt_end_iterate(iter);
411
412 /* reset random number generator for deletion */
413 pg_prng_seed(&state, seed);
414
415 /* delete in original random order */
416 for (uint64 i = 0; i < num_keys; i++)
417 {
418 uint64 key = pg_prng_uint64(&state) & filter;
419
420 rt_delete(radixtree, key);
421 }
422
423 EXPECT_TRUE(rt_num_entries(radixtree) == 0);
424
425 pfree(keys);
426 rt_free(radixtree);
427
428#ifdef TEST_SHARED_RT
429 dsa_detach(dsa);
430#endif
431}
432
433Datum
435{
436 /* borrowed from RT_MAX_SHIFT */
437 const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
438
439 test_empty();
440
441 for (int i = 0; i < lengthof(rt_node_class_tests); i++)
442 {
444
445 /* a tree with one level, i.e. a single node under the root node */
446 test_basic(test_info, 0, true);
447 test_basic(test_info, 0, false);
448
449 /* a tree with two levels */
450 test_basic(test_info, 8, true);
451 test_basic(test_info, 8, false);
452
453 /* a tree with the maximum number of levels */
454 test_basic(test_info, max_shift, true);
455 test_basic(test_info, max_shift, false);
456 }
457
458 test_random();
459
461}
TimestampTz GetCurrentTimestamp(void)
Definition: timestamp.c:1644
uint64_t uint64
Definition: c.h:489
#define lengthof(array)
Definition: c.h:745
#define PG_UINT64_MAX
Definition: c.h:550
void dsa_detach(dsa_area *area)
Definition: dsa.c:1952
#define dsa_create(tranch_id)
Definition: dsa.h:117
#define elog(elevel,...)
Definition: elog.h:225
#define NOTICE
Definition: elog.h:35
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
static struct @162 value
long val
Definition: informix.c:689
static int pg_cmp_u64(uint64 a, uint64 b)
Definition: int.h:664
int b
Definition: isn.c:69
int a
Definition: isn.c:68
int i
Definition: isn.c:72
void LWLockRegisterTranche(int tranche_id, const char *tranche_name)
Definition: lwlock.c:628
int LWLockNewTrancheId(void)
Definition: lwlock.c:603
void pfree(void *pointer)
Definition: mcxt.c:1521
void * palloc(Size size)
Definition: mcxt.c:1317
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
#define AllocSetContextCreate
Definition: memutils.h:129
#define SLAB_DEFAULT_BLOCK_SIZE
Definition: memutils.h:189
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:170
#define BITS_PER_BYTE
uint64 pg_prng_uint64(pg_prng_state *state)
Definition: pg_prng.c:134
void pg_prng_seed(pg_prng_state *state, uint64 seed)
Definition: pg_prng.c:89
#define qsort(a, b, c, d)
Definition: port.h:475
uintptr_t Datum
Definition: postgres.h:69
tree
Definition: radixtree.h:1828
MemoryContext SlabContextCreate(MemoryContext parent, const char *name, Size blockSize, Size chunkSize)
Definition: slab.c:322
Definition: dsa.c:348
Definition: regguts.h:323
#define EXPECT_TRUE(expr)
uint64 TestValueType
PG_FUNCTION_INFO_V1(test_radixtree)
static uint64 rt_num_entries(rt_radix_tree *tree)
#define EXPECT_FALSE(expr)
PG_MODULE_MAGIC
#define EXPECT_EQ_U64(result_expr, expected_expr)
static void test_random(void)
Datum test_radixtree(PG_FUNCTION_ARGS)
static void test_empty(void)
static void test_basic(rt_node_class_test_elem *test_info, int shift, bool asc)
static int key_cmp(const void *a, const void *b)
struct rt_node_class_test_elem rt_node_class_test_elem
static rt_node_class_test_elem rt_node_class_tests[]