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 * Propagate a node overflow up a tree until it stops. Returns 0 or
115 * 1, depending on whether the root had to be split or not.
117 static int add234_insert(node234 *left, void *e, node234 *right,
118 node234 **root, node234 *n, int ki) {
121 * We need to insert the new left/element/right set in n at
124 lcount = countnode234(left);
125 rcount = countnode234(right);
127 LOG((" at %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
129 n->kids[0], n->counts[0], n->elems[0],
130 n->kids[1], n->counts[1], n->elems[1],
131 n->kids[2], n->counts[2], n->elems[2],
132 n->kids[3], n->counts[3]));
133 LOG((" need to insert %p/%d \"%s\" %p/%d at position %d\n",
134 left, lcount, e, right, rcount, ki));
135 if (n->elems[1] == NULL) {
137 * Insert in a 2-node; simple.
140 LOG((" inserting on left of 2-node\n"));
141 n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
142 n->elems[1] = n->elems[0];
143 n->kids[1] = right; n->counts[1] = rcount;
145 n->kids[0] = left; n->counts[0] = lcount;
146 } else { /* ki == 1 */
147 LOG((" inserting on right of 2-node\n"));
148 n->kids[2] = right; n->counts[2] = rcount;
150 n->kids[1] = left; n->counts[1] = lcount;
152 if (n->kids[0]) n->kids[0]->parent = n;
153 if (n->kids[1]) n->kids[1]->parent = n;
154 if (n->kids[2]) n->kids[2]->parent = n;
157 } else if (n->elems[2] == NULL) {
159 * Insert in a 3-node; simple.
162 LOG((" inserting on left of 3-node\n"));
163 n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
164 n->elems[2] = n->elems[1];
165 n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
166 n->elems[1] = n->elems[0];
167 n->kids[1] = right; n->counts[1] = rcount;
169 n->kids[0] = left; n->counts[0] = lcount;
170 } else if (ki == 1) {
171 LOG((" inserting in middle of 3-node\n"));
172 n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
173 n->elems[2] = n->elems[1];
174 n->kids[2] = right; n->counts[2] = rcount;
176 n->kids[1] = left; n->counts[1] = lcount;
177 } else { /* ki == 2 */
178 LOG((" inserting on right of 3-node\n"));
179 n->kids[3] = right; n->counts[3] = rcount;
181 n->kids[2] = left; n->counts[2] = lcount;
183 if (n->kids[0]) n->kids[0]->parent = n;
184 if (n->kids[1]) n->kids[1]->parent = n;
185 if (n->kids[2]) n->kids[2]->parent = n;
186 if (n->kids[3]) n->kids[3]->parent = n;
190 node234 *m = mknew(node234);
191 m->parent = n->parent;
192 LOG((" splitting a 4-node; created new node %p\n", m));
194 * Insert in a 4-node; split into a 2-node and a
195 * 3-node, and move focus up a level.
197 * I don't think it matters which way round we put the
198 * 2 and the 3. For simplicity, we'll put the 3 first
202 m->kids[0] = left; m->counts[0] = lcount;
204 m->kids[1] = right; m->counts[1] = rcount;
205 m->elems[1] = n->elems[0];
206 m->kids[2] = n->kids[1]; m->counts[2] = n->counts[1];
208 n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
209 n->elems[0] = n->elems[2];
210 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
211 } else if (ki == 1) {
212 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
213 m->elems[0] = n->elems[0];
214 m->kids[1] = left; m->counts[1] = lcount;
216 m->kids[2] = right; m->counts[2] = rcount;
218 n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
219 n->elems[0] = n->elems[2];
220 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
221 } else if (ki == 2) {
222 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
223 m->elems[0] = n->elems[0];
224 m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
225 m->elems[1] = n->elems[1];
226 m->kids[2] = left; m->counts[2] = lcount;
228 n->kids[0] = right; n->counts[0] = rcount;
229 n->elems[0] = n->elems[2];
230 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
231 } else { /* ki == 3 */
232 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
233 m->elems[0] = n->elems[0];
234 m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
235 m->elems[1] = n->elems[1];
236 m->kids[2] = n->kids[2]; m->counts[2] = n->counts[2];
237 n->kids[0] = left; n->counts[0] = lcount;
239 n->kids[1] = right; n->counts[1] = rcount;
242 m->kids[3] = n->kids[3] = n->kids[2] = NULL;
243 m->counts[3] = n->counts[3] = n->counts[2] = 0;
244 m->elems[2] = n->elems[2] = n->elems[1] = NULL;
245 if (m->kids[0]) m->kids[0]->parent = m;
246 if (m->kids[1]) m->kids[1]->parent = m;
247 if (m->kids[2]) m->kids[2]->parent = m;
248 if (n->kids[0]) n->kids[0]->parent = n;
249 if (n->kids[1]) n->kids[1]->parent = n;
250 LOG((" left (%p): %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", m,
251 m->kids[0], m->counts[0], m->elems[0],
252 m->kids[1], m->counts[1], m->elems[1],
253 m->kids[2], m->counts[2]));
254 LOG((" right (%p): %p/%d \"%s\" %p/%d\n", n,
255 n->kids[0], n->counts[0], n->elems[0],
256 n->kids[1], n->counts[1]));
257 left = m; lcount = countnode234(left);
258 right = n; rcount = countnode234(right);
261 ki = (n->parent->kids[0] == n ? 0 :
262 n->parent->kids[1] == n ? 1 :
263 n->parent->kids[2] == n ? 2 : 3);
268 * If we've come out of here by `break', n will still be
269 * non-NULL and all we need to do is go back up the tree
270 * updating counts. If we've come here because n is NULL, we
271 * need to create a new root for the tree because the old one
272 * has just split into two. */
275 int count = countnode234(n);
277 childnum = (n->parent->kids[0] == n ? 0 :
278 n->parent->kids[1] == n ? 1 :
279 n->parent->kids[2] == n ? 2 : 3);
280 n->parent->counts[childnum] = count;
283 return 0; /* root unchanged */
285 LOG((" root is overloaded, split into two\n"));
286 (*root) = mknew(node234);
287 (*root)->kids[0] = left; (*root)->counts[0] = lcount;
288 (*root)->elems[0] = e;
289 (*root)->kids[1] = right; (*root)->counts[1] = rcount;
290 (*root)->elems[1] = NULL;
291 (*root)->kids[2] = NULL; (*root)->counts[2] = 0;
292 (*root)->elems[2] = NULL;
293 (*root)->kids[3] = NULL; (*root)->counts[3] = 0;
294 (*root)->parent = NULL;
295 if ((*root)->kids[0]) (*root)->kids[0]->parent = (*root);
296 if ((*root)->kids[1]) (*root)->kids[1]->parent = (*root);
297 LOG((" new root is %p/%d \"%s\" %p/%d\n",
298 (*root)->kids[0], (*root)->counts[0],
300 (*root)->kids[1], (*root)->counts[1]));
301 return 1; /* root moved */
306 * Add an element e to a 2-3-4 tree t. Returns e on success, or if
307 * an existing element compares equal, returns that.
309 static void *add234_internal(tree234 *t, void *e, int index) {
315 LOG(("adding element \"%s\" to tree %p\n", e, t));
316 if (t->root == NULL) {
317 t->root = mknew(node234);
318 t->root->elems[1] = t->root->elems[2] = NULL;
319 t->root->kids[0] = t->root->kids[1] = NULL;
320 t->root->kids[2] = t->root->kids[3] = NULL;
321 t->root->counts[0] = t->root->counts[1] = 0;
322 t->root->counts[2] = t->root->counts[3] = 0;
323 t->root->parent = NULL;
324 t->root->elems[0] = e;
325 LOG((" created root %p\n", t->root));
331 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
333 n->kids[0], n->counts[0], n->elems[0],
334 n->kids[1], n->counts[1], n->elems[1],
335 n->kids[2], n->counts[2], n->elems[2],
336 n->kids[3], n->counts[3]));
340 * Leaf node. We want to insert at kid position
341 * equal to the index:
348 * Internal node. We always descend through it (add
349 * always starts at the bottom, never in the
352 if (index <= n->counts[0]) {
354 } else if (index -= n->counts[0] + 1, index <= n->counts[1]) {
356 } else if (index -= n->counts[1] + 1, index <= n->counts[2]) {
358 } else if (index -= n->counts[2] + 1, index <= n->counts[3]) {
361 return NULL; /* error: index out of range */
364 if ((c = t->cmp(e, n->elems[0])) < 0)
367 return n->elems[0]; /* already exists */
368 else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
371 return n->elems[1]; /* already exists */
372 else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
375 return n->elems[2]; /* already exists */
379 LOG((" moving to child %d (%p)\n", ki, n->kids[ki]));
385 add234_insert(NULL, e, NULL, &t->root, n, ki);
390 void *add234(tree234 *t, void *e) {
391 if (!t->cmp) /* tree is unsorted */
394 return add234_internal(t, e, -1);
396 void *addpos234(tree234 *t, void *e, int index) {
397 if (index < 0 || /* index out of range */
398 t->cmp) /* tree is sorted */
399 return NULL; /* return failure */
401 return add234_internal(t, e, index); /* this checks the upper bound */
405 * Look up the element at a given numeric index in a 2-3-4 tree.
406 * Returns NULL if the index is out of range.
408 void *index234(tree234 *t, int index) {
412 return NULL; /* tree is empty */
414 if (index < 0 || index >= countnode234(t->root))
415 return NULL; /* out of range */
420 if (index < n->counts[0])
422 else if (index -= n->counts[0] + 1, index < 0)
424 else if (index < n->counts[1])
426 else if (index -= n->counts[1] + 1, index < 0)
428 else if (index < n->counts[2])
430 else if (index -= n->counts[2] + 1, index < 0)
436 /* We shouldn't ever get here. I wonder how we did. */
441 * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
442 * found. e is always passed as the first argument to cmp, so cmp
443 * can be an asymmetric function if desired. cmp can also be passed
444 * as NULL, in which case the compare function from the tree proper
447 void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp,
448 int relation, int *index) {
452 int idx, ecount, kcount, cmpret;
462 * Attempt to find the element itself.
467 * Prepare a fake `cmp' result if e is NULL.
471 assert(relation == REL234_LT || relation == REL234_GT);
472 if (relation == REL234_LT)
473 cmpret = +1; /* e is a max: always greater */
474 else if (relation == REL234_GT)
475 cmpret = -1; /* e is a min: always smaller */
478 for (kcount = 0; kcount < 4; kcount++) {
479 if (kcount >= 3 || n->elems[kcount] == NULL ||
480 (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
483 if (n->kids[kcount]) idx += n->counts[kcount];
500 * We have found the element we're looking for. It's
501 * n->elems[ecount], at tree index idx. If our search
502 * relation is EQ, LE or GE we can now go home.
504 if (relation != REL234_LT && relation != REL234_GT) {
505 if (index) *index = idx;
506 return n->elems[ecount];
510 * Otherwise, we'll do an indexed lookup for the previous
511 * or next element. (It would be perfectly possible to
512 * implement these search types in a non-counted tree by
513 * going back up from where we are, but far more fiddly.)
515 if (relation == REL234_LT)
521 * We've found our way to the bottom of the tree and we
522 * know where we would insert this node if we wanted to:
523 * we'd put it in in place of the (empty) subtree
524 * n->kids[kcount], and it would have index idx
526 * But the actual element isn't there. So if our search
527 * relation is EQ, we're doomed.
529 if (relation == REL234_EQ)
533 * Otherwise, we must do an index lookup for index idx-1
534 * (if we're going left - LE or LT) or index idx (if we're
535 * going right - GE or GT).
537 if (relation == REL234_LT || relation == REL234_LE) {
543 * We know the index of the element we want; just call index234
544 * to do the rest. This will return NULL if the index is out of
545 * bounds, which is exactly what we want.
547 ret = index234(t, idx);
548 if (ret && index) *index = idx;
551 void *find234(tree234 *t, void *e, cmpfn234 cmp) {
552 return findrelpos234(t, e, cmp, REL234_EQ, NULL);
554 void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) {
555 return findrelpos234(t, e, cmp, relation, NULL);
557 void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) {
558 return findrelpos234(t, e, cmp, REL234_EQ, index);
562 * Tree transformation used in delete and split: move a subtree
563 * right, from child ki of a node to the next child. Update k and
564 * index so that they still point to the same place in the
565 * transformed tree. Assumes the destination child is not full, and
566 * that the source child does have a subtree to spare. Can cope if
567 * the destination child is undersized.
571 * [more] a A b B c d D e [more] a A b c C d D e
575 * [more] a A b B c d [more] a A b c C d
577 static void trans234_subtree_right(node234 *n, int ki, int *k, int *index) {
579 int i, srclen, adjust;
582 dest = n->kids[ki+1];
584 LOG((" trans234_subtree_right(%p, %d):\n", n, ki));
585 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
587 n->kids[0], n->counts[0], n->elems[0],
588 n->kids[1], n->counts[1], n->elems[1],
589 n->kids[2], n->counts[2], n->elems[2],
590 n->kids[3], n->counts[3]));
591 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
593 src->kids[0], src->counts[0], src->elems[0],
594 src->kids[1], src->counts[1], src->elems[1],
595 src->kids[2], src->counts[2], src->elems[2],
596 src->kids[3], src->counts[3]));
597 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
599 dest->kids[0], dest->counts[0], dest->elems[0],
600 dest->kids[1], dest->counts[1], dest->elems[1],
601 dest->kids[2], dest->counts[2], dest->elems[2],
602 dest->kids[3], dest->counts[3]));
604 * Move over the rest of the destination node to make space.
606 dest->kids[3] = dest->kids[2]; dest->counts[3] = dest->counts[2];
607 dest->elems[2] = dest->elems[1];
608 dest->kids[2] = dest->kids[1]; dest->counts[2] = dest->counts[1];
609 dest->elems[1] = dest->elems[0];
610 dest->kids[1] = dest->kids[0]; dest->counts[1] = dest->counts[0];
612 /* which element to move over */
613 i = (src->elems[2] ? 2 : src->elems[1] ? 1 : 0);
615 dest->elems[0] = n->elems[ki];
616 n->elems[ki] = src->elems[i];
617 src->elems[i] = NULL;
619 dest->kids[0] = src->kids[i+1]; dest->counts[0] = src->counts[i+1];
620 src->kids[i+1] = NULL; src->counts[i+1] = 0;
622 if (dest->kids[0]) dest->kids[0]->parent = dest;
624 adjust = dest->counts[0] + 1;
626 n->counts[ki] -= adjust;
627 n->counts[ki+1] += adjust;
629 srclen = n->counts[ki];
632 LOG((" before: k,index = %d,%d\n", (*k), (*index)));
633 if ((*k) == ki && (*index) > srclen) {
634 (*index) -= srclen + 1;
636 } else if ((*k) == ki+1) {
639 LOG((" after: k,index = %d,%d\n", (*k), (*index)));
642 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
644 n->kids[0], n->counts[0], n->elems[0],
645 n->kids[1], n->counts[1], n->elems[1],
646 n->kids[2], n->counts[2], n->elems[2],
647 n->kids[3], n->counts[3]));
648 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
650 src->kids[0], src->counts[0], src->elems[0],
651 src->kids[1], src->counts[1], src->elems[1],
652 src->kids[2], src->counts[2], src->elems[2],
653 src->kids[3], src->counts[3]));
654 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
656 dest->kids[0], dest->counts[0], dest->elems[0],
657 dest->kids[1], dest->counts[1], dest->elems[1],
658 dest->kids[2], dest->counts[2], dest->elems[2],
659 dest->kids[3], dest->counts[3]));
663 * Tree transformation used in delete and split: move a subtree
664 * left, from child ki of a node to the previous child. Update k
665 * and index so that they still point to the same place in the
666 * transformed tree. Assumes the destination child is not full, and
667 * that the source child does have a subtree to spare. Can cope if
668 * the destination child is undersized.
672 * a A b c C d D e [more] a A b B c d D e [more]
676 * a b B c C d [more] a A b c C d [more]
678 static void trans234_subtree_left(node234 *n, int ki, int *k, int *index) {
683 dest = n->kids[ki-1];
685 LOG((" trans234_subtree_left(%p, %d):\n", n, ki));
686 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
688 n->kids[0], n->counts[0], n->elems[0],
689 n->kids[1], n->counts[1], n->elems[1],
690 n->kids[2], n->counts[2], n->elems[2],
691 n->kids[3], n->counts[3]));
692 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
694 dest->kids[0], dest->counts[0], dest->elems[0],
695 dest->kids[1], dest->counts[1], dest->elems[1],
696 dest->kids[2], dest->counts[2], dest->elems[2],
697 dest->kids[3], dest->counts[3]));
698 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
700 src->kids[0], src->counts[0], src->elems[0],
701 src->kids[1], src->counts[1], src->elems[1],
702 src->kids[2], src->counts[2], src->elems[2],
703 src->kids[3], src->counts[3]));
705 /* where in dest to put it */
706 i = (dest->elems[1] ? 2 : dest->elems[0] ? 1 : 0);
707 dest->elems[i] = n->elems[ki-1];
708 n->elems[ki-1] = src->elems[0];
710 dest->kids[i+1] = src->kids[0]; dest->counts[i+1] = src->counts[0];
712 if (dest->kids[i+1]) dest->kids[i+1]->parent = dest;
715 * Move over the rest of the source node.
717 src->kids[0] = src->kids[1]; src->counts[0] = src->counts[1];
718 src->elems[0] = src->elems[1];
719 src->kids[1] = src->kids[2]; src->counts[1] = src->counts[2];
720 src->elems[1] = src->elems[2];
721 src->kids[2] = src->kids[3]; src->counts[2] = src->counts[3];
722 src->elems[2] = NULL;
723 src->kids[3] = NULL; src->counts[3] = 0;
725 adjust = dest->counts[i+1] + 1;
727 n->counts[ki] -= adjust;
728 n->counts[ki-1] += adjust;
731 LOG((" before: k,index = %d,%d\n", (*k), (*index)));
735 (*index) += n->counts[ki-1] + 1;
739 LOG((" after: k,index = %d,%d\n", (*k), (*index)));
742 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
744 n->kids[0], n->counts[0], n->elems[0],
745 n->kids[1], n->counts[1], n->elems[1],
746 n->kids[2], n->counts[2], n->elems[2],
747 n->kids[3], n->counts[3]));
748 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
750 dest->kids[0], dest->counts[0], dest->elems[0],
751 dest->kids[1], dest->counts[1], dest->elems[1],
752 dest->kids[2], dest->counts[2], dest->elems[2],
753 dest->kids[3], dest->counts[3]));
754 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
756 src->kids[0], src->counts[0], src->elems[0],
757 src->kids[1], src->counts[1], src->elems[1],
758 src->kids[2], src->counts[2], src->elems[2],
759 src->kids[3], src->counts[3]));
763 * Tree transformation used in delete and split: merge child nodes
764 * ki and ki+1 of a node. Update k and index so that they still
765 * point to the same place in the transformed tree. Assumes both
766 * children _are_ sufficiently small.
770 * a A b c C d a A b B c C d
772 * This routine can also cope with either child being undersized:
780 * a b B c C d a A b B c C d
782 static void trans234_subtree_merge(node234 *n, int ki, int *k, int *index) {
783 node234 *left, *right;
784 int i, leftlen, rightlen, lsize, rsize;
786 left = n->kids[ki]; leftlen = n->counts[ki];
787 right = n->kids[ki+1]; rightlen = n->counts[ki+1];
789 LOG((" trans234_subtree_merge(%p, %d):\n", n, ki));
790 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
792 n->kids[0], n->counts[0], n->elems[0],
793 n->kids[1], n->counts[1], n->elems[1],
794 n->kids[2], n->counts[2], n->elems[2],
795 n->kids[3], n->counts[3]));
796 LOG((" left %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
798 left->kids[0], left->counts[0], left->elems[0],
799 left->kids[1], left->counts[1], left->elems[1],
800 left->kids[2], left->counts[2], left->elems[2],
801 left->kids[3], left->counts[3]));
802 LOG((" right %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
804 right->kids[0], right->counts[0], right->elems[0],
805 right->kids[1], right->counts[1], right->elems[1],
806 right->kids[2], right->counts[2], right->elems[2],
807 right->kids[3], right->counts[3]));
809 assert(!left->elems[2] && !right->elems[2]); /* neither is large! */
810 lsize = (left->elems[1] ? 2 : left->elems[0] ? 1 : 0);
811 rsize = (right->elems[1] ? 2 : right->elems[0] ? 1 : 0);
813 left->elems[lsize] = n->elems[ki];
815 for (i = 0; i < rsize+1; i++) {
816 left->kids[lsize+1+i] = right->kids[i];
817 left->counts[lsize+1+i] = right->counts[i];
818 if (left->kids[lsize+1+i])
819 left->kids[lsize+1+i]->parent = left;
821 left->elems[lsize+1+i] = right->elems[i];
824 n->counts[ki] += rightlen + 1;
829 * Move the rest of n up by one.
831 for (i = ki+1; i < 3; i++) {
832 n->kids[i] = n->kids[i+1];
833 n->counts[i] = n->counts[i+1];
835 for (i = ki; i < 2; i++) {
836 n->elems[i] = n->elems[i+1];
843 LOG((" before: k,index = %d,%d\n", (*k), (*index)));
846 (*index) += leftlen + 1;
847 } else if ((*k) > ki+1) {
850 LOG((" after: k,index = %d,%d\n", (*k), (*index)));
853 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
855 n->kids[0], n->counts[0], n->elems[0],
856 n->kids[1], n->counts[1], n->elems[1],
857 n->kids[2], n->counts[2], n->elems[2],
858 n->kids[3], n->counts[3]));
859 LOG((" merged %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
861 left->kids[0], left->counts[0], left->elems[0],
862 left->kids[1], left->counts[1], left->elems[1],
863 left->kids[2], left->counts[2], left->elems[2],
864 left->kids[3], left->counts[3]));
869 * Delete an element e in a 2-3-4 tree. Does not free the element,
870 * merely removes all links to it from the tree nodes.
872 static void *delpos234_internal(tree234 *t, int index) {
879 n = t->root; /* by assumption this is non-NULL */
880 LOG(("deleting item %d from tree %p\n", index, t));
884 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n",
886 n->kids[0], n->counts[0], n->elems[0],
887 n->kids[1], n->counts[1], n->elems[1],
888 n->kids[2], n->counts[2], n->elems[2],
889 n->kids[3], n->counts[3],
891 if (index <= n->counts[0]) {
893 } else if (index -= n->counts[0]+1, index <= n->counts[1]) {
895 } else if (index -= n->counts[1]+1, index <= n->counts[2]) {
897 } else if (index -= n->counts[2]+1, index <= n->counts[3]) {
900 assert(0); /* can't happen */
904 break; /* n is a leaf node; we're here! */
907 * Check to see if we've found our target element. If so,
908 * we must choose a new target (we'll use the old target's
909 * successor, which will be in a leaf), move it into the
910 * place of the old one, continue down to the leaf and
911 * delete the old copy of the new target.
913 if (index == n->counts[ki]) {
915 LOG((" found element in internal node, index %d\n", ki));
916 assert(n->elems[ki]); /* must be a kid _before_ an element */
918 for (m = n->kids[ki]; m->kids[0]; m = m->kids[0])
920 LOG((" replacing with element \"%s\" from leaf node %p\n",
922 retval = n->elems[ki-1];
923 n->elems[ki-1] = m->elems[0];
927 * Recurse down to subtree ki. If it has only one element,
928 * we have to do some transformation to start with.
930 LOG((" moving to subtree %d\n", ki));
932 if (!sub->elems[1]) {
933 LOG((" subtree has only one element!\n"));
934 if (ki > 0 && n->kids[ki-1]->elems[1]) {
936 * Child ki has only one element, but child
937 * ki-1 has two or more. So we need to move a
938 * subtree from ki-1 to ki.
940 trans234_subtree_right(n, ki-1, &ki, &index);
941 } else if (ki < 3 && n->kids[ki+1] &&
942 n->kids[ki+1]->elems[1]) {
944 * Child ki has only one element, but ki+1 has
945 * two or more. Move a subtree from ki+1 to ki.
947 trans234_subtree_left(n, ki+1, &ki, &index);
950 * ki is small with only small neighbours. Pick a
951 * neighbour and merge with it.
953 trans234_subtree_merge(n, ki>0 ? ki-1 : ki, &ki, &index);
958 * The root is empty and needs to be
961 LOG((" shifting root!\n"));
976 * Now n is a leaf node, and ki marks the element number we
977 * want to delete. We've already arranged for the leaf to be
978 * bigger than minimum size, so let's just go to it.
982 retval = n->elems[ki];
984 for (i = ki; i < 2 && n->elems[i+1]; i++)
985 n->elems[i] = n->elems[i+1];
989 * It's just possible that we have reduced the leaf to zero
990 * size. This can only happen if it was the root - so destroy
991 * it and make the tree empty.
994 LOG((" removed last element in tree, destroying empty root\n"));
995 assert(n == t->root);
1000 return retval; /* finished! */
1002 void *delpos234(tree234 *t, int index) {
1003 if (index < 0 || index >= countnode234(t->root))
1005 return delpos234_internal(t, index);
1007 void *del234(tree234 *t, void *e) {
1009 if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
1010 return NULL; /* it wasn't in there anyway */
1011 return delpos234_internal(t, index); /* it's there; delete it. */
1015 * Join two subtrees together with a separator element between
1016 * them, given their relative height.
1018 * (Height<0 means the left tree is shorter, >0 means the right
1019 * tree is shorter, =0 means (duh) they're equal.)
1021 * It is assumed that any checks needed on the ordering criterion
1022 * have _already_ been done.
1024 * The value returned in `height' is 0 or 1 depending on whether the
1025 * resulting tree is the same height as the original larger one, or
1028 static node234 *join234_internal(node234 *left, void *sep,
1029 node234 *right, int *height) {
1030 node234 *root, *node;
1031 int relht = *height;
1034 LOG((" join: joining %p \"%s\" %p, relative height is %d\n",
1035 left, sep, right, relht));
1038 * The trees are the same height. Create a new one-element
1039 * root containing the separator and pointers to the two
1043 newroot = mknew(node234);
1044 newroot->kids[0] = left; newroot->counts[0] = countnode234(left);
1045 newroot->elems[0] = sep;
1046 newroot->kids[1] = right; newroot->counts[1] = countnode234(right);
1047 newroot->elems[1] = NULL;
1048 newroot->kids[2] = NULL; newroot->counts[2] = 0;
1049 newroot->elems[2] = NULL;
1050 newroot->kids[3] = NULL; newroot->counts[3] = 0;
1051 newroot->parent = NULL;
1052 if (left) left->parent = newroot;
1053 if (right) right->parent = newroot;
1055 LOG((" join: same height, brand new root\n"));
1060 * This now works like the addition algorithm on the larger
1061 * tree. We're replacing a single kid pointer with two kid
1062 * pointers separated by an element; if that causes the node to
1063 * overload, we split it in two, move a separator element up to
1064 * the next node, and repeat.
1068 * Left tree is shorter. Search down the right tree to find
1069 * the pointer we're inserting at.
1071 node = root = right;
1072 while (++relht < 0) {
1073 node = node->kids[0];
1076 right = node->kids[ki];
1079 * Right tree is shorter; search down the left to find the
1080 * pointer we're inserting at.
1083 while (--relht > 0) {
1085 node = node->kids[3];
1086 else if (node->elems[1])
1087 node = node->kids[2];
1089 node = node->kids[1];
1093 else if (node->elems[1])
1097 left = node->kids[ki];
1101 * Now proceed as for addition.
1103 *height = add234_insert(left, sep, right, &root, node, ki);
1107 static int height234(tree234 *t) {
1109 node234 *n = t->root;
1116 tree234 *join234(tree234 *t1, tree234 *t2) {
1117 int size2 = countnode234(t2->root);
1123 element = index234(t2, 0);
1124 element = findrelpos234(t1, element, NULL, REL234_GE, NULL);
1129 element = delpos234(t2, 0);
1130 relht = height234(t1) - height234(t2);
1131 t1->root = join234_internal(t1->root, element, t2->root, &relht);
1136 tree234 *join234r(tree234 *t1, tree234 *t2) {
1137 int size1 = countnode234(t1->root);
1143 element = index234(t1, size1-1);
1144 element = findrelpos234(t2, element, NULL, REL234_LE, NULL);
1149 element = delpos234(t1, size1-1);
1150 relht = height234(t1) - height234(t2);
1151 t2->root = join234_internal(t1->root, element, t2->root, &relht);
1158 * Split out the first <index> elements in a tree and return a
1159 * pointer to the root node. Leave the root node of the remainder
1162 static node234 *split234_internal(tree234 *t, int index) {
1163 node234 *halves[2], *n, *sib, *sub;
1164 node234 *lparent, *rparent;
1165 int ki, pki, i, half, lcount, rcount;
1168 LOG(("splitting tree %p at point %d\n", t, index));
1171 * Easy special cases. After this we have also dealt completely
1172 * with the empty-tree case and we can assume the root exists.
1174 if (index == 0) /* return nothing */
1176 if (index == countnode234(t->root)) { /* return the whole tree */
1177 node234 *ret = t->root;
1183 * Search down the tree to find the split point.
1185 lparent = rparent = NULL;
1188 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n",
1190 n->kids[0], n->counts[0], n->elems[0],
1191 n->kids[1], n->counts[1], n->elems[1],
1192 n->kids[2], n->counts[2], n->elems[2],
1193 n->kids[3], n->counts[3],
1196 rcount = countnode234(n) - lcount;
1197 if (index <= n->counts[0]) {
1199 } else if (index -= n->counts[0]+1, index <= n->counts[1]) {
1201 } else if (index -= n->counts[1]+1, index <= n->counts[2]) {
1204 index -= n->counts[2]+1;
1208 LOG((" splitting at subtree %d\n", ki));
1211 LOG((" splitting at child index %d\n", ki));
1214 * Split the node, put halves[0] on the right of the left
1215 * one and halves[1] on the left of the right one, put the
1216 * new node pointers in halves[0] and halves[1], and go up
1219 sib = mknew(node234);
1220 for (i = 0; i < 3; i++) {
1221 if (i+ki < 3 && n->elems[i+ki]) {
1222 sib->elems[i] = n->elems[i+ki];
1223 sib->kids[i+1] = n->kids[i+ki+1];
1224 if (sib->kids[i+1]) sib->kids[i+1]->parent = sib;
1225 sib->counts[i+1] = n->counts[i+ki+1];
1226 n->elems[i+ki] = NULL;
1227 n->kids[i+ki+1] = NULL;
1228 n->counts[i+ki+1] = 0;
1230 sib->elems[i] = NULL;
1231 sib->kids[i+1] = NULL;
1232 sib->counts[i+1] = 0;
1236 lparent->kids[pki] = n;
1237 lparent->counts[pki] = lcount;
1238 n->parent = lparent;
1239 rparent->kids[0] = sib;
1240 rparent->counts[0] = rcount;
1241 sib->parent = rparent;
1251 LOG((" left node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
1253 n->kids[0], n->counts[0], n->elems[0],
1254 n->kids[1], n->counts[1], n->elems[1],
1255 n->kids[2], n->counts[2], n->elems[2],
1256 n->kids[3], n->counts[3]));
1257 LOG((" right node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
1259 sib->kids[0], sib->counts[0], sib->elems[0],
1260 sib->kids[1], sib->counts[1], sib->elems[1],
1261 sib->kids[2], sib->counts[2], sib->elems[2],
1262 sib->kids[3], sib->counts[3]));
1268 * We've come off the bottom here, so we've successfully split
1269 * the tree into two equally high subtrees. The only problem is
1270 * that some of the nodes down the fault line will be smaller
1271 * than the minimum permitted size. (Since this is a 2-3-4
1272 * tree, that means they'll be zero-element one-child nodes.)
1274 LOG((" fell off bottom, lroot is %p, rroot is %p\n",
1275 halves[0], halves[1]));
1276 lparent->counts[pki] = rparent->counts[0] = 0;
1277 lparent->kids[pki] = rparent->kids[0] = NULL;
1280 * So now we go back down the tree from each of the two roots,
1281 * fixing up undersize nodes.
1283 for (half = 0; half < 2; half++) {
1285 * Remove the root if it's undersize (it will contain only
1286 * one child pointer, so just throw it away and replace it
1287 * with its child). This might happen several times.
1289 while (halves[half] && !halves[half]->elems[0]) {
1290 LOG((" root %p is undersize, throwing away\n", halves[half]));
1291 halves[half] = halves[half]->kids[0];
1292 sfree(halves[half]->parent);
1293 halves[half]->parent = NULL;
1294 LOG((" new root is %p\n", halves[half]));
1299 void (*toward)(node234 *n, int ki, int *k, int *index);
1303 * Now we have a potentially undersize node on the
1304 * right (if half==0) or left (if half==1). Sort it
1305 * out, by merging with a neighbour or by transferring
1306 * subtrees over. At this time we must also ensure that
1307 * nodes are bigger than minimum, in case we need an
1308 * element to merge two nodes below.
1310 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
1312 n->kids[0], n->counts[0], n->elems[0],
1313 n->kids[1], n->counts[1], n->elems[1],
1314 n->kids[2], n->counts[2], n->elems[2],
1315 n->kids[3], n->counts[3]));
1317 ki = 0; /* the kid we're interested in */
1318 ni = 1; /* the neighbour */
1319 merge = 0; /* for merge: leftmost of the two */
1320 toward = trans234_subtree_left;
1322 ki = (n->kids[3] ? 3 : n->kids[2] ? 2 : 1);
1325 toward = trans234_subtree_right;
1329 if (sub && !sub->elems[1]) {
1331 * This node is undersized or minimum-size. If we
1332 * can merge it with its neighbour, we do so;
1333 * otherwise we must be able to transfer subtrees
1334 * over to it until it is greater than minimum
1337 int undersized = (!sub->elems[0]);
1338 LOG((" child %d is %ssize\n", ki,
1339 undersized ? "under" : "minimum-"));
1340 LOG((" neighbour is %s\n",
1341 n->kids[ni]->elems[2] ? "large" :
1342 n->kids[ni]->elems[1] ? "medium" : "small"));
1343 if (!n->kids[ni]->elems[1] ||
1344 (undersized && !n->kids[ni]->elems[2])) {
1346 * Neighbour is small, or possibly neighbour is
1347 * medium and we are undersize.
1349 trans234_subtree_merge(n, merge, NULL, NULL);
1350 sub = n->kids[merge];
1353 * n is empty, and hence must have been the
1354 * root and needs to be removed.
1357 LOG((" shifting root!\n"));
1359 halves[half]->parent = NULL;
1363 /* Neighbour is big enough to move trees over. */
1364 toward(n, ni, NULL, NULL);
1366 toward(n, ni, NULL, NULL);
1373 t->root = halves[1];
1376 tree234 *splitpos234(tree234 *t, int index, int before) {
1381 count = countnode234(t->root);
1382 if (index < 0 || index > count)
1383 return NULL; /* error */
1384 ret = newtree234(t->cmp);
1385 n = split234_internal(t, index);
1387 /* We want to return the ones before the index. */
1391 * We want to keep the ones before the index and return the
1394 ret->root = t->root;
1399 tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel) {
1403 assert(rel != REL234_EQ);
1405 if (rel == REL234_GT || rel == REL234_GE) {
1407 rel = (rel == REL234_GT ? REL234_LE : REL234_LT);
1411 if (!findrelpos234(t, e, cmp, rel, &index))
1414 return splitpos234(t, index+1, before);
1417 static node234 *copynode234(node234 *n, copyfn234 copyfn, void *copyfnstate) {
1419 node234 *n2 = mknew(node234);
1421 for (i = 0; i < 3; i++) {
1422 if (n->elems[i] && copyfn)
1423 n2->elems[i] = copyfn(copyfnstate, n->elems[i]);
1425 n2->elems[i] = n->elems[i];
1428 for (i = 0; i < 4; i++) {
1430 n2->kids[i] = copynode234(n->kids[i], copyfn, copyfnstate);
1431 n2->kids[i]->parent = n2;
1435 n2->counts[i] = n->counts[i];
1440 tree234 *copytree234(tree234 *t, copyfn234 copyfn, void *copyfnstate) {
1443 t2 = newtree234(t->cmp);
1444 t2->root = copynode234(t->root, copyfn, copyfnstate);
1445 t2->root->parent = NULL;
1453 * Test code for the 2-3-4 tree. This code maintains an alternative
1454 * representation of the data in the tree, in an array (using the
1455 * obvious and slow insert and delete functions). After each tree
1456 * operation, the verify() function is called, which ensures all
1457 * the tree properties are preserved:
1458 * - node->child->parent always equals node
1459 * - tree->root->parent always equals NULL
1460 * - number of kids == 0 or number of elements + 1;
1461 * - tree has the same depth everywhere
1462 * - every node has at least one element
1463 * - subtree element counts are accurate
1464 * - any NULL kid pointer is accompanied by a zero count
1465 * - in a sorted tree: ordering property between elements of a
1466 * node and elements of its children is preserved
1467 * and also ensures the list represented by the tree is the same
1468 * list it should be. (This last check also doubly verifies the
1469 * ordering properties, because the `same list it should be' is by
1470 * definition correctly ordered. It also ensures all nodes are
1471 * distinct, because the enum functions would get caught in a loop
1477 #define srealloc realloc
1480 * Error reporting function.
1482 void error(char *fmt, ...) {
1486 vfprintf(stdout, fmt, ap);
1491 /* The array representation of the data. */
1493 int arraylen, arraysize;
1496 /* The tree representation of the same data. */
1500 * Routines to provide a diagnostic printout of a tree. Currently
1501 * relies on every element in the tree being a one-character string
1508 int dispnode(node234 *n, int level, dispctx *ctx) {
1510 int xpos = strlen(ctx->levels[0]);
1514 len = sprintf(ctx->levels[0]+xpos, " %s%s%s",
1515 n->elems[0], n->elems[1], n->elems[2]);
1516 else if (n->elems[1])
1517 len = sprintf(ctx->levels[0]+xpos, " %s%s",
1518 n->elems[0], n->elems[1]);
1520 len = sprintf(ctx->levels[0]+xpos, " %s",
1522 return xpos + 1 + (len-1) / 2;
1525 int nodelen, mypos, myleft, x, i;
1527 xpos[0] = dispnode(n->kids[0], level-3, ctx);
1528 xpos[1] = dispnode(n->kids[1], level-3, ctx);
1531 xpos[2] = dispnode(n->kids[2], level-3, ctx);
1535 xpos[3] = dispnode(n->kids[3], level-3, ctx);
1540 mypos = (xpos[1] + xpos[2]) / 2;
1541 else if (nkids == 3)
1544 mypos = (xpos[0] + xpos[1]) / 2;
1545 nodelen = nkids * 2 - 1;
1546 myleft = mypos - ((nodelen-1)/2);
1547 assert(myleft >= xpos[0]);
1548 assert(myleft + nodelen-1 <= xpos[nkids-1]);
1550 x = strlen(ctx->levels[level]);
1551 while (x <= xpos[0] && x < myleft)
1552 ctx->levels[level][x++] = ' ';
1554 ctx->levels[level][x++] = '_';
1556 x += sprintf(ctx->levels[level]+x, ".%s.%s.%s.",
1557 n->elems[0], n->elems[1], n->elems[2]);
1559 x += sprintf(ctx->levels[level]+x, ".%s.%s.",
1560 n->elems[0], n->elems[1]);
1562 x += sprintf(ctx->levels[level]+x, ".%s.",
1564 while (x < xpos[nkids-1])
1565 ctx->levels[level][x++] = '_';
1566 ctx->levels[level][x] = '\0';
1568 x = strlen(ctx->levels[level-1]);
1569 for (i = 0; i < nkids; i++) {
1572 if (i > 0 && i < nkids-1)
1578 while (x < pos && x < rpos)
1579 ctx->levels[level-1][x++] = ' ';
1581 ctx->levels[level-1][x++] = '|';
1582 while (x < pos || x < rpos)
1583 ctx->levels[level-1][x++] = '_';
1585 ctx->levels[level-1][x++] = '|';
1587 ctx->levels[level-1][x] = '\0';
1589 x = strlen(ctx->levels[level-2]);
1590 for (i = 0; i < nkids; i++) {
1594 ctx->levels[level-2][x++] = ' ';
1595 ctx->levels[level-2][x++] = '|';
1597 ctx->levels[level-2][x] = '\0';
1603 void disptree(tree234 *t) {
1606 int width = count234(t);
1607 int ht = height234(t) * 3 - 2;
1611 printf("[empty tree]\n");
1614 leveldata = smalloc(ht * (width+2));
1615 ctx.levels = smalloc(ht * sizeof(char *));
1616 for (i = 0; i < ht; i++) {
1617 ctx.levels[i] = leveldata + i * (width+2);
1618 ctx.levels[i][0] = '\0';
1621 (void) dispnode(t->root, ht-1, &ctx);
1624 printf("%s\n", ctx.levels[i]);
1635 int chknode(chkctx *ctx, int level, node234 *node,
1636 void *lowbound, void *highbound) {
1641 /* Count the non-NULL kids. */
1642 for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
1643 /* Ensure no kids beyond the first NULL are non-NULL. */
1644 for (i = nkids; i < 4; i++)
1645 if (node->kids[i]) {
1646 error("node %p: nkids=%d but kids[%d] non-NULL",
1648 } else if (node->counts[i]) {
1649 error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
1650 node, i, i, node->counts[i]);
1653 /* Count the non-NULL elements. */
1654 for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
1655 /* Ensure no elements beyond the first NULL are non-NULL. */
1656 for (i = nelems; i < 3; i++)
1657 if (node->elems[i]) {
1658 error("node %p: nelems=%d but elems[%d] non-NULL",
1664 * If nkids==0, this is a leaf node; verify that the tree
1665 * depth is the same everywhere.
1667 if (ctx->treedepth < 0)
1668 ctx->treedepth = level; /* we didn't know the depth yet */
1669 else if (ctx->treedepth != level)
1670 error("node %p: leaf at depth %d, previously seen depth %d",
1671 node, level, ctx->treedepth);
1674 * If nkids != 0, then it should be nelems+1, unless nelems
1675 * is 0 in which case nkids should also be 0 (and so we
1676 * shouldn't be in this condition at all).
1678 int shouldkids = (nelems ? nelems+1 : 0);
1679 if (nkids != shouldkids) {
1680 error("node %p: %d elems should mean %d kids but has %d",
1681 node, nelems, shouldkids, nkids);
1686 * nelems should be at least 1.
1689 error("node %p: no elems", node, nkids);
1693 * Add nelems to the running element count of the whole tree.
1695 ctx->elemcount += nelems;
1698 * Check ordering property: all elements should be strictly >
1699 * lowbound, strictly < highbound, and strictly < each other in
1700 * sequence. (lowbound and highbound are NULL at edges of tree
1701 * - both NULL at root node - and NULL is considered to be <
1702 * everything and > everything. IYSWIM.)
1705 for (i = -1; i < nelems; i++) {
1706 void *lower = (i == -1 ? lowbound : node->elems[i]);
1707 void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
1708 if (lower && higher && cmp(lower, higher) >= 0) {
1709 error("node %p: kid comparison [%d=%s,%d=%s] failed",
1710 node, i, lower, i+1, higher);
1716 * Check parent pointers: all non-NULL kids should have a
1717 * parent pointer coming back to this node.
1719 for (i = 0; i < nkids; i++)
1720 if (node->kids[i]->parent != node) {
1721 error("node %p kid %d: parent ptr is %p not %p",
1722 node, i, node->kids[i]->parent, node);
1727 * Now (finally!) recurse into subtrees.
1731 for (i = 0; i < nkids; i++) {
1732 void *lower = (i == 0 ? lowbound : node->elems[i-1]);
1733 void *higher = (i >= nelems ? highbound : node->elems[i]);
1734 int subcount = chknode(ctx, level+1, node->kids[i], lower, higher);
1735 if (node->counts[i] != subcount) {
1736 error("node %p kid %d: count says %d, subtree really has %d",
1737 node, i, node->counts[i], subcount);
1745 void verifytree(tree234 *tree, void **array, int arraylen) {
1750 ctx.treedepth = -1; /* depth unknown yet */
1751 ctx.elemcount = 0; /* no elements seen yet */
1753 * Verify validity of tree properties.
1756 if (tree->root->parent != NULL)
1757 error("root->parent is %p should be null", tree->root->parent);
1758 chknode(&ctx, 0, tree->root, NULL, NULL);
1760 printf("tree depth: %d\n", ctx.treedepth);
1762 * Enumerate the tree and ensure it matches up to the array.
1764 for (i = 0; NULL != (p = index234(tree, i)); i++) {
1766 error("tree contains more than %d elements", arraylen);
1768 error("enum at position %d: array says %s, tree says %s",
1771 if (ctx.elemcount != i) {
1772 error("tree really contains %d elements, enum gave %d",
1776 error("enum gave only %d elements, array has %d", i, arraylen);
1779 if (ctx.elemcount != i) {
1780 error("tree really contains %d elements, count234 gave %d",
1784 void verify(void) { verifytree(tree, array, arraylen); }
1786 void internal_addtest(void *elem, int index, void *realret) {
1790 if (arraysize < arraylen+1) {
1791 arraysize = arraylen+1+256;
1792 array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
1793 srealloc(array, arraysize*sizeof(*array)));
1797 /* now i points to the first element >= elem */
1798 retval = elem; /* expect elem returned (success) */
1799 for (j = arraylen; j > i; j--)
1800 array[j] = array[j-1];
1801 array[i] = elem; /* add elem to array */
1804 if (realret != retval) {
1805 error("add: retval was %p expected %p", realret, retval);
1811 void addtest(void *elem) {
1815 realret = add234(tree, elem);
1818 while (i < arraylen && cmp(elem, array[i]) > 0)
1820 if (i < arraylen && !cmp(elem, array[i])) {
1821 void *retval = array[i]; /* expect that returned not elem */
1822 if (realret != retval) {
1823 error("add: retval was %p expected %p", realret, retval);
1826 internal_addtest(elem, i, realret);
1829 void addpostest(void *elem, int i) {
1832 realret = addpos234(tree, elem, i);
1834 internal_addtest(elem, i, realret);
1837 void delpostest(int i) {
1839 void *elem = array[i], *ret;
1841 /* i points to the right element */
1842 while (i < arraylen-1) {
1843 array[i] = array[i+1];
1846 arraylen--; /* delete elem from array */
1849 ret = del234(tree, elem);
1851 ret = delpos234(tree, index);
1854 error("del returned %p, expected %p", ret, elem);
1860 void deltest(void *elem) {
1864 while (i < arraylen && cmp(elem, array[i]) > 0)
1866 if (i >= arraylen || cmp(elem, array[i]) != 0)
1867 return; /* don't do it! */
1871 /* A sample data set and test utility. Designed for pseudo-randomness,
1872 * and yet repeatability. */
1875 * This random number generator uses the `portable implementation'
1876 * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
1879 int randomnumber(unsigned *seed) {
1880 *seed *= 1103515245;
1882 return ((*seed) / 65536) % 32768;
1885 int mycmp(void *av, void *bv) {
1886 char const *a = (char const *)av;
1887 char const *b = (char const *)bv;
1888 return strcmp(a, b);
1891 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
1894 "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i",
1895 "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E",
1896 "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u",
1897 "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y",
1900 "a", "ab", "absque", "coram", "de",
1901 "palam", "clam", "cum", "ex", "e",
1902 "sine", "tenus", "pro", "prae",
1903 "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
1904 "penguin", "blancmange", "pangolin", "whale", "hedgehog",
1905 "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
1906 "murfl", "spoo", "breen", "flarn", "octothorpe",
1907 "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
1908 "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
1909 "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
1910 "wand", "ring", "amulet"
1914 #define NSTR lenof(strings)
1916 void findtest(void) {
1917 static const int rels[] = {
1918 REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
1920 static const char *const relnames[] = {
1921 "EQ", "GE", "LE", "LT", "GT"
1923 int i, j, rel, index;
1924 char *p, *ret, *realret, *realret2;
1927 for (i = 0; i < (int)NSTR; i++) {
1929 for (j = 0; j < (int)(sizeof(rels)/sizeof(*rels)); j++) {
1932 lo = 0; hi = arraylen-1;
1934 mid = (lo + hi) / 2;
1935 c = strcmp(p, array[mid]);
1945 if (rel == REL234_LT)
1946 ret = (mid > 0 ? array[--mid] : NULL);
1947 else if (rel == REL234_GT)
1948 ret = (mid < arraylen-1 ? array[++mid] : NULL);
1953 if (rel == REL234_LT || rel == REL234_LE) {
1955 ret = (hi >= 0 ? array[hi] : NULL);
1956 } else if (rel == REL234_GT || rel == REL234_GE) {
1958 ret = (lo < arraylen ? array[lo] : NULL);
1963 realret = findrelpos234(tree, p, NULL, rel, &index);
1964 if (realret != ret) {
1965 error("find(\"%s\",%s) gave %s should be %s",
1966 p, relnames[j], realret, ret);
1968 if (realret && index != mid) {
1969 error("find(\"%s\",%s) gave %d should be %d",
1970 p, relnames[j], index, mid);
1972 if (realret && rel == REL234_EQ) {
1973 realret2 = index234(tree, index);
1974 if (realret2 != realret) {
1975 error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
1976 p, relnames[j], realret, index, index, realret2);
1980 printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
1986 realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
1987 if (arraylen && (realret != array[0] || index != 0)) {
1988 error("find(NULL,GT) gave %s(%d) should be %s(0)",
1989 realret, index, array[0]);
1990 } else if (!arraylen && (realret != NULL)) {
1991 error("find(NULL,GT) gave %s(%d) should be NULL",
1995 realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
1996 if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
1997 error("find(NULL,LT) gave %s(%d) should be %s(0)",
1998 realret, index, array[arraylen-1]);
1999 } else if (!arraylen && (realret != NULL)) {
2000 error("find(NULL,LT) gave %s(%d) should be NULL",
2005 void splittest(tree234 *tree, void **array, int arraylen) {
2007 tree234 *tree3, *tree4;
2008 for (i = 0; i <= arraylen; i++) {
2009 tree3 = copytree234(tree, NULL, NULL);
2010 tree4 = splitpos234(tree3, i, 0);
2011 verifytree(tree3, array, i);
2012 verifytree(tree4, array+i, arraylen-i);
2013 join234(tree3, tree4);
2014 freetree234(tree4); /* left empty by join */
2015 verifytree(tree3, array, arraylen);
2023 int tworoot, tmplen;
2025 tree234 *tree2, *tree3, *tree4;
2028 setvbuf(stdout, NULL, _IOLBF, 0);
2030 for (i = 0; i < (int)NSTR; i++) in[i] = 0;
2032 arraylen = arraysize = 0;
2033 tree = newtree234(mycmp);
2037 for (i = 0; i < 10000; i++) {
2038 j = randomnumber(&seed);
2040 printf("trial: %d\n", i);
2042 printf("deleting %s (%d)\n", strings[j], j);
2043 deltest(strings[j]);
2046 printf("adding %s (%d)\n", strings[j], j);
2047 addtest(strings[j]);
2054 while (arraylen > 0) {
2055 j = randomnumber(&seed);
2063 * Now try an unsorted tree. We don't really need to test
2064 * delpos234 because we know del234 is based on it, so it's
2065 * already been tested in the above sorted-tree code; but for
2066 * completeness we'll use it to tear down our unsorted tree
2067 * once we've built it.
2069 tree = newtree234(NULL);
2072 for (i = 0; i < 1000; i++) {
2073 printf("trial: %d\n", i);
2074 j = randomnumber(&seed);
2076 k = randomnumber(&seed);
2077 k %= count234(tree)+1;
2078 printf("adding string %s at index %d\n", strings[j], k);
2079 addpostest(strings[j], k);
2083 * While we have this tree in its full form, we'll take a copy
2084 * of it to use in split and join testing.
2086 tree2 = copytree234(tree, NULL, NULL);
2087 verifytree(tree2, array, arraylen);/* check the copy is accurate */
2089 * Split tests. Split the tree at every possible point and
2090 * check the resulting subtrees.
2092 tworoot = (!tree2->root->elems[1]);/* see if it has a 2-root */
2093 splittest(tree2, array, arraylen);
2095 * Now do the split test again, but on a tree that has a 2-root
2096 * (if the previous one didn't) or doesn't (if the previous one
2100 while ((!tree2->root->elems[1]) == tworoot) {
2101 delpos234(tree2, --tmplen);
2103 printf("now trying splits on second tree\n");
2104 splittest(tree2, array, tmplen);
2108 * Back to the main testing of uncounted trees.
2110 while (count234(tree) > 0) {
2111 printf("cleanup: tree size %d\n", count234(tree));
2112 j = randomnumber(&seed);
2113 j %= count234(tree);
2114 printf("deleting string %s from index %d\n", (char *)array[j], j);
2120 * Finally, do some testing on split/join on _sorted_ trees. At
2121 * the same time, we'll be testing split on very small trees.
2123 tree = newtree234(mycmp);
2126 for (i = 0; i < 16; i++) {
2127 addtest(strings[i]);
2128 tree2 = copytree234(tree, NULL, NULL);
2129 splittest(tree2, array, arraylen);
2135 * Test silly cases of join: join(emptytree, emptytree), and
2136 * also ensure join correctly spots when sorted trees fail the
2137 * ordering constraint.
2139 tree = newtree234(mycmp);
2140 tree2 = newtree234(mycmp);
2141 tree3 = newtree234(mycmp);
2142 tree4 = newtree234(mycmp);
2143 assert(mycmp(strings[0], strings[1]) < 0); /* just in case :-) */
2144 add234(tree2, strings[1]);
2145 add234(tree4, strings[0]);
2146 array[0] = strings[0];
2147 array[1] = strings[1];
2148 verifytree(tree, array, 0);
2149 verifytree(tree2, array+1, 1);
2150 verifytree(tree3, array, 0);
2151 verifytree(tree4, array, 1);
2155 * - join(tree,tree3) should leave both tree and tree3 unchanged.
2156 * - joinr(tree,tree2) should leave both tree and tree2 unchanged.
2157 * - join(tree4,tree3) should leave both tree3 and tree4 unchanged.
2158 * - join(tree, tree2) should move the element from tree2 to tree.
2159 * - joinr(tree4, tree3) should move the element from tree4 to tree3.
2160 * - join(tree,tree3) should return NULL and leave both unchanged.
2161 * - join(tree3,tree) should work and create a bigger tree in tree3.
2163 assert(tree == join234(tree, tree3));
2164 verifytree(tree, array, 0);
2165 verifytree(tree3, array, 0);
2166 assert(tree2 == join234r(tree, tree2));
2167 verifytree(tree, array, 0);
2168 verifytree(tree2, array+1, 1);
2169 assert(tree4 == join234(tree4, tree3));
2170 verifytree(tree3, array, 0);
2171 verifytree(tree4, array, 1);
2172 assert(tree == join234(tree, tree2));
2173 verifytree(tree, array+1, 1);
2174 verifytree(tree2, array, 0);
2175 assert(tree3 == join234r(tree4, tree3));
2176 verifytree(tree3, array, 1);
2177 verifytree(tree4, array, 0);
2178 assert(NULL == join234(tree, tree3));
2179 verifytree(tree, array+1, 1);
2180 verifytree(tree3, array, 1);
2181 assert(tree3 == join234(tree3, tree));
2182 verifytree(tree3, array, 2);
2183 verifytree(tree, array, 0);
2190 #if 0 /* sorted list of strings might be useful */
2192 "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",