root/jlog_hash.c

Revision 9b8a62c4050371b1896f1b7751c6a4f675dd4e28, 9.6 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 7 years ago)

Offer these files under a new BSD-style license. Yay

  • 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 #include "jlog_config.h"
34 #include "jlog_hash.h"
35
36 /* This is from http://burtleburtle.net/bob/hash/doobs.html */
37
38 #define JLogHASH_INITIAL_SIZE (1<<7)
39
40 #define mix(a,b,c) \
41 { \
42   a -= b; a -= c; a ^= (c>>13); \
43   b -= c; b -= a; b ^= (a<<8); \
44   c -= a; c -= b; c ^= (b>>13); \
45   a -= b; a -= c; a ^= (c>>12);  \
46   b -= c; b -= a; b ^= (a<<16); \
47   c -= a; c -= b; c ^= (b>>5); \
48   a -= b; a -= c; a ^= (c>>3);  \
49   b -= c; b -= a; b ^= (a<<10); \
50   c -= a; c -= b; c ^= (b>>15); \
51 }
52
53 static inline
54 u_int32_t __hash(const char *k, u_int32_t length, u_int32_t initval)
55 {
56    register u_int32_t a,b,c,len;
57
58    /* Set up the internal state */
59    len = length;
60    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
61    c = initval;         /* the previous hash value */
62
63    /*---------------------------------------- handle most of the key */
64    while (len >= 12)
65    {
66       a += (k[0] +((u_int32_t)k[1]<<8) +((u_int32_t)k[2]<<16) +((u_int32_t)k[3]<<24));
67       b += (k[4] +((u_int32_t)k[5]<<8) +((u_int32_t)k[6]<<16) +((u_int32_t)k[7]<<24));
68       c += (k[8] +((u_int32_t)k[9]<<8) +((u_int32_t)k[10]<<16)+((u_int32_t)k[11]<<24));
69       mix(a,b,c);
70       k += 12; len -= 12;
71    }
72
73    /*------------------------------------- handle the last 11 bytes */
74    c += length;
75    switch(len)              /* all the case statements fall through */
76    {
77    case 11: c+=((u_int32_t)k[10]<<24);
78    case 10: c+=((u_int32_t)k[9]<<16);
79    case 9 : c+=((u_int32_t)k[8]<<8);
80       /* the first byte of c is reserved for the length */
81    case 8 : b+=((u_int32_t)k[7]<<24);
82    case 7 : b+=((u_int32_t)k[6]<<16);
83    case 6 : b+=((u_int32_t)k[5]<<8);
84    case 5 : b+=k[4];
85    case 4 : a+=((u_int32_t)k[3]<<24);
86    case 3 : a+=((u_int32_t)k[2]<<16);
87    case 2 : a+=((u_int32_t)k[1]<<8);
88    case 1 : a+=k[0];
89      /* case 0: nothing left to add */
90    }
91    mix(a,b,c);
92    /*-------------------------------------------- report the result */
93    return c;
94 }
95
96 u_int32_t jlog_hash__hash(const char *k, u_int32_t length, u_int32_t initval) {
97   return __hash(k,length,initval);
98 }
99
100 void jlog_hash_init(jlog_hash_table *h) {
101   memset(h, 0, sizeof(jlog_hash_table));
102   h->initval = lrand48();
103   h->table_size = JLogHASH_INITIAL_SIZE;
104   h->buckets = calloc(h->table_size, sizeof(jlog_hash_bucket *));
105 }
106
107 jlog_hash_bucket *jlog_hash__new_bucket(const char *k, int klen, void *data) {
108   jlog_hash_bucket *b;
109   b = calloc(1, sizeof(jlog_hash_bucket));
110   b->k = k;
111   b->klen = klen;
112   b->data = data;
113   return b;
114 }
115 void jlog_hash__rebucket(jlog_hash_table *h, int newsize) {
116   int i, newoff;
117   jlog_hash_bucket **newbuckets, *b, *n;
118
119   if (h->dont_rebucket) return;
120
121   i = newsize;
122   while(i) {
123     if(i & 1) break;
124     i >>= 1;
125   }
126   if(i & ~1) {
127     return;
128   }
129   newbuckets = calloc(newsize, sizeof(jlog_hash_bucket *));
130   h->num_used_buckets = 0;
131   for(i = 0; i < h->table_size; i++) {
132     b = h->buckets[i];
133     while(b) {
134       n = b->next;
135       newoff = __hash(b->k, b->klen, h->initval) & (newsize-1);
136       if(newbuckets[newoff] == NULL) h->num_used_buckets++;
137       b->next = newbuckets[newoff];
138       newbuckets[newoff] = b;
139       b = n;
140     }
141   }
142   free(h->buckets);
143   h->table_size = newsize;
144   h->buckets = newbuckets;
145 }
146 int jlog_hash_replace(jlog_hash_table *h, const char *k, int klen, void *data,
147                    JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) {
148   int off;
149   int replaced = 0;
150   jlog_hash_bucket __b, *tr, *b = &__b;
151
152   if(h->table_size == 0) jlog_hash_init(h);
153   off = __hash(k, klen, h->initval) & (h->table_size-1);
154   __b.next = h->buckets[off];
155   if(!b->next) h->num_used_buckets++;
156   while(b->next) {
157     if(b->next->klen == klen && !memcmp(b->next->k, k, klen)) {
158       tr = b->next;
159       if(keyfree) keyfree((void *)tr->k);
160       if(datafree && tr->data) datafree((void *)tr->data);
161       b->next = tr->next;
162       if(tr == h->buckets[off]) h->buckets[off] = tr->next;
163       free(tr);
164       replaced = 1;
165       break;
166     } else {
167       b = b->next;
168     }
169   }
170   b = jlog_hash__new_bucket(k, klen, data);
171   b->next = h->buckets[off];
172   h->buckets[off] = b;
173   if(!replaced) h->size++;
174
175   if(h->size > h->table_size - (h->table_size >> 3)) {
176     jlog_hash__rebucket(h, h->table_size << 1);
177   }
178   return 1;
179 }
180 int jlog_hash_store(jlog_hash_table *h, const char *k, int klen, void *data) {
181   int off;
182   jlog_hash_bucket *b;
183
184   if(h->table_size == 0) jlog_hash_init(h);
185   off = __hash(k, klen, h->initval) & (h->table_size-1);
186   b = h->buckets[off];
187   if(!b) h->num_used_buckets++;
188   while(b) {
189     if(b->klen == klen && !memcmp(b->k, k, klen)) return 0;
190     b = b->next;
191   }
192   b = jlog_hash__new_bucket(k, klen, data);
193   b->next = h->buckets[off];
194   h->buckets[off] = b;
195   h->size++;
196
197   if(h->size > h->table_size - (h->table_size >> 3)) {
198     jlog_hash__rebucket(h, h->table_size << 1);
199   }
200   return 1;
201 }
202 int jlog_hash_retrieve(jlog_hash_table *h, const char *k, int klen, void **data) {
203   int off;
204   jlog_hash_bucket *b;
205
206   if(h->table_size == 0) jlog_hash_init(h);
207   off = __hash(k, klen, h->initval) & (h->table_size-1);
208   b = h->buckets[off];
209   while(b) {
210     if(b->klen == klen && !memcmp(b->k, k, klen)) break;
211     b = b->next;
212   }
213   if(b) {
214     if(data) *data = b->data;
215     return 1;
216   }
217   return 0;
218 }
219 int jlog_hash_delete(jlog_hash_table *h, const char *k, int klen,
220                   JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) {
221   int off;
222   void *data;
223   jlog_hash_bucket *b, *prev = NULL;
224
225   if(h->table_size == 0) jlog_hash_init(h);
226   off = __hash(k, klen, h->initval) & (h->table_size-1);
227   b = h->buckets[off];
228   while(b) {
229     if(b->klen == klen && !memcmp(b->k, k, klen)) break;
230     prev = b;
231     b = b->next;
232   }
233   if(!b) return 0; /* No match */
234   data = b->data;
235   if(!prev) h->buckets[off] = h->buckets[off]->next;
236   else prev->next = b->next;
237   if(keyfree) keyfree((void *)b->k);
238   if(datafree && b->data) datafree(b->data);
239   free(b);
240   h->size--;
241   if(h->buckets[off] == NULL) h->num_used_buckets--;
242   if(h->table_size > JLogHASH_INITIAL_SIZE &&
243      h->size < h->table_size >> 2)
244     jlog_hash__rebucket(h, h->table_size >> 1);
245   return 1;
246 }
247
248 void jlog_hash_delete_all(jlog_hash_table *h, JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) {
249   int i;
250   jlog_hash_bucket *b, *tofree;
251   for(i=0; i<h->table_size; i++) {
252     b = h->buckets[i];
253     while(b) {
254       tofree = b;
255       b = b->next;
256       if(keyfree) keyfree((void *)tofree->k);
257       if(datafree && tofree->data) datafree(tofree->data);
258       free(tofree);
259     }
260     h->buckets[i] = NULL;
261   }
262   h->num_used_buckets = 0;
263   h->size = 0;
264   jlog_hash__rebucket(h, JLogHASH_INITIAL_SIZE);
265 }
266
267 void jlog_hash_destroy(jlog_hash_table *h, JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) {
268   jlog_hash_delete_all(h, keyfree, datafree);
269   if(h->buckets) free(h->buckets);
270 }
271
272 int jlog_hash_next(jlog_hash_table *h, jlog_hash_iter *iter,
273                 const char **k, int *klen, void **data) {
274   jlog_hash_bucket *b;
275  next_row:
276   if(iter->p1 < 0 || iter->p1 >= h->table_size) return 0;
277   if(iter->p2 == NULL) iter->p2 = (void *)h->buckets[iter->p1];
278   if(iter->p2 == NULL) {
279     iter->p1++;
280     goto next_row;
281   }
282   b = (jlog_hash_bucket *)(iter->p2);
283   *k = b->k; *klen = b->klen;
284   if(data) *data = b->data;
285   b = b->next;
286   if(!b) iter->p1++;
287   iter->p2 = b;
288   return 1;
289 }
290
291 int jlog_hash_firstkey(jlog_hash_table *h, const char **k, int *klen) {
292   int i;
293   for(i=0;i<h->table_size;i++) {
294     if(h->buckets[i]) {
295       *k = h->buckets[i]->k;
296       *klen = h->buckets[i]->klen;
297       return 1;
298     }
299   }
300   return 0;
301 }
302 int jlog_hash_nextkey(jlog_hash_table *h, const char **k, int *klen, const char *lk, int lklen) {
303   int off;
304   jlog_hash_bucket *b;
305
306   if(h->table_size == 0) return 0;
307   off = __hash(lk, lklen, h->initval) & (h->table_size-1);
308   b = h->buckets[off];
309   while(b) {
310     if(b->klen == lklen && !memcmp(b->k, lk, lklen)) break;
311     b = b->next;
312   }
313   if(b) {
314     if(b->next) {
315       *k = b->next->k;
316       *klen = b->next->klen;
317       return 1;
318     } else {
319       off++;
320       for(;off < h->table_size; off++) {
321         if(h->buckets[off]) {
322           *k = h->buckets[off]->k;
323           *klen = h->buckets[off]->klen;
324           return 1;
325         }
326       }
327     }
328   }
329   return 0;
330 }
331 /* vim: se sw=2 ts=2 et: */
Note: See TracBrowser for help on using the browser.