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

   1 /* -*-c-*-
   2  *
   3  * Insertion and removal for AVL 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 "avl.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 int xyla_avl_insert(struct xyla_bt_nodecls *cls,
  34                     struct xyla_avl_path *path, struct xyla_avl_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_avl_node *p, *n, *c;
  47   struct xyla_bt_node **nlink, **plink;
  48   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  49   int k = path->k;
  50   unsigned trail = 0, bal;
  51
  52   /* The trail.  Rather than keep looking things up in the tree nodes, we
  53    * keep track of information in a bitmask.  Records build up at the low
  54    * end, and get shifted up as we ascend the tree, so more-significant bit
  55    * positions refer to lower nodes in the tree.  The iteration ends when we
  56    * find an imbalanced ancestor; as we ascend, we adjust the balance
  57    * annotations which end up matching the direction of the child from which
  58    * we ascended.  So there's no point tracking both: the balance state of a
  59    * node is equal to the direction of its child.
  60    */
  61 #define TRAILSH 2
  62 #define NODE (0*TRAILSH)
  63 #define CHILD (1*TRAILSH)
  64 #define DIR(lv) ((trail >> (lv))&3u)
  65 #define BAL(lv) ((trail >> ((lv) + TRAILSH))&3u)
  66
  67   /* Check that the path is well-formed and describes a failed probe. */
  68   nlink = path->p[k]; XYLA__ASSERT(!*nlink);
  69
  70   /* Initialize the new node's links and hook it onto the tree. */
  71   node->avl.f = (node->avl.f&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;
  72   node->bt.left = node->bt.right = 0;
  73   *nlink = &node->bt;
  74
  75   /* And now we have to rebalance the tree.  Getting started is a little
  76    * tricky.  Start with the easy case: if we're at the top of the tree
  77    * already, then the whole thing has just gotten taller.
  78    */
  79   if (!k) {
  80     if (updfn) updfn(cls, &node->bt);
  81     return (XYLA_RC_HTCHG);
  82   }
  83
  84   /* Propagate the change up the tree. */
  85   n = node; c = 0; /* unnecessary */
  86   for (;;) {
  87     /* The node n has not yet been updated. */
  88
  89     /* Collect the parent node and enter the details in the trail. */
  90     plink = path->p[--k]; p = AVL_NODE(*plink);
  91     trail |= (nlink == &p->bt.left ?
  92                 XYLA_AVLBAL_LBIAS : XYLA_AVLBAL_RBIAS) << NODE;
  93     bal = p->avl.f&XYLA_AVLF_BALMASK; if (bal != XYLA_AVLBAL_EVEN) break;
  94     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))
  95          fprintf(xyla__verbout, "XYLA-AVL INSERT "
  96                  "parent = (%s child): %s tree\n",
  97                  DIR(NODE) == XYLA_AVLBAL_LBIAS ? "left" : "right",
  98                  k ? "ascend" : "extend"); )
  99
 100     /* The parent node was equally balanced.  It's now heavy on the side of
 101      * the current node.  That's fine, but the parent's height has changed in
 102      * the process.
 103      *
 104      *            p = -> -              p = -> +
 105      *               ( )        or         ( )
 106      *           n  /   \                 /   \  n
 107      *          h + 1     h             h     h + 1
 108      */
 109
 110     /* Update the balance annotation. */
 111     p->avl.f |= DIR(NODE);
 112
 113     /* If there's no more tree to ascend then it got taller. */
 114     if (!k) {
 115       if (updfn) { updfn(cls, &n->bt); updfn(cls, &p->bt); }
 116       return (XYLA_RC_HTCHG);
 117     }
 118
 119     /* Ascend the tree. */
 120     if (updfn) updfn(cls, &n->bt);
 121     c = n; n = p; nlink = plink; trail <<= TRAILSH;
 122   }
 123
 124   /* Finishing touches. */
 125   if (DIR(NODE) != bal) {
 126     /* The parent node was imbalanced, and the current node is on what was
 127      * previously the light side.  It's now been evened out.
 128      *
 129      *          p - or + -> =
 130      *               ( )
 131      *           n  /   \
 132      *          h + 1   h + 1
 133      */
 134
 135     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))
 136          fprintf(xyla__verbout, "XYLA-AVL INSERT parent %c (%s child)\n",
 137                  AVL_BALCH(p),
 138                  DIR(NODE) == XYLA_AVLBAL_LBIAS ? "left" : "right"); )
 139     p->avl.f = (p->avl.f&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;
 140     if (updfn) { updfn(cls, &n->bt); updfn(cls, &p->bt); }
 141   }
 142
 143   else if (DIR(NODE) == XYLA_AVLBAL_LBIAS)
 144 #define FIXUP_INSERT(left, LBIAS, right, RBIAS, EEL, REE) do {          \
 145     /* The parent node was biased to the left, and the current node is  \
 146      * the parent's left child.  That means that we must have ascended  \
 147      * a level: the original node's parent lacked a child before we     \
 148      * added one, so must have balanced evenly or biased in the         \
 149      * opposite direction.                                              \
 150      */                                                                 \
 151                                                                         \
 152     if (BAL(NODE) == XYLA_AVLBAL_##LBIAS) {                             \
 153       /* The current node is already biased in the same direction as    \
 154        * the parent.  We can resolve the situation by applying a        \
 155        * rotation and adjusting balance annotations.                    \
 156        *                                                                \
 157        *                 p                            n                 \
 158        *                  (- -)                        (=)              \
 159        *            n    /     \                     /    \    p        \
 160        *             (-)          n     --->    h + 1       (=)         \
 161        *            /   \                                  /   \        \
 162        *        h + 1     h                              h       h      \
 163        *                                                                \
 164        * The final height of the subtree remains unchanged at h + 2, so \
 165        * we're done propagating the height change.                      \
 166        */                                                               \
 167                                                                         \
 168       V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))          \
 169            fprintf(xyla__verbout, "XYLA-AVL INSERT parent %c, node %c " \
 170                    "(" #left " child)\n",                               \
 171                    AVL_BALCH(p), AVL_BALCH(n)); )                       \
 172       p->bt.left = n->bt.right; n->bt.right = &p->bt; *plink = &n->bt;  \
 173       n->avl.f = (n->avl.f&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;      \
 174       p->avl.f = (p->avl.f&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;      \
 175       if (updfn) { updfn(cls, &p->bt); updfn(cls, &n->bt); }            \
 176     } else {                                                            \
 177       /* The current node is already biased in the opposite direction   \
 178        * from its parent.  We can resolve the situation by applying two \
 179        * rotations and adjusting balance annotations.                   \
 180        *                                                                \
 181        *                 p                                              \
 182        *                  (- -)                        c                \
 183        *            n    /     \                        (=)             \
 184        *             (+)         h             n   ,---'   `---,   p    \
 185        *            /   \   c           --->    (*)             (*)     \
 186        *          h      (*)                   /   \           /   \    \
 187        *                /   \                h       h       h       h  \
 188        *              h       h                    h - 1   h - 1        \
 189        *            h - 1   h - 1                                       \
 190        *                                                                \
 191        * The resulting balance annotations depend on the child's        \
 192        * initial state.  The child node c has height h + 1.  The new    \
 193        * node may be one of c's descendants: in that case, c must       \
 194        * previously have been evenly balanced, or we wouldn't have got  \
 195        * this far up the tree; the subtree containing the new node now  \
 196        * has height h and the sibling subtree still has height h - 1.   \
 197        * Alternatively, the child node may be the new node itself, in   \
 198        * which case it has no children and is evenly balanced, and      \
 199        * h = 0.                                                         \
 200        *                                                                \
 201        * In any event, at most one of c's subtrees has height h - 1, so \
 202        * c always ends up evenly balanced; the new balance annotations  \
 203        * for nodes n and p are as follows.                              \
 204        *                                                                \
 205        *        c | n   p                                               \
 206        *        --+------                                               \
 207        *        - | =   +                                               \
 208        *        = | =   =                                               \
 209        *        + | -   =                                               \
 210        *                                                                \
 211        * The final height of the subtree remains unchanged at h + 2, so \
 212        * we're done propagating the height change.                      \
 213        */                                                               \
 214                                                                         \
 215       V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))          \
 216            fprintf(xyla__verbout,                                       \
 217                    "XYLA-AVL INSERT parent %c, node %c, child %c "      \
 218                    "(" #left " child)\n",                               \
 219                    AVL_BALCH(p), AVL_BALCH(n), AVL_BALCH(c)); )         \
 220       n->bt.right = c->bt.left; c->bt.left = &n->bt;                    \
 221       p->bt.left = c->bt.right; c->bt.right = &p->bt; *plink = &c->bt;  \
 222       bal = BAL(CHILD);                                                 \
 223       c->avl.f = (c->avl.f&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;      \
 224       n->avl.f = (n->avl.f&~XYLA_AVLF_BALMASK) | AVL_REBAL_##EEL(bal);  \
 225       p->avl.f = (p->avl.f&~XYLA_AVLF_BALMASK) | AVL_REBAL_##REE(bal);  \
 226       if (updfn) {                                                      \
 227         /* We've updated c once already.  I can't see a good way to     \
 228          * avoid this without introducing a bunch of additional         \
 229          * conditional logic into the other cases.                      \
 230          */                                                             \
 231         updfn(cls, &n->bt); updfn(cls, &p->bt); updfn(cls, &c->bt);     \
 232       }                                                                 \
 233     }                                                                   \
 234 } while (0)
 235     FIXUP_INSERT(left, LBIAS, right, RBIAS, EEL, REE);
 236   else
 237     FIXUP_INSERT(right, RBIAS, left, LBIAS, REE, EEL);
 238 #undef FIXUP_INSERT
 239
 240   /* Follow the rest of the path up to the root, updating the nodes. */
 241   if (updfn) while (k) updfn(cls, *path->p[--k]);
 242
 243   /* All done.  The tree didn't change height. */
 244   return (XYLA_RC_OK);
 245
 246 #undef TRAILSH
 247 #undef CHILD
 248 #undef NODE
 249 #undef BAL
 250 #undef DIR
 251 }
 252
 253 int xyla_avl_remove(struct xyla_bt_nodecls *cls, struct xyla_avl_path *path)
 254 {
 255   /* Remove the node identified by the PATH.  The node was allocated by the
 256    * caller, and should be freed by the caller in whatever way is
 257    * appropriate.  Returns `XYLA_RC_HTCHG' if the tree has decreased in
 258    * height, or `XYLA_RC_OK' if its height remains unchanged.
 259    */
 260
 261   struct xyla_avl_node *p, *s, *t;
 262   struct xyla_bt_node **nlink, **plink;
 263   struct xyla_bt_node *del, *subst, *replace;
 264   unsigned bal, pf, sf, tf;
 265   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 266   int k, rc;
 267
 268   /* Unlink the node from the tree. */
 269   rc = xyla_bt_remove(&del, &subst, &replace,
 270                       path->p, &path->k, XYLA_AVL_HTMAX);
 271     XYLA__ASSERT(!rc);
 272   t = AVL_NODE(del); s = AVL_NODE(subst); k = path->k;
 273
 274   /* If the node was substituted, then fix up the balance annotation. */
 275   if (s)
 276     s->avl.f = (s->avl.f&~XYLA_AVLF_BALMASK) | (t->avl.f&XYLA_AVLF_BALMASK);
 277
 278   /* We've cut off a node, which makes the containing subtree shorter by one.
 279    * Ascend the tree, fixing the balance annotations, and restructure it as
 280    * necessary.
 281    */
 282   nlink = path->p[k];
 283   for (;;) {
 284     /* The containing subtree is short.  Examine the parent node to decide
 285      * what to do.
 286      */
 287
 288     /* If we're already at the top, then the tree as a whole just got
 289      * shorter.
 290      */
 291     if (!k) {
 292       V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))
 293            fputs("XYLA-AVL REMOVE shorten tree\n", xyla__verbout); )
 294       return (XYLA_RC_HTCHG);
 295     }
 296
 297     /* Collect the parent.  We'll want to keep the link address if we
 298      * ascend.
 299      */
 300     plink = path->p[--k]; p = AVL_NODE(*plink); pf = p->avl.f;
 301
 302     /* And now we split into cases according to which side of the parent our
 303      * current node is on.
 304      */
 305     if (nlink == &p->bt.left)
 306 #define FIXUP_REMOVE(left, LBIAS, right, RBIAS, EEL, REE, XRE, XLE) do { \
 307       /* The current node is the left child. */                         \
 308                                                                         \
 309       switch (pf&XYLA_AVLF_BALMASK) {                                   \
 310                                                                         \
 311         case XYLA_AVLBAL_EVEN:                                          \
 312           /* The parent was previously evenly balanced, so it's now     \
 313            * biased to the right.  But the right subtree is still the   \
 314            * same height, so the change stops propagating here.         \
 315            *                                                            \
 316            *       p                                p                   \
 317            *        (=)                              (+)                \
 318            *    n  /   \                --->     n  /   \               \
 319            *     h       h                      h - 1     h             \
 320            */                                                           \
 321                                                                         \
 322           V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))      \
 323                fputs("XYLA-AVL REMOVE parent = (" #left " child)\n",    \
 324                      xyla__verbout); )                                  \
 325           p->avl.f = (pf&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_##RBIAS;     \
 326           if (updfn) updfn(cls, &p->bt);                                \
 327           goto update;                                                  \
 328                                                                         \
 329         case XYLA_AVLBAL_##LBIAS:                                       \
 330           /* The parent was previously biased to the left, so it's now  \
 331            * evenly balanced.  But it's now shorter by one as a whole,  \
 332            * so the change keeps propagating.                           \
 333            *                                                            \
 334            *       p                                p                   \
 335            *        (-)                              (=)                \
 336            *    n  /   \                --->     n  /   \               \
 337            *     h     h - 1                    h - 1   h - 1           \
 338            */                                                           \
 339                                                                         \
 340           V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))      \
 341                fprintf(xyla__verbout, "XYLA-AVL REMOVE parent %c "      \
 342                        "(" #left " child)\n", AVL_BALCH(p)); )          \
 343           p->avl.f = (pf&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;        \
 344           if (updfn) updfn(cls, &p->bt);                                \
 345           break;                                                        \
 346                                                                         \
 347         case XYLA_AVLBAL_##RBIAS:                                       \
 348           /* The parent was previously biased to the right, so it's now \
 349            * out of balance.  There are two subcases to examine,        \
 350            * depending on the sibling node s.                           \
 351            */                                                           \
 352                                                                         \
 353           s = AVL_NODE(p->bt.right); sf = s->avl.f;                     \
 354           if ((sf&XYLA_AVLF_BALMASK) == XYLA_AVLBAL_##LBIAS) {          \
 355             /* The sibling is biased to the left.  In particular, then, \
 356              * it must have a left child node t, the `nibling'.  We     \
 357              * restructure the tree, but it's going to get shorter as a \
 358              * whole, so we'll have to continue ascending afterwards.   \
 359              *                                                          \
 360              *       p                                                  \
 361              *        (+ +)                          t                  \
 362              *       /     \    s                     (=)               \
 363              *  h - 1        (-)             p   ,---'   `---,   s      \
 364              *          t   /   \       --->  (*)             (*)       \
 365              *           (*)    h - 1        /   \           /   \      \
 366              *          /   \            h - 1   h - 1   h - 1   h - 1  \
 367              *      h - 1   h - 1                h - 2   h - 2          \
 368              *      h - 2   h - 2                                       \
 369              *                                                          \
 370              * The resulting balance annotations depend on the initial  \
 371              * state of the nibling.                                    \
 372              *                                                          \
 373              *  t | p   s                                               \
 374              *  --+------                                               \
 375              *  - | =   +                                               \
 376              *  = | =   =                                               \
 377              *  + | -   =                                               \
 378              */                                                         \
 379                                                                         \
 380             t = AVL_NODE(s->bt.left); tf = t->avl.f;                    \
 381             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 382                  fprintf(xyla__verbout, "XYLA-AVL REMOVE "              \
 383                          "parent %c, sibling %c, nibling %c "           \
 384                          "(" #left " child)\n",                         \
 385                          AVL_BALCH(p), AVL_BALCH(s), AVL_BALCH(t)); )   \
 386             p->bt.right = t->bt.left; t->bt.left = &p->bt;              \
 387             s->bt.left = t->bt.right; t->bt.right = &s->bt;             \
 388             t->avl.f = (tf&~XYLA_AVLF_BALMASK) | XYLA_AVLBAL_EVEN;      \
 389             bal = tf&XYLA_AVLF_BALMASK;                                 \
 390             p->avl.f = (pf&~XYLA_AVLF_BALMASK) | AVL_REBAL_##EEL(bal);  \
 391             s->avl.f = (sf&~XYLA_AVLF_BALMASK) | AVL_REBAL_##REE(bal);  \
 392             if (updfn) {                                                \
 393               updfn(cls, &p->bt); updfn(cls, &s->bt);                   \
 394               updfn(cls, &t->bt);                                       \
 395             }                                                           \
 396             *plink = &t->bt;                                            \
 397           } else {                                                      \
 398             /* The sibling is not biased to the left.  Again, we        \
 399              * restructure the tree, and it might or might not get      \
 400              * shorter, depending on the balance state of s: we         \
 401              * continue ascending if s is evenly balanced, and stop if  \
 402              * it's biased to the right.  (If s were left biased, then  \
 403              * we'd be in the other case.)                              \
 404              *                                                          \
 405              *       p                                    s             \
 406              *        (+ +)                                (*)          \
 407              *       /     \    s                   p    /     \        \
 408              *  h - 1        (*)        --->         (*)          h     \
 409              *              /   \                   /   \               \
 410              *            h       h             h - 1     h             \
 411              *          h - 1                           h - 1           \
 412              *                                                          \
 413              *  s | p   s  up?                                          \
 414              *  --+-----------                                          \
 415              *  - |   (n/a)                                             \
 416              *  = | +   -  no                                           \
 417              *  + | =   =  yes                                          \
 418              */                                                         \
 419                                                                         \
 420             V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))    \
 421                  fprintf(xyla__verbout, "XYLA-AVL REMOVE "              \
 422                          "parent %c, sibling %c (" #left " child)\n",   \
 423                          AVL_BALCH(p), AVL_BALCH(s)); )                 \
 424             p->bt.right = s->bt.left; s->bt.left = &p->bt;              \
 425             bal = sf&XYLA_AVLF_BALMASK;                                 \
 426             p->avl.f = (pf&~XYLA_AVLF_BALMASK) | AVL_REBAL_##XRE(bal);  \
 427             s->avl.f = (sf&~XYLA_AVLF_BALMASK) | AVL_REBAL_##XLE(bal);  \
 428             if (updfn) { updfn(cls, &p->bt); updfn(cls, &s->bt); }      \
 429             *plink = &s->bt;                                            \
 430             if (bal == XYLA_AVLBAL_EVEN) goto update;                   \
 431           }                                                             \
 432           break;                                                        \
 433       }                                                                 \
 434 } while (0)
 435       FIXUP_REMOVE(left, LBIAS, right, RBIAS, EEL, REE, XRE, XLE);
 436     else
 437       FIXUP_REMOVE(right, RBIAS, left, LBIAS, REE, EEL, ELX, ERX);
 438 #undef FIXUP_REMOVE
 439
 440     /* Continue ascending the tree. */
 441     nlink = plink;
 442   }
 443
 444   /* Follow the rest of the path up to the root, updating the nodes. */
 445 update:
 446   if (updfn) while (k) updfn(cls, *path->p[--k]);
 447   return (XYLA_RC_OK);
 448 }
 449
 450 /*----- That's all, folks -------------------------------------------------*/