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

   1 /* -*-c-*-
   2  *
   3  * Path utilities 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 void *xyla_rb_current(const struct xyla_rb_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_rb_copypath(struct xyla_rb_path *newpath,
  43                       const struct xyla_rb_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_rb_firstpath(struct xyla_bt_node **root,
  57                         struct xyla_rb_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_RB_HTMAX);
  68     XYLA__ASSERT(!rc);
  69   return (node);
  70 }
  71
  72 void *xyla_rb_lastpath(struct xyla_bt_node **root,
  73                        struct xyla_rb_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_RB_HTMAX);
  84     XYLA__ASSERT(!rc);
  85   return (node);
  86 }
  87
  88 void *xyla_rb_nextpath(struct xyla_rb_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_RB_HTMAX);
 108     XYLA__ASSERT(!rc);
 109   return (node);
 110 }
 111
 112 void *xyla_rb_prevpath(struct xyla_rb_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_RB_HTMAX);
 132     XYLA__ASSERT(!rc);
 133   return (node);
 134 }
 135
 136 void xyla_rb_beforepath(struct xyla_rb_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_RB_HTMAX);
 146     XYLA__ASSERT(!rc);
 147 }
 148
 149 void xyla_rb_afterpath(struct xyla_rb_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_RB_HTMAX);
 159     XYLA__ASSERT(!rc);
 160 }
 161
 162 void *xyla_rb_rootpath(struct xyla_bt_node **root,
 163                        struct xyla_rb_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_rb_uppath(unsigned *pos_out, struct xyla_rb_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_rb_leftpath(struct xyla_rb_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_RB_HTMAX);
 203     XYLA__ASSERT(!rc);
 204   return (node);
 205 }
 206
 207 void *xyla_rb_rightpath(struct xyla_rb_path *path)
 208 {
 209   /* Update the PATH to refer to the right child of the node currently
 210    * designated, and set NODE to be this child node.  The PATH must initially
 211    * have been full, and may become empty as a result.
 212    */
 213
 214   struct xyla_bt_node *node;
 215   int rc;
 216
 217   XYLA_BT_CHILDPATH(rc, node, path->p, path->k, right, XYLA_RB_HTMAX);
 218     XYLA__ASSERT(!rc);
 219   return (node);
 220 }
 221
 222 void xyla_rb_replace(const struct xyla_rb_path *path,
 223                      struct xyla_rb_node *node)
 224 {
 225   /* Replace the node identified by the PATH with the given NODE.  The node's
 226    * links need not be initialized.  Paths and iterators are not invalidated.
 227    * It is the caller's responsibility to ensure that any ordering invariants
 228    * are respected as a result of the change.
 229    */
 230
 231   struct xyla_rb_node *old_node;
 232   int k = path->k;
 233
 234   old_node = RB_NODE(*path->p[k]); XYLA__ASSERT(old_node);
 235
 236   node->bt = old_node->bt;
 237   node->rb.f = (node->rb.f&~XYLA_RBF_RED) | (old_node->rb.f&XYLA_RBF_RED);
 238 }
 239
 240 void xyla_rb_ripple(struct xyla_bt_nodecls *cls,
 241                     const struct xyla_rb_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_rb_ascend(xyla_bt_ascendfn *fn,
 253                    const struct xyla_rb_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 -------------------------------------------------*/