lib/tsearch.c

   1 /* Copyright (C) 1995-1997, 2000, 2006-2007, 2009 Free Software Foundation, Inc.
   2    Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
   3
   4    NOTE: The canonical source of this file is maintained with the GNU C
   5    Library.  Bugs can be reported to bug-glibc@gnu.org.
   6
   7    This program is free software: you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 3 of the License, or any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 /* Tree search for red/black trees.
  21    The algorithm for adding nodes is taken from one of the many "Algorithms"
  22    books by Robert Sedgewick, although the implementation differs.
  23    The algorithm for deleting nodes can probably be found in a book named
  24    "Introduction to Algorithms" by Cormen/Leiserson/Rivest.  At least that's
  25    the book that my professor took most algorithms from during the "Data
  26    Structures" course...
  27
  28    Totally public domain.  */
  29
  30 /* Red/black trees are binary trees in which the edges are colored either red
  31    or black.  They have the following properties:
  32    1. The number of black edges on every path from the root to a leaf is
  33       constant.
  34    2. No two red edges are adjacent.
  35    Therefore there is an upper bound on the length of every path, it's
  36    O(log n) where n is the number of nodes in the tree.  No path can be longer
  37    than 1+2*P where P is the length of the shortest path in the tree.
  38    Useful for the implementation:
  39    3. If one of the children of a node is NULL, then the other one is red
  40       (if it exists).
  41
  42    In the implementation, not the edges are colored, but the nodes.  The color
  43    interpreted as the color of the edge leading to this node.  The color is
  44    meaningless for the root node, but we color the root node black for
  45    convenience.  All added nodes are red initially.
  46
  47    Adding to a red/black tree is rather easy.  The right place is searched
  48    with a usual binary tree search.  Additionally, whenever a node N is
  49    reached that has two red successors, the successors are colored black and
  50    the node itself colored red.  This moves red edges up the tree where they
  51    pose less of a problem once we get to really insert the new node.  Changing
  52    N's color to red may violate rule 2, however, so rotations may become
  53    necessary to restore the invariants.  Adding a new red leaf may violate
  54    the same rule, so afterwards an additional check is run and the tree
  55    possibly rotated.
  56
  57    Deleting is hairy.  There are mainly two nodes involved: the node to be
  58    deleted (n1), and another node that is to be unchained from the tree (n2).
  59    If n1 has a successor (the node with a smallest key that is larger than
  60    n1), then the successor becomes n2 and its contents are copied into n1,
  61    otherwise n1 becomes n2.
  62    Unchaining a node may violate rule 1: if n2 is black, one subtree is
  63    missing one black edge afterwards.  The algorithm must try to move this
  64    error upwards towards the root, so that the subtree that does not have
  65    enough black edges becomes the whole tree.  Once that happens, the error
  66    has disappeared.  It may not be necessary to go all the way up, since it
  67    is possible that rotations and recoloring can fix the error before that.
  68
  69    Although the deletion algorithm must walk upwards through the tree, we
  70    do not store parent pointers in the nodes.  Instead, delete allocates a
  71    small array of parent pointers and fills it while descending the tree.
  72    Since we know that the length of a path is O(log n), where n is the number
  73    of nodes, this is likely to use less memory.  */
  74
  75 /* Tree rotations look like this:
  76       A                C
  77      / \              / \
  78     B   C            A   G
  79    / \ / \  -->     / \
  80    D E F G         B   F
  81                   / \
  82                  D   E
  83
  84    In this case, A has been rotated left.  This preserves the ordering of the
  85    binary tree.  */
  86
  87 #include <config.h>
  88
  89 /* Don't use __attribute__ __nonnull__ in this compilation unit.  Otherwise gcc
  90    optimizes away the rootp == NULL tests below.  */
  91 #define _GL_ARG_NONNULL(params)
  92
  93 /* Specification.  */
  94 #ifdef IN_LIBINTL
  95 # include "tsearch.h"
  96 #else
  97 # include <search.h>
  98 #endif
  99
 100 #include <stdlib.h>
 101
 102 typedef int (*__compar_fn_t) (const void *, const void *);
 103 typedef void (*__action_fn_t) (const void *, VISIT, int);
 104
 105 #ifndef weak_alias
 106 # define __tsearch tsearch
 107 # define __tfind tfind
 108 # define __tdelete tdelete
 109 # define __twalk twalk
 110 #endif
 111
 112 #ifndef internal_function
 113 /* Inside GNU libc we mark some function in a special way.  In other
 114    environments simply ignore the marking.  */
 115 # define internal_function
 116 #endif
 117
 118 typedef struct node_t
 119 {
 120   /* Callers expect this to be the first element in the structure - do not
 121      move!  */
 122   const void *key;
 123   struct node_t *left;
 124   struct node_t *right;
 125   unsigned int red:1;
 126 } *node;
 127 typedef const struct node_t *const_node;
 128
 129 #undef DEBUGGING
 130
 131 #ifdef DEBUGGING
 132
 133 /* Routines to check tree invariants.  */
 134
 135 #include <assert.h>
 136
 137 #define CHECK_TREE(a) check_tree(a)
 138
 139 static void
 140 check_tree_recurse (node p, int d_sofar, int d_total)
 141 {
 142   if (p == NULL)
 143     {
 144       assert (d_sofar == d_total);
 145       return;
 146     }
 147
 148   check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total);
 149   check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total);
 150   if (p->left)
 151     assert (!(p->left->red && p->red));
 152   if (p->right)
 153     assert (!(p->right->red && p->red));
 154 }
 155
 156 static void
 157 check_tree (node root)
 158 {
 159   int cnt = 0;
 160   node p;
 161   if (root == NULL)
 162     return;
 163   root->red = 0;
 164   for(p = root->left; p; p = p->left)
 165     cnt += !p->red;
 166   check_tree_recurse (root, 0, cnt);
 167 }
 168
 169
 170 #else
 171
 172 #define CHECK_TREE(a)
 173
 174 #endif
 175
 176 /* Possibly "split" a node with two red successors, and/or fix up two red
 177    edges in a row.  ROOTP is a pointer to the lowest node we visited, PARENTP
 178    and GPARENTP pointers to its parent/grandparent.  P_R and GP_R contain the
 179    comparison values that determined which way was taken in the tree to reach
 180    ROOTP.  MODE is 1 if we need not do the split, but must check for two red
 181    edges between GPARENTP and ROOTP.  */
 182 static void
 183 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 184                         int p_r, int gp_r, int mode)
 185 {
 186   node root = *rootp;
 187   node *rp, *lp;
 188   rp = &(*rootp)->right;
 189   lp = &(*rootp)->left;
 190
 191   /* See if we have to split this node (both successors red).  */
 192   if (mode == 1
 193       || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
 194     {
 195       /* This node becomes red, its successors black.  */
 196       root->red = 1;
 197       if (*rp)
 198         (*rp)->red = 0;
 199       if (*lp)
 200         (*lp)->red = 0;
 201
 202       /* If the parent of this node is also red, we have to do
 203          rotations.  */
 204       if (parentp != NULL && (*parentp)->red)
 205         {
 206           node gp = *gparentp;
 207           node p = *parentp;
 208           /* There are two main cases:
 209              1. The edge types (left or right) of the two red edges differ.
 210              2. Both red edges are of the same type.
 211              There exist two symmetries of each case, so there is a total of
 212              4 cases.  */
 213           if ((p_r > 0) != (gp_r > 0))
 214             {
 215               /* Put the child at the top of the tree, with its parent
 216                  and grandparent as successors.  */
 217               p->red = 1;
 218               gp->red = 1;
 219               root->red = 0;
 220               if (p_r < 0)
 221                 {
 222                   /* Child is left of parent.  */
 223                   p->left = *rp;
 224                   *rp = p;
 225                   gp->right = *lp;
 226                   *lp = gp;
 227                 }
 228               else
 229                 {
 230                   /* Child is right of parent.  */
 231                   p->right = *lp;
 232                   *lp = p;
 233                   gp->left = *rp;
 234                   *rp = gp;
 235                 }
 236               *gparentp = root;
 237             }
 238           else
 239             {
 240               *gparentp = *parentp;
 241               /* Parent becomes the top of the tree, grandparent and
 242                  child are its successors.  */
 243               p->red = 0;
 244               gp->red = 1;
 245               if (p_r < 0)
 246                 {
 247                   /* Left edges.  */
 248                   gp->left = p->right;
 249                   p->right = gp;
 250                 }
 251               else
 252                 {
 253                   /* Right edges.  */
 254                   gp->right = p->left;
 255                   p->left = gp;
 256                 }
 257             }
 258         }
 259     }
 260 }
 261
 262 /* Find or insert datum into search tree.
 263    KEY is the key to be located, ROOTP is the address of tree root,
 264    COMPAR the ordering function.  */
 265 void *
 266 __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 267 {
 268   node q;
 269   node *parentp = NULL, *gparentp = NULL;
 270   node *rootp = (node *) vrootp;
 271   node *nextp;
 272   int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler.  */
 273
 274   if (rootp == NULL)
 275     return NULL;
 276
 277   /* This saves some additional tests below.  */
 278   if (*rootp != NULL)
 279     (*rootp)->red = 0;
 280
 281   CHECK_TREE (*rootp);
 282
 283   nextp = rootp;
 284   while (*nextp != NULL)
 285     {
 286       node root = *rootp;
 287       r = (*compar) (key, root->key);
 288       if (r == 0)
 289         return root;
 290
 291       maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
 292       /* If that did any rotations, parentp and gparentp are now garbage.
 293          That doesn't matter, because the values they contain are never
 294          used again in that case.  */
 295
 296       nextp = r < 0 ? &root->left : &root->right;
 297       if (*nextp == NULL)
 298         break;
 299
 300       gparentp = parentp;
 301       parentp = rootp;
 302       rootp = nextp;
 303
 304       gp_r = p_r;
 305       p_r = r;
 306     }
 307
 308   q = (struct node_t *) malloc (sizeof (struct node_t));
 309   if (q != NULL)
 310     {
 311       *nextp = q;                       /* link new node to old */
 312       q->key = key;                     /* initialize new node */
 313       q->red = 1;
 314       q->left = q->right = NULL;
 315
 316       if (nextp != rootp)
 317         /* There may be two red edges in a row now, which we must avoid by
 318            rotating the tree.  */
 319         maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
 320     }
 321
 322   return q;
 323 }
 324 #ifdef weak_alias
 325 weak_alias (__tsearch, tsearch)
 326 #endif
 327
 328
 329 /* Find datum in search tree.
 330    KEY is the key to be located, ROOTP is the address of tree root,
 331    COMPAR the ordering function.  */
 332 void *
 333 __tfind (key, vrootp, compar)
 334      const void *key;
 335      void *const *vrootp;
 336      __compar_fn_t compar;
 337 {
 338   node *rootp = (node *) vrootp;
 339
 340   if (rootp == NULL)
 341     return NULL;
 342
 343   CHECK_TREE (*rootp);
 344
 345   while (*rootp != NULL)
 346     {
 347       node root = *rootp;
 348       int r;
 349
 350       r = (*compar) (key, root->key);
 351       if (r == 0)
 352         return root;
 353
 354       rootp = r < 0 ? &root->left : &root->right;
 355     }
 356   return NULL;
 357 }
 358 #ifdef weak_alias
 359 weak_alias (__tfind, tfind)
 360 #endif
 361
 362
 363 /* Delete node with given key.
 364    KEY is the key to be deleted, ROOTP is the address of the root of tree,
 365    COMPAR the comparison function.  */
 366 void *
 367 __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 368 {
 369   node p, q, r, retval;
 370   int cmp;
 371   node *rootp = (node *) vrootp;
 372   node root, unchained;
 373   /* Stack of nodes so we remember the parents without recursion.  It's
 374      _very_ unlikely that there are paths longer than 40 nodes.  The tree
 375      would need to have around 250.000 nodes.  */
 376   int stacksize = 100;
 377   int sp = 0;
 378   node *nodestack[100];
 379
 380   if (rootp == NULL)
 381     return NULL;
 382   p = *rootp;
 383   if (p == NULL)
 384     return NULL;
 385
 386   CHECK_TREE (p);
 387
 388   while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
 389     {
 390       if (sp == stacksize)
 391         abort ();
 392
 393       nodestack[sp++] = rootp;
 394       p = *rootp;
 395       rootp = ((cmp < 0)
 396                ? &(*rootp)->left
 397                : &(*rootp)->right);
 398       if (*rootp == NULL)
 399         return NULL;
 400     }
 401
 402   /* This is bogus if the node to be deleted is the root... this routine
 403      really should return an integer with 0 for success, -1 for failure
 404      and errno = ESRCH or something.  */
 405   retval = p;
 406
 407   /* We don't unchain the node we want to delete. Instead, we overwrite
 408      it with its successor and unchain the successor.  If there is no
 409      successor, we really unchain the node to be deleted.  */
 410
 411   root = *rootp;
 412
 413   r = root->right;
 414   q = root->left;
 415
 416   if (q == NULL || r == NULL)
 417     unchained = root;
 418   else
 419     {
 420       node *parent = rootp, *up = &root->right;
 421       for (;;)
 422         {
 423           if (sp == stacksize)
 424             abort ();
 425           nodestack[sp++] = parent;
 426           parent = up;
 427           if ((*up)->left == NULL)
 428             break;
 429           up = &(*up)->left;
 430         }
 431       unchained = *up;
 432     }
 433
 434   /* We know that either the left or right successor of UNCHAINED is NULL.
 435      R becomes the other one, it is chained into the parent of UNCHAINED.  */
 436   r = unchained->left;
 437   if (r == NULL)
 438     r = unchained->right;
 439   if (sp == 0)
 440     *rootp = r;
 441   else
 442     {
 443       q = *nodestack[sp-1];
 444       if (unchained == q->right)
 445         q->right = r;
 446       else
 447         q->left = r;
 448     }
 449
 450   if (unchained != root)
 451     root->key = unchained->key;
 452   if (!unchained->red)
 453     {
 454       /* Now we lost a black edge, which means that the number of black
 455          edges on every path is no longer constant.  We must balance the
 456          tree.  */
 457       /* NODESTACK now contains all parents of R.  R is likely to be NULL
 458          in the first iteration.  */
 459       /* NULL nodes are considered black throughout - this is necessary for
 460          correctness.  */
 461       while (sp > 0 && (r == NULL || !r->red))
 462         {
 463           node *pp = nodestack[sp - 1];
 464           p = *pp;
 465           /* Two symmetric cases.  */
 466           if (r == p->left)
 467             {
 468               /* Q is R's brother, P is R's parent.  The subtree with root
 469                  R has one black edge less than the subtree with root Q.  */
 470               q = p->right;
 471               if (q->red)
 472                 {
 473                   /* If Q is red, we know that P is black. We rotate P left
 474                      so that Q becomes the top node in the tree, with P below
 475                      it.  P is colored red, Q is colored black.
 476                      This action does not change the black edge count for any
 477                      leaf in the tree, but we will be able to recognize one
 478                      of the following situations, which all require that Q
 479                      is black.  */
 480                   q->red = 0;
 481                   p->red = 1;
 482                   /* Left rotate p.  */
 483                   p->right = q->left;
 484                   q->left = p;
 485                   *pp = q;
 486                   /* Make sure pp is right if the case below tries to use
 487                      it.  */
 488                   nodestack[sp++] = pp = &q->left;
 489                   q = p->right;
 490                 }
 491               /* We know that Q can't be NULL here.  We also know that Q is
 492                  black.  */
 493               if ((q->left == NULL || !q->left->red)
 494                   && (q->right == NULL || !q->right->red))
 495                 {
 496                   /* Q has two black successors.  We can simply color Q red.
 497                      The whole subtree with root P is now missing one black
 498                      edge.  Note that this action can temporarily make the
 499                      tree invalid (if P is red).  But we will exit the loop
 500                      in that case and set P black, which both makes the tree
 501                      valid and also makes the black edge count come out
 502                      right.  If P is black, we are at least one step closer
 503                      to the root and we'll try again the next iteration.  */
 504                   q->red = 1;
 505                   r = p;
 506                 }
 507               else
 508                 {
 509                   /* Q is black, one of Q's successors is red.  We can
 510                      repair the tree with one operation and will exit the
 511                      loop afterwards.  */
 512                   if (q->right == NULL || !q->right->red)
 513                     {
 514                       /* The left one is red.  We perform the same action as
 515                          in maybe_split_for_insert where two red edges are
 516                          adjacent but point in different directions:
 517                          Q's left successor (let's call it Q2) becomes the
 518                          top of the subtree we are looking at, its parent (Q)
 519                          and grandparent (P) become its successors. The former
 520                          successors of Q2 are placed below P and Q.
 521                          P becomes black, and Q2 gets the color that P had.
 522                          This changes the black edge count only for node R and
 523                          its successors.  */
 524                       node q2 = q->left;
 525                       q2->red = p->red;
 526                       p->right = q2->left;
 527                       q->left = q2->right;
 528                       q2->right = q;
 529                       q2->left = p;
 530                       *pp = q2;
 531                       p->red = 0;
 532                     }
 533                   else
 534                     {
 535                       /* It's the right one.  Rotate P left. P becomes black,
 536                          and Q gets the color that P had.  Q's right successor
 537                          also becomes black.  This changes the black edge
 538                          count only for node R and its successors.  */
 539                       q->red = p->red;
 540                       p->red = 0;
 541
 542                       q->right->red = 0;
 543
 544                       /* left rotate p */
 545                       p->right = q->left;
 546                       q->left = p;
 547                       *pp = q;
 548                     }
 549
 550                   /* We're done.  */
 551                   sp = 1;
 552                   r = NULL;
 553                 }
 554             }
 555           else
 556             {
 557               /* Comments: see above.  */
 558               q = p->left;
 559               if (q->red)
 560                 {
 561                   q->red = 0;
 562                   p->red = 1;
 563                   p->left = q->right;
 564                   q->right = p;
 565                   *pp = q;
 566                   nodestack[sp++] = pp = &q->right;
 567                   q = p->left;
 568                 }
 569               if ((q->right == NULL || !q->right->red)
 570                        && (q->left == NULL || !q->left->red))
 571                 {
 572                   q->red = 1;
 573                   r = p;
 574                 }
 575               else
 576                 {
 577                   if (q->left == NULL || !q->left->red)
 578                     {
 579                       node q2 = q->right;
 580                       q2->red = p->red;
 581                       p->left = q2->right;
 582                       q->right = q2->left;
 583                       q2->left = q;
 584                       q2->right = p;
 585                       *pp = q2;
 586                       p->red = 0;
 587                     }
 588                   else
 589                     {
 590                       q->red = p->red;
 591                       p->red = 0;
 592                       q->left->red = 0;
 593                       p->left = q->right;
 594                       q->right = p;
 595                       *pp = q;
 596                     }
 597                   sp = 1;
 598                   r = NULL;
 599                 }
 600             }
 601           --sp;
 602         }
 603       if (r != NULL)
 604         r->red = 0;
 605     }
 606
 607   free (unchained);
 608   return retval;
 609 }
 610 #ifdef weak_alias
 611 weak_alias (__tdelete, tdelete)
 612 #endif
 613
 614
 615 /* Walk the nodes of a tree.
 616    ROOT is the root of the tree to be walked, ACTION the function to be
 617    called at each node.  LEVEL is the level of ROOT in the whole tree.  */
 618 static void
 619 internal_function
 620 trecurse (const void *vroot, __action_fn_t action, int level)
 621 {
 622   const_node root = (const_node) vroot;
 623
 624   if (root->left == NULL && root->right == NULL)
 625     (*action) (root, leaf, level);
 626   else
 627     {
 628       (*action) (root, preorder, level);
 629       if (root->left != NULL)
 630         trecurse (root->left, action, level + 1);
 631       (*action) (root, postorder, level);
 632       if (root->right != NULL)
 633         trecurse (root->right, action, level + 1);
 634       (*action) (root, endorder, level);
 635     }
 636 }
 637
 638
 639 /* Walk the nodes of a tree.
 640    ROOT is the root of the tree to be walked, ACTION the function to be
 641    called at each node.  */
 642 void
 643 __twalk (const void *vroot, __action_fn_t action)
 644 {
 645   const_node root = (const_node) vroot;
 646
 647   CHECK_TREE (root);
 648
 649   if (root != NULL && action != NULL)
 650     trecurse (root, action, 0);
 651 }
 652 #ifdef weak_alias
 653 weak_alias (__twalk, twalk)
 654 #endif
 655
 656
 657 #ifdef _LIBC
 658
 659 /* The standardized functions miss an important functionality: the
 660    tree cannot be removed easily.  We provide a function to do this.  */
 661 static void
 662 internal_function
 663 tdestroy_recurse (node root, __free_fn_t freefct)
 664 {
 665   if (root->left != NULL)
 666     tdestroy_recurse (root->left, freefct);
 667   if (root->right != NULL)
 668     tdestroy_recurse (root->right, freefct);
 669   (*freefct) ((void *) root->key);
 670   /* Free the node itself.  */
 671   free (root);
 672 }
 673
 674 void
 675 __tdestroy (void *vroot, __free_fn_t freefct)
 676 {
 677   node root = (node) vroot;
 678
 679   CHECK_TREE (root);
 680
 681   if (root != NULL)
 682     tdestroy_recurse (root, freefct);
 683 }
 684 weak_alias (__tdestroy, tdestroy)
 685
 686 #endif /* _LIBC */