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