1 |
/* Creation date: 2005-06-24 21:22:40
|
2 |
* Authors: Don
|
3 |
* Change log:
|
4 |
*/
|
5 |
|
6 |
/* Copyright (c) 2005 Don Owens
|
7 |
All rights reserved.
|
8 |
|
9 |
This code is released under the BSD license:
|
10 |
|
11 |
Redistribution and use in source and binary forms, with or without
|
12 |
modification, are permitted provided that the following conditions
|
13 |
are met:
|
14 |
|
15 |
* Redistributions of source code must retain the above copyright
|
16 |
notice, this list of conditions and the following disclaimer.
|
17 |
|
18 |
* Redistributions in binary form must reproduce the above
|
19 |
copyright notice, this list of conditions and the following
|
20 |
disclaimer in the documentation and/or other materials provided
|
21 |
with the distribution.
|
22 |
|
23 |
* Neither the name of the author nor the names of its
|
24 |
contributors may be used to endorse or promote products derived
|
25 |
from this software without specific prior written permission.
|
26 |
|
27 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
28 |
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
29 |
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
|
30 |
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
|
31 |
COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
|
32 |
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
33 |
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
34 |
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
35 |
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
36 |
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
37 |
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
|
38 |
OF THE POSSIBILITY OF SUCH DAMAGE.
|
39 |
*/
|
40 |
|
41 |
#include "cfu.h"
|
42 |
|
43 |
#include <pthread.h>
|
44 |
#include <string.h>
|
45 |
#include <stdlib.h>
|
46 |
#include <ctype.h>
|
47 |
|
48 |
#include "cfuhash.h"
|
49 |
#include "cfustring.h"
|
50 |
|
51 |
#ifdef CFU_DEBUG
|
52 |
#ifdef NDEBUG
|
53 |
#undef NDEBUG
|
54 |
#endif
|
55 |
#else
|
56 |
#ifndef NDEBUG
|
57 |
#define NDEBUG 1
|
58 |
#endif
|
59 |
#endif
|
60 |
#include <assert.h>
|
61 |
|
62 |
typedef struct cfuhash_event_flags {
|
63 |
int resized:1;
|
64 |
int pad:31;
|
65 |
} cfuhash_event_flags;
|
66 |
|
67 |
typedef struct cfuhash_entry {
|
68 |
long long key;
|
69 |
size_t key_size;
|
70 |
long data;
|
71 |
size_t data_size;
|
72 |
struct cfuhash_entry *next;
|
73 |
} cfuhash_entry;
|
74 |
|
75 |
struct cfuhash_table {
|
76 |
libcfu_type type;
|
77 |
size_t num_buckets;
|
78 |
size_t entries; /* Total number of entries in the table. */
|
79 |
cfuhash_entry **buckets;
|
80 |
pthread_mutex_t mutex;
|
81 |
u_int32_t flags;
|
82 |
cfuhash_function_t hash_func;
|
83 |
size_t each_bucket_index;
|
84 |
cfuhash_entry *each_chain_entry;
|
85 |
float high;
|
86 |
float low;
|
87 |
cfuhash_free_fn_t free_fn;
|
88 |
unsigned int resized_count;
|
89 |
cfuhash_event_flags event_flags;
|
90 |
};
|
91 |
|
92 |
/* Perl's hash function */
|
93 |
static u_int32_t
|
94 |
hash_func(long long key, size_t length)
|
95 |
{
|
96 |
register size_t i = sizeof(long long);
|
97 |
register u_int hv = 0; /* could put a seed here instead of zero */
|
98 |
register const unsigned char *s = (char *)&key;
|
99 |
|
100 |
while (i--)
|
101 |
{
|
102 |
hv += *s++;
|
103 |
hv += (hv << 10);
|
104 |
hv ^= (hv >> 6);
|
105 |
}
|
106 |
|
107 |
hv += (hv << 3);
|
108 |
hv ^= (hv >> 11);
|
109 |
hv += (hv << 15);
|
110 |
|
111 |
return hv;
|
112 |
}
|
113 |
|
114 |
/* makes sure the real size of the buckets array is a power of 2 */
|
115 |
static u_int
|
116 |
hash_size(u_int s) {
|
117 |
u_int i = 1;
|
118 |
while (i < s) i <<= 1;
|
119 |
return i;
|
120 |
}
|
121 |
|
122 |
static inline void *
|
123 |
hash_key_dup(const void *key, size_t key_size) {
|
124 |
void *new_key = malloc(key_size);
|
125 |
memcpy(new_key, key, key_size);
|
126 |
return new_key;
|
127 |
}
|
128 |
|
129 |
static inline void *
|
130 |
hash_key_dup_lower_case(const void *key, size_t key_size) {
|
131 |
char *new_key = (char *)hash_key_dup(key, key_size);
|
132 |
size_t i = 0;
|
133 |
for (i = 0; i < key_size; i++) new_key[i] = tolower(new_key[i]);
|
134 |
return (void *)new_key;
|
135 |
}
|
136 |
|
137 |
/* returns the index into the buckets array */
|
138 |
static inline u_int
|
139 |
hash_value(cfuhash_table_t *ht, long long key, size_t key_size, size_t num_buckets) {
|
140 |
u_int hv = 0;
|
141 |
|
142 |
if (key) {
|
143 |
//if (ht->flags & CFUHASH_IGNORE_CASE) {
|
144 |
// char *lc_key = (char *)hash_key_dup_lower_case(key, key_size);
|
145 |
// hv = ht->hash_func(lc_key, key_size);
|
146 |
// free(lc_key);
|
147 |
//} else {
|
148 |
hv = ht->hash_func(key, key_size);
|
149 |
//}
|
150 |
}
|
151 |
|
152 |
/* The idea is the following: if, e.g., num_buckets is 32
|
153 |
(000001), num_buckets - 1 will be 31 (111110). The & will make
|
154 |
sure we only get the first 5 bits which will guarantee the
|
155 |
index is less than 32.
|
156 |
*/
|
157 |
return hv & (num_buckets - 1);
|
158 |
}
|
159 |
|
160 |
static cfuhash_table_t *
|
161 |
_cfuhash_new(size_t size, u_int32_t flags) {
|
162 |
cfuhash_table_t *ht;
|
163 |
|
164 |
size = hash_size(size);
|
165 |
ht = (cfuhash_table_t *)malloc(sizeof(cfuhash_table_t));
|
166 |
memset(ht, '\000', sizeof(cfuhash_table_t));
|
167 |
|
168 |
ht->type = libcfu_t_hash_table;
|
169 |
ht->num_buckets = size;
|
170 |
ht->entries = 0;
|
171 |
ht->flags = flags;
|
172 |
ht->buckets = (cfuhash_entry **)calloc(size, sizeof(cfuhash_entry *));
|
173 |
pthread_mutex_init(&ht->mutex, NULL);
|
174 |
|
175 |
ht->hash_func = hash_func;
|
176 |
ht->high = 0.75;
|
177 |
ht->low = 0.25;
|
178 |
|
179 |
return ht;
|
180 |
}
|
181 |
|
182 |
extern cfuhash_table_t *
|
183 |
cfuhash_new() {
|
184 |
return _cfuhash_new(8, CFUHASH_FROZEN_UNTIL_GROWS);
|
185 |
}
|
186 |
|
187 |
extern cfuhash_table_t *
|
188 |
cfuhash_new_with_initial_size(size_t size) {
|
189 |
if (size == 0) size = 8;
|
190 |
return _cfuhash_new(size, CFUHASH_FROZEN_UNTIL_GROWS);
|
191 |
}
|
192 |
|
193 |
extern cfuhash_table_t *
|
194 |
cfuhash_new_with_flags(u_int32_t flags) {
|
195 |
return _cfuhash_new(8, CFUHASH_FROZEN_UNTIL_GROWS|flags);
|
196 |
}
|
197 |
|
198 |
extern cfuhash_table_t * cfuhash_new_with_free_fn(cfuhash_free_fn_t ff) {
|
199 |
cfuhash_table_t *ht = _cfuhash_new(8, CFUHASH_FROZEN_UNTIL_GROWS);
|
200 |
cfuhash_set_free_function(ht, ff);
|
201 |
return ht;
|
202 |
}
|
203 |
|
204 |
extern int
|
205 |
cfuhash_copy(cfuhash_table_t *src, cfuhash_table_t *dst) {
|
206 |
size_t num_keys = 0;
|
207 |
void **keys = NULL;
|
208 |
size_t *key_sizes;
|
209 |
size_t i = 0;
|
210 |
void *val = NULL;
|
211 |
size_t data_size = 0;
|
212 |
|
213 |
keys = cfuhash_keys_data(src, &num_keys, &key_sizes, 0);
|
214 |
|
215 |
for (i = 0; i < num_keys; i++) {
|
216 |
if (cfuhash_get_data(src, (void *)keys[i], key_sizes[i], &val, &data_size)) {
|
217 |
cfuhash_put_data(dst, (void *)keys[i], key_sizes[i], val, data_size, NULL);
|
218 |
}
|
219 |
free(keys[i]);
|
220 |
}
|
221 |
|
222 |
free(keys);
|
223 |
free(key_sizes);
|
224 |
|
225 |
return 1;
|
226 |
}
|
227 |
|
228 |
extern cfuhash_table_t *
|
229 |
cfuhash_merge(cfuhash_table_t *ht1, cfuhash_table_t *ht2, u_int32_t flags) {
|
230 |
cfuhash_table_t *new_ht = NULL;
|
231 |
|
232 |
flags |= CFUHASH_FROZEN_UNTIL_GROWS;
|
233 |
new_ht = _cfuhash_new(cfuhash_num_entries(ht1) + cfuhash_num_entries(ht2), flags);
|
234 |
if (ht1) cfuhash_copy(ht1, new_ht);
|
235 |
if (ht2) cfuhash_copy(ht2, new_ht);
|
236 |
|
237 |
return new_ht;
|
238 |
}
|
239 |
|
240 |
/* returns the flags */
|
241 |
extern u_int32_t
|
242 |
cfuhash_get_flags(cfuhash_table_t *ht) {
|
243 |
return ht->flags;
|
244 |
}
|
245 |
|
246 |
/* sets the given flag and returns the old flags value */
|
247 |
extern u_int32_t
|
248 |
cfuhash_set_flag(cfuhash_table_t *ht, u_int32_t new_flag) {
|
249 |
u_int32_t flags = ht->flags;
|
250 |
ht->flags = flags | new_flag;
|
251 |
return flags;
|
252 |
}
|
253 |
|
254 |
extern u_int32_t
|
255 |
cfuhash_clear_flag(cfuhash_table_t *ht, u_int32_t new_flag) {
|
256 |
u_int32_t flags = ht->flags;
|
257 |
ht->flags = flags & ~new_flag;
|
258 |
return flags;
|
259 |
}
|
260 |
|
261 |
extern int
|
262 |
cfuhash_set_thresholds(cfuhash_table_t *ht, float low, float high) {
|
263 |
float h = high < 0 ? ht->high : high;
|
264 |
float l = low < 0 ? ht->low : low;
|
265 |
|
266 |
if (h < l) return -1;
|
267 |
|
268 |
ht->high = h;
|
269 |
ht->low = l;
|
270 |
|
271 |
return 0;
|
272 |
}
|
273 |
|
274 |
/* Sets the hash function for the hash table ht. Pass NULL for hf to reset to the default */
|
275 |
extern int
|
276 |
cfuhash_set_hash_function(cfuhash_table_t *ht, cfuhash_function_t hf) {
|
277 |
/* can't allow changing the hash function if the hash already contains entries */
|
278 |
if (ht->entries) return -1;
|
279 |
|
280 |
ht->hash_func = hf ? hf : hash_func;
|
281 |
return 0;
|
282 |
}
|
283 |
|
284 |
extern int
|
285 |
cfuhash_set_free_function(cfuhash_table_t * ht, cfuhash_free_fn_t ff) {
|
286 |
if (ff) ht->free_fn = ff;
|
287 |
return 0;
|
288 |
}
|
289 |
|
290 |
static inline void
|
291 |
lock_hash(cfuhash_table_t *ht) {
|
292 |
|
293 |
return;
|
294 |
|
295 |
//if (!ht) return;
|
296 |
//if (ht->flags & CFUHASH_NO_LOCKING) return;
|
297 |
//pthread_mutex_lock(&ht->mutex);
|
298 |
}
|
299 |
|
300 |
static inline void
|
301 |
unlock_hash(cfuhash_table_t *ht) {
|
302 |
|
303 |
return;
|
304 |
|
305 |
//if (!ht) return;
|
306 |
//if (ht->flags & CFUHASH_NO_LOCKING) return;
|
307 |
//pthread_mutex_unlock(&ht->mutex);
|
308 |
}
|
309 |
|
310 |
extern int
|
311 |
cfuhash_lock(cfuhash_table_t *ht) {
|
312 |
//pthread_mutex_lock(&ht->mutex);
|
313 |
return 1;
|
314 |
}
|
315 |
|
316 |
extern int
|
317 |
cfuhash_unlock(cfuhash_table_t *ht) {
|
318 |
//pthread_mutex_unlock(&ht->mutex);
|
319 |
return 1;
|
320 |
}
|
321 |
|
322 |
/* see if this key matches the one in the hash entry */
|
323 |
/* uses the convention that zero means a match, like memcmp */
|
324 |
|
325 |
static inline int
|
326 |
hash_cmp(long long key, size_t key_size, cfuhash_entry *he, u_int case_insensitive) {
|
327 |
// if (key_size != he->key_size) return 1;
|
328 |
if (key == he->key) return 0;
|
329 |
//if (case_insensitive) {
|
330 |
// return strncasecmp(key, he->key, key_size);
|
331 |
//}
|
332 |
//return memcmp(key, he->key, key_size);
|
333 |
return 1;
|
334 |
}
|
335 |
|
336 |
|
337 |
static inline cfuhash_entry *
|
338 |
hash_add_entry(cfuhash_table_t *ht, u_int hv, long long key, size_t key_size,
|
339 |
long data, size_t data_size) {
|
340 |
cfuhash_entry *he = (cfuhash_entry *)calloc(1, sizeof(cfuhash_entry));
|
341 |
|
342 |
assert(hv < ht->num_buckets);
|
343 |
|
344 |
/*
|
345 |
if (ht->flags & CFUHASH_NOCOPY_KEYS)
|
346 |
he->key = (void *)key;
|
347 |
else
|
348 |
he->key = hash_key_dup(key, key_size);
|
349 |
*/
|
350 |
he->key = key;
|
351 |
|
352 |
//he->key_size = key_size;
|
353 |
he->data = data;
|
354 |
|
355 |
//printf("data=%ld\n", data);
|
356 |
//printf("data2=%ld\n", he->data);
|
357 |
|
358 |
//he->data_size = data_size;
|
359 |
he->next = ht->buckets[hv];
|
360 |
ht->buckets[hv] = he;
|
361 |
ht->entries++;
|
362 |
|
363 |
return he;
|
364 |
}
|
365 |
|
366 |
/*
|
367 |
Returns one if the entry was found, zero otherwise. If found, r is
|
368 |
changed to point to the data in the entry.
|
369 |
*/
|
370 |
extern int
|
371 |
cfuhash_get_data(cfuhash_table_t *ht, long long key, size_t key_size, long *r,
|
372 |
size_t *data_size) {
|
373 |
u_int hv = 0;
|
374 |
cfuhash_entry *hr = NULL;
|
375 |
|
376 |
if (!ht) return 0;
|
377 |
|
378 |
/*
|
379 |
if (key_size == (size_t)(-1)) {
|
380 |
if (key) key_size = strlen(key) + 1;
|
381 |
else key_size = 0;
|
382 |
|
383 |
}
|
384 |
*/
|
385 |
|
386 |
//lock_hash(ht);
|
387 |
hv = hash_value(ht, key, key_size, ht->num_buckets);
|
388 |
|
389 |
assert(hv < ht->num_buckets);
|
390 |
|
391 |
for (hr = ht->buckets[hv]; hr; hr = hr->next)
|
392 |
{
|
393 |
if (!hash_cmp(key, key_size, hr, 0)) break;
|
394 |
}
|
395 |
|
396 |
if (hr)
|
397 |
{
|
398 |
*r = hr->data;
|
399 |
//fprintf(stdout, "xdata=%p\n", hr->data);
|
400 |
//fprintf(stdout, "xdata2=%p\n", r);
|
401 |
//if (data_size) *data_size = hr->data_size;
|
402 |
}
|
403 |
|
404 |
//unlock_hash(ht);
|
405 |
|
406 |
return (hr ? 1 : 0);
|
407 |
}
|
408 |
|
409 |
/*
|
410 |
Assumes the key is a null-terminated string, returns the data, or NULL if not found. Note that it is possible for the data itself to be NULL
|
411 |
*/
|
412 |
extern void *
|
413 |
cfuhash_get(cfuhash_table_t *ht, const char *key) {
|
414 |
void *r = NULL;
|
415 |
int rv = 0;
|
416 |
rv = cfuhash_get_data(ht, (const void *)key, -1, &r, NULL);
|
417 |
if (rv) return r; /* found */
|
418 |
return NULL;
|
419 |
}
|
420 |
|
421 |
/* Returns 1 if an entry exists in the table for the given key, 0 otherwise */
|
422 |
extern int
|
423 |
cfuhash_exists_data(cfuhash_table_t *ht, long long key, size_t key_size) {
|
424 |
void *r = NULL;
|
425 |
int rv = cfuhash_get_data(ht, key, key_size, &r, NULL);
|
426 |
if (rv) return 1; /* found */
|
427 |
return 0;
|
428 |
}
|
429 |
|
430 |
/* Same as cfuhash_exists_data(), except assumes key is a null-terminated string */
|
431 |
extern int
|
432 |
cfuhash_exists(cfuhash_table_t *ht, const char *key) {
|
433 |
return cfuhash_exists_data(ht, (const void *)key, -1);
|
434 |
}
|
435 |
|
436 |
/*
|
437 |
Add the entry to the hash. If there is already an entry for the
|
438 |
given key, the old data value will be returned in r, and the return
|
439 |
value is zero. If a new entry is created for the key, the function
|
440 |
returns 1.
|
441 |
*/
|
442 |
extern int
|
443 |
cfuhash_put_data(cfuhash_table_t *ht, long long key, size_t key_size, long data,
|
444 |
size_t data_size, void *r) {
|
445 |
u_int hv = 0;
|
446 |
cfuhash_entry *he = NULL;
|
447 |
int added_an_entry = 0;
|
448 |
|
449 |
//printf("data in=%ld\n", data);
|
450 |
|
451 |
/*
|
452 |
if (key_size == (size_t)(-1)) {
|
453 |
if (key) key_size = strlen(key) + 1;
|
454 |
else key_size = 0;
|
455 |
}
|
456 |
if (data_size == (size_t)(-1)) {
|
457 |
if (data) data_size = strlen(data) + 1;
|
458 |
else data_size = 0;
|
459 |
|
460 |
}
|
461 |
*/
|
462 |
|
463 |
//lock_hash(ht);
|
464 |
|
465 |
hv = hash_value(ht, key, key_size, ht->num_buckets);
|
466 |
assert(hv < ht->num_buckets);
|
467 |
for (he = ht->buckets[hv]; he; he = he->next) {
|
468 |
if (!hash_cmp(key, key_size, he, 0)) break;
|
469 |
}
|
470 |
|
471 |
if (he) {
|
472 |
//if (r) r = he->data;
|
473 |
//if (ht->free_fn) {
|
474 |
// ht->free_fn(he->data);
|
475 |
// if (r) r = NULL; /* don't return a pointer to a free()'d location */
|
476 |
//}
|
477 |
he->data = data;
|
478 |
he->data_size = data_size;
|
479 |
} else {
|
480 |
hash_add_entry(ht, hv, key, key_size, data, data_size);
|
481 |
added_an_entry = 1;
|
482 |
}
|
483 |
|
484 |
//unlock_hash(ht);
|
485 |
|
486 |
if (added_an_entry && !(ht->flags & CFUHASH_FROZEN)) {
|
487 |
if ( (float)ht->entries/(float)ht->num_buckets > ht->high ) cfuhash_rehash(ht);
|
488 |
}
|
489 |
|
490 |
return added_an_entry;
|
491 |
}
|
492 |
|
493 |
/*
|
494 |
Same as cfuhash_put_data(), except the key is assumed to be a
|
495 |
null-terminated string, and the old value is returned if it existed,
|
496 |
otherwise NULL is returned.
|
497 |
*/
|
498 |
extern void *
|
499 |
cfuhash_put(cfuhash_table_t *ht, const char *key, void *data) {
|
500 |
void *r = NULL;
|
501 |
if (!cfuhash_put_data(ht, (const void *)key, -1, data, 0, &r)) {
|
502 |
return r;
|
503 |
}
|
504 |
return NULL;
|
505 |
}
|
506 |
|
507 |
extern void
|
508 |
cfuhash_clear(cfuhash_table_t *ht) {
|
509 |
cfuhash_entry *he = NULL;
|
510 |
cfuhash_entry *hep = NULL;
|
511 |
size_t i = 0;
|
512 |
|
513 |
lock_hash(ht);
|
514 |
for (i = 0; i < ht->num_buckets; i++) {
|
515 |
if ( (he = ht->buckets[i]) ) {
|
516 |
while (he) {
|
517 |
hep = he;
|
518 |
he = he->next;
|
519 |
//if (! (ht->flags & CFUHASH_NOCOPY_KEYS) ) free(hep->key);
|
520 |
//if (ht->free_fn) ht->free_fn(hep->data);
|
521 |
free(hep);
|
522 |
}
|
523 |
ht->buckets[i] = NULL;
|
524 |
}
|
525 |
}
|
526 |
ht->entries = 0;
|
527 |
|
528 |
unlock_hash(ht);
|
529 |
|
530 |
if ( !(ht->flags & CFUHASH_FROZEN) &&
|
531 |
!( (ht->flags & CFUHASH_FROZEN_UNTIL_GROWS) && !ht->resized_count) ) {
|
532 |
if ( (float)ht->entries/(float)ht->num_buckets < ht->low ) cfuhash_rehash(ht);
|
533 |
}
|
534 |
|
535 |
}
|
536 |
|
537 |
extern void *
|
538 |
cfuhash_delete_data(cfuhash_table_t *ht, const void *key, size_t key_size) {
|
539 |
u_int hv = 0;
|
540 |
cfuhash_entry *he = NULL;
|
541 |
cfuhash_entry *hep = NULL;
|
542 |
void *r = NULL;
|
543 |
|
544 |
if (key_size == (size_t)(-1)) key_size = strlen(key) + 1;
|
545 |
lock_hash(ht);
|
546 |
hv = hash_value(ht, key, key_size, ht->num_buckets);
|
547 |
|
548 |
for (he = ht->buckets[hv]; he; he = he->next) {
|
549 |
if (!hash_cmp(key, key_size, he, ht->flags & CFUHASH_IGNORE_CASE)) break;
|
550 |
hep = he;
|
551 |
}
|
552 |
|
553 |
if (he) {
|
554 |
r = he->data;
|
555 |
if (hep) hep->next = he->next;
|
556 |
else ht->buckets[hv] = he->next;
|
557 |
|
558 |
ht->entries--;
|
559 |
if (! (ht->flags & CFUHASH_NOCOPY_KEYS) ) free(he->key);
|
560 |
if (ht->free_fn) {
|
561 |
ht->free_fn(he->data);
|
562 |
r = NULL; /* don't return a pointer to a free()'d location */
|
563 |
}
|
564 |
free(he);
|
565 |
}
|
566 |
|
567 |
unlock_hash(ht);
|
568 |
|
569 |
if (he && !(ht->flags & CFUHASH_FROZEN) &&
|
570 |
!( (ht->flags & CFUHASH_FROZEN_UNTIL_GROWS) && !ht->resized_count) ) {
|
571 |
if ( (float)ht->entries/(float)ht->num_buckets < ht->low ) cfuhash_rehash(ht);
|
572 |
}
|
573 |
|
574 |
|
575 |
return r;
|
576 |
}
|
577 |
|
578 |
extern void *
|
579 |
cfuhash_delete(cfuhash_table_t *ht, const char *key) {
|
580 |
return cfuhash_delete_data(ht, key, -1);
|
581 |
}
|
582 |
|
583 |
extern void **
|
584 |
cfuhash_keys_data(cfuhash_table_t *ht, size_t *num_keys, size_t **key_sizes, int fast) {
|
585 |
size_t *key_lengths = NULL;
|
586 |
void **keys = NULL;
|
587 |
cfuhash_entry *he = NULL;
|
588 |
size_t bucket = 0;
|
589 |
size_t entry_index = 0;
|
590 |
size_t key_count = 0;
|
591 |
|
592 |
if (!ht) {
|
593 |
*key_sizes = NULL;
|
594 |
*num_keys = 0;
|
595 |
return NULL;
|
596 |
}
|
597 |
|
598 |
if (! (ht->flags & CFUHASH_NO_LOCKING) ) lock_hash(ht);
|
599 |
|
600 |
if (key_sizes) key_lengths = (size_t *)calloc(ht->entries, sizeof(size_t));
|
601 |
keys = (void **)calloc(ht->entries, sizeof(void *));
|
602 |
|
603 |
for (bucket = 0; bucket < ht->num_buckets; bucket++) {
|
604 |
if ( (he = ht->buckets[bucket]) ) {
|
605 |
for (; he; he = he->next, entry_index++) {
|
606 |
if (entry_index >= ht->entries) break; /* this should never happen */
|
607 |
|
608 |
if (fast) {
|
609 |
keys[entry_index] = he->key;
|
610 |
} else {
|
611 |
keys[entry_index] = (void *)calloc(he->key_size, 1);
|
612 |
memcpy(keys[entry_index], he->key, he->key_size);
|
613 |
}
|
614 |
key_count++;
|
615 |
|
616 |
if (key_lengths) key_lengths[entry_index] = he->key_size;
|
617 |
}
|
618 |
}
|
619 |
}
|
620 |
|
621 |
if (! (ht->flags & CFUHASH_NO_LOCKING) ) unlock_hash(ht);
|
622 |
|
623 |
if (key_sizes) *key_sizes = key_lengths;
|
624 |
*num_keys = key_count;
|
625 |
|
626 |
return keys;
|
627 |
}
|
628 |
|
629 |
extern void **
|
630 |
cfuhash_keys(cfuhash_table_t *ht, size_t *num_keys, int fast) {
|
631 |
return cfuhash_keys_data(ht, num_keys, NULL, fast);
|
632 |
}
|
633 |
|
634 |
extern int
|
635 |
cfuhash_each_data(cfuhash_table_t *ht, void **key, size_t *key_size, void **data,
|
636 |
size_t *data_size) {
|
637 |
|
638 |
ht->each_bucket_index = -1;
|
639 |
ht->each_chain_entry = NULL;
|
640 |
|
641 |
return cfuhash_next_data(ht, key, key_size, data, data_size);
|
642 |
}
|
643 |
|
644 |
extern int
|
645 |
cfuhash_next_data(cfuhash_table_t *ht, void **key, size_t *key_size, void **data,
|
646 |
size_t *data_size) {
|
647 |
|
648 |
if (ht->each_chain_entry && ht->each_chain_entry->next) {
|
649 |
ht->each_chain_entry = ht->each_chain_entry->next;
|
650 |
} else {
|
651 |
ht->each_chain_entry = NULL;
|
652 |
ht->each_bucket_index++;
|
653 |
for (; ht->each_bucket_index < ht->num_buckets; ht->each_bucket_index++) {
|
654 |
if (ht->buckets[ht->each_bucket_index]) {
|
655 |
ht->each_chain_entry = ht->buckets[ht->each_bucket_index];
|
656 |
break;
|
657 |
}
|
658 |
}
|
659 |
}
|
660 |
|
661 |
if (ht->each_chain_entry) {
|
662 |
*key = ht->each_chain_entry->key;
|
663 |
*key_size = ht->each_chain_entry->key_size;
|
664 |
*data = ht->each_chain_entry->data;
|
665 |
if (data_size) *data_size = ht->each_chain_entry->data_size;
|
666 |
return 1;
|
667 |
}
|
668 |
|
669 |
return 0;
|
670 |
}
|
671 |
|
672 |
static void
|
673 |
_cfuhash_destroy_entry(cfuhash_table_t *ht, cfuhash_entry *he, cfuhash_free_fn_t ff) {
|
674 |
|
675 |
/*
|
676 |
if (ff) {
|
677 |
ff(he->data);
|
678 |
} else {
|
679 |
if (ht->free_fn) ht->free_fn(he->data);
|
680 |
else {
|
681 |
if (ht->flags & CFUHASH_FREE_DATA) free(he->data);
|
682 |
}
|
683 |
}
|
684 |
if ( !(ht->flags & CFUHASH_NOCOPY_KEYS) ) free(he->key);
|
685 |
*/
|
686 |
free(he);
|
687 |
}
|
688 |
|
689 |
extern size_t
|
690 |
cfuhash_foreach_remove(cfuhash_table_t *ht, cfuhash_remove_fn_t r_fn, cfuhash_free_fn_t ff,
|
691 |
void *arg) {
|
692 |
cfuhash_entry *entry = NULL;
|
693 |
cfuhash_entry *prev = NULL;
|
694 |
size_t hv = 0;
|
695 |
size_t num_removed = 0;
|
696 |
cfuhash_entry **buckets = NULL;
|
697 |
size_t num_buckets = 0;
|
698 |
|
699 |
if (!ht) return 0;
|
700 |
|
701 |
lock_hash(ht);
|
702 |
|
703 |
buckets = ht->buckets;
|
704 |
num_buckets = ht->num_buckets;
|
705 |
for (hv = 0; hv < num_buckets; hv++) {
|
706 |
entry = buckets[hv];
|
707 |
if (!entry) continue;
|
708 |
prev = NULL;
|
709 |
|
710 |
while (entry) {
|
711 |
if (r_fn(entry->key, entry->key_size, entry->data, entry->data_size, arg)) {
|
712 |
num_removed++;
|
713 |
if (prev) {
|
714 |
prev->next = entry->next;
|
715 |
_cfuhash_destroy_entry(ht, entry, ff);
|
716 |
entry = prev->next;
|
717 |
} else {
|
718 |
buckets[hv] = entry->next;
|
719 |
_cfuhash_destroy_entry(ht, entry, NULL);
|
720 |
entry = buckets[hv];
|
721 |
}
|
722 |
} else {
|
723 |
prev = entry;
|
724 |
entry = entry->next;
|
725 |
}
|
726 |
}
|
727 |
}
|
728 |
|
729 |
unlock_hash(ht);
|
730 |
|
731 |
return num_removed;
|
732 |
}
|
733 |
|
734 |
extern size_t
|
735 |
cfuhash_foreach(cfuhash_table_t *ht, cfuhash_foreach_fn_t fe_fn, void *arg) {
|
736 |
cfuhash_entry *entry = NULL;
|
737 |
size_t hv = 0;
|
738 |
size_t num_accessed = 0;
|
739 |
cfuhash_entry **buckets = NULL;
|
740 |
size_t num_buckets = 0;
|
741 |
int rv = 0;
|
742 |
|
743 |
if (!ht) return 0;
|
744 |
|
745 |
lock_hash(ht);
|
746 |
|
747 |
buckets = ht->buckets;
|
748 |
num_buckets = ht->num_buckets;
|
749 |
for (hv = 0; hv < num_buckets && !rv; hv++) {
|
750 |
entry = buckets[hv];
|
751 |
|
752 |
for (; entry && !rv; entry = entry->next) {
|
753 |
num_accessed++;
|
754 |
rv = fe_fn(entry->key, entry->key_size, entry->data, entry->data_size, arg);
|
755 |
}
|
756 |
}
|
757 |
|
758 |
unlock_hash(ht);
|
759 |
|
760 |
return num_accessed;
|
761 |
}
|
762 |
|
763 |
extern int
|
764 |
cfuhash_each(cfuhash_table_t *ht, char **key, void **data) {
|
765 |
size_t key_size = 0;
|
766 |
return cfuhash_each_data(ht, (void **)key, &key_size, data, NULL);
|
767 |
}
|
768 |
|
769 |
extern int
|
770 |
cfuhash_next(cfuhash_table_t *ht, char **key, void **data) {
|
771 |
size_t key_size = 0;
|
772 |
return cfuhash_next_data(ht, (void **)key, &key_size, data, NULL);
|
773 |
}
|
774 |
|
775 |
extern int
|
776 |
cfuhash_destroy_with_free_fn(cfuhash_table_t *ht, cfuhash_free_fn_t ff) {
|
777 |
size_t i;
|
778 |
if (!ht) return 0;
|
779 |
|
780 |
lock_hash(ht);
|
781 |
for (i = 0; i < ht->num_buckets; i++) {
|
782 |
if (ht->buckets[i]) {
|
783 |
cfuhash_entry *he = ht->buckets[i];
|
784 |
while (he) {
|
785 |
cfuhash_entry *hn = he->next;
|
786 |
_cfuhash_destroy_entry(ht, he, ff);
|
787 |
he = hn;
|
788 |
}
|
789 |
}
|
790 |
}
|
791 |
free(ht->buckets);
|
792 |
unlock_hash(ht);
|
793 |
pthread_mutex_destroy(&ht->mutex);
|
794 |
free(ht);
|
795 |
|
796 |
return 1;
|
797 |
}
|
798 |
|
799 |
extern int
|
800 |
cfuhash_destroy(cfuhash_table_t *ht) {
|
801 |
return cfuhash_destroy_with_free_fn(ht, NULL);
|
802 |
}
|
803 |
|
804 |
typedef struct _pretty_print_arg {
|
805 |
size_t count;
|
806 |
FILE *fp;
|
807 |
} _pretty_print_arg;
|
808 |
|
809 |
static int
|
810 |
_pretty_print_foreach(void *key, size_t key_size, void *data, size_t data_size, void *arg) {
|
811 |
_pretty_print_arg *parg = (_pretty_print_arg *)arg;
|
812 |
key_size = key_size;
|
813 |
data_size = data_size;
|
814 |
parg->count += fprintf(parg->fp, "\t\"%s\" => \"%s\",\n", (char *)key, (char *)data);
|
815 |
return 0;
|
816 |
}
|
817 |
|
818 |
extern int
|
819 |
cfuhash_pretty_print(cfuhash_table_t *ht, FILE *fp) {
|
820 |
int rv = 0;
|
821 |
_pretty_print_arg parg;
|
822 |
|
823 |
parg.fp = fp;
|
824 |
parg.count = 0;
|
825 |
|
826 |
rv += fprintf(fp, "{\n");
|
827 |
|
828 |
cfuhash_foreach(ht, _pretty_print_foreach, (void *)&parg);
|
829 |
rv += parg.count;
|
830 |
|
831 |
rv += fprintf(fp, "}\n");
|
832 |
|
833 |
return rv;
|
834 |
}
|
835 |
|
836 |
extern int
|
837 |
cfuhash_rehash(cfuhash_table_t *ht) {
|
838 |
size_t new_size, i;
|
839 |
cfuhash_entry **new_buckets = NULL;
|
840 |
|
841 |
lock_hash(ht);
|
842 |
new_size = hash_size(ht->entries * 2 / (ht->high + ht->low));
|
843 |
if (new_size == ht->num_buckets) {
|
844 |
unlock_hash(ht);
|
845 |
return 0;
|
846 |
}
|
847 |
new_buckets = (cfuhash_entry **)calloc(new_size, sizeof(cfuhash_entry *));
|
848 |
|
849 |
for (i = 0; i < ht->num_buckets; i++) {
|
850 |
cfuhash_entry *he = ht->buckets[i];
|
851 |
while (he) {
|
852 |
cfuhash_entry *nhe = he->next;
|
853 |
u_int hv = hash_value(ht, he->key, he->key_size, new_size);
|
854 |
he->next = new_buckets[hv];
|
855 |
new_buckets[hv] = he;
|
856 |
he = nhe;
|
857 |
}
|
858 |
}
|
859 |
|
860 |
ht->num_buckets = new_size;
|
861 |
free(ht->buckets);
|
862 |
ht->buckets = new_buckets;
|
863 |
ht->resized_count++;
|
864 |
|
865 |
unlock_hash(ht);
|
866 |
return 1;
|
867 |
}
|
868 |
|
869 |
extern size_t
|
870 |
cfuhash_num_entries(cfuhash_table_t *ht) {
|
871 |
if (!ht) return 0;
|
872 |
return ht->entries;
|
873 |
}
|
874 |
|
875 |
extern size_t
|
876 |
cfuhash_num_buckets(cfuhash_table_t *ht) {
|
877 |
if (!ht) return 0;
|
878 |
return ht->num_buckets;
|
879 |
}
|
880 |
|
881 |
extern size_t
|
882 |
cfuhash_num_buckets_used(cfuhash_table_t *ht) {
|
883 |
size_t i = 0;
|
884 |
size_t count = 0;
|
885 |
|
886 |
if (!ht) return 0;
|
887 |
|
888 |
lock_hash(ht);
|
889 |
|
890 |
for (i = 0; i < ht->num_buckets; i++) {
|
891 |
if (ht->buckets[i]) count++;
|
892 |
}
|
893 |
unlock_hash(ht);
|
894 |
return count;
|
895 |
}
|
896 |
|
897 |
extern char *
|
898 |
cfuhash_bencode_strings(cfuhash_table_t *ht) {
|
899 |
cfustring_t *bencoded = cfustring_new_with_initial_size(16);
|
900 |
char **keys = NULL;
|
901 |
size_t num_keys = 0;
|
902 |
size_t i = 0;
|
903 |
char len_str[32];
|
904 |
char *rv = NULL;
|
905 |
|
906 |
cfustring_append(bencoded, "d");
|
907 |
|
908 |
keys = (char **)cfuhash_keys(ht, &num_keys, 0);
|
909 |
for (i = 0; i < num_keys; i++) {
|
910 |
char *val = NULL;
|
911 |
|
912 |
snprintf(len_str, 32, "%d:", (keys[i] ? strlen(keys[i]) : 0));
|
913 |
cfustring_append(bencoded, len_str);
|
914 |
cfustring_append(bencoded, keys[i]);
|
915 |
|
916 |
val = (char *)cfuhash_get(ht, keys[i]);
|
917 |
snprintf(len_str, 32, "%d:", (val ? strlen(val) : 0));
|
918 |
cfustring_append(bencoded, len_str);
|
919 |
cfustring_append(bencoded, val);
|
920 |
|
921 |
free(keys[i]);
|
922 |
}
|
923 |
free(keys);
|
924 |
|
925 |
cfustring_append(bencoded, "e");
|
926 |
rv = cfustring_get_buffer_copy(bencoded);
|
927 |
cfustring_destroy(bencoded);
|
928 |
|
929 |
return rv;
|
930 |
}
|