1 /*
2  * Copyright (c) 2006  Dustin Sallings <dustin@spy.net>
3  */
4 
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <math.h>
8 #include <platform/cbassert.h>
9 
10 #include "genhash.h"
11 #include "genhash_int.h"
12 
13 /* Table of 32 primes by their distance from the nearest power of two */
14 static int prime_size_table[]={
15     3, 7, 13, 23, 47, 97, 193, 383, 769, 1531, 3067, 6143, 12289, 24571, 49157,
16     98299, 196613, 393209, 786433, 1572869, 3145721, 6291449, 12582917,
17     25165813, 50331653, 100663291, 201326611, 402653189, 805306357,
18     1610612741
19 };
20 
dup_key(genhash_t *h, const void *key, size_t klen)21 static void* dup_key(genhash_t *h, const void *key, size_t klen)
22 {
23     if (h->ops.dupKey != NULL) {
24         return h->ops.dupKey(key, klen);
25     } else {
26         return (void*)key;
27     }
28 }
29 
dup_value(genhash_t *h, const void *value, size_t vlen)30 static void* dup_value(genhash_t *h, const void *value, size_t vlen)
31 {
32     if (h->ops.dupValue != NULL) {
33         return h->ops.dupValue(value, vlen);
34     } else {
35         return (void*)value;
36     }
37 }
38 
free_key(genhash_t *h, void *key)39 static void free_key(genhash_t *h, void *key)
40 {
41     if (h->ops.freeKey != NULL) {
42         h->ops.freeKey(key);
43     }
44 }
45 
free_value(genhash_t *h, void *value)46 static void free_value(genhash_t *h, void *value)
47 {
48     if (h->ops.freeValue != NULL) {
49         h->ops.freeValue(value);
50     }
51 }
52 
estimate_table_size(int est)53 static int estimate_table_size(int est)
54 {
55     int rv=0;
56     size_t magn=0;
57     cb_assert(est > 0);
58     magn=(int)log((double)est)/log(2);
59     magn--;
60     magn = ((int)magn < 0) ? 0 : magn;
61     cb_assert(magn < (sizeof(prime_size_table) / sizeof(int)));
62     rv=prime_size_table[magn];
63     return rv;
64 }
65 
genhash_init(int est, struct hash_ops ops)66 genhash_t* genhash_init(int est, struct hash_ops ops)
67 {
68     genhash_t* rv=NULL;
69     int size=0;
70     if (est < 1) {
71         return NULL;
72     }
73 
74     cb_assert(ops.hashfunc != NULL);
75     cb_assert(ops.hasheq != NULL);
76     cb_assert((ops.dupKey != NULL && ops.freeKey != NULL) || ops.freeKey == NULL);
77     cb_assert((ops.dupValue != NULL && ops.freeValue != NULL) || ops.freeValue == NULL);
78 
79     size=estimate_table_size(est);
80     rv=calloc(1, sizeof(genhash_t)
81               + (size * sizeof(struct genhash_entry_t *)));
82     cb_assert(rv != NULL);
83     rv->size=size;
84     rv->ops=ops;
85 
86     return rv;
87 }
88 
genhash_free(genhash_t* h)89 void genhash_free(genhash_t* h)
90 {
91     if(h != NULL) {
92         genhash_clear(h);
93         free(h);
94     }
95 }
96 
genhash_store(genhash_t *h, const void* k, size_t klen, const void* v, size_t vlen)97 void genhash_store(genhash_t *h, const void* k, size_t klen,
98                    const void* v, size_t vlen)
99 {
100     size_t n=0;
101     struct genhash_entry_t *p;
102 
103     cb_assert(h != NULL);
104 
105     n=h->ops.hashfunc(k, klen) % h->size;
106     cb_assert((int)n >= 0);
107     cb_assert(n < h->size);
108 
109     p=calloc(1, sizeof(struct genhash_entry_t));
110     cb_assert(p);
111 
112     p->key=dup_key(h, k, klen);
113     p->nkey = klen;
114     p->value=dup_value(h, v, vlen);
115     p->nvalue = vlen;
116 
117     p->next=h->buckets[n];
118     h->buckets[n]=p;
119 }
120 
genhash_find_entry(genhash_t *h, const void* k, size_t klen)121 static struct genhash_entry_t *genhash_find_entry(genhash_t *h,
122                                                   const void* k,
123                                                   size_t klen)
124 {
125     size_t n=0;
126     struct genhash_entry_t *p;
127 
128     cb_assert(h != NULL);
129     n=h->ops.hashfunc(k, klen) % h->size;
130     cb_assert((int)n >= 0);
131     cb_assert(n < h->size);
132 
133     for(p=h->buckets[n]; p && !h->ops.hasheq(k, klen, p->key, p->nkey); p=p->next);
134     return p;
135 }
136 
genhash_find(genhash_t *h, const void* k, size_t klen)137 void* genhash_find(genhash_t *h, const void* k, size_t klen)
138 {
139     struct genhash_entry_t *p;
140     void *rv=NULL;
141 
142     p=genhash_find_entry(h, k, klen);
143 
144     if(p) {
145         rv=p->value;
146     }
147     return rv;
148 }
149 
genhash_update(genhash_t* h, const void* k, size_t klen, const void* v, size_t vlen)150 enum update_type genhash_update(genhash_t* h, const void* k, size_t klen,
151                                 const void* v, size_t vlen)
152 {
153     struct genhash_entry_t *p;
154     enum update_type rv=0;
155 
156     p=genhash_find_entry(h, k, klen);
157 
158     if(p) {
159         free_value(h, p->value);
160         p->value=dup_value(h, v, vlen);
161         rv=MODIFICATION;
162     } else {
163         genhash_store(h, k, klen, v, vlen);
164         rv=NEW;
165     }
166 
167     return rv;
168 }
169 
genhash_fun_update(genhash_t* h, const void* k, size_t klen, void *(*upd)(const void *, const void *, size_t *, void *), void (*fr)(void*), void *arg, const void *def, size_t deflen)170 enum update_type genhash_fun_update(genhash_t* h, const void* k, size_t klen,
171                                     void *(*upd)(const void *, const void *,
172                                                  size_t *, void *),
173                                     void (*fr)(void*),
174                                     void *arg,
175                                     const void *def, size_t deflen)
176 {
177     struct genhash_entry_t *p;
178     enum update_type rv=0;
179     size_t newSize = 0;
180     (void)deflen;
181 
182     p=genhash_find_entry(h, k, klen);
183 
184     if(p) {
185         void *newValue=upd(k, p->value, &newSize, arg);
186         free_value(h, p->value);
187         p->value=dup_value(h, newValue, newSize);
188         fr(newValue);
189         rv=MODIFICATION;
190     } else {
191         void *newValue=upd(k, def, &newSize, arg);
192         genhash_store(h, k, klen, newValue, newSize);
193         fr(newValue);
194         rv=NEW;
195     }
196 
197     return rv;
198 }
199 
free_item(genhash_t *h, struct genhash_entry_t *i)200 static void free_item(genhash_t *h, struct genhash_entry_t *i)
201 {
202     cb_assert(i);
203     free_key(h, i->key);
204     free_value(h, i->value);
205     free(i);
206 }
207 
genhash_delete(genhash_t* h, const void* k, size_t klen)208 int genhash_delete(genhash_t* h, const void* k, size_t klen)
209 {
210     struct genhash_entry_t *deleteme=NULL;
211     size_t n=0;
212     int rv=0;
213 
214     cb_assert(h != NULL);
215     n=h->ops.hashfunc(k, klen) % h->size;
216     cb_assert((int)n >= 0);
217     cb_assert(n < h->size);
218 
219     if(h->buckets[n] != NULL) {
220         /* Special case the first one */
221         if(h->ops.hasheq(h->buckets[n]->key, h->buckets[n]->nkey, k, klen)) {
222             deleteme=h->buckets[n];
223             h->buckets[n]=deleteme->next;
224         } else {
225             struct genhash_entry_t *p=NULL;
226             for(p=h->buckets[n]; deleteme==NULL && p->next != NULL; p=p->next) {
227                 if(h->ops.hasheq(p->next->key, p->next->nkey, k, klen)) {
228                     deleteme=p->next;
229                     p->next=deleteme->next;
230                 }
231             }
232         }
233     }
234     if(deleteme != NULL) {
235         free_item(h, deleteme);
236         rv++;
237     }
238 
239     return rv;
240 }
241 
genhash_delete_all(genhash_t* h, const void* k, size_t klen)242 int genhash_delete_all(genhash_t* h, const void* k, size_t klen)
243 {
244     int rv=0;
245     while(genhash_delete(h, k, klen) == 1) {
246         rv++;
247     }
248     return rv;
249 }
250 
genhash_iter(genhash_t* h, void (*iterfunc)(const void* key, size_t nkey, const void* val, size_t nval, void *arg), void *arg)251 void genhash_iter(genhash_t* h,
252                   void (*iterfunc)(const void* key, size_t nkey,
253                                    const void* val, size_t nval,
254                                    void *arg), void *arg)
255 {
256     size_t i=0;
257     struct genhash_entry_t *p=NULL;
258     cb_assert(h != NULL);
259 
260     for(i=0; i<h->size; i++) {
261         for(p=h->buckets[i]; p!=NULL; p=p->next) {
262             iterfunc(p->key, p->nkey, p->value, p->nvalue, arg);
263         }
264     }
265 }
266 
genhash_clear(genhash_t *h)267 int genhash_clear(genhash_t *h)
268 {
269     size_t i = 0;
270     int rv = 0;
271     cb_assert(h != NULL);
272 
273     for(i = 0; i < h->size; i++) {
274         while(h->buckets[i]) {
275             struct genhash_entry_t *p = NULL;
276             p = h->buckets[i];
277             h->buckets[i] = p->next;
278             free_item(h, p);
279         }
280     }
281 
282     return rv;
283 }
284 
count_entries(const void *key, size_t klen, const void *val, size_t vlen, void *arg)285 static void count_entries(const void *key, size_t klen,
286                           const void *val, size_t vlen, void *arg)
287 {
288     int *count=(int *)arg;
289     (*count)++;
290     (void)key;
291     (void)klen;
292     (void)val;
293     (void)vlen;
294 }
295 
genhash_size(genhash_t* h)296 int genhash_size(genhash_t* h) {
297     int rv=0;
298     cb_assert(h != NULL);
299     genhash_iter(h, count_entries, &rv);
300     return rv;
301 }
302 
genhash_size_for_key(genhash_t* h, const void* k, size_t klen)303 int genhash_size_for_key(genhash_t* h, const void* k, size_t klen)
304 {
305     int rv=0;
306     cb_assert(h != NULL);
307     genhash_iter_key(h, k, klen, count_entries, &rv);
308     return rv;
309 }
310 
genhash_iter_key(genhash_t* h, const void* key, size_t klen, void (*iterfunc)(const void* key, size_t klen, const void* val, size_t vlen, void *arg), void *arg)311 void genhash_iter_key(genhash_t* h, const void* key, size_t klen,
312                       void (*iterfunc)(const void* key, size_t klen,
313                                        const void* val, size_t vlen,
314                                        void *arg), void *arg)
315 {
316     size_t n=0;
317     struct genhash_entry_t *p=NULL;
318 
319     cb_assert(h != NULL);
320     n=h->ops.hashfunc(key, klen) % h->size;
321     cb_assert((int)n >= 0);
322     cb_assert(n < h->size);
323 
324     for(p=h->buckets[n]; p!=NULL; p=p->next) {
325         if(h->ops.hasheq(key, klen, p->key, p->nkey)) {
326             iterfunc(p->key, p->nkey, p->value, p->nvalue, arg);
327         }
328     }
329 }
330 
genhash_string_hash(const void* p, size_t nkey)331 int genhash_string_hash(const void* p, size_t nkey)
332 {
333     int rv=5381;
334     size_t i=0;
335     char *str=(char *)p;
336 
337     for(i=0; i < nkey; i++) {
338         rv = ((rv << 5) + rv) ^ str[i];
339     }
340 
341     return rv;
342 }
343