source: filezilla/trunk/fuentes/src/putty/tree234.c @ 130

Last change on this file since 130 was 130, checked in by jrpelegrina, 4 years ago

First release to xenial

File size: 39.3 KB
Line 
1/*
2 * tree234.c: reasonably generic counted 2-3-4 tree routines.
3 *
4 * This file is copyright 1999-2001 Simon Tatham.
5 *
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
13 * conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
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
25 * SOFTWARE.
26 */
27
28#include <stdio.h>
29#include <stdlib.h>
30#include <assert.h>
31
32#include "tree234.h"
33
34#ifdef TEST
35#define LOG(x) (printf x)
36#define snew(type) ((type *)malloc(sizeof(type)))
37#define snewn(n, type) ((type *)malloc((n) * sizeof(type)))
38#define sresize(ptr, n, type)                                         \
39    ((type *)realloc(sizeof((type *)0 == (ptr)) ? (ptr) : (ptr),      \
40                     (n) * sizeof(type)))
41#define sfree(ptr) free(ptr)
42#else
43#include "puttymem.h"
44#define LOG(x)
45#endif
46
47typedef struct node234_Tag node234;
48
49struct tree234_Tag {
50    node234 *root;
51    cmpfn234 cmp;
52};
53
54struct node234_Tag {
55    node234 *parent;
56    node234 *kids[4];
57    int counts[4];
58    void *elems[3];
59};
60
61/*
62 * Create a 2-3-4 tree.
63 */
64tree234 *newtree234(cmpfn234 cmp)
65{
66    tree234 *ret = snew(tree234);
67    LOG(("created tree %p\n", ret));
68    ret->root = NULL;
69    ret->cmp = cmp;
70    return ret;
71}
72
73/*
74 * Free a 2-3-4 tree (not including freeing the elements).
75 */
76static void freenode234(node234 * n)
77{
78    if (!n)
79        return;
80    freenode234(n->kids[0]);
81    freenode234(n->kids[1]);
82    freenode234(n->kids[2]);
83    freenode234(n->kids[3]);
84    sfree(n);
85}
86
87void freetree234(tree234 * t)
88{
89    freenode234(t->root);
90    sfree(t);
91}
92
93/*
94 * Internal function to count a node.
95 */
96static int countnode234(node234 * n)
97{
98    int count = 0;
99    int i;
100    if (!n)
101        return 0;
102    for (i = 0; i < 4; i++)
103        count += n->counts[i];
104    for (i = 0; i < 3; i++)
105        if (n->elems[i])
106            count++;
107    return count;
108}
109
110/*
111 * Count the elements in a tree.
112 */
113int count234(tree234 * t)
114{
115    if (t->root)
116        return countnode234(t->root);
117    else
118        return 0;
119}
120
121/*
122 * Add an element e to a 2-3-4 tree t. Returns e on success, or if
123 * an existing element compares equal, returns that.
124 */
125static void *add234_internal(tree234 * t, void *e, int index)
126{
127    node234 *n, **np, *left, *right;
128    void *orig_e = e;
129    int c, lcount, rcount;
130
131    LOG(("adding node %p to tree %p\n", e, t));
132    if (t->root == NULL) {
133        t->root = snew(node234);
134        t->root->elems[1] = t->root->elems[2] = NULL;
135        t->root->kids[0] = t->root->kids[1] = NULL;
136        t->root->kids[2] = t->root->kids[3] = NULL;
137        t->root->counts[0] = t->root->counts[1] = 0;
138        t->root->counts[2] = t->root->counts[3] = 0;
139        t->root->parent = NULL;
140        t->root->elems[0] = e;
141        LOG(("  created root %p\n", t->root));
142        return orig_e;
143    }
144
145    n = NULL; /* placate gcc; will always be set below since t->root != NULL */
146    np = &t->root;
147    while (*np) {
148        int childnum;
149        n = *np;
150        LOG(("  node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d\n",
151             n,
152             n->kids[0], n->counts[0], n->elems[0],
153             n->kids[1], n->counts[1], n->elems[1],
154             n->kids[2], n->counts[2], n->elems[2],
155             n->kids[3], n->counts[3]));
156        if (index >= 0) {
157            if (!n->kids[0]) {
158                /*
159                 * Leaf node. We want to insert at kid position
160                 * equal to the index:
161                 *
162                 *   0 A 1 B 2 C 3
163                 */
164                childnum = index;
165            } else {
166                /*
167                 * Internal node. We always descend through it (add
168                 * always starts at the bottom, never in the
169                 * middle).
170                 */
171                do {                   /* this is a do ... while (0) to allow `break' */
172                    if (index <= n->counts[0]) {
173                        childnum = 0;
174                        break;
175                    }
176                    index -= n->counts[0] + 1;
177                    if (index <= n->counts[1]) {
178                        childnum = 1;
179                        break;
180                    }
181                    index -= n->counts[1] + 1;
182                    if (index <= n->counts[2]) {
183                        childnum = 2;
184                        break;
185                    }
186                    index -= n->counts[2] + 1;
187                    if (index <= n->counts[3]) {
188                        childnum = 3;
189                        break;
190                    }
191                    return NULL;       /* error: index out of range */
192                } while (0);
193            }
194        } else {
195            if ((c = t->cmp(e, n->elems[0])) < 0)
196                childnum = 0;
197            else if (c == 0)
198                return n->elems[0];    /* already exists */
199            else if (n->elems[1] == NULL
200                     || (c = t->cmp(e, n->elems[1])) < 0) childnum = 1;
201            else if (c == 0)
202                return n->elems[1];    /* already exists */
203            else if (n->elems[2] == NULL
204                     || (c = t->cmp(e, n->elems[2])) < 0) childnum = 2;
205            else if (c == 0)
206                return n->elems[2];    /* already exists */
207            else
208                childnum = 3;
209        }
210        np = &n->kids[childnum];
211        LOG(("  moving to child %d (%p)\n", childnum, *np));
212    }
213
214    /*
215     * We need to insert the new element in n at position np.
216     */
217    left = NULL;
218    lcount = 0;
219    right = NULL;
220    rcount = 0;
221    while (n) {
222        LOG(("  at %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d\n",
223             n,
224             n->kids[0], n->counts[0], n->elems[0],
225             n->kids[1], n->counts[1], n->elems[1],
226             n->kids[2], n->counts[2], n->elems[2],
227             n->kids[3], n->counts[3]));
228        LOG(("  need to insert %p/%d [%p] %p/%d at position %d\n",
229             left, lcount, e, right, rcount, (int)(np - n->kids)));
230        if (n->elems[1] == NULL) {
231            /*
232             * Insert in a 2-node; simple.
233             */
234            if (np == &n->kids[0]) {
235                LOG(("  inserting on left of 2-node\n"));
236                n->kids[2] = n->kids[1];
237                n->counts[2] = n->counts[1];
238                n->elems[1] = n->elems[0];
239                n->kids[1] = right;
240                n->counts[1] = rcount;
241                n->elems[0] = e;
242                n->kids[0] = left;
243                n->counts[0] = lcount;
244            } else {                   /* np == &n->kids[1] */
245                LOG(("  inserting on right of 2-node\n"));
246                n->kids[2] = right;
247                n->counts[2] = rcount;
248                n->elems[1] = e;
249                n->kids[1] = left;
250                n->counts[1] = lcount;
251            }
252            if (n->kids[0])
253                n->kids[0]->parent = n;
254            if (n->kids[1])
255                n->kids[1]->parent = n;
256            if (n->kids[2])
257                n->kids[2]->parent = n;
258            LOG(("  done\n"));
259            break;
260        } else if (n->elems[2] == NULL) {
261            /*
262             * Insert in a 3-node; simple.
263             */
264            if (np == &n->kids[0]) {
265                LOG(("  inserting on left of 3-node\n"));
266                n->kids[3] = n->kids[2];
267                n->counts[3] = n->counts[2];
268                n->elems[2] = n->elems[1];
269                n->kids[2] = n->kids[1];
270                n->counts[2] = n->counts[1];
271                n->elems[1] = n->elems[0];
272                n->kids[1] = right;
273                n->counts[1] = rcount;
274                n->elems[0] = e;
275                n->kids[0] = left;
276                n->counts[0] = lcount;
277            } else if (np == &n->kids[1]) {
278                LOG(("  inserting in middle of 3-node\n"));
279                n->kids[3] = n->kids[2];
280                n->counts[3] = n->counts[2];
281                n->elems[2] = n->elems[1];
282                n->kids[2] = right;
283                n->counts[2] = rcount;
284                n->elems[1] = e;
285                n->kids[1] = left;
286                n->counts[1] = lcount;
287            } else {                   /* np == &n->kids[2] */
288                LOG(("  inserting on right of 3-node\n"));
289                n->kids[3] = right;
290                n->counts[3] = rcount;
291                n->elems[2] = e;
292                n->kids[2] = left;
293                n->counts[2] = lcount;
294            }
295            if (n->kids[0])
296                n->kids[0]->parent = n;
297            if (n->kids[1])
298                n->kids[1]->parent = n;
299            if (n->kids[2])
300                n->kids[2]->parent = n;
301            if (n->kids[3])
302                n->kids[3]->parent = n;
303            LOG(("  done\n"));
304            break;
305        } else {
306            node234 *m = snew(node234);
307            m->parent = n->parent;
308            LOG(("  splitting a 4-node; created new node %p\n", m));
309            /*
310             * Insert in a 4-node; split into a 2-node and a
311             * 3-node, and move focus up a level.
312             *
313             * I don't think it matters which way round we put the
314             * 2 and the 3. For simplicity, we'll put the 3 first
315             * always.
316             */
317            if (np == &n->kids[0]) {
318                m->kids[0] = left;
319                m->counts[0] = lcount;
320                m->elems[0] = e;
321                m->kids[1] = right;
322                m->counts[1] = rcount;
323                m->elems[1] = n->elems[0];
324                m->kids[2] = n->kids[1];
325                m->counts[2] = n->counts[1];
326                e = n->elems[1];
327                n->kids[0] = n->kids[2];
328                n->counts[0] = n->counts[2];
329                n->elems[0] = n->elems[2];
330                n->kids[1] = n->kids[3];
331                n->counts[1] = n->counts[3];
332            } else if (np == &n->kids[1]) {
333                m->kids[0] = n->kids[0];
334                m->counts[0] = n->counts[0];
335                m->elems[0] = n->elems[0];
336                m->kids[1] = left;
337                m->counts[1] = lcount;
338                m->elems[1] = e;
339                m->kids[2] = right;
340                m->counts[2] = rcount;
341                e = n->elems[1];
342                n->kids[0] = n->kids[2];
343                n->counts[0] = n->counts[2];
344                n->elems[0] = n->elems[2];
345                n->kids[1] = n->kids[3];
346                n->counts[1] = n->counts[3];
347            } else if (np == &n->kids[2]) {
348                m->kids[0] = n->kids[0];
349                m->counts[0] = n->counts[0];
350                m->elems[0] = n->elems[0];
351                m->kids[1] = n->kids[1];
352                m->counts[1] = n->counts[1];
353                m->elems[1] = n->elems[1];
354                m->kids[2] = left;
355                m->counts[2] = lcount;
356                /* e = e; */
357                n->kids[0] = right;
358                n->counts[0] = rcount;
359                n->elems[0] = n->elems[2];
360                n->kids[1] = n->kids[3];
361                n->counts[1] = n->counts[3];
362            } else {                   /* np == &n->kids[3] */
363                m->kids[0] = n->kids[0];
364                m->counts[0] = n->counts[0];
365                m->elems[0] = n->elems[0];
366                m->kids[1] = n->kids[1];
367                m->counts[1] = n->counts[1];
368                m->elems[1] = n->elems[1];
369                m->kids[2] = n->kids[2];
370                m->counts[2] = n->counts[2];
371                n->kids[0] = left;
372                n->counts[0] = lcount;
373                n->elems[0] = e;
374                n->kids[1] = right;
375                n->counts[1] = rcount;
376                e = n->elems[2];
377            }
378            m->kids[3] = n->kids[3] = n->kids[2] = NULL;
379            m->counts[3] = n->counts[3] = n->counts[2] = 0;
380            m->elems[2] = n->elems[2] = n->elems[1] = NULL;
381            if (m->kids[0])
382                m->kids[0]->parent = m;
383            if (m->kids[1])
384                m->kids[1]->parent = m;
385            if (m->kids[2])
386                m->kids[2]->parent = m;
387            if (n->kids[0])
388                n->kids[0]->parent = n;
389            if (n->kids[1])
390                n->kids[1]->parent = n;
391            LOG(("  left (%p): %p/%d [%p] %p/%d [%p] %p/%d\n", m,
392                 m->kids[0], m->counts[0], m->elems[0],
393                 m->kids[1], m->counts[1], m->elems[1],
394                 m->kids[2], m->counts[2]));
395            LOG(("  right (%p): %p/%d [%p] %p/%d\n", n,
396                 n->kids[0], n->counts[0], n->elems[0],
397                 n->kids[1], n->counts[1]));
398            left = m;
399            lcount = countnode234(left);
400            right = n;
401            rcount = countnode234(right);
402        }
403        if (n->parent)
404            np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
405                  n->parent->kids[1] == n ? &n->parent->kids[1] :
406                  n->parent->kids[2] == n ? &n->parent->kids[2] :
407                  &n->parent->kids[3]);
408        n = n->parent;
409    }
410
411    /*
412     * If we've come out of here by `break', n will still be
413     * non-NULL and all we need to do is go back up the tree
414     * updating counts. If we've come here because n is NULL, we
415     * need to create a new root for the tree because the old one
416     * has just split into two. */
417    if (n) {
418        while (n->parent) {
419            int count = countnode234(n);
420            int childnum;
421            childnum = (n->parent->kids[0] == n ? 0 :
422                        n->parent->kids[1] == n ? 1 :
423                        n->parent->kids[2] == n ? 2 : 3);
424            n->parent->counts[childnum] = count;
425            n = n->parent;
426        }
427    } else {
428        LOG(("  root is overloaded, split into two\n"));
429        t->root = snew(node234);
430        t->root->kids[0] = left;
431        t->root->counts[0] = lcount;
432        t->root->elems[0] = e;
433        t->root->kids[1] = right;
434        t->root->counts[1] = rcount;
435        t->root->elems[1] = NULL;
436        t->root->kids[2] = NULL;
437        t->root->counts[2] = 0;
438        t->root->elems[2] = NULL;
439        t->root->kids[3] = NULL;
440        t->root->counts[3] = 0;
441        t->root->parent = NULL;
442        if (t->root->kids[0])
443            t->root->kids[0]->parent = t->root;
444        if (t->root->kids[1])
445            t->root->kids[1]->parent = t->root;
446        LOG(("  new root is %p/%d [%p] %p/%d\n",
447             t->root->kids[0], t->root->counts[0],
448             t->root->elems[0], t->root->kids[1], t->root->counts[1]));
449    }
450
451    return orig_e;
452}
453
454void *add234(tree234 * t, void *e)
455{
456    if (!t->cmp)                       /* tree is unsorted */
457        return NULL;
458
459    return add234_internal(t, e, -1);
460}
461void *addpos234(tree234 * t, void *e, int index)
462{
463    if (index < 0 ||                   /* index out of range */
464        t->cmp)                        /* tree is sorted */
465        return NULL;                   /* return failure */
466
467    return add234_internal(t, e, index);        /* this checks the upper bound */
468}
469
470/*
471 * Look up the element at a given numeric index in a 2-3-4 tree.
472 * Returns NULL if the index is out of range.
473 */
474void *index234(tree234 * t, int index)
475{
476    node234 *n;
477
478    if (!t->root)
479        return NULL;                   /* tree is empty */
480
481    if (index < 0 || index >= countnode234(t->root))
482        return NULL;                   /* out of range */
483
484    n = t->root;
485
486    while (n) {
487        if (index < n->counts[0])
488            n = n->kids[0];
489        else if (index -= n->counts[0] + 1, index < 0)
490            return n->elems[0];
491        else if (index < n->counts[1])
492            n = n->kids[1];
493        else if (index -= n->counts[1] + 1, index < 0)
494            return n->elems[1];
495        else if (index < n->counts[2])
496            n = n->kids[2];
497        else if (index -= n->counts[2] + 1, index < 0)
498            return n->elems[2];
499        else
500            n = n->kids[3];
501    }
502
503    /* We shouldn't ever get here. I wonder how we did. */
504    return NULL;
505}
506
507/*
508 * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
509 * found. e is always passed as the first argument to cmp, so cmp
510 * can be an asymmetric function if desired. cmp can also be passed
511 * as NULL, in which case the compare function from the tree proper
512 * will be used.
513 */
514void *findrelpos234(tree234 * t, void *e, cmpfn234 cmp,
515                    int relation, int *index)
516{
517    node234 *n;
518    void *ret;
519    int c;
520    int idx, ecount, kcount, cmpret;
521
522    if (t->root == NULL)
523        return NULL;
524
525    if (cmp == NULL)
526        cmp = t->cmp;
527
528    n = t->root;
529    /*
530     * Attempt to find the element itself.
531     */
532    idx = 0;
533    ecount = -1;
534    /*
535     * Prepare a fake `cmp' result if e is NULL.
536     */
537    cmpret = 0;
538    if (e == NULL) {
539        assert(relation == REL234_LT || relation == REL234_GT);
540        if (relation == REL234_LT)
541            cmpret = +1;               /* e is a max: always greater */
542        else if (relation == REL234_GT)
543            cmpret = -1;               /* e is a min: always smaller */
544    }
545    while (1) {
546        for (kcount = 0; kcount < 4; kcount++) {
547            if (kcount >= 3 || n->elems[kcount] == NULL ||
548                (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
549                break;
550            }
551            if (n->kids[kcount])
552                idx += n->counts[kcount];
553            if (c == 0) {
554                ecount = kcount;
555                break;
556            }
557            idx++;
558        }
559        if (ecount >= 0)
560            break;
561        if (n->kids[kcount])
562            n = n->kids[kcount];
563        else
564            break;
565    }
566
567    if (ecount >= 0) {
568        /*
569         * We have found the element we're looking for. It's
570         * n->elems[ecount], at tree index idx. If our search
571         * relation is EQ, LE or GE we can now go home.
572         */
573        if (relation != REL234_LT && relation != REL234_GT) {
574            if (index)
575                *index = idx;
576            return n->elems[ecount];
577        }
578
579        /*
580         * Otherwise, we'll do an indexed lookup for the previous
581         * or next element. (It would be perfectly possible to
582         * implement these search types in a non-counted tree by
583         * going back up from where we are, but far more fiddly.)
584         */
585        if (relation == REL234_LT)
586            idx--;
587        else
588            idx++;
589    } else {
590        /*
591         * We've found our way to the bottom of the tree and we
592         * know where we would insert this node if we wanted to:
593         * we'd put it in in place of the (empty) subtree
594         * n->kids[kcount], and it would have index idx
595         *
596         * But the actual element isn't there. So if our search
597         * relation is EQ, we're doomed.
598         */
599        if (relation == REL234_EQ)
600            return NULL;
601
602        /*
603         * Otherwise, we must do an index lookup for index idx-1
604         * (if we're going left - LE or LT) or index idx (if we're
605         * going right - GE or GT).
606         */
607        if (relation == REL234_LT || relation == REL234_LE) {
608            idx--;
609        }
610    }
611
612    /*
613     * We know the index of the element we want; just call index234
614     * to do the rest. This will return NULL if the index is out of
615     * bounds, which is exactly what we want.
616     */
617    ret = index234(t, idx);
618    if (ret && index)
619        *index = idx;
620    return ret;
621}
622void *find234(tree234 * t, void *e, cmpfn234 cmp)
623{
624    return findrelpos234(t, e, cmp, REL234_EQ, NULL);
625}
626void *findrel234(tree234 * t, void *e, cmpfn234 cmp, int relation)
627{
628    return findrelpos234(t, e, cmp, relation, NULL);
629}
630void *findpos234(tree234 * t, void *e, cmpfn234 cmp, int *index)
631{
632    return findrelpos234(t, e, cmp, REL234_EQ, index);
633}
634
635/*
636 * Delete an element e in a 2-3-4 tree. Does not free the element,
637 * merely removes all links to it from the tree nodes.
638 */
639static void *delpos234_internal(tree234 * t, int index)
640{
641    node234 *n;
642    void *retval;
643    int ei = -1;
644
645    retval = 0;
646
647    n = t->root;
648    LOG(("deleting item %d from tree %p\n", index, t));
649    while (1) {
650        while (n) {
651            int ki;
652            node234 *sub;
653
654            LOG(
655                ("  node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d index=%d\n",
656                 n, n->kids[0], n->counts[0], n->elems[0], n->kids[1],
657                 n->counts[1], n->elems[1], n->kids[2], n->counts[2],
658                 n->elems[2], n->kids[3], n->counts[3], index));
659            if (index < n->counts[0]) {
660                ki = 0;
661            } else if (index -= n->counts[0] + 1, index < 0) {
662                ei = 0;
663                break;
664            } else if (index < n->counts[1]) {
665                ki = 1;
666            } else if (index -= n->counts[1] + 1, index < 0) {
667                ei = 1;
668                break;
669            } else if (index < n->counts[2]) {
670                ki = 2;
671            } else if (index -= n->counts[2] + 1, index < 0) {
672                ei = 2;
673                break;
674            } else {
675                ki = 3;
676            }
677            /*
678             * Recurse down to subtree ki. If it has only one element,
679             * we have to do some transformation to start with.
680             */
681            LOG(("  moving to subtree %d\n", ki));
682            sub = n->kids[ki];
683            if (!sub->elems[1]) {
684                LOG(("  subtree has only one element!\n", ki));
685                if (ki > 0 && n->kids[ki - 1]->elems[1]) {
686                    /*
687                     * Case 3a, left-handed variant. Child ki has
688                     * only one element, but child ki-1 has two or
689                     * more. So we need to move a subtree from ki-1
690                     * to ki.
691                     *
692                     *                . C .                     . B .
693                     *               /     \     ->            /     \
694                     * [more] a A b B c   d D e      [more] a A b   c C d D e
695                     */
696                    node234 *sib = n->kids[ki - 1];
697                    int lastelem = (sib->elems[2] ? 2 :
698                                    sib->elems[1] ? 1 : 0);
699                    sub->kids[2] = sub->kids[1];
700                    sub->counts[2] = sub->counts[1];
701                    sub->elems[1] = sub->elems[0];
702                    sub->kids[1] = sub->kids[0];
703                    sub->counts[1] = sub->counts[0];
704                    sub->elems[0] = n->elems[ki - 1];
705                    sub->kids[0] = sib->kids[lastelem + 1];
706                    sub->counts[0] = sib->counts[lastelem + 1];
707                    if (sub->kids[0])
708                        sub->kids[0]->parent = sub;
709                    n->elems[ki - 1] = sib->elems[lastelem];
710                    sib->kids[lastelem + 1] = NULL;
711                    sib->counts[lastelem + 1] = 0;
712                    sib->elems[lastelem] = NULL;
713                    n->counts[ki] = countnode234(sub);
714                    LOG(("  case 3a left\n"));
715                    LOG(
716                        ("  index and left subtree count before adjustment: %d, %d\n",
717                         index, n->counts[ki - 1]));
718                    index += n->counts[ki - 1];
719                    n->counts[ki - 1] = countnode234(sib);
720                    index -= n->counts[ki - 1];
721                    LOG(
722                        ("  index and left subtree count after adjustment: %d, %d\n",
723                         index, n->counts[ki - 1]));
724                } else if (ki < 3 && n->kids[ki + 1]
725                           && n->kids[ki + 1]->elems[1]) {
726                    /*
727                     * Case 3a, right-handed variant. ki has only
728                     * one element but ki+1 has two or more. Move a
729                     * subtree from ki+1 to ki.
730                     *
731                     *      . B .                             . C .
732                     *     /     \                ->         /     \
733                     *  a A b   c C d D e [more]      a A b B c   d D e [more]
734                     */
735                    node234 *sib = n->kids[ki + 1];
736                    int j;
737                    sub->elems[1] = n->elems[ki];
738                    sub->kids[2] = sib->kids[0];
739                    sub->counts[2] = sib->counts[0];
740                    if (sub->kids[2])
741                        sub->kids[2]->parent = sub;
742                    n->elems[ki] = sib->elems[0];
743                    sib->kids[0] = sib->kids[1];
744                    sib->counts[0] = sib->counts[1];
745                    for (j = 0; j < 2 && sib->elems[j + 1]; j++) {
746                        sib->kids[j + 1] = sib->kids[j + 2];
747                        sib->counts[j + 1] = sib->counts[j + 2];
748                        sib->elems[j] = sib->elems[j + 1];
749                    }
750                    sib->kids[j + 1] = NULL;
751                    sib->counts[j + 1] = 0;
752                    sib->elems[j] = NULL;
753                    n->counts[ki] = countnode234(sub);
754                    n->counts[ki + 1] = countnode234(sib);
755                    LOG(("  case 3a right\n"));
756                } else {
757                    /*
758                     * Case 3b. ki has only one element, and has no
759                     * neighbour with more than one. So pick a
760                     * neighbour and merge it with ki, taking an
761                     * element down from n to go in the middle.
762                     *
763                     *      . B .                .
764                     *     /     \     ->        |
765                     *  a A b   c C d      a A b B c C d
766                     *
767                     * (Since at all points we have avoided
768                     * descending to a node with only one element,
769                     * we can be sure that n is not reduced to
770                     * nothingness by this move, _unless_ it was
771                     * the very first node, ie the root of the
772                     * tree. In that case we remove the now-empty
773                     * root and replace it with its single large
774                     * child as shown.)
775                     */
776                    node234 *sib;
777                    int j;
778
779                    if (ki > 0) {
780                        ki--;
781                        index += n->counts[ki] + 1;
782                    }
783                    sib = n->kids[ki];
784                    sub = n->kids[ki + 1];
785
786                    sub->kids[3] = sub->kids[1];
787                    sub->counts[3] = sub->counts[1];
788                    sub->elems[2] = sub->elems[0];
789                    sub->kids[2] = sub->kids[0];
790                    sub->counts[2] = sub->counts[0];
791                    sub->elems[1] = n->elems[ki];
792                    sub->kids[1] = sib->kids[1];
793                    sub->counts[1] = sib->counts[1];
794                    if (sub->kids[1])
795                        sub->kids[1]->parent = sub;
796                    sub->elems[0] = sib->elems[0];
797                    sub->kids[0] = sib->kids[0];
798                    sub->counts[0] = sib->counts[0];
799                    if (sub->kids[0])
800                        sub->kids[0]->parent = sub;
801
802                    n->counts[ki + 1] = countnode234(sub);
803
804                    sfree(sib);
805
806                    /*
807                     * That's built the big node in sub. Now we
808                     * need to remove the reference to sib in n.
809                     */
810                    for (j = ki; j < 3 && n->kids[j + 1]; j++) {
811                        n->kids[j] = n->kids[j + 1];
812                        n->counts[j] = n->counts[j + 1];
813                        n->elems[j] = j < 2 ? n->elems[j + 1] : NULL;
814                    }
815                    n->kids[j] = NULL;
816                    n->counts[j] = 0;
817                    if (j < 3)
818                        n->elems[j] = NULL;
819                    LOG(("  case 3b ki=%d\n", ki));
820
821                    if (!n->elems[0]) {
822                        /*
823                         * The root is empty and needs to be
824                         * removed.
825                         */
826                        LOG(("  shifting root!\n"));
827                        t->root = sub;
828                        sub->parent = NULL;
829                        sfree(n);
830                    }
831                }
832            }
833            n = sub;
834        }
835        if (!retval)
836            retval = n->elems[ei];
837
838        if (ei == -1)
839            return NULL;               /* although this shouldn't happen */
840
841        /*
842         * Treat special case: this is the one remaining item in
843         * the tree. n is the tree root (no parent), has one
844         * element (no elems[1]), and has no kids (no kids[0]).
845         */
846        if (!n->parent && !n->elems[1] && !n->kids[0]) {
847            LOG(("  removed last element in tree\n"));
848            sfree(n);
849            t->root = NULL;
850            return retval;
851        }
852
853        /*
854         * Now we have the element we want, as n->elems[ei], and we
855         * have also arranged for that element not to be the only
856         * one in its node. So...
857         */
858
859        if (!n->kids[0] && n->elems[1]) {
860            /*
861             * Case 1. n is a leaf node with more than one element,
862             * so it's _really easy_. Just delete the thing and
863             * we're done.
864             */
865            int i;
866            LOG(("  case 1\n"));
867            for (i = ei; i < 2 && n->elems[i + 1]; i++)
868                n->elems[i] = n->elems[i + 1];
869            n->elems[i] = NULL;
870            /*
871             * Having done that to the leaf node, we now go back up
872             * the tree fixing the counts.
873             */
874            while (n->parent) {
875                int childnum;
876                childnum = (n->parent->kids[0] == n ? 0 :
877                            n->parent->kids[1] == n ? 1 :
878                            n->parent->kids[2] == n ? 2 : 3);
879                n->parent->counts[childnum]--;
880                n = n->parent;
881            }
882            return retval;             /* finished! */
883        } else if (n->kids[ei]->elems[1]) {
884            /*
885             * Case 2a. n is an internal node, and the root of the
886             * subtree to the left of e has more than one element.
887             * So find the predecessor p to e (ie the largest node
888             * in that subtree), place it where e currently is, and
889             * then start the deletion process over again on the
890             * subtree with p as target.
891             */
892            node234 *m = n->kids[ei];
893            void *target;
894            LOG(("  case 2a\n"));
895            while (m->kids[0]) {
896                m = (m->kids[3] ? m->kids[3] :
897                     m->kids[2] ? m->kids[2] :
898                     m->kids[1] ? m->kids[1] : m->kids[0]);
899            }
900            target = (m->elems[2] ? m->elems[2] :
901                      m->elems[1] ? m->elems[1] : m->elems[0]);
902            n->elems[ei] = target;
903            index = n->counts[ei] - 1;
904            n = n->kids[ei];
905        } else if (n->kids[ei + 1]->elems[1]) {
906            /*
907             * Case 2b, symmetric to 2a but s/left/right/ and
908             * s/predecessor/successor/. (And s/largest/smallest/).
909             */
910            node234 *m = n->kids[ei + 1];
911            void *target;
912            LOG(("  case 2b\n"));
913            while (m->kids[0]) {
914                m = m->kids[0];
915            }
916            target = m->elems[0];
917            n->elems[ei] = target;
918            n = n->kids[ei + 1];
919            index = 0;
920        } else {
921            /*
922             * Case 2c. n is an internal node, and the subtrees to
923             * the left and right of e both have only one element.
924             * So combine the two subnodes into a single big node
925             * with their own elements on the left and right and e
926             * in the middle, then restart the deletion process on
927             * that subtree, with e still as target.
928             */
929            node234 *a = n->kids[ei], *b = n->kids[ei + 1];
930            int j;
931
932            LOG(("  case 2c\n"));
933            a->elems[1] = n->elems[ei];
934            a->kids[2] = b->kids[0];
935            a->counts[2] = b->counts[0];
936            if (a->kids[2])
937                a->kids[2]->parent = a;
938            a->elems[2] = b->elems[0];
939            a->kids[3] = b->kids[1];
940            a->counts[3] = b->counts[1];
941            if (a->kids[3])
942                a->kids[3]->parent = a;
943            sfree(b);
944            n->counts[ei] = countnode234(a);
945            /*
946             * That's built the big node in a, and destroyed b. Now
947             * remove the reference to b (and e) in n.
948             */
949            for (j = ei; j < 2 && n->elems[j + 1]; j++) {
950                n->elems[j] = n->elems[j + 1];
951                n->kids[j + 1] = n->kids[j + 2];
952                n->counts[j + 1] = n->counts[j + 2];
953            }
954            n->elems[j] = NULL;
955            n->kids[j + 1] = NULL;
956            n->counts[j + 1] = 0;
957            /*
958             * It's possible, in this case, that we've just removed
959             * the only element in the root of the tree. If so,
960             * shift the root.
961             */
962            if (n->elems[0] == NULL) {
963                LOG(("  shifting root!\n"));
964                t->root = a;
965                a->parent = NULL;
966                sfree(n);
967            }
968            /*
969             * Now go round the deletion process again, with n
970             * pointing at the new big node and e still the same.
971             */
972            n = a;
973            index = a->counts[0] + a->counts[1] + 1;
974        }
975    }
976}
977void *delpos234(tree234 * t, int index)
978{
979    if (index < 0 || index >= countnode234(t->root))
980        return NULL;
981    return delpos234_internal(t, index);
982}
983void *del234(tree234 * t, void *e)
984{
985    int index;
986    if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
987        return NULL;                   /* it wasn't in there anyway */
988    return delpos234_internal(t, index);        /* it's there; delete it. */
989}
990
991#ifdef TEST
992
993/*
994 * Test code for the 2-3-4 tree. This code maintains an alternative
995 * representation of the data in the tree, in an array (using the
996 * obvious and slow insert and delete functions). After each tree
997 * operation, the verify() function is called, which ensures all
998 * the tree properties are preserved:
999 *  - node->child->parent always equals node
1000 *  - tree->root->parent always equals NULL
1001 *  - number of kids == 0 or number of elements + 1;
1002 *  - tree has the same depth everywhere
1003 *  - every node has at least one element
1004 *  - subtree element counts are accurate
1005 *  - any NULL kid pointer is accompanied by a zero count
1006 *  - in a sorted tree: ordering property between elements of a
1007 *    node and elements of its children is preserved
1008 * and also ensures the list represented by the tree is the same
1009 * list it should be. (This last check also doubly verifies the
1010 * ordering properties, because the `same list it should be' is by
1011 * definition correctly ordered. It also ensures all nodes are
1012 * distinct, because the enum functions would get caught in a loop
1013 * if not.)
1014 */
1015
1016#include <stdarg.h>
1017
1018/*
1019 * Error reporting function.
1020 */
1021void error(char *fmt, ...)
1022{
1023    va_list ap;
1024    printf("ERROR: ");
1025    va_start(ap, fmt);
1026    vfprintf(stdout, fmt, ap);
1027    va_end(ap);
1028    printf("\n");
1029}
1030
1031/* The array representation of the data. */
1032void **array;
1033int arraylen, arraysize;
1034cmpfn234 cmp;
1035
1036/* The tree representation of the same data. */
1037tree234 *tree;
1038
1039typedef struct {
1040    int treedepth;
1041    int elemcount;
1042} chkctx;
1043
1044int chknode(chkctx * ctx, int level, node234 * node,
1045            void *lowbound, void *highbound)
1046{
1047    int nkids, nelems;
1048    int i;
1049    int count;
1050
1051    /* Count the non-NULL kids. */
1052    for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
1053    /* Ensure no kids beyond the first NULL are non-NULL. */
1054    for (i = nkids; i < 4; i++)
1055        if (node->kids[i]) {
1056            error("node %p: nkids=%d but kids[%d] non-NULL",
1057                  node, nkids, i);
1058        } else if (node->counts[i]) {
1059            error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
1060                  node, i, i, node->counts[i]);
1061        }
1062
1063    /* Count the non-NULL elements. */
1064    for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
1065    /* Ensure no elements beyond the first NULL are non-NULL. */
1066    for (i = nelems; i < 3; i++)
1067        if (node->elems[i]) {
1068            error("node %p: nelems=%d but elems[%d] non-NULL",
1069                  node, nelems, i);
1070        }
1071
1072    if (nkids == 0) {
1073        /*
1074         * If nkids==0, this is a leaf node; verify that the tree
1075         * depth is the same everywhere.
1076         */
1077        if (ctx->treedepth < 0)
1078            ctx->treedepth = level;    /* we didn't know the depth yet */
1079        else if (ctx->treedepth != level)
1080            error("node %p: leaf at depth %d, previously seen depth %d",
1081                  node, level, ctx->treedepth);
1082    } else {
1083        /*
1084         * If nkids != 0, then it should be nelems+1, unless nelems
1085         * is 0 in which case nkids should also be 0 (and so we
1086         * shouldn't be in this condition at all).
1087         */
1088        int shouldkids = (nelems ? nelems + 1 : 0);
1089        if (nkids != shouldkids) {
1090            error("node %p: %d elems should mean %d kids but has %d",
1091                  node, nelems, shouldkids, nkids);
1092        }
1093    }
1094
1095    /*
1096     * nelems should be at least 1.
1097     */
1098    if (nelems == 0) {
1099        error("node %p: no elems", node, nkids);
1100    }
1101
1102    /*
1103     * Add nelems to the running element count of the whole tree.
1104     */
1105    ctx->elemcount += nelems;
1106
1107    /*
1108     * Check ordering property: all elements should be strictly >
1109     * lowbound, strictly < highbound, and strictly < each other in
1110     * sequence. (lowbound and highbound are NULL at edges of tree
1111     * - both NULL at root node - and NULL is considered to be <
1112     * everything and > everything. IYSWIM.)
1113     */
1114    if (cmp) {
1115        for (i = -1; i < nelems; i++) {
1116            void *lower = (i == -1 ? lowbound : node->elems[i]);
1117            void *higher =
1118                (i + 1 == nelems ? highbound : node->elems[i + 1]);
1119            if (lower && higher && cmp(lower, higher) >= 0) {
1120                error("node %p: kid comparison [%d=%s,%d=%s] failed",
1121                      node, i, lower, i + 1, higher);
1122            }
1123        }
1124    }
1125
1126    /*
1127     * Check parent pointers: all non-NULL kids should have a
1128     * parent pointer coming back to this node.
1129     */
1130    for (i = 0; i < nkids; i++)
1131        if (node->kids[i]->parent != node) {
1132            error("node %p kid %d: parent ptr is %p not %p",
1133                  node, i, node->kids[i]->parent, node);
1134        }
1135
1136
1137    /*
1138     * Now (finally!) recurse into subtrees.
1139     */
1140    count = nelems;
1141
1142    for (i = 0; i < nkids; i++) {
1143        void *lower = (i == 0 ? lowbound : node->elems[i - 1]);
1144        void *higher = (i >= nelems ? highbound : node->elems[i]);
1145        int subcount =
1146            chknode(ctx, level + 1, node->kids[i], lower, higher);
1147        if (node->counts[i] != subcount) {
1148            error("node %p kid %d: count says %d, subtree really has %d",
1149                  node, i, node->counts[i], subcount);
1150        }
1151        count += subcount;
1152    }
1153
1154    return count;
1155}
1156
1157void verify(void)
1158{
1159    chkctx ctx;
1160    int i;
1161    void *p;
1162
1163    ctx.treedepth = -1;                /* depth unknown yet */
1164    ctx.elemcount = 0;                 /* no elements seen yet */
1165    /*
1166     * Verify validity of tree properties.
1167     */
1168    if (tree->root) {
1169        if (tree->root->parent != NULL)
1170            error("root->parent is %p should be null", tree->root->parent);
1171        chknode(&ctx, 0, tree->root, NULL, NULL);
1172    }
1173    printf("tree depth: %d\n", ctx.treedepth);
1174    /*
1175     * Enumerate the tree and ensure it matches up to the array.
1176     */
1177    for (i = 0; NULL != (p = index234(tree, i)); i++) {
1178        if (i >= arraylen)
1179            error("tree contains more than %d elements", arraylen);
1180        if (array[i] != p)
1181            error("enum at position %d: array says %s, tree says %s",
1182                  i, array[i], p);
1183    }
1184    if (ctx.elemcount != i) {
1185        error("tree really contains %d elements, enum gave %d",
1186              ctx.elemcount, i);
1187    }
1188    if (i < arraylen) {
1189        error("enum gave only %d elements, array has %d", i, arraylen);
1190    }
1191    i = count234(tree);
1192    if (ctx.elemcount != i) {
1193        error("tree really contains %d elements, count234 gave %d",
1194              ctx.elemcount, i);
1195    }
1196}
1197
1198void internal_addtest(void *elem, int index, void *realret)
1199{
1200    int i, j;
1201    void *retval;
1202
1203    if (arraysize < arraylen + 1) {
1204        arraysize = arraylen + 1 + 256;
1205        array = sresize(array, arraysize, void *);
1206    }
1207
1208    i = index;
1209    /* now i points to the first element >= elem */
1210    retval = elem;                     /* expect elem returned (success) */
1211    for (j = arraylen; j > i; j--)
1212        array[j] = array[j - 1];
1213    array[i] = elem;                   /* add elem to array */
1214    arraylen++;
1215
1216    if (realret != retval) {
1217        error("add: retval was %p expected %p", realret, retval);
1218    }
1219
1220    verify();
1221}
1222
1223void addtest(void *elem)
1224{
1225    int i;
1226    void *realret;
1227
1228    realret = add234(tree, elem);
1229
1230    i = 0;
1231    while (i < arraylen && cmp(elem, array[i]) > 0)
1232        i++;
1233    if (i < arraylen && !cmp(elem, array[i])) {
1234        void *retval = array[i];       /* expect that returned not elem */
1235        if (realret != retval) {
1236            error("add: retval was %p expected %p", realret, retval);
1237        }
1238    } else
1239        internal_addtest(elem, i, realret);
1240}
1241
1242void addpostest(void *elem, int i)
1243{
1244    void *realret;
1245
1246    realret = addpos234(tree, elem, i);
1247
1248    internal_addtest(elem, i, realret);
1249}
1250
1251void delpostest(int i)
1252{
1253    int index = i;
1254    void *elem = array[i], *ret;
1255
1256    /* i points to the right element */
1257    while (i < arraylen - 1) {
1258        array[i] = array[i + 1];
1259        i++;
1260    }
1261    arraylen--;                        /* delete elem from array */
1262
1263    if (tree->cmp)
1264        ret = del234(tree, elem);
1265    else
1266        ret = delpos234(tree, index);
1267
1268    if (ret != elem) {
1269        error("del returned %p, expected %p", ret, elem);
1270    }
1271
1272    verify();
1273}
1274
1275void deltest(void *elem)
1276{
1277    int i;
1278
1279    i = 0;
1280    while (i < arraylen && cmp(elem, array[i]) > 0)
1281        i++;
1282    if (i >= arraylen || cmp(elem, array[i]) != 0)
1283        return;                        /* don't do it! */
1284    delpostest(i);
1285}
1286
1287/* A sample data set and test utility. Designed for pseudo-randomness,
1288 * and yet repeatability. */
1289
1290/*
1291 * This random number generator uses the `portable implementation'
1292 * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
1293 * change it if not.
1294 */
1295int randomnumber(unsigned *seed)
1296{
1297    *seed *= 1103515245;
1298    *seed += 12345;
1299    return ((*seed) / 65536) % 32768;
1300}
1301
1302int mycmp(void *av, void *bv)
1303{
1304    char const *a = (char const *) av;
1305    char const *b = (char const *) bv;
1306    return strcmp(a, b);
1307}
1308
1309#define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
1310
1311char *strings[] = {
1312    "a", "ab", "absque", "coram", "de",
1313    "palam", "clam", "cum", "ex", "e",
1314    "sine", "tenus", "pro", "prae",
1315    "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
1316    "penguin", "blancmange", "pangolin", "whale", "hedgehog",
1317    "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
1318    "murfl", "spoo", "breen", "flarn", "octothorpe",
1319    "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
1320    "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
1321    "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
1322    "wand", "ring", "amulet"
1323};
1324
1325#define NSTR lenof(strings)
1326
1327int findtest(void)
1328{
1329    const static int rels[] = {
1330        REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
1331    };
1332    const static char *const relnames[] = {
1333        "EQ", "GE", "LE", "LT", "GT"
1334    };
1335    int i, j, rel, index;
1336    char *p, *ret, *realret, *realret2;
1337    int lo, hi, mid, c;
1338
1339    for (i = 0; i < NSTR; i++) {
1340        p = strings[i];
1341        for (j = 0; j < sizeof(rels) / sizeof(*rels); j++) {
1342            rel = rels[j];
1343
1344            lo = 0;
1345            hi = arraylen - 1;
1346            while (lo <= hi) {
1347                mid = (lo + hi) / 2;
1348                c = strcmp(p, array[mid]);
1349                if (c < 0)
1350                    hi = mid - 1;
1351                else if (c > 0)
1352                    lo = mid + 1;
1353                else
1354                    break;
1355            }
1356
1357            if (c == 0) {
1358                if (rel == REL234_LT)
1359                    ret = (mid > 0 ? array[--mid] : NULL);
1360                else if (rel == REL234_GT)
1361                    ret = (mid < arraylen - 1 ? array[++mid] : NULL);
1362                else
1363                    ret = array[mid];
1364            } else {
1365                assert(lo == hi + 1);
1366                if (rel == REL234_LT || rel == REL234_LE) {
1367                    mid = hi;
1368                    ret = (hi >= 0 ? array[hi] : NULL);
1369                } else if (rel == REL234_GT || rel == REL234_GE) {
1370                    mid = lo;
1371                    ret = (lo < arraylen ? array[lo] : NULL);
1372                } else
1373                    ret = NULL;
1374            }
1375
1376            realret = findrelpos234(tree, p, NULL, rel, &index);
1377            if (realret != ret) {
1378                error("find(\"%s\",%s) gave %s should be %s",
1379                      p, relnames[j], realret, ret);
1380            }
1381            if (realret && index != mid) {
1382                error("find(\"%s\",%s) gave %d should be %d",
1383                      p, relnames[j], index, mid);
1384            }
1385            if (realret && rel == REL234_EQ) {
1386                realret2 = index234(tree, index);
1387                if (realret2 != realret) {
1388                    error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
1389                          p, relnames[j], realret, index, index, realret2);
1390                }
1391            }
1392#if 0
1393            printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
1394                   realret, index);
1395#endif
1396        }
1397    }
1398
1399    realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
1400    if (arraylen && (realret != array[0] || index != 0)) {
1401        error("find(NULL,GT) gave %s(%d) should be %s(0)",
1402              realret, index, array[0]);
1403    } else if (!arraylen && (realret != NULL)) {
1404        error("find(NULL,GT) gave %s(%d) should be NULL", realret, index);
1405    }
1406
1407    realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
1408    if (arraylen
1409        && (realret != array[arraylen - 1] || index != arraylen - 1)) {
1410        error("find(NULL,LT) gave %s(%d) should be %s(0)", realret, index,
1411              array[arraylen - 1]);
1412    } else if (!arraylen && (realret != NULL)) {
1413        error("find(NULL,LT) gave %s(%d) should be NULL", realret, index);
1414    }
1415}
1416
1417int main(void)
1418{
1419    int in[NSTR];
1420    int i, j, k;
1421    unsigned seed = 0;
1422
1423    for (i = 0; i < NSTR; i++)
1424        in[i] = 0;
1425    array = NULL;
1426    arraylen = arraysize = 0;
1427    tree = newtree234(mycmp);
1428    cmp = mycmp;
1429
1430    verify();
1431    for (i = 0; i < 10000; i++) {
1432        j = randomnumber(&seed);
1433        j %= NSTR;
1434        printf("trial: %d\n", i);
1435        if (in[j]) {
1436            printf("deleting %s (%d)\n", strings[j], j);
1437            deltest(strings[j]);
1438            in[j] = 0;
1439        } else {
1440            printf("adding %s (%d)\n", strings[j], j);
1441            addtest(strings[j]);
1442            in[j] = 1;
1443        }
1444        findtest();
1445    }
1446
1447    while (arraylen > 0) {
1448        j = randomnumber(&seed);
1449        j %= arraylen;
1450        deltest(array[j]);
1451    }
1452
1453    freetree234(tree);
1454
1455    /*
1456     * Now try an unsorted tree. We don't really need to test
1457     * delpos234 because we know del234 is based on it, so it's
1458     * already been tested in the above sorted-tree code; but for
1459     * completeness we'll use it to tear down our unsorted tree
1460     * once we've built it.
1461     */
1462    tree = newtree234(NULL);
1463    cmp = NULL;
1464    verify();
1465    for (i = 0; i < 1000; i++) {
1466        printf("trial: %d\n", i);
1467        j = randomnumber(&seed);
1468        j %= NSTR;
1469        k = randomnumber(&seed);
1470        k %= count234(tree) + 1;
1471        printf("adding string %s at index %d\n", strings[j], k);
1472        addpostest(strings[j], k);
1473    }
1474    while (count234(tree) > 0) {
1475        printf("cleanup: tree size %d\n", count234(tree));
1476        j = randomnumber(&seed);
1477        j %= count234(tree);
1478        printf("deleting string %s from index %d\n",
1479               (const char *)array[j], j);
1480        delpostest(j);
1481    }
1482
1483    return 0;
1484}
1485
1486#endif
Note: See TracBrowser for help on using the repository browser.