/[zanavi_public1]/navit/navit/maptool/libcfu-0.03-zanavi/src/cfuhash.c
ZANavi

Contents of /navit/navit/maptool/libcfu-0.03-zanavi/src/cfuhash.c

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki