hashtable.c

   1 /*
   2   Copyright (c) 2002, 2004, Christopher Clark
   3   All rights reserved.
   4
   5   Redistribution and use in source and binary forms, with or without
   6   modification, are permitted provided that the following conditions are met:
   7
   8     * Redistributions of source code must retain the above copyright notice,
   9       this list of conditions and the following disclaimer.
  10
  11     * Redistributions in binary form must reproduce the above copyright notice,
  12       this list of conditions and the following disclaimer in the documentation
  13       and/or other materials provided with the distribution.
  14
  15     * Neither the name of the original author; nor the names of any
  16       contributors may be used to endorse or promote products derived from this
  17       software without specific prior written permission.
  18
  19   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20   AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22   ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  23   LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24   CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25   SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27   CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28   ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29   POSSIBILITY OF SUCH DAMAGE.
  30 */
  31
  32 #include "hashtable.h"
  33 #include "hashtable_private.h"
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37 #include <math.h>
  38
  39 /*
  40 Credit for primes table: Aaron Krowne
  41  http://br.endernet.org/~akrowne/
  42  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
  43 */
  44 static const unsigned int primes[] = {
  45 53, 97, 193, 389,
  46 769, 1543, 3079, 6151,
  47 12289, 24593, 49157, 98317,
  48 196613, 393241, 786433, 1572869,
  49 3145739, 6291469, 12582917, 25165843,
  50 50331653, 100663319, 201326611, 402653189,
  51 805306457, 1610612741
  52 };
  53 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
  54 const float max_load_factor = 0.65;
  55
  56 /*****************************************************************************/
  57 struct hashtable *
  58 create_hashtable(unsigned int minsize,
  59                  unsigned int (*hashf) (void*),
  60                  int (*eqf) (void*,void*))
  61 {
  62     struct hashtable *h;
  63     unsigned int pindex, size = primes[0];
  64     /* Check requested hashtable isn't too large */
  65     if (minsize > (1u << 30)) return NULL;
  66     /* Enforce size as prime */
  67     for (pindex=0; pindex < prime_table_length; pindex++) {
  68         if (primes[pindex] > minsize) { size = primes[pindex]; break; }
  69     }
  70     h = (struct hashtable *)malloc(sizeof(struct hashtable));
  71     if (NULL == h) return NULL; /*oom*/
  72     h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
  73     if (NULL == h->table) { free(h); return NULL; } /*oom*/
  74     memset(h->table, 0, size * sizeof(struct entry *));
  75     h->tablelength  = size;
  76     h->primeindex   = pindex;
  77     h->entrycount   = 0;
  78     h->hashfn       = hashf;
  79     h->eqfn         = eqf;
  80     h->loadlimit    = (unsigned int) ceil(size * max_load_factor);
  81     return h;
  82 }
  83
  84 /*****************************************************************************/
  85 unsigned int
  86 hash(struct hashtable *h, void *k)
  87 {
  88     /* Aim to protect against poor hash functions by adding logic here
  89      * - logic taken from java 1.4 hashtable source */
  90     unsigned int i = h->hashfn(k);
  91     i += ~(i << 9);
  92     i ^=  ((i >> 14) | (i << 18)); /* >>> */
  93     i +=  (i << 4);
  94     i ^=  ((i >> 10) | (i << 22)); /* >>> */
  95     return i;
  96 }
  97
  98 /*****************************************************************************/
  99 static int
 100 hashtable_expand(struct hashtable *h)
 101 {
 102     /* Double the size of the table to accomodate more entries */
 103     struct entry **newtable;
 104     struct entry *e;
 105     struct entry **pE;
 106     unsigned int newsize, i, index;
 107     /* Check we're not hitting max capacity */
 108     if (h->primeindex == (prime_table_length - 1)) return 0;
 109     newsize = primes[++(h->primeindex)];
 110
 111     newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
 112     if (NULL != newtable)
 113     {
 114         memset(newtable, 0, newsize * sizeof(struct entry *));
 115         /* This algorithm is not 'stable'. ie. it reverses the list
 116          * when it transfers entries between the tables */
 117         for (i = 0; i < h->tablelength; i++) {
 118             while (NULL != (e = h->table[i])) {
 119                 h->table[i] = e->next;
 120                 index = indexFor(newsize,e->h);
 121                 e->next = newtable[index];
 122                 newtable[index] = e;
 123             }
 124         }
 125         free(h->table);
 126         h->table = newtable;
 127     }
 128     /* Plan B: realloc instead */
 129     else
 130     {
 131         newtable = (struct entry **)
 132                    realloc(h->table, newsize * sizeof(struct entry *));
 133         if (NULL == newtable) { (h->primeindex)--; return 0; }
 134         h->table = newtable;
 135         memset(newtable[h->tablelength], 0, newsize - h->tablelength);
 136         for (i = 0; i < h->tablelength; i++) {
 137             for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
 138                 index = indexFor(newsize,e->h);
 139                 if (index == i)
 140                 {
 141                     pE = &(e->next);
 142                 }
 143                 else
 144                 {
 145                     *pE = e->next;
 146                     e->next = newtable[index];
 147                     newtable[index] = e;
 148                 }
 149             }
 150         }
 151     }
 152     h->tablelength = newsize;
 153     h->loadlimit   = (unsigned int) ceil(newsize * max_load_factor);
 154     return -1;
 155 }
 156
 157 /*****************************************************************************/
 158 unsigned int
 159 hashtable_count(struct hashtable *h)
 160 {
 161     return h->entrycount;
 162 }
 163
 164 /*****************************************************************************/
 165 int
 166 hashtable_insert(struct hashtable *h, void *k, void *v)
 167 {
 168     /* This method allows duplicate keys - but they shouldn't be used */
 169     unsigned int index;
 170     struct entry *e;
 171     if (++(h->entrycount) > h->loadlimit)
 172     {
 173         /* Ignore the return value. If expand fails, we should
 174          * still try cramming just this value into the existing table
 175          * -- we may not have memory for a larger table, but one more
 176          * element may be ok. Next time we insert, we'll try expanding again.*/
 177         hashtable_expand(h);
 178     }
 179     e = (struct entry *)malloc(sizeof(struct entry));
 180     if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
 181     e->h = hash(h,k);
 182     index = indexFor(h->tablelength,e->h);
 183     e->k = k;
 184     e->v = v;
 185     e->next = h->table[index];
 186     h->table[index] = e;
 187     return -1;
 188 }
 189
 190 /*****************************************************************************/
 191 void * /* returns value associated with key */
 192 hashtable_search(struct hashtable *h, void *k)
 193 {
 194     struct entry *e;
 195     unsigned int hashvalue, index;
 196     hashvalue = hash(h,k);
 197     index = indexFor(h->tablelength,hashvalue);
 198     e = h->table[index];
 199     while (NULL != e)
 200     {
 201         /* Check hash value to short circuit heavier comparison */
 202         if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
 203         e = e->next;
 204     }
 205     return NULL;
 206 }
 207
 208 /*****************************************************************************/
 209 void * /* returns value associated with key */
 210 hashtable_remove(struct hashtable *h, void *k)
 211 {
 212     /* TODO: consider compacting the table when the load factor drops enough,
 213      *       or provide a 'compact' method. */
 214
 215     struct entry *e;
 216     struct entry **pE;
 217     void *v;
 218     unsigned int hashvalue, index;
 219
 220     hashvalue = hash(h,k);
 221     index = indexFor(h->tablelength,hash(h,k));
 222     pE = &(h->table[index]);
 223     e = *pE;
 224     while (NULL != e)
 225     {
 226         /* Check hash value to short circuit heavier comparison */
 227         if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
 228         {
 229             *pE = e->next;
 230             h->entrycount--;
 231             v = e->v;
 232             freekey(e->k);
 233             free(e);
 234             return v;
 235         }
 236         pE = &(e->next);
 237         e = e->next;
 238     }
 239     return NULL;
 240 }
 241
 242 /*****************************************************************************/
 243 /* destroy */
 244 void
 245 hashtable_destroy(struct hashtable *h, int free_values)
 246 {
 247     unsigned int i;
 248     struct entry *e, *f;
 249     struct entry **table = h->table;
 250     if (free_values)
 251     {
 252         for (i = 0; i < h->tablelength; i++)
 253         {
 254             e = table[i];
 255             while (NULL != e)
 256             { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
 257         }
 258     }
 259     else
 260     {
 261         for (i = 0; i < h->tablelength; i++)
 262         {
 263             e = table[i];
 264             while (NULL != e)
 265             { f = e; e = e->next; freekey(f->k); free(f); }
 266         }
 267     }
 268     free(h->table);
 269     free(h);
 270 }
 271
 272 /*
 273  * Copyright (c) 2002, Christopher Clark
 274  * All rights reserved.
 275  *
 276  * Redistribution and use in source and binary forms, with or without
 277  * modification, are permitted provided that the following conditions
 278  * are met:
 279  *
 280  * * Redistributions of source code must retain the above copyright
 281  * notice, this list of conditions and the following disclaimer.
 282  *
 283  * * Redistributions in binary form must reproduce the above copyright
 284  * notice, this list of conditions and the following disclaimer in the
 285  * documentation and/or other materials provided with the distribution.
 286  *
 287  * * Neither the name of the original author; nor the names of any contributors
 288  * may be used to endorse or promote products derived from this software
 289  * without specific prior written permission.
 290  *
 291  *
 292  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 293  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 294  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 295  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 296  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 297  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 298  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 299  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 300  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 301  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 302  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 303 */