PostgreSQL Source Code git master
Data Structures | Typedefs | Functions | Variables
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 RBTNode *  irbt_alloc (void *arg)
 
static void  irbt_free (RBTNode *node, void *arg)
 
static RBTree *  create_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  testfindltgt (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),
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 RBTNode * irbt_alloc(void *arg)
Definition: test_rbtree.c:64
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

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

Referenced by testdelete(), testfind(), testfindltgt(), 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}
j
int j
Definition: isn.c:78
i
int i
Definition: isn.c:77
void * palloc(Size size)
Definition: mcxt.c:1365
uint64 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
Definition: pg_prng.c:144
pg_prng_state pg_global_prng_state
Definition: pg_prng.c:34

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}
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73

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:39
#define elog(elevel,...)
Definition: elog.h:226

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:1594

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

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

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

◆ test_rb_tree()

Datum test_rb_tree ( PG_FUNCTION_ARGS  )

Definition at line 503 of file test_rbtree.c.

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));
516}
#define Max(x, y)
Definition: c.h:997
#define MaxAllocSize
Definition: fe_memutils.h:22
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
static void testleftright(int size)
Definition: test_rbtree.c:164
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
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(), testfindltgt(), testleftmost(), testleftright(), and testrightleft().

◆ testdelete()

static void testdelete ( int  size,
int  delsize 
)
static

Definition at line 409 of file test_rbtree.c.

410{
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}
void * palloc0(Size size)
Definition: mcxt.c:1395
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:235
void rbt_delete(RBTree *rbt, RBTNode *node)
Definition: rbtree.c:695
static int find(struct vars *v, struct cnfa *cnfa, struct colormap *cm)
Definition: regexec.c:419
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(), rbt_populate(), and tree.

Referenced by test_rb_tree().

◆ testfind()

static void testfind ( int  size )
static

Definition at line 243 of file test_rbtree.c.

244{
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(), rbt_populate(), and tree.

Referenced by test_rb_tree().

◆ testfindltgt()

static void testfindltgt ( int  size )
static

Definition at line 287 of file test_rbtree.c.

288{
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}
RBTNode * rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:172
RBTNode * rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:203

References create_int_rbtree(), elog, ERROR, IntRBTreeNode::key, pg_global_prng_state, pg_prng_uint64_range(), rbt_delete(), rbt_find_great(), rbt_find_less(), rbt_populate(), and tree.

Referenced by test_rb_tree().

◆ testleftmost()

static void testleftmost ( int  size )
static

Definition at line 387 of file test_rbtree.c.

388{
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}

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

Referenced by test_rb_tree().

◆ testleftright()

static void testleftright ( int  size )
static

Definition at line 164 of file test_rbtree.c.

165{
167 IntRBTreeNode *node;
168 RBTreeIterator iter;
169 int lastKey = -1;
170 int count = 0;
171
172 /* check iteration over empty tree */
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 */
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:826
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:802
@ LeftRightWalk
Definition: rbtree.h:37

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

Referenced by test_rb_tree().

◆ testrightleft()

static void testrightleft ( int  size )
static

Definition at line 204 of file test_rbtree.c.

205{
207 IntRBTreeNode *node;
208 RBTreeIterator iter;
209 int lastKey = size;
210 int count = 0;
211
212 /* check iteration over empty tree */
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 */
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(), RightLeftWalk, and tree.

Referenced by test_rb_tree().

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 21 of file test_rbtree.c.

AltStyle によって変換されたページ (->オリジナル) /