Permalink
Newer
Older
100644 335 lines (280 sloc) 6.67 KB
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 <assert.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
21
static int
22
estimate_table_size(int est)
23
{
24
int rv=0;
25
int magn=0;
26
assert(est > 0);
27
magn=(int)log((double)est)/log(2);
28
magn--;
29
magn = (magn < 0) ? 0 : magn;
30
assert(magn < (int) (sizeof(prime_size_table) / sizeof(int)));
31
rv=prime_size_table[magn];
32
return rv;
33
}
34
35
genhash_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
assert(ops.hashfunc != NULL);
44
assert(ops.hasheq != NULL);
45
assert(ops.dupKey != NULL);
46
assert(ops.dupValue != NULL);
47
assert(ops.freeKey != NULL);
48
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
assert(rv != NULL);
54
rv->size=size;
55
rv->ops=ops;
56
57
return rv;
58
}
59
60
static void
61
free_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
71
void
72
genhash_free(genhash_t* h)
73
{
74
if(h != NULL) {
76
for(i=0; i<h->size; i++) {
77
free_bucket(h, h->buckets[i]);
78
}
79
free(h);
80
}
81
}
82
83
void
84
genhash_store(genhash_t *h, const void* k, const void* v)
85
{
86
int n=0;
87
struct genhash_entry_t *p;
88
89
assert(h != NULL);
90
91
n=h->ops.hashfunc(k) % h->size;
92
assert(n >= 0);
93
assert(n < (int) h->size);
94
95
p=calloc(1, sizeof(struct genhash_entry_t));
96
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
105
static struct genhash_entry_t *
106
genhash_find_entry(genhash_t *h, const void* k)
107
{
108
int n=0;
109
struct genhash_entry_t *p;
110
111
assert(h != NULL);
112
n=h->ops.hashfunc(k) % h->size;
113
assert(n >= 0);
114
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
121
void*
122
genhash_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
135
enum update_type
136
genhash_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);
152
rv=MODIFICATION;
153
} else {
154
genhash_store(h, k, v);
155
rv=NEW;
156
}
157
158
return rv;
159
}
160
161
enum update_type
162
genhash_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);
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
195
int
196
genhash_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
assert(h != NULL);
203
n=h->ops.hashfunc(k) % h->size;
204
assert(n >= 0);
205
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
232
int
233
genhash_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
242
void
243
genhash_iter(genhash_t* h,
244
void (*iterfunc)(const void* key, const void* val, void *arg), void *arg)
245
{
247
struct genhash_entry_t *p=NULL;
248
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
257
int
258
genhash_clear(genhash_t *h)
259
{
261
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
275
}
276
277
static void
278
count_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
286
int
287
genhash_size(genhash_t* h) {
288
int rv=0;
289
assert(h != NULL);
290
genhash_iter(h, count_entries, &rv);
291
return rv;
292
}
293
294
int
295
genhash_size_for_key(genhash_t* h, const void* k)
296
{
297
int rv=0;
298
assert(h != NULL);
299
genhash_iter_key(h, k, count_entries, &rv);
300
return rv;
301
}
302
303
void
304
genhash_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
assert(h != NULL);
311
n=h->ops.hashfunc(key) % h->size;
312
assert(n >= 0);
313
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
322
int
323
genhash_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
}