LCOV - code coverage report
Current view: top level - src/test/modules/test_radixtree - test_radixtree.c (source / functions) Hit Total Coverage
Test: PostgreSQL 19devel Lines: 126 127 99.2 %
Date: 2025-09-10 22:18:18 Functions: 8 8 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.16