diff options
Diffstat (limited to 'avl-1.4.0/avl.c')
-rw-r--r-- | avl-1.4.0/avl.c | 1154 |
1 files changed, 1154 insertions, 0 deletions
diff --git a/avl-1.4.0/avl.c b/avl-1.4.0/avl.c new file mode 100644 index 0000000..82cdb6e --- /dev/null +++ b/avl-1.4.0/avl.c @@ -0,0 +1,1154 @@ +/* libavl - manipulates AVL trees. + Copyright (C) 1998, 1999 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program 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 + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. + + The author may be contacted at <pfaffben@pilot.msu.edu> on the + Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA + through more mundane means. */ + +/* This is file avl.c in libavl. */ + +#if HAVE_CONFIG_H +#include <config.h> +#endif +#if PSPP +#include "common.h" +#include "arena.h" +#define HAVE_XMALLOC 1 +#endif +#if SELF_TEST +#include <limits.h> +#include <time.h> +#endif +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include "avl.h" + +#if !PSPP && !__GCC__ +#define inline +#endif + +#if !PSPP +#if __GNUC__ >= 2 +#define unused __attribute__ ((unused)) +#else +#define unused +#endif +#endif + +#ifdef HAVE_XMALLOC +void *xmalloc (size_t); +#else /* !HAVE_XMALLOC */ +/* Allocates SIZE bytes of space using malloc(). Aborts if out of + memory. */ +static void * +xmalloc (size_t size) +{ + void *vp; + + if (size == 0) + return NULL; + vp = malloc (size); + + assert (vp != NULL); + if (vp == NULL) + { + fprintf (stderr, "virtual memory exhausted\n"); + exit (EXIT_FAILURE); + } + return vp; +} +#endif /* !HAVE_XMALLOC */ + +/* Creates an AVL tree in arena OWNER (which can be NULL). The arena + is owned by the caller, not by the AVL tree. CMP is a order + function for the data to be stored in the tree. PARAM is arbitrary + data that becomes an argument to the comparison function. */ +avl_tree * +avl_create (MAYBE_ARENA avl_comparison_func cmp, void *param) +{ + avl_tree *tree; + + assert (cmp != NULL); +#if PSPP + if (owner) + tree = arena_alloc (owner, sizeof (avl_tree)); + else +#endif + tree = xmalloc (sizeof (avl_tree)); + +#if PSPP + tree->owner = owner; +#endif + tree->root.link[0] = NULL; + tree->root.link[1] = NULL; + tree->cmp = cmp; + tree->count = 0; + tree->param = param; + + return tree; +} + +/* Destroy tree TREE. Function FREE_FUNC is called for every node in + the tree as it is destroyed. + + No effect if the tree has an arena owner and free_func is NULL. + The caller owns the arena and must destroy it itself. + + Do not attempt to reuse the tree after it has been freed. Create a + new one. */ +void +avl_destroy (avl_tree *tree, avl_node_func free_func) +{ + assert (tree != NULL); + +#if PSPP + if (free_func || tree->owner == NULL) +#endif + { + /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13 + (postorder traversal). */ + + /* T1. */ + avl_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */ + char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */ + int ap = 0; /* Stack A: height. */ + avl_node *p = tree->root.link[0]; + + for (;;) + { + /* T2. */ + while (p != NULL) + { + /* T3. */ + ab[ap] = 0; + an[ap++] = p; + p = p->link[0]; + } + + /* T4. */ + for (;;) + { + if (ap == 0) + goto done; + + p = an[--ap]; + if (ab[ap] == 0) + { + ab[ap++] = 1; + p = p->link[1]; + break; + } + + if (free_func) + free_func (p->data, tree->param); +#if PSPP + if (tree->owner == NULL) +#endif + free (p); + } + } + } + + done: +#if PSPP + if (tree->owner == NULL) +#endif + free (tree); +} + +/* avl_destroy() with FREE_FUNC hardcoded as free(). */ +void +avl_free (avl_tree *tree) +{ + avl_destroy (tree, (avl_node_func) free); +} + +/* Return the number of nodes in TREE. */ +int +avl_count (const avl_tree *tree) +{ + assert (tree != NULL); + return tree->count; +} + +/* Allocates room for a new avl_node in arena OWNER, or using + xmalloc() if OWNER is NULL. */ +#if PSPP +static inline avl_node * +new_node (arena **owner) +{ + if (owner != NULL) + return arena_alloc (owner, sizeof (avl_node)); + else + return xmalloc (sizeof (avl_node)); +} +#else +static inline avl_node * +new_node (void) +{ + return xmalloc (sizeof (avl_node)); +} + +#define new_node(owner) \ + new_node () +#endif + +/* Copy the contents of TREE to a new tree in arena OWNER. If COPY is + non-NULL, then each data item is passed to function COPY, and the + return values are inserted into the new tree; otherwise, the items + are copied verbatim from the old tree to the new tree. Returns the + new tree. */ +avl_tree * +avl_copy (MAYBE_ARENA const avl_tree *tree, avl_copy_func copy) +{ + /* This is a combination of Knuth's Algorithm 2.3.1C (copying a + binary tree) and Algorithm 2.3.1T as modified by exercise 12 + (preorder traversal). */ + + avl_tree *new_tree; + + /* PT1. */ + const avl_node *pa[AVL_MAX_HEIGHT]; /* Stack PA: nodes. */ + const avl_node **pp = pa; /* Stack PA: stack pointer. */ + const avl_node *p = &tree->root; + + /* QT1. */ + avl_node *qa[AVL_MAX_HEIGHT]; /* Stack QA: nodes. */ + avl_node **qp = qa; /* Stack QA: stack pointer. */ + avl_node *q; + + assert (tree != NULL); +#if PSPP + new_tree = avl_create (owner, tree->cmp, tree->param); +#else + new_tree = avl_create (tree->cmp, tree->param); +#endif + new_tree->count = tree->count; + q = &new_tree->root; + + for (;;) + { + /* C4. */ + if (p->link[0] != NULL) + { + avl_node *r = new_node (owner); + r->link[0] = r->link[1] = NULL; + q->link[0] = r; + } + + /* C5: Find preorder successors of P and Q. */ + goto start; + for (;;) + { + /* PT2. */ + while (p != NULL) + { + goto escape; + start: + /* PT3. */ + *pp++ = p; + *qp++ = q; + p = p->link[0]; + q = q->link[0]; + } + + /* PT4. */ + if (pp == pa) + { + assert (qp == qa); + return new_tree; + } + + p = *--pp; + q = *--qp; + + /* PT5. */ + p = p->link[1]; + q = q->link[1]; + } + escape: + + /* C2. */ + if (p->link[1]) + { + avl_node *r = new_node (owner); + r->link[0] = r->link[1] = NULL; + q->link[1] = r; + } + + /* C3. */ + q->bal = p->bal; + if (copy == NULL) + q->data = p->data; + else + q->data = copy (p->data, tree->param); + } +} + +/* Walk tree TREE in inorder, calling WALK_FUNC at each node. Passes + PARAM to WALK_FUNC. */ +void +avl_walk (const avl_tree *tree, avl_node_func walk_func, void *param) +{ + /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */ + assert (tree && walk_func); + + { + /* T1. */ + const avl_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */ + const avl_node **ap = an; /* Stack A: stack pointer. */ + const avl_node *p = tree->root.link[0]; + + for (;;) + { + /* T2. */ + while (p != NULL) + { + /* T3. */ + *ap++ = p; + p = p->link[0]; + } + + /* T4. */ + if (ap == an) + return; + p = *--ap; + + /* T5. */ + walk_func (p->data, param); + p = p->link[1]; + } + } +} + +/* Each call to this function for a given TREE and TRAV return the + next item in the tree in inorder. Initialize the first element of + TRAV (init) to 0 before calling the first time. Returns NULL when + out of elements. */ +void * +avl_traverse (const avl_tree *tree, avl_traverser *trav) +{ + assert (tree && trav); + + /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */ + if (trav->init == 0) + { + /* T1. */ + trav->init = 1; + trav->nstack = 0; + trav->p = tree->root.link[0]; + } + else + /* T5. */ + trav->p = trav->p->link[1]; + + for (;;) + { + /* T2. */ + while (trav->p != NULL) + { + /* T3. */ + trav->stack[trav->nstack++] = trav->p; + trav->p = trav->p->link[0]; + } + + /* T4. */ + if (trav->nstack == 0) + { + trav->init = 0; + return NULL; + } + trav->p = trav->stack[--trav->nstack]; + + /* T5. */ + return trav->p->data; + } +} + +/* Search TREE for an item matching ITEM. If found, returns a pointer + to the address of the item. If none is found, ITEM is inserted + into the tree, and a pointer to the address of ITEM is returned. + In either case, the pointer returned can be changed by the caller, + or the returned data item can be directly edited, but the key data + in the item must not be changed. */ +void ** +avl_probe (avl_tree *tree, void *item) +{ + /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and + insertion), but caches results of comparisons. In empirical + tests this eliminates about 25% of the comparisons seen under + random insertions. */ + + /* A1. */ + avl_node *t; + avl_node *s, *p, *q, *r; + + assert (tree != NULL); + t = &tree->root; + s = p = t->link[0]; + + if (s == NULL) + { + tree->count++; + assert (tree->count == 1); + q = t->link[0] = new_node (tree->owner); + q->data = item; + q->link[0] = q->link[1] = NULL; + q->bal = 0; + return &q->data; + } + + for (;;) + { + /* A2. */ + int diff = tree->cmp (item, p->data, tree->param); + + /* A3. */ + if (diff < 0) + { + p->cache = 0; + q = p->link[0]; + if (q == NULL) + { + p->link[0] = q = new_node (tree->owner); + break; + } + } + /* A4. */ + else if (diff > 0) + { + p->cache = 1; + q = p->link[1]; + if (q == NULL) + { + p->link[1] = q = new_node (tree->owner); + break; + } + } + else + /* A2. */ + return &p->data; + + /* A3, A4. */ + if (q->bal != 0) + t = p, s = q; + p = q; + } + + /* A5. */ + tree->count++; + q->data = item; + q->link[0] = q->link[1] = NULL; + q->bal = 0; + + /* A6. */ + r = p = s->link[(int) s->cache]; + while (p != q) + { + p->bal = p->cache * 2 - 1; + p = p->link[(int) p->cache]; + } + + /* A7. */ + if (s->cache == 0) + { + /* a = -1. */ + if (s->bal == 0) + { + s->bal = -1; + return &q->data; + } + else if (s->bal == +1) + { + s->bal = 0; + return &q->data; + } + + assert (s->bal == -1); + if (r->bal == -1) + { + /* A8. */ + p = r; + s->link[0] = r->link[1]; + r->link[1] = s; + s->bal = r->bal = 0; + } + else + { + /* A9. */ + assert (r->bal == +1); + p = r->link[1]; + r->link[1] = p->link[0]; + p->link[0] = r; + s->link[0] = p->link[1]; + p->link[1] = s; + if (p->bal == -1) + s->bal = 1, r->bal = 0; + else if (p->bal == 0) + s->bal = r->bal = 0; + else + { + assert (p->bal == +1); + s->bal = 0, r->bal = -1; + } + p->bal = 0; + } + } + else + { + /* a == +1. */ + if (s->bal == 0) + { + s->bal = 1; + return &q->data; + } + else if (s->bal == -1) + { + s->bal = 0; + return &q->data; + } + + assert (s->bal == +1); + if (r->bal == +1) + { + /* A8. */ + p = r; + s->link[1] = r->link[0]; + r->link[0] = s; + s->bal = r->bal = 0; + } + else + { + /* A9. */ + assert (r->bal == -1); + p = r->link[0]; + r->link[0] = p->link[1]; + p->link[1] = r; + s->link[1] = p->link[0]; + p->link[0] = s; + if (p->bal == +1) + s->bal = -1, r->bal = 0; + else if (p->bal == 0) + s->bal = r->bal = 0; + else + { + assert (p->bal == -1); + s->bal = 0, r->bal = 1; + } + p->bal = 0; + } + } + + /* A10. */ + if (t != &tree->root && s == t->link[1]) + t->link[1] = p; + else + t->link[0] = p; + + return &q->data; +} + +/* Search TREE for an item matching ITEM, and return it if found. */ +void * +avl_find (const avl_tree *tree, const void *item) +{ + const avl_node *p; + + assert (tree != NULL); + for (p = tree->root.link[0]; p; ) + { + int diff = tree->cmp (item, p->data, tree->param); + + if (diff < 0) + p = p->link[0]; + else if (diff > 0) + p = p->link[1]; + else + return p->data; + } + + return NULL; +} + +/* Search TREE for an item close to the value of ITEM, and return it. + This function will return a null pointer only if TREE is empty. */ +void * +avl_find_close (const avl_tree *tree, const void *item) +{ + const avl_node *p; + + assert (tree != NULL); + p = tree->root.link[0]; + if (p == NULL) + return NULL; + + for (;;) + { + int diff = tree->cmp (item, p->data, tree->param); + int t; + + if (diff < 0) + t = 0; + else if (diff > 0) + t = 1; + else + return p->data; + + if (p->link[t]) + p = p->link[t]; + else + return p->data; + } +} + +/* Searches AVL tree TREE for an item matching ITEM. If found, the + item is removed from the tree and the actual item found is returned + to the caller. If no item matching ITEM exists in the tree, + returns NULL. */ +void * +avl_delete (avl_tree *tree, const void *item) +{ + /* Uses my Algorithm D, which can be found at + http://www.msu.edu/user/pfaffben/avl. Algorithm D is based on + Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced + tree search and insertion), as well as the notes on pages 465-466 + of Vol. 3. */ + + /* D1. */ + avl_node *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */ + char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */ + int k = 1; /* Stack P: Pointer. */ + + avl_node **q; + avl_node *p; + + assert (tree != NULL); + + a[0] = 0; + pa[0] = &tree->root; + p = tree->root.link[0]; + for (;;) + { + /* D2. */ + int diff; + + if (p == NULL) + return NULL; + + diff = tree->cmp (item, p->data, tree->param); + if (diff == 0) + break; + + /* D3, D4. */ + pa[k] = p; + if (diff < 0) + { + p = p->link[0]; + a[k] = 0; + } + else if (diff > 0) + { + p = p->link[1]; + a[k] = 1; + } + k++; + } + tree->count--; + + item = p->data; + + /* D5. */ + q = &pa[k - 1]->link[(int) a[k - 1]]; + if (p->link[1] == NULL) + { + *q = p->link[0]; + if (*q) + (*q)->bal = 0; + } + else + { + /* D6. */ + avl_node *r = p->link[1]; + if (r->link[0] == NULL) + { + r->link[0] = p->link[0]; + *q = r; + r->bal = p->bal; + a[k] = 1; + pa[k++] = r; + } + else + { + /* D7. */ + avl_node *s = r->link[0]; + int l = k++; + + a[k] = 0; + pa[k++] = r; + + /* D8. */ + while (s->link[0] != NULL) + { + r = s; + s = r->link[0]; + a[k] = 0; + pa[k++] = r; + } + + /* D9. */ + a[l] = 1; + pa[l] = s; + s->link[0] = p->link[0]; + r->link[0] = s->link[1]; + s->link[1] = p->link[1]; + s->bal = p->bal; + *q = s; + } + } + +#if PSPP + if (tree->owner == NULL) +#endif + free (p); + + assert (k > 0); + /* D10. */ + while (--k) + { + avl_node *s = pa[k], *r; + + if (a[k] == 0) + { + /* D10. */ + if (s->bal == -1) + { + s->bal = 0; + continue; + } + else if (s->bal == 0) + { + s->bal = 1; + break; + } + + assert (s->bal == +1); + r = s->link[1]; + + assert (r != NULL); + if (r->bal == 0) + { + /* D11. */ + s->link[1] = r->link[0]; + r->link[0] = s; + r->bal = -1; + pa[k - 1]->link[(int) a[k - 1]] = r; + break; + } + else if (r->bal == +1) + { + /* D12. */ + s->link[1] = r->link[0]; + r->link[0] = s; + s->bal = r->bal = 0; + pa[k - 1]->link[(int) a[k - 1]] = r; + } + else + { + /* D13. */ + assert (r->bal == -1); + p = r->link[0]; + r->link[0] = p->link[1]; + p->link[1] = r; + s->link[1] = p->link[0]; + p->link[0] = s; + if (p->bal == +1) + s->bal = -1, r->bal = 0; + else if (p->bal == 0) + s->bal = r->bal = 0; + else + { + assert (p->bal == -1); + s->bal = 0, r->bal = +1; + } + p->bal = 0; + pa[k - 1]->link[(int) a[k - 1]] = p; + } + } + else + { + assert (a[k] == 1); + + /* D10. */ + if (s->bal == +1) + { + s->bal = 0; + continue; + } + else if (s->bal == 0) + { + s->bal = -1; + break; + } + + assert (s->bal == -1); + r = s->link[0]; + + if (r == NULL || r->bal == 0) + { + /* D11. */ + s->link[0] = r->link[1]; + r->link[1] = s; + r->bal = 1; + pa[k - 1]->link[(int) a[k - 1]] = r; + break; + } + else if (r->bal == -1) + { + /* D12. */ + s->link[0] = r->link[1]; + r->link[1] = s; + s->bal = r->bal = 0; + pa[k - 1]->link[(int) a[k - 1]] = r; + } + else if (r->bal == +1) + { + /* D13. */ + p = r->link[1]; + r->link[1] = p->link[0]; + p->link[0] = r; + s->link[0] = p->link[1]; + p->link[1] = s; + if (p->bal == -1) + s->bal = 1, r->bal = 0; + else if (p->bal == 0) + s->bal = r->bal = 0; + else + { + assert (p->bal == 1); + s->bal = 0, r->bal = -1; + } + p->bal = 0; + pa[k - 1]->link[(int) a[k - 1]] = p; + } + } + } + + return (void *) item; +} + +/* Inserts ITEM into TREE. Returns NULL if the item was inserted, + otherwise a pointer to the duplicate item. */ +void * +avl_insert (avl_tree *tree, void *item) +{ + void **p; + + assert (tree != NULL); + + p = avl_probe (tree, item); + return (*p == item) ? NULL : *p; +} + +/* If ITEM does not exist in TREE, inserts it and returns NULL. If a + matching item does exist, it is replaced by ITEM and the item + replaced is returned. The caller is responsible for freeing the + item returned. */ +void * +avl_replace (avl_tree *tree, void *item) +{ + void **p; + + assert (tree != NULL); + + p = avl_probe (tree, item); + if (*p == item) + return NULL; + else + { + void *r = *p; + *p = item; + return r; + } +} + +/* Delete ITEM from TREE when you know that ITEM must be in TREE. For + debugging purposes. */ +void * +(avl_force_delete) (avl_tree *tree, void *item) +{ + void *found = avl_delete (tree, item); + assert (found != NULL); + return found; +} + +#if SELF_TEST + +/* Used to flag delayed aborting. */ +int done = 0; + +/* Print the structure of node NODE of an avl tree, which is LEVEL + levels from the top of the tree. Uses different delimiters to + visually distinguish levels. */ +void +print_structure (avl_node *node, int level) +{ + char lc[] = "([{`/"; + char rc[] = ")]}'\\"; + + assert (level <= 10); + + if (node == NULL) + { + printf (" nil"); + return; + } + printf (" %c%d", lc[level % 5], (int) node->data); + if (node->link[0] || node->link[1]) + print_structure (node->link[0], level + 1); + if (node->link[1]) + print_structure (node->link[1], level + 1); + printf ("%c", rc[level % 5]); +} + +/* Compare two integers A and B and return a strcmp()-type result. */ +int +compare_ints (const void *a, const void *b, void *param unused) +{ + return ((int) a) - ((int) b); +} + +/* Print the value of integer A. */ +void +print_int (void *a, void *param unused) +{ + printf (" %d", (int) a); +} + +/* Linearly print contents of TREE. */ +void +print_contents (avl_tree *tree) +{ + avl_walk (tree, print_int, NULL); + printf ("\n"); +} + +/* Examine NODE in a avl tree. *COUNT is increased by the number of + nodes in the tree, including the current one. If the node is the + root of the tree, PARENT should be INT_MIN, otherwise it should be + the parent node value. DIR is the direction that the current node + is linked from the parent: -1 for left child, +1 for right child; + it is not used if PARENT is INT_MIN. Returns the height of the + tree rooted at NODE. */ +int +recurse_tree (avl_node *node, int *count, int parent, int dir) +{ + if (node) + { + int d = (int) node->data; + int nl = node->link[0] ? recurse_tree (node->link[0], count, d, -1) : 0; + int nr = node->link[1] ? recurse_tree (node->link[1], count, d, 1) : 0; + (*count)++; + + if (nr - nl != node->bal) + { + printf (" Node %d is unbalanced: right height=%d, left height=%d, " + "difference=%d, but balance factor=%d.\n", + d, nr, nl, nr - nl, node->bal); + done = 1; + } + + if (parent != INT_MIN) + { + assert (dir == -1 || dir == +1); + if (dir == -1 && d > parent) + { + printf (" Node %d is smaller than its left child %d.\n", + parent, d); + done = 1; + } + else if (dir == +1 && d < parent) + { + printf (" Node %d is larger than its right child %d.\n", + parent, d); + done = 1; + } + } + assert (node->bal >= -1 && node->bal <= 1); + return 1 + (nl > nr ? nl : nr); + } + else return 0; +} + +/* Check that everything about TREE is kosher. */ +void +verify_tree (avl_tree *tree) +{ + int count = 0; + recurse_tree (tree->root.link[0], &count, INT_MIN, 0); + if (count != tree->count) + { + printf (" Tree has %d nodes, but tree count is %d.\n", + count, tree->count); + done = 1; + } + if (done) + abort (); +} + +/* Arrange the N elements of ARRAY in random order. */ +void +shuffle (int *array, int n) +{ + int i; + + for (i = 0; i < n; i++) + { + int j = i + rand () % (n - i); + int t = array[j]; + array[j] = array[i]; + array[i] = t; + } +} + +/* Compares avl trees rooted at A and B, making sure that they are + identical. */ +void +compare_trees (avl_node *a, avl_node *b) +{ + if (a == NULL || b == NULL) + { + assert (a == NULL && b == NULL); + return; + } + if (a->data != b->data || a->bal != b->bal + || ((a->link[0] != NULL) ^ (b->link[0] != NULL)) + || ((a->link[1] != NULL) ^ (b->link[1] != NULL))) + { + printf (" Copied nodes differ: %d b=%d a->bal=%d b->bal=%d a:", + (int) a->data, (int) b->data, a->bal, b->bal); + if (a->link[0]) + printf ("l"); + if (a->link[1]) + printf ("r"); + printf (" b:"); + if (b->link[0]) + printf ("l"); + if (b->link[1]) + printf ("r"); + printf ("\n"); + abort (); + } + if (a->link[0] != NULL) + compare_trees (a->link[0], b->link[0]); + if (a->link[1] != NULL) + compare_trees (a->link[1], b->link[1]); +} + +/* Simple stress test procedure for the AVL tree routines. Does the + following: + + * Generate a random number seed. By default this is generated from + the current time. You can also pass a seed value on the command + line if you want to test the same case. The seed value is + displayed. + + * Create a tree and insert the integers from 0 up to TREE_SIZE - 1 + into it, in random order. Verify the tree structure after each + insertion. + + * Remove each integer from the tree, in a different random order. + After each deletion, verify the tree structure; also, make a copy + of the tree into a new tree, verify the copy and compare it to the + original, then destroy the copy. + + * Destroy the tree, increment the random seed value, and start over. + + If you make any modifications to the avl tree routines, then you + might want to insert some calls to print_structure() at strategic + places in order to be able to see what's really going on. Also, + memory debuggers like Checker or Purify are very handy. */ +#define TREE_SIZE 1024 +#define N_ITERATIONS 16 +int +main (int argc, char **argv) +{ + int array[TREE_SIZE]; + int seed; + int iteration; + + if (argc == 2) + seed = atoi (argv[1]); + else + seed = time (0) * 257 % 32768; + + fputs ("Testing avl...\n", stdout); + + for (iteration = 1; iteration <= N_ITERATIONS; iteration++) + { + avl_tree *tree; + int i; + + printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed); + fflush (stdout); + + srand (seed++); + + for (i = 0; i < TREE_SIZE; i++) + array[i] = i; + shuffle (array, TREE_SIZE); + + tree = avl_create (compare_ints, NULL); + for (i = 0; i < TREE_SIZE; i++) + avl_force_insert (tree, (void *) (array[i])); + verify_tree (tree); + + shuffle (array, TREE_SIZE); + for (i = 0; i < TREE_SIZE; i++) + { + avl_tree *copy; + + avl_delete (tree, (void *) (array[i])); + verify_tree (tree); + + copy = avl_copy (tree, NULL); + verify_tree (copy); + compare_trees (tree->root.link[0], copy->root.link[0]); + avl_destroy (copy, NULL); + + if (i % 128 == 0) + { + putchar ('.'); + fflush (stdout); + } + } + fputs (" good.\n", stdout); + + avl_destroy (tree, NULL); + } + + return 0; +} +#endif /* SELF_TEST */ + +/* + Local variables: + compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avl-test avl.c" + End: +*/ + |