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); updfn(cls, &n->bt);   \
 151         }                                                               \
 152         *plink = &n->bt;                                                \
 153       } else {                                                          \
 154         /*                p                                             \
 155          *                 (*)                        c                 \
 156          *          n    /     \                       (*)              \
 157          *           ( )                --->    n    /     \    p       \
 158          *          /   \   c                    ( )         ( )        \
 159          *               ( )                    /   \       /   \       \
 160          *              /   \                                           \
 161          */                                                             \
 162                                                                         \
 163         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))        \
 164              fputs("XYLA-RB INSERT zig-zag (" #left " child)\n",        \
 165                    xyla__verbout); )                                    \
 166         n->bt.right = c->bt.left; c->bt.left = &n->bt;                  \
 167         p->bt.left = c->bt.right; c->bt.right = &p->bt;                 \
 168         c->rb.f &= ~XYLA_RBF_RED; p->rb.f |= XYLA_RBF_RED;              \
 169         if (updfn) {                                                    \
 170           updfn(cls, &n->bt); updfn(cls, &p->bt);                       \
 171           updfn(cls, &c->bt);                                           \
 172         }                                                               \
 173         *plink = &c->bt;                                                \
 174       }                                                                 \
 175 } while (0)
 176       FIXUP_INSERT(left, l, right, r);
 177     else
 178       FIXUP_INSERT(right, r, left, l);
 179 #undef FIXUP_INSERT
 180
 181     /* Whatever happened above, we're now done: the parent is still black. */
 182     break;
 183   }
 184
 185   /* Follow the rest of the path up to the root, updating the nodes. */
 186   if (updfn) while (k) updfn(cls, *path->p[--k]);
 187
 188   /* We're done.  The overall black-height only changes if we reach the root,
 189    * and we'd have returned already if that happened.
 190    */
 191   return (XYLA_RC_OK);
 192 }
 193
 194 int xyla_rb_remove(struct xyla_bt_nodecls *cls, struct xyla_rb_path *path)
 195 {
 196   /* Remove the node identified by the PATH.  The node was allocated by the
 197    * caller, and should be freed by the caller in whatever way is
 198    * appropriate.  Returns `XYLA_RC_HTCHG' if the tree has decreased in
 199    * height, or `XYLA_RC_OK' if its height remains unchanged.
 200    */
 201
 202   struct xyla_rb_node *n, *p, *s, *t, *l, *r;
 203   struct xyla_bt_node *del, *subst, *replace, **nlink, **plink;
 204   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 205   int k, rc;
 206   unsigned f, ff;
 207
 208   /* Unlink the node from the tree. */
 209   rc = xyla_bt_remove(&del, &subst, &replace,
 210                       path->p, &path->k, XYLA_RB_HTMAX);
 211     XYLA__ASSERT(!rc);
 212   t = RB_NODE(del); f = t->rb.f; s = RB_NODE(subst); n = RB_NODE(replace);
 213   k = path->k;
 214
 215   /* If the node was substituted, then fix up the colouring. */
 216   if (s)
 217     { ff = f; f = s->rb.f; s->rb.f = (f&~XYLA_RBF_RED) | (ff&XYLA_RBF_RED); }
 218
 219   /* We've cut out out a node t, and replaced it with one of its `children' n
 220    * -- which might, in fact, be null.  If t was black, then, to maintain the
 221    * invariant, we (mentally) assign an additional dose of blackness to n.
 222    * Our task will be to take one of these blackness doses and move it
 223    * somewhere safe -- either a red ancestor, or the root, where we can just
 224    * safely forget about it.
 225    */
 226   if (f&XYLA_RBF_RED) {
 227     /* If the node we've cut out was actually red then we can just forget
 228      * about it.
 229      */
 230
 231     if (updfn && n) updfn(cls, &n->bt);
 232   } else if (n && (n->rb.f&XYLA_RBF_RED)) {
 233     /* If n is actually a real node, and it's red, then we can just blacken
 234      * it.
 235      */
 236
 237     n->rb.f &= ~XYLA_RBF_RED;
 238     if (updfn && n) updfn(cls, &n->bt);
 239   } else {
 240     /* It looks like we have some actual work to do. */
 241
 242     nlink = path->p[k];
 243     for (;;) {
 244       /* The node n is doubly black, and we must offload one of the doses of
 245        * blackness somewhere else.
 246        */
 247
 248       if (!k) {
 249         /* The node we're looking at is, in fact, the root.  The extra
 250          * blackness affects all paths to the leaves equally, so we can can
 251          * just throw it away without anyone noticing, except that the tree
 252          * black-height has decreased.
 253          */
 254
 255         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))
 256              fputs("XYLA-RB REMOVE shorten tree\n", xyla__verbout); )
 257         return (XYLA_RC_HTCHG);
 258       }
 259
 260       /* Not the root, so we can find a parent node. */
 261       plink = path->p[--k]; p = RB_NODE(*plink);
 262
 263       /* In fact, because we have at least one blackness dose, we must have a
 264        * live sibling, with a subtree containing at least one black node.
 265        * Split into two main cases according to whether we're on the left or
 266        * right.
 267        */
 268       if (nlink == &p->bt.left)
 269 #define FIXUP_REMOVE(left, l, right, r) do {                            \
 270         /* We're the left child. */                                     \
 271                                                                         \
 272         s = RB_NODE(p->bt.right);                                       \
 273         if (s->rb.f&XYLA_RBF_RED) {                                     \
 274           /* Our sibling is red.  The parent must then be black, and    \
 275            * the sibling must have two black children, our node's       \
 276            * niblings, though we're only interested in the left-hand    \
 277            * one, which we call t.                                      \
 278            */                                                           \
 279                                                                         \
 280           t = RB_NODE(s->bt.left);                                      \
 281           l = RB_NODE(t->bt.left); r = RB_NODE(t->bt.right);            \
 282                                                                         \
 283           if (r && r->rb.f&XYLA_RBF_RED) {                              \
 284             /* The left nibling has a red right child.  The following   \
 285              * rearrangement discharges the surplus black dose.         \
 286              *                                                          \
 287              *        p                                       s         \
 288              *         (*)                                     (*)      \
 289              * n     /     \    s                       t    /     \    \
 290              *  (* *)        ( )        --->             ( )            \
 291              *  /   \   t   /   \                   p   /   \   r       \
 292              *           (*)                         (*)     (*)        \
 293              *          /   \   r               n   /   \   /   \       \
 294              *               ( )                 (*)                    \
 295              *              /   \               /   \                   \
 296              */                                                         \
 297                                                                         \
 298             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 299                  fputs("XYLA-RB REMOVE red sibling, "                   \
 300                        "outer red great-nibling (" #left " child)\n",   \
 301                        xyla__verbout); )                                \
 302             p->bt.right = l ? &l->bt : 0;                               \
 303             t->bt.left = &p->bt; s->bt.left = &t->bt;                   \
 304             s->rb.f &= ~XYLA_RBF_RED; r->rb.f &= ~XYLA_RBF_RED;         \
 305             t->rb.f |= XYLA_RBF_RED;                                    \
 306             if (updfn) {                                                \
 307               updfn(cls, &p->bt); updfn(cls, &t->bt);                   \
 308               updfn(cls, &s->bt);                                       \
 309             }                                                           \
 310           } else if (l && l->rb.f&XYLA_RBF_RED) {                       \
 311             /* The left nibling has a red left child.  The following    \
 312              * rearrangement discharges the surplus black dose.         \
 313              *                                                          \
 314              *        p                                       s         \
 315              *         (*)                                     (*)      \
 316              * n     /     \    s                       l    /     \    \
 317              *  (* *)        ( )        --->             ( )            \
 318              *  /   \   t   /   \                   p   /   \   t       \
 319              *           (*)                         (*)     (*)        \
 320              *      l   /   \                   n   /   \   /   \       \
 321              *       ( )                         (*)                    \
 322              *      /   \                       /   \                   \
 323              */                                                         \
 324                                                                         \
 325             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 326                  fputs("XYLA-RB REMOVE red sibling, "                   \
 327                        "inner red great-nibling (" #left " child)\n",   \
 328                        xyla__verbout); )                                \
 329             p->bt.right = l->bt.left; l->bt.left = &p->bt;              \
 330             t->bt.left = l->bt.right; l->bt.right = &t->bt;             \
 331             s->bt.left = &l->bt; s->rb.f &= ~XYLA_RBF_RED;              \
 332             if (updfn) {                                                \
 333               updfn(cls, &p->bt); updfn(cls, &t->bt);                   \
 334               updfn(cls, &l->bt); updfn(cls, &s->bt);                   \
 335             }                                                           \
 336           } else {                                                      \
 337             /* The left nibling has no red children.  The following     \
 338              * rearrangement discharges the surplus black dose:         \
 339              * reddening t is safe because it has no red children.      \
 340              *                                                          \
 341              *        p                                   s             \
 342              *         (*)                                 (*)          \
 343              * n     /     \    s                   p    /     \        \
 344              *  (* *)        ( )        --->         (*)                \
 345              *  /   \   t   /   \               n   /   \   t           \
 346              *           (*)                     (*)     ( )            \
 347              *          /   \                   /   \   /   \           \
 348              */                                                         \
 349                                                                         \
 350             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 351                  fputs("XYLA-RB REMOVE red sibling, "                   \
 352                        "no red great-nibling (" #left " child)\n",      \
 353                        xyla__verbout); )                                \
 354             p->bt.right = &t->bt; s->bt.left = &p->bt;                  \
 355             s->rb.f &= ~XYLA_RBF_RED; t->rb.f |= XYLA_RBF_RED;          \
 356             if (updfn) { updfn(cls, &p->bt); updfn(cls, &s->bt); }      \
 357           }                                                             \
 358                                                                         \
 359           /* Adjust the parent link.  In all cases, the invariant has   \
 360            * been properly restored.                                    \
 361            */                                                           \
 362           *plink = &s->bt; goto update;                                 \
 363         } else {                                                        \
 364           /* Our sibling is black.  We can't deduce the colour of the   \
 365            * parent node.                                               \
 366            */                                                           \
 367                                                                         \
 368           l = RB_NODE(s->bt.left); r = RB_NODE(s->bt.right);            \
 369                                                                         \
 370           if (r && r->rb.f&XYLA_RBF_RED) {                              \
 371             /* The sibling has a red right child.  The following        \
 372              * rearrangement discharges the surplus black dose.         \
 373              *                                                          \
 374              *        p                                    s            \
 375              *         (?)                                  (?)         \
 376              * n     /     \   s                     p    /     \   r   \
 377              *  (* *)       (*)         --->          (*)        (*)    \
 378              *  /   \      /   \   r            n    /   \      /   \   \
 379              *                  ( )              (*)                    \
 380              *                 /   \            /   \                   \
 381              */                                                         \
 382                                                                         \
 383             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 384                  fputs("XYLA-RB REMOVE black sibling, "                 \
 385                        "outer red nibling (" #left " child)\n",         \
 386                        xyla__verbout); )                                \
 387             p->bt.right = l ? &l->bt : 0; s->bt.left = &p->bt;          \
 388             s->rb.f |= p->rb.f&XYLA_RBF_RED;                            \
 389             p->rb.f &= ~XYLA_RBF_RED; r->rb.f &= ~XYLA_RBF_RED;         \
 390             if (updfn) { updfn(cls, &p->bt); updfn(cls, &s->bt); }      \
 391             *plink = &s->bt; goto update;                               \
 392           } else if (l && l->rb.f&XYLA_RBF_RED) {                       \
 393             /* The sibling has a red left child.  The following         \
 394              * rearrangement discharges the surplus black dose.         \
 395              *                                                          \
 396              *        p                                    l            \
 397              *         (?)                                  (?)         \
 398              * n     /     \   s                     p    /     \   s   \
 399              *  (* *)       (*)         --->          (*)        (*)    \
 400              *  /   \  l   /   \                n    /   \      /   \   \
 401              *          ( )                      (*)                    \
 402              *         /   \                    /   \                   \
 403              */                                                         \
 404                                                                         \
 405             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 406                  fputs("XYLA-RB REMOVE black sibling, "                 \
 407                        "inner red nibling (" #left " child)\n",         \
 408                        xyla__verbout); )                                \
 409             p->bt.right = l->bt.left; l->bt.left = &p->bt;              \
 410             s->bt.left = l->bt.right; l->bt.right = &s->bt;             \
 411             l->rb.f = (l->rb.f&~XYLA_RBF_RED) | (p->rb.f&XYLA_RBF_RED); \
 412             p->rb.f &= ~XYLA_RBF_RED;                                   \
 413             if (updfn) {                                                \
 414               updfn(cls, &p->bt); updfn(cls, &s->bt);                   \
 415               updfn(cls, &l->bt);                                       \
 416             }                                                           \
 417             *plink = &l->bt; goto update;                               \
 418           } else {                                                      \
 419             /* The sibling has no red children.  That means that it's   \
 420              * safe to make it red, so we can push the extra black dose \
 421              * up into the parent.  If the parent was previously red,   \
 422              * then we're done; otherwise, we ascend the tree.          \
 423              *                                                          \
 424              *        p                                   p             \
 425              *         (?)                                 (? *)        \
 426              * n     /     \   s                     n    /     \   s   \
 427              *  (* *)       (*)         --->          (*)        ( )    \
 428              *  /   \      /   \                     /   \      /   \   \
 429              */                                                         \
 430                                                                         \
 431             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 432                  fprintf(xyla__verbout, "XYLA-RB REMOVE "               \
 433                          "black sibling, %s parent, no red nibling "    \
 434                          "(" #left " child)\n",                         \
 435                          p->rb.f&XYLA_RBF_RED ? "red" : "black"); )     \
 436             s->rb.f |= XYLA_RBF_RED;                                    \
 437             if (updfn) updfn(cls, &p->bt);                              \
 438             if (p->rb.f&XYLA_RBF_RED)                                   \
 439               { p->rb.f &= ~XYLA_RBF_RED; goto update; }                \
 440             n = p; nlink = plink;                                       \
 441           }                                                             \
 442         }                                                               \
 443 } while (0)
 444         FIXUP_REMOVE(left, l, right, r);
 445       else
 446         FIXUP_REMOVE(right, r, left, l);
 447 #undef FIXUP_REMOVE
 448     }
 449   }
 450
 451   /* Follow the rest of the path up to the root, updating the nodes. */
 452 update:
 453   if (updfn) while (k) updfn(cls, *path->p[--k]);
 454   return (XYLA_RC_OK);
 455 }
 456
 457 /*----- That's all, folks -------------------------------------------------*/