src/libgame/hash.c

   1 /***********************************************************
   2 * Artsoft Retro-Game Library                               *
   3 *----------------------------------------------------------*
   4 * (c) 1994-2006 Artsoft Entertainment                      *
   5 *               Holger Schemel                             *
   6 *               Detmolder Strasse 189                      *
   7 *               33604 Bielefeld                            *
   8 *               Germany                                    *
   9 *               e-mail: info@artsoft.org                   *
  10 *----------------------------------------------------------*
  11 * hash.c                                                   *
  12 ***********************************************************/
  13
  14 /*
  15  * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
  16  *
  17  * Permission is hereby granted, free of charge, to any person obtaining a copy
  18  * of this software and associated documentation files (the "Software"), to
  19  * deal in the Software without restriction, including without limitation the
  20  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  21  * sell copies of the Software, and to permit persons to whom the Software is
  22  * furnished to do so, subject to the following conditions:
  23  *
  24  * The above copyright notice and this permission notice shall be included in
  25  * all copies of the Software and its documentation and acknowledgment shall be
  26  * given in the documentation and software packages that this Software was
  27  * used.
  28  *
  29  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  30  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  31  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  32  * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  33  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  34  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  35  * */
  36
  37 #include <stdlib.h>
  38 #include <stdio.h>
  39 #include <string.h>
  40
  41 #include "hash.h"
  42
  43
  44 /*****************************************************************************/
  45 struct hashtable *
  46 create_hashtable(unsigned int minsize, float maxloadfactor,
  47                  unsigned int (*hashf) (void*),
  48                  int (*eqf) (void*,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
  84   return h;
  85 }
  86
  87 /*****************************************************************************/
  88 static unsigned int
  89 hash(struct hashtable *h, void *k)
  90 {
  91   /* Aim to protect against poor hash functions by adding logic here
  92    * - logic taken from java 1.4 hashtable source */
  93
  94   unsigned int i = h->hashfn(k);
  95
  96   i += ~(i << 9);
  97   i ^=  ((i >> 14) | (i << 18)); /* >>> */
  98   i +=  (i << 4);
  99   i ^=  ((i >> 10) | (i << 22)); /* >>> */
 100
 101   return i;
 102 }
 103
 104 /*****************************************************************************/
 105 static unsigned int
 106 indexFor(unsigned int tablelength, unsigned int hashvalue)
 107 {
 108   /* Only works if tablelength == 2^N */
 109   return (hashvalue & (tablelength - 1u));
 110 }
 111
 112 /*****************************************************************************/
 113 static int
 114 hashtable_expand(struct hashtable *h)
 115 {
 116   /* Double the size of the table to accomodate more entries */
 117   struct entry **newtable;
 118   struct entry *e;
 119   struct entry **pE;
 120   unsigned int newsize, i, index;
 121
 122   /* Check we're not hitting max capacity */
 123   if (0 == (newsize = (h->tablelength << 1)))
 124     return 0;
 125
 126   newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
 127
 128   if (newtable != NULL)
 129   {
 130     memset(newtable, 0, newsize * sizeof(struct entry *));
 131
 132     /* This algorithm is not 'stable'. ie. it reverses the list
 133      * when it transfers entries between the tables */
 134     for (i = 0; i < h->tablelength; i++)
 135     {
 136       while ((e = h->table[i]) != NULL)
 137       {
 138         h->table[i] = e->next;
 139         index = indexFor(newsize,e->h);
 140         e->next = newtable[index];
 141         newtable[index] = e;
 142       }
 143     }
 144
 145     free(h->table);
 146     h->table = newtable;
 147   }
 148   else          /* Plan B: realloc instead */
 149   {
 150     newtable = (struct entry **)
 151       realloc(h->table, newsize * sizeof(struct entry *));
 152
 153     if (newtable == NULL)
 154       return 0;
 155
 156     h->table = newtable;
 157
 158     for (i = h->tablelength; i < newsize; i++)
 159       newtable[i] = NULL;
 160
 161     for (i = 0; i < h->tablelength; i++)
 162     {
 163       for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE)
 164       {
 165         index = indexFor(newsize,e->h);
 166
 167         if (index == i)
 168         {
 169           pE = &(e->next);
 170         }
 171         else
 172         {
 173           *pE = e->next;
 174           e->next = newtable[index];
 175           newtable[index] = e;
 176         }
 177       }
 178     }
 179   }
 180
 181   h->tablelength = newsize;
 182   h->loadlimit <<= 1;
 183
 184   return -1;
 185 }
 186
 187 /*****************************************************************************/
 188 unsigned int
 189 hashtable_count(struct hashtable *h)
 190 {
 191   return h->entrycount;
 192 }
 193
 194 /*****************************************************************************/
 195 int
 196 hashtable_insert(struct hashtable *h, void *k, void *v)
 197 {
 198   /* This method allows duplicate keys - but they shouldn't be used */
 199   unsigned int index;
 200   struct entry *e;
 201
 202   if (++(h->entrycount) > h->loadlimit)
 203   {
 204     /* Ignore the return value. If expand fails, we should
 205      * still try cramming just this value into the existing table
 206      * -- we may not have memory for a larger table, but one more
 207      * element may be ok. Next time we insert, we'll try expanding again.*/
 208
 209     hashtable_expand(h);
 210   }
 211
 212   e = (struct entry *)malloc(sizeof(struct entry));
 213
 214   if (e == NULL)
 215   {
 216     --(h->entrycount);
 217
 218     return 0;
 219   }
 220
 221   e->h = hash(h,k);
 222   index = indexFor(h->tablelength,e->h);
 223   e->k = k;
 224   e->v = v;
 225   e->next = h->table[index];
 226   h->table[index] = e;
 227
 228   return -1;
 229 }
 230
 231 /*****************************************************************************/
 232 int
 233 hashtable_change(struct hashtable *h, void *k, void *v)
 234 {
 235   struct entry *e;
 236   unsigned int hashvalue, index;
 237
 238   hashvalue = hash(h,k);
 239   index = indexFor(h->tablelength,hashvalue);
 240   e = h->table[index];
 241
 242   while (e != NULL)
 243   {
 244     /* Check hash value to short circuit heavier comparison */
 245     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 246     {
 247       free(e->v);
 248       e->v = v;
 249
 250       return -1;
 251     }
 252
 253     e = e->next;
 254   }
 255
 256   return 0;
 257 }
 258
 259 /*****************************************************************************/
 260 void * /* returns value associated with key */
 261 hashtable_search(struct hashtable *h, void *k)
 262 {
 263   struct entry *e;
 264   unsigned int hashvalue, index;
 265
 266   hashvalue = hash(h,k);
 267   index = indexFor(h->tablelength,hashvalue);
 268   e = h->table[index];
 269
 270   while (e != NULL)
 271   {
 272     /* Check hash value to short circuit heavier comparison */
 273     if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 274       return e->v;
 275
 276     e = e->next;
 277   }
 278
 279   return NULL;
 280 }
 281
 282 /*****************************************************************************/
 283 void * /* returns value associated with key */
 284 hashtable_remove(struct hashtable *h, void *k)
 285 {
 286   /* TODO: consider compacting the table when the load factor drops enough,
 287    *       or provide a 'compact' method. */
 288
 289   struct entry *e;
 290   struct entry **pE;
 291   void *v;
 292   unsigned int index = indexFor(h->tablelength,hash(h,k));
 293
 294   pE = &(h->table[index]);
 295   e = *pE;
 296
 297   while (e != NULL)
 298   {
 299     if (h->eqfn(k, e->k))
 300     {
 301       *pE = e->next;
 302       h->entrycount--;
 303       v = e->v;
 304       free(e->k);
 305       free(e);
 306
 307       return v;
 308     }
 309
 310     pE = &(e->next);
 311     e = e->next;
 312   }
 313
 314   return NULL;
 315 }
 316
 317 /*****************************************************************************/
 318 /* destroy */
 319 void
 320 hashtable_destroy(struct hashtable *h, int free_values)
 321 {
 322   unsigned int i;
 323   struct entry *e, *f;
 324   struct entry **table = h->table;
 325
 326   for (i = 0; i < h->tablelength; i++)
 327   {
 328     e = table[i];
 329
 330     while (e != NULL)
 331     {
 332       f = e;
 333       e = e->next;
 334       free(f->k);
 335
 336       if (free_values)
 337         free(f->v);
 338
 339       free(f);
 340     }
 341   }
 342
 343   free(h->table);
 344   free(h);
 345 }
 346
 347
 348 /*****************************************************************************/
 349 /* hashtable_iterator    - iterator constructor */
 350
 351 struct hashtable_itr *
 352 hashtable_iterator(struct hashtable *h)
 353 {
 354   unsigned int i, tablelength;
 355   struct hashtable_itr *itr = (struct hashtable_itr *)
 356     malloc(sizeof(struct hashtable_itr));
 357
 358   if (itr == NULL)
 359     return NULL;
 360
 361   itr->h = h;
 362   itr->e = NULL;
 363   tablelength = h->tablelength;
 364   itr->index = tablelength;
 365
 366   if (0 == h->entrycount)
 367     return itr;
 368
 369   for (i = 0; i < tablelength; i++)
 370   {
 371     if (h->table[i] != NULL)
 372     {
 373       itr->e = h->table[i];
 374       itr->index = i;
 375
 376       break;
 377     }
 378   }
 379
 380   return itr;
 381 }
 382
 383 /*****************************************************************************/
 384 /* key - return the key of the (key,value) pair at the current position */
 385
 386 void *
 387 hashtable_iterator_key(struct hashtable_itr *i)
 388 {
 389   return i->e->k;
 390 }
 391
 392 /*****************************************************************************/
 393 /* value - return the value of the (key,value) pair at the current position */
 394
 395 void *
 396 hashtable_iterator_value(struct hashtable_itr *i)
 397 {
 398   return i->e->v;
 399 }
 400
 401 /*****************************************************************************/
 402 /* advance - advance the iterator to the next element
 403  *           returns zero if advanced to end of table */
 404
 405 int
 406 hashtable_iterator_advance(struct hashtable_itr *itr)
 407 {
 408   unsigned int j,tablelength;
 409   struct entry **table;
 410   struct entry *next;
 411
 412   if (itr->e == NULL)
 413     return 0; /* stupidity check */
 414
 415   next = itr->e->next;
 416   if (next != NULL)
 417   {
 418     itr->e = next;
 419
 420     return -1;
 421   }
 422
 423   tablelength = itr->h->tablelength;
 424   if (tablelength <= (j = ++(itr->index)))
 425   {
 426     itr->e = NULL;
 427
 428     return 0;
 429   }
 430
 431   table = itr->h->table;
 432   while ((next = table[j]) == NULL)
 433   {
 434     if (++j >= tablelength)
 435     {
 436       itr->index = tablelength;
 437
 438       return 0;
 439     }
 440   }
 441
 442   itr->index = j;
 443   itr->e = next;
 444
 445   return -1;
 446 }