diff options
Diffstat (limited to 'st.c')
-rw-r--r-- | st.c | 202 |
1 files changed, 125 insertions, 77 deletions
@@ -1,21 +1,13 @@ /* This is a general purpose hash table package written by Peter Moore @ UCB. */ static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; -#ifndef lint -static char *rcsid = "$Header: /usr/ext/cvsroot/ruby/st.c,v 1.3 1994/12/09 01:28:33 matz Exp $"; -#endif #include "config.h" #include <stdio.h> #include "st.h" -extern void *xmalloc(); -static void rehash(); - -#define max(a,b) ((a) > (b) ? (a) : (b)) -#define nil(type) ((type *) 0) -#define alloc(type) (type *)xmalloc((unsigned)sizeof(type)) -#define Calloc(n,s) (char *)xcalloc((n),(s)) +#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 @@ -26,47 +18,98 @@ static void rehash(); * allocated initially * */ +static int numcmp(); +static int numhash(); +struct st_hash_type type_numhash = { + numcmp, + numhash, +}; + +extern int strcmp(); +static int strhash(); +struct st_hash_type type_strhash = { + strcmp, + strhash, +}; + +#include "sig.h" + +extern void *xmalloc(); +static void rehash(); + +#define max(a,b) ((a) > (b) ? (a) : (b)) +#define nil(type) ((type*)0) +#define alloc(type) (type*)xmalloc((unsigned)sizeof(type)) +#define Calloc(n,s) (char*)xcalloc((n),(s)) + +static int +call_cmp_func(table, x, y) + st_table *table; + char *x, *y; +{ + int cmp; + + DEFER_INTS; + cmp = (*table->type->compare)(x, y); + ALLOW_INTS; + return cmp; +} + +#define EQUAL(table, x, y) (call_cmp_func((table),(x), (y)) == 0) -#define EQUAL(func, x, y) \ - ((func == ST_NUMCMP) ? ((x) == (y)) : ((*func)((x), (y)) == 0)) +static int +call_hash_func(key, table) + char *key; + st_table *table; +{ + int hash; -/*#define do_hash(key, table) (*table->hash)(key, table->num_bins)*/ + DEFER_INTS; + hash = (*table->type->hash)((key), table->num_bins); + ALLOW_INTS; + return hash; +} -#define do_hash(key, table)\ - ((table->hash == ST_PTRHASH) ? (((int) (key) >> 2) % table->num_bins) :\ - (table->hash == ST_NUMHASH) ? ((int) (key) % table->num_bins) :\ - (*table->hash)((key), table->num_bins)) +#define do_hash(key, table) call_hash_func((key), table) st_table* -st_init_table_with_params(compare, hash, size, density, reorder_flag) - int (*compare)(); - int (*hash)(); +st_init_table_with_size(type, size) + struct st_hash_type *type; int size; - int density; - int reorder_flag; { 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; + tbl = alloc(st_table); - tbl->compare = compare; - tbl->hash = hash; + tbl->type = type; tbl->num_entries = 0; - tbl->max_density = density; - tbl->reorder_flag = reorder_flag; tbl->num_bins = size; - tbl->bins = - (st_table_entry **) Calloc((unsigned)size, sizeof(st_table_entry *)); + tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); return tbl; } st_table* -st_init_table(compare, hash) - int (*compare)(); - int (*hash)(); +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_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE, - ST_DEFAULT_MAX_DENSITY, - ST_DEFAULT_REORDER_FLAG); + return st_init_table(&type_numhash); +} + +st_table* +st_init_strtable() +{ + return st_init_table(&type_strhash); } int @@ -80,32 +123,24 @@ st_free_table(table) ptr = table->bins[i]; while (ptr != nil(st_table_entry)) { next = ptr->next; - free((char *) ptr); + free((char*)ptr); ptr = next; } } - free((char *) table->bins); - free((char *) table); + free((char*)table->bins); + free((char*)table); } -#define PTR_NOT_EQUAL(table, ptr, key)\ -(ptr != nil(st_table_entry) && !EQUAL(table->compare, key, (ptr)->key)) +#define PTR_NOT_EQUAL(table, ptr, key) \ +(ptr != nil(st_table_entry) && !EQUAL(table, key, (ptr)->key)) -#define FIND_ENTRY(table, ptr, hash_val)\ +#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)) {\ ptr = ptr->next;\ }\ - if (ptr->next != nil(st_table_entry) && (table)->reorder_flag) {\ - st_table_entry *_tmp = (ptr)->next;\ - (ptr)->next = (ptr)->next->next;\ - _tmp->next = (table)->bins[hash_val];\ - (table)->bins[hash_val] = _tmp;\ - ptr = _tmp;\ - } else {\ - ptr = ptr->next;\ - }\ + ptr = ptr->next;\ } int @@ -124,16 +159,16 @@ st_lookup(table, key, value) if (ptr == nil(st_table_entry)) { return 0; } else { - if (value != nil(char *)) *value = ptr->record; + if (value != nil(char*)) *value = ptr->record; return 1; } } #define ADD_DIRECT(table, key, value, hash_val, tbl)\ {\ - if (table->num_entries/table->num_bins > table->max_density) {\ + if (table->num_entries/table->num_bins > ST_DEFAULT_MAX_DENSITY) {\ rehash(table);\ - hash_val = do_hash(key,table);\ + hash_val = do_hash(key, table);\ }\ \ tbl = alloc(st_table_entry);\ @@ -195,11 +230,11 @@ st_find_or_add(table, key, slot) FIND_ENTRY(table, ptr, hash_val); if (ptr == nil(st_table_entry)) { - ADD_DIRECT(table, key, (char *)0, hash_val, tbl) - if (slot != nil(char **)) *slot = &tbl->record; + ADD_DIRECT(table, key, (char*)0, hash_val, tbl) + if (slot != nil(char**)) *slot = &tbl->record; return 0; } else { - if (slot != nil(char **)) *slot = &ptr->record; + if (slot != nil(char**)) *slot = &ptr->record; return 1; } } @@ -211,16 +246,15 @@ rehash(table) register st_table_entry *ptr, *next, **old_bins = table->bins; int i, old_num_bins = table->num_bins, hash_val; - table->num_bins = 2*old_num_bins; + table->num_bins = 1.79*old_num_bins; if (table->num_bins%2 == 0) { table->num_bins += 1; } table->num_entries = 0; - table->bins = - (st_table_entry **) Calloc((unsigned) table->num_bins, - sizeof(st_table_entry *)); + table->bins = (st_table_entry **) + Calloc((unsigned)table->num_bins, sizeof(st_table_entry*)); for(i = 0; i < old_num_bins ; i++) { ptr = old_bins[i]; @@ -233,7 +267,7 @@ rehash(table) ptr = next; } } - free((char *) old_bins); + free((char*)old_bins); } st_table* @@ -250,12 +284,11 @@ st_copy(old_table) } *new_table = *old_table; - new_table->bins = - (st_table_entry **) Calloc((unsigned) num_bins, - sizeof(st_table_entry *)); + new_table->bins = (st_table_entry**) + Calloc((unsigned)num_bins, sizeof(st_table_entry*)); - if (new_table->bins == nil(st_table_entry *)) { - free((char *) new_table); + if (new_table->bins == nil(st_table_entry*)) { + free((char*)new_table); return nil(st_table); } @@ -265,8 +298,8 @@ st_copy(old_table) while (ptr != nil(st_table_entry)) { tbl = alloc(st_table_entry); if (tbl == nil(st_table_entry)) { - free((char *) new_table->bins); - free((char *) new_table); + free((char*)new_table->bins); + free((char*)new_table); return nil(st_table); } *tbl = *ptr; @@ -293,27 +326,27 @@ st_delete(table, key, value) ptr = table->bins[hash_val]; if (ptr == nil(st_table_entry)) { - if (value != nil(char *)) *value = nil(char); + if (value != nil(char*)) *value = nil(char); return 0; } - if (EQUAL(table->compare, *key, ptr->key)) { + if (EQUAL(table, *key, ptr->key)) { table->bins[hash_val] = ptr->next; table->num_entries--; - if (value != nil(char *)) *value = ptr->record; + if (value != nil(char*)) *value = ptr->record; *key = ptr->key; - free((char *) ptr); + free((char*)ptr); return 1; } for(; ptr->next != nil(st_table_entry); ptr = ptr->next) { - if (EQUAL(table->compare, ptr->next->key, *key)) { + if (EQUAL(table, ptr->next->key, *key)) { tmp = ptr->next; ptr->next = ptr->next->next; table->num_entries--; - if (value != nil(char *)) *value = tmp->record; + if (value != nil(char*)) *value = tmp->record; *key = tmp->key; - free((char *) tmp); + free((char*)tmp); return 1; } } @@ -350,15 +383,15 @@ st_foreach(table, func, arg) last->next = ptr->next; } ptr = ptr->next; - free((char *) tmp); + free((char*)tmp); table->num_entries--; } } } } -int -st_strhash(string, modulus) +static int +strhash(string, modulus) register char *string; int modulus; { @@ -371,3 +404,18 @@ st_strhash(string, modulus) return ((val < 0) ? -val : val)%modulus; } + +static int +numcmp(x, y) + int x, y; +{ + return x != y; +} + +static int +numhash(n, modulus) + int n; + int modulus; +{ + return n % modulus; +} |