2 * tree234.c: reasonably generic 2-3-4 tree routines. Currently
3 * supports insert, delete, find and iterate operations.
11 #define mknew(typ) ( (typ *) malloc (sizeof (typ)) )
15 #define LOG(x) (printf x)
32 * Create a 2-3-4 tree.
34 tree234
*newtree234(cmpfn234 cmp
) {
35 tree234
*ret
= mknew(tree234
);
36 LOG(("created tree %p\n", ret
));
43 * Free a 2-3-4 tree (not including freeing the elements).
45 static void freenode234(node234
*n
) {
48 freenode234(n
->kids
[0]);
49 freenode234(n
->kids
[1]);
50 freenode234(n
->kids
[2]);
51 freenode234(n
->kids
[3]);
54 void freetree234(tree234
*t
) {
60 * Add an element e to a 2-3-4 tree t. Returns e on success, or if
61 * an existing element compares equal, returns that.
63 void *add234(tree234
*t
, void *e
) {
64 node234
*n
, **np
, *left
, *right
;
68 LOG(("adding node %p to tree %p\n", e
, t
));
69 if (t
->root
== NULL
) {
70 t
->root
= mknew(node234
);
71 t
->root
->elems
[1] = t
->root
->elems
[2] = NULL
;
72 t
->root
->kids
[0] = t
->root
->kids
[1] = NULL
;
73 t
->root
->kids
[2] = t
->root
->kids
[3] = NULL
;
74 t
->root
->parent
= NULL
;
75 t
->root
->elems
[0] = e
;
76 LOG((" created root %p\n", t
->root
));
83 LOG((" node %p: %p [%p] %p [%p] %p [%p] %p\n",
84 n
, n
->kids
[0], n
->elems
[0], n
->kids
[1], n
->elems
[1],
85 n
->kids
[2], n
->elems
[2], n
->kids
[3]));
86 if ((c
= t
->cmp(e
, n
->elems
[0])) < 0)
89 return n
->elems
[0]; /* already exists */
90 else if (n
->elems
[1] == NULL
|| (c
= t
->cmp(e
, n
->elems
[1])) < 0)
93 return n
->elems
[1]; /* already exists */
94 else if (n
->elems
[2] == NULL
|| (c
= t
->cmp(e
, n
->elems
[2])) < 0)
97 return n
->elems
[2]; /* already exists */
100 LOG((" moving to child %d (%p)\n", np
- n
->kids
, *np
));
104 * We need to insert the new element in n at position np.
109 LOG((" at %p: %p [%p] %p [%p] %p [%p] %p\n",
110 n
, n
->kids
[0], n
->elems
[0], n
->kids
[1], n
->elems
[1],
111 n
->kids
[2], n
->elems
[2], n
->kids
[3]));
112 LOG((" need to insert %p [%p] %p at position %d\n",
113 left
, e
, right
, np
- n
->kids
));
114 if (n
->elems
[1] == NULL
) {
116 * Insert in a 2-node; simple.
118 if (np
== &n
->kids
[0]) {
119 LOG((" inserting on left of 2-node\n"));
120 n
->kids
[2] = n
->kids
[1];
121 n
->elems
[1] = n
->elems
[0];
125 } else { /* np == &n->kids[1] */
126 LOG((" inserting on right of 2-node\n"));
131 if (n
->kids
[0]) n
->kids
[0]->parent
= n
;
132 if (n
->kids
[1]) n
->kids
[1]->parent
= n
;
133 if (n
->kids
[2]) n
->kids
[2]->parent
= n
;
136 } else if (n
->elems
[2] == NULL
) {
138 * Insert in a 3-node; simple.
140 if (np
== &n
->kids
[0]) {
141 LOG((" inserting on left of 3-node\n"));
142 n
->kids
[3] = n
->kids
[2];
143 n
->elems
[2] = n
->elems
[1];
144 n
->kids
[2] = n
->kids
[1];
145 n
->elems
[1] = n
->elems
[0];
149 } else if (np
== &n
->kids
[1]) {
150 LOG((" inserting in middle of 3-node\n"));
151 n
->kids
[3] = n
->kids
[2];
152 n
->elems
[2] = n
->elems
[1];
156 } else { /* np == &n->kids[2] */
157 LOG((" inserting on right of 3-node\n"));
162 if (n
->kids
[0]) n
->kids
[0]->parent
= n
;
163 if (n
->kids
[1]) n
->kids
[1]->parent
= n
;
164 if (n
->kids
[2]) n
->kids
[2]->parent
= n
;
165 if (n
->kids
[3]) n
->kids
[3]->parent
= n
;
169 node234
*m
= mknew(node234
);
170 m
->parent
= n
->parent
;
171 LOG((" splitting a 4-node; created new node %p\n", m
));
173 * Insert in a 4-node; split into a 2-node and a
174 * 3-node, and move focus up a level.
176 * I don't think it matters which way round we put the
177 * 2 and the 3. For simplicity, we'll put the 3 first
180 if (np
== &n
->kids
[0]) {
184 m
->elems
[1] = n
->elems
[0];
185 m
->kids
[2] = n
->kids
[1];
187 n
->kids
[0] = n
->kids
[2];
188 n
->elems
[0] = n
->elems
[2];
189 n
->kids
[1] = n
->kids
[3];
190 } else if (np
== &n
->kids
[1]) {
191 m
->kids
[0] = n
->kids
[0];
192 m
->elems
[0] = n
->elems
[0];
197 n
->kids
[0] = n
->kids
[2];
198 n
->elems
[0] = n
->elems
[2];
199 n
->kids
[1] = n
->kids
[3];
200 } else if (np
== &n
->kids
[2]) {
201 m
->kids
[0] = n
->kids
[0];
202 m
->elems
[0] = n
->elems
[0];
203 m
->kids
[1] = n
->kids
[1];
204 m
->elems
[1] = n
->elems
[1];
208 n
->elems
[0] = n
->elems
[2];
209 n
->kids
[1] = n
->kids
[3];
210 } else { /* np == &n->kids[3] */
211 m
->kids
[0] = n
->kids
[0];
212 m
->elems
[0] = n
->elems
[0];
213 m
->kids
[1] = n
->kids
[1];
214 m
->elems
[1] = n
->elems
[1];
215 m
->kids
[2] = n
->kids
[2];
221 m
->kids
[3] = n
->kids
[3] = n
->kids
[2] = NULL
;
222 m
->elems
[2] = n
->elems
[2] = n
->elems
[1] = NULL
;
223 if (m
->kids
[0]) m
->kids
[0]->parent
= m
;
224 if (m
->kids
[1]) m
->kids
[1]->parent
= m
;
225 if (m
->kids
[2]) m
->kids
[2]->parent
= m
;
226 if (n
->kids
[0]) n
->kids
[0]->parent
= n
;
227 if (n
->kids
[1]) n
->kids
[1]->parent
= n
;
228 LOG((" left (%p): %p [%p] %p [%p] %p\n", m
,
229 m
->kids
[0], m
->elems
[0],
230 m
->kids
[1], m
->elems
[1],
232 LOG((" right (%p): %p [%p] %p\n", n
,
233 n
->kids
[0], n
->elems
[0],
239 np
= (n
->parent
->kids
[0] == n ?
&n
->parent
->kids
[0] :
240 n
->parent
->kids
[1] == n ?
&n
->parent
->kids
[1] :
241 n
->parent
->kids
[2] == n ?
&n
->parent
->kids
[2] :
242 &n
->parent
->kids
[3]);
247 * If we've come out of here by `break', n will still be
248 * non-NULL and we've finished. If we've come here because n is
249 * NULL, we need to create a new root for the tree because the
250 * old one has just split into two.
253 LOG((" root is overloaded, split into two\n"));
254 t
->root
= mknew(node234
);
255 t
->root
->kids
[0] = left
;
256 t
->root
->elems
[0] = e
;
257 t
->root
->kids
[1] = right
;
258 t
->root
->elems
[1] = NULL
;
259 t
->root
->kids
[2] = NULL
;
260 t
->root
->elems
[2] = NULL
;
261 t
->root
->kids
[3] = NULL
;
262 t
->root
->parent
= NULL
;
263 if (t
->root
->kids
[0]) t
->root
->kids
[0]->parent
= t
->root
;
264 if (t
->root
->kids
[1]) t
->root
->kids
[1]->parent
= t
->root
;
265 LOG((" new root is %p [%p] %p\n",
266 t
->root
->kids
[0], t
->root
->elems
[0], t
->root
->kids
[1]));
273 * Find an element e in a 2-3-4 tree t. Returns NULL if not found.
274 * e is always passed as the first argument to cmp, so cmp can be
275 * an asymmetric function if desired. cmp can also be passed as
276 * NULL, in which case the compare function from the tree proper
279 void *find234(tree234
*t
, void *e
, cmpfn234 cmp
) {
291 if ( (c
= cmp(e
, n
->elems
[0])) < 0)
295 else if (n
->elems
[1] == NULL
|| (c
= cmp(e
, n
->elems
[1])) < 0)
299 else if (n
->elems
[2] == NULL
|| (c
= cmp(e
, n
->elems
[2])) < 0)
308 * We've found our way to the bottom of the tree and we know
309 * where we would insert this node if we wanted to. But it
316 * Delete an element e in a 2-3-4 tree. Does not free the element,
317 * merely removes all links to it from the tree nodes.
319 void del234(tree234
*t
, void *e
) {
324 LOG(("deleting %p from tree %p\n", e
, t
));
331 LOG((" node %p: %p [%p] %p [%p] %p [%p] %p\n",
332 n
, n
->kids
[0], n
->elems
[0], n
->kids
[1], n
->elems
[1],
333 n
->kids
[2], n
->elems
[2], n
->kids
[3]));
334 if ((c
= t
->cmp(e
, n
->elems
[0])) < 0) {
338 } else if (n
->elems
[1] == NULL
|| (c
= t
->cmp(e
, n
->elems
[1])) < 0) {
342 } else if (n
->elems
[2] == NULL
|| (c
= t
->cmp(e
, n
->elems
[2])) < 0) {
350 * Recurse down to subtree ki. If it has only one element,
351 * we have to do some transformation to start with.
353 LOG((" moving to subtree %d\n", ki
));
355 if (!sub
->elems
[1]) {
356 LOG((" subtree has only one element!\n", ki
));
357 if (ki
> 0 && n
->kids
[ki
-1]->elems
[1]) {
359 * Case 3a, left-handed variant. Child ki has
360 * only one element, but child ki-1 has two or
361 * more. So we need to move a subtree from ki-1
366 * [more] a A b B c d D e [more] a A b c C d D e
368 node234
*sib
= n
->kids
[ki
-1];
369 int lastelem
= (sib
->elems
[2] ?
2 :
370 sib
->elems
[1] ?
1 : 0);
371 sub
->kids
[2] = sub
->kids
[1];
372 sub
->elems
[1] = sub
->elems
[0];
373 sub
->kids
[1] = sub
->kids
[0];
374 sub
->elems
[0] = n
->elems
[ki
-1];
375 sub
->kids
[0] = sib
->kids
[lastelem
+1];
376 if (sub
->kids
[0]) sub
->kids
[0]->parent
= sub
;
377 n
->elems
[ki
-1] = sib
->elems
[lastelem
];
378 sib
->kids
[lastelem
+1] = NULL
;
379 sib
->elems
[lastelem
] = NULL
;
380 LOG((" case 3a left\n"));
381 } else if (ki
< 3 && n
->kids
[ki
+1] &&
382 n
->kids
[ki
+1]->elems
[1]) {
384 * Case 3a, right-handed variant. ki has only
385 * one element but ki+1 has two or more. Move a
386 * subtree from ki+1 to ki.
390 * a A b c C d D e [more] a A b B c d D e [more]
392 node234
*sib
= n
->kids
[ki
+1];
394 sub
->elems
[1] = n
->elems
[ki
];
395 sub
->kids
[2] = sib
->kids
[0];
396 if (sub
->kids
[2]) sub
->kids
[2]->parent
= sub
;
397 n
->elems
[ki
] = sib
->elems
[0];
398 sib
->kids
[0] = sib
->kids
[1];
399 for (j
= 0; j
< 2 && sib
->elems
[j
+1]; j
++) {
400 sib
->kids
[j
+1] = sib
->kids
[j
+2];
401 sib
->elems
[j
] = sib
->elems
[j
+1];
403 sib
->kids
[j
+1] = NULL
;
404 sib
->elems
[j
] = NULL
;
405 LOG((" case 3a right\n"));
408 * Case 3b. ki has only one element, and has no
409 * neighbour with more than one. So pick a
410 * neighbour and merge it with ki, taking an
411 * element down from n to go in the middle.
415 * a A b c C d a A b B c C d
417 * (Since at all points we have avoided
418 * descending to a node with only one element,
419 * we can be sure that n is not reduced to
420 * nothingness by this move, _unless_ it was
421 * the very first node, ie the root of the
422 * tree. In that case we remove the now-empty
423 * root and replace it with its single large
434 sub
->kids
[3] = sub
->kids
[1];
435 sub
->elems
[2] = sub
->elems
[0];
436 sub
->kids
[2] = sub
->kids
[0];
437 sub
->elems
[1] = n
->elems
[ki
];
438 sub
->kids
[1] = sib
->kids
[1];
439 if (sub
->kids
[1]) sub
->kids
[1]->parent
= sub
;
440 sub
->elems
[0] = sib
->elems
[0];
441 sub
->kids
[0] = sib
->kids
[0];
442 if (sub
->kids
[0]) sub
->kids
[0]->parent
= sub
;
447 * That's built the big node in sub. Now we
448 * need to remove the reference to sib in n.
450 for (j
= ki
; j
< 3 && n
->kids
[j
+1]; j
++) {
451 n
->kids
[j
] = n
->kids
[j
+1];
452 n
->elems
[j
] = j
<2 ? n
->elems
[j
+1] : NULL
;
455 if (j
< 3) n
->elems
[j
] = NULL
;
456 LOG((" case 3b ki=%d\n", ki
));
460 * The root is empty and needs to be
463 LOG((" shifting root!\n"));
473 return; /* nothing to do; `already removed' */
476 * Treat special case: this is the one remaining item in
477 * the tree. n is the tree root (no parent), has one
478 * element (no elems[1]), and has no kids (no kids[0]).
480 if (!n
->parent
&& !n
->elems
[1] && !n
->kids
[0]) {
481 LOG((" removed last element in tree\n"));
488 * Now we have the element we want, as n->elems[ei], and we
489 * have also arranged for that element not to be the only
490 * one in its node. So...
493 if (!n
->kids
[0] && n
->elems
[1]) {
495 * Case 1. n is a leaf node with more than one element,
496 * so it's _really easy_. Just delete the thing and
501 for (i
= ei
; i
< 2 && n
->elems
[i
+1]; i
++)
502 n
->elems
[i
] = n
->elems
[i
+1];
504 return; /* finished! */
505 } else if (n
->kids
[ei
]->elems
[1]) {
507 * Case 2a. n is an internal node, and the root of the
508 * subtree to the left of e has more than one element.
509 * So find the predecessor p to e (ie the largest node
510 * in that subtree), place it where e currently is, and
511 * then start the deletion process over again on the
512 * subtree with p as target.
514 node234
*m
= n
->kids
[ei
];
518 m
= (m
->kids
[3] ? m
->kids
[3] :
519 m
->kids
[2] ? m
->kids
[2] :
520 m
->kids
[1] ? m
->kids
[1] : m
->kids
[0]);
522 target
= (m
->elems
[2] ? m
->elems
[2] :
523 m
->elems
[1] ? m
->elems
[1] : m
->elems
[0]);
524 n
->elems
[ei
] = target
;
527 } else if (n
->kids
[ei
+1]->elems
[1]) {
529 * Case 2b, symmetric to 2a but s/left/right/ and
530 * s/predecessor/successor/. (And s/largest/smallest/).
532 node234
*m
= n
->kids
[ei
+1];
538 target
= m
->elems
[0];
539 n
->elems
[ei
] = target
;
544 * Case 2c. n is an internal node, and the subtrees to
545 * the left and right of e both have only one element.
546 * So combine the two subnodes into a single big node
547 * with their own elements on the left and right and e
548 * in the middle, then restart the deletion process on
549 * that subtree, with e still as target.
551 node234
*a
= n
->kids
[ei
], *b
= n
->kids
[ei
+1];
555 a
->elems
[1] = n
->elems
[ei
];
556 a
->kids
[2] = b
->kids
[0];
557 if (a
->kids
[2]) a
->kids
[2]->parent
= a
;
558 a
->elems
[2] = b
->elems
[0];
559 a
->kids
[3] = b
->kids
[1];
560 if (a
->kids
[3]) a
->kids
[3]->parent
= a
;
563 * That's built the big node in a, and destroyed b. Now
564 * remove the reference to b (and e) in n.
566 for (j
= ei
; j
< 2 && n
->elems
[j
+1]; j
++) {
567 n
->elems
[j
] = n
->elems
[j
+1];
568 n
->kids
[j
+1] = n
->kids
[j
+2];
573 * Now go round the deletion process again, with n
574 * pointing at the new big node and e still the same.
582 * Iterate over the elements of a tree234, in order.
584 void *first234(tree234
*t
, enum234
*e
) {
585 node234
*n
= t
->root
;
595 void *next234(enum234
*e
) {
596 node234
*n
= e
->node
;
599 if (n
->kids
[pos
+1]) {
608 if (pos
< 2 && n
->elems
[pos
+1]) {
610 return n
->elems
[e
->posn
];
614 node234
*nn
= n
->parent
;
616 return NULL
; /* end of tree */
617 pos
= (nn
->kids
[0] == n ?
0 :
618 nn
->kids
[1] == n ?
1 :
619 nn
->kids
[2] == n ?
2 : 3);
621 } while (pos
== 3 || n
->kids
[pos
+1] == NULL
);
625 return n
->elems
[pos
];
631 * Test code for the 2-3-4 tree. This code maintains an alternative
632 * representation of the data in the tree, in an array (using the
633 * obvious and slow insert and delete functions). After each tree
634 * operation, the tree_valid() function is called, which ensures
635 * all the tree properties are preserved (node->child->parent
636 * always equals node; number of kids == number of elements + 1;
637 * all tree nodes are distinct; ordering property between elements
638 * of a node and elements of its children is preserved) and also
639 * ensures the list represented by the tree is the same list it
640 * should be. (This last check also verifies the ordering
641 * properties, because the `same list it should be' is by
642 * definition correctly ordered.)
648 * Error reporting function.
650 void error(char *fmt
, ...) {
654 vfprintf(stdout
, fmt
, ap
);
659 /* The array representation of the data. */
661 int arraylen
, arraysize
;
664 /* The tree representation of the same data. */
672 void chknode(chkctx
*ctx
, int level
, node234
*node
,
673 void *lowbound
, void *highbound
) {
677 /* Count the non-NULL kids. */
678 for (nkids
= 0; nkids
< 4 && node
->kids
[nkids
]; nkids
++);
679 /* Ensure no kids beyond the first NULL are non-NULL. */
680 for (i
= nkids
; i
< 4; i
++)
682 error("node %p: nkids=%d but kids[%d] non-NULL",
686 /* Count the non-NULL elements. */
687 for (nelems
= 0; nelems
< 3 && node
->elems
[nelems
]; nelems
++);
688 /* Ensure no elements beyond the first NULL are non-NULL. */
689 for (i
= nelems
; i
< 3; i
++)
690 if (node
->elems
[i
]) {
691 error("node %p: nelems=%d but elems[%d] non-NULL",
697 * If nkids==0, this is a leaf node; verify that the tree
698 * depth is the same everywhere.
700 if (ctx
->treedepth
< 0)
701 ctx
->treedepth
= level
; /* we didn't know the depth yet */
702 else if (ctx
->treedepth
!= level
)
703 error("node %p: leaf at depth %d, previously seen depth %d",
704 node
, level
, ctx
->treedepth
);
707 * If nkids != 0, then it should be nelems+1, unless nelems
708 * is 0 in which case nkids should also be 0 (and so we
709 * shouldn't be in this condition at all).
711 int shouldkids
= (nelems ? nelems
+1 : 0);
712 if (nkids
!= shouldkids
) {
713 error("node %p: %d elems should mean %d kids but has %d",
714 node
, nelems
, shouldkids
, nkids
);
719 * nelems should be at least 1.
722 error("node %p: no elems", node
, nkids
);
726 * Add nelems to the running element count of the whole tree
727 * (to ensure the enum234 routines see them all).
729 ctx
->elemcount
+= nelems
;
732 * Check ordering property: all elements should be strictly >
733 * lowbound, strictly < highbound, and strictly < each other in
734 * sequence. (lowbound and highbound are NULL at edges of tree
735 * - both NULL at root node - and NULL is considered to be <
736 * everything and > everything. IYSWIM.)
738 for (i
= -1; i
< nelems
; i
++) {
739 void *lower
= (i
== -1 ? lowbound
: node
->elems
[i
]);
740 void *higher
= (i
+1 == nelems ? highbound
: node
->elems
[i
+1]);
741 if (lower
&& higher
&& cmp(lower
, higher
) >= 0) {
742 error("node %p: kid comparison [%d=%s,%d=%s] failed",
743 node
, i
, lower
, i
+1, higher
);
748 * Check parent pointers: all non-NULL kids should have a
749 * parent pointer coming back to this node.
751 for (i
= 0; i
< nkids
; i
++)
752 if (node
->kids
[i
]->parent
!= node
) {
753 error("node %p kid %d: parent ptr is %p not %p",
754 node
, i
, node
->kids
[i
]->parent
, node
);
759 * Now (finally!) recurse into subtrees.
761 for (i
= 0; i
< nkids
; i
++) {
762 void *lower
= (i
== 0 ? lowbound
: node
->elems
[i
-1]);
763 void *higher
= (i
>= nelems ? highbound
: node
->elems
[i
]);
764 chknode(ctx
, level
+1, node
->kids
[i
], lower
, higher
);
774 ctx
.treedepth
= -1; /* depth unknown yet */
775 ctx
.elemcount
= 0; /* no elements seen yet */
777 * Verify validity of tree properties.
780 chknode(&ctx
, 0, tree
->root
, NULL
, NULL
);
781 printf("tree depth: %d\n", ctx
.treedepth
);
783 * Enumerate the tree and ensure it matches up to the array.
785 for (i
= 0, p
= first234(tree
, &e
);
787 i
++, p
= next234(&e
)) {
789 error("tree contains more than %d elements", arraylen
);
791 error("enum at position %d: array says %s, tree says %s",
794 if (i
!= ctx
.elemcount
) {
795 error("tree really contains %d elements, enum gave %d",
799 error("enum gave only %d elements, array has %d", i
, arraylen
);
803 void addtest(void *elem
) {
805 void *retval
, *realret
;
807 if (arraysize
< arraylen
+1) {
808 arraysize
= arraylen
+1+256;
809 array
= (array
== NULL ?
malloc(arraysize
*sizeof(*array
)) :
810 realloc(array
, arraysize
*sizeof(*array
)));
814 while (i
< arraylen
&& cmp(elem
, array
[i
]) > 0)
816 /* now i points to the first element >= elem */
817 if (i
< arraylen
&& !cmp(elem
, array
[i
]))
818 retval
= array
[i
]; /* expect that returned not elem */
820 retval
= elem
; /* expect elem returned (success) */
821 for (j
= arraylen
; j
> i
; j
--)
822 array
[j
] = array
[j
-1];
823 array
[i
] = elem
; /* add elem to array */
827 realret
= add234(tree
, elem
);
828 if (realret
!= retval
) {
829 error("add: retval was %p expected %p", realret
, retval
);
835 void deltest(void *elem
) {
839 while (i
< arraylen
&& cmp(elem
, array
[i
]) > 0)
841 /* now i points to the first element >= elem */
842 if (i
>= arraylen
|| cmp(elem
, array
[i
]) != 0)
843 return; /* don't do it! */
845 while (i
< arraylen
-1) {
846 array
[i
] = array
[i
+1];
849 arraylen
--; /* delete elem from array */
857 /* A sample data set and test utility. Designed for pseudo-randomness,
858 * and yet repeatability. */
861 * This random number generator uses the `portable implementation'
862 * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
865 int randomnumber(unsigned *seed
) {
868 return ((*seed
) / 65536) % 32768;
871 int mycmp(void *av
, void *bv
) {
872 char const *a
= (char const *)av
;
873 char const *b
= (char const *)bv
;
877 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
880 "a", "ab", "absque", "coram", "de",
881 "palam", "clam", "cum", "ex", "e",
882 "sine", "tenus", "pro", "prae",
883 "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
884 "penguin", "blancmange", "pangolin", "whale", "hedgehog",
885 "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
886 "murfl", "spoo", "breen", "flarn", "octothorpe",
887 "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
888 "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
889 "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
890 "wand", "ring", "amulet"
893 #define NSTR lenof(strings)
900 for (i
= 0; i
< NSTR
; i
++) in
[i
] = 0;
902 arraylen
= arraysize
= 0;
903 tree
= newtree234(mycmp
);
907 for (i
= 0; i
< 10000; i
++) {
908 j
= randomnumber(&seed
);
910 printf("trial: %d\n", i
);
912 printf("deleting %s (%d)\n", strings
[j
], j
);
916 printf("adding %s (%d)\n", strings
[j
], j
);
922 while (arraylen
> 0) {
923 j
= randomnumber(&seed
);