--- /dev/null
+/*
+ * Flexible B-tree implementation. Supports reference counting for
+ * copy-on-write, user-defined node properties, and variable
+ * degree.
+ *
+ * This file is copyright 2001,2004 Simon Tatham.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+ * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+/*
+ * TODO:
+ *
+ * Possibly TODO in future, but may not be sensible in this code
+ * architecture:
+ *
+ * - user write properties.
+ * * this all happens during write_unlock(), I think. Except
+ * that we'll now need an _internal_ write_unlock() which
+ * does everything except user write properties. Sigh.
+ * * note that we also need a transform function for elements
+ * (rot13 will certainly require this, and reverse will
+ * require it if the elements themselves are in some way
+ * reversible).
+ *
+ * Still untested:
+ * - searching on user read properties.
+ * - user-supplied copy function.
+ * - bt_add when element already exists.
+ * - bt_del when element doesn't.
+ * - splitpos with before==TRUE.
+ * - split() on sorted elements (but it should be fine).
+ * - bt_replace, at all (it won't be useful until we get user read
+ * properties).
+ * - bt_index_w (won't make much sense until we start using
+ * user-supplied copy fn).
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#ifdef TEST
+#include <stdio.h>
+#include <stdarg.h>
+#endif
+
+#include "btree.h"
+
+#ifdef TEST
+static void set_invalid_property(void *prop);
+#endif
+
+/* ----------------------------------------------------------------------
+ * Type definitions.
+ */
+
+typedef union nodecomponent nodecomponent;
+typedef nodecomponent *nodeptr;
+
+/*
+ * For type-checking purposes, and to ensure I don't accidentally
+ * confuse node_addr with node_ptr during implementation, I'll
+ * define node_addr for the in-memory case as being a struct
+ * containing only a nodeptr.
+ *
+ * This unfortunately needs to go in btree.h so that clients
+ * writing user properties can know about the nodecomponent
+ * structure.
+ */
+typedef struct {
+ nodeptr p;
+} node_addr;
+
+/*
+ * A B-tree node is a horrible thing when you're trying to be
+ * flexible. It is of variable size, and it contains a variety of
+ * distinct types of thing: nodes, elements, some counters, some
+ * user-defined properties ... it's a horrible thing. So we define
+ * it as an array of unions, each union being either an `int' or a
+ * `bt_element_t' or a `node_addr'...
+ */
+
+union nodecomponent {
+ int i;
+ node_addr na;
+ bt_element_t ep;
+};
+
+static const node_addr NODE_ADDR_NULL = { NULL };
+
+/*
+ * The array of nodecomponents will take the following form:
+ *
+ * - (maxdegree) child pointers.
+ * - (maxdegree-1) element pointers.
+ * - one subtree count (current number of child pointers that are
+ * valid; note that `valid' doesn't imply non-NULL).
+ * - one element count.
+ * - one reference count.
+ */
+
+struct btree {
+ int mindegree; /* min number of subtrees */
+ int maxdegree; /* max number of subtrees */
+ int depth; /* helps to store this explicitly */
+ node_addr root;
+ cmpfn_t cmp;
+ copyfn_t copy;
+ freefn_t freeelt;
+ int propsize, propalign, propoffset;
+ propmakefn_t propmake;
+ propmergefn_t propmerge;
+ void *userstate; /* passed to all user functions */
+};
+
+/* ----------------------------------------------------------------------
+ * Memory management routines and other housekeeping.
+ */
+#ifdef HAVE_ALLOCA
+# define ialloc(x) alloca(x)
+# define ifree(x)
+#else
+# define ialloc(x) smalloc(x)
+# define ifree(x) sfree(x)
+#endif
+
+#define new1(t) ( (t *) smalloc(sizeof(t)) )
+#define newn(t, n) ( (t *) smalloc((n) * sizeof(t)) )
+#define inew1(t) ( (t *) ialloc(sizeof(t)) )
+#define inewn(t, n) ( (t *) ialloc((n) * sizeof(t)) )
+
+static void *smalloc(size_t size)
+{
+ void *ret = malloc(size);
+ if (!ret)
+ abort();
+ return ret;
+}
+
+static void sfree(void *p)
+{
+ free(p);
+}
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+/* We could probably do with more compiler-specific branches of this #if. */
+#if defined(__GNUC__)
+#define INLINE __inline
+#else
+#define INLINE
+#endif
+
+/* Hooks into the low-level code for test purposes. */
+#ifdef TEST
+void testlock(int write, int set, nodeptr n);
+#else
+#define testlock(w,s,n)
+#endif
+
+/* ----------------------------------------------------------------------
+ * Low-level helper routines, which understand the in-memory format
+ * of a node and know how to read-lock and write-lock.
+ */
+
+/*
+ * Read and write the node_addr of a child.
+ */
+static INLINE node_addr bt_child(btree *bt, nodeptr n, int index)
+{
+ return n[index].na;
+}
+static INLINE void bt_set_child(btree *bt, nodeptr n,
+ int index, node_addr value)
+{
+ n[index].na = value;
+}
+
+/*
+ * Read and write the address of an element.
+ */
+static INLINE bt_element_t bt_element(btree *bt, nodeptr n, int index)
+{
+ return n[bt->maxdegree + index].ep;
+}
+static INLINE void bt_set_element(btree *bt, nodeptr n,
+ int index, bt_element_t value)
+{
+ n[bt->maxdegree + index].ep = value;
+}
+
+/*
+ * Give the number of subtrees currently present in an element.
+ */
+static INLINE int bt_subtrees(btree *bt, nodeptr n)
+{
+ return n[bt->maxdegree*2-1].i;
+}
+#define bt_elements(bt,n) (bt_subtrees(bt,n) - 1)
+
+/*
+ * Give the minimum and maximum number of subtrees allowed in a
+ * node.
+ */
+static INLINE int bt_min_subtrees(btree *bt)
+{
+ return bt->mindegree;
+}
+static INLINE int bt_max_subtrees(btree *bt)
+{
+ return bt->maxdegree;
+}
+
+/*
+ * Return the count of items, and the user properties, in a
+ * particular subtree of a node.
+ *
+ * Note that in the in-memory form of the tree, this breaks the
+ * read-locking semantics, by reading the counts out of the child
+ * nodes without bothering to lock them. We're allowed to do this
+ * because this function is implemented at the same very low level
+ * as the implementation of bt_read_lock(), so we're allowed to
+ * know that read locking actually doesn't do anything.
+ */
+static INLINE int bt_child_count(btree *bt, nodeptr n, int index)
+{
+ if (n[index].na.p)
+ return n[index].na.p[bt->maxdegree*2].i;
+ else
+ return 0;
+}
+
+static INLINE void *bt_child_prop(btree *bt, nodeptr n, int index)
+{
+ if (n[index].na.p)
+ return (char *)n[index].na.p + bt->propoffset;
+ else
+ return NULL;
+}
+
+/*
+ * Return the count of items in a whole node.
+ */
+static INLINE int bt_node_count(btree *bt, nodeptr n)
+{
+ return n[bt->maxdegree*2].i;
+}
+
+/*
+ * Determine whether a node is a leaf node or not.
+ */
+static INLINE int bt_is_leaf(btree *bt, nodeptr n)
+{
+ return n[0].na.p == NULL;
+}
+
+/*
+ * Create a new write-locked node, and return a pointer to it.
+ */
+static INLINE nodeptr bt_new_node(btree *bt, int nsubtrees)
+{
+ nodeptr ret = (nodecomponent *)smalloc(bt->propoffset + bt->propsize);
+ ret[bt->maxdegree*2-1].i = nsubtrees;
+ ret[bt->maxdegree*2+1].i = 1; /* reference count 1 */
+#ifdef TEST
+ set_invalid_property(ret + bt->maxdegree * 2 + 2);
+#else
+ memset((char *)ret + bt->propoffset, 0, bt->propsize);
+#endif
+ testlock(TRUE, TRUE, ret);
+ return ret;
+}
+
+/*
+ * Destroy a node (must be write-locked).
+ */
+static INLINE void bt_destroy_node(btree *bt, nodeptr n)
+{
+ testlock(TRUE, FALSE, n);
+ /* Free the property. */
+ bt->propmerge(bt->userstate, NULL, NULL, n + bt->maxdegree * 2 + 2);
+ sfree(n);
+}
+
+/*
+ * Take an existing node and prepare to re-use it in a new context.
+ */
+static INLINE nodeptr bt_reuse_node(btree *bt, nodeptr n, int nsubtrees)
+{
+ testlock(TRUE, FALSE, n);
+ testlock(TRUE, TRUE, n);
+ n[bt->maxdegree*2-1].i = nsubtrees;
+ return n;
+}
+
+/*
+ * Return an extra reference to a node, for purposes of cloning. So
+ * we have to update its reference count as well.
+ */
+static INLINE node_addr bt_ref_node(btree *bt, node_addr n)
+{
+ if (n.p)
+ n.p[bt->maxdegree*2+1].i++;
+ return n;
+}
+
+/*
+ * Drop a node's reference count, for purposes of freeing. Returns
+ * the new reference count. Typically this will be tested against
+ * zero to see if the node needs to be physically freed; hence a
+ * NULL node_addr causes a return of 1 (because this isn't
+ * necessary).
+ */
+static INLINE int bt_unref_node(btree *bt, node_addr n)
+{
+ if (n.p) {
+ n.p[bt->maxdegree*2+1].i--;
+ return n.p[bt->maxdegree*2+1].i;
+ } else
+ return 1; /* a NULL node is considered OK */
+}
+
+/*
+ * Clone a node during write unlocking, if its reference count is
+ * more than one.
+ */
+static nodeptr bt_clone_node(btree *bt, nodeptr n)
+{
+ int i;
+ nodeptr ret = (nodecomponent *)smalloc(bt->propoffset + bt->propsize);
+ memcpy(ret, n, (bt->maxdegree*2+1) * sizeof(nodecomponent));
+ if (bt->copy) {
+ for (i = 0; i < bt_elements(bt, ret); i++) {
+ bt_element_t *e = bt_element(bt, ret, i);
+ bt_set_element(bt, ret, i, bt->copy(bt->userstate, e));
+ }
+ }
+ ret[bt->maxdegree*2+1].i = 1; /* clone has reference count 1 */
+ n[bt->maxdegree*2+1].i--; /* drop original's ref count by one */
+ /*
+ * At this low level, we're allowed to reach directly into the
+ * subtrees to fiddle with their reference counts without
+ * having to lock them.
+ */
+ for (i = 0; i < bt_subtrees(bt, ret); i++) {
+ node_addr na = bt_child(bt, ret, i);
+ if (na.p)
+ na.p[bt->maxdegree*2+1].i++; /* inc ref count of each child */
+ }
+ /*
+ * Copy the user property explicitly (in case it contains a
+ * pointer to an allocated area).
+ */
+ memset((char *)ret + bt->propoffset, 0, bt->propsize);
+ bt->propmerge(bt->userstate, NULL, n + bt->maxdegree * 2 + 2,
+ ret + bt->maxdegree * 2 + 2);
+ return ret;
+}
+
+/*
+ * Return the node_addr for a currently locked node. NB that this
+ * means node movement must take place during _locking_ rather than
+ * unlocking!
+ */
+static INLINE node_addr bt_node_addr(btree *bt, nodeptr n)
+{
+ node_addr ret;
+ ret.p = n;
+ return ret;
+}
+
+/*
+ * The bt_write_lock and bt_read_lock functions should gracefully
+ * handle being asked to write-lock a null node pointer, and just
+ * return a null nodeptr.
+ */
+static INLINE nodeptr bt_write_lock_child(btree *bt, nodeptr a, int index)
+{
+ node_addr addr = bt_child(bt, a, index);
+ if (addr.p && addr.p[bt->maxdegree*2+1].i > 1) {
+ nodeptr clone = bt_clone_node(bt, addr.p);
+ bt_set_child(bt, a, index, bt_node_addr(bt, clone));
+ testlock(TRUE, TRUE, clone);
+ return clone;
+ }
+ testlock(TRUE, TRUE, addr.p);
+ return addr.p;
+}
+static INLINE nodeptr bt_write_lock_root(btree *bt)
+{
+ node_addr addr = bt->root;
+ if (addr.p && addr.p[bt->maxdegree*2+1].i > 1) {
+ nodeptr clone = bt_clone_node(bt, addr.p);
+ bt->root = bt_node_addr(bt, clone);
+ testlock(TRUE, TRUE, clone);
+ return clone;
+ }
+ testlock(TRUE, TRUE, addr.p);
+ return addr.p;
+}
+static INLINE nodeptr bt_read_lock(btree *bt, node_addr a)
+{
+ testlock(FALSE, TRUE, a.p);
+ return a.p;
+}
+#define bt_read_lock_root(bt) (bt_read_lock(bt, (bt)->root))
+#define bt_read_lock_child(bt,a,index) (bt_read_lock(bt,bt_child(bt,a,index)))
+
+static INLINE void bt_write_relock(btree *bt, nodeptr n, int props)
+{
+ int i, ns, count;
+
+ /*
+ * Update the count in the node.
+ */
+ ns = bt_subtrees(bt, n);
+ count = ns-1; /* count the elements */
+ for (i = 0; i < ns; i++)
+ count += bt_child_count(bt, n, i);
+ n[bt->maxdegree*2].i = count;
+ testlock(TRUE, FALSE, n);
+ testlock(TRUE, TRUE, n);
+
+ /*
+ * Update user read properties.
+ */
+ if (props && bt->propsize) {
+ void *prevprop, *eltprop, *thisprop, *childprop;
+
+ prevprop = NULL;
+ eltprop = ialloc(bt->propsize);
+ thisprop = (void *)((char *)n + bt->propoffset);
+
+ for (i = 0; i < ns; i++) {
+ /* Merge a subtree's property into this one.
+ * Initially prevprop==NULL, meaning to just copy. */
+ if ( (childprop = bt_child_prop(bt, n, i)) != NULL ) {
+ bt->propmerge(bt->userstate, prevprop, childprop, thisprop);
+ prevprop = thisprop;
+ }
+
+ if (i < ns-1) {
+ /* Now merge in the separating element. */
+ bt->propmake(bt->userstate, bt_element(bt, n, i), eltprop);
+ bt->propmerge(bt->userstate, prevprop, eltprop, thisprop);
+ prevprop = thisprop;
+ }
+ }
+
+ ifree(eltprop);
+ }
+}
+
+static INLINE node_addr bt_write_unlock_internal(btree *bt, nodeptr n,
+ int props)
+{
+ node_addr ret;
+
+ bt_write_relock(bt, n, props);
+
+ testlock(TRUE, FALSE, n);
+
+ ret.p = n;
+ return ret;
+}
+
+static INLINE node_addr bt_write_unlock(btree *bt, nodeptr n)
+{
+ return bt_write_unlock_internal(bt, n, TRUE);
+}
+
+static INLINE void bt_read_unlock(btree *bt, nodeptr n)
+{
+ /*
+ * For trees in memory, we do nothing here, except run some
+ * optional testing.
+ */
+ testlock(FALSE, FALSE, n);
+}
+
+/* ----------------------------------------------------------------------
+ * Higher-level helper functions, which should be independent of
+ * the knowledge of precise node structure in the above code.
+ */
+
+/*
+ * Return the count of items below a node that appear before the
+ * start of a given subtree.
+ */
+static int bt_child_startpos(btree *bt, nodeptr n, int index)
+{
+ int pos = 0;
+
+ while (index > 0) {
+ index--;
+ pos += bt_child_count(bt, n, index) + 1; /* 1 for separating elt */
+ }
+ return pos;
+}
+
+/*
+ * Create a new root node for a tree.
+ */
+static void bt_new_root(btree *bt, node_addr left, node_addr right,
+ bt_element_t element)
+{
+ nodeptr n;
+ n = bt_new_node(bt, 2);
+ bt_set_child(bt, n, 0, left);
+ bt_set_child(bt, n, 1, right);
+ bt_set_element(bt, n, 0, element);
+ bt->root = bt_write_unlock(bt, n);
+ bt->depth++;
+}
+
+/*
+ * Discard the root node of a tree, and enshrine a new node as the
+ * root. Expects to be passed a write-locked nodeptr to the old
+ * root.
+ */
+static void bt_shift_root(btree *bt, nodeptr n, node_addr na)
+{
+ bt_destroy_node(bt, n);
+ bt->root = na;
+ bt->depth--;
+}
+
+/*
+ * Given a numeric index within a node, find which subtree we would
+ * descend to in order to find that index.
+ *
+ * Updates `pos' to give the numeric index within the subtree
+ * found. Also returns `ends' (if non-NULL), which has bit 0 set if
+ * the index is at the very left edge of the subtree, and/or bit 1
+ * if it's at the very right edge.
+ *
+ * Return value is the number of the subtree (0 upwards).
+ */
+#define ENDS_NONE 0
+#define ENDS_LEFT 1
+#define ENDS_RIGHT 2
+#define ENDS_BOTH 3
+static int bt_lookup_pos(btree *bt, nodeptr n, int *pos, int *ends)
+{
+ int child = 0;
+ int nchildren = bt_subtrees(bt, n);
+
+ while (child < nchildren) {
+ int count = bt_child_count(bt, n, child);
+ if (*pos <= count) {
+ if (ends) {
+ *ends = 0;
+ if (*pos == count)
+ *ends |= ENDS_RIGHT;
+ if (*pos == 0)
+ *ends |= ENDS_LEFT;
+ }
+ return child;
+ }
+ *pos -= count + 1; /* 1 for the separating element */
+ child++;
+ }
+ return -1; /* ran off the end; shouldn't happen */
+}
+
+/*
+ * Given an element to search for within a node, find either the
+ * element, or which subtree we would descend to to continue
+ * searching for that element.
+ *
+ * Return value is either the index of the element, or the index of
+ * the subtree (both 0 upwards). `is_elt' returns FALSE or TRUE
+ * respectively.
+ *
+ * Since this may be used by bt_find() with an alternative cmpfn_t,
+ * we always pass the input element as the first argument to cmp.
+ */
+static int bt_lookup_cmp(btree *bt, nodeptr n, bt_element_t element,
+ cmpfn_t cmp, int *is_elt)
+{
+ int mintree = 0, maxtree = bt_subtrees(bt, n)-1;
+
+ while (mintree < maxtree) {
+ int elt = (maxtree + mintree) / 2;
+ int c = cmp(bt->userstate, element, bt_element(bt, n, elt));
+
+ if (c == 0) {
+ *is_elt = TRUE;
+ return elt;
+ } else if (c < 0) {
+ /*
+ * `element' is less than element `elt'. So it can be
+ * in subtree number `elt' at the highest.
+ */
+ maxtree = elt;
+ } else { /* c > 0 */
+ /*
+ * `element' is greater than element `elt'. So it can
+ * be in subtree number (elt+1) at the lowest.
+ */
+ mintree = elt+1;
+ }
+ }
+
+ /*
+ * If we reach here without returning, we must have narrowed
+ * our search to the point where mintree = maxtree. So the
+ * element is not in the node itself and we know which subtree
+ * to search next.
+ */
+ assert(mintree == maxtree);
+ *is_elt = FALSE;
+ return mintree;
+}
+
+/*
+ * Generic transformations on B-tree nodes.
+ *
+ * This function divides essentially into an input side and an
+ * output side. The input side accumulates a list of items
+ * node,element,node,element,...,element,node; the output side
+ * writes those items into either one or two nodes.
+ *
+ * `intype' can be:
+ *
+ * - NODE_AS_IS. The input list is the contents of in1, followed
+ * by inelt, followed by the contents of in2. The `extra'
+ * parameters are unused, as is `inaux'.
+ *
+ * - NODE_ADD_ELT. `in2' is unused. The input list is the contents
+ * of `in1', but with subtree pointer number `inaux' replaced by
+ * extra1/inelt/extra2.
+ *
+ * - NODE_DEL_ELT. `in2' and `inelt' are unused, as is `extra2'.
+ * The input list is the contents of `in1', but with element
+ * pointer number `inaux' and its surrounding two subtrees
+ * replaced by extra1.
+ *
+ * Having obtained the input list, it is then written to one or two
+ * output nodes. If `splitpos' is NODE_JOIN, everything is written
+ * into one output node `out1'. Otherwise, `splitpos' is treated as
+ * an element index within the input list; that element is returned
+ * in `outelt', and the contents of the list is divided there and
+ * returned in nodes `out1' and `out2'.
+ *
+ * This function will re-use nodes in the `obvious' order. If two
+ * nodes are passed in and two nodes are output, they'll be the
+ * same nodes; if one node is passed in and one node output, it
+ * will be the same node too. If two are passed in and only one
+ * output, the first one will be used and the second destroyed; if
+ * one node is passed in and two are output, the one passed in will
+ * be the first of those returned, and the second will be new.
+ */
+#define NODE_AS_IS 1
+#define NODE_ADD_ELT 2
+#define NODE_DEL_ELT 3
+#define NODE_JOIN -1
+static void bt_xform(btree *bt, int intype, int inaux,
+ nodeptr in1, nodeptr in2, bt_element_t inelt,
+ node_addr extra1, node_addr extra2,
+ int splitpos, nodeptr *out1, nodeptr *out2,
+ bt_element_t *outelt)
+{
+ node_addr *nodes;
+ bt_element_t *elements;
+ nodeptr ret1, ret2;
+ int n1, n2, off2, i, j;
+
+ nodes = inewn(node_addr, 2 * bt_max_subtrees(bt));
+ elements = inewn(bt_element_t, 2 * bt_max_subtrees(bt));
+
+ /*
+ * Accumulate the input list.
+ */
+ switch(intype) {
+ case NODE_AS_IS:
+ n1 = bt_subtrees(bt, in1);
+ n2 = bt_subtrees(bt, in2);
+ off2 = 0;
+ break;
+ case NODE_ADD_ELT:
+ in2 = in1;
+ n1 = inaux+1;
+ n2 = bt_subtrees(bt, in1) - inaux;
+ off2 = inaux;
+ break;
+ case NODE_DEL_ELT:
+ in2 = in1;
+ n1 = inaux+1;
+ n2 = bt_subtrees(bt, in1) - inaux - 1;
+ off2 = inaux+1;
+ break;
+ }
+ i = j = 0;
+ while (j < n1) {
+ nodes[i] = bt_child(bt, in1, j);
+ if (j+1 < n1)
+ elements[i] = bt_element(bt, in1, j);
+ i++, j++;
+ }
+ if (intype == NODE_DEL_ELT) {
+ i--;
+ }
+ j = 0;
+ while (j < n2) {
+ nodes[i] = bt_child(bt, in2, off2+j);
+ if (j+1 < n2)
+ elements[i] = bt_element(bt, in2, off2+j);
+ i++, j++;
+ }
+ switch (intype) {
+ case NODE_AS_IS:
+ elements[n1-1] = inelt;
+ break;
+ case NODE_ADD_ELT:
+ nodes[n1-1] = extra1;
+ nodes[n1] = extra2;
+ elements[n1-1] = inelt;
+ break;
+ case NODE_DEL_ELT:
+ nodes[n1-1] = extra1;
+ break;
+ }
+
+ /*
+ * Now determine how many subtrees go in each output node, and
+ * actually create the nodes to be returned.
+ */
+ if (splitpos != NODE_JOIN) {
+ n1 = splitpos+1, n2 = i - splitpos - 1;
+ if (outelt)
+ *outelt = elements[splitpos];
+ } else {
+ n1 = i, n2 = 0;
+ }
+
+ ret1 = bt_reuse_node(bt, in1, n1);
+ if (intype == NODE_AS_IS && in2) {
+ /* We have a second input node. */
+ if (n2)
+ ret2 = bt_reuse_node(bt, in2, n2);
+ else
+ bt_destroy_node(bt, in2);
+ } else {
+ /* We have no second input node. */
+ if (n2)
+ ret2 = bt_new_node(bt, n2);
+ else
+ ret2 = NULL;
+ }
+
+ if (out1) *out1 = ret1;
+ if (out2) *out2 = ret2;
+
+ for (i = 0; i < n1; i++) {
+ bt_set_child(bt, ret1, i, nodes[i]);
+ if (i+1 < n1)
+ bt_set_element(bt, ret1, i, elements[i]);
+ }
+ if (n2) {
+ if (outelt) *outelt = elements[n1-1];
+ for (i = 0; i < n2; i++) {
+ bt_set_child(bt, ret2, i, nodes[n1+i]);
+ if (i+1 < n2)
+ bt_set_element(bt, ret2, i, elements[n1+i]);
+ }
+ }
+
+ ifree(nodes);
+ ifree(elements);
+}
+
+/*
+ * Fiddly little compare functions for use in special cases of
+ * findrelpos. One always returns +1 (a > b), the other always
+ * returns -1 (a < b).
+ */
+static int bt_cmp_greater(void *state,
+ const bt_element_t a, const bt_element_t b)
+{
+ return +1;
+}
+static int bt_cmp_less(void *state,
+ const bt_element_t a, const bt_element_t b)
+{
+ return -1;
+}
+
+/* ----------------------------------------------------------------------
+ * User-visible administration routines.
+ */
+
+btree *bt_new(cmpfn_t cmp, copyfn_t copy, freefn_t freeelt,
+ int propsize, int propalign, propmakefn_t propmake,
+ propmergefn_t propmerge, void *state, int mindegree)
+{
+ btree *ret;
+
+ ret = new1(btree);
+ ret->mindegree = mindegree;
+ ret->maxdegree = 2*mindegree;
+ ret->depth = 0; /* not even a root right now */
+ ret->root = NODE_ADDR_NULL;
+ ret->cmp = cmp;
+ ret->copy = copy;
+ ret->freeelt = freeelt;
+ ret->propsize = propsize;
+ ret->propalign = propalign;
+ ret->propoffset = sizeof(nodecomponent) * (ret->maxdegree*2 + 2);
+ if (propalign > 0) {
+ ret->propoffset += propalign - 1;
+ ret->propoffset -= ret->propoffset % propalign;
+ }
+ ret->propmake = propmake;
+ ret->propmerge = propmerge;
+ ret->userstate = state;
+
+ return ret;
+}
+
+static void bt_free_node(btree *bt, nodeptr n)
+{
+ int i;
+
+ for (i = 0; i < bt_subtrees(bt, n); i++) {
+ node_addr na;
+ nodeptr n2;
+
+ na = bt_child(bt, n, i);
+ if (!bt_unref_node(bt, na)) {
+ n2 = bt_write_lock_child(bt, n, i);
+ bt_free_node(bt, n2);
+ }
+ }
+
+ if (bt->freeelt) {
+ for (i = 0; i < bt_subtrees(bt, n)-1; i++)
+ bt->freeelt(bt->userstate, bt_element(bt, n, i));
+ }
+
+ bt_destroy_node(bt, n);
+}
+
+void bt_free(btree *bt)
+{
+ nodeptr n;
+
+ if (!bt_unref_node(bt, bt->root)) {
+ n = bt_write_lock_root(bt);
+ bt_free_node(bt, n);
+ }
+
+ sfree(bt);
+}
+
+btree *bt_clone(btree *bt)
+{
+ btree *bt2;
+
+ bt2 = bt_new(bt->cmp, bt->copy, bt->freeelt, bt->propsize, bt->propalign,
+ bt->propmake, bt->propmerge, bt->userstate, bt->mindegree);
+ bt2->depth = bt->depth;
+ bt2->root = bt_ref_node(bt, bt->root);
+ return bt2;
+}
+
+/*
+ * Nice simple function to count the size of a tree.
+ */
+int bt_count(btree *bt)
+{
+ int count;
+ nodeptr n;
+
+ n = bt_read_lock_root(bt);
+ if (n) {
+ count = bt_node_count(bt, n);
+ bt_read_unlock(bt, n);
+ return count;
+ } else {
+ return 0;
+ }
+}
+
+/* ----------------------------------------------------------------------
+ * Actual B-tree algorithms.
+ */
+
+/*
+ * Find an element by numeric index. bt_index_w is the same, but
+ * works with write locks instead of read locks, so it guarantees
+ * to return an element with only one reference to it. (You'd use
+ * this if you were using tree cloning, and wanted to modify the
+ * element once you'd found it.)
+ */
+bt_element_t bt_index(btree *bt, int index)
+{
+ nodeptr n, n2;
+ int child, ends;
+
+ n = bt_read_lock_root(bt);
+
+ if (index < 0 || index >= bt_node_count(bt, n)) {
+ bt_read_unlock(bt, n);
+ return NULL;
+ }
+
+ while (1) {
+ child = bt_lookup_pos(bt, n, &index, &ends);
+ if (ends & ENDS_RIGHT) {
+ bt_element_t ret = bt_element(bt, n, child);
+ bt_read_unlock(bt, n);
+ return ret;
+ }
+ n2 = bt_read_lock_child(bt, n, child);
+ bt_read_unlock(bt, n);
+ n = n2;
+ assert(n != NULL);
+ }
+}
+
+bt_element_t bt_index_w(btree *bt, int index)
+{
+ nodeptr n, n2;
+ int nnodes, child, ends;
+ nodeptr *nodes;
+ bt_element_t ret;
+
+ nodes = inewn(nodeptr, bt->depth+1);
+ nnodes = 0;
+
+ n = bt_write_lock_root(bt);
+
+ if (index < 0 || index >= bt_node_count(bt, n)) {
+ bt_write_unlock(bt, n);
+ return NULL;
+ }
+
+ while (1) {
+ nodes[nnodes++] = n;
+ child = bt_lookup_pos(bt, n, &index, &ends);
+ if (ends & ENDS_RIGHT) {
+ ret = bt_element(bt, n, child);
+ break;
+ }
+ n2 = bt_write_lock_child(bt, n, child);
+ n = n2;
+ assert(n != NULL);
+ }
+
+ while (nnodes-- > 0)
+ bt_write_unlock(bt, nodes[nnodes]);
+
+ return ret;
+}
+
+/*
+ * Search for an element by sorted order.
+ */
+bt_element_t bt_findrelpos(btree *bt, bt_element_t element, cmpfn_t cmp,
+ int relation, int *index)
+{
+ nodeptr n, n2;
+ int child, is_elt;
+ bt_element_t gotit;
+ int pos = 0;
+ int count;
+
+ if (!cmp) cmp = bt->cmp;
+
+ /*
+ * Special case: relation LT/GT and element NULL means get an
+ * extreme element of the tree. We do this by fudging the
+ * compare function so that our NULL element will be considered
+ * infinitely large or infinitely small.
+ */
+ if (element == NULL) {
+ assert(relation == BT_REL_LT || relation == BT_REL_GT);
+ if (relation == BT_REL_LT)
+ cmp = bt_cmp_greater; /* always returns a > b */
+ else
+ cmp = bt_cmp_less; /* always returns a < b */
+ }
+
+ gotit = NULL;
+ n = bt_read_lock_root(bt);
+ if (!n)
+ return NULL;
+ count = bt_node_count(bt, n);
+ while (n) {
+ child = bt_lookup_cmp(bt, n, element, cmp, &is_elt);
+ if (is_elt) {
+ pos += bt_child_startpos(bt, n, child+1) - 1;
+ gotit = bt_element(bt, n, child);
+ bt_read_unlock(bt, n);
+ break;
+ } else {
+ pos += bt_child_startpos(bt, n, child);
+ n2 = bt_read_lock_child(bt, n, child);
+ bt_read_unlock(bt, n);
+ n = n2;
+ }
+ }
+
+ /*
+ * Now all nodes are unlocked, and we are _either_ (a) holding
+ * an element in `gotit' whose index we have in `pos', _or_ (b)
+ * holding nothing in `gotit' but we know the index of the
+ * next-higher element.
+ */
+ if (gotit) {
+ /*
+ * We have the real element. For EQ, LE and GE relations we
+ * can now just return it; otherwise we must return the
+ * next element down or up.
+ */
+ if (relation == BT_REL_LT)
+ gotit = bt_index(bt, --pos);
+ else if (relation == BT_REL_GT)
+ gotit = bt_index(bt, ++pos);
+ } else {
+ /*
+ * We don't have the real element. For EQ relation we now
+ * just give up; for everything else we return the next
+ * element down or up.
+ */
+ if (relation == BT_REL_LT || relation == BT_REL_LE)
+ gotit = bt_index(bt, --pos);
+ else if (relation == BT_REL_GT || relation == BT_REL_GE)
+ gotit = bt_index(bt, pos);
+ }
+
+ if (gotit && index) *index = pos;
+ return gotit;
+}
+bt_element_t bt_findrel(btree *bt, bt_element_t element, cmpfn_t cmp,
+ int relation)
+{
+ return bt_findrelpos(bt, element, cmp, relation, NULL);
+}
+bt_element_t bt_findpos(btree *bt, bt_element_t element, cmpfn_t cmp,
+ int *index)
+{
+ return bt_findrelpos(bt, element, cmp, BT_REL_EQ, index);
+}
+bt_element_t bt_find(btree *bt, bt_element_t element, cmpfn_t cmp)
+{
+ return bt_findrelpos(bt, element, cmp, BT_REL_EQ, NULL);
+}
+
+/*
+ * Find an element by property-based search. Returns the element
+ * (if one is selected - the search can also terminate by
+ * descending to a nonexistent subtree of a leaf node, equivalent
+ * to selecting the _gap_ between two elements); also returns the
+ * index of either the element or the gap in `*index' if `index' is
+ * non-NULL.
+ */
+bt_element_t bt_propfind(btree *bt, searchfn_t search, void *sstate,
+ int *index)
+{
+ nodeptr n, n2;
+ int i, j, count, is_elt;
+ void **props;
+ int *counts;
+ bt_element_t *elts;
+ bt_element_t *e = NULL;
+
+ props = inewn(void *, bt->maxdegree);
+ counts = inewn(int, bt->maxdegree);
+ elts = inewn(bt_element_t, bt->maxdegree);
+
+ n = bt_read_lock_root(bt);
+
+ count = 0;
+
+ while (n) {
+ int ntrees = bt_subtrees(bt, n);
+
+ /*
+ * Prepare the arguments to the search function.
+ */
+ for (i = 0; i < ntrees; i++) {
+ props[i] = bt_child_prop(bt, n, i);
+ counts[i] = bt_child_count(bt, n, i);
+ if (i < ntrees-1)
+ elts[i] = bt_element(bt, n, i);
+ }
+
+ /*
+ * Call the search function.
+ */
+ i = search(bt->userstate, sstate, ntrees,
+ props, counts, elts, &is_elt);
+
+ if (!is_elt) {
+ /*
+ * Descend to subtree i. Update `count' to consider
+ * everything (both subtrees and elements) before that
+ * subtree.
+ */
+ for (j = 0; j < i; j++)
+ count += 1 + bt_child_count(bt, n, j);
+ n2 = bt_read_lock_child(bt, n, i);
+ bt_read_unlock(bt, n);
+ n = n2;
+ } else {
+ /*
+ * Return element i. Update `count' to consider
+ * everything (both subtrees and elements) before that
+ * element.
+ */
+ for (j = 0; j <= i; j++)
+ count += 1 + bt_child_count(bt, n, j);
+ count--; /* don't count element i itself */
+ e = bt_element(bt, n, i);
+ bt_read_unlock(bt, n);
+ break;
+ }
+ }
+
+ ifree(props);
+ ifree(counts);
+ ifree(elts);
+
+ if (index) *index = count;
+ return e;
+}
+
+/*
+ * Replace the element at a numeric index by a new element. Returns
+ * the old element.
+ *
+ * Can also be used when the new element is the _same_ as the old
+ * element, but has changed in some way that will affect user
+ * properties.
+ */
+bt_element_t bt_replace(btree *bt, bt_element_t element, int index)
+{
+ nodeptr n;
+ nodeptr *nodes;
+ bt_element_t ret;
+ int nnodes, child, ends;
+
+ nodes = inewn(nodeptr, bt->depth+1);
+ nnodes = 0;
+
+ n = bt_write_lock_root(bt);
+
+ if (index < 0 || index >= bt_node_count(bt, n)) {
+ bt_write_unlock(bt, n);
+ return NULL;
+ }
+
+ while (1) {
+ nodes[nnodes++] = n;
+ child = bt_lookup_pos(bt, n, &index, &ends);
+ if (ends & ENDS_RIGHT) {
+ ret = bt_element(bt, n, child);
+ bt_set_element(bt, n, child, element);
+ break;
+ }
+ n = bt_write_lock_child(bt, n, child);
+ assert(n != NULL);
+ }
+
+ while (nnodes-- > 0)
+ bt_write_unlock(bt, nodes[nnodes]);
+
+ return ret;
+}
+
+/*
+ * Add at a specific position. As we search down the tree we must
+ * write-lock every node we meet, since otherwise we might fail to
+ * clone nodes that will end up pointing to different things.
+ */
+void bt_addpos(btree *bt, bt_element_t element, int pos)
+{
+ nodeptr n;
+ node_addr left, right, single;
+ nodeptr *nodes;
+ int *childposns;
+ int nnodes, child;
+
+ /*
+ * Since in a reference-counted tree we can't have parent
+ * links, we will have to use O(depth) space to store the list
+ * of nodeptrs we have gone through, so we can un-write-lock
+ * them when we've finished. We also store the subtree index we
+ * descended to at each stage.
+ */
+ nodes = inewn(nodeptr, bt->depth+1);
+ childposns = inewn(int, bt->depth+1);
+ nnodes = 0;
+
+ n = bt_write_lock_root(bt);
+
+ assert(pos >= 0 && pos <= (n ? bt_node_count(bt, n) : 0));
+
+ /*
+ * Scan down the tree, write-locking nodes, until we find the
+ * empty subtree where we want to insert the item.
+ */
+ while (n) {
+ nodes[nnodes] = n;
+ child = bt_lookup_pos(bt, n, &pos, NULL);
+ childposns[nnodes] = child;
+ nnodes++;
+ n = bt_write_lock_child(bt, n, child);
+ }
+
+ left = right = NODE_ADDR_NULL;
+
+ /*
+ * Now nodes[nnodes-1] wants to have subtree index
+ * childposns[nnodes-1] replaced by the node/element/node triple
+ * (left,element,right). Propagate this up the tree until we
+ * can stop.
+ */
+ while (nnodes-- > 0) {
+ n = nodes[nnodes];
+ if (bt_subtrees(bt, n) == bt_max_subtrees(bt)) {
+ nodeptr lptr, rptr;
+ /* Split the node and carry on up. */
+ bt_xform(bt, NODE_ADD_ELT, childposns[nnodes],
+ n, NULL, element, left, right,
+ bt_min_subtrees(bt), &lptr, &rptr, &element);
+ left = bt_write_unlock(bt, lptr);
+ right = bt_write_unlock(bt, rptr);
+ } else {
+ bt_xform(bt, NODE_ADD_ELT, childposns[nnodes],
+ n, NULL, element, left, right,
+ NODE_JOIN, &n, NULL, NULL);
+ single = bt_write_unlock(bt, n);
+ break;
+ }
+ }
+
+ /*
+ * If nnodes < 0, we have just split the root and we need to
+ * build a new root node.
+ */
+ if (nnodes < 0) {
+ bt_new_root(bt, left, right, element);
+ } else {
+ /*
+ * Now nodes[nnodes-1] just wants to have child pointer
+ * child[nnodes-1] replaced by `single', in case the
+ * subtree was moved. Propagate this back up to the root,
+ * unlocking all nodes.
+ */
+ while (nnodes-- > 0) {
+ bt_set_child(bt, nodes[nnodes], childposns[nnodes], single);
+ single = bt_write_unlock(bt, nodes[nnodes]);
+ }
+ }
+
+ ifree(nodes);
+ ifree(childposns);
+}
+
+/*
+ * Add an element in sorted order. This is a wrapper on bt_addpos()
+ * which finds the numeric index to add the item at and then calls
+ * addpos. This isn't an optimal use of time, but it saves space by
+ * avoiding starting to clone multiply-linked nodes until it's
+ * known that the item _can_ be added to the tree (and isn't
+ * duplicated in it already).
+ */
+bt_element_t bt_add(btree *bt, bt_element_t element)
+{
+ nodeptr n, n2;
+ int child, is_elt;
+ int pos = 0;
+
+ n = bt_read_lock_root(bt);
+ while (n) {
+ child = bt_lookup_cmp(bt, n, element, bt->cmp, &is_elt);
+ if (is_elt) {
+ bt_read_unlock(bt, n);
+ return bt_element(bt, n, child); /* element exists already */
+ } else {
+ pos += bt_child_startpos(bt, n, child);
+ n2 = bt_read_lock_child(bt, n, child);
+ bt_read_unlock(bt, n);
+ n = n2;
+ }
+ }
+ bt_addpos(bt, element, pos);
+ return element;
+}
+
+/*
+ * Delete an element given its numeric position. Returns the
+ * element deleted.
+ */
+bt_element_t bt_delpos(btree *bt, int pos)
+{
+ nodeptr n, c, c2, saved_n;
+ nodeptr *nodes;
+ int nnodes, child, nroot, pos2, ends, st, splitpoint, saved_pos;
+ bt_element_t e, ret;
+
+ /*
+ * Just like in bt_add, we store the set of nodeptrs we
+ * write-locked on the way down, so we can unlock them on the
+ * way back up.
+ */
+ nodes = inewn(nodeptr, bt->depth+1);
+ nnodes = 0;
+
+ n = bt_write_lock_root(bt);
+ nroot = TRUE;
+ saved_n = NULL;
+
+ if (!n || pos < 0 || pos >= bt_node_count(bt, n)) {
+ if (n)
+ bt_write_unlock(bt, n);
+ return NULL;
+ }
+
+ while (1) {
+ nodes[nnodes++] = n;
+
+ /*
+ * Find out which subtree to descend to.
+ */
+ pos2 = pos;
+ child = bt_lookup_pos(bt, n, &pos, &ends);
+ c = bt_write_lock_child(bt, n, child);
+ if (c && bt_subtrees(bt, c) == bt_min_subtrees(bt)) {
+ /*
+ * We're trying to descend to a subtree that's of
+ * minimum size. Do something!
+ */
+ if (child > 0) {
+ /*
+ * Either move a subtree from the left sibling, or
+ * merge with it. (Traditionally we would only
+ * merge if we can't move a subtree from _either_
+ * sibling, but this way avoids too many extra
+ * write locks.)
+ */
+ c2 = c;
+ c = bt_write_lock_child(bt, n, child-1);
+ e = bt_element(bt, n, child-1);
+ st = bt_subtrees(bt, c);
+ if (st > bt_min_subtrees(bt))
+ splitpoint = st - 2;
+ else
+ splitpoint = NODE_JOIN;
+ child--;
+ } else {
+ /*
+ * Likewise on the right-hand side.
+ */
+ c2 = bt_write_lock_child(bt, n, child+1);
+ e = bt_element(bt, n, child);
+ st = bt_subtrees(bt, c2);
+ if (st > bt_min_subtrees(bt))
+ splitpoint = bt_min_subtrees(bt);
+ else
+ splitpoint = NODE_JOIN;
+ }
+
+ if (splitpoint == NODE_JOIN) {
+ /*
+ * So if we're merging nodes, go to it...
+ */
+ bt_xform(bt, NODE_AS_IS, 0,
+ c, c2, e, NODE_ADDR_NULL, NODE_ADDR_NULL,
+ NODE_JOIN, &c, NULL, NULL);
+ bt_xform(bt, NODE_DEL_ELT, child,
+ n, NULL, NULL, bt_node_addr(bt, c), NODE_ADDR_NULL,
+ NODE_JOIN, &n, NULL, NULL);
+ if (nroot && bt_subtrees(bt, n) == 1) {
+ /*
+ * Whoops, we just merged the last two children
+ * of the root. Better relocate the root.
+ */
+ bt_shift_root(bt, n, bt_node_addr(bt, c));
+ nnodes--; /* don't leave it in nodes[]! */
+ n = NULL;
+ bt_write_relock(bt, c, TRUE);
+ } else
+ bt_write_unlock(bt, c);
+ } else {
+ /*
+ * Or if we're redistributing subtrees, go to that.
+ */
+ bt_xform(bt, NODE_AS_IS, 0,
+ c, c2, e, NODE_ADDR_NULL, NODE_ADDR_NULL,
+ splitpoint, &c, &c2, &e);
+ bt_set_element(bt, n, child, e);
+ bt_write_unlock(bt, c);
+ bt_write_unlock(bt, c2);
+ }
+
+ if (n) {
+ /* Recompute the counts in n so we can do lookups again. */
+ bt_write_relock(bt, n, TRUE);
+
+ /* Having done the transform, redo the position lookup. */
+ pos = pos2;
+ child = bt_lookup_pos(bt, n, &pos, &ends);
+ c = bt_write_lock_child(bt, n, child);
+ } else {
+ pos = pos2;
+ }
+ }
+
+ /*
+ * Now see if this node contains the element we're
+ * looking for.
+ */
+ if (n && (ends & ENDS_RIGHT)) {
+ /*
+ * It does. Element number `child' is the element we
+ * want to delete. See if this is a leaf node...
+ */
+ if (!bt_is_leaf(bt, n)) {
+ /*
+ * It's not a leaf node. So we save the nodeptr and
+ * element index for later reference, and decrement
+ * `pos' so that we're searching for the element to its
+ * left, which _will_ be in a leaf node.
+ */
+ saved_n = n;
+ saved_pos = child;
+ pos--;
+ } else {
+ /*
+ * We've reached a leaf node. Check to see if an
+ * internal-node position was stored in saved_n and
+ * saved_pos, and move this element there if so.
+ */
+ if (saved_n) {
+ ret = bt_element(bt, saved_n, saved_pos);
+ bt_set_element(bt, saved_n, saved_pos,
+ bt_element(bt, n, child));
+ } else {
+ ret = bt_element(bt, n, child);
+ }
+ /* Then delete it from the leaf node. */
+ bt_xform(bt, NODE_DEL_ELT, child,
+ n, NULL, NULL, NODE_ADDR_NULL, NODE_ADDR_NULL,
+ NODE_JOIN, &n, NULL, NULL);
+ /*
+ * Final special case: if this is the root node and
+ * we've just deleted its last element, we should
+ * destroy it and leave a completely empty tree.
+ */
+ if (nroot && bt_subtrees(bt, n) == 1) {
+ bt_shift_root(bt, n, NODE_ADDR_NULL);
+ nnodes--; /* and take it out of nodes[] */
+ }
+ /* Now we're done */
+ break;
+ }
+ }
+
+ /* Descend to the child and go round again. */
+ n = c;
+ nroot = FALSE;
+ }
+
+ /*
+ * All done. Zip back up the tree un-write-locking nodes.
+ */
+ while (nnodes-- > 0)
+ bt_write_unlock(bt, nodes[nnodes]);
+
+ ifree(nodes);
+
+ return ret;
+}
+
+/*
+ * Delete an element in sorted order.
+ */
+bt_element_t bt_del(btree *bt, bt_element_t element)
+{
+ int index;
+ if (!bt_findrelpos(bt, element, NULL, BT_REL_EQ, &index))
+ return NULL; /* wasn't there */
+ return bt_delpos(bt, index);
+}
+
+/*
+ * Join two trees together, given their respective depths and a
+ * middle element. Puts the resulting tree in the root of `bt'.
+ *
+ * This internal routine assumes that the trees have the same
+ * degree.
+ *
+ * The input nodeptrs are assumed to be write-locked, but none of
+ * their children are yet write-locked.
+ */
+static void bt_join_internal(btree *bt, nodeptr lp, nodeptr rp,
+ bt_element_t sep, int ld, int rd)
+{
+ nodeptr *nodes;
+ int *childposns;
+ int nnodes, nodessize;
+ int lsub, rsub;
+
+ /*
+ * We will need to store parent nodes up to the difference
+ * between ld and rd.
+ */
+ nodessize = (ld < rd ? rd-ld : ld-rd);
+ if (nodessize) { /* we may not need _any_! */
+ nodes = inewn(nodeptr, nodessize);
+ childposns = inewn(int, nodessize);
+ }
+ nnodes = 0;
+
+ if (ld > rd) {
+ bt->root = bt_node_addr(bt, lp);
+ bt->depth = ld;
+ /* If the left tree is taller, search down its right-hand edge. */
+ while (ld > rd) {
+ int child = bt_subtrees(bt, lp) - 1;
+ nodeptr n = bt_write_lock_child(bt, lp, child);
+ nodes[nnodes] = lp;
+ childposns[nnodes] = child;
+ nnodes++;
+ lp = n;
+ ld--;
+ }
+ } else {
+ bt->root = bt_node_addr(bt, rp);
+ bt->depth = rd;
+ /* If the right tree is taller, search down its left-hand edge. */
+ while (rd > ld) {
+ nodeptr n = bt_write_lock_child(bt, rp, 0);
+ nodes[nnodes] = rp;
+ childposns[nnodes] = 0;
+ nnodes++;
+ rp = n;
+ rd--;
+ }
+ }
+
+ /*
+ * So we now want to combine nodes lp and rp into either one or
+ * two plausibly-sized nodes, whichever is feasible. We have a
+ * joining element `sep'.
+ */
+ lsub = (lp ? bt_subtrees(bt, lp) : 0);
+ rsub = (rp ? bt_subtrees(bt, rp) : 0);
+ if (lp && rp && lsub + rsub <= bt_max_subtrees(bt)) {
+ node_addr la;
+ /* Join the nodes into one. */
+ bt_xform(bt, NODE_AS_IS, 0, lp, rp, sep,
+ NODE_ADDR_NULL, NODE_ADDR_NULL,
+ NODE_JOIN, &lp, NULL, NULL);
+ /* Unlock the node. */
+ la = bt_write_unlock(bt, lp);
+ /* Update the child pointer in the next node up. */
+ if (nnodes > 0)
+ bt_set_child(bt, nodes[nnodes-1], childposns[nnodes-1], la);
+ else
+ bt->root = la;
+ } else {
+ node_addr la, ra;
+ if (!lp || !rp) {
+ la = NODE_ADDR_NULL;
+ ra = NODE_ADDR_NULL;
+ } else {
+ int lsize, rsize;
+ /* Re-split the nodes into two plausibly sized ones. */
+ lsize = lsub + rsub;
+ rsize = lsize / 2;
+ lsize -= rsize;
+ bt_xform(bt, NODE_AS_IS, 0, lp, rp, sep,
+ NODE_ADDR_NULL, NODE_ADDR_NULL,
+ lsize-1, &lp, &rp, &sep);
+ /* Unlock the nodes. */
+ la = bt_write_unlock(bt, lp);
+ ra = bt_write_unlock(bt, rp);
+ }
+
+ /*
+ * Now we have to do the addition thing: progress up the
+ * tree replacing a single subtree pointer with the
+ * la/sep/ra assembly, until no more nodes have to split as
+ * a result.
+ */
+ while (nnodes-- > 0) {
+ nodeptr n = nodes[nnodes];
+ if (bt_subtrees(bt, n) == bt_max_subtrees(bt)) {
+ /* Split the node and carry on up. */
+ bt_xform(bt, NODE_ADD_ELT, childposns[nnodes],
+ n, NULL, sep, la, ra,
+ bt_min_subtrees(bt), &lp, &rp, &sep);
+ la = bt_write_unlock(bt, lp);
+ ra = bt_write_unlock(bt, rp);
+ } else {
+ bt_xform(bt, NODE_ADD_ELT, childposns[nnodes],
+ n, NULL, sep, la, ra,
+ NODE_JOIN, &n, NULL, NULL);
+ bt_write_unlock(bt, n);
+ break;
+ }
+ }
+
+ /*
+ * If nnodes < 0, we have just split the root and we need
+ * to build a new root node.
+ */
+ if (nnodes < 0)
+ bt_new_root(bt, la, ra, sep);
+ }
+
+ /*
+ * Now we just need to go back up and unlock any remaining
+ * nodes. Also here we ensure the root points where it should.
+ */
+ while (nnodes-- > 0) {
+ node_addr na;
+ na = bt_write_unlock(bt, nodes[nnodes]);
+ if (nnodes == 0)
+ bt->root = na;
+ }
+
+ if (nodessize) {
+ ifree(nodes);
+ ifree(childposns);
+ }
+}
+
+/*
+ * External interfaces to the join functionality: join and joinr
+ * (differing only in which B-tree structure they leave without any
+ * elements, and which they return the combined tree in).
+ */
+btree *bt_join(btree *bt1, btree *bt2)
+{
+ nodeptr root1, root2;
+ int size2;
+
+ size2 = bt_count(bt2);
+ if (size2 > 0) {
+ bt_element_t sep;
+
+ if (bt1->cmp) {
+ /*
+ * The trees are ordered, so verify the ordering
+ * condition: ensure nothing in bt1 is greater than or
+ * equal to the minimum element in bt2.
+ */
+ sep = bt_index(bt2, 0);
+ sep = bt_findrelpos(bt1, sep, NULL, BT_REL_GE, NULL);
+ if (sep)
+ return NULL;
+ }
+
+ sep = bt_delpos(bt2, 0);
+ root1 = bt_write_lock_root(bt1);
+ root2 = bt_write_lock_root(bt2);
+ bt_join_internal(bt1, root1, root2, sep, bt1->depth, bt2->depth);
+ bt2->root = NODE_ADDR_NULL;
+ bt2->depth = 0;
+ }
+ return bt1;
+}
+
+btree *bt_joinr(btree *bt1, btree *bt2)
+{
+ nodeptr root1, root2;
+ int size1;
+
+ size1 = bt_count(bt1);
+ if (size1 > 0) {
+ bt_element_t sep;
+
+ if (bt2->cmp) {
+ /*
+ * The trees are ordered, so verify the ordering
+ * condition: ensure nothing in bt2 is less than or
+ * equal to the maximum element in bt1.
+ */
+ sep = bt_index(bt1, size1-1);
+ sep = bt_findrelpos(bt2, sep, NULL, BT_REL_LE, NULL);
+ if (sep)
+ return NULL;
+ }
+
+ sep = bt_delpos(bt1, size1-1);
+ root1 = bt_write_lock_root(bt1);
+ root2 = bt_write_lock_root(bt2);
+ bt_join_internal(bt2, root1, root2, sep, bt1->depth, bt2->depth);
+ bt1->root = NODE_ADDR_NULL;
+ bt1->depth = 0;
+ }
+ return bt2;
+}
+
+/*
+ * Perform the healing process after a tree has been split. `rhs'
+ * is set if the cut edge is the one on the right.
+ */
+static void bt_split_heal(btree *bt, int rhs)
+{
+ nodeptr n;
+ nodeptr *nodes;
+ int nnodes;
+
+ nodes = inewn(nodeptr, bt->depth);
+ nnodes = 0;
+
+ n = bt_write_lock_root(bt);
+
+ /*
+ * First dispense with completely trivial cases: a root node
+ * containing only one subtree can be thrown away instantly.
+ */
+ while (n && bt_subtrees(bt, n) == 1) {
+ nodeptr n2 = bt_write_lock_child(bt, n, 0);
+ bt_shift_root(bt, n, bt_node_addr(bt, n2));
+ n = n2;
+ }
+
+ /*
+ * Now we have a plausible root node. Start going down the cut
+ * edge looking for undersized or minimum nodes, and arranging
+ * for them to be above minimum size.
+ */
+ while (n) {
+ int edge, next, elt, size_e, size_n, size_total;
+ nodeptr ne, nn, nl, nr;
+ bt_element_t el;
+
+ nodes[nnodes++] = n;
+
+ if (rhs) {
+ edge = bt_subtrees(bt, n) - 1;
+ next = edge - 1;
+ elt = next;
+ } else {
+ edge = 0;
+ next = 1;
+ elt = edge;
+ }
+
+ ne = bt_write_lock_child(bt, n, edge);
+ if (!ne)
+ break;
+
+ size_e = bt_subtrees(bt, ne);
+
+ if (size_e <= bt_min_subtrees(bt)) {
+ nn = bt_write_lock_child(bt, n, next);
+ el = bt_element(bt, n, elt);
+ size_n = bt_subtrees(bt, nn);
+ if (edge < next)
+ nl = ne, nr = nn;
+ else
+ nl = nn, nr = ne;
+ size_total = size_e + size_n;
+ if (size_e + size_n <= bt_max_subtrees(bt)) {
+ /*
+ * Merge the edge node and its sibling together.
+ */
+ bt_xform(bt, NODE_AS_IS, 0, nl, nr, el,
+ NODE_ADDR_NULL, NODE_ADDR_NULL,
+ NODE_JOIN, &ne, NULL, NULL);
+ bt_xform(bt, NODE_DEL_ELT, elt, n, NULL, NULL,
+ bt_node_addr(bt, ne), NODE_ADDR_NULL,
+ NODE_JOIN, &n, NULL, NULL);
+ /*
+ * It's possible we've just trashed the root of the
+ * tree, again.
+ */
+ if (bt_subtrees(bt, n) == 1) {
+ bt_shift_root(bt, n, bt_node_addr(bt, ne));
+ nnodes--; /* and take it out of nodes[] */
+ }
+ } else {
+ /*
+ * Redistribute subtrees between the edge node and
+ * its sibling.
+ */
+ int split;
+ size_e = (size_total + 1) / 2;
+ assert(size_e > bt_min_subtrees(bt));
+ if (next < edge)
+ split = size_total - size_e - 1;
+ else
+ split = size_e - 1;
+ bt_xform(bt, NODE_AS_IS, 0, nl, nr, el,
+ NODE_ADDR_NULL, NODE_ADDR_NULL,
+ split, &nl, &nr, &el);
+ bt_write_unlock(bt, nn);
+ bt_set_element(bt, n, elt, el);
+ }
+ }
+
+ n = ne;
+ }
+
+ /*
+ * Now we just need to go back up and unlock any remaining
+ * nodes.
+ */
+ while (nnodes-- > 0)
+ bt_write_unlock(bt, nodes[nnodes]);
+
+ ifree(nodes);
+}
+
+/*
+ * Split a tree by numeric position. The new tree returned is the
+ * one on the right; the original tree contains the stuff on the
+ * left.
+ */
+static btree *bt_split_internal(btree *bt1, int index)
+{
+ btree *bt2;
+ nodeptr *lnodes, *rnodes;
+ nodeptr n1, n2, n;
+ int nnodes, child;
+
+ bt2 = bt_new(bt1->cmp, bt1->copy, bt1->freeelt, bt1->propsize,
+ bt1->propalign, bt1->propmake, bt1->propmerge,
+ bt1->userstate, bt1->mindegree);
+ bt2->depth = bt1->depth;
+
+ lnodes = inewn(nodeptr, bt1->depth);
+ rnodes = inewn(nodeptr, bt2->depth);
+ nnodes = 0;
+
+ n1 = bt_write_lock_root(bt1);
+ while (n1) {
+ child = bt_lookup_pos(bt1, n1, &index, NULL);
+ n = bt_write_lock_child(bt1, n1, child);
+ bt_xform(bt1, NODE_ADD_ELT, child, n1, NULL, NULL,
+ bt_node_addr(bt1, n), NODE_ADDR_NULL,
+ child, &n1, &n2, NULL);
+ lnodes[nnodes] = n1;
+ rnodes[nnodes] = n2;
+ if (nnodes > 0)
+ bt_set_child(bt2, rnodes[nnodes-1], 0, bt_node_addr(bt2, n2));
+ else
+ bt2->root = bt_node_addr(bt2, n2);
+ nnodes++;
+ n1 = n;
+ }
+
+ /*
+ * Now we go back up and unlock all the nodes. At this point we
+ * don't mess with user properties, because there's the danger
+ * of a node containing no subtrees _or_ elements and hence us
+ * having to invent a notation for an empty property. We're
+ * going to make a second healing pass in a moment anyway,
+ * which will sort all that out for us.
+ */
+ while (nnodes-- > 0) {
+ bt_write_unlock_internal(bt1, lnodes[nnodes], FALSE);
+ bt_write_unlock_internal(bt2, rnodes[nnodes], FALSE);
+ }
+
+ /*
+ * Then we make a healing pass down each side of the tree.
+ */
+ bt_split_heal(bt1, TRUE);
+ bt_split_heal(bt2, FALSE);
+
+ ifree(lnodes);
+ ifree(rnodes);
+
+ return bt2;
+}
+
+/*
+ * Split a tree at a numeric index.
+ */
+btree *bt_splitpos(btree *bt, int index, int before)
+{
+ btree *ret;
+ node_addr na;
+ int count, nd;
+ nodeptr n;
+
+ n = bt_read_lock_root(bt);
+ count = (n ? bt_node_count(bt, n) : 0);
+ bt_read_unlock(bt, n);
+
+ if (index < 0 || index > count)
+ return NULL;
+
+ ret = bt_split_internal(bt, index);
+ if (before) {
+ na = bt->root;
+ bt->root = ret->root;
+ ret->root = na;
+
+ nd = bt->depth;
+ bt->depth = ret->depth;
+ ret->depth = nd;
+ }
+ return ret;
+}
+
+/*
+ * Split a tree at a position dictated by the sorting order.
+ */
+btree *bt_split(btree *bt, bt_element_t element, cmpfn_t cmp, int rel)
+{
+ int before, index;
+
+ assert(rel != BT_REL_EQ); /* has to be an inequality */
+
+ if (rel == BT_REL_GT || rel == BT_REL_GE) {
+ before = TRUE;
+ rel = (rel == BT_REL_GT ? BT_REL_LE : BT_REL_LT);
+ } else {
+ before = FALSE;
+ }
+ if (!bt_findrelpos(bt, element, cmp, rel, &index))
+ index = -1;
+ return bt_splitpos(bt, index+1, before);
+}
+
+#ifdef TEST
+
+#define TEST_DEGREE 4
+#define BT_COPY bt_clone
+#define MAXTREESIZE 10000
+#define MAXLOCKS 100
+
+int errors;
+
+/*
+ * Error reporting function.
+ */
+void error(char *fmt, ...) {
+ va_list ap;
+ fprintf(stderr, "ERROR: ");
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+ fprintf(stderr, "\n");
+ errors++;
+}
+
+/*
+ * See if a tree has a 2-element root node.
+ */
+static int bt_tworoot(btree *bt)
+{
+ nodeptr n;
+ int i;
+ n = bt_read_lock_root(bt);
+ i = bt_subtrees(bt, n);
+ bt_read_unlock(bt, n);
+ return (i == 2 ? TRUE : FALSE);
+}
+
+/*
+ * Physically copy an entire B-tree. (NB this appears as a test
+ * routine rather than a production one, since reference counting
+ * and bt_clone() provide a better way to do this for real code. If
+ * anyone really needs a genuine physical copy for anything other
+ * than testing reasons, I suppose they could always lift this into
+ * the admin section above.)
+ */
+
+static nodeptr bt_copy_node(btree *bt, nodeptr n)
+{
+ int i, children;
+ nodeptr ret;
+
+ children = bt_subtrees(bt, n);
+ ret = bt_new_node(bt, children);
+
+ for (i = 0; i < children; i++) {
+ nodeptr n2 = bt_read_lock_child(bt, n, i);
+ nodeptr n3;
+ if (n2) {
+ n3 = bt_copy_node(bt, n2);
+ bt_set_child(bt, ret, i, bt_write_unlock(bt, n3));
+ } else {
+ bt_set_child(bt, ret, i, NODE_ADDR_NULL);
+ }
+ bt_read_unlock(bt, n2);
+
+ if (i < children-1) {
+ bt_element_t e = bt_element(bt, n, i);
+ if (bt->copy)
+ e = bt->copy(bt->userstate, e);
+ bt_set_element(bt, ret, i, e);
+ }
+ }
+
+ return ret;
+}
+
+btree *bt_copy(btree *bt)
+{
+ nodeptr n;
+ btree *bt2;
+
+ bt2 = bt_new(bt->cmp, bt->copy, bt->freeelt, bt->propsize, bt->propalign,
+ bt->propmake, bt->propmerge, bt->userstate, bt->mindegree);
+ bt2->depth = bt->depth;
+
+ n = bt_read_lock_root(bt);
+ if (n)
+ bt2->root = bt_write_unlock(bt2, bt_copy_node(bt, n));
+ bt_read_unlock(bt, n);
+
+ return bt2;
+}
+
+/*
+ * This function is intended to be called from gdb when debugging
+ * things.
+ */
+void bt_dump_nodes(btree *bt, ...)
+{
+ int i, children;
+ va_list ap;
+ nodeptr n;
+
+ va_start(ap, bt);
+ while (1) {
+ n = va_arg(ap, nodeptr);
+ if (!n)
+ break;
+ printf("%p [%d]:", n, n[bt->maxdegree*2+1].i);
+ children = bt_subtrees(bt, n);
+ for (i = 0; i < children; i++) {
+ printf(" %p", bt_child(bt, n, i).p);
+ if (i < children-1)
+ printf(" %s", (char *)bt_element(bt, n, i));
+ }
+ printf("\n");
+ }
+ va_end(ap);
+}
+
+/*
+ * Verify a tree against an array. Checks that:
+ *
+ * - every node has a valid number of subtrees
+ * - subtrees are either all present (internal node) or all absent
+ * (leaf)
+ * - elements are all present
+ * - every leaf is at exactly the depth claimed by the tree
+ * - the tree represents the correct list of elements in the
+ * correct order. (This also tests the ordering constraint,
+ * assuming the array is correctly constructed.)
+ */
+
+void verifynode(btree *bt, nodeptr n, bt_element_t *array, int *arraypos,
+ int depth)
+{
+ int subtrees, min, max, i, before, after, count;
+
+ /* Check the subtree count. The root can have as few as 2 subtrees. */
+ subtrees = bt_subtrees(bt, n);
+ max = bt_max_subtrees(bt);
+ min = (depth == 1) ? 2 : bt_min_subtrees(bt);
+ if (subtrees > max)
+ error("node %p has too many subtrees (%d > %d)", n, subtrees, max);
+ if (subtrees < min)
+ error("node %p has too few subtrees (%d < %d)", n, subtrees, min);
+
+ /* Check that subtrees are present or absent as required. */
+ for (i = 0; i < subtrees; i++) {
+ node_addr child = bt_child(bt, n, i);
+ if (depth == bt->depth && child.p != NULL)
+ error("leaf node %p child %d is %p not NULL\n", n, i, child);
+ if (depth != bt->depth && child.p == NULL)
+ error("non-leaf node %p child %d is NULL\n", n, i);
+ }
+
+ /* Check that elements are all present. */
+ for (i = 0; i < subtrees-1; i++) {
+ bt_element_t elt = bt_element(bt, n, i);
+ if (elt == NULL)
+ error("node %p element %d is NULL\n", n, i);
+ }
+
+ before = *arraypos;
+
+ /* Now verify the subtrees, and simultaneously check the ordering. */
+ for (i = 0; i < subtrees; i++) {
+ if (depth < bt->depth) {
+ nodeptr child = bt_read_lock_child(bt, n, i);
+ verifynode(bt, child, array, arraypos, depth+1);
+ bt_read_unlock(bt, child);
+ }
+ if (i < subtrees-1) {
+ bt_element_t elt = bt_element(bt, n, i);
+ if (array[*arraypos] != elt) {
+ error("node %p element %d is \"%s\", but array[%d]=\"%s\"",
+ n, i, elt, *arraypos, array[*arraypos]);
+ }
+ (*arraypos)++;
+ }
+ }
+
+ after = *arraypos;
+
+ /* Check the node count. */
+ count = bt_node_count(bt, n);
+ if (count != after - before)
+ error("node %p count is %d, should be %d", n, count, after - before);
+
+ /*
+ * Check the user properties.
+ */
+ {
+ nodecomponent *prop;
+ int i;
+ int max = 0, total = 0;
+
+ prop = n + bt->maxdegree * 2 + 2;
+
+ for (i = before; i < after; i++) {
+ int c = (unsigned char)*(char *)array[i];
+
+ if (max < c) max = c;
+ total += c;
+ }
+
+ if (prop[0].i != total)
+ error("node %p total prop is %d, should be %d", n,
+ prop[0].i, total);
+ if (prop[1].i != max)
+ error("node %p max prop is %d, should be %d", n,
+ prop[1].i, max);
+ }
+}
+
+void verifytree(btree *bt, bt_element_t *array, int arraylen)
+{
+ nodeptr n;
+ int i = 0;
+ n = bt_read_lock_root(bt);
+ if (n) {
+ verifynode(bt, n, array, &i, 1);
+ bt_read_unlock(bt, n);
+ } else {
+ if (bt->depth != 0) {
+ error("tree has null root but depth is %d not zero", bt->depth);
+ }
+ }
+ if (i != arraylen)
+ error("tree contains %d elements, array contains %d",
+ i, arraylen);
+ testlock(-1, 0, NULL);
+}
+
+int mycmp(void *state, void *av, void *bv) {
+ char const *a = (char const *)av;
+ char const *b = (char const *)bv;
+ return strcmp(a, b);
+}
+
+static void set_invalid_property(void *propv)
+{
+ int *prop = (int *)propv;
+ prop[0] = prop[1] = -1;
+}
+
+void mypropmake(void *state, void *av, void *destv)
+{
+ char const *a = (char const *)av;
+ int *dest = (int *)destv;
+ dest[0] = dest[1] = (unsigned char)*a;
+}
+
+void mypropmerge(void *state, void *s1v, void *s2v, void *destv)
+{
+ int *s1 = (int *)s1v;
+ int *s2 = (int *)s2v;
+ int *dest = (int *)destv;
+ if (!s1v && !s2v) {
+ /* Special `destroy' case. */
+ set_invalid_property(destv);
+ return;
+ }
+ assert(s2[0] >= 0 && s2[1] >= 0);
+ assert(s1 == NULL || (s1[0] >= 0 && s1[1] >= 0));
+ dest[0] = s2[0] + (s1 ? s1[0] : 0);
+ dest[1] = (s1 && s1[1] > s2[1] ? s1[1] : s2[1]);
+}
+
+void array_addpos(bt_element_t *array, int *arraylen, bt_element_t e, int i)
+{
+ bt_element_t e2;
+ int len = *arraylen;
+
+ assert(len < MAXTREESIZE);
+
+ while (i < len) {
+ e2 = array[i];
+ array[i] = e;
+ e = e2;
+ i++;
+ }
+ array[len] = e;
+ *arraylen = len+1;
+}
+
+void array_add(bt_element_t *array, int *arraylen, bt_element_t e)
+{
+ int i;
+ int len = *arraylen;
+
+ for (i = 0; i < len; i++)
+ if (mycmp(NULL, array[i], e) >= 0)
+ break;
+ assert(i == len || mycmp(NULL, array[i], e) != 0);
+ array_addpos(array, arraylen, e, i);
+}
+
+void array_delpos(bt_element_t *array, int *arraylen, int i)
+{
+ int len = *arraylen;
+
+ while (i < len-1) {
+ array[i] = array[i+1];
+ i++;
+ }
+ *arraylen = len-1;
+}
+
+bt_element_t array_del(bt_element_t *array, int *arraylen, bt_element_t e)
+{
+ int i;
+ int len = *arraylen;
+ bt_element_t ret;
+
+ for (i = 0; i < len; i++)
+ if (mycmp(NULL, array[i], e) >= 0)
+ break;
+ if (i < len && mycmp(NULL, array[i], e) == 0) {
+ ret = array[i];
+ array_delpos(array, arraylen, i);
+ } else
+ ret = NULL;
+ return ret;
+}
+
+/* A sample data set and test utility. Designed for pseudo-randomness,
+ * and yet repeatability. */
+
+/*
+ * This random number generator uses the `portable implementation'
+ * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
+ * change it if not.
+ */
+int randomnumber(unsigned *seed) {
+ *seed *= 1103515245;
+ *seed += 12345;
+ return ((*seed) / 65536) % 32768;
+}
+
+#define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
+
+char *strings[] = {
+ "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i",
+ "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E",
+ "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u",
+ "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y",
+ "m", "s", "l", "4",
+};
+
+#define NSTR lenof(strings)
+
+void findtest(btree *tree, bt_element_t *array, int arraylen)
+{
+ static const int rels[] = {
+ BT_REL_EQ, BT_REL_GE, BT_REL_LE, BT_REL_LT, BT_REL_GT
+ };
+ static const char *const relnames[] = {
+ "EQ", "GE", "LE", "LT", "GT"
+ };
+ int i, j, rel, index;
+ char *p, *ret, *realret, *realret2;
+ int lo, hi, mid, c;
+
+ for (i = 0; i < (int)NSTR; i++) {
+ p = strings[i];
+ for (j = 0; j < (int)(sizeof(rels)/sizeof(*rels)); j++) {
+ rel = rels[j];
+
+ lo = 0; hi = arraylen-1;
+ while (lo <= hi) {
+ mid = (lo + hi) / 2;
+ c = strcmp(p, array[mid]);
+ if (c < 0)
+ hi = mid-1;
+ else if (c > 0)
+ lo = mid+1;
+ else
+ break;
+ }
+
+ if (c == 0) {
+ if (rel == BT_REL_LT)
+ ret = (mid > 0 ? array[--mid] : NULL);
+ else if (rel == BT_REL_GT)
+ ret = (mid < arraylen-1 ? array[++mid] : NULL);
+ else
+ ret = array[mid];
+ } else {
+ assert(lo == hi+1);
+ if (rel == BT_REL_LT || rel == BT_REL_LE) {
+ mid = hi;
+ ret = (hi >= 0 ? array[hi] : NULL);
+ } else if (rel == BT_REL_GT || rel == BT_REL_GE) {
+ mid = lo;
+ ret = (lo < arraylen ? array[lo] : NULL);
+ } else
+ ret = NULL;
+ }
+
+ realret = bt_findrelpos(tree, p, NULL, rel, &index);
+ testlock(-1, 0, NULL);
+ if (realret != ret) {
+ error("find(\"%s\",%s) gave %s should be %s",
+ p, relnames[j], realret, ret);
+ }
+ if (realret && index != mid) {
+ error("find(\"%s\",%s) gave %d should be %d",
+ p, relnames[j], index, mid);
+ }
+ if (realret && rel == BT_REL_EQ) {
+ realret2 = bt_index(tree, index);
+ if (realret2 != realret) {
+ error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
+ p, relnames[j], realret, index, index, realret2);
+ }
+ }
+ }
+ }
+
+ realret = bt_findrelpos(tree, NULL, NULL, BT_REL_GT, &index);
+ testlock(-1, 0, NULL);
+ if (arraylen && (realret != array[0] || index != 0)) {
+ error("find(NULL,GT) gave %s(%d) should be %s(0)",
+ realret, index, array[0]);
+ } else if (!arraylen && (realret != NULL)) {
+ error("find(NULL,GT) gave %s(%d) should be NULL",
+ realret, index);
+ }
+
+ realret = bt_findrelpos(tree, NULL, NULL, BT_REL_LT, &index);
+ testlock(-1, 0, NULL);
+ if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
+ error("find(NULL,LT) gave %s(%d) should be %s(0)",
+ realret, index, array[arraylen-1]);
+ } else if (!arraylen && (realret != NULL)) {
+ error("find(NULL,LT) gave %s(%d) should be NULL",
+ realret, index);
+ }
+}
+
+void splittest(btree *tree, bt_element_t *array, int arraylen)
+{
+ int i;
+ btree *tree3, *tree4;
+ for (i = 0; i <= arraylen; i++) {
+ printf("splittest: %d\n", i);
+ tree3 = BT_COPY(tree);
+ testlock(-1, 0, NULL);
+ tree4 = bt_splitpos(tree3, i, 0);
+ testlock(-1, 0, NULL);
+ verifytree(tree3, array, i);
+ verifytree(tree4, array+i, arraylen-i);
+ bt_join(tree3, tree4);
+ testlock(-1, 0, NULL);
+ verifytree(tree4, NULL, 0);
+ bt_free(tree4); /* left empty by join */
+ testlock(-1, 0, NULL);
+ verifytree(tree3, array, arraylen);
+ bt_free(tree3);
+ testlock(-1, 0, NULL);
+ }
+}
+
+/*
+ * Called to track read and write locks on nodes.
+ */
+void testlock(int write, int set, nodeptr n)
+{
+ static nodeptr readlocks[MAXLOCKS], writelocks[MAXLOCKS];
+ static int nreadlocks = 0, nwritelocks = 0;
+
+ int i, rp, wp;
+
+ if (write == -1) {
+ /* Called after an operation to ensure all locks are unlocked. */
+ if (nreadlocks != 0 || nwritelocks != 0)
+ error("at least one left-behind lock exists!");
+ return;
+ }
+
+ /* Locking NULL does nothing. Unlocking it is an error. */
+ if (n == NULL) {
+ if (!set)
+ error("attempting to %s-unlock NULL", write ? "write" : "read");
+ return;
+ }
+
+ assert(nreadlocks < MAXLOCKS && nwritelocks < MAXLOCKS);
+
+ /* First look for the node in both lock lists. */
+ rp = wp = -1;
+ for (i = 0; i < nreadlocks; i++)
+ if (readlocks[i] == n)
+ rp = i;
+ for (i = 0; i < nwritelocks; i++)
+ if (writelocks[i] == n)
+ wp = i;
+
+ /* Now diverge based on what we're supposed to be up to. */
+ if (set) {
+ /* Setting a lock. Should not already be locked in either list. */
+ if (rp != -1 || wp != -1) {
+ error("attempt to %s-lock node %p, already %s-locked",
+ (write ? "write" : "read"), n, (rp==-1 ? "write" : "read"));
+ }
+ if (write)
+ writelocks[nwritelocks++] = n;
+ else
+ readlocks[nreadlocks++] = n;
+ } else {
+ /* Clearing a lock. Should exist in exactly the correct list. */
+ if (write && rp != -1)
+ error("attempt to write-unlock node %p which is read-locked", n);
+ if (!write && wp != -1)
+ error("attempt to read-unlock node %p which is write-locked", n);
+ if (wp != -1) {
+ nwritelocks--;
+ for (i = wp; i < nwritelocks; i++)
+ writelocks[i] = writelocks[i+1];
+ }
+ if (rp != -1) {
+ nreadlocks--;
+ for (i = rp; i < nreadlocks; i++)
+ readlocks[i] = readlocks[i+1];
+ }
+ }
+}
+
+int main(void) {
+ int in[NSTR];
+ int i, j, k;
+ int tworoot, tmplen;
+ unsigned seed = 0;
+ bt_element_t *array;
+ int arraylen;
+ bt_element_t ret, ret2, item;
+ btree *tree, *tree2, *tree3, *tree4;
+
+ setvbuf(stdout, NULL, _IOLBF, 0);
+ setvbuf(stderr, NULL, _IOLBF, 0);
+ errors = 0;
+
+ for (i = 0; i < (int)NSTR; i++) in[i] = 0;
+ array = newn(bt_element_t, MAXTREESIZE);
+ arraylen = 0;
+ tree = bt_new(mycmp, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+
+ verifytree(tree, array, arraylen);
+ for (i = 0; i < 10000; i++) {
+ j = randomnumber(&seed);
+ j %= NSTR;
+ printf("trial: %d\n", i);
+ if (in[j]) {
+ printf("deleting %s (%d)\n", strings[j], j);
+ ret2 = array_del(array, &arraylen, strings[j]);
+ ret = bt_del(tree, strings[j]);
+ testlock(-1, 0, NULL);
+ assert((bt_element_t)strings[j] == ret && ret == ret2);
+ verifytree(tree, array, arraylen);
+ in[j] = 0;
+ } else {
+ printf("adding %s (%d)\n", strings[j], j);
+ array_add(array, &arraylen, strings[j]);
+ ret = bt_add(tree, strings[j]);
+ testlock(-1, 0, NULL);
+ assert(strings[j] == ret);
+ verifytree(tree, array, arraylen);
+ in[j] = 1;
+ }
+ /* disptree(tree); */
+ findtest(tree, array, arraylen);
+ }
+
+ while (arraylen > 0) {
+ j = randomnumber(&seed);
+ j %= arraylen;
+ item = array[j];
+ ret2 = array_del(array, &arraylen, item);
+ ret = bt_del(tree, item);
+ testlock(-1, 0, NULL);
+ assert(ret2 == ret);
+ verifytree(tree, array, arraylen);
+ }
+
+ bt_free(tree);
+ testlock(-1, 0, NULL);
+
+ /*
+ * Now try an unsorted tree. We don't really need to test
+ * delpos because we know del is based on it, so it's already
+ * been tested in the above sorted-tree code; but for
+ * completeness we'll use it to tear down our unsorted tree
+ * once we've built it.
+ */
+ tree = bt_new(NULL, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+ verifytree(tree, array, arraylen);
+ for (i = 0; i < 1000; i++) {
+ printf("trial: %d\n", i);
+ j = randomnumber(&seed);
+ j %= NSTR;
+ k = randomnumber(&seed);
+ k %= bt_count(tree)+1;
+ testlock(-1, 0, NULL);
+ printf("adding string %s at index %d\n", strings[j], k);
+ array_addpos(array, &arraylen, strings[j], k);
+ bt_addpos(tree, strings[j], k);
+ testlock(-1, 0, NULL);
+ verifytree(tree, array, arraylen);
+ }
+
+ /*
+ * While we have this tree in its full form, we'll take a copy
+ * of it to use in split and join testing.
+ */
+ tree2 = BT_COPY(tree);
+ testlock(-1, 0, NULL);
+ verifytree(tree2, array, arraylen);/* check the copy is accurate */
+ /*
+ * Split tests. Split the tree at every possible point and
+ * check the resulting subtrees.
+ */
+ tworoot = bt_tworoot(tree2); /* see if it has a 2-root */
+ testlock(-1, 0, NULL);
+ splittest(tree2, array, arraylen);
+ /*
+ * Now do the split test again, but on a tree that has a 2-root
+ * (if the previous one didn't) or doesn't (if the previous one
+ * did).
+ */
+ tmplen = arraylen;
+ while (bt_tworoot(tree2) == tworoot) {
+ bt_delpos(tree2, --tmplen);
+ testlock(-1, 0, NULL);
+ }
+ printf("now trying splits on second tree\n");
+ splittest(tree2, array, tmplen);
+ bt_free(tree2);
+ testlock(-1, 0, NULL);
+
+ /*
+ * Back to the main testing of uncounted trees.
+ */
+ while (bt_count(tree) > 0) {
+ printf("cleanup: tree size %d\n", bt_count(tree));
+ j = randomnumber(&seed);
+ j %= bt_count(tree);
+ printf("deleting string %s from index %d\n", (char *)array[j], j);
+ ret = bt_delpos(tree, j);
+ testlock(-1, 0, NULL);
+ assert((bt_element_t)array[j] == ret);
+ array_delpos(array, &arraylen, j);
+ verifytree(tree, array, arraylen);
+ }
+ bt_free(tree);
+ testlock(-1, 0, NULL);
+
+ /*
+ * Finally, do some testing on split/join on _sorted_ trees. At
+ * the same time, we'll be testing split on very small trees.
+ */
+ tree = bt_new(mycmp, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+ arraylen = 0;
+ for (i = 0; i < 16; i++) {
+ array_add(array, &arraylen, strings[i]);
+ ret = bt_add(tree, strings[i]);
+ testlock(-1, 0, NULL);
+ assert(strings[i] == ret);
+ verifytree(tree, array, arraylen);
+ tree2 = BT_COPY(tree);
+ splittest(tree2, array, arraylen);
+ testlock(-1, 0, NULL);
+ bt_free(tree2);
+ testlock(-1, 0, NULL);
+ }
+ bt_free(tree);
+ testlock(-1, 0, NULL);
+
+ /*
+ * Test silly cases of join: join(emptytree, emptytree), and
+ * also ensure join correctly spots when sorted trees fail the
+ * ordering constraint.
+ */
+ tree = bt_new(mycmp, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+ tree2 = bt_new(mycmp, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+ tree3 = bt_new(mycmp, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+ tree4 = bt_new(mycmp, NULL, NULL, 2*sizeof(int), alignof(int),
+ mypropmake, mypropmerge, NULL, TEST_DEGREE);
+ assert(mycmp(NULL, strings[0], strings[1]) < 0); /* just in case :-) */
+ bt_add(tree2, strings[1]);
+ testlock(-1, 0, NULL);
+ bt_add(tree4, strings[0]);
+ testlock(-1, 0, NULL);
+ array[0] = strings[0];
+ array[1] = strings[1];
+ verifytree(tree, array, 0);
+ verifytree(tree2, array+1, 1);
+ verifytree(tree3, array, 0);
+ verifytree(tree4, array, 1);
+
+ /*
+ * So:
+ * - join(tree,tree3) should leave both tree and tree3 unchanged.
+ * - joinr(tree,tree2) should leave both tree and tree2 unchanged.
+ * - join(tree4,tree3) should leave both tree3 and tree4 unchanged.
+ * - join(tree, tree2) should move the element from tree2 to tree.
+ * - joinr(tree4, tree3) should move the element from tree4 to tree3.
+ * - join(tree,tree3) should return NULL and leave both unchanged.
+ * - join(tree3,tree) should work and create a bigger tree in tree3.
+ */
+ assert(tree == bt_join(tree, tree3));
+ testlock(-1, 0, NULL);
+ verifytree(tree, array, 0);
+ verifytree(tree3, array, 0);
+ assert(tree2 == bt_joinr(tree, tree2));
+ testlock(-1, 0, NULL);
+ verifytree(tree, array, 0);
+ verifytree(tree2, array+1, 1);
+ assert(tree4 == bt_join(tree4, tree3));
+ testlock(-1, 0, NULL);
+ verifytree(tree3, array, 0);
+ verifytree(tree4, array, 1);
+ assert(tree == bt_join(tree, tree2));
+ testlock(-1, 0, NULL);
+ verifytree(tree, array+1, 1);
+ verifytree(tree2, array, 0);
+ assert(tree3 == bt_joinr(tree4, tree3));
+ testlock(-1, 0, NULL);
+ verifytree(tree3, array, 1);
+ verifytree(tree4, array, 0);
+ assert(NULL == bt_join(tree, tree3));
+ testlock(-1, 0, NULL);
+ verifytree(tree, array+1, 1);
+ verifytree(tree3, array, 1);
+ assert(tree3 == bt_join(tree3, tree));
+ testlock(-1, 0, NULL);
+ verifytree(tree3, array, 2);
+ verifytree(tree, array, 0);
+
+ bt_free(tree);
+ testlock(-1, 0, NULL);
+ bt_free(tree2);
+ testlock(-1, 0, NULL);
+ bt_free(tree3);
+ testlock(-1, 0, NULL);
+ bt_free(tree4);
+ testlock(-1, 0, NULL);
+
+ sfree(array);
+
+ if (errors)
+ fprintf(stderr, "%d errors!\n", errors);
+ return (errors != 0 ? 1 : 0);
+}
+
+#endif
--- /dev/null
+/*
+ * Flexible B-tree implementation. Supports reference counting for
+ * copy-on-write, user-defined node properties, and variable
+ * degree.
+ *
+ * This file is copyright 2001,2004 Simon Tatham.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+ * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#ifndef BTREE_H
+#define BTREE_H
+
+#include <stddef.h> /* for offsetof */
+
+#ifndef alignof
+#define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
+#endif
+
+typedef struct btree btree;
+typedef void *bt_element_t;
+
+typedef int (*cmpfn_t)(void *state, bt_element_t, bt_element_t);
+typedef bt_element_t (*copyfn_t)(void *state, bt_element_t);
+typedef void (*freefn_t)(void *state, bt_element_t);
+typedef void (*propmakefn_t)(void *state, bt_element_t, void *dest);
+/* s1 may be NULL (indicating copy s2 into dest). s2 is never NULL. */
+typedef void (*propmergefn_t)(void *state, void *s1, void *s2, void *dest);
+typedef int (*searchfn_t)(void *tstate, void *sstate, int ntrees,
+ void **props, int *counts,
+ bt_element_t *elts, int *is_elt);
+
+enum {
+ BT_REL_EQ, BT_REL_LT, BT_REL_LE, BT_REL_GT, BT_REL_GE
+};
+
+btree *bt_new(cmpfn_t cmp, copyfn_t copy, freefn_t freeelt,
+ int propsize, int propalign, propmakefn_t propmake,
+ propmergefn_t propmerge, void *state, int mindegree);
+void bt_free(btree *bt);
+btree *bt_clone(btree *bt);
+int bt_count(btree *bt);
+bt_element_t bt_index(btree *bt, int index);
+bt_element_t bt_index_w(btree *bt, int index);
+bt_element_t bt_findrelpos(btree *bt, bt_element_t element, cmpfn_t cmp,
+ int relation, int *index);
+bt_element_t bt_findrel(btree *bt, bt_element_t element, cmpfn_t cmp,
+ int relation);
+bt_element_t bt_findpos(btree *bt, bt_element_t element, cmpfn_t cmp,
+ int *index);
+bt_element_t bt_find(btree *bt, bt_element_t element, cmpfn_t cmp);
+bt_element_t bt_propfind(btree *bt, searchfn_t search, void *sstate,
+ int *index);
+bt_element_t bt_replace(btree *bt, bt_element_t element, int index);
+void bt_addpos(btree *bt, bt_element_t element, int pos);
+bt_element_t bt_add(btree *bt, bt_element_t element);
+bt_element_t bt_delpos(btree *bt, int pos);
+bt_element_t bt_del(btree *bt, bt_element_t element);
+btree *bt_join(btree *bt1, btree *bt2);
+btree *bt_joinr(btree *bt1, btree *bt2);
+btree *bt_splitpos(btree *bt, int index, int before);
+btree *bt_split(btree *bt, bt_element_t element, cmpfn_t cmp, int rel);
+
+#endif /* BTREE_H */
--- /dev/null
+/*
+ * tree234.c: reasonably generic counted 2-3-4 tree routines.
+ *
+ * This file is copyright 1999-2001 Simon Tatham.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+ * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "tree234.h"
+
+#define smalloc malloc
+#define sfree free
+
+#define mknew(typ) ( (typ *) smalloc (sizeof (typ)) )
+
+#ifdef TEST
+#define LOG(x) (printf x)
+#else
+#define LOG(x)
+#endif
+
+typedef struct node234_Tag node234;
+
+struct tree234_Tag {
+ node234 *root;
+ cmpfn234 cmp;
+};
+
+struct node234_Tag {
+ node234 *parent;
+ node234 *kids[4];
+ int counts[4];
+ void *elems[3];
+};
+
+/*
+ * Create a 2-3-4 tree.
+ */
+tree234 *newtree234(cmpfn234 cmp) {
+ tree234 *ret = mknew(tree234);
+ LOG(("created tree %p\n", ret));
+ ret->root = NULL;
+ ret->cmp = cmp;
+ return ret;
+}
+
+/*
+ * Free a 2-3-4 tree (not including freeing the elements).
+ */
+static void freenode234(node234 *n) {
+ if (!n)
+ return;
+ freenode234(n->kids[0]);
+ freenode234(n->kids[1]);
+ freenode234(n->kids[2]);
+ freenode234(n->kids[3]);
+ sfree(n);
+}
+void freetree234(tree234 *t) {
+ freenode234(t->root);
+ sfree(t);
+}
+
+/*
+ * Internal function to count a node.
+ */
+static int countnode234(node234 *n) {
+ int count = 0;
+ int i;
+ if (!n)
+ return 0;
+ for (i = 0; i < 4; i++)
+ count += n->counts[i];
+ for (i = 0; i < 3; i++)
+ if (n->elems[i])
+ count++;
+ return count;
+}
+
+/*
+ * Count the elements in a tree.
+ */
+int count234(tree234 *t) {
+ if (t->root)
+ return countnode234(t->root);
+ else
+ return 0;
+}
+
+/*
+ * Propagate a node overflow up a tree until it stops. Returns 0 or
+ * 1, depending on whether the root had to be split or not.
+ */
+static int add234_insert(node234 *left, void *e, node234 *right,
+ node234 **root, node234 *n, int ki) {
+ int lcount, rcount;
+ /*
+ * We need to insert the new left/element/right set in n at
+ * child position ki.
+ */
+ lcount = countnode234(left);
+ rcount = countnode234(right);
+ while (n) {
+ LOG((" at %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" need to insert %p/%d \"%s\" %p/%d at position %d\n",
+ left, lcount, e, right, rcount, ki));
+ if (n->elems[1] == NULL) {
+ /*
+ * Insert in a 2-node; simple.
+ */
+ if (ki == 0) {
+ LOG((" inserting on left of 2-node\n"));
+ n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
+ n->elems[1] = n->elems[0];
+ n->kids[1] = right; n->counts[1] = rcount;
+ n->elems[0] = e;
+ n->kids[0] = left; n->counts[0] = lcount;
+ } else { /* ki == 1 */
+ LOG((" inserting on right of 2-node\n"));
+ n->kids[2] = right; n->counts[2] = rcount;
+ n->elems[1] = e;
+ n->kids[1] = left; n->counts[1] = lcount;
+ }
+ if (n->kids[0]) n->kids[0]->parent = n;
+ if (n->kids[1]) n->kids[1]->parent = n;
+ if (n->kids[2]) n->kids[2]->parent = n;
+ LOG((" done\n"));
+ break;
+ } else if (n->elems[2] == NULL) {
+ /*
+ * Insert in a 3-node; simple.
+ */
+ if (ki == 0) {
+ LOG((" inserting on left of 3-node\n"));
+ n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
+ n->elems[2] = n->elems[1];
+ n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
+ n->elems[1] = n->elems[0];
+ n->kids[1] = right; n->counts[1] = rcount;
+ n->elems[0] = e;
+ n->kids[0] = left; n->counts[0] = lcount;
+ } else if (ki == 1) {
+ LOG((" inserting in middle of 3-node\n"));
+ n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
+ n->elems[2] = n->elems[1];
+ n->kids[2] = right; n->counts[2] = rcount;
+ n->elems[1] = e;
+ n->kids[1] = left; n->counts[1] = lcount;
+ } else { /* ki == 2 */
+ LOG((" inserting on right of 3-node\n"));
+ n->kids[3] = right; n->counts[3] = rcount;
+ n->elems[2] = e;
+ n->kids[2] = left; n->counts[2] = lcount;
+ }
+ if (n->kids[0]) n->kids[0]->parent = n;
+ if (n->kids[1]) n->kids[1]->parent = n;
+ if (n->kids[2]) n->kids[2]->parent = n;
+ if (n->kids[3]) n->kids[3]->parent = n;
+ LOG((" done\n"));
+ break;
+ } else {
+ node234 *m = mknew(node234);
+ m->parent = n->parent;
+ LOG((" splitting a 4-node; created new node %p\n", m));
+ /*
+ * Insert in a 4-node; split into a 2-node and a
+ * 3-node, and move focus up a level.
+ *
+ * I don't think it matters which way round we put the
+ * 2 and the 3. For simplicity, we'll put the 3 first
+ * always.
+ */
+ if (ki == 0) {
+ m->kids[0] = left; m->counts[0] = lcount;
+ m->elems[0] = e;
+ m->kids[1] = right; m->counts[1] = rcount;
+ m->elems[1] = n->elems[0];
+ m->kids[2] = n->kids[1]; m->counts[2] = n->counts[1];
+ e = n->elems[1];
+ n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
+ n->elems[0] = n->elems[2];
+ n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
+ } else if (ki == 1) {
+ m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
+ m->elems[0] = n->elems[0];
+ m->kids[1] = left; m->counts[1] = lcount;
+ m->elems[1] = e;
+ m->kids[2] = right; m->counts[2] = rcount;
+ e = n->elems[1];
+ n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
+ n->elems[0] = n->elems[2];
+ n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
+ } else if (ki == 2) {
+ m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
+ m->elems[0] = n->elems[0];
+ m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
+ m->elems[1] = n->elems[1];
+ m->kids[2] = left; m->counts[2] = lcount;
+ /* e = e; */
+ n->kids[0] = right; n->counts[0] = rcount;
+ n->elems[0] = n->elems[2];
+ n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
+ } else { /* ki == 3 */
+ m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
+ m->elems[0] = n->elems[0];
+ m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
+ m->elems[1] = n->elems[1];
+ m->kids[2] = n->kids[2]; m->counts[2] = n->counts[2];
+ n->kids[0] = left; n->counts[0] = lcount;
+ n->elems[0] = e;
+ n->kids[1] = right; n->counts[1] = rcount;
+ e = n->elems[2];
+ }
+ m->kids[3] = n->kids[3] = n->kids[2] = NULL;
+ m->counts[3] = n->counts[3] = n->counts[2] = 0;
+ m->elems[2] = n->elems[2] = n->elems[1] = NULL;
+ if (m->kids[0]) m->kids[0]->parent = m;
+ if (m->kids[1]) m->kids[1]->parent = m;
+ if (m->kids[2]) m->kids[2]->parent = m;
+ if (n->kids[0]) n->kids[0]->parent = n;
+ if (n->kids[1]) n->kids[1]->parent = n;
+ LOG((" left (%p): %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", m,
+ m->kids[0], m->counts[0], m->elems[0],
+ m->kids[1], m->counts[1], m->elems[1],
+ m->kids[2], m->counts[2]));
+ LOG((" right (%p): %p/%d \"%s\" %p/%d\n", n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1]));
+ left = m; lcount = countnode234(left);
+ right = n; rcount = countnode234(right);
+ }
+ if (n->parent)
+ ki = (n->parent->kids[0] == n ? 0 :
+ n->parent->kids[1] == n ? 1 :
+ n->parent->kids[2] == n ? 2 : 3);
+ n = n->parent;
+ }
+
+ /*
+ * If we've come out of here by `break', n will still be
+ * non-NULL and all we need to do is go back up the tree
+ * updating counts. If we've come here because n is NULL, we
+ * need to create a new root for the tree because the old one
+ * has just split into two. */
+ if (n) {
+ while (n->parent) {
+ int count = countnode234(n);
+ int childnum;
+ childnum = (n->parent->kids[0] == n ? 0 :
+ n->parent->kids[1] == n ? 1 :
+ n->parent->kids[2] == n ? 2 : 3);
+ n->parent->counts[childnum] = count;
+ n = n->parent;
+ }
+ return 0; /* root unchanged */
+ } else {
+ LOG((" root is overloaded, split into two\n"));
+ (*root) = mknew(node234);
+ (*root)->kids[0] = left; (*root)->counts[0] = lcount;
+ (*root)->elems[0] = e;
+ (*root)->kids[1] = right; (*root)->counts[1] = rcount;
+ (*root)->elems[1] = NULL;
+ (*root)->kids[2] = NULL; (*root)->counts[2] = 0;
+ (*root)->elems[2] = NULL;
+ (*root)->kids[3] = NULL; (*root)->counts[3] = 0;
+ (*root)->parent = NULL;
+ if ((*root)->kids[0]) (*root)->kids[0]->parent = (*root);
+ if ((*root)->kids[1]) (*root)->kids[1]->parent = (*root);
+ LOG((" new root is %p/%d \"%s\" %p/%d\n",
+ (*root)->kids[0], (*root)->counts[0],
+ (*root)->elems[0],
+ (*root)->kids[1], (*root)->counts[1]));
+ return 1; /* root moved */
+ }
+}
+
+/*
+ * Add an element e to a 2-3-4 tree t. Returns e on success, or if
+ * an existing element compares equal, returns that.
+ */
+static void *add234_internal(tree234 *t, void *e, int index) {
+ node234 *n;
+ int ki;
+ void *orig_e = e;
+ int c;
+
+ LOG(("adding element \"%s\" to tree %p\n", e, t));
+ if (t->root == NULL) {
+ t->root = mknew(node234);
+ t->root->elems[1] = t->root->elems[2] = NULL;
+ t->root->kids[0] = t->root->kids[1] = NULL;
+ t->root->kids[2] = t->root->kids[3] = NULL;
+ t->root->counts[0] = t->root->counts[1] = 0;
+ t->root->counts[2] = t->root->counts[3] = 0;
+ t->root->parent = NULL;
+ t->root->elems[0] = e;
+ LOG((" created root %p\n", t->root));
+ return orig_e;
+ }
+
+ n = t->root;
+ while (n) {
+ LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ if (index >= 0) {
+ if (!n->kids[0]) {
+ /*
+ * Leaf node. We want to insert at kid position
+ * equal to the index:
+ *
+ * 0 A 1 B 2 C 3
+ */
+ ki = index;
+ } else {
+ /*
+ * Internal node. We always descend through it (add
+ * always starts at the bottom, never in the
+ * middle).
+ */
+ if (index <= n->counts[0]) {
+ ki = 0;
+ } else if (index -= n->counts[0] + 1, index <= n->counts[1]) {
+ ki = 1;
+ } else if (index -= n->counts[1] + 1, index <= n->counts[2]) {
+ ki = 2;
+ } else if (index -= n->counts[2] + 1, index <= n->counts[3]) {
+ ki = 3;
+ } else
+ return NULL; /* error: index out of range */
+ }
+ } else {
+ if ((c = t->cmp(e, n->elems[0])) < 0)
+ ki = 0;
+ else if (c == 0)
+ return n->elems[0]; /* already exists */
+ else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
+ ki = 1;
+ else if (c == 0)
+ return n->elems[1]; /* already exists */
+ else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
+ ki = 2;
+ else if (c == 0)
+ return n->elems[2]; /* already exists */
+ else
+ ki = 3;
+ }
+ LOG((" moving to child %d (%p)\n", ki, n->kids[ki]));
+ if (!n->kids[ki])
+ break;
+ n = n->kids[ki];
+ }
+
+ add234_insert(NULL, e, NULL, &t->root, n, ki);
+
+ return orig_e;
+}
+
+void *add234(tree234 *t, void *e) {
+ if (!t->cmp) /* tree is unsorted */
+ return NULL;
+
+ return add234_internal(t, e, -1);
+}
+void *addpos234(tree234 *t, void *e, int index) {
+ if (index < 0 || /* index out of range */
+ t->cmp) /* tree is sorted */
+ return NULL; /* return failure */
+
+ return add234_internal(t, e, index); /* this checks the upper bound */
+}
+
+/*
+ * Look up the element at a given numeric index in a 2-3-4 tree.
+ * Returns NULL if the index is out of range.
+ */
+void *index234(tree234 *t, int index) {
+ node234 *n;
+
+ if (!t->root)
+ return NULL; /* tree is empty */
+
+ if (index < 0 || index >= countnode234(t->root))
+ return NULL; /* out of range */
+
+ n = t->root;
+
+ while (n) {
+ if (index < n->counts[0])
+ n = n->kids[0];
+ else if (index -= n->counts[0] + 1, index < 0)
+ return n->elems[0];
+ else if (index < n->counts[1])
+ n = n->kids[1];
+ else if (index -= n->counts[1] + 1, index < 0)
+ return n->elems[1];
+ else if (index < n->counts[2])
+ n = n->kids[2];
+ else if (index -= n->counts[2] + 1, index < 0)
+ return n->elems[2];
+ else
+ n = n->kids[3];
+ }
+
+ /* We shouldn't ever get here. I wonder how we did. */
+ return NULL;
+}
+
+/*
+ * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
+ * found. e is always passed as the first argument to cmp, so cmp
+ * can be an asymmetric function if desired. cmp can also be passed
+ * as NULL, in which case the compare function from the tree proper
+ * will be used.
+ */
+void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp,
+ int relation, int *index) {
+ node234 *n;
+ void *ret;
+ int c;
+ int idx, ecount, kcount, cmpret;
+
+ if (t->root == NULL)
+ return NULL;
+
+ if (cmp == NULL)
+ cmp = t->cmp;
+
+ n = t->root;
+ /*
+ * Attempt to find the element itself.
+ */
+ idx = 0;
+ ecount = -1;
+ /*
+ * Prepare a fake `cmp' result if e is NULL.
+ */
+ cmpret = 0;
+ if (e == NULL) {
+ assert(relation == REL234_LT || relation == REL234_GT);
+ if (relation == REL234_LT)
+ cmpret = +1; /* e is a max: always greater */
+ else if (relation == REL234_GT)
+ cmpret = -1; /* e is a min: always smaller */
+ }
+ while (1) {
+ for (kcount = 0; kcount < 4; kcount++) {
+ if (kcount >= 3 || n->elems[kcount] == NULL ||
+ (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
+ break;
+ }
+ if (n->kids[kcount]) idx += n->counts[kcount];
+ if (c == 0) {
+ ecount = kcount;
+ break;
+ }
+ idx++;
+ }
+ if (ecount >= 0)
+ break;
+ if (n->kids[kcount])
+ n = n->kids[kcount];
+ else
+ break;
+ }
+
+ if (ecount >= 0) {
+ /*
+ * We have found the element we're looking for. It's
+ * n->elems[ecount], at tree index idx. If our search
+ * relation is EQ, LE or GE we can now go home.
+ */
+ if (relation != REL234_LT && relation != REL234_GT) {
+ if (index) *index = idx;
+ return n->elems[ecount];
+ }
+
+ /*
+ * Otherwise, we'll do an indexed lookup for the previous
+ * or next element. (It would be perfectly possible to
+ * implement these search types in a non-counted tree by
+ * going back up from where we are, but far more fiddly.)
+ */
+ if (relation == REL234_LT)
+ idx--;
+ else
+ idx++;
+ } else {
+ /*
+ * We've found our way to the bottom of the tree and we
+ * know where we would insert this node if we wanted to:
+ * we'd put it in in place of the (empty) subtree
+ * n->kids[kcount], and it would have index idx
+ *
+ * But the actual element isn't there. So if our search
+ * relation is EQ, we're doomed.
+ */
+ if (relation == REL234_EQ)
+ return NULL;
+
+ /*
+ * Otherwise, we must do an index lookup for index idx-1
+ * (if we're going left - LE or LT) or index idx (if we're
+ * going right - GE or GT).
+ */
+ if (relation == REL234_LT || relation == REL234_LE) {
+ idx--;
+ }
+ }
+
+ /*
+ * We know the index of the element we want; just call index234
+ * to do the rest. This will return NULL if the index is out of
+ * bounds, which is exactly what we want.
+ */
+ ret = index234(t, idx);
+ if (ret && index) *index = idx;
+ return ret;
+}
+void *find234(tree234 *t, void *e, cmpfn234 cmp) {
+ return findrelpos234(t, e, cmp, REL234_EQ, NULL);
+}
+void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) {
+ return findrelpos234(t, e, cmp, relation, NULL);
+}
+void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) {
+ return findrelpos234(t, e, cmp, REL234_EQ, index);
+}
+
+/*
+ * Tree transformation used in delete and split: move a subtree
+ * right, from child ki of a node to the next child. Update k and
+ * index so that they still point to the same place in the
+ * transformed tree. Assumes the destination child is not full, and
+ * that the source child does have a subtree to spare. Can cope if
+ * the destination child is undersized.
+ *
+ * . C . . B .
+ * / \ -> / \
+ * [more] a A b B c d D e [more] a A b c C d D e
+ *
+ * . C . . B .
+ * / \ -> / \
+ * [more] a A b B c d [more] a A b c C d
+ */
+static void trans234_subtree_right(node234 *n, int ki, int *k, int *index) {
+ node234 *src, *dest;
+ int i, srclen, adjust;
+
+ src = n->kids[ki];
+ dest = n->kids[ki+1];
+
+ LOG((" trans234_subtree_right(%p, %d):\n", n, ki));
+ LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ src,
+ src->kids[0], src->counts[0], src->elems[0],
+ src->kids[1], src->counts[1], src->elems[1],
+ src->kids[2], src->counts[2], src->elems[2],
+ src->kids[3], src->counts[3]));
+ LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ dest,
+ dest->kids[0], dest->counts[0], dest->elems[0],
+ dest->kids[1], dest->counts[1], dest->elems[1],
+ dest->kids[2], dest->counts[2], dest->elems[2],
+ dest->kids[3], dest->counts[3]));
+ /*
+ * Move over the rest of the destination node to make space.
+ */
+ dest->kids[3] = dest->kids[2]; dest->counts[3] = dest->counts[2];
+ dest->elems[2] = dest->elems[1];
+ dest->kids[2] = dest->kids[1]; dest->counts[2] = dest->counts[1];
+ dest->elems[1] = dest->elems[0];
+ dest->kids[1] = dest->kids[0]; dest->counts[1] = dest->counts[0];
+
+ /* which element to move over */
+ i = (src->elems[2] ? 2 : src->elems[1] ? 1 : 0);
+
+ dest->elems[0] = n->elems[ki];
+ n->elems[ki] = src->elems[i];
+ src->elems[i] = NULL;
+
+ dest->kids[0] = src->kids[i+1]; dest->counts[0] = src->counts[i+1];
+ src->kids[i+1] = NULL; src->counts[i+1] = 0;
+
+ if (dest->kids[0]) dest->kids[0]->parent = dest;
+
+ adjust = dest->counts[0] + 1;
+
+ n->counts[ki] -= adjust;
+ n->counts[ki+1] += adjust;
+
+ srclen = n->counts[ki];
+
+ if (k) {
+ LOG((" before: k,index = %d,%d\n", (*k), (*index)));
+ if ((*k) == ki && (*index) > srclen) {
+ (*index) -= srclen + 1;
+ (*k)++;
+ } else if ((*k) == ki+1) {
+ (*index) += adjust;
+ }
+ LOG((" after: k,index = %d,%d\n", (*k), (*index)));
+ }
+
+ LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ src,
+ src->kids[0], src->counts[0], src->elems[0],
+ src->kids[1], src->counts[1], src->elems[1],
+ src->kids[2], src->counts[2], src->elems[2],
+ src->kids[3], src->counts[3]));
+ LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ dest,
+ dest->kids[0], dest->counts[0], dest->elems[0],
+ dest->kids[1], dest->counts[1], dest->elems[1],
+ dest->kids[2], dest->counts[2], dest->elems[2],
+ dest->kids[3], dest->counts[3]));
+}
+
+/*
+ * Tree transformation used in delete and split: move a subtree
+ * left, from child ki of a node to the previous child. Update k
+ * and index so that they still point to the same place in the
+ * transformed tree. Assumes the destination child is not full, and
+ * that the source child does have a subtree to spare. Can cope if
+ * the destination child is undersized.
+ *
+ * . B . . C .
+ * / \ -> / \
+ * a A b c C d D e [more] a A b B c d D e [more]
+ *
+ * . A . . B .
+ * / \ -> / \
+ * a b B c C d [more] a A b c C d [more]
+ */
+static void trans234_subtree_left(node234 *n, int ki, int *k, int *index) {
+ node234 *src, *dest;
+ int i, adjust;
+
+ src = n->kids[ki];
+ dest = n->kids[ki-1];
+
+ LOG((" trans234_subtree_left(%p, %d):\n", n, ki));
+ LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ dest,
+ dest->kids[0], dest->counts[0], dest->elems[0],
+ dest->kids[1], dest->counts[1], dest->elems[1],
+ dest->kids[2], dest->counts[2], dest->elems[2],
+ dest->kids[3], dest->counts[3]));
+ LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ src,
+ src->kids[0], src->counts[0], src->elems[0],
+ src->kids[1], src->counts[1], src->elems[1],
+ src->kids[2], src->counts[2], src->elems[2],
+ src->kids[3], src->counts[3]));
+
+ /* where in dest to put it */
+ i = (dest->elems[1] ? 2 : dest->elems[0] ? 1 : 0);
+ dest->elems[i] = n->elems[ki-1];
+ n->elems[ki-1] = src->elems[0];
+
+ dest->kids[i+1] = src->kids[0]; dest->counts[i+1] = src->counts[0];
+
+ if (dest->kids[i+1]) dest->kids[i+1]->parent = dest;
+
+ /*
+ * Move over the rest of the source node.
+ */
+ src->kids[0] = src->kids[1]; src->counts[0] = src->counts[1];
+ src->elems[0] = src->elems[1];
+ src->kids[1] = src->kids[2]; src->counts[1] = src->counts[2];
+ src->elems[1] = src->elems[2];
+ src->kids[2] = src->kids[3]; src->counts[2] = src->counts[3];
+ src->elems[2] = NULL;
+ src->kids[3] = NULL; src->counts[3] = 0;
+
+ adjust = dest->counts[i+1] + 1;
+
+ n->counts[ki] -= adjust;
+ n->counts[ki-1] += adjust;
+
+ if (k) {
+ LOG((" before: k,index = %d,%d\n", (*k), (*index)));
+ if ((*k) == ki) {
+ (*index) -= adjust;
+ if ((*index) < 0) {
+ (*index) += n->counts[ki-1] + 1;
+ (*k)--;
+ }
+ }
+ LOG((" after: k,index = %d,%d\n", (*k), (*index)));
+ }
+
+ LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ dest,
+ dest->kids[0], dest->counts[0], dest->elems[0],
+ dest->kids[1], dest->counts[1], dest->elems[1],
+ dest->kids[2], dest->counts[2], dest->elems[2],
+ dest->kids[3], dest->counts[3]));
+ LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ src,
+ src->kids[0], src->counts[0], src->elems[0],
+ src->kids[1], src->counts[1], src->elems[1],
+ src->kids[2], src->counts[2], src->elems[2],
+ src->kids[3], src->counts[3]));
+}
+
+/*
+ * Tree transformation used in delete and split: merge child nodes
+ * ki and ki+1 of a node. Update k and index so that they still
+ * point to the same place in the transformed tree. Assumes both
+ * children _are_ sufficiently small.
+ *
+ * . B . .
+ * / \ -> |
+ * a A b c C d a A b B c C d
+ *
+ * This routine can also cope with either child being undersized:
+ *
+ * . A . .
+ * / \ -> |
+ * a b B c a A b B c
+ *
+ * . A . .
+ * / \ -> |
+ * a b B c C d a A b B c C d
+ */
+static void trans234_subtree_merge(node234 *n, int ki, int *k, int *index) {
+ node234 *left, *right;
+ int i, leftlen, rightlen, lsize, rsize;
+
+ left = n->kids[ki]; leftlen = n->counts[ki];
+ right = n->kids[ki+1]; rightlen = n->counts[ki+1];
+
+ LOG((" trans234_subtree_merge(%p, %d):\n", n, ki));
+ LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" left %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ left,
+ left->kids[0], left->counts[0], left->elems[0],
+ left->kids[1], left->counts[1], left->elems[1],
+ left->kids[2], left->counts[2], left->elems[2],
+ left->kids[3], left->counts[3]));
+ LOG((" right %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ right,
+ right->kids[0], right->counts[0], right->elems[0],
+ right->kids[1], right->counts[1], right->elems[1],
+ right->kids[2], right->counts[2], right->elems[2],
+ right->kids[3], right->counts[3]));
+
+ assert(!left->elems[2] && !right->elems[2]); /* neither is large! */
+ lsize = (left->elems[1] ? 2 : left->elems[0] ? 1 : 0);
+ rsize = (right->elems[1] ? 2 : right->elems[0] ? 1 : 0);
+
+ left->elems[lsize] = n->elems[ki];
+
+ for (i = 0; i < rsize+1; i++) {
+ left->kids[lsize+1+i] = right->kids[i];
+ left->counts[lsize+1+i] = right->counts[i];
+ if (left->kids[lsize+1+i])
+ left->kids[lsize+1+i]->parent = left;
+ if (i < rsize)
+ left->elems[lsize+1+i] = right->elems[i];
+ }
+
+ n->counts[ki] += rightlen + 1;
+
+ sfree(right);
+
+ /*
+ * Move the rest of n up by one.
+ */
+ for (i = ki+1; i < 3; i++) {
+ n->kids[i] = n->kids[i+1];
+ n->counts[i] = n->counts[i+1];
+ }
+ for (i = ki; i < 2; i++) {
+ n->elems[i] = n->elems[i+1];
+ }
+ n->kids[3] = NULL;
+ n->counts[3] = 0;
+ n->elems[2] = NULL;
+
+ if (k) {
+ LOG((" before: k,index = %d,%d\n", (*k), (*index)));
+ if ((*k) == ki+1) {
+ (*k)--;
+ (*index) += leftlen + 1;
+ } else if ((*k) > ki+1) {
+ (*k)--;
+ }
+ LOG((" after: k,index = %d,%d\n", (*k), (*index)));
+ }
+
+ LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" merged %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ left,
+ left->kids[0], left->counts[0], left->elems[0],
+ left->kids[1], left->counts[1], left->elems[1],
+ left->kids[2], left->counts[2], left->elems[2],
+ left->kids[3], left->counts[3]));
+
+}
+
+/*
+ * Delete an element e in a 2-3-4 tree. Does not free the element,
+ * merely removes all links to it from the tree nodes.
+ */
+static void *delpos234_internal(tree234 *t, int index) {
+ node234 *n;
+ void *retval;
+ int ki, i;
+
+ retval = NULL;
+
+ n = t->root; /* by assumption this is non-NULL */
+ LOG(("deleting item %d from tree %p\n", index, t));
+ while (1) {
+ node234 *sub;
+
+ LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3],
+ index));
+ if (index <= n->counts[0]) {
+ ki = 0;
+ } else if (index -= n->counts[0]+1, index <= n->counts[1]) {
+ ki = 1;
+ } else if (index -= n->counts[1]+1, index <= n->counts[2]) {
+ ki = 2;
+ } else if (index -= n->counts[2]+1, index <= n->counts[3]) {
+ ki = 3;
+ } else {
+ assert(0); /* can't happen */
+ }
+
+ if (!n->kids[0])
+ break; /* n is a leaf node; we're here! */
+
+ /*
+ * Check to see if we've found our target element. If so,
+ * we must choose a new target (we'll use the old target's
+ * successor, which will be in a leaf), move it into the
+ * place of the old one, continue down to the leaf and
+ * delete the old copy of the new target.
+ */
+ if (index == n->counts[ki]) {
+ node234 *m;
+ LOG((" found element in internal node, index %d\n", ki));
+ assert(n->elems[ki]); /* must be a kid _before_ an element */
+ ki++; index = 0;
+ for (m = n->kids[ki]; m->kids[0]; m = m->kids[0])
+ continue;
+ LOG((" replacing with element \"%s\" from leaf node %p\n",
+ m->elems[0], m));
+ retval = n->elems[ki-1];
+ n->elems[ki-1] = m->elems[0];
+ }
+
+ /*
+ * Recurse down to subtree ki. If it has only one element,
+ * we have to do some transformation to start with.
+ */
+ LOG((" moving to subtree %d\n", ki));
+ sub = n->kids[ki];
+ if (!sub->elems[1]) {
+ LOG((" subtree has only one element!\n"));
+ if (ki > 0 && n->kids[ki-1]->elems[1]) {
+ /*
+ * Child ki has only one element, but child
+ * ki-1 has two or more. So we need to move a
+ * subtree from ki-1 to ki.
+ */
+ trans234_subtree_right(n, ki-1, &ki, &index);
+ } else if (ki < 3 && n->kids[ki+1] &&
+ n->kids[ki+1]->elems[1]) {
+ /*
+ * Child ki has only one element, but ki+1 has
+ * two or more. Move a subtree from ki+1 to ki.
+ */
+ trans234_subtree_left(n, ki+1, &ki, &index);
+ } else {
+ /*
+ * ki is small with only small neighbours. Pick a
+ * neighbour and merge with it.
+ */
+ trans234_subtree_merge(n, ki>0 ? ki-1 : ki, &ki, &index);
+ sub = n->kids[ki];
+
+ if (!n->elems[0]) {
+ /*
+ * The root is empty and needs to be
+ * removed.
+ */
+ LOG((" shifting root!\n"));
+ t->root = sub;
+ sub->parent = NULL;
+ sfree(n);
+ n = NULL;
+ }
+ }
+ }
+
+ if (n)
+ n->counts[ki]--;
+ n = sub;
+ }
+
+ /*
+ * Now n is a leaf node, and ki marks the element number we
+ * want to delete. We've already arranged for the leaf to be
+ * bigger than minimum size, so let's just go to it.
+ */
+ assert(!n->kids[0]);
+ if (!retval)
+ retval = n->elems[ki];
+
+ for (i = ki; i < 2 && n->elems[i+1]; i++)
+ n->elems[i] = n->elems[i+1];
+ n->elems[i] = NULL;
+
+ /*
+ * It's just possible that we have reduced the leaf to zero
+ * size. This can only happen if it was the root - so destroy
+ * it and make the tree empty.
+ */
+ if (!n->elems[0]) {
+ LOG((" removed last element in tree, destroying empty root\n"));
+ assert(n == t->root);
+ sfree(n);
+ t->root = NULL;
+ }
+
+ return retval; /* finished! */
+}
+void *delpos234(tree234 *t, int index) {
+ if (index < 0 || index >= countnode234(t->root))
+ return NULL;
+ return delpos234_internal(t, index);
+}
+void *del234(tree234 *t, void *e) {
+ int index;
+ if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
+ return NULL; /* it wasn't in there anyway */
+ return delpos234_internal(t, index); /* it's there; delete it. */
+}
+
+/*
+ * Join two subtrees together with a separator element between
+ * them, given their relative height.
+ *
+ * (Height<0 means the left tree is shorter, >0 means the right
+ * tree is shorter, =0 means (duh) they're equal.)
+ *
+ * It is assumed that any checks needed on the ordering criterion
+ * have _already_ been done.
+ *
+ * The value returned in `height' is 0 or 1 depending on whether the
+ * resulting tree is the same height as the original larger one, or
+ * one higher.
+ */
+static node234 *join234_internal(node234 *left, void *sep,
+ node234 *right, int *height) {
+ node234 *root, *node;
+ int relht = *height;
+ int ki;
+
+ LOG((" join: joining %p \"%s\" %p, relative height is %d\n",
+ left, sep, right, relht));
+ if (relht == 0) {
+ /*
+ * The trees are the same height. Create a new one-element
+ * root containing the separator and pointers to the two
+ * nodes.
+ */
+ node234 *newroot;
+ newroot = mknew(node234);
+ newroot->kids[0] = left; newroot->counts[0] = countnode234(left);
+ newroot->elems[0] = sep;
+ newroot->kids[1] = right; newroot->counts[1] = countnode234(right);
+ newroot->elems[1] = NULL;
+ newroot->kids[2] = NULL; newroot->counts[2] = 0;
+ newroot->elems[2] = NULL;
+ newroot->kids[3] = NULL; newroot->counts[3] = 0;
+ newroot->parent = NULL;
+ if (left) left->parent = newroot;
+ if (right) right->parent = newroot;
+ *height = 1;
+ LOG((" join: same height, brand new root\n"));
+ return newroot;
+ }
+
+ /*
+ * This now works like the addition algorithm on the larger
+ * tree. We're replacing a single kid pointer with two kid
+ * pointers separated by an element; if that causes the node to
+ * overload, we split it in two, move a separator element up to
+ * the next node, and repeat.
+ */
+ if (relht < 0) {
+ /*
+ * Left tree is shorter. Search down the right tree to find
+ * the pointer we're inserting at.
+ */
+ node = root = right;
+ while (++relht < 0) {
+ node = node->kids[0];
+ }
+ ki = 0;
+ right = node->kids[ki];
+ } else {
+ /*
+ * Right tree is shorter; search down the left to find the
+ * pointer we're inserting at.
+ */
+ node = root = left;
+ while (--relht > 0) {
+ if (node->elems[2])
+ node = node->kids[3];
+ else if (node->elems[1])
+ node = node->kids[2];
+ else
+ node = node->kids[1];
+ }
+ if (node->elems[2])
+ ki = 3;
+ else if (node->elems[1])
+ ki = 2;
+ else
+ ki = 1;
+ left = node->kids[ki];
+ }
+
+ /*
+ * Now proceed as for addition.
+ */
+ *height = add234_insert(left, sep, right, &root, node, ki);
+
+ return root;
+}
+static int height234(tree234 *t) {
+ int level = 0;
+ node234 *n = t->root;
+ while (n) {
+ level++;
+ n = n->kids[0];
+ }
+ return level;
+}
+tree234 *join234(tree234 *t1, tree234 *t2) {
+ int size2 = countnode234(t2->root);
+ if (size2 > 0) {
+ void *element;
+ int relht;
+
+ if (t1->cmp) {
+ element = index234(t2, 0);
+ element = findrelpos234(t1, element, NULL, REL234_GE, NULL);
+ if (element)
+ return NULL;
+ }
+
+ element = delpos234(t2, 0);
+ relht = height234(t1) - height234(t2);
+ t1->root = join234_internal(t1->root, element, t2->root, &relht);
+ t2->root = NULL;
+ }
+ return t1;
+}
+tree234 *join234r(tree234 *t1, tree234 *t2) {
+ int size1 = countnode234(t1->root);
+ if (size1 > 0) {
+ void *element;
+ int relht;
+
+ if (t2->cmp) {
+ element = index234(t1, size1-1);
+ element = findrelpos234(t2, element, NULL, REL234_LE, NULL);
+ if (element)
+ return NULL;
+ }
+
+ element = delpos234(t1, size1-1);
+ relht = height234(t1) - height234(t2);
+ t2->root = join234_internal(t1->root, element, t2->root, &relht);
+ t1->root = NULL;
+ }
+ return t2;
+}
+
+/*
+ * Split out the first <index> elements in a tree and return a
+ * pointer to the root node. Leave the root node of the remainder
+ * in t.
+ */
+static node234 *split234_internal(tree234 *t, int index) {
+ node234 *halves[2], *n, *sib, *sub;
+ node234 *lparent, *rparent;
+ int ki, pki, i, half, lcount, rcount;
+
+ n = t->root;
+ LOG(("splitting tree %p at point %d\n", t, index));
+
+ /*
+ * Easy special cases. After this we have also dealt completely
+ * with the empty-tree case and we can assume the root exists.
+ */
+ if (index == 0) /* return nothing */
+ return NULL;
+ if (index == countnode234(t->root)) { /* return the whole tree */
+ node234 *ret = t->root;
+ t->root = NULL;
+ return ret;
+ }
+
+ /*
+ * Search down the tree to find the split point.
+ */
+ lparent = rparent = NULL;
+ while (n) {
+ LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3],
+ index));
+ lcount = index;
+ rcount = countnode234(n) - lcount;
+ if (index <= n->counts[0]) {
+ ki = 0;
+ } else if (index -= n->counts[0]+1, index <= n->counts[1]) {
+ ki = 1;
+ } else if (index -= n->counts[1]+1, index <= n->counts[2]) {
+ ki = 2;
+ } else {
+ index -= n->counts[2]+1;
+ ki = 3;
+ }
+
+ LOG((" splitting at subtree %d\n", ki));
+ sub = n->kids[ki];
+
+ LOG((" splitting at child index %d\n", ki));
+
+ /*
+ * Split the node, put halves[0] on the right of the left
+ * one and halves[1] on the left of the right one, put the
+ * new node pointers in halves[0] and halves[1], and go up
+ * a level.
+ */
+ sib = mknew(node234);
+ for (i = 0; i < 3; i++) {
+ if (i+ki < 3 && n->elems[i+ki]) {
+ sib->elems[i] = n->elems[i+ki];
+ sib->kids[i+1] = n->kids[i+ki+1];
+ if (sib->kids[i+1]) sib->kids[i+1]->parent = sib;
+ sib->counts[i+1] = n->counts[i+ki+1];
+ n->elems[i+ki] = NULL;
+ n->kids[i+ki+1] = NULL;
+ n->counts[i+ki+1] = 0;
+ } else {
+ sib->elems[i] = NULL;
+ sib->kids[i+1] = NULL;
+ sib->counts[i+1] = 0;
+ }
+ }
+ if (lparent) {
+ lparent->kids[pki] = n;
+ lparent->counts[pki] = lcount;
+ n->parent = lparent;
+ rparent->kids[0] = sib;
+ rparent->counts[0] = rcount;
+ sib->parent = rparent;
+ } else {
+ halves[0] = n;
+ n->parent = NULL;
+ halves[1] = sib;
+ sib->parent = NULL;
+ }
+ lparent = n;
+ rparent = sib;
+ pki = ki;
+ LOG((" left node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ LOG((" right node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ sib,
+ sib->kids[0], sib->counts[0], sib->elems[0],
+ sib->kids[1], sib->counts[1], sib->elems[1],
+ sib->kids[2], sib->counts[2], sib->elems[2],
+ sib->kids[3], sib->counts[3]));
+
+ n = sub;
+ }
+
+ /*
+ * We've come off the bottom here, so we've successfully split
+ * the tree into two equally high subtrees. The only problem is
+ * that some of the nodes down the fault line will be smaller
+ * than the minimum permitted size. (Since this is a 2-3-4
+ * tree, that means they'll be zero-element one-child nodes.)
+ */
+ LOG((" fell off bottom, lroot is %p, rroot is %p\n",
+ halves[0], halves[1]));
+ lparent->counts[pki] = rparent->counts[0] = 0;
+ lparent->kids[pki] = rparent->kids[0] = NULL;
+
+ /*
+ * So now we go back down the tree from each of the two roots,
+ * fixing up undersize nodes.
+ */
+ for (half = 0; half < 2; half++) {
+ /*
+ * Remove the root if it's undersize (it will contain only
+ * one child pointer, so just throw it away and replace it
+ * with its child). This might happen several times.
+ */
+ while (halves[half] && !halves[half]->elems[0]) {
+ LOG((" root %p is undersize, throwing away\n", halves[half]));
+ halves[half] = halves[half]->kids[0];
+ sfree(halves[half]->parent);
+ halves[half]->parent = NULL;
+ LOG((" new root is %p\n", halves[half]));
+ }
+
+ n = halves[half];
+ while (n) {
+ void (*toward)(node234 *n, int ki, int *k, int *index);
+ int ni, merge;
+
+ /*
+ * Now we have a potentially undersize node on the
+ * right (if half==0) or left (if half==1). Sort it
+ * out, by merging with a neighbour or by transferring
+ * subtrees over. At this time we must also ensure that
+ * nodes are bigger than minimum, in case we need an
+ * element to merge two nodes below.
+ */
+ LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
+ n,
+ n->kids[0], n->counts[0], n->elems[0],
+ n->kids[1], n->counts[1], n->elems[1],
+ n->kids[2], n->counts[2], n->elems[2],
+ n->kids[3], n->counts[3]));
+ if (half == 1) {
+ ki = 0; /* the kid we're interested in */
+ ni = 1; /* the neighbour */
+ merge = 0; /* for merge: leftmost of the two */
+ toward = trans234_subtree_left;
+ } else {
+ ki = (n->kids[3] ? 3 : n->kids[2] ? 2 : 1);
+ ni = ki-1;
+ merge = ni;
+ toward = trans234_subtree_right;
+ }
+
+ sub = n->kids[ki];
+ if (sub && !sub->elems[1]) {
+ /*
+ * This node is undersized or minimum-size. If we
+ * can merge it with its neighbour, we do so;
+ * otherwise we must be able to transfer subtrees
+ * over to it until it is greater than minimum
+ * size.
+ */
+ int undersized = (!sub->elems[0]);
+ LOG((" child %d is %ssize\n", ki,
+ undersized ? "under" : "minimum-"));
+ LOG((" neighbour is %s\n",
+ n->kids[ni]->elems[2] ? "large" :
+ n->kids[ni]->elems[1] ? "medium" : "small"));
+ if (!n->kids[ni]->elems[1] ||
+ (undersized && !n->kids[ni]->elems[2])) {
+ /*
+ * Neighbour is small, or possibly neighbour is
+ * medium and we are undersize.
+ */
+ trans234_subtree_merge(n, merge, NULL, NULL);
+ sub = n->kids[merge];
+ if (!n->elems[0]) {
+ /*
+ * n is empty, and hence must have been the
+ * root and needs to be removed.
+ */
+ assert(!n->parent);
+ LOG((" shifting root!\n"));
+ halves[half] = sub;
+ halves[half]->parent = NULL;
+ sfree(n);
+ }
+ } else {
+ /* Neighbour is big enough to move trees over. */
+ toward(n, ni, NULL, NULL);
+ if (undersized)
+ toward(n, ni, NULL, NULL);
+ }
+ }
+ n = sub;
+ }
+ }
+
+ t->root = halves[1];
+ return halves[0];
+}
+tree234 *splitpos234(tree234 *t, int index, int before) {
+ tree234 *ret;
+ node234 *n;
+ int count;
+
+ count = countnode234(t->root);
+ if (index < 0 || index > count)
+ return NULL; /* error */
+ ret = newtree234(t->cmp);
+ n = split234_internal(t, index);
+ if (before) {
+ /* We want to return the ones before the index. */
+ ret->root = n;
+ } else {
+ /*
+ * We want to keep the ones before the index and return the
+ * ones after.
+ */
+ ret->root = t->root;
+ t->root = n;
+ }
+ return ret;
+}
+tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel) {
+ int before;
+ int index;
+
+ assert(rel != REL234_EQ);
+
+ if (rel == REL234_GT || rel == REL234_GE) {
+ before = 1;
+ rel = (rel == REL234_GT ? REL234_LE : REL234_LT);
+ } else {
+ before = 0;
+ }
+ if (!findrelpos234(t, e, cmp, rel, &index))
+ index = 0;
+
+ return splitpos234(t, index+1, before);
+}
+
+static node234 *copynode234(node234 *n, copyfn234 copyfn, void *copyfnstate) {
+ int i;
+ node234 *n2 = mknew(node234);
+
+ for (i = 0; i < 3; i++) {
+ if (n->elems[i] && copyfn)
+ n2->elems[i] = copyfn(copyfnstate, n->elems[i]);
+ else
+ n2->elems[i] = n->elems[i];
+ }
+
+ for (i = 0; i < 4; i++) {
+ if (n->kids[i]) {
+ n2->kids[i] = copynode234(n->kids[i], copyfn, copyfnstate);
+ n2->kids[i]->parent = n2;
+ } else {
+ n2->kids[i] = NULL;
+ }
+ n2->counts[i] = n->counts[i];
+ }
+
+ return n2;
+}
+tree234 *copytree234(tree234 *t, copyfn234 copyfn, void *copyfnstate) {
+ tree234 *t2;
+
+ t2 = newtree234(t->cmp);
+ t2->root = copynode234(t->root, copyfn, copyfnstate);
+ t2->root->parent = NULL;
+
+ return t2;
+}
+
+#ifdef TEST
+
+/*
+ * Test code for the 2-3-4 tree. This code maintains an alternative
+ * representation of the data in the tree, in an array (using the
+ * obvious and slow insert and delete functions). After each tree
+ * operation, the verify() function is called, which ensures all
+ * the tree properties are preserved:
+ * - node->child->parent always equals node
+ * - tree->root->parent always equals NULL
+ * - number of kids == 0 or number of elements + 1;
+ * - tree has the same depth everywhere
+ * - every node has at least one element
+ * - subtree element counts are accurate
+ * - any NULL kid pointer is accompanied by a zero count
+ * - in a sorted tree: ordering property between elements of a
+ * node and elements of its children is preserved
+ * and also ensures the list represented by the tree is the same
+ * list it should be. (This last check also doubly verifies the
+ * ordering properties, because the `same list it should be' is by
+ * definition correctly ordered. It also ensures all nodes are
+ * distinct, because the enum functions would get caught in a loop
+ * if not.)
+ */
+
+#include <stdarg.h>
+
+#define srealloc realloc
+
+/*
+ * Error reporting function.
+ */
+void error(char *fmt, ...) {
+ va_list ap;
+ printf("ERROR: ");
+ va_start(ap, fmt);
+ vfprintf(stdout, fmt, ap);
+ va_end(ap);
+ printf("\n");
+}
+
+/* The array representation of the data. */
+void **array;
+int arraylen, arraysize;
+cmpfn234 cmp;
+
+/* The tree representation of the same data. */
+tree234 *tree;
+
+/*
+ * Routines to provide a diagnostic printout of a tree. Currently
+ * relies on every element in the tree being a one-character string
+ * :-)
+ */
+typedef struct {
+ char **levels;
+} dispctx;
+
+int dispnode(node234 *n, int level, dispctx *ctx) {
+ if (level == 0) {
+ int xpos = strlen(ctx->levels[0]);
+ int len;
+
+ if (n->elems[2])
+ len = sprintf(ctx->levels[0]+xpos, " %s%s%s",
+ n->elems[0], n->elems[1], n->elems[2]);
+ else if (n->elems[1])
+ len = sprintf(ctx->levels[0]+xpos, " %s%s",
+ n->elems[0], n->elems[1]);
+ else
+ len = sprintf(ctx->levels[0]+xpos, " %s",
+ n->elems[0]);
+ return xpos + 1 + (len-1) / 2;
+ } else {
+ int xpos[4], nkids;
+ int nodelen, mypos, myleft, x, i;
+
+ xpos[0] = dispnode(n->kids[0], level-3, ctx);
+ xpos[1] = dispnode(n->kids[1], level-3, ctx);
+ nkids = 2;
+ if (n->kids[2]) {
+ xpos[2] = dispnode(n->kids[2], level-3, ctx);
+ nkids = 3;
+ }
+ if (n->kids[3]) {
+ xpos[3] = dispnode(n->kids[3], level-3, ctx);
+ nkids = 4;
+ }
+
+ if (nkids == 4)
+ mypos = (xpos[1] + xpos[2]) / 2;
+ else if (nkids == 3)
+ mypos = xpos[1];
+ else
+ mypos = (xpos[0] + xpos[1]) / 2;
+ nodelen = nkids * 2 - 1;
+ myleft = mypos - ((nodelen-1)/2);
+ assert(myleft >= xpos[0]);
+ assert(myleft + nodelen-1 <= xpos[nkids-1]);
+
+ x = strlen(ctx->levels[level]);
+ while (x <= xpos[0] && x < myleft)
+ ctx->levels[level][x++] = ' ';
+ while (x < myleft)
+ ctx->levels[level][x++] = '_';
+ if (nkids==4)
+ x += sprintf(ctx->levels[level]+x, ".%s.%s.%s.",
+ n->elems[0], n->elems[1], n->elems[2]);
+ else if (nkids==3)
+ x += sprintf(ctx->levels[level]+x, ".%s.%s.",
+ n->elems[0], n->elems[1]);
+ else
+ x += sprintf(ctx->levels[level]+x, ".%s.",
+ n->elems[0]);
+ while (x < xpos[nkids-1])
+ ctx->levels[level][x++] = '_';
+ ctx->levels[level][x] = '\0';
+
+ x = strlen(ctx->levels[level-1]);
+ for (i = 0; i < nkids; i++) {
+ int rpos, pos;
+ rpos = xpos[i];
+ if (i > 0 && i < nkids-1)
+ pos = myleft + 2*i;
+ else
+ pos = rpos;
+ if (rpos < pos)
+ rpos++;
+ while (x < pos && x < rpos)
+ ctx->levels[level-1][x++] = ' ';
+ if (x == pos)
+ ctx->levels[level-1][x++] = '|';
+ while (x < pos || x < rpos)
+ ctx->levels[level-1][x++] = '_';
+ if (x == pos)
+ ctx->levels[level-1][x++] = '|';
+ }
+ ctx->levels[level-1][x] = '\0';
+
+ x = strlen(ctx->levels[level-2]);
+ for (i = 0; i < nkids; i++) {
+ int rpos = xpos[i];
+
+ while (x < rpos)
+ ctx->levels[level-2][x++] = ' ';
+ ctx->levels[level-2][x++] = '|';
+ }
+ ctx->levels[level-2][x] = '\0';
+
+ return mypos;
+ }
+}
+
+void disptree(tree234 *t) {
+ dispctx ctx;
+ char *leveldata;
+ int width = count234(t);
+ int ht = height234(t) * 3 - 2;
+ int i;
+
+ if (!t->root) {
+ printf("[empty tree]\n");
+ }
+
+ leveldata = smalloc(ht * (width+2));
+ ctx.levels = smalloc(ht * sizeof(char *));
+ for (i = 0; i < ht; i++) {
+ ctx.levels[i] = leveldata + i * (width+2);
+ ctx.levels[i][0] = '\0';
+ }
+
+ (void) dispnode(t->root, ht-1, &ctx);
+
+ for (i = ht; i-- ;)
+ printf("%s\n", ctx.levels[i]);
+
+ sfree(ctx.levels);
+ sfree(leveldata);
+}
+
+typedef struct {
+ int treedepth;
+ int elemcount;
+} chkctx;
+
+int chknode(chkctx *ctx, int level, node234 *node,
+ void *lowbound, void *highbound) {
+ int nkids, nelems;
+ int i;
+ int count;
+
+ /* Count the non-NULL kids. */
+ for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
+ /* Ensure no kids beyond the first NULL are non-NULL. */
+ for (i = nkids; i < 4; i++)
+ if (node->kids[i]) {
+ error("node %p: nkids=%d but kids[%d] non-NULL",
+ node, nkids, i);
+ } else if (node->counts[i]) {
+ error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
+ node, i, i, node->counts[i]);
+ }
+
+ /* Count the non-NULL elements. */
+ for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
+ /* Ensure no elements beyond the first NULL are non-NULL. */
+ for (i = nelems; i < 3; i++)
+ if (node->elems[i]) {
+ error("node %p: nelems=%d but elems[%d] non-NULL",
+ node, nelems, i);
+ }
+
+ if (nkids == 0) {
+ /*
+ * If nkids==0, this is a leaf node; verify that the tree
+ * depth is the same everywhere.
+ */
+ if (ctx->treedepth < 0)
+ ctx->treedepth = level; /* we didn't know the depth yet */
+ else if (ctx->treedepth != level)
+ error("node %p: leaf at depth %d, previously seen depth %d",
+ node, level, ctx->treedepth);
+ } else {
+ /*
+ * If nkids != 0, then it should be nelems+1, unless nelems
+ * is 0 in which case nkids should also be 0 (and so we
+ * shouldn't be in this condition at all).
+ */
+ int shouldkids = (nelems ? nelems+1 : 0);
+ if (nkids != shouldkids) {
+ error("node %p: %d elems should mean %d kids but has %d",
+ node, nelems, shouldkids, nkids);
+ }
+ }
+
+ /*
+ * nelems should be at least 1.
+ */
+ if (nelems == 0) {
+ error("node %p: no elems", node, nkids);
+ }
+
+ /*
+ * Add nelems to the running element count of the whole tree.
+ */
+ ctx->elemcount += nelems;
+
+ /*
+ * Check ordering property: all elements should be strictly >
+ * lowbound, strictly < highbound, and strictly < each other in
+ * sequence. (lowbound and highbound are NULL at edges of tree
+ * - both NULL at root node - and NULL is considered to be <
+ * everything and > everything. IYSWIM.)
+ */
+ if (cmp) {
+ for (i = -1; i < nelems; i++) {
+ void *lower = (i == -1 ? lowbound : node->elems[i]);
+ void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
+ if (lower && higher && cmp(lower, higher) >= 0) {
+ error("node %p: kid comparison [%d=%s,%d=%s] failed",
+ node, i, lower, i+1, higher);
+ }
+ }
+ }
+
+ /*
+ * Check parent pointers: all non-NULL kids should have a
+ * parent pointer coming back to this node.
+ */
+ for (i = 0; i < nkids; i++)
+ if (node->kids[i]->parent != node) {
+ error("node %p kid %d: parent ptr is %p not %p",
+ node, i, node->kids[i]->parent, node);
+ }
+
+
+ /*
+ * Now (finally!) recurse into subtrees.
+ */
+ count = nelems;
+
+ for (i = 0; i < nkids; i++) {
+ void *lower = (i == 0 ? lowbound : node->elems[i-1]);
+ void *higher = (i >= nelems ? highbound : node->elems[i]);
+ int subcount = chknode(ctx, level+1, node->kids[i], lower, higher);
+ if (node->counts[i] != subcount) {
+ error("node %p kid %d: count says %d, subtree really has %d",
+ node, i, node->counts[i], subcount);
+ }
+ count += subcount;
+ }
+
+ return count;
+}
+
+void verifytree(tree234 *tree, void **array, int arraylen) {
+ chkctx ctx;
+ int i;
+ void *p;
+
+ ctx.treedepth = -1; /* depth unknown yet */
+ ctx.elemcount = 0; /* no elements seen yet */
+ /*
+ * Verify validity of tree properties.
+ */
+ if (tree->root) {
+ if (tree->root->parent != NULL)
+ error("root->parent is %p should be null", tree->root->parent);
+ chknode(&ctx, 0, tree->root, NULL, NULL);
+ }
+ printf("tree depth: %d\n", ctx.treedepth);
+ /*
+ * Enumerate the tree and ensure it matches up to the array.
+ */
+ for (i = 0; NULL != (p = index234(tree, i)); i++) {
+ if (i >= arraylen)
+ error("tree contains more than %d elements", arraylen);
+ if (array[i] != p)
+ error("enum at position %d: array says %s, tree says %s",
+ i, array[i], p);
+ }
+ if (ctx.elemcount != i) {
+ error("tree really contains %d elements, enum gave %d",
+ ctx.elemcount, i);
+ }
+ if (i < arraylen) {
+ error("enum gave only %d elements, array has %d", i, arraylen);
+ }
+ i = count234(tree);
+ if (ctx.elemcount != i) {
+ error("tree really contains %d elements, count234 gave %d",
+ ctx.elemcount, i);
+ }
+}
+void verify(void) { verifytree(tree, array, arraylen); }
+
+void internal_addtest(void *elem, int index, void *realret) {
+ int i, j;
+ void *retval;
+
+ if (arraysize < arraylen+1) {
+ arraysize = arraylen+1+256;
+ array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
+ srealloc(array, arraysize*sizeof(*array)));
+ }
+
+ i = index;
+ /* now i points to the first element >= elem */
+ retval = elem; /* expect elem returned (success) */
+ for (j = arraylen; j > i; j--)
+ array[j] = array[j-1];
+ array[i] = elem; /* add elem to array */
+ arraylen++;
+
+ if (realret != retval) {
+ error("add: retval was %p expected %p", realret, retval);
+ }
+
+ verify();
+}
+
+void addtest(void *elem) {
+ int i;
+ void *realret;
+
+ realret = add234(tree, elem);
+
+ i = 0;
+ while (i < arraylen && cmp(elem, array[i]) > 0)
+ i++;
+ if (i < arraylen && !cmp(elem, array[i])) {
+ void *retval = array[i]; /* expect that returned not elem */
+ if (realret != retval) {
+ error("add: retval was %p expected %p", realret, retval);
+ }
+ } else
+ internal_addtest(elem, i, realret);
+}
+
+void addpostest(void *elem, int i) {
+ void *realret;
+
+ realret = addpos234(tree, elem, i);
+
+ internal_addtest(elem, i, realret);
+}
+
+void delpostest(int i) {
+ int index = i;
+ void *elem = array[i], *ret;
+
+ /* i points to the right element */
+ while (i < arraylen-1) {
+ array[i] = array[i+1];
+ i++;
+ }
+ arraylen--; /* delete elem from array */
+
+ if (tree->cmp)
+ ret = del234(tree, elem);
+ else
+ ret = delpos234(tree, index);
+
+ if (ret != elem) {
+ error("del returned %p, expected %p", ret, elem);
+ }
+
+ verify();
+}
+
+void deltest(void *elem) {
+ int i;
+
+ i = 0;
+ while (i < arraylen && cmp(elem, array[i]) > 0)
+ i++;
+ if (i >= arraylen || cmp(elem, array[i]) != 0)
+ return; /* don't do it! */
+ delpostest(i);
+}
+
+/* A sample data set and test utility. Designed for pseudo-randomness,
+ * and yet repeatability. */
+
+/*
+ * This random number generator uses the `portable implementation'
+ * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
+ * change it if not.
+ */
+int randomnumber(unsigned *seed) {
+ *seed *= 1103515245;
+ *seed += 12345;
+ return ((*seed) / 65536) % 32768;
+}
+
+int mycmp(void *av, void *bv) {
+ char const *a = (char const *)av;
+ char const *b = (char const *)bv;
+ return strcmp(a, b);
+}
+
+#define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
+
+char *strings[] = {
+ "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i",
+ "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E",
+ "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u",
+ "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y",
+ "m", "s", "l", "4",
+#if 0
+ "a", "ab", "absque", "coram", "de",
+ "palam", "clam", "cum", "ex", "e",
+ "sine", "tenus", "pro", "prae",
+ "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
+ "penguin", "blancmange", "pangolin", "whale", "hedgehog",
+ "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
+ "murfl", "spoo", "breen", "flarn", "octothorpe",
+ "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
+ "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
+ "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
+ "wand", "ring", "amulet"
+#endif
+};
+
+#define NSTR lenof(strings)
+
+void findtest(void) {
+ static const int rels[] = {
+ REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
+ };
+ static const char *const relnames[] = {
+ "EQ", "GE", "LE", "LT", "GT"
+ };
+ int i, j, rel, index;
+ char *p, *ret, *realret, *realret2;
+ int lo, hi, mid, c;
+
+ for (i = 0; i < (int)NSTR; i++) {
+ p = strings[i];
+ for (j = 0; j < (int)(sizeof(rels)/sizeof(*rels)); j++) {
+ rel = rels[j];
+
+ lo = 0; hi = arraylen-1;
+ while (lo <= hi) {
+ mid = (lo + hi) / 2;
+ c = strcmp(p, array[mid]);
+ if (c < 0)
+ hi = mid-1;
+ else if (c > 0)
+ lo = mid+1;
+ else
+ break;
+ }
+
+ if (c == 0) {
+ if (rel == REL234_LT)
+ ret = (mid > 0 ? array[--mid] : NULL);
+ else if (rel == REL234_GT)
+ ret = (mid < arraylen-1 ? array[++mid] : NULL);
+ else
+ ret = array[mid];
+ } else {
+ assert(lo == hi+1);
+ if (rel == REL234_LT || rel == REL234_LE) {
+ mid = hi;
+ ret = (hi >= 0 ? array[hi] : NULL);
+ } else if (rel == REL234_GT || rel == REL234_GE) {
+ mid = lo;
+ ret = (lo < arraylen ? array[lo] : NULL);
+ } else
+ ret = NULL;
+ }
+
+ realret = findrelpos234(tree, p, NULL, rel, &index);
+ if (realret != ret) {
+ error("find(\"%s\",%s) gave %s should be %s",
+ p, relnames[j], realret, ret);
+ }
+ if (realret && index != mid) {
+ error("find(\"%s\",%s) gave %d should be %d",
+ p, relnames[j], index, mid);
+ }
+ if (realret && rel == REL234_EQ) {
+ realret2 = index234(tree, index);
+ if (realret2 != realret) {
+ error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
+ p, relnames[j], realret, index, index, realret2);
+ }
+ }
+#if 0
+ printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
+ realret, index);
+#endif
+ }
+ }
+
+ realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
+ if (arraylen && (realret != array[0] || index != 0)) {
+ error("find(NULL,GT) gave %s(%d) should be %s(0)",
+ realret, index, array[0]);
+ } else if (!arraylen && (realret != NULL)) {
+ error("find(NULL,GT) gave %s(%d) should be NULL",
+ realret, index);
+ }
+
+ realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
+ if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
+ error("find(NULL,LT) gave %s(%d) should be %s(0)",
+ realret, index, array[arraylen-1]);
+ } else if (!arraylen && (realret != NULL)) {
+ error("find(NULL,LT) gave %s(%d) should be NULL",
+ realret, index);
+ }
+}
+
+void splittest(tree234 *tree, void **array, int arraylen) {
+ int i;
+ tree234 *tree3, *tree4;
+ for (i = 0; i <= arraylen; i++) {
+ tree3 = copytree234(tree, NULL, NULL);
+ tree4 = splitpos234(tree3, i, 0);
+ verifytree(tree3, array, i);
+ verifytree(tree4, array+i, arraylen-i);
+ join234(tree3, tree4);
+ freetree234(tree4); /* left empty by join */
+ verifytree(tree3, array, arraylen);
+ freetree234(tree3);
+ }
+}
+
+int main(void) {
+ int in[NSTR];
+ int i, j, k;
+ int tworoot, tmplen;
+ unsigned seed = 0;
+ tree234 *tree2, *tree3, *tree4;
+ int c;
+
+ setvbuf(stdout, NULL, _IOLBF, 0);
+
+ for (i = 0; i < (int)NSTR; i++) in[i] = 0;
+ array = NULL;
+ arraylen = arraysize = 0;
+ tree = newtree234(mycmp);
+ cmp = mycmp;
+
+ verify();
+ for (i = 0; i < 10000; i++) {
+ j = randomnumber(&seed);
+ j %= NSTR;
+ printf("trial: %d\n", i);
+ if (in[j]) {
+ printf("deleting %s (%d)\n", strings[j], j);
+ deltest(strings[j]);
+ in[j] = 0;
+ } else {
+ printf("adding %s (%d)\n", strings[j], j);
+ addtest(strings[j]);
+ in[j] = 1;
+ }
+ disptree(tree);
+ findtest();
+ }
+
+ while (arraylen > 0) {
+ j = randomnumber(&seed);
+ j %= arraylen;
+ deltest(array[j]);
+ }
+
+ freetree234(tree);
+
+ /*
+ * Now try an unsorted tree. We don't really need to test
+ * delpos234 because we know del234 is based on it, so it's
+ * already been tested in the above sorted-tree code; but for
+ * completeness we'll use it to tear down our unsorted tree
+ * once we've built it.
+ */
+ tree = newtree234(NULL);
+ cmp = NULL;
+ verify();
+ for (i = 0; i < 1000; i++) {
+ printf("trial: %d\n", i);
+ j = randomnumber(&seed);
+ j %= NSTR;
+ k = randomnumber(&seed);
+ k %= count234(tree)+1;
+ printf("adding string %s at index %d\n", strings[j], k);
+ addpostest(strings[j], k);
+ }
+
+ /*
+ * While we have this tree in its full form, we'll take a copy
+ * of it to use in split and join testing.
+ */
+ tree2 = copytree234(tree, NULL, NULL);
+ verifytree(tree2, array, arraylen);/* check the copy is accurate */
+ /*
+ * Split tests. Split the tree at every possible point and
+ * check the resulting subtrees.
+ */
+ tworoot = (!tree2->root->elems[1]);/* see if it has a 2-root */
+ splittest(tree2, array, arraylen);
+ /*
+ * Now do the split test again, but on a tree that has a 2-root
+ * (if the previous one didn't) or doesn't (if the previous one
+ * did).
+ */
+ tmplen = arraylen;
+ while ((!tree2->root->elems[1]) == tworoot) {
+ delpos234(tree2, --tmplen);
+ }
+ printf("now trying splits on second tree\n");
+ splittest(tree2, array, tmplen);
+ freetree234(tree2);
+
+ /*
+ * Back to the main testing of uncounted trees.
+ */
+ while (count234(tree) > 0) {
+ printf("cleanup: tree size %d\n", count234(tree));
+ j = randomnumber(&seed);
+ j %= count234(tree);
+ printf("deleting string %s from index %d\n", (char *)array[j], j);
+ delpostest(j);
+ }
+ freetree234(tree);
+
+ /*
+ * Finally, do some testing on split/join on _sorted_ trees. At
+ * the same time, we'll be testing split on very small trees.
+ */
+ tree = newtree234(mycmp);
+ cmp = mycmp;
+ arraylen = 0;
+ for (i = 0; i < 16; i++) {
+ addtest(strings[i]);
+ tree2 = copytree234(tree, NULL, NULL);
+ splittest(tree2, array, arraylen);
+ freetree234(tree2);
+ }
+ freetree234(tree);
+
+ /*
+ * Test silly cases of join: join(emptytree, emptytree), and
+ * also ensure join correctly spots when sorted trees fail the
+ * ordering constraint.
+ */
+ tree = newtree234(mycmp);
+ tree2 = newtree234(mycmp);
+ tree3 = newtree234(mycmp);
+ tree4 = newtree234(mycmp);
+ assert(mycmp(strings[0], strings[1]) < 0); /* just in case :-) */
+ add234(tree2, strings[1]);
+ add234(tree4, strings[0]);
+ array[0] = strings[0];
+ array[1] = strings[1];
+ verifytree(tree, array, 0);
+ verifytree(tree2, array+1, 1);
+ verifytree(tree3, array, 0);
+ verifytree(tree4, array, 1);
+
+ /*
+ * So:
+ * - join(tree,tree3) should leave both tree and tree3 unchanged.
+ * - joinr(tree,tree2) should leave both tree and tree2 unchanged.
+ * - join(tree4,tree3) should leave both tree3 and tree4 unchanged.
+ * - join(tree, tree2) should move the element from tree2 to tree.
+ * - joinr(tree4, tree3) should move the element from tree4 to tree3.
+ * - join(tree,tree3) should return NULL and leave both unchanged.
+ * - join(tree3,tree) should work and create a bigger tree in tree3.
+ */
+ assert(tree == join234(tree, tree3));
+ verifytree(tree, array, 0);
+ verifytree(tree3, array, 0);
+ assert(tree2 == join234r(tree, tree2));
+ verifytree(tree, array, 0);
+ verifytree(tree2, array+1, 1);
+ assert(tree4 == join234(tree4, tree3));
+ verifytree(tree3, array, 0);
+ verifytree(tree4, array, 1);
+ assert(tree == join234(tree, tree2));
+ verifytree(tree, array+1, 1);
+ verifytree(tree2, array, 0);
+ assert(tree3 == join234r(tree4, tree3));
+ verifytree(tree3, array, 1);
+ verifytree(tree4, array, 0);
+ assert(NULL == join234(tree, tree3));
+ verifytree(tree, array+1, 1);
+ verifytree(tree3, array, 1);
+ assert(tree3 == join234(tree3, tree));
+ verifytree(tree3, array, 2);
+ verifytree(tree, array, 0);
+
+ return 0;
+}
+
+#endif
+
+#if 0 /* sorted list of strings might be useful */
+{
+ "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
+}
+#endif
--- /dev/null
+/*
+ * tree234.h: header defining functions in tree234.c.
+ *
+ * This file is copyright 1999-2001 Simon Tatham.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+ * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#ifndef TREE234_H
+#define TREE234_H
+
+/*
+ * This typedef is opaque outside tree234.c itself.
+ */
+typedef struct tree234_Tag tree234;
+
+typedef int (*cmpfn234)(void *, void *);
+
+typedef void *(*copyfn234)(void *state, void *element);
+
+/*
+ * Create a 2-3-4 tree. If `cmp' is NULL, the tree is unsorted, and
+ * lookups by key will fail: you can only look things up by numeric
+ * index, and you have to use addpos234() and delpos234().
+ */
+tree234 *newtree234(cmpfn234 cmp);
+
+/*
+ * Free a 2-3-4 tree (not including freeing the elements).
+ */
+void freetree234(tree234 *t);
+
+/*
+ * Add an element e to a sorted 2-3-4 tree t. Returns e on success,
+ * or if an existing element compares equal, returns that.
+ */
+void *add234(tree234 *t, void *e);
+
+/*
+ * Add an element e to an unsorted 2-3-4 tree t. Returns e on
+ * success, NULL on failure. (Failure should only occur if the
+ * index is out of range or the tree is sorted.)
+ *
+ * Index range can be from 0 to the tree's current element count,
+ * inclusive.
+ */
+void *addpos234(tree234 *t, void *e, int index);
+
+/*
+ * Look up the element at a given numeric index in a 2-3-4 tree.
+ * Returns NULL if the index is out of range.
+ *
+ * One obvious use for this function is in iterating over the whole
+ * of a tree (sorted or unsorted):
+ *
+ * for (i = 0; (p = index234(tree, i)) != NULL; i++) consume(p);
+ *
+ * or
+ *
+ * int maxcount = count234(tree);
+ * for (i = 0; i < maxcount; i++) {
+ * p = index234(tree, i);
+ * assert(p != NULL);
+ * consume(p);
+ * }
+ */
+void *index234(tree234 *t, int index);
+
+/*
+ * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
+ * found. e is always passed as the first argument to cmp, so cmp
+ * can be an asymmetric function if desired. cmp can also be passed
+ * as NULL, in which case the compare function from the tree proper
+ * will be used.
+ *
+ * Three of these functions are special cases of findrelpos234. The
+ * non-`pos' variants lack the `index' parameter: if the parameter
+ * is present and non-NULL, it must point to an integer variable
+ * which will be filled with the numeric index of the returned
+ * element.
+ *
+ * The non-`rel' variants lack the `relation' parameter. This
+ * parameter allows you to specify what relation the element you
+ * provide has to the element you're looking for. This parameter
+ * can be:
+ *
+ * REL234_EQ - find only an element that compares equal to e
+ * REL234_LT - find the greatest element that compares < e
+ * REL234_LE - find the greatest element that compares <= e
+ * REL234_GT - find the smallest element that compares > e
+ * REL234_GE - find the smallest element that compares >= e
+ *
+ * Non-`rel' variants assume REL234_EQ.
+ *
+ * If `rel' is REL234_GT or REL234_LT, the `e' parameter may be
+ * NULL. In this case, REL234_GT will return the smallest element
+ * in the tree, and REL234_LT will return the greatest. This gives
+ * an alternative means of iterating over a sorted tree, instead of
+ * using index234:
+ *
+ * // to loop forwards
+ * for (p = NULL; (p = findrel234(tree, p, NULL, REL234_GT)) != NULL ;)
+ * consume(p);
+ *
+ * // to loop backwards
+ * for (p = NULL; (p = findrel234(tree, p, NULL, REL234_LT)) != NULL ;)
+ * consume(p);
+ */
+enum {
+ REL234_EQ, REL234_LT, REL234_LE, REL234_GT, REL234_GE
+};
+void *find234(tree234 *t, void *e, cmpfn234 cmp);
+void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
+void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
+void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
+ int *index);
+
+/*
+ * Delete an element e in a 2-3-4 tree. Does not free the element,
+ * merely removes all links to it from the tree nodes.
+ *
+ * delpos234 deletes the element at a particular tree index: it
+ * works on both sorted and unsorted trees.
+ *
+ * del234 deletes the element passed to it, so it only works on
+ * sorted trees. (It's equivalent to using findpos234 to determine
+ * the index of an element, and then passing that index to
+ * delpos234.)
+ *
+ * Both functions return a pointer to the element they delete, for
+ * the user to free or pass on elsewhere or whatever. If the index
+ * is out of range (delpos234) or the element is already not in the
+ * tree (del234) then they return NULL.
+ */
+void *del234(tree234 *t, void *e);
+void *delpos234(tree234 *t, int index);
+
+/*
+ * Return the total element count of a tree234.
+ */
+int count234(tree234 *t);
+
+/*
+ * Split a tree234 into two valid tree234s.
+ *
+ * splitpos234 splits at a given index. If `before' is TRUE, the
+ * items at and after that index are left in t and the ones before
+ * are returned; if `before' is FALSE, the items before that index
+ * are left in t and the rest are returned.
+ *
+ * split234 splits at a given key. You can pass any of the
+ * relations used with findrel234, except for REL234_EQ. The items
+ * in the tree that satisfy the relation are returned; the
+ * remainder are left.
+ */
+tree234 *splitpos234(tree234 *t, int index, int before);
+tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
+
+/*
+ * Join two tree234s together into a single one.
+ *
+ * All the elements in t1 are placed to the left of all the
+ * elements in t2. If the trees are sorted, there will be a test to
+ * ensure that this satisfies the ordering criterion, and NULL will
+ * be returned otherwise. If the trees are unsorted, there is no
+ * restriction on the use of join234.
+ *
+ * The tree returned is t1 (join234) or t2 (join234r), if the
+ * operation is successful.
+ */
+tree234 *join234(tree234 *t1, tree234 *t2);
+tree234 *join234r(tree234 *t1, tree234 *t2);
+
+/*
+ * Make a complete copy of a tree234. Element pointers will be
+ * reused unless copyfn is non-NULL, in which case it will be used
+ * to copy each element. (copyfn takes two `void *' parameters; the
+ * first is private state and the second is the element. A simple
+ * copy routine probably won't need private state.)
+ */
+tree234 *copytree234(tree234 *t, copyfn234 copyfn, void *copyfnstate);
+
+#endif /* TREE234_H */
~mdw / sgt / library / commitdiff