1 /*-----------------------------------------------------------------------------
2 * $Id: Hash.c,v 1.2 2000/10/06 15:34:29 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 * -------------------------------------------------------------------------- */
16 #define HSEGSIZE 1024 /* Size of a single hash table segment */
17 /* Also the minimum size of a hash table */
18 #define HDIRSIZE 1024 /* Size of the segment directory */
19 /* Maximum hash table size is HSEGSIZE * HDIRSIZE */
20 #define HLOAD 5 /* Maximum average load of a single hash bucket */
22 #define HCHUNK (1024 * sizeof(W_) / sizeof(HashList))
23 /* Number of HashList cells to allocate in one go */
26 /* Linked list of (key, data) pairs for separate chaining */
30 struct hashlist *next; /* Next cell in bucket chain (same hash value) */
33 typedef struct hashlist HashList;
35 typedef int HashFunction(HashTable *table, StgWord key);
36 typedef int CompareFunction(StgWord key1, StgWord key2);
39 int split; /* Next bucket to split when expanding */
40 int max; /* Max bucket of smaller table */
41 int mask1; /* Mask for doing the mod of h_1 (smaller table) */
42 int mask2; /* Mask for doing the mod of h_2 (larger table) */
43 int kcount; /* Number of keys */
44 int bcount; /* Number of buckets */
45 HashList **dir[HDIRSIZE]; /* Directory of segments */
46 HashFunction *hash; /* hash function */
47 CompareFunction *compare; /* key comparison function */
50 /* -----------------------------------------------------------------------------
51 * Hash first using the smaller table. If the bucket is less than the
52 * next bucket to be split, re-hash using the larger table.
53 * -------------------------------------------------------------------------- */
56 hashWord(HashTable *table, StgWord key)
60 /* Strip the boring zero bits */
61 key /= sizeof(StgWord);
63 /* Mod the size of the hash table (a power of 2) */
64 bucket = key & table->mask1;
66 if (bucket < table->split) {
67 /* Mod the size of the expanded hash table (also a power of 2) */
68 bucket = key & table->mask2;
74 hashStr(HashTable *table, char *key)
83 h = h % 1048583; /* some random large prime */
86 /* Mod the size of the hash table (a power of 2) */
87 bucket = h & table->mask1;
89 if (bucket < table->split) {
90 /* Mod the size of the expanded hash table (also a power of 2) */
91 bucket = h & table->mask2;
98 compareWord(StgWord key1, StgWord key2)
100 return (key1 == key2);
104 compareStr(StgWord key1, StgWord key2)
106 return (strcmp((char *)key1, (char *)key2) == 0);
110 /* -----------------------------------------------------------------------------
111 * Allocate a new segment of the dynamically growing hash table.
112 * -------------------------------------------------------------------------- */
115 allocSegment(HashTable *table, int segment)
117 table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *),
122 /* -----------------------------------------------------------------------------
123 * Expand the larger hash table by one bucket, and split one bucket
124 * from the smaller table into two parts. Only the bucket referenced
125 * by @table->split@ is affected by the expansion.
126 * -------------------------------------------------------------------------- */
129 expand(HashTable *table)
140 if (table->split + table->max >= HDIRSIZE * HSEGSIZE)
141 /* Wow! That's big. Too big, so don't expand. */
144 /* Calculate indices of bucket to split */
145 oldsegment = table->split / HSEGSIZE;
146 oldindex = table->split % HSEGSIZE;
148 newbucket = table->max + table->split;
150 /* And the indices of the new bucket */
151 newsegment = newbucket / HSEGSIZE;
152 newindex = newbucket % HSEGSIZE;
155 allocSegment(table, newsegment);
157 if (++table->split == table->max) {
160 table->mask1 = table->mask2;
161 table->mask2 = table->mask2 << 1 | 1;
165 /* Split the bucket, paying no attention to the original order */
168 for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) {
170 if (table->hash(table, hl->key) == newbucket) {
178 table->dir[oldsegment][oldindex] = old;
179 table->dir[newsegment][newindex] = new;
185 lookupHashTable(HashTable *table, StgWord key)
192 bucket = table->hash(table, key);
193 segment = bucket / HSEGSIZE;
194 index = bucket % HSEGSIZE;
196 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next)
197 if (table->compare(hl->key, key))
204 /* -----------------------------------------------------------------------------
205 * We allocate the hashlist cells in large chunks to cut down on malloc
206 * overhead. Although we keep a free list of hashlist cells, we make
207 * no effort to actually return the space to the malloc arena.
208 * -------------------------------------------------------------------------- */
210 static HashList *freeList = NULL;
217 if ((hl = freeList) != NULL) {
220 hl = stgMallocBytes(HCHUNK * sizeof(HashList), "allocHashList");
223 for (p = freeList; p < hl + HCHUNK - 1; p++)
231 freeHashList(HashList *hl)
238 insertHashTable(HashTable *table, StgWord key, void *data)
245 /* We want no duplicates */
246 ASSERT(lookupHashTable(table, key) == NULL);
248 /* When the average load gets too high, we expand the table */
249 if (++table->kcount >= HLOAD * table->bcount)
252 bucket = table->hash(table, key);
253 segment = bucket / HSEGSIZE;
254 index = bucket % HSEGSIZE;
256 hl = allocHashList();
260 hl->next = table->dir[segment][index];
261 table->dir[segment][index] = hl;
266 removeHashTable(HashTable *table, StgWord key, void *data)
272 HashList *prev = NULL;
274 bucket = table->hash(table, key);
275 segment = bucket / HSEGSIZE;
276 index = bucket % HSEGSIZE;
278 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
279 if (table->compare(hl->key,key) && (data == NULL || hl->data == data)) {
281 table->dir[segment][index] = hl->next;
283 prev->next = hl->next;
291 ASSERT(data == NULL);
295 /* -----------------------------------------------------------------------------
296 * When we free a hash table, we are also good enough to free the
297 * data part of each (key, data) pair, as long as our caller can tell
299 * -------------------------------------------------------------------------- */
302 freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
309 /* The last bucket with something in it is table->max + table->split - 1 */
310 segment = (table->max + table->split - 1) / HSEGSIZE;
311 index = (table->max + table->split - 1) % HSEGSIZE;
313 while (segment >= 0) {
315 for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
317 if (freeDataFun != NULL)
318 (*freeDataFun)(hl->data);
323 free(table->dir[segment]);
325 index = HSEGSIZE - 1;
330 /* -----------------------------------------------------------------------------
331 * When we initialize a hash table, we set up the first segment as well,
332 * initializing all of the first segment's hash buckets to NULL.
333 * -------------------------------------------------------------------------- */
336 allocHashTable_(HashFunction *hash, CompareFunction *compare)
341 table = stgMallocBytes(sizeof(HashTable),"allocHashTable");
343 allocSegment(table, 0);
345 for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)
349 table->max = HSEGSIZE;
350 table->mask1 = HSEGSIZE - 1;
351 table->mask2 = 2 * HSEGSIZE - 1;
353 table->bcount = HSEGSIZE;
355 table->compare = compare;
363 return allocHashTable_(hashWord, compareWord);
367 allocStrHashTable(void)
369 return allocHashTable_((HashFunction *)hashStr,
370 (CompareFunction *)compareStr);