diff options
Diffstat (limited to 'misc')
| -rw-r--r-- | misc/Makefile | 8 | ||||
| -rw-r--r-- | misc/tsearch.c | 612 | ||||
| -rw-r--r-- | misc/tst-tsearch.c | 329 |
3 files changed, 846 insertions, 103 deletions
diff --git a/misc/Makefile b/misc/Makefile index b789659eaa..e2db14daa0 100644 --- a/misc/Makefile +++ b/misc/Makefile @@ -64,7 +64,7 @@ install-lib := libbsd-compat.a libg.a non-lib.a := libbsd-compat.a gpl2lgpl := error.c error.h -tests := tst-dirname +tests := tst-dirname tst-tsearch include ../Rules @@ -77,3 +77,9 @@ $(objpfx)libg.a: $(dep-dummy-lib); $(make-dummy-lib) CFLAGS-init-misc.c = -fkeep-inline-functions + +ifeq ($(build-shared),yes) +$(objpfx)tst-tsearch: $(common-objpfx)math/libm.so$(libm.so-version) +else +$(objpfx)tst-tsearch: $(common-objpfx)math/libm.a +endif diff --git a/misc/tsearch.c b/misc/tsearch.c index 6af6536a72..466536bf34 100644 --- a/misc/tsearch.c +++ b/misc/tsearch.c @@ -1,5 +1,6 @@ -/* Copyright (C) 1995, 1996 Free Software Foundation, Inc. +/* Copyright (C) 1995, 1996, 1997 Free Software Foundation, Inc. This file is part of the GNU C Library. + Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997. The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as @@ -16,175 +17,584 @@ write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ -/* Tree search generalized from Knuth (6.2.2) Algorithm T just like - the AT&T man page says. - - The node_t structure is for internal use only, lint doesn't grok it. - - Written by reading the System V Interface Definition, not the code. +/* Tree search for red/black trees. + The algorithm for adding nodes is taken from one of the many "Algorithms" + books by Robert Sedgewick, although the implementation differs. + The algorithm for deleting nodes can probably be found in a book named + "Introduction to Algorithms" by Cormen/Leiserson/Rivest. At least that's + the book that my professor took most algorithms from during the "Data + Structures" course... Totally public domain. */ -/*LINTLIBRARY*/ + +/* Red/black trees are binary trees in which the edges are colored either red + or black. They have the following properties: + 1. The number of black edges on every path from the root to a leaf is + constant. + 2. No two red edges are adjacent. + Therefore there is an upper bound on the length of every path, it's + O(log n) where n is the number of nodes in the tree. No path can be longer + than 1+2*P where P is the length of the shortest path in the tree. + Useful for the implementation: + 3. If one of the children of a node is NULL, then the other one is red + (if it exists). + + In the implementation, not the edges are colored, but the nodes. The color + interpreted as the color of the edge leading to this node. The color is + meaningless for the root node, but we color the root node black for + convenience. All added nodes are red initially. + + Adding to a red/black tree is rather easy. The right place is searched + with a usual binary tree search. Additionally, whenever a node N is + reached that has two red successors, the successors are colored black and + the node itself colored red. This moves red edges up the tree where they + pose less of a problem once we get to really insert the new node. Changing + N's color to red may violate rule 2, however, so rotations may become + necessary to restore the invariants. Adding a new red leaf may violate + the same rule, so afterwards an additional check is run and the tree + possibly rotated. + + Deleting is hairy. There are mainly two nodes involved: the node to be + deleted (n1), and another node that is to be unchained from the tree (n2). + If n1 has a successor (the node with a smallest key that is larger than + n1), then the successor becomes n2 and its contents are copied into n1, + otherwise n1 becomes n2. + Unchaining a node may violate rule 1: if n2 is black, one subtree is + missing one black edge afterwards. The algorithm must try to move this + error upwards towards the root, so that the subtree that does not have + enough black edges becomes the whole tree. Once that happens, the error + has disappeared. It may not be necessary to go all the way up, since it + is possible that rotations and recoloring can fix the error before that. + + Although the deletion algorithm must walk upwards through the tree, we + do not store parent pointers in the nodes. Instead, delete allocates a + small array of parent pointers and fills it while descending the tree. + Since we know that the length of a path is O(log n), where n is the number + of nodes, this is likely to use less memory. */ + +/* Tree rotations look like this: + A C + / \ / \ + B C A G + / \ / \ --> / \ + D E F G B F + / \ + D E + + In this case, A has been rotated left. This preserves the ordering of the + binary tree. */ #include <stdlib.h> #include <search.h> -/* This routine is not very bad. It makes many assumptions about - the compiler. It assumes that the first field in the node must be - the "key" field, which points to the datum. It is very tricky - stuff. H.J. */ - typedef struct node_t { + /* Callers expect this to be the first element in the structure - do not + move! */ const void *key; struct node_t *left; struct node_t *right; + unsigned int red:1; +} *node; + +#undef DEBUGGING + +#ifdef DEBUGGING + +/* Routines to check tree invariants. */ + +#include <assert.h> + +#define CHECK_TREE(a) check_tree(a) + +static void +check_tree_recurse (node p, int d_sofar, int d_total) +{ + if (p == NULL) + { + assert (d_sofar == d_total); + return; + } + + check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total); + check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total); + if (p->left) + assert (!(p->left->red && p->red)); + if (p->right) + assert (!(p->right->red && p->red)); +} + +static void +check_tree (node root) +{ + int cnt = 0; + node p; + if (root == NULL) + return; + root->red = 0; + for(p = root->left; p; p = p->left) + cnt += !p->red; + check_tree_recurse (root, 0, cnt); } -node; -/* Prototype fpr local function. */ -static void trecurse __P ((const void *vroot, __action_fn_t action, int level)); +#else -/* find or insert datum into search tree. -char *key; key to be located -node **rootp; address of tree root -int (*compar)(); ordering function -*/ +#define CHECK_TREE(a) + +#endif + +/* Possibly "split" a node with two red successors, and/or fix up two red + edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP + and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the + comparison values that determined which way was taken in the tree to reach + ROOTP. MODE is 1 if we need not do the split, but must check for two red + edges between GPARENTP and ROOTP. */ +static void +maybe_split_for_insert (node *rootp, node *parentp, node *gparentp, + int p_r, int gp_r, int mode) +{ + node root = *rootp; + node *rp, *lp; + rp = &(*rootp)->right; + lp = &(*rootp)->left; + + /* See if we have to split this node (both successors red). */ + if (mode == 1 + || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red)) + { + /* This node becomes red, its successors black. */ + root->red = 1; + if (*rp) + (*rp)->red = 0; + if (*lp) + (*lp)->red = 0; + + /* If the parent of this node is also red, we have to do + rotations. */ + if (parentp != NULL && (*parentp)->red) + { + node gp = *gparentp; + node p = *parentp; + /* There are two main cases: + 1. The edge types (left or right) of the two red edges differ. + 2. Both red edges are of the same type. + There exist two symmetries of each case, so there is a total of + 4 cases. */ + if ((p_r > 0) != (gp_r > 0)) + { + /* Put the child at the top of the tree, with its parent + and grandparent as successors. */ + p->red = 1; + gp->red = 1; + root->red = 0; + if (p_r < 0) + { + /* Child is left of parent. */ + p->left = *rp; + *rp = p; + gp->right = *lp; + *lp = gp; + } + else + { + /* Child is right of parent. */ + p->right = *lp; + *lp = p; + gp->left = *rp; + *rp = gp; + } + *gparentp = root; + } + else + { + *gparentp = *parentp; + /* Parent becomes the top of the tree, grandparent and + child are its successors. */ + p->red = 0; + gp->red = 1; + if (p_r < 0) + { + /* Left edges. */ + gp->left = p->right; + p->right = gp; + } + else + { + /* Right edges. */ + gp->right = p->left; + p->left = gp; + } + } + } + } +} + +/* Find or insert datum into search tree. + KEY is the key to be located, ROOTP is the address of tree root, + COMPAR the ordering function. */ void * -__tsearch (key, vrootp, compar) - const void *key; - void **vrootp; - __compar_fn_t compar; +__tsearch (const void *key, void **vrootp, __compar_fn_t compar) { - node *q; - node **rootp = (node **) vrootp; + node q; + node *parentp = NULL, *gparentp = NULL; + node *rootp = (node *) vrootp; + node *nextp; + int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */ if (rootp == NULL) return NULL; - while (*rootp != NULL) /* Knuth's T1: */ - { - int r; + /* This saves some additional tests below. */ + if (*rootp != NULL) + (*rootp)->red = 0; + + CHECK_TREE (*rootp); - r = (*compar) (key, (*rootp)->key); - if (r == 0) /* T2: */ - return *rootp; /* we found it! */ - rootp = (r < 0) - ? &(*rootp)->left /* T3: follow left branch */ - : &(*rootp)->right; /* T4: follow right branch */ + nextp = rootp; + while (*nextp != NULL) + { + node root = *rootp; + r = (*compar) (key, root->key); + if (r == 0) + return root; + + maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0); + /* If that did any rotations, parentp and gparentp are now garbage. + That doesn't matter, because the values they contain are never + used again in that case. */ + + nextp = r < 0 ? &root->left : &root->right; + if (*nextp == NULL) + break; + + gparentp = parentp; + parentp = rootp; + rootp = nextp; + + gp_r = p_r; + p_r = r; } - q = (node *) malloc (sizeof (node)); /* T5: key not found */ - if (q != NULL) /* make new node */ + q = (struct node_t *) malloc (sizeof (struct node_t)); + if (q != NULL) { - *rootp = q; /* link new node to old */ + *nextp = q; /* link new node to old */ q->key = key; /* initialize new node */ + q->red = 1; q->left = q->right = NULL; } + if (nextp != rootp) + /* There may be two red edges in a row now, which we must avoid by + rotating the tree. */ + maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); return q; } weak_alias (__tsearch, tsearch) +/* Find datum in search tree. + KEY is the key to be located, ROOTP is the address of tree root, + COMPAR the ordering function. */ void * __tfind (key, vrootp, compar) const void *key; const void **vrootp; __compar_fn_t compar; { - node **rootp = (node **) vrootp; + node *rootp = (node *) vrootp; if (rootp == NULL) return NULL; - while (*rootp != NULL) /* Knuth's T1: */ + CHECK_TREE (*rootp); + + while (*rootp != NULL) { + node root = *rootp; int r; - r = (*compar)(key, (*rootp)->key); - if (r == 0) /* T2: */ - return *rootp; /* we found it! */ + r = (*compar) (key, root->key); + if (r == 0) + return root; - rootp = (r < 0) - ? &(*rootp)->left /* T3: follow left branch */ - : &(*rootp)->right; /* T4: follow right branch */ + rootp = r < 0 ? &root->left : &root->right; } - return NULL; + return NULL; } weak_alias (__tfind, tfind) -/* delete node with given key -char *key; key to be deleted -node **rootp; address of the root of tree -int (*compar)(); comparison function -*/ +/* Delete node with given key. + KEY is the key to be deleted, ROOTP is the address of the root of tree, + COMPAR the comparison function. */ void * -__tdelete (key, vrootp, compar) - const void *key; - void **vrootp; - __compar_fn_t compar; +__tdelete (const void *key, void **vrootp, __compar_fn_t compar) { - node *p; - node *q; - node *r; + node p, q, r, retval; int cmp; - node **rootp = (node **) vrootp; + node *rootp = (node *) vrootp; + node root, unchained; + /* Stack of nodes so we remember the parents without recursion. It's + _very_ unlikely that there are paths longer than 40 nodes. The tree + would need to have around 250.000 nodes. */ + int stacksize = 40; + int sp = 0; + node **nodestack = alloca (sizeof (node *) * stacksize); - if (rootp == NULL || (p = *rootp) == NULL) + if (rootp == NULL) return NULL; + p = *rootp; + if (p == NULL) + return NULL; + + CHECK_TREE (p); while ((cmp = (*compar) (key, (*rootp)->key)) != 0) { + if (sp == stacksize) + { + node **newstack; + stacksize += 20; + newstack = alloca (sizeof (node *) * stacksize); + memcpy (newstack, nodestack, sp * sizeof (node *)); + nodestack = newstack; + } + + nodestack[sp++] = rootp; p = *rootp; - rootp = (cmp < 0) - ? &(*rootp)->left /* follow left branch */ - : &(*rootp)->right; /* follow right branch */ + rootp = ((cmp < 0) + ? &(*rootp)->left + : &(*rootp)->right); if (*rootp == NULL) - return NULL; /* key not found */ + return NULL; } - r = (*rootp)->right; /* D1: */ - q = (*rootp)->left; - if (q == NULL) /* Left NULL? */ - q = r; - else if (r != NULL) /* Right link is NULL? */ + /* This is bogus if the node to be deleted is the root... this routine + really should return an integer with 0 for success, -1 for failure + and errno = ESRCH or something. */ + retval = p; + + /* We don't unchain the node we want to delete. Instead, we overwrite + it with its successor and unchain the successor. If there is no + successor, we really unchain the node to be deleted. */ + + root = *rootp; + + r = root->right; + q = root->left; + + if (q == NULL || r == NULL) + unchained = root; + else { - if (r->left == NULL) /* D2: Find successor */ + node *parent = rootp, *up = &root->right; + for (;;) { - r->left = q; - q = r; + if (sp == stacksize) + { + node **newstack; + stacksize += 20; + newstack = alloca (sizeof (node *) * stacksize); + memcpy (newstack, nodestack, sp * sizeof (node *)); + nodestack = newstack; + } + nodestack[sp++] = parent; + parent = up; + if ((*up)->left == NULL) + break; + up = &(*up)->left; } + unchained = *up; + } + + /* We know that either the left or right successor of UNCHAINED is NULL. + R becomes the other one, it is chained into the parent of UNCHAINED. */ + r = unchained->left; + if (r == NULL) + r = unchained->right; + if (sp == 0) + *rootp = r; + else + { + q = *nodestack[sp-1]; + if (unchained == q->right) + q->right = r; else - { /* D3: Find (struct node_t *)0 link */ - for (q = r->left; q->left != NULL; q = r->left) - r = q; - r->left = q->right; - q->left = (*rootp)->left; - q->right = (*rootp)->right; + q->left = r; + } + + if (unchained != root) + root->key = unchained->key; + if (!unchained->red) + { + /* Now we lost a black edge, which means that the number of black + edges on every path is no longer constant. We must balance the + tree. */ + /* NODESTACK now contains all parents of R. R is likely to be NULL + in the first iteration. */ + /* NULL nodes are considered black throughout - this is necessary for + correctness. */ + while (sp > 0 && (r == NULL || !r->red)) + { + node *pp = nodestack[sp - 1]; + p = *pp; + /* Two symmetric cases. */ + if (r == p->left) + { + /* Q is R's brother, P is R's parent. The subtree with root + R has one black edge less than the subtree with root Q. */ + q = p->right; + if (q != NULL && q->red) + { + /* If Q is red, we know that P is black. We rotate P left + so that Q becomes the top node in the tree, with P below + it. P is colored red, Q is colored black. + This action does not change the black edge count for any + leaf in the tree, but we will be able to recognize one + of the following situations, which all require that Q + is black. */ + q->red = 0; + p->red = 1; + /* Left rotate p. */ + p->right = q->left; + q->left = p; + *pp = q; + /* Make sure pp is right if the case below tries to use + it. */ + nodestack[sp++] = pp = &q->left; + q = p->right; + } + /* We know that Q can't be NULL here. We also know that Q is + black. */ + if ((q->left == NULL || !q->left->red) + && (q->right == NULL || !q->right->red)) + { + /* Q has two black successors. We can simply color Q red. + The whole subtree with root P is now missing one black + edge. Note that this action can temporarily make the + tree invalid (if P is red). But we will exit the loop + in that case and set P black, which both makes the tree + valid and also makes the black edge count come out + right. If P is black, we are at least one step closer + to the root and we'll try again the next iteration. */ + q->red = 1; + r = p; + } + else + { + /* Q is black, one of Q's successors is red. We can + repair the tree with one operation and will exit the + loop afterwards. */ + if (q->right == NULL || !q->right->red) + { + /* The left one is red. We perform the same action as + in maybe_split_for_insert where two red edges are + adjacent but point in different directions: + Q's left successor (let's call it Q2) becomes the + top of the subtree we are looking at, its parent (Q) + and grandparent (P) become its successors. The former + successors of Q2 are placed below P and Q. + P becomes black, and Q2 gets the color that P had. + This changes the black edge count only for node R and + its successors. */ + node q2 = q->left; + q2->red = p->red; + p->right = q2->left; + q->left = q2->right; + q2->right = q; + q2->left = p; + *pp = q2; + p->red = 0; + } + else + { + /* It's the right one. Rotate P left. P becomes black, + and Q gets the color that P had. Q's right successor + also becomes black. This changes the black edge + count only for node R and its successors. */ + q->red = p->red; + p->red = 0; + + q->right->red = 0; + + /* left rotate p */ + p->right = q->left; + q->left = p; + *pp = q; + } + + /* We're done. */ + sp = 1; + r = NULL; + } + } + else + { + /* Comments: see above. */ + q = p->left; + if (q != NULL && q->red) + { + q->red = 0; + p->red = 1; + p->left = q->right; + q->right = p; + *pp = q; + nodestack[sp++] = pp = &q->right; + q = p->left; + } + if ((q->right == NULL || !q->right->red) + && (q->left == NULL || !q->left->red)) + { + q->red = 1; + r = p; + } + else + { + if (q->left == NULL || !q->left->red) + { + node q2 = q->right; + q2->red = p->red; + p->left = q2->right; + q->right = q2->left; + q2->left = q; + q2->right = p; + *pp = q2; + p->red = 0; + } + else + { + q->red = p->red; + p->red = 0; + q->left->red = 0; + p->left = q->right; + q->right = p; + *pp = q; + } + sp = 1; + r = NULL; + } + } + --sp; } + if (r != NULL) + r->red = 0; } - free ((struct node_t *) *rootp); /* D4: Free node */ - *rootp = q; /* link parent to new node */ - return p; + + free (unchained); + return retval; } weak_alias (__tdelete, tdelete) -/* Walk the nodes of a tree -node *root; Root of the tree to be walked -void (*action)(); Function to be called at each node -int level; -*/ +/* Walk the nodes of a tree. + ROOT is the root of the tree to be walked, ACTION the function to be + called at each node. LEVEL is the level of ROOT in the whole tree. */ static void -trecurse (vroot, action, level) - const void *vroot; - __action_fn_t action; - int level; +trecurse (const void *vroot, __action_fn_t action, int level) { - node *root = (node *) vroot; + node root = (node ) vroot; if (root->left == NULL && root->right == NULL) (*action) (root, leaf, level); @@ -201,17 +611,15 @@ trecurse (vroot, action, level) } -/* void twalk(root, action) Walk the nodes of a tree -node *root; Root of the tree to be walked -void (*action)(); Function to be called at each node -PTR -*/ +/* Walk the nodes of a tree. + ROOT is the root of the tree to be walked, ACTION the function to be + called at each node. */ void -__twalk (vroot, action) - const void *vroot; - __action_fn_t action; +__twalk (const void *vroot, __action_fn_t action) { - const node *root = (node *) vroot; + const node root = (node) vroot; + + CHECK_TREE (root); if (root != NULL && action != NULL) trecurse (root, action, 0); diff --git a/misc/tst-tsearch.c b/misc/tst-tsearch.c new file mode 100644 index 0000000000..eca11cbb95 --- /dev/null +++ b/misc/tst-tsearch.c @@ -0,0 +1,329 @@ +/* Test program for tsearch et al. + Copyright (C) 1997 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with the GNU C Library; see the file COPYING.LIB. If not, + write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. */ + +#define _GNU_SOURCE 1 + +#include <stdio.h> +#include <stdlib.h> +#include <search.h> + +#define SEED 0 +#define BALANCED 1 +#define PASSES 100 + +#if BALANCED +#include <math.h> +#define SIZE 1000 +#else +#define SIZE 100 +#endif + +enum order +{ + ascending, + descending, + randomorder +}; + +enum action +{ + build, + build_and_del, + delete, + find +}; + +/* Set to 1 if a test is flunked. */ +static int error = 0; + +/* The keys we add to the tree. */ +static int x[SIZE]; + +/* Pointers into the key array, possibly permutated, to define an order + for insertion/removal. */ +static int y[SIZE]; + +/* Flags set for each element visited during a tree walk. */ +static int z[SIZE]; + +/* Depths for all the elements, to check that the depth is constant for + all three visits. */ +static int depths[SIZE]; + +/* Maximum depth during a tree walk. */ +static int max_depth; + +/* Compare two keys. */ +static int +cmp_fn (const void *a, const void *b) +{ + return *(const int *) a - *(const int *) b; +} + +/* Permute an array of integers. */ +static void +memfry (int *string) +{ + int i; + + for (i = 0; i < SIZE; ++i) + { + int32_t j; + int c; + + j = random () % SIZE; + + c = string[i]; + string[i] = string[j]; + string[j] = c; + } +} + +static void +walk_action (const void *nodep, const VISIT which, const int depth) +{ + int key = **(int **) nodep; + + if (depth > max_depth) + max_depth = depth; + if (which == leaf || which == preorder) + { + ++z[key]; + depths[key] = depth; + } + else + { + if (depths[key] != depth) + { + fputs ("Depth for one element is not constant during tree walk.\n", + stderr); + } + } +} + +static void +walk_tree (void *root, int expected_count) +{ + int i; + + memset (z, 0, sizeof z); + max_depth = 0; + + twalk (root, walk_action); + for (i = 0; i < expected_count; ++i) + if (z[i] != 1) + { + fputs ("Node was not visited.\n", stderr); + error = 1; + } + +#if BALANCED + if (max_depth > log (expected_count) * 2 + 2) +#else + if (max_depth > expected_count) +#endif + { + fputs ("Depth too large during tree walk.\n", stderr); + error = 1; + } +} + +/* Perform an operation on a tree. */ +static void +mangle_tree (enum order how, enum action what, void **root, int lag) +{ + int i; + + if (how == randomorder) + { + for (i = 0; i < SIZE; ++i) + y[i] = i; + memfry (y); + } + + for (i = 0; i < SIZE + lag; ++i) + { + void *elem; + int j, k; + + switch (how) + { + case randomorder: + if (i >= lag) + k = y[i - lag]; + else + k = y[SIZE - i - 1 + lag]; + j = y[i]; + break; + + case ascending: + k = i - lag; + j = i; + break; + + case descending: + k = SIZE - i - 1 + lag; + j = SIZE - i - 1; + break; + + default: + /* This never should happen, but gcc isn't smart enough to + recognize it. */ + abort (); + } + + switch (what) + { + case build_and_del: + case build: + if (i < SIZE) + { + if (tfind (x + j, (const void **) root, cmp_fn) != NULL) + { + fputs ("Found element which is not in tree yet.\n", stderr); + error = 1; + } + elem = tsearch (x + j, root, cmp_fn); + if (elem == 0 + || tfind (x + j, (const void **) root, cmp_fn) == NULL) + { + fputs ("Couldn't find element after it was added.\n", + stderr); + error = 1; + } + } + + if (what == build || i < lag) + break; + + j = k; + /* fall through */ + + case delete: + elem = tfind (x + j, (const void **) root, cmp_fn); + if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL) + { + fputs ("Error deleting element.\n", stderr); + error = 1; + } + break; + + case find: + if (tfind (x + j, (const void **) root, cmp_fn) == NULL) + { + fputs ("Couldn't find element after it was added.\n", stderr); + error = 1; + } + break; + + } + } +} + + +int +main (int argc, char **argv) +{ + int total_error = 0; + static int state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + void *root = NULL; + int i, j; + + initstate (SEED, state, 8); + + for (i = 0; i < SIZE; ++i) + x[i] = i; + + /* Do this loop several times to get different permutations for the + random case. */ + fputs ("Series I\n", stderr); + for (i = 0; i < PASSES; ++i) + { + fprintf (stderr, "Pass %d... ", i + 1); + fflush (stdout); + error = 0; + + mangle_tree (ascending, build, &root, 0); + mangle_tree (ascending, find, &root, 0); + mangle_tree (descending, find, &root, 0); + mangle_tree (randomorder, find, &root, 0); + walk_tree (root, SIZE); + mangle_tree (ascending, delete, &root, 0); + + mangle_tree (ascending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (descending, delete, &root, 0); + + mangle_tree (ascending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (randomorder, delete, &root, 0); + + mangle_tree (descending, build, &root, 0); + mangle_tree (ascending, find, &root, 0); + mangle_tree (descending, find, &root, 0); + mangle_tree (randomorder, find, &root, 0); + walk_tree (root, SIZE); + mangle_tree (descending, delete, &root, 0); + + mangle_tree (descending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (descending, delete, &root, 0); + + mangle_tree (descending, build, &root, 0); + walk_tree (root, SIZE); + mangle_tree (randomorder, delete, &root, 0); + + mangle_tree (randomorder, build, &root, 0); + mangle_tree (ascending, find, &root, 0); + mangle_tree (descending, find, &root, 0); + mangle_tree (randomorder, find, &root, 0); + walk_tree (root, SIZE); + mangle_tree (randomorder, delete, &root, 0); + + for (j = 1; j < SIZE; j *= 2) + { + mangle_tree (randomorder, build_and_del, &root, j); + } + + fputs (error ? " failed!\n" : " ok.\n", stderr); + total_error |= error; + } + + fputs ("Series II\n", stderr); + for (i = 1; i < SIZE; i *= 2) + { + fprintf (stderr, "For size %d... ", i); + fflush (stdout); + error = 0; + + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + mangle_tree (ascending, build_and_del, &root, i); + mangle_tree (descending, build_and_del, &root, i); + + fputs (error ? " failed!\n" : " ok.\n", stderr); + total_error |= error; + } + + return total_error; +} |