root/maint/gnulib/lib/tsearch.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. check_tree_recurse
  2. check_tree
  3. maybe_split_for_insert
  4. __tsearch
  5. weak_alias
  6. weak_alias
  7. weak_alias
  8. __twalk
  9. weak_alias
  10. __tdestroy

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

/* [previous][next][first][last][top][bottom][index][help] */