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(unsigned int minsize, float maxloadfactor,
  45                  unsigned int (*hashf) (void*),
  46                  int (*eqf) (void*,void*))
  47 {
  48   struct hashtable *h;
  49   unsigned int i, size = 1u;
  50
  51   /* Check requested hashtable isn't too large */
  52   if (minsize > (1u << 31))
  53     return NULL;
  54
  55   /* Enforce size as power of 2 */
  56   while (size < minsize)
  57     size <<= 1;
  58
  59   h = (struct hashtable *)malloc(sizeof(struct hashtable));
  60
  61   if (h == NULL)
  62     return NULL;
  63
  64   h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
  65
  66   if (h->table == NULL)
  67   {
  68     free(h);
  69
  70     return NULL;
  71   }
  72
  73   for (i=0; i < size; i++)
  74     h->table[i] = NULL;
  75
  76   h->tablelength  = size;
  77   h->entrycount   = 0;
  78   h->hashfn       = hashf;
  79   h->eqfn         = eqf;
  80   h->loadlimit    = (unsigned int) ((float)size * maxloadfactor);
  81
  82   return h;
  83 }
  84
  85 /*****************************************************************************/
  86 static unsigned int
  87 hash(struct hashtable *h, void *k)
  88 {
  89   /* Aim to protect against poor hash functions by adding logic here
  90    * - logic taken from java 1.4 hashtable source */
  91
  92   unsigned int i = h->hashfn(k);
  93
  94   i += ~(i << 9);
  95   i ^=  ((i >> 14) | (i << 18)); /* >>> */
  96   i +=  (i << 4);
  97   i ^=  ((i >> 10) | (i << 22)); /* >>> */
  98
  99   return i;
 100 }
 101
 102 /*****************************************************************************/
 103 static unsigned int
 104 indexFor(unsigned int tablelength, unsigned int hashvalue)
 105 {
 106   /* Only works if tablelength == 2^N */
 107   return (hashvalue & (tablelength - 1u));
 108 }
 109
 110 /*****************************************************************************/
 111 static int
 112 hashtable_expand(struct hashtable *h)
 113 {
 114   /* Double the size of the table to accomodate more entries */
 115   struct entry **newtable;
 116   struct entry *e;
 117   struct entry **pE;
 118   unsigned int newsize, i, index;
 119
 120   /* Check we're not hitting max capacity */
 121   if (0 == (newsize = (h->tablelength << 1)))
 122     return 0;
 123
 124   newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
 125
 126   if (newtable != NULL)
 127   {
 128     memset(newtable, 0, newsize * sizeof(struct entry *));
 129
 130     /* This algorithm is not 'stable'. ie. it reverses the list
 131      * when it transfers entries between the tables */
 132     for (i = 0; i < h->tablelength; i++)
 133     {
 134       while ((e = h->table[i]) != NULL)
 135       {
 136         h->table[i] = e->next;
 137         index = indexFor(newsize,e->h);
 138         e->next = newtable[index];
 139         newtable[index] = e;
 140       }
 141     }
 142
 143     free(h->table);
 144     h->table = newtable;
 145   }
 146   else          /* Plan B: realloc instead */
 147   {
 148     newtable = (struct entry **)
 149       realloc(h->table, newsize * sizeof(struct entry *));
 150
 151     if (newtable == NULL)
 152       return 0;
 153
 154     h->table = newtable;
 155
 156     for (i = h->tablelength; i < newsize; i++)
 157       newtable[i] = NULL;
 158
 159     for (i = 0; i < h->tablelength; i++)
 160     {
 161       for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
 162       {
 163         index = indexFor(newsize,e->h);
 164
 165         if (index == i)
 166         {
 167           pE = &(e->next);
 168         }
 169         else
 170         {
 171           *pE = e->next;
 172           e->next = newtable[index];
 173           newtable[index] = e;
 174         }
 175       }
 176     }
 177   }
 178
 179   h->tablelength = newsize;
 180   h->loadlimit <<= 1;
 181
 182   return -1;
 183 }
 184
 185 /*****************************************************************************/
 186 unsigned int
 187 hashtable_count(struct hashtable *h)
 188 {
 189   return h->entrycount;
 190 }
 191
 192 /*****************************************************************************/
 193 int
 194 hashtable_insert(struct hashtable *h, void *k, void *v)
 195 {
 196   /* This method allows duplicate keys - but they shouldn't be used */
 197   unsigned int index;
 198   struct entry *e;
 199
 200   if (++(h->entrycount) > h->loadlimit)
 201   {
 202     /* Ignore the return value. If expand fails, we should
 203      * still try cramming just this value into the existing table
 204      * -- we may not have memory for a larger table, but one more
 205      * element may be ok. Next time we insert, we'll try expanding again.*/
 206
 207     hashtable_expand(h);
 208   }
 209
 210   e = (struct entry *)malloc(sizeof(struct entry));
 211
 212   if (e == NULL)
 213   {
 214     --(h->entrycount);
 215
 216     return 0;
 217   }
 218
 219   e->h = hash(h,k);
 220   index = indexFor(h->tablelength,e->h);
 221   e->k = k;
 222   e->v = v;
 223   e->next = h->table[index];
 224   h->table[index] = e;
 225
 226   return -1;
 227 }
 228
 229 /*****************************************************************************/
 230 int
 231 hashtable_change(struct hashtable *h, void *k, void *v)
 232 {
 233   struct entry *e;
 234   unsigned int hashvalue, index;
 235
 236   hashvalue = hash(h,k);
 237   index = indexFor(h->tablelength,hashvalue);
 238   e = h->table[index];
 239
 240   while (e != NULL)
 241   {
 242     /* Check hash value to short circuit heavier comparison */
 243     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 244     {
 245       free(e->v);
 246       e->v = v;
 247
 248       return -1;
 249     }
 250
 251     e = e->next;
 252   }
 253
 254   return 0;
 255 }
 256
 257 /*****************************************************************************/
 258 void * /* returns value associated with key */
 259 hashtable_search(struct hashtable *h, void *k)
 260 {
 261   struct entry *e;
 262   unsigned int hashvalue, index;
 263
 264   hashvalue = hash(h,k);
 265   index = indexFor(h->tablelength,hashvalue);
 266   e = h->table[index];
 267
 268   while (e != NULL)
 269   {
 270     /* Check hash value to short circuit heavier comparison */
 271     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 272       return e->v;
 273
 274     e = e->next;
 275   }
 276
 277   return NULL;
 278 }
 279
 280 /*****************************************************************************/
 281 void * /* returns value associated with key */
 282 hashtable_remove(struct hashtable *h, void *k)
 283 {
 284   /* TODO: consider compacting the table when the load factor drops enough,
 285    *       or provide a 'compact' method. */
 286
 287   struct entry *e;
 288   struct entry **pE;
 289   void *v;
 290   unsigned int index = indexFor(h->tablelength,hash(h,k));
 291
 292   pE = &(h->table[index]);
 293   e = *pE;
 294
 295   while (e != NULL)
 296   {
 297     if (h->eqfn(k, e->k))
 298     {
 299       *pE = e->next;
 300       h->entrycount--;
 301       v = e->v;
 302       free(e->k);
 303       free(e);
 304
 305       return v;
 306     }
 307
 308     pE = &(e->next);
 309     e = e->next;
 310   }
 311
 312   return NULL;
 313 }
 314
 315 /*****************************************************************************/
 316 /* destroy */
 317 void
 318 hashtable_destroy(struct hashtable *h, int free_values)
 319 {
 320   unsigned int i;
 321   struct entry *e, *f;
 322   struct entry **table = h->table;
 323
 324   for (i = 0; i < h->tablelength; i++)
 325   {
 326     e = table[i];
 327
 328     while (e != NULL)
 329     {
 330       f = e;
 331       e = e->next;
 332       free(f->k);
 333
 334       if (free_values)
 335         free(f->v);
 336
 337       free(f);
 338     }
 339   }
 340
 341   free(h->table);
 342   free(h);
 343 }
 344
 345
 346 /*****************************************************************************/
 347 /* hashtable_iterator    - iterator constructor */
 348
 349 struct hashtable_itr *
 350 hashtable_iterator(struct hashtable *h)
 351 {
 352   unsigned int i, tablelength;
 353   struct hashtable_itr *itr = (struct hashtable_itr *)
 354     malloc(sizeof(struct hashtable_itr));
 355
 356   if (itr == NULL)
 357     return NULL;
 358
 359   itr->h = h;
 360   itr->e = NULL;
 361   tablelength = h->tablelength;
 362   itr->index = tablelength;
 363
 364   if (0 == h->entrycount)
 365     return itr;
 366
 367   for (i = 0; i < tablelength; i++)
 368   {
 369     if (h->table[i] != NULL)
 370     {
 371       itr->e = h->table[i];
 372       itr->index = i;
 373
 374       break;
 375     }
 376   }
 377
 378   return itr;
 379 }
 380
 381 /*****************************************************************************/
 382 /* key - return the key of the (key,value) pair at the current position */
 383
 384 void *
 385 hashtable_iterator_key(struct hashtable_itr *i)
 386 {
 387   return i->e->k;
 388 }
 389
 390 /*****************************************************************************/
 391 /* value - return the value of the (key,value) pair at the current position */
 392
 393 void *
 394 hashtable_iterator_value(struct hashtable_itr *i)
 395 {
 396   return i->e->v;
 397 }
 398
 399 /*****************************************************************************/
 400 /* advance - advance the iterator to the next element
 401  *           returns zero if advanced to end of table */
 402
 403 int
 404 hashtable_iterator_advance(struct hashtable_itr *itr)
 405 {
 406   unsigned int j,tablelength;
 407   struct entry **table;
 408   struct entry *next;
 409
 410   if (itr->e == NULL)
 411     return 0; /* stupidity check */
 412
 413   next = itr->e->next;
 414   if (next != NULL)
 415   {
 416     itr->e = next;
 417
 418     return -1;
 419   }
 420
 421   tablelength = itr->h->tablelength;
 422   if (tablelength <= (j = ++(itr->index)))
 423   {
 424     itr->e = NULL;
 425
 426     return 0;
 427   }
 428
 429   table = itr->h->table;
 430   while ((next = table[j]) == NULL)
 431   {
 432     if (++j >= tablelength)
 433     {
 434       itr->index = tablelength;
 435
 436       return 0;
 437     }
 438   }
 439
 440   itr->index = j;
 441   itr->e = next;
 442
 443   return -1;
 444 }