misc/tsearch.c

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