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

   1 /* -*-c-*-
   2  *
   3  * Treaps
   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_TREAP_H
  27 #define XYLA_TREAP_H
  28
  29 /*----- Header files ------------------------------------------------------*/
  30
  31 #include "bt.h"
  32
  33 /*----- Data structures ---------------------------------------------------*/
  34
  35 struct xyla_treap_nodeslots {
  36   size_t wt;
  37 };
  38 #define XYLA_TREAP_NODEPFX XYLA_BT_NODEPFX; struct xyla_treap_nodeslots trp
  39 struct xyla_treap_node { XYLA_TREAP_NODEPFX; };
  40 #define XYLA_TREAP_NODEUSFX struct xyla_treap_node trp; XYLA_BT_NODEUSFX
  41 union xyla_treap_nodeu { XYLA_TREAP_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.  The structure of a treap is
  46  * completely determined by its nodes' ordering and weights, if they are
  47  * distinct.  (The root is the lightest node; its left and right subtrees are
  48  * then treaps consisting of the nodes ordered before and and after the root,
  49  * respectively; their structure is uniquely determined, by induction, and
  50  * the claim follows.)
  51  *
  52  * Instead, we assume that the weights are assigned randomly and
  53  * independently of the node ordering.  A server inserting hostile data into
  54  * a treap must therefore ensure that its source of random weights is kept
  55  * secure, and this is left as the caller's responsibility.  This allows us
  56  * to determine a probabilistic bound on the treap's height.
  57  *
  58  * Rather than wade through all of the derivation, I'm just going to refer to
  59  *
  60  *      https://www.cse.wustl.edu/~angelee/archive/cse341/fall14/
  61  *
  62  * for the details.  The main results are as follows.  Let n be the number of
  63  * nodes in the treap, and for 0 <= k < n, let D_k be the depth of node k.
  64  * Then (Lecture 19)
  65  *
  66  *      μ_k = E[D_k] = H_k + H_{n-k-1} ,
  67  *
  68  * so
  69  *
  70  *      log n <= μ_k <= 2 log n ,
  71  *
  72  * and a Chernoff bound (Lecture 20) gives
  73  *
  74  *                              (      (λ - 1)^2 )
  75  *      Pr[D_k >= λ μ_k] <= exp ( -μ_k --------- ) .
  76  *                              (        λ + 1   )
  77  *
  78  * Substituting gives
  79  *
  80  *                                  (          (λ - 1)^2 )
  81  *      Pr[D_k >= 2 λ log n] <= exp ( -(log n) --------- )
  82  *                                  (            λ + 1   )
  83  *
  84  *                                       1
  85  *                            = ----------------- .
  86  *                              n^{(λ-1)^2/(λ+1)}
  87  *
  88  * If H_n is the height of an n-node tree, then
  89  *
  90  *                                       1
  91  *      Pr[H_n >= 2 λ log n] <= -------------------
  92  *                              n^{(λ-1)^2/(λ+1)-1}
  93  *
  94  *                                     1
  95  *                            = --------------- .
  96  *                              n^{λ(λ-3)(λ+1)}
  97  *
  98  * Suppose we want to bound Pr[H_n >= 2 λ log n] <= ε, so
  99  *
 100  *             1
 101  *      --------------- <= ε .
 102  *      n^{λ(λ-3)(λ+1)}
 103  *
 104  * We can get Sage to grind through the algebra and tell us a lower bound
 105  * for λ.  When we substitute this back, we find that we want
 106  *
 107  *      H_n >= B_n = log 2 (√{(3 lg n)^2 - 10 lg n·lg ε + (lg ε)^2} +
 108  *                           3 lg n - lg ε) .
 109  *
 110  * We want to bound B_n from below, so
 111  *
 112  *      B_n = log 2 √{(5 lg n - lg ε)^2 - (4 lg n)^2} + 3 lg n - lg ε
 113  *
 114  *              <= log 2 (8 lg n - 2 lg ε)
 115  *
 116  *                 1
 117  *              <= - (28 lg n - 7 lg ε) .
 118  *                 5
 119  *
 120  * This estimate isn't particularly tight, but it will do.
 121  *
 122  * On conventional 32-bit targets, this is 359; on 64-bit targets, it's 538.
 123  */
 124
 125 #define XYLA_TREAP_NLGEPSILON 128
 126 #define XYLA_TREAP_HTMAX                                                \
 127         ((28*sizeof(size_t)*CHAR_BIT + 7*XYLA_TREAP_NLGEPSILON + 4)/5)
 128
 129 struct xyla_treap_iter {
 130   int sp;
 131   const struct xyla_bt_node *stack[XYLA_TREAP_HTMAX];
 132 };
 133 struct xyla_treap_riter {
 134   int sp;
 135   const struct xyla_bt_node *stack[XYLA_TREAP_HTMAX];
 136 };
 137
 138 struct xyla_treap_path {
 139   int k;
 140   struct xyla_bt_node **p[XYLA_TREAP_HTMAX + 1];
 141 };
 142
 143 /*----- Iteration ---------------------------------------------------------*/
 144
 145 extern void xyla_treap_inititer(const struct xyla_bt_node */*root*/,
 146                                 struct xyla_treap_iter */*it*/);
 147   /* Initialize the iterator IT to start returning nodes in left-to-right
 148    * order from the tree rooted at ROOT.
 149    */
 150
 151 extern void *xyla_treap_next(struct xyla_treap_iter */*it*/);
 152   /* Advances a tree iterator.  Inserting or removing elements invalidates
 153    * the iterator.  As a special exception, it is permitted to free all of
 154    * the nodes by iterating over the tree in the obvious manner:
 155    *
 156    *    xyla_treap_inititer(tree, &it);
 157    *    for (;;) {
 158    *      node = xyla_treap_next(&it); if (!node) break;
 159    *      free(node);
 160    *    }
 161    *
 162    * It's probably better to use `xyla_bt_severfirst' for this task.
 163    */
 164
 165 extern void xyla_treap_initriter(const struct xyla_bt_node */*root*/,
 166                                  struct xyla_treap_riter */*rit*/);
 167   /* Initialize the iterator RIT to start returning nodes in right-to-left
 168    * order from the tree rooted at ROOT.
 169    */
 170
 171 extern void *xyla_treap_prev(struct xyla_treap_riter */*rit*/);
 172   /* Advance the iterator RIT, returning the previous node, or null if the
 173    * iteration is complete.
 174    *
 175    * Inserting or removing elements invalidates the iterator.  As a special
 176    * exception, it is permitted to free all of the nodes by iterating over
 177    * the tree in the obvious manner:
 178    *
 179    *    xyla_treap_inititer(tree, &rit);
 180    *    for (;;) {
 181    *      node = xyla_treap_next(&rit); if (!node) break;
 182    *      free(node);
 183    *    }
 184    *
 185    * It's probably better to use `xyla_bt_severfirst' for this task.
 186    */
 187
 188 /*----- Paths -------------------------------------------------------------*/
 189
 190 extern void *xyla_treap_current(const struct xyla_treap_path */*path*/);
 191   /* Return the node currently designated by PATH, or null if PATH is
 192    * empty.
 193    */
 194
 195 extern void xyla_treap_copypath(struct xyla_treap_path */*newpath*/,
 196                                 const struct xyla_treap_path */*path*/);
 197   /* Make a copy of PATH as NEWPATH.  This has the same effect as simply
 198    * assigning the path structures, but may be significantly faster because
 199    * it only copies the active part of the path vector.
 200    */
 201
 202 extern void *xyla_treap_firstpath(struct xyla_bt_node **/*root*/,
 203                                   struct xyla_treap_path */*path*/);
 204 extern void *xyla_treap_lastpath(struct xyla_bt_node **/*root*/,
 205                                  struct xyla_treap_path */*path*/);
 206   /* Return the first or last node in the tree, together with a PATH to the
 207    * requested node, which can be used to remove them, or to navigate to
 208    * other nodes in the tree.  Return null if the tree is empty.
 209    */
 210
 211 extern void *xyla_treap_nextpath(struct xyla_treap_path */*path*/);
 212 extern void *xyla_treap_prevpath(struct xyla_treap_path */*path*/);
 213   /* Return the next or previous node in the tree, and update the PATH to the
 214    * requested node, which can be used to remove them, or to navigate to
 215    * other nodes in the tree.
 216    *
 217    * If the path is full, i.e., refers to an existing node, then the
 218    * functions return that node's successor or predecessor.  If the path is
 219    * empty, i.e., refers to a space between nodes where a new node can be
 220    * inserted, then the functions return the node at the upper or lower end
 221    * of the gap, unless the `gap' is actually at an extreme of the tree and
 222    * no such node exists.  In the latter case, a null pointer is returned.
 223    * The path is modified to refer to the new node, if any, or to the gap at
 224    * the appropriate extreme of the tree.
 225    */
 226
 227 extern void xyla_treap_beforepath(struct xyla_treap_path */*path*/);
 228 extern void xyla_treap_afterpath(struct xyla_treap_path */*path*/);
 229   /* Advance the PATH to just before or after the current node.  The path
 230    * thereby becomes empty, suitable to insert an element or split the tree
 231    * just before or after the previously selected node.
 232    */
 233
 234 extern void *xyla_treap_rootpath(struct xyla_bt_node **/*root*/,
 235                                  struct xyla_treap_path */*path*/);
 236   /* Initialize PATH to refer to the tree root, given the address ROOT of the
 237    * root link, and return this root node.  The resulting path will be empty
 238    * if and only if the tree is empty.
 239    */
 240
 241 extern void *xyla_treap_uppath(unsigned */*pos_out*/,
 242                                struct xyla_treap_path */*path*/);
 243   /* Update the PATH to refer to the parent of the link currently designated;
 244    * return this parent node, and set *POS_OUT to the `XYLA_BTPOS_...'
 245    * constant describing the link's relation to the parent.  If the path
 246    * initially designated the tree's root link, then return null, set
 247    * *POS_OUT to `XYLA_BTPOS_ROOT', and leave the path unchanged; otherwise,
 248    * the tree becomes full.
 249    */
 250
 251 extern void *xyla_treap_leftpath(struct xyla_treap_path */*path*/);
 252 extern void *xyla_treap_rightpath(struct xyla_treap_path */*path*/);
 253   /* Update the PATH to refer to the left or right child of the node
 254    * currently designated, and set NODE to be this child node.  The PATH must
 255    * initially have been full, and may become empty as a result.
 256    */
 257
 258 extern void xyla_treap_replace(const struct xyla_treap_path */*path*/,
 259                                struct xyla_treap_node */*node*/);
 260   /* Replace the node identified by the PATH with the given NODE.  The node's
 261    * links need not be initialized.  The replacement node's weight is copied
 262    * from the original.  Paths and iterators are not invalidated.  It is the
 263    * caller's responsibility to ensure that any ordering invariants are
 264    * respected as a result of the change.
 265    */
 266
 267 extern void xyla_treap_ripple(struct xyla_bt_nodecls */*cls*/,
 268                               const struct xyla_treap_path */*path*/);
 269   /* Update a node's ancestors -- i.e., call the node class `upd' function on
 270    * them, in ascending order -- after it has been modified.  The PATH
 271    * describes a full path to the node that has been changed.  The PATH
 272    * remains valid.
 273    */
 274
 275 extern int xyla_treap_ascend(xyla_bt_ascendfn */*fn*/,
 276                              const struct xyla_treap_path */*path*/,
 277                              void */*arg*/);
 278   /* Ascend the tree along the PATH, allowing FN to accumulate summary data
 279    * from the nodes to the root; see `XYLA_BT_ASCEND' for details.  If FN
 280    * returns nonzero, then stop and return the nonzero value; otherwise
 281    * return zero.  The PATH remains valid.
 282    */
 283
 284 /*----- Searching ---------------------------------------------------------*/
 285
 286 extern void *xyla_treap_lookup(struct xyla_bt_nodecls */*cls*/,
 287                                struct xyla_bt_node **/*root*/,
 288                                xyla_bt_navfn */*navfn*/, void */*arg*/);
 289   /* Search for a node within the tree rooted at ROOT.  The search is guided
 290    * by NAVFN, passing it ARG at each node.  Return the node that the
 291    * function matches, or null if no matching node exists.
 292    */
 293
 294 extern void *xyla_treap_probe(struct xyla_bt_nodecls */*cls*/,
 295                               struct xyla_bt_node **/*root*/,
 296                               xyla_bt_navfn */*navfn*/, void */*arg*/,
 297                               struct xyla_treap_path */*path*/);
 298   /* Search for a node within the tree rooted at ROOT.  The search is guided
 299    * by NAVFN, passing it ARG at each node.  Record the search path in PATH.
 300    * This can be used later, e.g., by `xyla_treap_insert' to insert a new
 301    * node if none was found, or by `xyla_treap_remove' to remove the node
 302    * that was found.  Return the node that the function matches, or null if
 303    * no matching node exists.
 304    */
 305
 306 /*----- Insertion and removal ---------------------------------------------*/
 307
 308 extern int xyla_treap_insert(struct xyla_bt_nodecls */*cls*/,
 309                              struct xyla_treap_path */*path*/,
 310                              struct xyla_treap_node */*node*/);
 311   /* Add a new node to the tree, in the place determined by the empty PATH.
 312    * It's the caller's responsibility to ensure that inserting the node here
 313    * respects any ordering invariants.
 314    *
 315    * The new node is not copied, and its storage must remain valid until the
 316    * node is removed or the tree is discarded.
 317    *
 318    * Returns `XYLA_RC_OK'.
 319    */
 320
 321 extern int xyla_treap_remove(struct xyla_bt_nodecls */*cls*/,
 322                              struct xyla_treap_path */*path*/);
 323   /* Remove the node identified by the PATH.  The node was allocated by the
 324    * caller, and should be freed by the caller in whatever way is
 325    * appropriate.
 326    *
 327    * Returns `XYLA_RC_OK'.
 328    */
 329
 330 /*----- Splitting and joining ---------------------------------------------*/
 331
 332 extern int xyla_treap_join(struct xyla_bt_nodecls */*cls*/,
 333                            struct xyla_bt_node **/*root_out*/,
 334                            struct xyla_bt_node **/*left*/,
 335                            struct xyla_bt_node */*mid*/,
 336                            struct xyla_bt_node **/*right*/);
 337   /* Concatenate the two trees rooted at LEFT and RIGHT in order; if MID is
 338    * not null, then place this node between them.  The root of the resulting
 339    * tree is stored in *ROOT_OUT.  It's the caller's responsibility to ensure
 340    * that this respects any ordering invariants.
 341    *
 342    * The ROOT_OUT pointer may equal either LEFT or RIGHT (or, indeed, both,
 343    * only if both are empty).  If LEFT is distinct from ROOT_OUT then *LEFT
 344    * is set null on exit; similarly, if RIGHT is distinct from ROOT_OUT, then
 345    * *RIGHT is set null on exit.
 346    *
 347    * Returns `XYLA_RC_OK'.
 348    */
 349
 350 extern int xyla_treap_split(struct xyla_bt_nodecls */*cls*/,
 351                             struct xyla_bt_node **/*left_out*/,
 352                             struct xyla_bt_node **/*mid_out*/,
 353                             struct xyla_bt_node **/*right_out*/,
 354                             struct xyla_treap_path */*path*/);
 355   /* Split a tree tree into two at the indicated place indicated by the PATH.
 356    * Store in *LEFT_OUT and *RIGHT_OUT the roots of trees containing every
 357    * node respectively preceding and following the PATH.
 358    *
 359    * If the PATH is full, i.e., it denotes a node in the input tree, then
 360    * that becomes the `middle node', which does not appear in either output
 361    * tree; a pointer to this node is stored in *MID_OUT.
 362    *
 363    * Returns `XYLA_RC_OK'.
 364    */
 365
 366 extern int xyla_treap_splitat(struct xyla_bt_nodecls */*cls*/,
 367                               struct xyla_bt_node **/*left_out*/,
 368                               struct xyla_bt_node **/*mid_out*/,
 369                               struct xyla_bt_node **/*right_out*/,
 370                               struct xyla_bt_node **/*root*/,
 371                               const void */*key*/);
 372   /* Split the tree rooted at ROOT into two at an indicated KEY.  Store in
 373    * *LEFT_OUT and *RIGHT_OUT the roots of trees containing every node whose
 374    * key is respectively less than and greater than the KEY.
 375    *
 376    * If a node matching the KEY exists in the input tree, then that becomes
 377    * the `middle node', which does not appear in either output tree; a
 378    * pointer to this node is stored in *MID_OUT.
 379    *
 380    * This operation assumes that the tree traversal ordering matches an
 381    * ordering on search keys, which is implemented by the node-class `nav'
 382    * function.
 383    *
 384    * Returns `XYLA_RC_OK'.
 385    */
 386
 387 extern int xyla_treap_splitroot(struct xyla_bt_node **/*left_out*/,
 388                                 struct xyla_bt_node **/*root_out*/,
 389                                 struct xyla_bt_node **/*right_out*/,
 390                                 struct xyla_bt_node **/*root*/);
 391   /* Split the tree rooted at ROOT into two at its root.  Store in *ROOT_OUT
 392    * a pointer to the original root node, or null if the tree was initially
 393    * empty; store in *LEFT_OUT and *RIGHT_OUT the root of the original root's
 394    * left and right subtrees respectively.
 395    *
 396    * Returns `XYLA_RC_OK'.
 397    */
 398
 399 /*----- Set operations ----------------------------------------------------*/
 400
 401 extern int xyla_treap_unisect(struct xyla_bt_nodecls */*cls*/,
 402                               struct xyla_bt_node **/*uni_out*/,
 403                               struct xyla_bt_node **/*isect_out*/,
 404                               struct xyla_bt_node **/*aroot*/,
 405                               struct xyla_bt_node **/*broot*/);
 406   /* Compute the union and intersection of two trees.
 407    *
 408    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
 409    * trees are considered to represent sets, with one element per node; the
 410    * element is determined by the `key' node-class operation.  On exit,
 411    * *UNI_OUT points to the root of a tree containing (one copy of) each
 412    * element present in either a or b, and *ISECT_OUT points to the root of a
 413    * tree containing the other copy of each element present in both a and b.
 414    * If AROOT and/or BROOT are distinct from UNI_OUT and ISECT_OUT, then null
 415    * pointers are stored in them.  The original trees are destroyed; each
 416    * node in the original operands trees ends up in exactly one of the result
 417    * trees.
 418    *
 419    * Returns `XYLA_RC_OK'.
 420    */
 421
 422 extern int xyla_treap_diffsect(struct xyla_bt_nodecls */*cls*/,
 423                                struct xyla_bt_node **/*diff_out*/,
 424                                struct xyla_bt_node **/*isect_out*/,
 425                                struct xyla_bt_node **/*aroot*/,
 426                                struct xyla_bt_node **/*broot*/);
 427   /* Compute the set difference of the two operand trees.
 428    *
 429    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
 430    * trees are considered to represent sets, with one element per node; the
 431    * element is determined by the `key' node-class operation.  On exit,
 432    * *DIFF_OUT points to the root of a tree containing each element of a but
 433    * not b, and *ISECT_OUT points to the root of a tree containing each
 434    * element of a that's also in b.  If AROOT and/or BROOT are distinct from
 435    * DIFF_OUT and ISECT_OUT, then null pointers are stored in them.  The
 436    * original a tree is destroyed; each node in the original operands trees
 437    * ends up in exactly one of the result trees.  The input b tree is
 438    * unchanged.
 439    *
 440    * Returns `XYLA_RC_OK'.
 441    */
 442
 443 /*----- Checking ----------------------------------------------------------*/
 444
 445 #ifndef XYLA_FREESTANDING
 446
 447 extern int xyla_treap_check(struct xyla_bt_nodecls */*cls*/,
 448                             struct xyla_bt_node *const */*root*/,
 449                             FILE */*fp*/, unsigned /*f*/,
 450                             void */*arg*/);
 451   /* Examine a treap, checking that it satisfies all of the necessary
 452    * invariants.
 453    *
 454    * This function uses the `xyla_bt_check' framework; see the description of
 455    * that function for details.  Returns `XYLA_RC_OK' on success,
 456    * `XYLA_RC_BAD' if problems are found, or some other code if verification
 457    * had to finish prematurely.
 458    */
 459
 460 #endif
 461
 462 /*----- That's all, folks -------------------------------------------------*/
 463
 464 #endif