2 Copyright (c) 2002, 2004, Christopher Clark
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
8 * Redistributions of source code must retain the above copyright notice,
9 this list of conditions and the following disclaimer.
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.
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.
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.
32 #include "hashtable.h"
33 #include "hashtable_private.h"
40 Credit for primes table: Aaron Krowne
41 http://br.endernet.org/~akrowne/
42 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
44 static const unsigned int primes[] = {
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,
53 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
54 const float max_load_factor = 0.65;
56 /*****************************************************************************/
58 create_hashtable(unsigned int minsize,
59 unsigned int (*hashf) (void*),
60 int (*eqf) (void*,void*))
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; }
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;
80 h->loadlimit = (unsigned int) ceil(size * max_load_factor);
84 /*****************************************************************************/
86 hash(struct hashtable *h, void *k)
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);
92 i ^= ((i >> 14) | (i << 18)); /* >>> */
94 i ^= ((i >> 10) | (i << 22)); /* >>> */
98 /*****************************************************************************/
100 hashtable_expand(struct hashtable *h)
102 /* Double the size of the table to accomodate more entries */
103 struct entry **newtable;
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)];
111 newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
112 if (NULL != newtable)
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];
128 /* Plan B: realloc instead */
131 newtable = (struct entry **)
132 realloc(h->table, newsize * sizeof(struct entry *));
133 if (NULL == newtable) { (h->primeindex)--; return 0; }
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);
146 e->next = newtable[index];
152 h->tablelength = newsize;
153 h->loadlimit = (unsigned int) ceil(newsize * max_load_factor);
157 /*****************************************************************************/
159 hashtable_count(struct hashtable *h)
161 return h->entrycount;
164 /*****************************************************************************/
166 hashtable_insert(struct hashtable *h, void *k, void *v)
168 /* This method allows duplicate keys - but they shouldn't be used */
171 if (++(h->entrycount) > h->loadlimit)
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.*/
179 e = (struct entry *)malloc(sizeof(struct entry));
180 if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
182 index = indexFor(h->tablelength,e->h);
185 e->next = h->table[index];
190 /*****************************************************************************/
191 void * /* returns value associated with key */
192 hashtable_search(struct hashtable *h, void *k)
195 unsigned int hashvalue, index;
196 hashvalue = hash(h,k);
197 index = indexFor(h->tablelength,hashvalue);
201 /* Check hash value to short circuit heavier comparison */
202 if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
208 /*****************************************************************************/
209 void * /* returns value associated with key */
210 hashtable_remove(struct hashtable *h, void *k)
212 /* TODO: consider compacting the table when the load factor drops enough,
213 * or provide a 'compact' method. */
218 unsigned int hashvalue, index;
220 hashvalue = hash(h,k);
221 index = indexFor(h->tablelength,hash(h,k));
222 pE = &(h->table[index]);
226 /* Check hash value to short circuit heavier comparison */
227 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
242 /*****************************************************************************/
245 hashtable_destroy(struct hashtable *h, int free_values)
249 struct entry **table = h->table;
252 for (i = 0; i < h->tablelength; i++)
256 { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
261 for (i = 0; i < h->tablelength; i++)
265 { f = e; e = e->next; freekey(f->k); free(f); }
273 * Copyright (c) 2002, Christopher Clark
274 * All rights reserved.
276 * Redistribution and use in source and binary forms, with or without
277 * modification, are permitted provided that the following conditions
280 * * Redistributions of source code must retain the above copyright
281 * notice, this list of conditions and the following disclaimer.
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.
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.
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.