Branch data Line data Source code
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 : 1 : create_hashtable(unsigned int minsize,
59 : : unsigned int (*hashf) (void*),
60 : : int (*eqf) (void*,void*))
61 : : {
62 : : struct hashtable *h;
63 : 1 : unsigned int pindex, size = primes[0];
64 : : /* Check requested hashtable isn't too large */
65 [ - + ]: 1 : if (minsize > (1u << 30)) return NULL;
66 : : /* Enforce size as prime */
67 [ + - ]: 6 : for (pindex=0; pindex < prime_table_length; pindex++) {
68 [ + + ]: 6 : if (primes[pindex] > minsize) { size = primes[pindex]; break; }
69 : : }
70 : 1 : h = (struct hashtable *)malloc(sizeof(struct hashtable));
71 [ - + ]: 1 : if (NULL == h) return NULL; /*oom*/
72 : 1 : h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
73 [ - + ]: 1 : if (NULL == h->table) { free(h); return NULL; } /*oom*/
74 : 1 : memset(h->table, 0, size * sizeof(struct entry *));
75 : 1 : h->tablelength = size;
76 : 1 : h->primeindex = pindex;
77 : 1 : h->entrycount = 0;
78 : 1 : h->hashfn = hashf;
79 : 1 : h->eqfn = eqf;
80 : 1 : h->loadlimit = (unsigned int) ceil(size * max_load_factor);
81 : 1 : return h;
82 : : }
83 : :
84 : : /*****************************************************************************/
85 : : unsigned int
86 : 0 : 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 : 0 : unsigned int i = h->hashfn(k);
91 : 0 : i += ~(i << 9);
92 : 0 : i ^= ((i >> 14) | (i << 18)); /* >>> */
93 : 0 : i += (i << 4);
94 : 0 : i ^= ((i >> 10) | (i << 22)); /* >>> */
95 : 0 : return i;
96 : : }
97 : :
98 : : /*****************************************************************************/
99 : : static int
100 : 0 : hashtable_expand(struct hashtable *h)
101 : : {
102 : : /* Double the size of the table to accommodate 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 [ # # ]: 0 : if (h->primeindex == (prime_table_length - 1)) return 0;
109 : 0 : newsize = primes[++(h->primeindex)];
110 : :
111 : 0 : newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
112 [ # # ]: 0 : if (NULL != newtable)
113 : : {
114 : 0 : 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 [ # # ]: 0 : for (i = 0; i < h->tablelength; i++) {
118 [ # # ]: 0 : while (NULL != (e = h->table[i])) {
119 : 0 : h->table[i] = e->next;
120 : 0 : index = indexFor(newsize,e->h);
121 : 0 : e->next = newtable[index];
122 : 0 : newtable[index] = e;
123 : : }
124 : : }
125 : 0 : free(h->table);
126 : 0 : h->table = newtable;
127 : : }
128 : : /* Plan B: realloc instead */
129 : : else
130 : : {
131 : 0 : newtable = (struct entry **)
132 : 0 : realloc(h->table, newsize * sizeof(struct entry *));
133 [ # # ]: 0 : if (NULL == newtable) { (h->primeindex)--; return 0; }
134 : 0 : h->table = newtable;
135 : 0 : memset(newtable[h->tablelength], 0, newsize - h->tablelength);
136 [ # # ]: 0 : for (i = 0; i < h->tablelength; i++) {
137 [ # # ]: 0 : for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
138 : 0 : index = indexFor(newsize,e->h);
139 [ # # ]: 0 : if (index == i)
140 : : {
141 : 0 : pE = &(e->next);
142 : : }
143 : : else
144 : : {
145 : 0 : *pE = e->next;
146 : 0 : e->next = newtable[index];
147 : 0 : newtable[index] = e;
148 : : }
149 : : }
150 : : }
151 : : }
152 : 0 : h->tablelength = newsize;
153 : 0 : h->loadlimit = (unsigned int) ceil(newsize * max_load_factor);
154 : 0 : return -1;
155 : : }
156 : :
157 : : /*****************************************************************************/
158 : : unsigned int
159 : 0 : hashtable_count(struct hashtable *h)
160 : : {
161 : 0 : return h->entrycount;
162 : : }
163 : :
164 : : /*****************************************************************************/
165 : : int
166 : 0 : 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 [ # # ]: 0 : 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 : 0 : hashtable_expand(h);
178 : : }
179 : 0 : e = (struct entry *)malloc(sizeof(struct entry));
180 [ # # ]: 0 : if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
181 : 0 : e->h = hash(h,k);
182 : 0 : index = indexFor(h->tablelength,e->h);
183 : 0 : e->k = k;
184 : 0 : e->v = v;
185 : 0 : e->next = h->table[index];
186 : 0 : h->table[index] = e;
187 : 0 : return -1;
188 : : }
189 : :
190 : : /*****************************************************************************/
191 : : void * /* returns value associated with key */
192 : 0 : hashtable_search(struct hashtable *h, void *k)
193 : : {
194 : : struct entry *e;
195 : : unsigned int hashvalue, index;
196 : 0 : hashvalue = hash(h,k);
197 : 0 : index = indexFor(h->tablelength,hashvalue);
198 : 0 : e = h->table[index];
199 [ # # ]: 0 : while (NULL != e)
200 : : {
201 : : /* Check hash value to short circuit heavier comparison */
202 [ # # ][ # # ]: 0 : if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
203 : 0 : e = e->next;
204 : : }
205 : 0 : return NULL;
206 : : }
207 : :
208 : : /*****************************************************************************/
209 : : void * /* returns value associated with key */
210 : 0 : 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 : 0 : hashvalue = hash(h,k);
221 : 0 : index = indexFor(h->tablelength,hash(h,k));
222 : 0 : pE = &(h->table[index]);
223 : 0 : e = *pE;
224 [ # # ]: 0 : while (NULL != e)
225 : : {
226 : : /* Check hash value to short circuit heavier comparison */
227 [ # # ][ # # ]: 0 : if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
228 : : {
229 : 0 : *pE = e->next;
230 : 0 : h->entrycount--;
231 : 0 : v = e->v;
232 : 0 : freekey(e->k);
233 : 0 : free(e);
234 : 0 : return v;
235 : : }
236 : 0 : pE = &(e->next);
237 : 0 : e = e->next;
238 : : }
239 : 0 : return NULL;
240 : : }
241 : :
242 : : /*****************************************************************************/
243 : : /* destroy */
244 : : void
245 : 0 : hashtable_destroy(struct hashtable *h, int free_values)
246 : : {
247 : : unsigned int i;
248 : : struct entry *e, *f;
249 : 0 : struct entry **table = h->table;
250 [ # # ]: 0 : if (free_values)
251 : : {
252 [ # # ]: 0 : for (i = 0; i < h->tablelength; i++)
253 : : {
254 : 0 : e = table[i];
255 [ # # ]: 0 : while (NULL != e)
256 : 0 : { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
257 : : }
258 : : }
259 : : else
260 : : {
261 [ # # ]: 0 : for (i = 0; i < h->tablelength; i++)
262 : : {
263 : 0 : e = table[i];
264 [ # # ]: 0 : while (NULL != e)
265 : 0 : { f = e; e = e->next; freekey(f->k); free(f); }
266 : : }
267 : : }
268 : 0 : free(h->table);
269 : 0 : free(h);
270 : 0 : }
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 : : */
|
