LCOV - code coverage report
Current view: top level - src/backend/lib - rbtree.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 267 270 98.9 %
Date: 2024-02-22 00:11:39 Functions: 17 17 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-2024, 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             :     .color = RBTBLACK,.left = RBTNIL,.right = RBTNIL,.parent = 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         356 : 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         356 :     RBTree     *tree = (RBTree *) palloc(sizeof(RBTree));
     110             : 
     111             :     Assert(node_size > sizeof(RBTNode));
     112             : 
     113         356 :     tree->root = RBTNIL;
     114         356 :     tree->node_size = node_size;
     115         356 :     tree->comparator = comparator;
     116         356 :     tree->combiner = combiner;
     117         356 :     tree->allocfunc = allocfunc;
     118         356 :     tree->freefunc = freefunc;
     119             : 
     120         356 :     tree->arg = arg;
     121             : 
     122         356 :     return tree;
     123             : }
     124             : 
     125             : /* Copy the additional data fields from one RBTNode to another */
     126             : static inline void
     127      640254 : rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
     128             : {
     129      640254 :     memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
     130      640254 : }
     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      981412 :     while (node != RBTNIL)
     150             :     {
     151      959410 :         int         cmp = rbt->comparator(data, node, rbt->arg);
     152             : 
     153      959410 :         if (cmp == 0)
     154       58000 :             return node;
     155      901410 :         else if (cmp < 0)
     156      525580 :             node = node->left;
     157             :         else
     158      375830 :             node = node->right;
     159             :     }
     160             : 
     161       22002 :     return NULL;
     162             : }
     163             : 
     164             : /*
     165             :  * rbt_find_great: search for a greater value in an RBTree
     166             :  *
     167             :  * If equal_match is true, this will be a great or equal search.
     168             :  *
     169             :  * Returns the matching tree entry, or NULL if no match is found.
     170             :  */
     171             : RBTNode *
     172        5784 : rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
     173             : {
     174        5784 :     RBTNode    *node = rbt->root;
     175        5784 :     RBTNode    *greater = NULL;
     176             : 
     177       81946 :     while (node != RBTNIL)
     178             :     {
     179       76164 :         int         cmp = rbt->comparator(data, node, rbt->arg);
     180             : 
     181       76164 :         if (equal_match && cmp == 0)
     182           2 :             return node;
     183       76162 :         else if (cmp < 0)
     184             :         {
     185       30872 :             greater = node;
     186       30872 :             node = node->left;
     187             :         }
     188             :         else
     189       45290 :             node = node->right;
     190             :     }
     191             : 
     192        5782 :     return greater;
     193             : }
     194             : 
     195             : /*
     196             :  * rbt_find_less: search for a lesser value in an RBTree
     197             :  *
     198             :  * If equal_match is true, this will be a less or equal search.
     199             :  *
     200             :  * Returns the matching tree entry, or NULL if no match is found.
     201             :  */
     202             : RBTNode *
     203       14226 : rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
     204             : {
     205       14226 :     RBTNode    *node = rbt->root;
     206       14226 :     RBTNode    *lesser = NULL;
     207             : 
     208      197358 :     while (node != RBTNIL)
     209             :     {
     210      183134 :         int         cmp = rbt->comparator(data, node, rbt->arg);
     211             : 
     212      183134 :         if (equal_match && cmp == 0)
     213           2 :             return node;
     214      183132 :         else if (cmp > 0)
     215             :         {
     216       90562 :             lesser = node;
     217       90562 :             node = node->right;
     218             :         }
     219             :         else
     220       92570 :             node = node->left;
     221             :     }
     222             : 
     223       14224 :     return lesser;
     224             : }
     225             : 
     226             : /*
     227             :  * rbt_leftmost: fetch the leftmost (smallest-valued) tree node.
     228             :  * Returns NULL if tree is empty.
     229             :  *
     230             :  * Note: in the original implementation this included an unlink step, but
     231             :  * that's a bit awkward.  Just call rbt_delete on the result if that's what
     232             :  * you want.
     233             :  */
     234             : RBTNode *
     235           6 : rbt_leftmost(RBTree *rbt)
     236             : {
     237           6 :     RBTNode    *node = rbt->root;
     238           6 :     RBTNode    *leftmost = rbt->root;
     239             : 
     240          28 :     while (node != RBTNIL)
     241             :     {
     242          22 :         leftmost = node;
     243          22 :         node = node->left;
     244             :     }
     245             : 
     246           6 :     if (leftmost != RBTNIL)
     247           2 :         return leftmost;
     248             : 
     249           4 :     return NULL;
     250             : }
     251             : 
     252             : /**********************************************************************
     253             :  *                            Insertion                               *
     254             :  **********************************************************************/
     255             : 
     256             : /*
     257             :  * Rotate node x to left.
     258             :  *
     259             :  * x's right child takes its place in the tree, and x becomes the left
     260             :  * child of that node.
     261             :  */
     262             : static void
     263      537140 : rbt_rotate_left(RBTree *rbt, RBTNode *x)
     264             : {
     265      537140 :     RBTNode    *y = x->right;
     266             : 
     267             :     /* establish x->right link */
     268      537140 :     x->right = y->left;
     269      537140 :     if (y->left != RBTNIL)
     270      259534 :         y->left->parent = x;
     271             : 
     272             :     /* establish y->parent link */
     273      537140 :     if (y != RBTNIL)
     274      537140 :         y->parent = x->parent;
     275      537140 :     if (x->parent)
     276             :     {
     277      536240 :         if (x == x->parent->left)
     278      164586 :             x->parent->left = y;
     279             :         else
     280      371654 :             x->parent->right = y;
     281             :     }
     282             :     else
     283             :     {
     284         900 :         rbt->root = y;
     285             :     }
     286             : 
     287             :     /* link x and y */
     288      537140 :     y->left = x;
     289      537140 :     if (x != RBTNIL)
     290      537140 :         x->parent = y;
     291      537140 : }
     292             : 
     293             : /*
     294             :  * Rotate node x to right.
     295             :  *
     296             :  * x's left right child takes its place in the tree, and x becomes the right
     297             :  * child of that node.
     298             :  */
     299             : static void
     300      141362 : rbt_rotate_right(RBTree *rbt, RBTNode *x)
     301             : {
     302      141362 :     RBTNode    *y = x->left;
     303             : 
     304             :     /* establish x->left link */
     305      141362 :     x->left = y->right;
     306      141362 :     if (y->right != RBTNIL)
     307       45336 :         y->right->parent = x;
     308             : 
     309             :     /* establish y->parent link */
     310      141362 :     if (y != RBTNIL)
     311      141362 :         y->parent = x->parent;
     312      141362 :     if (x->parent)
     313             :     {
     314      141248 :         if (x == x->parent->right)
     315      124878 :             x->parent->right = y;
     316             :         else
     317       16370 :             x->parent->left = y;
     318             :     }
     319             :     else
     320             :     {
     321         114 :         rbt->root = y;
     322             :     }
     323             : 
     324             :     /* link x and y */
     325      141362 :     y->right = x;
     326      141362 :     if (x != RBTNIL)
     327      141362 :         x->parent = y;
     328      141362 : }
     329             : 
     330             : /*
     331             :  * Maintain Red-Black tree balance after inserting node x.
     332             :  *
     333             :  * The newly inserted node is always initially marked red.  That may lead to
     334             :  * a situation where a red node has a red child, which is prohibited.  We can
     335             :  * always fix the problem by a series of color changes and/or "rotations",
     336             :  * which move the problem progressively higher up in the tree.  If one of the
     337             :  * two red nodes is the root, we can always fix the problem by changing the
     338             :  * root from red to black.
     339             :  *
     340             :  * (This does not work lower down in the tree because we must also maintain
     341             :  * the invariant that every leaf has equal black-height.)
     342             :  */
     343             : static void
     344      635230 : rbt_insert_fixup(RBTree *rbt, RBTNode *x)
     345             : {
     346             :     /*
     347             :      * x is always a red node.  Initially, it is the newly inserted node. Each
     348             :      * iteration of this loop moves it higher up in the tree.
     349             :      */
     350     1732588 :     while (x != rbt->root && x->parent->color == RBTRED)
     351             :     {
     352             :         /*
     353             :          * x and x->parent are both red.  Fix depends on whether x->parent is
     354             :          * a left or right child.  In either case, we define y to be the
     355             :          * "uncle" of x, that is, the other child of x's grandparent.
     356             :          *
     357             :          * If the uncle is red, we flip the grandparent to red and its two
     358             :          * children to black.  Then we loop around again to check whether the
     359             :          * grandparent still has a problem.
     360             :          *
     361             :          * If the uncle is black, we will perform one or two "rotations" to
     362             :          * balance the tree.  Either x or x->parent will take the
     363             :          * grandparent's position in the tree and recolored black, and the
     364             :          * original grandparent will be recolored red and become a child of
     365             :          * that node. This always leaves us with a valid red-black tree, so
     366             :          * the loop will terminate.
     367             :          */
     368     1097358 :         if (x->parent == x->parent->parent->left)
     369             :         {
     370      160694 :             RBTNode    *y = x->parent->parent->right;
     371             : 
     372      160694 :             if (y->color == RBTRED)
     373             :             {
     374             :                 /* uncle is RBTRED */
     375       38726 :                 x->parent->color = RBTBLACK;
     376       38726 :                 y->color = RBTBLACK;
     377       38726 :                 x->parent->parent->color = RBTRED;
     378             : 
     379       38726 :                 x = x->parent->parent;
     380             :             }
     381             :             else
     382             :             {
     383             :                 /* uncle is RBTBLACK */
     384      121968 :                 if (x == x->parent->right)
     385             :                 {
     386             :                     /* make x a left child */
     387      107556 :                     x = x->parent;
     388      107556 :                     rbt_rotate_left(rbt, x);
     389             :                 }
     390             : 
     391             :                 /* recolor and rotate */
     392      121968 :                 x->parent->color = RBTBLACK;
     393      121968 :                 x->parent->parent->color = RBTRED;
     394             : 
     395      121968 :                 rbt_rotate_right(rbt, x->parent->parent);
     396             :             }
     397             :         }
     398             :         else
     399             :         {
     400             :             /* mirror image of above code */
     401      936664 :             RBTNode    *y = x->parent->parent->left;
     402             : 
     403      936664 :             if (y->color == RBTRED)
     404             :             {
     405             :                 /* uncle is RBTRED */
     406      519346 :                 x->parent->color = RBTBLACK;
     407      519346 :                 y->color = RBTBLACK;
     408      519346 :                 x->parent->parent->color = RBTRED;
     409             : 
     410      519346 :                 x = x->parent->parent;
     411             :             }
     412             :             else
     413             :             {
     414             :                 /* uncle is RBTBLACK */
     415      417318 :                 if (x == x->parent->left)
     416             :                 {
     417       14856 :                     x = x->parent;
     418       14856 :                     rbt_rotate_right(rbt, x);
     419             :                 }
     420      417318 :                 x->parent->color = RBTBLACK;
     421      417318 :                 x->parent->parent->color = RBTRED;
     422             : 
     423      417318 :                 rbt_rotate_left(rbt, x->parent->parent);
     424             :             }
     425             :         }
     426             :     }
     427             : 
     428             :     /*
     429             :      * The root may already have been black; if not, the black-height of every
     430             :      * node in the tree increases by one.
     431             :      */
     432      635230 :     rbt->root->color = RBTBLACK;
     433      635230 : }
     434             : 
     435             : /*
     436             :  * rbt_insert: insert a new value into the tree.
     437             :  *
     438             :  * data represents the value to insert.  Its RBTNode fields need not
     439             :  * be valid, it's the extra data in the larger struct that is of interest.
     440             :  *
     441             :  * If the value represented by "data" is not present in the tree, then
     442             :  * we copy "data" into a new tree entry and return that node, setting *isNew
     443             :  * to true.
     444             :  *
     445             :  * If the value represented by "data" is already present, then we call the
     446             :  * combiner function to merge data into the existing node, and return the
     447             :  * existing node, setting *isNew to false.
     448             :  *
     449             :  * "data" is unmodified in either case; it's typically just a local
     450             :  * variable in the caller.
     451             :  */
     452             : RBTNode *
     453     2642562 : rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
     454             : {
     455             :     RBTNode    *current,
     456             :                *parent,
     457             :                *x;
     458             :     int         cmp;
     459             : 
     460             :     /* find where node belongs */
     461     2642562 :     current = rbt->root;
     462     2642562 :     parent = NULL;
     463     2642562 :     cmp = 0;                    /* just to prevent compiler warning */
     464             : 
     465    27536366 :     while (current != RBTNIL)
     466             :     {
     467    26901136 :         cmp = rbt->comparator(data, current, rbt->arg);
     468    26901136 :         if (cmp == 0)
     469             :         {
     470             :             /*
     471             :              * Found node with given key.  Apply combiner.
     472             :              */
     473     2007332 :             rbt->combiner(current, data, rbt->arg);
     474     2007332 :             *isNew = false;
     475     2007332 :             return current;
     476             :         }
     477    24893804 :         parent = current;
     478    24893804 :         current = (cmp < 0) ? current->left : current->right;
     479             :     }
     480             : 
     481             :     /*
     482             :      * Value is not present, so create a new node containing data.
     483             :      */
     484      635230 :     *isNew = true;
     485             : 
     486      635230 :     x = rbt->allocfunc(rbt->arg);
     487             : 
     488      635230 :     x->color = RBTRED;
     489             : 
     490      635230 :     x->left = RBTNIL;
     491      635230 :     x->right = RBTNIL;
     492      635230 :     x->parent = parent;
     493      635230 :     rbt_copy_data(rbt, x, data);
     494             : 
     495             :     /* insert node in tree */
     496      635230 :     if (parent)
     497             :     {
     498      634918 :         if (cmp < 0)
     499      137028 :             parent->left = x;
     500             :         else
     501      497890 :             parent->right = x;
     502             :     }
     503             :     else
     504             :     {
     505         312 :         rbt->root = x;
     506             :     }
     507             : 
     508      635230 :     rbt_insert_fixup(rbt, x);
     509             : 
     510      635230 :     return x;
     511             : }
     512             : 
     513             : /**********************************************************************
     514             :  *                          Deletion                                  *
     515             :  **********************************************************************/
     516             : 
     517             : /*
     518             :  * Maintain Red-Black tree balance after deleting a black node.
     519             :  */
     520             : static void
     521       25928 : rbt_delete_fixup(RBTree *rbt, RBTNode *x)
     522             : {
     523             :     /*
     524             :      * x is always a black node.  Initially, it is the former child of the
     525             :      * deleted node.  Each iteration of this loop moves it higher up in the
     526             :      * tree.
     527             :      */
     528       48260 :     while (x != rbt->root && x->color == RBTBLACK)
     529             :     {
     530             :         /*
     531             :          * Left and right cases are symmetric.  Any nodes that are children of
     532             :          * x have a black-height one less than the remainder of the nodes in
     533             :          * the tree.  We rotate and recolor nodes to move the problem up the
     534             :          * tree: at some stage we'll either fix the problem, or reach the root
     535             :          * (where the black-height is allowed to decrease).
     536             :          */
     537       22332 :         if (x == x->parent->left)
     538             :         {
     539       18994 :             RBTNode    *w = x->parent->right;
     540             : 
     541       18994 :             if (w->color == RBTRED)
     542             :             {
     543        4536 :                 w->color = RBTBLACK;
     544        4536 :                 x->parent->color = RBTRED;
     545             : 
     546        4536 :                 rbt_rotate_left(rbt, x->parent);
     547        4536 :                 w = x->parent->right;
     548             :             }
     549             : 
     550       18994 :             if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
     551             :             {
     552       11842 :                 w->color = RBTRED;
     553             : 
     554       11842 :                 x = x->parent;
     555             :             }
     556             :             else
     557             :             {
     558        7152 :                 if (w->right->color == RBTBLACK)
     559             :                 {
     560        2534 :                     w->left->color = RBTBLACK;
     561        2534 :                     w->color = RBTRED;
     562             : 
     563        2534 :                     rbt_rotate_right(rbt, w);
     564        2534 :                     w = x->parent->right;
     565             :                 }
     566        7152 :                 w->color = x->parent->color;
     567        7152 :                 x->parent->color = RBTBLACK;
     568        7152 :                 w->right->color = RBTBLACK;
     569             : 
     570        7152 :                 rbt_rotate_left(rbt, x->parent);
     571        7152 :                 x = rbt->root;   /* Arrange for loop to terminate. */
     572             :             }
     573             :         }
     574             :         else
     575             :         {
     576        3338 :             RBTNode    *w = x->parent->left;
     577             : 
     578        3338 :             if (w->color == RBTRED)
     579             :             {
     580         380 :                 w->color = RBTBLACK;
     581         380 :                 x->parent->color = RBTRED;
     582             : 
     583         380 :                 rbt_rotate_right(rbt, x->parent);
     584         380 :                 w = x->parent->left;
     585             :             }
     586             : 
     587        3338 :             if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
     588             :             {
     589        1714 :                 w->color = RBTRED;
     590             : 
     591        1714 :                 x = x->parent;
     592             :             }
     593             :             else
     594             :             {
     595        1624 :                 if (w->left->color == RBTBLACK)
     596             :                 {
     597         578 :                     w->right->color = RBTBLACK;
     598         578 :                     w->color = RBTRED;
     599             : 
     600         578 :                     rbt_rotate_left(rbt, w);
     601         578 :                     w = x->parent->left;
     602             :                 }
     603        1624 :                 w->color = x->parent->color;
     604        1624 :                 x->parent->color = RBTBLACK;
     605        1624 :                 w->left->color = RBTBLACK;
     606             : 
     607        1624 :                 rbt_rotate_right(rbt, x->parent);
     608        1624 :                 x = rbt->root;   /* Arrange for loop to terminate. */
     609             :             }
     610             :         }
     611             :     }
     612       25928 :     x->color = RBTBLACK;
     613       25928 : }
     614             : 
     615             : /*
     616             :  * Delete node z from tree.
     617             :  */
     618             : static void
     619       30152 : rbt_delete_node(RBTree *rbt, RBTNode *z)
     620             : {
     621             :     RBTNode    *x,
     622             :                *y;
     623             : 
     624             :     /* This is just paranoia: we should only get called on a valid node */
     625       30152 :     if (!z || z == RBTNIL)
     626           0 :         return;
     627             : 
     628             :     /*
     629             :      * y is the node that will actually be removed from the tree.  This will
     630             :      * be z if z has fewer than two children, or the tree successor of z
     631             :      * otherwise.
     632             :      */
     633       30152 :     if (z->left == RBTNIL || z->right == RBTNIL)
     634             :     {
     635             :         /* y has a RBTNIL node as a child */
     636       25128 :         y = z;
     637             :     }
     638             :     else
     639             :     {
     640             :         /* find tree successor */
     641        5024 :         y = z->right;
     642       10506 :         while (y->left != RBTNIL)
     643        5482 :             y = y->left;
     644             :     }
     645             : 
     646             :     /* x is y's only child */
     647       30152 :     if (y->left != RBTNIL)
     648        1294 :         x = y->left;
     649             :     else
     650       28858 :         x = y->right;
     651             : 
     652             :     /* Remove y from the tree. */
     653       30152 :     x->parent = y->parent;
     654       30152 :     if (y->parent)
     655             :     {
     656       30148 :         if (y == y->parent->left)
     657       24256 :             y->parent->left = x;
     658             :         else
     659        5892 :             y->parent->right = x;
     660             :     }
     661             :     else
     662             :     {
     663           4 :         rbt->root = x;
     664             :     }
     665             : 
     666             :     /*
     667             :      * If we removed the tree successor of z rather than z itself, then move
     668             :      * the data for the removed node to the one we were supposed to remove.
     669             :      */
     670       30152 :     if (y != z)
     671        5024 :         rbt_copy_data(rbt, z, y);
     672             : 
     673             :     /*
     674             :      * Removing a black node might make some paths from root to leaf contain
     675             :      * fewer black nodes than others, or it might make two red nodes adjacent.
     676             :      */
     677       30152 :     if (y->color == RBTBLACK)
     678       25928 :         rbt_delete_fixup(rbt, x);
     679             : 
     680             :     /* Now we can recycle the y node */
     681       30152 :     if (rbt->freefunc)
     682       30152 :         rbt->freefunc(y, rbt->arg);
     683             : }
     684             : 
     685             : /*
     686             :  * rbt_delete: remove the given tree entry
     687             :  *
     688             :  * "node" must have previously been found via rbt_find or rbt_leftmost.
     689             :  * It is caller's responsibility to free any subsidiary data attached
     690             :  * to the node before calling rbt_delete.  (Do *not* try to push that
     691             :  * responsibility off to the freefunc, as some other physical node
     692             :  * may be the one actually freed!)
     693             :  */
     694             : void
     695       30152 : rbt_delete(RBTree *rbt, RBTNode *node)
     696             : {
     697       30152 :     rbt_delete_node(rbt, node);
     698       30152 : }
     699             : 
     700             : /**********************************************************************
     701             :  *                        Traverse                                    *
     702             :  **********************************************************************/
     703             : 
     704             : static RBTNode *
     705      535532 : rbt_left_right_iterator(RBTreeIterator *iter)
     706             : {
     707      535532 :     if (iter->last_visited == NULL)
     708             :     {
     709         302 :         iter->last_visited = iter->rbt->root;
     710        1766 :         while (iter->last_visited->left != RBTNIL)
     711        1464 :             iter->last_visited = iter->last_visited->left;
     712             : 
     713         302 :         return iter->last_visited;
     714             :     }
     715             : 
     716      535230 :     if (iter->last_visited->right != RBTNIL)
     717             :     {
     718      267654 :         iter->last_visited = iter->last_visited->right;
     719      533464 :         while (iter->last_visited->left != RBTNIL)
     720      265810 :             iter->last_visited = iter->last_visited->left;
     721             : 
     722      267654 :         return iter->last_visited;
     723             :     }
     724             : 
     725             :     for (;;)
     726      267654 :     {
     727      535230 :         RBTNode    *came_from = iter->last_visited;
     728             : 
     729      535230 :         iter->last_visited = iter->last_visited->parent;
     730      535230 :         if (iter->last_visited == NULL)
     731             :         {
     732         302 :             iter->is_over = true;
     733         302 :             break;
     734             :         }
     735             : 
     736      534928 :         if (iter->last_visited->left == came_from)
     737      267274 :             break;              /* came from left sub-tree, return current
     738             :                                  * node */
     739             : 
     740             :         /* else - came from right sub-tree, continue to move up */
     741             :     }
     742             : 
     743      267576 :     return iter->last_visited;
     744             : }
     745             : 
     746             : static RBTNode *
     747       20002 : rbt_right_left_iterator(RBTreeIterator *iter)
     748             : {
     749       20002 :     if (iter->last_visited == NULL)
     750             :     {
     751           2 :         iter->last_visited = iter->rbt->root;
     752          28 :         while (iter->last_visited->right != RBTNIL)
     753          26 :             iter->last_visited = iter->last_visited->right;
     754             : 
     755           2 :         return iter->last_visited;
     756             :     }
     757             : 
     758       20000 :     if (iter->last_visited->left != RBTNIL)
     759             :     {
     760       10046 :         iter->last_visited = iter->last_visited->left;
     761       19972 :         while (iter->last_visited->right != RBTNIL)
     762        9926 :             iter->last_visited = iter->last_visited->right;
     763             : 
     764       10046 :         return iter->last_visited;
     765             :     }
     766             : 
     767             :     for (;;)
     768       10046 :     {
     769       20000 :         RBTNode    *came_from = iter->last_visited;
     770             : 
     771       20000 :         iter->last_visited = iter->last_visited->parent;
     772       20000 :         if (iter->last_visited == NULL)
     773             :         {
     774           2 :             iter->is_over = true;
     775           2 :             break;
     776             :         }
     777             : 
     778       19998 :         if (iter->last_visited->right == came_from)
     779        9952 :             break;              /* came from right sub-tree, return current
     780             :                                  * node */
     781             : 
     782             :         /* else - came from left sub-tree, continue to move up */
     783             :     }
     784             : 
     785        9954 :     return iter->last_visited;
     786             : }
     787             : 
     788             : /*
     789             :  * rbt_begin_iterate: prepare to traverse the tree in any of several orders
     790             :  *
     791             :  * After calling rbt_begin_iterate, call rbt_iterate repeatedly until it
     792             :  * returns NULL or the traversal stops being of interest.
     793             :  *
     794             :  * If the tree is changed during traversal, results of further calls to
     795             :  * rbt_iterate are unspecified.  Multiple concurrent iterators on the same
     796             :  * tree are allowed.
     797             :  *
     798             :  * The iterator state is stored in the 'iter' struct.  The caller should
     799             :  * treat it as an opaque struct.
     800             :  */
     801             : void
     802         352 : rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
     803             : {
     804             :     /* Common initialization for all traversal orders */
     805         352 :     iter->rbt = rbt;
     806         352 :     iter->last_visited = NULL;
     807         352 :     iter->is_over = (rbt->root == RBTNIL);
     808             : 
     809         352 :     switch (ctrl)
     810             :     {
     811         348 :         case LeftRightWalk:     /* visit left, then self, then right */
     812         348 :             iter->iterate = rbt_left_right_iterator;
     813         348 :             break;
     814           4 :         case RightLeftWalk:     /* visit right, then self, then left */
     815           4 :             iter->iterate = rbt_right_left_iterator;
     816           4 :             break;
     817           0 :         default:
     818           0 :             elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
     819             :     }
     820         352 : }
     821             : 
     822             : /*
     823             :  * rbt_iterate: return the next node in traversal order, or NULL if no more
     824             :  */
     825             : RBTNode *
     826      555582 : rbt_iterate(RBTreeIterator *iter)
     827             : {
     828      555582 :     if (iter->is_over)
     829          48 :         return NULL;
     830             : 
     831      555534 :     return iter->iterate(iter);
     832             : }

Generated by: LCOV version 1.14