1 |
/* |
---|
2 |
* Copyright (c) 2005-2007, OmniTI Computer Consulting, Inc. |
---|
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 |
---|
7 |
* met: |
---|
8 |
* |
---|
9 |
* * Redistributions of source code must retain the above copyright |
---|
10 |
* notice, this list of conditions and the following disclaimer. |
---|
11 |
* * Redistributions in binary form must reproduce the above |
---|
12 |
* copyright notice, this list of conditions and the following |
---|
13 |
* disclaimer in the documentation and/or other materials provided |
---|
14 |
* with the distribution. |
---|
15 |
* * Neither the name OmniTI Computer Consulting, Inc. nor the names |
---|
16 |
* of its contributors may be used to endorse or promote products |
---|
17 |
* derived from this software without specific prior written |
---|
18 |
* permission. |
---|
19 |
* |
---|
20 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
---|
21 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
---|
22 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
---|
23 |
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
---|
24 |
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
---|
25 |
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
---|
26 |
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
---|
27 |
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
---|
28 |
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
---|
29 |
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
---|
30 |
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
---|
31 |
*/ |
---|
32 |
|
---|
33 |
/* this is just a copy (with search and replace) from jlog_hash */ |
---|
34 |
|
---|
35 |
#include "noit_config.h" |
---|
36 |
#include "noit_hash.h" |
---|
37 |
|
---|
38 |
/* This is from http://burtleburtle.net/bob/hash/doobs.html */ |
---|
39 |
|
---|
40 |
#define NoitHASH_INITIAL_SIZE (1<<7) |
---|
41 |
|
---|
42 |
#define mix(a,b,c) \ |
---|
43 |
{ \ |
---|
44 |
a -= b; a -= c; a ^= (c>>13); \ |
---|
45 |
b -= c; b -= a; b ^= (a<<8); \ |
---|
46 |
c -= a; c -= b; c ^= (b>>13); \ |
---|
47 |
a -= b; a -= c; a ^= (c>>12); \ |
---|
48 |
b -= c; b -= a; b ^= (a<<16); \ |
---|
49 |
c -= a; c -= b; c ^= (b>>5); \ |
---|
50 |
a -= b; a -= c; a ^= (c>>3); \ |
---|
51 |
b -= c; b -= a; b ^= (a<<10); \ |
---|
52 |
c -= a; c -= b; c ^= (b>>15); \ |
---|
53 |
} |
---|
54 |
|
---|
55 |
static inline |
---|
56 |
u_int32_t __hash(const char *k, u_int32_t length, u_int32_t initval) |
---|
57 |
{ |
---|
58 |
register u_int32_t a,b,c,len; |
---|
59 |
|
---|
60 |
/* Set up the internal state */ |
---|
61 |
len = length; |
---|
62 |
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ |
---|
63 |
c = initval; /* the previous hash value */ |
---|
64 |
|
---|
65 |
/*---------------------------------------- handle most of the key */ |
---|
66 |
while (len >= 12) |
---|
67 |
{ |
---|
68 |
a += (k[0] +((u_int32_t)k[1]<<8) +((u_int32_t)k[2]<<16) +((u_int32_t)k[3]<<24)); |
---|
69 |
b += (k[4] +((u_int32_t)k[5]<<8) +((u_int32_t)k[6]<<16) +((u_int32_t)k[7]<<24)); |
---|
70 |
c += (k[8] +((u_int32_t)k[9]<<8) +((u_int32_t)k[10]<<16)+((u_int32_t)k[11]<<24)); |
---|
71 |
mix(a,b,c); |
---|
72 |
k += 12; len -= 12; |
---|
73 |
} |
---|
74 |
|
---|
75 |
/*------------------------------------- handle the last 11 bytes */ |
---|
76 |
c += length; |
---|
77 |
switch(len) /* all the case statements fall through */ |
---|
78 |
{ |
---|
79 |
case 11: c+=((u_int32_t)k[10]<<24); |
---|
80 |
case 10: c+=((u_int32_t)k[9]<<16); |
---|
81 |
case 9 : c+=((u_int32_t)k[8]<<8); |
---|
82 |
/* the first byte of c is reserved for the length */ |
---|
83 |
case 8 : b+=((u_int32_t)k[7]<<24); |
---|
84 |
case 7 : b+=((u_int32_t)k[6]<<16); |
---|
85 |
case 6 : b+=((u_int32_t)k[5]<<8); |
---|
86 |
case 5 : b+=k[4]; |
---|
87 |
case 4 : a+=((u_int32_t)k[3]<<24); |
---|
88 |
case 3 : a+=((u_int32_t)k[2]<<16); |
---|
89 |
case 2 : a+=((u_int32_t)k[1]<<8); |
---|
90 |
case 1 : a+=k[0]; |
---|
91 |
/* case 0: nothing left to add */ |
---|
92 |
} |
---|
93 |
mix(a,b,c); |
---|
94 |
/*-------------------------------------------- report the result */ |
---|
95 |
return c; |
---|
96 |
} |
---|
97 |
|
---|
98 |
u_int32_t noit_hash__hash(const char *k, u_int32_t length, u_int32_t initval) { |
---|
99 |
return __hash(k,length,initval); |
---|
100 |
} |
---|
101 |
|
---|
102 |
void noit_hash_init(noit_hash_table *h) { |
---|
103 |
memset(h, 0, sizeof(noit_hash_table)); |
---|
104 |
h->initval = lrand48(); |
---|
105 |
h->table_size = NoitHASH_INITIAL_SIZE; |
---|
106 |
h->buckets = calloc(h->table_size, sizeof(noit_hash_bucket *)); |
---|
107 |
} |
---|
108 |
|
---|
109 |
noit_hash_bucket *noit_hash__new_bucket(const char *k, int klen, void *data) { |
---|
110 |
noit_hash_bucket *b; |
---|
111 |
b = calloc(1, sizeof(noit_hash_bucket)); |
---|
112 |
b->k = k; |
---|
113 |
b->klen = klen; |
---|
114 |
b->data = data; |
---|
115 |
return b; |
---|
116 |
} |
---|
117 |
void noit_hash__rebucket(noit_hash_table *h, int newsize) { |
---|
118 |
int i, newoff; |
---|
119 |
noit_hash_bucket **newbuckets, *b, *n; |
---|
120 |
|
---|
121 |
if (h->dont_rebucket) return; |
---|
122 |
|
---|
123 |
i = newsize; |
---|
124 |
while(i) { |
---|
125 |
if(i & 1) break; |
---|
126 |
i >>= 1; |
---|
127 |
} |
---|
128 |
if(i & ~1) { |
---|
129 |
return; |
---|
130 |
} |
---|
131 |
newbuckets = calloc(newsize, sizeof(noit_hash_bucket *)); |
---|
132 |
h->num_used_buckets = 0; |
---|
133 |
for(i = 0; i < h->table_size; i++) { |
---|
134 |
b = h->buckets[i]; |
---|
135 |
while(b) { |
---|
136 |
n = b->next; |
---|
137 |
newoff = __hash(b->k, b->klen, h->initval) & (newsize-1); |
---|
138 |
if(newbuckets[newoff] == NULL) h->num_used_buckets++; |
---|
139 |
b->next = newbuckets[newoff]; |
---|
140 |
newbuckets[newoff] = b; |
---|
141 |
b = n; |
---|
142 |
} |
---|
143 |
} |
---|
144 |
free(h->buckets); |
---|
145 |
h->table_size = newsize; |
---|
146 |
h->buckets = newbuckets; |
---|
147 |
} |
---|
148 |
int noit_hash_replace(noit_hash_table *h, const char *k, int klen, void *data, |
---|
149 |
NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { |
---|
150 |
int off; |
---|
151 |
int replaced = 0; |
---|
152 |
noit_hash_bucket __b, *tr, *b = &__b; |
---|
153 |
|
---|
154 |
if(h->table_size == 0) noit_hash_init(h); |
---|
155 |
off = __hash(k, klen, h->initval) & (h->table_size-1); |
---|
156 |
__b.next = h->buckets[off]; |
---|
157 |
if(!b->next) h->num_used_buckets++; |
---|
158 |
while(b->next) { |
---|
159 |
if(b->next->klen == klen && !memcmp(b->next->k, k, klen)) { |
---|
160 |
tr = b->next; |
---|
161 |
if(keyfree) keyfree((void *)tr->k); |
---|
162 |
if(datafree && tr->data) datafree((void *)tr->data); |
---|
163 |
b->next = tr->next; |
---|
164 |
if(tr == h->buckets[off]) h->buckets[off] = tr->next; |
---|
165 |
free(tr); |
---|
166 |
replaced = 1; |
---|
167 |
break; |
---|
168 |
} else { |
---|
169 |
b = b->next; |
---|
170 |
} |
---|
171 |
} |
---|
172 |
b = noit_hash__new_bucket(k, klen, data); |
---|
173 |
b->next = h->buckets[off]; |
---|
174 |
h->buckets[off] = b; |
---|
175 |
if(!replaced) h->size++; |
---|
176 |
|
---|
177 |
if(h->size > h->table_size - (h->table_size >> 3)) { |
---|
178 |
noit_hash__rebucket(h, h->table_size << 1); |
---|
179 |
} |
---|
180 |
return 1; |
---|
181 |
} |
---|
182 |
int noit_hash_store(noit_hash_table *h, const char *k, int klen, void *data) { |
---|
183 |
int off; |
---|
184 |
noit_hash_bucket *b; |
---|
185 |
|
---|
186 |
if(h->table_size == 0) noit_hash_init(h); |
---|
187 |
off = __hash(k, klen, h->initval) & (h->table_size-1); |
---|
188 |
b = h->buckets[off]; |
---|
189 |
if(!b) h->num_used_buckets++; |
---|
190 |
while(b) { |
---|
191 |
if(b->klen == klen && !memcmp(b->k, k, klen)) return 0; |
---|
192 |
b = b->next; |
---|
193 |
} |
---|
194 |
b = noit_hash__new_bucket(k, klen, data); |
---|
195 |
b->next = h->buckets[off]; |
---|
196 |
h->buckets[off] = b; |
---|
197 |
h->size++; |
---|
198 |
|
---|
199 |
if(h->size > h->table_size - (h->table_size >> 3)) { |
---|
200 |
noit_hash__rebucket(h, h->table_size << 1); |
---|
201 |
} |
---|
202 |
return 1; |
---|
203 |
} |
---|
204 |
int noit_hash_retrieve(noit_hash_table *h, const char *k, int klen, void **data) { |
---|
205 |
int off; |
---|
206 |
noit_hash_bucket *b; |
---|
207 |
|
---|
208 |
if(!h) return 0; |
---|
209 |
if(h->table_size == 0) noit_hash_init(h); |
---|
210 |
off = __hash(k, klen, h->initval) & (h->table_size-1); |
---|
211 |
b = h->buckets[off]; |
---|
212 |
while(b) { |
---|
213 |
if(b->klen == klen && !memcmp(b->k, k, klen)) break; |
---|
214 |
b = b->next; |
---|
215 |
} |
---|
216 |
if(b) { |
---|
217 |
if(data) *data = b->data; |
---|
218 |
return 1; |
---|
219 |
} |
---|
220 |
return 0; |
---|
221 |
} |
---|
222 |
int noit_hash_delete(noit_hash_table *h, const char *k, int klen, |
---|
223 |
NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { |
---|
224 |
int off; |
---|
225 |
void *data; |
---|
226 |
noit_hash_bucket *b, *prev = NULL; |
---|
227 |
|
---|
228 |
if(h->table_size == 0) noit_hash_init(h); |
---|
229 |
off = __hash(k, klen, h->initval) & (h->table_size-1); |
---|
230 |
b = h->buckets[off]; |
---|
231 |
while(b) { |
---|
232 |
if(b->klen == klen && !memcmp(b->k, k, klen)) break; |
---|
233 |
prev = b; |
---|
234 |
b = b->next; |
---|
235 |
} |
---|
236 |
if(!b) return 0; /* No match */ |
---|
237 |
data = b->data; |
---|
238 |
if(!prev) h->buckets[off] = h->buckets[off]->next; |
---|
239 |
else prev->next = b->next; |
---|
240 |
if(keyfree) keyfree((void *)b->k); |
---|
241 |
if(datafree && b->data) datafree(b->data); |
---|
242 |
free(b); |
---|
243 |
h->size--; |
---|
244 |
if(h->buckets[off] == NULL) h->num_used_buckets--; |
---|
245 |
if(h->table_size > NoitHASH_INITIAL_SIZE && |
---|
246 |
h->size < h->table_size >> 2) |
---|
247 |
noit_hash__rebucket(h, h->table_size >> 1); |
---|
248 |
return 1; |
---|
249 |
} |
---|
250 |
|
---|
251 |
void noit_hash_delete_all(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { |
---|
252 |
int i; |
---|
253 |
noit_hash_bucket *b, *tofree; |
---|
254 |
for(i=0; i<h->table_size; i++) { |
---|
255 |
b = h->buckets[i]; |
---|
256 |
while(b) { |
---|
257 |
tofree = b; |
---|
258 |
b = b->next; |
---|
259 |
if(keyfree) keyfree((void *)tofree->k); |
---|
260 |
if(datafree && tofree->data) datafree(tofree->data); |
---|
261 |
free(tofree); |
---|
262 |
} |
---|
263 |
h->buckets[i] = NULL; |
---|
264 |
} |
---|
265 |
h->num_used_buckets = 0; |
---|
266 |
h->size = 0; |
---|
267 |
noit_hash__rebucket(h, NoitHASH_INITIAL_SIZE); |
---|
268 |
} |
---|
269 |
|
---|
270 |
void noit_hash_destroy(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { |
---|
271 |
noit_hash_delete_all(h, keyfree, datafree); |
---|
272 |
if(h->buckets) free(h->buckets); |
---|
273 |
} |
---|
274 |
|
---|
275 |
int noit_hash_next(noit_hash_table *h, noit_hash_iter *iter, |
---|
276 |
const char **k, int *klen, void **data) { |
---|
277 |
noit_hash_bucket *b; |
---|
278 |
next_row: |
---|
279 |
if(iter->p1 < 0 || iter->p1 >= h->table_size) return 0; |
---|
280 |
if(iter->p2 == NULL) iter->p2 = (void *)h->buckets[iter->p1]; |
---|
281 |
if(iter->p2 == NULL) { |
---|
282 |
iter->p1++; |
---|
283 |
goto next_row; |
---|
284 |
} |
---|
285 |
b = (noit_hash_bucket *)(iter->p2); |
---|
286 |
*k = b->k; *klen = b->klen; |
---|
287 |
if(data) *data = b->data; |
---|
288 |
b = b->next; |
---|
289 |
if(!b) iter->p1++; |
---|
290 |
iter->p2 = b; |
---|
291 |
return 1; |
---|
292 |
} |
---|
293 |
|
---|
294 |
int noit_hash_firstkey(noit_hash_table *h, const char **k, int *klen) { |
---|
295 |
int i; |
---|
296 |
for(i=0;i<h->table_size;i++) { |
---|
297 |
if(h->buckets[i]) { |
---|
298 |
*k = h->buckets[i]->k; |
---|
299 |
*klen = h->buckets[i]->klen; |
---|
300 |
return 1; |
---|
301 |
} |
---|
302 |
} |
---|
303 |
return 0; |
---|
304 |
} |
---|
305 |
int noit_hash_nextkey(noit_hash_table *h, const char **k, int *klen, const char *lk, int lklen) { |
---|
306 |
int off; |
---|
307 |
noit_hash_bucket *b; |
---|
308 |
|
---|
309 |
if(h->table_size == 0) return 0; |
---|
310 |
off = __hash(lk, lklen, h->initval) & (h->table_size-1); |
---|
311 |
b = h->buckets[off]; |
---|
312 |
while(b) { |
---|
313 |
if(b->klen == lklen && !memcmp(b->k, lk, lklen)) break; |
---|
314 |
b = b->next; |
---|
315 |
} |
---|
316 |
if(b) { |
---|
317 |
if(b->next) { |
---|
318 |
*k = b->next->k; |
---|
319 |
*klen = b->next->klen; |
---|
320 |
return 1; |
---|
321 |
} else { |
---|
322 |
off++; |
---|
323 |
for(;off < h->table_size; off++) { |
---|
324 |
if(h->buckets[off]) { |
---|
325 |
*k = h->buckets[off]->k; |
---|
326 |
*klen = h->buckets[off]->klen; |
---|
327 |
return 1; |
---|
328 |
} |
---|
329 |
} |
---|
330 |
} |
---|
331 |
} |
---|
332 |
return 0; |
---|
333 |
} |
---|
334 |
/* vim: se sw=2 ts=2 et: */ |
---|