PostgreSQL Source Code  git master
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)
#define ERROR
Definition: elog.h:39
#define UINT64_HEX_FORMAT

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

◆ 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.

300 {
301  return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);
302 }
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

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.

116 {
117  return tree->ctl->num_keys;
118 }
tree
Definition: radixtree.h:1832

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.

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 }
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
static struct @155 value
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
Definition: dsa.c:348
#define EXPECT_TRUE(expr)
uint64 TestValueType
#define EXPECT_FALSE(expr)
#define EXPECT_EQ_U64(result_expr, expected_expr)

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.

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 }
#define PG_UINT64_MAX
Definition: c.h:593
static uint64 rt_num_entries(rt_radix_tree *tree)

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.

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 }
#define lengthof(array)
Definition: c.h:788
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define BITS_PER_BYTE
static void test_random(void)
static void test_empty(void)
static void test_basic(rt_node_class_test_elem *test_info, int shift, bool asc)
static rt_node_class_test_elem rt_node_class_tests[]

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.

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 }
TimestampTz GetCurrentTimestamp(void)
Definition: timestamp.c:1654
long val
Definition: informix.c:670
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
Definition: regguts.h:323
static int key_cmp(const void *a, const void *b)

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().