CMakeLists.txt, lib.h, t/soak, t/treetest.c: Add some support for Windows.

[xyla] / bt.h

/* -*-c-*-
 *
 * Basic binary tree operations
 *
 * (c) 2024 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Xyla, a library of binary trees.
 *
 * Xyla is free software: you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 3 of the License, or (at your
 * option) any later version.
 *
 * Xyla is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
 */

#ifndef XYLA_BT_H
#define XYLA_BT_H

/*----- Header files ------------------------------------------------------*/

#include <limits.h>
#include <stddef.h>

#ifndef XYLA_FREESTANDING
#  include <stdio.h>
#  include <string.h>
#  ifndef XYLA__ASSERT
#    include <assert.h>
#    define XYLA__ASSERT assert
#  endif
#else
#  ifndef XYLA__ASSERT
#    define XYLA__ASSERT(x) do (void)(x); while (0)
#  endif
#endif

/*----- Data structures ---------------------------------------------------*/

#define XYLA_RC_DOLOSE(_)                                               \
  /* add new error codes at the top here */                             \
  _(NOMEM,      "out of memory")                                        \
  _(BAD,        "tree structure invalid")                               \
  _(TALL,       "height limit exceeded")                                \
  _(FAIL,       "operation failed")
#define XYLA_RC_DOWIN(_)                                                \
  _(OK,         "ok")                                                   \
  _(HTCHG,      "height changed")                                       \
  /* add new success codes at the bottom here */

enum {
#define XYLA__RC_DEFLOSE(tag, msg) XYLA__RCLOSE_##tag,
  XYLA_RC_DOLOSE(XYLA__RC_DEFLOSE)
#undef XYLA__RC_DEFLOSE
  XYLA__RCLOSE_LIMIT
};

enum {
#define XYLA__RC_DEFWIN(tag, msg) XYLA_RC_##tag,
  XYLA_RC_DOWIN(XYLA__RC_DEFWIN)
#undef XYLA__RC_DEFWIN
  XYLA_RC_WINLIMIT,

#define XYLA__RC_DEFLOSE(tag, msg) XYLA_RC_##tag =                      \
        -XYLA__RCLOSE_LIMIT + XYLA__RCLOSE_##tag,
  XYLA_RC_DOLOSE(XYLA__RC_DEFLOSE)
#undef XYLA__RC_DEFLOSE
  XYLA_RC_LOSELIMIT = -XYLA__RCLOSE_LIMIT,
};

struct xyla_bt_node {
  /* The intrusion into a binary tree node. */

  struct xyla_bt_node *left, *right;   /* links to left and right subtrees */
};
#define XYLA_BT_NODEPFX struct xyla_bt_node bt
#define XYLA_BT_NODEUSFX struct xyla_bt_node bt

struct xyla_bt_nodecls {
  /* Tree node class. */

  const struct xyla_bt_nodeops *ops;    /* pointer to node operations */
};

enum {
  /* Node position code. */

  XYLA_BTPOS_ROOT,                      /* node is the root */
  XYLA_BTPOS_LEFT,                      /* node is a left child */
  XYLA_BTPOS_RIGHT                      /* node is a right child */
};

typedef void xyla_bt_updfn(struct xyla_bt_nodecls */*cls*/,
                           struct xyla_bt_node */*node*/);
  /* Node update function.  Called when a node's child pointers are modified,
   * to recompute summary data.
   */

typedef void xyla__dummyfn(void);
  /* A dummy function, currently unused.  Must be null for forwards
   * compatibility.
   */

struct xyla_bt_nodeops {
  /* Node operations table. */

  size_t sz;
  xyla_bt_updfn *upd;
  xyla__dummyfn *_rsvd2, *_rsvd3;
};
#define XYLA_BT_NODEOPSPFX struct xyla_bt_nodeops node
#define XYLA_BT_NODEOPSUSFX struct xyla_bt_nodeops node

typedef int xyla_bt_navfn(struct xyla_bt_nodecls */*cls*/,
                          const struct xyla_bt_node */*node*/,
                          void */*arg*/);
  /* Navigation function, called from `lookup', `probe' and related
   * functions.  Passed a NODE pointer and an opaque pointer ARG from the
   * caller.  Return zero if the NODE is the one sought; negative to
   * continue the search into NODE's left subtree; or positive to continue
   * the search into NODE's right subtree.
   */

typedef const void *xyla_bt_keyfn(struct xyla_bt_nodecls */*cls*/,
                                  const struct xyla_bt_node */*node*/);
  /* Key projection function, called from set operations.  Return a pointer
   * to the NODE's key data, suitable for passing to the corresponding
   * navigation function.
   */

struct xyla_bt_ordopslots {
  /* Ordering operations table. */

  xyla_bt_navfn *nav;
  xyla_bt_keyfn *key;
};
#define XYLA_BT_ORDOPSPFX XYLA_BT_NODEOPSPFX; struct xyla_bt_ordopslots ord
struct xyla_bt_ordops { XYLA_BT_ORDOPSPFX; };
#define XYLA_BT_ORDOPSUSFX struct xyla_bt_ordops ord; XYLA_BT_NODEOPSUSFX
union xyla_bt_ordopsu { XYLA_BT_ORDOPSUSFX; };

typedef int xyla_bt_ascendfn(struct xyla_bt_node */*node*/,
                             struct xyla_bt_node */*parent*/,
                             struct xyla_bt_node */*sibling*/,
                             unsigned /*pos*/, void */*arg*/);
  /* Ascension function; see `XYLA_BT_ASCEND'.  Called on a NODE, together
   * with its PARENT, SIBLING, and POS (`XYLA_POS_...') indicating the
   * node's position relative to its parent; ARG is an opaque pointer
   * provided by the caller, usually a pointer to some structure which is
   * updated by the ascension function.
   */

/*----- Diagnostics -------------------------------------------------------*/

extern const char *xyla_strerror(int /*rc*/);
  /* Return the message string associated with the return code RC. */

/*----- Iteration ---------------------------------------------------------*/

/* Background on iteration.
 *
 * Consider an arbitrary node N in a binary tree.  The next nodes to visit
 * are those in N's right subtree.  Then, if N is a left child, we must visit
 * N's parent, followed by the subtree headed by N's sibling.
 *
 * The invariant that we maintain is as follows.
 *
 *   * If the stack is empty, then all nodes have been visited.
 *
 *   * If the stack is nonempty, then the topmost entry in the stack is the
 *     least node which has not yet been visited -- and therefore is the next
 *     node to visit.
 *
 *     The lower entries in the stack are, in top-to-bottom order, those of
 *     the topmost stack node's ancestors, from parent to root, which have
 *     not yet been visited.  In other words, a node appears in the stack if
 *     and only if some node in its left subtree is nearer to the top of the
 *     stack.
 *
 * The stack is initialized by pushing the root, the root's left child, its
 * leftmost grandchild, and so on.  This establishes the invariants above:
 * the leftmost leaf is the first node to be visited, and its entire ancestry
 * is on the stack since none of these nodes has yet been visited.  If the
 * tree is empty, the root is null, so we have done nothing and left the
 * stack empty.
 *
 * When we come to actually visit a node, we pop the topmost node from the
 * stack.  We don't return it yet: we must restore the invariant.
 *
 *   * If the node to visit has a right subtree, then the next node to visit
 *     is the leftmost node in that subtree.  All of the nodes on the stack
 *     are unvisited ancestors of the current node, and therefore of every
 *     node in its right subtree.  We're just about to visit the current
 *     node, so that should indeed indeed have been removed.  The right
 *     subtree contains descendants of the current node, so they are not yet
 *     on the stack, but they have not yet been visited.  We therefore push
 *     the current node's right child, its left child, leftmost grandchild,
 *     and so on.
 *
 *   * Otherwise, we have just finished traversing a subtree.  Either we are
 *     now done, or we have just finished traversing the left subtree of the
 *     enxt topmost node on the stack.  This must therefore be the next node
 *     to visit, and the remainder of the stack is already correct.
 */

#define XYLA_BT_STEPITER(rc, node, stack, sp, max, back) do {           \
  /* Advance the tree iterator represented by STACK and SP; the stack   \
   * contains space for at least MAX elements.  A new left-to-right     \
   * iterator can be initialized by passing NODE as the tree root,      \
   * SP = 0, and BACK = `left'.  Once the iterator is set up:           \
   *                                                                    \
   *   * if SP is zero, there are no more nodes;                        \
   *                                                                    \
   *   * otherwise, the next NODE in order is STACK[--SP]; call again,  \
   *     passing NODE->right to update the stack.                       \
   *                                                                    \
   * Similarly, to iterate right-to-left, pass BACK = `right' and pass  \
   * NODE->left to update.                                              \
   *                                                                    \
   * If RC is `XYLA_RC_TALL' on exit, then the stack was too small for  \
   * the tree height: to make progress, either the stack must be        \
   * extended or the tree must be rebalanced to limit its height.  On   \
   * failure, stack entries beyond the initial stack pointer may be     \
   * clobbered, but entries below the stack pointer, and the stack      \
   * pointer itself, are preserved.  If you extend the stack vector,    \
   * you can either just retry, or, more efficiently, advance the stack \
   * pointer to MAX and call with NODE = STACK[MAX - 1]->left.          \
   */                                                                   \
                                                                        \
  const struct xyla_bt_node *_node = (node), **_stack = (stack);        \
  int _sp = (sp), _max = (max);                                         \
                                                                        \
  for (;;)                                                              \
    if (!_node) { (sp) = _sp; (rc) = XYLA_RC_OK; break; }               \
    else if (_sp >= _max) { (rc) = XYLA_RC_TALL; break; }               \
    else { _stack[_sp++] = _node; _node = _node->back; }                \
} while (0)

extern void *xyla_bt_severfirst(struct xyla_bt_node **/*root*/);
  /* Remove and return the first node in the traversal order of the tree
   * rooted at *ROOT.  The tree is restructured in a simple way which likely
   * invalidates any invariants maintained by the application or balance
   * policy, so this is mostly useful if the entire tree is about to be
   * destroyed.
   */

/*----- Paths -------------------------------------------------------------*/

/* Background on paths.
 *
 * The structure describes a path from the root to a node, or to a null link
 * denoting a place to insert a node, by indicating the links that are
 * followed.  A path which ends with a link to a node is a `full' path, while
 * one that ends with a null link is an `empty' path.
 *
 * The first link followed is always the root link in the tree header, so
 * PATH[0] is always the address of the tree root link.  After that, each
 * step involves following a left or right pointer from a node to one of its
 * children, so, for 0 <= i < k, we have
 *
 *   PATH[i + 1] == &(*PATH[i])->left || PATH[i + 1] == &(*PATH[i])->right .
 *
 * For reasons of internal convenience, K is not the length of the path, but
 * one less than this, so *PATH[K] is the node or null link which terminates
 * the path.
 */

#define XYLA_BT_CURRENT(path, k) (*(path)[(k)])
  /* Return the node currently designated by the PATH, or null if the path is
   * empty.
   */

#ifdef XYLA_FREESTANDING
#  define XYLA_BT_COPYPATH(newpath, path, k) do {                       \
     struct xyla_bt_node                                                \
       ***_newpath = (newpath),                                         \
       **const *_path = (path);                                         \
     int _i, _n = (k) + 1;                                              \
                                                                        \
     for (_i = 0; _i < _n; _i++) _newpath[_i] = _path[_i];              \
   } while (0)
#else
#  define XYLA_BT_COPYPATH(newpath, path, k) do {                       \
     memcpy((newpath), (path),                                          \
            ((k) + 1)*sizeof(struct xyla_bt_node **));                  \
   } while (0)
#endif
  /* Copy the (K + 1) path entries from PATH to NEWPATH. */

#define XYLA_BT_EXTRMPATH(rc, node, root, path, k, dir, htmax) do {     \
  /* Set NODE to be the first (if DIR is `left') or last (if DIR is     \
   * `right') node in the tree whose root link is at ROOT, with a path  \
   * to the requested node, which can be used to remove it, or to       \
   * navigate to other nodes in the tree, stored in PATH, with its      \
   * length left in K.  If the tree is empty, set NODE to be null.      \
   *                                                                    \
   * If the path length to the chosen node exceeds HTMAX then set       \
   * RC = `XYLA_RC_TALL'; otherwise, RC = `XYLA_RC_OK' on exit.         \
   */                                                                   \
                                                                        \
  struct xyla_bt_node *_node, *_next,                                   \
    **_root = (root), ***_path = (path);                                \
  int _k, _htmax = (htmax);                                             \
                                                                        \
  /* A path always begins with the root link. */                        \
  _k = 0; _path[0] = _root; _node = *_root;                             \
                                                                        \
  if (!_node) {                                                         \
    /* The tree is empty.  The path is empty and covers only the root   \
     * link.                                                            \
     */                                                                 \
                                                                        \
    (node) = 0; (k) = _k; (rc) = XYLA_RC_OK;                            \
  } else {                                                              \
    /* There is at least one node.  We trace out a full path to one end \
     * of the tree.  There's a slight inconsistency here because the    \
     * root link will be present regardless of whether the path is full \
     * or empty.                                                        \
     */                                                                 \
                                                                        \
    for (;;) {                                                          \
      _next = _node->dir;                                               \
      if (!_next)                                                       \
        { (node) = _node; (k) = _k; (rc) = XYLA_RC_OK; break; }         \
      else if (_k >= _htmax)                                            \
        { (rc) = XYLA_RC_TALL; (node) = 0; break; }                     \
      else                                                              \
        { _path[++_k] = &_node->dir; _node = _next; }                   \
    }                                                                   \
  }                                                                     \
} while (0)

#define XYLA_BT_STEPPATH(rc, node, path, k, dir, opp, htmax) do {       \
  /* Set NODE to be the next (if DIR is `right' and OPP is `left') or   \
   * previous (if DIR is `left' and OPP is `right') node in the tree,   \
   * relative to the current PATH position, updating the path to the    \
   * requested node.  The path may be either full, in which case the    \
   * macro finds the current node's successor or predecessor, or empty, \
   * in which case it finds the nearest node before or after the gap to \
   * which the path refers.  If the path already refers to the last or  \
   * first node, or to the gap beyond, then set `node' to a null        \
   * pointer and adjust PATH to refer to the appropriate extreme null   \
   * link.                                                              \
   *                                                                    \
   * If the path length to the chosen node exceeds HTMAX then set       \
   * RC = `XYLA_RC_TALL' without altering the path; otherwise, set      \
   * RC = `XYLA_RC_OK' on exit.                                         \
   */                                                                   \
                                                                        \
  struct xyla_bt_node *_node0, *_node, *_next,                          \
    **_link, **_plink, ***_path = (path);                               \
  int _k0 = (k), _k = _k0, _htmax = (htmax);                            \
                                                                        \
  /* Collect the start node and the link address. */                    \
  _link = _path[_k]; _node0 = *_link;                                   \
                                                                        \
  /* If there's a node, then we should explore the subtree on the       \
   * relevant side if there is one.                                     \
   */                                                                   \
  if (_node0) {                                                         \
    _next = _node0->dir;                                                \
    if (_next) {                                                        \
      /* There is indeed a subtree on the relevant side.  We need to    \
       * chase links in the opposite direction to find the next node.   \
       */                                                               \
                                                                        \
      if (_k >= _htmax)                                                 \
        { (rc) = XYLA_RC_TALL; (node) = 0; }                            \
      else {                                                            \
        _path[++_k] = &_node0->dir; _node = _next;                      \
        for (;;) {                                                      \
          _next = _node->opp;                                           \
          if (!_next)                                                   \
            { (node) = _node; (k) = _k; (rc) = 0; break; }              \
          else if (_k >= _htmax)                                        \
            { (rc) = XYLA_RC_TALL; (node) = 0; break; }                 \
          else                                                          \
            { _path[++_k] = &_node->opp; _node = _next; }               \
        }                                                               \
      }                                                                 \
      break;                                                            \
    }                                                                   \
  }                                                                     \
                                                                        \
  /* There either isn't a node at all, or its subtree on the relevant   \
   * side is empty.  Ascend the tree, searching for the most recent     \
   * ancestor in the required direction.                                \
   */                                                                   \
  for (;;) {                                                            \
                                                                        \
    /* If there's no more tree to ascend then set the path to refer to  \
     * a terminating null link beyond the initial node.  We know that   \
     * either the initial path was empty, in which case it's already    \
     * good, or its subtree was empty, in which case we select that.    \
     * Note that we don't modify the path before this point so it's     \
     * safe to revert the path length here.                             \
     */                                                                 \
    if (!_k) {                                                          \
      _k = _k0;                                                         \
      if (!_node0)                                                      \
        { (node) = 0; /* `k' already correct */ (rc) = XYLA_RC_OK; }    \
      else if (_k >= _htmax)                                            \
        { (rc) = XYLA_RC_TALL; (node) = 0; }                            \
      else {                                                            \
        _path[++_k] = &_node0->dir;                                     \
        (node) = 0; (k) = _k; (rc) = XYLA_RC_OK;                        \
      }                                                                 \
      break;                                                            \
    }                                                                   \
                                                                        \
    /* Ascend the tree and check the link direction. */                 \
    _plink = _path[--_k]; _node = *_plink;                              \
    if (_link == &_node->opp)                                           \
      { (node) = _node; (k) = _k; (rc) = XYLA_RC_OK; break; }           \
    _link = _plink;                                                     \
  }                                                                     \
} while (0)

#define XYLA_BT_NUDGEPATH(rc, path, k, dir, opp, htmax) do {            \
  /* The PATH must be full, i.e., refer to a node in the tree.  Adjust  \
   * the path so as to refer instead to the gap immediately before (if  \
   * DIR is `left' and OPP is `right') or after (if DIR is `right' and  \
   * OPP is `left') the selected node, suitable to insert an element or \
   * split the tree just before or after the previously selected node.  \
   * A call to `XYLA_BT_STEPPATH' in the opposite direction will find   \
   * the original node again; stepping in the same direction will find  \
   * the node's predecessor or successor if there is one.               \
   *                                                                    \
   * If the path length to the null link exceeds HTMAX then set         \
   * RC = `XYLA_RC_TALL' without altering the path; otherwise, set      \
   * RC = `XYLA_RC_OK' on exit.                                         \
   */                                                                   \
                                                                        \
  struct xyla_bt_node *_node, ***_path = (path);                        \
  int _k = (k), _htmax = (htmax);                                       \
                                                                        \
  /* Collect the starting point, and check that the path is full. */    \
  _node = *_path[_k]; XYLA__ASSERT(_node);                              \
                                                                        \
  /* Descend into the appropriate side subtree to find a null link. */  \
  if (_k >= _htmax)                                                     \
    (rc) = XYLA_RC_TALL;                                                \
  else {                                                                \
    _path[++_k] = &_node->dir; _node = _node->dir;                      \
    for (;;)                                                            \
      if (!_node) { (k) = _k; (rc) = XYLA_RC_OK; break; }               \
      else if (_k >= _htmax) { (rc) = XYLA_RC_TALL; break; }            \
      else { _path[++_k] = &_node->opp; _node = _node->opp; }           \
  }                                                                     \
} while (0)

#define XYLA_BT_ROOTPATH(node, root, path, k) do {                      \
  /* Initialize PATH and K to refer to the tree root, given the address \
   * ROOT of the root link, and set NODE to be the root node.  The      \
   * resulting path will be empty if and only if the tree is empty.     \
   */                                                                   \
                                                                        \
  (k) = 0;                                                              \
  (node) = *((path)[0] = (root));                                       \
} while (0)

#define XYLA_BT_PARENTPATH(node, pos, path, k) do {                     \
  /* Update the PATH and K to refer to the parent of the link currently \
   * designated; set NODE to be this parent, and POS to the             \
   * `XYLA_BTPOS_...'  constant describing the link's relation to the   \
   * parent.  If the path initially designated the tree's root link,    \
   * then set NODE to null and POS to `XYLA_BTPOS_ROOT', and leave the  \
   * path unchanged; otherwise, the tree becomes full, and decrement K  \
   * by one.                                                            \
   */                                                                   \
                                                                        \
  struct xyla_bt_node **_link, *_node, ***_path = (path);               \
  int _k = (k);                                                         \
                                                                        \
  if (!_k)                                                              \
    { (node) = 0; (pos) = XYLA_BTPOS_ROOT; }                            \
  else {                                                                \
    _link = _path[_k]; (node) = _node = *_path[--_k]; (k) = _k;         \
    (pos) = _link == &_node->left ?                                     \
              XYLA_BTPOS_LEFT : XYLA_BTPOS_RIGHT;                       \
  }                                                                     \
} while (0)

#define XYLA_BT_CHILDPATH(rc, node, path, k, dir, htmax) do {           \
  /* Update the PATH and K to refer to the left (if DIR is `left') or   \
   * right (if DIR is `right') child of the node currently designated,  \
   * and set NODE to be this child node.  The path must initially have  \
   * been full, and may become empty as a result.                       \
   *                                                                    \
   * If the path length to the chosen node exceeds HTMAX then set       \
   * RC = `XYLA_RC_TALL' without altering the path; otherwise, set      \
   * RC = `XYLA_RC_OK' on exit.                                         \
   */                                                                   \
                                                                        \
  struct xyla_bt_node *_node, ***_path = (path);                        \
  int _k = (k), _htmax = (htmax);                                       \
                                                                        \
  _node = *_path[_k]; XYLA__ASSERT(_node);                              \
  if (_k >= _htmax)                                                     \
    { (rc) = XYLA_RC_TALL; (node) = 0; }                                \
  else {                                                                \
    _path[++_k] = &_node->dir; (k) = _k;                                \
    (node) = _node->dir; (rc) = XYLA_RC_OK;                             \
  }                                                                     \
} while (0)

#define XYLA_BT_RIPPLE(cls, path, k) do {                               \
  /* Update a node's ancestors -- i.e., call the node class `upd'       \
   * function on them, in ascending order -- after it has been          \
   * modified.  The PATH and K describe a full path to the node that    \
   * has been changed.  The PATH remains valid.                         \
   */                                                                   \
                                                                        \
  struct xyla_bt_nodecls *_cls = (cls);                                 \
  xyla_bt_updfn *_updfn = _cls->ops->upd;                               \
  struct xyla_bt_node **const *_path = (path);                          \
  int _k = (k);                                                         \
                                                                        \
  XYLA__ASSERT(*_path[_k]); while (_k) _updfn(_cls, *_path[--_k]);      \
} while (0)

#define XYLA_BT_ASCEND(rc, fn, path, k, arg) do {                       \
  /* Ascend the tree along the PATH, allowing FN to accumulate summary  \
   * data from the nodes to the root.  For each NODE link on the PATH,  \
   * including the null link in the case of an empty path, call the FN, \
   * passing the NODE pointer, its position POS, its PARENT and SIBLING \
   * pointers, and ARG.  The PATH remains valid.  If the NODE is at the \
   * root, then POS is `XYLA_BTPOS_ROOT', and PARENT and SIBLING are    \
   * null; otherwise, POS is `XYLA_BTPOS_LEFT' or `XYLA_BTPOS_RIGHT',   \
   * PARENT is the node's parent, and SIBLING points to the node's      \
   * sibling if any.  If FN returns nonzero, then stop immediately,     \
   * setting RC to the nonzero return value; otherwise, set RC to zero  \
   * on exit.                                                           \
   */                                                                   \
                                                                        \
  xyla_bt_ascendfn *_fn = (fn);                                         \
  struct xyla_bt_node *_node, **_nlink, *_parent, **_plink,             \
    **const *_path = (path);                                            \
  int _k = (k), _rc;                                                    \
  void *_arg = (arg);                                                   \
                                                                        \
  _nlink = _path[_k]; _node = *_nlink;                                  \
  for (;;) {                                                            \
    if (!_k) { (rc) = _fn(_node, 0, 0, XYLA_BTPOS_ROOT, _arg); break; } \
    _plink = _path[--_k]; _parent = *_plink;                            \
    if (_nlink == &_parent->left)                                       \
      _rc = _fn(_node, _parent, _parent->right, XYLA_BTPOS_LEFT, _arg); \
    else                                                                \
      _rc = _fn(_node, _parent, _parent->left, XYLA_BTPOS_RIGHT, _arg); \
    if (_rc) { (rc) = _rc; break; }                                     \
    _nlink = _plink; _node = _parent;                                   \
  }                                                                     \
} while (0)

/*----- Searching ---------------------------------------------------------*/

#define XYLA_BT_LOOKUP(node, cls, root, navfn, arg) do {                \
  /* Search for a node within the tree rooted at ROOT.  The search is   \
   * guided by NAVFN, passing it ARG at each node.  If the function     \
   * matches a node, then set NODE to the matching node; otherwise NODE \
   * is null on exit.                                                   \
   */                                                                   \
                                                                        \
  struct xyla_bt_node *_node;                                           \
  struct xyla_bt_nodecls *_cls = (cls);                                 \
  const struct xyla_bt_ordops *_ops;                                    \
  xyla_bt_navfn *_navfn = (navfn);                                      \
  void *_arg = (arg);                                                   \
  int _dir;                                                             \
                                                                        \
  /* If no NAVFN is provided, then see if there's one in the node       \
   * class.                                                             \
   */                                                                   \
  if (!_navfn) {                                                        \
    _ops = (const struct xyla_bt_ordops *)_cls->ops;                    \
    _navfn = _ops->ord.nav;                                             \
  }                                                                     \
                                                                        \
  /* Unsurprisingly, start at the root. */                              \
  _node = (root);                                                       \
                                                                        \
  /* Descend the tree. */                                               \
  for (;;) {                                                            \
                                                                        \
    /* If we've reached the end, then give up. */                       \
    if (!_node) { (node) = 0; break; }                                  \
                                                                        \
    /* Consult the navigation function to decide where to go next. */   \
    _dir = _navfn(_cls, _node, _arg);                                   \
    if (_dir < 0) _node = _node->left;                                  \
    else if (_dir > 0) _node = _node->right;                            \
    else { (node) = _node; break; }                                     \
  }                                                                     \
} while (0)

#define XYLA_BT_PROBE(rc, node, cls, root, navfn, arg,                  \
                      path, k, htmax) do {                              \
  /* Search for a node within the tree according to NAVFN, recording    \
   * the search path.                                                   \
   *                                                                    \
   * If the path length to the chosen node or link exceeds HTMAX then   \
   * set RC = `XYLA_RC_TALL' without altering the path; otherwise, set  \
   * RC = `XYLA_RC_OK' on exit.                                         \
   *                                                                    \
   * Balanced tree structures which maintain a constant bound on the    \
   * maximum possible height of a tree never experience failure.  Less  \
   * carefully-maintained trees must check for and handle failure: a    \
   * usual response would be to rebalance the tree and try again; a     \
   * second failure should be impossible.  Note that `failure' to find  \
   * a matching node is still considered success for the purposes of    \
   * the return value.                                                  \
   */                                                                   \
                                                                        \
  struct xyla_bt_node *_node, **_link,                                  \
    **_root = (root), ***_path = (path);                                \
  struct xyla_bt_nodecls *_cls = (cls);                                 \
  const struct xyla_bt_ordops *_ops;                                    \
  xyla_bt_navfn *_navfn = (navfn);                                      \
  void *_arg = (arg);                                                   \
  int _k, _htmax = (htmax), _dir;                                       \
                                                                        \
  /* If no NAVFN is provided, then see if there's one in the node       \
   * class.                                                             \
   */                                                                   \
  if (!_navfn) {                                                        \
    _ops = (const struct xyla_bt_ordops *)_cls->ops;                    \
    _navfn = _ops->ord.nav;                                             \
  }                                                                     \
                                                                        \
  /* Unsurprisingly, start at the root. */                              \
  _path[0] = _root; _k = 0; _node = *_root;                             \
                                                                        \
  /* Descend the tree. */                                               \
  for (;;) {                                                            \
                                                                        \
    /* If we've reached the end, then give up. */                       \
    if (!_node) { (node) = 0; (k) = _k; (rc) = XYLA_RC_OK; break; }     \
                                                                        \
    /* Consult the navigation function to decide where to go next. */   \
    _dir = _navfn(_cls, _node, _arg);                                   \
    if (_dir < 0) _link = &_node->left;                                 \
    else if (_dir > 0) _link = &_node->right;                           \
    else { (node) = _node; (k) = _k; (rc) = XYLA_RC_OK; break; }        \
                                                                        \
    /* Append the link to the path and continue. */                     \
    if (_k >= _htmax) { (rc) = XYLA_RC_TALL; (node) = 0; break; }       \
    _path[++_k] = _link; _node = *_link;                                \
  }                                                                     \
} while (0)

/*----- Removal -----------------------------------------------------------*/

extern int xyla_bt_remove(struct xyla_bt_node **/*del_out*/,
                          struct xyla_bt_node **/*subst_out*/,
                          struct xyla_bt_node **/*replace_out*/,
                          struct xyla_bt_node ***/*path*/, int */*k_inout*/,
                          int /*htmax*/);
  /* Remove a node from a binary tree.
   *
   * The (*K_INOUT + 1)-step PATH must be full, i.e., its final link must
   * point to a node present in the tree.  It's that node which is to be
   * removed; a pointer to it is stored in *DEL_OUT.
   *
   * If the deleted node has two children, then it can't easily be
   * disentangled from the tree.  Instead, the node is swapped with its
   * immediate successor, which must exist because the node has two children
   * and therefore a right child.  On the other hand, the immediate successor
   * is the leftmost node in the deleted node's right subtree, and therefore
   * has no left child.  In this case, *SUBST_NODE is set to the successor
   * node, which may require some further fixing up (e.g., to maintain
   * balance state).  The path is extended, by appending addition link
   * pointers and updating *K_INOUT, to refer to the place at which the
   * successor node was linked.  If the deleted node doesn't have both
   * children, none of this is necessary: *SUBST_NODE is set to null, and the
   * path is left unchanged.  If there is insufficient space in the path
   * vector, then return `XYLA_RC_TALL'.
   *
   * The node (after substitution) is replaced with its child, if it has one,
   * or a null pointer.  This replacement node is returned in *REPLACE_OUT.
   *
   * The modified nodes are all on the PATH; updating them is left for the
   * caller.
   *
   * Return `XYLA_RC_OK' on success.
   */

/*----- Set operations ----------------------------------------------------*/

typedef int xyla_bt_joinfn(struct xyla_bt_nodecls */*cls*/,
                           struct xyla_bt_node **/*root_out*/,
                             int */*rootht_out*/,
                           struct xyla_bt_node **/*left*/, int /*lht*/,
                           struct xyla_bt_node */*mid*/,
                           struct xyla_bt_node **/*right*/, int /*rht*/);
  /* Join two trees rooted at *LEFT and *RIGHT, with heights LHT and RHT,
   * with the separating node MID (which may be null to join the trees with
   * no additional separator).  Write the root of the joined tree to
   * *ROOT_OUT and its height (if interesting) to *ROOTHT_OUT.  Return a
   * `XYLA_RC_...' code, but failure is not currently permitted.
   */

typedef int xyla_bt_splitatfn(struct xyla_bt_nodecls */*cls*/,
                              struct xyla_bt_node **/*left_out*/,
                                int */*lht_out*/,
                              struct xyla_bt_node **/*mid_out*/,
                              struct xyla_bt_node **/*right_out*/,
                                int */*rht_out*/,
                              struct xyla_bt_node **/*root*/,
                              const void */*key*/);
  /* Split the tree rooted at *ROOT at the position indicated by the KEY.
   * Write the roots of the resulting left and right trees to *LEFT_OUT and
   * *RIGHT_OUT, and their heights, if interesting, to *LHT_OUT and *RHT_OUT.
   * If a node matching KEY was found, then it is not included in either
   * subtree: instead, a store a pointer to the matching node in *MID_OUT;
   * otherwise, set *MID_OUT to null.  Return a `XYLA_RC_...' code, but
   * failure is not currently permitted.
   */

typedef int xyla_bt_splitrootfn(struct xyla_bt_node **/*left_out*/,
                                  int */*lht_out*/,
                                struct xyla_bt_node **/*root_out*/,
                                struct xyla_bt_node **/*right_out*/,
                                  int */*rht*/,
                                struct xyla_bt_node **/*root*/,
                                  int /*treeht*/);
  /* Split the tree rooted at *ROOT, with height TREEHT, at its root.  Write
   * the roots of the left and right subtrees to *LEFT_OUT and *RIGHT_OUT,
   * and their heights, if interesting, to *LHT_OUT and *RHT_OUT, and the
   * original root node to *ROOT_OUT.  Return a `XYLA_RC_...' code, but
   * failure is not currently permitted.
   */

struct xyla_bt_treeops {
  /* Tree operations table. */

  xyla_bt_joinfn *join;
  xyla_bt_splitatfn *splitat;
  xyla_bt_splitrootfn *splitroot;
};

struct xyla_bt_setopstack {
  /* Stack entries for set operations. */

  unsigned op;
  union {
    struct {
      struct xyla_bt_node *a; int aht;
      struct xyla_bt_node *b; int bht;
    } right;
    struct {
      struct xyla_bt_node *uni; int uniht;
      struct xyla_bt_node *isect; int isectht;
    } join_union;
    struct {
      struct xyla_bt_node *diff; int diffht;
      struct xyla_bt_node *isect; int isectht;
    } join_diff;
  } u;
  struct xyla_bt_node *am, *bm;
};

extern int xyla_bt_unisect(struct xyla_bt_nodecls */*cls*/,
                           struct xyla_bt_node **/*uni_out*/,
                             int */*uniht_out*/,
                           struct xyla_bt_node **/*isect_out*/,
                             int */*isectht_out*/,
                           struct xyla_bt_node **/*aroot*/,
                             int */*aht_inout*/,
                           struct xyla_bt_node **/*broot*/,
                             int */*bht_inout*/,
                           const struct xyla_bt_treeops */*ops*/,
                           struct xyla_bt_setopstack */*stack*/,
                           int /*htmax*/);
  /* Compute the union and intersection of two trees.
   *
   * On entry, *AROOT and *BROOT are the roots of two trees a and b, with
   * their respective heights in *AHT_INOUT and *BHT_INOUT.  The trees are
   * considered to represent sets, with one element per node; the element is
   * determined by the `key' node-class operation.  On exit, *UNI_OUT points
   * to the root of a tree containing (one copy of) each element present in
   * either a or b, and *ISECT_OUT points to the root of a tree containing
   * the other copy of each element present in both a and b; the heights of
   * the output trees (the exact meaning of which is determined by the tree
   * implementation) are stored in *UNIHT_OUT and *ISECTHT_OUT.  If AROOT
   * and/or BROOT are distinct from UNI_OUT and ISECT_OUT, then null pointers
   * are stored in them.  The original trees are destroyed; each node in the
   * original operands trees ends up in exactly one of the result trees.
   *
   * The STACK argument points to caller-provided workspace, with HTMAX
   * entries.  The function returns `XYLA_RC_OK' on success.  If the stack is
   * too small then it returns `XYLA_RC_TALL'; *UNI_OUT and *ISECT_OUT are
   * unchanged; and the trees rooted at *AROOT and *BROOT are modified, with
   * their heights at *AHT_INOUT and *BHT_INOUT updated.  Retrying the
   * operation with a larger stack or following rebalancing will produce the
   * correct result.  The critical factor is the maximum height of the tree
   * at *AROOT.
   */

extern int xyla_bt_diffsect(struct xyla_bt_nodecls */*cls*/,
                            struct xyla_bt_node **/*diff_out*/,
                              int */*diffht_out*/,
                            struct xyla_bt_node **/*isect_out*/,
                              int */*isectht_out*/,
                            struct xyla_bt_node **/*aroot*/,
                              int */*aht_inout*/,
                            struct xyla_bt_node **/*broot*/,
                            const struct xyla_bt_treeops */*ops*/,
                            struct xyla_bt_setopstack */*stack*/,
                              int /*htmax*/);
  /* Compute the set difference of the two operand trees.
   *
   * On entry, *AROOT and *BROOT are the roots of two trees a and b, with a's
   * height in *AHT_INOUT (the height of b is not significant).  The trees
   * are considered to represent sets, with one element per node; the element
   * is determined by the `key' node-class operation.  On exit, *DIFF_OUT
   * points to the root of a tree containing each element of a but not b, and
   * *ISECT_OUT points to the root of a tree containing each element of a
   * that's also in b; the heights of the output trees (the exact meaning of
   * which is determined by the tree implementation) are stored in
   * *DIFFHT_OUT and *ISECTHT_OUT.  If AROOT and/or BROOT are distinct from
   * DIFF_OUT and ISECT_OUT, then null pointers are stored in them.  The
   * original a tree is destroyed; each node in the original operands trees
   * ends up in exactly one of the result trees.  The input b tree is
   * unchanged.
   *
   * The STACK argument points to caller-provided workspace, with HTMAX
   * entries.  The function return `XYLA_RC_OK' on success.  If the stack is
   * too small then it returns `XYLA_RC_TALL'; *DIFF_OUT is unchanged, and
   * the nodes of the a tree are split between output trees rooted at *AROOT
   * and *ISECT_OUT, with the heights at *AHT_INOUT and *ISECTHT_OUT set
   * appropriately.  The critical factor is the maximum height of the tree at
   * *BROOT.  The correct result can be obtained by (a) restoring the
   * original a set as the union of the *AROOT and *ISECTHT_OUT trees and (b)
   * retrying the original difference computation with a rebalanced b tree.
   * Note that the intersection result from (a) will be empty.
   */

/*----- Checking ----------------------------------------------------------*/

#ifndef XYLA_FREESTANDING

enum {
  /* Operation code passed to checking functions. */

  XYLA_CHKOP_NIL,                       /* a null link */
  XYLA_CHKOP_SETUP,                     /* initialize node information */
  XYLA_CHKOP_BEFORE,                    /* before the children */
  XYLA_CHKOP_MID,                       /* after left child, before right */
  XYLA_CHKOP_AFTER,                     /* after both children */
  XYLA_CHKOP_TEARDOWN                   /* release node information */
};

struct xyla_bt_check;

typedef int xyla_bt_chkfn(unsigned /*op*/,
                          const struct xyla_bt_check */*chk*/);
  /* A tree checker function.  It's passed an OP code, which is one of the
   * `XYLA_CHKOP_...' codes listed above, and a pointer CHK to the checking
   * state.
   *
   * The function returns a `XYLA_RC_...' code, which may be `XYLA_RC_OK' if
   * all is well, `XYLA_RC_BAD' to record that the tree structure is invalid,
   * or anything else to abort checking.  The `XYLA_CHKOP_TEARDOWN' operation
   * must not fail.
   */

typedef void xyla_bt_idfn(struct xyla_bt_nodecls */*cls*/,
                          const struct xyla_bt_node */*node*/, FILE */*fp*/);
  /* Print a description of the NODE to the output stream FP. */

struct xyla_bt_chkopslots {
  /* Checking operations table. */

  xyla_bt_chkfn *chk; size_t infosz;
  xyla_bt_idfn *id;
};
#define XYLA_BT_CHKOPSPFX XYLA_BT_ORDOPSPFX; struct xyla_bt_chkopslots chk
struct xyla_bt_chkops { XYLA_BT_CHKOPSPFX; };
#define XYLA_BT_CHKOPSUSFX struct xyla_bt_chkops chk; XYLA_BT_ORDOPSUSFX
union xyla_bt_chkopsu { XYLA_BT_CHKOPSUSFX; };

struct xyla_bt_check {
  /* Structure holding information passed to checking functions. */

  struct xyla_bt_nodecls *cls;          /* node class */
  struct xyla_bt_node *const *root;     /* address of root link */
  FILE *fp;                             /* output file descriptor or null */
  unsigned f;                           /* flags */
#define XYLA_CHKF_COREMASK 0x003fu      /*   flags reserved for core */
#define XYLA_CHKF_TREEMASK 0x07c0u      /*   flags reserved for tree */
#define XYLA_CHKF_APPMASK 0xf800u       /*   flags reserved for app */
  const struct xyla_bt_node *parent; void *parent_info; /* parent */
  const struct xyla_bt_node *node; unsigned pos; void *node_info; /* node */
  const struct xyla_bt_node *left; void *left_info; /* left child */
  const struct xyla_bt_node *right; void *right_info; /* right child */
  void *state;                          /* checker state */
};

extern void xyla_bt_bughdr(const char */*token*/,
                           struct xyla_bt_node *const */*root*/,
                           FILE */*fp*/);
  /* Begin reporting a bug found during checking. */

extern void xyla_bt_printnode(struct xyla_bt_nodecls */*cls*/,
                              const struct xyla_bt_node */*node*/,
                              FILE */*fp*/);
  /* Print a description of NODE to the stream FP. */

extern int xyla_bt_check(struct xyla_bt_nodecls */*cls*/,
                         struct xyla_bt_node *const */*root*/,
                         FILE */*fp*/, unsigned /*f*/,
                         xyla_bt_chkfn */*tree_chkfn*/,
                         size_t /*tree_infosz*/,
                         void */*tree_state*/, void */*user_state*/);
  /* Check that a binary tree satisfies all of its invariants.
   *
   * Walk a binary tree, checking everything.  The only property that this
   * function checks for itself is that each node is linked from only one
   * parent.  All other checking is performed by caller-provided functions.
   *
   * There are two caller-provided checkers.  The `tree checker' is provided
   * by the tree implementation, checking that the tree satisfies the
   * necessary balance properties; the `user checker' is provided by the
   * application, through the node class, and checks that the application's
   * invariants are satisfied.
   *
   * Each of the two checkers has a /function/, which is called (several
   * times) on each node in turn; a /state/ pointer, which is passed through
   * to the function to track its overall state; and per-node /info/ pointers
   * used to track perperties through the tree.  The tree checker function is
   * provided as the TREE_CHKFN argument, and the user checker function is
   * the `chk' operation in the node class CLS; the state pointers are
   * provided as arguments TREE_STATE and USER_STATE; the walker allocates
   * storage for the info structures as it traverses the tree, based on the
   * TREE_INFOSZ argument for the tree checker, and the `infosz' class-
   * operations member for the user checker.
   *
   * The ROOT argument is the /address/ of the tree's root link.  The root is
   * not modified, but the address is printed in diagnostics.
   *
   * The F argument holds flags passed to checking functions.  No flags are
   * currently defined, but the space is divided with six for the core
   * (though likely of interest to all), five for tree implementations, and
   * five for applications.
   *
   * Diagnostics are reported to FP, unless this is null.  Usually, `stderr'
   * is a good choice.
   *
   * The walker operates as follows.
   *
   *   * If the link it has followed is null, then it calls the checking
   *     functions with operation `XYLA_CHKOP_NIL' and returns to the parent.
   *
   *   * Otherwise, it notes that the current node has been seen on the
   *     current traversal.  This currently involves rewriting the node's
   *     links, so they are /not valid/ when the tree and user checkers are
   *     invoked; the `struct xyla_bt_check' structure passed to the checker
   *     functions contains the correct child links.
   *
   *   * It allocates per-node information storage for the checkers, and
   *     calls the checker functions with operation `XYLA_CHKOP_SETUP' to
   *     initialize their per-node storage.
   *
   *   * It calls the checker functions with operation `XYLA_CHKOP_BEFORE'.
   *
   *   * It visits the node's left child link.  If the left link is not null,
   *     this will recursively allocate and set up the left child's node
   *     information, which is provided to future calls to the checker.
   *
   *   * It calls the checker functions with operation `XYLA_CHKOP_MID'.
   *
   *   * It visits the node's right child link.  If the right link is not
   *     null, this will recursively allocate and set up the right child's
   *     node information, which is provided to future calls to the checker.
   *
   *   * It calls the checker functions with operation `XYLA_CHKOP_AFTER'.
   *
   *   * It calls the checker functions with operation `XYLA_CHKOP_TEARDOWN'
   *     after calling the /parent/ with `XYLA_CHKOP_AFTER'.
   *
   * If a checker function returns a code other than `XYLA_RC_OK' or
   * `XYLA_RC_BAD' then further processing is abbreviated: no new nodes are
   * visited and only `XYLA_CHKOP_TEARDOWN' calls are made.
   *
   * If all the checker calls returned `XYLA_RC_OK' then the return value is
   * `XYLA_RC_OK'; if any checker call returned `XYLA_RC_BAD', but none
   * returned any other value, then the return value is `XYLA_RC_BAD';
   * otherwise, the return value is the code from the failing checker call.
   */

struct xyla_bt_ordinfo {
  /* This is the node-information structure maintained by `xyla_bt_chkorder'
   * below.
   */

  const void *lbound, *rbound;
};

extern xyla_bt_chkfn xyla_bt_chkorder;
  /* A checking function to verify that the tree order respects the
   * ordering.
   */

#endif

/*----- That's all, folks -------------------------------------------------*/

#endif