root/tags/2.0.0/echash.c

Revision 41, 9.3 kB (checked in by jesus, 8 years ago)

autoconf support

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