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

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