PostgreSQL Source Code  git master
test_rbtree.c File Reference
#include "postgres.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 79 of file test_rbtree.c.

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

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

80 {
81  return rbt_create(sizeof(IntRBTreeNode),
82  irbt_cmp,
84  irbt_alloc,
85  irbt_free,
86  NULL);
87 }
static void irbt_combine(RBTNode *existing, const RBTNode *newdata, void *arg)
Definition: test_rbtree.c:51
static RBTNode * irbt_alloc(void *arg)
Definition: test_rbtree.c:63
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:70
static int irbt_cmp(const RBTNode *a, const RBTNode *b, void *arg)
Definition: test_rbtree.c:38

◆ GetPermutation()

static int* GetPermutation ( int  size)
static

Definition at line 93 of file test_rbtree.c.

References i, palloc(), and random().

Referenced by rbt_populate().

94 {
95  int *permutation;
96  int i;
97 
98  permutation = (int *) palloc(size * sizeof(int));
99 
100  permutation[0] = 0;
101 
102  /*
103  * This is the "inside-out" variant of the Fisher-Yates shuffle algorithm.
104  * Notionally, we append each new value to the array and then swap it with
105  * a randomly-chosen array element (possibly including itself, else we
106  * fail to generate permutations with the last integer last). The swap
107  * step can be optimized by combining it with the insertion.
108  */
109  for (i = 1; i < size; i++)
110  {
111  int j = random() % (i + 1);
112 
113  if (j < i) /* avoid fetching undefined data if j=i */
114  permutation[i] = permutation[j];
115  permutation[j] = i;
116  }
117 
118  return permutation;
119 }
long random(void)
Definition: random.c:22
void * palloc(Size size)
Definition: mcxt.c:949
int i

◆ irbt_alloc()

static RBTNode* irbt_alloc ( void *  arg)
static

Definition at line 63 of file test_rbtree.c.

References palloc().

Referenced by create_int_rbtree().

64 {
65  return (RBTNode *) palloc(sizeof(IntRBTreeNode));
66 }
Definition: rbtree.h:23
void * palloc(Size size)
Definition: mcxt.c:949

◆ irbt_cmp()

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

Definition at line 38 of file test_rbtree.c.

References IntRBTreeNode::key.

Referenced by create_int_rbtree().

39 {
40  const IntRBTreeNode *ea = (const IntRBTreeNode *) a;
41  const IntRBTreeNode *eb = (const IntRBTreeNode *) b;
42 
43  return ea->key - eb->key;
44 }

◆ irbt_combine()

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

Definition at line 51 of file test_rbtree.c.

References elog, ERROR, and IntRBTreeNode::key.

Referenced by create_int_rbtree().

52 {
53  const IntRBTreeNode *eexist = (const IntRBTreeNode *) existing;
54  const IntRBTreeNode *enew = (const IntRBTreeNode *) newdata;
55 
56  if (eexist->key != enew->key)
57  elog(ERROR, "red-black tree combines %d into %d",
58  enew->key, eexist->key);
59 }
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:228

◆ irbt_free()

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

Definition at line 70 of file test_rbtree.c.

References pfree().

Referenced by create_int_rbtree().

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

◆ PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1 ( test_rb_tree  )

Referenced by testdelete().

◆ rbt_populate()

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

Definition at line 126 of file test_rbtree.c.

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

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

127 {
128  int *permutation = GetPermutation(size);
129  IntRBTreeNode node;
130  bool isNew;
131  int i;
132 
133  /* Insert values. We don't expect any collisions. */
134  for (i = 0; i < size; i++)
135  {
136  node.key = step * permutation[i];
137  rbt_insert(tree, (RBTNode *) &node, &isNew);
138  if (!isNew)
139  elog(ERROR, "unexpected !isNew result from rbt_insert");
140  }
141 
142  /*
143  * Re-insert the first value to make sure collisions work right. It's
144  * probably not useful to test that case over again for all the values.
145  */
146  if (size > 0)
147  {
148  node.key = step * permutation[0];
149  rbt_insert(tree, (RBTNode *) &node, &isNew);
150  if (isNew)
151  elog(ERROR, "unexpected isNew result from rbt_insert");
152  }
153 
154  pfree(permutation);
155 }
RBTNode * rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
Definition: rbtree.c:391
void pfree(void *pointer)
Definition: mcxt.c:1056
#define ERROR
Definition: elog.h:43
static int * GetPermutation(int size)
Definition: test_rbtree.c:93
Definition: rbtree.h:23
#define elog(elevel,...)
Definition: elog.h:228
int i

◆ test_rb_tree()

Datum test_rb_tree ( PG_FUNCTION_ARGS  )

Definition at line 401 of file test_rbtree.c.

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

Referenced by testdelete().

402 {
403  int size = PG_GETARG_INT32(0);
404 
405  if (size <= 0 || size > MaxAllocSize / sizeof(int))
406  elog(ERROR, "invalid size for test_rb_tree: %d", size);
407  testleftright(size);
408  testrightleft(size);
409  testfind(size);
410  testleftmost(size);
411  testdelete(size, Max(size / 10, 1));
412  PG_RETURN_VOID();
413 }
static void testrightleft(int size)
Definition: test_rbtree.c:203
#define PG_GETARG_INT32(n)
Definition: fmgr.h:264
static void testleftright(int size)
Definition: test_rbtree.c:163
#define ERROR
Definition: elog.h:43
static void testleftmost(int size)
Definition: test_rbtree.c:285
static void testfind(int size)
Definition: test_rbtree.c:242
#define MaxAllocSize
Definition: memutils.h:40
static void testdelete(int size, int delsize)
Definition: test_rbtree.c:307
#define PG_RETURN_VOID()
Definition: fmgr.h:339
#define Max(x, y)
Definition: c.h:905
#define elog(elevel,...)
Definition: elog.h:228

◆ testdelete()

static void testdelete ( int  size,
int  delsize 
)
static

Definition at line 307 of file test_rbtree.c.

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

Referenced by test_rb_tree().

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

◆ testfind()

static void testfind ( int  size)
static

Definition at line 242 of file test_rbtree.c.

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

Referenced by test_rb_tree().

243 {
244  RBTree *tree = create_int_rbtree();
245  int i;
246 
247  /* Insert even integers from 0 to 2 * (size-1) */
248  rbt_populate(tree, size, 2);
249 
250  /* Check that all inserted elements can be found */
251  for (i = 0; i < size; i++)
252  {
253  IntRBTreeNode node;
254  IntRBTreeNode *resultNode;
255 
256  node.key = 2 * i;
257  resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
258  if (resultNode == NULL)
259  elog(ERROR, "inserted element was not found");
260  if (node.key != resultNode->key)
261  elog(ERROR, "find operation in rbtree gave wrong result");
262  }
263 
264  /*
265  * Check that not-inserted elements can not be found, being sure to try
266  * values before the first and after the last element.
267  */
268  for (i = -1; i <= 2 * size; i += 2)
269  {
270  IntRBTreeNode node;
271  IntRBTreeNode *resultNode;
272 
273  node.key = i;
274  resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
275  if (resultNode != NULL)
276  elog(ERROR, "not-inserted element was found");
277  }
278 }
static void rbt_populate(RBTree *tree, int size, int step)
Definition: test_rbtree.c:126
static RBTree * create_int_rbtree(void)
Definition: test_rbtree.c:79
#define ERROR
Definition: elog.h:43
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
Definition: rbtree.h:23
#define elog(elevel,...)
Definition: elog.h:228
int i
Definition: rbtree.c:41

◆ testleftmost()

static void testleftmost ( int  size)
static

Definition at line 285 of file test_rbtree.c.

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

Referenced by test_rb_tree().

286 {
287  RBTree *tree = create_int_rbtree();
288  IntRBTreeNode *result;
289 
290  /* Check that empty tree has no leftmost element */
291  if (rbt_leftmost(tree) != NULL)
292  elog(ERROR, "leftmost node of empty tree is not NULL");
293 
294  /* fill tree with consecutive natural numbers */
295  rbt_populate(tree, size, 1);
296 
297  /* Check that leftmost element is the smallest one */
298  result = (IntRBTreeNode *) rbt_leftmost(tree);
299  if (result == NULL || result->key != 0)
300  elog(ERROR, "rbt_leftmost gave wrong result");
301 }
static void rbt_populate(RBTree *tree, int size, int step)
Definition: test_rbtree.c:126
static RBTree * create_int_rbtree(void)
Definition: test_rbtree.c:79
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:173
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:228
Definition: rbtree.c:41

◆ testleftright()

static void testleftright ( int  size)
static

Definition at line 163 of file test_rbtree.c.

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

Referenced by test_rb_tree().

164 {
165  RBTree *tree = create_int_rbtree();
166  IntRBTreeNode *node;
167  RBTreeIterator iter;
168  int lastKey = -1;
169  int count = 0;
170 
171  /* check iteration over empty tree */
172  rbt_begin_iterate(tree, LeftRightWalk, &iter);
173  if (rbt_iterate(&iter) != NULL)
174  elog(ERROR, "left-right walk over empty tree produced an element");
175 
176  /* fill tree with consecutive natural numbers */
177  rbt_populate(tree, size, 1);
178 
179  /* iterate over the tree */
180  rbt_begin_iterate(tree, LeftRightWalk, &iter);
181 
182  while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL)
183  {
184  /* check that order is increasing */
185  if (node->key <= lastKey)
186  elog(ERROR, "left-right walk gives elements not in sorted order");
187  lastKey = node->key;
188  count++;
189  }
190 
191  if (lastKey != size - 1)
192  elog(ERROR, "left-right walk did not reach end");
193  if (count != size)
194  elog(ERROR, "left-right walk missed some elements");
195 }
RBTNode * rbt_iterate(RBTreeIterator *iter)
Definition: rbtree.c:764
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:740
static void rbt_populate(RBTree *tree, int size, int step)
Definition: test_rbtree.c:126
static RBTree * create_int_rbtree(void)
Definition: test_rbtree.c:79
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:228
Definition: rbtree.c:41

◆ testrightleft()

static void testrightleft ( int  size)
static

Definition at line 203 of file test_rbtree.c.

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

Referenced by test_rb_tree().

204 {
205  RBTree *tree = create_int_rbtree();
206  IntRBTreeNode *node;
207  RBTreeIterator iter;
208  int lastKey = size;
209  int count = 0;
210 
211  /* check iteration over empty tree */
212  rbt_begin_iterate(tree, RightLeftWalk, &iter);
213  if (rbt_iterate(&iter) != NULL)
214  elog(ERROR, "right-left walk over empty tree produced an element");
215 
216  /* fill tree with consecutive natural numbers */
217  rbt_populate(tree, size, 1);
218 
219  /* iterate over the tree */
220  rbt_begin_iterate(tree, RightLeftWalk, &iter);
221 
222  while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL)
223  {
224  /* check that order is decreasing */
225  if (node->key >= lastKey)
226  elog(ERROR, "right-left walk gives elements not in sorted order");
227  lastKey = node->key;
228  count++;
229  }
230 
231  if (lastKey != 0)
232  elog(ERROR, "right-left walk did not reach end");
233  if (count != size)
234  elog(ERROR, "right-left walk missed some elements");
235 }
RBTNode * rbt_iterate(RBTreeIterator *iter)
Definition: rbtree.c:764
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:740
static void rbt_populate(RBTree *tree, int size, int step)
Definition: test_rbtree.c:126
static RBTree * create_int_rbtree(void)
Definition: test_rbtree.c:79
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:228
Definition: rbtree.c:41

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 20 of file test_rbtree.c.