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