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