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

   1 #ifndef XYLA_BSTREE_H
   2 #define XYLA_BSTREE_H
   3
   4 #include <stdio.h>
   5
   6 struct bstnode {
   7   /* The intrusion into a binary search tree node. */
   8
   9   struct bstnode *left, *right;        /* links to left and right subtrees */
  10 };
  11
  12 struct bstree_nodecls {
  13   /* Tree node class. */
  14
  15   const struct bstree_nodeops *ops;     /* pointer to node operations */
  16 };
  17
  18 enum { BSTCHK_LEAF, BSTCHK_BEFORE, BSTCHK_MID, BSTCHK_AFTER };
  19
  20 typedef int bstree_navfn(struct bstree_nodecls */*cls*/,
  21                          const struct bstnode */*node*/,
  22                          void */*arg*/);
  23 typedef void bstree_updfn(struct bstree_nodecls */*cls*/,
  24                           struct bstnode */*node*/);
  25 typedef const void *bstree_keyfn(struct bstree_nodecls */*cls*/,
  26                                  const struct bstnode */*node*/);
  27 typedef int bstree_chkfn(struct bstree_nodecls */*cls*/,
  28                          struct bstnode *const */*root*/,
  29                          const struct bstnode */*parent*/,
  30                          const struct bstnode */*lbound*/,
  31                          const struct bstnode */*rbound*/,
  32                          const struct bstnode */*node*/, unsigned /*ord*/,
  33                          void */*arg*/);
  34 typedef void bstree_idfn(struct bstree_nodecls */*cls*/,
  35                          const struct bstnode */*node*/, FILE */*fp*/);
  36
  37 struct bstree_nodeops {
  38   /* Node operations table. */
  39
  40   bstree_navfn *nav;
  41   bstree_updfn *upd;
  42   bstree_keyfn *key;
  43   bstree_chkfn *chk;
  44   bstree_idfn *id;
  45 };
  46
  47 typedef int bstree_joinfn(struct bstree_nodecls */*cls*/,
  48                           struct bstnode **/*root_out*/,
  49                           struct bstnode **/*left*/, int /*lht*/,
  50                           struct bstnode */*mid*/,
  51                           struct bstnode **/*right*/, int /*rht*/);
  52
  53 typedef void *bstree_splitatfn(struct bstree_nodecls */*cls*/,
  54                                struct bstnode **/*left_out*/,
  55                                  int */*lht_out*/,
  56                                int */*mht_out*/,
  57                                struct bstnode **/*right_out*/,
  58                                  int */*rht_out*/,
  59                                struct bstnode **/*root*/,
  60                                const void */*key*/);
  61
  62 typedef void *bstree_splitrootfn(struct bstnode **/*left_out*/,
  63                                    int */*lht_out*/,
  64                                  int */*mht_out*/,
  65                                  struct bstnode **/*right_out*/,
  66                                    int */*rht*/,
  67                                  struct bstnode **/*root*/, int /*treeht*/);
  68
  69 struct bstree_treeops {
  70   /* Tree operations table. */
  71
  72   bstree_joinfn *join;
  73   bstree_splitatfn *splitat;
  74   bstree_splitrootfn *splitroot;
  75 };
  76
  77 struct bstree_setopstack {
  78   /* Stack entries for set operations. */
  79
  80   unsigned op;
  81   union {
  82     struct {
  83       struct bstnode *a; int aht;
  84       struct bstnode *b; int bht;
  85     } right;
  86     struct {
  87       struct bstnode *uni; int uniht;
  88       struct bstnode *isect; int isectht;
  89     } join_union;
  90     struct {
  91       struct bstnode *diff; int diffht;
  92       struct bstnode *isect; int isectht;
  93     } join_diff;
  94   } u;
  95   struct bstnode *am, *bm;
  96 };
  97
  98 /* --- @bstree_chkorder@ --- *
  99  *
 100  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 101  *              @struct bstnode *const *root@ = pointer to root link
 102  *              @const struct bstnode *parent@ = pointer to parent, or null
 103  *              @const struct bstnode *lbound, *rbound@ = most recent
 104  *                      ancestors on the left and right, or null
 105  *              @const struct bstnode *node@ = node under consideration
 106  *              @unsigned ord@ = ordering pass
 107  *              @void *arg@ = ignored
 108  *
 109  * Returns:     Zero if everything was OK, %$-1$% if problems were found and
 110  *              reported.
 111  *
 112  * Use:         Check that the node satisfies the binary search tree ordering
 113  *              invariants.
 114  */
 115
 116 extern int bstree_chkorder(struct bstree_nodecls */*cls*/,
 117                            struct bstnode *const */*root*/,
 118                            const struct bstnode */*parent*/,
 119                            const struct bstnode */*lbound*/,
 120                            const struct bstnode */*rbound*/,
 121                            const struct bstnode */*node*/, unsigned /*ord*/,
 122                            void */*arg*/);
 123
 124 /* --- @bstree_inititer@ --- *
 125  *
 126  * Arguments:   @struct bstnode *root@ = pointer to the tree header
 127  *              @struct bstnode *stack@ = pointer to stack to initialize
 128  *              @int *sp_out@ = where to leave the initial stack pointer
 129  *
 130  * Returns:     ---
 131  *
 132  * Use:         Initialize an iterator for binary search trees with
 133  *              %%\emph{a priori}%% bounded height.  This function does not
 134  *              need to know the bound: the caller should simply allocate
 135  *              enough entries in the stack vector.
 136  */
 137
 138 extern void bstree_inititer(struct bstnode */*root*/,
 139                             struct bstnode **/*stack*/, int */*sp_out*/);
 140
 141 /* --- @bstree_next@ --- *
 142  *
 143  * Arguments:   @struct bstnode *stack@ = pointer to iterator stack
 144  *              @int *sp_inout@ = stack pointer, updated
 145  *
 146  * Returns:     A pointer to the next node in ascending order, or null
 147  *              if no more nodes remain.
 148  *
 149  * Use:         Advances a tree iterator.  Inserting or removing elements
 150  *              invalidates the iterator.
 151  */
 152
 153 extern void *bstree_next(struct bstnode **/*stack*/, int */*sp_inout*/);
 154
 155 /* --- @bstree_lookup@ --- *
 156  *
 157  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 158  *              @struct bstnode *root@ = pointer to root node
 159  *              @void *arg@ = argument to the navigation function
 160  *
 161  * Returns:     Pointer to the matching node, or null if it couldn't be
 162  *              found.
 163  *
 164  * Use:         Search for a node within the tree according to the navigation
 165  *              function.
 166  */
 167
 168 extern void *bstree_lookup(struct bstree_nodecls */*cls*/,
 169                            struct bstnode */*root*/, void */*arg*/);
 170
 171 /* --- @bstree_probe@ --- *
 172  *
 173  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 174  *              @struct bstnode **root@ = pointer to root link
 175  *              @void *arg@ = argument to the navigation function
 176  *              @struct bstnode ***path@ = path to fill in
 177  *              @int *k_out@ = length of path
 178  *
 179  * Returns:     Pointer to the matching node, or null if it couldn't be
 180  *              found.
 181  *
 182  * Use:         Search for a node within the tree according to the navigation
 183  *              function, recording the search path.
 184  *
 185  *              The tree must have bounded height.  The bound is implicit:
 186  *              the caller is simply expected to have allocated enough space
 187  *              in the path vector.
 188  */
 189
 190 extern void *bstree_probe(struct bstree_nodecls */*cls*/,
 191                           struct bstnode **/*root*/, void */*arg*/,
 192                           struct bstnode ***/*path*/, int */*k_out*/);
 193
 194 /* --- @bstree_firstpath@, @bstree_lastpath@ --- *
 195  *
 196  * Arguments:   @struct bstnode **root@ = address of the tree root link
 197  *              @struct bstnode ***path@ = path to fill in
 198  *              @int *k_out@ = length of path
 199  *
 200  * Returns:     Pointer to the requested node, or null if the tree is empty.
 201  *
 202  * Use:         Return the first or last node in the tree, as ordered by
 203  *              their keys, together with a path to the requested node, which
 204  *              can be used to remove them, or to navigate to other nodes in
 205  *              the tree.
 206  *
 207  *              The tree must have bounded height.  The bound is implicit:
 208  *              the caller is simply expected to have allocated enough space
 209  *              in the path vector.
 210  */
 211
 212 extern struct bstnode *bstree_firstpath(struct bstnode **/*root*/,
 213                                         struct bstnode ***/*path*/,
 214                                         int */*k_out*/);
 215 extern struct bstnode *bstree_lastpath(struct bstnode **/*root*/,
 216                                        struct bstnode ***/*path*/,
 217                                        int */*k_out*/);
 218
 219 /* --- @bstree_nextpath@, @bstree_prevpath@ --- *
 220  *
 221  * Arguments:   @struct bstnode ***path@ = path to update
 222  *              @int *k_inout@ = length of path
 223  *
 224  * Returns:     Pointer to the requested node, or null if the tree is empty
 225  *              or the path is already positioned at the relevant extreme.
 226  *
 227  * Use:         Return the next or previous node in the tree, as ordered by
 228  *              their keys, together with a path to the requested node, which
 229  *              can be used to remove them, or to navigate to other nodes in
 230  *              the tree.
 231  *
 232  *              If the path is full, i.e., refers to an existing node, then
 233  *              the functions return that node's successor or predecessor.
 234  *              If the path is empty, i.e., refers to a space between nodes
 235  *              where a new node can be inserted, then the functions return
 236  *              the node at the upper or lower end of the gap, unless the
 237  *              `gap' is actually at an extreme of the tree and no such node
 238  *              exists.  In the latter case, a null pointer is returned.
 239  *              The path is modified to refer to the new node, if any, or to
 240  *              the gap at the appropriate extreme of the tree.
 241  *
 242  *              The tree must have bounded height.  The bound is implicit:
 243  *              the caller is simply expected to have allocated enough space
 244  *              in the path vector.
 245  */
 246
 247 extern struct bstnode *bstree_nextpath(struct bstnode ***/*path*/,
 248                                        int */*k_inout*/);
 249 extern struct bstnode *bstree_prevpath(struct bstnode ***/*path*/,
 250                                        int */*k_inout*/);
 251
 252 /* --- @bstree_beforepath@, @bstree_afterpath@ --- *
 253  *
 254  * Arguments:   @struct bstnode ***path@ = (full) path to update
 255  *              @int *k_inout@ = length of path, updated
 256  *
 257  * Returns:     ---
 258  *
 259  * Use:         Advance the path to just before or after the current node.
 260  *              The path thereby becomes empty, suitable to insert an element
 261  *              or split the tree just before or after the previously
 262  *              selected node.
 263  */
 264
 265 extern void bstree_beforepath(struct bstnode ***/*path*/, int */*k_inout*/);
 266 extern void bstree_afterpath(struct bstnode ***/*path*/, int */*k_inout*/);
 267
 268 /* --- @bstree_remove@ --- *
 269  *
 270  * Arguments:   @struct bstnode **del_out@ = pointer to deleted node
 271  *              @struct bstnode **subst_out@ = pointer to substituted node
 272  *              @struct bstnode **replace_out@ = pointer to replacement node
 273  *              @struct bstnode ***path@ = (full) path to consult and update
 274  *              @int *k_inout@ = length of path, updated
 275  *
 276  * Returns:     ---
 277  *
 278  * Use:         Remove a node from a binary search tree.
 279  *
 280  *              The path must be full, i.e., it must refer to a node present
 281  *              in the tree.  That node is returned as @*del_out@.
 282  *
 283  *              If the deleted node has two children, then it can't easily be
 284  *              disentangled from the tree.  Instead, the node is swapped
 285  *              with its immediate successor, which must exist because the
 286  *              node has two children and therefore a right child.  On the
 287  *              other hand, the immediate successor is the leftmost node in
 288  *              the deleted node's right subtree, and therefore has no left
 289  *              child.  In this case, @*subst_node@ is set to the successor
 290  *              node, which may require some further fixing up (e.g., to
 291  *              maintain balance state).  The path is extended to refer to
 292  *              the place at which the successor node was linked.  If the
 293  *              deleted node doesn't have both children, none of this is
 294  *              necessary: @*subst_node@ is set to null, and the path is left
 295  *              unchanged.
 296  *
 297  *              The node (after substitution) is replaced with its child, if
 298  *              it has one, or a null pointer.  This replacement node is
 299  *              returned in @*replace_out@.
 300  *
 301  *              The modified nodes are all on the @path@; updating them is
 302  *              left for the caller.
 303  */
 304
 305 extern void bstree_remove(struct bstnode **/*del_out*/,
 306                           struct bstnode **/*subst_out*/,
 307                           struct bstnode **/*replace_out*/,
 308                           struct bstnode ***/*path*/, int */*k_inout*/);
 309
 310 /* --- @bstree_unisect@ --- *
 311  *
 312  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 313  *              @struct bstnode **uni_out@ = where to write the union root
 314  *              @int *uniht_out@ = where to put the union height (or null)
 315  *              @struct bstnode **isect_out@ = where to write the
 316  *                      intersection root
 317  *              @int *isectht_out@ = where to put the intersection height (or
 318  *                      null)
 319  *              @struct bstnode *a@ = pointer to first operand root node
 320  *              @int aht@ = first operand height
 321  *              @struct bstnode *b@ = pointer to second operand root node
 322  *              @int bht@ = second operand height
 323  *              @const struct bstree_treeops *ops@ = pointer to tree
 324  *                      (split/join) operations table
 325  *              @struct bstree_setopstack *stack@ = pointer to sufficiently
 326  *                      large stack vector
 327  *
 328  * Returns:     ---
 329  *
 330  * Use:         Compute the union and intersection of the two operand trees.
 331  *
 332  *              The original trees are destroyed.  Each node in the original
 333  *              operands trees ends up in exactly one of the result trees.
 334  */
 335
 336 extern void bstree_unisect(struct bstree_nodecls */*cls*/,
 337                            struct bstnode **/*uni_out*/,
 338                              int */*uniht_out*/,
 339                            struct bstnode **/*isect_out*/,
 340                              int */*isectht_out*/,
 341                            struct bstnode */*a*/, int /*aht*/,
 342                            struct bstnode */*b*/, int /*bht*/,
 343                            const struct bstree_treeops */*ops*/,
 344                            struct bstree_setopstack */*stack*/);
 345
 346 /* --- @bstree_diffsect@ --- *
 347  *
 348  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 349  *              @struct bstnode **diff_out@ = where to write the difference
 350  *                      root
 351  *              @int *diffht_out@ = where to put the difference height (or
 352  *                      null)
 353  *              @struct bstnode **isect_out@ = where to write the
 354  *                      intersection root
 355  *              @int *isectht_out@ = where to put the intersection height (or
 356  *                      null)
 357  *              @struct bstnode *a@ = pointer to first operand root node
 358  *              @int aht@ = first operand height
 359  *              @struct bstnode *b@ = pointer to second operand root node
 360  *              @const struct bstree_treeops *ops@ = pointer to tree
 361  *                      (split/join) operations table
 362  *              @struct bstree_setopstack *stack@ = pointer to sufficiently
 363  *                      large stack vector
 364  *
 365  * Returns:     ---
 366  *
 367  * Use:         Compute the difference -- i.e., those nodes in %$a$% without
 368  *              matching nodes in %$b$% -- and intersection of the two
 369  *              operand trees.
 370  *
 371  *              The original tree %$a$% is destroyed.  Each node in the
 372  *              original operands tree ends up in exactly one of the result
 373  *              trees.  The input tree %$b$% is unchanged.
 374  */
 375
 376 extern void bstree_diffsect(struct bstree_nodecls */*cls*/,
 377                             struct bstnode **/*diff_out*/,
 378                               int */*diffht_out*/,
 379                             struct bstnode **/*isect_out*/,
 380                               int */*isectht_out*/,
 381                             struct bstnode */*a*/, int /*aht*/,
 382                             struct bstnode */*b*/,
 383                             const struct bstree_treeops */*ops*/,
 384                             struct bstree_setopstack */*stack*/);
 385
 386 #endif