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