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
));
579 LOG((" node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d index=%d\n",
581 n
->kids
[0], n
->counts
[0], n
->elems
[0],
582 n
->kids
[1], n
->counts
[1], n
->elems
[1],
583 n
->kids
[2], n
->counts
[2], n
->elems
[2],
584 n
->kids
[3], n
->counts
[3],
586 if (index
< n
->counts
[0]) {
588 } else if (index
-= n
->counts
[0]+1, index
< 0) {
590 } else if (index
< n
->counts
[1]) {
592 } else if (index
-= n
->counts
[1]+1, index
< 0) {
594 } else if (index
< n
->counts
[2]) {
596 } else if (index
-= n
->counts
[2]+1, index
< 0) {
602 * Recurse down to subtree ki. If it has only one element,
603 * we have to do some transformation to start with.
605 LOG((" moving to subtree %d\n", ki
));
607 if (!sub
->elems
[1]) {
608 LOG((" subtree has only one element!\n", ki
));
609 if (ki
> 0 && n
->kids
[ki
-1]->elems
[1]) {
611 * Case 3a, left-handed variant. Child ki has
612 * only one element, but child ki-1 has two or
613 * more. So we need to move a subtree from ki-1
618 * [more] a A b B c d D e [more] a A b c C d D e
620 node234
*sib
= n
->kids
[ki
-1];
621 int lastelem
= (sib
->elems
[2] ?
2 :
622 sib
->elems
[1] ?
1 : 0);
623 sub
->kids
[2] = sub
->kids
[1];
624 sub
->counts
[2] = sub
->counts
[1];
625 sub
->elems
[1] = sub
->elems
[0];
626 sub
->kids
[1] = sub
->kids
[0];
627 sub
->counts
[1] = sub
->counts
[0];
628 sub
->elems
[0] = n
->elems
[ki
-1];
629 sub
->kids
[0] = sib
->kids
[lastelem
+1];
630 sub
->counts
[0] = sib
->counts
[lastelem
+1];
631 if (sub
->kids
[0]) sub
->kids
[0]->parent
= sub
;
632 n
->elems
[ki
-1] = sib
->elems
[lastelem
];
633 sib
->kids
[lastelem
+1] = NULL
;
634 sib
->counts
[lastelem
+1] = 0;
635 sib
->elems
[lastelem
] = NULL
;
636 n
->counts
[ki
] = countnode234(sub
);
637 LOG((" case 3a left\n"));
638 LOG((" index and left subtree count before adjustment: %d, %d\n",
639 index
, n
->counts
[ki
-1]));
640 index
+= n
->counts
[ki
-1];
641 n
->counts
[ki
-1] = countnode234(sib
);
642 index
-= n
->counts
[ki
-1];
643 LOG((" index and left subtree count after adjustment: %d, %d\n",
644 index
, n
->counts
[ki
-1]));
645 } else if (ki
< 3 && n
->kids
[ki
+1] &&
646 n
->kids
[ki
+1]->elems
[1]) {
648 * Case 3a, right-handed variant. ki has only
649 * one element but ki+1 has two or more. Move a
650 * subtree from ki+1 to ki.
654 * a A b c C d D e [more] a A b B c d D e [more]
656 node234
*sib
= n
->kids
[ki
+1];
658 sub
->elems
[1] = n
->elems
[ki
];
659 sub
->kids
[2] = sib
->kids
[0];
660 sub
->counts
[2] = sib
->counts
[0];
661 if (sub
->kids
[2]) sub
->kids
[2]->parent
= sub
;
662 n
->elems
[ki
] = sib
->elems
[0];
663 sib
->kids
[0] = sib
->kids
[1];
664 sib
->counts
[0] = sib
->counts
[1];
665 for (j
= 0; j
< 2 && sib
->elems
[j
+1]; j
++) {
666 sib
->kids
[j
+1] = sib
->kids
[j
+2];
667 sib
->counts
[j
+1] = sib
->counts
[j
+2];
668 sib
->elems
[j
] = sib
->elems
[j
+1];
670 sib
->kids
[j
+1] = NULL
;
671 sib
->counts
[j
+1] = 0;
672 sib
->elems
[j
] = NULL
;
673 n
->counts
[ki
] = countnode234(sub
);
674 n
->counts
[ki
+1] = countnode234(sib
);
675 LOG((" case 3a right\n"));
678 * Case 3b. ki has only one element, and has no
679 * neighbour with more than one. So pick a
680 * neighbour and merge it with ki, taking an
681 * element down from n to go in the middle.
685 * a A b c C d a A b B c C d
687 * (Since at all points we have avoided
688 * descending to a node with only one element,
689 * we can be sure that n is not reduced to
690 * nothingness by this move, _unless_ it was
691 * the very first node, ie the root of the
692 * tree. In that case we remove the now-empty
693 * root and replace it with its single large
701 index
+= n
->counts
[ki
] + 1;
706 sub
->kids
[3] = sub
->kids
[1];
707 sub
->counts
[3] = sub
->counts
[1];
708 sub
->elems
[2] = sub
->elems
[0];
709 sub
->kids
[2] = sub
->kids
[0];
710 sub
->counts
[2] = sub
->counts
[0];
711 sub
->elems
[1] = n
->elems
[ki
];
712 sub
->kids
[1] = sib
->kids
[1];
713 sub
->counts
[1] = sib
->counts
[1];
714 if (sub
->kids
[1]) sub
->kids
[1]->parent
= sub
;
715 sub
->elems
[0] = sib
->elems
[0];
716 sub
->kids
[0] = sib
->kids
[0];
717 sub
->counts
[0] = sib
->counts
[0];
718 if (sub
->kids
[0]) sub
->kids
[0]->parent
= sub
;
720 n
->counts
[ki
+1] = countnode234(sub
);
725 * That's built the big node in sub. Now we
726 * need to remove the reference to sib in n.
728 for (j
= ki
; j
< 3 && n
->kids
[j
+1]; j
++) {
729 n
->kids
[j
] = n
->kids
[j
+1];
730 n
->counts
[j
] = n
->counts
[j
+1];
731 n
->elems
[j
] = j
<2 ? n
->elems
[j
+1] : NULL
;
735 if (j
< 3) n
->elems
[j
] = NULL
;
736 LOG((" case 3b ki=%d\n", ki
));
740 * The root is empty and needs to be
743 LOG((" shifting root!\n"));
753 retval
= n
->elems
[ei
];
756 return NULL
; /* although this shouldn't happen */
759 * Treat special case: this is the one remaining item in
760 * the tree. n is the tree root (no parent), has one
761 * element (no elems[1]), and has no kids (no kids[0]).
763 if (!n
->parent
&& !n
->elems
[1] && !n
->kids
[0]) {
764 LOG((" removed last element in tree\n"));
771 * Now we have the element we want, as n->elems[ei], and we
772 * have also arranged for that element not to be the only
773 * one in its node. So...
776 if (!n
->kids
[0] && n
->elems
[1]) {
778 * Case 1. n is a leaf node with more than one element,
779 * so it's _really easy_. Just delete the thing and
784 for (i
= ei
; i
< 2 && n
->elems
[i
+1]; i
++)
785 n
->elems
[i
] = n
->elems
[i
+1];
788 * Having done that to the leaf node, we now go back up
789 * the tree fixing the counts.
793 childnum
= (n
->parent
->kids
[0] == n ?
0 :
794 n
->parent
->kids
[1] == n ?
1 :
795 n
->parent
->kids
[2] == n ?
2 : 3);
796 n
->parent
->counts
[childnum
]--;
799 return retval
; /* finished! */
800 } else if (n
->kids
[ei
]->elems
[1]) {
802 * Case 2a. n is an internal node, and the root of the
803 * subtree to the left of e has more than one element.
804 * So find the predecessor p to e (ie the largest node
805 * in that subtree), place it where e currently is, and
806 * then start the deletion process over again on the
807 * subtree with p as target.
809 node234
*m
= n
->kids
[ei
];
813 m
= (m
->kids
[3] ? m
->kids
[3] :
814 m
->kids
[2] ? m
->kids
[2] :
815 m
->kids
[1] ? m
->kids
[1] : m
->kids
[0]);
817 target
= (m
->elems
[2] ? m
->elems
[2] :
818 m
->elems
[1] ? m
->elems
[1] : m
->elems
[0]);
819 n
->elems
[ei
] = target
;
820 index
= n
->counts
[ei
]-1;
822 } else if (n
->kids
[ei
+1]->elems
[1]) {
824 * Case 2b, symmetric to 2a but s/left/right/ and
825 * s/predecessor/successor/. (And s/largest/smallest/).
827 node234
*m
= n
->kids
[ei
+1];
833 target
= m
->elems
[0];
834 n
->elems
[ei
] = target
;
839 * Case 2c. n is an internal node, and the subtrees to
840 * the left and right of e both have only one element.
841 * So combine the two subnodes into a single big node
842 * with their own elements on the left and right and e
843 * in the middle, then restart the deletion process on
844 * that subtree, with e still as target.
846 node234
*a
= n
->kids
[ei
], *b
= n
->kids
[ei
+1];
850 a
->elems
[1] = n
->elems
[ei
];
851 a
->kids
[2] = b
->kids
[0];
852 a
->counts
[2] = b
->counts
[0];
853 if (a
->kids
[2]) a
->kids
[2]->parent
= a
;
854 a
->elems
[2] = b
->elems
[0];
855 a
->kids
[3] = b
->kids
[1];
856 a
->counts
[3] = b
->counts
[1];
857 if (a
->kids
[3]) a
->kids
[3]->parent
= a
;
859 n
->counts
[ei
] = countnode234(a
);
861 * That's built the big node in a, and destroyed b. Now
862 * remove the reference to b (and e) in n.
864 for (j
= ei
; j
< 2 && n
->elems
[j
+1]; j
++) {
865 n
->elems
[j
] = n
->elems
[j
+1];
866 n
->kids
[j
+1] = n
->kids
[j
+2];
867 n
->counts
[j
+1] = n
->counts
[j
+2];
873 * It's possible, in this case, that we've just removed
874 * the only element in the root of the tree. If so,
877 if (n
->elems
[0] == NULL
) {
878 LOG((" shifting root!\n"));
884 * Now go round the deletion process again, with n
885 * pointing at the new big node and e still the same.
888 index
= a
->counts
[0] + a
->counts
[1] + 1;
892 void *delpos234(tree234
*t
, int index
) {
893 if (index
< 0 || index
>= countnode234(t
->root
))
895 return delpos234_internal(t
, index
);
897 void *del234(tree234
*t
, void *e
) {
899 if (!findrelpos234(t
, e
, NULL
, REL234_EQ
, &index
))
900 return NULL
; /* it wasn't in there anyway */
901 return delpos234_internal(t
, index
); /* it's there; delete it. */
907 * Test code for the 2-3-4 tree. This code maintains an alternative
908 * representation of the data in the tree, in an array (using the
909 * obvious and slow insert and delete functions). After each tree
910 * operation, the verify() function is called, which ensures all
911 * the tree properties are preserved:
912 * - node->child->parent always equals node
913 * - tree->root->parent always equals NULL
914 * - number of kids == 0 or number of elements + 1;
915 * - tree has the same depth everywhere
916 * - every node has at least one element
917 * - subtree element counts are accurate
918 * - any NULL kid pointer is accompanied by a zero count
919 * - in a sorted tree: ordering property between elements of a
920 * node and elements of its children is preserved
921 * and also ensures the list represented by the tree is the same
922 * list it should be. (This last check also doubly verifies the
923 * ordering properties, because the `same list it should be' is by
924 * definition correctly ordered. It also ensures all nodes are
925 * distinct, because the enum functions would get caught in a loop
931 #define srealloc realloc
934 * Error reporting function.
936 void error(char *fmt
, ...) {
940 vfprintf(stdout
, fmt
, ap
);
945 /* The array representation of the data. */
947 int arraylen
, arraysize
;
950 /* The tree representation of the same data. */
958 int chknode(chkctx
*ctx
, int level
, node234
*node
,
959 void *lowbound
, void *highbound
) {
964 /* Count the non-NULL kids. */
965 for (nkids
= 0; nkids
< 4 && node
->kids
[nkids
]; nkids
++);
966 /* Ensure no kids beyond the first NULL are non-NULL. */
967 for (i
= nkids
; i
< 4; i
++)
969 error("node %p: nkids=%d but kids[%d] non-NULL",
971 } else if (node
->counts
[i
]) {
972 error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
973 node
, i
, i
, node
->counts
[i
]);
976 /* Count the non-NULL elements. */
977 for (nelems
= 0; nelems
< 3 && node
->elems
[nelems
]; nelems
++);
978 /* Ensure no elements beyond the first NULL are non-NULL. */
979 for (i
= nelems
; i
< 3; i
++)
980 if (node
->elems
[i
]) {
981 error("node %p: nelems=%d but elems[%d] non-NULL",
987 * If nkids==0, this is a leaf node; verify that the tree
988 * depth is the same everywhere.
990 if (ctx
->treedepth
< 0)
991 ctx
->treedepth
= level
; /* we didn't know the depth yet */
992 else if (ctx
->treedepth
!= level
)
993 error("node %p: leaf at depth %d, previously seen depth %d",
994 node
, level
, ctx
->treedepth
);
997 * If nkids != 0, then it should be nelems+1, unless nelems
998 * is 0 in which case nkids should also be 0 (and so we
999 * shouldn't be in this condition at all).
1001 int shouldkids
= (nelems ? nelems
+1 : 0);
1002 if (nkids
!= shouldkids
) {
1003 error("node %p: %d elems should mean %d kids but has %d",
1004 node
, nelems
, shouldkids
, nkids
);
1009 * nelems should be at least 1.
1012 error("node %p: no elems", node
, nkids
);
1016 * Add nelems to the running element count of the whole tree.
1018 ctx
->elemcount
+= nelems
;
1021 * Check ordering property: all elements should be strictly >
1022 * lowbound, strictly < highbound, and strictly < each other in
1023 * sequence. (lowbound and highbound are NULL at edges of tree
1024 * - both NULL at root node - and NULL is considered to be <
1025 * everything and > everything. IYSWIM.)
1028 for (i
= -1; i
< nelems
; i
++) {
1029 void *lower
= (i
== -1 ? lowbound
: node
->elems
[i
]);
1030 void *higher
= (i
+1 == nelems ? highbound
: node
->elems
[i
+1]);
1031 if (lower
&& higher
&& cmp(lower
, higher
) >= 0) {
1032 error("node %p: kid comparison [%d=%s,%d=%s] failed",
1033 node
, i
, lower
, i
+1, higher
);
1039 * Check parent pointers: all non-NULL kids should have a
1040 * parent pointer coming back to this node.
1042 for (i
= 0; i
< nkids
; i
++)
1043 if (node
->kids
[i
]->parent
!= node
) {
1044 error("node %p kid %d: parent ptr is %p not %p",
1045 node
, i
, node
->kids
[i
]->parent
, node
);
1050 * Now (finally!) recurse into subtrees.
1054 for (i
= 0; i
< nkids
; i
++) {
1055 void *lower
= (i
== 0 ? lowbound
: node
->elems
[i
-1]);
1056 void *higher
= (i
>= nelems ? highbound
: node
->elems
[i
]);
1057 int subcount
= chknode(ctx
, level
+1, node
->kids
[i
], lower
, higher
);
1058 if (node
->counts
[i
] != subcount
) {
1059 error("node %p kid %d: count says %d, subtree really has %d",
1060 node
, i
, node
->counts
[i
], subcount
);
1073 ctx
.treedepth
= -1; /* depth unknown yet */
1074 ctx
.elemcount
= 0; /* no elements seen yet */
1076 * Verify validity of tree properties.
1079 if (tree
->root
->parent
!= NULL
)
1080 error("root->parent is %p should be null", tree
->root
->parent
);
1081 chknode(&ctx
, 0, tree
->root
, NULL
, NULL
);
1083 printf("tree depth: %d\n", ctx
.treedepth
);
1085 * Enumerate the tree and ensure it matches up to the array.
1087 for (i
= 0; NULL
!= (p
= index234(tree
, i
)); i
++) {
1089 error("tree contains more than %d elements", arraylen
);
1091 error("enum at position %d: array says %s, tree says %s",
1094 if (ctx
.elemcount
!= i
) {
1095 error("tree really contains %d elements, enum gave %d",
1099 error("enum gave only %d elements, array has %d", i
, arraylen
);
1102 if (ctx
.elemcount
!= i
) {
1103 error("tree really contains %d elements, count234 gave %d",
1108 void internal_addtest(void *elem
, int index
, void *realret
) {
1112 if (arraysize
< arraylen
+1) {
1113 arraysize
= arraylen
+1+256;
1114 array
= (array
== NULL ?
smalloc(arraysize
*sizeof(*array
)) :
1115 srealloc(array
, arraysize
*sizeof(*array
)));
1119 /* now i points to the first element >= elem */
1120 retval
= elem
; /* expect elem returned (success) */
1121 for (j
= arraylen
; j
> i
; j
--)
1122 array
[j
] = array
[j
-1];
1123 array
[i
] = elem
; /* add elem to array */
1126 if (realret
!= retval
) {
1127 error("add: retval was %p expected %p", realret
, retval
);
1133 void addtest(void *elem
) {
1137 realret
= add234(tree
, elem
);
1140 while (i
< arraylen
&& cmp(elem
, array
[i
]) > 0)
1142 if (i
< arraylen
&& !cmp(elem
, array
[i
])) {
1143 void *retval
= array
[i
]; /* expect that returned not elem */
1144 if (realret
!= retval
) {
1145 error("add: retval was %p expected %p", realret
, retval
);
1148 internal_addtest(elem
, i
, realret
);
1151 void addpostest(void *elem
, int i
) {
1154 realret
= addpos234(tree
, elem
, i
);
1156 internal_addtest(elem
, i
, realret
);
1159 void delpostest(int i
) {
1161 void *elem
= array
[i
], *ret
;
1163 /* i points to the right element */
1164 while (i
< arraylen
-1) {
1165 array
[i
] = array
[i
+1];
1168 arraylen
--; /* delete elem from array */
1171 ret
= del234(tree
, elem
);
1173 ret
= delpos234(tree
, index
);
1176 error("del returned %p, expected %p", ret
, elem
);
1182 void deltest(void *elem
) {
1186 while (i
< arraylen
&& cmp(elem
, array
[i
]) > 0)
1188 if (i
>= arraylen
|| cmp(elem
, array
[i
]) != 0)
1189 return; /* don't do it! */
1193 /* A sample data set and test utility. Designed for pseudo-randomness,
1194 * and yet repeatability. */
1197 * This random number generator uses the `portable implementation'
1198 * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
1201 int randomnumber(unsigned *seed
) {
1202 *seed
*= 1103515245;
1204 return ((*seed
) / 65536) % 32768;
1207 int mycmp(void *av
, void *bv
) {
1208 char const *a
= (char const *)av
;
1209 char const *b
= (char const *)bv
;
1210 return strcmp(a
, b
);
1213 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
1216 "a", "ab", "absque", "coram", "de",
1217 "palam", "clam", "cum", "ex", "e",
1218 "sine", "tenus", "pro", "prae",
1219 "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
1220 "penguin", "blancmange", "pangolin", "whale", "hedgehog",
1221 "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
1222 "murfl", "spoo", "breen", "flarn", "octothorpe",
1223 "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
1224 "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
1225 "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
1226 "wand", "ring", "amulet"
1229 #define NSTR lenof(strings)
1231 int findtest(void) {
1232 const static int rels
[] = {
1233 REL234_EQ
, REL234_GE
, REL234_LE
, REL234_LT
, REL234_GT
1235 const static char *const relnames
[] = {
1236 "EQ", "GE", "LE", "LT", "GT"
1238 int i
, j
, rel
, index
;
1239 char *p
, *ret
, *realret
, *realret2
;
1242 for (i
= 0; i
< NSTR
; i
++) {
1244 for (j
= 0; j
< sizeof(rels
)/sizeof(*rels
); j
++) {
1247 lo
= 0; hi
= arraylen
-1;
1249 mid
= (lo
+ hi
) / 2;
1250 c
= strcmp(p
, array
[mid
]);
1260 if (rel
== REL234_LT
)
1261 ret
= (mid
> 0 ? array
[--mid
] : NULL
);
1262 else if (rel
== REL234_GT
)
1263 ret
= (mid
< arraylen
-1 ? array
[++mid
] : NULL
);
1268 if (rel
== REL234_LT
|| rel
== REL234_LE
) {
1270 ret
= (hi
>= 0 ? array
[hi
] : NULL
);
1271 } else if (rel
== REL234_GT
|| rel
== REL234_GE
) {
1273 ret
= (lo
< arraylen ? array
[lo
] : NULL
);
1278 realret
= findrelpos234(tree
, p
, NULL
, rel
, &index
);
1279 if (realret
!= ret
) {
1280 error("find(\"%s\",%s) gave %s should be %s",
1281 p
, relnames
[j
], realret
, ret
);
1283 if (realret
&& index
!= mid
) {
1284 error("find(\"%s\",%s) gave %d should be %d",
1285 p
, relnames
[j
], index
, mid
);
1287 if (realret
&& rel
== REL234_EQ
) {
1288 realret2
= index234(tree
, index
);
1289 if (realret2
!= realret
) {
1290 error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
1291 p
, relnames
[j
], realret
, index
, index
, realret2
);
1295 printf("find(\"%s\",%s) gave %s(%d)\n", p
, relnames
[j
],
1301 realret
= findrelpos234(tree
, NULL
, NULL
, REL234_GT
, &index
);
1302 if (arraylen
&& (realret
!= array
[0] || index
!= 0)) {
1303 error("find(NULL,GT) gave %s(%d) should be %s(0)",
1304 realret
, index
, array
[0]);
1305 } else if (!arraylen
&& (realret
!= NULL
)) {
1306 error("find(NULL,GT) gave %s(%d) should be NULL",
1310 realret
= findrelpos234(tree
, NULL
, NULL
, REL234_LT
, &index
);
1311 if (arraylen
&& (realret
!= array
[arraylen
-1] || index
!= arraylen
-1)) {
1312 error("find(NULL,LT) gave %s(%d) should be %s(0)",
1313 realret
, index
, array
[arraylen
-1]);
1314 } else if (!arraylen
&& (realret
!= NULL
)) {
1315 error("find(NULL,LT) gave %s(%d) should be NULL",
1325 for (i
= 0; i
< NSTR
; i
++) in
[i
] = 0;
1327 arraylen
= arraysize
= 0;
1328 tree
= newtree234(mycmp
);
1332 for (i
= 0; i
< 10000; i
++) {
1333 j
= randomnumber(&seed
);
1335 printf("trial: %d\n", i
);
1337 printf("deleting %s (%d)\n", strings
[j
], j
);
1338 deltest(strings
[j
]);
1341 printf("adding %s (%d)\n", strings
[j
], j
);
1342 addtest(strings
[j
]);
1348 while (arraylen
> 0) {
1349 j
= randomnumber(&seed
);
1357 * Now try an unsorted tree. We don't really need to test
1358 * delpos234 because we know del234 is based on it, so it's
1359 * already been tested in the above sorted-tree code; but for
1360 * completeness we'll use it to tear down our unsorted tree
1361 * once we've built it.
1363 tree
= newtree234(NULL
);
1366 for (i
= 0; i
< 1000; i
++) {
1367 printf("trial: %d\n", i
);
1368 j
= randomnumber(&seed
);
1370 k
= randomnumber(&seed
);
1371 k
%= count234(tree
)+1;
1372 printf("adding string %s at index %d\n", strings
[j
], k
);
1373 addpostest(strings
[j
], k
);
1375 while (count234(tree
) > 0) {
1376 printf("cleanup: tree size %d\n", count234(tree
));
1377 j
= randomnumber(&seed
);
1378 j
%= count234(tree
);
1379 printf("deleting string %s from index %d\n", array
[j
], j
);