PostgreSQL Source Code  git master
test_rbtree.c
Go to the documentation of this file.
1 /*--------------------------------------------------------------------------
2  *
3  * test_rbtree.c
4  * Test correctness of red-black tree operations.
5  *
6  * Copyright (c) 2009-2022, PostgreSQL Global Development Group
7  *
8  * IDENTIFICATION
9  * src/test/modules/test_rbtree/test_rbtree.c
10  *
11  * -------------------------------------------------------------------------
12  */
13 
14 #include "postgres.h"
15 
16 #include "common/pg_prng.h"
17 #include "fmgr.h"
18 #include "lib/rbtree.h"
19 #include "utils/memutils.h"
20 
22 
23 
24 /*
25  * Our test trees store an integer key, and nothing else.
26  */
27 typedef struct IntRBTreeNode
28 {
30  int key;
32 
33 
34 /*
35  * Node comparator. We don't worry about overflow in the subtraction,
36  * since none of our test keys are negative.
37  */
38 static int
39 irbt_cmp(const RBTNode *a, const RBTNode *b, void *arg)
40 {
41  const IntRBTreeNode *ea = (const IntRBTreeNode *) a;
42  const IntRBTreeNode *eb = (const IntRBTreeNode *) b;
43 
44  return ea->key - eb->key;
45 }
46 
47 /*
48  * Node combiner. For testing purposes, just check that library doesn't
49  * try to combine unequal keys.
50  */
51 static void
52 irbt_combine(RBTNode *existing, const RBTNode *newdata, void *arg)
53 {
54  const IntRBTreeNode *eexist = (const IntRBTreeNode *) existing;
55  const IntRBTreeNode *enew = (const IntRBTreeNode *) newdata;
56 
57  if (eexist->key != enew->key)
58  elog(ERROR, "red-black tree combines %d into %d",
59  enew->key, eexist->key);
60 }
61 
62 /* Node allocator */
63 static RBTNode *
65 {
66  return (RBTNode *) palloc(sizeof(IntRBTreeNode));
67 }
68 
69 /* Node freer */
70 static void
71 irbt_free(RBTNode *node, void *arg)
72 {
73  pfree(node);
74 }
75 
76 /*
77  * Create a red-black tree using our support functions
78  */
79 static RBTree *
81 {
82  return rbt_create(sizeof(IntRBTreeNode),
83  irbt_cmp,
85  irbt_alloc,
86  irbt_free,
87  NULL);
88 }
89 
90 /*
91  * Generate a random permutation of the integers 0..size-1
92  */
93 static int *
94 GetPermutation(int size)
95 {
96  int *permutation;
97  int i;
98 
99  permutation = (int *) palloc(size * sizeof(int));
100 
101  permutation[0] = 0;
102 
103  /*
104  * This is the "inside-out" variant of the Fisher-Yates shuffle algorithm.
105  * Notionally, we append each new value to the array and then swap it with
106  * a randomly-chosen array element (possibly including itself, else we
107  * fail to generate permutations with the last integer last). The swap
108  * step can be optimized by combining it with the insertion.
109  */
110  for (i = 1; i < size; i++)
111  {
113 
114  if (j < i) /* avoid fetching undefined data if j=i */
115  permutation[i] = permutation[j];
116  permutation[j] = i;
117  }
118 
119  return permutation;
120 }
121 
122 /*
123  * Populate an empty RBTree with "size" integers having the values
124  * 0, step, 2*step, 3*step, ..., inserting them in random order
125  */
126 static void
127 rbt_populate(RBTree *tree, int size, int step)
128 {
129  int *permutation = GetPermutation(size);
130  IntRBTreeNode node;
131  bool isNew;
132  int i;
133 
134  /* Insert values. We don't expect any collisions. */
135  for (i = 0; i < size; i++)
136  {
137  node.key = step * permutation[i];
138  rbt_insert(tree, (RBTNode *) &node, &isNew);
139  if (!isNew)
140  elog(ERROR, "unexpected !isNew result from rbt_insert");
141  }
142 
143  /*
144  * Re-insert the first value to make sure collisions work right. It's
145  * probably not useful to test that case over again for all the values.
146  */
147  if (size > 0)
148  {
149  node.key = step * permutation[0];
150  rbt_insert(tree, (RBTNode *) &node, &isNew);
151  if (isNew)
152  elog(ERROR, "unexpected isNew result from rbt_insert");
153  }
154 
155  pfree(permutation);
156 }
157 
158 /*
159  * Check the correctness of left-right traversal.
160  * Left-right traversal is correct if all elements are
161  * visited in increasing order.
162  */
163 static void
164 testleftright(int size)
165 {
166  RBTree *tree = create_int_rbtree();
167  IntRBTreeNode *node;
168  RBTreeIterator iter;
169  int lastKey = -1;
170  int count = 0;
171 
172  /* check iteration over empty tree */
173  rbt_begin_iterate(tree, LeftRightWalk, &iter);
174  if (rbt_iterate(&iter) != NULL)
175  elog(ERROR, "left-right walk over empty tree produced an element");
176 
177  /* fill tree with consecutive natural numbers */
178  rbt_populate(tree, size, 1);
179 
180  /* iterate over the tree */
181  rbt_begin_iterate(tree, LeftRightWalk, &iter);
182 
183  while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL)
184  {
185  /* check that order is increasing */
186  if (node->key <= lastKey)
187  elog(ERROR, "left-right walk gives elements not in sorted order");
188  lastKey = node->key;
189  count++;
190  }
191 
192  if (lastKey != size - 1)
193  elog(ERROR, "left-right walk did not reach end");
194  if (count != size)
195  elog(ERROR, "left-right walk missed some elements");
196 }
197 
198 /*
199  * Check the correctness of right-left traversal.
200  * Right-left traversal is correct if all elements are
201  * visited in decreasing order.
202  */
203 static void
204 testrightleft(int size)
205 {
206  RBTree *tree = create_int_rbtree();
207  IntRBTreeNode *node;
208  RBTreeIterator iter;
209  int lastKey = size;
210  int count = 0;
211 
212  /* check iteration over empty tree */
213  rbt_begin_iterate(tree, RightLeftWalk, &iter);
214  if (rbt_iterate(&iter) != NULL)
215  elog(ERROR, "right-left walk over empty tree produced an element");
216 
217  /* fill tree with consecutive natural numbers */
218  rbt_populate(tree, size, 1);
219 
220  /* iterate over the tree */
221  rbt_begin_iterate(tree, RightLeftWalk, &iter);
222 
223  while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL)
224  {
225  /* check that order is decreasing */
226  if (node->key >= lastKey)
227  elog(ERROR, "right-left walk gives elements not in sorted order");
228  lastKey = node->key;
229  count++;
230  }
231 
232  if (lastKey != 0)
233  elog(ERROR, "right-left walk did not reach end");
234  if (count != size)
235  elog(ERROR, "right-left walk missed some elements");
236 }
237 
238 /*
239  * Check the correctness of the rbt_find operation by searching for
240  * both elements we inserted and elements we didn't.
241  */
242 static void
243 testfind(int size)
244 {
245  RBTree *tree = create_int_rbtree();
246  int i;
247 
248  /* Insert even integers from 0 to 2 * (size-1) */
249  rbt_populate(tree, size, 2);
250 
251  /* Check that all inserted elements can be found */
252  for (i = 0; i < size; i++)
253  {
254  IntRBTreeNode node;
255  IntRBTreeNode *resultNode;
256 
257  node.key = 2 * i;
258  resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
259  if (resultNode == NULL)
260  elog(ERROR, "inserted element was not found");
261  if (node.key != resultNode->key)
262  elog(ERROR, "find operation in rbtree gave wrong result");
263  }
264 
265  /*
266  * Check that not-inserted elements can not be found, being sure to try
267  * values before the first and after the last element.
268  */
269  for (i = -1; i <= 2 * size; i += 2)
270  {
271  IntRBTreeNode node;
272  IntRBTreeNode *resultNode;
273 
274  node.key = i;
275  resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
276  if (resultNode != NULL)
277  elog(ERROR, "not-inserted element was found");
278  }
279 }
280 
281 /*
282  * Check the correctness of the rbt_find_less() and rbt_find_great() functions
283  * by searching for an equal key and iterating the lesser keys then the greater
284  * keys.
285  */
286 static void
287 testfindltgt(int size)
288 {
289  RBTree *tree = create_int_rbtree();
290 
291  /*
292  * Using the size as the random key to search wouldn't allow us to get at
293  * least one greater match, so we do size - 1
294  */
295  int randomKey = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1);
296  bool keyDeleted;
297  IntRBTreeNode searchNode = {.key = randomKey};
298  IntRBTreeNode *lteNode;
299  IntRBTreeNode *gteNode;
300  IntRBTreeNode *node;
301 
302  /* Insert natural numbers */
303  rbt_populate(tree, size, 1);
304 
305  /*
306  * Since the search key is included in the naturals of the tree, we're
307  * sure to find an equal match
308  */
309  lteNode = (IntRBTreeNode *) rbt_find_less(tree, (RBTNode *) &searchNode, true);
310  gteNode = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode, true);
311 
312  if (lteNode == NULL || lteNode->key != searchNode.key)
313  elog(ERROR, "rbt_find_less() didn't find the equal key");
314 
315  if (gteNode == NULL || gteNode->key != searchNode.key)
316  elog(ERROR, "rbt_find_great() didn't find the equal key");
317 
318  if (lteNode != gteNode)
319  elog(ERROR, "rbt_find_less() and rbt_find_great() found different equal keys");
320 
321  /* Find the rest of the naturals lesser than the search key */
322  keyDeleted = false;
323  for (; searchNode.key > 0; searchNode.key--)
324  {
325  /*
326  * Find the next key. If the current key is deleted, we can pass
327  * equal_match == true and still find the next one.
328  */
329  node = (IntRBTreeNode *) rbt_find_less(tree, (RBTNode *) &searchNode,
330  keyDeleted);
331 
332  /* ensure we find a lesser match */
333  if (!node || !(node->key < searchNode.key))
334  elog(ERROR, "rbt_find_less() didn't find a lesser key");
335 
336  /* randomly delete the found key or leave it */
337  keyDeleted = (pg_prng_uint64_range(&pg_global_prng_state, 0, 1) == 1);
338  if (keyDeleted)
339  rbt_delete(tree, (RBTNode *) node);
340  }
341 
342  /* Find the rest of the naturals greater than the search key */
343  keyDeleted = false;
344  for (searchNode.key = randomKey; searchNode.key < size - 1; searchNode.key++)
345  {
346  /*
347  * Find the next key. If the current key is deleted, we can pass
348  * equal_match == true and still find the next one.
349  */
350  node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode,
351  keyDeleted);
352 
353  /* ensure we find a greater match */
354  if (!node || !(node->key > searchNode.key))
355  elog(ERROR, "rbt_find_great() didn't find a greater key");
356 
357  /* randomly delete the found key or leave it */
358  keyDeleted = (pg_prng_uint64_range(&pg_global_prng_state, 0, 1) == 1);
359  if (keyDeleted)
360  rbt_delete(tree, (RBTNode *) node);
361  }
362 
363  /* Check out of bounds searches find nothing */
364  searchNode.key = -1;
365  node = (IntRBTreeNode *) rbt_find_less(tree, (RBTNode *) &searchNode, true);
366  if (node != NULL)
367  elog(ERROR, "rbt_find_less() found non-inserted element");
368  searchNode.key = 0;
369  node = (IntRBTreeNode *) rbt_find_less(tree, (RBTNode *) &searchNode, false);
370  if (node != NULL)
371  elog(ERROR, "rbt_find_less() found non-inserted element");
372  searchNode.key = size;
373  node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode, true);
374  if (node != NULL)
375  elog(ERROR, "rbt_find_great() found non-inserted element");
376  searchNode.key = size - 1;
377  node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode, false);
378  if (node != NULL)
379  elog(ERROR, "rbt_find_great() found non-inserted element");
380 }
381 
382 /*
383  * Check the correctness of the rbt_leftmost operation.
384  * This operation should always return the smallest element of the tree.
385  */
386 static void
387 testleftmost(int size)
388 {
389  RBTree *tree = create_int_rbtree();
390  IntRBTreeNode *result;
391 
392  /* Check that empty tree has no leftmost element */
393  if (rbt_leftmost(tree) != NULL)
394  elog(ERROR, "leftmost node of empty tree is not NULL");
395 
396  /* fill tree with consecutive natural numbers */
397  rbt_populate(tree, size, 1);
398 
399  /* Check that leftmost element is the smallest one */
400  result = (IntRBTreeNode *) rbt_leftmost(tree);
401  if (result == NULL || result->key != 0)
402  elog(ERROR, "rbt_leftmost gave wrong result");
403 }
404 
405 /*
406  * Check the correctness of the rbt_delete operation.
407  */
408 static void
409 testdelete(int size, int delsize)
410 {
411  RBTree *tree = create_int_rbtree();
412  int *deleteIds;
413  bool *chosen;
414  int i;
415 
416  /* fill tree with consecutive natural numbers */
417  rbt_populate(tree, size, 1);
418 
419  /* Choose unique ids to delete */
420  deleteIds = (int *) palloc(delsize * sizeof(int));
421  chosen = (bool *) palloc0(size * sizeof(bool));
422 
423  for (i = 0; i < delsize; i++)
424  {
425  int k = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1);
426 
427  while (chosen[k])
428  k = (k + 1) % size;
429  deleteIds[i] = k;
430  chosen[k] = true;
431  }
432 
433  /* Delete elements */
434  for (i = 0; i < delsize; i++)
435  {
437  IntRBTreeNode *node;
438 
439  find.key = deleteIds[i];
440  /* Locate the node to be deleted */
441  node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find);
442  if (node == NULL || node->key != deleteIds[i])
443  elog(ERROR, "expected element was not found during deleting");
444  /* Delete it */
445  rbt_delete(tree, (RBTNode *) node);
446  }
447 
448  /* Check that deleted elements are deleted */
449  for (i = 0; i < size; i++)
450  {
451  IntRBTreeNode node;
452  IntRBTreeNode *result;
453 
454  node.key = i;
455  result = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
456  if (chosen[i])
457  {
458  /* Deleted element should be absent */
459  if (result != NULL)
460  elog(ERROR, "deleted element still present in the rbtree");
461  }
462  else
463  {
464  /* Else it should be present */
465  if (result == NULL || result->key != i)
466  elog(ERROR, "delete operation removed wrong rbtree value");
467  }
468  }
469 
470  /* Delete remaining elements, so as to exercise reducing tree to empty */
471  for (i = 0; i < size; i++)
472  {
474  IntRBTreeNode *node;
475 
476  if (chosen[i])
477  continue;
478  find.key = i;
479  /* Locate the node to be deleted */
480  node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find);
481  if (node == NULL || node->key != i)
482  elog(ERROR, "expected element was not found during deleting");
483  /* Delete it */
484  rbt_delete(tree, (RBTNode *) node);
485  }
486 
487  /* Tree should now be empty */
488  if (rbt_leftmost(tree) != NULL)
489  elog(ERROR, "deleting all elements failed");
490 
491  pfree(deleteIds);
492  pfree(chosen);
493 }
494 
495 /*
496  * SQL-callable entry point to perform all tests
497  *
498  * Argument is the number of entries to put in the trees
499  */
501 
502 Datum
504 {
505  int size = PG_GETARG_INT32(0);
506 
507  if (size <= 0 || size > MaxAllocSize / sizeof(int))
508  elog(ERROR, "invalid size for test_rb_tree: %d", size);
509  testleftright(size);
510  testrightleft(size);
511  testfind(size);
512  testfindltgt(size);
513  testleftmost(size);
514  testdelete(size, Max(size / 10, 1));
515  PG_RETURN_VOID();
516 }
#define Max(x, y)
Definition: c.h:931
#define ERROR
Definition: elog.h:35
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
void pfree(void *pointer)
Definition: mcxt.c:1306
void * palloc0(Size size)
Definition: mcxt.c:1230
void * palloc(Size size)
Definition: mcxt.c:1199
#define MaxAllocSize
Definition: memutils.h:40
void * arg
uint64 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
Definition: pg_prng.c:138
pg_prng_state pg_global_prng_state
Definition: pg_prng.c:28
uintptr_t Datum
Definition: postgres.h:412
RBTNode * rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:172
RBTNode * rbt_iterate(RBTreeIterator *iter)
Definition: rbtree.c:826
RBTNode * rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
Definition: rbtree.c:453
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:802
RBTree * rbt_create(Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
Definition: rbtree.c:102
RBTNode * rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:203
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:235
void rbt_delete(RBTree *rbt, RBTNode *node)
Definition: rbtree.c:695
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
@ RightLeftWalk
Definition: rbtree.h:38
@ LeftRightWalk
Definition: rbtree.h:37
static int find(struct vars *v, struct cnfa *cnfa, struct colormap *cm)
Definition: regexec.c:419
RBTNode rbtnode
Definition: test_rbtree.c:29
Definition: rbtree.h:24
Definition: rbtree.c:42
Datum test_rb_tree(PG_FUNCTION_ARGS)
Definition: test_rbtree.c:503
PG_MODULE_MAGIC
Definition: test_rbtree.c:21
static void irbt_free(RBTNode *node, void *arg)
Definition: test_rbtree.c:71
static int * GetPermutation(int size)
Definition: test_rbtree.c:94
static void testleftright(int size)
Definition: test_rbtree.c:164
static void irbt_combine(RBTNode *existing, const RBTNode *newdata, void *arg)
Definition: test_rbtree.c:52
PG_FUNCTION_INFO_V1(test_rb_tree)
static void rbt_populate(RBTree *tree, int size, int step)
Definition: test_rbtree.c:127
static RBTree * create_int_rbtree(void)
Definition: test_rbtree.c:80
static void testleftmost(int size)
Definition: test_rbtree.c:387
static void testdelete(int size, int delsize)
Definition: test_rbtree.c:409
static void testfindltgt(int size)
Definition: test_rbtree.c:287
struct IntRBTreeNode IntRBTreeNode
static int irbt_cmp(const RBTNode *a, const RBTNode *b, void *arg)
Definition: test_rbtree.c:39
static RBTNode * irbt_alloc(void *arg)
Definition: test_rbtree.c:64
static void testrightleft(int size)
Definition: test_rbtree.c:204
static void testfind(int size)
Definition: test_rbtree.c:243