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