misc/tsearch.c

   1 /* Copyright (C) 1995, 1996, 1997, 2000, 2006 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library 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 GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, write to the Free
  17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  18    02111-1307 USA.  */
  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 <stdlib.h>
  88 #include <string.h>
  89 #include <search.h>
  90
  91 typedef struct node_t
  92 {
  93   /* Callers expect this to be the first element in the structure - do not
  94      move!  */
  95   const void *key;
  96   struct node_t *left;
  97   struct node_t *right;
  98   unsigned int red:1;
  99 } *node;
 100 typedef const struct node_t *const_node;
 101
 102 #undef DEBUGGING
 103
 104 #ifdef DEBUGGING
 105
 106 /* Routines to check tree invariants.  */
 107
 108 #include <assert.h>
 109
 110 #define CHECK_TREE(a) check_tree(a)
 111
 112 static void
 113 check_tree_recurse (node p, int d_sofar, int d_total)
 114 {
 115   if (p == NULL)
 116     {
 117       assert (d_sofar == d_total);
 118       return;
 119     }
 120
 121   check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total);
 122   check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total);
 123   if (p->left)
 124     assert (!(p->left->red && p->red));
 125   if (p->right)
 126     assert (!(p->right->red && p->red));
 127 }
 128
 129 static void
 130 check_tree (node root)
 131 {
 132   int cnt = 0;
 133   node p;
 134   if (root == NULL)
 135     return;
 136   root->red = 0;
 137   for(p = root->left; p; p = p->left)
 138     cnt += !p->red;
 139   check_tree_recurse (root, 0, cnt);
 140 }
 141
 142
 143 #else
 144
 145 #define CHECK_TREE(a)
 146
 147 #endif
 148
 149 /* Possibly "split" a node with two red successors, and/or fix up two red
 150    edges in a row.  ROOTP is a pointer to the lowest node we visited, PARENTP
 151    and GPARENTP pointers to its parent/grandparent.  P_R and GP_R contain the
 152    comparison values that determined which way was taken in the tree to reach
 153    ROOTP.  MODE is 1 if we need not do the split, but must check for two red
 154    edges between GPARENTP and ROOTP.  */
 155 static void
 156 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 157                         int p_r, int gp_r, int mode)
 158 {
 159   node root = *rootp;
 160   node *rp, *lp;
 161   rp = &(*rootp)->right;
 162   lp = &(*rootp)->left;
 163
 164   /* See if we have to split this node (both successors red).  */
 165   if (mode == 1
 166       || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
 167     {
 168       /* This node becomes red, its successors black.  */
 169       root->red = 1;
 170       if (*rp)
 171         (*rp)->red = 0;
 172       if (*lp)
 173         (*lp)->red = 0;
 174
 175       /* If the parent of this node is also red, we have to do
 176          rotations.  */
 177       if (parentp != NULL && (*parentp)->red)
 178         {
 179           node gp = *gparentp;
 180           node p = *parentp;
 181           /* There are two main cases:
 182              1. The edge types (left or right) of the two red edges differ.
 183              2. Both red edges are of the same type.
 184              There exist two symmetries of each case, so there is a total of
 185              4 cases.  */
 186           if ((p_r > 0) != (gp_r > 0))
 187             {
 188               /* Put the child at the top of the tree, with its parent
 189                  and grandparent as successors.  */
 190               p->red = 1;
 191               gp->red = 1;
 192               root->red = 0;
 193               if (p_r < 0)
 194                 {
 195                   /* Child is left of parent.  */
 196                   p->left = *rp;
 197                   *rp = p;
 198                   gp->right = *lp;
 199                   *lp = gp;
 200                 }
 201               else
 202                 {
 203                   /* Child is right of parent.  */
 204                   p->right = *lp;
 205                   *lp = p;
 206                   gp->left = *rp;
 207                   *rp = gp;
 208                 }
 209               *gparentp = root;
 210             }
 211           else
 212             {
 213               *gparentp = *parentp;
 214               /* Parent becomes the top of the tree, grandparent and
 215                  child are its successors.  */
 216               p->red = 0;
 217               gp->red = 1;
 218               if (p_r < 0)
 219                 {
 220                   /* Left edges.  */
 221                   gp->left = p->right;
 222                   p->right = gp;
 223                 }
 224               else
 225                 {
 226                   /* Right edges.  */
 227                   gp->right = p->left;
 228                   p->left = gp;
 229                 }
 230             }
 231         }
 232     }
 233 }
 234
 235 /* Find or insert datum into search tree.
 236    KEY is the key to be located, ROOTP is the address of tree root,
 237    COMPAR the ordering function.  */
 238 void *
 239 __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 240 {
 241   node q;
 242   node *parentp = NULL, *gparentp = NULL;
 243   node *rootp = (node *) vrootp;
 244   node *nextp;
 245   int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler.  */
 246
 247   if (rootp == NULL)
 248     return NULL;
 249
 250   /* This saves some additional tests below.  */
 251   if (*rootp != NULL)
 252     (*rootp)->red = 0;
 253
 254   CHECK_TREE (*rootp);
 255
 256   nextp = rootp;
 257   while (*nextp != NULL)
 258     {
 259       node root = *rootp;
 260       r = (*compar) (key, root->key);
 261       if (r == 0)
 262         return root;
 263
 264       maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
 265       /* If that did any rotations, parentp and gparentp are now garbage.
 266          That doesn't matter, because the values they contain are never
 267          used again in that case.  */
 268
 269       nextp = r < 0 ? &root->left : &root->right;
 270       if (*nextp == NULL)
 271         break;
 272
 273       gparentp = parentp;
 274       parentp = rootp;
 275       rootp = nextp;
 276
 277       gp_r = p_r;
 278       p_r = r;
 279     }
 280
 281   q = (struct node_t *) malloc (sizeof (struct node_t));
 282   if (q != NULL)
 283     {
 284       *nextp = q;                       /* link new node to old */
 285       q->key = key;                     /* initialize new node */
 286       q->red = 1;
 287       q->left = q->right = NULL;
 288
 289       if (nextp != rootp)
 290         /* There may be two red edges in a row now, which we must avoid by
 291            rotating the tree.  */
 292         maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
 293     }
 294
 295   return q;
 296 }
 297 weak_alias (__tsearch, tsearch)
 298
 299
 300 /* Find datum in search tree.
 301    KEY is the key to be located, ROOTP is the address of tree root,
 302    COMPAR the ordering function.  */
 303 void *
 304 __tfind (key, vrootp, compar)
 305      const void *key;
 306      void *const *vrootp;
 307      __compar_fn_t compar;
 308 {
 309   node *rootp = (node *) vrootp;
 310
 311   if (rootp == NULL)
 312     return NULL;
 313
 314   CHECK_TREE (*rootp);
 315
 316   while (*rootp != NULL)
 317     {
 318       node root = *rootp;
 319       int r;
 320
 321       r = (*compar) (key, root->key);
 322       if (r == 0)
 323         return root;
 324
 325       rootp = r < 0 ? &root->left : &root->right;
 326     }
 327   return NULL;
 328 }
 329 weak_alias (__tfind, tfind)
 330
 331
 332 /* Delete node with given key.
 333    KEY is the key to be deleted, ROOTP is the address of the root of tree,
 334    COMPAR the comparison function.  */
 335 void *
 336 __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 337 {
 338   node p, q, r, retval;
 339   int cmp;
 340   node *rootp = (node *) vrootp;
 341   node root, unchained;
 342   /* Stack of nodes so we remember the parents without recursion.  It's
 343      _very_ unlikely that there are paths longer than 40 nodes.  The tree
 344      would need to have around 250.000 nodes.  */
 345   int stacksize = 40;
 346   int sp = 0;
 347   node **nodestack = alloca (sizeof (node *) * stacksize);
 348
 349   if (rootp == NULL)
 350     return NULL;
 351   p = *rootp;
 352   if (p == NULL)
 353     return NULL;
 354
 355   CHECK_TREE (p);
 356
 357   while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
 358     {
 359       if (sp == stacksize)
 360         {
 361           node **newstack;
 362           stacksize += 20;
 363           newstack = alloca (sizeof (node *) * stacksize);
 364           nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
 365         }
 366
 367       nodestack[sp++] = rootp;
 368       p = *rootp;
 369       rootp = ((cmp < 0)
 370                ? &(*rootp)->left
 371                : &(*rootp)->right);
 372       if (*rootp == NULL)
 373         return NULL;
 374     }
 375
 376   /* This is bogus if the node to be deleted is the root... this routine
 377      really should return an integer with 0 for success, -1 for failure
 378      and errno = ESRCH or something.  */
 379   retval = p;
 380
 381   /* We don't unchain the node we want to delete. Instead, we overwrite
 382      it with its successor and unchain the successor.  If there is no
 383      successor, we really unchain the node to be deleted.  */
 384
 385   root = *rootp;
 386
 387   r = root->right;
 388   q = root->left;
 389
 390   if (q == NULL || r == NULL)
 391     unchained = root;
 392   else
 393     {
 394       node *parent = rootp, *up = &root->right;
 395       for (;;)
 396         {
 397           if (sp == stacksize)
 398             {
 399               node **newstack;
 400               stacksize += 20;
 401               newstack = alloca (sizeof (node *) * stacksize);
 402               nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
 403             }
 404           nodestack[sp++] = parent;
 405           parent = up;
 406           if ((*up)->left == NULL)
 407             break;
 408           up = &(*up)->left;
 409         }
 410       unchained = *up;
 411     }
 412
 413   /* We know that either the left or right successor of UNCHAINED is NULL.
 414      R becomes the other one, it is chained into the parent of UNCHAINED.  */
 415   r = unchained->left;
 416   if (r == NULL)
 417     r = unchained->right;
 418   if (sp == 0)
 419     *rootp = r;
 420   else
 421     {
 422       q = *nodestack[sp-1];
 423       if (unchained == q->right)
 424         q->right = r;
 425       else
 426         q->left = r;
 427     }
 428
 429   if (unchained != root)
 430     root->key = unchained->key;
 431   if (!unchained->red)
 432     {
 433       /* Now we lost a black edge, which means that the number of black
 434          edges on every path is no longer constant.  We must balance the
 435          tree.  */
 436       /* NODESTACK now contains all parents of R.  R is likely to be NULL
 437          in the first iteration.  */
 438       /* NULL nodes are considered black throughout - this is necessary for
 439          correctness.  */
 440       while (sp > 0 && (r == NULL || !r->red))
 441         {
 442           node *pp = nodestack[sp - 1];
 443           p = *pp;
 444           /* Two symmetric cases.  */
 445           if (r == p->left)
 446             {
 447               /* Q is R's brother, P is R's parent.  The subtree with root
 448                  R has one black edge less than the subtree with root Q.  */
 449               q = p->right;
 450               if (q->red)
 451                 {
 452                   /* If Q is red, we know that P is black. We rotate P left
 453                      so that Q becomes the top node in the tree, with P below
 454                      it.  P is colored red, Q is colored black.
 455                      This action does not change the black edge count for any
 456                      leaf in the tree, but we will be able to recognize one
 457                      of the following situations, which all require that Q
 458                      is black.  */
 459                   q->red = 0;
 460                   p->red = 1;
 461                   /* Left rotate p.  */
 462                   p->right = q->left;
 463                   q->left = p;
 464                   *pp = q;
 465                   /* Make sure pp is right if the case below tries to use
 466                      it.  */
 467                   nodestack[sp++] = pp = &q->left;
 468                   q = p->right;
 469                 }
 470               /* We know that Q can't be NULL here.  We also know that Q is
 471                  black.  */
 472               if ((q->left == NULL || !q->left->red)
 473                   && (q->right == NULL || !q->right->red))
 474                 {
 475                   /* Q has two black successors.  We can simply color Q red.
 476                      The whole subtree with root P is now missing one black
 477                      edge.  Note that this action can temporarily make the
 478                      tree invalid (if P is red).  But we will exit the loop
 479                      in that case and set P black, which both makes the tree
 480                      valid and also makes the black edge count come out
 481                      right.  If P is black, we are at least one step closer
 482                      to the root and we'll try again the next iteration.  */
 483                   q->red = 1;
 484                   r = p;
 485                 }
 486               else
 487                 {
 488                   /* Q is black, one of Q's successors is red.  We can
 489                      repair the tree with one operation and will exit the
 490                      loop afterwards.  */
 491                   if (q->right == NULL || !q->right->red)
 492                     {
 493                       /* The left one is red.  We perform the same action as
 494                          in maybe_split_for_insert where two red edges are
 495                          adjacent but point in different directions:
 496                          Q's left successor (let's call it Q2) becomes the
 497                          top of the subtree we are looking at, its parent (Q)
 498                          and grandparent (P) become its successors. The former
 499                          successors of Q2 are placed below P and Q.
 500                          P becomes black, and Q2 gets the color that P had.
 501                          This changes the black edge count only for node R and
 502                          its successors.  */
 503                       node q2 = q->left;
 504                       q2->red = p->red;
 505                       p->right = q2->left;
 506                       q->left = q2->right;
 507                       q2->right = q;
 508                       q2->left = p;
 509                       *pp = q2;
 510                       p->red = 0;
 511                     }
 512                   else
 513                     {
 514                       /* It's the right one.  Rotate P left. P becomes black,
 515                          and Q gets the color that P had.  Q's right successor
 516                          also becomes black.  This changes the black edge
 517                          count only for node R and its successors.  */
 518                       q->red = p->red;
 519                       p->red = 0;
 520
 521                       q->right->red = 0;
 522
 523                       /* left rotate p */
 524                       p->right = q->left;
 525                       q->left = p;
 526                       *pp = q;
 527                     }
 528
 529                   /* We're done.  */
 530                   sp = 1;
 531                   r = NULL;
 532                 }
 533             }
 534           else
 535             {
 536               /* Comments: see above.  */
 537               q = p->left;
 538               if (q->red)
 539                 {
 540                   q->red = 0;
 541                   p->red = 1;
 542                   p->left = q->right;
 543                   q->right = p;
 544                   *pp = q;
 545                   nodestack[sp++] = pp = &q->right;
 546                   q = p->left;
 547                 }
 548               if ((q->right == NULL || !q->right->red)
 549                        && (q->left == NULL || !q->left->red))
 550                 {
 551                   q->red = 1;
 552                   r = p;
 553                 }
 554               else
 555                 {
 556                   if (q->left == NULL || !q->left->red)
 557                     {
 558                       node q2 = q->right;
 559                       q2->red = p->red;
 560                       p->left = q2->right;
 561                       q->right = q2->left;
 562                       q2->left = q;
 563                       q2->right = p;
 564                       *pp = q2;
 565                       p->red = 0;
 566                     }
 567                   else
 568                     {
 569                       q->red = p->red;
 570                       p->red = 0;
 571                       q->left->red = 0;
 572                       p->left = q->right;
 573                       q->right = p;
 574                       *pp = q;
 575                     }
 576                   sp = 1;
 577                   r = NULL;
 578                 }
 579             }
 580           --sp;
 581         }
 582       if (r != NULL)
 583         r->red = 0;
 584     }
 585
 586   free (unchained);
 587   return retval;
 588 }
 589 weak_alias (__tdelete, tdelete)
 590
 591
 592 /* Walk the nodes of a tree.
 593    ROOT is the root of the tree to be walked, ACTION the function to be
 594    called at each node.  LEVEL is the level of ROOT in the whole tree.  */
 595 static void
 596 internal_function
 597 trecurse (const void *vroot, __action_fn_t action, int level)
 598 {
 599   const_node root = (const_node) vroot;
 600
 601   if (root->left == NULL && root->right == NULL)
 602     (*action) (root, leaf, level);
 603   else
 604     {
 605       (*action) (root, preorder, level);
 606       if (root->left != NULL)
 607         trecurse (root->left, action, level + 1);
 608       (*action) (root, postorder, level);
 609       if (root->right != NULL)
 610         trecurse (root->right, action, level + 1);
 611       (*action) (root, endorder, level);
 612     }
 613 }
 614
 615
 616 /* Walk the nodes of a tree.
 617    ROOT is the root of the tree to be walked, ACTION the function to be
 618    called at each node.  */
 619 void
 620 __twalk (const void *vroot, __action_fn_t action)
 621 {
 622   const_node root = (const_node) vroot;
 623
 624   CHECK_TREE (root);
 625
 626   if (root != NULL && action != NULL)
 627     trecurse (root, action, 0);
 628 }
 629 weak_alias (__twalk, twalk)
 630
 631
 632
 633 /* The standardized functions miss an important functionality: the
 634    tree cannot be removed easily.  We provide a function to do this.  */
 635 static void
 636 internal_function
 637 tdestroy_recurse (node root, __free_fn_t freefct)
 638 {
 639   if (root->left != NULL)
 640     tdestroy_recurse (root->left, freefct);
 641   if (root->right != NULL)
 642     tdestroy_recurse (root->right, freefct);
 643   (*freefct) ((void *) root->key);
 644   /* Free the node itself.  */
 645   free (root);
 646 }
 647
 648 void
 649 __tdestroy (void *vroot, __free_fn_t freefct)
 650 {
 651   node root = (node) vroot;
 652
 653   CHECK_TREE (root);
 654
 655   if (root != NULL)
 656     tdestroy_recurse (root, freefct);
 657 }
 658 weak_alias (__tdestroy, tdestroy)