summaryrefslogtreecommitdiffstats
path: root/abc70930/src/misc/st/st.c
diff options
context:
space:
mode:
Diffstat (limited to 'abc70930/src/misc/st/st.c')
-rw-r--r--abc70930/src/misc/st/st.c625
1 files changed, 625 insertions, 0 deletions
diff --git a/abc70930/src/misc/st/st.c b/abc70930/src/misc/st/st.c
new file mode 100644
index 00000000..872fe51b
--- /dev/null
+++ b/abc70930/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);
+}