Line data Source code
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 RBNode.color)
34 : */
35 : #define RBBLACK (0)
36 : #define RBRED (1)
37 :
38 : /*
39 : * RBTree control structure
40 : */
41 : struct RBTree
42 : {
43 : RBNode *root; /* root node, or RBNIL if tree is empty */
44 :
45 : /* Remaining fields are constant after rb_create */
46 :
47 : Size node_size; /* actual size of tree nodes */
48 : /* The caller-supplied manipulation functions */
49 : rb_comparator comparator;
50 : rb_combiner combiner;
51 : rb_allocfunc allocfunc;
52 : rb_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 RBNIL (&sentinel)
62 :
63 : static RBNode sentinel = {RBBLACK, RBNIL, RBNIL, 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 : * rb_create: create an empty RBTree
79 : *
80 : * Arguments are:
81 : * node_size: actual size of tree nodes (> sizeof(RBNode))
82 : * The manipulation functions:
83 : * comparator: compare two RBNodes for less/equal/greater
84 : * combiner: merge an existing tree entry with a new one
85 : * allocfunc: allocate a new RBNode
86 : * freefunc: free an old RBNode
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 rb_insert, in which the RBNode 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 : * RBNode fields, only the extra fields of the struct the RBNode 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 *
110 15 : rb_create(Size node_size,
111 : rb_comparator comparator,
112 : rb_combiner combiner,
113 : rb_allocfunc allocfunc,
114 : rb_freefunc freefunc,
115 : void *arg)
116 : {
117 15 : RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
118 :
119 15 : Assert(node_size > sizeof(RBNode));
120 :
121 15 : tree->root = RBNIL;
122 15 : tree->node_size = node_size;
123 15 : tree->comparator = comparator;
124 15 : tree->combiner = combiner;
125 15 : tree->allocfunc = allocfunc;
126 15 : tree->freefunc = freefunc;
127 :
128 15 : tree->arg = arg;
129 :
130 15 : return tree;
131 : }
132 :
133 : /* Copy the additional data fields from one RBNode to another */
134 : static inline void
135 35485 : rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src)
136 : {
137 35485 : memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
138 35485 : }
139 :
140 : /**********************************************************************
141 : * Search *
142 : **********************************************************************/
143 :
144 : /*
145 : * rb_find: search for a value in an RBTree
146 : *
147 : * data represents the value to try to find. Its RBNode 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 : RBNode *
153 0 : rb_find(RBTree *rb, const RBNode *data)
154 : {
155 0 : RBNode *node = rb->root;
156 :
157 0 : while (node != RBNIL)
158 : {
159 0 : int cmp = rb->comparator(data, node, rb->arg);
160 :
161 0 : if (cmp == 0)
162 0 : return node;
163 0 : else if (cmp < 0)
164 0 : node = node->left;
165 : else
166 0 : node = node->right;
167 : }
168 :
169 0 : return NULL;
170 : }
171 :
172 : /*
173 : * rb_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 rb_delete on the result if that's what
178 : * you want.
179 : */
180 : RBNode *
181 0 : rb_leftmost(RBTree *rb)
182 : {
183 0 : RBNode *node = rb->root;
184 0 : RBNode *leftmost = rb->root;
185 :
186 0 : while (node != RBNIL)
187 : {
188 0 : leftmost = node;
189 0 : node = node->left;
190 : }
191 :
192 0 : if (leftmost != RBNIL)
193 0 : return leftmost;
194 :
195 0 : 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
209 32646 : rb_rotate_left(RBTree *rb, RBNode *x)
210 : {
211 32646 : RBNode *y = x->right;
212 :
213 : /* establish x->right link */
214 32646 : x->right = y->left;
215 32646 : if (y->left != RBNIL)
216 16014 : y->left->parent = x;
217 :
218 : /* establish y->parent link */
219 32646 : if (y != RBNIL)
220 32646 : y->parent = x->parent;
221 32646 : if (x->parent)
222 : {
223 32611 : if (x == x->parent->left)
224 1070 : x->parent->left = y;
225 : else
226 31541 : x->parent->right = y;
227 : }
228 : else
229 : {
230 35 : rb->root = y;
231 : }
232 :
233 : /* link x and y */
234 32646 : y->left = x;
235 32646 : if (x != RBNIL)
236 32646 : x->parent = y;
237 32646 : }
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
246 1361 : rb_rotate_right(RBTree *rb, RBNode *x)
247 : {
248 1361 : RBNode *y = x->left;
249 :
250 : /* establish x->left link */
251 1361 : x->left = y->right;
252 1361 : if (y->right != RBNIL)
253 455 : y->right->parent = x;
254 :
255 : /* establish y->parent link */
256 1361 : if (y != RBNIL)
257 1361 : y->parent = x->parent;
258 1361 : if (x->parent)
259 : {
260 1348 : if (x == x->parent->right)
261 927 : x->parent->right = y;
262 : else
263 421 : x->parent->left = y;
264 : }
265 : else
266 : {
267 13 : rb->root = y;
268 : }
269 :
270 : /* link x and y */
271 1361 : y->right = x;
272 1361 : if (x != RBNIL)
273 1361 : x->parent = y;
274 1361 : }
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
290 35485 : rb_insert_fixup(RBTree *rb, RBNode *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 137435 : while (x != rb->root && x->parent->color == RBRED)
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 66465 : if (x->parent == x->parent->parent->left)
315 : {
316 1963 : RBNode *y = x->parent->parent->right;
317 :
318 1963 : if (y->color == RBRED)
319 : {
320 : /* uncle is RBRED */
321 1005 : x->parent->color = RBBLACK;
322 1005 : y->color = RBBLACK;
323 1005 : x->parent->parent->color = RBRED;
324 :
325 1005 : x = x->parent->parent;
326 : }
327 : else
328 : {
329 : /* uncle is RBBLACK */
330 958 : if (x == x->parent->right)
331 : {
332 : /* make x a left child */
333 612 : x = x->parent;
334 612 : rb_rotate_left(rb, x);
335 : }
336 :
337 : /* recolor and rotate */
338 958 : x->parent->color = RBBLACK;
339 958 : x->parent->parent->color = RBRED;
340 :
341 958 : rb_rotate_right(rb, x->parent->parent);
342 : }
343 : }
344 : else
345 : {
346 : /* mirror image of above code */
347 64502 : RBNode *y = x->parent->parent->left;
348 :
349 64502 : if (y->color == RBRED)
350 : {
351 : /* uncle is RBRED */
352 32468 : x->parent->color = RBBLACK;
353 32468 : y->color = RBBLACK;
354 32468 : x->parent->parent->color = RBRED;
355 :
356 32468 : x = x->parent->parent;
357 : }
358 : else
359 : {
360 : /* uncle is RBBLACK */
361 32034 : if (x == x->parent->left)
362 : {
363 403 : x = x->parent;
364 403 : rb_rotate_right(rb, x);
365 : }
366 32034 : x->parent->color = RBBLACK;
367 32034 : x->parent->parent->color = RBRED;
368 :
369 32034 : rb_rotate_left(rb, 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 35485 : rb->root->color = RBBLACK;
379 35485 : }
380 :
381 : /*
382 : * rb_insert: insert a new value into the tree.
383 : *
384 : * data represents the value to insert. Its RBNode 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 : RBNode *
399 140877 : rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
400 : {
401 : RBNode *current,
402 : *parent,
403 : *x;
404 : int cmp;
405 :
406 : /* find where node belongs */
407 140877 : current = rb->root;
408 140877 : parent = NULL;
409 140877 : cmp = 0; /* just to prevent compiler warning */
410 :
411 1979990 : while (current != RBNIL)
412 : {
413 1803628 : cmp = rb->comparator(data, current, rb->arg);
414 1803628 : if (cmp == 0)
415 : {
416 : /*
417 : * Found node with given key. Apply combiner.
418 : */
419 105392 : rb->combiner(current, data, rb->arg);
420 105392 : *isNew = false;
421 105392 : return current;
422 : }
423 1698236 : parent = current;
424 1698236 : current = (cmp < 0) ? current->left : current->right;
425 : }
426 :
427 : /*
428 : * Value is not present, so create a new node containing data.
429 : */
430 35485 : *isNew = true;
431 :
432 35485 : x = rb->allocfunc(rb->arg);
433 :
434 35485 : x->color = RBRED;
435 :
436 35485 : x->left = RBNIL;
437 35485 : x->right = RBNIL;
438 35485 : x->parent = parent;
439 35485 : rb_copy_data(rb, x, data);
440 :
441 : /* insert node in tree */
442 35485 : if (parent)
443 : {
444 35472 : if (cmp < 0)
445 2003 : parent->left = x;
446 : else
447 33469 : parent->right = x;
448 : }
449 : else
450 : {
451 13 : rb->root = x;
452 : }
453 :
454 35485 : rb_insert_fixup(rb, x);
455 :
456 35485 : 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
467 0 : rb_delete_fixup(RBTree *rb, RBNode *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 0 : while (x != rb->root && x->color == RBBLACK)
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 0 : if (x == x->parent->left)
484 : {
485 0 : RBNode *w = x->parent->right;
486 :
487 0 : if (w->color == RBRED)
488 : {
489 0 : w->color = RBBLACK;
490 0 : x->parent->color = RBRED;
491 :
492 0 : rb_rotate_left(rb, x->parent);
493 0 : w = x->parent->right;
494 : }
495 :
496 0 : if (w->left->color == RBBLACK && w->right->color == RBBLACK)
497 : {
498 0 : w->color = RBRED;
499 :
500 0 : x = x->parent;
501 : }
502 : else
503 : {
504 0 : if (w->right->color == RBBLACK)
505 : {
506 0 : w->left->color = RBBLACK;
507 0 : w->color = RBRED;
508 :
509 0 : rb_rotate_right(rb, w);
510 0 : w = x->parent->right;
511 : }
512 0 : w->color = x->parent->color;
513 0 : x->parent->color = RBBLACK;
514 0 : w->right->color = RBBLACK;
515 :
516 0 : rb_rotate_left(rb, x->parent);
517 0 : x = rb->root; /* Arrange for loop to terminate. */
518 : }
519 : }
520 : else
521 : {
522 0 : RBNode *w = x->parent->left;
523 :
524 0 : if (w->color == RBRED)
525 : {
526 0 : w->color = RBBLACK;
527 0 : x->parent->color = RBRED;
528 :
529 0 : rb_rotate_right(rb, x->parent);
530 0 : w = x->parent->left;
531 : }
532 :
533 0 : if (w->right->color == RBBLACK && w->left->color == RBBLACK)
534 : {
535 0 : w->color = RBRED;
536 :
537 0 : x = x->parent;
538 : }
539 : else
540 : {
541 0 : if (w->left->color == RBBLACK)
542 : {
543 0 : w->right->color = RBBLACK;
544 0 : w->color = RBRED;
545 :
546 0 : rb_rotate_left(rb, w);
547 0 : w = x->parent->left;
548 : }
549 0 : w->color = x->parent->color;
550 0 : x->parent->color = RBBLACK;
551 0 : w->left->color = RBBLACK;
552 :
553 0 : rb_rotate_right(rb, x->parent);
554 0 : x = rb->root; /* Arrange for loop to terminate. */
555 : }
556 : }
557 : }
558 0 : x->color = RBBLACK;
559 0 : }
560 :
561 : /*
562 : * Delete node z from tree.
563 : */
564 : static void
565 0 : rb_delete_node(RBTree *rb, RBNode *z)
566 : {
567 : RBNode *x,
568 : *y;
569 :
570 0 : if (!z || z == RBNIL)
571 0 : 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 0 : if (z->left == RBNIL || z->right == RBNIL)
579 : {
580 : /* y has a RBNIL node as a child */
581 0 : y = z;
582 : }
583 : else
584 : {
585 : /* find tree successor */
586 0 : y = z->right;
587 0 : while (y->left != RBNIL)
588 0 : y = y->left;
589 : }
590 :
591 : /* x is y's only child */
592 0 : if (y->left != RBNIL)
593 0 : x = y->left;
594 : else
595 0 : x = y->right;
596 :
597 : /* Remove y from the tree. */
598 0 : x->parent = y->parent;
599 0 : if (y->parent)
600 : {
601 0 : if (y == y->parent->left)
602 0 : y->parent->left = x;
603 : else
604 0 : y->parent->right = x;
605 : }
606 : else
607 : {
608 0 : rb->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 0 : if (y != z)
616 0 : rb_copy_data(rb, 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 0 : if (y->color == RBBLACK)
623 0 : rb_delete_fixup(rb, x);
624 :
625 : /* Now we can recycle the y node */
626 0 : if (rb->freefunc)
627 0 : rb->freefunc(y, rb->arg);
628 : }
629 :
630 : /*
631 : * rb_delete: remove the given tree entry
632 : *
633 : * "node" must have previously been found via rb_find or rb_leftmost.
634 : * It is caller's responsibility to free any subsidiary data attached
635 : * to the node before calling rb_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
640 0 : rb_delete(RBTree *rb, RBNode *node)
641 : {
642 0 : rb_delete_node(rb, node);
643 0 : }
644 :
645 : /**********************************************************************
646 : * Traverse *
647 : **********************************************************************/
648 :
649 : static RBNode *
650 35498 : rb_left_right_iterator(RBTreeIterator *iter)
651 : {
652 35498 : if (iter->last_visited == NULL)
653 : {
654 13 : iter->last_visited = iter->rb->root;
655 116 : while (iter->last_visited->left != RBNIL)
656 90 : iter->last_visited = iter->last_visited->left;
657 :
658 13 : return iter->last_visited;
659 : }
660 :
661 35485 : if (iter->last_visited->right != RBNIL)
662 : {
663 17743 : iter->last_visited = iter->last_visited->right;
664 53125 : while (iter->last_visited->left != RBNIL)
665 17639 : iter->last_visited = iter->last_visited->left;
666 :
667 17743 : return iter->last_visited;
668 : }
669 :
670 : for (;;)
671 : {
672 35485 : RBNode *came_from = iter->last_visited;
673 :
674 35485 : iter->last_visited = iter->last_visited->parent;
675 35485 : if (iter->last_visited == NULL)
676 : {
677 13 : iter->is_over = true;
678 13 : break;
679 : }
680 :
681 35472 : if (iter->last_visited->left == came_from)
682 17729 : break; /* came from left sub-tree, return current
683 : * node */
684 :
685 : /* else - came from right sub-tree, continue to move up */
686 17743 : }
687 :
688 17742 : return iter->last_visited;
689 : }
690 :
691 : static RBNode *
692 0 : rb_right_left_iterator(RBTreeIterator *iter)
693 : {
694 0 : if (iter->last_visited == NULL)
695 : {
696 0 : iter->last_visited = iter->rb->root;
697 0 : while (iter->last_visited->right != RBNIL)
698 0 : iter->last_visited = iter->last_visited->right;
699 :
700 0 : return iter->last_visited;
701 : }
702 :
703 0 : if (iter->last_visited->left != RBNIL)
704 : {
705 0 : iter->last_visited = iter->last_visited->left;
706 0 : while (iter->last_visited->right != RBNIL)
707 0 : iter->last_visited = iter->last_visited->right;
708 :
709 0 : return iter->last_visited;
710 : }
711 :
712 : for (;;)
713 : {
714 0 : RBNode *came_from = iter->last_visited;
715 :
716 0 : iter->last_visited = iter->last_visited->parent;
717 0 : if (iter->last_visited == NULL)
718 : {
719 0 : iter->is_over = true;
720 0 : break;
721 : }
722 :
723 0 : if (iter->last_visited->right == came_from)
724 0 : break; /* came from right sub-tree, return current
725 : * node */
726 :
727 : /* else - came from left sub-tree, continue to move up */
728 0 : }
729 :
730 0 : return iter->last_visited;
731 : }
732 :
733 : static RBNode *
734 0 : rb_direct_iterator(RBTreeIterator *iter)
735 : {
736 0 : if (iter->last_visited == NULL)
737 : {
738 0 : iter->last_visited = iter->rb->root;
739 0 : return iter->last_visited;
740 : }
741 :
742 0 : if (iter->last_visited->left != RBNIL)
743 : {
744 0 : iter->last_visited = iter->last_visited->left;
745 0 : return iter->last_visited;
746 : }
747 :
748 : do
749 : {
750 0 : if (iter->last_visited->right != RBNIL)
751 : {
752 0 : iter->last_visited = iter->last_visited->right;
753 0 : break;
754 : }
755 :
756 : /* go up and one step right */
757 : for (;;)
758 : {
759 0 : RBNode *came_from = iter->last_visited;
760 :
761 0 : iter->last_visited = iter->last_visited->parent;
762 0 : if (iter->last_visited == NULL)
763 : {
764 0 : iter->is_over = true;
765 0 : break;
766 : }
767 :
768 0 : if ((iter->last_visited->right != came_from) && (iter->last_visited->right != RBNIL))
769 : {
770 0 : iter->last_visited = iter->last_visited->right;
771 0 : return iter->last_visited;
772 : }
773 0 : }
774 : }
775 0 : while (iter->last_visited != NULL);
776 :
777 0 : return iter->last_visited;
778 : }
779 :
780 : static RBNode *
781 0 : rb_inverted_iterator(RBTreeIterator *iter)
782 : {
783 : RBNode *came_from;
784 : RBNode *current;
785 :
786 0 : current = iter->last_visited;
787 :
788 : loop:
789 0 : switch ((InvertedWalkNextStep) iter->next_step)
790 : {
791 : /* First call, begin from root */
792 : case NextStepBegin:
793 0 : current = iter->rb->root;
794 0 : iter->next_step = NextStepLeft;
795 0 : goto loop;
796 :
797 : case NextStepLeft:
798 0 : while (current->left != RBNIL)
799 0 : current = current->left;
800 :
801 0 : iter->next_step = NextStepRight;
802 0 : goto loop;
803 :
804 : case NextStepRight:
805 0 : if (current->right != RBNIL)
806 : {
807 0 : current = current->right;
808 0 : iter->next_step = NextStepLeft;
809 0 : goto loop;
810 : }
811 : else /* not moved - return current, then go up */
812 0 : iter->next_step = NextStepUp;
813 0 : break;
814 :
815 : case NextStepUp:
816 0 : came_from = current;
817 0 : current = current->parent;
818 0 : if (current == NULL)
819 : {
820 0 : iter->is_over = true;
821 0 : break; /* end of iteration */
822 : }
823 0 : else if (came_from == current->right)
824 : {
825 : /* return current, then continue to go up */
826 0 : break;
827 : }
828 : else
829 : {
830 : /* otherwise we came from the left */
831 0 : Assert(came_from == current->left);
832 0 : iter->next_step = NextStepRight;
833 0 : goto loop;
834 : }
835 : }
836 :
837 0 : iter->last_visited = current;
838 0 : return current;
839 : }
840 :
841 : /*
842 : * rb_begin_iterate: prepare to traverse the tree in any of several orders
843 : *
844 : * After calling rb_begin_iterate, call rb_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 : * rb_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
855 15 : rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
856 : {
857 : /* Common initialization for all traversal orders */
858 15 : iter->rb = rb;
859 15 : iter->last_visited = NULL;
860 15 : iter->is_over = (rb->root == RBNIL);
861 :
862 15 : switch (ctrl)
863 : {
864 : case LeftRightWalk: /* visit left, then self, then right */
865 15 : iter->iterate = rb_left_right_iterator;
866 15 : break;
867 : case RightLeftWalk: /* visit right, then self, then left */
868 0 : iter->iterate = rb_right_left_iterator;
869 0 : break;
870 : case DirectWalk: /* visit self, then left, then right */
871 0 : iter->iterate = rb_direct_iterator;
872 0 : break;
873 : case InvertedWalk: /* visit left, then right, then self */
874 0 : iter->iterate = rb_inverted_iterator;
875 0 : iter->next_step = NextStepBegin;
876 0 : break;
877 : default:
878 0 : elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
879 : }
880 15 : }
881 :
882 : /*
883 : * rb_iterate: return the next node in traversal order, or NULL if no more
884 : */
885 : RBNode *
886 35500 : rb_iterate(RBTreeIterator *iter)
887 : {
888 35500 : if (iter->is_over)
889 2 : return NULL;
890 :
891 35498 : return iter->iterate(iter);
892 : }
|
