src/libgame/hash.c

   1 // ============================================================================
   2 // Artsoft Retro-Game Library
   3 // ----------------------------------------------------------------------------
   4 // (c) 1995-2014 by Artsoft Entertainment
   5 //                  Holger Schemel
   6 //                  info@artsoft.org
   7 //                  https://www.artsoft.org/
   8 // ----------------------------------------------------------------------------
   9 // hash.c
  10 // ============================================================================
  11
  12 /*
  13  * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
  14  *
  15  * Permission is hereby granted, free of charge, to any person obtaining a copy
  16  * of this software and associated documentation files (the "Software"), to
  17  * deal in the Software without restriction, including without limitation the
  18  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  19  * sell copies of the Software, and to permit persons to whom the Software is
  20  * furnished to do so, subject to the following conditions:
  21  *
  22  * The above copyright notice and this permission notice shall be included in
  23  * all copies of the Software and its documentation and acknowledgment shall be
  24  * given in the documentation and software packages that this Software was
  25  * used.
  26  *
  27  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  28  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  29  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  30  * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  31  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  32  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  33  * */
  34
  35 #include <stdlib.h>
  36 #include <stdio.h>
  37 #include <string.h>
  38
  39 #include "hash.h"
  40
  41
  42 /*****************************************************************************/
  43 struct hashtable *
  44 create_hashtable_ext(unsigned int minsize, float maxloadfactor,
  45                      unsigned int (*hashf) (void*),
  46                      int (*eqf) (void*, void*),
  47                      void (*freekfn) (void*),
  48                      void (*freevfn) (void*))
  49 {
  50   struct hashtable *h;
  51   unsigned int i, size = 1u;
  52
  53   /* Check requested hashtable isn't too large */
  54   if (minsize > (1u << 31))
  55     return NULL;
  56
  57   /* Enforce size as power of 2 */
  58   while (size < minsize)
  59     size <<= 1;
  60
  61   h = (struct hashtable *)malloc(sizeof(struct hashtable));
  62
  63   if (h == NULL)
  64     return NULL;
  65
  66   h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
  67
  68   if (h->table == NULL)
  69   {
  70     free(h);
  71
  72     return NULL;
  73   }
  74
  75   for (i = 0; i < size; i++)
  76     h->table[i] = NULL;
  77
  78   h->tablelength  = size;
  79   h->entrycount   = 0;
  80   h->hashfn       = hashf;
  81   h->eqfn         = eqf;
  82   h->loadlimit    = (unsigned int) ((float)size * maxloadfactor);
  83   h->freekfn      = freekfn;
  84   h->freevfn      = freevfn;
  85
  86   return h;
  87 }
  88
  89 struct hashtable *
  90 create_hashtable(unsigned int (*hashf) (void*),
  91                  int (*eqf) (void*, void*),
  92                  void (*freekfn) (void*),
  93                  void (*freevfn) (void*))
  94 {
  95   return create_hashtable_ext(16, 0.75, hashf, eqf, freekfn, freevfn);
  96 }
  97
  98 /*****************************************************************************/
  99 static unsigned int
 100 hash(struct hashtable *h, void *k)
 101 {
 102   /* Aim to protect against poor hash functions by adding logic here
 103    * - logic taken from java 1.4 hashtable source */
 104
 105   unsigned int i = h->hashfn(k);
 106
 107   i += ~(i << 9);
 108   i ^=  ((i >> 14) | (i << 18)); /* >>> */
 109   i +=  (i << 4);
 110   i ^=  ((i >> 10) | (i << 22)); /* >>> */
 111
 112   return i;
 113 }
 114
 115 /*****************************************************************************/
 116 static unsigned int
 117 indexFor(unsigned int tablelength, unsigned int hashvalue)
 118 {
 119   /* Only works if tablelength == 2^N */
 120   return (hashvalue & (tablelength - 1u));
 121 }
 122
 123 /*****************************************************************************/
 124 static int
 125 hashtable_expand(struct hashtable *h)
 126 {
 127   /* Double the size of the table to accomodate more entries */
 128   struct entry **newtable;
 129   struct entry *e;
 130   struct entry **pE;
 131   unsigned int newsize, i, index;
 132
 133   /* Check we're not hitting max capacity */
 134   if (0 == (newsize = (h->tablelength << 1)))
 135     return 0;
 136
 137   newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
 138
 139   if (newtable != NULL)
 140   {
 141     memset(newtable, 0, newsize * sizeof(struct entry *));
 142
 143     /* This algorithm is not 'stable'. ie. it reverses the list
 144      * when it transfers entries between the tables */
 145     for (i = 0; i < h->tablelength; i++)
 146     {
 147       while ((e = h->table[i]) != NULL)
 148       {
 149         h->table[i] = e->next;
 150         index = indexFor(newsize, e->h);
 151         e->next = newtable[index];
 152         newtable[index] = e;
 153       }
 154     }
 155
 156     free(h->table);
 157     h->table = newtable;
 158   }
 159   else          /* Plan B: realloc instead */
 160   {
 161     newtable = (struct entry **)
 162       realloc(h->table, newsize * sizeof(struct entry *));
 163
 164     if (newtable == NULL)
 165       return 0;
 166
 167     h->table = newtable;
 168
 169     for (i = h->tablelength; i < newsize; i++)
 170       newtable[i] = NULL;
 171
 172     for (i = 0; i < h->tablelength; i++)
 173     {
 174       for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
 175       {
 176         index = indexFor(newsize, e->h);
 177
 178         if (index == i)
 179         {
 180           pE = &(e->next);
 181         }
 182         else
 183         {
 184           *pE = e->next;
 185           e->next = newtable[index];
 186           newtable[index] = e;
 187         }
 188       }
 189     }
 190   }
 191
 192   h->tablelength = newsize;
 193   h->loadlimit <<= 1;
 194
 195   return -1;
 196 }
 197
 198 /*****************************************************************************/
 199 unsigned int
 200 hashtable_count(struct hashtable *h)
 201 {
 202   return h->entrycount;
 203 }
 204
 205 /*****************************************************************************/
 206 int
 207 hashtable_insert(struct hashtable *h, void *k, void *v)
 208 {
 209   /* This method allows duplicate keys - but they shouldn't be used */
 210   unsigned int index;
 211   struct entry *e;
 212
 213   if (++(h->entrycount) > h->loadlimit)
 214   {
 215     /* Ignore the return value. If expand fails, we should
 216      * still try cramming just this value into the existing table
 217      * -- we may not have memory for a larger table, but one more
 218      * element may be ok. Next time we insert, we'll try expanding again.*/
 219
 220     hashtable_expand(h);
 221   }
 222
 223   e = (struct entry *)malloc(sizeof(struct entry));
 224
 225   if (e == NULL)
 226   {
 227     --(h->entrycount);
 228
 229     return 0;
 230   }
 231
 232   e->h = hash(h, k);
 233   index = indexFor(h->tablelength, e->h);
 234   e->k = k;
 235   e->v = v;
 236   e->next = h->table[index];
 237   h->table[index] = e;
 238
 239   return -1;
 240 }
 241
 242 /*****************************************************************************/
 243 int
 244 hashtable_change(struct hashtable *h, void *k, void *v)
 245 {
 246   struct entry *e;
 247   unsigned int hashvalue, index;
 248
 249   hashvalue = hash(h, k);
 250   index = indexFor(h->tablelength, hashvalue);
 251   e = h->table[index];
 252
 253   while (e != NULL)
 254   {
 255     /* Check hash value to short circuit heavier comparison */
 256     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 257     {
 258       if (h->freevfn != NULL)
 259         h->freevfn(e->v);
 260       e->v = v;
 261
 262       return -1;
 263     }
 264
 265     e = e->next;
 266   }
 267
 268   return 0;
 269 }
 270
 271 /*****************************************************************************/
 272 int /* checks if key exists */
 273 hashtable_exists(struct hashtable *h, void *k)
 274 {
 275   struct entry *e;
 276   unsigned int hashvalue, index;
 277
 278   hashvalue = hash(h, k);
 279   index = indexFor(h->tablelength, hashvalue);
 280   e = h->table[index];
 281
 282   while (e != NULL)
 283   {
 284     /* Check hash value to short circuit heavier comparison */
 285     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 286       return 1;
 287
 288     e = e->next;
 289   }
 290
 291   return 0;
 292 }
 293
 294 /*****************************************************************************/
 295 void * /* returns value associated with key */
 296 hashtable_search(struct hashtable *h, void *k)
 297 {
 298   struct entry *e;
 299   unsigned int hashvalue, index;
 300
 301   hashvalue = hash(h, k);
 302   index = indexFor(h->tablelength, hashvalue);
 303   e = h->table[index];
 304
 305   while (e != NULL)
 306   {
 307     /* Check hash value to short circuit heavier comparison */
 308     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 309       return e->v;
 310
 311     e = e->next;
 312   }
 313
 314   return NULL;
 315 }
 316
 317 /*****************************************************************************/
 318 void * /* returns value associated with key */
 319 hashtable_remove(struct hashtable *h, void *k)
 320 {
 321   /* TODO: consider compacting the table when the load factor drops enough,
 322    *       or provide a 'compact' method. */
 323
 324   struct entry *e;
 325   struct entry **pE;
 326   void *v;
 327   unsigned int index = indexFor(h->tablelength, hash(h, k));
 328
 329   pE = &(h->table[index]);
 330   e = *pE;
 331
 332   while (e != NULL)
 333   {
 334     if (h->eqfn(k, e->k))
 335     {
 336       *pE = e->next;
 337       h->entrycount--;
 338       v = NULL;
 339       if (h->freekfn != NULL)
 340         h->freekfn(e->k);
 341       if (h->freevfn != NULL)
 342         h->freevfn(e->v);
 343       else
 344         v = e->v;
 345       free(e);
 346
 347       return v;
 348     }
 349
 350     pE = &(e->next);
 351     e = e->next;
 352   }
 353
 354   return NULL;
 355 }
 356
 357 /*****************************************************************************/
 358 /* destroy */
 359 void
 360 hashtable_destroy(struct hashtable *h)
 361 {
 362   unsigned int i;
 363   struct entry *e, *f;
 364   struct entry **table = h->table;
 365
 366   for (i = 0; i < h->tablelength; i++)
 367   {
 368     e = table[i];
 369
 370     while (e != NULL)
 371     {
 372       f = e;
 373       e = e->next;
 374       if (h->freekfn != NULL)
 375         h->freekfn(f->k);
 376       if (h->freevfn != NULL)
 377         h->freevfn(f->v);
 378
 379       free(f);
 380     }
 381   }
 382
 383   free(h->table);
 384   free(h);
 385 }
 386
 387 /*****************************************************************************/
 388 /* hashtable_iterator    - iterator constructor */
 389
 390 struct hashtable_itr *
 391 hashtable_iterator(struct hashtable *h)
 392 {
 393   unsigned int i, tablelength;
 394   struct hashtable_itr *itr = (struct hashtable_itr *)
 395     malloc(sizeof(struct hashtable_itr));
 396
 397   if (itr == NULL)
 398     return NULL;
 399
 400   itr->h = h;
 401   itr->e = NULL;
 402   tablelength = h->tablelength;
 403   itr->index = tablelength;
 404
 405   if (0 == h->entrycount)
 406     return itr;
 407
 408   for (i = 0; i < tablelength; i++)
 409   {
 410     if (h->table[i] != NULL)
 411     {
 412       itr->e = h->table[i];
 413       itr->index = i;
 414
 415       break;
 416     }
 417   }
 418
 419   return itr;
 420 }
 421
 422 /*****************************************************************************/
 423 /* key - return the key of the (key, value) pair at the current position */
 424
 425 void *
 426 hashtable_iterator_key(struct hashtable_itr *itr)
 427 {
 428   if (itr == NULL || itr->e == NULL)
 429     return NULL;
 430
 431   return itr->e->k;
 432 }
 433
 434 /*****************************************************************************/
 435 /* value - return the value of the (key, value) pair at the current position */
 436
 437 void *
 438 hashtable_iterator_value(struct hashtable_itr *itr)
 439 {
 440   if (itr == NULL || itr->e == NULL)
 441     return NULL;
 442
 443   return itr->e->v;
 444 }
 445
 446 /*****************************************************************************/
 447 /* advance - advance the iterator to the next element
 448  *           returns zero if advanced to end of table */
 449
 450 int
 451 hashtable_iterator_advance(struct hashtable_itr *itr)
 452 {
 453   unsigned int j, tablelength;
 454   struct entry **table;
 455   struct entry *next;
 456
 457   if (itr->e == NULL)
 458     return 0; /* stupidity check */
 459
 460   next = itr->e->next;
 461   if (next != NULL)
 462   {
 463     itr->e = next;
 464
 465     return -1;
 466   }
 467
 468   tablelength = itr->h->tablelength;
 469   if (tablelength <= (j = ++(itr->index)))
 470   {
 471     itr->e = NULL;
 472
 473     return 0;
 474   }
 475
 476   table = itr->h->table;
 477   while ((next = table[j]) == NULL)
 478   {
 479     if (++j >= tablelength)
 480     {
 481       itr->index = tablelength;
 482
 483       return 0;
 484     }
 485   }
 486
 487   itr->index = j;
 488   itr->e = next;
 489
 490   return -1;
 491 }
 492
 493 /*****************************************************************************/
 494 /* call function for all hashtable entries */
 495 void
 496 hashtable_foreach(struct hashtable *h, hashtable_fn fn, void *userdata)
 497 {
 498   if (h == NULL)
 499     return;
 500
 501   if (hashtable_count(h) == 0)
 502     return;
 503
 504   struct hashtable_itr *itr = hashtable_iterator(h);
 505
 506   do
 507   {
 508     fn(hashtable_iterator_key(itr), hashtable_iterator_value(itr), userdata);
 509   }
 510   while (hashtable_iterator_advance(itr));
 511
 512   free(itr);
 513 }
 514
 515 /*****************************************************************************/
 516 /* call function for all hashtable entries and remove them, if function returned 1 */
 517 unsigned int
 518 hashtable_foreach_remove(struct hashtable *h, hashtable_remove_fn fn, void *userdata)
 519 {
 520   if (h == NULL)
 521     return 0;
 522
 523   if (hashtable_count(h) == 0)
 524     return 0;
 525
 526   struct hashtable *remove = create_hashtable(h->hashfn, h->eqfn, NULL, NULL);
 527   struct hashtable_itr *itr = hashtable_iterator(h);
 528
 529   do
 530   {
 531     if (fn(hashtable_iterator_key(itr), hashtable_iterator_value(itr), userdata))
 532       hashtable_insert(remove, hashtable_iterator_key(itr), "1");
 533   }
 534   while (hashtable_iterator_advance(itr));
 535
 536   free(itr);
 537
 538   unsigned int num_removed = 0;
 539
 540   if (hashtable_count(remove) > 0)
 541   {
 542     struct hashtable_itr *itr_remove = hashtable_iterator(remove);
 543
 544     do
 545     {
 546       hashtable_remove(h, hashtable_iterator_key(itr_remove));
 547       num_removed++;
 548     }
 549     while (hashtable_iterator_advance(itr_remove));
 550
 551     free(itr_remove);
 552   }
 553
 554   hashtable_destroy(remove);
 555
 556   return num_removed;
 557 }
 558
 559 /*****************************************************************************/
 560 /* remove_all hashtable entries */
 561 unsigned int
 562 hashtable_remove_all(struct hashtable *h)
 563 {
 564   /* TODO: this function should directly remove all hashtable entries */
 565
 566   if (h == NULL)
 567     return 0;
 568
 569   if (hashtable_count(h) == 0)
 570     return 0;
 571
 572   struct hashtable *remove = create_hashtable(h->hashfn, h->eqfn, NULL, NULL);
 573   struct hashtable_itr *itr = hashtable_iterator(h);
 574
 575   do
 576   {
 577     hashtable_insert(remove, hashtable_iterator_key(itr), "1");
 578   }
 579   while (hashtable_iterator_advance(itr));
 580
 581   free(itr);
 582
 583   struct hashtable_itr *itr_remove = hashtable_iterator(remove);
 584   unsigned int num_removed = 0;
 585
 586   do
 587   {
 588     hashtable_remove(h, hashtable_iterator_key(itr_remove));
 589     num_removed++;
 590   }
 591   while (hashtable_iterator_advance(itr_remove));
 592
 593   free(itr_remove);
 594
 595   hashtable_destroy(remove);
 596
 597   return num_removed;
 598 }