Use https links in user-facing startup and error messages
[ghc.git] / rts / Hash.c
index 9c9b2bc..658187b 100644 (file)
 
 #include "Hash.h"
 #include "RtsUtils.h"
+#include "xxhash.h"
 
 #include <string.h>
 
 #define HSEGSIZE    1024    /* Size of a single hash table segment */
-                           /* Also the minimum size of a hash table */
+                            /* Also the minimum size of a hash table */
 #define HDIRSIZE    1024    /* Size of the segment directory */
-                           /* Maximum hash table size is HSEGSIZE * HDIRSIZE */
-#define HLOAD      5       /* Maximum average load of a single hash bucket */
+                            /* Maximum hash table size is HSEGSIZE * HDIRSIZE */
+#define HLOAD       5       /* Maximum average load of a single hash bucket */
 
-#define HCHUNK     (1024 * sizeof(W_) / sizeof(HashList))
-                           /* Number of HashList cells to allocate in one go */
+#define HCHUNK      (1024 * sizeof(W_) / sizeof(HashList))
+                            /* Number of HashList cells to allocate in one go */
 
 
 /* Linked list of (key, data) pairs for separate chaining */
 typedef struct hashlist {
     StgWord key;
-    void *data;
+    const void *data;
     struct hashlist *next;  /* Next cell in bucket chain (same hash value) */
 } HashList;
 
@@ -39,13 +40,13 @@ typedef struct chunklist {
 } HashListChunk;
 
 struct hashtable {
-    int split;             /* Next bucket to split when expanding */
-    int max;               /* Max bucket of smaller table */
-    int mask1;             /* Mask for doing the mod of h_1 (smaller table) */
-    int mask2;             /* Mask for doing the mod of h_2 (larger table) */
-    int kcount;                    /* Number of keys */
-    int bcount;                    /* Number of buckets */
-    HashList **dir[HDIRSIZE];  /* Directory of segments */
+    int split;              /* Next bucket to split when expanding */
+    int max;                /* Max bucket of smaller table */
+    int mask1;              /* Mask for doing the mod of h_1 (smaller table) */
+    int mask2;              /* Mask for doing the mod of h_2 (larger table) */
+    int kcount;             /* Number of keys */
+    int bcount;             /* Number of buckets */
+    HashList **dir[HDIRSIZE];   /* Directory of segments */
     HashList *freeList;         /* free list of HashLists */
     HashListChunk *chunks;
     HashFunction *hash;         /* hash function */
@@ -58,7 +59,7 @@ struct hashtable {
  * -------------------------------------------------------------------------- */
 
 int
-hashWord(HashTable *table, StgWord key)
+hashWord(const HashTable *table, StgWord key)
 {
     int bucket;
 
@@ -69,31 +70,28 @@ hashWord(HashTable *table, StgWord key)
     bucket = key & table->mask1;
 
     if (bucket < table->split) {
-       /* Mod the size of the expanded hash table (also a power of 2) */
-       bucket = key & table->mask2;
+        /* Mod the size of the expanded hash table (also a power of 2) */
+        bucket = key & table->mask2;
     }
     return bucket;
 }
 
 int
-hashStr(HashTable *table, char *key)
+hashStr(const HashTable *table, StgWord w)
 {
-    int h, bucket;
-    char *s;
-
-    s = key;
-    for (h=0; *s; s++) {
-       h *= 128;
-       h += *s;
-       h = h % 1048583;        /* some random large prime */
-    }
+    const char *key = (char*) w;
+#ifdef x86_64_HOST_ARCH
+    StgWord h = XXH64 (key, strlen(key), 1048583);
+#else
+    StgWord h = XXH32 (key, strlen(key), 1048583);
+#endif
 
     /* Mod the size of the hash table (a power of 2) */
-    bucket = h & table->mask1;
+    int 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;
+        /* Mod the size of the expanded hash table (also a power of 2) */
+        bucket = h & table->mask2;
     }
 
     return bucket;
@@ -119,8 +117,8 @@ compareStr(StgWord key1, StgWord key2)
 static void
 allocSegment(HashTable *table, int segment)
 {
-    table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *), 
-                                        "allocSegment");
+    table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *),
+                                         "allocSegment");
 }
 
 
@@ -143,8 +141,8 @@ expand(HashTable *table)
     HashList *old, *new;
 
     if (table->split + table->max >= HDIRSIZE * HSEGSIZE)
-       /* Wow!  That's big.  Too big, so don't expand. */
-       return;
+        /* Wow!  That's big.  Too big, so don't expand. */
+        return;
 
     /* Calculate indices of bucket to split */
     oldsegment = table->split / HSEGSIZE;
@@ -157,13 +155,13 @@ expand(HashTable *table)
     newindex = newbucket % HSEGSIZE;
 
     if (newindex == 0)
-       allocSegment(table, newsegment);
+        allocSegment(table, newsegment);
 
     if (++table->split == table->max) {
-       table->split = 0;
-       table->max *= 2;
-       table->mask1 = table->mask2;
-       table->mask2 = table->mask2 << 1 | 1;
+        table->split = 0;
+        table->max *= 2;
+        table->mask1 = table->mask2;
+        table->mask2 = table->mask2 << 1 | 1;
     }
     table->bcount++;
 
@@ -171,14 +169,14 @@ expand(HashTable *table)
 
     old = new = NULL;
     for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) {
-       next = hl->next;
-       if (table->hash(table, hl->key) == newbucket) {
-           hl->next = new;
-           new = hl;
-       } else {
-           hl->next = old;
-           old = hl;
-       }
+        next = hl->next;
+        if (table->hash(table, hl->key) == newbucket) {
+            hl->next = new;
+            new = hl;
+        } else {
+            hl->next = old;
+            old = hl;
+        }
     }
     table->dir[oldsegment][oldindex] = old;
     table->dir[newsegment][newindex] = new;
@@ -187,7 +185,7 @@ expand(HashTable *table)
 }
 
 void *
-lookupHashTable(HashTable *table, StgWord key)
+lookupHashTable(const HashTable *table, StgWord key)
 {
     int bucket;
     int segment;
@@ -198,14 +196,47 @@ lookupHashTable(HashTable *table, StgWord key)
     segment = bucket / HSEGSIZE;
     index = bucket % HSEGSIZE;
 
-    for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next)
-       if (table->compare(hl->key, key))
-           return hl->data;
+    CompareFunction *cmp = table->compare;
+    for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
+        if (cmp(hl->key, key))
+            return (void *) hl->data;
+    }
 
     /* It's not there */
     return NULL;
 }
 
+// Puts up to szKeys keys of the hash table into the given array. Returns the
+// actual amount of keys that have been retrieved.
+//
+// If the table is modified concurrently, the function behavior is undefined.
+//
+int keysHashTable(HashTable *table, StgWord keys[], int szKeys) {
+    int segment, index;
+    int k = 0;
+    HashList *hl;
+
+
+    /* The last bucket with something in it is table->max + table->split - 1 */
+    segment = (table->max + table->split - 1) / HSEGSIZE;
+    index = (table->max + table->split - 1) % HSEGSIZE;
+
+    while (segment >= 0 && k < szKeys) {
+        while (index >= 0 && k < szKeys) {
+            hl = table->dir[segment][index];
+            while (hl && k < szKeys) {
+                keys[k] = hl->key;
+                k += 1;
+                hl = hl->next;
+            }
+            index--;
+        }
+        segment--;
+        index = HSEGSIZE - 1;
+    }
+    return k;
+}
+
 /* -----------------------------------------------------------------------------
  * We allocate the hashlist cells in large chunks to cut down on malloc
  * overhead.  Although we keep a free list of hashlist cells, we make
@@ -222,15 +253,15 @@ allocHashList (HashTable *table)
         table->freeList = hl->next;
     } else {
         hl = stgMallocBytes(HCHUNK * sizeof(HashList), "allocHashList");
-       cl = stgMallocBytes(sizeof (*cl), "allocHashList: chunkList");
+        cl = stgMallocBytes(sizeof (*cl), "allocHashList: chunkList");
         cl->chunk = hl;
         cl->next = table->chunks;
         table->chunks = cl;
 
         table->freeList = hl + 1;
         for (p = table->freeList; p < hl + HCHUNK - 1; p++)
-           p->next = p + 1;
-       p->next = NULL;
+            p->next = p + 1;
+        p->next = NULL;
     }
     return hl;
 }
@@ -243,7 +274,7 @@ freeHashList (HashTable *table, HashList *hl)
 }
 
 void
-insertHashTable(HashTable *table, StgWord key, void *data)
+insertHashTable(HashTable *table, StgWord key, const void *data)
 {
     int bucket;
     int segment;
@@ -256,7 +287,7 @@ insertHashTable(HashTable *table, StgWord key, void *data)
 
     /* When the average load gets too high, we expand the table */
     if (++table->kcount >= HLOAD * table->bcount)
-       expand(table);
+        expand(table);
 
     bucket = table->hash(table, key);
     segment = bucket / HSEGSIZE;
@@ -272,7 +303,7 @@ insertHashTable(HashTable *table, StgWord key, void *data)
 }
 
 void *
-removeHashTable(HashTable *table, StgWord key, void *data)
+removeHashTable(HashTable *table, StgWord key, const void *data)
 {
     int bucket;
     int segment;
@@ -285,16 +316,16 @@ removeHashTable(HashTable *table, StgWord key, void *data)
     index = bucket % HSEGSIZE;
 
     for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
-       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;
+        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(table,hl);
-           table->kcount--;
-           return hl->data;
-       }
-       prev = hl;
+            table->kcount--;
+            return (void *) hl->data;
+        }
+        prev = hl;
     }
 
     /* It's not there */
@@ -322,17 +353,17 @@ freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
     index = (table->max + table->split - 1) % HSEGSIZE;
 
     while (segment >= 0) {
-       while (index >= 0) {
-           for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
-               next = hl->next;
-               if (freeDataFun != NULL)
-                   (*freeDataFun)(hl->data);
+        while (index >= 0) {
+            for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
+                next = hl->next;
+                if (freeDataFun != NULL)
+                    (*freeDataFun)((void *) hl->data);
             }
-           index--;
-       }
-       stgFree(table->dir[segment]);
-       segment--;
-       index = HSEGSIZE - 1;
+            index--;
+        }
+        stgFree(table->dir[segment]);
+        segment--;
+        index = HSEGSIZE - 1;
     }
     for (cl = table->chunks; cl != NULL; cl = cl_next) {
         cl_next = cl->next;
@@ -343,6 +374,33 @@ freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
 }
 
 /* -----------------------------------------------------------------------------
+ * Map a function over all the keys/values in a HashTable
+ * -------------------------------------------------------------------------- */
+
+void
+mapHashTable(HashTable *table, void *data, MapHashFn fn)
+{
+    long segment;
+    long index;
+    HashList *hl;
+
+    /* The last bucket with something in it is table->max + table->split - 1 */
+    segment = (table->max + table->split - 1) / HSEGSIZE;
+    index = (table->max + table->split - 1) % HSEGSIZE;
+
+    while (segment >= 0) {
+        while (index >= 0) {
+            for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
+                fn(data, hl->key, hl->data);
+            }
+            index--;
+        }
+        segment--;
+        index = HSEGSIZE - 1;
+    }
+}
+
+/* -----------------------------------------------------------------------------
  * When we initialize a hash table, we set up the first segment as well,
  * initializing all of the first segment's hash buckets to NULL.
  * -------------------------------------------------------------------------- */
@@ -358,7 +416,7 @@ allocHashTable_(HashFunction *hash, CompareFunction *compare)
     allocSegment(table, 0);
 
     for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)
-       *hb = NULL;
+        *hb = NULL;
 
     table->split = 0;
     table->max = HSEGSIZE;
@@ -383,8 +441,7 @@ allocHashTable(void)
 HashTable *
 allocStrHashTable(void)
 {
-    return allocHashTable_((HashFunction *)hashStr, 
-                          (CompareFunction *)compareStr);
+    return allocHashTable_(hashStr, compareStr);
 }
 
 void
@@ -392,3 +449,8 @@ exitHashTable(void)
 {
     /* nothing to do */
 }
+
+int keyCountHashTable (HashTable *table)
+{
+    return table->kcount;
+}