#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
* 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;
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));
/*
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;
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;
* 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);
* 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;
/*
* Search down the tree to find the split point.
*/
+ halves[0] = halves[1] = NULL;
lparent = rparent = NULL;
pki = -1;
while (n) {
* 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];
*/
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;
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)
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;
}
* if not.)
*/
+#include <string.h>
#include <stdarg.h>
#define srealloc realloc
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",
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);