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 */
14static 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
21static 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
30static 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
39static void free_key(genhash_t *h, void *key)
40{
41    if (h->ops.freeKey != NULL) {
42        h->ops.freeKey(key);
43    }
44}
45
46static void free_value(genhash_t *h, void *value)
47{
48    if (h->ops.freeValue != NULL) {
49        h->ops.freeValue(value);
50    }
51}
52
53static 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
66genhash_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
89void genhash_free(genhash_t* h)
90{
91    if(h != NULL) {
92        genhash_clear(h);
93        free(h);
94    }
95}
96
97void 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
121static 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
137void* 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
150enum 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
170enum 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
200static 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
208int 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
242int 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
251void 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
267int 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
285static 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
296int 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
303int 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
311void 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
331int 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