chiark - git - mdw - xyla/blob - splay.h

   1 /* -*-c-*-
   2  *
   3  * 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 #ifndef XYLA_SPLAY_H
  27 #define XYLA_SPLAY_H
  28
  29 /*----- Header files ------------------------------------------------------*/
  30
  31 #include "bt.h"
  32
  33 /*----- Data structures ---------------------------------------------------*/
  34
  35 struct xyla_splay_nodeslots {
  36   struct xyla_splay_node *parent;
  37 };
  38 #define XYLA_SPLAY_NODEPFX XYLA_BT_NODEPFX; struct xyla_splay_nodeslots spl
  39 struct xyla_splay_node { XYLA_SPLAY_NODEPFX; };
  40 #define XYLA_SPLAY_NODEUSFX struct xyla_splay_node spl; XYLA_BT_NODEUSFX
  41 union xyla_splay_nodeu { XYLA_SPLAY_NODEUSFX; };
  42
  43 /* In the case of algorithmically balanced trees such as AVL or red-black
  44  * trees, we have the happy situation where we can derive a useful upper
  45  * bound on the height of a tree with n nodes; in the case of treaps, we can
  46  * at least determine a distribution on tree heights and therefore a bound
  47  * which will be exceeded only with negligible probability independent of the
  48  * data access pattern.  In the current case of splay trees, we have no way
  49  * to determine even a probabilistic static bound.
  50  *
  51  * In an earlier version, and following Ben Pfaff's `Performance Analysis of
  52  * BSTs in System Software' (SIGMETRICS/Performance 2004),
  53  *
  54  *      https://web.stanford.edu/~blp/papers/libavl.pdf ,
  55  *
  56  * I reserved a fixed-sized vector for iterators and paths, and forcibly
  57  * rebalanced the tree if the depth bounds were exceeded.  Pfaff reported
  58  * that rebalancing didn't occur in splay trees; in my testing, however, I
  59  * found that rebalancing occurred fairly frequently and was a significant
  60  * performance cost.
  61  *
  62  * Instead, this implementation maintains a parent pointer in each node,
  63  * which allows constant-size iterators and paths to remain valid as the tree
  64  * is restructured.  It seems that splay trees occasionally become very deep
  65  * in unused parts of the structure, paying for the additional search and
  66  * restructuring cost when those parts are eventually accessed by better
  67  * performance for the parts of the tree accessed previously.
  68  */
  69
  70 struct xyla_splay_iter {
  71   const struct xyla_splay_node *top, *next;
  72 };
  73 struct xyla_splay_riter {
  74   const struct xyla_splay_node *top, *next;
  75 };
  76
  77 struct xyla_splay_path {
  78   unsigned f;
  79 #define XYLA_SPF_LEFT 1u
  80 #define XYLA_SPF_RIGHT 2u
  81   struct xyla_bt_node **root;
  82   struct xyla_splay_node *node;
  83 };
  84
  85 /* We still need a static bound for the set operations.  These will forcibly
  86  * rebalance as necessary.  Performance may suffer as a result, so splay
  87  * trees may be a poor choice for large sets.
  88  */
  89 #define XYLA_SPLAY_HTMAX 128
  90
  91 /*----- Machinery ---------------------------------------------------------*/
  92
  93 extern void xyla_splay_splay(struct xyla_bt_nodecls */*cls*/,
  94                              struct xyla_splay_path */*path*/);
  95   /* Promote the node designated by the PATH to the root.  Call this after
  96    * `xyla_splay_probe' if you're not about to do anything else with the
  97    * path.
  98    */
  99
 100 extern void xyla_splay_rebalance(struct xyla_bt_nodecls */*cls*/,
 101                                  struct xyla_bt_node **/*root*/);
 102   /* Force the tree whose root link is at ROOT to be rebalanced.
 103    *
 104    * The tree is restructured so as to have minimal height.  Weight balance
 105    * is not guaranteed, and, currently, at any rate, the rightmost portions
 106    * of the tree are likely to be quite light if the number of nodes is far
 107    * from a power of 2.
 108    */
 109
 110 /*----- Iteration ---------------------------------------------------------*/
 111
 112 /* Iteration doesn't work like the other trees in this library, because we
 113  * have parent pointers.  Instead, the `iterator' simply keeps track of the
 114  * /next/ node to return.
 115  */
 116
 117 extern void xyla_splay_inititer(const struct xyla_bt_node */*root*/,
 118                                 struct xyla_splay_iter */*it*/);
 119   /* Initialize the iterator IT to start returning nodes from the tree rooted
 120    * at ROOT.
 121    */
 122
 123 extern void *xyla_splay_next(struct xyla_splay_iter */*it*/);
 124   /* Advances a tree iterator.  Inserting or removing elements does /not/
 125    * invalidate the iterator.  It is permitted to free all of the nodes by
 126    * iterating over the tree in the obvious manner:
 127    *
 128    *    xyla_splay_inititer(tree, &it);
 129    *    for (;;) {
 130    *      node = xyla_splay_next(&it); if (!node) break;
 131    *      free(node);
 132    *    }
 133    *
 134    * It's probably better to use `xyla_bt_severfirst' for this task.
 135    */
 136
 137 extern void xyla_splay_initriter(const struct xyla_bt_node */*root*/,
 138                                  struct xyla_splay_riter */*rit*/);
 139   /* Initialize the iterator RIT to start returning nodes in right-to-left
 140    * order from the tree rooted at ROOT.
 141    */
 142
 143 extern void *xyla_splay_prev(struct xyla_splay_riter */*rit*/);
 144   /* Advance the iterator RIT, returning the previous node, or null if the
 145    * iteration is complete.
 146    *
 147    * Inserting or removing elements invalidates the iterator.  As a special
 148    * exception, it is permitted to free all of the nodes by iterating over
 149    * the tree in the obvious manner:
 150    *
 151    *    xyla_splay_inititer(tree, &rit);
 152    *    for (;;) {
 153    *      node = xyla_splay_next(&rit); if (!node) break;
 154    *      free(node);
 155    *    }
 156    *
 157    * It's probably better to use `xyla_bt_severfirst' for this task.
 158    */
 159
 160 /*----- Paths -------------------------------------------------------------*/
 161
 162 extern void *xyla_splay_current(const struct xyla_splay_path */*path*/);
 163   /* Return the node currently designated by PATH, or null if PATH is
 164    * empty.
 165    */
 166
 167 extern void xyla_splay_copypath(struct xyla_splay_path */*newpath*/,
 168                                 const struct xyla_splay_path */*path*/);
 169   /* Make a copy of PATH as NEWPATH.  This has the same effect as simply
 170    * assigning the path structures.
 171    */
 172
 173 extern void *xyla_splay_firstpath(struct xyla_bt_node **/*root*/,
 174                                   struct xyla_splay_path */*path*/);
 175 extern void *xyla_splay_lastpath(struct xyla_bt_node **/*root*/,
 176                                  struct xyla_splay_path */*path*/);
 177   /* Return the first or last node in the tree, together with a PATH to the
 178    * requested node, which can be used to remove them, or to navigate to
 179    * other nodes in the tree.  Return null if the tree is empty.
 180    */
 181
 182 extern void *xyla_splay_nextpath(struct xyla_splay_path */*path*/);
 183 extern void *xyla_splay_prevpath(struct xyla_splay_path */*path*/);
 184   /* Return the next or previous node in the tree, and update the PATH to the
 185    * requested node, which can be used to remove them, or to navigate to
 186    * other nodes in the tree.
 187    *
 188    * If the path is full, i.e., refers to an existing node, then the
 189    * functions return that node's successor or predecessor.  If the path is
 190    * empty, i.e., refers to a space between nodes where a new node can be
 191    * inserted, then the functions return the node at the upper or lower end
 192    * of the gap, unless the `gap' is actually at an extreme of the tree and
 193    * no such node exists.  In the latter case, a null pointer is returned.
 194    * The path is modified to refer to the new node, if any, or to the gap at
 195    * the appropriate extreme of the tree.
 196    */
 197
 198 extern void xyla_splay_beforepath(struct xyla_splay_path */*path*/);
 199 extern void xyla_splay_afterpath(struct xyla_splay_path */*path*/);
 200   /* Advance the PATH to just before or after the current node.  The path
 201    * thereby becomes empty, suitable to insert an element or split the tree
 202    * just before or after the previously selected node.
 203    */
 204
 205 extern void *xyla_splay_rootpath(struct xyla_bt_node **/*root*/,
 206                                  struct xyla_splay_path */*path*/);
 207   /* Initialize PATH to refer to the tree root, given the address ROOT of the
 208    * root link, and return this root node.  The resulting path will be empty
 209    * if and only if the tree is empty.
 210    */
 211
 212 extern void *xyla_splay_uppath(unsigned */*pos_out*/,
 213                                struct xyla_splay_path */*path*/);
 214   /* Update the PATH to refer to the parent of the link currently designated;
 215    * return this parent node, and set *POS_OUT to the `XYLA_BTPOS_...'
 216    * constant describing the link's relation to the parent.  If the path
 217    * initially designated the tree's root link, then return null, set
 218    * *POS_OUT to `XYLA_BTPOS_ROOT', and leave the path unchanged; otherwise,
 219    * the tree becomes full.
 220    */
 221
 222 extern void *xyla_splay_leftpath(struct xyla_splay_path */*path*/);
 223 extern void *xyla_splay_rightpath(struct xyla_splay_path */*path*/);
 224   /* Update the PATH to refer to the left or right child of the node
 225    * currently designated, and set NODE to be this child node.  The PATH must
 226    * initially have been full, and may become empty as a result.
 227    */
 228
 229 extern void xyla_splay_replace(const struct xyla_splay_path */*path*/,
 230                                struct xyla_splay_node */*node*/);
 231   /* Replace the node identified by the PATH with the given NODE.  The node's
 232    * links need not be initialized.  The replacement node's weight is copied
 233    * from the original.  Paths and iterators are not invalidated.  It is the
 234    * caller's responsibility to ensure that any ordering invariants are
 235    * respected as a result of the change.
 236    */
 237
 238 extern void xyla_splay_ripple(struct xyla_bt_nodecls */*cls*/,
 239                               const struct xyla_splay_path */*path*/);
 240   /* Update a node's ancestors -- i.e., call the node class `upd' function on
 241    * them, in ascending order -- after it has been modified.  The PATH
 242    * describes a full path to the node that has been changed.  The PATH
 243    * remains valid.
 244    */
 245
 246 extern int xyla_splay_ascend(xyla_bt_ascendfn */*fn*/,
 247                              const struct xyla_splay_path */*path*/,
 248                              void */*arg*/);
 249   /* Ascend the tree along the PATH, allowing FN to accumulate summary data
 250    * from the nodes to the root; see `XYLA_BT_ASCEND' for details.  If FN
 251    * returns nonzero, then stop and return the nonzero value; otherwise
 252    * return zero.  The PATH remains valid.
 253    */
 254
 255 /*----- Searching ---------------------------------------------------------*/
 256
 257 extern void *xyla_splay_lookup(struct xyla_bt_nodecls */*cls*/,
 258                                struct xyla_bt_node **/*root*/,
 259                                xyla_bt_navfn */*navfn*/, void */*arg*/);
 260   /* Search for a node within the tree rooted at ROOT.  The search is guided
 261    * by NAVFN, passing it ARG at each node.  Return the node that the
 262    * function matches, or null if no matching node exists.
 263    */
 264
 265 extern void *xyla_splay_probe(struct xyla_bt_nodecls */*cls*/,
 266                               struct xyla_bt_node **/*root*/,
 267                               xyla_bt_navfn */*navfn*/, void */*arg*/,
 268                               struct xyla_splay_path */*path*/);
 269   /* Search for a node within the tree rooted at ROOT.  The search is guided
 270    * by NAVFN, passing it ARG at each node.  Record the search path in PATH.
 271    * This can be used later, e.g., by `xyla_splay_insert' to insert a new
 272    * node if none was found, or by `xyla_splay_remove' to remove the node
 273    * that was found.  Return the node that the function matches, or null if
 274    * no matching node exists.
 275    */
 276
 277 /*----- Insertion and removal ---------------------------------------------*/
 278
 279 extern int xyla_splay_insert(struct xyla_bt_nodecls */*cls*/,
 280                              struct xyla_splay_path */*path*/,
 281                              struct xyla_splay_node */*node*/);
 282   /* Add a new node to the tree, in the place determined by the empty PATH.
 283    * It's the caller's responsibility to ensure that inserting the node here
 284    * respects any ordering invariants.
 285    *
 286    * The new node is not copied, and its storage must remain valid until the
 287    * node is removed or the tree is discarded.
 288    *
 289    * Returns `XYLA_RC_OK'.
 290    */
 291
 292 extern int xyla_splay_remove(struct xyla_bt_nodecls */*cls*/,
 293                              struct xyla_splay_path */*path*/);
 294   /* Remove the node identified by the PATH.  The node was allocated by the
 295    * caller, and should be freed by the caller in whatever way is
 296    * appropriate.
 297    *
 298    * Returns `XYLA_RC_OK'.
 299    */
 300
 301 /*----- Splitting and joining ---------------------------------------------*/
 302
 303 extern int xyla_splay_join(struct xyla_bt_nodecls */*cls*/,
 304                            struct xyla_bt_node **/*root_out*/,
 305                            struct xyla_bt_node **/*left*/,
 306                            struct xyla_bt_node */*mid*/,
 307                            struct xyla_bt_node **/*right*/);
 308   /* Concatenate the two trees rooted at LEFT and RIGHT in order; if MID is
 309    * not null, then place this node between them.  The root of the resulting
 310    * tree is stored in *ROOT_OUT.  It's the caller's responsibility to ensure
 311    * that this respects any ordering invariants.
 312    *
 313    * The ROOT_OUT pointer may equal either LEFT or RIGHT (or, indeed, both,
 314    * only if both are empty).  If LEFT is distinct from ROOT_OUT then *LEFT
 315    * is set null on exit; similarly, if RIGHT is distinct from ROOT_OUT, then
 316    * *RIGHT is set null on exit.
 317    *
 318    * Returns `XYLA_RC_OK'.
 319    */
 320
 321 extern int xyla_splay_split(struct xyla_bt_nodecls */*cls*/,
 322                             struct xyla_bt_node **/*left_out*/,
 323                             struct xyla_bt_node **/*mid_out*/,
 324                             struct xyla_bt_node **/*right_out*/,
 325                             struct xyla_splay_path */*path*/);
 326   /* Split a tree tree into two at the indicated place indicated by the PATH.
 327    * Store in *LEFT_OUT and *RIGHT_OUT the roots of trees containing every
 328    * node respectively preceding and following the PATH.
 329    *
 330    * If the PATH is full, i.e., it denotes a node in the input tree, then
 331    * that becomes the `middle node', which does not appear in either output
 332    * tree; a pointer to this node is stored in *MID_OUT.
 333    *
 334    * Returns `XYLA_RC_OK'.
 335    */
 336
 337 extern int xyla_splay_splitat(struct xyla_bt_nodecls */*cls*/,
 338                               struct xyla_bt_node **/*left_out*/,
 339                               struct xyla_bt_node **/*mid_out*/,
 340                               struct xyla_bt_node **/*right_out*/,
 341                               struct xyla_bt_node **/*root*/,
 342                               const void */*key*/);
 343   /* Split the tree rooted at ROOT into two at an indicated KEY.  Store in
 344    * *LEFT_OUT and *RIGHT_OUT the roots of trees containing every node whose
 345    * key is respectively less than and greater than the KEY.
 346    *
 347    * If a node matching the KEY exists in the input tree, then that becomes
 348    * the `middle node', which does not appear in either output tree; a
 349    * pointer to this node is stored in *MID_OUT.
 350    *
 351    * This operation assumes that the tree traversal ordering matches an
 352    * ordering on search keys, which is implemented by the node-class `nav'
 353    * function.
 354    *
 355    * Returns `XYLA_RC_OK'.
 356    */
 357
 358 extern int xyla_splay_splitroot(struct xyla_bt_node **/*left_out*/,
 359                                 struct xyla_bt_node **/*root_out*/,
 360                                 struct xyla_bt_node **/*right_out*/,
 361                                 struct xyla_bt_node **/*root*/);
 362   /* Split the tree rooted at ROOT into two at its root.  Store in *ROOT_OUT
 363    * a pointer to the original root node, or null if the tree was initially
 364    * empty; store in *LEFT_OUT and *RIGHT_OUT the root of the original root's
 365    * left and right subtrees respectively.
 366    *
 367    * Returns `XYLA_RC_OK'.
 368    */
 369
 370 /*----- Set operations ----------------------------------------------------*/
 371
 372 extern int xyla_splay_unisect(struct xyla_bt_nodecls */*cls*/,
 373                               struct xyla_bt_node **/*uni_out*/,
 374                               struct xyla_bt_node **/*isect_out*/,
 375                               struct xyla_bt_node **/*aroot*/,
 376                               struct xyla_bt_node **/*broot*/);
 377   /* Compute the union and intersection of two trees.
 378    *
 379    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
 380    * trees are considered to represent sets, with one element per node; the
 381    * element is determined by the `key' node-class operation.  On exit,
 382    * *UNI_OUT points to the root of a tree containing (one copy of) each
 383    * element present in either a or b, and *ISECT_OUT points to the root of a
 384    * tree containing the other copy of each element present in both a and b.
 385    * If AROOT and/or BROOT are distinct from UNI_OUT and ISECT_OUT, then null
 386    * pointers are stored in them.  The original trees are destroyed; each
 387    * node in the original operands trees ends up in exactly one of the result
 388    * trees.
 389    *
 390    * Returns `XYLA_RC_OK'.
 391    */
 392
 393 extern int xyla_splay_diffsect(struct xyla_bt_nodecls */*cls*/,
 394                                struct xyla_bt_node **/*diff_out*/,
 395                                struct xyla_bt_node **/*isect_out*/,
 396                                struct xyla_bt_node **/*aroot*/,
 397                                struct xyla_bt_node **/*broot*/);
 398   /* Compute the set difference of the two operand trees.
 399    *
 400    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
 401    * trees are considered to represent sets, with one element per node; the
 402    * element is determined by the `key' node-class operation.  On exit,
 403    * *DIFF_OUT points to the root of a tree containing each element of a but
 404    * not b, and *ISECT_OUT points to the root of a tree containing each
 405    * element of a that's also in b.  If AROOT and/or BROOT are distinct from
 406    * DIFF_OUT and ISECT_OUT, then null pointers are stored in them.  The
 407    * original a tree is destroyed; each node in the original operands trees
 408    * ends up in exactly one of the result trees.  The input b tree is
 409    * unchanged.
 410    *
 411    * Returns `XYLA_RC_OK'.
 412    */
 413
 414 /*----- Checking ----------------------------------------------------------*/
 415
 416 #ifndef XYLA_FREESTANDING
 417
 418 extern int xyla_splay_check(struct xyla_bt_nodecls */*cls*/,
 419                             struct xyla_bt_node *const */*root*/,
 420                             FILE */*fp*/, unsigned /*f*/,
 421                             void */*arg*/);
 422   /* Examine a treap, checking that it satisfies all of the necessary
 423    * invariants.  A splay tree has no special structural invariants: splay
 424    * trees are characterized by the algorithms that act on them, rather than
 425    * their static structure.  But we do need to check the parent links.
 426    *
 427    * This function uses the `xyla_bt_check' framework; see the description of
 428    * that function for details.  Returns `XYLA_RC_OK' on success,
 429    * `XYLA_RC_BAD' if problems are found, or some other code if verification
 430    * had to finish prematurely.
 431    */
 432
 433 #endif
 434
 435 /*----- That's all, folks -------------------------------------------------*/
 436
 437 #endif