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

   1 /* -*-c-*-
   2  *
   3  * Insertion and removal for 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_insert(struct xyla_bt_nodecls *cls,
  34                       struct xyla_splay_path *path,
  35                       struct xyla_splay_node *node)
  36 {
  37   /* Add a new node to the tree, in the place determined by the empty PATH.
  38    * It's the caller's responsibility to ensure that inserting the node here
  39    * respects any ordering invariants.
  40    *
  41    * The new node is not copied, and its storage must remain valid until the
  42    * node is removed or the tree is discarded.
  43    *
  44    * Returns `XYLA_RC_OK'.
  45    */
  46
  47   struct xyla_splay_node *left, *right;
  48   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  49   unsigned side;
  50
  51   /* Set up the node's links. */
  52   node->bt.left = node->bt.right = 0; node->spl.parent = 0;
  53
  54   /* If the tree isn't empty then hook the node onto the appropriate null
  55    * link and splay.
  56    */
  57   if (path->node) {
  58
  59     /* Find the actual null link, if the path is out of date. */
  60     XYLA__ASSERT(path->f); side = xyla__splay_resolve_path(path);
  61
  62     /* Splay the tree. */
  63     xyla__splay_split(cls, &node->bt.left, &node->bt.right,
  64                       path->node, side);
  65
  66     /* Attach the left and right subtrees. */
  67     left = SPLAY_NODE(node->bt.left); if (left) left->spl.parent = node;
  68     right = SPLAY_NODE(node->bt.right); if (right) right->spl.parent = node;
  69   }
  70
  71   /* Update the new root node. */
  72   if (updfn) updfn(cls, &node->bt);
  73
  74   /* Set it as the root and return. */
  75   *path->root = &node->bt;
  76   return (XYLA_RC_OK);
  77 }
  78
  79 int xyla_splay_remove(struct xyla_bt_nodecls *cls,
  80                       struct xyla_splay_path *path)
  81 {
  82   /* Remove the node identified by the PATH.  The node was allocated by the
  83    * caller, and should be freed by the caller in whatever way is
  84    * appropriate.
  85    *
  86    * Returns `XYLA_RC_OK'.
  87    */
  88
  89   struct xyla_splay_node *node, *parent;
  90   struct xyla_bt_node **link;
  91   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  92
  93   /* Find the node. */
  94   node = path->node; XYLA__ASSERT(node); XYLA__ASSERT(!path->f);
  95
  96   /* Replace the node by the result of joining its children. */
  97   parent = node->spl.parent;
  98   if (!parent) link = path->root;
  99   else if (parent->bt.left == &node->bt) link = &parent->bt.left;
 100   else link = &parent->bt.right;
 101   node = xyla__splay_join(cls,
 102                           SPLAY_NODE(node->bt.left),
 103                           SPLAY_NODE(node->bt.right));
 104   *link = node ? &node->bt : 0; if (node) node->spl.parent = parent;
 105
 106   /* Finally, xyla_splay at the parent node, if there is one. */
 107   if (parent) {
 108     xyla__splay_splay(cls, parent); *path->root = &parent->bt;
 109     if (updfn) updfn(cls, &parent->bt);
 110   }
 111
 112   /* Done. */
 113   return (XYLA_RC_OK);
 114 }
 115
 116 /*----- That's all, folks -------------------------------------------------*/