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

   1 /* -*-c-*-
   2  *
   3  * Path 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 /* A path is much simpler than in other trees, again because we have parent
  34  * pointers.  We just keep track of the address of the root link, a node, and
  35  * some flags.  If the path designates to a node, then the path just
  36  * maintains a pointer to that node.  If it designates a null link, then
  37  * there are two cases: if the tree is empty, then the null root link is
  38  * indicated by a null node pointer; otherwise, the path holds the a pointer
  39  * to the parent node and a set flag indicating which of its child links is
  40  * designated.
  41  */
  42
  43 void *xyla_splay_current(const struct xyla_splay_path *path)
  44 {
  45   /* Return the node currently designated by PATH, or null if PATH is
  46    * empty.
  47    */
  48
  49   struct xyla_splay_node *node = path->node;
  50
  51   return (node && !path->f ? node : 0);
  52 }
  53
  54 void xyla_splay_copypath(struct xyla_splay_path *newpath,
  55                          const struct xyla_splay_path *path)
  56 {
  57   /* Make a copy of PATH as NEWPATH.  This has the same effect as simply
  58    * assigning the path structures.
  59    */
  60
  61   *newpath = *path;
  62 }
  63
  64 #define DEF_EXTRMPATH(op, OP, dir)                                      \
  65   void *xyla_splay_##op(struct xyla_bt_node **root,                     \
  66                         struct xyla_splay_path *path)                   \
  67   {                                                                     \
  68     /* Return the first or last node in the tree, together with a PATH  \
  69      * to the requested node, which can be used to remove them, or to   \
  70      * navigate to other nodes in the tree.  Return null if the tree    \
  71      * is empty.                                                        \
  72      */                                                                 \
  73                                                                         \
  74     struct xyla_splay_node *next,                                       \
  75       *node = SPLAY_NODE(*root);                                        \
  76                                                                         \
  77     /* Save the root link address. */                                   \
  78     path->root = root;                                                  \
  79                                                                         \
  80     /* Find the leftmost or rightmost node if there is one. */          \
  81     if (node)                                                           \
  82       for (;;) {                                                        \
  83         next = SPLAY_NODE(node->bt.dir);                                \
  84           if (!next) break;                                             \
  85         node = next;                                                    \
  86       }                                                                 \
  87                                                                         \
  88     /* All done.  The flags must be clear here: either the tree is      \
  89      * empty, and the `node' pointer is null, or the tree contains at   \
  90      * least one node, and we find the leftmost.                        \
  91      */                                                                 \
  92     path->node = node; path->f = 0; return (node);                      \
  93   }
  94
  95 DEF_EXTRMPATH(firstpath, FIRSTPATH, left)
  96 DEF_EXTRMPATH(lastpath, LASTPATH, right)
  97
  98 #undef DEF_EXTRMPATH
  99
 100 #define DEF_STEPPATH(op, OP, dir, DIR, opp, OPP)                        \
 101   void *xyla_splay_##op(struct xyla_splay_path *path)                   \
 102   {                                                                     \
 103     /* Return the next or previous node in the tree, and update the     \
 104      * PATH to the requested node, which can be used to remove them,    \
 105      * or to navigate to other nodes in the tree.                       \
 106      *                                                                  \
 107      * If the path is full, i.e., refers to an existing node, then the  \
 108      * functions return that node's successor or predecessor.  If the   \
 109      * path is empty, i.e., refers to a space between nodes where a     \
 110      * new node can be inserted, then the functions return the node at  \
 111      * the upper or lower end of the gap, unless the `gap' is actually  \
 112      * at an extreme of the tree and no such node exists.  In the       \
 113      * latter case, a null pointer is returned.  The path is modified   \
 114      * to refer to the new node, if any, or to the gap at the           \
 115      * appropriate extreme of the tree.                                 \
 116      */                                                                 \
 117                                                                         \
 118     struct xyla_splay_node *next, *old, *node = path->node;             \
 119                                                                         \
 120     /* Resolve an empty path.  An intervening splay might have          \
 121      * rearranged the links, but the appropriate actions are clear.     \
 122      * If there's no node, then the tree must have been empty           \
 123      * initially.  If the gap is on the far side of the node, then we   \
 124      * return to the node.  If it's on the same side, then we want the  \
 125      * node's successor anyway.                                         \
 126      */                                                                 \
 127     if (!node) return (0);                                              \
 128     else if (path->f&XYLA_SPF_##OPP) { path->f = 0; return (node); }    \
 129                                                                         \
 130     next = SPLAY_NODE(node->bt.dir);                                    \
 131     if (next)                                                           \
 132       /* The node has a subtree in the appropriate direction, so        \
 133        * explore it.                                                    \
 134        */                                                               \
 135                                                                         \
 136       do {                                                              \
 137         node = next;                                                    \
 138         next = SPLAY_NODE(node->bt.opp);                                \
 139       } while (next);                                                   \
 140     else                                                                \
 141       /* Ascend the tree and find an ancestor on the correct side. */   \
 142                                                                         \
 143       for (;;) {                                                        \
 144         old = node; node = node->spl.parent;                            \
 145         if (!node) { path->f = XYLA_SPF_##DIR; return (0); }            \
 146         if (node->bt.opp == &old->bt) break;                            \
 147       }                                                                 \
 148                                                                         \
 149     path->node = node; path->f = 0; return (node);                      \
 150   }
 151
 152 DEF_STEPPATH(nextpath, NEXTPATH, right, RIGHT, left, LEFT)
 153 DEF_STEPPATH(prevpath, PREVPATH, left, LEFT, right, RIGHT)
 154
 155 #undef DEF_STEPPATH
 156
 157 #define DEF_NUDGEPATH(op, OP, dir, DIR)                                 \
 158   void xyla_splay_##op(struct xyla_splay_path *path)                    \
 159   {                                                                     \
 160     /* Advance the PATH to just before or after the current node.  The  \
 161      * path thereby becomes empty, suitable to insert an element or     \
 162      * split the tree just before or after the previously selected      \
 163      * node.                                                            \
 164      */                                                                 \
 165                                                                         \
 166     /* Very lazy: just designate the appropriate link of the current    \
 167      * node, and expect everything else to cope.  If anyone asks,       \
 168      * pretend that we did everything properly, but the tree was        \
 169      * splayed afterwards.                                              \
 170      */                                                                 \
 171     XYLA__ASSERT(path->node && !path->f); path->f = XYLA_SPF_##DIR;     \
 172   }
 173
 174 DEF_NUDGEPATH(beforepath, BEFOREPATH, left, LEFT)
 175 DEF_NUDGEPATH(afterpath, AFTERPATH, right, RIGHT)
 176
 177 #undef DEF_NUDGEPATH
 178
 179 void *xyla_splay_rootpath(struct xyla_bt_node **root,
 180                           struct xyla_splay_path *path)
 181 {
 182   /* Initialize PATH to refer to the tree root, given the address ROOT of the
 183    * root link, and return this root node.  The resulting path will be empty
 184    * if and only if the tree is empty.
 185    */
 186
 187   struct xyla_bt_node *node;
 188
 189   node = *root; path->node = SPLAY_NODE(node);
 190   path->f = 0; return (node);
 191 }
 192
 193 void *xyla_splay_uppath(unsigned *pos_out, struct xyla_splay_path *path)
 194 {
 195   /* Update the PATH to refer to the parent of the link currently designated;
 196    * return this parent node, and set *POS_OUT to the `XYLA_BTPOS_...'
 197    * constant describing the link's relation to the parent.  If the path
 198    * initially designated the tree's root link, then return null, set
 199    * *POS_OUT to `XYLA_BTPOS_ROOT', and leave the path unchanged; otherwise,
 200    * the tree becomes full.
 201    */
 202
 203   struct xyla_splay_node *node, *parent;
 204   unsigned f, dir;
 205
 206   if (!path->node)
 207     { *pos_out = XYLA_BTPOS_ROOT; return (0); }
 208   else {
 209     node = path->node; f = path->f;
 210     if (f&XYLA_SPF_LEFT) {
 211       if (!node->bt.left)
 212         { path->f = 0; *pos_out = XYLA_BTPOS_LEFT; return (node); }
 213       else {
 214         dir = xyla__splay_resolve_path(path);
 215         *pos_out = dir == SPLAY_LEFT ? XYLA_BTPOS_LEFT : XYLA_BTPOS_RIGHT;
 216         path->f = 0; return (path->node);
 217       }
 218     } else if (f&XYLA_SPF_RIGHT) {
 219       if (!node->bt.right)
 220         { path->f = 0; *pos_out = XYLA_BTPOS_RIGHT; return (node); }
 221       else {
 222         dir = xyla__splay_resolve_path(path);
 223         *pos_out = dir == SPLAY_LEFT ? XYLA_BTPOS_LEFT : XYLA_BTPOS_RIGHT;
 224         path->f = 0; return (path->node);
 225       }
 226     } else {
 227       parent = node->spl.parent;
 228       if (!parent)
 229         { *pos_out = XYLA_BTPOS_ROOT; return (0); }
 230       else if (parent->bt.left == &node->bt) {
 231         *pos_out = XYLA_BTPOS_LEFT; path->node = parent;
 232         return (parent);
 233       } else {
 234         *pos_out = XYLA_BTPOS_RIGHT; path->node = parent;
 235         return (parent);
 236       }
 237     }
 238   }
 239 }
 240
 241 #define DEF_CHILDPATH(dir, DIR)                                         \
 242   void *xyla_splay_##dir##path(struct xyla_splay_path *path)            \
 243   {                                                                     \
 244     /* Update the PATH to refer to the left (if DIR is `left') or       \
 245      * right (if DIR is `right') child of the node currently            \
 246      * designated, and set NODE to be this child node.  The PATH must   \
 247      * initially have been full, and may become empty as a result.      \
 248      */                                                                 \
 249                                                                         \
 250     struct xyla_splay_node *node;                                       \
 251                                                                         \
 252     node = path->node; XYLA__ASSERT(node); XYLA__ASSERT(!path->f);      \
 253     node = SPLAY_NODE(node->bt.dir);                                    \
 254     if (!node) path->f = XYLA_SPF_##DIR;                                \
 255     else path->node = node;                                             \
 256     return (node);                                                      \
 257   }
 258
 259 DEF_CHILDPATH(left, LEFT)
 260 DEF_CHILDPATH(right, RIGHT)
 261
 262 #undef DEF_CHILDPATH
 263
 264 void xyla_splay_replace(const struct xyla_splay_path *path,
 265                         struct xyla_splay_node *node)
 266 {
 267   /* Replace the node identified by the PATH with the given NODE.  The node's
 268    * links need not be initialized.  The replacement node's weight is copied
 269    * from the original.  Paths and iterators are not invalidated.  It is the
 270    * caller's responsibility to ensure that any ordering invariants are
 271    * respected as a result of the change.
 272    */
 273
 274   struct xyla_splay_node *old_node, *left, *right;
 275
 276   old_node = path->node; XYLA__ASSERT(old_node);
 277   left = SPLAY_NODE(old_node->bt.left);
 278   right = SPLAY_NODE(old_node->bt.right);
 279
 280   node->bt = old_node->bt;
 281   node->spl.parent = old_node->spl.parent;
 282   if (left) left->spl.parent = node;
 283   if (right) right->spl.parent = node;
 284 }
 285
 286 void xyla_splay_ripple(struct xyla_bt_nodecls *cls,
 287                        const struct xyla_splay_path *path)
 288 {
 289   /* Update a node's ancestors -- i.e., call the node class `upd' function on
 290    * them, in ascending order -- after it has been modified.  The PATH
 291    * describes a full path to the node that has been changed.  The PATH
 292    * remains valid.
 293    */
 294
 295   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 296   struct xyla_splay_node *node = path->node;
 297
 298   XYLA__ASSERT(node); XYLA__ASSERT(!path->f);
 299   for (;;) {
 300     node = node->spl.parent; if (!node) break;
 301     updfn(cls, &node->bt);
 302   }
 303 }
 304
 305 int xyla_splay_ascend(xyla_bt_ascendfn *fn,
 306                        const struct xyla_splay_path *path, void *arg)
 307 {
 308   /* Ascend the tree along the PATH, allowing FN to accumulate summary data
 309    * from the nodes to the root; see `XYLA_BT_ASCEND' for details.  If FN
 310    * returns nonzero, then stop and return the nonzero value; otherwise
 311    * return zero.  The PATH remains valid.
 312    */
 313
 314   struct xyla_splay_node *node, *parent;
 315   struct xyla_splay_path mypath;
 316   int rc;
 317
 318   node = path->node;
 319
 320   if (!node)
 321     rc = fn(0, 0, 0, XYLA_BTPOS_ROOT, arg);
 322   else {
 323     if (path->f) {
 324       mypath = *path; xyla__splay_resolve_path(&mypath); node = mypath.node;
 325       if (mypath.f&XYLA_SPF_LEFT)
 326         rc = fn(0, &node->bt, node->bt.right, XYLA_BTPOS_LEFT, arg);
 327       else
 328         rc = fn(0, &node->bt, node->bt.left, XYLA_BTPOS_RIGHT, arg);
 329       if (rc) return (rc);
 330     }
 331
 332     for (;;) {
 333       parent = node->spl.parent; if (!parent) break;
 334       if (&node->bt == parent->bt.left)
 335         rc = fn(&node->bt, &parent->bt, parent->bt.right,
 336                 XYLA_BTPOS_LEFT, arg);
 337       else
 338         rc = fn(&node->bt, &parent->bt, parent->bt.left,
 339                 XYLA_BTPOS_RIGHT, arg);
 340       if (rc) return (rc);
 341       node = parent;
 342     }
 343
 344     rc = fn(&node->bt, 0, 0, XYLA_BTPOS_ROOT, arg);
 345   }
 346   return (rc);
 347 }
 348
 349 /*----- That's all, folks -------------------------------------------------*/