From c4ec36d6a2886b30f932276c6db5430f8d739ad6 Mon Sep 17 00:00:00 2001 From: simonmar Date: Fri, 6 Oct 2000 15:34:29 +0000 Subject: [PATCH] [project @ 2000-10-06 15:34:29 by simonmar] Extend the hash table implementation to support string-indexed dynamic hash tables. --- ghc/rts/Hash.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++-------- ghc/rts/Hash.h | 24 +++++++++++++++--- 2 files changed, 88 insertions(+), 13 deletions(-) diff --git a/ghc/rts/Hash.c b/ghc/rts/Hash.c index 96713d8..e1cc0a3 100644 --- a/ghc/rts/Hash.c +++ b/ghc/rts/Hash.c @@ -1,5 +1,5 @@ /*----------------------------------------------------------------------------- - * $Id: Hash.c,v 1.1 1999/01/27 12:11:25 simonm Exp $ + * $Id: Hash.c,v 1.2 2000/10/06 15:34:29 simonmar Exp $ * * (c) The AQUA Project, Glasgow University, 1995-1998 * (c) The GHC Team, 1999 @@ -32,6 +32,9 @@ struct hashlist { typedef struct hashlist HashList; +typedef int HashFunction(HashTable *table, StgWord key); +typedef int CompareFunction(StgWord key1, StgWord key2); + struct hashtable { int split; /* Next bucket to split when expanding */ int max; /* Max bucket of smaller table */ @@ -40,6 +43,8 @@ struct hashtable { int kcount; /* Number of keys */ int bcount; /* Number of buckets */ HashList **dir[HDIRSIZE]; /* Directory of segments */ + HashFunction *hash; /* hash function */ + CompareFunction *compare; /* key comparison function */ }; /* ----------------------------------------------------------------------------- @@ -48,7 +53,7 @@ struct hashtable { * -------------------------------------------------------------------------- */ static int -hash(HashTable *table, W_ key) +hashWord(HashTable *table, StgWord key) { int bucket; @@ -65,6 +70,43 @@ hash(HashTable *table, W_ key) return bucket; } +static int +hashStr(HashTable *table, char *key) +{ + int h, bucket; + char *s; + + s = key; + for (h=0; *s; s++) { + h *= 128; + h += *s; + h = h % 1048583; /* some random large prime */ + } + + /* Mod the size of the hash table (a power of 2) */ + bucket = h & table->mask1; + + if (bucket < table->split) { + /* Mod the size of the expanded hash table (also a power of 2) */ + bucket = h & table->mask2; + } + + return bucket; +} + +static int +compareWord(StgWord key1, StgWord key2) +{ + return (key1 == key2); +} + +static int +compareStr(StgWord key1, StgWord key2) +{ + return (strcmp((char *)key1, (char *)key2) == 0); +} + + /* ----------------------------------------------------------------------------- * Allocate a new segment of the dynamically growing hash table. * -------------------------------------------------------------------------- */ @@ -125,7 +167,7 @@ expand(HashTable *table) old = new = NULL; for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) { next = hl->next; - if (hash(table, hl->key) == newbucket) { + if (table->hash(table, hl->key) == newbucket) { hl->next = new; new = hl; } else { @@ -147,12 +189,12 @@ lookupHashTable(HashTable *table, StgWord key) int index; HashList *hl; - bucket = hash(table, key); + bucket = table->hash(table, key); segment = bucket / HSEGSIZE; index = bucket % HSEGSIZE; for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) - if (hl->key == key) + if (table->compare(hl->key, key)) return hl->data; /* It's not there */ @@ -207,7 +249,7 @@ insertHashTable(HashTable *table, StgWord key, void *data) if (++table->kcount >= HLOAD * table->bcount) expand(table); - bucket = hash(table, key); + bucket = table->hash(table, key); segment = bucket / HSEGSIZE; index = bucket % HSEGSIZE; @@ -229,12 +271,12 @@ removeHashTable(HashTable *table, StgWord key, void *data) HashList *hl; HashList *prev = NULL; - bucket = hash(table, key); + bucket = table->hash(table, key); segment = bucket / HSEGSIZE; index = bucket % HSEGSIZE; for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) { - if (hl->key == key && (data == NULL || hl->data == data)) { + if (table->compare(hl->key,key) && (data == NULL || hl->data == data)) { if (prev == NULL) table->dir[segment][index] = hl->next; else @@ -290,8 +332,8 @@ freeHashTable(HashTable *table, void (*freeDataFun)(void *) ) * initializing all of the first segment's hash buckets to NULL. * -------------------------------------------------------------------------- */ -HashTable * -allocHashTable(void) +static HashTable * +allocHashTable_(HashFunction *hash, CompareFunction *compare) { HashTable *table; HashList **hb; @@ -309,6 +351,21 @@ allocHashTable(void) table->mask2 = 2 * HSEGSIZE - 1; table->kcount = 0; table->bcount = HSEGSIZE; + table->hash = hash; + table->compare = compare; return table; } + +HashTable * +allocHashTable(void) +{ + return allocHashTable_(hashWord, compareWord); +} + +HashTable * +allocStrHashTable(void) +{ + return allocHashTable_((HashFunction *)hashStr, + (CompareFunction *)compareStr); +} diff --git a/ghc/rts/Hash.h b/ghc/rts/Hash.h index 74ff321..a946bb9 100644 --- a/ghc/rts/Hash.h +++ b/ghc/rts/Hash.h @@ -1,5 +1,5 @@ /*----------------------------------------------------------------------------- - * $Id: Hash.h,v 1.2 2000/01/13 14:34:03 hwloidl Exp $ + * $Id: Hash.h,v 1.3 2000/10/06 15:34:29 simonmar Exp $ * * (c) The GHC Team, 1999 * @@ -9,9 +9,27 @@ typedef struct hashtable HashTable; /* abstract */ +/* Hash table access where the keys are StgWords */ +HashTable * allocHashTable ( void ); void * lookupHashTable ( HashTable *table, StgWord key ); void insertHashTable ( HashTable *table, StgWord key, void *data ); void * removeHashTable ( HashTable *table, StgWord key, void *data ); -void freeHashTable ( HashTable *table, void (*freeDataFun)(void *) ); -HashTable * allocHashTable ( void ); +/* Hash table access where the keys are C strings (the strings are + * assumed to be allocated by the caller, and mustn't be deallocated + * until the corresponding hash table entry has been removed). + */ +HashTable * allocStrHashTable ( void ); + +#define lookupStrHashTable(table, key) \ + (lookupHashTable(table, (StgWord)key)) + +#define insertStrHashTable(table, key, data) \ + (insertHashTable(table, (StgWord)key, data)) + +#define removeStrHashTable(table, key, data) \ + (removeHashTable(table, (StgWord)key, data)) + +/* Freeing hash tables + */ +void freeHashTable ( HashTable *table, void (*freeDataFun)(void *) ); -- 1.7.10.4