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