From f936cc0680c98ffe51b3a1716c996072d5dbf76c Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 18 Jan 2009 08:01:00 -0800 Subject: Version abc90118 --- src/misc/avl/avl.c | 616 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/misc/avl/avl.doc | 166 ++++++++++++++ src/misc/avl/avl.h | 80 +++++++ 3 files changed, 862 insertions(+) create mode 100644 src/misc/avl/avl.c create mode 100644 src/misc/avl/avl.doc create mode 100644 src/misc/avl/avl.h (limited to 'src/misc/avl') diff --git a/src/misc/avl/avl.c b/src/misc/avl/avl.c new file mode 100644 index 00000000..2c2dec88 --- /dev/null +++ b/src/misc/avl/avl.c @@ -0,0 +1,616 @@ +/* + * 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" + + + +#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; +} diff --git a/src/misc/avl/avl.doc b/src/misc/avl/avl.doc new file mode 100644 index 00000000..a9753b3a --- /dev/null +++ b/src/misc/avl/avl.doc @@ -0,0 +1,166 @@ +/* + * Revision Control Information + * + * /projects/hsis/CVS/utilities/avl/avl.doc,v + * rajeev + * 1.3 + * 1995/08/08 22:36:22 + * + */ +avl_tree * +avl_init_table(compare) +int (*compare)(); + Initialize and return a new avl_tree. Use the function `compare' to + compare items in the tree. `compare' should be of the form: + + int + compare(a,b) + char *a, *b; + + and return a number < 0, == 0, > 0 depending on whether a < b, + a == b, or a > b, respectively. + + +void +avl_free_table(tree, key_delete_func, value_delete_func) +avl_tree *tree; +void (*key_delete_func)(); +void (*value_delete_func)(); + + Delete all storage associated with `tree'. The functions + key_delete_func and value_delete_func, if non-null, are called + to free each (key, value) pair. They are declared as: + + void + key_delete_func(key) + char *key; + {} + + void + value_delete_func(value) + char *value; + {} + + The C-library function free is often suitable as a free function. + + +avl_first(tree, key_p, value_p) +avl_tree *tree; +char **key_p; +char **value_p; + Retrieves the smallest element in the tree. Returns 0 if there + are no elements in the tree. + + +avl_last(tree, key_p, value_p) +avl_tree *tree; +char **key_p; +char **value_p; + Retrieves the largest element in the tree. Returns 0 if there + are no elements in the tree. + + +avl_lookup(tree, key, value_p) +avl_tree *tree; +char *key; +char **value_p; + Search for an entry matching `key'. If found, set `value_p' to + the associated value field and return 1. If not found, return + 0 and leave `value_p' unchanged. + + +avl_insert(tree, key, value); +avl_tree *tree; +char *key; +char *value; + Insert the value `value' under the key `key'. Multiple items + are allowed with the same value; all are inserted. + + +avl_delete(tree, key_p, value_p) +avl_tree *tree; +char **key_p; +char **value_p; + Search for the item with key `*key_p' in `tree'. If found, set + `key_p' and `value_p' to point to the key and value of item, + delete the item and return 1. Otherwise return 0 and leave + `key_p' and `value_p' unchanged. WARNING: This interface is + buggy; in particular, if identical keys are in the table, it is + not possible to delete a particular (key, value) pair. This + will be fixed either with 'handles' or a separate delete + function. + + +avl_find_or_add(tree, key, slot_p) +avl_tree *tree; +char *key; +char ***slot_p; + Search for an entry matching key; if not found, insert key and + return the address of the value slot for this entry. If found, + do not insert key, and return the address of the value slot for + the existing entry. slot_p can be used to associate a value with + the key. + + +void +avl_foreach(tree, func, direction) +avl_tree *tree; +int (*func)(); +int direction; + + Apply `func' to each item in the tree `tree' in turn. If + direction is AVL_FORWARD, the tree is traversed from smallest + to largest. Otherwise it is traversed from largest to smallest. + + func should be of the form: + + void + func(key, value) + char *key; + char *value; + + where `key' is the key the item was stored under, and `value' + the value of the item. + + +avl_count(tree) +avl_tree *tree; + Returns the number of entries in the avl tree. + + +avl_generator * +avl_init_gen(tree, direction) +avl_tree *tree; +int direction; + Start up a generator on an avl-tree. direction is either + AVL_FORWARD or AVL_BACKWARD indicating the direction of + generation. + + +avl_gen(gen, key_p, value_p) +avl_generator *gen; +char **key_p; +char **value_p; + Generate the next item from the avl-tree. Returns 0 if there + are no more items in the tree. Deletion of last generated item + (via avl_delete) is supported. Insertion of items during + generation will result in these items never being generated + (until the next avl_init_gen()). Excercise for the interested + student: how does one write an avl generator ? + + +void +avl_free_gen(gen) +avl_generator *gen; + Free a generator. + + +avl_foreach_item(tree, gen, direction, key_p, value_p) +avl_tree *tree; +avl_generator *gen; +int direction; +char **key_p; +char **value_p; + Generate over all items in an avl-tree. This macro iterator + combines avl_init_gen(), avl_gen(), and avl_free_gen() into + a single statement iterator. diff --git a/src/misc/avl/avl.h b/src/misc/avl/avl.h new file mode 100644 index 00000000..21d811da --- /dev/null +++ b/src/misc/avl/avl.h @@ -0,0 +1,80 @@ +/* + * Revision Control Information + * + * $Source: /vol/opua/opua2/sis/sis-1.2/common/src/sis/avl/RCS/avl.h,v $ + * $Author: sis $ + * $Revision: 1.3 $ + * $Date: 1994/07/15 23:00:40 $ + * + */ +#ifndef AVL_INCLUDED +#define AVL_INCLUDED + +#define EXTERN +#define ARGS(protos) protos + +#define MAX(a,b) ((a) > (b) ? (a) : (b)) + +#define NIL(type) \ + ((type *) 0) +#define ALLOC(type, num) \ + ((type *) malloc(sizeof(type) * (num))) +#define REALLOC(type, obj, num) \ + ((type *) realloc((char *) obj, sizeof(type) * (num))) +#define FREE(obj) \ + free((char *) (obj)) + + + +typedef struct avl_node_struct avl_node; +struct avl_node_struct { + avl_node *left, *right; + char *key; + char *value; + int height; +}; + + +typedef struct avl_tree_struct avl_tree; +struct avl_tree_struct { + avl_node *root; + int (*compar)(); + int num_entries; + int modified; +}; + + +typedef struct avl_generator_struct avl_generator; +struct avl_generator_struct { + avl_tree *tree; + avl_node **nodelist; + int count; +}; + + +#define AVL_FORWARD 0 +#define AVL_BACKWARD 1 + + +EXTERN avl_tree *avl_init_table ARGS((int (*)())); +EXTERN int avl_delete ARGS((avl_tree *, char **, char **)); +EXTERN int avl_insert ARGS((avl_tree *, char *, char *)); +EXTERN int avl_lookup ARGS((avl_tree *, char *, char **)); +EXTERN int avl_first ARGS((avl_tree *, char **, char **)); +EXTERN int avl_last ARGS((avl_tree *, char **, char **)); +EXTERN int avl_find_or_add ARGS((avl_tree *, char *, char ***)); +EXTERN int avl_count ARGS((avl_tree *)); +EXTERN int avl_numcmp ARGS((char *, char *)); +EXTERN int avl_gen ARGS((avl_generator *, char **, char **)); +EXTERN void avl_foreach ARGS((avl_tree *, void (*)(), int)); +EXTERN void avl_free_table ARGS((avl_tree *, void (*)(), void (*)())); +EXTERN void avl_free_gen ARGS((avl_generator *)); +EXTERN avl_generator *avl_init_gen ARGS((avl_tree *, int)); + +#define avl_is_member(tree, key) avl_lookup(tree, key, (char **) 0) + +#define avl_foreach_item(table, gen, dir, key_p, value_p) \ + for(gen = avl_init_gen(table, dir); \ + avl_gen(gen, key_p, value_p) || (avl_free_gen(gen),0);) + +#endif -- cgit v1.2.3