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

Generated by: LCOV version 1.13