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 unsigned
 189 WMCountHashTable(WMHashTable *table)
 190 {
 191     return table->itemCount;
 192 }
 193
 194
 195 void*
 196 WMHashGet(WMHashTable *table, const void *key)
 197 {
 198     unsigned h;
 199     HashItem *item;
 200
 201     h = HASH(table, key);
 202     item = table->table[h];
 203
 204     if (table->callbacks.keyIsEqual) {
 205         while (item) {
 206             if ((*table->callbacks.keyIsEqual)(key, item->key)) {
 207                 break;
 208             }
 209             item = item->next;
 210         }
 211     } else {
 212         while (item) {
 213             if (key == item->key) {
 214                 break;
 215             }
 216             item = item->next;
 217         }
 218     }
 219     if (item)
 220         return (void*)item->data;
 221     else
 222         return NULL;
 223 }
 224
 225
 226
 227 void*
 228 WMHashInsert(WMHashTable *table, const void *key, const void *data)
 229 {
 230     unsigned h;
 231     HashItem *item;
 232     int replacing = 0;
 233
 234     h = HASH(table, key);
 235     /* look for the entry */
 236     item = table->table[h];
 237     if (table->callbacks.keyIsEqual) {
 238         while (item) {
 239             if ((*table->callbacks.keyIsEqual)(key, item->key)) {
 240                 replacing = 1;
 241                 break;
 242             }
 243             item = item->next;
 244         }
 245     } else {
 246         while (item) {
 247             if (key == item->key) {
 248                 replacing = 1;
 249                 break;
 250             }
 251             item = item->next;
 252         }
 253     }
 254
 255     if (replacing) {
 256         const void *old;
 257
 258         old = item->data;
 259         item->data = data;
 260         RELKEY(table, item->key);
 261         item->key = DUPKEY(table, key);
 262
 263         return (void*)old;
 264     } else {
 265         HashItem *nitem;
 266
 267         nitem = wmalloc(sizeof(HashItem));
 268         nitem->key = DUPKEY(table, key);
 269         nitem->data = data;
 270         nitem->next = table->table[h];
 271         table->table[h] = nitem;
 272
 273         table->itemCount++;
 274     }
 275
 276     /* OPTIMIZE: put this in an idle handler.*/
 277     if (table->itemCount > table->size) {
 278 #ifdef DEBUG0
 279         printf("rebuilding hash table...\n");
 280 #endif
 281         rebuildTable(table);
 282 #ifdef DEBUG0
 283         printf("finished rebuild.\n");
 284 #endif
 285     }
 286
 287     return NULL;
 288 }
 289
 290
 291 static HashItem*
 292 deleteFromList(HashTable *table, HashItem *item, const void *key)
 293 {
 294     HashItem *next;
 295
 296     if (item==NULL)
 297         return NULL;
 298
 299     if ((table->callbacks.keyIsEqual
 300          && (*table->callbacks.keyIsEqual)(key, item->key))
 301         || (!table->callbacks.keyIsEqual && key==item->key)) {
 302
 303         next = item->next;
 304         RELKEY(table, item->key);
 305         wfree(item);
 306
 307         table->itemCount--;
 308
 309         return next;
 310     }
 311
 312     item->next = deleteFromList(table, item->next, key);
 313
 314     return item;
 315 }
 316
 317
 318 void
 319 WMHashRemove(WMHashTable *table, const void *key)
 320 {
 321     unsigned h;
 322
 323     h = HASH(table, key);
 324
 325     table->table[h] = deleteFromList(table, table->table[h], key);
 326 }
 327
 328
 329 WMHashEnumerator
 330 WMEnumerateHashTable(WMHashTable *table)
 331 {
 332     WMHashEnumerator enumerator;
 333
 334     enumerator.table = table;
 335     enumerator.index = 0;
 336     enumerator.nextItem = table->table[0];
 337
 338     return enumerator;
 339 }
 340
 341
 342
 343 void*
 344 WMNextHashEnumeratorItem(WMHashEnumerator *enumerator)
 345 {
 346     const void *data = NULL;
 347
 348     /* this assumes the table doesn't change between
 349      * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
 350
 351     if (enumerator->nextItem==NULL) {
 352         HashTable *table = enumerator->table;
 353         while (++enumerator->index < table->size) {
 354             if (table->table[enumerator->index]!=NULL) {
 355                 enumerator->nextItem = table->table[enumerator->index];
 356                 break;
 357             }
 358         }
 359     }
 360
 361     if (enumerator->nextItem) {
 362         data = ((HashItem*)enumerator->nextItem)->data;
 363         enumerator->nextItem = ((HashItem*)enumerator->nextItem)->next;
 364     }
 365
 366     return (void*)data;
 367 }
 368
 369
 370 void*
 371 WMNextHashEnumeratorKey(WMHashEnumerator *enumerator)
 372 {
 373     const void *key = NULL;
 374
 375     /* this assumes the table doesn't change between
 376      * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
 377
 378     if (enumerator->nextItem==NULL) {
 379         HashTable *table = enumerator->table;
 380         while (++enumerator->index < table->size) {
 381             if (table->table[enumerator->index]!=NULL) {
 382                 enumerator->nextItem = table->table[enumerator->index];
 383                 break;
 384             }
 385         }
 386     }
 387
 388     if (enumerator->nextItem) {
 389         key = ((HashItem*)enumerator->nextItem)->key;
 390         enumerator->nextItem = ((HashItem*)enumerator->nextItem)->next;
 391     }
 392
 393     return (void*)key;
 394 }
 395
 396
 397 Bool
 398 WMNextHashEnumeratorItemAndKey(WMHashEnumerator *enumerator,
 399                                void **item, void **key)
 400 {
 401     const void *data = NULL;
 402
 403     /* this assumes the table doesn't change between
 404      * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
 405
 406     if (enumerator->nextItem==NULL) {
 407         HashTable *table = enumerator->table;
 408         while (++enumerator->index < table->size) {
 409             if (table->table[enumerator->index]!=NULL) {
 410                 enumerator->nextItem = table->table[enumerator->index];
 411                 break;
 412             }
 413         }
 414     }
 415
 416     if (enumerator->nextItem) {
 417         *item = (void*)((HashItem*)enumerator->nextItem)->data;
 418         *key = (void*)((HashItem*)enumerator->nextItem)->key;
 419         enumerator->nextItem = ((HashItem*)enumerator->nextItem)->next;
 420
 421         return True;
 422     }
 423
 424     return False;
 425 }
 426
 427
 428 static Bool
 429 compareStrings(const char *key1, const char *key2)
 430 {
 431     return strcmp(key1, key2)==0;
 432 }
 433
 434
 435 typedef unsigned (*hashFunc)(const void*);
 436 typedef Bool (*isEqualFunc)(const void*, const void*);
 437 typedef void* (*retainFunc)(const void*);
 438 typedef void (*releaseFunc)(const void*);
 439
 440
 441 const WMHashTableCallbacks WMIntHashCallbacks = {
 442     NULL,
 443         NULL,
 444         NULL,
 445         NULL
 446 };
 447
 448 const WMHashTableCallbacks WMStringHashCallbacks = {
 449     (hashFunc)hashString,
 450         (isEqualFunc)compareStrings,
 451         (retainFunc)wstrdup,
 452         (releaseFunc)wfree
 453 };
 454
 455
 456
 457 const WMHashTableCallbacks WMStringPointerHashCallbacks = {
 458     (hashFunc)hashString,
 459         (isEqualFunc)compareStrings,
 460         NULL,
 461         NULL
 462 };
 463