/*-----------------------------------------------------------------------------
- * $Id: Hash.c,v 1.7 2001/11/26 13:06:49 simonmar Exp $
*
* (c) The AQUA Project, Glasgow University, 1995-1998
* (c) The GHC Team, 1999
#include "Rts.h"
#include "Hash.h"
#include "RtsUtils.h"
-#include "Arena.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 */
HashList **dir[HDIRSIZE]; /* Directory of segments */
HashFunction *hash; /* hash function */
CompareFunction *compare; /* key comparison function */
- Arena *arena;
};
/* -----------------------------------------------------------------------------
"allocSegment");
}
+
/* -----------------------------------------------------------------------------
* Expand the larger hash table by one bucket, and split one bucket
* from the smaller table into two parts. Only the bucket referenced
return NULL;
}
+/* -----------------------------------------------------------------------------
+ * 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
+ * no effort to actually return the space to the malloc arena.
+ * -------------------------------------------------------------------------- */
+
+static HashList *freeList = NULL;
+
+static HashList *
+allocHashList(void)
+{
+ HashList *hl, *p;
+
+ if ((hl = freeList) != NULL) {
+ freeList = hl->next;
+ } else {
+ hl = stgMallocBytes(HCHUNK * sizeof(HashList), "allocHashList");
+
+ freeList = hl + 1;
+ for (p = freeList; p < hl + HCHUNK - 1; p++)
+ p->next = p + 1;
+ p->next = NULL;
+ }
+ return hl;
+}
+
+static void
+freeHashList(HashList *hl)
+{
+ hl->next = freeList;
+ freeList = hl;
+}
+
void
insertHashTable(HashTable *table, StgWord key, void *data)
{
int index;
HashList *hl;
- /* We want no duplicates */
- ASSERT(lookupHashTable(table, key) == NULL);
+ // Disable this assert; sometimes it's useful to be able to
+ // overwrite entries in the hash table.
+ // ASSERT(lookupHashTable(table, key) == NULL);
/* When the average load gets too high, we expand the table */
if (++table->kcount >= HLOAD * table->bcount)
segment = bucket / HSEGSIZE;
index = bucket % HSEGSIZE;
- hl = arenaAlloc(table->arena, sizeof(struct hashlist));
+ hl = allocHashList();
hl->key = key;
hl->data = data;
table->dir[segment][index] = hl->next;
else
prev->next = hl->next;
+ freeHashList(hl);
table->kcount--;
return hl->data;
}
* -------------------------------------------------------------------------- */
void
-freeHashTable( HashTable *table, void (*freeDataFun)(void *) )
+freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
{
long segment;
long index;
/* 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) {
- if (freeDataFun != NULL) {
- while (index >= 0) {
- for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
- next = hl->next;
+ while (index >= 0) {
+ for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
+ next = hl->next;
+ if (freeDataFun != NULL)
(*freeDataFun)(hl->data);
- }
- index--;
+ freeHashList(hl);
}
+ index--;
}
- free(table->dir[segment]);
+ stgFree(table->dir[segment]);
segment--;
index = HSEGSIZE - 1;
}
-
- arenaFree(table->arena);
- free(table);
+ stgFree(table);
}
/* -----------------------------------------------------------------------------
table = stgMallocBytes(sizeof(HashTable),"allocHashTable");
- table->arena = newArena();
-
allocSegment(table, 0);
for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)