test_radixtree.c File Reference

#include "postgres.h"
#include "common/int.h"
#include "common/pg_prng.h"
#include "fmgr.h"
#include "miscadmin.h"
#include "storage/lwlock.h"
#include "utils/memutils.h"
#include "utils/timestamp.h"
#include "lib/radixtree.h"

Include dependency graph for test_radixtree.c:

Go to the source code of this file.

Data Structures
struct	rt_node_class_test_elem

Macros
#define	UINT64_HEX_FORMAT   "%" INT64_MODIFIER "X"
#define	EXPECT_TRUE(expr)
#define	EXPECT_FALSE(expr)
#define	EXPECT_EQ_U64(result_expr, expected_expr)
#define	RT_PREFIX   rt
#define	RT_SCOPE
#define	RT_DECLARE
#define	RT_DEFINE
#define	RT_USE_DELETE
#define	RT_VALUE_TYPE   TestValueType
#define	RT_DEBUG

Typedefs
typedef uint64	TestValueType
typedef struct rt_node_class_test_elem	rt_node_class_test_elem

Functions
static uint64	rt_num_entries (rt_radix_tree *tree)
	PG_FUNCTION_INFO_V1 (test_radixtree)
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)
static void	test_random (void)
Datum	test_radixtree (PG_FUNCTION_ARGS)

Variables
static rt_node_class_test_elem	rt_node_class_tests []
	PG_MODULE_MAGIC

Macro Definition Documentation

EXPECT_EQ_U64

#define EXPECT_EQ_U64	(		result_expr,
			expected_expr
	)

Value:

    do { \
        uint64      _result = (result_expr); \
        uint64      _expected = (expected_expr); \
        if (_result != _expected) \
            elog(ERROR, \
                 "%s yielded " UINT64_HEX_FORMAT ", expected " UINT64_HEX_FORMAT " (%s) in file \"%s\" line %u", \
                 #result_expr, _result, _expected, #expected_expr, __FILE__, __LINE__); \
    } while (0)

Definition at line 45 of file test_radixtree.c.

EXPECT_FALSE

#define EXPECT_FALSE

(

expr

)

Value:

    do { \
        if (expr) \
            elog(ERROR, \
                 "%s was unexpectedly true in file \"%s\" line %u", \
                 #expr, __FILE__, __LINE__); \
    } while (0)

Definition at line 37 of file test_radixtree.c.

EXPECT_TRUE

#define EXPECT_TRUE

(

expr

)

Value:

    do { \
        if (!(expr)) \
            elog(ERROR, \
                 "%s was unexpectedly false in file \"%s\" line %u", \
                 #expr, __FILE__, __LINE__); \
    } while (0)

Definition at line 29 of file test_radixtree.c.

RT_DEBUG

#define RT_DEBUG

Definition at line 107 of file test_radixtree.c.

RT_DECLARE

#define RT_DECLARE

Definition at line 100 of file test_radixtree.c.

RT_DEFINE

#define RT_DEFINE

Definition at line 101 of file test_radixtree.c.

RT_PREFIX

#define RT_PREFIX   rt

Definition at line 98 of file test_radixtree.c.

RT_SCOPE

#define RT_SCOPE

Definition at line 99 of file test_radixtree.c.

RT_USE_DELETE

#define RT_USE_DELETE

Definition at line 102 of file test_radixtree.c.

RT_VALUE_TYPE

#define RT_VALUE_TYPE   TestValueType

Definition at line 103 of file test_radixtree.c.

UINT64_HEX_FORMAT

#define UINT64_HEX_FORMAT   "%" INT64_MODIFIER "X"

Definition at line 26 of file test_radixtree.c.

Typedef Documentation

rt_node_class_test_elem

typedef struct rt_node_class_test_elem rt_node_class_test_elem

TestValueType

typedef uint64 TestValueType

Definition at line 60 of file test_radixtree.c.

Function Documentation

key_cmp()

static int key_cmp ( const void *  a, const void *  b  )

static

Definition at line 299 of file test_radixtree.c.

{
    return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
}

References a, b, and pg_cmp_u64().

Referenced by test_random().

PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1

(

test_radixtree

)

rt_num_entries()

static uint64 rt_num_entries ( rt_radix_tree *  tree )

static

Definition at line 115 of file test_radixtree.c.

{
    return tree->ctl->num_keys;
}

References tree.

Referenced by test_empty(), and test_random().

test_basic()

static void test_basic ( rt_node_class_test_elem *  test_info, int  shift, bool  asc  )

static

Definition at line 170 of file test_radixtree.c.

{
    MemoryContext radixtree_ctx;
    rt_radix_tree *radixtree;
    rt_iter    *iter;
    uint64     *keys;
    int         children = test_info->nkeys;
#ifdef TEST_SHARED_RT
    int         tranche_id = LWLockNewTrancheId();
    dsa_area   *dsa;
#endif
 
    radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
                                          "test_radix_tree",
                                          ALLOCSET_SMALL_SIZES);
 
#ifdef TEST_SHARED_RT
    LWLockRegisterTranche(tranche_id, "test_radix_tree");
    dsa = dsa_create(tranche_id);
 
    radixtree = rt_create(radixtree_ctx, dsa, tranche_id);
#else
    radixtree = rt_create(radixtree_ctx);
#endif
 
    elog(NOTICE, "testing node %s with shift %d and %s keys",
         test_info->class_name, shift, asc ? "ascending" : "descending");
 
    keys = palloc(sizeof(uint64) * children);
    for (int i = 0; i < children; i++)
    {
        if (asc)
            keys[i] = (uint64) i << shift;
        else
            keys[i] = (uint64) (children - 1 - i) << shift;
    }
 
    /*
     * Insert keys. Since the tree was just created, rt_set should return
     * false.
     */
    for (int i = 0; i < children; i++)
        EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
 
    rt_stats(radixtree);
 
    /* look up keys */
    for (int i = 0; i < children; i++)
    {
        TestValueType *value;
 
        value = rt_find(radixtree, keys[i]);
 
        /* Test rt_find returns the expected value */
        EXPECT_TRUE(value != NULL);
        EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
    }
 
    /* update keys */
    for (int i = 0; i < children; i++)
    {
        TestValueType update = keys[i] + 1;
 
        /* rt_set should report the key found */
        EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));
    }
 
    /* delete and re-insert keys */
    for (int i = 0; i < children; i++)
    {
        EXPECT_TRUE(rt_delete(radixtree, keys[i]));
        EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));
    }
 
    /* look up keys after deleting and re-inserting */
    for (int i = 0; i < children; i++)
    {
        TestValueType *value;
 
        value = rt_find(radixtree, keys[i]);
 
        /* Test that rt_find returns the expected value */
        EXPECT_TRUE(value != NULL);
        EXPECT_EQ_U64(*value, (TestValueType) keys[i]);
    }
 
    /* test that iteration returns the expected keys and values */
    iter = rt_begin_iterate(radixtree);
 
    for (int i = 0; i < children; i++)
    {
        uint64      expected;
        uint64      iterkey;
        TestValueType *iterval;
 
        /* iteration is ordered by key, so adjust expected value accordingly */
        if (asc)
            expected = keys[i];
        else
            expected = keys[children - 1 - i];
 
        iterval = rt_iterate_next(iter, &iterkey);
 
        EXPECT_TRUE(iterval != NULL);
        EXPECT_EQ_U64(iterkey, expected);
        EXPECT_EQ_U64(*iterval, expected);
    }
 
    rt_end_iterate(iter);
 
    /* delete all keys again */
    for (int i = 0; i < children; i++)
        EXPECT_TRUE(rt_delete(radixtree, keys[i]));
 
    /* test that all keys were deleted */
    for (int i = 0; i < children; i++)
        EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);
 
    rt_stats(radixtree);
 
    pfree(keys);
    rt_free(radixtree);
 
#ifdef TEST_SHARED_RT
    dsa_detach(dsa);
#endif
}

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, rt_node_class_test_elem::class_name, CurrentMemoryContext, dsa_create, dsa_detach(), elog, EXPECT_EQ_U64, EXPECT_FALSE, EXPECT_TRUE, i, LWLockNewTrancheId(), LWLockRegisterTranche(), rt_node_class_test_elem::nkeys, NOTICE, palloc(), pfree(), and value.

Referenced by test_radixtree().

test_empty()

static void test_empty ( void  )

static

Definition at line 125 of file test_radixtree.c.

{
    MemoryContext radixtree_ctx;
    rt_radix_tree *radixtree;
    rt_iter    *iter;
    uint64      key;
#ifdef TEST_SHARED_RT
    int         tranche_id = LWLockNewTrancheId();
    dsa_area   *dsa;
#endif
 
    radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
                                          "test_radix_tree",
                                          ALLOCSET_SMALL_SIZES);
 
#ifdef TEST_SHARED_RT
    LWLockRegisterTranche(tranche_id, "test_radix_tree");
    dsa = dsa_create(tranche_id);
 
    radixtree = rt_create(radixtree_ctx, dsa, tranche_id);
#else
    radixtree = rt_create(radixtree_ctx);
#endif
 
    /* Should not find anything in an empty tree */
    EXPECT_TRUE(rt_find(radixtree, 0) == NULL);
    EXPECT_TRUE(rt_find(radixtree, 1) == NULL);
    EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);
    EXPECT_FALSE(rt_delete(radixtree, 0));
    EXPECT_TRUE(rt_num_entries(radixtree) == 0);
 
    /* Iterating on an empty tree should not return anything */
    iter = rt_begin_iterate(radixtree);
    EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);
    rt_end_iterate(iter);
 
    rt_free(radixtree);
 
#ifdef TEST_SHARED_RT
    dsa_detach(dsa);
#endif
}

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, CurrentMemoryContext, dsa_create, dsa_detach(), EXPECT_FALSE, EXPECT_TRUE, sort-test::key, LWLockNewTrancheId(), LWLockRegisterTranche(), PG_UINT64_MAX, and rt_num_entries().

Referenced by test_radixtree().

test_radixtree()

Datum test_radixtree

(

PG_FUNCTION_ARGS

)

Definition at line 446 of file test_radixtree.c.

{
    /* borrowed from RT_MAX_SHIFT */
    const int   max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;
 
    test_empty();
 
    for (int i = 0; i < lengthof(rt_node_class_tests); i++)
    {
        rt_node_class_test_elem *test_info = &(rt_node_class_tests[i]);
 
        /* a tree with one level, i.e. a single node under the root node */
        test_basic(test_info, 0, true);
        test_basic(test_info, 0, false);
 
        /* a tree with two levels */
        test_basic(test_info, 8, true);
        test_basic(test_info, 8, false);
 
        /* a tree with the maximum number of levels */
        test_basic(test_info, max_shift, true);
        test_basic(test_info, max_shift, false);
    }
 
    test_random();
 
    PG_RETURN_VOID();
}

References BITS_PER_BYTE, i, lengthof, PG_RETURN_VOID, rt_node_class_tests, test_basic(), test_empty(), and test_random().

test_random()

static void test_random ( void  )

static

Definition at line 305 of file test_radixtree.c.

{
    MemoryContext radixtree_ctx;
    rt_radix_tree *radixtree;
    rt_iter    *iter;
    pg_prng_state state;
 
    /* limit memory usage by limiting the key space */
    uint64      filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);
    uint64      seed = GetCurrentTimestamp();
    int         num_keys = 100000;
    uint64     *keys;
#ifdef TEST_SHARED_RT
    int         tranche_id = LWLockNewTrancheId();
    dsa_area   *dsa;
#endif
 
    radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,
                                          "test_radix_tree",
                                          ALLOCSET_SMALL_SIZES);
 
#ifdef TEST_SHARED_RT
    LWLockRegisterTranche(tranche_id, "test_radix_tree");
    dsa = dsa_create(tranche_id);
 
    radixtree = rt_create(radixtree_ctx, dsa, tranche_id);
#else
    radixtree = rt_create(radixtree_ctx);
#endif
 
    /* add some random values */
    pg_prng_seed(&state, seed);
    keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);
    for (uint64 i = 0; i < num_keys; i++)
    {
        uint64      key = pg_prng_uint64(&state) & filter;
        TestValueType val = (TestValueType) key;
 
        /* save in an array */
        keys[i] = key;
 
        rt_set(radixtree, key, &val);
    }
 
    rt_stats(radixtree);
 
    for (uint64 i = 0; i < num_keys; i++)
    {
        TestValueType *value;
 
        value = rt_find(radixtree, keys[i]);
 
        /* Test rt_find for values just inserted */
        EXPECT_TRUE(value != NULL);
        EXPECT_EQ_U64(*value, keys[i]);
    }
 
    /* sort keys for iteration and absence tests */
    qsort(keys, num_keys, sizeof(uint64), key_cmp);
 
    /* should not find numbers in between the keys */
    for (uint64 i = 0; i < num_keys - 1; i++)
    {
        TestValueType *value;
 
        /* skip duplicate and adjacent keys */
        if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)
            continue;
 
        /* should not find the number right after key */
        value = rt_find(radixtree, keys[i] + 1);
        EXPECT_TRUE(value == NULL);
    }
 
    /* should not find numbers lower than lowest key */
    for (uint64 key = 0; key < keys[0]; key++)
    {
        TestValueType *value;
 
        /* arbitrary stopping point */
        if (key > 10000)
            break;
 
        value = rt_find(radixtree, key);
        EXPECT_TRUE(value == NULL);
    }
 
    /* should not find numbers higher than highest key */
    for (uint64 i = 1; i < 10000; i++)
    {
        TestValueType *value;
 
        value = rt_find(radixtree, keys[num_keys - 1] + i);
        EXPECT_TRUE(value == NULL);
    }
 
    /* test that iteration returns the expected keys and values */
    iter = rt_begin_iterate(radixtree);
 
    for (int i = 0; i < num_keys; i++)
    {
        uint64      expected;
        uint64      iterkey;
        TestValueType *iterval;
 
        /* skip duplicate keys */
        if (i < num_keys - 1 && keys[i + 1] == keys[i])
            continue;
 
        expected = keys[i];
        iterval = rt_iterate_next(iter, &iterkey);
 
        EXPECT_TRUE(iterval != NULL);
        EXPECT_EQ_U64(iterkey, expected);
        EXPECT_EQ_U64(*iterval, expected);
    }
 
    rt_end_iterate(iter);
 
    /* reset random number generator for deletion */
    pg_prng_seed(&state, seed);
 
    /* delete in original random order */
    for (uint64 i = 0; i < num_keys; i++)
    {
        uint64      key = pg_prng_uint64(&state) & filter;
 
        rt_delete(radixtree, key);
    }
 
    EXPECT_TRUE(rt_num_entries(radixtree) == 0);
 
    pfree(keys);
    rt_free(radixtree);
 
#ifdef TEST_SHARED_RT
    dsa_detach(dsa);
#endif
}

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, CurrentMemoryContext, dsa_create, dsa_detach(), EXPECT_EQ_U64, EXPECT_TRUE, GetCurrentTimestamp(), i, sort-test::key, key_cmp(), LWLockNewTrancheId(), LWLockRegisterTranche(), palloc(), pfree(), pg_prng_seed(), pg_prng_uint64(), qsort, rt_num_entries(), val, and value.

Referenced by test_radixtree().

Variable Documentation

PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 120 of file test_radixtree.c.

rt_node_class_tests

rt_node_class_test_elem rt_node_class_tests[]

static

Initial value:

=
{
    {
        .class_name = "node-4", 
        .nkeys = 2,
    },
    {
        .class_name = "node-16-lo", 
        .nkeys = 15,
    },
    {
        .class_name = "node-16-hi", 
        .nkeys = 30,
    },
    {
        .class_name = "node-48",    
        .nkeys = 60,
    },
    {
        .class_name = "node-256",   
        .nkeys = 256,
    },
}

Definition at line 72 of file test_radixtree.c.

Referenced by test_radixtree().