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     for (i=0;i<size;i++) { h->table[i] = NULL; }
  61     h->tablelength  = size;
  62     h->entrycount   = 0;
  63     h->hashfn       = hashf;
  64     h->eqfn         = eqf;
  65     h->loadlimit    = (unsigned int) ((float)size * maxloadfactor);
  66     return h;
  67 }
  68
  69 /*****************************************************************************/
  70 static unsigned int
  71 hash(struct hashtable *h, void *k)
  72 {
  73     /* Aim to protect against poor hash functions by adding logic here
  74      * - logic taken from java 1.4 hashtable source */
  75     unsigned int i = h->hashfn(k);
  76     i += ~(i << 9);
  77     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  78     i +=  (i << 4);
  79     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  80     return i;
  81 }
  82 /*****************************************************************************/
  83 static unsigned int
  84 indexFor(unsigned int tablelength, unsigned int hashvalue)
  85 {
  86     /* Only works if tablelength == 2^N */
  87     return (hashvalue & (tablelength - 1u));
  88 }
  89
  90 /*****************************************************************************/
  91 static int
  92 hashtable_expand(struct hashtable *h)
  93 {
  94     /* Double the size of the table to accomodate more entries */
  95     struct entry **newtable;
  96     struct entry *e;
  97     struct entry **pE;
  98     unsigned int newsize, i, index;
  99     /* Check we're not hitting max capacity */
 100     if (0 == (newsize = (h->tablelength << 1))) return 0;
 101
 102     newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
 103     if (NULL != newtable)
 104     {
 105         memset(newtable, 0, newsize * sizeof(struct entry *));
 106         /* This algorithm is not 'stable'. ie. it reverses the list
 107          * when it transfers entries between the tables */
 108         for (i = 0; i < h->tablelength; i++) {
 109             while (NULL != (e = h->table[i])) {
 110                 h->table[i] = e->next;
 111                 index = indexFor(newsize,e->h);
 112                 e->next = newtable[index];
 113                 newtable[index] = e;
 114             }
 115         }
 116         free(h->table);
 117         h->table = newtable;
 118     }
 119     /* Plan B: realloc instead */
 120     else
 121     {
 122         newtable = (struct entry **)
 123                    realloc(h->table, newsize * sizeof(struct entry *));
 124         if (NULL == newtable) return 0;
 125         h->table = newtable;
 126         for (i = h->tablelength; i < newsize; i++) {
 127             newtable[i] = NULL;
 128         }
 129         for (i = 0; i < h->tablelength; i++) {
 130             for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
 131                 index = indexFor(newsize,e->h);
 132                 if (index == i)
 133                 {
 134                     pE = &(e->next);
 135                 }
 136                 else
 137                 {
 138                     *pE = e->next;
 139                     e->next = newtable[index];
 140                     newtable[index] = e;
 141                 }
 142             }
 143         }
 144     }
 145     h->tablelength = newsize;
 146     h->loadlimit <<= 1;
 147     return -1;
 148 }
 149
 150 /*****************************************************************************/
 151 unsigned int
 152 hashtable_count(struct hashtable *h)
 153 {
 154     return h->entrycount;
 155 }
 156
 157 /*****************************************************************************/
 158 int
 159 hashtable_insert(struct hashtable *h, void *k, void *v)
 160 {
 161     /* This method allows duplicate keys - but they shouldn't be used */
 162     unsigned int index;
 163     struct entry *e;
 164     if (++(h->entrycount) > h->loadlimit)
 165     {
 166         /* Ignore the return value. If expand fails, we should
 167          * still try cramming just this value into the existing table
 168          * -- we may not have memory for a larger table, but one more
 169          * element may be ok. Next time we insert, we'll try expanding again.*/
 170         hashtable_expand(h);
 171     }
 172     e = (struct entry *)malloc(sizeof(struct entry));
 173     if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
 174     e->h = hash(h,k);
 175     index = indexFor(h->tablelength,e->h);
 176     e->k = k;
 177     e->v = v;
 178     e->next = h->table[index];
 179     h->table[index] = e;
 180     return -1;
 181 }
 182
 183 /*****************************************************************************/
 184 int
 185 hashtable_change(struct hashtable *h, void *k, void *v)
 186 {
 187     struct entry *e;
 188     unsigned int hashvalue, index;
 189     hashvalue = hash(h,k);
 190     index = indexFor(h->tablelength,hashvalue);
 191     e = h->table[index];
 192     while (NULL != e)
 193     {
 194         /* Check hash value to short circuit heavier comparison */
 195         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 196         {
 197           free(e->v);
 198           e->v = v;
 199           return -1;
 200         }
 201         e = e->next;
 202     }
 203     return 0;
 204 }
 205
 206 /*****************************************************************************/
 207 void * /* returns value associated with key */
 208 hashtable_search(struct hashtable *h, void *k)
 209 {
 210     struct entry *e;
 211     unsigned int hashvalue, index;
 212     hashvalue = hash(h,k);
 213     index = indexFor(h->tablelength,hashvalue);
 214     e = h->table[index];
 215     while (NULL != e)
 216     {
 217         /* Check hash value to short circuit heavier comparison */
 218         if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
 219         e = e->next;
 220     }
 221     return NULL;
 222 }
 223
 224 /*****************************************************************************/
 225 void * /* returns value associated with key */
 226 hashtable_remove(struct hashtable *h, void *k)
 227 {
 228     /* TODO: consider compacting the table when the load factor drops enough,
 229      *       or provide a 'compact' method. */
 230
 231     struct entry *e;
 232     struct entry **pE;
 233     void *v;
 234
 235     unsigned int index = indexFor(h->tablelength,hash(h,k));
 236     pE = &(h->table[index]);
 237     e = *pE;
 238     while (NULL != e)
 239     {
 240         if (h->eqfn(k, e->k))
 241         {
 242             *pE = e->next;
 243             h->entrycount--;
 244             v = e->v;
 245             free(e->k);
 246             free(e);
 247             return v;
 248         }
 249         pE = &(e->next);
 250         e = e->next;
 251     }
 252     return NULL;
 253 }
 254
 255 /*****************************************************************************/
 256 /* destroy */
 257 void
 258 hashtable_destroy(struct hashtable *h, int free_values)
 259 {
 260     unsigned int i;
 261     struct entry *e, *f;
 262     struct entry **table = h->table;
 263     if (free_values)
 264     {
 265         for (i = 0; i < h->tablelength; i++)
 266         {
 267             e = table[i];
 268             while (NULL != e)
 269             { f = e; e = e->next; free(f->k); free(f->v); free(f); }
 270         }
 271     }
 272     else
 273     {
 274         for (i = 0; i < h->tablelength; i++)
 275         {
 276             e = table[i];
 277             while (NULL != e)
 278             { f = e; e = e->next; free(f->k); free(f); }
 279         }
 280     }
 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 }