From 84d73314a79384e99f8b3490f97868ee81bf1146 Mon Sep 17 00:00:00 2001 From: "(no author)" <(no author)@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> Date: Wed, 20 Jan 1999 04:59:39 +0000 Subject: This commit was manufactured by cvs2svn to create branch 'ruby_1_3'. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_3@375 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- st.c | 483 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 483 insertions(+) create mode 100644 st.c (limited to 'st.c') diff --git a/st.c b/st.c new file mode 100644 index 0000000000..8c0a3861f5 --- /dev/null +++ b/st.c @@ -0,0 +1,483 @@ +/* This is a general purpose hash table package written by Peter Moore @ UCB. */ + +static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; + +#include "config.h" +#include +#include "st.h" + +#ifdef USE_CWGUSI +#include +#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 + + /* + * DEFAULT_MAX_DENSITY is the default for the largest we allow the + * average number of items per bin before increasing the number of + * bins + * + * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins + * allocated initially + * + */ +static int numcmp(); +static int numhash(); +static struct st_hash_type type_numhash = { + numcmp, + numhash, +}; + +extern int strcmp(); +static int strhash(); +static struct st_hash_type type_strhash = { + strcmp, + strhash, +}; + +void *xmalloc(); +void *xcalloc(); +void *xrealloc(); +static void rehash(); + +#define alloc(type) (type*)xmalloc((unsigned)sizeof(type)) +#define Calloc(n,s) (char*)xcalloc((n),(s)) + +#define EQUAL(table, x, y) ((*table->type->compare)(x, y) == 0) + +#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 prime numbers 2^n+a, 2<=n<=30. +*/ +static long primes[] = { + 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(primes)/sizeof(primes[0]); + i++, newsize <<= 1) + { + if (newsize > size) return primes[i]; + } + /* Ran out of polynomials */ + return -1; /* should raise exception */ +} + +st_table* +st_init_table_with_size(type, size) + struct st_hash_type *type; + int size; +{ + st_table *tbl; + + 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; +} + +st_table* +st_init_table(type) + struct st_hash_type *type; +{ + return st_init_table_with_size(type, 0); +} + +st_table* +st_init_numtable() +{ + return st_init_table(&type_numhash); +} + +st_table* +st_init_numtable_with_size(size) + int size; +{ + return st_init_table_with_size(&type_numhash, size); +} + +st_table* +st_init_strtable() +{ + return st_init_table(&type_strhash); +} + +st_table* +st_init_strtable_with_size(size) + int size; +{ + return st_init_table_with_size(&type_strhash, size); +} + +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 != 0) { + next = ptr->next; + free(ptr); + ptr = next; + } + } + free(table->bins); + free(table); +} + +#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, 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;\ +} + +int +st_lookup(table, key, value) + st_table *table; + register char *key; + char **value; +{ + unsigned int hash_val, bin_pos; + register st_table_entry *ptr; + + hash_val = do_hash(key, table); + FIND_ENTRY(table, ptr, hash_val, bin_pos); + + if (ptr == 0) { + return 0; + } else { + if (value != 0) *value = ptr->record; + return 1; + } +} + +#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);\ + 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[bin_pos];\ + table->bins[bin_pos] = tbl;\ + table->num_entries++;\ +} + +int +st_insert(table, key, value) + register st_table *table; + register char *key; + char *value; +{ + unsigned int hash_val, bin_pos; + register st_table_entry *ptr; + + hash_val = do_hash(key, table); + FIND_ENTRY(table, ptr, hash_val, bin_pos); + + if (ptr == 0) { + ADD_DIRECT(table, key, value, hash_val, bin_pos); + return 0; + } else { + ptr->record = value; + return 1; + } +} + +void +st_add_direct(table, key, value) + st_table *table; + char *key; + char *value; +{ + unsigned int hash_val, bin_pos; + + hash_val = do_hash(key, table); + bin_pos = hash_val % table->num_bins; + ADD_DIRECT(table, key, value, hash_val, bin_pos); +} + +static void +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; + unsigned int hash_val; + + 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 = ptr->hash % new_num_bins; + ptr->next = new_bins[hash_val]; + new_bins[hash_val] = ptr; + ptr = next; + } + } + free(table->bins); + table->num_bins = new_num_bins; + table->bins = new_bins; +} + +st_table* +st_copy(old_table) + st_table *old_table; +{ + st_table *new_table; + st_table_entry *ptr, *tbl; + int i, num_bins = old_table->num_bins; + + new_table = alloc(st_table); + if (new_table == 0) { + return 0; + } + + *new_table = *old_table; + new_table->bins = (st_table_entry**) + Calloc((unsigned)num_bins, sizeof(st_table_entry*)); + + if (new_table->bins == 0) { + free(new_table); + return 0; + } + + for(i = 0; i < num_bins ; i++) { + new_table->bins[i] = 0; + ptr = old_table->bins[i]; + while (ptr != 0) { + tbl = alloc(st_table_entry); + if (tbl == 0) { + free(new_table->bins); + free(new_table); + return 0; + } + *tbl = *ptr; + tbl->next = new_table->bins[i]; + new_table->bins[i] = tbl; + ptr = ptr->next; + } + } + return new_table; +} + +int +st_delete(table, key, value) + register st_table *table; + register char **key; + char **value; +{ + unsigned int hash_val; + st_table_entry *tmp; + register st_table_entry *ptr; + + hash_val = do_hash_bin(*key, table); + ptr = table->bins[hash_val]; + + if (ptr == 0) { + if (value != 0) *value = 0; + return 0; + } + + if (EQUAL(table, *key, ptr->key)) { + table->bins[hash_val] = ptr->next; + table->num_entries--; + if (value != 0) *value = ptr->record; + *key = ptr->key; + free(ptr); + return 1; + } + + for(; ptr->next != 0; ptr = ptr->next) { + if (EQUAL(table, ptr->next->key, *key)) { + tmp = ptr->next; + ptr->next = ptr->next->next; + table->num_entries--; + if (value != 0) *value = tmp->record; + *key = tmp->key; + free(tmp); + return 1; + } + } + + return 0; +} + +int +st_delete_safe(table, key, value, never) + register st_table *table; + register char **key; + char **value; + char *never; +{ + unsigned int hash_val; + register st_table_entry *ptr; + + hash_val = do_hash_bin(*key, table); + ptr = table->bins[hash_val]; + + if (ptr == 0) { + if (value != 0) *value = 0; + return 0; + } + + if (EQUAL(table, *key, ptr->key)) { + table->num_entries--; + *key = ptr->key; + if (value != 0) *value = ptr->record; + ptr->key = ptr->record = never; + return 1; + } + + for(; ptr->next != 0; ptr = ptr->next) { + if (EQUAL(table, ptr->next->key, *key)) { + table->num_entries--; + *key = ptr->key; + if (value != 0) *value = ptr->record; + ptr->key = ptr->record = never; + return 1; + } + } + + return 0; +} + +void +st_foreach(table, func, arg) + st_table *table; + enum st_retval (*func)(); + char *arg; +{ + st_table_entry *ptr, *last, *tmp; + enum st_retval retval; + int i; + + for(i = 0; i < table->num_bins; i++) { + last = 0; + for(ptr = table->bins[i]; ptr != 0;) { + retval = (*func)(ptr->key, ptr->record, arg); + switch (retval) { + case ST_CONTINUE: + last = ptr; + ptr = ptr->next; + break; + case ST_STOP: + return; + case ST_DELETE: + tmp = ptr; + if (last == 0) { + table->bins[i] = ptr->next; + } else { + last->next = ptr->next; + } + ptr = ptr->next; + free(tmp); + table->num_entries--; + } + } + } +} + +static int +strhash(string) + register char *string; +{ + register int val = 0; + register int c; + + while ((c = *string++) != '\0') { + val = val*997 + c; + } + + return val; +} + +static int +numcmp(x, y) + int x, y; +{ + return x != y; +} + +static int +numhash(n) + int n; +{ + return n; +} -- cgit v1.2.3