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

   1 /* -*-c-*-
   2  *
   3  * Set operations 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 /*----- Tree operations ---------------------------------------------------*/
  32
  33 static int join_set(struct xyla_bt_nodecls *cls,
  34                     struct xyla_bt_node **root_out, int *rootht_out,
  35                     struct xyla_bt_node **left, int lht,
  36                     struct xyla_bt_node *mid,
  37                     struct xyla_bt_node **right, int rht)
  38 {
  39   int rc;
  40
  41   rc = xyla_splay_join(cls, root_out, left, mid, right);
  42   *rootht_out = 0; return (rc);
  43 }
  44
  45 static int split_set_at(struct xyla_bt_nodecls *cls,
  46                         struct xyla_bt_node **left_out, int *lht_out,
  47                         struct xyla_bt_node **mid_out,
  48                         struct xyla_bt_node **right_out, int *rht_out,
  49                         struct xyla_bt_node **root, const void *key)
  50 {
  51   int rc;
  52
  53   rc = xyla_splay_splitat(cls, left_out, mid_out, right_out, root, key);
  54   *lht_out = *rht_out = 0; return (rc);
  55 }
  56
  57 static int split_set_root(struct xyla_bt_node **left_out, int *lht_out,
  58                           struct xyla_bt_node **root_out,
  59                           struct xyla_bt_node **right_out, int *rht_out,
  60                           struct xyla_bt_node **root, int ht)
  61 {
  62   int rc;
  63
  64   rc = xyla_splay_splitroot(left_out, root_out, right_out, root);
  65   *lht_out = *rht_out = 0; return (rc);
  66 }
  67
  68 static const struct xyla_bt_treeops splay_ops =
  69   { join_set, split_set_at, split_set_root };
  70
  71 /*----- Main code ---------------------------------------------------------*/
  72
  73 int xyla_splay_unisect(struct xyla_bt_nodecls *cls,
  74                        struct xyla_bt_node **uni_out,
  75                        struct xyla_bt_node **isect_out,
  76                        struct xyla_bt_node **aroot,
  77                        struct xyla_bt_node **broot)
  78 {
  79   /* Compute the union and intersection of two trees.
  80    *
  81    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
  82    * trees are considered to represent sets, with one element per node; the
  83    * element is determined by the `key' node-class operation.  On exit,
  84    * *UNI_OUT points to the root of a tree containing (one copy of) each
  85    * element present in either a or b, and *ISECT_OUT points to the root of a
  86    * tree containing the other copy of each element present in both a and b.
  87    * If AROOT and/or BROOT are distinct from UNI_OUT and ISECT_OUT, then null
  88    * pointers are stored in them.  The original trees are destroyed; each
  89    * node in the original operands trees ends up in exactly one of the result
  90    * trees.
  91    *
  92    * Returns `XYLA_RC_OK'.
  93    */
  94
  95   struct xyla_bt_setopstack stack[XYLA_SPLAY_HTMAX];
  96   int pass, rc;
  97
  98   for (pass = 0; pass < 2; pass++) {
  99     rc = xyla_bt_unisect(cls, uni_out, 0, isect_out, 0,
 100                          aroot, 0, broot, 0,
 101                          &splay_ops, stack, XYLA_SPLAY_HTMAX);
 102       if (!rc) break;
 103       XYLA__ASSERT(rc == XYLA_RC_TALL);
 104     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_UNISECT))
 105          fputs("XYLA-SPLAY UNISECT rebalance\n", xyla__verbout); )
 106     XYLA__ASSERT(!pass); xyla_splay_rebalance(cls, aroot);
 107   }
 108   return (XYLA_RC_OK);
 109 }
 110
 111 int xyla_splay_diffsect(struct xyla_bt_nodecls *cls,
 112                         struct xyla_bt_node **diff_out,
 113                         struct xyla_bt_node **isect_out,
 114                         struct xyla_bt_node **aroot,
 115                         struct xyla_bt_node **broot)
 116 {
 117   /* Compute the set difference of the two operand trees.
 118    *
 119    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
 120    * trees are considered to represent sets, with one element per node; the
 121    * element is determined by the `key' node-class operation.  On exit,
 122    * *DIFF_OUT points to the root of a tree containing each element of a but
 123    * not b, and *ISECT_OUT points to the root of a tree containing each
 124    * element of a that's also in b.  If AROOT and/or BROOT are distinct from
 125    * DIFF_OUT and ISECT_OUT, then null pointers are stored in them.  The
 126    * original a tree is destroyed; each node in the original operands trees
 127    * ends up in exactly one of the result trees.  The input b tree is
 128    * unchanged.
 129    *
 130    * Returns `XYLA_RC_OK'.
 131    */
 132
 133   struct xyla_bt_setopstack stack[XYLA_SPLAY_HTMAX];
 134   int pass, upass, rc;
 135
 136   for (pass = 0; pass < 2; pass++) {
 137     rc = xyla_bt_diffsect(cls, diff_out, 0, isect_out, 0,
 138                           aroot, 0, broot,
 139                           &splay_ops, stack, XYLA_SPLAY_HTMAX);
 140       if (!rc) break;
 141       XYLA__ASSERT(rc == XYLA_RC_TALL);
 142     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_DIFFSECT))
 143          fputs("XYLA-SPLAY DIFFSECT rebalance\n", xyla__verbout); )
 144     XYLA__ASSERT(!pass); xyla_splay_rebalance(cls, broot);
 145     for (upass = 0; upass < 2; upass++) {
 146       rc = xyla_bt_unisect(cls, aroot, 0, isect_out, 0,
 147                            isect_out, 0, aroot, 0,
 148                            &splay_ops, stack, XYLA_SPLAY_HTMAX);
 149         if (!rc) break;
 150         XYLA__ASSERT(rc == XYLA_RC_TALL);
 151       XYLA__ASSERT(!upass); xyla_splay_rebalance(cls, isect_out);
 152     }
 153     XYLA__ASSERT(!*isect_out);
 154   }
 155   return (XYLA_RC_OK);
 156 }
 157
 158 /*----- That's all, folks -------------------------------------------------*/