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         table->size = newSize;
  85
  86         for (i = 0; i < oldSize; i++) {
  87                 while (oldArray[i] != NULL) {
  88                         next = oldArray[i]->next;
  89                         rellocateItem(table, oldArray[i]);
  90                         oldArray[i] = next;
  91                 }
  92         }
  93         wfree(oldArray);
  94 }
  95
  96 WMHashTable *WMCreateHashTable(WMHashTableCallbacks callbacks)
  97 {
  98         HashTable *table;
  99
 100         table = wmalloc(sizeof(HashTable));
 101         memset(table, 0, sizeof(HashTable));
 102
 103         table->callbacks = callbacks;
 104
 105         table->size = INITIAL_CAPACITY;
 106
 107         table->table = wmalloc(sizeof(HashItem *) * table->size);
 108         memset(table->table, 0, sizeof(HashItem *) * table->size);
 109
 110         return table;
 111 }
 112
 113 void WMResetHashTable(WMHashTable * table)
 114 {
 115         HashItem *item, *tmp;
 116         int i;
 117
 118         for (i = 0; i < table->size; i++) {
 119                 item = table->table[i];
 120                 while (item) {
 121                         tmp = item->next;
 122                         RELKEY(table, item->key);
 123                         wfree(item);
 124                         item = tmp;
 125                 }
 126         }
 127
 128         table->itemCount = 0;
 129
 130         if (table->size > INITIAL_CAPACITY) {
 131                 wfree(table->table);
 132                 table->size = INITIAL_CAPACITY;
 133                 table->table = wmalloc(sizeof(HashItem *) * table->size);
 134         }
 135         memset(table->table, 0, sizeof(HashItem *) * table->size);
 136 }
 137
 138 void WMFreeHashTable(WMHashTable * table)
 139 {
 140         HashItem *item, *tmp;
 141         int i;
 142
 143         for (i = 0; i < table->size; i++) {
 144                 item = table->table[i];
 145                 while (item) {
 146                         tmp = item->next;
 147                         RELKEY(table, item->key);
 148                         wfree(item);
 149                         item = tmp;
 150                 }
 151         }
 152         wfree(table->table);
 153         wfree(table);
 154 }
 155
 156 unsigned WMCountHashTable(WMHashTable * table)
 157 {
 158         return table->itemCount;
 159 }
 160
 161 void *WMHashGet(WMHashTable * table, const void *key)
 162 {
 163         unsigned h;
 164         HashItem *item;
 165
 166         h = HASH(table, key);
 167         item = table->table[h];
 168
 169         if (table->callbacks.keyIsEqual) {
 170                 while (item) {
 171                         if ((*table->callbacks.keyIsEqual) (key, item->key)) {
 172                                 break;
 173                         }
 174                         item = item->next;
 175                 }
 176         } else {
 177                 while (item) {
 178                         if (key == item->key) {
 179                                 break;
 180                         }
 181                         item = item->next;
 182                 }
 183         }
 184         if (item)
 185                 return (void *)item->data;
 186         else
 187                 return NULL;
 188 }
 189
 190 Bool WMHashGetItemAndKey(WMHashTable * table, const void *key, void **retItem, void **retKey)
 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                 if (retKey)
 215                         *retKey = (void *)item->key;
 216                 if (retItem)
 217                         *retItem = (void *)item->data;
 218                 return True;
 219         } else {
 220                 return False;
 221         }
 222 }
 223
 224 void *WMHashInsert(WMHashTable * table, const void *key, const void *data)
 225 {
 226         unsigned h;
 227         HashItem *item;
 228         int replacing = 0;
 229
 230         h = HASH(table, key);
 231         /* look for the entry */
 232         item = table->table[h];
 233         if (table->callbacks.keyIsEqual) {
 234                 while (item) {
 235                         if ((*table->callbacks.keyIsEqual) (key, item->key)) {
 236                                 replacing = 1;
 237                                 break;
 238                         }
 239                         item = item->next;
 240                 }
 241         } else {
 242                 while (item) {
 243                         if (key == item->key) {
 244                                 replacing = 1;
 245                                 break;
 246                         }
 247                         item = item->next;
 248                 }
 249         }
 250
 251         if (replacing) {
 252                 const void *old;
 253
 254                 old = item->data;
 255                 item->data = data;
 256                 RELKEY(table, item->key);
 257                 item->key = DUPKEY(table, key);
 258
 259                 return (void *)old;
 260         } else {
 261                 HashItem *nitem;
 262
 263                 nitem = wmalloc(sizeof(HashItem));
 264                 nitem->key = DUPKEY(table, key);
 265                 nitem->data = data;
 266                 nitem->next = table->table[h];
 267                 table->table[h] = nitem;
 268
 269                 table->itemCount++;
 270         }
 271
 272         /* OPTIMIZE: put this in an idle handler. */
 273         if (table->itemCount > table->size) {
 274 #ifdef DEBUG0
 275                 printf("rebuilding hash table...\n");
 276 #endif
 277                 rebuildTable(table);
 278 #ifdef DEBUG0
 279                 printf("finished rebuild.\n");
 280 #endif
 281         }
 282
 283         return NULL;
 284 }
 285
 286 static HashItem *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 && (*table->callbacks.keyIsEqual) (key, item->key))
 294             || (!table->callbacks.keyIsEqual && key == item->key)) {
 295
 296                 next = item->next;
 297                 RELKEY(table, item->key);
 298                 wfree(item);
 299
 300                 table->itemCount--;
 301
 302                 return next;
 303         }
 304
 305         item->next = deleteFromList(table, item->next, key);
 306
 307         return item;
 308 }
 309
 310 void WMHashRemove(WMHashTable * table, const void *key)
 311 {
 312         unsigned h;
 313
 314         h = HASH(table, key);
 315
 316         table->table[h] = deleteFromList(table, table->table[h], key);
 317 }
 318
 319 WMHashEnumerator WMEnumerateHashTable(WMHashTable * table)
 320 {
 321         WMHashEnumerator enumerator;
 322
 323         enumerator.table = table;
 324         enumerator.index = 0;
 325         enumerator.nextItem = table->table[0];
 326
 327         return enumerator;
 328 }
 329
 330 void *WMNextHashEnumeratorItem(WMHashEnumerator * enumerator)
 331 {
 332         const void *data = NULL;
 333
 334         /* this assumes the table doesn't change between
 335          * WMEnumerateHashTable() and WMNextHashEnumeratorItem() calls */
 336
 337         if (enumerator->nextItem == NULL) {
 338                 HashTable *table = enumerator->table;
 339                 while (++enumerator->index < table->size) {
 340                         if (table->table[enumerator->index] != NULL) {
 341                                 enumerator->nextItem = table->table[enumerator->index];
 342                                 break;
 343                         }
 344                 }
 345         }
 346
 347         if (enumerator->nextItem) {
 348                 data = ((HashItem *) enumerator->nextItem)->data;
 349                 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
 350         }
 351
 352         return (void *)data;
 353 }
 354
 355 void *WMNextHashEnumeratorKey(WMHashEnumerator * enumerator)
 356 {
 357         const void *key = NULL;
 358
 359         /* this assumes the table doesn't change between
 360          * WMEnumerateHashTable() and WMNextHashEnumeratorKey() calls */
 361
 362         if (enumerator->nextItem == NULL) {
 363                 HashTable *table = enumerator->table;
 364                 while (++enumerator->index < table->size) {
 365                         if (table->table[enumerator->index] != NULL) {
 366                                 enumerator->nextItem = table->table[enumerator->index];
 367                                 break;
 368                         }
 369                 }
 370         }
 371
 372         if (enumerator->nextItem) {
 373                 key = ((HashItem *) enumerator->nextItem)->key;
 374                 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
 375         }
 376
 377         return (void *)key;
 378 }
 379
 380 Bool WMNextHashEnumeratorItemAndKey(WMHashEnumerator * enumerator, void **item, void **key)
 381 {
 382         /* this assumes the table doesn't change between
 383          * WMEnumerateHashTable() and WMNextHashEnumeratorItemAndKey() calls */
 384
 385         if (enumerator->nextItem == NULL) {
 386                 HashTable *table = enumerator->table;
 387                 while (++enumerator->index < table->size) {
 388                         if (table->table[enumerator->index] != NULL) {
 389                                 enumerator->nextItem = table->table[enumerator->index];
 390                                 break;
 391                         }
 392                 }
 393         }
 394
 395         if (enumerator->nextItem) {
 396                 if (item)
 397                         *item = (void *)((HashItem *) enumerator->nextItem)->data;
 398                 if (key)
 399                         *key = (void *)((HashItem *) enumerator->nextItem)->key;
 400                 enumerator->nextItem = ((HashItem *) enumerator->nextItem)->next;
 401
 402                 return True;
 403         }
 404
 405         return False;
 406 }
 407
 408 static Bool compareStrings(const char *key1, const char *key2)
 409 {
 410         return strcmp(key1, key2) == 0;
 411 }
 412
 413 typedef unsigned (*hashFunc) (const void *);
 414 typedef Bool(*isEqualFunc) (const void *, const void *);
 415 typedef void *(*retainFunc) (const void *);
 416 typedef void (*releaseFunc) (const void *);
 417
 418 const WMHashTableCallbacks WMIntHashCallbacks = {
 419         NULL,
 420         NULL,
 421         NULL,
 422         NULL
 423 };
 424
 425 const WMHashTableCallbacks WMStringHashCallbacks = {
 426         (hashFunc) hashString,
 427         (isEqualFunc) compareStrings,
 428         (retainFunc) wstrdup,
 429         (releaseFunc) wfree
 430 };
 431
 432 const WMHashTableCallbacks WMStringPointerHashCallbacks = {
 433         (hashFunc) hashString,
 434         (isEqualFunc) compareStrings,
 435         NULL,
 436         NULL
 437 };