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