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

   1 /* -*-c-*-
   2  *
   3  * Insertion and removal for 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 /*----- Header files ------------------------------------------------------*/
  27
  28 #include "lib.h"
  29 #include "treap.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 int xyla_treap_insert(struct xyla_bt_nodecls *cls,
  34                       struct xyla_treap_path *path,
  35                       struct xyla_treap_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_treap_node *p, *l, *r;
  48   struct xyla_bt_node **nlink, **plink;
  49   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  50   size_t nwt = node->trp.wt, pwt;
  51   int k = path->k;
  52
  53   /* The new node is notionally attached to its parent, but may be too light
  54    * to stay here.  Allow it to float up to its proper resting place.  We
  55    * don't actually link it into the tree until the end.
  56    */
  57   nlink = path->p[k]; XYLA__ASSERT(!*nlink); l = r = 0;
  58   for (;;) {
  59
  60     /* If we're at the root then stop here. */
  61     if (!k) {
  62       *nlink = &node->bt;
  63       node->bt.left = l ? &l->bt : 0;
  64       node->bt.right = r ? &r->bt : 0;
  65       if (updfn) updfn(cls, &node->bt);
  66       break;
  67     }
  68
  69     /* Fetch the parent node.  If it's not heavier than the new node, then we
  70      * can stop.
  71      */
  72     plink = path->p[--k]; p = TREAP_NODE(*plink); pwt = p->trp.wt;
  73     if (pwt <= nwt) {
  74       *nlink = &node->bt;
  75       node->bt.left = l ? &l->bt : 0;
  76       node->bt.right = r ? &r->bt : 0;
  77       if (updfn) { updfn(cls, &node->bt); updfn(cls, &p->bt); }
  78       break;
  79     }
  80
  81     /* The node is lighter than its parent, and so must float up.  Adjust
  82      * the links.
  83      */
  84     if (nlink == &p->bt.left)
  85 #define FIXUP_INSERT(left, l, right, r) do {                            \
  86       /* The new node is currently the left child.                      \
  87        *                                                                \
  88        *                p                                               \
  89        *                 (*)                         ( )                \
  90        *               /     \                     /     \    p         \
  91        *           ( )                  --->    l          (*)          \
  92        *          /   \                                   /   \         \
  93        *        l       r                               r               \
  94        */                                                               \
  95                                                                         \
  96       V( if (xyla__verbout && (xyla__verbose&XYLA__VF_INSERT))          \
  97            fputs("XYLA-TREAP INSERT " #left " child\n",                 \
  98                  xyla__verbout); )                                      \
  99       p->bt.left = r ? &r->bt : 0; r = p;                               \
 100 } while (0)
 101       FIXUP_INSERT(left, l, right, r);
 102     else
 103       FIXUP_INSERT(right, r, left, l);
 104 #undef FIXUP_INSERT
 105
 106     /* And ascend the tree. */
 107     if (updfn) updfn(cls, &p->bt);
 108     nlink = plink;
 109   }
 110
 111   /* Follow the rest of the path up to the root, updating the nodes. */
 112   if (updfn) while (k) updfn(cls, *path->p[--k]);
 113
 114   /* Done. */
 115   return (XYLA_RC_OK);
 116 }
 117
 118 int xyla_treap_remove(struct xyla_bt_nodecls *cls,
 119                       struct xyla_treap_path *path)
 120 {
 121   /* Remove the node identified by the PATH.  The node was allocated by the
 122    * caller, and should be freed by the caller in whatever way is
 123    * appropriate.
 124    *
 125    * Returns `XYLA_RC_OK'.
 126    */
 127
 128   struct xyla_treap_node *n, *l, *r;
 129   struct xyla_bt_node **nlink;
 130   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 131   size_t lwt, rwt;
 132   int k = path->k;
 133
 134   /* Collect the node and its children. */
 135   nlink = path->p[k];
 136   n = TREAP_NODE(*nlink); XYLA__ASSERT(n);
 137   l = TREAP_NODE(n->bt.left); r = TREAP_NODE(n->bt.right);
 138
 139   if (!l) {
 140     /* The node has a null left link, so the job is easy: replace the node by
 141      * its right child.
 142      */
 143
 144     *nlink = r ? &r->bt : 0;
 145   } else if (!r) {
 146     /* The node has a null right link. */
 147
 148     *nlink = l ? &l->bt : 0;
 149   } else {
 150     /* The node has two active children.  We're going to pretend that our
 151      * node has suddenly become very heavy, so it has to sink to the bottom
 152      * of the tree.
 153      */
 154
 155     /* Start by collecting the child weights. */
 156     lwt = l->trp.wt; rwt = r->trp.wt;
 157
 158     /* Descend the tree until one of the links becomes null. */
 159     for (;;) {
 160       if (k >= XYLA_TREAP_HTMAX) xyla__treap_boundfail();
 161
 162       /* Replace the node with its lighter child. */
 163       if (lwt <= rwt)
 164 #define FIXUP_REMOVE(left, l, lwt, right, r, rwt) do {                  \
 165         /* The left child is lighter.  Rearrange links and descend.     \
 166          *                                                              \
 167          *                                       l                      \
 168          *             n                          (*)                   \
 169          *              ( )                     /     \    n            \
 170          *       l    /     \    r      --->            ( )             \
 171          *        (*)         (*)                      /   \   r        \
 172          *       /   \       /   \                          (*)         \
 173          *                                                 /   \        \
 174          */                                                             \
 175                                                                         \
 176         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_REMOVE))        \
 177              fputs("XYLA-TREAP REMOVE float " #left " child\n",         \
 178                    xyla__verbout); )                                    \
 179         *nlink = &l->bt; nlink = path->p[++k] = &l->bt.right;           \
 180         l = TREAP_NODE(l->bt.right);                                    \
 181                                                                         \
 182         /* If the new left link is null then we're done. */             \
 183         if (!l) { *nlink = &r->bt; goto done; }                         \
 184         lwt = l->trp.wt;                                                \
 185 } while (0)
 186         FIXUP_REMOVE(left, l, lwt, right, r, rwt);
 187       else
 188         FIXUP_REMOVE(right, r, rwt, left, l, lwt);
 189 #undef FIXUP_REMOVE
 190     }
 191   done:;
 192   }
 193
 194   /* Follow the rest of the path up to the root, updating the nodes. */
 195   if (updfn) while (k) updfn(cls, *path->p[--k]);
 196
 197   /* Done. */
 198   return (XYLA_RC_OK);
 199 }
 200
 201 /*----- That's all, folks -------------------------------------------------*/