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, 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  */
67 {
68  char *class_name;
69  int nkeys;
71 
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 rt_num_entries(rt_radix_tree *tree)
116 {
117  return tree->ctl->num_keys;
118 }
119 
121 
123 
124 static 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 
137  "test_radix_tree",
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  radixtree = rt_create(radixtree_ctx);
147 #endif
148 
149  /* Should not find anything in an empty tree */
150  EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
151  EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
152  EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
153  EXPECT_FALSE(rt_delete(radixtree, 0));
154  EXPECT_TRUE(rt_num_entries(radixtree) == 0);
155 
156  /* Iterating on an empty tree should not return anything */
157  iter = rt_begin_iterate(radixtree);
158  EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
159  rt_end_iterate(iter);
160 
161  rt_free(radixtree);
162 
163 #ifdef TEST_SHARED_RT
164  dsa_detach(dsa);
165 #endif
166 }
167 
168 /* Basic set, find, and delete tests */
169 static void
170 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  int children = test_info->nkeys;
177 #ifdef TEST_SHARED_RT
178  int tranche_id = LWLockNewTrancheId();
179  dsa_area *dsa;
180 #endif
181 
183  "test_radix_tree",
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  radixtree = rt_create(radixtree_ctx);
193 #endif
194 
195  elog(NOTICE, "testing node %s with shift %d and %s keys",
196  test_info->class_name, shift, asc ? "ascending" : "descending");
197 
198  keys = palloc(sizeof(uint64) * children);
199  for (int i = 0; i < children; i++)
200  {
201  if (asc)
202  keys[i] = (uint64) i << shift;
203  else
204  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  for (int i = 0; i < children; i++)
212  EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
213 
214  rt_stats(radixtree);
215 
216  /* look up keys */
217  for (int i = 0; i < children; i++)
218  {
220 
221  value = rt_find(radixtree, keys[i]);
222 
223  /* Test rt_find returns the expected value */
224  EXPECT_TRUE(value != NULL);
225  EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
226  }
227 
228  /* update keys */
229  for (int i = 0; i < children; i++)
230  {
231  TestValueType update = keys[i] + 1;
232 
233  /* rt_set should report the key found */
234  EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));
235  }
236 
237  /* delete and re-insert keys */
238  for (int i = 0; i < children; i++)
239  {
240  EXPECT_TRUE(rt_delete(radixtree, keys[i]));
241  EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
242  }
243 
244  /* look up keys after deleting and re-inserting */
245  for (int i = 0; i < children; i++)
246  {
248 
249  value = rt_find(radixtree, keys[i]);
250 
251  /* Test that rt_find returns the expected value */
252  EXPECT_TRUE(value != NULL);
253  EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
254  }
255 
256  /* test that iteration returns the expected keys and values */
257  iter = rt_begin_iterate(radixtree);
258 
259  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  if (asc)
267  expected = keys[i];
268  else
269  expected = keys[children - 1 - i];
270 
271  iterval = rt_iterate_next(iter, &iterkey);
272 
273  EXPECT_TRUE(iterval != NULL);
274  EXPECT_EQ_U64(iterkey, expected);
275  EXPECT_EQ_U64(*iterval, expected);
276  }
277 
278  rt_end_iterate(iter);
279 
280  /* delete all keys again */
281  for (int i = 0; i < children; i++)
282  EXPECT_TRUE(rt_delete(radixtree, keys[i]));
283 
284  /* test that all keys were deleted */
285  for (int i = 0; i < children; i++)
286  EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
287 
288  rt_stats(radixtree);
289 
290  pfree(keys);
291  rt_free(radixtree);
292 
293 #ifdef TEST_SHARED_RT
294  dsa_detach(dsa);
295 #endif
296 }
297 
298 static int
299 key_cmp(const void *a, const void *b)
300 {
301  return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
302 }
303 
304 static void
306 {
307  MemoryContext radixtree_ctx;
308  rt_radix_tree *radixtree;
309  rt_iter *iter;
311 
312  /* limit memory usage by limiting the key space */
313  uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
314  uint64 seed = GetCurrentTimestamp();
315  int num_keys = 100000;
316  uint64 *keys;
317 #ifdef TEST_SHARED_RT
318  int tranche_id = LWLockNewTrancheId();
319  dsa_area *dsa;
320 #endif
321 
323  "test_radix_tree",
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  radixtree = rt_create(radixtree_ctx);
333 #endif
334 
335  /* add some random values */
336  pg_prng_seed(&state, seed);
337  keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
338  for (uint64 i = 0; i < num_keys; i++)
339  {
340  uint64 key = pg_prng_uint64(&state) & filter;
342 
343  /* save in an array */
344  keys[i] = key;
345 
346  rt_set(radixtree, key, &val);
347  }
348 
349  rt_stats(radixtree);
350 
351  for (uint64 i = 0; i < num_keys; i++)
352  {
354 
355  value = rt_find(radixtree, keys[i]);
356 
357  /* Test rt_find for values just inserted */
358  EXPECT_TRUE(value != NULL);
359  EXPECT_EQ_U64(*value, keys[i]);
360  }
361 
362  /* sort keys for iteration and absence tests */
363  qsort(keys, num_keys, sizeof(uint64), key_cmp);
364 
365  /* should not find numbers in between the keys */
366  for (uint64 i = 0; i < num_keys - 1; i++)
367  {
369 
370  /* skip duplicate and adjacent keys */
371  if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
372  continue;
373 
374  /* should not find the number right after key */
375  value = rt_find(radixtree, keys[i] + 1);
376  EXPECT_TRUE(value == NULL);
377  }
378 
379  /* should not find numbers lower than lowest key */
380  for (uint64 key = 0; key < keys[0]; key++)
381  {
383 
384  /* arbitrary stopping point */
385  if (key > 10000)
386  break;
387 
388  value = rt_find(radixtree, key);
389  EXPECT_TRUE(value == NULL);
390  }
391 
392  /* should not find numbers higher than highest key */
393  for (uint64 i = 1; i < 10000; i++)
394  {
396 
397  value = rt_find(radixtree, keys[num_keys - 1] + i);
398  EXPECT_TRUE(value == NULL);
399  }
400 
401  /* test that iteration returns the expected keys and values */
402  iter = rt_begin_iterate(radixtree);
403 
404  for (int i = 0; i < num_keys; i++)
405  {
406  uint64 expected;
407  uint64 iterkey;
408  TestValueType *iterval;
409 
410  /* skip duplicate keys */
411  if (i < num_keys - 1 && keys[i + 1] == keys[i])
412  continue;
413 
414  expected = keys[i];
415  iterval = rt_iterate_next(iter, &iterkey);
416 
417  EXPECT_TRUE(iterval != NULL);
418  EXPECT_EQ_U64(iterkey, expected);
419  EXPECT_EQ_U64(*iterval, expected);
420  }
421 
422  rt_end_iterate(iter);
423 
424  /* reset random number generator for deletion */
425  pg_prng_seed(&state, seed);
426 
427  /* delete in original random order */
428  for (uint64 i = 0; i < num_keys; i++)
429  {
430  uint64 key = pg_prng_uint64(&state) & filter;
431 
432  rt_delete(radixtree, key);
433  }
434 
435  EXPECT_TRUE(rt_num_entries(radixtree) == 0);
436 
437  pfree(keys);
438  rt_free(radixtree);
439 
440 #ifdef TEST_SHARED_RT
441  dsa_detach(dsa);
442 #endif
443 }
444 
445 Datum
447 {
448  /* borrowed from RT_MAX_SHIFT */
449  const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
450 
451  test_empty();
452 
453  for (int i = 0; i < lengthof(rt_node_class_tests); i++)
454  {
456 
457  /* a tree with one level, i.e. a single node under the root node */
458  test_basic(test_info, 0, true);
459  test_basic(test_info, 0, false);
460 
461  /* a tree with two levels */
462  test_basic(test_info, 8, true);
463  test_basic(test_info, 8, false);
464 
465  /* a tree with the maximum number of levels */
466  test_basic(test_info, max_shift, true);
467  test_basic(test_info, max_shift, false);
468  }
469 
470  test_random();
471 
472  PG_RETURN_VOID();
473 }
TimestampTz GetCurrentTimestamp(void)
Definition: timestamp.c:1654
#define lengthof(array)
Definition: c.h:788
#define PG_UINT64_MAX
Definition: c.h:593
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:224
#define NOTICE
Definition: elog.h:35
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
long val
Definition: informix.c:670
static struct @155 value
static int pg_cmp_u64(uint64 a, uint64 b)
Definition: int.h:501
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int i
Definition: isn.c:73
void LWLockRegisterTranche(int tranche_id, const char *tranche_name)
Definition: lwlock.c:630
int LWLockNewTrancheId(void)
Definition: lwlock.c:606
void pfree(void *pointer)
Definition: mcxt.c:1520
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void * palloc(Size size)
Definition: mcxt.c:1316
#define AllocSetContextCreate
Definition: memutils.h:129
#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:449
uintptr_t Datum
Definition: postgres.h:64
tree
Definition: radixtree.h:1832
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[]