2 * tree234.c: reasonably generic counted 2-3-4 tree routines.
4 * This file is copyright 1999-2001 Simon Tatham.
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or
11 * sell copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
23 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
24 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
34 #define smalloc malloc
37 #define mknew(typ) ( (typ *) smalloc (sizeof (typ)) )
40 #define LOG(x) (printf x)
45 typedef struct node234_Tag node234;
60 * Create a 2-3-4 tree.
62 tree234 *newtree234(cmpfn234 cmp) {
63 tree234 *ret = mknew(tree234);
64 LOG(("created tree %p\n", ret));
71 * Free a 2-3-4 tree (not including freeing the elements).
73 static void freenode234(node234 *n) {
76 freenode234(n->kids[0]);
77 freenode234(n->kids[1]);
78 freenode234(n->kids[2]);
79 freenode234(n->kids[3]);
82 void freetree234(tree234 *t) {
88 * Internal function to count a node.
90 static int countnode234(node234 *n) {
95 for (i = 0; i < 4; i++)
96 count += n->counts[i];
97 for (i = 0; i < 3; i++)
104 * Count the elements in a tree.
106 int count234(tree234 *t) {
108 return countnode234(t->root);
114 * Add an element e to a 2-3-4 tree t. Returns e on success, or if
115 * an existing element compares equal, returns that.
117 static void *add234_internal(tree234 *t, void *e, int index) {
118 node234 *n, **np, *left, *right;
120 int c, lcount, rcount;
122 LOG(("adding node %p to tree %p\n", e, t));
123 if (t->root == NULL) {
124 t->root = mknew(node234);
125 t->root->elems[1] = t->root->elems[2] = NULL;
126 t->root->kids[0] = t->root->kids[1] = NULL;
127 t->root->kids[2] = t->root->kids[3] = NULL;
128 t->root->counts[0] = t->root->counts[1] = 0;
129 t->root->counts[2] = t->root->counts[3] = 0;
130 t->root->parent = NULL;
131 t->root->elems[0] = e;
132 LOG((" created root %p\n", t->root));
140 LOG((" node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d\n",
142 n->kids[0], n->counts[0], n->elems[0],
143 n->kids[1], n->counts[1], n->elems[1],
144 n->kids[2], n->counts[2], n->elems[2],
145 n->kids[3], n->counts[3]));
149 * Leaf node. We want to insert at kid position
150 * equal to the index:
157 * Internal node. We always descend through it (add
158 * always starts at the bottom, never in the
161 do { /* this is a do ... while (0) to allow `break' */
162 if (index <= n->counts[0]) {
166 index -= n->counts[0] + 1;
167 if (index <= n->counts[1]) {
171 index -= n->counts[1] + 1;
172 if (index <= n->counts[2]) {
176 index -= n->counts[2] + 1;
177 if (index <= n->counts[3]) {
181 return NULL; /* error: index out of range */
185 if ((c = t->cmp(e, n->elems[0])) < 0)
188 return n->elems[0]; /* already exists */
189 else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
192 return n->elems[1]; /* already exists */
193 else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
196 return n->elems[2]; /* already exists */
200 np = &n->kids[childnum];
201 LOG((" moving to child %d (%p)\n", childnum, *np));
205 * We need to insert the new element in n at position np.
207 left = NULL; lcount = 0;
208 right = NULL; rcount = 0;
210 LOG((" at %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d\n",
212 n->kids[0], n->counts[0], n->elems[0],
213 n->kids[1], n->counts[1], n->elems[1],
214 n->kids[2], n->counts[2], n->elems[2],
215 n->kids[3], n->counts[3]));
216 LOG((" need to insert %p/%d [%p] %p/%d at position %d\n",
217 left, lcount, e, right, rcount, np - n->kids));
218 if (n->elems[1] == NULL) {
220 * Insert in a 2-node; simple.
222 if (np == &n->kids[0]) {
223 LOG((" inserting on left of 2-node\n"));
224 n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
225 n->elems[1] = n->elems[0];
226 n->kids[1] = right; n->counts[1] = rcount;
228 n->kids[0] = left; n->counts[0] = lcount;
229 } else { /* np == &n->kids[1] */
230 LOG((" inserting on right of 2-node\n"));
231 n->kids[2] = right; n->counts[2] = rcount;
233 n->kids[1] = left; n->counts[1] = lcount;
235 if (n->kids[0]) n->kids[0]->parent = n;
236 if (n->kids[1]) n->kids[1]->parent = n;
237 if (n->kids[2]) n->kids[2]->parent = n;
240 } else if (n->elems[2] == NULL) {
242 * Insert in a 3-node; simple.
244 if (np == &n->kids[0]) {
245 LOG((" inserting on left of 3-node\n"));
246 n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
247 n->elems[2] = n->elems[1];
248 n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
249 n->elems[1] = n->elems[0];
250 n->kids[1] = right; n->counts[1] = rcount;
252 n->kids[0] = left; n->counts[0] = lcount;
253 } else if (np == &n->kids[1]) {
254 LOG((" inserting in middle of 3-node\n"));
255 n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
256 n->elems[2] = n->elems[1];
257 n->kids[2] = right; n->counts[2] = rcount;
259 n->kids[1] = left; n->counts[1] = lcount;
260 } else { /* np == &n->kids[2] */
261 LOG((" inserting on right of 3-node\n"));
262 n->kids[3] = right; n->counts[3] = rcount;
264 n->kids[2] = left; n->counts[2] = lcount;
266 if (n->kids[0]) n->kids[0]->parent = n;
267 if (n->kids[1]) n->kids[1]->parent = n;
268 if (n->kids[2]) n->kids[2]->parent = n;
269 if (n->kids[3]) n->kids[3]->parent = n;
273 node234 *m = mknew(node234);
274 m->parent = n->parent;
275 LOG((" splitting a 4-node; created new node %p\n", m));
277 * Insert in a 4-node; split into a 2-node and a
278 * 3-node, and move focus up a level.
280 * I don't think it matters which way round we put the
281 * 2 and the 3. For simplicity, we'll put the 3 first
284 if (np == &n->kids[0]) {
285 m->kids[0] = left; m->counts[0] = lcount;
287 m->kids[1] = right; m->counts[1] = rcount;
288 m->elems[1] = n->elems[0];
289 m->kids[2] = n->kids[1]; m->counts[2] = n->counts[1];
291 n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
292 n->elems[0] = n->elems[2];
293 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
294 } else if (np == &n->kids[1]) {
295 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
296 m->elems[0] = n->elems[0];
297 m->kids[1] = left; m->counts[1] = lcount;
299 m->kids[2] = right; m->counts[2] = rcount;
301 n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
302 n->elems[0] = n->elems[2];
303 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
304 } else if (np == &n->kids[2]) {
305 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
306 m->elems[0] = n->elems[0];
307 m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
308 m->elems[1] = n->elems[1];
309 m->kids[2] = left; m->counts[2] = lcount;
311 n->kids[0] = right; n->counts[0] = rcount;
312 n->elems[0] = n->elems[2];
313 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
314 } else { /* np == &n->kids[3] */
315 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
316 m->elems[0] = n->elems[0];
317 m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
318 m->elems[1] = n->elems[1];
319 m->kids[2] = n->kids[2]; m->counts[2] = n->counts[2];
320 n->kids[0] = left; n->counts[0] = lcount;
322 n->kids[1] = right; n->counts[1] = rcount;
325 m->kids[3] = n->kids[3] = n->kids[2] = NULL;
326 m->counts[3] = n->counts[3] = n->counts[2] = 0;
327 m->elems[2] = n->elems[2] = n->elems[1] = NULL;
328 if (m->kids[0]) m->kids[0]->parent = m;
329 if (m->kids[1]) m->kids[1]->parent = m;
330 if (m->kids[2]) m->kids[2]->parent = m;
331 if (n->kids[0]) n->kids[0]->parent = n;
332 if (n->kids[1]) n->kids[1]->parent = n;
333 LOG((" left (%p): %p/%d [%p] %p/%d [%p] %p/%d\n", m,
334 m->kids[0], m->counts[0], m->elems[0],
335 m->kids[1], m->counts[1], m->elems[1],
336 m->kids[2], m->counts[2]));
337 LOG((" right (%p): %p/%d [%p] %p/%d\n", n,
338 n->kids[0], n->counts[0], n->elems[0],
339 n->kids[1], n->counts[1]));
340 left = m; lcount = countnode234(left);
341 right = n; rcount = countnode234(right);
344 np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
345 n->parent->kids[1] == n ? &n->parent->kids[1] :
346 n->parent->kids[2] == n ? &n->parent->kids[2] :
347 &n->parent->kids[3]);
352 * If we've come out of here by `break', n will still be
353 * non-NULL and all we need to do is go back up the tree
354 * updating counts. If we've come here because n is NULL, we
355 * need to create a new root for the tree because the old one
356 * has just split into two. */
359 int count = countnode234(n);
361 childnum = (n->parent->kids[0] == n ? 0 :
362 n->parent->kids[1] == n ? 1 :
363 n->parent->kids[2] == n ? 2 : 3);
364 n->parent->counts[childnum] = count;
368 LOG((" root is overloaded, split into two\n"));
369 t->root = mknew(node234);
370 t->root->kids[0] = left; t->root->counts[0] = lcount;
371 t->root->elems[0] = e;
372 t->root->kids[1] = right; t->root->counts[1] = rcount;
373 t->root->elems[1] = NULL;
374 t->root->kids[2] = NULL; t->root->counts[2] = 0;
375 t->root->elems[2] = NULL;
376 t->root->kids[3] = NULL; t->root->counts[3] = 0;
377 t->root->parent = NULL;
378 if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
379 if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
380 LOG((" new root is %p/%d [%p] %p/%d\n",
381 t->root->kids[0], t->root->counts[0],
383 t->root->kids[1], t->root->counts[1]));
389 void *add234(tree234 *t, void *e) {
390 if (!t->cmp) /* tree is unsorted */
393 return add234_internal(t, e, -1);
395 void *addpos234(tree234 *t, void *e, int index) {
396 if (index < 0 || /* index out of range */
397 t->cmp) /* tree is sorted */
398 return NULL; /* return failure */
400 return add234_internal(t, e, index); /* this checks the upper bound */
404 * Look up the element at a given numeric index in a 2-3-4 tree.
405 * Returns NULL if the index is out of range.
407 void *index234(tree234 *t, int index) {
411 return NULL; /* tree is empty */
413 if (index < 0 || index >= countnode234(t->root))
414 return NULL; /* out of range */
419 if (index < n->counts[0])
421 else if (index -= n->counts[0] + 1, index < 0)
423 else if (index < n->counts[1])
425 else if (index -= n->counts[1] + 1, index < 0)
427 else if (index < n->counts[2])
429 else if (index -= n->counts[2] + 1, index < 0)
435 /* We shouldn't ever get here. I wonder how we did. */
440 * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
441 * found. e is always passed as the first argument to cmp, so cmp
442 * can be an asymmetric function if desired. cmp can also be passed
443 * as NULL, in which case the compare function from the tree proper
446 void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp,
447 int relation, int *index) {
451 int idx, ecount, kcount, cmpret;
461 * Attempt to find the element itself.
466 * Prepare a fake `cmp' result if e is NULL.
470 assert(relation == REL234_LT || relation == REL234_GT);
471 if (relation == REL234_LT)
472 cmpret = +1; /* e is a max: always greater */
473 else if (relation == REL234_GT)
474 cmpret = -1; /* e is a min: always smaller */
477 for (kcount = 0; kcount < 4; kcount++) {
478 if (kcount >= 3 || n->elems[kcount] == NULL ||
479 (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
482 if (n->kids[kcount]) idx += n->counts[kcount];
499 * We have found the element we're looking for. It's
500 * n->elems[ecount], at tree index idx. If our search
501 * relation is EQ, LE or GE we can now go home.
503 if (relation != REL234_LT && relation != REL234_GT) {
504 if (index) *index = idx;
505 return n->elems[ecount];
509 * Otherwise, we'll do an indexed lookup for the previous
510 * or next element. (It would be perfectly possible to
511 * implement these search types in a non-counted tree by
512 * going back up from where we are, but far more fiddly.)
514 if (relation == REL234_LT)
520 * We've found our way to the bottom of the tree and we
521 * know where we would insert this node if we wanted to:
522 * we'd put it in in place of the (empty) subtree
523 * n->kids[kcount], and it would have index idx
525 * But the actual element isn't there. So if our search
526 * relation is EQ, we're doomed.
528 if (relation == REL234_EQ)
532 * Otherwise, we must do an index lookup for index idx-1
533 * (if we're going left - LE or LT) or index idx (if we're
534 * going right - GE or GT).
536 if (relation == REL234_LT || relation == REL234_LE) {
542 * We know the index of the element we want; just call index234
543 * to do the rest. This will return NULL if the index is out of
544 * bounds, which is exactly what we want.
546 ret = index234(t, idx);
547 if (ret && index) *index = idx;
550 void *find234(tree234 *t, void *e, cmpfn234 cmp) {
551 return findrelpos234(t, e, cmp, REL234_EQ, NULL);
553 void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) {
554 return findrelpos234(t, e, cmp, relation, NULL);
556 void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) {
557 return findrelpos234(t, e, cmp, REL234_EQ, index);
561 * Delete an element e in a 2-3-4 tree. Does not free the element,
562 * merely removes all links to it from the tree nodes.
564 static void *delpos234_internal(tree234 *t, int index) {
572 LOG(("deleting item %d from tree %p\n", index, t));
578 LOG((" node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d index=%d\n",
580 n->kids[0], n->counts[0], n->elems[0],
581 n->kids[1], n->counts[1], n->elems[1],
582 n->kids[2], n->counts[2], n->elems[2],
583 n->kids[3], n->counts[3],
585 if (index < n->counts[0]) {
587 } else if (index -= n->counts[0]+1, index < 0) {
589 } else if (index < n->counts[1]) {
591 } else if (index -= n->counts[1]+1, index < 0) {
593 } else if (index < n->counts[2]) {
595 } else if (index -= n->counts[2]+1, index < 0) {
601 * Recurse down to subtree ki. If it has only one element,
602 * we have to do some transformation to start with.
604 LOG((" moving to subtree %d\n", ki));
606 if (!sub->elems[1]) {
607 LOG((" subtree has only one element!\n", ki));
608 if (ki > 0 && n->kids[ki-1]->elems[1]) {
610 * Case 3a, left-handed variant. Child ki has
611 * only one element, but child ki-1 has two or
612 * more. So we need to move a subtree from ki-1
617 * [more] a A b B c d D e [more] a A b c C d D e
619 node234 *sib = n->kids[ki-1];
620 int lastelem = (sib->elems[2] ? 2 :
621 sib->elems[1] ? 1 : 0);
622 sub->kids[2] = sub->kids[1];
623 sub->counts[2] = sub->counts[1];
624 sub->elems[1] = sub->elems[0];
625 sub->kids[1] = sub->kids[0];
626 sub->counts[1] = sub->counts[0];
627 sub->elems[0] = n->elems[ki-1];
628 sub->kids[0] = sib->kids[lastelem+1];
629 sub->counts[0] = sib->counts[lastelem+1];
630 if (sub->kids[0]) sub->kids[0]->parent = sub;
631 n->elems[ki-1] = sib->elems[lastelem];
632 sib->kids[lastelem+1] = NULL;
633 sib->counts[lastelem+1] = 0;
634 sib->elems[lastelem] = NULL;
635 n->counts[ki] = countnode234(sub);
636 LOG((" case 3a left\n"));
637 LOG((" index and left subtree count before adjustment: %d, %d\n",
638 index, n->counts[ki-1]));
639 index += n->counts[ki-1];
640 n->counts[ki-1] = countnode234(sib);
641 index -= n->counts[ki-1];
642 LOG((" index and left subtree count after adjustment: %d, %d\n",
643 index, n->counts[ki-1]));
644 } else if (ki < 3 && n->kids[ki+1] &&
645 n->kids[ki+1]->elems[1]) {
647 * Case 3a, right-handed variant. ki has only
648 * one element but ki+1 has two or more. Move a
649 * subtree from ki+1 to ki.
653 * a A b c C d D e [more] a A b B c d D e [more]
655 node234 *sib = n->kids[ki+1];
657 sub->elems[1] = n->elems[ki];
658 sub->kids[2] = sib->kids[0];
659 sub->counts[2] = sib->counts[0];
660 if (sub->kids[2]) sub->kids[2]->parent = sub;
661 n->elems[ki] = sib->elems[0];
662 sib->kids[0] = sib->kids[1];
663 sib->counts[0] = sib->counts[1];
664 for (j = 0; j < 2 && sib->elems[j+1]; j++) {
665 sib->kids[j+1] = sib->kids[j+2];
666 sib->counts[j+1] = sib->counts[j+2];
667 sib->elems[j] = sib->elems[j+1];
669 sib->kids[j+1] = NULL;
670 sib->counts[j+1] = 0;
671 sib->elems[j] = NULL;
672 n->counts[ki] = countnode234(sub);
673 n->counts[ki+1] = countnode234(sib);
674 LOG((" case 3a right\n"));
677 * Case 3b. ki has only one element, and has no
678 * neighbour with more than one. So pick a
679 * neighbour and merge it with ki, taking an
680 * element down from n to go in the middle.
684 * a A b c C d a A b B c C d
686 * (Since at all points we have avoided
687 * descending to a node with only one element,
688 * we can be sure that n is not reduced to
689 * nothingness by this move, _unless_ it was
690 * the very first node, ie the root of the
691 * tree. In that case we remove the now-empty
692 * root and replace it with its single large
700 index += n->counts[ki] + 1;
705 sub->kids[3] = sub->kids[1];
706 sub->counts[3] = sub->counts[1];
707 sub->elems[2] = sub->elems[0];
708 sub->kids[2] = sub->kids[0];
709 sub->counts[2] = sub->counts[0];
710 sub->elems[1] = n->elems[ki];
711 sub->kids[1] = sib->kids[1];
712 sub->counts[1] = sib->counts[1];
713 if (sub->kids[1]) sub->kids[1]->parent = sub;
714 sub->elems[0] = sib->elems[0];
715 sub->kids[0] = sib->kids[0];
716 sub->counts[0] = sib->counts[0];
717 if (sub->kids[0]) sub->kids[0]->parent = sub;
719 n->counts[ki+1] = countnode234(sub);
724 * That's built the big node in sub. Now we
725 * need to remove the reference to sib in n.
727 for (j = ki; j < 3 && n->kids[j+1]; j++) {
728 n->kids[j] = n->kids[j+1];
729 n->counts[j] = n->counts[j+1];
730 n->elems[j] = j<2 ? n->elems[j+1] : NULL;
734 if (j < 3) n->elems[j] = NULL;
735 LOG((" case 3b ki=%d\n", ki));
739 * The root is empty and needs to be
742 LOG((" shifting root!\n"));
752 retval = n->elems[ei];
755 return NULL; /* although this shouldn't happen */
758 * Treat special case: this is the one remaining item in
759 * the tree. n is the tree root (no parent), has one
760 * element (no elems[1]), and has no kids (no kids[0]).
762 if (!n->parent && !n->elems[1] && !n->kids[0]) {
763 LOG((" removed last element in tree\n"));
770 * Now we have the element we want, as n->elems[ei], and we
771 * have also arranged for that element not to be the only
772 * one in its node. So...
775 if (!n->kids[0] && n->elems[1]) {
777 * Case 1. n is a leaf node with more than one element,
778 * so it's _really easy_. Just delete the thing and
783 for (i = ei; i < 2 && n->elems[i+1]; i++)
784 n->elems[i] = n->elems[i+1];
787 * Having done that to the leaf node, we now go back up
788 * the tree fixing the counts.
792 childnum = (n->parent->kids[0] == n ? 0 :
793 n->parent->kids[1] == n ? 1 :
794 n->parent->kids[2] == n ? 2 : 3);
795 n->parent->counts[childnum]--;
798 return retval; /* finished! */
799 } else if (n->kids[ei]->elems[1]) {
801 * Case 2a. n is an internal node, and the root of the
802 * subtree to the left of e has more than one element.
803 * So find the predecessor p to e (ie the largest node
804 * in that subtree), place it where e currently is, and
805 * then start the deletion process over again on the
806 * subtree with p as target.
808 node234 *m = n->kids[ei];
812 m = (m->kids[3] ? m->kids[3] :
813 m->kids[2] ? m->kids[2] :
814 m->kids[1] ? m->kids[1] : m->kids[0]);
816 target = (m->elems[2] ? m->elems[2] :
817 m->elems[1] ? m->elems[1] : m->elems[0]);
818 n->elems[ei] = target;
819 index = n->counts[ei]-1;
821 } else if (n->kids[ei+1]->elems[1]) {
823 * Case 2b, symmetric to 2a but s/left/right/ and
824 * s/predecessor/successor/. (And s/largest/smallest/).
826 node234 *m = n->kids[ei+1];
832 target = m->elems[0];
833 n->elems[ei] = target;
838 * Case 2c. n is an internal node, and the subtrees to
839 * the left and right of e both have only one element.
840 * So combine the two subnodes into a single big node
841 * with their own elements on the left and right and e
842 * in the middle, then restart the deletion process on
843 * that subtree, with e still as target.
845 node234 *a = n->kids[ei], *b = n->kids[ei+1];
849 a->elems[1] = n->elems[ei];
850 a->kids[2] = b->kids[0];
851 a->counts[2] = b->counts[0];
852 if (a->kids[2]) a->kids[2]->parent = a;
853 a->elems[2] = b->elems[0];
854 a->kids[3] = b->kids[1];
855 a->counts[3] = b->counts[1];
856 if (a->kids[3]) a->kids[3]->parent = a;
858 n->counts[ei] = countnode234(a);
860 * That's built the big node in a, and destroyed b. Now
861 * remove the reference to b (and e) in n.
863 for (j = ei; j < 2 && n->elems[j+1]; j++) {
864 n->elems[j] = n->elems[j+1];
865 n->kids[j+1] = n->kids[j+2];
866 n->counts[j+1] = n->counts[j+2];
872 * It's possible, in this case, that we've just removed
873 * the only element in the root of the tree. If so,
876 if (n->elems[0] == NULL) {
877 LOG((" shifting root!\n"));
883 * Now go round the deletion process again, with n
884 * pointing at the new big node and e still the same.
887 index = a->counts[0] + a->counts[1] + 1;
891 void *delpos234(tree234 *t, int index) {
892 if (index < 0 || index >= countnode234(t->root))
894 return delpos234_internal(t, index);
896 void *del234(tree234 *t, void *e) {
898 if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
899 return NULL; /* it wasn't in there anyway */
900 return delpos234_internal(t, index); /* it's there; delete it. */
906 * Test code for the 2-3-4 tree. This code maintains an alternative
907 * representation of the data in the tree, in an array (using the
908 * obvious and slow insert and delete functions). After each tree
909 * operation, the verify() function is called, which ensures all
910 * the tree properties are preserved:
911 * - node->child->parent always equals node
912 * - tree->root->parent always equals NULL
913 * - number of kids == 0 or number of elements + 1;
914 * - tree has the same depth everywhere
915 * - every node has at least one element
916 * - subtree element counts are accurate
917 * - any NULL kid pointer is accompanied by a zero count
918 * - in a sorted tree: ordering property between elements of a
919 * node and elements of its children is preserved
920 * and also ensures the list represented by the tree is the same
921 * list it should be. (This last check also doubly verifies the
922 * ordering properties, because the `same list it should be' is by
923 * definition correctly ordered. It also ensures all nodes are
924 * distinct, because the enum functions would get caught in a loop
930 #define srealloc realloc
933 * Error reporting function.
935 void error(char *fmt, ...) {
939 vfprintf(stdout, fmt, ap);
944 /* The array representation of the data. */
946 int arraylen, arraysize;
949 /* The tree representation of the same data. */
957 int chknode(chkctx *ctx, int level, node234 *node,
958 void *lowbound, void *highbound) {
963 /* Count the non-NULL kids. */
964 for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
965 /* Ensure no kids beyond the first NULL are non-NULL. */
966 for (i = nkids; i < 4; i++)
968 error("node %p: nkids=%d but kids[%d] non-NULL",
970 } else if (node->counts[i]) {
971 error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
972 node, i, i, node->counts[i]);
975 /* Count the non-NULL elements. */
976 for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
977 /* Ensure no elements beyond the first NULL are non-NULL. */
978 for (i = nelems; i < 3; i++)
979 if (node->elems[i]) {
980 error("node %p: nelems=%d but elems[%d] non-NULL",
986 * If nkids==0, this is a leaf node; verify that the tree
987 * depth is the same everywhere.
989 if (ctx->treedepth < 0)
990 ctx->treedepth = level; /* we didn't know the depth yet */
991 else if (ctx->treedepth != level)
992 error("node %p: leaf at depth %d, previously seen depth %d",
993 node, level, ctx->treedepth);
996 * If nkids != 0, then it should be nelems+1, unless nelems
997 * is 0 in which case nkids should also be 0 (and so we
998 * shouldn't be in this condition at all).
1000 int shouldkids = (nelems ? nelems+1 : 0);
1001 if (nkids != shouldkids) {
1002 error("node %p: %d elems should mean %d kids but has %d",
1003 node, nelems, shouldkids, nkids);
1008 * nelems should be at least 1.
1011 error("node %p: no elems", node, nkids);
1015 * Add nelems to the running element count of the whole tree.
1017 ctx->elemcount += nelems;
1020 * Check ordering property: all elements should be strictly >
1021 * lowbound, strictly < highbound, and strictly < each other in
1022 * sequence. (lowbound and highbound are NULL at edges of tree
1023 * - both NULL at root node - and NULL is considered to be <
1024 * everything and > everything. IYSWIM.)
1027 for (i = -1; i < nelems; i++) {
1028 void *lower = (i == -1 ? lowbound : node->elems[i]);
1029 void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
1030 if (lower && higher && cmp(lower, higher) >= 0) {
1031 error("node %p: kid comparison [%d=%s,%d=%s] failed",
1032 node, i, lower, i+1, higher);
1038 * Check parent pointers: all non-NULL kids should have a
1039 * parent pointer coming back to this node.
1041 for (i = 0; i < nkids; i++)
1042 if (node->kids[i]->parent != node) {
1043 error("node %p kid %d: parent ptr is %p not %p",
1044 node, i, node->kids[i]->parent, node);
1049 * Now (finally!) recurse into subtrees.
1053 for (i = 0; i < nkids; i++) {
1054 void *lower = (i == 0 ? lowbound : node->elems[i-1]);
1055 void *higher = (i >= nelems ? highbound : node->elems[i]);
1056 int subcount = chknode(ctx, level+1, node->kids[i], lower, higher);
1057 if (node->counts[i] != subcount) {
1058 error("node %p kid %d: count says %d, subtree really has %d",
1059 node, i, node->counts[i], subcount);
1072 ctx.treedepth = -1; /* depth unknown yet */
1073 ctx.elemcount = 0; /* no elements seen yet */
1075 * Verify validity of tree properties.
1078 if (tree->root->parent != NULL)
1079 error("root->parent is %p should be null", tree->root->parent);
1080 chknode(&ctx, 0, tree->root, NULL, NULL);
1082 printf("tree depth: %d\n", ctx.treedepth);
1084 * Enumerate the tree and ensure it matches up to the array.
1086 for (i = 0; NULL != (p = index234(tree, i)); i++) {
1088 error("tree contains more than %d elements", arraylen);
1090 error("enum at position %d: array says %s, tree says %s",
1093 if (ctx.elemcount != i) {
1094 error("tree really contains %d elements, enum gave %d",
1098 error("enum gave only %d elements, array has %d", i, arraylen);
1101 if (ctx.elemcount != i) {
1102 error("tree really contains %d elements, count234 gave %d",
1107 void internal_addtest(void *elem, int index, void *realret) {
1111 if (arraysize < arraylen+1) {
1112 arraysize = arraylen+1+256;
1113 array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
1114 srealloc(array, arraysize*sizeof(*array)));
1118 /* now i points to the first element >= elem */
1119 retval = elem; /* expect elem returned (success) */
1120 for (j = arraylen; j > i; j--)
1121 array[j] = array[j-1];
1122 array[i] = elem; /* add elem to array */
1125 if (realret != retval) {
1126 error("add: retval was %p expected %p", realret, retval);
1132 void addtest(void *elem) {
1136 realret = add234(tree, elem);
1139 while (i < arraylen && cmp(elem, array[i]) > 0)
1141 if (i < arraylen && !cmp(elem, array[i])) {
1142 void *retval = array[i]; /* expect that returned not elem */
1143 if (realret != retval) {
1144 error("add: retval was %p expected %p", realret, retval);
1147 internal_addtest(elem, i, realret);
1150 void addpostest(void *elem, int i) {
1153 realret = addpos234(tree, elem, i);
1155 internal_addtest(elem, i, realret);
1158 void delpostest(int i) {
1160 void *elem = array[i], *ret;
1162 /* i points to the right element */
1163 while (i < arraylen-1) {
1164 array[i] = array[i+1];
1167 arraylen--; /* delete elem from array */
1170 ret = del234(tree, elem);
1172 ret = delpos234(tree, index);
1175 error("del returned %p, expected %p", ret, elem);
1181 void deltest(void *elem) {
1185 while (i < arraylen && cmp(elem, array[i]) > 0)
1187 if (i >= arraylen || cmp(elem, array[i]) != 0)
1188 return; /* don't do it! */
1192 /* A sample data set and test utility. Designed for pseudo-randomness,
1193 * and yet repeatability. */
1196 * This random number generator uses the `portable implementation'
1197 * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
1200 int randomnumber(unsigned *seed) {
1201 *seed *= 1103515245;
1203 return ((*seed) / 65536) % 32768;
1206 int mycmp(void *av, void *bv) {
1207 char const *a = (char const *)av;
1208 char const *b = (char const *)bv;
1209 return strcmp(a, b);
1212 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
1215 "a", "ab", "absque", "coram", "de",
1216 "palam", "clam", "cum", "ex", "e",
1217 "sine", "tenus", "pro", "prae",
1218 "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
1219 "penguin", "blancmange", "pangolin", "whale", "hedgehog",
1220 "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
1221 "murfl", "spoo", "breen", "flarn", "octothorpe",
1222 "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
1223 "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
1224 "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
1225 "wand", "ring", "amulet"
1228 #define NSTR lenof(strings)
1230 int findtest(void) {
1231 const static int rels[] = {
1232 REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
1234 const static char *const relnames[] = {
1235 "EQ", "GE", "LE", "LT", "GT"
1237 int i, j, rel, index;
1238 char *p, *ret, *realret, *realret2;
1241 for (i = 0; i < NSTR; i++) {
1243 for (j = 0; j < sizeof(rels)/sizeof(*rels); j++) {
1246 lo = 0; hi = arraylen-1;
1248 mid = (lo + hi) / 2;
1249 c = strcmp(p, array[mid]);
1259 if (rel == REL234_LT)
1260 ret = (mid > 0 ? array[--mid] : NULL);
1261 else if (rel == REL234_GT)
1262 ret = (mid < arraylen-1 ? array[++mid] : NULL);
1267 if (rel == REL234_LT || rel == REL234_LE) {
1269 ret = (hi >= 0 ? array[hi] : NULL);
1270 } else if (rel == REL234_GT || rel == REL234_GE) {
1272 ret = (lo < arraylen ? array[lo] : NULL);
1277 realret = findrelpos234(tree, p, NULL, rel, &index);
1278 if (realret != ret) {
1279 error("find(\"%s\",%s) gave %s should be %s",
1280 p, relnames[j], realret, ret);
1282 if (realret && index != mid) {
1283 error("find(\"%s\",%s) gave %d should be %d",
1284 p, relnames[j], index, mid);
1286 if (realret && rel == REL234_EQ) {
1287 realret2 = index234(tree, index);
1288 if (realret2 != realret) {
1289 error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
1290 p, relnames[j], realret, index, index, realret2);
1294 printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
1300 realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
1301 if (arraylen && (realret != array[0] || index != 0)) {
1302 error("find(NULL,GT) gave %s(%d) should be %s(0)",
1303 realret, index, array[0]);
1304 } else if (!arraylen && (realret != NULL)) {
1305 error("find(NULL,GT) gave %s(%d) should be NULL",
1309 realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
1310 if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
1311 error("find(NULL,LT) gave %s(%d) should be %s(0)",
1312 realret, index, array[arraylen-1]);
1313 } else if (!arraylen && (realret != NULL)) {
1314 error("find(NULL,LT) gave %s(%d) should be NULL",
1324 for (i = 0; i < NSTR; i++) in[i] = 0;
1326 arraylen = arraysize = 0;
1327 tree = newtree234(mycmp);
1331 for (i = 0; i < 10000; i++) {
1332 j = randomnumber(&seed);
1334 printf("trial: %d\n", i);
1336 printf("deleting %s (%d)\n", strings[j], j);
1337 deltest(strings[j]);
1340 printf("adding %s (%d)\n", strings[j], j);
1341 addtest(strings[j]);
1347 while (arraylen > 0) {
1348 j = randomnumber(&seed);
1356 * Now try an unsorted tree. We don't really need to test
1357 * delpos234 because we know del234 is based on it, so it's
1358 * already been tested in the above sorted-tree code; but for
1359 * completeness we'll use it to tear down our unsorted tree
1360 * once we've built it.
1362 tree = newtree234(NULL);
1365 for (i = 0; i < 1000; i++) {
1366 printf("trial: %d\n", i);
1367 j = randomnumber(&seed);
1369 k = randomnumber(&seed);
1370 k %= count234(tree)+1;
1371 printf("adding string %s at index %d\n", strings[j], k);
1372 addpostest(strings[j], k);
1374 while (count234(tree) > 0) {
1375 printf("cleanup: tree size %d\n", count234(tree));
1376 j = randomnumber(&seed);
1377 j %= count234(tree);
1378 printf("deleting string %s from index %d\n", array[j], j);