chiark - git - mdw - xyla/blob - splay-base.c

   1 /* -*-c-*-
   2  *
   3  * Basic utilities for splay 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 "splay.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 void xyla__splay_split(struct xyla_bt_nodecls *cls,
  34                        struct xyla_bt_node **left_inout,
  35                        struct xyla_bt_node **right_inout,
  36                        struct xyla_splay_node *parent, unsigned side)
  37 {
  38   /* Splay the tree at a possibly fictional node.  The node is promoted to
  39    * the tree root, and the child links are updated.
  40    *
  41    * The PARENT and SIDE arguments identify the node's initial position in
  42    * the tree, and *LEFT_INOUT and *RIGHT_INOUT identify its child links.  It
  43    * is valid if the node is already the tree root: in this case, PARENT is
  44    * null and SIDE is ignored; otherwise SIDE must be one of the constants
  45    * `SPLAY_LEFT' or `SPLAY_RIGHT'.
  46    *
  47    * The `xyla__splay_splay' function below calls this with a real node,
  48    * determining the PARENT and SIDE appropriately; `xyla_splay_insert' uses
  49    * this to prepare the tree before the new node is linked in;
  50    * `xyla_splay_split' uses this to handle both its full and empty path
  51    * cases.
  52    */
  53
  54   struct xyla_splay_node *p, *n, *g, *l, *r, *t;
  55   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  56   unsigned trail;
  57
  58   l = SPLAY_NODE(*left_inout); r = SPLAY_NODE(*right_inout);
  59   n = parent; trail = side;
  60
  61   /* Ascend the tree two links at a time. */
  62   for (;;) {
  63     if (!n) goto end;
  64     p = n->spl.parent; if (!p) break;
  65     trail <<= 2;
  66     trail |= (p->bt.left == &n->bt ? SPLAY_LEFT : SPLAY_RIGHT) << 1;
  67     g = p->spl.parent;
  68     if (g)
  69       trail |= (g->bt.left == &p->bt ? SPLAY_LEFT : SPLAY_RIGHT) << 0;
  70
  71     switch (trail&6) {
  72 #define SPLAY_ZZ(left, LEFT, l, right, RIGHT, r)                        \
  73       case (SPLAY_##LEFT << 2) | (SPLAY_##LEFT << 1):                   \
  74         /* Zig-zig case: left child of a left child.                    \
  75          *                                                              \
  76          *                 p                             c              \
  77          *                   (*)                     ( )                \
  78          *           n     /     \                 /     \     n        \
  79          *             (*)                      l          (*)          \
  80          *       c    /   \             --->              /   \    p    \
  81          *         ( )      t                           r      (*)      \
  82          *        /   \                                       /   \     \
  83          *      l       r                                   t           \
  84          */                                                             \
  85                                                                         \
  86         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_SPLAY))         \
  87              fputs("XYLA-SPLAY SPLAY zig-zig "                          \
  88                    #left "/" #left " child\n", xyla__verbout); )        \
  89         t = SPLAY_NODE(n->bt.right);                                    \
  90         p->bt.left = t ? &t->bt : 0; if (t) t->spl.parent = p;          \
  91         n->bt.right = &p->bt; p->spl.parent = n;                        \
  92         n->bt.left = r ? &r->bt : 0; if (r) r->spl.parent = n;          \
  93         r = n;                                                          \
  94         break;                                                          \
  95       case (SPLAY_##RIGHT << 2) | (SPLAY_##LEFT << 1):                  \
  96         /* Zig-zag case: right child of a left child.                   \
  97          *                                                              \
  98          *           p                                                  \
  99          *             (*)                            c                 \
 100          *     n     /     \                            ( )             \
 101          *       (*)                            n     /     \     p     \
 102          *      /   \    c              --->      (*)         (*)       \
 103          *           ( )                         /   \       /   \      \
 104          *          /   \                              l   r            \
 105          *        l       r                                             \
 106          */                                                             \
 107                                                                         \
 108         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_SPLAY))         \
 109              fputs("XYLA-SPLAY SPLAY zig-zag "                          \
 110                    #left "/" #right " child\n", xyla__verbout); )       \
 111         p->bt.left = r ? &r->bt : 0; if (r) r->spl.parent = p;          \
 112         n->bt.right = l ? &l->bt : 0; if (l) l->spl.parent = n;         \
 113         l = n; r = p;                                                   \
 114         break;
 115
 116       SPLAY_ZZ(left, LEFT, l, right, RIGHT, r);
 117       SPLAY_ZZ(right, RIGHT, r, left, LEFT, l);
 118
 119 #undef SPLAY_ZZ
 120     }
 121
 122     /* Update the node and its parent.  The ascending child still hasn't
 123      * found its level yet.
 124      */
 125     if (updfn) { updfn(cls, &p->bt); updfn(cls, &n->bt); }
 126
 127     /* Ascend the tree. */
 128     n = g;
 129   }
 130
 131   /* Fix up the remaining link from the (old) root. */
 132   if ((trail&1) == SPLAY_LEFT)
 133 #define SPLAY_Z(left, l, right, r) do {                                 \
 134     /* Zig case: left child of the root.                                \
 135      *                                                                  \
 136      *                 n                                c               \
 137      *                   (*)                        ( )                 \
 138      *           c     /     \                    /     \     n         \
 139      *             ( )                  --->    l         (*)           \
 140      *            /   \                                  /   \          \
 141      *          l       r                              r                \
 142      */                                                                 \
 143                                                                         \
 144     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_SPLAY))             \
 145          fputs("XYLA-SPLAY SPLAY zig "                                  \
 146                #left " child\n", xyla__verbout); )                      \
 147     n->bt.left = r ? &r->bt : 0; if (r) r->spl.parent = n;              \
 148     r = n;                                                              \
 149 } while (0)
 150     SPLAY_Z(left, l, right, r);
 151   else
 152     SPLAY_Z(right, r, left, l);
 153 #undef SPLAY_Z
 154
 155   if (updfn) updfn(cls, &n->bt);
 156
 157 end:
 158   /* All done. */
 159   *left_inout = l ? &l->bt : 0; *right_inout = r ? &r->bt : 0;
 160 }
 161
 162 void xyla__splay_splay(struct xyla_bt_nodecls *cls,
 163                        struct xyla_splay_node *node)
 164 {
 165   /* Splay the tree at NODE.  The NODE becomes the new tree root; updating
 166    * this is the caller's responsibility.  The NODE is /not/ updated, since
 167    * the caller may want to make further changes before it's ready.
 168    */
 169
 170   struct xyla_splay_node *parent, *left, *right;
 171
 172   /* Determine the node's parent. */
 173   parent = node->spl.parent;
 174
 175   if (parent) {
 176     /* There's a parent, so the tree needs updating. */
 177
 178     /* Split the tree and update the links. */
 179     xyla__splay_split(cls, &node->bt.left, &node->bt.right, parent,
 180                       parent->bt.left == &node->bt ?
 181                         SPLAY_LEFT : SPLAY_RIGHT);
 182
 183     /* Fix the parent links in the node and left and right subtree roots. */
 184     left = SPLAY_NODE(node->bt.left); if (left) left->spl.parent = node;
 185     right = SPLAY_NODE(node->bt.right); if (right) right->spl.parent = node;
 186     node->spl.parent = 0;
 187   }
 188 }
 189
 190 void *xyla__splay_join(struct xyla_bt_nodecls *cls,
 191                        struct xyla_splay_node *left,
 192                        struct xyla_splay_node *right)
 193 {
 194   /* Join the two trees LEFT and RIGHT, without an intervening node.  The
 195    * input tree roots' parent links need not be cleared before calling.
 196    */
 197
 198   struct xyla_splay_node *next, *node;
 199   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 200
 201   if (!left) {
 202     /* There's no left tree, so the combined tree is simply the right tree.
 203      * If the right tree isn't empty, then clear its parent link.
 204      */
 205
 206     if (right) right->spl.parent = 0;
 207     node = right;
 208   } else if (!right) {
 209     /* There's no right tree, so the combined tree is simply the left tree.
 210      * The left tree is definitely not empty, or we'd have taken the previous
 211      * case.
 212      */
 213
 214     left->spl.parent = 0;
 215     node = left;
 216   } else {
 217     /* Both trees are non-empty.  Splay the right tree at its leftmost node.
 218      * It's left link becomes null, so hook the left tree in its place.
 219      */
 220
 221     /* Clear the root's parent link, and find the leftmost node. */
 222     node = right; node->spl.parent = 0;
 223     for (;;) {
 224       next = SPLAY_NODE(node->bt.left); if (!next) break;
 225       node = next;
 226     }
 227
 228     /* Splay, and hook the left tree in place. */
 229     xyla__splay_splay(cls, node);
 230     node->bt.left = &left->bt; left->spl.parent = node;
 231
 232     /* Update the new root. */
 233     if (updfn) updfn(cls, &node->bt);
 234   }
 235   return (node);
 236 }
 237
 238 unsigned xyla__splay_resolve_path(struct xyla_splay_path *path)
 239 {
 240   /* The PATH must be empty -- i.e., refer to a null link rather than a real
 241    * node -- and nontrivial -- so the tree must not be empty.  If the tree
 242    * has been reorganized since the path was constructed, then the `gap'
 243    * referred to by the path may have moved, so that the link referenced
 244    * isn't actually null any more.  Modify the PATH so that it refers to the
 245    * actual null link at the same position in the tree's ordering, and return
 246    * `SPLAY_LEFT' or `SPLAY_RIGHT' suitable for calling `xyla__splay_split'.
 247    */
 248
 249   struct xyla_splay_node *node = path->node, *next;
 250   unsigned side;
 251
 252   if (path->f&XYLA_SPF_LEFT)
 253 #define RESOLVE(left, LEFT, right, RIGHT) do {                          \
 254     /* The original link is on the left of the node. */                 \
 255                                                                         \
 256     if (!node->bt.left)                                                 \
 257       /* The left link is still null.  Just roll with it. */            \
 258                                                                         \
 259       side = SPLAY_##LEFT;                                              \
 260     else {                                                              \
 261       /* Descend into to the left subtree and work all the way          \
 262        * rightwards.                                                    \
 263        */                                                               \
 264                                                                         \
 265       node = SPLAY_NODE(node->bt.left);                                 \
 266       for (;;) {                                                        \
 267         next = SPLAY_NODE(node->bt.right);                              \
 268         if (!next) break;                                               \
 269         node = next;                                                    \
 270       }                                                                 \
 271       side = SPLAY_##RIGHT; path->node = node;                          \
 272       path->f = XYLA_SPF_##RIGHT;                                       \
 273     }                                                                   \
 274 } while (0)
 275     RESOLVE(left, LEFT, right, RIGHT);
 276   else
 277     RESOLVE(right, RIGHT, left, LEFT);
 278 #undef RESOLVE
 279   return (side);
 280 }
 281
 282 void xyla_splay_splay(struct xyla_bt_nodecls *cls,
 283                       struct xyla_splay_path *path)
 284 {
 285   /* Promote the node designated by the PATH to the root.  Call this after
 286    * `xyla_splay_probe' if you're not about to do anything else with the
 287    * path.
 288    */
 289
 290   struct xyla_splay_node *node;
 291   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 292
 293   node = path->node;
 294   if (node) {
 295     xyla__splay_splay(cls, node); *path->root = &node->bt;
 296     if (updfn) updfn(cls, &node->bt);
 297   }
 298 }
 299
 300 /*----- That's all, folks -------------------------------------------------*/