chiark - git - mdw - xyla/blob - rbtree.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3
   4 #include "internal.h"
   5 #include "rbtree.h"
   6
   7 /* --- @check_recurse@ --- *
   8  *
   9  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
  10  *              @struct bstnode *const *root@ = the tree we're checking
  11  *              @const struct rbnode *parent@ = the node's parent, or null if
  12  *                      we're looking at the root node
  13  *              @const struct rbnode *lbound, *rbound@ = left and right bound
  14  *                      nodes, i.e., the closest ancestors from which the
  15  *                      current node can be reached by following a right or
  16  *                      left link, respectively; one or other of these is
  17  *                      equal to @parent@
  18  *              @const struct rbnode *node@ = the node we're looking at now,
  19  *                      which may be null
  20  *              @int blkht@ = the number of black nodes on the path to the
  21  *                      current node -- but not including it
  22  *              @int *tree_blkht_inout@ = address of the reference black-
  23  *                      height for the tree, since this ought to be the same
  24  *                      for all paths to the leaves; this is initially %$-1$%
  25  *                      if no expected height was passed to @rbtree_check@
  26  *              @void *arg@ = argument to pass to check function
  27  *
  28  * Returns:     Zero if everything was OK, %$-1$% if problems were found and
  29  *              reported.
  30  *
  31  * Use:         Recursively examine a subtree of a red-black tree, checking
  32  *              that it satisfies all of the necessary invariants.
  33  */
  34
  35 static int check_recurse(struct bstree_nodecls *cls,
  36                          struct bstnode *const *root,
  37                          const struct rbnode *parent,
  38                          const struct rbnode *lbound,
  39                          const struct rbnode *rbound,
  40                          const struct rbnode *node,
  41                          int blkht, int *tree_blkht_inout,
  42                          void *arg)
  43 {
  44   bstree_idfn *idfn = cls->ops->id;
  45   bstree_chkfn *chkfn = cls->ops->chk;
  46   int rc = 0;
  47
  48   if (!node) {
  49     /* We've fallen off the bottom of the tree. */
  50
  51     /* The black-height of the tree should be the same for every path from
  52      * root to leaf.  If we've not previously established the black height
  53      * for this tree, then we do this now.  Otherwise, check that we get the
  54      * same answer as last time.
  55      */
  56     if (*tree_blkht_inout == -1)
  57       *tree_blkht_inout = blkht;
  58     else if (*tree_blkht_inout != blkht) {
  59       fprintf(stderr, "RBTREE %p BUG: ", (void *)root);
  60       if (!parent) fputs("empty tree", stderr);
  61       else {
  62         fputs("leaf node ", stderr);
  63         if (cls->ops->id) cls->ops->id(cls, &parent->_bst, stderr);
  64         else fprintf(stderr, "%p", (void*)parent);
  65       }
  66       fprintf(stderr, " black-height %d /= %d\n", blkht, *tree_blkht_inout);
  67       rc = -1;
  68     }
  69
  70     /* Check that the user is happy with this leaf. */
  71     if (chkfn &&
  72         chkfn(cls, root,
  73               parent ? &parent->_bst : 0,
  74               lbound ? &lbound->_bst : 0,
  75               rbound ? &rbound->_bst : 0,
  76               node ? &node->_bst : 0, BSTCHK_LEAF,
  77               arg))
  78       rc = -1;
  79   } else {
  80     /* We have a valid node. */
  81
  82     /* If the node is black, then increment the black-height here.  (Recall
  83      * that the argument doesn't include this node.)  If the node is red,
  84      * then check that our parent wasn't also red -- and that we're not at
  85      * the root.
  86      */
  87     if (!(node->f&RBF_RED))
  88       blkht++;
  89     else if (!parent) {
  90       fprintf(stderr, "RBTREE %p BUG: root ", (void *)root);
  91       if (idfn) idfn(cls, &node->_bst, stderr);
  92       else fprintf(stderr, "%p", (void*)node);
  93       fputs(" is red\n", stderr);
  94       rc = -1;
  95     } else if (parent->f&RBF_RED) {
  96       fprintf(stderr, "RBTREE %p BUG: red node ", (void *)root);
  97       if (idfn) idfn(cls, &node->_bst, stderr);
  98       else fprintf(stderr, "%p", (void*)node);
  99       fputs(" has red parent ", stderr);
 100       if (idfn) idfn(cls, &parent->_bst, stderr);
 101       else fprintf(stderr, "%p", (void*)parent);
 102       putc('\n', stderr);
 103       rc = -1;
 104     }
 105
 106     /* Check the subtrees recursively. */
 107     if (chkfn &&
 108         chkfn(cls, root,
 109               parent ? &parent->_bst : 0,
 110               lbound ? &lbound->_bst : 0,
 111               rbound ? &rbound->_bst : 0,
 112               node ? &node->_bst : 0, BSTCHK_BEFORE,
 113               arg))
 114       rc = -1;
 115     if (check_recurse(cls, root, node, lbound, node,
 116                       (const struct rbnode *)node->_bst.left,
 117                       blkht, tree_blkht_inout, arg))
 118       rc = -1;
 119     if (chkfn &&
 120         chkfn(cls, root,
 121               parent ? &parent->_bst : 0,
 122               lbound ? &lbound->_bst : 0,
 123               rbound ? &rbound->_bst : 0,
 124               node ? &node->_bst : 0, BSTCHK_MID,
 125               arg))
 126       rc = -1;
 127     if (check_recurse(cls, root, node, node, rbound,
 128                       (const struct rbnode *)node->_bst.right,
 129                       blkht, tree_blkht_inout, arg))
 130       rc = -1;
 131     if (chkfn &&
 132         chkfn(cls, root,
 133               parent ? &parent->_bst : 0,
 134               lbound ? &lbound->_bst : 0,
 135               rbound ? &rbound->_bst : 0,
 136               node ? &node->_bst : 0, BSTCHK_AFTER,
 137               arg))
 138       rc = -1;
 139   }
 140
 141   /* All done. */
 142   return (rc);
 143 }
 144
 145 /* --- @rbtree_check@ --- *
 146  *
 147  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 148  *              @struct rbnode *const *root@ = root pointer that we're
 149  *                      checking
 150  *              @int blkht@ = expected black-height for tree, or %$-1$% if
 151  *                      unknown
 152  *              @void *arg@ = argument to pass to check function
 153  *
 154  * Returns:     Zero if everything was OK, %$-1$% if problems were found and
 155  *              reported.
 156  *
 157  * Use:         Recursively examine a red-black tree, checking that it
 158  *              satisfies all of the necessary invariants.
 159  */
 160
 161 int rbtree_check(struct bstree_nodecls *cls,
 162                  struct bstnode *const *root, int blkht, void *arg)
 163 {
 164   return (check_recurse(cls, root, 0, 0, 0,
 165                         (const struct rbnode *)*root,
 166                         0, &blkht, arg));
 167 }
 168
 169 /* --- @rbtree_height@ --- *
 170  *
 171  * Arguments:   @const struct rbnode *node@ = pointer to a tree node
 172  *
 173  * Returns:     The `black height' for the (sub)tree rooted at @node@.  This
 174  *              is primarily useful as input to @rbtree_join@ and
 175  *              @rbtree_split@.
 176  */
 177
 178 int rbtree_height(const struct rbnode *node)
 179 {
 180   int blkht = 0;
 181
 182   while (node) {
 183     if (!(node->f&RBF_RED)) blkht++;
 184     node = (const struct rbnode *)node->_bst.left;
 185   }
 186   return (blkht);
 187 }
 188
 189 /* --- @rbtree_lookup@ --- *
 190  *
 191  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 192  *              @struct bstnode *root@ = pointer to root node
 193  *              @void *arg@ = argument to the navigation function
 194  *
 195  * Returns:     Pointer to the matching node, or null if it couldn't be
 196  *              found.
 197  *
 198  * Use:         Search for a node within the tree according to the navigation
 199  *              function.
 200  */
 201
 202 void *rbtree_lookup(struct bstree_nodecls *cls,
 203                     struct bstnode *root, void *arg)
 204   { return (bstree_lookup(cls, root, arg)); }
 205
 206 /* --- @rbtree_probe@ --- *
 207  *
 208  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 209  *              @struct bstnode **root@ = pointer to root link
 210  *              @const void *search_key@ = the key to search for
 211  *              @struct rbpath *path@ = path to fill in
 212  *
 213  * Returns:     Pointer to the matching node, or null if it couldn't be
 214  *              found.
 215  *
 216  * Use:         Search for a node within the tree according to the navigation
 217  *              function, recording the search path  This can be used later,
 218  *              e.g., by @rbtree_insert@ to insert a new node if none was
 219  *              found, or by @rbtree_remove@ to remove the node that was
 220  *              found.
 221  */
 222
 223 void *rbtree_probe(struct bstree_nodecls *cls,
 224                    struct bstnode **root, void *arg, struct rbpath *path)
 225   { return (bstree_probe(cls, root, arg, path->p, &path->k)); }
 226
 227 /* --- @rbtree_inititer@ --- *
 228  *
 229  * Arguments:   @struct bstnode *root@ = pointer to the tree header
 230  *              @struct rbiter *it@ = pointer to iterator to initialize
 231  *
 232  * Returns:     ---
 233  *
 234  * Use:         Initialize an iterator.
 235  */
 236
 237 void rbtree_inititer(struct bstnode *root, struct rbiter *it)
 238   { bstree_inititer(root, it->stack, &it->sp); }
 239
 240 /* --- @rbtree_next@ --- *
 241  *
 242  * Arguments:   @struct rbiter *it@ = pointer to iterator
 243  *
 244  * Returns:     A pointer to the next node in ascending order, or null
 245  *              if no more nodes remain.
 246  *
 247  * Use:         Advances a tree iterator.  Inserting or removing elements
 248  *              invalidates the iterator.  As a special exception, it is
 249  *              permitted to free all of the nodes by iterating over the tree
 250  *              in the obvious manner:
 251  *
 252  *                      @rbtree_inititer(tree, &it);@
 253  *                      @for (;;) {@
 254  *                        @node = rbtree_next(&it); if (!node) break;@
 255  *                        @free(node);@
 256  *                      @}@
 257  *
 258  *              At this point, the tree header structure is left in an
 259  *              invalid state, and must not be used; it is, however, safe to
 260  *              discard, since it holds no resources.
 261  */
 262
 263 void *rbtree_next(struct rbiter *it)
 264   { return ((struct rbnode *)bstree_next(it->stack, &it->sp)); }
 265
 266 /* --- @rbtree_firstpath@, @rbtree_lastpath@ --- *
 267  *
 268  * Arguments:   @struct bstnode **root@ = address of the tree root link
 269  *              @struct rbpath *path@ = path to fill in
 270  *
 271  * Returns:     Pointer to the requested node, or null if the tree is empty.
 272  *
 273  * Use:         Return the first or last node in the tree, as ordered by
 274  *              their keys, together with a path to the requested node, which
 275  *              can be used to remove them, or to navigate to other nodes in
 276  *              the tree.
 277  */
 278
 279 void *rbtree_firstpath(struct bstnode **root, struct rbpath *path)
 280   { return (bstree_firstpath(root, path->p, &path->k)); }
 281
 282 void *rbtree_lastpath(struct bstnode **root, struct rbpath *path)
 283   { return (bstree_lastpath(root, path->p, &path->k)); }
 284
 285 /* --- @rbtree_nextpath@, @rbtree_prevpath@ --- *
 286  *
 287  * Arguments:   @struct rbpath *path@ = path to update
 288  *
 289  * Returns:     Pointer to the requested node, or null if the tree is empty
 290  *              or the path is already positioned at the relevant extreme.
 291  *
 292  * Use:         Return the next or previous node in the tree, as ordered by
 293  *              their keys, together with a path to the requested node, which
 294  *              can be used to remove them, or to navigate to other nodes in
 295  *              the tree.
 296  *
 297  *              If the path is full, i.e., refers to an existing node, then
 298  *              the functions return that node's successor or predecessor.
 299  *              If the path is empty, i.e., refers to a space between nodes
 300  *              where a new node can be inserted, then the functions return
 301  *              the node at the upper or lower end of the gap, unless the
 302  *              `gap' is actually at an extreme of the tree and no such node
 303  *              exists.  In the latter case, a null pointer is returned.
 304  *              The path is modified to refer to the new node, if any, or to
 305  *              the gap at the appropriate extreme of the tree.
 306  */
 307
 308 void *rbtree_nextpath(struct rbpath *path)
 309   { return (bstree_nextpath(path->p, &path->k)); }
 310
 311 void *rbtree_prevpath(struct rbpath *path)
 312   { return (bstree_prevpath(path->p, &path->k)); }
 313
 314 /* --- @rbtree_beforepath@, @rbtree_afterpath@ --- *
 315  *
 316  * Arguments:   @struct rbpath *path@ = path to update
 317  *
 318  * Returns:     ---
 319  *
 320  * Use:         Advance the path to just before or after the current node.
 321  *              The path thereby becomes empty, suitable to insert an element
 322  *              or split the tree just before or after the previously
 323  *              selected node.
 324  */
 325
 326 void rbtree_afterpath(struct rbpath *path)
 327   { bstree_afterpath(path->p, &path->k); }
 328
 329 void rbtree_beforepath(struct rbpath *path)
 330   { bstree_beforepath(path->p, &path->k); }
 331
 332 /* --- @rbtree_replace@ --- *
 333  *
 334  * Arguments:   @struct rbpath *path@ = pointer to a full path
 335  *              @struct rbnode *node@ = pointer to replacement node
 336  *
 337  * Returns:     ---
 338  *
 339  * Use:         Replace the node identified by the @path@ with the given
 340  *              @node@.  The replacement @node@ should have the same (equal,
 341  *              according to the node-class comparison function) key as the
 342  *              node it replaces, and %%\emph{must}%% be strictly between the
 343  *              keys of the old node's predecessor and successor.  The node's
 344  *              links need not be initialized.  Paths and iterators are not
 345  *              invalidated.
 346  */
 347
 348 void rbtree_replace(struct rbpath *path, struct rbnode *node)
 349 {
 350   struct rbnode *old_node;
 351   int k = path->k;
 352
 353   old_node = (struct rbnode *)*path->p[k]; assert(old_node);
 354
 355   node->_bst = old_node->_bst;
 356   node->f = (node->f&~RBF_RED) | (old_node->f&RBF_RED);
 357 }
 358
 359 /* --- @rbtree_insert@ --- *
 360  *
 361  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 362  *              @struct rbpath *path@ = pointer to an empty path
 363  *              @struct rbnode *node@ = the new node to add
 364  *
 365  * Returns:     Adjustment (%$0$% or %$+1$%) to the tree black-height.
 366  *
 367  * Use:         Add a new node to the tree, in the place determined by the
 368  *              empty path.  The @new_node@'s key must be equal to the key
 369  *              passed to @rbtree_probe@ when it produced the path.
 370  *
 371  *              The new node is not copied, and its storage must remain valid
 372  *              until the node is removed or the tree is discarded.
 373  */
 374
 375 int rbtree_insert(struct bstree_nodecls *cls,
 376                   struct rbpath *path, struct rbnode *node)
 377 {
 378   struct rbnode *p, *n, *c, *l, *r;
 379   struct bstnode **clink, **nlink, **plink;
 380   bstree_updfn *updfn = cls->ops->upd;
 381   int k = path->k;
 382
 383   /* Check that the path is well-formed and describes a failed probe. */
 384   clink = path->p[k]; assert(!*clink);
 385
 386   /* Initialize the new node's links and hook it onto the tree. */
 387   node->_bst.left = node->_bst.right = 0; *clink = &node->_bst;
 388
 389   /* If the tree was empty then the new node is going to be the root of the
 390    * tree, which must be black.
 391    */
 392   if (!k) {
 393     node->f &= ~RBF_RED;
 394     if (updfn) updfn(cls, &node->_bst);
 395     return (+1);
 396   }
 397
 398   /* Otherwise we'll provisionally paint the new node red and try to fix
 399    * things up.
 400    */
 401   c = node; c->f |= RBF_RED;
 402   for (;;) {
 403     /* The child node %$c$% is known to be red.  Our focus node %$n$% is the
 404      * child's parent, and it might also be red; this is the only violation
 405      * of the tree invariants, and we're trying to fix it.  In particular,
 406      * %$c$%'s children, if any, are black.  Neither %$c$% nor %$n$% has been
 407      * updated yet.  We'll also be interested in the focus node's parent
 408      * %$p$%.  The focus node's sibling, denoted %$s$% in the diagrams below,
 409      * is also interesting to the theory, but not named explicitly in the
 410      * code itself.
 411      */
 412
 413     /* Retrieve the focus node, which must exist because %$c$% is red and the
 414      * tree root is black.  If the focus node is black then we're done.
 415      */
 416     nlink = path->p[--k]; n = (struct rbnode *)*nlink;
 417     if (!(n->f&RBF_RED)) {
 418       if (updfn) { updfn(cls, &c->_bst); updfn(cls, &n->_bst); }
 419       break;
 420     }
 421
 422     /* Retrieve the focus node's parent %$p$%, which must also exist for the
 423      * same reason.  Note that %$p$% is definitely black, since it has at
 424      * least one red child.
 425      */
 426     plink = path->p[--k]; p = (struct rbnode *)*plink;
 427
 428     /* If the parent has two children and they're both red, then blacken them
 429      * both.  (This approach avoids dealing with all of the symmetry in the
 430      * loop.)  If the parent is the root then we're done, and the tree black-
 431      * height has increased by one; otherwise, redden it and ascend.
 432      *
 433      *                    p                               p
 434      *                     (*)                             ( )
 435      *              n    /     \    s               n    /     \    s
 436      *               ( )         ( )    --->         (*)         (*)
 437      *          c   /   \       /   \           c   /   \       /   \
 438      *           ( )                             ( )
 439      *          /   \                           /   \
 440      */
 441     l = (struct rbnode *)p->_bst.left; r = (struct rbnode *)p->_bst.right;
 442     if (l && r && (l->f&r->f&RBF_RED)) {
 443       V( fprintf(stderr, "RBTREE INSERT red sibling: %s\n",
 444                  k ? "ascend" : "extend tree"); )
 445       l->f &= ~RBF_RED; r->f &= ~RBF_RED;
 446       if (!k) {
 447         if (updfn) {
 448           updfn(cls, &c->_bst); updfn(cls, &n->_bst);
 449           updfn(cls, &p->_bst);
 450         }
 451         return (+1);
 452       }
 453       if (updfn) { updfn(cls, &c->_bst); updfn(cls, &n->_bst); }
 454       p->f |= RBF_RED; c = p; clink = plink; continue;
 455     }
 456
 457     /* Otherwise, we have some links to rewrite. */
 458     if (nlink == &p->_bst.left)
 459 #define FIXUP_INSERT(left, l, right, r) do {                            \
 460       /* The focus node is its parent's left child.  There are two      \
 461        * cases, depending on whether %$c$% is the focus node's left or  \
 462        * right child.  It's safe to redden %$p$% here: if the focus     \
 463        * node has a red sibling then we'd have ascended the tree above. \
 464        */                                                               \
 465                                                                         \
 466       if (clink == &n->_bst.left) {                                     \
 467         /*                p                                             \
 468          *                 (*)                        n                 \
 469          *          n    /     \                       (*)              \
 470          *           ( )                --->    c    /     \    p       \
 471          *      c   /   \                        ( )         ( )        \
 472          *       ( )                            /   \       /   \       \
 473          *      /   \                                                   \
 474          */                                                             \
 475                                                                         \
 476         V( fputs("RBTREE INSERT zig-zig (" #left " child)\n", stderr); ) \
 477         p->_bst.left = n->_bst.right; n->_bst.right = &p->_bst;         \
 478         n->f &= ~RBF_RED; p->f |= RBF_RED;                              \
 479         if (updfn) {                                                    \
 480           updfn(cls, &c->_bst); updfn(cls, &p->_bst);                   \
 481           updfn(cls, &n->_bst);                                         \
 482         }                                                               \
 483         *plink = &n->_bst;                                              \
 484       } else {                                                          \
 485         /*                p                                             \
 486          *                 (*)                        c                 \
 487          *          n    /     \                       (*)              \
 488          *           ( )                --->    n    /     \    p       \
 489          *          /   \   c                    ( )         ( )        \
 490          *               ( )                    /   \       /   \       \
 491          *              /   \                                           \
 492          */                                                             \
 493                                                                         \
 494         V( fputs("RBTREE INSERT zig-zag (" #left " child)\n", stderr); ) \
 495         n->_bst.right = c->_bst.left; c->_bst.left = &n->_bst;          \
 496         p->_bst.left = c->_bst.right; c->_bst.right = &p->_bst;         \
 497         c->f &= ~RBF_RED; p->f |= RBF_RED;                              \
 498         if (updfn) {                                                    \
 499           updfn(cls, &n->_bst); updfn(cls, &p->_bst);                   \
 500           updfn(cls, &c->_bst);                                         \
 501         }                                                               \
 502         *plink = &c->_bst;                                              \
 503       }                                                                 \
 504 } while (0)
 505       FIXUP_INSERT(left, l, right, r);
 506     else
 507       FIXUP_INSERT(right, r, left, l);
 508 #undef FIXUP_INSERT
 509
 510     /* Whatever happened above, we're now done: the parent is still black. */
 511     break;
 512   }
 513
 514   /* Follow the rest of the path up to the root, updating the nodes. */
 515   if (updfn) while (k) updfn(cls, *path->p[--k]);
 516
 517   /* We're done.  The overall black-height only changes if we reach the root,
 518    * and we'd have returned already if that happened.
 519    */
 520   return (0);
 521 }
 522
 523 /* --- @rbtree_remove@ --- *
 524  *
 525  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 526  *              @struct rbpath *path@ = pointer to a full path
 527  *
 528  * Returns:     Adjustment (%$0$% or %$-1$%) to the tree black-height.
 529  *
 530  * Use:         Removes the node identified by the path.  The node was
 531  *              allocated by the caller, and should be freed by the caller in
 532  *              whatever way is appropriate.
 533  */
 534
 535 int rbtree_remove(struct bstree_nodecls *cls, struct rbpath *path)
 536 {
 537   struct rbnode *n, *p, *s, *t, *l, *r;
 538   struct bstnode *del, *subst, *replace, **nlink, **plink;
 539   bstree_updfn *updfn = cls->ops->upd;
 540   int k;
 541   unsigned f, ff;
 542
 543   /* Unlink the node from the tree. */
 544   bstree_remove(&del, &subst, &replace, path->p, &path->k);
 545   t = (struct rbnode *)del; f = t->f;
 546   s = (struct rbnode *)subst;
 547   n = (struct rbnode *)replace;
 548   k = path->k;
 549
 550   /* If the node was substituted, then fix up the colouring. */
 551   if (s) { ff = f; f = s->f; s->f = (f&~RBF_RED) | (ff&RBF_RED); }
 552
 553   /* We've cut out out a node %$t$%, and replaced it with one of its
 554    * `children' %$n$% -- which might, in fact, be null.  If %$t$% was black,
 555    * then, to maintain the invariant, we (mentally) assign an additional dose
 556    * of blackness to %$n$%.  Our task will be to take one of these blackness
 557    * doses and move it somewhere safe -- either a red ancestor, or the root,
 558    * where we can just safely forget about it.
 559    */
 560   if (f&RBF_RED) {
 561     /* If the node we've cut out was actually red then we can just forget
 562      * about it.
 563      */
 564
 565     if (updfn && n) updfn(cls, &n->_bst);
 566   } else if (n && (n->f&RBF_RED)) {
 567     /* If %$n$% is actually a real node, and it's red, then we can just
 568      * blacken it.
 569      */
 570
 571     n->f &= ~RBF_RED;
 572     if (updfn && n) updfn(cls, &n->_bst);
 573   } else {
 574     /* It looks like we have some actual work to do. */
 575
 576     nlink = path->p[k];
 577     for (;;) {
 578       /* The node %$n$% is doubly black, and we must offload one of the doses
 579        * of blackness somewhere else.
 580        */
 581
 582       if (!k) {
 583         /* The node we're looking at is, in fact, the root.  The extra
 584          * blackness affects all paths to the leaves equally, so we can can
 585          * just throw it away without anyone noticing, except that the tree
 586          * black-height has decreased.
 587          */
 588
 589         V( fputs("RBTREE REMOVE shorten tree\n", stderr); )
 590         return (-1);
 591       }
 592
 593       /* Not the root, so we can find a parent node. */
 594       plink = path->p[--k]; p = (struct rbnode *)*plink;
 595
 596       /* In fact, because we have at least one blackness dose, we must have a
 597        * live sibling, with a subtree containing at least one black node.
 598        * Split into two main cases according to whether we're on the left or
 599        * right.
 600        */
 601       if (nlink == &p->_bst.left)
 602 #define FIXUP_REMOVE(left, l, right, r) do {                            \
 603         /* We're the left child. */                                     \
 604                                                                         \
 605         s = (struct rbnode *)p->_bst.right;                             \
 606         if (s->f&RBF_RED) {                                             \
 607           /* Our sibling is red.  The parent must then be black, and    \
 608            * the sibling must have two black children, our node's       \
 609            * niblings, though we're only interested in the left-hand    \
 610            * one, which we call %$t$%.                                  \
 611            */                                                           \
 612                                                                         \
 613           t = (struct rbnode *)s->_bst.left;                            \
 614           l = (struct rbnode *)t->_bst.left;                            \
 615           r = (struct rbnode *)t->_bst.right;                           \
 616                                                                         \
 617           if (r && r->f&RBF_RED) {                                      \
 618             /* The left nibling has a red right child.  The following   \
 619              * rearrangement discharges the surplus black dose.         \
 620              *                                                          \
 621              *        p                                       s         \
 622              *         (*)                                     (*)      \
 623              * n     /     \    s                       t    /     \    \
 624              *  (* *)        ( )        --->             ( )            \
 625              *  /   \   t   /   \                   p   /   \   r       \
 626              *           (*)                         (*)     (*)        \
 627              *          /   \   r               n   /   \   /   \       \
 628              *               ( )                 (*)                    \
 629              *              /   \               /   \                   \
 630              */                                                         \
 631                                                                         \
 632             V( fputs("RBTREE REMOVE red sibling, "                      \
 633                      "outer red great-nibling (" #left " child)\n",     \
 634                      stderr); )                                         \
 635             p->_bst.right = l ? &l->_bst : 0;                           \
 636             t->_bst.left = &p->_bst; s->_bst.left = &t->_bst;           \
 637             s->f &= ~RBF_RED; t->f |= RBF_RED; r->f &= ~RBF_RED;        \
 638             if (updfn) {                                                \
 639               updfn(cls, &p->_bst); updfn(cls, &t->_bst);               \
 640               updfn(cls, &s->_bst);                                     \
 641             }                                                           \
 642           } else if (l && l->f&RBF_RED) {                               \
 643             /* The left nibling has a red left child.  The following    \
 644              * rearrangement discharges the surplus black dose.         \
 645              *                                                          \
 646              *        p                                       s         \
 647              *         (*)                                     (*)      \
 648              * n     /     \    s                       l    /     \    \
 649              *  (* *)        ( )        --->             ( )            \
 650              *  /   \   t   /   \                   p   /   \   t       \
 651              *           (*)                         (*)     (*)        \
 652              *      l   /   \                   n   /   \   /   \       \
 653              *       ( )                         (*)                    \
 654              *      /   \                       /   \                   \
 655              */                                                         \
 656                                                                         \
 657             V( fputs("RBTREE REMOVE red sibling, "                      \
 658                      "inner red great-nibling (" #left " child)\n",     \
 659                      stderr); )                                         \
 660             p->_bst.right = l->_bst.left; l->_bst.left = &p->_bst;      \
 661             t->_bst.left = l->_bst.right; l->_bst.right = &t->_bst;     \
 662             s->_bst.left = &l->_bst; s->f &= ~RBF_RED;                  \
 663             if (updfn) {                                                \
 664               updfn(cls, &p->_bst); updfn(cls, &t->_bst);               \
 665               updfn(cls, &l->_bst); updfn(cls, &s->_bst);               \
 666             }                                                           \
 667           } else {                                                      \
 668             /* The left nibling has no red children.  The following     \
 669              * rearrangement discharges the surplus black dose:         \
 670              * reddening %$t$% is safe because it has no red children.  \
 671              *                                                          \
 672              *        p                                   s             \
 673              *         (*)                                 (*)          \
 674              * n     /     \    s                   p    /     \        \
 675              *  (* *)        ( )        --->         (*)                \
 676              *  /   \   t   /   \               n   /   \   t           \
 677              *           (*)                     (*)     ( )            \
 678              *          /   \                   /   \   /   \           \
 679              */                                                         \
 680                                                                         \
 681             V( fputs("RBTREE REMOVE red sibling, "                      \
 682                      "no red great-nibling (" #left " child)\n",        \
 683                      stderr); )                                         \
 684             p->_bst.right = &t->_bst; s->_bst.left = &p->_bst;          \
 685             s->f &= ~RBF_RED; t->f |= RBF_RED;                          \
 686             if (updfn) { updfn(cls, &p->_bst); updfn(cls, &s->_bst); }  \
 687           }                                                             \
 688                                                                         \
 689           /* Adjust the parent link.  In all cases, the invariant has   \
 690            * been properly restored.                                    \
 691            */                                                           \
 692           *plink = &s->_bst; goto update;                               \
 693         } else {                                                        \
 694           /* Our sibling is black.  We can't deduce the colour of the   \
 695            * parent node.                                               \
 696            */                                                           \
 697                                                                         \
 698           l = (struct rbnode *)s->_bst.left;                            \
 699           r = (struct rbnode *)s->_bst.right;                           \
 700                                                                         \
 701           if (r && r->f&RBF_RED) {                                      \
 702             /* The sibling has a red right child.  The following        \
 703              * rearrangement discharges the surplus black dose.         \
 704              *                                                          \
 705              *        p                                    s            \
 706              *         (?)                                  (?)         \
 707              * n     /     \   s                     p    /     \   r   \
 708              *  (* *)       (*)         --->          (*)        (*)    \
 709              *  /   \      /   \   r            n    /   \      /   \   \
 710              *                  ( )              (*)                    \
 711              *                 /   \            /   \                   \
 712              */                                                         \
 713                                                                         \
 714             V( fputs("RBTREE REMOVE black sibling, "                    \
 715                      "outer red nibling (" #left " child)\n",           \
 716                      stderr); )                                         \
 717             p->_bst.right = l ? &l->_bst : 0; s->_bst.left = &p->_bst;  \
 718             s->f |= p->f&RBF_RED; p->f &= ~RBF_RED; r->f &= ~RBF_RED;   \
 719             if (updfn) { updfn(cls, &p->_bst); updfn(cls, &s->_bst); }  \
 720             *plink = &s->_bst; goto update;                             \
 721           } else if (l && l->f&RBF_RED) {                               \
 722             /* The sibling has a red left child.  The following         \
 723              * rearrangement discharges the surplus black dose.         \
 724              *                                                          \
 725              *        p                                    l            \
 726              *         (?)                                  (?)         \
 727              * n     /     \   s                     p    /     \   s   \
 728              *  (* *)       (*)         --->          (*)        (*)    \
 729              *  /   \  l   /   \                n    /   \      /   \   \
 730              *          ( )                      (*)                    \
 731              *         /   \                    /   \                   \
 732              */                                                         \
 733                                                                         \
 734             V( fputs("RBTREE REMOVE black sibling, "                    \
 735                      "inner red nibling (" #left " child)\n",           \
 736                      stderr); )                                         \
 737             p->_bst.right = l->_bst.left; l->_bst.left = &p->_bst;      \
 738             s->_bst.left = l->_bst.right; l->_bst.right = &s->_bst;     \
 739             l->f &= ~RBF_RED | (p->f&RBF_RED); p->f &= ~RBF_RED;        \
 740             if (updfn) {                                                \
 741               updfn(cls, &p->_bst); updfn(cls, &s->_bst);               \
 742               updfn(cls, &l->_bst);                                     \
 743             }                                                           \
 744             *plink = &l->_bst; goto update;                             \
 745           } else {                                                      \
 746             /* The sibling has no red children.  That means that it's   \
 747              * safe to make it red, so we can push the extra black      \
 748              * dose up into the parent.  If the parent was previously   \
 749              * red, then we're done; otherwise, we ascend the tree.     \
 750              *                                                          \
 751              *        p                                    p            \
 752              *         (?)                                 (? *)        \
 753              * n     /     \   s                     n    /     \   s   \
 754              *  (* *)       (*)         --->          (*)        ( )    \
 755              *  /   \      /   \                     /   \      /   \   \
 756              */                                                         \
 757                                                                         \
 758             V( fprintf(stderr, "RBTREE REMOVE black sibling, "          \
 759                        "%s parent, no red nibling (" #left " child)\n", \
 760                        p->f&RBF_RED ? "red" : "black"); )               \
 761             s->f |= RBF_RED;                                            \
 762             if (updfn) updfn(cls, &p->_bst);                            \
 763             if (p->f&RBF_RED) { p->f &= ~RBF_RED; goto update; }        \
 764             n = p; nlink = plink;                                       \
 765           }                                                             \
 766         }                                                               \
 767 } while (0)
 768         FIXUP_REMOVE(left, l, right, r);
 769       else
 770         FIXUP_REMOVE(right, r, left, l);
 771 #undef FIXUP_REMOVE
 772     }
 773   }
 774
 775   /* Follow the rest of the path up to the root, updating the nodes. */
 776 update:
 777   if (updfn) while (k) updfn(cls, *path->p[--k]);
 778   return (0);
 779 }
 780
 781 /* --- @rbtree_join@ --- *
 782  *
 783  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 784  *              @struct bstnode **root_out@ = address to store the link to
 785  *                      the root of the combined tree
 786  *              @struct bstnode **left@ = address containing the current
 787  *                      root of the left tree
 788  *              @int lht@ = black-height of the left tree, or %$-1$% if
 789  *                      unknown
 790  *              @struct bstnode *mid@ = pointer to middle node, or null
 791  *              @struct bstnode **right@ = address containing the current
 792  *                      root of the right tree
 793  *              @int rht@ = black-height of the right tree, or %$-1$% if
 794  *                      unknown
 795  *
 796  * Returns:     The black-height of the combined tree.
 797  *
 798  * Use:         Concatenate two trees.
 799  *
 800  *              Every node in the left tree must have a key strictly less
 801  *              than any node of the right tree.  If a middle node is
 802  *              provided, then its key must be greater than that of any node
 803  *              in the left tree, and less than that of any node in the right
 804  *              tree.
 805  *
 806  *              The output is a single tree containing every node in the left
 807  *              and right input trees, together with the middle node, if that
 808  *              is not null.
 809  *
 810  *              The @root_out@ pointer may etestqual either @left@ or @right@
 811  *              (or, indeed, both, only if both are empty).  If @left@ is
 812  *              distinct from @root_out@ then @*left@ set null on exit;
 813  *              similarly, if @right@ is distinct from @root_out@, then
 814  *              @*right@ is set null on exit.
 815  */
 816
 817 int rbtree_join(struct bstree_nodecls *cls,
 818                 struct bstnode **root_out,
 819                 struct bstnode **left, int lht,
 820                 struct bstnode *mid,
 821                 struct bstnode **right, int rht)
 822 {
 823   struct rbnode *m = (struct rbnode *)mid, *p, *n, *s;
 824   struct bstnode **clink, **plink, *root;
 825   bstree_updfn *updfn = cls->ops->upd;
 826   struct rbpath path;
 827   int blkht;
 828
 829   /* Determine the heights of the left and right trees if the caller didn't
 830    * supply them.
 831    */
 832   if (lht < 0) lht = rbtree_height((struct rbnode *)*left);
 833   if (rht < 0) rht = rbtree_height((struct rbnode *)*right);
 834
 835   /* If we're not given a joining node then take one from the right tree.  If
 836    * the right tree is empty, then the join is just the left tree and there's
 837    * nothing to do.
 838    */
 839   if (!m) {
 840     if (!rht) { root = *left; blkht = lht; goto end; }
 841     else if (!lht) { root = *right; blkht = rht; goto end; }
 842     else {
 843       m = rbtree_firstpath(right, &path);
 844       rht += rbtree_remove(cls, &path);
 845     }
 846   }
 847
 848   if (lht == rht) {
 849     /* The trees have the same black-height.  We can just join them the
 850      * stupid way.  The joining node will be the root, so it must be black,
 851      * and the resulting height is one greater than the input heights.
 852      */
 853
 854     V( fputs("RBTREE JOIN equal heights\n", stderr); )
 855     m->_bst.left = *left; m->_bst.right = *right;
 856     m->f &= ~RBF_RED;
 857     if (updfn) updfn(cls, &m->_bst);
 858     root = &m->_bst; blkht = lht + 1;
 859   } else {
 860     if (lht > rht)
 861 #define FIXUP_JOIN(left, lht, right, rht) do {                          \
 862       /* The left tree is taller. */                                    \
 863                                                                         \
 864       /* Find the rightmost subtree in the left tree whose black-       \
 865        * height is equal to the right tree's black-height.              \
 866        */                                                               \
 867       path.k = 0; path.p[0] = clink = left; blkht = lht;                \
 868       for (;;) {                                                        \
 869         n = (struct rbnode *)*clink;                                    \
 870         if (!(n && (n->f&RBF_RED))) {                                   \
 871           if (blkht == rht) break;                                      \
 872           blkht--;                                                      \
 873         }                                                               \
 874         path.p[++path.k] = clink = &n->_bst.right;                      \
 875       }                                                                 \
 876                                                                         \
 877       /* Replace this subtree with the two trees, joined by a red       \
 878        * node.  This will preserve the global black-height invariant,   \
 879        * but may result in two adjacent red nodes.                      \
 880        */                                                               \
 881       *clink = &m->_bst; m->f |= RBF_RED;                               \
 882       m->_bst.left = n ? &n->_bst : 0;                                  \
 883       m->_bst.right = *right;                                           \
 884       if (updfn) updfn(cls, &m->_bst);                                  \
 885                                                                         \
 886       /* Fix up the tree to restore the invariant.  This is a simpler   \
 887        * version of the fix-up in @rbtree_insert@ above.  We get to     \
 888        * throw out a lot of the complexity because we know that our     \
 889        * path runs down the extremity of the taller tree, so, in        \
 890        * particular, we won't need to check which side a node is from   \
 891        * its parent.                                                    \
 892        */                                                               \
 893       blkht = lht;                                                      \
 894       for (;;) {                                                        \
 895                                                                         \
 896         /* Fetch the parent: our child node is red, so it must have     \
 897          * one.  If the parent is black then we're done.                \
 898          */                                                             \
 899         n = (struct rbnode *)*path.p[--path.k];                         \
 900         if (!(n->f&RBF_RED)) {                                          \
 901           if (updfn) updfn(cls, &n->_bst);                              \
 902           break;                                                        \
 903         }                                                               \
 904                                                                         \
 905         /* Our child has a red parent.  That's the new focus node.      \
 906          * Since it's red, it has a black parent.                       \
 907          */                                                             \
 908         plink = path.p[--path.k]; p = (struct rbnode *)*plink;          \
 909                                                                         \
 910         /* If the node has a red sibling then we can blacken this node  \
 911          * and its sibling.  If the parent is the root, then the tree   \
 912          * got taller; otherwise, redden the parent and continue        \
 913          * ascending.                                                   \
 914          */                                                             \
 915         s = (struct rbnode *)p->_bst.left;                              \
 916         if (s && s->f&RBF_RED) {                                        \
 917           V( fprintf(stderr, "RBTREE JOIN red sibling "                 \
 918                      "(" #right " child): %s\n",                        \
 919                      path.k ? "ascend" : "extend tree"); )              \
 920           n->f &= ~RBF_RED; s->f &= ~RBF_RED;                           \
 921           if (updfn) { updfn(cls, &n->_bst); updfn(cls, &p->_bst); }    \
 922           if (!path.k) { blkht++; break; }                              \
 923           p->f |= RBF_RED; continue;                                    \
 924         }                                                               \
 925                                                                         \
 926         /* The node has a red right child and a black parent, but no    \
 927          * red sibling.                                                 \
 928          *                                                              \
 929          *       p                                                      \
 930          *        (*)                                 n                 \
 931          *      /     \    n                           (*)              \
 932          *              ( )             --->    p    /     \    c       \
 933          *             /   \   c                 ( )         ( )        \
 934          *                  ( )                 /   \       /   \       \
 935          *                 /   \                                        \
 936          */                                                             \
 937         V( fputs("RBTREE JOIN no red sibling (" #right " child)\n",     \
 938                  stderr); )                                             \
 939         p->_bst.right = n->_bst.left; n->_bst.left = &p->_bst;          \
 940         n->f &= ~RBF_RED; p->f |= RBF_RED;                              \
 941         if (updfn) { updfn(cls, &p->_bst); updfn(cls, &n->_bst); }      \
 942         *plink = &n->_bst;                                              \
 943         break;                                                          \
 944       }                                                                 \
 945                                                                         \
 946       /* Return the result. */                                          \
 947       root = *left;                                                     \
 948 } while (0)
 949       FIXUP_JOIN(left, lht, right, rht);
 950     else
 951       FIXUP_JOIN(right, rht, left, lht);
 952 #undef FIXUP_JOIN
 953
 954     /* Follow the rest of the path up to the root, updating the nodes. */
 955     if (updfn) while (path.k) updfn(cls, *path.p[--path.k]);
 956   }
 957
 958   /* All done.  Fix up the root pointers and return the new black-height. */
 959 end:
 960   *left = 0; *right = 0; *root_out = root; return (blkht);
 961 }
 962
 963 /* --- @rbtree_split@ --- *
 964  *
 965  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 966  *              @struct bstnode *left_out@ = where to leave the root of the
 967  *                      resulting left tree
 968  *              @int *lht_out@ = where to leave the black-height of the left
 969  *                      tree, or null to discard this information
 970  *              @int *mht_out@ = where to leave the black-height of the
 971  *                      middle node (either zero or one), or null to discard
 972  *                      this information
 973  *              @struct bstnode *rirght_out@ = where to leave the root of the
 974  *                      resulting right tree
 975  *              @int *rht_out@ = where to leave the black-height of the right
 976  *                      tree, or null to discard this information
 977  *              @struct rbpath *path@ = full or empty path at which to split
 978  *                      the tree
 979  *
 980  * Returns:     A pointer to the resulting middle node, or null.
 981  *
 982  * Use:         Split a tree into two at an indicated place.
 983  *
 984  *              The splitting operation produces two trees, a `left tree'
 985  *              containing every node preceding the given path, and a `right
 986  *              tree' containing every node following the path.  If the path
 987  *              is full, i.e., it denotes a node in the input tree, then that
 988  *              becomes the `middle node', which does not appear in either
 989  *              tree, and is returned separately.
 990  */
 991
 992 void *rbtree_split(struct bstree_nodecls *cls,
 993                    struct bstnode **left_out, int *lht_out,
 994                    int *mht_out,
 995                    struct bstnode **right_out, int *rht_out,
 996                    struct rbpath *path)
 997 {
 998   struct bstnode *left, *right, *sub, **next, **link;
 999   struct rbnode *parent, *node, *mid;
1000   int k, blkht, lht, rht, subht;
1001   unsigned f;
1002
1003   /* The basic idea is to work up the tree, following the provided path,
1004    * maintaining left and right trees.  When we come across a node with a
1005    * leftward link, then we join that node and its right subtree onto our
1006    * right tree; and %%\emph{vice-versa}%%.
1007    *
1008    *                       |        *           |
1009    *                  ,----|------'   `---------|-,
1010    *                *      |                    |   *
1011    *          ,---'   `---,|                  ,-|-'   `---,
1012    *        *              |*               *   |           *
1013    *      /   \           /|  \           /   \ |         /   \
1014    *    *       *       *  |    *       *       *       *       *
1015    *   / \     / \     / \ |   / \     / \     /|\     / \     / \
1016    *  *   *   *   *   *   *|  *   *   *   *   * | *   *   *   *   *
1017    *                       |                    |
1018    *
1019    * The conceptual difficulty lies in how to initialize the left and right
1020    * trees.
1021    *
1022    * The other fiddly part is keeping track of the black-heights as we work
1023    * through the tree.
1024    */
1025
1026   /* Retrieve the designated node. */
1027   k = path->k; link = path->p[k]; mid = (struct rbnode *)*link;
1028   if (mid) {
1029     /* The path is full, i.e., it terminates in a link to a node, which will
1030      * be the final mid node.  Initialize the left and right trees to the
1031      * node's left and right subtrees.  Work out their black-heights -- this
1032      * will save effort later, because we know that they'll be equal.
1033      * Forcibly blacken the roots of the trees, and fix the heights as
1034      * necessary.
1035      */
1036
1037     /* Initialize the left and right trees. */
1038     left = mid->_bst.left; right = mid->_bst.right;
1039
1040     /* Initialize the black-heights.  The two subtrees must have the same
1041      * black-height initially, but we must blacken the roots, and that might
1042      * introduce a difference.
1043      */
1044     lht = rht = blkht = rbtree_height((struct rbnode *)left);
1045     if (left) {
1046       node = (struct rbnode *)left;
1047       if (node->f&RBF_RED) { node->f &= ~RBF_RED; lht++; }
1048     }
1049     if (right) {
1050       node = (struct rbnode *)right;
1051       if (node->f&RBF_RED) { node->f &= ~RBF_RED; rht++; }
1052     }
1053
1054     /* Clear the split node's links, so that it's a standalone singleton
1055      * tree.  If the split node is black then its height was one more than
1056      * its children's.  If it's red, then blacken it because it's a root now.
1057      */
1058     mid->_bst.left = mid->_bst.right = 0;
1059     if (!(mid->f&RBF_RED)) blkht++;
1060     else mid->f &= ~RBF_RED;
1061
1062     /* Special case: the split node is the tree root.
1063      *
1064      * This is only `special' because the other case ascends one step higher
1065      * in the tree, so we should do the same here.
1066      */
1067     if (!k) goto end;
1068
1069     /* Prefetch the next node up the path. */
1070     next = path->p[--k]; parent = (struct rbnode *)*next;
1071   } else {
1072     /* The path is empty, i.e., it terminates in a null link, and the final
1073      * mid node will be null.  The obvious thing to do is to initialize the
1074      * left and right trees to be empty, but that will end up doing too much
1075      * work.  If we examine the diagram above, we see that there will be an
1076      * intact subtree on one side of the split line.  Working step-by-step
1077      * risks messing with the structure of that subtree for no benefit: if
1078      * the root of some inner subtree is red then we'll end up blackening it
1079      * because the root of a tree must be black -- but then its height will
1080      * differ from its sibling's when we come to join them together again and
1081      * we'll have to rebalance.
1082      *
1083      * Instead, we note the direction of the final null link.  Every further
1084      * link in the path that's in the same direction means that we're still
1085      * searching for the initial subtree root.
1086      */
1087
1088     /* Special case: the tree is actually empty. */
1089     if (!k) { left = right = 0; lht = rht = 0; goto end; }
1090
1091     /* Retrieve the parent node and split into cases according to the link
1092      * direction.
1093      */
1094     next = path->p[--k]; node = (struct rbnode *)*next; blkht = 0;
1095     if (link == &node->_bst.left)
1096 #define INIT_SPLIT_EMPTY(left, lht, right, rht) do {                    \
1097       /* The null link points leftwards, so the we're searching to      \
1098        * bound the initial right tree.                                  \
1099        */                                                               \
1100                                                                         \
1101       for (;;) {                                                        \
1102                                                                         \
1103         /* We've decided to include the current node in the initial     \
1104          * tree, so update the black-height.                            \
1105          */                                                             \
1106         if (!(node->f&RBF_RED)) blkht++;                                \
1107                                                                         \
1108         /* The current node is the tree root.  There can be nothing     \
1109          * else.                                                        \
1110          */                                                             \
1111         if (!k) {                                                       \
1112           left = 0; lht = 0;                                            \
1113           right = &node->_bst; rht = blkht;                             \
1114           goto end;                                                     \
1115         }                                                               \
1116                                                                         \
1117         /* Ascend the tree and check the link direction. */             \
1118         link = next; next = path->p[--k];                               \
1119         parent = (struct rbnode *)*next;                                \
1120         if (link != &parent->_bst.left) break;                          \
1121         node = parent; link = next;                                     \
1122       }                                                                 \
1123                                                                         \
1124       /* Establish the left and right trees. */                         \
1125       left = 0; lht = 0;                                                \
1126       right = &node->_bst; rht = blkht;                                 \
1127                                                                         \
1128       /* Make sure the root of the right tree is painted black. */      \
1129       if (node->f&RBF_RED) { rht++; node->f &= ~RBF_RED; }              \
1130 } while (0)
1131       INIT_SPLIT_EMPTY(left, lht, right, rht);
1132     else
1133       INIT_SPLIT_EMPTY(right, rht, left, lht);
1134 #undef INIT_SPLIT_EMPTY
1135   }
1136
1137   /* Ascend the tree, accumulating additional material into the left or right
1138    * trees.  This is actually much less complicated than it sounds.
1139    */
1140   for (;;) {
1141     /* The state at this point is a little tricky.
1142      *
1143      * There is a current node; @link@ holds a link to this node, and @blkht@
1144      * is its black-height.  The subtree rooted at this current node has been
1145      * split, resulting in a left tree rooted at @left@, with black-height
1146      * @lht@, and a right tree rooted at @right@, with black-height @rht@,
1147      * and, depending on the initial path, possibly a mid node @mid@.
1148      *
1149      * The node has a @parent@.  The link to the parent is in @next@.  The
1150      * parent and the current node's subling subtree must be accumulated into
1151      * the appropriate left or right tree.  Note that the sibling subtree has
1152      * the same black-height as the current node.
1153      */
1154
1155     /* Take note of the parent node's flags because they'll be clobbered in
1156      * the next step.
1157      */
1158     f = parent->f;
1159
1160     /* Accumulate the parent and the sibling subtree onto the appropriate
1161      * tree.
1162      */
1163     if (link == &parent->_bst.left) {
1164       sub = parent->_bst.right; subht = blkht;
1165       node = (struct rbnode *)sub;
1166       if (node && node->f&RBF_RED) { subht++; node->f &= ~RBF_RED; }
1167       rht = rbtree_join(cls, &right,
1168                         &right, rht, &parent->_bst, &sub, subht);
1169     } else {
1170       sub = parent->_bst.left; subht = blkht;
1171       node = (struct rbnode *)sub;
1172       if (node && node->f&RBF_RED) { subht++; node->f &= ~RBF_RED; }
1173       lht = rbtree_join(cls, &left,
1174                         &sub, subht, &parent->_bst, &left, lht);
1175     }
1176
1177     /* If we've reached the root then we're done. */
1178     if (!k) goto end;
1179
1180     /* Update the black-height. */
1181     if (!(f&RBF_RED)) blkht++;
1182
1183     /* Ascend the tree. */
1184     link = next; node = parent;
1185     next = path->p[--k]; parent = (struct rbnode *)*next;
1186   }
1187
1188   /* We're done. */
1189 end:
1190   *path->p[0] = 0;
1191   *left_out = left; if (lht_out) *lht_out = lht;
1192   *right_out = right; if (rht_out) *rht_out = rht;
1193   if (mht_out) *mht_out = mid ? 1 : 0;
1194   return (mid);
1195 }
1196
1197 /* --- @rbtree_splitat@ --- *
1198  *
1199  * Arguments:   @struct bstnode *left_out@ = where to leave the root of the
1200  *                      resulting left tree
1201  *              @int *lht_out@ = where to leave the black-height of the left
1202  *                      tree, or null to discard this information
1203  *              @int *mht_out@ = where to leave the black-height of the
1204  *                      middle node (either zero or one), or null to discard
1205  *                      this information
1206  *              @struct bstnode *right_out@ = where to leave the root of the
1207  *                      resulting right tree
1208  *              @int *rht_out@ = where to leave the black-height of the right
1209  *                      tree, or null to discard this information
1210  *              @struct bstnode **root@ = address of the root link of the
1211  *                      input tree
1212  *              @const void *key@ = key at which to split the tree.
1213  *
1214  * Returns:     A pointer to the matching middle node, or null.
1215  *
1216  * Use:         Split a tree into two at an indicated key.
1217  *
1218  *              The splitting operation produces two trees, a `left tree'
1219  *              containing every node whose key is less than @key@, and a
1220  *              `right tree' containing every node whose key is greater than
1221  *              @key@.  If a node matching the @key@ exists in the input
1222  *              tree, then that becomes the `middle node', which does not
1223  *              appear in either tree, and is returned separately.
1224  */
1225
1226 void *rbtree_splitat(struct bstree_nodecls *cls,
1227                      struct bstnode **left_out, int *lht_out,
1228                      int *mht_out,
1229                      struct bstnode **right_out, int *rht_out,
1230                      struct bstnode **root, const void *key)
1231 {
1232   struct rbpath path;
1233
1234   bstree_probe(cls, root, (/*unconst*/ void *)key, path.p, &path.k);
1235   return (rbtree_split(cls, left_out, lht_out, mht_out, right_out, rht_out,
1236                        &path));
1237 }
1238
1239 /* --- @rbtree_splitroot@ --- *
1240  *
1241  * Arguments:   @struct bstnode *left_out@ = where to leave the root of the
1242  *                      resulting left tree
1243  *              @int *lht_out@ = where to leave the black-height of the left
1244  *                      tree, or null to discard this information
1245  *              @int *mht_out@ = where to leave the black-height of the
1246  *                      middle node (either zero or one), or null to discard
1247  *                      this information
1248  *              @struct bstnode *right_out@ = where to leave the root of the
1249  *                      resulting right tree
1250  *              @int *rht_out@ = where to leave the black-height of the right
1251  *                      tree, or null to discard this information
1252  *              @struct bstnode **root@ = tree root node, or null
1253  *              @int blkht@ = black-height of the tree, or %$-1$% if unknown
1254  *
1255  * Returns:     A pointer to the resulting middle node, or null.
1256  *
1257  * Use:         Split a tree into two at its root.
1258  *
1259  *              The splitting operation produces two trees, a `left tree'
1260  *              containing every node preceding the root, and a `right
1261  *              tree' containing every node following the root, together with
1262  *              the root.  If the root is null, then the left and right trees
1263  *              are also null.
1264  */
1265
1266 void *rbtree_splitroot(struct bstnode **left_out, int *lht_out,
1267                        int *mht_out,
1268                        struct bstnode **right_out, int *rht_out,
1269                        struct bstnode **root, int blkht)
1270 {
1271   struct rbnode *left, *right, *node;
1272   int lht, rht;
1273
1274   node = (struct rbnode *)*root; *root = 0;
1275   if (!node) {
1276     *left_out = *right_out = 0;
1277     if (lht_out) *lht_out = 0;
1278     if (mht_out) *mht_out = 0;
1279     if (rht_out) *rht_out = 0;
1280   } else {
1281     left = (struct rbnode *)node->_bst.left;
1282     right = (struct rbnode *)node->_bst.right;
1283     if (!lht_out && !rht_out) {
1284       if (left->f&RBF_RED) { left->f &= ~RBF_RED; }
1285       if (right->f&RBF_RED) { right->f &= ~RBF_RED; }
1286     } else {
1287       if (blkht < 0) blkht = rbtree_height(node);
1288       lht = rht = blkht - 1;
1289       if (left && left->f&RBF_RED) { lht++; left->f &= ~RBF_RED; }
1290       if (right && right->f&RBF_RED) { rht++; right->f &= ~RBF_RED; }
1291       if (lht_out) *lht_out = lht;
1292       if (rht_out) *rht_out = rht;
1293     }
1294     if (mht_out) *mht_out = 1;
1295     *left_out = left ? &left->_bst : 0;
1296     *right_out = right ? &right->_bst : 0;
1297   }
1298   return (node);
1299 }
1300
1301 static const struct bstree_treeops rbtree_ops =
1302   { rbtree_join, rbtree_splitat, rbtree_splitroot };
1303
1304 /* --- @rbtree_unisect@ --- *
1305  *
1306  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
1307  *              @struct bstnode **uni_out@ = where to write the union root
1308  *              @int *uniht_out@ = where to put the union height (or null)
1309  *              @struct bstnode **isect_out@ = where to write the
1310  *                      intersection root
1311  *              @int *isectht_out@ = where to put the intersection height (or
1312  *                      null)
1313  *              @struct bstnode *a@ = pointer to first operand root node
1314  *              @int aht@ = first operand height, or %$-1$%
1315  *              @struct bstnode *b@ = pointer to second operand root node
1316  *              @int bht@ = second operand height, or %$-1$%
1317  *
1318  * Returns:     ---
1319  *
1320  * Use:         Compute the union and intersection of the two operand trees.
1321  *
1322  *              The original trees are destroyed.  Each node in the original
1323  *              operands trees ends up in exactly one of the result trees.
1324  */
1325
1326 void rbtree_unisect(struct bstree_nodecls *cls,
1327                     struct bstnode **uni_out, int *uniht_out,
1328                     struct bstnode **isect_out, int *isectht_out,
1329                     struct bstnode **aroot, int aht,
1330                     struct bstnode **broot, int bht)
1331 {
1332   struct bstnode *a, *b;
1333   struct bstree_setopstack stack[RBTREE_PATHMAX];
1334
1335   a = *aroot; if (aht < 0) aht = rbtree_height((struct rbnode *)a);
1336   b = *broot; if (bht < 0) bht = rbtree_height((struct rbnode *)b);
1337   *aroot = *broot = 0;
1338
1339   bstree_unisect(cls, uni_out, uniht_out, isect_out, isectht_out,
1340                  a, aht, b, bht, &rbtree_ops, stack);
1341 }
1342
1343 /* --- @rbtree_diffsect@ --- *
1344  *
1345  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
1346  *              @struct bstnode **diff_out@ = where to write the difference
1347  *                      root
1348  *              @int *diffht_out@ = where to put the difference height (or
1349  *                      null)
1350  *              @struct bstnode **isect_out@ = where to write the
1351  *                      intersection root
1352  *              @int *isectht_out@ = where to put the intersection height (or
1353  *                      null)
1354  *              @struct bstnode *a@ = pointer to first operand root node
1355  *              @int aht@ = first operand height, or %$-1$%
1356  *              @struct bstnode *b@ = pointer to second operand root node
1357  *
1358  * Returns:     ---
1359  *
1360  * Use:         Compute the difference -- i.e., those nodes in %$a$% without
1361  *              matching nodes in %$b$% -- and intersection of the two
1362  *              operand trees.
1363  *
1364  *              The original tree %$a$% is destroyed.  Each node in the
1365  *              original operands tree ends up in exactly one of the result
1366  *              trees.  The input tree %$b$% is unchanged.
1367  */
1368
1369 void rbtree_diffsect(struct bstree_nodecls *cls,
1370                      struct bstnode **diff_out, int *diffht_out,
1371                      struct bstnode **isect_out, int *isectht_out,
1372                      struct bstnode **aroot, int aht,
1373                      struct bstnode **broot)
1374 {
1375   struct bstnode *a, *b;
1376   struct bstree_setopstack stack[RBTREE_PATHMAX];
1377
1378   a = *aroot; if (aht < 0) aht = rbtree_height((struct rbnode *)a);
1379   b = *broot;
1380
1381   bstree_diffsect(cls, diff_out, diffht_out, isect_out, isectht_out,
1382                   a, aht, b, &rbtree_ops, stack);
1383 }