diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-30 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-30 08:01:00 -0700 |
commit | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (patch) | |
tree | de3ffe87c3e17950351e3b7d97fa18318bd5ea9a /src/misc/st | |
parent | 7d7e60f2dc84393cd4c5db22d2eaf7b1fb1a79b2 (diff) | |
download | abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.tar.gz abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.tar.bz2 abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.zip |
Version abc70930
Diffstat (limited to 'src/misc/st')
-rw-r--r-- | src/misc/st/module.make | 2 | ||||
-rw-r--r-- | src/misc/st/st.c | 625 | ||||
-rw-r--r-- | src/misc/st/st.h | 96 | ||||
-rw-r--r-- | src/misc/st/stmm.c | 688 | ||||
-rw-r--r-- | src/misc/st/stmm.h | 127 |
5 files changed, 0 insertions, 1538 deletions
diff --git a/src/misc/st/module.make b/src/misc/st/module.make deleted file mode 100644 index 33e442c0..00000000 --- a/src/misc/st/module.make +++ /dev/null @@ -1,2 +0,0 @@ -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 deleted file mode 100644 index 872fe51b..00000000 --- a/src/misc/st/st.c +++ /dev/null @@ -1,625 +0,0 @@ -/* - * 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 deleted file mode 100644 index b15f3c83..00000000 --- a/src/misc/st/st.h +++ /dev/null @@ -1,96 +0,0 @@ -/* - * 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 deleted file mode 100644 index 8dfacfe4..00000000 --- a/src/misc/st/stmm.c +++ /dev/null @@ -1,688 +0,0 @@ -/* - * 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 deleted file mode 100644 index 4330416e..00000000 --- a/src/misc/st/stmm.h +++ /dev/null @@ -1,127 +0,0 @@ -/* - * 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 */ |