Version abc90118

3 files changed, 862 insertions, 0 deletions

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 <stdio.h>
+#include <stdlib.h>
+
+#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