src/libgame/hash.c

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