From 888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 29 Jul 2005 08:01:00 -0700 Subject: Version abc50729 --- src/misc/st/module.make | 2 + src/misc/st/st.c | 606 ++++++++++++++++++++++++++++++++++++++++++ src/misc/st/st.h | 88 +++++++ src/misc/st/stmm.c | 683 ++++++++++++++++++++++++++++++++++++++++++++++++ src/misc/st/stmm.h | 119 +++++++++ 5 files changed, 1498 insertions(+) create mode 100644 src/misc/st/module.make create mode 100644 src/misc/st/st.c create mode 100644 src/misc/st/st.h create mode 100644 src/misc/st/stmm.c create mode 100644 src/misc/st/stmm.h (limited to 'src/misc/st') 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..13e9bd6a --- /dev/null +++ b/src/misc/st/st.c @@ -0,0 +1,606 @@ +/* + * Revision Control Information + * + * /projects/hsis/CVS/utilities/st/st.c,v + * serdar + * 1.1 + * 1993/07/29 01:00:13 + * + */ +#include +#include "util.h" +#include "st.h" + +#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) +#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 == NIL(st_table)) { + return NIL(st_table); + } + 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 == NIL(st_table_entry *)) { + FREE(new); + return NIL(st_table); + } + 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 != NIL(st_table_entry)) { + next = ptr->next; + FREE(ptr); + ptr = next; + } + } + FREE(table->bins); + FREE(table); +} + +#define PTR_NOT_EQUAL(table, ptr, user_key)\ +(ptr != NIL(st_table_entry) && !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) != NIL(st_table_entry) && (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 == NIL(st_table_entry)) { + return 0; + } else { + if (value != NIL(char *)) { + *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 == NIL(st_table_entry)) { + return 0; + } else { + if (value != NIL(int)) { + *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 == NIL(st_table_entry)) { + 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 == NIL(st_table_entry)) { + 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 == NIL(st_table_entry)) { + 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 == NIL(st_table_entry)) { + 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 == NIL(st_table_entry)) { + 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 != NIL(char **)) *slot = &new->record; + return 0; + } else { + if (slot != NIL(char **)) *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 == NIL(st_table_entry)) { + return 0; + } else { + if (slot != NIL(char **)) { + *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 == NIL(st_table_entry *)) { + 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 != NIL(st_table_entry)) { + 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 == NIL(st_table)) { + return NIL(st_table); + } + + *new_table = *old_table; + new_table->bins = ALLOC(st_table_entry *, num_bins); + if (new_table->bins == NIL(st_table_entry *)) { + FREE(new_table); + return NIL(st_table); + } + for(i = 0; i < num_bins ; i++) { + new_table->bins[i] = NIL(st_table_entry); + ptr = old_table->bins[i]; + while (ptr != NIL(st_table_entry)) { + new = ALLOC(st_table_entry, 1); + if (new == NIL(st_table_entry)) { + for (j = 0; j <= i; j++) { + newptr = new_table->bins[j]; + while (newptr != NIL(st_table_entry)) { + next = newptr->next; + FREE(newptr); + newptr = next; + } + } + FREE(new_table->bins); + FREE(new_table); + return NIL(st_table); + } + *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 == NIL(st_table_entry)) { + return 0; + } + + *last = ptr->next; + if (value != NIL(char *)) *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 == NIL(st_table_entry)) { + return 0; + } + + *last = ptr->next; + if (value != NIL(char *)) *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 != NIL(st_table_entry)) { + 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 == NIL(st_generator)) { + return NIL(st_generator); + } + gen->table = table; + gen->entry = NIL(st_table_entry); + 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 == NIL(st_table_entry)) { + /* try to find next entry */ + for(i = gen->index; i < gen->table->num_bins; i++) { + if (gen->table->bins[i] != NIL(st_table_entry)) { + gen->index = i+1; + gen->entry = gen->table->bins[i]; + break; + } + } + if (gen->entry == NIL(st_table_entry)) { + 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 == NIL(st_table_entry)) { + /* try to find next entry */ + for(i = gen->index; i < gen->table->num_bins; i++) { + if (gen->table->bins[i] != NIL(st_table_entry)) { + gen->index = i+1; + gen->entry = gen->table->bins[i]; + break; + } + } + if (gen->entry == NIL(st_table_entry)) { + return 0; /* that's all folks ! */ + } + } + *key_p = gen->entry->key; + if (value_p != NIL(long)) { + *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..c51873e9 --- /dev/null +++ b/src/misc/st/st.h @@ -0,0 +1,88 @@ +/* + * 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 + +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 ARGS((ST_PFI, ST_PFI, int, int, double, int)); +EXTERN st_table *st_init_table ARGS((ST_PFI, ST_PFI)); +EXTERN void st_free_table ARGS((st_table *)); +EXTERN int st_lookup ARGS((st_table *, char *, char **)); +EXTERN int st_lookup_int ARGS((st_table *, char *, int *)); +EXTERN int st_insert ARGS((st_table *, char *, char *)); +EXTERN int st_add_direct ARGS((st_table *, char *, char *)); +EXTERN int st_find_or_add ARGS((st_table *, char *, char ***)); +EXTERN int st_find ARGS((st_table *, char *, char ***)); +EXTERN st_table *st_copy ARGS((st_table *)); +EXTERN int st_delete ARGS((st_table *, char **, char **)); +EXTERN int st_delete_int ARGS((st_table *, long *, char **)); +EXTERN int st_foreach ARGS((st_table *, ST_PFSR, char *)); +EXTERN int st_strhash ARGS((char *, int)); +EXTERN int st_numhash ARGS((char *, int)); +EXTERN int st_ptrhash ARGS((char *, int)); +EXTERN int st_numcmp ARGS((char *, char *)); +EXTERN int st_ptrcmp ARGS((char *, char *)); +EXTERN st_generator *st_init_gen ARGS((st_table *)); +EXTERN int st_gen ARGS((st_generator *, char **, char **)); +EXTERN int st_gen_int ARGS((st_generator *, char **, long *)); +EXTERN void st_free_gen ARGS((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 + +#endif /* ST_INCLUDED */ diff --git a/src/misc/st/stmm.c b/src/misc/st/stmm.c new file mode 100644 index 00000000..b75b0134 --- /dev/null +++ b/src/misc/st/stmm.c @@ -0,0 +1,683 @@ +/* + * Revision Control Information + * + * /projects/hsis/CVS/utilities/st/st.c,v + * serdar + * 1.1 + * 1993/07/29 01:00:13 + * + */ +#include +#include "util.h" +#include "stmm.h" + +#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) +#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 == NIL (stmm_table)) { + return NIL (stmm_table); + } + 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 == NIL (stmm_table_entry *)) { + FREE (new); + return NIL (stmm_table); + } + 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 != NIL( stmm_table_entry ) ) + { + 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, 0); + 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 != NIL(stmm_table_entry) && !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) != NIL(stmm_table_entry) && (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 == NIL (stmm_table_entry)) { + return 0; + } + else { + if (value != NIL (char *)) + { + *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 == NIL (stmm_table_entry)) { + return 0; + } + else { + if (value != NIL (int)) + { + *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 == NIL (stmm_table_entry)) { + 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 == NIL (stmm_table_entry)) { + 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 == NIL (stmm_table_entry)) { + 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 == NIL (stmm_table_entry)) { + 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 == NIL (stmm_table_entry)) { + 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 != NIL (char **)) + *slot = &new->record; + return 0; + } + else { + if (slot != NIL (char **)) + *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 == NIL (stmm_table_entry)) { + return 0; + } + else { + if (slot != NIL (char **)) + { + *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 == NIL (stmm_table_entry *)) { + 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 != NIL (stmm_table_entry)) { + 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 == NIL (stmm_table)) { + return NIL (stmm_table); + } + + *new_table = *old_table; + new_table->bins = ALLOC (stmm_table_entry *, num_bins); + if (new_table->bins == NIL (stmm_table_entry *)) { + FREE (new_table); + return NIL (stmm_table); + } + + // 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] = NIL (stmm_table_entry); + ptr = old_table->bins[i]; + while (ptr != NIL (stmm_table_entry)) { +// new = ALLOC( stmm_table_entry, 1 ); + new = + (stmm_table_entry *) Extra_MmFixedEntryFetch (new_table-> + pMemMan); + + if (new == NIL (stmm_table_entry)) { +/* + for ( j = 0; j <= i; j++ ) + { + newptr = new_table->bins[j]; + while ( newptr != NIL( stmm_table_entry ) ) + { + next = newptr->next; + FREE( newptr ); + newptr = next; + } + } +*/ + Extra_MmFixedStop (new_table->pMemMan, 0); + + FREE (new_table->bins); + FREE (new_table); + return NIL (stmm_table); + } + *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 == NIL (stmm_table_entry)) { + return 0; + } + + *last = ptr->next; + if (value != NIL (char *)) + *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 == NIL (stmm_table_entry)) { + return 0; + } + + *last = ptr->next; + if (value != NIL (char *)) + *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 != NIL (stmm_table_entry)) { + 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 == NIL (stmm_generator)) { + return NIL (stmm_generator); + } + gen->table = table; + gen->entry = NIL (stmm_table_entry); + 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 == NIL (stmm_table_entry)) { + /* try to find next entry */ + for (i = gen->index; i < gen->table->num_bins; i++) { + if (gen->table->bins[i] != NIL (stmm_table_entry)) { + gen->index = i + 1; + gen->entry = gen->table->bins[i]; + break; + } + } + if (gen->entry == NIL (stmm_table_entry)) { + 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 == NIL (stmm_table_entry)) { + /* try to find next entry */ + for (i = gen->index; i < gen->table->num_bins; i++) { + if (gen->table->bins[i] != NIL (stmm_table_entry)) { + gen->index = i + 1; + gen->entry = gen->table->bins[i]; + break; + } + } + if (gen->entry == NIL (stmm_table_entry)) { + return 0; /* that's all folks ! */ + } + } + *key_p = gen->entry->key; + if (value_p != NIL (long)) + { + *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..1fe3dfd2 --- /dev/null +++ b/src/misc/st/stmm.h @@ -0,0 +1,119 @@ +/* + * 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 + +#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=NIL(stmm_table_entry), 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 + +*/ + +#endif /* STMM_INCLUDED */ -- cgit v1.2.3