LCOV - code coverage report
Current view: top level - src/backend/lib - rbtree.c (source / functions) Hit Total Coverage
Test: PostgreSQL Lines: 243 244 99.6 %
Date: 2017-09-21 23:18:17 Functions: 15 15 100.0 %
Legend: Lines: hit not hit

          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             : /*
      67             :  * rb_create: create an empty RBTree
      68             :  *
      69             :  * Arguments are:
      70             :  *  node_size: actual size of tree nodes (> sizeof(RBNode))
      71             :  *  The manipulation functions:
      72             :  *  comparator: compare two RBNodes for less/equal/greater
      73             :  *  combiner: merge an existing tree entry with a new one
      74             :  *  allocfunc: allocate a new RBNode
      75             :  *  freefunc: free an old RBNode
      76             :  *  arg: passthrough pointer that will be passed to the manipulation functions
      77             :  *
      78             :  * Note that the combiner's righthand argument will be a "proposed" tree node,
      79             :  * ie the input to rb_insert, in which the RBNode fields themselves aren't
      80             :  * valid.  Similarly, either input to the comparator may be a "proposed" node.
      81             :  * This shouldn't matter since the functions aren't supposed to look at the
      82             :  * RBNode fields, only the extra fields of the struct the RBNode is embedded
      83             :  * in.
      84             :  *
      85             :  * The freefunc should just be pfree or equivalent; it should NOT attempt
      86             :  * to free any subsidiary data, because the node passed to it may not contain
      87             :  * valid data!  freefunc can be NULL if caller doesn't require retail
      88             :  * space reclamation.
      89             :  *
      90             :  * The RBTree node is palloc'd in the caller's memory context.  Note that
      91             :  * all contents of the tree are actually allocated by the caller, not here.
      92             :  *
      93             :  * Since tree contents are managed by the caller, there is currently not
      94             :  * an explicit "destroy" operation; typically a tree would be freed by
      95             :  * resetting or deleting the memory context it's stored in.  You can pfree
      96             :  * the RBTree node if you feel the urge.
      97             :  */
      98             : RBTree *
      99          72 : rb_create(Size node_size,
     100             :           rb_comparator comparator,
     101             :           rb_combiner combiner,
     102             :           rb_allocfunc allocfunc,
     103             :           rb_freefunc freefunc,
     104             :           void *arg)
     105             : {
     106          72 :     RBTree     *tree = (RBTree *) palloc(sizeof(RBTree));
     107             : 
     108          72 :     Assert(node_size > sizeof(RBNode));
     109             : 
     110          72 :     tree->root = RBNIL;
     111          72 :     tree->node_size = node_size;
     112          72 :     tree->comparator = comparator;
     113          72 :     tree->combiner = combiner;
     114          72 :     tree->allocfunc = allocfunc;
     115          72 :     tree->freefunc = freefunc;
     116             : 
     117          72 :     tree->arg = arg;
     118             : 
     119          72 :     return tree;
     120             : }
     121             : 
     122             : /* Copy the additional data fields from one RBNode to another */
     123             : static inline void
     124      125732 : rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src)
     125             : {
     126      125732 :     memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
     127      125732 : }
     128             : 
     129             : /**********************************************************************
     130             :  *                        Search                                      *
     131             :  **********************************************************************/
     132             : 
     133             : /*
     134             :  * rb_find: search for a value in an RBTree
     135             :  *
     136             :  * data represents the value to try to find.  Its RBNode fields need not
     137             :  * be valid, it's the extra data in the larger struct that is of interest.
     138             :  *
     139             :  * Returns the matching tree entry, or NULL if no match is found.
     140             :  */
     141             : RBNode *
     142       40001 : rb_find(RBTree *rb, const RBNode *data)
     143             : {
     144       40001 :     RBNode     *node = rb->root;
     145             : 
     146      532231 :     while (node != RBNIL)
     147             :     {
     148      481229 :         int         cmp = rb->comparator(data, node, rb->arg);
     149             : 
     150      481229 :         if (cmp == 0)
     151       29000 :             return node;
     152      452229 :         else if (cmp < 0)
     153      265531 :             node = node->left;
     154             :         else
     155      186698 :             node = node->right;
     156             :     }
     157             : 
     158       11001 :     return NULL;
     159             : }
     160             : 
     161             : /*
     162             :  * rb_leftmost: fetch the leftmost (smallest-valued) tree node.
     163             :  * Returns NULL if tree is empty.
     164             :  *
     165             :  * Note: in the original implementation this included an unlink step, but
     166             :  * that's a bit awkward.  Just call rb_delete on the result if that's what
     167             :  * you want.
     168             :  */
     169             : RBNode *
     170           3 : rb_leftmost(RBTree *rb)
     171             : {
     172           3 :     RBNode     *node = rb->root;
     173           3 :     RBNode     *leftmost = rb->root;
     174             : 
     175          20 :     while (node != RBNIL)
     176             :     {
     177          14 :         leftmost = node;
     178          14 :         node = node->left;
     179             :     }
     180             : 
     181           3 :     if (leftmost != RBNIL)
     182           1 :         return leftmost;
     183             : 
     184           2 :     return NULL;
     185             : }
     186             : 
     187             : /**********************************************************************
     188             :  *                            Insertion                               *
     189             :  **********************************************************************/
     190             : 
     191             : /*
     192             :  * Rotate node x to left.
     193             :  *
     194             :  * x's right child takes its place in the tree, and x becomes the left
     195             :  * child of that node.
     196             :  */
     197             : static void
     198       87361 : rb_rotate_left(RBTree *rb, RBNode *x)
     199             : {
     200       87361 :     RBNode     *y = x->right;
     201             : 
     202             :     /* establish x->right link */
     203       87361 :     x->right = y->left;
     204       87361 :     if (y->left != RBNIL)
     205       40644 :         y->left->parent = x;
     206             : 
     207             :     /* establish y->parent link */
     208       87361 :     if (y != RBNIL)
     209       87361 :         y->parent = x->parent;
     210       87361 :     if (x->parent)
     211             :     {
     212       87231 :         if (x == x->parent->left)
     213       18302 :             x->parent->left = y;
     214             :         else
     215       68929 :             x->parent->right = y;
     216             :     }
     217             :     else
     218             :     {
     219         130 :         rb->root = y;
     220             :     }
     221             : 
     222             :     /* link x and y */
     223       87361 :     y->left = x;
     224       87361 :     if (x != RBNIL)
     225       87361 :         x->parent = y;
     226       87361 : }
     227             : 
     228             : /*
     229             :  * Rotate node x to right.
     230             :  *
     231             :  * x's left right child takes its place in the tree, and x becomes the right
     232             :  * child of that node.
     233             :  */
     234             : static void
     235       19983 : rb_rotate_right(RBTree *rb, RBNode *x)
     236             : {
     237       19983 :     RBNode     *y = x->left;
     238             : 
     239             :     /* establish x->left link */
     240       19983 :     x->left = y->right;
     241       19983 :     if (y->right != RBNIL)
     242        5755 :         y->right->parent = x;
     243             : 
     244             :     /* establish y->parent link */
     245       19983 :     if (y != RBNIL)
     246       19983 :         y->parent = x->parent;
     247       19983 :     if (x->parent)
     248             :     {
     249       19948 :         if (x == x->parent->right)
     250       13544 :             x->parent->right = y;
     251             :         else
     252        6404 :             x->parent->left = y;
     253             :     }
     254             :     else
     255             :     {
     256          35 :         rb->root = y;
     257             :     }
     258             : 
     259             :     /* link x and y */
     260       19983 :     y->right = x;
     261       19983 :     if (x != RBNIL)
     262       19983 :         x->parent = y;
     263       19983 : }
     264             : 
     265             : /*
     266             :  * Maintain Red-Black tree balance after inserting node x.
     267             :  *
     268             :  * The newly inserted node is always initially marked red.  That may lead to
     269             :  * a situation where a red node has a red child, which is prohibited.  We can
     270             :  * always fix the problem by a series of color changes and/or "rotations",
     271             :  * which move the problem progressively higher up in the tree.  If one of the
     272             :  * two red nodes is the root, we can always fix the problem by changing the
     273             :  * root from red to black.
     274             :  *
     275             :  * (This does not work lower down in the tree because we must also maintain
     276             :  * the invariant that every leaf has equal black-height.)
     277             :  */
     278             : static void
     279      125265 : rb_insert_fixup(RBTree *rb, RBNode *x)
     280             : {
     281             :     /*
     282             :      * x is always a red node.  Initially, it is the newly inserted node. Each
     283             :      * iteration of this loop moves it higher up in the tree.
     284             :      */
     285      433915 :     while (x != rb->root && x->parent->color == RBRED)
     286             :     {
     287             :         /*
     288             :          * x and x->parent are both red.  Fix depends on whether x->parent is
     289             :          * a left or right child.  In either case, we define y to be the
     290             :          * "uncle" of x, that is, the other child of x's grandparent.
     291             :          *
     292             :          * If the uncle is red, we flip the grandparent to red and its two
     293             :          * children to black.  Then we loop around again to check whether the
     294             :          * grandparent still has a problem.
     295             :          *
     296             :          * If the uncle is black, we will perform one or two "rotations" to
     297             :          * balance the tree.  Either x or x->parent will take the
     298             :          * grandparent's position in the tree and recolored black, and the
     299             :          * original grandparent will be recolored red and become a child of
     300             :          * that node. This always leaves us with a valid red-black tree, so
     301             :          * the loop will terminate.
     302             :          */
     303      183385 :         if (x->parent == x->parent->parent->left)
     304             :         {
     305       28195 :             RBNode     *y = x->parent->parent->right;
     306             : 
     307       28195 :             if (y->color == RBRED)
     308             :             {
     309             :                 /* uncle is RBRED */
     310       15325 :                 x->parent->color = RBBLACK;
     311       15325 :                 y->color = RBBLACK;
     312       15325 :                 x->parent->parent->color = RBRED;
     313             : 
     314       15325 :                 x = x->parent->parent;
     315             :             }
     316             :             else
     317             :             {
     318             :                 /* uncle is RBBLACK */
     319       12870 :                 if (x == x->parent->right)
     320             :                 {
     321             :                     /* make x a left child */
     322        6976 :                     x = x->parent;
     323        6976 :                     rb_rotate_left(rb, x);
     324             :                 }
     325             : 
     326             :                 /* recolor and rotate */
     327       12870 :                 x->parent->color = RBBLACK;
     328       12870 :                 x->parent->parent->color = RBRED;
     329             : 
     330       12870 :                 rb_rotate_right(rb, x->parent->parent);
     331             :             }
     332             :         }
     333             :         else
     334             :         {
     335             :             /* mirror image of above code */
     336      155190 :             RBNode     *y = x->parent->parent->left;
     337             : 
     338      155190 :             if (y->color == RBRED)
     339             :             {
     340             :                 /* uncle is RBRED */
     341       80118 :                 x->parent->color = RBBLACK;
     342       80118 :                 y->color = RBBLACK;
     343       80118 :                 x->parent->parent->color = RBRED;
     344             : 
     345       80118 :                 x = x->parent->parent;
     346             :             }
     347             :             else
     348             :             {
     349             :                 /* uncle is RBBLACK */
     350       75072 :                 if (x == x->parent->left)
     351             :                 {
     352        5916 :                     x = x->parent;
     353        5916 :                     rb_rotate_right(rb, x);
     354             :                 }
     355       75072 :                 x->parent->color = RBBLACK;
     356       75072 :                 x->parent->parent->color = RBRED;
     357             : 
     358       75072 :                 rb_rotate_left(rb, x->parent->parent);
     359             :             }
     360             :         }
     361             :     }
     362             : 
     363             :     /*
     364             :      * The root may already have been black; if not, the black-height of every
     365             :      * node in the tree increases by one.
     366             :      */
     367      125265 :     rb->root->color = RBBLACK;
     368      125265 : }
     369             : 
     370             : /*
     371             :  * rb_insert: insert a new value into the tree.
     372             :  *
     373             :  * data represents the value to insert.  Its RBNode fields need not
     374             :  * be valid, it's the extra data in the larger struct that is of interest.
     375             :  *
     376             :  * If the value represented by "data" is not present in the tree, then
     377             :  * we copy "data" into a new tree entry and return that node, setting *isNew
     378             :  * to true.
     379             :  *
     380             :  * If the value represented by "data" is already present, then we call the
     381             :  * combiner function to merge data into the existing node, and return the
     382             :  * existing node, setting *isNew to false.
     383             :  *
     384             :  * "data" is unmodified in either case; it's typically just a local
     385             :  * variable in the caller.
     386             :  */
     387             : RBNode *
     388      490946 : rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
     389             : {
     390             :     RBNode     *current,
     391             :                *parent,
     392             :                *x;
     393             :     int         cmp;
     394             : 
     395             :     /* find where node belongs */
     396      490946 :     current = rb->root;
     397      490946 :     parent = NULL;
     398      490946 :     cmp = 0;                    /* just to prevent compiler warning */
     399             : 
     400     5505559 :     while (current != RBNIL)
     401             :     {
     402     4889348 :         cmp = rb->comparator(data, current, rb->arg);
     403     4889348 :         if (cmp == 0)
     404             :         {
     405             :             /*
     406             :              * Found node with given key.  Apply combiner.
     407             :              */
     408      365681 :             rb->combiner(current, data, rb->arg);
     409      365681 :             *isNew = false;
     410      365681 :             return current;
     411             :         }
     412     4523667 :         parent = current;
     413     4523667 :         current = (cmp < 0) ? current->left : current->right;
     414             :     }
     415             : 
     416             :     /*
     417             :      * Value is not present, so create a new node containing data.
     418             :      */
     419      125265 :     *isNew = true;
     420             : 
     421      125265 :     x = rb->allocfunc(rb->arg);
     422             : 
     423      125265 :     x->color = RBRED;
     424             : 
     425      125265 :     x->left = RBNIL;
     426      125265 :     x->right = RBNIL;
     427      125265 :     x->parent = parent;
     428      125265 :     rb_copy_data(rb, x, data);
     429             : 
     430             :     /* insert node in tree */
     431      125265 :     if (parent)
     432             :     {
     433      125202 :         if (cmp < 0)
     434       30790 :             parent->left = x;
     435             :         else
     436       94412 :             parent->right = x;
     437             :     }
     438             :     else
     439             :     {
     440          63 :         rb->root = x;
     441             :     }
     442             : 
     443      125265 :     rb_insert_fixup(rb, x);
     444             : 
     445      125265 :     return x;
     446             : }
     447             : 
     448             : /**********************************************************************
     449             :  *                          Deletion                                  *
     450             :  **********************************************************************/
     451             : 
     452             : /*
     453             :  * Maintain Red-Black tree balance after deleting a black node.
     454             :  */
     455             : static void
     456        9514 : rb_delete_fixup(RBTree *rb, RBNode *x)
     457             : {
     458             :     /*
     459             :      * x is always a black node.  Initially, it is the former child of the
     460             :      * deleted node.  Each iteration of this loop moves it higher up in the
     461             :      * tree.
     462             :      */
     463       27402 :     while (x != rb->root && x->color == RBBLACK)
     464             :     {
     465             :         /*
     466             :          * Left and right cases are symmetric.  Any nodes that are children of
     467             :          * x have a black-height one less than the remainder of the nodes in
     468             :          * the tree.  We rotate and recolor nodes to move the problem up the
     469             :          * tree: at some stage we'll either fix the problem, or reach the root
     470             :          * (where the black-height is allowed to decrease).
     471             :          */
     472        8374 :         if (x == x->parent->left)
     473             :         {
     474        8223 :             RBNode     *w = x->parent->right;
     475             : 
     476        8223 :             if (w->color == RBRED)
     477             :             {
     478        2157 :                 w->color = RBBLACK;
     479        2157 :                 x->parent->color = RBRED;
     480             : 
     481        2157 :                 rb_rotate_left(rb, x->parent);
     482        2157 :                 w = x->parent->right;
     483             :             }
     484             : 
     485        8223 :             if (w->left->color == RBBLACK && w->right->color == RBBLACK)
     486             :             {
     487        5092 :                 w->color = RBRED;
     488             : 
     489        5092 :                 x = x->parent;
     490             :             }
     491             :             else
     492             :             {
     493        3131 :                 if (w->right->color == RBBLACK)
     494             :                 {
     495        1088 :                     w->left->color = RBBLACK;
     496        1088 :                     w->color = RBRED;
     497             : 
     498        1088 :                     rb_rotate_right(rb, w);
     499        1088 :                     w = x->parent->right;
     500             :                 }
     501        3131 :                 w->color = x->parent->color;
     502        3131 :                 x->parent->color = RBBLACK;
     503        3131 :                 w->right->color = RBBLACK;
     504             : 
     505        3131 :                 rb_rotate_left(rb, x->parent);
     506        3131 :                 x = rb->root;    /* Arrange for loop to terminate. */
     507             :             }
     508             :         }
     509             :         else
     510             :         {
     511         151 :             RBNode     *w = x->parent->left;
     512             : 
     513         151 :             if (w->color == RBRED)
     514             :             {
     515          17 :                 w->color = RBBLACK;
     516          17 :                 x->parent->color = RBRED;
     517             : 
     518          17 :                 rb_rotate_right(rb, x->parent);
     519          17 :                 w = x->parent->left;
     520             :             }
     521             : 
     522         151 :             if (w->right->color == RBBLACK && w->left->color == RBBLACK)
     523             :             {
     524          59 :                 w->color = RBRED;
     525             : 
     526          59 :                 x = x->parent;
     527             :             }
     528             :             else
     529             :             {
     530          92 :                 if (w->left->color == RBBLACK)
     531             :                 {
     532          25 :                     w->right->color = RBBLACK;
     533          25 :                     w->color = RBRED;
     534             : 
     535          25 :                     rb_rotate_left(rb, w);
     536          25 :                     w = x->parent->left;
     537             :                 }
     538          92 :                 w->color = x->parent->color;
     539          92 :                 x->parent->color = RBBLACK;
     540          92 :                 w->left->color = RBBLACK;
     541             : 
     542          92 :                 rb_rotate_right(rb, x->parent);
     543          92 :                 x = rb->root;    /* Arrange for loop to terminate. */
     544             :             }
     545             :         }
     546             :     }
     547        9514 :     x->color = RBBLACK;
     548        9514 : }
     549             : 
     550             : /*
     551             :  * Delete node z from tree.
     552             :  */
     553             : static void
     554       10000 : rb_delete_node(RBTree *rb, RBNode *z)
     555             : {
     556             :     RBNode     *x,
     557             :                *y;
     558             : 
     559             :     /* This is just paranoia: we should only get called on a valid node */
     560       10000 :     if (!z || z == RBNIL)
     561       10000 :         return;
     562             : 
     563             :     /*
     564             :      * y is the node that will actually be removed from the tree.  This will
     565             :      * be z if z has fewer than two children, or the tree successor of z
     566             :      * otherwise.
     567             :      */
     568       10000 :     if (z->left == RBNIL || z->right == RBNIL)
     569             :     {
     570             :         /* y has a RBNIL node as a child */
     571        9533 :         y = z;
     572             :     }
     573             :     else
     574             :     {
     575             :         /* find tree successor */
     576         467 :         y = z->right;
     577        1568 :         while (y->left != RBNIL)
     578         634 :             y = y->left;
     579             :     }
     580             : 
     581             :     /* x is y's only child */
     582       10000 :     if (y->left != RBNIL)
     583          67 :         x = y->left;
     584             :     else
     585        9933 :         x = y->right;
     586             : 
     587             :     /* Remove y from the tree. */
     588       10000 :     x->parent = y->parent;
     589       10000 :     if (y->parent)
     590             :     {
     591        9998 :         if (y == y->parent->left)
     592        9575 :             y->parent->left = x;
     593             :         else
     594         423 :             y->parent->right = x;
     595             :     }
     596             :     else
     597             :     {
     598           2 :         rb->root = x;
     599             :     }
     600             : 
     601             :     /*
     602             :      * If we removed the tree successor of z rather than z itself, then move
     603             :      * the data for the removed node to the one we were supposed to remove.
     604             :      */
     605       10000 :     if (y != z)
     606         467 :         rb_copy_data(rb, z, y);
     607             : 
     608             :     /*
     609             :      * Removing a black node might make some paths from root to leaf contain
     610             :      * fewer black nodes than others, or it might make two red nodes adjacent.
     611             :      */
     612       10000 :     if (y->color == RBBLACK)
     613        9514 :         rb_delete_fixup(rb, x);
     614             : 
     615             :     /* Now we can recycle the y node */
     616       10000 :     if (rb->freefunc)
     617       10000 :         rb->freefunc(y, rb->arg);
     618             : }
     619             : 
     620             : /*
     621             :  * rb_delete: remove the given tree entry
     622             :  *
     623             :  * "node" must have previously been found via rb_find or rb_leftmost.
     624             :  * It is caller's responsibility to free any subsidiary data attached
     625             :  * to the node before calling rb_delete.  (Do *not* try to push that
     626             :  * responsibility off to the freefunc, as some other physical node
     627             :  * may be the one actually freed!)
     628             :  */
     629             : void
     630       10000 : rb_delete(RBTree *rb, RBNode *node)
     631             : {
     632       10000 :     rb_delete_node(rb, node);
     633       10000 : }
     634             : 
     635             : /**********************************************************************
     636             :  *                        Traverse                                    *
     637             :  **********************************************************************/
     638             : 
     639             : static RBNode *
     640       85324 : rb_left_right_iterator(RBTreeIterator *iter)
     641             : {
     642       85324 :     if (iter->last_visited == NULL)
     643             :     {
     644          59 :         iter->last_visited = iter->rb->root;
     645         381 :         while (iter->last_visited->left != RBNIL)
     646         263 :             iter->last_visited = iter->last_visited->left;
     647             : 
     648          59 :         return iter->last_visited;
     649             :     }
     650             : 
     651       85265 :     if (iter->last_visited->right != RBNIL)
     652             :     {
     653       42652 :         iter->last_visited = iter->last_visited->right;
     654      127595 :         while (iter->last_visited->left != RBNIL)
     655       42291 :             iter->last_visited = iter->last_visited->left;
     656             : 
     657       42652 :         return iter->last_visited;
     658             :     }
     659             : 
     660             :     for (;;)
     661             :     {
     662       85265 :         RBNode     *came_from = iter->last_visited;
     663             : 
     664       85265 :         iter->last_visited = iter->last_visited->parent;
     665       85265 :         if (iter->last_visited == NULL)
     666             :         {
     667          59 :             iter->is_over = true;
     668          59 :             break;
     669             :         }
     670             : 
     671       85206 :         if (iter->last_visited->left == came_from)
     672       42554 :             break;              /* came from left sub-tree, return current
     673             :                                  * node */
     674             : 
     675             :         /* else - came from right sub-tree, continue to move up */
     676       42652 :     }
     677             : 
     678       42613 :     return iter->last_visited;
     679             : }
     680             : 
     681             : static RBNode *
     682       10001 : rb_right_left_iterator(RBTreeIterator *iter)
     683             : {
     684       10001 :     if (iter->last_visited == NULL)
     685             :     {
     686           1 :         iter->last_visited = iter->rb->root;
     687          14 :         while (iter->last_visited->right != RBNIL)
     688          12 :             iter->last_visited = iter->last_visited->right;
     689             : 
     690           1 :         return iter->last_visited;
     691             :     }
     692             : 
     693       10000 :     if (iter->last_visited->left != RBNIL)
     694             :     {
     695        4996 :         iter->last_visited = iter->last_visited->left;
     696       14983 :         while (iter->last_visited->right != RBNIL)
     697        4991 :             iter->last_visited = iter->last_visited->right;
     698             : 
     699        4996 :         return iter->last_visited;
     700             :     }
     701             : 
     702             :     for (;;)
     703             :     {
     704       10000 :         RBNode     *came_from = iter->last_visited;
     705             : 
     706       10000 :         iter->last_visited = iter->last_visited->parent;
     707       10000 :         if (iter->last_visited == NULL)
     708             :         {
     709           1 :             iter->is_over = true;
     710           1 :             break;
     711             :         }
     712             : 
     713        9999 :         if (iter->last_visited->right == came_from)
     714        5003 :             break;              /* came from right sub-tree, return current
     715             :                                  * node */
     716             : 
     717             :         /* else - came from left sub-tree, continue to move up */
     718        4996 :     }
     719             : 
     720        5004 :     return iter->last_visited;
     721             : }
     722             : 
     723             : /*
     724             :  * rb_begin_iterate: prepare to traverse the tree in any of several orders
     725             :  *
     726             :  * After calling rb_begin_iterate, call rb_iterate repeatedly until it
     727             :  * returns NULL or the traversal stops being of interest.
     728             :  *
     729             :  * If the tree is changed during traversal, results of further calls to
     730             :  * rb_iterate are unspecified.  Multiple concurrent iterators on the same
     731             :  * tree are allowed.
     732             :  *
     733             :  * The iterator state is stored in the 'iter' struct.  The caller should
     734             :  * treat it as an opaque struct.
     735             :  */
     736             : void
     737          71 : rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
     738             : {
     739             :     /* Common initialization for all traversal orders */
     740          71 :     iter->rb = rb;
     741          71 :     iter->last_visited = NULL;
     742          71 :     iter->is_over = (rb->root == RBNIL);
     743             : 
     744          71 :     switch (ctrl)
     745             :     {
     746             :         case LeftRightWalk:     /* visit left, then self, then right */
     747          69 :             iter->iterate = rb_left_right_iterator;
     748          69 :             break;
     749             :         case RightLeftWalk:     /* visit right, then self, then left */
     750           2 :             iter->iterate = rb_right_left_iterator;
     751           2 :             break;
     752             :         default:
     753           0 :             elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
     754             :     }
     755          71 : }
     756             : 
     757             : /*
     758             :  * rb_iterate: return the next node in traversal order, or NULL if no more
     759             :  */
     760             : RBNode *
     761       95336 : rb_iterate(RBTreeIterator *iter)
     762             : {
     763       95336 :     if (iter->is_over)
     764          11 :         return NULL;
     765             : 
     766       95325 :     return iter->iterate(iter);
     767             : }

Generated by: LCOV version 1.11