diff options
Diffstat (limited to 'st.c')
| -rw-r--r-- | st.c | 177 |
1 files changed, 105 insertions, 72 deletions
@@ -10,6 +10,15 @@ static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; #include <stdlib.h> #endif +typedef struct st_table_entry st_table_entry; + +struct st_table_entry { + unsigned int hash; + char *key; + char *record; + st_table_entry *next; +}; + #define ST_DEFAULT_MAX_DENSITY 5 #define ST_DEFAULT_INIT_TABLE_SIZE 11 @@ -47,8 +56,66 @@ static void rehash(); #define EQUAL(table, x, y) ((*table->type->compare)(x, y) == 0) -#define do_hash(key, table) (*(table)->type->hash)((key), (table)->num_bins) -#define do_hash2(key, table, bins) (*(table)->type->hash)((key), bins) +#define do_hash(key, table) (unsigned int)(*(table)->type->hash)((key)) +#define do_hash_bin(key, table) (do_hash(key, table)%(table)->num_bins) + +/* + * MINSIZE is the minimum size of a dictionary. + */ + +#define MINSIZE 8 + +/* +Table of irreducible polynomials to efficiently cycle through +GF(2^n)-{0}, 2<=n<=30. +*/ +static long polys[] = { + 8 + 3, + 16 + 3, + 32 + 5, + 64 + 3, + 128 + 3, + 256 + 29, + 512 + 17, + 1024 + 9, + 2048 + 5, + 4096 + 83, + 8192 + 27, + 16384 + 43, + 32768 + 3, + 65536 + 45, + 131072 + 9, + 262144 + 39, + 524288 + 39, + 1048576 + 9, + 2097152 + 5, + 4194304 + 3, + 8388608 + 33, + 16777216 + 27, + 33554432 + 9, + 67108864 + 71, + 134217728 + 39, + 268435456 + 9, + 536870912 + 5, + 1073741824 + 83, + 0 +}; + +static int +new_size(size) + int size; +{ + int i, newsize; + + for (i = 0, newsize = MINSIZE; + i < sizeof(polys)/sizeof(polys[0]); + i++, newsize <<= 1) + { + if (newsize > size) return polys[i]; + } + /* Ran out of polynomials */ + return -1; /* should raise exception */ +} st_table* st_init_table_with_size(type, size) @@ -57,17 +124,14 @@ st_init_table_with_size(type, size) { st_table *tbl; - if (size == 0) size = ST_DEFAULT_INIT_TABLE_SIZE; - else size /= ST_DEFAULT_MAX_DENSITY*0.87; - - if (size < ST_DEFAULT_INIT_TABLE_SIZE) - size = ST_DEFAULT_INIT_TABLE_SIZE; + size = new_size(size); /* round up to prime number */ tbl = alloc(st_table); tbl->type = type; tbl->num_entries = 0; tbl->num_bins = size; tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); + return tbl; } @@ -123,13 +187,14 @@ st_free_table(table) free(table); } -#define PTR_NOT_EQUAL(table, ptr, key) \ -(ptr != 0 && !EQUAL(table, key, (ptr)->key)) +#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ +((ptr) != 0 && ptr->hash != (hash_val) && !EQUAL((table), (key), (ptr)->key)) -#define FIND_ENTRY(table, ptr, hash_val) \ -ptr = (table)->bins[hash_val];\ -if (PTR_NOT_EQUAL(table, ptr, key)) {\ - while (PTR_NOT_EQUAL(table, ptr->next, key)) {\ +#define FIND_ENTRY(table, ptr, hash_val, bin_pos) \ +bin_pos = hash_val%(table)->num_bins;\ +ptr = (table)->bins[bin_pos];\ +if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ + while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ ptr = ptr->next;\ }\ ptr = ptr->next;\ @@ -141,12 +206,11 @@ st_lookup(table, key, value) register char *key; char **value; { - int hash_val; + unsigned int hash_val, bin_pos; register st_table_entry *ptr; hash_val = do_hash(key, table); - - FIND_ENTRY(table, ptr, hash_val); + FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) { return 0; @@ -156,19 +220,21 @@ st_lookup(table, key, value) } } -#define ADD_DIRECT(table, key, value, hash_val, tbl)\ +#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ {\ + st_table_entry *tbl;\ if (table->num_entries/table->num_bins > ST_DEFAULT_MAX_DENSITY) {\ rehash(table);\ - hash_val = do_hash(key, table);\ + bin_pos = hash_val % table->num_bins;\ }\ \ tbl = alloc(st_table_entry);\ \ + tbl->hash = hash_val;\ tbl->key = key;\ tbl->record = value;\ - tbl->next = table->bins[hash_val];\ - table->bins[hash_val] = tbl;\ + tbl->next = table->bins[bin_pos];\ + table->bins[bin_pos] = tbl;\ table->num_entries++;\ } @@ -178,16 +244,14 @@ st_insert(table, key, value) register char *key; char *value; { - int hash_val; - st_table_entry *tbl; + unsigned int hash_val, bin_pos; register st_table_entry *ptr; hash_val = do_hash(key, table); - - FIND_ENTRY(table, ptr, hash_val); + FIND_ENTRY(table, ptr, hash_val, bin_pos); if (ptr == 0) { - ADD_DIRECT(table,key,value,hash_val,tbl); + ADD_DIRECT(table, key, value, hash_val, bin_pos); return 0; } else { ptr->record = value; @@ -201,34 +265,12 @@ st_add_direct(table, key, value) char *key; char *value; { - int hash_val; + unsigned int hash_val, bin_pos; st_table_entry *tbl; hash_val = do_hash(key, table); - ADD_DIRECT(table, key, value, hash_val, tbl); -} - -int -st_find_or_add(table, key, slot) - st_table *table; - char *key; - char ***slot; -{ - int hash_val; - st_table_entry *tbl, *ptr; - - hash_val = do_hash(key, table); - - FIND_ENTRY(table, ptr, hash_val); - - if (ptr == 0) { - ADD_DIRECT(table, key, (char*)0, hash_val, tbl) - if (slot != 0) *slot = &tbl->record; - return 0; - } else { - if (slot != 0) *slot = &ptr->record; - return 1; - } + bin_pos = hash_val % table->num_bins; + ADD_DIRECT(table, key, value, hash_val, bin_pos); } static void @@ -236,22 +278,17 @@ rehash(table) register st_table *table; { register st_table_entry *ptr, *next, **new_bins; - int i, old_num_bins = table->num_bins, new_num_bins, hash_val; + int i, old_num_bins = table->num_bins, new_num_bins; + unsigned int hash_val; - new_num_bins = 1.79*old_num_bins; - - if (new_num_bins%2 == 0) { - new_num_bins += 1; - } - - new_bins = (st_table_entry **) - Calloc((unsigned)new_num_bins, sizeof(st_table_entry*)); + new_num_bins = new_size(old_num_bins); + new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); for(i = 0; i < old_num_bins ; i++) { ptr = table->bins[i]; while (ptr != 0) { next = ptr->next; - hash_val = do_hash2(ptr->key, table, new_num_bins); + hash_val = ptr->hash % new_num_bins; ptr->next = new_bins[hash_val]; new_bins[hash_val] = ptr; ptr = next; @@ -309,12 +346,11 @@ st_delete(table, key, value) register char **key; char **value; { - int hash_val; + unsigned int hash_val; st_table_entry *tmp; register st_table_entry *ptr; - hash_val = do_hash(*key, table); - + hash_val = do_hash_bin(*key, table); ptr = table->bins[hash_val]; if (ptr == 0) { @@ -353,11 +389,10 @@ st_delete_safe(table, key, value, never) char **value; char *never; { - int hash_val; + unsigned int hash_val; register st_table_entry *ptr; - hash_val = do_hash(*key, table); - + hash_val = do_hash_bin(*key, table); ptr = table->bins[hash_val]; if (ptr == 0) { @@ -423,9 +458,8 @@ st_foreach(table, func, arg) } static int -strhash(string, modulus) +strhash(string) register char *string; - int modulus; { register int val = 0; register int c; @@ -434,7 +468,7 @@ strhash(string, modulus) val = val*997 + c; } - return ((val < 0) ? -val : val)%modulus; + return val; } static int @@ -445,9 +479,8 @@ numcmp(x, y) } static int -numhash(n, modulus) +numhash(n) int n; - int modulus; { - return n % modulus; + return n; } |