WINGs/hashtable.c

   1
   2
   3 #include <sys/types.h>
   4 #include <string.h>
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7
   8 #include "WUtil.h"
   9
  10
  11
  12
  13 #define INITIAL_CAPACITY        23
  14
  15
  16 #if defined(__GNUC__) && !defined(__STRICT_ANSI__)
  17 # define INLINE inline
  18 #else
  19 # define INLINE
  20 #endif
  21
  22
  23 typedef struct HashItem {
  24     const void *key;
  25     const void *data;
  26
  27     struct HashItem *next;             /* collided item list */
  28 } HashItem;
  29
  30
  31 typedef struct W_HashTable {
  32     WMHashTableCallbacks callbacks;
  33
  34     unsigned itemCount;
  35     unsigned size;                     /* table size */
  36
  37     HashItem **table;
  38 } HashTable;
  39
  40
  41
  42
  43 #define HASH(table, key)  (((table)->callbacks.hash ? \
  44             (*(table)->callbacks.hash)(key) : hashPtr(key)) % (table)->size)
  45
  46 #define DUPKEY(table, key) ((table)->callbacks.retainKey ? \
  47                     (*(table)->callbacks.retainKey)(key) : (key))
  48
  49 #define RELKEY(table, key) if ((table)->callbacks.releaseKey) \
  50                     (*(table)->callbacks.releaseKey)(key)
  51
  52
  53
  54
  55 static INLINE unsigned
  56 hashString(const char *key)
  57 {
  58     unsigned ret = 0;
  59     unsigned ctr = 0;
  60
  61     while (*key) {
  62         ret ^= *(char*)key++ << ctr;
  63         ctr = (ctr + 1) % sizeof (char *);
  64     }
  65
  66     return ret;
  67 }
  68
  69
  70
  71 static INLINE unsigned
  72 hashPtr(const void *key)
  73 {
  74     return ((size_t)key / sizeof(char*));
  75 }
  76
  77
  78
  79
  80 static void
  81 rellocateItem(WMHashTable *table, HashItem *item)
  82 {
  83     unsigned h;
  84
  85     h = HASH(table, item->key);
  86
  87     item->next = table->table[h];
  88     table->table[h] = item;
  89 }
  90
  91
  92 static void
  93 rebuildTable(WMHashTable *table)
  94 {
  95     HashItem *next;
  96     HashItem **oldArray;
  97     int i;
  98     int oldSize;
  99     int newSize;
 100
 101     oldArray = table->table;
 102     oldSize = table->size;
 103
 104     newSize = table->size*2;
 105
 106     table->table = wmalloc(sizeof(char*)*newSize);
 107     memset(table->table, 0, sizeof(char*)*newSize);
 108     table->size = newSize;
 109
 110     for (i = 0; i < oldSize; i++) {
 111         while (oldArray[i]!=NULL) {
 112             next = oldArray[i]->next;
 113             rellocateItem(table, oldArray[i]);
 114             oldArray[i] = next;
 115         }
 116     }
 117     wfree(oldArray);
 118 }
 119
 120
 121
 122 WMHashTable*
 123 WMCreateHashTable(WMHashTableCallbacks callbacks)
 124 {
 125     HashTable *table;
 126
 127     table = wmalloc(sizeof(HashTable));
 128     memset(table, 0, sizeof(HashTable));
 129
 130     table->callbacks = callbacks;
 131
 132     table->size = INITIAL_CAPACITY;
 133
 134     table->table = wmalloc(sizeof(HashItem*)*table->size);
 135     memset(table->table, 0, sizeof(HashItem*)*table->size);
 136
 137     return table;
 138 }
 139
 140
 141 void
 142 WMResetHashTable(WMHashTable *table)
 143 {
 144     HashItem *item, *tmp;
 145     int i;
 146
 147     for (i = 0; i < table->size; i++) {
 148         item = table->table[i];
 149         while (item) {
 150             tmp = item->next;
 151             RELKEY(table, item);
 152             wfree(item);
 153             item = tmp;
 154         }
 155     }
 156
 157     table->itemCount = 0;
 158
 159     if (table->size > INITIAL_CAPACITY) {
 160         wfree(table->table);
 161         table->size = INITIAL_CAPACITY;
 162         table->table = wmalloc(sizeof(HashItem*)*table->size);
 163     }
 164     memset(table->table, 0, sizeof(HashItem*)*table->size);
 165 }
 166
 167
 168 void
 169 WMFreeHashTable(WMHashTable *table)
 170 {
 171     HashItem *item, *tmp;
 172     int i;
 173
 174     for (i = 0; i < table->size; i++) {
 175         item = table->table[i];
 176         while (item) {
 177             tmp = item->next;
 178             RELKEY(table, item->key);
 179             wfree(item);
 180             item = tmp;
 181         }
 182     }
 183     wfree(table->table);
 184     wfree(table);
 185 }
 186
 187
 188
 189 void*
 190 WMHashGet(WMHashTable *table, const void *key)
 191 {
 192     unsigned h;
 193     HashItem *item;
 194
 195     h = HASH(table, key);
 196     item = table->table[h];
 197
 198     if (table->callbacks.keyIsEqual) {
 199         while (item) {
 200             if ((*table->callbacks.keyIsEqual)(key, item->key)) {
 201                 break;
 202             }
 203             item = item->next;
 204         }
 205     } else {
 206         while (item) {
 207             if (key == item->key) {
 208                 break;
 209             }
 210             item = item->next;
 211         }
 212     }
 213     if (item)
 214         return (void*)item->data;
 215     else
 216         return NULL;
 217 }
 218
 219
 220
 221 void*
 222 WMHashInsert(WMHashTable *table, const void *key, const void *data)
 223 {
 224     unsigned h;
 225     HashItem *item;
 226     int replacing = 0;
 227
 228     h = HASH(table, key);
 229     /* look for the entry */
 230     item = table->table[h];
 231     if (table->callbacks.keyIsEqual) {
 232         while (item) {
 233             if ((*table->callbacks.keyIsEqual)(key, item->key)) {
 234                 replacing = 1;
 235                 break;
 236             }
 237             item = item->next;
 238         }
 239     } else {
 240         while (item) {
 241             if (key == item->key) {
 242                 replacing = 1;
 243                 break;
 244             }
 245             item = item->next;
 246         }
 247     }
 248
 249     if (replacing) {
 250         const void *old;
 251
 252         old = item->data;
 253         item->data = data;
 254         RELKEY(table, item->key);
 255         item->key = DUPKEY(table, key);
 256
 257         return (void*)old;
 258     } else {
 259         HashItem *nitem;
 260
 261         nitem = wmalloc(sizeof(HashItem));
 262         nitem->key = DUPKEY(table, key);
 263         nitem->data = data;
 264         nitem->next = table->table[h];
 265         table->table[h] = nitem;
 266
 267         table->itemCount++;
 268     }
 269
 270     /* OPTIMIZE: put this in an idle handler.*/
 271     if (table->itemCount > table->size) {
 272 #ifdef DEBUG0
 273         printf("rebuilding hash table...\n");
 274 #endif
 275         rebuildTable(table);
 276 #ifdef DEBUG0
 277         printf("finished rebuild.\n");
 278 #endif
 279     }
 280
 281     return NULL;
 282 }
 283
 284
 285 static HashItem*
 286 deleteFromList(HashTable *table, HashItem *item, const void *key)
 287 {
 288     HashItem *next;
 289
 290     if (item==NULL)
 291         return NULL;
 292
 293     if ((table->callbacks.keyIsEqual
 294          && (*table->callbacks.keyIsEqual)(key, item->key))
 295         || (!table->callbacks.keyIsEqual && key==item->key)) {
 296
 297         next = item->next;
 298         RELKEY(table, item->key);
 299         wfree(item);
 300
 301         table->itemCount--;
 302
 303         return next;
 304     }
 305
 306     item->next = deleteFromList(table, item->next, key);
 307
 308     return item;
 309 }
 310
 311
 312 void
 313 WMHashRemove(WMHashTable *table, const void *key)
 314 {
 315     unsigned h;
 316
 317     h = HASH(table, key);
 318
 319     table->table[h] = deleteFromList(table, table->table[h], key);
 320 }
 321
 322
 323 WMHashEnumerator
 324 WMEnumerateHashTable(WMHashTable *table)
 325 {
 326     WMHashEnumerator enumerator;
 327
 328     enumerator.table = table;
 329     enumerator.index = 0;
 330     enumerator.nextItem = table->table[0];
 331
 332     return enumerator;
 333 }
 334
 335
 336
 337 void*
 338 WMNextHashEnumeratorItem(WMHashEnumerator *enumerator)
 339 {
 340     const void *data = NULL;
 341
 342     /* this assumes the table doesn't change between
 343      * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
 344
 345     if (enumerator->nextItem==NULL) {
 346         HashTable *table = enumerator->table;
 347         while (++enumerator->index < table->size) {
 348             if (table->table[enumerator->index]!=NULL) {
 349                 enumerator->nextItem = table->table[enumerator->index];
 350                 break;
 351             }
 352         }
 353     }
 354
 355     if (enumerator->nextItem) {
 356         data = ((HashItem*)enumerator->nextItem)->data;
 357         enumerator->nextItem = ((HashItem*)enumerator->nextItem)->next;
 358     }
 359
 360     return (void*)data;
 361 }
 362
 363
 364 void*
 365 WMNextHashEnumeratorKey(WMHashEnumerator *enumerator)
 366 {
 367     const void *key = NULL;
 368
 369     /* this assumes the table doesn't change between
 370      * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
 371
 372     if (enumerator->nextItem==NULL) {
 373         HashTable *table = enumerator->table;
 374         while (++enumerator->index < table->size) {
 375             if (table->table[enumerator->index]!=NULL) {
 376                 enumerator->nextItem = table->table[enumerator->index];
 377                 break;
 378             }
 379         }
 380     }
 381
 382     if (enumerator->nextItem) {
 383         key = ((HashItem*)enumerator->nextItem)->key;
 384         enumerator->nextItem = ((HashItem*)enumerator->nextItem)->next;
 385     }
 386
 387     return (void*)key;
 388 }
 389
 390
 391 unsigned
 392 WMCountHashTable(WMHashTable *table)
 393 {
 394     return table->itemCount;
 395 }
 396
 397
 398 static Bool
 399 compareStrings(const char *key1, const char *key2)
 400 {
 401     return strcmp(key1, key2)==0;
 402 }
 403
 404
 405 typedef unsigned (*hashFunc)(const void*);
 406 typedef Bool (*isEqualFunc)(const void*, const void*);
 407 typedef void* (*retainFunc)(const void*);
 408 typedef void (*releaseFunc)(const void*);
 409
 410
 411 const WMHashTableCallbacks WMIntHashCallbacks = {
 412     NULL,
 413         NULL,
 414         NULL,
 415         NULL
 416 };
 417
 418 const WMHashTableCallbacks WMStringHashCallbacks = {
 419     (hashFunc)hashString,
 420         (isEqualFunc)compareStrings,
 421         (retainFunc)wstrdup,
 422         (releaseFunc)wfree
 423 };
 424
 425
 426
 427 const WMHashTableCallbacks WMStringPointerHashCallbacks = {
 428     (hashFunc)hashString,
 429         (isEqualFunc)compareStrings,
 430         NULL,
 431         NULL
 432 };
 433