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

   1 /* -*-c-*-
   2  *
   3  * Internal definitions
   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_LIB_H
  27 #define XYLA_LIB_H
  28
  29 /*----- Coverage instrumentation ------------------------------------------*/
  30
  31 /* Verbosity control. */
  32 #ifdef XYLA_VERBOSE
  33 #  include <stdio.h>
  34   extern unsigned xyla__verbose;
  35   extern FILE *xyla__verbout;
  36 #  define V(x) x
  37 #  define NV(x)
  38 #else
  39 #  define V(x)
  40 #  define NV(x) x
  41 #endif
  42
  43 /* Verbosity flags. */
  44 #define XYLA__VF_ITER 0x0001
  45 #define XYLA__VF_PATH 0x0002
  46 #define XYLA__VF_PROBE 0x0004
  47 #define XYLA__VF_INSERT 0x0008
  48 #define XYLA__VF_REMOVE 0x0010
  49 #define XYLA__VF_SPLIT 0x0020
  50 #define XYLA__VF_JOIN 0x0040
  51 #define XYLA__VF_UNISECT 0x0080
  52 #define XYLA__VF_DIFFSECT 0x0100
  53 #define XYLA__VF_SPLAY 0x1000
  54
  55 /*----- Compiler-specific features ----------------------------------------*/
  56
  57 #ifdef __clang__
  58 #  define CLANG_VERSION_P(maj, min)                                     \
  59         (__clang_major__ > (maj) ||                                     \
  60          (__clang_major__ == (maj) && __clang_minor__ >= (min)))
  61 #  define GCC_VERSION_P(maj, min) 0     /* Clang is /not/ GCC */
  62 #else
  63 #  define CLANG_VERSION_P(maj, min) 0
  64 #  ifdef __GNUC__
  65 #    define GCC_VERSION_P(maj, min)                                     \
  66         (__GNUC__ > (maj) || (__GNUC__ == (maj) && __GNUC_MINOR__ >= (min)))
  67 #  else
  68 #    define GCC_VERSION_P(maj, min) 0
  69 #  endif
  70 #endif
  71
  72 #ifdef _MSC_VER
  73 #  define MSC_VERSION_P(maj, min) (_MSC_VER >= (maj)*100 + (min))
  74 #else
  75 #  define MSC_VERSION_P(maj, min) 0
  76 #endif
  77
  78 #if GCC_VERSION_P(2, 5) || CLANG_VERSION_P(3, 3)
  79 #  define NORETURN __attribute__((__noreturn__))
  80 #endif
  81
  82 #if GCC_VERSION_P(4, 0) || CLANG_VERSION_P(3, 3)
  83 #  define PRINTF_LIKE(fix, aix) __attribute__((__format__(printf, fix, aix)))
  84 #endif
  85
  86 #if MSC_VERSION_P(8, 0)
  87 #  define NORETURN __declspec(noreturn)
  88 #endif
  89
  90 #ifndef NORETURN
  91 #  define NORETURN
  92 #endif
  93
  94 #ifndef PRINTF_LIKE
  95 #  define PRINTF_LIKE(fix, aix)
  96 #endif
  97
  98 /*----- Conversion utilities ----------------------------------------------*/
  99
 100 #define CHECK_TYPE(expty, x) (!sizeof(*(expty *)0 = (x)))
 101
 102 #define CONVERT_CAREFULLY(newty, expty, x)                              \
 103         (CHECK_TYPE(expty, x) ?                                         \
 104           (/*unconst unvolatile*/ newty)(x) :                           \
 105           (/*unconst unvolatile*/ newty)(x))
 106
 107 #define CONTAINER(type, mem, p)                                         \
 108         (!sizeof((p) == &((type *)0)->mem) +                            \
 109          (type *)((unsigned char *)(p) - offsetof(type, mem)))
 110
 111 #define UNCONST(type, p) CONVERT_CAREFULLY(type *, const type *, p)
 112
 113 #define ORDER_OPS(ops) CONTAINER(const struct xyla_bt_ordops, node, ops)
 114 #define CHECK_OPS(ops) CONTAINER(const struct xyla_bt_chkops, node, ops)
 115
 116 /*----- AVL tree utilities ------------------------------------------------*/
 117
 118 /* Conversions. */
 119 #define AVL_NODE(node)                                                  \
 120         CONVERT_CAREFULLY(struct xyla_avl_node *,                       \
 121                           struct xyla_bt_node *,                        \
 122                           node)
 123 #define CONST_AVL_NODE(node)                                            \
 124         CONVERT_CAREFULLY(const struct xyla_avl_node *,                 \
 125                           const struct xyla_bt_node *,                  \
 126                           node)
 127
 128 /* Diagnostic output. */
 129 #define AVL_BALCH(node) ("=-+"[(node)->avl.f&XYLA_AVLF_BALMASK])
 130   /* Return the AVL balance character for NODE. */
 131
 132 /* Combinatorial logic for balance-annotation adjustments. */
 133 #define AVL_REBAL_EEL(bal) ((bal) >> 1)
 134 #define AVL_REBAL_REE(bal) (((bal) << 1)&XYLA_AVLF_BALMASK)
 135 #define AVL_REBAL_XRE(bal) ((bal) ^ XYLA_AVLBAL_RBIAS)
 136 #define AVL_REBAL_XLE(bal) (((bal) ^ XYLA_AVLBAL_RBIAS) >> 1)
 137 #define AVL_REBAL_ELX(bal) ((bal) ^ XYLA_AVLBAL_LBIAS)
 138 #define AVL_REBAL_ERX(bal) (((bal) ^ XYLA_AVLBAL_LBIAS) << 1)
 139
 140 /*----- Red-black tree utilities ------------------------------------------*/
 141
 142 /* Conversions. */
 143 #define RB_NODE(node)                                                   \
 144         CONVERT_CAREFULLY(struct xyla_rb_node *,                        \
 145                           struct xyla_bt_node *,                        \
 146                           node)
 147 #define CONST_RB_NODE(node)                                             \
 148         CONVERT_CAREFULLY(const struct xyla_rb_node *,                  \
 149                           const struct xyla_bt_node *,                  \
 150                           node)
 151
 152 /*----- Splay tree utilities ----------------------------------------------*/
 153
 154 /* Conversions. */
 155 #define SPLAY_NODE(node)                                                \
 156         CONVERT_CAREFULLY(struct xyla_splay_node *,                     \
 157                           struct xyla_bt_node *,                        \
 158                           node)
 159 #define CONST_SPLAY_NODE(node)                                          \
 160         CONVERT_CAREFULLY(const struct xyla_splay_node *,               \
 161                           const struct xyla_bt_node *,                  \
 162                           node)
 163
 164 /* Side constants. */
 165 #define SPLAY_LEFT 0u
 166 #define SPLAY_RIGHT 1u
 167
 168 struct xyla_bt_node;
 169 struct xyla_bt_nodecls;
 170 struct xyla_splay_node;
 171 struct xyla_splay_path;
 172
 173 extern void xyla__splay_split(struct xyla_bt_nodecls */*cls*/,
 174                               struct xyla_bt_node **/*left_inout*/,
 175                               struct xyla_bt_node **/*right_inout*/,
 176                               struct xyla_splay_node */*parent*/,
 177                               unsigned /*side*/);
 178   /* Splay the tree at a possibly fictional node.  The node is promoted to
 179    * the tree root, and the child links are updated.
 180    *
 181    * The PARENT and SIDE arguments identify the node's initial position in
 182    * the tree, and *LEFT_INOUT and *RIGHT_INOUT identify its child links.  It
 183    * is valid if the node is already the tree root: in this case, PARENT is
 184    * null and SIDE is ignored; otherwise SIDE must be one of the constants
 185    * `SPLAY_LEFT' or `SPLAY_RIGHT'.
 186    *
 187    * The `xyla__splay_splay' function below calls this with a real node,
 188    * determining the PARENT and SIDE appropriately; `xyla_splay_insert' uses
 189    * this to prepare the tree before the new node is linked in;
 190    * `xyla_splay_split' uses this to handle both its full and empty path
 191    * cases.
 192    */
 193
 194 extern void xyla__splay_splay(struct xyla_bt_nodecls */*cls*/,
 195                               struct xyla_splay_node */*node*/);
 196   /* Splay the tree at NODE.  The NODE becomes the new tree root; updating
 197    * this is the caller's responsibility.  The NODE is /not/ updated, since
 198    * the caller may want to make further changes before it's ready.
 199    */
 200
 201 extern void *xyla__splay_join(struct xyla_bt_nodecls */*cls*/,
 202                               struct xyla_splay_node */*left*/,
 203                               struct xyla_splay_node */*right*/);
 204   /* Join the two trees LEFT and RIGHT, without an intervening node.  The
 205    * input tree roots' parent links need not be cleared before calling.
 206    */
 207
 208 extern unsigned xyla__splay_resolve_path(struct xyla_splay_path */*path*/);
 209   /* The PATH must be empty -- i.e., refer to a null link rather than a real
 210    * node -- and nontrivial -- so the tree must not be empty.  If the tree
 211    * has been reorganized since the path was constructed, then the `gap'
 212    * referred to by the path may have moved, so that the link referenced
 213    * isn't actually null any more.  Modify the PATH so that it refers to the
 214    * actual null link at the same position in the tree's ordering, and return
 215    * `SPLAY_LEFT' or `SPLAY_RIGHT' suitable for calling `xyla__splay_split'.
 216    */
 217
 218 /*----- Treap utilities ---------------------------------------------------*/
 219
 220 /* Conversions. */
 221 #define TREAP_NODE(node)                                                \
 222         CONVERT_CAREFULLY(struct xyla_treap_node *,                     \
 223                           struct xyla_bt_node *,                        \
 224                           node)
 225 #define CONST_TREAP_NODE(node)                                          \
 226         CONVERT_CAREFULLY(const struct xyla_treap_node *,               \
 227                           const struct xyla_bt_node *,                  \
 228                           node)
 229
 230 extern NORETURN void xyla__treap_boundfail(void);
 231   /* Report a failure in the height bound.
 232    *
 233    * The default implementation calls on `fputs' and `abort'.  If you want to
 234    * embed the library in an environment which doesn't have these, then
 235    * you'll need to replace this function with something else that crashes in
 236    * a distinctive way.
 237    */
 238
 239 /*----- That's all, folks -------------------------------------------------*/
 240
 241 #endif