"Fossies" - the Fresh Open Source Software Archive

Member "inotify-tools-3.20.11.0/libinotifytools/src/redblack.c" (13 Nov 2020, 24509 Bytes) of package /linux/privat/inotify-tools-3.20.11.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "redblack.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.20.2.2_vs_3.20.11.0.

    1 /*
    2    Redblack balanced tree algorithm
    3    Copyright (C) Damian Ivereigh 2000
    4 
    5    This program is free software; you can redistribute it and/or modify
    6    it under the terms of the GNU Lesser General Public License as published by
    7    the Free Software Foundation; either version 2.1 of the License, or
    8    (at your option) any later version. See the file COPYING for details.
    9 
   10    This program is distributed in the hope that it will be useful,
   11    but WITHOUT ANY WARRANTY; without even the implied warranty of
   12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   13    GNU General Public License for more details.
   14 
   15    You should have received a copy of the GNU Lesser General Public License
   16    along with this program; if not, write to the Free Software
   17    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   18  */
   19 
   20 /* Implement the red/black tree structure. It is designed to emulate
   21 ** the standard tsearch() stuff. i.e. the calling conventions are
   22 ** exactly the same
   23 */
   24 
   25 #include <stddef.h>
   26 #include <stdlib.h>
   27 #include <unistd.h>
   28 #include "redblack.h"
   29 
   30 #define assert(expr)
   31 
   32 /* Uncomment this if you would rather use a raw sbrk to get memory
   33 ** (however the memory is never released again (only re-used). Can't
   34 ** see any point in using this these days.
   35 */
   36 /* #define USE_SBRK */
   37 
   38 enum nodecolour { BLACK, RED };
   39 
   40 struct RB_ENTRY(node)
   41 {
   42     struct RB_ENTRY(node) *left;        /* Left down */
   43     struct RB_ENTRY(node) *right;       /* Right down */
   44     struct RB_ENTRY(node) *up;      /* Up */
   45     enum nodecolour colour;     /* Node colour */
   46 #ifdef RB_INLINE
   47     RB_ENTRY(data_t) key;       /* User's key (and data) */
   48 #define RB_GET(x,y)     &x->y
   49 #define RB_SET(x,y,v)       x->y = *(v)
   50 #else
   51     const RB_ENTRY(data_t) *key;    /* Pointer to user's key (and data) */
   52 #define RB_GET(x,y)     x->y
   53 #define RB_SET(x,y,v)       x->y = v
   54 #endif /* RB_INLINE */
   55 };
   56 
   57 /* Dummy (sentinel) node, so that we can make X->left->up = X
   58 ** We then use this instead of NULL to mean the top or bottom
   59 ** end of the rb tree. It is a black node.
   60 **
   61 ** Initialization of the last field in this initializer is left implicit
   62 ** because it could be of any type.  We count on the compiler to zero it.
   63 */
   64 struct RB_ENTRY(node) RB_ENTRY(_null)={&RB_ENTRY(_null), &RB_ENTRY(_null), &RB_ENTRY(_null), BLACK};
   65 #define RBNULL (&RB_ENTRY(_null))
   66 
   67 #if defined(USE_SBRK)
   68 
   69 static struct RB_ENTRY(node) *RB_ENTRY(_alloc)();
   70 static void RB_ENTRY(_free)(struct RB_ENTRY(node) *);
   71 
   72 #else
   73 
   74 static struct RB_ENTRY(node) *RB_ENTRY(_alloc)() {return (struct RB_ENTRY(node) *) malloc(sizeof(struct RB_ENTRY(node)));}
   75 static void RB_ENTRY(_free)(struct RB_ENTRY(node) *x) {free(x);}
   76 
   77 #endif
   78 
   79 /* These functions are always needed */
   80 static void RB_ENTRY(_left_rotate)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *);
   81 static void RB_ENTRY(_right_rotate)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *);
   82 static struct RB_ENTRY(node) *RB_ENTRY(_successor)(const struct RB_ENTRY(node) *);
   83 static struct RB_ENTRY(node) *RB_ENTRY(_predecessor)(const struct RB_ENTRY(node) *);
   84 static struct RB_ENTRY(node) *RB_ENTRY(_traverse)(int, const RB_ENTRY(data_t) * , struct RB_ENTRY(tree) *);
   85 
   86 /* These functions may not be needed */
   87 #ifndef no_lookup
   88 static struct RB_ENTRY(node) *RB_ENTRY(_lookup)(int, const RB_ENTRY(data_t) * , struct RB_ENTRY(tree) *);
   89 #endif
   90 
   91 #ifndef no_destroy
   92 static void RB_ENTRY(_destroy)(struct RB_ENTRY(node) *);
   93 #endif
   94 
   95 #ifndef no_delete
   96 static void RB_ENTRY(_delete)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *);
   97 static void RB_ENTRY(_delete_fix)(struct RB_ENTRY(node) **, struct RB_ENTRY(node) *);
   98 #endif
   99 
  100 #ifndef no_walk
  101 static void RB_ENTRY(_walk)(const struct RB_ENTRY(node) *, void (*)(const RB_ENTRY(data_t) *, const VISIT, const int, void *), void *, int);
  102 #endif
  103 
  104 #ifndef no_readlist
  105 static RBLIST *RB_ENTRY(_openlist)(const struct RB_ENTRY(node) *);
  106 static const RB_ENTRY(data_t) * RB_ENTRY(_readlist)(RBLIST *);
  107 static void RB_ENTRY(_closelist)(RBLIST *);
  108 #endif
  109 
  110 /*
  111 ** OK here we go, the balanced tree stuff. The algorithm is the
  112 ** fairly standard red/black taken from "Introduction to Algorithms"
  113 ** by Cormen, Leiserson & Rivest. Maybe one of these days I will
  114 ** fully understand all this stuff.
  115 **
  116 ** Basically a red/black balanced tree has the following properties:-
  117 ** 1) Every node is either red or black (colour is RED or BLACK)
  118 ** 2) A leaf (RBNULL pointer) is considered black
  119 ** 3) If a node is red then its children are black
  120 ** 4) Every path from a node to a leaf contains the same no
  121 **    of black nodes
  122 **
  123 ** 3) & 4) above guarantee that the longest path (alternating
  124 ** red and black nodes) is only twice as long as the shortest
  125 ** path (all black nodes). Thus the tree remains fairly balanced.
  126 */
  127 
  128 /*
  129  * Initialise a tree. Identifies the comparison routine and any config
  130  * data that must be sent to it when called.
  131  * Returns a pointer to the top of the tree.
  132  */
  133 #ifndef RB_CUSTOMIZE
  134 RB_STATIC struct RB_ENTRY(tree) *
  135 rbinit(int (*cmp)(const void *, const void *, const void *), const void *config)
  136 #else
  137 RB_STATIC struct RB_ENTRY(tree) *RB_ENTRY(init)(void)
  138 #endif /* RB_CUSTOMIZE */
  139 {
  140     struct RB_ENTRY(tree) *retval;
  141 
  142     if ((retval=(struct RB_ENTRY(tree) *) malloc(sizeof(struct RB_ENTRY(tree))))==NULL)
  143         return(NULL);
  144     
  145 #ifndef RB_CUSTOMIZE
  146     retval->rb_cmp=cmp;
  147     retval->rb_config=config;
  148 #endif /* RB_CUSTOMIZE */
  149     retval->rb_root=RBNULL;
  150 
  151     return(retval);
  152 }
  153 
  154 #ifndef no_destroy
  155 RB_STATIC void
  156 RB_ENTRY(destroy)(struct RB_ENTRY(tree) *rbinfo)
  157 {
  158     if (rbinfo==NULL)
  159         return;
  160 
  161     if (rbinfo->rb_root!=RBNULL)
  162         RB_ENTRY(_destroy)(rbinfo->rb_root);
  163     
  164     free(rbinfo);
  165 }
  166 #endif /* no_destroy */
  167 
  168 #ifndef no_search
  169 RB_STATIC const RB_ENTRY(data_t) *
  170 RB_ENTRY(search)(const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo)
  171 {
  172     struct RB_ENTRY(node) *x;
  173 
  174     if (rbinfo==NULL)
  175         return(NULL);
  176 
  177     x=RB_ENTRY(_traverse)(1, key, rbinfo);
  178 
  179     return((x==RBNULL) ? NULL : RB_GET(x, key));
  180 }
  181 #endif /* no_search */
  182 
  183 #ifndef no_find
  184 RB_STATIC const RB_ENTRY(data_t) * 
  185 RB_ENTRY(find)(const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo)
  186 {
  187     struct RB_ENTRY(node) *x;
  188 
  189     if (rbinfo==NULL)
  190         return(NULL);
  191 
  192     /* If we have a NULL root (empty tree) then just return */
  193     if (rbinfo->rb_root==RBNULL)
  194         return(NULL);
  195 
  196     x=RB_ENTRY(_traverse)(0, key, rbinfo);
  197 
  198     return((x==RBNULL) ? NULL : RB_GET(x, key));
  199 }
  200 #endif /* no_find */
  201 
  202 #ifndef no_delete
  203 RB_STATIC const RB_ENTRY(data_t) * 
  204 RB_ENTRY(delete)(const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo)
  205 {
  206     struct RB_ENTRY(node) *x;
  207     const RB_ENTRY(data_t) * y;
  208 
  209     if (rbinfo==NULL)
  210         return(NULL);
  211 
  212     x=RB_ENTRY(_traverse)(0, key, rbinfo);
  213 
  214     if (x==RBNULL)
  215     {
  216         return(NULL);
  217     }
  218     else
  219     {
  220         y=RB_GET(x, key);
  221         RB_ENTRY(_delete)(&rbinfo->rb_root, x);
  222 
  223         return(y);
  224     }
  225 }
  226 #endif /* no_delete */
  227 
  228 #ifndef no_walk
  229 RB_STATIC void
  230 RB_ENTRY(walk)(const struct RB_ENTRY(tree) *rbinfo, void (*action)(const RB_ENTRY(data_t) *, const VISIT, const int, void *), void *arg)
  231 {
  232     if (rbinfo==NULL)
  233         return;
  234 
  235     RB_ENTRY(_walk)(rbinfo->rb_root, action, arg, 0);
  236 }
  237 #endif /* no_walk */
  238 
  239 #ifndef no_readlist
  240 RB_STATIC RBLIST *
  241 RB_ENTRY(openlist)(const struct RB_ENTRY(tree) *rbinfo)
  242 {
  243     if (rbinfo==NULL)
  244         return(NULL);
  245 
  246     return(RB_ENTRY(_openlist)(rbinfo->rb_root));
  247 }
  248 
  249 RB_STATIC const RB_ENTRY(data_t) * 
  250 RB_ENTRY(readlist)(RBLIST *rblistp)
  251 {
  252     if (rblistp==NULL)
  253         return(NULL);
  254 
  255     return(RB_ENTRY(_readlist)(rblistp));
  256 }
  257 
  258 RB_STATIC void
  259 RB_ENTRY(closelist)(RBLIST *rblistp)
  260 {
  261     if (rblistp==NULL)
  262         return;
  263 
  264     RB_ENTRY(_closelist)(rblistp);
  265 }
  266 #endif /* no_readlist */
  267 
  268 #ifndef no_lookup
  269 RB_STATIC const RB_ENTRY(data_t) * 
  270 RB_ENTRY(lookup)(int mode, const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo)
  271 {
  272     struct RB_ENTRY(node) *x;
  273 
  274     /* If we have a NULL root (empty tree) then just return NULL */
  275     if (rbinfo==NULL || rbinfo->rb_root==NULL)
  276         return(NULL);
  277 
  278     x=RB_ENTRY(_lookup)(mode, key, rbinfo);
  279 
  280     return((x==RBNULL) ? NULL : RB_GET(x, key));
  281 }
  282 #endif /* no_lookup */
  283 
  284 /* --------------------------------------------------------------------- */
  285 
  286 /* Search for and if not found and insert is true, will add a new
  287 ** node in. Returns a pointer to the new node, or the node found
  288 */
  289 static struct RB_ENTRY(node) *
  290 RB_ENTRY(_traverse)(int insert, const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo)
  291 {
  292     struct RB_ENTRY(node) *x,*y,*z;
  293     int cmp;
  294     int found=0;
  295 
  296     y=RBNULL; /* points to the parent of x */
  297     x=rbinfo->rb_root;
  298 
  299     /* walk x down the tree */
  300     while(x!=RBNULL && found==0)
  301     {
  302         y=x;
  303         /* printf("key=%s, RB_GET(x, key)=%s\n", key, RB_GET(x, key)); */
  304 #ifndef RB_CUSTOMIZE
  305         cmp=RB_CMP(key, RB_GET(x, key), rbinfo->rb_config);
  306 #else
  307         cmp=RB_CMP(key, RB_GET(x, key));
  308 #endif /* RB_CUSTOMIZE */
  309 
  310         if (cmp<0)
  311             x=x->left;
  312         else if (cmp>0)
  313             x=x->right;
  314         else
  315             found=1;
  316     }
  317 
  318     if (found || !insert)
  319         return(x);
  320 
  321     if ((z=RB_ENTRY(_alloc)())==NULL)
  322     {
  323         /* Whoops, no memory */
  324         return(RBNULL);
  325     }
  326 
  327     RB_SET(z, key, key);
  328     z->up=y;
  329     if (y==RBNULL)
  330     {
  331         rbinfo->rb_root=z;
  332     }
  333     else
  334     {
  335 #ifndef RB_CUSTOMIZE
  336         cmp=RB_CMP(RB_GET(z, key), RB_GET(y, key), rbinfo->rb_config);
  337 #else
  338         cmp=RB_CMP(RB_GET(z, key), RB_GET(y, key));
  339 #endif /* RB_CUSTOMIZE */
  340         if (cmp<0)
  341             y->left=z;
  342         else
  343             y->right=z;
  344     }
  345 
  346     z->left=RBNULL;
  347     z->right=RBNULL;
  348 
  349     /* colour this new node red */
  350     z->colour=RED;
  351 
  352     /* Having added a red node, we must now walk back up the tree balancing
  353     ** it, by a series of rotations and changing of colours
  354     */
  355     x=z;
  356 
  357     /* While we are not at the top and our parent node is red
  358     ** N.B. Since the root node is guaranteed black, then we
  359     ** are also going to stop if we are the child of the root
  360     */
  361 
  362     while(x != rbinfo->rb_root && (x->up->colour == RED))
  363     {
  364         /* if our parent is on the left side of our grandparent */
  365         if (x->up == x->up->up->left)
  366         {
  367             /* get the right side of our grandparent (uncle?) */
  368             y=x->up->up->right;
  369             if (y->colour == RED)
  370             {
  371                 /* make our parent black */
  372                 x->up->colour = BLACK;
  373                 /* make our uncle black */
  374                 y->colour = BLACK;
  375                 /* make our grandparent red */
  376                 x->up->up->colour = RED;
  377 
  378                 /* now consider our grandparent */
  379                 x=x->up->up;
  380             }
  381             else
  382             {
  383                 /* if we are on the right side of our parent */
  384                 if (x == x->up->right)
  385                 {
  386                     /* Move up to our parent */
  387                     x=x->up;
  388                     RB_ENTRY(_left_rotate)(&rbinfo->rb_root, x);
  389                 }
  390 
  391                 /* make our parent black */
  392                 x->up->colour = BLACK;
  393                 /* make our grandparent red */
  394                 x->up->up->colour = RED;
  395                 /* right rotate our grandparent */
  396                 RB_ENTRY(_right_rotate)(&rbinfo->rb_root, x->up->up);
  397             }
  398         }
  399         else
  400         {
  401             /* everything here is the same as above, but
  402             ** exchanging left for right
  403             */
  404 
  405             y=x->up->up->left;
  406             if (y->colour == RED)
  407             {
  408                 x->up->colour = BLACK;
  409                 y->colour = BLACK;
  410                 x->up->up->colour = RED;
  411 
  412                 x=x->up->up;
  413             }
  414             else
  415             {
  416                 if (x == x->up->left)
  417                 {
  418                     x=x->up;
  419                     RB_ENTRY(_right_rotate)(&rbinfo->rb_root, x);
  420                 }
  421 
  422                 x->up->colour = BLACK;
  423                 x->up->up->colour = RED;
  424                 RB_ENTRY(_left_rotate)(&rbinfo->rb_root, x->up->up);
  425             }
  426         }
  427     }
  428 
  429     /* Set the root node black */
  430     (rbinfo->rb_root)->colour = BLACK;
  431 
  432     return(z);
  433 }
  434 
  435 #ifndef no_lookup
  436 /* Search for a key according to mode (see redblack.h)
  437 */
  438 static struct RB_ENTRY(node) *
  439 RB_ENTRY(_lookup)(int mode, const RB_ENTRY(data_t) *key, struct RB_ENTRY(tree) *rbinfo)
  440 {
  441     struct RB_ENTRY(node) *x,*y;
  442     int cmp=0;
  443     int found=0;
  444 
  445     y=RBNULL; /* points to the parent of x */
  446     x=rbinfo->rb_root;
  447 
  448     if (mode==RB_LUFIRST)
  449     {
  450         /* Keep going left until we hit a NULL */
  451         while(x!=RBNULL)
  452         {
  453             y=x;
  454             x=x->left;
  455         }
  456 
  457         return(y);
  458     }
  459     else if (mode==RB_LULAST)
  460     {
  461         /* Keep going right until we hit a NULL */
  462         while(x!=RBNULL)
  463         {
  464             y=x;
  465             x=x->right;
  466         }
  467 
  468         return(y);
  469     }
  470 
  471     /* walk x down the tree */
  472     while(x!=RBNULL && found==0)
  473     {
  474         y=x;
  475         /* printf("key=%s, RB_GET(x, key)=%s\n", key, RB_GET(x, key)); */
  476 #ifndef RB_CUSTOMIZE
  477         cmp=RB_CMP(key, RB_GET(x, key), rbinfo->rb_config);
  478 #else
  479         cmp=RB_CMP(key, RB_GET(x, key));
  480 #endif /* RB_CUSTOMIZE */
  481 
  482 
  483         if (cmp<0)
  484             x=x->left;
  485         else if (cmp>0)
  486             x=x->right;
  487         else
  488             found=1;
  489     }
  490 
  491     if (found && (mode==RB_LUEQUAL || mode==RB_LUGTEQ || mode==RB_LULTEQ))
  492         return(x);
  493     
  494     if (!found && (mode==RB_LUEQUAL || mode==RB_LUNEXT || mode==RB_LUPREV))
  495         return(RBNULL);
  496     
  497     if (mode==RB_LUGTEQ || (!found && mode==RB_LUGREAT))
  498     {
  499         if (cmp>0)
  500             return(RB_ENTRY(_successor)(y));
  501         else
  502             return(y);
  503     }
  504 
  505     if (mode==RB_LULTEQ || (!found && mode==RB_LULESS))
  506     {
  507         if (cmp<0)
  508             return(RB_ENTRY(_predecessor)(y));
  509         else
  510             return(y);
  511     }
  512 
  513     if (mode==RB_LUNEXT || (found && mode==RB_LUGREAT))
  514         return(RB_ENTRY(_successor)(x));
  515 
  516     if (mode==RB_LUPREV || (found && mode==RB_LULESS))
  517         return(RB_ENTRY(_predecessor)(x));
  518     
  519     /* Shouldn't get here */
  520     return(RBNULL);
  521 }
  522 #endif /* no_lookup */
  523 
  524 #ifndef no_destroy
  525 /*
  526  * Destroy all the elements blow us in the tree
  527  * only useful as part of a complete tree destroy.
  528  */
  529 static void
  530 RB_ENTRY(_destroy)(struct RB_ENTRY(node) *x)
  531 {
  532     if (x!=RBNULL)
  533     {
  534         if (x->left!=RBNULL)
  535             RB_ENTRY(_destroy)(x->left);
  536         if (x->right!=RBNULL)
  537             RB_ENTRY(_destroy)(x->right);
  538         RB_ENTRY(_free)(x);
  539     }
  540 }
  541 #endif /* no_destroy */
  542 
  543 /*
  544 ** Rotate our tree thus:-
  545 **
  546 **             X        rb_left_rotate(X)--->            Y
  547 **           /   \                                     /   \
  548 **          A     Y     <---rb_right_rotate(Y)        X     C
  549 **              /   \                               /   \
  550 **             B     C                             A     B
  551 **
  552 ** N.B. This does not change the ordering.
  553 **
  554 ** We assume that neither X or Y is NULL
  555 */
  556 
  557 static void
  558 RB_ENTRY(_left_rotate)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *x)
  559 {
  560     struct RB_ENTRY(node) *y;
  561 
  562     assert(x!=RBNULL);
  563     assert(x->right!=RBNULL);
  564 
  565     y=x->right; /* set Y */
  566 
  567     /* Turn Y's left subtree into X's right subtree (move B)*/
  568     x->right = y->left;
  569 
  570     /* If B is not null, set it's parent to be X */
  571     if (y->left != RBNULL)
  572         y->left->up = x;
  573 
  574     /* Set Y's parent to be what X's parent was */
  575     y->up = x->up;
  576 
  577     /* if X was the root */
  578     if (x->up == RBNULL)
  579     {
  580         *rootp=y;
  581     }
  582     else
  583     {
  584         /* Set X's parent's left or right pointer to be Y */
  585         if (x == x->up->left)
  586         {
  587             x->up->left=y;
  588         }
  589         else
  590         {
  591             x->up->right=y;
  592         }
  593     }
  594 
  595     /* Put X on Y's left */
  596     y->left=x;
  597 
  598     /* Set X's parent to be Y */
  599     x->up = y;
  600 }
  601 
  602 static void
  603 RB_ENTRY(_right_rotate)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *y)
  604 {
  605     struct RB_ENTRY(node) *x;
  606 
  607     assert(y!=RBNULL);
  608     assert(y->left!=RBNULL);
  609 
  610     x=y->left; /* set X */
  611 
  612     /* Turn X's right subtree into Y's left subtree (move B) */
  613     y->left = x->right;
  614 
  615     /* If B is not null, set it's parent to be Y */
  616     if (x->right != RBNULL)
  617         x->right->up = y;
  618 
  619     /* Set X's parent to be what Y's parent was */
  620     x->up = y->up;
  621 
  622     /* if Y was the root */
  623     if (y->up == RBNULL)
  624     {
  625         *rootp=x;
  626     }
  627     else
  628     {
  629         /* Set Y's parent's left or right pointer to be X */
  630         if (y == y->up->left)
  631         {
  632             y->up->left=x;
  633         }
  634         else
  635         {
  636             y->up->right=x;
  637         }
  638     }
  639 
  640     /* Put Y on X's right */
  641     x->right=y;
  642 
  643     /* Set Y's parent to be X */
  644     y->up = x;
  645 }
  646 
  647 /* Return a pointer to the smallest key greater than x
  648 */
  649 static struct RB_ENTRY(node) *
  650 RB_ENTRY(_successor)(const struct RB_ENTRY(node) *x)
  651 {
  652     struct RB_ENTRY(node) *y;
  653 
  654     if (x->right!=RBNULL)
  655     {
  656         /* If right is not NULL then go right one and
  657         ** then keep going left until we find a node with
  658         ** no left pointer.
  659         */
  660         for (y=x->right; y->left!=RBNULL; y=y->left);
  661     }
  662     else
  663     {
  664         /* Go up the tree until we get to a node that is on the
  665         ** left of its parent (or the root) and then return the
  666         ** parent.
  667         */
  668         y=x->up;
  669         while(y!=RBNULL && x==y->right)
  670         {
  671             x=y;
  672             y=y->up;
  673         }
  674     }
  675     return(y);
  676 }
  677 
  678 /* Return a pointer to the largest key smaller than x
  679 */
  680 static struct RB_ENTRY(node) *
  681 RB_ENTRY(_predecessor)(const struct RB_ENTRY(node) *x)
  682 {
  683     struct RB_ENTRY(node) *y;
  684 
  685     if (x->left!=RBNULL)
  686     {
  687         /* If left is not NULL then go left one and
  688         ** then keep going right until we find a node with
  689         ** no right pointer.
  690         */
  691         for (y=x->left; y->right!=RBNULL; y=y->right);
  692     }
  693     else
  694     {
  695         /* Go up the tree until we get to a node that is on the
  696         ** right of its parent (or the root) and then return the
  697         ** parent.
  698         */
  699         y=x->up;
  700         while(y!=RBNULL && x==y->left)
  701         {
  702             x=y;
  703             y=y->up;
  704         }
  705     }
  706     return(y);
  707 }
  708 
  709 #ifndef no_delete
  710 /* Delete the node z, and free up the space
  711 */
  712 static void
  713 RB_ENTRY(_delete)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *z)
  714 {
  715     struct RB_ENTRY(node) *x, *y;
  716 
  717     if (z->left == RBNULL || z->right == RBNULL)
  718         y=z;
  719     else
  720         y=RB_ENTRY(_successor)(z);
  721 
  722     if (y->left != RBNULL)
  723         x=y->left;
  724     else
  725         x=y->right;
  726 
  727     x->up = y->up;
  728 
  729     if (y->up == RBNULL)
  730     {
  731         *rootp=x;
  732     }
  733     else
  734     {
  735         if (y==y->up->left)
  736             y->up->left = x;
  737         else
  738             y->up->right = x;
  739     }
  740 
  741     if (y!=z)
  742     {
  743         RB_SET(z, key, RB_GET(y, key));
  744     }
  745 
  746     if (y->colour == BLACK)
  747         RB_ENTRY(_delete_fix)(rootp, x);
  748 
  749     RB_ENTRY(_free)(y);
  750 }
  751 
  752 /* Restore the reb-black properties after a delete */
  753 static void
  754 RB_ENTRY(_delete_fix)(struct RB_ENTRY(node) **rootp, struct RB_ENTRY(node) *x)
  755 {
  756     struct RB_ENTRY(node) *w;
  757 
  758     while (x!=*rootp && x->colour==BLACK)
  759     {
  760         if (x==x->up->left)
  761         {
  762             w=x->up->right;
  763             if (w->colour==RED)
  764             {
  765                 w->colour=BLACK;
  766                 x->up->colour=RED;
  767                 rb_left_rotate(rootp, x->up);
  768                 w=x->up->right;
  769             }
  770 
  771             if (w->left->colour==BLACK && w->right->colour==BLACK)
  772             {
  773                 w->colour=RED;
  774                 x=x->up;
  775             }
  776             else
  777             {
  778                 if (w->right->colour == BLACK)
  779                 {
  780                     w->left->colour=BLACK;
  781                     w->colour=RED;
  782                     RB_ENTRY(_right_rotate)(rootp, w);
  783                     w=x->up->right;
  784                 }
  785 
  786 
  787                 w->colour=x->up->colour;
  788                 x->up->colour = BLACK;
  789                 w->right->colour = BLACK;
  790                 RB_ENTRY(_left_rotate)(rootp, x->up);
  791                 x=*rootp;
  792             }
  793         }
  794         else
  795         {
  796             w=x->up->left;
  797             if (w->colour==RED)
  798             {
  799                 w->colour=BLACK;
  800                 x->up->colour=RED;
  801                 RB_ENTRY(_right_rotate)(rootp, x->up);
  802                 w=x->up->left;
  803             }
  804 
  805             if (w->right->colour==BLACK && w->left->colour==BLACK)
  806             {
  807                 w->colour=RED;
  808                 x=x->up;
  809             }
  810             else
  811             {
  812                 if (w->left->colour == BLACK)
  813                 {
  814                     w->right->colour=BLACK;
  815                     w->colour=RED;
  816                     RB_ENTRY(_left_rotate)(rootp, w);
  817                     w=x->up->left;
  818                 }
  819 
  820                 w->colour=x->up->colour;
  821                 x->up->colour = BLACK;
  822                 w->left->colour = BLACK;
  823                 RB_ENTRY(_right_rotate)(rootp, x->up);
  824                 x=*rootp;
  825             }
  826         }
  827     }
  828 
  829     x->colour=BLACK;
  830 }
  831 #endif /* no_delete */
  832 
  833 #ifndef no_walk
  834 static void
  835 RB_ENTRY(_walk)(const struct RB_ENTRY(node) *x, void (*action)(const RB_ENTRY(data_t) *, const VISIT, const int, void *), void *arg, int level)
  836 {
  837     if (x==RBNULL)
  838         return;
  839 
  840     if (x->left==RBNULL && x->right==RBNULL)
  841     {
  842         /* leaf */
  843         (*action)(RB_GET(x, key), leaf, level, arg);
  844     }
  845     else
  846     {
  847         (*action)(RB_GET(x, key), preorder, level, arg);
  848 
  849         RB_ENTRY(_walk)(x->left, action, arg, level+1);
  850 
  851         (*action)(RB_GET(x, key), postorder, level, arg);
  852 
  853         RB_ENTRY(_walk)(x->right, action, arg, level+1);
  854 
  855         (*action)(RB_GET(x, key), endorder, level, arg);
  856     }
  857 }
  858 #endif /* no_walk */
  859 
  860 #ifndef no_readlist
  861 static RBLIST *
  862 RB_ENTRY(_openlist)(const struct RB_ENTRY(node) *rootp)
  863 {
  864     RBLIST *rblistp;
  865 
  866     rblistp=(RBLIST *) malloc(sizeof(RBLIST));
  867     if (!rblistp)
  868         return(NULL);
  869 
  870     rblistp->rootp=rootp;
  871     rblistp->nextp=rootp;
  872 
  873     if (rootp!=RBNULL)
  874     {
  875         while(rblistp->nextp->left!=RBNULL)
  876         {
  877             rblistp->nextp=rblistp->nextp->left;
  878         }
  879     }
  880 
  881     return(rblistp);
  882 }
  883 
  884 static const RB_ENTRY(data_t) * 
  885 RB_ENTRY(_readlist)(RBLIST *rblistp)
  886 {
  887     const RB_ENTRY(data_t) *key=NULL;
  888 
  889     if (rblistp!=NULL && rblistp->nextp!=RBNULL)
  890     {
  891         key=RB_GET(rblistp->nextp, key);
  892         rblistp->nextp=RB_ENTRY(_successor)(rblistp->nextp);
  893     }
  894 
  895     return(key);
  896 }
  897 
  898 static void
  899 rb_closelist(RBLIST *rblistp)
  900 {
  901     if (rblistp)
  902         free(rblistp);
  903 }
  904 #endif /* no_readlist */
  905 
  906 #if defined(RB_USE_SBRK)
  907 /* Allocate space for our nodes, allowing us to get space from
  908 ** sbrk in larger chucks.
  909 */
  910 static struct RB_ENTRY(node) *rbfreep=NULL;
  911 
  912 #define RB_ENTRY(NODE)ALLOC_CHUNK_SIZE 1000
  913 static struct RB_ENTRY(node) *
  914 RB_ENTRY(_alloc)()
  915 {
  916     struct RB_ENTRY(node) *x;
  917     int i;
  918 
  919     if (rbfreep==NULL)
  920     {
  921         /* must grab some more space */
  922         rbfreep=(struct RB_ENTRY(node) *) sbrk(sizeof(struct RB_ENTRY(node)) * RB_ENTRY(NODE)ALLOC_CHUNK_SIZE);
  923 
  924         if (rbfreep==(struct RB_ENTRY(node) *) -1)
  925         {
  926             return(NULL);
  927         }
  928 
  929         /* tie them together in a linked list (use the up pointer) */
  930         for (i=0, x=rbfreep; i<RB_ENTRY(NODE)ALLOC_CHUNK_SIZE-1; i++, x++)
  931         {
  932             x->up = (x+1);
  933         }
  934         x->up=NULL;
  935     }
  936 
  937     x=rbfreep;
  938     rbfreep = rbfreep->up;
  939 #ifdef RB_ALLOC
  940     RB_ALLOC(ACCESS(x, key));
  941 #endif /* RB_ALLOC */
  942     return(x);
  943 }
  944 
  945 /* free (dealloc) an RB_ENTRY(node) structure - add it onto the front of the list
  946 ** N.B. RB_ENTRY(node) need not have been allocated through rb_alloc()
  947 */
  948 static void
  949 RB_ENTRY(_free)(struct RB_ENTRY(node) *x)
  950 {
  951 #ifdef RB_FREE
  952     RB_FREE(ACCESS(x, key));
  953 #endif /* RB_FREE */
  954     x->up=rbfreep;
  955     rbfreep=x;
  956 }
  957 
  958 #endif
  959 
  960 #if 0
  961 int
  962 RB_ENTRY(_check)(struct RB_ENTRY(node) *rootp)
  963 {
  964     if (rootp==NULL || rootp==RBNULL)
  965         return(0);
  966 
  967     if (rootp->up!=RBNULL)
  968     {
  969         fprintf(stderr, "Root up pointer not RBNULL");
  970         dumptree(rootp, 0);
  971         return(1);
  972     }
  973 
  974     if (RB_ENTRY(_check)1(rootp))
  975     {
  976         RB_ENTRY(dumptree)(rootp, 0);
  977         return(1);
  978     }
  979 
  980     if (RB_ENTRY(count_black)(rootp)==-1)
  981     {
  982         RB_ENTRY(dumptree)(rootp, 0);
  983         return(-1);
  984     }
  985 
  986     return(0);
  987 }
  988 
  989 int
  990 RB_ENTRY(_check1)(struct RB_ENTRY(node) *x)
  991 {
  992     if (x->left==NULL || x->right==NULL)
  993     {
  994         fprintf(stderr, "Left or right is NULL");
  995         return(1);
  996     }
  997 
  998     if (x->colour==RED)
  999     {
 1000         if (x->left->colour!=BLACK && x->right->colour!=BLACK)
 1001         {
 1002             fprintf(stderr, "Children of red node not both black, x=%ld", x);
 1003             return(1);
 1004         }
 1005     }
 1006 
 1007     if (x->left != RBNULL)
 1008     {
 1009         if (x->left->up != x)
 1010         {
 1011             fprintf(stderr, "x->left->up != x, x=%ld", x);
 1012             return(1);
 1013         }
 1014 
 1015         if (rb_check1(x->left))
 1016             return(1);
 1017     }       
 1018 
 1019     if (x->right != RBNULL)
 1020     {
 1021         if (x->right->up != x)
 1022         {
 1023             fprintf(stderr, "x->right->up != x, x=%ld", x);
 1024             return(1);
 1025         }
 1026 
 1027         if (rb_check1(x->right))
 1028             return(1);
 1029     }       
 1030     return(0);
 1031 }
 1032 
 1033 RB_ENTRY(count_black)(struct RB_ENTRY(node) *x)
 1034 {
 1035     int nleft, nright;
 1036 
 1037     if (x==RBNULL)
 1038         return(1);
 1039 
 1040     nleft=RB_ENTRY(count_black)(x->left);
 1041     nright=RB_ENTRY(count_black)(x->right);
 1042 
 1043     if (nleft==-1 || nright==-1)
 1044         return(-1);
 1045 
 1046     if (nleft != nright)
 1047     {
 1048         fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
 1049         return(-1);
 1050     }
 1051 
 1052     if (x->colour == BLACK)
 1053     {
 1054         nleft++;
 1055     }
 1056 
 1057     return(nleft);
 1058 }
 1059 
 1060 RB_ENTRY(dumptree)(struct RB_ENTRY(node) *x, int n)
 1061 {
 1062     char *prkey();
 1063 
 1064     if (x!=NULL && x!=RBNULL)
 1065     {
 1066         n++;
 1067         fprintf(stderr, "Tree: %*s %ld: left=%ld, right=%ld, colour=%s, key=%s",
 1068             n,
 1069             "",
 1070             x,
 1071             x->left,
 1072             x->right,
 1073             (x->colour==BLACK) ? "BLACK" : "RED",
 1074             prkey(RB_GET(x, key)));
 1075 
 1076         RB_ENTRY(dumptree)(x->left, n);
 1077         RB_ENTRY(dumptree)(x->right, n);
 1078     }   
 1079 }
 1080 #endif
 1081 
 1082 /*
 1083  * $Log: redblack.c,v $
 1084  * Revision 1.9  2003/10/24 01:31:21  damo
 1085  * Patches from Eric Raymond: %prefix is implemented.  Various other small
 1086  * changes avoid stepping on global namespaces and improve the documentation.
 1087  *
 1088  * Revision 1.8  2002/08/26 05:33:47  damo
 1089  * Some minor fixes:-
 1090  * Stopped ./configure warning about stuff being in the wrong order
 1091  * Fixed compiler warning about const (not sure about this)
 1092  * Changed directory of redblack.c in documentation
 1093  *
 1094  * Revision 1.7  2002/08/26 03:11:40  damo
 1095  * Fixed up a bunch of compiler warnings when compiling example4
 1096  *
 1097  * Tidies up the Makefile.am & Specfile.
 1098  *
 1099  * Renamed redblack to rbgen
 1100  *
 1101  * Revision 1.6  2002/08/26 01:03:35  damo
 1102  * Patch from Eric Raymond to change the way the library is used:-
 1103  *
 1104  * Eric's idea is to convert libredblack into a piece of in-line code
 1105  * generated by another program. This should be faster, smaller and easier
 1106  * to use.
 1107  *
 1108  * This is the first check-in of his code before I start futzing with it!
 1109  *
 1110  * Revision 1.5  2002/01/30 07:54:53  damo
 1111  * Fixed up the libtool versioning stuff (finally)
 1112  * Fixed bug 500600 (not detecting a NULL return from malloc)
 1113  * Fixed bug 509485 (no longer needs search.h)
 1114  * Cleaned up debugging section
 1115  * Allow multiple inclusions of redblack.h
 1116  * Thanks to Matthias Andree for reporting (and fixing) these
 1117  *
 1118  * Revision 1.4  2000/06/06 14:43:43  damo
 1119  * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
 1120  * Added two new examples
 1121  *
 1122  * Revision 1.3  2000/05/24 06:45:27  damo
 1123  * Converted everything over to using const
 1124  * Added a new example1.c file to demonstrate the worst case scenario
 1125  * Minor fixups of the spec file
 1126  *
 1127  * Revision 1.2  2000/05/24 06:17:10  damo
 1128  * Fixed up the License (now the LGPL)
 1129  *
 1130  * Revision 1.1  2000/05/24 04:15:53  damo
 1131  * Initial import of files. Versions are now all over the place. Oh well
 1132  *
 1133  */
 1134