chiark - git - mdw - xyla/blob - rb-splitjoin.c

   1 /* -*-c-*-
   2  *
   3  * Splitting and joining red-black trees
   4  *
   5  * (c) 2024 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Xyla, a library of binary trees.
  11  *
  12  * Xyla is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU Lesser General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Xyla is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20  * License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include "lib.h"
  29 #include "rb.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 int xyla_rb_join(struct xyla_bt_nodecls *cls,
  34                  struct xyla_bt_node **root_out, int *rootht_out,
  35                  struct xyla_bt_node **left, int lht,
  36                  struct xyla_bt_node *mid,
  37                  struct xyla_bt_node **right, int rht)
  38 {
  39   /* Concatenate the two trees rooted at LEFT and RIGHT in order; if MID is
  40    * not null, then place this node between them.  The root of the resulting
  41    * tree is stored in *ROOT_OUT.  It's the caller's responsibility to ensure
  42    * that this respects any ordering invariants.
  43    *
  44    * If the black-heights of the LEFT and RIGHT trees are known, then they
  45    * can be passed in as LHT and RHT; otherwise, LHT and/or RHT must be -1.
  46    * The black-height of the combined tree is stored in *ROOTHT_OUT if this
  47    * is not null.
  48    *
  49    * The ROOT_OUT pointer may equal either LEFT or RIGHT (or, indeed, both,
  50    * only if both are empty).  If LEFT is distinct from ROOT_OUT then *LEFT
  51    * is set null on exit; similarly, if RIGHT is distinct from ROOT_OUT, then
  52    * *RIGHT is set null on exit.
  53    *
  54    * Returns `XYLA_RC_OK'.
  55    */
  56
  57   struct xyla_rb_node *m = RB_NODE(mid), *p, *n, *s;
  58   struct xyla_bt_node **clink, **plink, *root;
  59   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  60   struct xyla_rb_path path;
  61   int blkht, rc;
  62
  63   /* Determine the heights of the left and right trees if the caller didn't
  64    * supply them.
  65    */
  66   if (lht < 0) lht = xyla_rb_height(RB_NODE(*left));
  67   if (rht < 0) rht = xyla_rb_height(RB_NODE(*right));
  68
  69   /* If we're not given a joining node then take one from the right tree.  If
  70    * the right tree is empty, then the join is just the left tree and there's
  71    * nothing to do.
  72    */
  73   if (!m) {
  74     if (!rht) { root = *left; blkht = lht; goto end; }
  75     else if (!lht) { root = *right; blkht = rht; goto end; }
  76     else {
  77       m = xyla_rb_firstpath(right, &path);
  78       rc = xyla_rb_remove(cls, &path);
  79         if (rc == XYLA_RC_HTCHG) rht--;
  80         else XYLA__ASSERT(!rc);
  81     }
  82   }
  83
  84   if (lht == rht) {
  85     /* The trees have the same black-height.  We can just join them the
  86      * stupid way.  The joining node will be the root, so it must be black,
  87      * and the resulting height is one greater than the input heights.
  88      */
  89
  90     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_JOIN))
  91          fputs("XYLA-RB JOIN equal heights\n", xyla__verbout); )
  92     m->bt.left = *left; m->bt.right = *right;
  93     m->rb.f &= ~XYLA_RBF_RED;
  94     if (updfn) updfn(cls, &m->bt);
  95     root = &m->bt; blkht = lht + 1;
  96   } else {
  97     if (lht > rht)
  98 #define FIXUP_JOIN(left, lht, right, rht) do {                          \
  99       /* The left tree is taller. */                                    \
 100                                                                         \
 101       /* Find the rightmost subtree in the left tree whose black-height \
 102        * is equal to the right tree's black-height.                     \
 103        */                                                               \
 104       path.k = 0; path.p[0] = clink = left; blkht = lht;                \
 105       for (;;) {                                                        \
 106         n = RB_NODE(*clink);                                            \
 107         if (!(n && (n->rb.f&XYLA_RBF_RED))) {                           \
 108           if (blkht == rht) break;                                      \
 109           blkht--;                                                      \
 110         }                                                               \
 111         path.p[++path.k] = clink = &n->bt.right;                        \
 112       }                                                                 \
 113                                                                         \
 114       /* Replace this subtree with the two trees, joined by a red node. \
 115        * This will preserve the global black-height invariant, but may  \
 116        * result in two adjacent red nodes.                              \
 117        */                                                               \
 118       *clink = &m->bt; m->rb.f |= XYLA_RBF_RED;                         \
 119       m->bt.left = n ? &n->bt : 0;                                      \
 120       m->bt.right = *right;                                             \
 121       if (updfn) updfn(cls, &m->bt);                                    \
 122                                                                         \
 123       /* Fix up the tree to restore the invariant.  This is a simpler   \
 124        * version of the fix-up in `xyla_rb_insert' above.  We get to    \
 125        * throw out a lot of the complexity because we know that our     \
 126        * path runs down the extremity of the taller tree, so, in        \
 127        * particular, we won't need to check which side a node is from   \
 128        * its parent.                                                    \
 129        */                                                               \
 130       blkht = lht;                                                      \
 131       for (;;) {                                                        \
 132                                                                         \
 133         /* Fetch the parent: our child node is red, so it must have     \
 134          * one.  If the parent is black then we're done.                \
 135          */                                                             \
 136         n = RB_NODE(*path.p[--path.k]);                                 \
 137         if (!(n->rb.f&XYLA_RBF_RED)) {                                  \
 138           if (updfn) updfn(cls, &n->bt);                                \
 139           break;                                                        \
 140         }                                                               \
 141                                                                         \
 142         /* Our child has a red parent.  That's the new focus node.      \
 143          * Since it's red, it has a black parent.                       \
 144          */                                                             \
 145         plink = path.p[--path.k]; p = RB_NODE(*plink);                  \
 146                                                                         \
 147         /* If the node has a red sibling then we can blacken this node  \
 148          * and its sibling.  If the parent is the root, then the tree   \
 149          * got taller; otherwise, redden the parent and continue        \
 150          * ascending.                                                   \
 151          */                                                             \
 152         s = RB_NODE(p->bt.left);                                        \
 153         if (s && s->rb.f&XYLA_RBF_RED) {                                \
 154           V( if (xyla__verbout && (xyla__verbose&XYLA__VF_JOIN))        \
 155                fprintf(xyla__verbout, "XYLA-RB JOIN red sibling "       \
 156                        "(" #right " child): %s\n",                      \
 157                        path.k ? "ascend" : "extend tree"); )            \
 158           n->rb.f &= ~XYLA_RBF_RED; s->rb.f &= ~XYLA_RBF_RED;           \
 159           if (updfn) { updfn(cls, &n->bt); updfn(cls, &p->bt); }        \
 160           if (!path.k) { blkht++; break; }                              \
 161           p->rb.f |= XYLA_RBF_RED; continue;                            \
 162         }                                                               \
 163                                                                         \
 164         /* The node has a red right child and a black parent, but no    \
 165          * red sibling.                                                 \
 166          *                                                              \
 167          *       p                                                      \
 168          *        (*)                                 n                 \
 169          *      /     \    n                           (*)              \
 170          *              ( )             --->    p    /     \    c       \
 171          *             /   \   c                 ( )         ( )        \
 172          *                  ( )                 /   \       /   \       \
 173          *                 /   \                                        \
 174          */                                                             \
 175         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_JOIN))          \
 176              fputs("XYLA-RB JOIN no red sibling (" #right " child)\n",  \
 177                    xyla__verbout); )                                    \
 178         p->bt.right = n->bt.left; n->bt.left = &p->bt;                  \
 179         n->rb.f &= ~XYLA_RBF_RED; p->rb.f |= XYLA_RBF_RED;              \
 180         if (updfn) { updfn(cls, &p->bt); updfn(cls, &n->bt); }          \
 181         *plink = &n->bt;                                                \
 182         break;                                                          \
 183       }                                                                 \
 184                                                                         \
 185       /* Return the result. */                                          \
 186       root = *left;                                                     \
 187 } while (0)
 188       FIXUP_JOIN(left, lht, right, rht);
 189     else
 190       FIXUP_JOIN(right, rht, left, lht);
 191 #undef FIXUP_JOIN
 192
 193     /* Follow the rest of the path up to the root, updating the nodes. */
 194     if (updfn) while (path.k) updfn(cls, *path.p[--path.k]);
 195   }
 196
 197   /* All done.  Fix up the root pointers and return the new black-height. */
 198 end:
 199   *left = 0; *right = 0; *root_out = root;
 200   if (rootht_out) *rootht_out = blkht;
 201   return (XYLA_RC_OK);
 202 }
 203
 204 int xyla_rb_split(struct xyla_bt_nodecls *cls,
 205                   struct xyla_bt_node **left_out, int *lht_out,
 206                   struct xyla_bt_node **mid_out,
 207                   struct xyla_bt_node **right_out, int *rht_out,
 208                   struct xyla_rb_path *path)
 209 {
 210   /* Split a tree tree into two at the indicated place indicated by the PATH.
 211    * Store in *LEFT_OUT and *RIGHT_OUT the roots of trees containing every
 212    * node respectively preceding and following the PATH, and in *LHT_OUT and
 213    * *RHT_OUT the black-heights of the respective output trees; either or
 214    * both of LHT_OUT and RHT_OUT may be null to discard this information.
 215    *
 216    * If the PATH is full, i.e., it denotes a node in the input tree, then
 217    * that becomes the `middle node', which does not appear in either output
 218    * tree; a pointer to this node is stored in *MID_OUT.
 219    *
 220    * Returns `XYLA_RC_OK'.
 221    */
 222
 223   struct xyla_bt_node *left, *right, *sub, **next, **link;
 224   struct xyla_rb_node *parent, *node, *mid;
 225   int k, blkht, lht, rht, subht;
 226   unsigned f;
 227
 228   /* The basic idea is to work up the tree, following the provided path,
 229    * maintaining left and right trees.  When we come across a node with a
 230    * leftward link, then we join that node and its right subtree onto our
 231    * right tree; and /vice-versa/.
 232    *
 233    *                         |        *           |
 234    *                    ,----|------'   `---------|-,
 235    *                  *      |                    |   *
 236    *            ,---'   `---,|                  ,-|-'   `---,
 237    *          *              |*               *   |           *
 238    *        /   \           /|  \           /   \ |         /   \
 239    *      *       *       *  |    *       *       *       *       *
 240    *     / \     / \     / \ |   / \     / \     /|\     / \     / \
 241    *    *   *   *   *   *   *|  *   *   *   *   * | *   *   *   *   *
 242    *                         |                    |
 243    *
 244    * The conceptual difficulty lies in how to initialize the left and right
 245    * trees.
 246    *
 247    * The other fiddly part is keeping track of the black-heights as we work
 248    * through the tree.
 249    */
 250
 251   /* Retrieve the designated node. */
 252   k = path->k; link = path->p[k]; mid = RB_NODE(*link);
 253   if (mid) {
 254     /* The path is full, i.e., it terminates in a link to a node, which will
 255      * be the final mid node.  Initialize the left and right trees to the
 256      * node's left and right subtrees.  Work out their black-heights -- this
 257      * will save effort later, because we know that they'll be equal.
 258      * Forcibly blacken the roots of the trees, and fix the heights as
 259      * necessary.
 260      */
 261
 262     /* Initialize the left and right trees. */
 263     left = mid->bt.left; right = mid->bt.right;
 264
 265     /* Initialize the black-heights.  The two subtrees must have the same
 266      * black-height initially, but we must blacken the roots, and that might
 267      * introduce a difference.
 268      */
 269     lht = rht = blkht = xyla_rb_height(RB_NODE(left));
 270     if (left) {
 271       node = RB_NODE(left);
 272       if (node->rb.f&XYLA_RBF_RED) { node->rb.f &= ~XYLA_RBF_RED; lht++; }
 273     }
 274     if (right) {
 275       node = RB_NODE(right);
 276       if (node->rb.f&XYLA_RBF_RED) { node->rb.f &= ~XYLA_RBF_RED; rht++; }
 277     }
 278
 279     /* Clear the split node's links, so that it's a standalone singleton
 280      * tree.  If the split node is black then its height was one more than
 281      * its children's.  If it's red, then blacken it because it's a root now.
 282      */
 283     mid->bt.left = mid->bt.right = 0;
 284     if (!(mid->rb.f&XYLA_RBF_RED)) blkht++;
 285     else mid->rb.f &= ~XYLA_RBF_RED;
 286
 287     /* Special case: the split node is the tree root.
 288      *
 289      * This is only `special' because the other case ascends one step higher
 290      * in the tree, so we should do the same here.
 291      */
 292     if (!k) goto end;
 293
 294     /* Prefetch the next node up the path. */
 295     next = path->p[--k]; parent = RB_NODE(*next);
 296   } else {
 297     /* The path is empty, i.e., it terminates in a null link, and the final
 298      * mid node will be null.  The obvious thing to do is to initialize the
 299      * left and right trees to be empty, but that will end up doing too much
 300      * work.  If we examine the diagram above, we see that there will be an
 301      * intact subtree on one side of the split line.  Working step-by-step
 302      * risks messing with the structure of that subtree for no benefit: if
 303      * the root of some inner subtree is red then we'll end up blackening it
 304      * because the root of a tree must be black -- but then its height will
 305      * differ from its sibling's when we come to join them together again and
 306      * we'll have to rebalance.
 307      *
 308      * Instead, we note the direction of the final null link.  Every further
 309      * link in the path that's in the same direction means that we're still
 310      * searching for the initial subtree root.
 311      */
 312
 313     /* Special case: the tree is actually empty. */
 314     if (!k) { left = right = 0; lht = rht = 0; goto end; }
 315
 316     /* Retrieve the parent node and split into cases according to the link
 317      * direction.
 318      */
 319     next = path->p[--k]; node = RB_NODE(*next); blkht = 0;
 320     if (link == &node->bt.left)
 321 #define INIT_SPLIT_EMPTY(left, lht, right, rht) do {                    \
 322       /* The null link points leftwards, so the we're searching to      \
 323        * bound the initial right tree.                                  \
 324        */                                                               \
 325                                                                         \
 326       for (;;) {                                                        \
 327                                                                         \
 328         /* We've decided to include the current node in the initial     \
 329          * tree, so update the black-height.                            \
 330          */                                                             \
 331         if (!(node->rb.f&XYLA_RBF_RED)) blkht++;                        \
 332                                                                         \
 333         /* The current node is the tree root.  There can be nothing     \
 334          * else.                                                        \
 335          */                                                             \
 336         if (!k) {                                                       \
 337           left = 0; lht = 0;                                            \
 338           right = &node->bt; rht = blkht;                               \
 339           goto end;                                                     \
 340         }                                                               \
 341                                                                         \
 342         /* Ascend the tree and check the link direction. */             \
 343         link = next; next = path->p[--k]; parent = RB_NODE(*next);      \
 344         if (link != &parent->bt.left) break;                            \
 345         node = parent; link = next;                                     \
 346       }                                                                 \
 347                                                                         \
 348       /* Establish the left and right trees. */                         \
 349       left = 0; lht = 0;                                                \
 350       right = &node->bt; rht = blkht;                                   \
 351                                                                         \
 352       /* Make sure the root of the right tree is painted black. */      \
 353       if (node->rb.f&XYLA_RBF_RED)                                      \
 354         { rht++; node->rb.f &= ~XYLA_RBF_RED; }                         \
 355 } while (0)
 356       INIT_SPLIT_EMPTY(left, lht, right, rht);
 357     else
 358       INIT_SPLIT_EMPTY(right, rht, left, lht);
 359 #undef INIT_SPLIT_EMPTY
 360   }
 361
 362   /* Ascend the tree, accumulating additional material into the left or right
 363    * trees.  This is actually much less complicated than it sounds.
 364    */
 365   for (;;) {
 366     /* The state at this point is a little tricky.
 367      *
 368      * There is a current node; `link' holds a link to this node, and `blkht'
 369      * is its black-height.  The subtree rooted at this current node has been
 370      * split, resulting in a left tree rooted at `left', with black-height
 371      * `lht', and a right tree rooted at `right', with black-height `rht',
 372      * and, depending on the initial path, possibly a mid node `mid'.
 373      *
 374      * The node has a `parent'.  The link to the parent is in `next'.  The
 375      * parent and the current node's subling subtree must be accumulated into
 376      * the appropriate left or right tree.  Note that the sibling subtree has
 377      * the same black-height as the current node.
 378      */
 379
 380     /* Take note of the parent node's flags because they'll be clobbered in
 381      * the next step.
 382      */
 383     f = parent->rb.f;
 384
 385     /* Accumulate the parent and the sibling subtree onto the appropriate
 386      * tree.
 387      */
 388     if (link == &parent->bt.left) {
 389       sub = parent->bt.right; subht = blkht; node = RB_NODE(sub);
 390       if (node && node->rb.f&XYLA_RBF_RED)
 391         { subht++; node->rb.f &= ~XYLA_RBF_RED; }
 392       xyla_rb_join(cls, &right, &rht, &right, rht, &parent->bt, &sub, subht);
 393     } else {
 394       sub = parent->bt.left; subht = blkht; node = RB_NODE(sub);
 395       if (node && node->rb.f&XYLA_RBF_RED)
 396         { subht++; node->rb.f &= ~XYLA_RBF_RED; }
 397       xyla_rb_join(cls, &left, &lht, &sub, subht, &parent->bt, &left, lht);
 398     }
 399
 400     /* If we've reached the root then we're done. */
 401     if (!k) goto end;
 402
 403     /* Update the black-height. */
 404     if (!(f&XYLA_RBF_RED)) blkht++;
 405
 406     /* Ascend the tree. */
 407     link = next; node = parent;
 408     next = path->p[--k]; parent = RB_NODE(*next);
 409   }
 410
 411   /* We're done. */
 412 end:
 413   *path->p[0] = 0;
 414   *left_out = left; if (lht_out) *lht_out = lht;
 415   *mid_out = mid ? &mid->bt : 0;
 416   *right_out = right; if (rht_out) *rht_out = rht;
 417   return (XYLA_RC_OK);
 418 }
 419
 420 int xyla_rb_splitat(struct xyla_bt_nodecls *cls,
 421                     struct xyla_bt_node **left_out, int *lht_out,
 422                     struct xyla_bt_node **mid_out,
 423                     struct xyla_bt_node **right_out, int *rht_out,
 424                     struct xyla_bt_node **root, const void *key)
 425 {
 426   /* Split the tree rooted at ROOT into two at an indicated KEY.  Store in
 427    * *LEFT_OUT and *RIGHT_OUT the roots of trees containing every node whose
 428    * key is respectively less than and greater than the KEY, and in *LHT_OUT
 429    * and *RHT_OUT the black-heights of the respective output trees; either or
 430    * both of LHT_OUT and RHT_OUT may be null to discard this information.
 431    *
 432    * If a node matching the KEY exists in the input tree, then that becomes
 433    * the `middle node', which does not appear in either output tree; a
 434    * pointer to this node is stored in *MID_OUT.
 435    *
 436    * This operation assumes that the tree traversal ordering matches an
 437    * ordering on search keys, which is implemented by the node-class `nav'
 438    * function.
 439    *
 440    * Returns `XYLA_RC_OK'.
 441    */
 442
 443   const struct xyla_bt_ordops *ops = ORDER_OPS(cls->ops);
 444   struct xyla_bt_node *node;
 445   struct xyla_rb_path path;
 446   int rc;
 447
 448   XYLA_BT_PROBE(rc, node, cls, root, ops->ord.nav, UNCONST(void, key),
 449                 path.p, path.k, XYLA_RB_HTMAX);
 450     XYLA__ASSERT(!rc); (void)node;
 451   return (xyla_rb_split(cls, left_out, lht_out, mid_out, right_out, rht_out,
 452                         &path));
 453 }
 454
 455 int xyla_rb_splitroot(struct xyla_bt_node **left_out, int *lht_out,
 456                       struct xyla_bt_node **root_out,
 457                       struct xyla_bt_node **right_out, int *rht_out,
 458                       struct xyla_bt_node **root, int blkht)
 459 {
 460   /* Split the tree rooted at ROOT into two at its root.  Store in *ROOT_OUT
 461    * a pointer to the original root node, or null if the tree was initially
 462    * empty; store in *LEFT_OUT and *RIGHT_OUT the root of the original root's
 463    * left and right subtrees respectively, and in *LHT_OUT and *RHT_OUT the
 464    * black-heights of the respective output trees; either or both of LHT_OUT
 465    * and RHT_OUT may be null to discard this information.  If the initial
 466    * tree's black-height is known, it can be passed in as BLKHT; otherwise,
 467    * BLKHT must be -1.
 468    *
 469    * Returns `XYLA_RC_OK'.
 470    */
 471
 472   struct xyla_rb_node *left, *right, *node;
 473   int lht, rht;
 474
 475   node = RB_NODE(*root); *root = 0;
 476   if (!node) {
 477     *left_out = *root_out = *right_out = 0;
 478     if (lht_out) *lht_out = 0;
 479     if (rht_out) *rht_out = 0;
 480   } else {
 481     left = RB_NODE(node->bt.left); right = RB_NODE(node->bt.right);
 482     node->bt.left = node->bt.right = 0;
 483     if (!lht_out && !rht_out) {
 484       if (left->rb.f&XYLA_RBF_RED) { left->rb.f &= ~XYLA_RBF_RED; }
 485       if (right->rb.f&XYLA_RBF_RED) { right->rb.f &= ~XYLA_RBF_RED; }
 486     } else {
 487       if (blkht < 0) blkht = xyla_rb_height(node);
 488       lht = rht = blkht - 1;
 489       if (left && left->rb.f&XYLA_RBF_RED)
 490         { lht++; left->rb.f &= ~XYLA_RBF_RED; }
 491       if (right && right->rb.f&XYLA_RBF_RED)
 492         { rht++; right->rb.f &= ~XYLA_RBF_RED; }
 493       if (lht_out) *lht_out = lht;
 494       if (rht_out) *rht_out = rht;
 495     }
 496     *left_out = left ? &left->bt : 0;
 497     *root_out = &node->bt;
 498     *right_out = right ? &right->bt : 0;
 499   }
 500   return (XYLA_RC_OK);
 501 }
 502
 503 /*----- That's all, folks -------------------------------------------------*/