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