root/src/utils/noit_hash.c

Revision 7553187be6560a2a36408a138e382a55250074ea, 10.8 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 7 months ago)

merge should replace

  • Property mode set to 100644
Line 
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 void noit_hash_init_size(noit_hash_table *h, int size) {
110   memset(h, 0, sizeof(noit_hash_table));
111   h->initval = lrand48();
112   if (size > 0)
113     h->table_size = size;
114   else
115     h->table_size = NoitHASH_INITIAL_SIZE;
116   h->buckets = calloc(h->table_size, sizeof(noit_hash_bucket *));
117 }
118
119 noit_hash_bucket *noit_hash__new_bucket(const char *k, int klen, void *data) {
120   noit_hash_bucket *b;
121   b = calloc(1, sizeof(noit_hash_bucket));
122   b->k = k;
123   b->klen = klen;
124   b->data = data;
125   return b;
126 }
127 void noit_hash__rebucket(noit_hash_table *h, int newsize) {
128   int i, newoff;
129   noit_hash_bucket **newbuckets, *b, *n;
130
131   if (h->dont_rebucket) return;
132
133   i = newsize;
134   while(i) {
135     if(i & 1) break;
136     i >>= 1;
137   }
138   if(i & ~1) {
139     return;
140   }
141   newbuckets = calloc(newsize, sizeof(noit_hash_bucket *));
142   h->num_used_buckets = 0;
143   for(i = 0; i < h->table_size; i++) {
144     b = h->buckets[i];
145     while(b) {
146       n = b->next;
147       newoff = __hash(b->k, b->klen, h->initval) & (newsize-1);
148       if(newbuckets[newoff] == NULL) h->num_used_buckets++;
149       b->next = newbuckets[newoff];
150       newbuckets[newoff] = b;
151       b = n;
152     }
153   }
154   free(h->buckets);
155   h->table_size = newsize;
156   h->buckets = newbuckets;
157 }
158 int noit_hash_replace(noit_hash_table *h, const char *k, int klen, void *data,
159                    NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
160   int off;
161   int replaced = 0;
162   noit_hash_bucket __b, *tr, *b = &__b;
163
164   if(h->table_size == 0) noit_hash_init(h);
165   off = __hash(k, klen, h->initval) & (h->table_size-1);
166   __b.next = h->buckets[off];
167   if(!b->next) h->num_used_buckets++;
168   while(b->next) {
169     if(b->next->klen == klen && !memcmp(b->next->k, k, klen)) {
170       tr = b->next;
171       if(keyfree) keyfree((void *)tr->k);
172       if(datafree && tr->data) datafree((void *)tr->data);
173       b->next = tr->next;
174       if(tr == h->buckets[off]) h->buckets[off] = tr->next;
175       free(tr);
176       replaced = 1;
177       break;
178     } else {
179       b = b->next;
180     }
181   }
182   b = noit_hash__new_bucket(k, klen, data);
183   b->next = h->buckets[off];
184   h->buckets[off] = b;
185   if(!replaced) h->size++;
186
187   if(h->size > h->table_size - (h->table_size >> 3)) {
188     noit_hash__rebucket(h, h->table_size << 1);
189   }
190   return 1;
191 }
192 int noit_hash_store(noit_hash_table *h, const char *k, int klen, void *data) {
193   int off;
194   noit_hash_bucket *b;
195
196   if(h->table_size == 0) noit_hash_init(h);
197   off = __hash(k, klen, h->initval) & (h->table_size-1);
198   b = h->buckets[off];
199   if(!b) h->num_used_buckets++;
200   while(b) {
201     if(b->klen == klen && !memcmp(b->k, k, klen)) return 0;
202     b = b->next;
203   }
204   b = noit_hash__new_bucket(k, klen, data);
205   b->next = h->buckets[off];
206   h->buckets[off] = b;
207   h->size++;
208
209   if(h->size > h->table_size - (h->table_size >> 3)) {
210     noit_hash__rebucket(h, h->table_size << 1);
211   }
212   return 1;
213 }
214 int noit_hash_retrieve(noit_hash_table *h, const char *k, int klen, void **data) {
215   int off;
216   noit_hash_bucket *b;
217
218   if(!h) return 0;
219   if(h->table_size == 0) noit_hash_init(h);
220   off = __hash(k, klen, h->initval) & (h->table_size-1);
221   b = h->buckets[off];
222   while(b) {
223     if(b->klen == klen && !memcmp(b->k, k, klen)) break;
224     b = b->next;
225   }
226   if(b) {
227     if(data) *data = b->data;
228     return 1;
229   }
230   return 0;
231 }
232 int noit_hash_retr_str(noit_hash_table *h, const char *k, int klen, const char **dstr) {
233   int rv;
234   void *vptr = NULL;
235   rv = noit_hash_retrieve(h,k,klen,&vptr);
236   *dstr = vptr;
237   return rv;
238 }
239 int noit_hash_delete(noit_hash_table *h, const char *k, int klen,
240                   NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
241   int off;
242   noit_hash_bucket *b, *prev = NULL;
243
244   if(h->table_size == 0) noit_hash_init(h);
245   off = __hash(k, klen, h->initval) & (h->table_size-1);
246   b = h->buckets[off];
247   while(b) {
248     if(b->klen == klen && !memcmp(b->k, k, klen)) break;
249     prev = b;
250     b = b->next;
251   }
252   if(!b) return 0; /* No match */
253   if(!prev) h->buckets[off] = h->buckets[off]->next;
254   else prev->next = b->next;
255   if(keyfree) keyfree((void *)b->k);
256   if(datafree && b->data) datafree(b->data);
257   free(b);
258   h->size--;
259   if(h->buckets[off] == NULL) h->num_used_buckets--;
260   if(h->table_size > NoitHASH_INITIAL_SIZE &&
261      h->size < h->table_size >> 2)
262     noit_hash__rebucket(h, h->table_size >> 1);
263   return 1;
264 }
265
266 void noit_hash_delete_all(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
267   int i;
268   noit_hash_bucket *b, *tofree;
269   for(i=0; i<h->table_size; i++) {
270     b = h->buckets[i];
271     while(b) {
272       tofree = b;
273       b = b->next;
274       if(keyfree) keyfree((void *)tofree->k);
275       if(datafree && tofree->data) datafree(tofree->data);
276       free(tofree);
277     }
278     h->buckets[i] = NULL;
279   }
280   h->num_used_buckets = 0;
281   h->size = 0;
282   noit_hash__rebucket(h, NoitHASH_INITIAL_SIZE);
283 }
284
285 void noit_hash_destroy(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
286   noit_hash_delete_all(h, keyfree, datafree);
287   if(h->buckets) free(h->buckets);
288 }
289
290 int noit_hash_size(noit_hash_table *h) {
291   if(h == NULL) return 0;
292   return h->size;
293 }
294
295 void noit_hash_merge_as_dict(noit_hash_table *dst, noit_hash_table *src) {
296   noit_hash_iter iter = NOIT_HASH_ITER_ZERO;
297   const char *k;
298   int klen;
299   void *data;
300   if(src == NULL || dst == NULL) return;
301   while(noit_hash_next(src, &iter, &k, &klen, &data))
302     noit_hash_replace(dst, strdup(k), klen, strdup((char *)data), free, free);
303 }
304
305 int noit_hash_next(noit_hash_table *h, noit_hash_iter *iter,
306                 const char **k, int *klen, void **data) {
307   noit_hash_bucket *b;
308  next_row:
309   if(iter->p1 < 0 || iter->p1 >= h->table_size) return 0;
310   if(iter->p2 == NULL) iter->p2 = (void *)h->buckets[iter->p1];
311   if(iter->p2 == NULL) {
312     iter->p1++;
313     goto next_row;
314   }
315   b = (noit_hash_bucket *)(iter->p2);
316   *k = b->k; *klen = b->klen;
317   if(data) *data = b->data;
318   b = b->next;
319   if(!b) iter->p1++;
320   iter->p2 = b;
321   return 1;
322 }
323
324 int noit_hash_next_str(noit_hash_table *h, noit_hash_iter *iter,
325                        const char **k, int *klen, const char **dstr) {
326   void *data = NULL;
327   int rv;
328   rv = noit_hash_next(h,iter,k,klen,&data);
329   *dstr = data;
330   return rv;
331 }
332
333 int noit_hash_firstkey(noit_hash_table *h, const char **k, int *klen) {
334   int i;
335   for(i=0;i<h->table_size;i++) {
336     if(h->buckets[i]) {
337       *k = h->buckets[i]->k;
338       *klen = h->buckets[i]->klen;
339       return 1;
340     }
341   }
342   return 0;
343 }
344 int noit_hash_nextkey(noit_hash_table *h, const char **k, int *klen, const char *lk, int lklen) {
345   int off;
346   noit_hash_bucket *b;
347
348   if(h->table_size == 0) return 0;
349   off = __hash(lk, lklen, h->initval) & (h->table_size-1);
350   b = h->buckets[off];
351   while(b) {
352     if(b->klen == lklen && !memcmp(b->k, lk, lklen)) break;
353     b = b->next;
354   }
355   if(b) {
356     if(b->next) {
357       *k = b->next->k;
358       *klen = b->next->klen;
359       return 1;
360     } else {
361       off++;
362       for(;off < h->table_size; off++) {
363         if(h->buckets[off]) {
364           *k = h->buckets[off]->k;
365           *klen = h->buckets[off]->klen;
366           return 1;
367         }
368       }
369     }
370   }
371   return 0;
372 }
373 /* vim: se sw=2 ts=2 et: */
Note: See TracBrowser for help on using the browser.