/[zanavi_public1]/navit/navit/maptool/cfuhash.c
ZANavi

Contents of /navit/navit/maptool/cfuhash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (6 years, 7 months ago) by zoff99
File MIME type: text/plain
File size: 21798 byte(s)
new map version, lots of fixes and experimental new features
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 }

   
Visit the ZANavi Wiki