Further development; mid-end index handling pretty much there!

[originally from svn r238]

1 files changed, 271 insertions, 0 deletions

diff --git a/tree23.c b/tree23.c
new file mode 100644
index 0000000..4a0d60c
--- /dev/null
+++ b/tree23.c
@@ -0,0 +1,271 @@
+/*
+ * tree23.c: reasonably generic 2-3 tree routines. Currently only
+ * supports insert and find operations.
+ */
+
+#include <stdio.h>		       /* we only need this for NULL :-) */
+
+/*
+ * This module should be easily de-Buttressable. All it relies on
+ * from the rest of Buttress is the macro `mknew':
+ *
+ *   #define mknew(typ) ( (typ *) malloc_like_function (sizeof (typ)) )
+ *
+ * and the free-like function `sfree'.
+ */
+#include "buttress.h"
+
+typedef struct node23_Tag node23;
+/* typedef struct tree23_Tag tree23; */
+
+struct tree23_Tag {
+    node23 *root;
+};
+
+struct node23_Tag {
+    node23 *parent;
+    node23 *kids[3];
+    void *elems[2];
+};
+
+/*
+ * Create a 2-3 tree.
+ */
+tree23 *newtree23(void) {
+    tree23 *ret = mknew(tree23);
+    ret->root = NULL;
+    return ret;
+}
+
+/*
+ * Free a 2-3 tree (not including freeing the elements).
+ */
+static void freenode23(node23 *n) {
+    if (!n)
+	return;
+    freenode23(n->kids[0]);
+    freenode23(n->kids[1]);
+    freenode23(n->kids[2]);
+    sfree(n);
+}
+void freetree23(tree23 *t) {
+    freenode23(t->root);
+    sfree(t);
+}
+
+/*
+ * Add an element e to a 2-3 tree t. Returns e on success, or if an
+ * existing element compares equal, returns that.
+ */
+void *add23(tree23 *t, void *e, int (*cmp)(void *, void *)) {
+    node23 *n, **np, *left, *right;
+    void *orig_e = e;
+    int c;
+
+    if (t->root == NULL) {
+	t->root = mknew(node23);
+	t->root->elems[1] = NULL;
+	t->root->kids[0] = t->root->kids[1] = t->root->kids[2] = NULL;
+	t->root->parent = NULL;
+	t->root->elems[0] = e;
+	return orig_e;
+    }
+
+    np = &t->root;
+    while (*np) {
+	n = *np;
+	c = cmp(e, n->elems[0]);
+	if (c == 0) {
+	    /* node already exists; return existing one */
+	    return n->elems[0];
+	} else if (c < 0) {
+	    np = &n->kids[0];
+	} else {
+	    if (n->elems[1] == NULL || (c = cmp(e, n->elems[1])) < 0)
+		np = &n->kids[1];
+	    else if (c > 0)
+		np = &n->kids[2];
+	    else {
+		/* node already exists; return existing one */
+		return n->elems[1];
+	    }
+	}
+    }
+
+    /*
+     * We need to insert the new element in n at position np.
+     */
+    left = NULL;
+    right = NULL;
+    while (n) {
+	if (n->elems[1] == NULL) {
+	    /*
+	     * Insert in a 2-node; simple.
+	     */
+	    if (np == &n->kids[0]) {
+		n->kids[2] = n->kids[1];
+		n->elems[1] = n->elems[0];
+		n->kids[1] = right;
+		n->elems[0] = e;
+		n->kids[0] = left;
+	    } else { /* np == &n->kids[1] */
+		n->kids[2] = right;
+		n->elems[1] = e;
+		n->kids[1] = left;
+	    }
+	    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;
+	    break;
+	} else {
+	    node23 *m = mknew(node23);
+	    m->parent = n->parent;
+	    /*
+	     * Insert in a 3-node; split into two 2-nodes and move
+	     * focus up a level.
+	     */
+	    if (np == &n->kids[0]) {
+		m->kids[0] = left;
+		m->elems[0] = e;
+		m->kids[1] = right;
+		e = n->elems[0];
+		n->kids[0] = n->kids[1];
+		n->elems[0] = n->elems[1];
+		n->kids[1] = n->kids[2];
+	    } else if (np == &n->kids[1]) {
+		m->kids[0] = n->kids[0];
+		m->elems[0] = n->elems[0];
+		m->kids[1] = left;
+		/* e = e; */
+		n->kids[0] = right;
+		n->elems[0] = n->elems[1];
+		n->kids[1] = n->kids[2];
+	    } else { /* np == &n->kids[2] */
+		m->kids[0] = n->kids[0];
+		m->elems[0] = n->elems[0];
+		m->kids[1] = n->kids[1];
+		n->kids[0] = left;
+		n->elems[0] = e;
+		n->kids[1] = right;
+		e = n->elems[1];
+	    }
+	    m->kids[2] = n->kids[2] = NULL;
+	    m->elems[1] = n->elems[1] = NULL;
+	    if (m->kids[0]) m->kids[0]->parent = m;
+	    if (m->kids[1]) m->kids[1]->parent = m;
+	    if (n->kids[0]) n->kids[0]->parent = n;
+	    if (n->kids[1]) n->kids[1]->parent = n;
+	    left = m;
+	    right = n;
+	}
+	if (n->parent)
+	    np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
+		  n->parent->kids[1] == n ? &n->parent->kids[1] :
+		  &n->parent->kids[2]);
+	n = n->parent;
+    }
+
+    /*
+     * If we've come out of here by `break', n will still be
+     * non-NULL and we've finished. 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) {
+	t->root = mknew(node23);
+	t->root->kids[0] = left;
+	t->root->elems[0] = e;
+	t->root->kids[1] = right;
+	t->root->elems[1] = NULL;
+	t->root->kids[2] = NULL;
+	t->root->parent = NULL;
+	if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
+	if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
+    }
+
+    return orig_e;
+}
+
+/*
+ * Find an element e in a 2-3 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.
+ */
+void *find23(tree23 *t, void *e, int (*cmp)(void *, void *)) {
+    node23 *n;
+    int c;
+
+    if (t->root == NULL)
+	return NULL;
+
+    n = t->root;
+    while (n) {
+	c = cmp(e, n->elems[0]);
+	if (c == 0) {
+	    return n->elems[0];
+	} else if (c < 0) {
+	    n = n->kids[0];
+	} else {
+	    if (n->elems[1] == NULL || (c = cmp(e, n->elems[1])) < 0)
+		n = n->kids[1];
+	    else if (c > 0)
+		n = n->kids[2];
+	    else {
+		return n->elems[1];
+	    }
+	}
+    }
+
+    /*
+     * We've found our way to the bottom of the tree and we know
+     * where we would insert this node if we wanted to. But it
+     * isn't there.
+     */
+    return NULL;
+}
+
+/*
+ * Iterate over the elements of a tree23, in order.
+ */
+void *first23(tree23 *t, enum23 *e) {
+    node23 *n = t->root;
+    if (!n)
+	return NULL;
+    while (n->kids[0])
+	n = n->kids[0];
+    e->node = n;
+    e->posn = 0;
+    return n->elems[0];
+}
+
+void *next23(tree23 *t, enum23 *e) {
+    node23 *n = (node23 *)e->node;
+    int pos = e->posn;
+
+    if (n->kids[pos+1]) {
+	n = n->kids[pos+1];
+	while (n->kids[0])
+	    n = n->kids[0];
+	e->node = n;
+	e->posn = 0;
+	return n->elems[0];
+    }
+
+    if (pos == 0 && n->elems[1]) {
+	e->posn = 1;
+	return n->elems[1];
+    }
+
+    do {
+	node23 *nn = n->parent;
+	if (nn == NULL)
+	    return NULL;	       /* end of tree */
+	pos = (nn->kids[0] == n ? 0 :
+	       nn->kids[1] == n ? 1 : 2);
+	n = nn;
+    } while (pos == 2 || n->kids[pos+1] == NULL);
+
+    e->node = n;
+    e->posn = pos;
+    return n->elems[pos];
+}