Version abc90118

1 files changed, 616 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;
+}