n = t->root;
while (n) {
- if ( (c = t->cmp(e, n->elems[0])) < 0)
+ if ( (c = cmp(e, n->elems[0])) < 0)
n = n->kids[0];
else if (c == 0)
return n->elems[0];
- else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
+ else if (n->elems[1] == NULL || (c = cmp(e, n->elems[1])) < 0)
n = n->kids[1];
else if (c == 0)
return n->elems[1];
- else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
+ else if (n->elems[2] == NULL || (c = cmp(e, n->elems[2])) < 0)
n = n->kids[2];
else if (c == 0)
return n->elems[2];
* 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.
*/
-void *del234(tree234 *t, void *e) {
+void del234(tree234 *t, void *e) {
node234 *n;
int ei = -1;
sub->kids[1] = sub->kids[0];
sub->elems[0] = n->elems[ki-1];
sub->kids[0] = sib->kids[lastelem+1];
+ if (sub->kids[0]) sub->kids[0]->parent = sub;
n->elems[ki-1] = sib->elems[lastelem];
sib->kids[lastelem+1] = NULL;
sib->elems[lastelem] = NULL;
int j;
sub->elems[1] = n->elems[ki];
sub->kids[2] = sib->kids[0];
+ if (sub->kids[2]) sub->kids[2]->parent = sub;
n->elems[ki] = sib->elems[0];
sib->kids[0] = sib->kids[1];
for (j = 0; j < 2 && sib->elems[j+1]; j++) {
sub->kids[2] = sub->kids[0];
sub->elems[1] = n->elems[ki];
sub->kids[1] = sib->kids[1];
+ if (sub->kids[1]) sub->kids[1]->parent = sub;
sub->elems[0] = sib->elems[0];
sub->kids[0] = sib->kids[0];
+ if (sub->kids[0]) sub->kids[0]->parent = sub;
sfree(sib);
*/
int i;
LOG((" case 1\n"));
- for (i = ei; i < 3 && n->elems[i+1]; i++)
+ for (i = ei; i < 2 && n->elems[i+1]; i++)
n->elems[i] = n->elems[i+1];
n->elems[i] = NULL;
return; /* finished! */
LOG((" case 2c\n"));
a->elems[1] = n->elems[ei];
a->kids[2] = b->kids[0];
+ if (a->kids[2]) a->kids[2]->parent = a;
a->elems[2] = b->elems[0];
a->kids[3] = b->kids[1];
+ if (a->kids[3]) a->kids[3]->parent = a;
sfree(b);
/*
* That's built the big node in a, and destroyed b. Now
return n->elems[0];
}
- if (pos == 0 && n->elems[1]) {
- e->posn = 1;
- return n->elems[1];
+ if (pos < 2 && n->elems[pos+1]) {
+ e->posn = pos+1;
+ return n->elems[e->posn];
}
do {