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

   1 /* -*-c-*-
   2  *
   3  * Path utilities 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 void *xyla_avl_current(const struct xyla_avl_path *path)
  34 {
  35   /* Return the node currently designated by PATH, or null if PATH is
  36    * empty.
  37    */
  38
  39   return (XYLA_BT_CURRENT(path->p, path->k));
  40 }
  41
  42 void xyla_avl_copypath(struct xyla_avl_path *newpath,
  43                        const struct xyla_avl_path *path)
  44 {
  45   /* Make a copy of PATH as NEWPATH.  This has the same effect as simply
  46    * assigning the path structures, but may be significantly faster because
  47    * it only copies the active part of the path vector.
  48    */
  49
  50   int k = path->k;
  51
  52   XYLA_BT_COPYPATH(newpath->p, path->p, k);
  53   newpath->k = k;
  54 }
  55
  56 void *xyla_avl_firstpath(struct xyla_bt_node **root,
  57                          struct xyla_avl_path *path)
  58 {
  59   /* Return the first node in the tree, together with a PATH to the requested
  60    * node, which can be used to remove them, or to navigate to other nodes in
  61    * the tree.  Return null if the tree is empty.
  62    */
  63
  64   struct xyla_bt_node *node;
  65   int rc;
  66
  67   XYLA_BT_EXTRMPATH(rc, node, root, path->p, path->k, left, XYLA_AVL_HTMAX);
  68     XYLA__ASSERT(!rc);
  69   return (node);
  70 }
  71
  72 void *xyla_avl_lastpath(struct xyla_bt_node **root,
  73                         struct xyla_avl_path *path)
  74 {
  75   /* Return the last node in the tree, together with a PATH to the requested
  76    * node, which can be used to remove them, or to navigate to other nodes in
  77    * the tree.  Return null if the tree is empty.
  78    */
  79
  80   struct xyla_bt_node *node;
  81   int rc;
  82
  83   XYLA_BT_EXTRMPATH(rc, node, root, path->p, path->k, right, XYLA_AVL_HTMAX);
  84     XYLA__ASSERT(!rc);
  85   return (node);
  86 }
  87
  88 void *xyla_avl_nextpath(struct xyla_avl_path *path)
  89 {
  90   /* Return the next node in the tree, and update the PATH to the requested
  91    * node, which can be used to remove them, or to navigate to other nodes in
  92    * the tree.
  93    *
  94    * If the path is full, i.e., refers to an existing node, then the function
  95    * returns that node's successor.  If the path is empty, i.e., refers to a
  96    * space between nodes where a new node can be inserted, then the function
  97    * returns the node at the upper end of the gap, unless the `gap' is
  98    * actually at the extreme right of the tree and no such node exists.  In
  99    * the latter case, a null pointer is returned.  The path is modified to
 100    * refer to the new node, if any, or to the gap at the extreme right of the
 101    * tree.
 102    */
 103
 104   struct xyla_bt_node *node;
 105   int rc;
 106
 107   XYLA_BT_STEPPATH(rc, node, path->p, path->k, right, left, XYLA_AVL_HTMAX);
 108     XYLA__ASSERT(!rc);
 109   return (node);
 110 }
 111
 112 void *xyla_avl_prevpath(struct xyla_avl_path *path)
 113 {
 114   /* Return the previous node in the tree, and update the PATH to the
 115    * requested node, which can be used to remove them, or to navigate to
 116    * other nodes in the tree.
 117    *
 118    * If the path is full, i.e., refers to an existing node, then the function
 119    * returns that node's predecessor.  If the path is empty, i.e., refers to
 120    * a space between nodes where a new node can be inserted, then the
 121    * function returns the node at the lower end of the gap, unless the `gap'
 122    * is actually at the extreme left of the tree and no such node exists.  In
 123    * the latter case, a null pointer is returned.  The path is modified to
 124    * refer to the new node, if any, or to the gap at the extreme left of the
 125    * tree.
 126    */
 127
 128   struct xyla_bt_node *node;
 129   int rc;
 130
 131   XYLA_BT_STEPPATH(rc, node, path->p, path->k, left, right, XYLA_AVL_HTMAX);
 132     XYLA__ASSERT(!rc);
 133   return (node);
 134 }
 135
 136 void xyla_avl_beforepath(struct xyla_avl_path *path)
 137 {
 138   /* Advance the PATH to just before the current node.  The path thereby
 139    * becomes empty, suitable to insert an element or split the tree just
 140    * before the previously selected node.
 141    */
 142
 143   int rc;
 144
 145   XYLA_BT_NUDGEPATH(rc, path->p, path->k, left, right, XYLA_AVL_HTMAX);
 146     XYLA__ASSERT(!rc);
 147 }
 148
 149 void xyla_avl_afterpath(struct xyla_avl_path *path)
 150 {
 151   /* Advance the PATH to just after the current node.  The path thereby
 152    * becomes empty, suitable to insert an element or split the tree just
 153    * after the previously selected node.
 154    */
 155
 156   int rc;
 157
 158   XYLA_BT_NUDGEPATH(rc, path->p, path->k, right, left, XYLA_AVL_HTMAX);
 159     XYLA__ASSERT(!rc);
 160 }
 161
 162 void *xyla_avl_rootpath(struct xyla_bt_node **root,
 163                         struct xyla_avl_path *path)
 164 {
 165   /* Initialize PATH to refer to the tree root, given the address ROOT of the
 166    * root link, and return this root node.  The resulting path will be empty
 167    * if and only if the tree is empty.
 168    */
 169
 170   struct xyla_bt_node *node;
 171
 172   XYLA_BT_ROOTPATH(node, root, path->p, path->k);
 173   return (node);
 174 }
 175
 176 void *xyla_avl_uppath(unsigned *pos_out, struct xyla_avl_path *path)
 177 {
 178   /* Update the PATH to refer to the parent of the link currently designated;
 179    * return this parent node, and set *POS_OUT to the `XYLA_BTPOS_...'
 180    * constant describing the link's relation to the parent.  If the path
 181    * initially designated the tree's root link, then return null, set
 182    * *POS_OUT to `XYLA_BTPOS_ROOT', and leave the path unchanged; otherwise,
 183    * the tree becomes full.
 184    */
 185
 186   struct xyla_bt_node *node;
 187
 188   XYLA_BT_PARENTPATH(node, *pos_out, path->p, path->k);
 189   return (node);
 190 }
 191
 192 void *xyla_avl_leftpath(struct xyla_avl_path *path)
 193 {
 194   /* Update the PATH to refer to the left child of the node currently
 195    * designated, and set NODE to be this child node.  The PATH must initially
 196    * have been full, and may become empty as a result.
 197    */
 198
 199   struct xyla_bt_node *node;
 200   int rc;
 201
 202   XYLA_BT_CHILDPATH(rc, node, path->p, path->k, left, XYLA_AVL_HTMAX);
 203     XYLA__ASSERT(!rc);
 204   return (node);
 205 }
 206
 207 void *xyla_avl_rightpath(struct xyla_avl_path *path) {
 208   /* Update the PATH to refer to the right child of the node currently
 209    * designated, and set NODE to be this child node.  The PATH must initially
 210    * have been full, and may become empty as a result.
 211    */
 212
 213   struct xyla_bt_node *node;
 214   int rc;
 215
 216   XYLA_BT_CHILDPATH(rc, node, path->p, path->k, right, XYLA_AVL_HTMAX);
 217     XYLA__ASSERT(!rc);
 218   return (node);
 219 }
 220
 221 void xyla_avl_replace(const struct xyla_avl_path *path,
 222                       struct xyla_avl_node *node)
 223 {
 224   /* Replace the node identified by the PATH with the given NODE.  The node's
 225    * links need not be initialized.  Paths and iterators are not invalidated.
 226    * It is the caller's responsibility to ensure that any ordering invariants
 227    * are respected as a result of the change.
 228    */
 229
 230   struct xyla_avl_node *old_node;
 231   int k = path->k;
 232
 233   old_node = AVL_NODE(*path->p[k]); XYLA__ASSERT(old_node);
 234
 235   node->bt = old_node->bt;
 236   node->avl.f =
 237     (node->avl.f&~XYLA_AVLF_BALMASK) | (old_node->avl.f&XYLA_AVLF_BALMASK);
 238 }
 239
 240 void xyla_avl_ripple(struct xyla_bt_nodecls *cls,
 241                      const struct xyla_avl_path *path)
 242 {
 243   /* Update a node's ancestors -- i.e., call the node class `upd' function on
 244    * them, in ascending order -- after it has been modified.  The PATH
 245    * describes a full path to the node that has been changed.  The PATH
 246    * remains valid.
 247    */
 248
 249   XYLA_BT_RIPPLE(cls, path->p, path->k);
 250 }
 251
 252 int xyla_avl_ascend(xyla_bt_ascendfn *fn,
 253                     const struct xyla_avl_path *path, void *arg)
 254 {
 255   /* Ascend the tree along the PATH, allowing FN to accumulate summary data
 256    * from the nodes to the root; see `XYLA_BT_ASCEND' for details.  If FN
 257    * returns nonzero, then stop and return the nonzero value; otherwise
 258    * return zero.  The PATH remains valid.
 259    */
 260
 261   int rc;
 262
 263   XYLA_BT_ASCEND(rc, fn, path->p, path->k, arg);
 264   return (rc);
 265 }
 266
 267 /*----- That's all, folks -------------------------------------------------*/