WINGs/hashtable.c

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