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