1 /*-------------------------------------------------------------------------
2 *
3 * rbtree.c
4 * implementation for PostgreSQL generic Red-Black binary tree package
5 * Adopted from http://algolist.manual.ru/ds/rbtree.php
6 *
7 * This code comes from Thomas Niemann's "Sorting and Searching Algorithms:
8 * a Cookbook".
9 *
10 * See http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_man.htm for
11 * license terms: "Source code, when part of a software project, may be used
12 * freely without reference to the author."
13 *
14 * Red-black trees are a type of balanced binary tree wherein (1) any child of
15 * a red node is always black, and (2) every path from root to leaf traverses
16 * an equal number of black nodes. From these properties, it follows that the
17 * longest path from root to leaf is only about twice as long as the shortest,
18 * so lookups are guaranteed to run in O(lg n) time.
19 *
20 * Copyright (c) 2009-2017, PostgreSQL Global Development Group
21 *
22 * IDENTIFICATION
23 * src/backend/lib/rbtree.c
24 *
25 *-------------------------------------------------------------------------
26 */
27 #include "postgres.h"
28
29 #include "lib/rbtree.h"
30
31
32 /*
33 * Colors of nodes (values of RBTNode.color)
34 */
35 #define RBTBLACK (0)
36 #define RBTRED (1)
37
38 /*
39 * RBTree control structure
40 */
41 struct RBTree
42 {
43 RBTNode *root; /* root node, or RBTNIL if tree is empty */
44
45 /* Remaining fields are constant after rbt_create */
46
47 Size node_size; /* actual size of tree nodes */
48 /* The caller-supplied manipulation functions */
49 rbt_comparator comparator;
50 rbt_combiner combiner;
51 rbt_allocfunc allocfunc;
52 rbt_freefunc freefunc;
53 /* Passthrough arg passed to all manipulation functions */
54 void *arg;
55 };
56
57 /*
58 * all leafs are sentinels, use customized NIL name to prevent
59 * collision with system-wide constant NIL which is actually NULL
60 */
61 #define RBTNIL (&sentinel)
62
63 static RBTNode sentinel = {RBTBLACK, RBTNIL, RBTNIL, NULL};
64
65 /*
66 * Values used in the RBTreeIterator.next_state field, with an
67 * InvertedWalk iterator.
68 */
69 typedef enum InvertedWalkNextStep
70 {
71 NextStepBegin,
72 NextStepUp,
73 NextStepLeft,
74 NextStepRight
75 } InvertedWalkNextStep;
76
77 /*
78 * rbt_create: create an empty RBTree
79 *
80 * Arguments are:
81 * node_size: actual size of tree nodes (> sizeof(RBTNode))
82 * The manipulation functions:
83 * comparator: compare two RBTNodes for less/equal/greater
84 * combiner: merge an existing tree entry with a new one
85 * allocfunc: allocate a new RBTNode
86 * freefunc: free an old RBTNode
87 * arg: passthrough pointer that will be passed to the manipulation functions
88 *
89 * Note that the combiner's righthand argument will be a "proposed" tree node,
90 * ie the input to rbt_insert, in which the RBTNode fields themselves aren't
91 * valid. Similarly, either input to the comparator may be a "proposed" node.
92 * This shouldn't matter since the functions aren't supposed to look at the
93 * RBTNode fields, only the extra fields of the struct the RBTNode is embedded
94 * in.
95 *
96 * The freefunc should just be pfree or equivalent; it should NOT attempt
97 * to free any subsidiary data, because the node passed to it may not contain
98 * valid data! freefunc can be NULL if caller doesn't require retail
99 * space reclamation.
100 *
101 * The RBTree node is palloc'd in the caller's memory context. Note that
102 * all contents of the tree are actually allocated by the caller, not here.
103 *
104 * Since tree contents are managed by the caller, there is currently not
105 * an explicit "destroy" operation; typically a tree would be freed by
106 * resetting or deleting the memory context it's stored in. You can pfree
107 * the RBTree node if you feel the urge.
108 */
109 RBTree *
rbt_create(Size node_size,rbt_comparator comparator,rbt_combiner combiner,rbt_allocfunc allocfunc,rbt_freefunc freefunc,void * arg)110 rbt_create(Size node_size,
111 rbt_comparator comparator,
112 rbt_combiner combiner,
113 rbt_allocfunc allocfunc,
114 rbt_freefunc freefunc,
115 void *arg)
116 {
117 RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
118
119 Assert(node_size > sizeof(RBTNode));
120
121 tree->root = RBTNIL;
122 tree->node_size = node_size;
123 tree->comparator = comparator;
124 tree->combiner = combiner;
125 tree->allocfunc = allocfunc;
126 tree->freefunc = freefunc;
127
128 tree->arg = arg;
129
130 return tree;
131 }
132
133 /* Copy the additional data fields from one RBTNode to another */
134 static inline void
rbt_copy_data(RBTree * rbt,RBTNode * dest,const RBTNode * src)135 rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
136 {
137 memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
138 }
139
140 /**********************************************************************
141 * Search *
142 **********************************************************************/
143
144 /*
145 * rbt_find: search for a value in an RBTree
146 *
147 * data represents the value to try to find. Its RBTNode fields need not
148 * be valid, it's the extra data in the larger struct that is of interest.
149 *
150 * Returns the matching tree entry, or NULL if no match is found.
151 */
152 RBTNode *
rbt_find(RBTree * rbt,const RBTNode * data)153 rbt_find(RBTree *rbt, const RBTNode *data)
154 {
155 RBTNode *node = rbt->root;
156
157 while (node != RBTNIL)
158 {
159 int cmp = rbt->comparator(data, node, rbt->arg);
160
161 if (cmp == 0)
162 return node;
163 else if (cmp < 0)
164 node = node->left;
165 else
166 node = node->right;
167 }
168
169 return NULL;
170 }
171
172 /*
173 * rbt_leftmost: fetch the leftmost (smallest-valued) tree node.
174 * Returns NULL if tree is empty.
175 *
176 * Note: in the original implementation this included an unlink step, but
177 * that's a bit awkward. Just call rbt_delete on the result if that's what
178 * you want.
179 */
180 RBTNode *
rbt_leftmost(RBTree * rbt)181 rbt_leftmost(RBTree *rbt)
182 {
183 RBTNode *node = rbt->root;
184 RBTNode *leftmost = rbt->root;
185
186 while (node != RBTNIL)
187 {
188 leftmost = node;
189 node = node->left;
190 }
191
192 if (leftmost != RBTNIL)
193 return leftmost;
194
195 return NULL;
196 }
197
198 /**********************************************************************
199 * Insertion *
200 **********************************************************************/
201
202 /*
203 * Rotate node x to left.
204 *
205 * x's right child takes its place in the tree, and x becomes the left
206 * child of that node.
207 */
208 static void
rbt_rotate_left(RBTree * rbt,RBTNode * x)209 rbt_rotate_left(RBTree *rbt, RBTNode *x)
210 {
211 RBTNode *y = x->right;
212
213 /* establish x->right link */
214 x->right = y->left;
215 if (y->left != RBTNIL)
216 y->left->parent = x;
217
218 /* establish y->parent link */
219 if (y != RBTNIL)
220 y->parent = x->parent;
221 if (x->parent)
222 {
223 if (x == x->parent->left)
224 x->parent->left = y;
225 else
226 x->parent->right = y;
227 }
228 else
229 {
230 rbt->root = y;
231 }
232
233 /* link x and y */
234 y->left = x;
235 if (x != RBTNIL)
236 x->parent = y;
237 }
238
239 /*
240 * Rotate node x to right.
241 *
242 * x's left right child takes its place in the tree, and x becomes the right
243 * child of that node.
244 */
245 static void
rbt_rotate_right(RBTree * rbt,RBTNode * x)246 rbt_rotate_right(RBTree *rbt, RBTNode *x)
247 {
248 RBTNode *y = x->left;
249
250 /* establish x->left link */
251 x->left = y->right;
252 if (y->right != RBTNIL)
253 y->right->parent = x;
254
255 /* establish y->parent link */
256 if (y != RBTNIL)
257 y->parent = x->parent;
258 if (x->parent)
259 {
260 if (x == x->parent->right)
261 x->parent->right = y;
262 else
263 x->parent->left = y;
264 }
265 else
266 {
267 rbt->root = y;
268 }
269
270 /* link x and y */
271 y->right = x;
272 if (x != RBTNIL)
273 x->parent = y;
274 }
275
276 /*
277 * Maintain Red-Black tree balance after inserting node x.
278 *
279 * The newly inserted node is always initially marked red. That may lead to
280 * a situation where a red node has a red child, which is prohibited. We can
281 * always fix the problem by a series of color changes and/or "rotations",
282 * which move the problem progressively higher up in the tree. If one of the
283 * two red nodes is the root, we can always fix the problem by changing the
284 * root from red to black.
285 *
286 * (This does not work lower down in the tree because we must also maintain
287 * the invariant that every leaf has equal black-height.)
288 */
289 static void
rbt_insert_fixup(RBTree * rbt,RBTNode * x)290 rbt_insert_fixup(RBTree *rbt, RBTNode *x)
291 {
292 /*
293 * x is always a red node. Initially, it is the newly inserted node. Each
294 * iteration of this loop moves it higher up in the tree.
295 */
296 while (x != rbt->root && x->parent->color == RBTRED)
297 {
298 /*
299 * x and x->parent are both red. Fix depends on whether x->parent is
300 * a left or right child. In either case, we define y to be the
301 * "uncle" of x, that is, the other child of x's grandparent.
302 *
303 * If the uncle is red, we flip the grandparent to red and its two
304 * children to black. Then we loop around again to check whether the
305 * grandparent still has a problem.
306 *
307 * If the uncle is black, we will perform one or two "rotations" to
308 * balance the tree. Either x or x->parent will take the
309 * grandparent's position in the tree and recolored black, and the
310 * original grandparent will be recolored red and become a child of
311 * that node. This always leaves us with a valid red-black tree, so
312 * the loop will terminate.
313 */
314 if (x->parent == x->parent->parent->left)
315 {
316 RBTNode *y = x->parent->parent->right;
317
318 if (y->color == RBTRED)
319 {
320 /* uncle is RBTRED */
321 x->parent->color = RBTBLACK;
322 y->color = RBTBLACK;
323 x->parent->parent->color = RBTRED;
324
325 x = x->parent->parent;
326 }
327 else
328 {
329 /* uncle is RBTBLACK */
330 if (x == x->parent->right)
331 {
332 /* make x a left child */
333 x = x->parent;
334 rbt_rotate_left(rbt, x);
335 }
336
337 /* recolor and rotate */
338 x->parent->color = RBTBLACK;
339 x->parent->parent->color = RBTRED;
340
341 rbt_rotate_right(rbt, x->parent->parent);
342 }
343 }
344 else
345 {
346 /* mirror image of above code */
347 RBTNode *y = x->parent->parent->left;
348
349 if (y->color == RBTRED)
350 {
351 /* uncle is RBTRED */
352 x->parent->color = RBTBLACK;
353 y->color = RBTBLACK;
354 x->parent->parent->color = RBTRED;
355
356 x = x->parent->parent;
357 }
358 else
359 {
360 /* uncle is RBTBLACK */
361 if (x == x->parent->left)
362 {
363 x = x->parent;
364 rbt_rotate_right(rbt, x);
365 }
366 x->parent->color = RBTBLACK;
367 x->parent->parent->color = RBTRED;
368
369 rbt_rotate_left(rbt, x->parent->parent);
370 }
371 }
372 }
373
374 /*
375 * The root may already have been black; if not, the black-height of every
376 * node in the tree increases by one.
377 */
378 rbt->root->color = RBTBLACK;
379 }
380
381 /*
382 * rbt_insert: insert a new value into the tree.
383 *
384 * data represents the value to insert. Its RBTNode fields need not
385 * be valid, it's the extra data in the larger struct that is of interest.
386 *
387 * If the value represented by "data" is not present in the tree, then
388 * we copy "data" into a new tree entry and return that node, setting *isNew
389 * to true.
390 *
391 * If the value represented by "data" is already present, then we call the
392 * combiner function to merge data into the existing node, and return the
393 * existing node, setting *isNew to false.
394 *
395 * "data" is unmodified in either case; it's typically just a local
396 * variable in the caller.
397 */
398 RBTNode *
rbt_insert(RBTree * rbt,const RBTNode * data,bool * isNew)399 rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
400 {
401 RBTNode *current,
402 *parent,
403 *x;
404 int cmp;
405
406 /* find where node belongs */
407 current = rbt->root;
408 parent = NULL;
409 cmp = 0; /* just to prevent compiler warning */
410
411 while (current != RBTNIL)
412 {
413 cmp = rbt->comparator(data, current, rbt->arg);
414 if (cmp == 0)
415 {
416 /*
417 * Found node with given key. Apply combiner.
418 */
419 rbt->combiner(current, data, rbt->arg);
420 *isNew = false;
421 return current;
422 }
423 parent = current;
424 current = (cmp < 0) ? current->left : current->right;
425 }
426
427 /*
428 * Value is not present, so create a new node containing data.
429 */
430 *isNew = true;
431
432 x = rbt->allocfunc(rbt->arg);
433
434 x->color = RBTRED;
435
436 x->left = RBTNIL;
437 x->right = RBTNIL;
438 x->parent = parent;
439 rbt_copy_data(rbt, x, data);
440
441 /* insert node in tree */
442 if (parent)
443 {
444 if (cmp < 0)
445 parent->left = x;
446 else
447 parent->right = x;
448 }
449 else
450 {
451 rbt->root = x;
452 }
453
454 rbt_insert_fixup(rbt, x);
455
456 return x;
457 }
458
459 /**********************************************************************
460 * Deletion *
461 **********************************************************************/
462
463 /*
464 * Maintain Red-Black tree balance after deleting a black node.
465 */
466 static void
rbt_delete_fixup(RBTree * rbt,RBTNode * x)467 rbt_delete_fixup(RBTree *rbt, RBTNode *x)
468 {
469 /*
470 * x is always a black node. Initially, it is the former child of the
471 * deleted node. Each iteration of this loop moves it higher up in the
472 * tree.
473 */
474 while (x != rbt->root && x->color == RBTBLACK)
475 {
476 /*
477 * Left and right cases are symmetric. Any nodes that are children of
478 * x have a black-height one less than the remainder of the nodes in
479 * the tree. We rotate and recolor nodes to move the problem up the
480 * tree: at some stage we'll either fix the problem, or reach the root
481 * (where the black-height is allowed to decrease).
482 */
483 if (x == x->parent->left)
484 {
485 RBTNode *w = x->parent->right;
486
487 if (w->color == RBTRED)
488 {
489 w->color = RBTBLACK;
490 x->parent->color = RBTRED;
491
492 rbt_rotate_left(rbt, x->parent);
493 w = x->parent->right;
494 }
495
496 if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
497 {
498 w->color = RBTRED;
499
500 x = x->parent;
501 }
502 else
503 {
504 if (w->right->color == RBTBLACK)
505 {
506 w->left->color = RBTBLACK;
507 w->color = RBTRED;
508
509 rbt_rotate_right(rbt, w);
510 w = x->parent->right;
511 }
512 w->color = x->parent->color;
513 x->parent->color = RBTBLACK;
514 w->right->color = RBTBLACK;
515
516 rbt_rotate_left(rbt, x->parent);
517 x = rbt->root; /* Arrange for loop to terminate. */
518 }
519 }
520 else
521 {
522 RBTNode *w = x->parent->left;
523
524 if (w->color == RBTRED)
525 {
526 w->color = RBTBLACK;
527 x->parent->color = RBTRED;
528
529 rbt_rotate_right(rbt, x->parent);
530 w = x->parent->left;
531 }
532
533 if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
534 {
535 w->color = RBTRED;
536
537 x = x->parent;
538 }
539 else
540 {
541 if (w->left->color == RBTBLACK)
542 {
543 w->right->color = RBTBLACK;
544 w->color = RBTRED;
545
546 rbt_rotate_left(rbt, w);
547 w = x->parent->left;
548 }
549 w->color = x->parent->color;
550 x->parent->color = RBTBLACK;
551 w->left->color = RBTBLACK;
552
553 rbt_rotate_right(rbt, x->parent);
554 x = rbt->root; /* Arrange for loop to terminate. */
555 }
556 }
557 }
558 x->color = RBTBLACK;
559 }
560
561 /*
562 * Delete node z from tree.
563 */
564 static void
rbt_delete_node(RBTree * rbt,RBTNode * z)565 rbt_delete_node(RBTree *rbt, RBTNode *z)
566 {
567 RBTNode *x,
568 *y;
569
570 if (!z || z == RBTNIL)
571 return;
572
573 /*
574 * y is the node that will actually be removed from the tree. This will
575 * be z if z has fewer than two children, or the tree successor of z
576 * otherwise.
577 */
578 if (z->left == RBTNIL || z->right == RBTNIL)
579 {
580 /* y has a RBTNIL node as a child */
581 y = z;
582 }
583 else
584 {
585 /* find tree successor */
586 y = z->right;
587 while (y->left != RBTNIL)
588 y = y->left;
589 }
590
591 /* x is y's only child */
592 if (y->left != RBTNIL)
593 x = y->left;
594 else
595 x = y->right;
596
597 /* Remove y from the tree. */
598 x->parent = y->parent;
599 if (y->parent)
600 {
601 if (y == y->parent->left)
602 y->parent->left = x;
603 else
604 y->parent->right = x;
605 }
606 else
607 {
608 rbt->root = x;
609 }
610
611 /*
612 * If we removed the tree successor of z rather than z itself, then move
613 * the data for the removed node to the one we were supposed to remove.
614 */
615 if (y != z)
616 rbt_copy_data(rbt, z, y);
617
618 /*
619 * Removing a black node might make some paths from root to leaf contain
620 * fewer black nodes than others, or it might make two red nodes adjacent.
621 */
622 if (y->color == RBTBLACK)
623 rbt_delete_fixup(rbt, x);
624
625 /* Now we can recycle the y node */
626 if (rbt->freefunc)
627 rbt->freefunc(y, rbt->arg);
628 }
629
630 /*
631 * rbt_delete: remove the given tree entry
632 *
633 * "node" must have previously been found via rbt_find or rbt_leftmost.
634 * It is caller's responsibility to free any subsidiary data attached
635 * to the node before calling rbt_delete. (Do *not* try to push that
636 * responsibility off to the freefunc, as some other physical node
637 * may be the one actually freed!)
638 */
639 void
rbt_delete(RBTree * rbt,RBTNode * node)640 rbt_delete(RBTree *rbt, RBTNode *node)
641 {
642 rbt_delete_node(rbt, node);
643 }
644
645 /**********************************************************************
646 * Traverse *
647 **********************************************************************/
648
649 static RBTNode *
rbt_left_right_iterator(RBTreeIterator * iter)650 rbt_left_right_iterator(RBTreeIterator *iter)
651 {
652 if (iter->last_visited == NULL)
653 {
654 iter->last_visited = iter->rbt->root;
655 while (iter->last_visited->left != RBTNIL)
656 iter->last_visited = iter->last_visited->left;
657
658 return iter->last_visited;
659 }
660
661 if (iter->last_visited->right != RBTNIL)
662 {
663 iter->last_visited = iter->last_visited->right;
664 while (iter->last_visited->left != RBTNIL)
665 iter->last_visited = iter->last_visited->left;
666
667 return iter->last_visited;
668 }
669
670 for (;;)
671 {
672 RBTNode *came_from = iter->last_visited;
673
674 iter->last_visited = iter->last_visited->parent;
675 if (iter->last_visited == NULL)
676 {
677 iter->is_over = true;
678 break;
679 }
680
681 if (iter->last_visited->left == came_from)
682 break; /* came from left sub-tree, return current
683 * node */
684
685 /* else - came from right sub-tree, continue to move up */
686 }
687
688 return iter->last_visited;
689 }
690
691 static RBTNode *
rbt_right_left_iterator(RBTreeIterator * iter)692 rbt_right_left_iterator(RBTreeIterator *iter)
693 {
694 if (iter->last_visited == NULL)
695 {
696 iter->last_visited = iter->rbt->root;
697 while (iter->last_visited->right != RBTNIL)
698 iter->last_visited = iter->last_visited->right;
699
700 return iter->last_visited;
701 }
702
703 if (iter->last_visited->left != RBTNIL)
704 {
705 iter->last_visited = iter->last_visited->left;
706 while (iter->last_visited->right != RBTNIL)
707 iter->last_visited = iter->last_visited->right;
708
709 return iter->last_visited;
710 }
711
712 for (;;)
713 {
714 RBTNode *came_from = iter->last_visited;
715
716 iter->last_visited = iter->last_visited->parent;
717 if (iter->last_visited == NULL)
718 {
719 iter->is_over = true;
720 break;
721 }
722
723 if (iter->last_visited->right == came_from)
724 break; /* came from right sub-tree, return current
725 * node */
726
727 /* else - came from left sub-tree, continue to move up */
728 }
729
730 return iter->last_visited;
731 }
732
733 static RBTNode *
rbt_direct_iterator(RBTreeIterator * iter)734 rbt_direct_iterator(RBTreeIterator *iter)
735 {
736 if (iter->last_visited == NULL)
737 {
738 iter->last_visited = iter->rbt->root;
739 return iter->last_visited;
740 }
741
742 if (iter->last_visited->left != RBTNIL)
743 {
744 iter->last_visited = iter->last_visited->left;
745 return iter->last_visited;
746 }
747
748 do
749 {
750 if (iter->last_visited->right != RBTNIL)
751 {
752 iter->last_visited = iter->last_visited->right;
753 break;
754 }
755
756 /* go up and one step right */
757 for (;;)
758 {
759 RBTNode *came_from = iter->last_visited;
760
761 iter->last_visited = iter->last_visited->parent;
762 if (iter->last_visited == NULL)
763 {
764 iter->is_over = true;
765 break;
766 }
767
768 if ((iter->last_visited->right != came_from) && (iter->last_visited->right != RBTNIL))
769 {
770 iter->last_visited = iter->last_visited->right;
771 return iter->last_visited;
772 }
773 }
774 }
775 while (iter->last_visited != NULL);
776
777 return iter->last_visited;
778 }
779
780 static RBTNode *
rbt_inverted_iterator(RBTreeIterator * iter)781 rbt_inverted_iterator(RBTreeIterator *iter)
782 {
783 RBTNode *came_from;
784 RBTNode *current;
785
786 current = iter->last_visited;
787
788 loop:
789 switch ((InvertedWalkNextStep) iter->next_step)
790 {
791 /* First call, begin from root */
792 case NextStepBegin:
793 current = iter->rbt->root;
794 iter->next_step = NextStepLeft;
795 goto loop;
796
797 case NextStepLeft:
798 while (current->left != RBTNIL)
799 current = current->left;
800
801 iter->next_step = NextStepRight;
802 goto loop;
803
804 case NextStepRight:
805 if (current->right != RBTNIL)
806 {
807 current = current->right;
808 iter->next_step = NextStepLeft;
809 goto loop;
810 }
811 else /* not moved - return current, then go up */
812 iter->next_step = NextStepUp;
813 break;
814
815 case NextStepUp:
816 came_from = current;
817 current = current->parent;
818 if (current == NULL)
819 {
820 iter->is_over = true;
821 break; /* end of iteration */
822 }
823 else if (came_from == current->right)
824 {
825 /* return current, then continue to go up */
826 break;
827 }
828 else
829 {
830 /* otherwise we came from the left */
831 Assert(came_from == current->left);
832 iter->next_step = NextStepRight;
833 goto loop;
834 }
835 }
836
837 iter->last_visited = current;
838 return current;
839 }
840
841 /*
842 * rbt_begin_iterate: prepare to traverse the tree in any of several orders
843 *
844 * After calling rbt_begin_iterate, call rbt_iterate repeatedly until it
845 * returns NULL or the traversal stops being of interest.
846 *
847 * If the tree is changed during traversal, results of further calls to
848 * rbt_iterate are unspecified. Multiple concurrent iterators on the same
849 * tree are allowed.
850 *
851 * The iterator state is stored in the 'iter' struct. The caller should
852 * treat it as opaque struct.
853 */
854 void
rbt_begin_iterate(RBTree * rbt,RBTOrderControl ctrl,RBTreeIterator * iter)855 rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
856 {
857 /* Common initialization for all traversal orders */
858 iter->rbt = rbt;
859 iter->last_visited = NULL;
860 iter->is_over = (rbt->root == RBTNIL);
861
862 switch (ctrl)
863 {
864 case LeftRightWalk: /* visit left, then self, then right */
865 iter->iterate = rbt_left_right_iterator;
866 break;
867 case RightLeftWalk: /* visit right, then self, then left */
868 iter->iterate = rbt_right_left_iterator;
869 break;
870 case DirectWalk: /* visit self, then left, then right */
871 iter->iterate = rbt_direct_iterator;
872 break;
873 case InvertedWalk: /* visit left, then right, then self */
874 iter->iterate = rbt_inverted_iterator;
875 iter->next_step = NextStepBegin;
876 break;
877 default:
878 elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
879 }
880 }
881
882 /*
883 * rbt_iterate: return the next node in traversal order, or NULL if no more
884 */
885 RBTNode *
rbt_iterate(RBTreeIterator * iter)886 rbt_iterate(RBTreeIterator *iter)
887 {
888 if (iter->is_over)
889 return NULL;
890
891 return iter->iterate(iter);
892 }
893