/* * 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 #include #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