WINGs/hashtable.c

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