Version abc71001

5 files changed, 1538 insertions, 0 deletions

diff --git a/src/misc/st/module.make b/src/misc/st/module.make
new file mode 100644
index 00000000..33e442c0
--- /dev/null
+++ b/src/misc/st/module.make
@@ -0,0 +1,2 @@
+SRC +=  src/misc/st/st.c \
+    src/misc/st/stmm.c
diff --git a/src/misc/st/st.c b/src/misc/st/st.c
new file mode 100644
index 00000000..872fe51b
--- /dev/null
+++ b/src/misc/st/st.c
@@ -0,0 +1,625 @@
+/*
+ * Revision Control Information
+ *
+ * /projects/hsis/CVS/utilities/st/st.c,v
+ * serdar
+ * 1.1
+ * 1993/07/29 01:00:13
+ *
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include "st.h"
+
+#ifndef ABS
+#  define ABS(a)            ((a) < 0 ? -(a) : (a))
+#endif
+
+#ifndef ALLOC
+#define ALLOC(type, num)     ((type *) malloc(sizeof(type) * (num)))
+#endif
+
+#ifndef FREE
+#define FREE(obj)             ((obj) ? (free((char *) (obj)), (obj) = 0) : 0)
+#endif
+
+#ifndef REALLOC
+#define REALLOC(type, obj, num)    \
+        ((obj) ? ((type *) realloc((char *)(obj), sizeof(type) * (num))) : \
+         ((type *) malloc(sizeof(type) * (num))))
+#endif
+
+#define ST_NUMCMP(x,y) ((x) != (y))
+#define ST_NUMHASH(x,size) (ABS((long)x)%(size))
+//#define ST_PTRHASH(x,size) ((int)((unsigned long)(x)>>2)%size)  // 64-bit bug fix 9/17/2007
+#define ST_PTRHASH(x,size) ((int)(((unsigned long)(x)>>2)%size))
+#define EQUAL(func, x, y) \
+    ((((func) == st_numcmp) || ((func) == st_ptrcmp)) ?\
+      (ST_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
+
+
+#define do_hash(key, table)\
+    ((table->hash == st_ptrhash) ? ST_PTRHASH((key),(table)->num_bins) :\
+     (table->hash == st_numhash) ? ST_NUMHASH((key), (table)->num_bins) :\
+     (*table->hash)((key), (table)->num_bins))
+
+static int rehash();
+int st_numhash(), st_ptrhash(), st_numcmp(), st_ptrcmp();
+
+st_table *
+st_init_table_with_params(compare, hash, size, density, grow_factor,
+              reorder_flag)
+int (*compare)();
+int (*hash)();
+int size;
+int density;
+double grow_factor;
+int reorder_flag;
+{
+    int i;
+    st_table *new;
+
+    new = ALLOC(st_table, 1);
+    if (new == NULL) {
+    return NULL;
+    }
+    new->compare = compare;
+    new->hash = hash;
+    new->num_entries = 0;
+    new->max_density = density;
+    new->grow_factor = grow_factor;
+    new->reorder_flag = reorder_flag;
+    if (size <= 0) {
+    size = 1;
+    }
+    new->num_bins = size;
+    new->bins = ALLOC(st_table_entry *, size);
+    if (new->bins == NULL) {
+    FREE(new);
+    return NULL;
+    }
+    for(i = 0; i < size; i++) {
+    new->bins[i] = 0;
+    }
+    return new;
+}
+
+st_table *
+st_init_table(compare, hash)
+int (*compare)();
+int (*hash)();
+{
+    return st_init_table_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
+                     ST_DEFAULT_MAX_DENSITY,
+                     ST_DEFAULT_GROW_FACTOR,
+                     ST_DEFAULT_REORDER_FLAG);
+}
+                
+void
+st_free_table(table)
+st_table *table;
+{
+    register st_table_entry *ptr, *next;
+    int i;
+
+    for(i = 0; i < table->num_bins ; i++) {
+    ptr = table->bins[i];
+    while (ptr != NULL) {
+        next = ptr->next;
+        FREE(ptr);
+        ptr = next;
+    }
+    }
+    FREE(table->bins);
+    FREE(table);
+}
+
+#define PTR_NOT_EQUAL(table, ptr, user_key)\
+(ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))
+
+#define FIND_ENTRY(table, hash_val, key, ptr, last) \
+    (last) = &(table)->bins[hash_val];\
+    (ptr) = *(last);\
+    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
+    (last) = &(ptr)->next; (ptr) = *(last);\
+    }\
+    if ((ptr) != NULL && (table)->reorder_flag) {\
+    *(last) = (ptr)->next;\
+    (ptr)->next = (table)->bins[hash_val];\
+    (table)->bins[hash_val] = (ptr);\
+    }
+
+int
+st_lookup(table, key, value)
+st_table *table;
+register char *key;
+char **value;
+{
+    int hash_val;
+    register st_table_entry *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr, last);
+    
+    if (ptr == NULL) {
+    return 0;
+    } else {
+    if (value != NULL) {
+        *value = ptr->record; 
+    }
+    return 1;
+    }
+}
+
+int
+st_lookup_int(table, key, value)
+st_table *table;
+register char *key;
+int *value;
+{
+    int hash_val;
+    register st_table_entry *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr, last);
+    
+    if (ptr == NULL) {
+    return 0;
+    } else {
+    if (value != 0) {
+        *value = (long) ptr->record;
+    }
+    return 1;
+    }
+}
+
+/* This macro does not check if memory allocation fails. Use at you own risk */
+#define ADD_DIRECT(table, key, value, hash_val, new)\
+{\
+    if (table->num_entries/table->num_bins >= table->max_density) {\
+    rehash(table);\
+    hash_val = do_hash(key,table);\
+    }\
+    \
+    new = ALLOC(st_table_entry, 1);\
+    \
+    new->key = key;\
+    new->record = value;\
+    new->next = table->bins[hash_val];\
+    table->bins[hash_val] = new;\
+    table->num_entries++;\
+}
+
+int
+st_insert(table, key, value)
+register st_table *table;
+register char *key;
+char *value;
+{
+    int hash_val;
+    st_table_entry *new;
+    register st_table_entry *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    if (table->num_entries/table->num_bins >= table->max_density) {
+        if (rehash(table) == ST_OUT_OF_MEM) {
+        return ST_OUT_OF_MEM;
+        }
+        hash_val = do_hash(key, table);
+    }
+    new = ALLOC(st_table_entry, 1);
+    if (new == NULL) {
+        return ST_OUT_OF_MEM;
+    }
+    new->key = key;
+    new->record = value;
+    new->next = table->bins[hash_val];
+    table->bins[hash_val] = new;
+    table->num_entries++;
+    return 0;
+    } else {
+    ptr->record = value;
+    return 1;
+    }
+}
+
+int
+st_add_direct(table, key, value)
+st_table *table;
+char *key;
+char *value;
+{
+    int hash_val;
+    st_table_entry *new;
+    
+    hash_val = do_hash(key, table);
+    if (table->num_entries / table->num_bins >= table->max_density) {
+    if (rehash(table) == ST_OUT_OF_MEM) {
+        return ST_OUT_OF_MEM;
+    }
+    }
+    hash_val = do_hash(key, table);
+    new = ALLOC(st_table_entry, 1);
+    if (new == NULL) {
+    return ST_OUT_OF_MEM;
+    }
+    new->key = key;
+    new->record = value;
+    new->next = table->bins[hash_val];
+    table->bins[hash_val] = new;
+    table->num_entries++;
+    return 1;
+}
+
+int
+st_find_or_add(table, key, slot)
+st_table *table;
+char *key;
+char ***slot;
+{
+    int hash_val;
+    st_table_entry *new, *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    if (table->num_entries / table->num_bins >= table->max_density) {
+        if (rehash(table) == ST_OUT_OF_MEM) {
+        return ST_OUT_OF_MEM;
+        }
+        hash_val = do_hash(key, table);
+    }
+    new = ALLOC(st_table_entry, 1);
+    if (new == NULL) {
+        return ST_OUT_OF_MEM;
+    }
+    new->key = key;
+    new->record = (char *) 0;
+    new->next = table->bins[hash_val];
+    table->bins[hash_val] = new;
+    table->num_entries++;
+    if (slot != NULL) *slot = &new->record;
+    return 0;
+    } else {
+    if (slot != NULL) *slot = &ptr->record;
+    return 1;
+    }
+}
+
+int
+st_find(table, key, slot)
+st_table *table;
+char *key;
+char ***slot;
+{
+    int hash_val;
+    st_table_entry *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    return 0;
+    } else {
+    if (slot != NULL) {
+        *slot = &ptr->record;
+    }
+    return 1;
+    }
+}
+
+static int
+rehash(table)
+register st_table *table;
+{
+    register st_table_entry *ptr, *next, **old_bins;
+    int             i, old_num_bins, hash_val, old_num_entries;
+
+    /* save old values */
+    old_bins = table->bins;
+    old_num_bins = table->num_bins;
+    old_num_entries = table->num_entries;
+
+    /* rehash */
+    table->num_bins = (int)(table->grow_factor * old_num_bins);
+    if (table->num_bins % 2 == 0) {
+    table->num_bins += 1;
+    }
+    table->num_entries = 0;
+    table->bins = ALLOC(st_table_entry *, table->num_bins);
+    if (table->bins == NULL) {
+    table->bins = old_bins;
+    table->num_bins = old_num_bins;
+    table->num_entries = old_num_entries;
+    return ST_OUT_OF_MEM;
+    }
+    /* initialize */
+    for (i = 0; i < table->num_bins; i++) {
+    table->bins[i] = 0;
+    }
+
+    /* copy data over */
+    for (i = 0; i < old_num_bins; i++) {
+    ptr = old_bins[i];
+    while (ptr != NULL) {
+        next = ptr->next;
+        hash_val = do_hash(ptr->key, table);
+        ptr->next = table->bins[hash_val];
+        table->bins[hash_val] = ptr;
+        table->num_entries++;
+        ptr = next;
+    }
+    }
+    FREE(old_bins);
+
+    return 1;
+}
+
+st_table *
+st_copy(old_table)
+st_table *old_table;
+{
+    st_table *new_table;
+    st_table_entry *ptr, *newptr, *next, *new;
+    int i, j, num_bins = old_table->num_bins;
+
+    new_table = ALLOC(st_table, 1);
+    if (new_table == NULL) {
+    return NULL;
+    }
+    
+    *new_table = *old_table;
+    new_table->bins = ALLOC(st_table_entry *, num_bins);
+    if (new_table->bins == NULL) {
+    FREE(new_table);
+    return NULL;
+    }
+    for(i = 0; i < num_bins ; i++) {
+    new_table->bins[i] = NULL;
+    ptr = old_table->bins[i];
+    while (ptr != NULL) {
+        new = ALLOC(st_table_entry, 1);
+        if (new == NULL) {
+        for (j = 0; j <= i; j++) {
+            newptr = new_table->bins[j];
+            while (newptr != NULL) {
+            next = newptr->next;
+            FREE(newptr);
+            newptr = next;
+            }
+        }
+        FREE(new_table->bins);
+        FREE(new_table);
+        return NULL;
+        }
+        *new = *ptr;
+        new->next = new_table->bins[i];
+        new_table->bins[i] = new;
+        ptr = ptr->next;
+    }
+    }
+    return new_table;
+}
+
+int
+st_delete(table, keyp, value)
+register st_table *table;
+register char **keyp;
+char **value;
+{
+    int hash_val;
+    char *key = *keyp;
+    register st_table_entry *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr ,last);
+    
+    if (ptr == NULL) {
+    return 0;
+    }
+
+    *last = ptr->next;
+    if (value != NULL) *value = ptr->record;
+    *keyp = ptr->key;
+    FREE(ptr);
+    table->num_entries--;
+    return 1;
+}
+
+int
+st_delete_int(table, keyp, value)
+register st_table *table;
+register long *keyp;
+char **value;
+{
+    int hash_val;
+    char *key = (char *) *keyp;
+    register st_table_entry *ptr, **last;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, hash_val, key, ptr ,last);
+
+    if (ptr == NULL) {
+        return 0;
+    }
+
+    *last = ptr->next;
+    if (value != NULL) *value = ptr->record;
+    *keyp = (long) ptr->key;
+    FREE(ptr);
+    table->num_entries--;
+    return 1;
+}
+
+int
+st_foreach(table, func, arg)
+st_table *table;
+enum st_retval (*func)();
+char *arg;
+{
+    st_table_entry *ptr, **last;
+    enum st_retval retval;
+    int i;
+
+    for(i = 0; i < table->num_bins; i++) {
+    last = &table->bins[i]; ptr = *last;
+    while (ptr != NULL) {
+        retval = (*func)(ptr->key, ptr->record, arg);
+        switch (retval) {
+        case ST_CONTINUE:
+        last = &ptr->next; ptr = *last;
+        break;
+        case ST_STOP:
+        return 0;
+        case ST_DELETE:
+        *last = ptr->next;
+        table->num_entries--;    /* cstevens@ic */
+        FREE(ptr);
+        ptr = *last;
+        }
+    }
+    }
+    return 1;
+}
+
+int
+st_strhash(string, modulus)
+register char *string;
+int modulus;
+{
+    register int val = 0;
+    register int c;
+    
+    while ((c = *string++) != '\0') {
+    val = val*997 + c;
+    }
+
+    return ((val < 0) ? -val : val)%modulus;
+}
+
+int
+st_numhash(x, size)
+char *x;
+int size;
+{
+    return ST_NUMHASH(x, size);
+}
+
+int
+st_ptrhash(x, size)
+char *x;
+int size;
+{
+    return ST_PTRHASH(x, size);
+}
+
+int
+st_numcmp(x, y)
+char *x;
+char *y;
+{
+    return ST_NUMCMP(x, y);
+}
+
+int
+st_ptrcmp(x, y)
+char *x;
+char *y;
+{
+    return ST_NUMCMP(x, y);
+}
+
+st_generator *
+st_init_gen(table)
+st_table *table;
+{
+    st_generator *gen;
+
+    gen = ALLOC(st_generator, 1);
+    if (gen == NULL) {
+    return NULL;
+    }
+    gen->table = table;
+    gen->entry = NULL;
+    gen->index = 0;
+    return gen;
+}
+
+
+int 
+st_gen(gen, key_p, value_p)
+st_generator *gen;
+char **key_p;
+char **value_p;
+{
+    register int i;
+
+    if (gen->entry == NULL) {
+    /* try to find next entry */
+    for(i = gen->index; i < gen->table->num_bins; i++) {
+        if (gen->table->bins[i] != NULL) {
+        gen->index = i+1;
+        gen->entry = gen->table->bins[i];
+        break;
+        }
+    }
+    if (gen->entry == NULL) {
+        return 0;        /* that's all folks ! */
+    }
+    }
+    *key_p = gen->entry->key;
+    if (value_p != 0) {
+    *value_p = gen->entry->record;
+    }
+    gen->entry = gen->entry->next;
+    return 1;
+}
+
+
+int 
+st_gen_int(gen, key_p, value_p)
+st_generator *gen;
+char **key_p;
+long *value_p;
+{
+    register int i;
+
+    if (gen->entry == NULL) {
+    /* try to find next entry */
+    for(i = gen->index; i < gen->table->num_bins; i++) {
+        if (gen->table->bins[i] != NULL) {
+        gen->index = i+1;
+        gen->entry = gen->table->bins[i];
+        break;
+        }
+    }
+    if (gen->entry == NULL) {
+        return 0;        /* that's all folks ! */
+    }
+    }
+    *key_p = gen->entry->key;
+    if (value_p != 0) {
+       *value_p = (long) gen->entry->record;
+    }
+    gen->entry = gen->entry->next;
+    return 1;
+}
+
+
+void
+st_free_gen(gen)
+st_generator *gen;
+{
+    FREE(gen);
+}
diff --git a/src/misc/st/st.h b/src/misc/st/st.h
new file mode 100644
index 00000000..b15f3c83
--- /dev/null
+++ b/src/misc/st/st.h
@@ -0,0 +1,96 @@
+/*
+ * Revision Control Information
+ *
+ * /projects/hsis/CVS/utilities/st/st.h,v
+ * serdar
+ * 1.1
+ * 1993/07/29 01:00:21
+ *
+ */
+/* LINTLIBRARY */
+
+/* /projects/hsis/CVS/utilities/st/st.h,v 1.1 1993/07/29 01:00:21 serdar Exp */
+
+#ifndef ST_INCLUDED
+#define ST_INCLUDED
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct st_table_entry st_table_entry;
+struct st_table_entry {
+    char *key;
+    char *record;
+    st_table_entry *next;
+};
+
+typedef struct st_table st_table;
+struct st_table {
+    int (*compare)();
+    int (*hash)();
+    int num_bins;
+    int num_entries;
+    int max_density;
+    int reorder_flag;
+    double grow_factor;
+    st_table_entry **bins;
+};
+
+typedef struct st_generator st_generator;
+struct st_generator {
+    st_table *table;
+    st_table_entry *entry;
+    int index;
+};
+
+#define st_is_member(table,key) st_lookup(table,key,(char **) 0)
+#define st_count(table) ((table)->num_entries)
+
+enum st_retval {ST_CONTINUE, ST_STOP, ST_DELETE};
+
+typedef enum st_retval (*ST_PFSR)();
+typedef int (*ST_PFI)();
+
+extern st_table *st_init_table_with_params (ST_PFI, ST_PFI, int, int, double, int);
+extern st_table *st_init_table (ST_PFI, ST_PFI); 
+extern void st_free_table (st_table *);
+extern int st_lookup (st_table *, char *, char **);
+extern int st_lookup_int (st_table *, char *, int *);
+extern int st_insert (st_table *, char *, char *);
+extern int st_add_direct (st_table *, char *, char *);
+extern int st_find_or_add (st_table *, char *, char ***);
+extern int st_find (st_table *, char *, char ***);
+extern st_table *st_copy (st_table *);
+extern int st_delete (st_table *, char **, char **);
+extern int st_delete_int (st_table *, long *, char **);
+extern int st_foreach (st_table *, ST_PFSR, char *);
+extern int st_strhash (char *, int);
+extern int st_numhash (char *, int);
+extern int st_ptrhash (char *, int);
+extern int st_numcmp (char *, char *);
+extern int st_ptrcmp (char *, char *);
+extern st_generator *st_init_gen (st_table *);
+extern int st_gen (st_generator *, char **, char **);
+extern int st_gen_int (st_generator *, char **, long *);
+extern void st_free_gen (st_generator *);
+
+
+#define ST_DEFAULT_MAX_DENSITY 5
+#define ST_DEFAULT_INIT_TABLE_SIZE 11
+#define ST_DEFAULT_GROW_FACTOR 2.0
+#define ST_DEFAULT_REORDER_FLAG 0
+
+#define st_foreach_item(table, gen, key, value) \
+    for(gen=st_init_gen(table); st_gen(gen,key,value) || (st_free_gen(gen),0);)
+
+#define st_foreach_item_int(table, gen, key, value) \
+    for(gen=st_init_gen(table); st_gen_int(gen,key,value) || (st_free_gen(gen),0);)
+
+#define ST_OUT_OF_MEM -10000
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* ST_INCLUDED */
diff --git a/src/misc/st/stmm.c b/src/misc/st/stmm.c
new file mode 100644
index 00000000..8dfacfe4
--- /dev/null
+++ b/src/misc/st/stmm.c
@@ -0,0 +1,688 @@
+/*
+ * Revision Control Information
+ *
+ * /projects/hsis/CVS/utilities/st/st.c,v
+ * serdar
+ * 1.1
+ * 1993/07/29 01:00:13
+ *
+ */
+#include <stdio.h>
+#include "extra.h"
+#include "stmm.h"
+
+#ifndef ABS
+#  define ABS(a)            ((a) < 0 ? -(a) : (a))
+#endif
+
+#define STMM_NUMCMP(x,y) ((x) != (y))
+#define STMM_NUMHASH(x,size) (ABS((long)x)%(size))
+//#define STMM_PTRHASH(x,size) ((int)((unsigned long)(x)>>2)%size) //  64-bit bug fix 9/17/2007
+#define STMM_PTRHASH(x,size) ((int)(((unsigned long)(x)>>2)%size))
+#define EQUAL(func, x, y) \
+    ((((func) == stmm_numcmp) || ((func) == stmm_ptrcmp)) ?\
+      (STMM_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))
+
+
+#define do_hash(key, table)\
+    ((table->hash == stmm_ptrhash) ? STMM_PTRHASH((key),(table)->num_bins) :\
+     (table->hash == stmm_numhash) ? STMM_NUMHASH((key), (table)->num_bins) :\
+     (*table->hash)((key), (table)->num_bins))
+
+static int rehash ();
+int stmm_numhash (), stmm_ptrhash (), stmm_numcmp (), stmm_ptrcmp ();
+
+stmm_table *
+stmm_init_table_with_params (compare, hash, size, density, grow_factor,
+                 reorder_flag)
+    int (*compare) ();
+    int (*hash) ();
+    int size;
+    int density;
+    double grow_factor;
+    int reorder_flag;
+{
+    int i;
+    stmm_table *new;
+
+    new = ALLOC (stmm_table, 1);
+    if (new == NULL) {
+    return NULL;
+    }
+    new->compare = compare;
+    new->hash = hash;
+    new->num_entries = 0;
+    new->max_density = density;
+    new->grow_factor = grow_factor;
+    new->reorder_flag = reorder_flag;
+    if (size <= 0) {
+    size = 1;
+    }
+    new->num_bins = size;
+    new->bins = ALLOC (stmm_table_entry *, size);
+    if (new->bins == NULL) {
+    FREE (new);
+    return NULL;
+    }
+    for (i = 0; i < size; i++) {
+    new->bins[i] = 0;
+    }
+
+    // added by alanmi
+    new->pMemMan = Extra_MmFixedStart(sizeof (stmm_table_entry));
+    return new;
+}
+
+stmm_table *
+stmm_init_table (compare, hash)
+    int (*compare) ();
+    int (*hash) ();
+{
+    return stmm_init_table_with_params (compare, hash,
+                    STMM_DEFAULT_INIT_TABLE_SIZE,
+                    STMM_DEFAULT_MAX_DENSITY,
+                    STMM_DEFAULT_GROW_FACTOR,
+                    STMM_DEFAULT_REORDER_FLAG);
+}
+
+void
+stmm_free_table (table)
+    stmm_table *table;
+{
+/*
+    register stmm_table_entry *ptr, *next;
+    int i;
+    for ( i = 0; i < table->num_bins; i++ )
+    {
+        ptr = table->bins[i];
+        while ( ptr != NULL )
+        {
+            next = ptr->next;
+            FREE( ptr );
+            ptr = next;
+        }
+    }
+*/
+    // no need to deallocate entries because they are in the memory manager now
+    // added by alanmi
+    if ( table->pMemMan )
+        Extra_MmFixedStop (table->pMemMan);
+    FREE (table->bins);
+    FREE (table);
+}
+
+// this function recycles all the bins
+void
+stmm_clean (table)
+    stmm_table *table;
+{
+    int i;
+    // clean the bins
+    for (i = 0; i < table->num_bins; i++)
+        table->bins[i] = NULL;
+    // reset the parameters
+    table->num_entries = 0;
+    // restart the memory manager
+    Extra_MmFixedRestart (table->pMemMan);
+}
+
+
+#define PTR_NOT_EQUAL(table, ptr, user_key)\
+(ptr != NULL && !EQUAL(table->compare, user_key, (ptr)->key))
+
+#define FIND_ENTRY(table, hash_val, key, ptr, last) \
+    (last) = &(table)->bins[hash_val];\
+    (ptr) = *(last);\
+    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\
+    (last) = &(ptr)->next; (ptr) = *(last);\
+    }\
+    if ((ptr) != NULL && (table)->reorder_flag) {\
+    *(last) = (ptr)->next;\
+    (ptr)->next = (table)->bins[hash_val];\
+    (table)->bins[hash_val] = (ptr);\
+    }
+
+int
+stmm_lookup (table, key, value)
+    stmm_table *table;
+    register char *key;
+    char **value;
+{
+    int hash_val;
+    register stmm_table_entry *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    return 0;
+    }
+    else {
+    if (value != NULL)
+    {
+        *value = ptr->record;
+    }
+    return 1;
+    }
+}
+
+int
+stmm_lookup_int (table, key, value)
+    stmm_table *table;
+    register char *key;
+    int *value;
+{
+    int hash_val;
+    register stmm_table_entry *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    return 0;
+    }
+    else {
+    if (value != 0)
+    {
+        *value = (long) ptr->record;
+    }
+    return 1;
+    }
+}
+
+// This macro contained a line
+//    new = ALLOC(stmm_table_entry, 1);
+// which was modified by alanmi
+
+
+/* This macro does not check if memory allocation fails. Use at you own risk */
+#define ADD_DIRECT(table, key, value, hash_val, new)\
+{\
+    if (table->num_entries/table->num_bins >= table->max_density) {\
+    rehash(table);\
+    hash_val = do_hash(key,table);\
+    }\
+    \
+    new = (stmm_table_entry *)Extra_MmFixedEntryFetch( table->pMemMan );\
+    \
+    new->key = key;\
+    new->record = value;\
+    new->next = table->bins[hash_val];\
+    table->bins[hash_val] = new;\
+    table->num_entries++;\
+}
+
+int
+stmm_insert (table, key, value)
+    register stmm_table *table;
+    register char *key;
+    char *value;
+{
+    int hash_val;
+    stmm_table_entry *new;
+    register stmm_table_entry *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    if (table->num_entries / table->num_bins >= table->max_density) {
+        if (rehash (table) == STMM_OUT_OF_MEM) {
+        return STMM_OUT_OF_MEM;
+        }
+        hash_val = do_hash (key, table);
+    }
+
+//              new = ALLOC( stmm_table_entry, 1 );
+    new = (stmm_table_entry *) Extra_MmFixedEntryFetch (table->pMemMan);
+    if (new == NULL) {
+        return STMM_OUT_OF_MEM;
+    }
+
+    new->key = key;
+    new->record = value;
+    new->next = table->bins[hash_val];
+    table->bins[hash_val] = new;
+    table->num_entries++;
+    return 0;
+    }
+    else {
+    ptr->record = value;
+    return 1;
+    }
+}
+
+int
+stmm_add_direct (table, key, value)
+    stmm_table *table;
+    char *key;
+    char *value;
+{
+    int hash_val;
+    stmm_table_entry *new;
+
+    hash_val = do_hash (key, table);
+    if (table->num_entries / table->num_bins >= table->max_density) {
+    if (rehash (table) == STMM_OUT_OF_MEM) {
+        return STMM_OUT_OF_MEM;
+    }
+    }
+    hash_val = do_hash (key, table);
+
+//      new = ALLOC( stmm_table_entry, 1 );
+    new = (stmm_table_entry *) Extra_MmFixedEntryFetch (table->pMemMan);
+    if (new == NULL) {
+    return STMM_OUT_OF_MEM;
+    }
+
+    new->key = key;
+    new->record = value;
+    new->next = table->bins[hash_val];
+    table->bins[hash_val] = new;
+    table->num_entries++;
+    return 1;
+}
+
+int
+stmm_find_or_add (table, key, slot)
+    stmm_table *table;
+    char *key;
+    char ***slot;
+{
+    int hash_val;
+    stmm_table_entry *new, *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    if (table->num_entries / table->num_bins >= table->max_density) {
+        if (rehash (table) == STMM_OUT_OF_MEM) {
+        return STMM_OUT_OF_MEM;
+        }
+        hash_val = do_hash (key, table);
+    }
+
+    // new = ALLOC( stmm_table_entry, 1 );
+    new = (stmm_table_entry *) Extra_MmFixedEntryFetch (table->pMemMan);
+    if (new == NULL) {
+        return STMM_OUT_OF_MEM;
+    }
+
+    new->key = key;
+    new->record = (char *) 0;
+    new->next = table->bins[hash_val];
+    table->bins[hash_val] = new;
+    table->num_entries++;
+    if (slot != NULL)
+         *slot = &new->record;
+    return 0;
+    }
+    else {
+    if (slot != NULL)
+         *slot = &ptr->record;
+    return 1;
+    }
+}
+
+int
+stmm_find (table, key, slot)
+    stmm_table *table;
+    char *key;
+    char ***slot;
+{
+    int hash_val;
+    stmm_table_entry *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    return 0;
+    }
+    else {
+    if (slot != NULL)
+    {
+        *slot = &ptr->record;
+    }
+    return 1;
+    }
+}
+
+static int
+rehash (table)
+    register stmm_table *table;
+{
+    register stmm_table_entry *ptr, *next, **old_bins;
+    int i, old_num_bins, hash_val, old_num_entries;
+
+    /* save old values */
+    old_bins = table->bins;
+    old_num_bins = table->num_bins;
+    old_num_entries = table->num_entries;
+
+    /* rehash */
+    table->num_bins = (int) (table->grow_factor * old_num_bins);
+    if (table->num_bins % 2 == 0) {
+    table->num_bins += 1;
+    }
+    table->num_entries = 0;
+    table->bins = ALLOC (stmm_table_entry *, table->num_bins);
+    if (table->bins == NULL) {
+    table->bins = old_bins;
+    table->num_bins = old_num_bins;
+    table->num_entries = old_num_entries;
+    return STMM_OUT_OF_MEM;
+    }
+    /* initialize */
+    for (i = 0; i < table->num_bins; i++) {
+    table->bins[i] = 0;
+    }
+
+    /* copy data over */
+    for (i = 0; i < old_num_bins; i++) {
+    ptr = old_bins[i];
+    while (ptr != NULL) {
+        next = ptr->next;
+        hash_val = do_hash (ptr->key, table);
+        ptr->next = table->bins[hash_val];
+        table->bins[hash_val] = ptr;
+        table->num_entries++;
+        ptr = next;
+    }
+    }
+    FREE (old_bins);
+
+    return 1;
+}
+
+stmm_table *
+stmm_copy (old_table)
+    stmm_table *old_table;
+{
+    stmm_table *new_table;
+    stmm_table_entry *ptr, /* *newptr, *next, */ *new;
+    int i, /*j, */ num_bins = old_table->num_bins;
+
+    new_table = ALLOC (stmm_table, 1);
+    if (new_table == NULL) {
+    return NULL;
+    }
+
+    *new_table = *old_table;
+    new_table->bins = ALLOC (stmm_table_entry *, num_bins);
+    if (new_table->bins == NULL) {
+    FREE (new_table);
+    return NULL;
+    }
+
+    // allocate the memory manager for the new table
+    new_table->pMemMan =
+    Extra_MmFixedStart (sizeof (stmm_table_entry));
+
+    for (i = 0; i < num_bins; i++) {
+    new_table->bins[i] = NULL;
+    ptr = old_table->bins[i];
+    while (ptr != NULL) {
+//                      new = ALLOC( stmm_table_entry, 1 );
+        new =
+        (stmm_table_entry *) Extra_MmFixedEntryFetch (new_table->
+                                pMemMan);
+
+        if (new == NULL) {
+/*
+                for ( j = 0; j <= i; j++ )
+                {
+                    newptr = new_table->bins[j];
+                    while ( newptr != NULL )
+                    {
+                        next = newptr->next;
+                        FREE( newptr );
+                        newptr = next;
+                    }
+                }
+*/
+        Extra_MmFixedStop (new_table->pMemMan);
+
+        FREE (new_table->bins);
+        FREE (new_table);
+        return NULL;
+        }
+        *new = *ptr;
+        new->next = new_table->bins[i];
+        new_table->bins[i] = new;
+        ptr = ptr->next;
+    }
+    }
+    return new_table;
+}
+
+int
+stmm_delete (table, keyp, value)
+    register stmm_table *table;
+    register char **keyp;
+    char **value;
+{
+    int hash_val;
+    char *key = *keyp;
+    register stmm_table_entry *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    return 0;
+    }
+
+    *last = ptr->next;
+    if (value != NULL)
+     *value = ptr->record;
+    *keyp = ptr->key;
+//      FREE( ptr );
+    Extra_MmFixedEntryRecycle (table->pMemMan, (char *) ptr);
+
+    table->num_entries--;
+    return 1;
+}
+
+int
+stmm_delete_int (table, keyp, value)
+    register stmm_table *table;
+    register long *keyp;
+    char **value;
+{
+    int hash_val;
+    char *key = (char *) *keyp;
+    register stmm_table_entry *ptr, **last;
+
+    hash_val = do_hash (key, table);
+
+    FIND_ENTRY (table, hash_val, key, ptr, last);
+
+    if (ptr == NULL) {
+    return 0;
+    }
+
+    *last = ptr->next;
+    if (value != NULL)
+     *value = ptr->record;
+    *keyp = (long) ptr->key;
+//      FREE( ptr );
+    Extra_MmFixedEntryRecycle (table->pMemMan, (char *) ptr);
+
+    table->num_entries--;
+    return 1;
+}
+
+int
+stmm_foreach (table, func, arg)
+    stmm_table *table;
+    enum stmm_retval (*func) ();
+    char *arg;
+{
+    stmm_table_entry *ptr, **last;
+    enum stmm_retval retval;
+    int i;
+
+    for (i = 0; i < table->num_bins; i++) {
+    last = &table->bins[i];
+    ptr = *last;
+    while (ptr != NULL) {
+        retval = (*func) (ptr->key, ptr->record, arg);
+        switch (retval) {
+        case STMM_CONTINUE:
+        last = &ptr->next;
+        ptr = *last;
+        break;
+        case STMM_STOP:
+        return 0;
+        case STMM_DELETE:
+        *last = ptr->next;
+        table->num_entries--;    /* cstevens@ic */
+//                              FREE( ptr );
+        Extra_MmFixedEntryRecycle (table->pMemMan, (char *) ptr);
+
+        ptr = *last;
+        }
+    }
+    }
+    return 1;
+}
+
+int
+stmm_strhash (string, modulus)
+    register char *string;
+    int modulus;
+{
+    register int val = 0;
+    register int c;
+
+    while ((c = *string++) != '\0') {
+    val = val * 997 + c;
+    }
+
+    return ((val < 0) ? -val : val) % modulus;
+}
+
+int
+stmm_numhash (x, size)
+    char *x;
+    int size;
+{
+    return STMM_NUMHASH (x, size);
+}
+
+int
+stmm_ptrhash (x, size)
+    char *x;
+    int size;
+{
+    return STMM_PTRHASH (x, size);
+}
+
+int
+stmm_numcmp (x, y)
+    char *x;
+    char *y;
+{
+    return STMM_NUMCMP (x, y);
+}
+
+int
+stmm_ptrcmp (x, y)
+    char *x;
+    char *y;
+{
+    return STMM_NUMCMP (x, y);
+}
+
+stmm_generator *
+stmm_init_gen (table)
+    stmm_table *table;
+{
+    stmm_generator *gen;
+
+    gen = ALLOC (stmm_generator, 1);
+    if (gen == NULL) {
+    return NULL;
+    }
+    gen->table = table;
+    gen->entry = NULL;
+    gen->index = 0;
+    return gen;
+}
+
+
+int
+stmm_gen (gen, key_p, value_p)
+    stmm_generator *gen;
+    char **key_p;
+    char **value_p;
+{
+    register int i;
+
+    if (gen->entry == NULL) {
+    /* try to find next entry */
+    for (i = gen->index; i < gen->table->num_bins; i++) {
+        if (gen->table->bins[i] != NULL) {
+        gen->index = i + 1;
+        gen->entry = gen->table->bins[i];
+        break;
+        }
+    }
+    if (gen->entry == NULL) {
+        return 0;        /* that's all folks ! */
+    }
+    }
+    *key_p = gen->entry->key;
+    if (value_p != 0) {
+    *value_p = gen->entry->record;
+    }
+    gen->entry = gen->entry->next;
+    return 1;
+}
+
+
+int
+stmm_gen_int (gen, key_p, value_p)
+    stmm_generator *gen;
+    char **key_p;
+    long *value_p;
+{
+    register int i;
+
+    if (gen->entry == NULL) {
+    /* try to find next entry */
+    for (i = gen->index; i < gen->table->num_bins; i++) {
+        if (gen->table->bins[i] != NULL) {
+        gen->index = i + 1;
+        gen->entry = gen->table->bins[i];
+        break;
+        }
+    }
+    if (gen->entry == NULL) {
+        return 0;        /* that's all folks ! */
+    }
+    }
+    *key_p = gen->entry->key;
+    if (value_p != 0)
+    {
+    *value_p = (long) gen->entry->record;
+    }
+    gen->entry = gen->entry->next;
+    return 1;
+}
+
+
+void
+stmm_free_gen (gen)
+    stmm_generator *gen;
+{
+    FREE (gen);
+}
diff --git a/src/misc/st/stmm.h b/src/misc/st/stmm.h
new file mode 100644
index 00000000..4330416e
--- /dev/null
+++ b/src/misc/st/stmm.h
@@ -0,0 +1,127 @@
+/*
+ * Revision Control Information
+ *
+ * /projects/hsis/CVS/utilities/st/st.h,v
+ * serdar
+ * 1.1
+ * 1993/07/29 01:00:21
+ *
+ */
+/* LINTLIBRARY */
+
+/* /projects/hsis/CVS/utilities/st/st.h,v 1.1 1993/07/29 01:00:21 serdar Exp */
+
+#ifndef STMM_INCLUDED
+#define STMM_INCLUDED
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "extra.h"
+
+typedef struct stmm_table_entry stmm_table_entry;
+typedef struct stmm_table stmm_table;
+typedef struct stmm_generator stmm_generator;
+
+struct stmm_table_entry
+{
+    char *key;
+    char *record;
+    stmm_table_entry *next;
+};
+
+struct stmm_table
+{
+    int (*compare) ();
+    int (*hash) ();
+    int num_bins;
+    int num_entries;
+    int max_density;
+    int reorder_flag;
+    double grow_factor;
+    stmm_table_entry **bins;
+    // memory manager to improve runtime and prevent memory fragmentation
+    // added by alanmi - January 16, 2003
+    Extra_MmFixed_t *pMemMan;
+};
+
+struct stmm_generator
+{
+    stmm_table *table;
+    stmm_table_entry *entry;
+    int index;
+};
+
+#define stmm_is_member(table,key) stmm_lookup(table,key,(char **) 0)
+#define stmm_count(table) ((table)->num_entries)
+
+enum stmm_retval
+{ STMM_CONTINUE, STMM_STOP, STMM_DELETE };
+
+typedef enum stmm_retval (*STMM_PFSR) ();
+typedef int (*STMM_PFI) ();
+
+EXTERN stmm_table *stmm_init_table_with_params
+ARGS ((STMM_PFI, STMM_PFI, int, int, double, int));
+EXTERN stmm_table *stmm_init_table ARGS ((STMM_PFI, STMM_PFI));
+EXTERN void stmm_free_table ARGS ((stmm_table *));
+EXTERN int stmm_lookup ARGS ((stmm_table *, char *, char **));
+EXTERN int stmm_lookup_int ARGS ((stmm_table *, char *, int *));
+EXTERN int stmm_insert ARGS ((stmm_table *, char *, char *));
+EXTERN int stmm_add_direct ARGS ((stmm_table *, char *, char *));
+EXTERN int stmm_find_or_add ARGS ((stmm_table *, char *, char ***));
+EXTERN int stmm_find ARGS ((stmm_table *, char *, char ***));
+EXTERN stmm_table *stmm_copy ARGS ((stmm_table *));
+EXTERN int stmm_delete ARGS ((stmm_table *, char **, char **));
+EXTERN int stmm_delete_int ARGS ((stmm_table *, long *, char **));
+EXTERN int stmm_foreach ARGS ((stmm_table *, STMM_PFSR, char *));
+EXTERN int stmm_strhash ARGS ((char *, int));
+EXTERN int stmm_numhash ARGS ((char *, int));
+EXTERN int stmm_ptrhash ARGS ((char *, int));
+EXTERN int stmm_numcmp ARGS ((char *, char *));
+EXTERN int stmm_ptrcmp ARGS ((char *, char *));
+EXTERN stmm_generator *stmm_init_gen ARGS ((stmm_table *));
+EXTERN int stmm_gen ARGS ((stmm_generator *, char **, char **));
+EXTERN int stmm_gen_int ARGS ((stmm_generator *, char **, long *));
+EXTERN void stmm_free_gen ARGS ((stmm_generator *));
+// additional functions
+EXTERN void stmm_clean ARGS ((stmm_table *));
+
+
+
+#define STMM_DEFAULT_MAX_DENSITY        5
+#define STMM_DEFAULT_INIT_TABLE_SIZE   11
+#define STMM_DEFAULT_GROW_FACTOR      2.0
+#define STMM_DEFAULT_REORDER_FLAG       0
+
+// added by Zhihong: no need for memory allocation
+#define stmm_foreach_item2(tb, /* stmm_generator */gen, key, value) \
+    for(gen.table=(tb), gen.entry=NULL, gen.index=0; \
+        stmm_gen(&(gen),key,value);)
+
+#define stmm_foreach_item(table, gen, key, value) \
+    for(gen=stmm_init_gen(table); stmm_gen(gen,key,value) || (stmm_free_gen(gen),0);)
+
+#define stmm_foreach_item_int(table, gen, key, value) \
+    for(gen=stmm_init_gen(table); stmm_gen_int(gen,key,value) || (stmm_free_gen(gen),0);)
+
+#define STMM_OUT_OF_MEM -10000
+
+/*
+
+// consider adding these other other similar definitions
+#define st_table       stmm_table
+#define st_insert      stmm_insert
+#define st_delete      stmm_delete
+#define st_lookup      stmm_lookup
+#define st_init_table  stmm_init_table
+#define st_free_table  stmm_free_table
+
+*/
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* STMM_INCLUDED */