PostgreSQL Source Code: src/test/modules/test_rbtree/test_rbtree.c Source File

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-2025, 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
21 PG_MODULE_MAGIC;
22
23
24/*
25 * Our test trees store an integer key, and nothing else.
26 */
27 typedef struct IntRBTreeNode
28{
29 RBTNode rbtnode;
30 int key;
31 } IntRBTreeNode;
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 */
38static 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 */
51static 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 */
63static RBTNode *
64 irbt_alloc(void *arg)
65{
66 return (RBTNode *) palloc(sizeof(IntRBTreeNode));
67}
68
69/* Node freer */
70static 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 */
79static RBTree *
80 create_int_rbtree(void)
81{
82 return rbt_create(sizeof(IntRBTreeNode),
83 irbt_cmp,
84 irbt_combine,
85 irbt_alloc,
86 irbt_free,
87 NULL);
88}
89
90/*
91 * Generate a random permutation of the integers 0..size-1
92 */
93static 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 {
112 int j = pg_prng_uint64_range(&pg_global_prng_state, 0, i);
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 */
126static 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 */
163static 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 */
203static 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 */
242static 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 */
286static 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 */
386static 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 */
408static 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 {
436 IntRBTreeNode find;
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 {
473 IntRBTreeNode find;
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 */
500 PG_FUNCTION_INFO_V1(test_rb_tree);
501
502Datum
503 test_rb_tree(PG_FUNCTION_ARGS)
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:997
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
#define MaxAllocSize
Definition: fe_memutils.h:22
#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
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73
j
int j
Definition: isn.c:78
i
int i
Definition: isn.c:77
void pfree(void *pointer)
Definition: mcxt.c:1594
void * palloc0(Size size)
Definition: mcxt.c:1395
void * palloc(Size size)
Definition: mcxt.c:1365
void * arg
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
uint64_t Datum
Definition: postgres.h:70
tree
Definition: radixtree.h:1828
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
RBTNode * rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:203
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(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
@ 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
static int * GetPermutation(int size)
Definition: test_rbtree.c:94
static RBTNode * irbt_alloc(void *arg)
Definition: test_rbtree.c:64
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 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 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 RBTree * create_int_rbtree(void)
Definition: test_rbtree.c:80
static void testrightleft(int size)
Definition: test_rbtree.c:204
static void testfind(int size)
Definition: test_rbtree.c:243

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