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

   1 /* -*-c-*-
   2  *
   3  * Insertion and removal for 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_insert(struct xyla_bt_nodecls *cls,
  34                    struct xyla_rb_path *path, struct xyla_rb_node *node)
  35 {
  36   /* Add a new node to the tree, in the place determined by the empty PATH.
  37    * It's the caller's responsibility to ensure that inserting the node here
  38    * respects any ordering invariants.  Returns `XYLA_RC_HTCHG' if the tree
  39    * has increased in height, or `XYLA_RC_OK' if its height remains
  40    * unchanged.
  41    *
  42    * The new node is not copied, and its storage must remain valid until the
  43    * node is removed or the tree is discarded.
  44    */
  45
  46   struct xyla_rb_node *p, *n, *c, *l, *r;
  47   struct xyla_bt_node **clink, **nlink, **plink;
  48   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  49   int k = path->k;
  50
  51   /* Check that the path is well-formed and describes a failed probe. */
  52   clink = path->p[k]; XYLA__ASSERT(!*clink);
  53
  54   /* Initialize the new node's links and hook it onto the tree. */
  55   node->bt.left = node->bt.right = 0; *clink = &node->bt;
  56
  57   /* If the tree was empty then the new node is going to be the root of the
  58    * tree, which must be black.
  59    */
  60   if (!k) {
  61     node->rb.f &= ~XYLA_RBF_RED;
  62     if (updfn) updfn(cls, &node->bt);
  63     return (XYLA_RC_HTCHG);
  64   }
  65
  66   /* Otherwise we'll provisionally paint the new node red and try to fix
  67    * things up.
  68    */
  69   c = node; c->rb.f |= XYLA_RBF_RED;
  70   for (;;) {
  71     /* The child node c is known to be red.  Our focus node n is the child's
  72      * parent, and it might also be red; this is the only violation of the
  73      * tree invariants, and we're trying to fix it.  In particular, c's
  74      * children, if any, are black.  Neither c nor n has been updated yet.
  75      * We'll also be interested in the focus node's parent p.  The focus
  76      * node's sibling, denoted s in the diagrams below, is also interesting
  77      * to the theory, but not named explicitly in the code itself.
  78      */
  79
  80     /* Retrieve the focus node, which must exist because c is red and the
  81      * tree root is black.  If the focus node is black then we're done.
  82      */
  83     nlink = path->p[--k]; n = RB_NODE(*nlink);
  84     if (!(n->rb.f&XYLA_RBF_RED)) {
  85       if (updfn) { updfn(cls, &c->bt); updfn(cls, &n->bt); }
  86       break;
  87     }
  88
  89     /* Retrieve the focus node's parent p, which must also exist for the same
  90      * reason.  Note that p is definitely black, since it has at least one
  91      * red child.
  92      */
  93     plink = path->p[--k]; p = RB_NODE(*plink);
  94
  95     /* If the parent has two children and they're both red, then blacken them
  96      * both.  (This approach avoids dealing with all of the symmetry in the
  97      * loop.)  If the parent is the root then we're done, and the tree black-
  98      * height has increased by one; otherwise, redden it and ascend.
  99      *
 100      *                    p                               p
 101      *                     (*)                             ( )
 102      *              n    /     \    s               n    /     \    s
 103      *               ( )         ( )    --->         (*)         (*)
 104      *          c   /   \       /   \           c   /   \       /   \
 105      *           ( )                             ( )
 106      *          /   \                           /   \
 107      */
 108     l = RB_NODE(p->bt.left); r = RB_NODE(p->bt.right);
 109     if (l && r && (l->rb.f&r->rb.f&XYLA_RBF_RED)) {
 110       V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))
 111            fprintf(xyla__verbout, "XYLA-RB INSERT red sibling: %s\n",
 112                    k ? "ascend" : "extend tree"); )
 113       l->rb.f &= ~XYLA_RBF_RED; r->rb.f &= ~XYLA_RBF_RED;
 114       if (!k) {
 115         if (updfn) {
 116           updfn(cls, &c->bt); updfn(cls, &n->bt);
 117           updfn(cls, &p->bt);
 118         }
 119         return (XYLA_RC_HTCHG);
 120       }
 121       if (updfn) { updfn(cls, &c->bt); updfn(cls, &n->bt); }
 122       p->rb.f |= XYLA_RBF_RED; c = p; clink = plink; continue;
 123     }
 124
 125     /* Otherwise, we have some links to rewrite. */
 126     if (nlink == &p->bt.left)
 127 #define FIXUP_INSERT(left, l, right, r) do {                            \
 128       /* The focus node is its parent's left child.  There are two      \
 129        * cases, depending on whether c is the focus node's left or      \
 130        * right child.  It's safe to redden p here: if the focus node    \
 131        * has a red sibling then we'd have ascended the tree above.      \
 132        */                                                               \
 133                                                                         \
 134       if (clink == &n->bt.left) {                                       \
 135         /*                p                                             \
 136          *                 (*)                        n                 \
 137          *          n    /     \                       (*)              \
 138          *           ( )                --->    c    /     \    p       \
 139          *      c   /   \                        ( )         ( )        \
 140          *       ( )                            /   \       /   \       \
 141          *      /   \                                                   \
 142          */                                                             \
 143                                                                         \
 144         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))        \
 145              fputs("XYLA-RB INSERT zig-zig (" #left " child)\n",        \
 146                    xyla__verbout); )                                    \
 147         p->bt.left = n->bt.right; n->bt.right = &p->bt;                 \
 148         n->rb.f &= ~XYLA_RBF_RED; p->rb.f |= XYLA_RBF_RED;              \
 149         if (updfn) {                                                    \
 150           updfn(cls, &c->bt); updfn(cls, &p->bt);                       \
 151           updfn(cls, &n->bt);                                           \
 152         }                                                               \
 153         *plink = &n->bt;                                                \
 154       } else {                                                          \
 155         /*                p                                             \
 156          *                 (*)                        c                 \
 157          *          n    /     \                       (*)              \
 158          *           ( )                --->    n    /     \    p       \
 159          *          /   \   c                    ( )         ( )        \
 160          *               ( )                    /   \       /   \       \
 161          *              /   \                                           \
 162          */                                                             \
 163                                                                         \
 164         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))        \
 165              fputs("XYLA-RB INSERT zig-zag (" #left " child)\n",        \
 166                    xyla__verbout); )                                    \
 167         n->bt.right = c->bt.left; c->bt.left = &n->bt;                  \
 168         p->bt.left = c->bt.right; c->bt.right = &p->bt;                 \
 169         c->rb.f &= ~XYLA_RBF_RED; p->rb.f |= XYLA_RBF_RED;              \
 170         if (updfn) {                                                    \
 171           updfn(cls, &n->bt); updfn(cls, &p->bt);                       \
 172           updfn(cls, &c->bt);                                           \
 173         }                                                               \
 174         *plink = &c->bt;                                                \
 175       }                                                                 \
 176 } while (0)
 177       FIXUP_INSERT(left, l, right, r);
 178     else
 179       FIXUP_INSERT(right, r, left, l);
 180 #undef FIXUP_INSERT
 181
 182     /* Whatever happened above, we're now done: the parent is still black. */
 183     break;
 184   }
 185
 186   /* Follow the rest of the path up to the root, updating the nodes. */
 187   if (updfn) while (k) updfn(cls, *path->p[--k]);
 188
 189   /* We're done.  The overall black-height only changes if we reach the root,
 190    * and we'd have returned already if that happened.
 191    */
 192   return (XYLA_RC_OK);
 193 }
 194
 195 int xyla_rb_remove(struct xyla_bt_nodecls *cls, struct xyla_rb_path *path)
 196 {
 197   /* Remove the node identified by the PATH.  The node was allocated by the
 198    * caller, and should be freed by the caller in whatever way is
 199    * appropriate.  Returns `XYLA_RC_HTCHG' if the tree has decreased in
 200    * height, or `XYLA_RC_OK' if its height remains unchanged.
 201    */
 202
 203   struct xyla_rb_node *n, *p, *s, *t, *l, *r;
 204   struct xyla_bt_node *del, *subst, *replace, **nlink, **plink;
 205   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 206   int k, rc;
 207   unsigned f, ff;
 208
 209   /* Unlink the node from the tree. */
 210   rc = xyla_bt_remove(&del, &subst, &replace,
 211                       path->p, &path->k, XYLA_RB_HTMAX);
 212     XYLA__ASSERT(!rc);
 213   t = RB_NODE(del); f = t->rb.f; s = RB_NODE(subst); n = RB_NODE(replace);
 214   k = path->k;
 215
 216   /* If the node was substituted, then fix up the colouring. */
 217   if (s)
 218     { ff = f; f = s->rb.f; s->rb.f = (f&~XYLA_RBF_RED) | (ff&XYLA_RBF_RED); }
 219
 220   /* We've cut out out a node t, and replaced it with one of its `children' n
 221    * -- which might, in fact, be null.  If t was black, then, to maintain the
 222    * invariant, we (mentally) assign an additional dose of blackness to n.
 223    * Our task will be to take one of these blackness doses and move it
 224    * somewhere safe -- either a red ancestor, or the root, where we can just
 225    * safely forget about it.
 226    */
 227   if (f&XYLA_RBF_RED) {
 228     /* If the node we've cut out was actually red then we can just forget
 229      * about it.
 230      */
 231
 232     if (updfn && n) updfn(cls, &n->bt);
 233   } else if (n && (n->rb.f&XYLA_RBF_RED)) {
 234     /* If n is actually a real node, and it's red, then we can just blacken
 235      * it.
 236      */
 237
 238     n->rb.f &= ~XYLA_RBF_RED;
 239     if (updfn && n) updfn(cls, &n->bt);
 240   } else {
 241     /* It looks like we have some actual work to do. */
 242
 243     nlink = path->p[k];
 244     for (;;) {
 245       /* The node n is doubly black, and we must offload one of the doses of
 246        * blackness somewhere else.
 247        */
 248
 249       if (!k) {
 250         /* The node we're looking at is, in fact, the root.  The extra
 251          * blackness affects all paths to the leaves equally, so we can can
 252          * just throw it away without anyone noticing, except that the tree
 253          * black-height has decreased.
 254          */
 255
 256         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))
 257              fputs("XYLA-RB REMOVE shorten tree\n", xyla__verbout); )
 258         return (XYLA_RC_HTCHG);
 259       }
 260
 261       /* Not the root, so we can find a parent node. */
 262       plink = path->p[--k]; p = RB_NODE(*plink);
 263
 264       /* In fact, because we have at least one blackness dose, we must have a
 265        * live sibling, with a subtree containing at least one black node.
 266        * Split into two main cases according to whether we're on the left or
 267        * right.
 268        */
 269       if (nlink == &p->bt.left)
 270 #define FIXUP_REMOVE(left, l, right, r) do {                            \
 271         /* We're the left child. */                                     \
 272                                                                         \
 273         s = RB_NODE(p->bt.right);                                       \
 274         if (s->rb.f&XYLA_RBF_RED) {                                     \
 275           /* Our sibling is red.  The parent must then be black, and    \
 276            * the sibling must have two black children, our node's       \
 277            * niblings, though we're only interested in the left-hand    \
 278            * one, which we call t.                                      \
 279            */                                                           \
 280                                                                         \
 281           t = RB_NODE(s->bt.left);                                      \
 282           l = RB_NODE(t->bt.left); r = RB_NODE(t->bt.right);            \
 283                                                                         \
 284           if (r && r->rb.f&XYLA_RBF_RED) {                              \
 285             /* The left nibling has a red right child.  The following   \
 286              * rearrangement discharges the surplus black dose.         \
 287              *                                                          \
 288              *        p                                       s         \
 289              *         (*)                                     (*)      \
 290              * n     /     \    s                       t    /     \    \
 291              *  (* *)        ( )        --->             ( )            \
 292              *  /   \   t   /   \                   p   /   \   r       \
 293              *           (*)                         (*)     (*)        \
 294              *          /   \   r               n   /   \   /   \       \
 295              *               ( )                 (*)                    \
 296              *              /   \               /   \                   \
 297              */                                                         \
 298                                                                         \
 299             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 300                  fputs("XYLA-RB REMOVE red sibling, "                   \
 301                        "outer red great-nibling (" #left " child)\n",   \
 302                        xyla__verbout); )                                \
 303             p->bt.right = l ? &l->bt : 0;                               \
 304             t->bt.left = &p->bt; s->bt.left = &t->bt;                   \
 305             s->rb.f &= ~XYLA_RBF_RED; r->rb.f &= ~XYLA_RBF_RED;         \
 306             t->rb.f |= XYLA_RBF_RED;                                    \
 307             if (updfn) {                                                \
 308               updfn(cls, &p->bt); updfn(cls, &t->bt);                   \
 309               updfn(cls, &s->bt);                                       \
 310             }                                                           \
 311           } else if (l && l->rb.f&XYLA_RBF_RED) {                       \
 312             /* The left nibling has a red left child.  The following    \
 313              * rearrangement discharges the surplus black dose.         \
 314              *                                                          \
 315              *        p                                       s         \
 316              *         (*)                                     (*)      \
 317              * n     /     \    s                       l    /     \    \
 318              *  (* *)        ( )        --->             ( )            \
 319              *  /   \   t   /   \                   p   /   \   t       \
 320              *           (*)                         (*)     (*)        \
 321              *      l   /   \                   n   /   \   /   \       \
 322              *       ( )                         (*)                    \
 323              *      /   \                       /   \                   \
 324              */                                                         \
 325                                                                         \
 326             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 327                  fputs("XYLA-RB REMOVE red sibling, "                   \
 328                        "inner red great-nibling (" #left " child)\n",   \
 329                        xyla__verbout); )                                \
 330             p->bt.right = l->bt.left; l->bt.left = &p->bt;              \
 331             t->bt.left = l->bt.right; l->bt.right = &t->bt;             \
 332             s->bt.left = &l->bt; s->rb.f &= ~XYLA_RBF_RED;              \
 333             if (updfn) {                                                \
 334               updfn(cls, &p->bt); updfn(cls, &t->bt);                   \
 335               updfn(cls, &l->bt); updfn(cls, &s->bt);                   \
 336             }                                                           \
 337           } else {                                                      \
 338             /* The left nibling has no red children.  The following     \
 339              * rearrangement discharges the surplus black dose:         \
 340              * reddening t is safe because it has no red children.      \
 341              *                                                          \
 342              *        p                                   s             \
 343              *         (*)                                 (*)          \
 344              * n     /     \    s                   p    /     \        \
 345              *  (* *)        ( )        --->         (*)                \
 346              *  /   \   t   /   \               n   /   \   t           \
 347              *           (*)                     (*)     ( )            \
 348              *          /   \                   /   \   /   \           \
 349              */                                                         \
 350                                                                         \
 351             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 352                  fputs("XYLA-RB REMOVE red sibling, "                   \
 353                        "no red great-nibling (" #left " child)\n",      \
 354                        xyla__verbout); )                                \
 355             p->bt.right = &t->bt; s->bt.left = &p->bt;                  \
 356             s->rb.f &= ~XYLA_RBF_RED; t->rb.f |= XYLA_RBF_RED;          \
 357             if (updfn) { updfn(cls, &p->bt); updfn(cls, &s->bt); }      \
 358           }                                                             \
 359                                                                         \
 360           /* Adjust the parent link.  In all cases, the invariant has   \
 361            * been properly restored.                                    \
 362            */                                                           \
 363           *plink = &s->bt; goto update;                                 \
 364         } else {                                                        \
 365           /* Our sibling is black.  We can't deduce the colour of the   \
 366            * parent node.                                               \
 367            */                                                           \
 368                                                                         \
 369           l = RB_NODE(s->bt.left); r = RB_NODE(s->bt.right);            \
 370                                                                         \
 371           if (r && r->rb.f&XYLA_RBF_RED) {                              \
 372             /* The sibling has a red right child.  The following        \
 373              * rearrangement discharges the surplus black dose.         \
 374              *                                                          \
 375              *        p                                    s            \
 376              *         (?)                                  (?)         \
 377              * n     /     \   s                     p    /     \   r   \
 378              *  (* *)       (*)         --->          (*)        (*)    \
 379              *  /   \      /   \   r            n    /   \      /   \   \
 380              *                  ( )              (*)                    \
 381              *                 /   \            /   \                   \
 382              */                                                         \
 383                                                                         \
 384             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 385                  fputs("XYLA-RB REMOVE black sibling, "                 \
 386                        "outer red nibling (" #left " child)\n",         \
 387                        xyla__verbout); )                                \
 388             p->bt.right = l ? &l->bt : 0; s->bt.left = &p->bt;          \
 389             s->rb.f |= p->rb.f&XYLA_RBF_RED;                            \
 390             p->rb.f &= ~XYLA_RBF_RED; r->rb.f &= ~XYLA_RBF_RED;         \
 391             if (updfn) { updfn(cls, &p->bt); updfn(cls, &s->bt); }      \
 392             *plink = &s->bt; goto update;                               \
 393           } else if (l && l->rb.f&XYLA_RBF_RED) {                       \
 394             /* The sibling has a red left child.  The following         \
 395              * rearrangement discharges the surplus black dose.         \
 396              *                                                          \
 397              *        p                                    l            \
 398              *         (?)                                  (?)         \
 399              * n     /     \   s                     p    /     \   s   \
 400              *  (* *)       (*)         --->          (*)        (*)    \
 401              *  /   \  l   /   \                n    /   \      /   \   \
 402              *          ( )                      (*)                    \
 403              *         /   \                    /   \                   \
 404              */                                                         \
 405                                                                         \
 406             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 407                  fputs("XYLA-RB REMOVE black sibling, "                 \
 408                        "inner red nibling (" #left " child)\n",         \
 409                        xyla__verbout); )                                \
 410             p->bt.right = l->bt.left; l->bt.left = &p->bt;              \
 411             s->bt.left = l->bt.right; l->bt.right = &s->bt;             \
 412             l->rb.f = (l->rb.f&~XYLA_RBF_RED) | (p->rb.f&XYLA_RBF_RED); \
 413             p->rb.f &= ~XYLA_RBF_RED;                                   \
 414             if (updfn) {                                                \
 415               updfn(cls, &p->bt); updfn(cls, &s->bt);                   \
 416               updfn(cls, &l->bt);                                       \
 417             }                                                           \
 418             *plink = &l->bt; goto update;                               \
 419           } else {                                                      \
 420             /* The sibling has no red children.  That means that it's   \
 421              * safe to make it red, so we can push the extra black dose \
 422              * up into the parent.  If the parent was previously red,   \
 423              * then we're done; otherwise, we ascend the tree.          \
 424              *                                                          \
 425              *        p                                   p             \
 426              *         (?)                                 (? *)        \
 427              * n     /     \   s                     n    /     \   s   \
 428              *  (* *)       (*)         --->          (*)        ( )    \
 429              *  /   \      /   \                     /   \      /   \   \
 430              */                                                         \
 431                                                                         \
 432             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 433                  fprintf(xyla__verbout, "XYLA-RB REMOVE "               \
 434                          "black sibling, %s parent, no red nibling "    \
 435                          "(" #left " child)\n",                         \
 436                          p->rb.f&XYLA_RBF_RED ? "red" : "black"); )     \
 437             s->rb.f |= XYLA_RBF_RED;                                    \
 438             if (updfn) updfn(cls, &p->bt);                              \
 439             if (p->rb.f&XYLA_RBF_RED)                                   \
 440               { p->rb.f &= ~XYLA_RBF_RED; goto update; }                \
 441             n = p; nlink = plink;                                       \
 442           }                                                             \
 443         }                                                               \
 444 } while (0)
 445         FIXUP_REMOVE(left, l, right, r);
 446       else
 447         FIXUP_REMOVE(right, r, left, l);
 448 #undef FIXUP_REMOVE
 449     }
 450   }
 451
 452   /* Follow the rest of the path up to the root, updating the nodes. */
 453 update:
 454   if (updfn) while (k) updfn(cls, *path->p[--k]);
 455   return (XYLA_RC_OK);
 456 }
 457
 458 /*----- That's all, folks -------------------------------------------------*/