root/src/utils/noit_hash.c

Revision 562e8748907cf83a714008cc9f4da844ee76c783, 8.7 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 2 months ago)

compile without warnings

  • Property mode set to 100644
Line 
1 /*
2  * Copyright (c) 2014, Circonus Inc.
3  * Copyright (c) 2005-2007, OmniTI Computer Consulting, Inc.
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are
8  * met:
9  *
10  *    * Redistributions of source code must retain the above copyright
11  *      notice, this list of conditions and the following disclaimer.
12  *    * Redistributions in binary form must reproduce the above
13  *      copyright notice, this list of conditions and the following
14  *      disclaimer in the documentation and/or other materials provided
15  *      with the distribution.
16  *    * Neither the name OmniTI Computer Consulting, Inc. nor the names
17  *      of its contributors may be used to endorse or promote products
18  *      derived from this software without specific prior written
19  *      permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33
34 #include "noit_config.h"
35 #include "noit_hash.h"
36 #include <time.h>
37 #include <assert.h>
38 #include <ck_epoch.h>
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 static int rand_init;
103 void noit_hash_init(noit_hash_table *h) {
104   return noit_hash_init_size(h, NoitHASH_INITIAL_SIZE);
105 }
106
107 static void *
108 ht_malloc(size_t r)
109 {
110
111   return malloc(r);
112 }
113
114 static void
115 ht_free(void *p, size_t b, bool r)
116 {
117
118   (void)b;
119   (void)r;
120   free(p);
121   return;
122 }
123
124 static struct ck_malloc my_allocator = {
125   .malloc = ht_malloc,
126   .free = ht_free
127 };
128
129 void noit_hash_init_size(noit_hash_table *h, int size) {
130   if(!rand_init) {
131     srand48((long int)time(NULL));
132     rand_init = 1;
133   }
134   if(size < 2) size = 2;
135   assert(ck_ht_init(&h->ht, CK_HT_MODE_BYTESTRING, NULL, &my_allocator,
136                     size, lrand48()));
137 }
138 int noit_hash_size(noit_hash_table *h) {
139   if(h->ht.h == NULL) noit_hash_init(h);
140   return ck_ht_count(&h->ht);
141 }
142 int noit_hash_replace(noit_hash_table *h, const char *k, int klen, void *data,
143                       NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
144   ck_ht_entry_t entry;
145   ck_ht_hash_t hv;
146   void *tofree;
147
148   if(h->ht.h == NULL) noit_hash_init(h);
149   ck_ht_hash(&hv, &h->ht, k, klen);
150   ck_ht_entry_set(&entry, hv, k, klen, data);
151   if(ck_ht_set_spmc(&h->ht, hv, &entry) && !ck_ht_entry_empty(&entry)) {
152     if(keyfree && (tofree = ck_ht_entry_key(&entry)) != k) keyfree(tofree);
153     if(datafree && (tofree = ck_ht_entry_value(&entry)) != data) datafree(tofree);
154   }
155   return 1;
156 }
157 int noit_hash_store(noit_hash_table *h, const char *k, int klen, void *data) {
158   ck_ht_entry_t entry;
159   ck_ht_hash_t hv;
160
161   if(h->ht.h == NULL) noit_hash_init(h);
162   ck_ht_hash(&hv, &h->ht, k, klen);
163   ck_ht_entry_set(&entry, hv, k, klen, data);
164   return ck_ht_put_spmc(&h->ht, hv, &entry);
165 }
166 int noit_hash_retrieve(noit_hash_table *h, const char *k, int klen, void **data) {
167   ck_ht_entry_t entry;
168   ck_ht_hash_t hv;
169
170   if(!h) return 0;
171   if(h->ht.h == NULL) noit_hash_init(h);
172   ck_ht_hash(&hv, &h->ht, k, klen);
173   ck_ht_entry_set(&entry, hv, k, klen, NULL);
174   if(ck_ht_get_spmc(&h->ht, hv, &entry)) {
175     if(data) *data = ck_ht_entry_value(&entry);
176     return 1;
177   }
178   return 0;
179 }
180 int noit_hash_retr_str(noit_hash_table *h, const char *k, int klen, const char **dstr) {
181   void *data;
182   if(!h) return 0;
183   if(noit_hash_retrieve(h, k, klen, &data)) {
184     if(dstr) *dstr = data;
185     return 1;
186   }
187   return 0;
188 }
189 int noit_hash_delete(noit_hash_table *h, const char *k, int klen,
190                      NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
191   ck_ht_entry_t entry;
192   ck_ht_hash_t hv;
193
194   if(!h) return 0;
195   if(h->ht.h == NULL) noit_hash_init(h);
196   ck_ht_hash(&hv, &h->ht, k, klen);
197   ck_ht_entry_set(&entry, hv, k, klen, NULL);
198   if(ck_ht_remove_spmc(&h->ht, hv, &entry)) {
199     void *tofree;
200     if(keyfree && (tofree = ck_ht_entry_key(&entry)) != NULL) keyfree(tofree);
201     if(datafree && (tofree = ck_ht_entry_value(&entry)) != NULL) datafree(tofree);
202     return 1;
203   }
204   return 0;
205 }
206
207 void noit_hash_delete_all(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
208   ck_ht_entry_t *cursor;
209   ck_ht_iterator_t iterator = CK_HT_ITERATOR_INITIALIZER;
210   if(!h) return;
211   if(!keyfree && !datafree) return;
212   if(h->ht.h == NULL) noit_hash_init(h);
213   while(ck_ht_next(&h->ht, &iterator, &cursor)) {
214     if(keyfree) keyfree(ck_ht_entry_key(cursor));
215     if(datafree) datafree(ck_ht_entry_value(cursor));
216   }
217 }
218
219 void noit_hash_destroy(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) {
220   if(!h) return;
221   if(h->ht.h == NULL) noit_hash_init(h);
222   noit_hash_delete_all(h, keyfree, datafree);
223   ck_ht_destroy(&h->ht);
224 }
225
226 void noit_hash_merge_as_dict(noit_hash_table *dst, noit_hash_table *src) {
227   noit_hash_iter iter = NOIT_HASH_ITER_ZERO;
228   const char *k;
229   int klen;
230   void *data;
231   if(src == NULL || dst == NULL) return;
232   while(noit_hash_next(src, &iter, &k, &klen, &data))
233     noit_hash_replace(dst, strdup(k), klen, strdup((char *)data), free, free);
234 }
235
236 int noit_hash_next(noit_hash_table *h, noit_hash_iter *iter,
237                 const char **k, int *klen, void **data) {
238   ck_ht_entry_t *cursor;
239   if(h->ht.h == NULL) noit_hash_init(h);
240   if(!ck_ht_next(&h->ht, iter, &cursor)) return 0;
241   *k = ck_ht_entry_key(cursor);
242   *klen = ck_ht_entry_key_length(cursor);
243   *data = ck_ht_entry_value(cursor);
244   return 1;
245 }
246
247 int noit_hash_next_str(noit_hash_table *h, noit_hash_iter *iter,
248                        const char **k, int *klen, const char **dstr) {
249   void *data = NULL;
250   int rv;
251   rv = noit_hash_next(h,iter,k,klen,&data);
252   *dstr = data;
253   return rv;
254 }
255
256 /* This exists so that we have an instance of this to pull in the CTF
257  * definition so that mdb can "know" the type alias here.
258  */
259 struct _noit_hash_bucket {
260 #ifdef CK_HT_PP
261   uintptr_t key;
262   uintptr_t value CK_CC_PACKED;
263 } CK_CC_ALIGN(16);
264 #else
265   /* these are simply renamed to make them look like the same
266    * keys as the old noit_hash_bucket implelentation...
267    * If ck_ht is pointer-packed, it's not reasonable.
268    */
269   const char *k;
270   void *data;
271   uint64_t klen;
272   uint64_t hash;
273 } CK_CC_ALIGN(32);
274 #endif
275 typedef struct _noit_hash_bucket noit_hash_bucket;
276 static noit_hash_bucket __noit_hash_use_of_hash_bucket __attribute__((unused));
277
278 /* vim: se sw=2 ts=2 et: */
Note: See TracBrowser for help on using the browser.