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

   1 /* -*-c-*-
   2  *
   3  * Splitting and joining 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 int xyla_splay_join(struct xyla_bt_nodecls *cls,
  34                     struct xyla_bt_node **root_out,
  35                     struct xyla_bt_node **left,
  36                     struct xyla_bt_node *mid,
  37                     struct xyla_bt_node **right)
  38 {
  39   /* Concatenate the two trees rooted at LEFT and RIGHT in order; if MID is
  40    * not null, then place this node between them.  The root of the resulting
  41    * tree is stored in *ROOT_OUT.  It's the caller's responsibility to ensure
  42    * that this respects any ordering invariants.
  43    *
  44    * The ROOT_OUT pointer may equal either LEFT or RIGHT (or, indeed, both,
  45    * only if both are empty).  If LEFT is distinct from ROOT_OUT then *LEFT
  46    * is set null on exit; similarly, if RIGHT is distinct from ROOT_OUT, then
  47    * *RIGHT is set null on exit.
  48    *
  49    * Returns `XYLA_RC_OK'.
  50    */
  51
  52   struct xyla_splay_node *mnode, *lnode, *rnode;
  53   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  54
  55   /* Collect the three nodes. */
  56   mnode = SPLAY_NODE(mid);
  57   lnode = SPLAY_NODE(*left); *left = 0;
  58   rnode = SPLAY_NODE(*right); *right = 0;
  59
  60   if (!mnode)
  61     /* There's no joining node.  We already have a routine for this case. */
  62
  63     *root_out = xyla__splay_join(cls, lnode, rnode);
  64   else {
  65     /* There's a joining node.  Just, err, make it the root, with the other
  66      * two trees as its children.
  67      */
  68
  69     mnode->bt.left = lnode ? &lnode->bt : 0;
  70       if (lnode) lnode->spl.parent = mnode;
  71     mnode->bt.right = rnode ? &rnode->bt : 0;
  72       if (rnode) rnode->spl.parent = mnode;
  73     mnode->spl.parent = 0;
  74     if (updfn) updfn(cls, &mnode->bt);
  75     *root_out = &mnode->bt;
  76   }
  77
  78   return (XYLA_RC_OK);
  79 }
  80
  81 int xyla_splay_split(struct xyla_bt_nodecls *cls,
  82                      struct xyla_bt_node **left_out,
  83                      struct xyla_bt_node **mid_out,
  84                      struct xyla_bt_node **right_out,
  85                      struct xyla_splay_path *path)
  86 {
  87   /* Split a tree tree into two at the indicated place indicated by the PATH.
  88    * Store in *LEFT_OUT and *RIGHT_OUT the roots of trees containing every
  89    * node respectively preceding and following the PATH.  If either LHT_OUT
  90    * and/or RHT_OUT are not-null, then store zero in these locations.
  91    *
  92    * If the PATH is full, i.e., it denotes a node in the input tree, then
  93    * that becomes the `middle node', which does not appear in either output
  94    * tree; a pointer to this node is stored in *MID_OUT.
  95    *
  96    * Returns `XYLA_RC_OK'.
  97    */
  98
  99   struct xyla_splay_node *node, *parent, *left, *right;
 100   unsigned side;
 101
 102   /* Collect the splitting node, or parent, and detach from the old root. */
 103   node = path->node; *path->root = 0;
 104
 105   if (!node)
 106     /* The tree is already empty.  There's nothing to do in this case. */
 107
 108     *left_out = *right_out = 0;
 109   else {
 110     /* The tree is not empty. */
 111
 112     if (path->f) {
 113       /* The path is empty.  Update it if it's stale, and split the tree by
 114        * pretending that there was a leaf node here.  It will become the new
 115        * root, so its left and right subtrees are the output trees that we
 116        * want.
 117        */
 118
 119       side = xyla__splay_resolve_path(path);
 120       node = 0; *left_out = *right_out = 0;
 121       xyla__splay_split(cls, left_out, right_out, path->node, side);
 122     } else {
 123       /* The path is full.  Splay the tree here, and then detach its left and
 124        * right subtrees.
 125        */
 126
 127       parent = node->spl.parent;
 128       *left_out = node->bt.left; *right_out = node->bt.right;
 129       side = parent && parent->bt.left == &node->bt ?
 130         SPLAY_LEFT : SPLAY_RIGHT;
 131       xyla__splay_split(cls, left_out, right_out, parent, side);
 132       node->spl.parent = 0; node->bt.left = node->bt.right = 0;
 133     }
 134
 135     /* Fix up the output trees' parent links so that they can stand on their
 136      * own.
 137      */
 138     left = SPLAY_NODE(*left_out); if (left) left->spl.parent = 0;
 139     right = SPLAY_NODE(*right_out); if (right) right->spl.parent = 0;
 140   }
 141
 142   /* All done. */
 143   *mid_out = node ? &node->bt : 0; return (XYLA_RC_OK);
 144 }
 145
 146 int xyla_splay_splitat(struct xyla_bt_nodecls *cls,
 147                        struct xyla_bt_node **left_out,
 148                        struct xyla_bt_node **mid_out,
 149                        struct xyla_bt_node **right_out,
 150                        struct xyla_bt_node **root, const void *key)
 151 {
 152   /* Split the tree rooted at ROOT into two at an indicated KEY.  Store in
 153    * *LEFT_OUT and *RIGHT_OUT the roots of trees containing every node whose
 154    * key is respectively less than and greater than the KEY.
 155    *
 156    * If a node matching the KEY exists in the input tree, then that becomes
 157    * the `middle node', which does not appear in either output tree; a
 158    * pointer to this node is stored in *MID_OUT.
 159    *
 160    * This operation assumes that the tree traversal ordering matches an
 161    * ordering on search keys, which is implemented by the node-class `nav'
 162    * function.
 163    *
 164    * Returns `XYLA_RC_OK'.
 165    */
 166
 167   const struct xyla_bt_ordops *ops = ORDER_OPS(cls->ops);
 168   struct xyla_splay_path path;
 169
 170   xyla_splay_probe(cls, root, ops->ord.nav, UNCONST(void, key), &path);
 171   return (xyla_splay_split(cls, left_out, mid_out, right_out, &path));
 172 }
 173
 174 int xyla_splay_splitroot(struct xyla_bt_node **left_out,
 175                          struct xyla_bt_node **root_out,
 176                          struct xyla_bt_node **right_out,
 177                          struct xyla_bt_node **root)
 178 {
 179   /* Split the tree rooted at ROOT into two at its root.  Store in *ROOT_OUT
 180    * a pointer to the original root node, or null if the tree was initially
 181    * empty; store in *LEFT_OUT and *RIGHT_OUT the root of the original root's
 182    * left and right subtrees respectively.
 183    *
 184    * Returns `XYLA_RC_OK'.
 185    */
 186
 187   struct xyla_splay_node *node, *left, *right;
 188
 189   node = SPLAY_NODE(*root); *root = 0;
 190   if (!node)
 191     *left_out = *right_out = 0;
 192   else {
 193     left = SPLAY_NODE(node->bt.left); right = SPLAY_NODE(node->bt.right);
 194     *left_out = left ? &left->bt : 0; if (left) left->spl.parent = 0;
 195     *right_out = right ? &right->bt : 0; if (right) right->spl.parent = 0;
 196     node->bt.left = node->bt.right = 0;
 197   }
 198
 199   *root_out = node ? &node->bt : 0; return (XYLA_RC_OK);
 200 }
 201
 202 /*----- That's all, folks -------------------------------------------------*/