X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/720a8fb73f1ec4860da71afb8cf0d18bfddf7691..2711f410eb53e9c632ed3021b41f00120913017b:/tree234.c

diff --git a/tree234.c b/tree234.c
index 93aeccc..4b3151e 100644
--- a/tree234.c
+++ b/tree234.c
@@ -31,13 +31,13 @@
 
 #include "tree234.h"
 
-#define smalloc malloc
-#define sfree free
-
-#define mknew(typ) ( (typ *) smalloc (sizeof (typ)) )
+#include "puzzles.h"		       /* for smalloc/sfree */
 
 #ifdef TEST
 #define LOG(x) (printf x)
+#define smalloc malloc
+#define srealloc realloc
+#define sfree free
 #else
 #define LOG(x)
 #endif
@@ -60,7 +60,7 @@ struct node234_Tag {
  * Create a 2-3-4 tree.
  */
 tree234 *newtree234(cmpfn234 cmp) {
-    tree234 *ret = mknew(tree234);
+    tree234 *ret = snew(tree234);
     LOG(("created tree %p\n", ret));
     ret->root = NULL;
     ret->cmp = cmp;
@@ -187,7 +187,7 @@ static int add234_insert(node234 *left, void *e, node234 *right,
 	    LOG(("  done\n"));
 	    break;
 	} else {
-	    node234 *m = mknew(node234);
+	    node234 *m = snew(node234);
 	    m->parent = n->parent;
 	    LOG(("  splitting a 4-node; created new node %p\n", m));
 	    /*
@@ -283,7 +283,7 @@ static int add234_insert(node234 *left, void *e, node234 *right,
 	return 0;		       /* root unchanged */
     } else {
 	LOG(("  root is overloaded, split into two\n"));
-	(*root) = mknew(node234);
+	(*root) = snew(node234);
 	(*root)->kids[0] = left;     (*root)->counts[0] = lcount;
 	(*root)->elems[0] = e;
 	(*root)->kids[1] = right;    (*root)->counts[1] = rcount;
@@ -314,7 +314,7 @@ static void *add234_internal(tree234 *t, void *e, int index) {
 
     LOG(("adding element \"%s\" to tree %p\n", e, t));
     if (t->root == NULL) {
-	t->root = mknew(node234);
+	t->root = snew(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;
@@ -1040,7 +1040,7 @@ static node234 *join234_internal(node234 *left, void *sep,
 	 * nodes.
 	 */
 	node234 *newroot;
-	newroot = mknew(node234);
+	newroot = snew(node234);
 	newroot->kids[0] = left;     newroot->counts[0] = countnode234(left);
 	newroot->elems[0] = sep;
 	newroot->kids[1] = right;    newroot->counts[1] = countnode234(right);
@@ -1160,7 +1160,7 @@ tree234 *join234r(tree234 *t1, tree234 *t2) {
  * in t.
  */
 static node234 *split234_internal(tree234 *t, int index) {
-    node234 *halves[2], *n, *sib, *sub;
+    node234 *halves[2] = { NULL, NULL }, *n, *sib, *sub;
     node234 *lparent, *rparent;
     int ki, pki, i, half, lcount, rcount;
 
@@ -1182,6 +1182,7 @@ static node234 *split234_internal(tree234 *t, int index) {
     /*
      * Search down the tree to find the split point.
      */
+    halves[0] = halves[1] = NULL;
     lparent = rparent = NULL;
     pki = -1;
     while (n) {
@@ -1216,7 +1217,7 @@ static node234 *split234_internal(tree234 *t, int index) {
 	 * new node pointers in halves[0] and halves[1], and go up
 	 * a level.
 	 */
-	sib = mknew(node234);
+	sib = snew(node234);
 	for (i = 0; i < 3; i++) {
 	    if (i+ki < 3 && n->elems[i+ki]) {
 		sib->elems[i] = n->elems[i+ki];
@@ -1273,6 +1274,8 @@ static node234 *split234_internal(tree234 *t, int index) {
      */
     LOG(("  fell off bottom, lroot is %p, rroot is %p\n",
 	 halves[0], halves[1]));
+    assert(halves[0] != NULL);
+    assert(halves[1] != NULL);
     lparent->counts[pki] = rparent->counts[0] = 0;
     lparent->kids[pki] = rparent->kids[0] = NULL;
 
@@ -1416,7 +1419,7 @@ tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel) {
 
 static node234 *copynode234(node234 *n, copyfn234 copyfn, void *copyfnstate) {
     int i;
-    node234 *n2 = mknew(node234);
+    node234 *n2 = snew(node234);
 
     for (i = 0; i < 3; i++) {
 	if (n->elems[i] && copyfn)
@@ -1441,8 +1444,11 @@ 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;
+    if (t->root) {
+	t2->root = copynode234(t->root, copyfn, copyfnstate);
+	t2->root->parent = NULL;
+    } else
+	t2->root = NULL;
 
     return t2;
 }
@@ -1472,6 +1478,7 @@ tree234 *copytree234(tree234 *t, copyfn234 copyfn, void *copyfnstate) {
  * if not.)
  */
 
+#include <string.h>
 #include <stdarg.h>
 
 #define srealloc realloc
@@ -1888,8 +1895,6 @@ int mycmp(void *av, void *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",
@@ -2123,11 +2128,12 @@ int main(void) {
     tree = newtree234(mycmp);
     cmp = mycmp;
     arraylen = 0;
-    for (i = 0; i < 16; i++) {
-	addtest(strings[i]);
+    for (i = 0; i < 17; i++) {
 	tree2 = copytree234(tree, NULL, NULL);
 	splittest(tree2, array, arraylen);
 	freetree234(tree2);
+	if (i < 16)
+	    addtest(strings[i]);
     }
     freetree234(tree);