ghc/rts/Hash.c

   1 /*-----------------------------------------------------------------------------
   2  * $Id: Hash.c,v 1.5 2001/06/27 11:29:10 sewardj Exp $
   3  *
   4  * (c) The AQUA Project, Glasgow University, 1995-1998
   5  * (c) The GHC Team, 1999
   6  *
   7  * Dynamically expanding linear hash tables, as described in
   8  * Per-\AAke Larson, ``Dynamic Hash Tables,'' CACM 31(4), April 1988,
   9  * pp. 446 -- 457.
  10  * -------------------------------------------------------------------------- */
  11
  12 #include "Rts.h"
  13 #include "Hash.h"
  14 #include "RtsUtils.h"
  15
  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 */
  21
  22 #define HCHUNK      (1024 * sizeof(W_) / sizeof(HashList))
  23                             /* Number of HashList cells to allocate in one go */
  24
  25
  26 /* Linked list of (key, data) pairs for separate chaining */
  27 struct hashlist {
  28     StgWord key;
  29     void *data;
  30     struct hashlist *next;  /* Next cell in bucket chain (same hash value) */
  31 };
  32
  33 typedef struct hashlist HashList;
  34
  35 typedef int HashFunction(HashTable *table, StgWord key);
  36 typedef int CompareFunction(StgWord key1, StgWord key2);
  37
  38 struct hashtable {
  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 */
  48 };
  49
  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  * -------------------------------------------------------------------------- */
  54
  55 static int
  56 hashWord(HashTable *table, StgWord key)
  57 {
  58     int bucket;
  59
  60     /* Strip the boring zero bits */
  61     key /= sizeof(StgWord);
  62
  63     /* Mod the size of the hash table (a power of 2) */
  64     bucket = key & table->mask1;
  65
  66     if (bucket < table->split) {
  67         /* Mod the size of the expanded hash table (also a power of 2) */
  68         bucket = key & table->mask2;
  69     }
  70     return bucket;
  71 }
  72
  73 static int
  74 hashStr(HashTable *table, char *key)
  75 {
  76     int h, bucket;
  77     char *s;
  78
  79     s = key;
  80     for (h=0; *s; s++) {
  81         h *= 128;
  82         h += *s;
  83         h = h % 1048583;        /* some random large prime */
  84     }
  85
  86     /* Mod the size of the hash table (a power of 2) */
  87     bucket = h & table->mask1;
  88
  89     if (bucket < table->split) {
  90         /* Mod the size of the expanded hash table (also a power of 2) */
  91         bucket = h & table->mask2;
  92     }
  93
  94     return bucket;
  95 }
  96
  97 static int
  98 compareWord(StgWord key1, StgWord key2)
  99 {
 100     return (key1 == key2);
 101 }
 102
 103 static int
 104 compareStr(StgWord key1, StgWord key2)
 105 {
 106     return (strcmp((char *)key1, (char *)key2) == 0);
 107 }
 108
 109
 110 /* -----------------------------------------------------------------------------
 111  * Allocate a new segment of the dynamically growing hash table.
 112  * -------------------------------------------------------------------------- */
 113
 114 static void
 115 allocSegment(HashTable *table, int segment)
 116 {
 117     table->dir[segment] = stgMallocBytes(HSEGSIZE * sizeof(HashList *),
 118                                          "allocSegment");
 119 }
 120
 121
 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  * -------------------------------------------------------------------------- */
 127
 128 static void
 129 expand(HashTable *table)
 130 {
 131     int oldsegment;
 132     int oldindex;
 133     int newbucket;
 134     int newsegment;
 135     int newindex;
 136     HashList *hl;
 137     HashList *next;
 138     HashList *old, *new;
 139
 140     if (table->split + table->max >= HDIRSIZE * HSEGSIZE)
 141         /* Wow!  That's big.  Too big, so don't expand. */
 142         return;
 143
 144     /* Calculate indices of bucket to split */
 145     oldsegment = table->split / HSEGSIZE;
 146     oldindex = table->split % HSEGSIZE;
 147
 148     newbucket = table->max + table->split;
 149
 150     /* And the indices of the new bucket */
 151     newsegment = newbucket / HSEGSIZE;
 152     newindex = newbucket % HSEGSIZE;
 153
 154     if (newindex == 0)
 155         allocSegment(table, newsegment);
 156
 157     if (++table->split == table->max) {
 158         table->split = 0;
 159         table->max *= 2;
 160         table->mask1 = table->mask2;
 161         table->mask2 = table->mask2 << 1 | 1;
 162     }
 163     table->bcount++;
 164
 165     /* Split the bucket, paying no attention to the original order */
 166
 167     old = new = NULL;
 168     for (hl = table->dir[oldsegment][oldindex]; hl != NULL; hl = next) {
 169         next = hl->next;
 170         if (table->hash(table, hl->key) == newbucket) {
 171             hl->next = new;
 172             new = hl;
 173         } else {
 174             hl->next = old;
 175             old = hl;
 176         }
 177     }
 178     table->dir[oldsegment][oldindex] = old;
 179     table->dir[newsegment][newindex] = new;
 180
 181     return;
 182 }
 183
 184 void *
 185 lookupHashTable(HashTable *table, StgWord key)
 186 {
 187     int bucket;
 188     int segment;
 189     int index;
 190     HashList *hl;
 191
 192     bucket = table->hash(table, key);
 193     segment = bucket / HSEGSIZE;
 194     index = bucket % HSEGSIZE;
 195
 196     for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next)
 197         if (table->compare(hl->key, key))
 198             return hl->data;
 199
 200     /* It's not there */
 201     return NULL;
 202 }
 203
 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  * -------------------------------------------------------------------------- */
 209
 210 static HashList *freeList = NULL;
 211
 212 static HashList *
 213 allocHashList(void)
 214 {
 215     HashList *hl, *p;
 216
 217     if ((hl = freeList) != NULL) {
 218         freeList = hl->next;
 219     } else {
 220         hl = stgMallocBytes(HCHUNK * sizeof(HashList), "allocHashList");
 221
 222         freeList = hl + 1;
 223         for (p = freeList; p < hl + HCHUNK - 1; p++)
 224             p->next = p + 1;
 225         p->next = NULL;
 226     }
 227     return hl;
 228 }
 229
 230 static void
 231 freeHashList(HashList *hl)
 232 {
 233     hl->next = freeList;
 234     freeList = hl;
 235 }
 236
 237 void
 238 insertHashTable(HashTable *table, StgWord key, void *data)
 239 {
 240     int bucket;
 241     int segment;
 242     int index;
 243     HashList *hl;
 244
 245     /* We want no duplicates */
 246     ASSERT(lookupHashTable(table, key) == NULL);
 247
 248     /* When the average load gets too high, we expand the table */
 249     if (++table->kcount >= HLOAD * table->bcount)
 250         expand(table);
 251
 252     bucket = table->hash(table, key);
 253     segment = bucket / HSEGSIZE;
 254     index = bucket % HSEGSIZE;
 255
 256     hl = allocHashList();
 257
 258     hl->key = key;
 259     hl->data = data;
 260     hl->next = table->dir[segment][index];
 261     table->dir[segment][index] = hl;
 262
 263 }
 264
 265 void *
 266 removeHashTable(HashTable *table, StgWord key, void *data)
 267 {
 268     int bucket;
 269     int segment;
 270     int index;
 271     HashList *hl;
 272     HashList *prev = NULL;
 273
 274     bucket = table->hash(table, key);
 275     segment = bucket / HSEGSIZE;
 276     index = bucket % HSEGSIZE;
 277
 278     for (hl = table->dir[segment][index]; hl != NULL; hl = hl->next) {
 279         if (table->compare(hl->key,key) && (data == NULL || hl->data == data)) {
 280             if (prev == NULL)
 281                 table->dir[segment][index] = hl->next;
 282             else
 283                 prev->next = hl->next;
 284             table->kcount--;
 285             return hl->data;
 286         }
 287         prev = hl;
 288     }
 289
 290     /* It's not there */
 291     ASSERT(data == NULL);
 292     return NULL;
 293 }
 294
 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
 298  * us how to do it.
 299  * -------------------------------------------------------------------------- */
 300
 301 void
 302 freeHashTable(HashTable *table, void (*freeDataFun)(void *) )
 303 {
 304     long segment;
 305     long index;
 306     HashList *hl;
 307     HashList *next;
 308
 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;
 312
 313     while (segment >= 0) {
 314         while (index >= 0) {
 315             for (hl = table->dir[segment][index]; hl != NULL; hl = next) {
 316                 next = hl->next;
 317                 if (freeDataFun != NULL)
 318                     (*freeDataFun)(hl->data);
 319                 freeHashList(hl);
 320             }
 321             index--;
 322         }
 323         free(table->dir[segment]);
 324         segment--;
 325         index = HSEGSIZE - 1;
 326     }
 327     free(table);
 328 }
 329
 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  * -------------------------------------------------------------------------- */
 334
 335 static HashTable *
 336 allocHashTable_(HashFunction *hash, CompareFunction *compare)
 337 {
 338     HashTable *table;
 339     HashList **hb;
 340
 341     table = stgMallocBytes(sizeof(HashTable),"allocHashTable");
 342
 343     allocSegment(table, 0);
 344
 345     for (hb = table->dir[0]; hb < table->dir[0] + HSEGSIZE; hb++)
 346         *hb = NULL;
 347
 348     table->split = 0;
 349     table->max = HSEGSIZE;
 350     table->mask1 = HSEGSIZE - 1;
 351     table->mask2 = 2 * HSEGSIZE - 1;
 352     table->kcount = 0;
 353     table->bcount = HSEGSIZE;
 354     table->hash = hash;
 355     table->compare = compare;
 356
 357     return table;
 358 }
 359
 360 HashTable *
 361 allocHashTable(void)
 362 {
 363     return allocHashTable_(hashWord, compareWord);
 364 }
 365
 366 HashTable *
 367 allocStrHashTable(void)
 368 {
 369     return allocHashTable_((HashFunction *)hashStr,
 370                            (CompareFunction *)compareStr);
 371 }