1 /* libavl - manipulates AVL trees.
2 Copyright (C) 1998-9, 2000 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
19 The author may be contacted at <pfaffben@pilot.msu.edu> on the
20 Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
21 through more mundane means. */
23 /* This is file avl.c in libavl. */
30 #define HAVE_XMALLOC 1
47 #define unused __attribute__ ((unused))
54 void *xmalloc (size_t);
55 #else /* !HAVE_XMALLOC */
56 /* Allocates SIZE bytes of space using malloc(). Aborts if out of
70 fprintf (stderr, "virtual memory exhausted\n");
75 #endif /* !HAVE_XMALLOC */
77 /* Creates an AVL tree in POOL (which can be NULL). POOL is owned by
78 the caller, not by the AVL tree. CMP is a order function for the
79 data to be stored in the tree. PARAM is arbitrary data that
80 becomes an argument to the comparison function. */
82 avl_create (MAYBE_POOL avl_comparison_func cmp, void *param)
89 tree = pool_alloc (pool, sizeof *tree);
92 tree = xmalloc (sizeof *tree);
97 tree->root.link[0] = NULL;
98 tree->root.link[1] = NULL;
106 /* Destroy tree TREE. Function FREE_FUNC is called for every node in
107 the tree as it is destroyed.
109 No effect if the tree has an pool owner and free_func is NULL.
110 The caller owns the pool and must destroy it itself.
112 Do not attempt to reuse the tree after it has been freed. Create a
115 avl_destroy (avl_tree *tree, avl_node_func free_func)
117 assert (tree != NULL);
120 if (free_func || tree->pool == NULL)
123 /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
124 (postorder traversal). */
127 avl_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
128 char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */
129 int ap = 0; /* Stack A: height. */
130 avl_node *p = tree->root.link[0];
158 free_func (p->data, tree->param);
160 if (tree->pool == NULL)
169 if (tree->pool == NULL)
174 /* avl_destroy() with FREE_FUNC hardcoded as free(). */
176 avl_free (avl_tree *tree)
178 avl_destroy (tree, (avl_node_func) free);
181 /* Return the number of nodes in TREE. */
183 avl_count (const avl_tree *tree)
185 assert (tree != NULL);
189 /* Allocates room for a new avl_node in POOL, or using xmalloc() if
192 static inline avl_node *
193 new_node (struct pool *pool)
196 return pool_alloc (pool, sizeof (avl_node));
198 return xmalloc (sizeof (avl_node));
201 static inline avl_node *
204 return xmalloc (sizeof (avl_node));
207 #define new_node(POOL) \
211 /* Copy the contents of TREE to a new tree in POOL. If COPY is
212 non-NULL, then each data item is passed to function COPY, and the
213 return values are inserted into the new tree; otherwise, the items
214 are copied verbatim from the old tree to the new tree. Returns the
217 avl_copy (MAYBE_POOL const avl_tree *tree, avl_copy_func copy)
219 /* This is a combination of Knuth's Algorithm 2.3.1C (copying a
220 binary tree) and Algorithm 2.3.1T as modified by exercise 12
221 (preorder traversal). */
226 const avl_node *pa[AVL_MAX_HEIGHT]; /* Stack PA: nodes. */
227 const avl_node **pp = pa; /* Stack PA: stack pointer. */
228 const avl_node *p = &tree->root;
231 avl_node *qa[AVL_MAX_HEIGHT]; /* Stack QA: nodes. */
232 avl_node **qp = qa; /* Stack QA: stack pointer. */
235 assert (tree != NULL);
237 new_tree = avl_create (pool, tree->cmp, tree->param);
239 new_tree = avl_create (tree->cmp, tree->param);
241 new_tree->count = tree->count;
247 if (p->link[0] != NULL)
249 avl_node *r = new_node (pool);
250 r->link[0] = r->link[1] = NULL;
254 /* C5: Find preorder successors of P and Q. */
289 avl_node *r = new_node (pool);
290 r->link[0] = r->link[1] = NULL;
299 q->data = copy (p->data, tree->param);
303 /* Walk tree TREE in inorder, calling WALK_FUNC at each node. Passes
304 PARAM to WALK_FUNC. */
306 avl_walk (const avl_tree *tree, avl_node_func walk_func, void *param)
308 /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
309 assert (tree && walk_func);
313 const avl_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
314 const avl_node **ap = an; /* Stack A: stack pointer. */
315 const avl_node *p = tree->root.link[0];
333 walk_func (p->data, param);
339 /* Each call to this function for a given TREE and TRAV return the
340 next item in the tree in inorder. Initialize the first element of
341 TRAV (init) to 0 before calling the first time. Returns NULL when
344 avl_traverse (const avl_tree *tree, avl_traverser *trav)
346 assert (tree && trav);
348 /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
354 trav->p = tree->root.link[0];
358 trav->p = trav->p->link[1];
363 while (trav->p != NULL)
366 trav->stack[trav->nstack++] = trav->p;
367 trav->p = trav->p->link[0];
371 if (trav->nstack == 0)
376 trav->p = trav->stack[--trav->nstack];
379 return trav->p->data;
383 /* Search TREE for an item matching ITEM. If found, returns a pointer
384 to the address of the item. If none is found, ITEM is inserted
385 into the tree, and a pointer to the address of ITEM is returned.
386 In either case, the pointer returned can be changed by the caller,
387 or the returned data item can be directly edited, but the key data
388 in the item must not be changed. */
390 avl_probe (avl_tree *tree, void *item)
392 /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
393 insertion), but caches results of comparisons. In empirical
394 tests this eliminates about 25% of the comparisons seen under
395 random insertions. */
399 avl_node *s, *p, *q, *r;
401 assert (tree != NULL);
408 assert (tree->count == 1);
409 q = t->link[0] = new_node (tree->pool);
411 q->link[0] = q->link[1] = NULL;
419 int diff = tree->cmp (item, p->data, tree->param);
428 p->link[0] = q = new_node (tree->pool);
439 p->link[1] = q = new_node (tree->pool);
456 q->link[0] = q->link[1] = NULL;
460 r = p = s->link[(int) s->cache];
463 p->bal = p->cache * 2 - 1;
464 p = p->link[(int) p->cache];
476 else if (s->bal == +1)
482 assert (s->bal == -1);
487 s->link[0] = r->link[1];
494 assert (r->bal == +1);
496 r->link[1] = p->link[0];
498 s->link[0] = p->link[1];
501 s->bal = 1, r->bal = 0;
502 else if (p->bal == 0)
506 assert (p->bal == +1);
507 s->bal = 0, r->bal = -1;
520 else if (s->bal == -1)
526 assert (s->bal == +1);
531 s->link[1] = r->link[0];
538 assert (r->bal == -1);
540 r->link[0] = p->link[1];
542 s->link[1] = p->link[0];
545 s->bal = -1, r->bal = 0;
546 else if (p->bal == 0)
550 assert (p->bal == -1);
551 s->bal = 0, r->bal = 1;
558 if (t != &tree->root && s == t->link[1])
566 /* Search TREE for an item matching ITEM, and return it if found. */
568 avl_find (const avl_tree *tree, const void *item)
572 assert (tree != NULL);
573 for (p = tree->root.link[0]; p; )
575 int diff = tree->cmp (item, p->data, tree->param);
588 /* Searches AVL tree TREE for an item matching ITEM. If found, the
589 item is removed from the tree and the actual item found is returned
590 to the caller. If no item matching ITEM exists in the tree,
593 avl_delete (avl_tree *tree, const void *item)
595 /* Uses my Algorithm D, which can be found at
596 http://www.msu.edu/user/pfaffben/avl. Algorithm D is based on
597 Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced
598 tree search and insertion), as well as the notes on pages 465-466
602 avl_node *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */
603 char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */
604 int k = 1; /* Stack P: Pointer. */
609 assert (tree != NULL);
613 p = tree->root.link[0];
622 diff = tree->cmp (item, p->data, tree->param);
645 q = &pa[k - 1]->link[(int) a[k - 1]];
646 if (p->link[1] == NULL)
655 avl_node *r = p->link[1];
656 if (r->link[0] == NULL)
658 r->link[0] = p->link[0];
667 avl_node *s = r->link[0];
674 while (s->link[0] != NULL)
685 s->link[0] = p->link[0];
686 r->link[0] = s->link[1];
687 s->link[1] = p->link[1];
694 if (tree->pool == NULL)
702 avl_node *s = pa[k], *r;
712 else if (s->bal == 0)
718 assert (s->bal == +1);
725 s->link[1] = r->link[0];
728 pa[k - 1]->link[(int) a[k - 1]] = r;
731 else if (r->bal == +1)
734 s->link[1] = r->link[0];
737 pa[k - 1]->link[(int) a[k - 1]] = r;
742 assert (r->bal == -1);
744 r->link[0] = p->link[1];
746 s->link[1] = p->link[0];
749 s->bal = -1, r->bal = 0;
750 else if (p->bal == 0)
754 assert (p->bal == -1);
755 s->bal = 0, r->bal = +1;
758 pa[k - 1]->link[(int) a[k - 1]] = p;
771 else if (s->bal == 0)
777 assert (s->bal == -1);
780 if (r == NULL || r->bal == 0)
783 s->link[0] = r->link[1];
786 pa[k - 1]->link[(int) a[k - 1]] = r;
789 else if (r->bal == -1)
792 s->link[0] = r->link[1];
795 pa[k - 1]->link[(int) a[k - 1]] = r;
797 else if (r->bal == +1)
801 r->link[1] = p->link[0];
803 s->link[0] = p->link[1];
806 s->bal = 1, r->bal = 0;
807 else if (p->bal == 0)
811 assert (p->bal == 1);
812 s->bal = 0, r->bal = -1;
815 pa[k - 1]->link[(int) a[k - 1]] = p;
820 return (void *) item;
823 /* Inserts ITEM into TREE. Returns NULL if the item was inserted,
824 otherwise a pointer to the duplicate item. */
826 avl_insert (avl_tree *tree, void *item)
830 assert (tree != NULL);
832 p = avl_probe (tree, item);
833 return (*p == item) ? NULL : *p;
836 /* If ITEM does not exist in TREE, inserts it and returns NULL. If a
837 matching item does exist, it is replaced by ITEM and the item
838 replaced is returned. The caller is responsible for freeing the
841 avl_replace (avl_tree *tree, void *item)
845 assert (tree != NULL);
847 p = avl_probe (tree, item);
858 /* Delete ITEM from TREE when you know that ITEM must be in TREE. For
859 debugging purposes. */
861 (avl_force_delete) (avl_tree *tree, void *item)
863 void *found = avl_delete (tree, item);
864 assert (found != NULL);
870 /* Used to flag delayed aborting. */
873 /* Print the structure of node NODE of an avl tree, which is LEVEL
874 levels from the top of the tree. Uses different delimiters to
875 visually distinguish levels. */
877 print_structure (avl_node *node, int level)
880 char rc[] = ")]}'\\";
882 assert (level <= 10);
889 printf (" %c%d", lc[level % 5], (int) node->data);
890 if (node->link[0] || node->link[1])
891 print_structure (node->link[0], level + 1);
893 print_structure (node->link[1], level + 1);
894 printf ("%c", rc[level % 5]);
897 /* Compare two integers A and B and return a strcmp()-type result. */
899 compare_ints (const void *a, const void *b, void *param unused)
901 return ((int) a) - ((int) b);
904 /* Print the value of integer A. */
906 print_int (void *a, void *param unused)
908 printf (" %d", (int) a);
911 /* Linearly print contents of TREE. */
913 print_contents (avl_tree *tree)
915 avl_walk (tree, print_int, NULL);
919 /* Examine NODE in a avl tree. *COUNT is increased by the number of
920 nodes in the tree, including the current one. If the node is the
921 root of the tree, PARENT should be INT_MIN, otherwise it should be
922 the parent node value. DIR is the direction that the current node
923 is linked from the parent: -1 for left child, +1 for right child;
924 it is not used if PARENT is INT_MIN. Returns the height of the
925 tree rooted at NODE. */
927 recurse_tree (avl_node *node, int *count, int parent, int dir)
931 int d = (int) node->data;
932 int nl = node->link[0] ? recurse_tree (node->link[0], count, d, -1) : 0;
933 int nr = node->link[1] ? recurse_tree (node->link[1], count, d, 1) : 0;
936 if (nr - nl != node->bal)
938 printf (" Node %d is unbalanced: right height=%d, left height=%d, "
939 "difference=%d, but balance factor=%d.\n",
940 d, nr, nl, nr - nl, node->bal);
944 if (parent != INT_MIN)
946 assert (dir == -1 || dir == +1);
947 if (dir == -1 && d > parent)
949 printf (" Node %d is smaller than its left child %d.\n",
953 else if (dir == +1 && d < parent)
955 printf (" Node %d is larger than its right child %d.\n",
960 assert (node->bal >= -1 && node->bal <= 1);
961 return 1 + (nl > nr ? nl : nr);
966 /* Check that everything about TREE is kosher. */
968 verify_tree (avl_tree *tree)
971 recurse_tree (tree->root.link[0], &count, INT_MIN, 0);
972 if (count != tree->count)
974 printf (" Tree has %d nodes, but tree count is %d.\n",
982 /* Arrange the N elements of ARRAY in random order. */
984 shuffle (int *array, int n)
988 for (i = 0; i < n; i++)
990 int j = i + rand () % (n - i);
997 /* Compares avl trees rooted at A and B, making sure that they are
1000 compare_trees (avl_node *a, avl_node *b)
1002 if (a == NULL || b == NULL)
1004 assert (a == NULL && b == NULL);
1007 if (a->data != b->data || a->bal != b->bal
1008 || ((a->link[0] != NULL) ^ (b->link[0] != NULL))
1009 || ((a->link[1] != NULL) ^ (b->link[1] != NULL)))
1011 printf (" Copied nodes differ: %d b=%d a->bal=%d b->bal=%d a:",
1012 (int) a->data, (int) b->data, a->bal, b->bal);
1025 if (a->link[0] != NULL)
1026 compare_trees (a->link[0], b->link[0]);
1027 if (a->link[1] != NULL)
1028 compare_trees (a->link[1], b->link[1]);
1031 /* Simple stress test procedure for the AVL tree routines. Does the
1034 * Generate a random number seed. By default this is generated from
1035 the current time. You can also pass a seed value on the command
1036 line if you want to test the same case. The seed value is
1039 * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
1040 into it, in random order. Verify the tree structure after each
1043 * Remove each integer from the tree, in a different random order.
1044 After each deletion, verify the tree structure; also, make a copy
1045 of the tree into a new tree, verify the copy and compare it to the
1046 original, then destroy the copy.
1048 * Destroy the tree, increment the random seed value, and start over.
1050 If you make any modifications to the avl tree routines, then you
1051 might want to insert some calls to print_structure() at strategic
1052 places in order to be able to see what's really going on. Also,
1053 memory debuggers like Checker or Purify are very handy. */
1054 #define TREE_SIZE 1024
1055 #define N_ITERATIONS 16
1057 main (int argc, char **argv)
1059 int array[TREE_SIZE];
1064 seed = atoi (argv[1]);
1066 seed = time (0) * 257 % 32768;
1068 fputs ("Testing avl...\n", stdout);
1070 for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
1075 printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
1080 for (i = 0; i < TREE_SIZE; i++)
1082 shuffle (array, TREE_SIZE);
1084 tree = avl_create (compare_ints, NULL);
1085 for (i = 0; i < TREE_SIZE; i++)
1086 avl_force_insert (tree, (void *) (array[i]));
1089 shuffle (array, TREE_SIZE);
1090 for (i = 0; i < TREE_SIZE; i++)
1094 avl_delete (tree, (void *) (array[i]));
1097 copy = avl_copy (tree, NULL);
1099 compare_trees (tree->root.link[0], copy->root.link[0]);
1100 avl_destroy (copy, NULL);
1108 fputs (" good.\n", stdout);
1110 avl_destroy (tree, NULL);
1115 #endif /* SELF_TEST */
1119 compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avl-test avl.c"