1 /*-----------------------------------------------------------------------------
2 * $Id: 0Hash.c,v 1.2 2000/01/13 14:34:06 hwloidl 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 * -------------------------------------------------------------------------- */
13 Replaced with ghc/rts/Hash.c in the new RTS
22 #define HSEGSIZE 1024 /* Size of a single hash table segment */
23 /* Also the minimum size of a hash table */
24 #define HDIRSIZE 1024 /* Size of the segment directory */
25 /* Maximum hash table size is HSEGSIZE * HDIRSIZE */
26 #define HLOAD 5 /* Maximum average load of a single hash bucket */
28 #define HCHUNK (1024 * sizeof(W_) / sizeof(HashList))
29 /* Number of HashList cells to allocate in one go */
32 /* Linked list of (key, data) pairs for separate chaining */
36 struct hashlist *next; /* Next cell in bucket chain (same hash value) */
39 typedef struct hashlist HashList;
42 int split; /* Next bucket to split when expanding */
43 int max; /* Max bucket of smaller table */
44 int mask1; /* Mask for doing the mod of h_1 (smaller table) */
45 int mask2; /* Mask for doing the mod of h_2 (larger table) */
46 int kcount; /* Number of keys */
47 int bcount; /* Number of buckets */
48 HashList **dir[HDIRSIZE]; /* Directory of segments */
51 /* -----------------------------------------------------------------------------
52 * Hash first using the smaller table. If the bucket is less than the
53 * next bucket to be split, re-hash using the larger table.
54 * -------------------------------------------------------------------------- */
57 hash(HashTable *table, W_ key)
61 /* Strip the boring zero bits */
62 key /= sizeof(StgWord);
64 /* Mod the size of the hash table (a power of 2) */
65 bucket = key & table->mask1;
67 if (bucket < table->split) {
68 /* Mod the size of the expanded hash table (also a power of 2) */
69 bucket = key & table->mask2;
74 /* -----------------------------------------------------------------------------
75 * Allocate a new segment of the dynamically growing hash table.
76 * -------------------------------------------------------------------------- */
79 allocSegment(HashTable *table, int segment)
81 table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *),
86 /* -----------------------------------------------------------------------------
87 * Expand the larger hash table by one bucket, and split one bucket
88 * from the smaller table into two parts. Only the bucket referenced
89 * by @table->split@ is affected by the expansion.
90 * -------------------------------------------------------------------------- */
93 expand(HashTable *table)
104 if (table->split + table->max >= HDIRSIZE * HSEGSIZE)
105 /* Wow! That's big. Too big, so don't expand. */
108 /* Calculate indices of bucket to split */
109 oldsegment = table->split / HSEGSIZE;
110 oldindex = table->split % HSEGSIZE;
112 newbucket = table->max + table->split;
114 /* And the indices of the new bucket */
115 newsegment = newbucket / HSEGSIZE;
116 newindex = newbucket % HSEGSIZE;
119 allocSegment(table, newsegment);
121 if (++table->split == table->max) {
124 table->mask1 = table->mask2;
125 table->mask2 = table->mask2 << 1 | 1;
129 /* Split the bucket, paying no attention to the original order */
132 for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) {
134 if (hash(table, hl->key) == newbucket) {
142 table->dir[oldsegment][oldindex] = old;
143 table->dir[newsegment][newindex] = new;
149 lookupHashTable(HashTable *table, StgWord key)
156 bucket = hash(table, key);
157 segment = bucket / HSEGSIZE;
158 index = bucket % HSEGSIZE;
160 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next)
168 /* -----------------------------------------------------------------------------
169 * We allocate the hashlist cells in large chunks to cut down on malloc
170 * overhead. Although we keep a free list of hashlist cells, we make
171 * no effort to actually return the space to the malloc arena.
172 * -------------------------------------------------------------------------- */
174 static HashList *freeList = NULL;
181 if ((hl = freeList) != NULL) {
184 hl = stgMallocBytes(HCHUNK * sizeof(HashList), "allocHashList");
187 for (p = freeList; p < hl + HCHUNK - 1; p++)
195 freeHashList(HashList *hl)
202 insertHashTable(HashTable *table, StgWord key, void *data)
209 /* We want no duplicates */
210 ASSERT(lookupHashTable(table, key) == NULL);
212 /* When the average load gets too high, we expand the table */
213 if (++table->kcount >= HLOAD * table->bcount)
216 bucket = hash(table, key);
217 segment = bucket / HSEGSIZE;
218 index = bucket % HSEGSIZE;
220 hl = allocHashList();
224 hl->next = table->dir[segment][index];
225 table->dir[segment][index] = hl;
230 removeHashTable(HashTable *table, StgWord key, void *data)
236 HashList *prev = NULL;
238 bucket = hash(table, key);
239 segment = bucket / HSEGSIZE;
240 index = bucket % HSEGSIZE;
242 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
243 if (hl->key == key && (data == NULL || hl->data == data)) {
245 table->dir[segment][index] = hl->next;
247 prev->next = hl->next;
255 ASSERT(data == NULL);
259 /* -----------------------------------------------------------------------------
260 * When we free a hash table, we are also good enough to free the
261 * data part of each (key, data) pair, as long as our caller can tell
263 * -------------------------------------------------------------------------- */
266 freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
273 /* The last bucket with something in it is table->max + table->split - 1 */
274 segment = (table->max + table->split - 1) / HSEGSIZE;
275 index = (table->max + table->split - 1) % HSEGSIZE;
277 while (segment >= 0) {
279 for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
281 if (freeDataFun != NULL)
282 (*freeDataFun)(hl->data);
287 free(table->dir[segment]);
289 index = HSEGSIZE - 1;
294 /* -----------------------------------------------------------------------------
295 * When we initialize a hash table, we set up the first segment as well,
296 * initializing all of the first segment's hash buckets to NULL.
297 * -------------------------------------------------------------------------- */
305 table = stgMallocBytes(sizeof(HashTable),"allocHashTable");
307 allocSegment(table, 0);
309 for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)
313 table->max = HSEGSIZE;
314 table->mask1 = HSEGSIZE - 1;
315 table->mask2 = 2 * HSEGSIZE - 1;
317 table->bcount = HSEGSIZE;