PostgreSQL Source Code  git master
test_rbtree.c File Reference
#include "postgres.h"
#include "common/pg_prng.h"
#include "fmgr.h"
#include "lib/rbtree.h"
#include "utils/memutils.h"
Include dependency graph for test_rbtree.c:

Go to the source code of this file.

Data Structures

struct  IntRBTreeNode
 

Typedefs

typedef struct IntRBTreeNode IntRBTreeNode
 

Functions

static int irbt_cmp (const RBTNode *a, const RBTNode *b, void *arg)
 
static void irbt_combine (RBTNode *existing, const RBTNode *newdata, void *arg)
 
static RBTNodeirbt_alloc (void *arg)
 
static void irbt_free (RBTNode *node, void *arg)
 
static RBTreecreate_int_rbtree (void)
 
static int * GetPermutation (int size)
 
static void rbt_populate (RBTree *tree, int size, int step)
 
static void testleftright (int size)
 
static void testrightleft (int size)
 
static void testfind (int size)
 
static void testleftmost (int size)
 
static void testdelete (int size, int delsize)
 
 PG_FUNCTION_INFO_V1 (test_rb_tree)
 
Datum test_rb_tree (PG_FUNCTION_ARGS)
 

Variables

 PG_MODULE_MAGIC
 

Typedef Documentation

◆ IntRBTreeNode

typedef struct IntRBTreeNode IntRBTreeNode

Function Documentation

◆ create_int_rbtree()

static RBTree* create_int_rbtree ( void  )
static

Definition at line 80 of file test_rbtree.c.

81 {
82  return rbt_create(sizeof(IntRBTreeNode),
83  irbt_cmp,
85  irbt_alloc,
86  irbt_free,
87  NULL);
88 }
RBTree * rbt_create(Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
Definition: rbtree.c:102
static void irbt_free(RBTNode *node, void *arg)
Definition: test_rbtree.c:71
static void irbt_combine(RBTNode *existing, const RBTNode *newdata, void *arg)
Definition: test_rbtree.c:52
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

References irbt_alloc(), irbt_cmp(), irbt_combine(), irbt_free(), and rbt_create().

Referenced by testdelete(), testfind(), testleftmost(), testleftright(), and testrightleft().

◆ GetPermutation()

static int* GetPermutation ( int  size)
static

Definition at line 94 of file test_rbtree.c.

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 }
int j
Definition: isn.c:74
int i
Definition: isn.c:73
void * palloc(Size size)
Definition: mcxt.c:1062
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

References i, j, palloc(), pg_global_prng_state, and pg_prng_uint64_range().

Referenced by rbt_populate().

◆ irbt_alloc()

static RBTNode* irbt_alloc ( void *  arg)
static

Definition at line 64 of file test_rbtree.c.

65 {
66  return (RBTNode *) palloc(sizeof(IntRBTreeNode));
67 }
Definition: rbtree.h:24

References palloc().

Referenced by create_int_rbtree().

◆ irbt_cmp()

static int irbt_cmp ( const RBTNode a,
const RBTNode b,
void *  arg 
)
static

Definition at line 39 of file test_rbtree.c.

40 {
41  const IntRBTreeNode *ea = (const IntRBTreeNode *) a;
42  const IntRBTreeNode *eb = (const IntRBTreeNode *) b;
43 
44  return ea->key - eb->key;
45 }
int b
Definition: isn.c:70
int a
Definition: isn.c:69

References a, b, and IntRBTreeNode::key.

Referenced by create_int_rbtree().

◆ irbt_combine()

static void irbt_combine ( RBTNode existing,
const RBTNode newdata,
void *  arg 
)
static

Definition at line 52 of file test_rbtree.c.

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 }
#define ERROR
Definition: elog.h:33
#define elog(elevel,...)
Definition: elog.h:218

References elog, ERROR, and IntRBTreeNode::key.

Referenced by create_int_rbtree().

◆ irbt_free()

static void irbt_free ( RBTNode node,
void *  arg 
)
static

Definition at line 71 of file test_rbtree.c.

72 {
73  pfree(node);
74 }
void pfree(void *pointer)
Definition: mcxt.c:1169

References pfree().

Referenced by create_int_rbtree().

◆ PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1 ( test_rb_tree  )

◆ rbt_populate()

static void rbt_populate ( RBTree tree,
int  size,
int  step 
)
static

Definition at line 127 of file test_rbtree.c.

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 }
RBTNode * rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
Definition: rbtree.c:391
static int * GetPermutation(int size)
Definition: test_rbtree.c:94

References elog, ERROR, GetPermutation(), i, IntRBTreeNode::key, pfree(), and rbt_insert().

Referenced by testdelete(), testfind(), testleftmost(), testleftright(), and testrightleft().

◆ test_rb_tree()

Datum test_rb_tree ( PG_FUNCTION_ARGS  )

Definition at line 402 of file test_rbtree.c.

403 {
404  int size = PG_GETARG_INT32(0);
405 
406  if (size <= 0 || size > MaxAllocSize / sizeof(int))
407  elog(ERROR, "invalid size for test_rb_tree: %d", size);
408  testleftright(size);
409  testrightleft(size);
410  testfind(size);
411  testleftmost(size);
412  testdelete(size, Max(size / 10, 1));
413  PG_RETURN_VOID();
414 }
#define Max(x, y)
Definition: c.h:980
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define MaxAllocSize
Definition: memutils.h:40
static void testleftright(int size)
Definition: test_rbtree.c:164
static void testleftmost(int size)
Definition: test_rbtree.c:286
static void testdelete(int size, int delsize)
Definition: test_rbtree.c:308
static void testrightleft(int size)
Definition: test_rbtree.c:204
static void testfind(int size)
Definition: test_rbtree.c:243

References elog, ERROR, Max, MaxAllocSize, PG_GETARG_INT32, PG_RETURN_VOID, testdelete(), testfind(), testleftmost(), testleftright(), and testrightleft().

◆ testdelete()

static void testdelete ( int  size,
int  delsize 
)
static

Definition at line 308 of file test_rbtree.c.

309 {
310  RBTree *tree = create_int_rbtree();
311  int *deleteIds;
312  bool *chosen;
313  int i;
314 
315  /* fill tree with consecutive natural numbers */
316  rbt_populate(tree, size, 1);
317 
318  /* Choose unique ids to delete */
319  deleteIds = (int *) palloc(delsize * sizeof(int));
320  chosen = (bool *) palloc0(size * sizeof(bool));
321 
322  for (i = 0; i < delsize; i++)
323  {
324  int k = pg_prng_uint64_range(&pg_global_prng_state, 0, size - 1);
325 
326  while (chosen[k])
327  k = (k + 1) % size;
328  deleteIds[i] = k;
329  chosen[k] = true;
330  }
331 
332  /* Delete elements */
333  for (i = 0; i < delsize; i++)
334  {
336  IntRBTreeNode *node;
337 
338  find.key = deleteIds[i];
339  /* Locate the node to be deleted */
340  node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find);
341  if (node == NULL || node->key != deleteIds[i])
342  elog(ERROR, "expected element was not found during deleting");
343  /* Delete it */
344  rbt_delete(tree, (RBTNode *) node);
345  }
346 
347  /* Check that deleted elements are deleted */
348  for (i = 0; i < size; i++)
349  {
350  IntRBTreeNode node;
351  IntRBTreeNode *result;
352 
353  node.key = i;
354  result = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
355  if (chosen[i])
356  {
357  /* Deleted element should be absent */
358  if (result != NULL)
359  elog(ERROR, "deleted element still present in the rbtree");
360  }
361  else
362  {
363  /* Else it should be present */
364  if (result == NULL || result->key != i)
365  elog(ERROR, "delete operation removed wrong rbtree value");
366  }
367  }
368 
369  /* Delete remaining elements, so as to exercise reducing tree to empty */
370  for (i = 0; i < size; i++)
371  {
373  IntRBTreeNode *node;
374 
375  if (chosen[i])
376  continue;
377  find.key = i;
378  /* Locate the node to be deleted */
379  node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find);
380  if (node == NULL || node->key != i)
381  elog(ERROR, "expected element was not found during deleting");
382  /* Delete it */
383  rbt_delete(tree, (RBTNode *) node);
384  }
385 
386  /* Tree should now be empty */
387  if (rbt_leftmost(tree) != NULL)
388  elog(ERROR, "deleting all elements failed");
389 
390  pfree(deleteIds);
391  pfree(chosen);
392 }
void * palloc0(Size size)
Definition: mcxt.c:1093
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:173
void rbt_delete(RBTree *rbt, RBTNode *node)
Definition: rbtree.c:633
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
static int find(struct vars *, struct cnfa *, struct colormap *)
Definition: regexec.c:410
Definition: rbtree.c:42
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

References create_int_rbtree(), elog, ERROR, find(), i, IntRBTreeNode::key, palloc(), palloc0(), pfree(), pg_global_prng_state, pg_prng_uint64_range(), rbt_delete(), rbt_find(), rbt_leftmost(), and rbt_populate().

Referenced by test_rb_tree().

◆ testfind()

static void testfind ( int  size)
static

Definition at line 243 of file test_rbtree.c.

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 }

References create_int_rbtree(), elog, ERROR, i, IntRBTreeNode::key, rbt_find(), and rbt_populate().

Referenced by test_rb_tree().

◆ testleftmost()

static void testleftmost ( int  size)
static

Definition at line 286 of file test_rbtree.c.

287 {
288  RBTree *tree = create_int_rbtree();
289  IntRBTreeNode *result;
290 
291  /* Check that empty tree has no leftmost element */
292  if (rbt_leftmost(tree) != NULL)
293  elog(ERROR, "leftmost node of empty tree is not NULL");
294 
295  /* fill tree with consecutive natural numbers */
296  rbt_populate(tree, size, 1);
297 
298  /* Check that leftmost element is the smallest one */
299  result = (IntRBTreeNode *) rbt_leftmost(tree);
300  if (result == NULL || result->key != 0)
301  elog(ERROR, "rbt_leftmost gave wrong result");
302 }

References create_int_rbtree(), elog, ERROR, IntRBTreeNode::key, rbt_leftmost(), and rbt_populate().

Referenced by test_rb_tree().

◆ testleftright()

static void testleftright ( int  size)
static

Definition at line 164 of file test_rbtree.c.

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 }
RBTNode * rbt_iterate(RBTreeIterator *iter)
Definition: rbtree.c:764
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:740
@ LeftRightWalk
Definition: rbtree.h:37

References create_int_rbtree(), elog, ERROR, IntRBTreeNode::key, LeftRightWalk, rbt_begin_iterate(), rbt_iterate(), and rbt_populate().

Referenced by test_rb_tree().

◆ testrightleft()

static void testrightleft ( int  size)
static

Definition at line 204 of file test_rbtree.c.

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 }
@ RightLeftWalk
Definition: rbtree.h:38

References create_int_rbtree(), elog, ERROR, IntRBTreeNode::key, rbt_begin_iterate(), rbt_iterate(), rbt_populate(), and RightLeftWalk.

Referenced by test_rb_tree().

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 21 of file test_rbtree.c.