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 void * /* returns value associated with key */
 273 hashtable_search(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 e->v;
 287
 288     e = e->next;
 289   }
 290
 291   return NULL;
 292 }
 293
 294 /*****************************************************************************/
 295 void * /* returns value associated with key */
 296 hashtable_remove(struct hashtable *h, void *k)
 297 {
 298   /* TODO: consider compacting the table when the load factor drops enough,
 299    *       or provide a 'compact' method. */
 300
 301   struct entry *e;
 302   struct entry **pE;
 303   void *v;
 304   unsigned int index = indexFor(h->tablelength, hash(h, k));
 305
 306   pE = &(h->table[index]);
 307   e = *pE;
 308
 309   while (e != NULL)
 310   {
 311     if (h->eqfn(k, e->k))
 312     {
 313       *pE = e->next;
 314       h->entrycount--;
 315       v = NULL;
 316       if (h->freekfn != NULL)
 317         h->freekfn(e->k);
 318       if (h->freevfn != NULL)
 319         h->freevfn(e->v);
 320       else
 321         v = e->v;
 322       free(e);
 323
 324       return v;
 325     }
 326
 327     pE = &(e->next);
 328     e = e->next;
 329   }
 330
 331   return NULL;
 332 }
 333
 334 /*****************************************************************************/
 335 /* destroy */
 336 void
 337 hashtable_destroy(struct hashtable *h)
 338 {
 339   unsigned int i;
 340   struct entry *e, *f;
 341   struct entry **table = h->table;
 342
 343   for (i = 0; i < h->tablelength; i++)
 344   {
 345     e = table[i];
 346
 347     while (e != NULL)
 348     {
 349       f = e;
 350       e = e->next;
 351       if (h->freekfn != NULL)
 352         h->freekfn(f->k);
 353       if (h->freevfn != NULL)
 354         h->freevfn(f->v);
 355
 356       free(f);
 357     }
 358   }
 359
 360   free(h->table);
 361   free(h);
 362 }
 363
 364 /*****************************************************************************/
 365 /* hashtable_iterator    - iterator constructor */
 366
 367 struct hashtable_itr *
 368 hashtable_iterator(struct hashtable *h)
 369 {
 370   unsigned int i, tablelength;
 371   struct hashtable_itr *itr = (struct hashtable_itr *)
 372     malloc(sizeof(struct hashtable_itr));
 373
 374   if (itr == NULL)
 375     return NULL;
 376
 377   itr->h = h;
 378   itr->e = NULL;
 379   tablelength = h->tablelength;
 380   itr->index = tablelength;
 381
 382   if (0 == h->entrycount)
 383     return itr;
 384
 385   for (i = 0; i < tablelength; i++)
 386   {
 387     if (h->table[i] != NULL)
 388     {
 389       itr->e = h->table[i];
 390       itr->index = i;
 391
 392       break;
 393     }
 394   }
 395
 396   return itr;
 397 }
 398
 399 /*****************************************************************************/
 400 /* key - return the key of the (key, value) pair at the current position */
 401
 402 void *
 403 hashtable_iterator_key(struct hashtable_itr *i)
 404 {
 405   return i->e->k;
 406 }
 407
 408 /*****************************************************************************/
 409 /* value - return the value of the (key, value) pair at the current position */
 410
 411 void *
 412 hashtable_iterator_value(struct hashtable_itr *i)
 413 {
 414   return i->e->v;
 415 }
 416
 417 /*****************************************************************************/
 418 /* advance - advance the iterator to the next element
 419  *           returns zero if advanced to end of table */
 420
 421 int
 422 hashtable_iterator_advance(struct hashtable_itr *itr)
 423 {
 424   unsigned int j, tablelength;
 425   struct entry **table;
 426   struct entry *next;
 427
 428   if (itr->e == NULL)
 429     return 0; /* stupidity check */
 430
 431   next = itr->e->next;
 432   if (next != NULL)
 433   {
 434     itr->e = next;
 435
 436     return -1;
 437   }
 438
 439   tablelength = itr->h->tablelength;
 440   if (tablelength <= (j = ++(itr->index)))
 441   {
 442     itr->e = NULL;
 443
 444     return 0;
 445   }
 446
 447   table = itr->h->table;
 448   while ((next = table[j]) == NULL)
 449   {
 450     if (++j >= tablelength)
 451     {
 452       itr->index = tablelength;
 453
 454       return 0;
 455     }
 456   }
 457
 458   itr->index = j;
 459   itr->e = next;
 460
 461   return -1;
 462 }