[project @ 2004-02-12 02:04:59 by mthomas]

[ghc-hetmet.git] / ghc / rts / Hash.c

diff --git a/ghc/rts/Hash.c b/ghc/rts/Hash.c
index 96713d8..1083b8a 100644 (file)
--- 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.10 2003/03/25 17:58:47 sof Exp $
  *
  * (c) The AQUA Project, Glasgow University, 1995-1998
  * (c) The GHC Team, 1999
@@ -9,10 +9,14 @@
  * pp. 446 -- 457.
  * -------------------------------------------------------------------------- */
 
+#include "PosixSource.h"
 #include "Rts.h"
 #include "Hash.h"
 #include "RtsUtils.h"
 
+#include <stdlib.h>
+#include <string.h>
+
 #define HSEGSIZE    1024    /* Size of a single hash table segment */
                            /* Also the minimum size of a hash table */
 #define HDIRSIZE    1024    /* Size of the segment directory */
@@ -32,6 +36,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 +47,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 +57,7 @@ struct hashtable {
  * -------------------------------------------------------------------------- */
 
 static int
-hash(HashTable *table, W_ key)
+hashWord(HashTable *table, StgWord key)
 {
     int bucket;
 
@@ -65,6 +74,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 +171,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 +193,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 */
@@ -202,12 +248,12 @@ insertHashTable(HashTable *table, StgWord key, void *data)
 
     /* We want no duplicates */
     ASSERT(lookupHashTable(table, key) == NULL);
-    
+
     /* When the average load gets too high, we expand the table */
     if (++table->kcount >= HLOAD * table->bcount)
        expand(table);
 
-    bucket = hash(table, key);
+    bucket = table->hash(table, key);
     segment = bucket / HSEGSIZE;
     index = bucket % HSEGSIZE;
 
@@ -229,16 +275,17 @@ 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
                prev->next = hl->next;
+           freeHashList(hl);
            table->kcount--;
            return hl->data;
        }
@@ -278,11 +325,11 @@ freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
            }
            index--;
        }
-       free(table->dir[segment]);
+       stgFree(table->dir[segment]);
        segment--;
        index = HSEGSIZE - 1;
     }
-    free(table);
+    stgFree(table);
 }
 
 /* -----------------------------------------------------------------------------
@@ -290,8 +337,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 +356,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);
+}