abc/src/misc/avl/avl.c - third_party/vtr-verilog-to-routing - Git at Google

 /*
  * Revision Control Information
  *
  * $Source: /vol/opua/opua2/sis/sis-1.2/common/src/sis/avl/RCS/avl.c,v $
  * $Author: sis $
  * $Revision: 1.3 $
  * $Date: 1994/07/15 23:00:40 $
  *
  */
 /* LINTLIBRARY */


 #include <stdio.h>
 #include <stdlib.h>

 #include "avl.h"

 ABC_NAMESPACE_IMPL_START


 #define HEIGHT(node) (node == NIL(avl_node) ? -1 : (node)->height)
 #define BALANCE(node) (HEIGHT((node)->right) - HEIGHT((node)->left))

 #define compute_height(node) {                \
     int x=HEIGHT(node->left), y=HEIGHT(node->right);    \
     (node)->height = MAX(x,y) + 1;            \
 }

 #define COMPARE(key, nodekey, compare)             \
     ((compare == avl_numcmp) ?                 \
     (int) key - (int) nodekey :             \
     (*compare)(key, nodekey))


 #define STACK_SIZE    50

 static avl_node *new_node ();
 static avl_node *find_rightmost ();
 static void do_rebalance ();
 static rotate_left ();
 static rotate_right ();
 static int do_check_tree ();

 avl_tree *
 avl_init_table (compar)
  int (*compar) ();
 {
     avl_tree *tree;

     tree = ALLOC (avl_tree, 1);
     tree->root = NIL (avl_node);
     tree->compar = compar;
     tree->num_entries = 0;
     return tree;
 }


 avl_lookup (tree, key, value_p)
  avl_tree *tree;
  register char *key;
  char **value_p;
 {
     register avl_node *node;
     register int (*compare) () = tree->compar, diff;

     node = tree->root;
     while (node != NIL (avl_node))
     {
         diff = COMPARE (key, node->key, compare);
         if (diff == 0)
         {
             /* got a match */
             if (value_p != NIL (char *))
                  *value_p = node->value;
             return 1;
         }
         node = (diff < 0) ? node->left : node->right;
     }
     return 0;
 }

 avl_first (tree, key_p, value_p)
  avl_tree *tree;
  char **key_p;
  char **value_p;
 {
     register avl_node *node;

     if (tree->root == 0)
     {
         return 0;                /* no entries */
     }
     else
     {
         /* walk down the tree; stop at leftmost leaf */
         for (node = tree->root; node->left != 0; node = node->left)
         {
         }
         if (key_p != NIL (char *))
              *key_p = node->key;
         if (value_p != NIL (char *))
              *value_p = node->value;
         return 1;
     }
 }


 avl_last (tree, key_p, value_p)
  avl_tree *tree;
  char **key_p;
  char **value_p;
 {
     register avl_node *node;

     if (tree->root == 0)
     {
         return 0;                /* no entries */
     }
     else
     {
         /* walk down the tree; stop at rightmost leaf */
         for (node = tree->root; node->right != 0; node = node->right)
         {
         }
         if (key_p != NIL (char *))
              *key_p = node->key;
         if (value_p != NIL (char *))
              *value_p = node->value;
         return 1;
     }
 }

 avl_insert (tree, key, value)
  avl_tree *tree;
  char *key;
  char *value;
 {
     register avl_node **node_p, *node;
     register int stack_n = 0;
     register int (*compare) () = tree->compar;
     avl_node **stack_nodep[STACK_SIZE];
     int diff, status;

     node_p = &tree->root;

     /* walk down the tree (saving the path); stop at insertion point */
     status = 0;
     while ((node = *node_p) != NIL (avl_node))
     {
         stack_nodep[stack_n++] = node_p;
         diff = COMPARE (key, node->key, compare);
         if (diff == 0)
             status = 1;
         node_p = (diff < 0) ? &node->left : &node->right;
     }

     /* insert the item and re-balance the tree */
     *node_p = new_node (key, value);
     do_rebalance (stack_nodep, stack_n);
     tree->num_entries++;
     tree->modified = 1;
     return status;
 }


 avl_find_or_add (tree, key, slot_p)
  avl_tree *tree;
  char *key;
  char ***slot_p;
 {
     register avl_node **node_p, *node;
     register int stack_n = 0;
     register int (*compare) () = tree->compar;
     avl_node **stack_nodep[STACK_SIZE];
     int diff;

     node_p = &tree->root;

     /* walk down the tree (saving the path); stop at insertion point */
     while ((node = *node_p) != NIL (avl_node))
     {
         stack_nodep[stack_n++] = node_p;
         diff = COMPARE (key, node->key, compare);
         if (diff == 0)
         {
             if (slot_p != 0)
                 *slot_p = &node->value;
             return 1;            /* found */
         }
         node_p = (diff < 0) ? &node->left : &node->right;
     }

     /* insert the item and re-balance the tree */
     *node_p = new_node (key, NIL (char));
     if (slot_p != 0)
         *slot_p = &(*node_p)->value;
     do_rebalance (stack_nodep, stack_n);
     tree->num_entries++;
     tree->modified = 1;
     return 0;                    /* not already in tree */
 }

 avl_delete (tree, key_p, value_p)
  avl_tree *tree;
  char **key_p;
  char **value_p;
 {
     register avl_node **node_p, *node, *rightmost;
     register int stack_n = 0;
     char *key = *key_p;
     int (*compare) () = tree->compar, diff;
     avl_node **stack_nodep[STACK_SIZE];

     node_p = &tree->root;

     /* Walk down the tree saving the path; return if not found */
     while ((node = *node_p) != NIL (avl_node))
     {
         diff = COMPARE (key, node->key, compare);
         if (diff == 0)
             goto delete_item;
         stack_nodep[stack_n++] = node_p;
         node_p = (diff < 0) ? &node->left : &node->right;
     }
     return 0;                    /* not found */

     /* prepare to delete node and replace it with rightmost of left tree */
   delete_item:
     *key_p = node->key;
     if (value_p != 0)
         *value_p = node->value;
     if (node->left == NIL (avl_node))
     {
         *node_p = node->right;
     }
     else
     {
         rightmost = find_rightmost (&node->left);
         rightmost->left = node->left;
         rightmost->right = node->right;
         rightmost->height = -2;    /* mark bogus height for do_rebal */
         *node_p = rightmost;
         stack_nodep[stack_n++] = node_p;
     }
     FREE (node);

     /* work our way back up, re-balancing the tree */
     do_rebalance (stack_nodep, stack_n);
     tree->num_entries--;
     tree->modified = 1;
     return 1;
 }

 static void
 avl_record_gen_forward (node, gen)
  avl_node *node;
  avl_generator *gen;
 {
     if (node != NIL (avl_node))
     {
         avl_record_gen_forward (node->left, gen);
         gen->nodelist[gen->count++] = node;
         avl_record_gen_forward (node->right, gen);
     }
 }


 static void
 avl_record_gen_backward (node, gen)
  avl_node *node;
  avl_generator *gen;
 {
     if (node != NIL (avl_node))
     {
         avl_record_gen_backward (node->right, gen);
         gen->nodelist[gen->count++] = node;
         avl_record_gen_backward (node->left, gen);
     }
 }


 avl_generator *
 avl_init_gen (tree, dir)
  avl_tree *tree;
  int dir;
 {
     avl_generator *gen;

     /* what a hack */
     gen = ALLOC (avl_generator, 1);
     gen->tree = tree;
     gen->nodelist = ALLOC (avl_node *, avl_count (tree));
     gen->count = 0;
     if (dir == AVL_FORWARD)
     {
         avl_record_gen_forward (tree->root, gen);
     }
     else
     {
         avl_record_gen_backward (tree->root, gen);
     }
     gen->count = 0;

     /* catch any attempt to modify the tree while we generate */
     tree->modified = 0;
     return gen;
 }


 avl_gen (gen, key_p, value_p)
  avl_generator *gen;
  char **key_p;
  char **value_p;
 {
     avl_node *node;

     if (gen->count == gen->tree->num_entries)
     {
         return 0;
     }
     else
     {
         node = gen->nodelist[gen->count++];
         if (key_p != NIL (char *))
              *key_p = node->key;
         if (value_p != NIL (char *))
              *value_p = node->value;
         return 1;
     }
 }


 void
 avl_free_gen (gen)
  avl_generator *gen;
 {
     FREE (gen->nodelist);
     FREE (gen);
 }

 static avl_node *
 find_rightmost (node_p)
  register avl_node **node_p;
 {
     register avl_node *node;
     register int stack_n = 0;
     avl_node **stack_nodep[STACK_SIZE];

     node = *node_p;
     while (node->right != NIL (avl_node))
     {
         stack_nodep[stack_n++] = node_p;
         node_p = &node->right;
         node = *node_p;
     }
     *node_p = node->left;

     do_rebalance (stack_nodep, stack_n);
     return node;
 }


 static void
 do_rebalance (stack_nodep, stack_n)
  register avl_node ***stack_nodep;
  register int stack_n;
 {
     register avl_node **node_p, *node;
     register int hl, hr;
     int height;

     /* work our way back up, re-balancing the tree */
     while (--stack_n >= 0)
     {
         node_p = stack_nodep[stack_n];
         node = *node_p;
         hl = HEIGHT (node->left);    /* watch for NIL */
         hr = HEIGHT (node->right);    /* watch for NIL */
         if ((hr - hl) < -1)
         {
             rotate_right (node_p);
         }
         else if ((hr - hl) > 1)
         {
             rotate_left (node_p);
         }
         else
         {
             height = MAX (hl, hr) + 1;
             if (height == node->height)
                 break;
             node->height = height;
         }
     }
 }

 static
 rotate_left (node_p)
  register avl_node **node_p;
 {
     register avl_node *old_root = *node_p, *new_root, *new_right;

     if (BALANCE (old_root->right) >= 0)
     {
         *node_p = new_root = old_root->right;
         old_root->right = new_root->left;
         new_root->left = old_root;
     }
     else
     {
         new_right = old_root->right;
         *node_p = new_root = new_right->left;
         old_root->right = new_root->left;
         new_right->left = new_root->right;
         new_root->right = new_right;
         new_root->left = old_root;
         compute_height (new_right);
     }
     compute_height (old_root);
     compute_height (new_root);
 }


 static
 rotate_right (node_p)
  avl_node **node_p;
 {
     register avl_node *old_root = *node_p, *new_root, *new_left;

     if (BALANCE (old_root->left) <= 0)
     {
         *node_p = new_root = old_root->left;
         old_root->left = new_root->right;
         new_root->right = old_root;
     }
     else
     {
         new_left = old_root->left;
         *node_p = new_root = new_left->right;
         old_root->left = new_root->right;
         new_left->right = new_root->left;
         new_root->left = new_left;
         new_root->right = old_root;
         compute_height (new_left);
     }
     compute_height (old_root);
     compute_height (new_root);
 }

 static void
 avl_walk_forward (node, func)
  avl_node *node;
  void (*func) ();
 {
     if (node != NIL (avl_node))
     {
         avl_walk_forward (node->left, func);
         (*func) (node->key, node->value);
         avl_walk_forward (node->right, func);
     }
 }


 static void
 avl_walk_backward (node, func)
  avl_node *node;
  void (*func) ();
 {
     if (node != NIL (avl_node))
     {
         avl_walk_backward (node->right, func);
         (*func) (node->key, node->value);
         avl_walk_backward (node->left, func);
     }
 }


 void
 avl_foreach (tree, func, direction)
  avl_tree *tree;
  void (*func) ();
  int direction;
 {
     if (direction == AVL_FORWARD)
     {
         avl_walk_forward (tree->root, func);
     }
     else
     {
         avl_walk_backward (tree->root, func);
     }
 }


 static void
 free_entry (node, key_free, value_free)
  avl_node *node;
  void (*key_free) ();
  void (*value_free) ();
 {
     if (node != NIL (avl_node))
     {
         free_entry (node->left, key_free, value_free);
         free_entry (node->right, key_free, value_free);
         if (key_free != 0)
             (*key_free) (node->key);
         if (value_free != 0)
             (*value_free) (node->value);
         FREE (node);
     }
 }


 void
 avl_free_table (tree, key_free, value_free)
  avl_tree *tree;
  void (*key_free) ();
  void (*value_free) ();
 {
     free_entry (tree->root, key_free, value_free);
     FREE (tree);
 }


 int
 avl_count (tree)
  avl_tree *tree;
 {
     return tree->num_entries;
 }

 static avl_node *
 new_node (key, value)
  char *key;
  char *value;
 {
     register avl_node *new;

     new = ALLOC (avl_node, 1);
     new->key = key;
     new->value = value;
     new->height = 0;
     new->left = new->right = NIL (avl_node);
     return new;
 }


 int
 avl_numcmp (x, y)
  char *x, *y;
 {
     return (int) x - (int) y;
 }

 int
 avl_check_tree (tree)
  avl_tree *tree;
 {
     int error = 0;
     (void) do_check_tree (tree->root, tree->compar, &error);
     return error;
 }


 static int
 do_check_tree (node, compar, error)
  avl_node *node;
  int (*compar) ();
  int *error;
 {
     int l_height, r_height, comp_height, bal;

     if (node == NIL (avl_node))
     {
         return -1;
     }

     r_height = do_check_tree (node->right, compar, error);
     l_height = do_check_tree (node->left, compar, error);

     comp_height = MAX (l_height, r_height) + 1;
     bal = r_height - l_height;

     if (comp_height != node->height)
     {
         (void) printf ("Bad height for 0x%08x: computed=%d stored=%d\n",
                        node, comp_height, node->height);
         ++*error;
     }

     if (bal > 1 || bal < -1)
     {
         (void) printf ("Out of balance at node 0x%08x, balance = %d\n",
                        node, bal);
         ++*error;
     }

     if (node->left != NIL (avl_node) &&
         (*compar) (node->left->key, node->key) > 0)
     {
         (void) printf ("Bad ordering between 0x%08x and 0x%08x",
                        node, node->left);
         ++*error;
     }

     if (node->right != NIL (avl_node) &&
         (*compar) (node->key, node->right->key) > 0)
     {
         (void) printf ("Bad ordering between 0x%08x and 0x%08x",
                        node, node->right);
         ++*error;
     }

     return comp_height;
 }
 ABC_NAMESPACE_IMPL_END
	/*
	* Revision Control Information
	*
	* $Source: /vol/opua/opua2/sis/sis-1.2/common/src/sis/avl/RCS/avl.c,v $
	* $Author: sis $
	* $Revision: 1.3 $
	* $Date: 1994/07/15 23:00:40 $
	*
	*/
	/* LINTLIBRARY */


	#include <stdio.h>
	#include <stdlib.h>

	#include "avl.h"

	ABC_NAMESPACE_IMPL_START




	#define HEIGHT(node) (node == NIL(avl_node) ? -1 : (node)->height)
	#define BALANCE(node) (HEIGHT((node)->right) - HEIGHT((node)->left))

	#define compute_height(node) { \
	int x=HEIGHT(node->left), y=HEIGHT(node->right); \
	(node)->height = MAX(x,y) + 1; \
	}

	#define COMPARE(key, nodekey, compare) \
	((compare == avl_numcmp) ? \
	(int) key - (int) nodekey : \
	(*compare)(key, nodekey))


	#define STACK_SIZE 50

	static avl_node *new_node ();
	static avl_node *find_rightmost ();
	static void do_rebalance ();
	static rotate_left ();
	static rotate_right ();
	static int do_check_tree ();

	avl_tree *
	avl_init_table (compar)
	int (*compar) ();
	{
	avl_tree *tree;

	tree = ALLOC (avl_tree, 1);
	tree->root = NIL (avl_node);
	tree->compar = compar;
	tree->num_entries = 0;
	return tree;
	}



	avl_lookup (tree, key, value_p)
	avl_tree *tree;
	register char *key;
	char **value_p;
	{
	register avl_node *node;
	register int (*compare) () = tree->compar, diff;

	node = tree->root;
	while (node != NIL (avl_node))
	{
	diff = COMPARE (key, node->key, compare);
	if (diff == 0)
	{
	/* got a match */
	if (value_p != NIL (char *))
	*value_p = node->value;
	return 1;
	}
	node = (diff < 0) ? node->left : node->right;
	}
	return 0;
	}

	avl_first (tree, key_p, value_p)
	avl_tree *tree;
	char **key_p;
	char **value_p;
	{
	register avl_node *node;

	if (tree->root == 0)
	{
	return 0; /* no entries */
	}
	else
	{
	/* walk down the tree; stop at leftmost leaf */
	for (node = tree->root; node->left != 0; node = node->left)
	{
	}
	if (key_p != NIL (char *))
	*key_p = node->key;
	if (value_p != NIL (char *))
	*value_p = node->value;
	return 1;
	}
	}


	avl_last (tree, key_p, value_p)
	avl_tree *tree;
	char **key_p;
	char **value_p;
	{
	register avl_node *node;

	if (tree->root == 0)
	{
	return 0; /* no entries */
	}
	else
	{
	/* walk down the tree; stop at rightmost leaf */
	for (node = tree->root; node->right != 0; node = node->right)
	{
	}
	if (key_p != NIL (char *))
	*key_p = node->key;
	if (value_p != NIL (char *))
	*value_p = node->value;
	return 1;
	}
	}

	avl_insert (tree, key, value)
	avl_tree *tree;
	char *key;
	char *value;
	{
	register avl_node *node_p, node;
	register int stack_n = 0;
	register int (*compare) () = tree->compar;
	avl_node **stack_nodep[STACK_SIZE];
	int diff, status;

	node_p = &tree->root;

	/* walk down the tree (saving the path); stop at insertion point */
	status = 0;
	while ((node = *node_p) != NIL (avl_node))
	{
	stack_nodep[stack_n++] = node_p;
	diff = COMPARE (key, node->key, compare);
	if (diff == 0)
	status = 1;
	node_p = (diff < 0) ? &node->left : &node->right;
	}

	/* insert the item and re-balance the tree */
	*node_p = new_node (key, value);
	do_rebalance (stack_nodep, stack_n);
	tree->num_entries++;
	tree->modified = 1;
	return status;
	}



	avl_find_or_add (tree, key, slot_p)
	avl_tree *tree;
	char *key;
	char ***slot_p;
	{
	register avl_node *node_p, node;
	register int stack_n = 0;
	register int (*compare) () = tree->compar;
	avl_node **stack_nodep[STACK_SIZE];
	int diff;

	node_p = &tree->root;

	/* walk down the tree (saving the path); stop at insertion point */
	while ((node = *node_p) != NIL (avl_node))
	{
	stack_nodep[stack_n++] = node_p;
	diff = COMPARE (key, node->key, compare);
	if (diff == 0)
	{
	if (slot_p != 0)
	*slot_p = &node->value;
	return 1; /* found */
	}
	node_p = (diff < 0) ? &node->left : &node->right;
	}

	/* insert the item and re-balance the tree */
	*node_p = new_node (key, NIL (char));
	if (slot_p != 0)
	slot_p = &(node_p)->value;
	do_rebalance (stack_nodep, stack_n);
	tree->num_entries++;
	tree->modified = 1;
	return 0; /* not already in tree */
	}

	avl_delete (tree, key_p, value_p)
	avl_tree *tree;
	char **key_p;
	char **value_p;
	{
	register avl_node *node_p, node, *rightmost;
	register int stack_n = 0;
	char key = key_p;
	int (*compare) () = tree->compar, diff;
	avl_node **stack_nodep[STACK_SIZE];

	node_p = &tree->root;

	/* Walk down the tree saving the path; return if not found */
	while ((node = *node_p) != NIL (avl_node))
	{
	diff = COMPARE (key, node->key, compare);
	if (diff == 0)
	goto delete_item;
	stack_nodep[stack_n++] = node_p;
	node_p = (diff < 0) ? &node->left : &node->right;
	}
	return 0; /* not found */

	/* prepare to delete node and replace it with rightmost of left tree */
	delete_item:
	*key_p = node->key;
	if (value_p != 0)
	*value_p = node->value;
	if (node->left == NIL (avl_node))
	{
	*node_p = node->right;
	}
	else
	{
	rightmost = find_rightmost (&node->left);
	rightmost->left = node->left;
	rightmost->right = node->right;
	rightmost->height = -2; /* mark bogus height for do_rebal */
	*node_p = rightmost;
	stack_nodep[stack_n++] = node_p;
	}
	FREE (node);

	/* work our way back up, re-balancing the tree */
	do_rebalance (stack_nodep, stack_n);
	tree->num_entries--;
	tree->modified = 1;
	return 1;
	}

	static void
	avl_record_gen_forward (node, gen)
	avl_node *node;
	avl_generator *gen;
	{
	if (node != NIL (avl_node))
	{
	avl_record_gen_forward (node->left, gen);
	gen->nodelist[gen->count++] = node;
	avl_record_gen_forward (node->right, gen);
	}
	}


	static void
	avl_record_gen_backward (node, gen)
	avl_node *node;
	avl_generator *gen;
	{
	if (node != NIL (avl_node))
	{
	avl_record_gen_backward (node->right, gen);
	gen->nodelist[gen->count++] = node;
	avl_record_gen_backward (node->left, gen);
	}
	}


	avl_generator *
	avl_init_gen (tree, dir)
	avl_tree *tree;
	int dir;
	{
	avl_generator *gen;

	/* what a hack */
	gen = ALLOC (avl_generator, 1);
	gen->tree = tree;
	gen->nodelist = ALLOC (avl_node *, avl_count (tree));
	gen->count = 0;
	if (dir == AVL_FORWARD)
	{
	avl_record_gen_forward (tree->root, gen);
	}
	else
	{
	avl_record_gen_backward (tree->root, gen);
	}
	gen->count = 0;

	/* catch any attempt to modify the tree while we generate */
	tree->modified = 0;
	return gen;
	}


	avl_gen (gen, key_p, value_p)
	avl_generator *gen;
	char **key_p;
	char **value_p;
	{
	avl_node *node;

	if (gen->count == gen->tree->num_entries)
	{
	return 0;
	}
	else
	{
	node = gen->nodelist[gen->count++];
	if (key_p != NIL (char *))
	*key_p = node->key;
	if (value_p != NIL (char *))
	*value_p = node->value;
	return 1;
	}
	}


	void
	avl_free_gen (gen)
	avl_generator *gen;
	{
	FREE (gen->nodelist);
	FREE (gen);
	}

	static avl_node *
	find_rightmost (node_p)
	register avl_node **node_p;
	{
	register avl_node *node;
	register int stack_n = 0;
	avl_node **stack_nodep[STACK_SIZE];

	node = *node_p;
	while (node->right != NIL (avl_node))
	{
	stack_nodep[stack_n++] = node_p;
	node_p = &node->right;
	node = *node_p;
	}
	*node_p = node->left;

	do_rebalance (stack_nodep, stack_n);
	return node;
	}


	static void
	do_rebalance (stack_nodep, stack_n)
	register avl_node ***stack_nodep;
	register int stack_n;
	{
	register avl_node *node_p, node;
	register int hl, hr;
	int height;

	/* work our way back up, re-balancing the tree */
	while (--stack_n >= 0)
	{
	node_p = stack_nodep[stack_n];
	node = *node_p;
	hl = HEIGHT (node->left); /* watch for NIL */
	hr = HEIGHT (node->right); /* watch for NIL */
	if ((hr - hl) < -1)
	{
	rotate_right (node_p);
	}
	else if ((hr - hl) > 1)
	{
	rotate_left (node_p);
	}
	else
	{
	height = MAX (hl, hr) + 1;
	if (height == node->height)
	break;
	node->height = height;
	}
	}
	}

	static
	rotate_left (node_p)
	register avl_node **node_p;
	{
	register avl_node old_root = node_p, new_root, new_right;

	if (BALANCE (old_root->right) >= 0)
	{
	*node_p = new_root = old_root->right;
	old_root->right = new_root->left;
	new_root->left = old_root;
	}
	else
	{
	new_right = old_root->right;
	*node_p = new_root = new_right->left;
	old_root->right = new_root->left;
	new_right->left = new_root->right;
	new_root->right = new_right;
	new_root->left = old_root;
	compute_height (new_right);
	}
	compute_height (old_root);
	compute_height (new_root);
	}


	static
	rotate_right (node_p)
	avl_node **node_p;
	{
	register avl_node old_root = node_p, new_root, new_left;

	if (BALANCE (old_root->left) <= 0)
	{
	*node_p = new_root = old_root->left;
	old_root->left = new_root->right;
	new_root->right = old_root;
	}
	else
	{
	new_left = old_root->left;
	*node_p = new_root = new_left->right;
	old_root->left = new_root->right;
	new_left->right = new_root->left;
	new_root->left = new_left;
	new_root->right = old_root;
	compute_height (new_left);
	}
	compute_height (old_root);
	compute_height (new_root);
	}

	static void
	avl_walk_forward (node, func)
	avl_node *node;
	void (*func) ();
	{
	if (node != NIL (avl_node))
	{
	avl_walk_forward (node->left, func);
	(*func) (node->key, node->value);
	avl_walk_forward (node->right, func);
	}
	}


	static void
	avl_walk_backward (node, func)
	avl_node *node;
	void (*func) ();
	{
	if (node != NIL (avl_node))
	{
	avl_walk_backward (node->right, func);
	(*func) (node->key, node->value);
	avl_walk_backward (node->left, func);
	}
	}


	void
	avl_foreach (tree, func, direction)
	avl_tree *tree;
	void (*func) ();
	int direction;
	{
	if (direction == AVL_FORWARD)
	{
	avl_walk_forward (tree->root, func);
	}
	else
	{
	avl_walk_backward (tree->root, func);
	}
	}


	static void
	free_entry (node, key_free, value_free)
	avl_node *node;
	void (*key_free) ();
	void (*value_free) ();
	{
	if (node != NIL (avl_node))
	{
	free_entry (node->left, key_free, value_free);
	free_entry (node->right, key_free, value_free);
	if (key_free != 0)
	(*key_free) (node->key);
	if (value_free != 0)
	(*value_free) (node->value);
	FREE (node);
	}
	}


	void
	avl_free_table (tree, key_free, value_free)
	avl_tree *tree;
	void (*key_free) ();
	void (*value_free) ();
	{
	free_entry (tree->root, key_free, value_free);
	FREE (tree);
	}


	int
	avl_count (tree)
	avl_tree *tree;
	{
	return tree->num_entries;
	}

	static avl_node *
	new_node (key, value)
	char *key;
	char *value;
	{
	register avl_node *new;

	new = ALLOC (avl_node, 1);
	new->key = key;
	new->value = value;
	new->height = 0;
	new->left = new->right = NIL (avl_node);
	return new;
	}


	int
	avl_numcmp (x, y)
	char x, y;
	{
	return (int) x - (int) y;
	}

	int
	avl_check_tree (tree)
	avl_tree *tree;
	{
	int error = 0;
	(void) do_check_tree (tree->root, tree->compar, &error);
	return error;
	}


	static int
	do_check_tree (node, compar, error)
	avl_node *node;
	int (*compar) ();
	int *error;
	{
	int l_height, r_height, comp_height, bal;

	if (node == NIL (avl_node))
	{
	return -1;
	}

	r_height = do_check_tree (node->right, compar, error);
	l_height = do_check_tree (node->left, compar, error);

	comp_height = MAX (l_height, r_height) + 1;
	bal = r_height - l_height;

	if (comp_height != node->height)
	{
	(void) printf ("Bad height for 0x%08x: computed=%d stored=%d\n",
	node, comp_height, node->height);
	++*error;
	}

	if (bal > 1 \|\| bal < -1)
	{
	(void) printf ("Out of balance at node 0x%08x, balance = %d\n",
	node, bal);
	++*error;
	}

	if (node->left != NIL (avl_node) &&
	(*compar) (node->left->key, node->key) > 0)
	{
	(void) printf ("Bad ordering between 0x%08x and 0x%08x",
	node, node->left);
	++*error;
	}

	if (node->right != NIL (avl_node) &&
	(*compar) (node->key, node->right->key) > 0)
	{
	(void) printf ("Bad ordering between 0x%08x and 0x%08x",
	node, node->right);
	++*error;
	}

	return comp_height;
	}
	ABC_NAMESPACE_IMPL_END