File: | bld/../dhash/dhash.c |
Location: | line 892, column 10 |
Description: | Although the value stored to 'error' is used in the enclosing expression, the value is never actually read from 'error' |
1 | /* |
2 | Authors: |
3 | John Dennis <jdennis.redhat.com> |
4 | Esmond Pitt <ejp@ausmelb.oz.AU> |
5 | |
6 | This implementation was based on a 3/7/1989 public domain submission |
7 | to comp.sources.misc by Esmond Pitt <ejp@ausmelb.oz.AU>. |
8 | |
9 | Copyright (C) 2009 Red Hat |
10 | |
11 | This program is free software; you can redistribute it and/or modify |
12 | it under the terms of the GNU Lesser General Public License as published by |
13 | the Free Software Foundation; either version 3 of the License, or |
14 | (at your option) any later version. |
15 | |
16 | This program is distributed in the hope that it will be useful, |
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
19 | GNU Lesser General Public License for more details. |
20 | |
21 | You should have received a copy of the GNU Lesser General Public License |
22 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
23 | */ |
24 | |
25 | /*****************************************************************************/ |
26 | /******************************** Documentation ******************************/ |
27 | /*****************************************************************************/ |
28 | |
29 | /* |
30 | * See documentation in corresponding header file dhash.h. |
31 | * |
32 | * Compilation controls: |
33 | * DEBUG controls some informative traces, mainly for debugging. |
34 | * HASH_STATISTICS causes hash_accesses and hash_collisions to be maintained; |
35 | * when combined with DEBUG, these are displayed by hash_destroy(). |
36 | * |
37 | */ |
38 | |
39 | /*****************************************************************************/ |
40 | /******************************* Include Files *******************************/ |
41 | /*****************************************************************************/ |
42 | |
43 | #include "config.h" |
44 | #include <stdio.h> |
45 | #include <string.h> |
46 | #include <stdlib.h> |
47 | #include <errno(*__errno_location ()).h> |
48 | #include "dhash.h" |
49 | |
50 | /*****************************************************************************/ |
51 | /****************************** Internal Defines *****************************/ |
52 | /*****************************************************************************/ |
53 | |
54 | #define PRIME_137 37 |
55 | #define PRIME_21048583 1048583 |
56 | |
57 | #ifndef MIN |
58 | #define MIN(a,b)(((a) < (b)) ? (a) : (b)) (((a) < (b)) ? (a) : (b)) |
59 | #endif |
60 | |
61 | #ifndef MAX |
62 | #define MAX(a,b)(((a) > (b)) ? (a) : (b)) (((a) > (b)) ? (a) : (b)) |
63 | #endif |
64 | |
65 | #define halloc(table, size)table->halloc(size, table->halloc_pvt) table->halloc(size, table->halloc_pvt)size->halloc(table->halloc_pvt, size->halloc_pvt) |
66 | #define hfree(table, ptr)table->hfree(ptr, table->halloc_pvt) table->hfree(ptr, table->halloc_pvt)ptr->hfree(table->halloc_pvt, ptr->halloc_pvt) |
67 | #define hdelete_callback(table, type, entry)do { if (table->delete_callback) { table->delete_callback (entry, type, table->delete_pvt); } } while(0) do { \ |
68 | if (table->delete_callback) { \ |
69 | table->delete_callback(entry, type, table->delete_pvt); \ |
70 | } \ |
71 | } while(0) |
72 | |
73 | /*****************************************************************************/ |
74 | /************************** Internal Type Definitions ************************/ |
75 | /*****************************************************************************/ |
76 | |
77 | typedef struct element_t { |
78 | hash_entry_t entry; |
79 | struct element_t *next; |
80 | } element_t, *segment_t; |
81 | |
82 | |
83 | struct hash_table_str { |
84 | unsigned long p; /* Next bucket to be split */ |
85 | unsigned long maxp; /* upper bound on p during expansion */ |
86 | unsigned long entry_count; /* current # entries */ |
87 | unsigned long bucket_count; /* current # buckets */ |
88 | unsigned long segment_count; /* current # segments */ |
89 | unsigned long min_load_factor; |
90 | unsigned long max_load_factor; |
91 | unsigned long directory_size; |
92 | unsigned int directory_size_shift; |
93 | unsigned long segment_size; |
94 | unsigned int segment_size_shift; |
95 | hash_delete_callback *delete_callback; |
96 | void *delete_pvt; |
97 | hash_alloc_func *halloc; |
98 | hash_free_func *hfree; |
99 | void *halloc_pvt; |
100 | segment_t **directory; |
101 | #ifdef HASH_STATISTICS |
102 | hash_statistics_t statistics; |
103 | #endif |
104 | |
105 | }; |
106 | |
107 | typedef unsigned long address_t; |
108 | |
109 | typedef struct hash_keys_callback_data_t { |
110 | unsigned long index; |
111 | hash_key_t *keys; |
112 | } hash_keys_callback_data_t; |
113 | |
114 | typedef struct hash_values_callback_data_t { |
115 | unsigned long index; |
116 | hash_value_t *values; |
117 | } hash_values_callback_data_t; |
118 | |
119 | struct _hash_iter_context_t { |
120 | struct hash_iter_context_t iter; |
121 | hash_table_t *table; |
122 | unsigned long i, j; |
123 | segment_t *s; |
124 | element_t *p; |
125 | }; |
126 | |
127 | /*****************************************************************************/ |
128 | /********************** External Function Declarations *********************/ |
129 | /*****************************************************************************/ |
130 | |
131 | /*****************************************************************************/ |
132 | /********************** Internal Function Declarations *********************/ |
133 | /*****************************************************************************/ |
134 | |
135 | static address_t convert_key(hash_key_t *key); |
136 | static address_t hash(hash_table_t *table, hash_key_t *key); |
137 | static bool_Bool key_equal(hash_key_t *a, hash_key_t *b); |
138 | static int contract_table(hash_table_t *table); |
139 | static int expand_table(hash_table_t *table); |
140 | static hash_entry_t *hash_iter_next(struct hash_iter_context_t *iter); |
141 | |
142 | /*****************************************************************************/ |
143 | /************************* External Global Variables ***********************/ |
144 | /*****************************************************************************/ |
145 | |
146 | /*****************************************************************************/ |
147 | /************************* Internal Global Variables ***********************/ |
148 | /*****************************************************************************/ |
149 | |
150 | #if DEBUG |
151 | int debug_level = 1; |
152 | #endif |
153 | |
154 | /*****************************************************************************/ |
155 | /*************************** Internal Functions ****************************/ |
156 | /*****************************************************************************/ |
157 | |
158 | static void *sys_malloc_wrapper(size_t size, void *pvt) |
159 | { |
160 | return malloc(size); |
161 | } |
162 | |
163 | static void sys_free_wrapper(void *ptr, void *pvt) |
164 | { |
165 | return free(ptr); |
166 | } |
167 | |
168 | static address_t convert_key(hash_key_t *key) |
169 | { |
170 | address_t h; |
171 | unsigned char *k; |
172 | |
173 | switch(key->type) { |
174 | case HASH_KEY_ULONG: |
175 | h = key->ul; |
176 | break; |
177 | case HASH_KEY_STRING: |
178 | /* Convert string to integer */ |
179 | for (h = 0, k = (unsigned char *) key->str; *k; k++) |
180 | h = h * PRIME_137 ^ (*k - ' '); |
181 | break; |
182 | default: |
183 | h = key->ul; |
184 | break; |
185 | } |
186 | return h; |
187 | } |
188 | |
189 | static address_t hash(hash_table_t *table, hash_key_t *key) |
190 | { |
191 | address_t h, address; |
192 | |
193 | h = convert_key(key); |
194 | h %= PRIME_21048583; |
195 | address = h & (table->maxp-1); /* h % maxp */ |
196 | if (address < table->p) |
197 | address = h & ((table->maxp << 1)-1); /* h % (2*table->maxp) */ |
198 | |
199 | return address; |
200 | } |
201 | |
202 | static bool_Bool is_valid_key_type(hash_key_enum key_type) |
203 | { |
204 | switch(key_type) { |
205 | case HASH_KEY_ULONG: |
206 | case HASH_KEY_STRING: |
207 | return true1; |
208 | default: |
209 | return false0; |
210 | } |
211 | } |
212 | |
213 | static bool_Bool is_valid_value_type(hash_value_enum value_type) |
214 | { |
215 | switch(value_type) { |
216 | case HASH_VALUE_UNDEF: |
217 | case HASH_VALUE_PTR: |
218 | case HASH_VALUE_INT: |
219 | case HASH_VALUE_UINT: |
220 | case HASH_VALUE_LONG: |
221 | case HASH_VALUE_ULONG: |
222 | case HASH_VALUE_FLOAT: |
223 | case HASH_VALUE_DOUBLE: |
224 | return true1; |
225 | default: |
226 | return false0; |
227 | } |
228 | } |
229 | |
230 | static bool_Bool key_equal(hash_key_t *a, hash_key_t *b) |
231 | { |
232 | if (a->type != b->type) return false0; |
233 | |
234 | switch(a->type) { |
235 | case HASH_KEY_ULONG: |
236 | return (a->ul == b->ul); |
237 | case HASH_KEY_STRING: |
238 | return (strcmp(a->str, b->str) == 0); |
239 | } |
240 | return false0; |
241 | } |
242 | |
243 | |
244 | static int expand_table(hash_table_t *table) |
245 | { |
246 | address_t new_address; |
247 | unsigned long old_segment_index, new_segment_index; |
248 | unsigned long old_segment_dir, new_segment_dir; |
249 | segment_t *old_segment, *new_segment; |
250 | element_t *current, **previous, **last_of_new; |
251 | |
252 | if (table->bucket_count < (table->directory_size << table->segment_size_shift)) { |
253 | #ifdef DEBUG |
254 | if (debug_level >= 2) |
255 | fprintf(stderrstderr, "expand_table on entry: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", |
256 | table->bucket_count, table->segment_count, table->p, table->maxp); |
257 | #endif |
258 | #ifdef HASH_STATISTICS |
259 | table->statistics.table_expansions++; |
260 | #endif |
261 | |
262 | /* |
263 | * Locate the bucket to be split |
264 | */ |
265 | old_segment_dir = table->p >> table->segment_size_shift; |
266 | old_segment = table->directory[old_segment_dir]; |
267 | old_segment_index = table->p & (table->segment_size-1); /* p % segment_size */ |
268 | /* |
269 | * Expand address space; if necessary create a new segment |
270 | */ |
271 | new_address = table->maxp + table->p; |
272 | new_segment_dir = new_address >> table->segment_size_shift; |
273 | new_segment_index = new_address & (table->segment_size-1); /* new_address % segment_size */ |
274 | if (new_segment_index == 0) { |
275 | table->directory[new_segment_dir] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t))table->halloc(table->segment_size * sizeof(segment_t), table ->halloc_pvt); |
276 | if (table->directory[new_segment_dir] == NULL((void*)0)) { |
277 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
278 | } |
279 | memset(table->directory[new_segment_dir], 0, table->segment_size * sizeof(segment_t)); |
280 | table->segment_count++; |
281 | } |
282 | new_segment = table->directory[new_segment_dir]; |
283 | /* |
284 | * Adjust state variables |
285 | */ |
286 | table->p++; |
287 | if (table->p == table->maxp) { |
288 | table->maxp <<= 1; /* table->maxp *= 2 */ |
289 | table->p = 0; |
290 | } |
291 | table->bucket_count++; |
292 | /* |
293 | * Relocate records to the new bucket |
294 | */ |
295 | previous = &old_segment[old_segment_index]; |
296 | current = *previous; |
297 | last_of_new = &new_segment[new_segment_index]; |
298 | *last_of_new = NULL((void*)0); |
299 | while (current != NULL((void*)0)) { |
300 | if (hash(table, ¤t->entry.key) == new_address) { |
301 | /* |
302 | * Attach it to the end of the new chain |
303 | */ |
304 | *last_of_new = current; |
305 | /* |
306 | * Remove it from old chain |
307 | */ |
308 | *previous = current->next; |
309 | last_of_new = ¤t->next; |
310 | current = current->next; |
311 | *last_of_new = NULL((void*)0); |
312 | } else { |
313 | /* |
314 | * leave it on the old chain |
315 | */ |
316 | previous = ¤t->next; |
317 | current = current->next; |
318 | } |
319 | } |
320 | #ifdef DEBUG |
321 | if (debug_level >= 2) |
322 | fprintf(stderrstderr, "expand_table on exit: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", |
323 | table->bucket_count, table->segment_count, table->p, table->maxp); |
324 | #endif |
325 | } |
326 | return HASH_SUCCESS0; |
327 | } |
328 | |
329 | static int contract_table(hash_table_t *table) |
330 | { |
331 | address_t new_address, old_address; |
332 | unsigned long old_segment_index, new_segment_index; |
333 | unsigned long old_segment_dir, new_segment_dir; |
334 | segment_t *old_segment, *new_segment; |
335 | element_t *current; |
336 | |
337 | if ((table->bucket_count > table->segment_size) && (table->segment_count > 1)) { |
338 | #ifdef DEBUG |
339 | if (debug_level >= 2) |
340 | fprintf(stderrstderr, "contract_table on entry: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", |
341 | table->bucket_count, table->segment_count, table->p, table->maxp); |
342 | #endif |
343 | |
344 | #ifdef HASH_STATISTICS |
345 | table->statistics.table_contractions++; |
346 | #endif |
347 | /* |
348 | * Locate the bucket to be merged with the last bucket |
349 | */ |
350 | old_address = table->bucket_count - 1; |
351 | old_segment_dir = old_address >> table->segment_size_shift; |
352 | old_segment = table->directory[old_segment_dir]; |
353 | old_segment_index = old_address & (table->segment_size-1); /* old_address % segment_size */ |
354 | |
355 | /* |
356 | * Adjust state variables |
357 | */ |
358 | if (table->p > 0) { |
359 | table->p--; |
360 | } else { |
361 | table->maxp >>= 1; |
362 | table->p = table->maxp - 1; |
363 | } |
364 | table->bucket_count--; |
365 | |
366 | /* |
367 | * Find the last bucket to merge back |
368 | */ |
369 | if((current = old_segment[old_segment_index]) != NULL((void*)0)) { |
370 | new_address = hash(table, &old_segment[old_segment_index]->entry.key); |
371 | new_segment_dir = new_address >> table->segment_size_shift; |
372 | new_segment_index = new_address & (table->segment_size-1); /* new_address % segment_size */ |
373 | new_segment = table->directory[new_segment_dir]; |
374 | |
375 | /* |
376 | * Relocate records to the new bucket by splicing the two chains |
377 | * together by inserting the old chain at the head of the new chain. |
378 | * First find the end of the old chain, then set its next pointer to |
379 | * point to the head of the new chain, set the head of the new chain to |
380 | * point to the old chain, then finally set the head of the old chain to |
381 | * NULL. |
382 | */ |
383 | |
384 | while (current->next != NULL((void*)0)) { |
385 | current = current->next; |
386 | } |
387 | |
388 | current->next = new_segment[new_segment_index]; |
389 | new_segment[new_segment_index] = old_segment[old_segment_index]; |
390 | old_segment[old_segment_index] = NULL((void*)0); |
391 | } |
392 | /* |
393 | * If we have removed the last of the chains in this segment then free the |
394 | * segment since its no longer in use. |
395 | */ |
396 | if (old_segment_index == 0) { |
397 | table->segment_count--; |
398 | hfree(table, table->directory[old_segment_dir])table->hfree(table->directory[old_segment_dir], table-> halloc_pvt); |
399 | } |
400 | |
401 | #ifdef DEBUG |
402 | if (debug_level >= 2) |
403 | fprintf(stderrstderr, "contract_table on exit: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n", |
404 | table->bucket_count, table->segment_count, table->p, table->maxp); |
405 | #endif |
406 | |
407 | } |
408 | return HASH_SUCCESS0; |
409 | } |
410 | |
411 | static int lookup(hash_table_t *table, hash_key_t *key, element_t **element_arg, segment_t **chain_arg) |
412 | { |
413 | address_t h; |
414 | segment_t *current_segment; |
415 | unsigned long segment_index, segment_dir; |
416 | segment_t *chain, element; |
417 | |
418 | *element_arg = NULL((void*)0); |
419 | *chain_arg = NULL((void*)0); |
420 | |
421 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
422 | |
423 | #ifdef HASH_STATISTICS |
424 | table->statistics.hash_accesses++; |
425 | #endif |
426 | h = hash(table, key); |
427 | segment_dir = h >> table->segment_size_shift; |
428 | segment_index = h & (table->segment_size-1); /* h % segment_size */ |
429 | /* |
430 | * valid segment ensured by hash() |
431 | */ |
432 | current_segment = table->directory[segment_dir]; |
433 | |
434 | #ifdef DEBUG |
435 | if (debug_level >= 3) |
436 | fprintf(stderrstderr, "lookup: h=%lu, segment_dir=%lu, segment_index=%lu current_segment=%p\n", |
437 | h, segment_dir, segment_index, current_segment); |
438 | #endif |
439 | |
440 | if (current_segment == NULL((void*)0)) return EFAULT14; |
441 | chain = ¤t_segment[segment_index]; |
442 | element = *chain; |
443 | /* |
444 | * Follow collision chain |
445 | */ |
446 | while (element != NULL((void*)0) && !key_equal(&element->entry.key, key)) { |
447 | chain = &element->next; |
448 | element = *chain; |
449 | #ifdef HASH_STATISTICS |
450 | table->statistics.hash_collisions++; |
451 | #endif |
452 | } |
453 | *element_arg = element; |
454 | *chain_arg = chain; |
455 | |
456 | return HASH_SUCCESS0; |
457 | } |
458 | |
459 | static bool_Bool hash_keys_callback(hash_entry_t *item, void *user_data) |
460 | { |
461 | hash_keys_callback_data_t *data = (hash_keys_callback_data_t *)user_data; |
462 | |
463 | data->keys[data->index++] = item->key; |
464 | return true1; |
465 | } |
466 | |
467 | static bool_Bool hash_values_callback(hash_entry_t *item, void *user_data) |
468 | { |
469 | hash_values_callback_data_t *data = (hash_values_callback_data_t *)user_data; |
470 | |
471 | data->values[data->index++] = item->value; |
472 | return true1; |
473 | } |
474 | |
475 | /*****************************************************************************/ |
476 | /**************************** Exported Functions ***************************/ |
477 | /*****************************************************************************/ |
478 | |
479 | const char* hash_error_string(int error) |
480 | { |
481 | switch(error) { |
482 | case HASH_SUCCESS0: return "Success"; |
483 | case HASH_ERROR_BAD_KEY_TYPE(-2000 + 1): return "Bad key type"; |
484 | case HASH_ERROR_BAD_VALUE_TYPE(-2000 + 2): return "Bad value type"; |
485 | case HASH_ERROR_NO_MEMORY(-2000 + 3): return "No memory"; |
486 | case HASH_ERROR_KEY_NOT_FOUND(-2000 + 4): return "Key not found"; |
487 | case HASH_ERROR_BAD_TABLE(-2000 + 5): return "Bad table"; |
488 | } |
489 | return NULL((void*)0); |
490 | } |
491 | |
492 | |
493 | int hash_create(unsigned long count, hash_table_t **tbl, |
494 | hash_delete_callback *delete_callback, |
495 | void *delete_private_data) |
496 | { |
497 | return hash_create_ex(count, tbl, 0, 0, 0, 0, |
498 | NULL((void*)0), NULL((void*)0), NULL((void*)0), |
499 | delete_callback, |
500 | delete_private_data); |
501 | } |
502 | |
503 | int hash_create_ex(unsigned long count, hash_table_t **tbl, |
504 | unsigned int directory_bits, |
505 | unsigned int segment_bits, |
506 | unsigned long min_load_factor, |
507 | unsigned long max_load_factor, |
508 | hash_alloc_func *alloc_func, |
509 | hash_free_func *free_func, |
510 | void *alloc_private_data, |
511 | hash_delete_callback *delete_callback, |
512 | void *delete_private_data) { |
513 | unsigned long i; |
514 | unsigned int n_addr_bits, requested_bits; |
515 | unsigned int requested_directory_bits; |
516 | unsigned int requested_segment_bits; |
517 | address_t addr; |
518 | hash_table_t *table = NULL((void*)0); |
519 | |
520 | /* Initialize to NULL in case of an early return due to an error */ |
521 | *tbl = NULL((void*)0); |
522 | |
523 | if (alloc_func == NULL((void*)0)) alloc_func = sys_malloc_wrapper; |
524 | if (free_func == NULL((void*)0)) free_func = sys_free_wrapper; |
525 | |
526 | /* Compute directory and segment parameters */ |
527 | |
528 | /* compute power of 2 >= count; it's the number of requested buckets */ |
529 | if (count > 1) { |
530 | for (requested_bits = 0; (1 << requested_bits) < count; requested_bits++); |
531 | } else { |
532 | requested_bits = 1; |
533 | } |
534 | |
535 | /* |
536 | * If caller didn't specify directory & segment allocation then |
537 | * compute it from the requested count. |
538 | */ |
539 | if (directory_bits == 0 || segment_bits == 0) { |
540 | /* Equally divide buckets between the directory and segments */ |
541 | requested_directory_bits = MAX(requested_bits >> 1, 1)(((requested_bits >> 1) > (1)) ? (requested_bits >> 1) : (1)); |
542 | requested_segment_bits = MAX(requested_bits - requested_directory_bits, 1)(((requested_bits - requested_directory_bits) > (1)) ? (requested_bits - requested_directory_bits) : (1)); |
543 | |
544 | /* If the requested count wasn't specified pick a default */ |
545 | if (count == 0) { |
546 | directory_bits = MAX(requested_directory_bits, HASH_DEFAULT_DIRECTORY_BITS)(((requested_directory_bits) > (5)) ? (requested_directory_bits ) : (5)); |
547 | segment_bits = MAX(requested_segment_bits, HASH_DEFAULT_SEGMENT_BITS)(((requested_segment_bits) > (5)) ? (requested_segment_bits ) : (5)); |
548 | } else { |
549 | directory_bits = requested_directory_bits; |
550 | segment_bits = requested_segment_bits; |
551 | } |
552 | } |
553 | |
554 | for (addr = ~0, n_addr_bits = 0; addr; addr >>= 1, n_addr_bits++); |
555 | |
556 | if (directory_bits + segment_bits > n_addr_bits) return EINVAL22; |
557 | |
558 | table = (hash_table_t *)alloc_func(sizeof(hash_table_t), |
559 | alloc_private_data); |
560 | if (table == NULL((void*)0)) { |
561 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
562 | } |
563 | memset(table, 0, sizeof(hash_table_t)); |
564 | table->halloc = alloc_func; |
565 | table->hfree = free_func; |
566 | table->halloc_pvt = alloc_private_data; |
567 | |
568 | table->directory_size_shift = directory_bits; |
569 | table->directory_size = directory_bits ? 1 << directory_bits : 0; |
570 | |
571 | table->segment_size_shift = segment_bits; |
572 | table->segment_size = segment_bits ? 1 << segment_bits : 0; |
573 | |
574 | /* Allocate directory */ |
575 | table->directory = (segment_t **)halloc(table, table->directory_size * sizeof(segment_t *))table->halloc(table->directory_size * sizeof(segment_t * ), table->halloc_pvt); |
576 | if (table->directory == NULL((void*)0)) { |
577 | hash_destroy(table); |
578 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
579 | } |
580 | memset(table->directory, 0, table->directory_size * sizeof(segment_t *)); |
581 | |
582 | /* |
583 | * If one wanted to pre-allocate all the buckets necessary to meet the needs |
584 | * of the requested count it would be done like this: |
585 | * |
586 | * table->segment_count = MIN((count + table->segment_size-1) / table->segment_size, |
587 | * table->directory_size); |
588 | * |
589 | * But with dynamic hash tables there is little point to this, the whole idea is to |
590 | * allow the table to grow/shrink dynamically, therefore we start with just one |
591 | * segment of buckets, the minimum necessary. |
592 | */ |
593 | table->segment_count = 1; |
594 | table->p = 0; |
595 | table->entry_count = 0; |
596 | table->delete_callback = delete_callback; |
597 | table->delete_pvt = delete_private_data; |
598 | |
599 | /* |
600 | * Allocate initial segments of buckets |
601 | */ |
602 | for (i = 0; i < table->segment_count; i++) { |
603 | table->directory[i] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t))table->halloc(table->segment_size * sizeof(segment_t), table ->halloc_pvt); |
604 | if (table->directory[i] == NULL((void*)0)) { |
605 | hash_destroy(table); |
606 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
607 | } |
608 | memset(table->directory[i], 0, table->segment_size * sizeof(segment_t)); |
609 | } |
610 | table->bucket_count = table->segment_count << table->segment_size_shift; |
611 | table->maxp = table->bucket_count; |
612 | table->min_load_factor = min_load_factor == 0 ? HASH_DEFAULT_MIN_LOAD_FACTOR1 : min_load_factor; |
613 | table->max_load_factor = max_load_factor == 0 ? HASH_DEFAULT_MAX_LOAD_FACTOR5 : max_load_factor; |
614 | |
615 | #if DEBUG |
616 | if (debug_level >= 1) { |
617 | fprintf(stderrstderr, "hash_create_ex: count=%lu available buckets=%lu bucket_count=%lu maxp=%lu\n", |
618 | count, table->directory_size*table->segment_size, table->bucket_count, table->maxp); |
619 | fprintf(stderrstderr, " directory_bits=%u segment_bits=%u requested_bits=%u\n", |
620 | directory_bits, segment_bits, requested_bits); |
621 | fprintf(stderrstderr, " directory_size=%lu segment_size=%lu segment_count=%lu\n", |
622 | table->directory_size, table->segment_size, table->segment_count); |
623 | fprintf(stderrstderr, " min_load_factor=%lu max_load_factor=%lu\n", |
624 | table->min_load_factor, table->max_load_factor); |
625 | } |
626 | #endif |
627 | #ifdef HASH_STATISTICS |
628 | memset(&table->statistics, 0, sizeof(table->statistics)); |
629 | #endif |
630 | |
631 | *tbl = table; |
632 | return HASH_SUCCESS0; |
633 | } |
634 | |
635 | #ifdef HASH_STATISTICS |
636 | int hash_get_statistics(hash_table_t *table, hash_statistics_t *statistics) |
637 | { |
638 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
639 | if (!statistics) return EINVAL22; |
640 | |
641 | *statistics = table->statistics; |
642 | |
643 | return HASH_SUCCESS0; |
644 | } |
645 | #endif |
646 | |
647 | int hash_destroy(hash_table_t *table) |
648 | { |
649 | unsigned long i, j; |
650 | segment_t *s; |
651 | element_t *p, *q; |
652 | |
653 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
654 | |
655 | if (table != NULL((void*)0)) { |
656 | if (table->directory) { |
657 | for (i = 0; i < table->segment_count; i++) { |
658 | /* test probably unnecessary */ |
659 | if ((s = table->directory[i]) != NULL((void*)0)) { |
660 | for (j = 0; j < table->segment_size; j++) { |
661 | p = s[j]; |
662 | while (p != NULL((void*)0)) { |
663 | q = p->next; |
664 | hdelete_callback(table, HASH_TABLE_DESTROY, &p->entry)do { if (table->delete_callback) { table->delete_callback (&p->entry, HASH_TABLE_DESTROY, table->delete_pvt); } } while(0); |
665 | if (p->entry.key.type == HASH_KEY_STRING) { |
666 | hfree(table, (char *)p->entry.key.str)table->hfree((char *)p->entry.key.str, table->halloc_pvt ); |
667 | } |
668 | hfree(table, (char *)p)table->hfree((char *)p, table->halloc_pvt); |
669 | p = q; |
670 | } |
671 | } |
672 | hfree(table, s)table->hfree(s, table->halloc_pvt); |
673 | } |
674 | } |
675 | hfree(table, table->directory)table->hfree(table->directory, table->halloc_pvt); |
676 | } |
677 | hfree(table, table)table->hfree(table, table->halloc_pvt); |
678 | table = NULL((void*)0); |
679 | } |
680 | return HASH_SUCCESS0; |
681 | } |
682 | |
683 | int hash_iterate(hash_table_t *table, hash_iterate_callback callback, void *user_data) |
684 | { |
685 | unsigned long i, j; |
686 | segment_t *s; |
687 | element_t *p; |
688 | |
689 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
690 | |
691 | if (table != NULL((void*)0)) { |
692 | for (i = 0; i < table->segment_count; i++) { |
693 | /* test probably unnecessary */ |
694 | if ((s = table->directory[i]) != NULL((void*)0)) { |
695 | for (j = 0; j < table->segment_size; j++) { |
696 | p = s[j]; |
697 | while (p != NULL((void*)0)) { |
698 | if(!(*callback)(&p->entry, user_data)) return HASH_SUCCESS0; |
699 | p = p->next; |
700 | } |
701 | } |
702 | } |
703 | } |
704 | } |
705 | return HASH_SUCCESS0; |
706 | } |
707 | |
708 | static hash_entry_t *hash_iter_next(struct hash_iter_context_t *iter_arg) |
709 | { |
710 | struct _hash_iter_context_t *iter = (struct _hash_iter_context_t *) iter_arg; |
711 | hash_entry_t *entry; |
712 | |
713 | if (iter->table == NULL((void*)0)) return NULL((void*)0); |
714 | goto state_3a; |
715 | |
716 | state_1: |
717 | iter->i++; |
718 | if(iter->i >= iter->table->segment_count) return NULL((void*)0); |
719 | /* test probably unnecessary */ |
720 | iter->s = iter->table->directory[iter->i]; |
721 | if (iter->s == NULL((void*)0)) goto state_1; |
722 | iter->j = 0; |
723 | state_2: |
724 | if (iter->j >= iter->table->segment_size) goto state_1; |
725 | iter->p = iter->s[iter->j]; |
726 | state_3a: |
727 | if (iter->p == NULL((void*)0)) goto state_3b; |
728 | entry = &iter->p->entry; |
729 | iter->p = iter->p->next; |
730 | return entry; |
731 | state_3b: |
732 | iter->j++; |
733 | goto state_2; |
734 | |
735 | /* Should never reach here */ |
736 | fprintf(stderrstderr, "ERROR hash_iter_next reached invalid state\n"); |
737 | return NULL((void*)0); |
738 | } |
739 | |
740 | struct hash_iter_context_t *new_hash_iter_context(hash_table_t *table) |
741 | { |
742 | struct _hash_iter_context_t *iter; |
743 | |
744 | if (!table) return NULL((void*)0);; |
745 | |
746 | iter = halloc(table, sizeof(struct _hash_iter_context_t))table->halloc(sizeof(struct _hash_iter_context_t), table-> halloc_pvt); |
747 | if (iter == NULL((void*)0)) { |
748 | return NULL((void*)0); |
749 | } |
750 | |
751 | |
752 | iter->iter.next = (hash_iter_next_t) hash_iter_next; |
753 | |
754 | iter->table = table; |
755 | iter->i = 0; |
756 | iter->j = 0; |
757 | iter->s = table->directory[iter->i]; |
758 | iter->p = iter->s[iter->j]; |
759 | |
760 | return (struct hash_iter_context_t *)iter; |
761 | } |
762 | |
763 | unsigned long hash_count(hash_table_t *table) |
764 | { |
765 | return table->entry_count; |
766 | } |
767 | |
768 | |
769 | int hash_keys(hash_table_t *table, unsigned long *count_arg, hash_key_t **keys_arg) |
770 | { |
771 | unsigned long count = table->entry_count; |
772 | hash_key_t *keys; |
773 | hash_keys_callback_data_t data; |
774 | |
775 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
776 | |
777 | if (count == 0) { |
778 | *count_arg = 0; |
779 | *keys_arg = NULL((void*)0); |
780 | return HASH_SUCCESS0; |
781 | } |
782 | |
783 | keys = halloc(table, sizeof(hash_key_t) * count)table->halloc(sizeof(hash_key_t) * count, table->halloc_pvt ); |
784 | if (keys == NULL((void*)0)) { |
785 | *count_arg = -1; |
786 | *keys_arg = NULL((void*)0); |
787 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
788 | } |
789 | |
790 | data.index = 0; |
791 | data.keys = keys; |
792 | |
793 | hash_iterate(table, hash_keys_callback, &data); |
794 | |
795 | *count_arg = count; |
796 | *keys_arg = keys; |
797 | return HASH_SUCCESS0; |
798 | } |
799 | |
800 | int hash_values(hash_table_t *table, unsigned long *count_arg, hash_value_t **values_arg) |
801 | { |
802 | unsigned long count = table->entry_count; |
803 | hash_value_t *values; |
804 | hash_values_callback_data_t data; |
805 | |
806 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
807 | |
808 | if (count == 0) { |
809 | *count_arg = 0; |
810 | *values_arg = NULL((void*)0); |
811 | return HASH_SUCCESS0; |
812 | } |
813 | |
814 | values = halloc(table, sizeof(hash_value_t) * count)table->halloc(sizeof(hash_value_t) * count, table->halloc_pvt ); |
815 | if (values == NULL((void*)0)) { |
816 | *count_arg = -1; |
817 | *values_arg = NULL((void*)0); |
818 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
819 | } |
820 | |
821 | data.index = 0; |
822 | data.values = values; |
823 | |
824 | hash_iterate(table, hash_values_callback, &data); |
825 | |
826 | *count_arg = count; |
827 | *values_arg = values; |
828 | return HASH_SUCCESS0; |
829 | } |
830 | |
831 | typedef struct hash_entries_callback_data_t { |
832 | unsigned long index; |
833 | hash_entry_t *entries; |
834 | } hash_entries_callback_data_t; |
835 | |
836 | static bool_Bool hash_entries_callback(hash_entry_t *item, void *user_data) |
837 | { |
838 | hash_entries_callback_data_t *data = (hash_entries_callback_data_t *)user_data; |
839 | |
840 | data->entries[data->index++] = *item; |
841 | return true1; |
842 | } |
843 | |
844 | int hash_entries(hash_table_t *table, unsigned long *count_arg, hash_entry_t **entries_arg) |
845 | { |
846 | unsigned long count = table->entry_count; |
847 | hash_entry_t *entries; |
848 | hash_entries_callback_data_t data; |
849 | |
850 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
851 | |
852 | if (count == 0) { |
853 | *count_arg = 0; |
854 | *entries_arg = NULL((void*)0); |
855 | return HASH_SUCCESS0; |
856 | } |
857 | |
858 | entries = halloc(table, sizeof(hash_entry_t) * count)table->halloc(sizeof(hash_entry_t) * count, table->halloc_pvt ); |
859 | if (entries == NULL((void*)0)) { |
860 | *count_arg = -1; |
861 | *entries_arg = NULL((void*)0); |
862 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
863 | } |
864 | |
865 | data.index = 0; |
866 | data.entries = entries; |
867 | |
868 | hash_iterate(table, hash_entries_callback, &data); |
869 | |
870 | *count_arg = count; |
871 | *entries_arg = entries; |
872 | return HASH_SUCCESS0; |
873 | } |
874 | |
875 | bool_Bool hash_has_key(hash_table_t *table, hash_key_t *key) |
876 | { |
877 | hash_value_t value; |
878 | |
879 | if (hash_lookup(table, key, &value) == HASH_SUCCESS0) |
880 | return true1; |
881 | else |
882 | return false0; |
883 | } |
884 | |
885 | |
886 | int hash_get_default(hash_table_t *table, hash_key_t *key, hash_value_t *value, hash_value_t *default_value) |
887 | { |
888 | int error; |
889 | |
890 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
891 | |
892 | if ((error = hash_lookup(table, key, value)) != HASH_SUCCESS0) { |
Although the value stored to 'error' is used in the enclosing expression, the value is never actually read from 'error' | |
893 | if ((error = hash_enter(table, key, default_value)) != HASH_SUCCESS0) { |
894 | return error; |
895 | } |
896 | *value = *default_value; |
897 | return HASH_SUCCESS0; |
898 | } |
899 | |
900 | return HASH_SUCCESS0; |
901 | } |
902 | |
903 | int hash_enter(hash_table_t *table, hash_key_t *key, hash_value_t *value) |
904 | { |
905 | int error; |
906 | segment_t element, *chain; |
907 | size_t len; |
908 | |
909 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
910 | |
911 | if (!is_valid_key_type(key->type)) |
912 | return HASH_ERROR_BAD_KEY_TYPE(-2000 + 1); |
913 | |
914 | if (!is_valid_value_type(value->type)) |
915 | return HASH_ERROR_BAD_VALUE_TYPE(-2000 + 2); |
916 | |
917 | lookup(table, key, &element, &chain); |
918 | |
919 | if (element == NULL((void*)0)) { /* not found */ |
920 | element = (element_t *)halloc(table, sizeof(element_t))table->halloc(sizeof(element_t), table->halloc_pvt); |
921 | if (element == NULL((void*)0)) { |
922 | /* Allocation failed, return NULL */ |
923 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
924 | } |
925 | memset(element, 0, sizeof(element_t)); |
926 | /* |
927 | * Initialize new element |
928 | */ |
929 | switch(element->entry.key.type = key->type) { |
930 | case HASH_KEY_ULONG: |
931 | element->entry.key.ul = key->ul; |
932 | break; |
933 | case HASH_KEY_STRING: |
934 | len = strlen(key->str)+1; |
935 | element->entry.key.str = halloc(table, len)table->halloc(len, table->halloc_pvt); |
936 | if (element->entry.key.str == NULL((void*)0)) { |
937 | hfree(table, element)table->hfree(element, table->halloc_pvt); |
938 | return HASH_ERROR_NO_MEMORY(-2000 + 3); |
939 | } |
940 | memcpy((void *)element->entry.key.str, key->str, len); |
941 | break; |
942 | } |
943 | |
944 | *chain = element; /* link into chain */ |
945 | element->next = NULL((void*)0); |
946 | |
947 | /* |
948 | * Table over-full? |
949 | */ |
950 | if (++table->entry_count / table->bucket_count > table->max_load_factor) { |
951 | if ((error = expand_table(table)) != HASH_SUCCESS0) { /* doesn't affect element */ |
952 | return error; |
953 | } |
954 | } |
955 | |
956 | } else { |
957 | hdelete_callback(table, HASH_ENTRY_DESTROY, &element->entry)do { if (table->delete_callback) { table->delete_callback (&element->entry, HASH_ENTRY_DESTROY, table->delete_pvt ); } } while(0); |
958 | } |
959 | |
960 | switch(element->entry.value.type = value->type) { |
961 | case HASH_VALUE_UNDEF: |
962 | element->entry.value.ul = 0; |
963 | break; |
964 | case HASH_VALUE_PTR: |
965 | element->entry.value.ptr = value->ptr; |
966 | break; |
967 | case HASH_VALUE_INT: |
968 | element->entry.value.i = value->i; |
969 | break; |
970 | case HASH_VALUE_UINT: |
971 | element->entry.value.ui = value->ui; |
972 | break; |
973 | case HASH_VALUE_LONG: |
974 | element->entry.value.l = value->l; |
975 | break; |
976 | case HASH_VALUE_ULONG: |
977 | element->entry.value.ul = value->ul; |
978 | break; |
979 | case HASH_VALUE_FLOAT: |
980 | element->entry.value.f = value->f; |
981 | break; |
982 | case HASH_VALUE_DOUBLE: |
983 | element->entry.value.d = value->d; |
984 | break; |
985 | } |
986 | |
987 | return HASH_SUCCESS0; |
988 | } |
989 | |
990 | int hash_lookup(hash_table_t *table, hash_key_t *key, hash_value_t *value) |
991 | { |
992 | segment_t element, *chain; |
993 | |
994 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
995 | |
996 | if (!is_valid_key_type(key->type)) |
997 | return HASH_ERROR_BAD_KEY_TYPE(-2000 + 1); |
998 | |
999 | lookup(table, key, &element, &chain); |
1000 | |
1001 | if (element) { |
1002 | *value = element->entry.value; |
1003 | return HASH_SUCCESS0; |
1004 | } else { |
1005 | return HASH_ERROR_KEY_NOT_FOUND(-2000 + 4); |
1006 | } |
1007 | } |
1008 | |
1009 | int hash_delete(hash_table_t *table, hash_key_t *key) |
1010 | { |
1011 | int error; |
1012 | segment_t element, *chain; |
1013 | |
1014 | if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5); |
1015 | |
1016 | if (!is_valid_key_type(key->type)) |
1017 | return HASH_ERROR_BAD_KEY_TYPE(-2000 + 1); |
1018 | |
1019 | lookup(table, key, &element, &chain); |
1020 | |
1021 | if (element) { |
1022 | hdelete_callback(table, HASH_ENTRY_DESTROY, &element->entry)do { if (table->delete_callback) { table->delete_callback (&element->entry, HASH_ENTRY_DESTROY, table->delete_pvt ); } } while(0); |
1023 | *chain = element->next; /* remove from chain */ |
1024 | /* |
1025 | * Table too sparse? |
1026 | */ |
1027 | if (--table->entry_count / table->bucket_count < table->min_load_factor) { |
1028 | if ((error = contract_table(table)) != HASH_SUCCESS0) { /* doesn't affect element */ |
1029 | return error; |
1030 | } |
1031 | } |
1032 | if (element->entry.key.type == HASH_KEY_STRING) { |
1033 | hfree(table, (char *)element->entry.key.str)table->hfree((char *)element->entry.key.str, table-> halloc_pvt); |
1034 | } |
1035 | hfree(table, element)table->hfree(element, table->halloc_pvt); |
1036 | return HASH_SUCCESS0; |
1037 | } else { |
1038 | return HASH_ERROR_KEY_NOT_FOUND(-2000 + 4); |
1039 | } |
1040 | } |
1041 | |
1042 |