CmmLayoutStack: Add unwind information on stack fixups
[ghc.git] / rts / Hash.c
1 /*-----------------------------------------------------------------------------
2 *
3 * (c) The AQUA Project, Glasgow University, 1995-1998
4 * (c) The GHC Team, 1999
5 *
6 * Dynamically expanding linear hash tables, as described in
7 * Per-\AAke Larson, ``Dynamic Hash Tables,'' CACM 31(4), April 1988,
8 * pp. 446 -- 457.
9 * -------------------------------------------------------------------------- */
10
11 #include "PosixSource.h"
12 #include "Rts.h"
13
14 #include "Hash.h"
15 #include "RtsUtils.h"
16
17 #include <string.h>
18
19 #define HSEGSIZE 1024 /* Size of a single hash table segment */
20 /* Also the minimum size of a hash table */
21 #define HDIRSIZE 1024 /* Size of the segment directory */
22 /* Maximum hash table size is HSEGSIZE * HDIRSIZE */
23 #define HLOAD 5 /* Maximum average load of a single hash bucket */
24
25 #define HCHUNK (1024 * sizeof(W_) / sizeof(HashList))
26 /* Number of HashList cells to allocate in one go */
27
28
29 /* Linked list of (key, data) pairs for separate chaining */
30 typedef struct hashlist {
31 StgWord key;
32 const void *data;
33 struct hashlist *next; /* Next cell in bucket chain (same hash value) */
34 } HashList;
35
36 typedef struct chunklist {
37 HashList *chunk;
38 struct chunklist *next;
39 } HashListChunk;
40
41 struct hashtable {
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 */
49 HashList *freeList; /* free list of HashLists */
50 HashListChunk *chunks;
51 HashFunction *hash; /* hash function */
52 CompareFunction *compare; /* key comparison function */
53 };
54
55 /* -----------------------------------------------------------------------------
56 * Hash first using the smaller table. If the bucket is less than the
57 * next bucket to be split, re-hash using the larger table.
58 * -------------------------------------------------------------------------- */
59
60 int
61 hashWord(const HashTable *table, StgWord key)
62 {
63 int bucket;
64
65 /* Strip the boring zero bits */
66 key /= sizeof(StgWord);
67
68 /* Mod the size of the hash table (a power of 2) */
69 bucket = key & table->mask1;
70
71 if (bucket < table->split) {
72 /* Mod the size of the expanded hash table (also a power of 2) */
73 bucket = key & table->mask2;
74 }
75 return bucket;
76 }
77
78 int
79 hashStr(const HashTable *table, char *key)
80 {
81 int h, bucket;
82 char *s;
83
84 s = key;
85 for (h=0; *s; s++) {
86 h *= 128;
87 h += *s;
88 h = h % 1048583; /* some random large prime */
89 }
90
91 /* Mod the size of the hash table (a power of 2) */
92 bucket = h & table->mask1;
93
94 if (bucket < table->split) {
95 /* Mod the size of the expanded hash table (also a power of 2) */
96 bucket = h & table->mask2;
97 }
98
99 return bucket;
100 }
101
102 static int
103 compareWord(StgWord key1, StgWord key2)
104 {
105 return (key1 == key2);
106 }
107
108 static int
109 compareStr(StgWord key1, StgWord key2)
110 {
111 return (strcmp((char *)key1, (char *)key2) == 0);
112 }
113
114
115 /* -----------------------------------------------------------------------------
116 * Allocate a new segment of the dynamically growing hash table.
117 * -------------------------------------------------------------------------- */
118
119 static void
120 allocSegment(HashTable *table, int segment)
121 {
122 table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *),
123 "allocSegment");
124 }
125
126
127 /* -----------------------------------------------------------------------------
128 * Expand the larger hash table by one bucket, and split one bucket
129 * from the smaller table into two parts. Only the bucket referenced
130 * by @table->split@ is affected by the expansion.
131 * -------------------------------------------------------------------------- */
132
133 static void
134 expand(HashTable *table)
135 {
136 int oldsegment;
137 int oldindex;
138 int newbucket;
139 int newsegment;
140 int newindex;
141 HashList *hl;
142 HashList *next;
143 HashList *old, *new;
144
145 if (table->split + table->max >= HDIRSIZE * HSEGSIZE)
146 /* Wow! That's big. Too big, so don't expand. */
147 return;
148
149 /* Calculate indices of bucket to split */
150 oldsegment = table->split / HSEGSIZE;
151 oldindex = table->split % HSEGSIZE;
152
153 newbucket = table->max + table->split;
154
155 /* And the indices of the new bucket */
156 newsegment = newbucket / HSEGSIZE;
157 newindex = newbucket % HSEGSIZE;
158
159 if (newindex == 0)
160 allocSegment(table, newsegment);
161
162 if (++table->split == table->max) {
163 table->split = 0;
164 table->max *= 2;
165 table->mask1 = table->mask2;
166 table->mask2 = table->mask2 << 1 | 1;
167 }
168 table->bcount++;
169
170 /* Split the bucket, paying no attention to the original order */
171
172 old = new = NULL;
173 for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) {
174 next = hl->next;
175 if (table->hash(table, hl->key) == newbucket) {
176 hl->next = new;
177 new = hl;
178 } else {
179 hl->next = old;
180 old = hl;
181 }
182 }
183 table->dir[oldsegment][oldindex] = old;
184 table->dir[newsegment][newindex] = new;
185
186 return;
187 }
188
189 void *
190 lookupHashTable(const HashTable *table, StgWord key)
191 {
192 int bucket;
193 int segment;
194 int index;
195 HashList *hl;
196
197 bucket = table->hash(table, key);
198 segment = bucket / HSEGSIZE;
199 index = bucket % HSEGSIZE;
200
201 CompareFunction *cmp = table->compare;
202 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
203 if (cmp(hl->key, key))
204 return (void *) hl->data;
205 }
206
207 /* It's not there */
208 return NULL;
209 }
210
211 // Puts up to szKeys keys of the hash table into the given array. Returns the
212 // actual amount of keys that have been retrieved.
213 //
214 // If the table is modified concurrently, the function behavior is undefined.
215 //
216 int keysHashTable(HashTable *table, StgWord keys[], int szKeys) {
217 int segment, index;
218 int k = 0;
219 HashList *hl;
220
221
222 /* The last bucket with something in it is table->max + table->split - 1 */
223 segment = (table->max + table->split - 1) / HSEGSIZE;
224 index = (table->max + table->split - 1) % HSEGSIZE;
225
226 while (segment >= 0 && k < szKeys) {
227 while (index >= 0 && k < szKeys) {
228 hl = table->dir[segment][index];
229 while (hl && k < szKeys) {
230 keys[k] = hl->key;
231 k += 1;
232 hl = hl->next;
233 }
234 index--;
235 }
236 segment--;
237 index = HSEGSIZE - 1;
238 }
239 return k;
240 }
241
242 /* -----------------------------------------------------------------------------
243 * We allocate the hashlist cells in large chunks to cut down on malloc
244 * overhead. Although we keep a free list of hashlist cells, we make
245 * no effort to actually return the space to the malloc arena.
246 * -------------------------------------------------------------------------- */
247
248 static HashList *
249 allocHashList (HashTable *table)
250 {
251 HashList *hl, *p;
252 HashListChunk *cl;
253
254 if ((hl = table->freeList) != NULL) {
255 table->freeList = hl->next;
256 } else {
257 hl = stgMallocBytes(HCHUNK * sizeof(HashList), "allocHashList");
258 cl = stgMallocBytes(sizeof (*cl), "allocHashList: chunkList");
259 cl->chunk = hl;
260 cl->next = table->chunks;
261 table->chunks = cl;
262
263 table->freeList = hl + 1;
264 for (p = table->freeList; p < hl + HCHUNK - 1; p++)
265 p->next = p + 1;
266 p->next = NULL;
267 }
268 return hl;
269 }
270
271 static void
272 freeHashList (HashTable *table, HashList *hl)
273 {
274 hl->next = table->freeList;
275 table->freeList = hl;
276 }
277
278 void
279 insertHashTable(HashTable *table, StgWord key, const void *data)
280 {
281 int bucket;
282 int segment;
283 int index;
284 HashList *hl;
285
286 // Disable this assert; sometimes it's useful to be able to
287 // overwrite entries in the hash table.
288 // ASSERT(lookupHashTable(table, key) == NULL);
289
290 /* When the average load gets too high, we expand the table */
291 if (++table->kcount >= HLOAD * table->bcount)
292 expand(table);
293
294 bucket = table->hash(table, key);
295 segment = bucket / HSEGSIZE;
296 index = bucket % HSEGSIZE;
297
298 hl = allocHashList(table);
299
300 hl->key = key;
301 hl->data = data;
302 hl->next = table->dir[segment][index];
303 table->dir[segment][index] = hl;
304
305 }
306
307 void *
308 removeHashTable(HashTable *table, StgWord key, const void *data)
309 {
310 int bucket;
311 int segment;
312 int index;
313 HashList *hl;
314 HashList *prev = NULL;
315
316 bucket = table->hash(table, key);
317 segment = bucket / HSEGSIZE;
318 index = bucket % HSEGSIZE;
319
320 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
321 if (table->compare(hl->key,key) && (data == NULL || hl->data == data)) {
322 if (prev == NULL)
323 table->dir[segment][index] = hl->next;
324 else
325 prev->next = hl->next;
326 freeHashList(table,hl);
327 table->kcount--;
328 return (void *) hl->data;
329 }
330 prev = hl;
331 }
332
333 /* It's not there */
334 ASSERT(data == NULL);
335 return NULL;
336 }
337
338 /* -----------------------------------------------------------------------------
339 * When we free a hash table, we are also good enough to free the
340 * data part of each (key, data) pair, as long as our caller can tell
341 * us how to do it.
342 * -------------------------------------------------------------------------- */
343
344 void
345 freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
346 {
347 long segment;
348 long index;
349 HashList *hl;
350 HashList *next;
351 HashListChunk *cl, *cl_next;
352
353 /* The last bucket with something in it is table->max + table->split - 1 */
354 segment = (table->max + table->split - 1) / HSEGSIZE;
355 index = (table->max + table->split - 1) % HSEGSIZE;
356
357 while (segment >= 0) {
358 while (index >= 0) {
359 for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
360 next = hl->next;
361 if (freeDataFun != NULL)
362 (*freeDataFun)((void *) hl->data);
363 }
364 index--;
365 }
366 stgFree(table->dir[segment]);
367 segment--;
368 index = HSEGSIZE - 1;
369 }
370 for (cl = table->chunks; cl != NULL; cl = cl_next) {
371 cl_next = cl->next;
372 stgFree(cl->chunk);
373 stgFree(cl);
374 }
375 stgFree(table);
376 }
377
378 /* -----------------------------------------------------------------------------
379 * Map a function over all the keys/values in a HashTable
380 * -------------------------------------------------------------------------- */
381
382 void
383 mapHashTable(HashTable *table, void *data, MapHashFn fn)
384 {
385 long segment;
386 long index;
387 HashList *hl;
388
389 /* The last bucket with something in it is table->max + table->split - 1 */
390 segment = (table->max + table->split - 1) / HSEGSIZE;
391 index = (table->max + table->split - 1) % HSEGSIZE;
392
393 while (segment >= 0) {
394 while (index >= 0) {
395 for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
396 fn(data, hl->key, hl->data);
397 }
398 index--;
399 }
400 segment--;
401 index = HSEGSIZE - 1;
402 }
403 }
404
405 /* -----------------------------------------------------------------------------
406 * When we initialize a hash table, we set up the first segment as well,
407 * initializing all of the first segment's hash buckets to NULL.
408 * -------------------------------------------------------------------------- */
409
410 HashTable *
411 allocHashTable_(HashFunction *hash, CompareFunction *compare)
412 {
413 HashTable *table;
414 HashList **hb;
415
416 table = stgMallocBytes(sizeof(HashTable),"allocHashTable");
417
418 allocSegment(table, 0);
419
420 for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)
421 *hb = NULL;
422
423 table->split = 0;
424 table->max = HSEGSIZE;
425 table->mask1 = HSEGSIZE - 1;
426 table->mask2 = 2 * HSEGSIZE - 1;
427 table->kcount = 0;
428 table->bcount = HSEGSIZE;
429 table->freeList = NULL;
430 table->chunks = NULL;
431 table->hash = hash;
432 table->compare = compare;
433
434 return table;
435 }
436
437 HashTable *
438 allocHashTable(void)
439 {
440 return allocHashTable_(hashWord, compareWord);
441 }
442
443 HashTable *
444 allocStrHashTable(void)
445 {
446 return allocHashTable_((HashFunction *)hashStr,
447 (CompareFunction *)compareStr);
448 }
449
450 void
451 exitHashTable(void)
452 {
453 /* nothing to do */
454 }
455
456 int keyCountHashTable (HashTable *table)
457 {
458 return table->kcount;
459 }