1 /*-----------------------------------------------------------------------------
2 * $Id: Hash.c,v 1.7 2001/11/26 13:06:49 simonmar Exp $
4 * (c) The AQUA Project, Glasgow University, 1995-1998
5 * (c) The GHC Team, 1999
7 * Dynamically expanding linear hash tables, as described in
8 * Per-\AAke Larson, ``Dynamic Hash Tables,'' CACM 31(4), April 1988,
10 * -------------------------------------------------------------------------- */
12 #include "PosixSource.h"
18 #define HSEGSIZE 1024 /* Size of a single hash table segment */
19 /* Also the minimum size of a hash table */
20 #define HDIRSIZE 1024 /* Size of the segment directory */
21 /* Maximum hash table size is HSEGSIZE * HDIRSIZE */
22 #define HLOAD 5 /* Maximum average load of a single hash bucket */
24 #define HCHUNK (1024 * sizeof(W_) / sizeof(HashList))
25 /* Number of HashList cells to allocate in one go */
28 /* Linked list of (key, data) pairs for separate chaining */
32 struct hashlist *next; /* Next cell in bucket chain (same hash value) */
35 typedef struct hashlist HashList;
37 typedef int HashFunction(HashTable *table, StgWord key);
38 typedef int CompareFunction(StgWord key1, StgWord key2);
41 int split; /* Next bucket to split when expanding */
42 int max; /* Max bucket of smaller table */
43 int mask1; /* Mask for doing the mod of h_1 (smaller table) */
44 int mask2; /* Mask for doing the mod of h_2 (larger table) */
45 int kcount; /* Number of keys */
46 int bcount; /* Number of buckets */
47 HashList **dir[HDIRSIZE]; /* Directory of segments */
48 HashFunction *hash; /* hash function */
49 CompareFunction *compare; /* key comparison function */
53 /* -----------------------------------------------------------------------------
54 * Hash first using the smaller table. If the bucket is less than the
55 * next bucket to be split, re-hash using the larger table.
56 * -------------------------------------------------------------------------- */
59 hashWord(HashTable *table, StgWord key)
63 /* Strip the boring zero bits */
64 key /= sizeof(StgWord);
66 /* Mod the size of the hash table (a power of 2) */
67 bucket = key & table->mask1;
69 if (bucket < table->split) {
70 /* Mod the size of the expanded hash table (also a power of 2) */
71 bucket = key & table->mask2;
77 hashStr(HashTable *table, char *key)
86 h = h % 1048583; /* some random large prime */
89 /* Mod the size of the hash table (a power of 2) */
90 bucket = h & table->mask1;
92 if (bucket < table->split) {
93 /* Mod the size of the expanded hash table (also a power of 2) */
94 bucket = h & table->mask2;
101 compareWord(StgWord key1, StgWord key2)
103 return (key1 == key2);
107 compareStr(StgWord key1, StgWord key2)
109 return (strcmp((char *)key1, (char *)key2) == 0);
113 /* -----------------------------------------------------------------------------
114 * Allocate a new segment of the dynamically growing hash table.
115 * -------------------------------------------------------------------------- */
118 allocSegment(HashTable *table, int segment)
120 table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *),
124 /* -----------------------------------------------------------------------------
125 * Expand the larger hash table by one bucket, and split one bucket
126 * from the smaller table into two parts. Only the bucket referenced
127 * by @table->split@ is affected by the expansion.
128 * -------------------------------------------------------------------------- */
131 expand(HashTable *table)
142 if (table->split + table->max >= HDIRSIZE * HSEGSIZE)
143 /* Wow! That's big. Too big, so don't expand. */
146 /* Calculate indices of bucket to split */
147 oldsegment = table->split / HSEGSIZE;
148 oldindex = table->split % HSEGSIZE;
150 newbucket = table->max + table->split;
152 /* And the indices of the new bucket */
153 newsegment = newbucket / HSEGSIZE;
154 newindex = newbucket % HSEGSIZE;
157 allocSegment(table, newsegment);
159 if (++table->split == table->max) {
162 table->mask1 = table->mask2;
163 table->mask2 = table->mask2 << 1 | 1;
167 /* Split the bucket, paying no attention to the original order */
170 for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) {
172 if (table->hash(table, hl->key) == newbucket) {
180 table->dir[oldsegment][oldindex] = old;
181 table->dir[newsegment][newindex] = new;
187 lookupHashTable(HashTable *table, StgWord key)
194 bucket = table->hash(table, key);
195 segment = bucket / HSEGSIZE;
196 index = bucket % HSEGSIZE;
198 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next)
199 if (table->compare(hl->key, key))
207 insertHashTable(HashTable *table, StgWord key, void *data)
214 /* We want no duplicates */
215 ASSERT(lookupHashTable(table, key) == NULL);
217 /* When the average load gets too high, we expand the table */
218 if (++table->kcount >= HLOAD * table->bcount)
221 bucket = table->hash(table, key);
222 segment = bucket / HSEGSIZE;
223 index = bucket % HSEGSIZE;
225 hl = arenaAlloc(table->arena, sizeof(struct hashlist));
229 hl->next = table->dir[segment][index];
230 table->dir[segment][index] = hl;
235 removeHashTable(HashTable *table, StgWord key, void *data)
241 HashList *prev = NULL;
243 bucket = table->hash(table, key);
244 segment = bucket / HSEGSIZE;
245 index = bucket % HSEGSIZE;
247 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
248 if (table->compare(hl->key,key) && (data == NULL || hl->data == data)) {
250 table->dir[segment][index] = hl->next;
252 prev->next = hl->next;
260 ASSERT(data == NULL);
264 /* -----------------------------------------------------------------------------
265 * When we free a hash table, we are also good enough to free the
266 * data part of each (key, data) pair, as long as our caller can tell
268 * -------------------------------------------------------------------------- */
271 freeHashTable( HashTable *table, void (*freeDataFun)(void *) )
278 /* The last bucket with something in it is table->max + table->split - 1 */
279 segment = (table->max + table->split - 1) / HSEGSIZE;
280 index = (table->max + table->split - 1) % HSEGSIZE;
282 while (segment >= 0) {
283 if (freeDataFun != NULL) {
285 for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
287 (*freeDataFun)(hl->data);
292 free(table->dir[segment]);
294 index = HSEGSIZE - 1;
297 arenaFree(table->arena);
301 /* -----------------------------------------------------------------------------
302 * When we initialize a hash table, we set up the first segment as well,
303 * initializing all of the first segment's hash buckets to NULL.
304 * -------------------------------------------------------------------------- */
307 allocHashTable_(HashFunction *hash, CompareFunction *compare)
312 table = stgMallocBytes(sizeof(HashTable),"allocHashTable");
314 table->arena = newArena();
316 allocSegment(table, 0);
318 for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)
322 table->max = HSEGSIZE;
323 table->mask1 = HSEGSIZE - 1;
324 table->mask2 = 2 * HSEGSIZE - 1;
326 table->bcount = HSEGSIZE;
328 table->compare = compare;
336 return allocHashTable_(hashWord, compareWord);
340 allocStrHashTable(void)
342 return allocHashTable_((HashFunction *)hashStr,
343 (CompareFunction *)compareStr);