diff options
Diffstat (limited to 'avl-1.4.0/avlt.c')
-rw-r--r-- | avl-1.4.0/avlt.c | 1597 |
1 files changed, 1597 insertions, 0 deletions
diff --git a/avl-1.4.0/avlt.c b/avl-1.4.0/avlt.c new file mode 100644 index 0000000..d050fba --- /dev/null +++ b/avl-1.4.0/avlt.c @@ -0,0 +1,1597 @@ +/* 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 avlt.c in libavl. */ + +#if HAVE_CONFIG_H +#include <config.h> +#endif +#if SELF_TEST +#include <limits.h> +#include <time.h> +#endif +#include <stdio.h> +#include <stddef.h> +#include <stdlib.h> +#include <assert.h> +#include "avlt.h" + +/* Tag types. */ +#define PLUS +1 +#define MINUS -1 + +#if !__GCC__ && !defined (inline) +#define inline +#endif + +#if __GNUC__ >= 2 +#define unused __attribute__ ((unused)) +#else +#define unused +#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. */ +avlt_tree * +avlt_create (avl_comparison_func cmp, void *param) +{ + avlt_tree *tree; + + assert (cmp != NULL); + tree = xmalloc (sizeof (avlt_tree)); + + tree->root.link[0] = tree->root.link[1] = &tree->root; + tree->root.tag[0] = MINUS; + tree->root.tag[1] = PLUS; + 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 +avlt_destroy (avlt_tree *tree, avl_node_func free_func) +{ + assert (tree != NULL); + + if (tree->root.link[0] != &tree->root) + { + /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13 + (postorder traversal). */ + + /* T1. */ + avlt_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */ + char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */ + int ap = 0; /* Stack A: height. */ + avlt_node *p = tree->root.link[0]; + + for (;;) + { + /* T2. */ + for (;;) + { + /* T3. */ + ab[ap] = 0; + an[ap++] = p; + if (p->tag[0] == MINUS) + break; + p = p->link[0]; + } + + /* T4. */ + for (;;) + { + if (ap == 0) + goto done; + + p = an[--ap]; + if (ab[ap] == 0) + { + ab[ap++] = 1; + if (p->tag[1] == MINUS) + continue; + p = p->link[1]; + break; + } + + if (free_func) + free_func (p->data, tree->param); + free (p); + } + } + } + + done: + free (tree); +} + +/* avlt_destroy() with FREE_FUNC hardcoded as free(). */ +void +avlt_free (avlt_tree *tree) +{ + avlt_destroy (tree, (avl_node_func) free); +} + +/* Return the number of nodes in TREE. */ +int +avlt_count (const avlt_tree *tree) +{ + assert (tree != NULL); + return tree->count; +} + +/* 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. */ +avlt_tree * +avlt_copy (const avlt_tree *tree, avl_copy_func copy) +{ + /* Knuth's Algorithm 2.3.1C (copying a binary tree). Additionally + uses Algorithm 2.3.1I (insertion into a threaded binary tree) and + Algorithm 2.3.1 exercise 17 (preorder successor in threaded + binary tree). */ + + avlt_tree *new_tree; + + const avlt_node *p; + avlt_node *q; + + assert (tree != NULL); + new_tree = avlt_create (tree->cmp, tree->param); + new_tree->count = tree->count; + p = &tree->root; + if (p->link[0] == p) + return new_tree; + q = &new_tree->root; + + for (;;) + { + /* C4. This is Algorithm 2.3.1I modified for insertion to the + left. Step I2 is not necessary. */ + if (p->tag[0] == PLUS) + { + avlt_node *r = xmalloc (sizeof (avlt_node)); + + r->link[0] = q->link[0]; + r->tag[0] = q->tag[0]; + q->link[0] = r; + q->tag[0] = PLUS; + r->link[1] = q; + r->tag[1] = MINUS; + } + + /* C5: Find preorder successors of P and Q. This is Algorithm + 2.3.1 exercise 17 but applies its actions to Q as well as + P. */ + if (p->tag[0] == PLUS) + { + p = p->link[0]; + q = q->link[0]; + } + else + { + while (p->tag[1] == MINUS) + { + p = p->link[1]; + q = q->link[1]; + } + p = p->link[1]; + q = q->link[1]; + } + + /* C6. */ + if (p == &tree->root) + { + assert (q == &new_tree->root); + return new_tree; + } + + /* C2. This is Algorithm 2.3.1I. Step I2 is not necessary. */ + if (p->tag[1] == PLUS) + { + avlt_node *r = xmalloc (sizeof (avlt_node)); + + r->link[1] = q->link[1]; + r->tag[1] = q->tag[1]; + q->link[1] = r; + q->tag[1] = PLUS; + r->link[0] = q; + r->tag[0] = MINUS; + } + + /* C3. */ + q->bal = p->bal; + if (copy == NULL) + q->data = p->data; + else + q->data = copy (p->data, tree->param); + } +} + +/* Threads the unthreaded AVL tree TREE in-place, and returns TREE cast to + avlt_tree *. */ +avlt_tree * +avlt_thread (struct avl_tree *_tree) +{ + /* Uses Knuth's Algorithm 2.3.1 exercise 30 (thread an unthreaded + tree, with Algorithm 2.3.1T (inorder traversal) for computing + Q$. */ + + avlt_tree *tree = (avlt_tree *) _tree; + + /* Algorithm T's variables. */ + avlt_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */ + avlt_node **ap; /* Stack A: stack pointer. */ + avlt_node *tp; /* P. */ + + /* Algorithm L's variables. */ + avlt_node *p, *q; + + assert (tree != NULL); + + /* T1. */ + ap = an; + tp = tree->root.link[0]; + + /* L1. */ + q = &tree->root; + q->link[1] = q; + + for (;;) + { + /* L2. */ + { + /* T2. */ + while (tp != NULL) + { + /* T3. */ + *ap++ = tp; + tp = tp->link[0]; + } + + /* T4. Modified to visit HEAD after fully traversing the + tree. */ + if (ap == an) + tp = &tree->root; + else + tp = *--ap; + + /* T5: Visit P. */ + p = tp; + } + + /* L3. */ + if (q->link[1] == NULL) + { + q->link[1] = p; + q->tag[1] = MINUS; + } + else + q->tag[1] = PLUS; + + if (p->link[0] == NULL) + { + p->link[0] = q; + p->tag[0] = MINUS; + } + else + p->tag[0] = PLUS; + + /* L4. */ + if (p == &tree->root) + return tree; + q = p; + + /* T5: Next. */ + tp = tp->link[1]; + } +} + +/* Unthreads the threaded tree TREE in-place, and returns TREE cast to + avl_tree *. */ +struct avl_tree * +avlt_unthread (avlt_tree *tree) +{ + /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13 + (postorder traversal). */ + + /* T1. */ + avlt_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */ + char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */ + int ap = 0; /* Stack A: height. */ + avlt_node *p; + + assert (tree != NULL); + p = tree->root.link[0]; + if (p != &tree->root) + for (;;) + { + /* T2. */ + for (;;) + { + /* T3. */ + ab[ap] = 0; + an[ap++] = p; + if (p->tag[0] == MINUS) + break; + p = p->link[0]; + } + + /* T4. */ + for (;;) + { + if (ap == 0) + goto done; + + p = an[--ap]; + if (ab[ap] == 0) + { + ab[ap++] = 1; + if (p->tag[1] == MINUS) + continue; + p = p->link[1]; + break; + } + + if (p->tag[0] == MINUS) + p->link[0] = NULL; + if (p->tag[1] == MINUS) + p->link[1] = NULL; + } + } + else + tree->root.link[0] = NULL; + + done: + tree->root.link[1] = NULL; + return (struct avl_tree *) tree; +} + +/* Walk tree TREE in inorder, calling WALK_FUNC at each node. Passes + PARAM to WALK_FUNC. */ +void +avlt_walk (const avlt_tree *tree, avl_node_func walk_func, void *param) +{ + const avlt_node *p; + + /* Uses Knuth's algorithm 2.3.1D (threaded inorder successor). */ + assert (tree && walk_func); + + p = &tree->root; + for (;;) + { + if (p->tag[1] == MINUS) + p = p->link[1]; + else + { + p = p->link[1]; + while (p->tag[0] == PLUS) + p = p->link[0]; + } + + if (p == &tree->root) + return; + + walk_func (p->data, param); + } +} + +/* 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 * +avlt_traverse (const avlt_tree *tree, avlt_traverser *trav) +{ + const avlt_node *p; + + assert (tree && trav); + + if (trav->init == 0) + { + p = &tree->root; + trav->init = 1; + } + else + p = trav->p; + + /* Knuth's Algorithm 2.3.1S (threaded inorder successor). */ + if (p->tag[1] == MINUS) + p = p->link[1]; + else + { + p = p->link[1]; + while (p->tag[0] == PLUS) + p = p->link[0]; + } + + if (p == &tree->root) + { + trav->init = 0; + return NULL; + } + else + { + trav->p = p; + return (void *) p->data; + } +} + +/* Given ITEM, a pointer to a data item in TREE (or NULL), returns a + pointer to the next item in the tree in comparison order, or NULL + if ITEM is the last item. */ +void ** +avlt_next (const avlt_tree *tree, void **item) +{ + const avlt_node *p; + + assert (tree != NULL); + if (item == NULL) + p = &tree->root; + else + p = (avlt_node *) (((char *) item) - offsetof (avlt_node, data)); + + /* Knuth's Algorithm 2.3.1S (threaded inorder successor). */ + if (p->tag[1] == MINUS) + p = p->link[1]; + else + { + p = p->link[1]; + while (p->tag[0] == PLUS) + p = p->link[0]; + } + + if (p == &tree->root) + return NULL; + + return (void **) &p->data; +} + +/* Given ITEM, a pointer to a data item in TREE (or NULL), returns a + pointer to the previous item in the tree in comparison order, or + NULL if ITEM is the first item. */ +void ** +avlt_prev (const avlt_tree *tree, void **item) +{ + const avlt_node *p; + + assert (tree != NULL); + if (item == NULL) + { + /* Find node with greatest value. */ + p = tree->root.link[0]; + if (p == &tree->root) + return NULL; + while (p->tag[1] == PLUS) + p = p->link[1]; + } + else + { + p = (avlt_node *) (((char *) item) - offsetof (avlt_node, data)); + + /* Knuth's Algorithm 2.3.1S (threaded inorder successor) + modified to find the predecessor node. */ + if (p->tag[0] == MINUS) + p = p->link[0]; + else + { + assert (p->tag[0] == PLUS); + p = p->link[0]; + while (p->tag[1] == PLUS) + p = p->link[1]; + } + } + + if (p == &tree->root) + return NULL; + + return (void **) &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 ** +avlt_probe (avlt_tree *tree, void *item) +{ + /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and + insertion), modified for a threaded binary tree. Caches results + of comparisons. In empirical tests this eliminates about 25% of + the comparisons seen under random insertions. */ + + /* A1. */ + avlt_node *t; + avlt_node *s, *p, *q, *r; + + assert (tree != NULL); + t = &tree->root; + s = p = t->link[0]; + + if (t->tag[0] == MINUS) + { + tree->count++; + assert (tree->count == 1); + t->tag[0] = PLUS; + q = t->link[0] = xmalloc (sizeof (avlt_node)); + q->data = item; + q->link[0] = q->link[1] = t; + q->tag[0] = q->tag[1] = MINUS; + 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 (p->tag[0] == MINUS) + { + q = xmalloc (sizeof (avlt_node)); + q->link[0] = p->link[0]; + q->tag[0] = p->tag[0]; + p->link[0] = q; + p->tag[0] = PLUS; + q->link[1] = p; + q->tag[1] = MINUS; + break; + } + } + /* A4. */ + else if (diff > 0) + { + p->cache = 1; + q = p->link[1]; + if (p->tag[1] == MINUS) + { + q = xmalloc (sizeof (avlt_node)); + q->link[1] = p->link[1]; + q->tag[1] = p->tag[1]; + p->link[1] = q; + p->tag[1] = PLUS; + q->link[0] = p; + q->tag[0] = MINUS; + 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->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]; + s->tag[0] = r->tag[1]; + r->link[1] = s; + r->tag[1] = PLUS; + if (s->link[0] == s) + { + s->link[0] = r; + s->tag[0] = MINUS; + } + r->tag[0] = r->tag[1] = PLUS; + 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; + p->tag[0] = p->tag[1] = PLUS; + if (s->link[0] == s) + { + s->link[0] = p; + s->tag[0] = MINUS; + } + if (r->link[1] == r) + { + r->link[1] = p; + r->tag[1] = MINUS; + } + } + } + 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]; + s->tag[1] = r->tag[0]; + r->link[0] = s; + r->tag[0] = PLUS; + if (s->link[1] == s) + { + s->link[1] = r; + s->tag[1] = MINUS; + } + 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->tag[0] = p->tag[1] = PLUS; + if (s->link[1] == s) + { + s->link[1] = p; + s->tag[1] = MINUS; + } + if (r->link[0] == r) + { + r->link[0] = p; + r->tag[0] = MINUS; + } + 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 a pointer to it + if found. */ +void ** +avlt_find (const avlt_tree *tree, const void *item) +{ + const avlt_node *p; + + assert (tree != NULL); + if (tree->root.tag[0] == MINUS) + /* Tree is empty. */ + return NULL; + + p = tree->root.link[0]; + for (;;) + { + int diff = tree->cmp (item, p->data, tree->param); + int t; + + /* A3. */ + if (diff < 0) + t = 0; + else if (diff > 0) + t = 1; + else + return (void **) &p->data; + + if (p->tag[t] == PLUS) + p = p->link[t]; + else + 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 ** +avlt_find_close (const avlt_tree *tree, const void *item) +{ + const avlt_node *p; + + assert (tree != NULL); + if (tree->root.tag[0] == MINUS) + /* Tree is empty. */ + return NULL; + + p = tree->root.link[0]; + for (;;) + { + int diff = tree->cmp (item, p->data, tree->param); + int t; + + /* A3. */ + if (diff < 0) + t = 0; + else if (diff > 0) + t = 1; + else + return (void **) &p->data; + + if (p->tag[t] == PLUS) + p = p->link[t]; + else + return (void **) &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 * +avlt_delete (avlt_tree *tree, const void *item) +{ + /* Uses my Algorithm DT, which can be found at + http://www.msu.edu/user/pfaffben/avl. Algorithm DT is based on + Knuth's Algorithms 6.2.2D (Tree deletion), 6.2.3A (Balanced tree + search and insertion), 2.3.1I (Insertion into a threaded binary + trees), and the notes on pages 465-466 of Vol. 3. */ + + /* D1. */ + avlt_node *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */ + unsigned char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */ + int k = 1; /* Stack P: Pointer. */ + + avlt_node *p; + + assert (tree != NULL); + + if (tree->root.tag[0] == MINUS) + /* Empty tree. */ + return NULL; + + a[0] = 0; + pa[0] = &tree->root; + p = tree->root.link[0]; + for (;;) + { + /* D2. */ + int diff = tree->cmp (item, p->data, tree->param); + + if (diff == 0) + break; + + /* D3, D4. */ + pa[k] = p; + if (diff < 0) + { + if (p->tag[0] == PLUS) + { + p = p->link[0]; + a[k] = 0; + } + else + return NULL; + } + else if (diff > 0) + { + if (p->tag[1] == PLUS) + { + p = p->link[1]; + a[k] = 1; + } + else + return NULL; + } + + k++; + } + tree->count--; + + item = p->data; + + { + avlt_node *t = p; + avlt_node **q = &pa[k - 1]->link[(int) a[k - 1]]; + + /* D5. */ + if (t->tag[1] == MINUS) + { + if (t->tag[0] == PLUS) + { + avlt_node *const x = t->link[0]; + + *q = x; + (*q)->bal = 0; + if (x->tag[1] == MINUS) + { + if (a[k - 1] == 1) + x->link[1] = t->link[1]; + else + x->link[1] = pa[k - 1]; + } + } + else + { + *q = t->link[a[k - 1]]; + pa[k - 1]->tag[a[k - 1]] = MINUS; + } + } + else + { + /* D6. */ + avlt_node *r = t->link[1]; + if (r->tag[0] == MINUS) + { + r->link[0] = t->link[0]; + r->tag[0] = t->tag[0]; + r->bal = t->bal; + if (r->tag[0] == PLUS) + { + avlt_node *s = r->link[0]; + while (s->tag[1] == PLUS) + s = s->link[1]; + assert (s->tag[1] == MINUS); + s->link[1] = r; + } + *q = r; + a[k] = 1; + pa[k++] = r; + } + else + { + /* D7. */ + avlt_node *s = r->link[0]; + + a[k] = 1; + pa[k++] = t; + + a[k] = 0; + pa[k++] = r; + + /* D8. */ + while (s->tag[0] != MINUS) + { + r = s; + s = r->link[0]; + a[k] = 0; + pa[k++] = r; + } + + /* D9. */ + t->data = s->data; + if (s->tag[1] == MINUS) + { + r->tag[0] = MINUS; + r->link[0] = t; + } + else + { + r->link[0] = s->link[1]; + if (s->link[1]->tag[0] == MINUS) + s->link[1]->link[0] = t; + } + p = s; + } + } + } + + free (p); + + assert (k > 0); + /* D10. */ + while (--k) + { + avlt_node *const s = pa[k]; + + if (a[k] == 0) + { + avlt_node *const r = s->link[1]; + + /* D10. */ + if (s->bal == -1) + { + s->bal = 0; + continue; + } + else if (s->bal == 0) + { + s->bal = +1; + break; + } + + assert (s->bal == +1); + if (s->tag[1] == MINUS || 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. */ + if (PLUS == (s->tag[1] = r->tag[0])) + s->link[1] = r->link[0]; + r->link[0] = s; + r->tag[0] = PLUS; + s->bal = r->bal = 0; + pa[k - 1]->link[a[k - 1]] = r; + } + else + { + /* D13. */ + assert (r->bal == -1); + p = r->link[0]; + if (PLUS == (r->tag[0] = p->tag[1])) + r->link[0] = p->link[1]; + p->link[1] = r; + p->tag[1] = PLUS; + if (MINUS == (s->tag[1] = p->tag[0])) + s->link[1] = p; + else + s->link[1] = p->link[0]; + p->link[0] = s; + p->tag[0] = PLUS; + 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; + pa[k - 1]->tag[(int) a[k - 1]] = PLUS; + } + } + else + { + avlt_node *const r = s->link[0]; + + /* D10. */ + if (s->bal == +1) + { + s->bal = 0; + continue; + } + else if (s->bal == 0) + { + s->bal = -1; + break; + } + + assert (s->bal == -1); + if (s->tag[0] == MINUS || 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. */ + if (PLUS == (s->tag[0] = r->tag[1])) + s->link[0] = r->link[1]; + r->link[1] = s; + r->tag[1] = PLUS; + s->bal = r->bal = 0; + pa[k - 1]->link[a[k - 1]] = r; + } + else + { + /* D13. */ + assert (r->bal == +1); + p = r->link[1]; + if (PLUS == (r->tag[1] = p->tag[0])) + r->link[1] = p->link[0]; + p->link[0] = r; + p->tag[0] = PLUS; + if (MINUS == (s->tag[0] = p->tag[1])) + s->link[0] = p; + else + s->link[0] = p->link[1]; + p->link[1] = s; + p->tag[1] = PLUS; + 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; + pa[k - 1]->tag[(int) a[k - 1]] = PLUS; + } + } + } + + return (void *) item; +} + +/* Inserts ITEM into TREE. Returns NULL if the item was inserted, + otherwise a pointer to the duplicate item. */ +void * +avlt_insert (avlt_tree *tree, void *item) +{ + void **p; + + assert (tree != NULL); + + p = avlt_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 * +avlt_replace (avlt_tree *tree, void *item) +{ + void **p; + + assert (tree != NULL); + + p = avlt_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 * +(avlt_force_delete) (avlt_tree *tree, void *item) +{ + void *found = avlt_delete (tree, item); + assert (found != NULL); + return found; +} + +#if SELF_TEST + +/* Size of the tree used for testing. */ +#define TREE_SIZE 1024 + +/* Used to flag delayed aborting. */ +int done = 0; + +/* Count the number of nodes in TREE below and including NODE. */ +int +count (avlt_tree *tree, avlt_node *node) +{ + int n = 1; + if (node->tag[0] == PLUS) + n += count (tree, node->link[0]); + if (node->tag[1] == PLUS) + n += count (tree, node->link[1]); + return n; +} + +/* 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 (avlt_tree *tree, avlt_node *node, int level) +{ + char lc[] = "([{<`"; + char rc[] = ")]}>'"; + + assert (node != NULL); + if (level >= 10) + { + printf ("Too deep, giving up.\n"); + done = 1; + return; + } + if (node == &tree->root) + { + printf (" root"); + return; + } + printf (" %c%d", lc[level % 5], (int) node->data); + fflush (stdout); + + { + int i; + + for (i = 0; i <= 1; i++) + { + if (node->tag[i] == PLUS) + print_structure (tree, node->link[i], level + 1); + else if (node->link[i] != &tree->root) + printf (" :%d", (int) node->link[i]->data); + else + printf (" :r"); + fflush (stdout); + } + } + printf ("%c", rc[level % 5]); + fflush (stdout); +} + +/* 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 (avlt_tree *tree) +{ + avlt_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 (avlt_tree *tree, avlt_node *node, int *count, int parent, + int dir, unsigned char *nodes, unsigned char *threads) +{ + if (node != &tree->root) + { + int d = (int) node->data; + int nl = 0; + int nr = 0; + + (*count)++; + + assert (d >= 0 && d < TREE_SIZE); + if (nodes[d / 8] & (1 << (d % 8))) + { + printf (" Arrived at node %d by two different paths.\n", d); + done = 1; + } + else + nodes[d / 8] |= 1 << (d % 8); + + if (node->tag[0] == PLUS) + nl = recurse_tree (tree, node->link[0], count, d, -1, nodes, threads); + else if (node->link[0] != &tree->root) + { + int dl = (int) node->link[0]->data; + assert (dl >= 0 && dl < TREE_SIZE); + threads[dl / 8] |= 1 << (dl % 8); + } + + if (node->tag[1] == PLUS) + nr = recurse_tree (tree, node->link[1], count, d, 1, nodes, threads); + else if (node->link[1] != &tree->root) + { + int dr = (int) node->link[1]->data; + assert (dr >= 0 && dr < TREE_SIZE); + threads[dr / 8] |= 1 << (dr % 8); + } + + if (nr - nl != node->bal) + { + printf (" Node %d has incorrect balance: right height=%d, " + "left height=%d, difference=%d, but balance factor=%d.\n", + d, nr, nl, nr - nl, node->bal); + done = 1; + } + + if (node->bal < -1 || node->bal > 1) + { + printf (" Node %d has invalid balance factor %d.\n", + d, 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 (avlt_tree *tree) +{ + { + unsigned char nodes[(TREE_SIZE + 7) / 8]; + unsigned char threads[(TREE_SIZE + 7) / 8]; + + int count = 0; + int i; + + memset (nodes, 0, (TREE_SIZE + 7) / 8); + memset (threads, 0, (TREE_SIZE + 7) / 8); + + recurse_tree (tree, tree->root.link[0], &count, INT_MIN, 0, nodes, + threads); + + if (count != tree->count) + { + printf (" Tree should have %d nodes, but tree count by recursive " + "descent is %d.\n", tree->count, count); + done = 1; + } + + for (i = 0; i < TREE_SIZE; i++) + { + int thread = threads[i / 8] & (1 << (i % 8)); + int node = nodes[i / 8] & (1 << (i % 8)); + + if (thread && !node) + { + printf (" A thread leads to ``node'' %d, which is " + "not in the tree.", i); + done = 1; + } + } + } + + /* Check right threads. */ + { + int count = 0; + int last = INT_MIN; + void **data = NULL; + + while (NULL != (data = avlt_next (tree, data))) + { + if (((int) *data) < last) + { + printf (" Misordered right threads.\n"); + abort (); + } + else if (((int) *data) == last) + { + printf (" Loop in right threads detected on %d.\n", last); + abort (); + } + last = (int) *data; + count++; + } + if (count != tree->count) + { + printf (" Tree should have %d nodes, but tree count by right threads " + "is %d.\n", tree->count, count); + done = 1; + } + } + + /* Check left threads. */ + { + int count = 0; + int last = INT_MAX; + void **data = NULL; + + while (NULL != (data = avlt_prev (tree, data))) + { + if (((int) *data) > last) + { + printf (" Misordered left threads.\n"); + abort (); + } + else if (((int) *data) == last) + { + printf (" Loop in left threads detected on %d.\n", last); + abort (); + } + last = (int) *data; + count++; + } + if (count != tree->count) + { + printf (" Tree should have %d nodes, but tree count by left threads " + "is %d.\n", tree->count, 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 (avlt_node *a, avlt_node *b) +{ + int diff = 0; + + assert (a && b); + + /* Separating these conditions makes it easier to pinpoint bad data + under a memory debugger like Checker because each test is a + separate statement. */ + diff |= a->data != b->data; + diff |= a->bal != b->bal; + diff |= ((a->tag[0] == PLUS) ^ (b->tag[0] == PLUS)); + diff |= ((a->tag[1] == PLUS) ^ (b->tag[1] == PLUS)); + if (diff) + { + 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->tag[0] == PLUS) + compare_trees (a->link[0], b->link[0]); + if (a->tag[1] == PLUS) + 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 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 avlt...\n", stdout); + + for (iteration = 1; iteration <= N_ITERATIONS; iteration++) + { + avlt_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 = avlt_create (compare_ints, NULL); + for (i = 0; i < TREE_SIZE; i++) + avlt_force_insert (tree, (void *) (array[i])); + verify_tree (tree); + + shuffle (array, TREE_SIZE); + for (i = 0; i < TREE_SIZE; i++) + { + avlt_tree *copy; + + avlt_delete (tree, (void *) (array[i])); + verify_tree (tree); + + copy = avlt_copy (tree, NULL); + verify_tree (copy); + if (tree->root.link[0] != &tree->root) + compare_trees (tree->root.link[0], copy->root.link[0]); + else if (copy->root.link[1] != ©->root) + printf (" Empty tree results in nonempty copy.\n"), abort (); + avlt_destroy (copy, NULL); + + if (i % 128 == 0) + { + putchar ('.'); + fflush (stdout); + } + } + fputs (" good.\n", stdout); + + avlt_destroy (tree, NULL); + } + + return 0; +} +#endif /* SELF_TEST */ + +/* + Local variables: + compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avlt-test avlt.c" + End: +*/ + |