"Fossies" - the Fresh Open Source Software Archive 
Member "fusesmb-0.8.7/hash.c" (22 Jul 2005, 28255 Bytes) of package /linux/privat/old/fusesmb-0.8.7.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "hash.c" see the
Fossies "Dox" file reference documentation.
1 /*
2 * Hash Table Data Type
3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
4 *
5 * Free Software License:
6 *
7 * All rights are reserved by the author, with the following exceptions:
8 * Permission is granted to freely reproduce and distribute this software,
9 * possibly in exchange for a fee, provided that this copyright notice appears
10 * intact. Permission is also granted to adapt this software to produce
11 * derivative works, as long as the modified versions carry this copyright
12 * notice and additional notices stating that the work has been modified.
13 * This source code may be translated into executable form and incorporated
14 * into proprietary software; there is no requirement for such software to
15 * contain a copyright notice related to this source.
16 *
17 * $Id: hash.c,v 1.36.2.11 2000/11/13 01:36:45 kaz Exp $
18 * $Name: kazlib_1_20 $
19 */
20
21 #include <stdlib.h>
22 #include <stddef.h>
23 #include <assert.h>
24 #include <string.h>
25 #define HASH_IMPLEMENTATION
26 #include "hash.h"
27
28 #ifdef KAZLIB_RCSID
29 static const char rcsid[] = "$Id: hash.c,v 1.36.2.11 2000/11/13 01:36:45 kaz Exp $";
30 #endif
31
32 #define INIT_BITS 6
33 #define INIT_SIZE (1UL << (INIT_BITS)) /* must be power of two */
34 #define INIT_MASK ((INIT_SIZE) - 1)
35
36 #define next hash_next
37 #define key hash_key
38 #define data hash_data
39 #define hkey hash_hkey
40
41 #define table hash_table
42 #define nchains hash_nchains
43 #define nodecount hash_nodecount
44 #define maxcount hash_maxcount
45 #define highmark hash_highmark
46 #define lowmark hash_lowmark
47 #define compare hash_compare
48 #define function hash_function
49 #define allocnode hash_allocnode
50 #define freenode hash_freenode
51 #define context hash_context
52 #define mask hash_mask
53 #define dynamic hash_dynamic
54
55 #define table hash_table
56 #define chain hash_chain
57
58 static hnode_t *hnode_alloc(void *context);
59 static void hnode_free(hnode_t *node, void *context);
60 static hash_val_t hash_fun_default(const void *key);
61 static int hash_comp_default(const void *key1, const void *key2);
62
63 int hash_val_t_bit;
64
65 /*
66 * Compute the number of bits in the hash_val_t type. We know that hash_val_t
67 * is an unsigned integral type. Thus the highest value it can hold is a
68 * Mersenne number (power of two, less one). We initialize a hash_val_t
69 * object with this value and then shift bits out one by one while counting.
70 * Notes:
71 * 1. HASH_VAL_T_MAX is a Mersenne number---one that is one less than a power
72 * of two. This means that its binary representation consists of all one
73 * bits, and hence ``val'' is initialized to all one bits.
74 * 2. While bits remain in val, we increment the bit count and shift it to the
75 * right, replacing the topmost bit by zero.
76 */
77
78 static void compute_bits(void)
79 {
80 hash_val_t val = HASH_VAL_T_MAX; /* 1 */
81 int bits = 0;
82
83 while (val) { /* 2 */
84 bits++;
85 val >>= 1;
86 }
87
88 hash_val_t_bit = bits;
89 }
90
91 /*
92 * Verify whether the given argument is a power of two.
93 */
94
95 static int is_power_of_two(hash_val_t arg)
96 {
97 if (arg == 0)
98 return 0;
99 while ((arg & 1) == 0)
100 arg >>= 1;
101 return (arg == 1);
102 }
103
104 /*
105 * Compute a shift amount from a given table size
106 */
107
108 static hash_val_t compute_mask(hashcount_t size)
109 {
110 assert (is_power_of_two(size));
111 assert (size >= 2);
112
113 return size - 1;
114 }
115
116 /*
117 * Initialize the table of pointers to null.
118 */
119
120 static void clear_table(hash_t *hash)
121 {
122 hash_val_t i;
123
124 for (i = 0; i < hash->nchains; i++)
125 hash->table[i] = NULL;
126 }
127
128 /*
129 * Double the size of a dynamic table. This works as follows. Each chain splits
130 * into two adjacent chains. The shift amount increases by one, exposing an
131 * additional bit of each hashed key. For each node in the original chain, the
132 * value of this newly exposed bit will decide which of the two new chains will
133 * receive the node: if the bit is 1, the chain with the higher index will have
134 * the node, otherwise the lower chain will receive the node. In this manner,
135 * the hash table will continue to function exactly as before without having to
136 * rehash any of the keys.
137 * Notes:
138 * 1. Overflow check.
139 * 2. The new number of chains is twice the old number of chains.
140 * 3. The new mask is one bit wider than the previous, revealing a
141 * new bit in all hashed keys.
142 * 4. Allocate a new table of chain pointers that is twice as large as the
143 * previous one.
144 * 5. If the reallocation was successful, we perform the rest of the growth
145 * algorithm, otherwise we do nothing.
146 * 6. The exposed_bit variable holds a mask with which each hashed key can be
147 * AND-ed to test the value of its newly exposed bit.
148 * 7. Now loop over each chain in the table and sort its nodes into two
149 * chains based on the value of each node's newly exposed hash bit.
150 * 8. The low chain replaces the current chain. The high chain goes
151 * into the corresponding sister chain in the upper half of the table.
152 * 9. We have finished dealing with the chains and nodes. We now update
153 * the various bookeeping fields of the hash structure.
154 */
155
156 static void grow_table(hash_t *hash)
157 {
158 hnode_t **newtable;
159
160 assert (2 * hash->nchains > hash->nchains); /* 1 */
161
162 newtable = realloc(hash->table,
163 sizeof *newtable * hash->nchains * 2); /* 4 */
164
165 if (newtable) { /* 5 */
166 hash_val_t mask = (hash->mask << 1) | 1; /* 3 */
167 hash_val_t exposed_bit = mask ^ hash->mask; /* 6 */
168 hash_val_t chain;
169
170 assert (mask != hash->mask);
171
172 for (chain = 0; chain < hash->nchains; chain++) { /* 7 */
173 hnode_t *low_chain = 0, *high_chain = 0, *hptr, *next;
174
175 for (hptr = newtable[chain]; hptr != 0; hptr = next) {
176 next = hptr->next;
177
178 if (hptr->hkey & exposed_bit) {
179 hptr->next = high_chain;
180 high_chain = hptr;
181 } else {
182 hptr->next = low_chain;
183 low_chain = hptr;
184 }
185 }
186
187 newtable[chain] = low_chain; /* 8 */
188 newtable[chain + hash->nchains] = high_chain;
189 }
190
191 hash->table = newtable; /* 9 */
192 hash->mask = mask;
193 hash->nchains *= 2;
194 hash->lowmark *= 2;
195 hash->highmark *= 2;
196 }
197 assert (hash_verify(hash));
198 }
199
200 /*
201 * Cut a table size in half. This is done by folding together adjacent chains
202 * and populating the lower half of the table with these chains. The chains are
203 * simply spliced together. Once this is done, the whole table is reallocated
204 * to a smaller object.
205 * Notes:
206 * 1. It is illegal to have a hash table with one slot. This would mean that
207 * hash->shift is equal to hash_val_t_bit, an illegal shift value.
208 * Also, other things could go wrong, such as hash->lowmark becoming zero.
209 * 2. Looping over each pair of sister chains, the low_chain is set to
210 * point to the head node of the chain in the lower half of the table,
211 * and high_chain points to the head node of the sister in the upper half.
212 * 3. The intent here is to compute a pointer to the last node of the
213 * lower chain into the low_tail variable. If this chain is empty,
214 * low_tail ends up with a null value.
215 * 4. If the lower chain is not empty, we simply tack the upper chain onto it.
216 * If the upper chain is a null pointer, nothing happens.
217 * 5. Otherwise if the lower chain is empty but the upper one is not,
218 * If the low chain is empty, but the high chain is not, then the
219 * high chain is simply transferred to the lower half of the table.
220 * 6. Otherwise if both chains are empty, there is nothing to do.
221 * 7. All the chain pointers are in the lower half of the table now, so
222 * we reallocate it to a smaller object. This, of course, invalidates
223 * all pointer-to-pointers which reference into the table from the
224 * first node of each chain.
225 * 8. Though it's unlikely, the reallocation may fail. In this case we
226 * pretend that the table _was_ reallocated to a smaller object.
227 * 9. Finally, update the various table parameters to reflect the new size.
228 */
229
230 static void shrink_table(hash_t *hash)
231 {
232 hash_val_t chain, nchains;
233 hnode_t **newtable, *low_tail, *low_chain, *high_chain;
234
235 assert (hash->nchains >= 2); /* 1 */
236 nchains = hash->nchains / 2;
237
238 for (chain = 0; chain < nchains; chain++) {
239 low_chain = hash->table[chain]; /* 2 */
240 high_chain = hash->table[chain + nchains];
241 for (low_tail = low_chain; low_tail && low_tail->next; low_tail = low_tail->next)
242 ; /* 3 */
243 if (low_chain != 0) /* 4 */
244 low_tail->next = high_chain;
245 else if (high_chain != 0) /* 5 */
246 hash->table[chain] = high_chain;
247 else
248 assert (hash->table[chain] == NULL); /* 6 */
249 }
250 newtable = realloc(hash->table,
251 sizeof *newtable * nchains); /* 7 */
252 if (newtable) /* 8 */
253 hash->table = newtable;
254 hash->mask >>= 1; /* 9 */
255 hash->nchains = nchains;
256 hash->lowmark /= 2;
257 hash->highmark /= 2;
258 assert (hash_verify(hash));
259 }
260
261
262 /*
263 * Create a dynamic hash table. Both the hash table structure and the table
264 * itself are dynamically allocated. Furthermore, the table is extendible in
265 * that it will automatically grow as its load factor increases beyond a
266 * certain threshold.
267 * Notes:
268 * 1. If the number of bits in the hash_val_t type has not been computed yet,
269 * we do so here, because this is likely to be the first function that the
270 * user calls.
271 * 2. Allocate a hash table control structure.
272 * 3. If a hash table control structure is successfully allocated, we
273 * proceed to initialize it. Otherwise we return a null pointer.
274 * 4. We try to allocate the table of hash chains.
275 * 5. If we were able to allocate the hash chain table, we can finish
276 * initializing the hash structure and the table. Otherwise, we must
277 * backtrack by freeing the hash structure.
278 * 6. INIT_SIZE should be a power of two. The high and low marks are always set
279 * to be twice the table size and half the table size respectively. When the
280 * number of nodes in the table grows beyond the high size (beyond load
281 * factor 2), it will double in size to cut the load factor down to about
282 * about 1. If the table shrinks down to or beneath load factor 0.5,
283 * it will shrink, bringing the load up to about 1. However, the table
284 * will never shrink beneath INIT_SIZE even if it's emptied.
285 * 7. This indicates that the table is dynamically allocated and dynamically
286 * resized on the fly. A table that has this value set to zero is
287 * assumed to be statically allocated and will not be resized.
288 * 8. The table of chains must be properly reset to all null pointers.
289 */
290
291 hash_t *hash_create(hashcount_t maxcount, hash_comp_t compfun,
292 hash_fun_t hashfun)
293 {
294 hash_t *hash;
295
296 if (hash_val_t_bit == 0) /* 1 */
297 compute_bits();
298
299 hash = malloc(sizeof *hash); /* 2 */
300
301 if (hash) { /* 3 */
302 hash->table = malloc(sizeof *hash->table * INIT_SIZE); /* 4 */
303 if (hash->table) { /* 5 */
304 hash->nchains = INIT_SIZE; /* 6 */
305 hash->highmark = INIT_SIZE * 2;
306 hash->lowmark = INIT_SIZE / 2;
307 hash->nodecount = 0;
308 hash->maxcount = maxcount;
309 hash->compare = compfun ? compfun : hash_comp_default;
310 hash->function = hashfun ? hashfun : hash_fun_default;
311 hash->allocnode = hnode_alloc;
312 hash->freenode = hnode_free;
313 hash->context = NULL;
314 hash->mask = INIT_MASK;
315 hash->dynamic = 1; /* 7 */
316 clear_table(hash); /* 8 */
317 assert (hash_verify(hash));
318 return hash;
319 }
320 free(hash);
321 }
322
323 return NULL;
324 }
325
326 /*
327 * Select a different set of node allocator routines.
328 */
329
330 void hash_set_allocator(hash_t *hash, hnode_alloc_t al,
331 hnode_free_t fr, void *context)
332 {
333 assert (hash_count(hash) == 0);
334 assert ((al == 0 && fr == 0) || (al != 0 && fr != 0));
335
336 hash->allocnode = al ? al : hnode_alloc;
337 hash->freenode = fr ? fr : hnode_free;
338 hash->context = context;
339 }
340
341 /*
342 * Free every node in the hash using the hash->freenode() function pointer, and
343 * cause the hash to become empty.
344 */
345
346 void hash_free_nodes(hash_t *hash)
347 {
348 hscan_t hs;
349 hnode_t *node;
350 hash_scan_begin(&hs, hash);
351 while ((node = hash_scan_next(&hs))) {
352 hash_scan_delete(hash, node);
353 hash->freenode(node, hash->context);
354 }
355 hash->nodecount = 0;
356 clear_table(hash);
357 }
358
359 /*
360 * Obsolescent function for removing all nodes from a table,
361 * freeing them and then freeing the table all in one step.
362 */
363
364 void hash_free(hash_t *hash)
365 {
366 #ifdef KAZLIB_OBSOLESCENT_DEBUG
367 assert ("call to obsolescent function hash_free()" && 0);
368 #endif
369 hash_free_nodes(hash);
370 hash_destroy(hash);
371 }
372
373 /*
374 * Free a dynamic hash table structure.
375 */
376
377 void hash_destroy(hash_t *hash)
378 {
379 assert (hash_val_t_bit != 0);
380 assert (hash_isempty(hash));
381 free(hash->table);
382 free(hash);
383 }
384
385 /*
386 * Initialize a user supplied hash structure. The user also supplies a table of
387 * chains which is assigned to the hash structure. The table is static---it
388 * will not grow or shrink.
389 * 1. See note 1. in hash_create().
390 * 2. The user supplied array of pointers hopefully contains nchains nodes.
391 * 3. See note 7. in hash_create().
392 * 4. We must dynamically compute the mask from the given power of two table
393 * size.
394 * 5. The user supplied table can't be assumed to contain null pointers,
395 * so we reset it here.
396 */
397
398 hash_t *hash_init(hash_t *hash, hashcount_t maxcount,
399 hash_comp_t compfun, hash_fun_t hashfun, hnode_t **table,
400 hashcount_t nchains)
401 {
402 if (hash_val_t_bit == 0) /* 1 */
403 compute_bits();
404
405 assert (is_power_of_two(nchains));
406
407 hash->table = table; /* 2 */
408 hash->nchains = nchains;
409 hash->nodecount = 0;
410 hash->maxcount = maxcount;
411 hash->compare = compfun ? compfun : hash_comp_default;
412 hash->function = hashfun ? hashfun : hash_fun_default;
413 hash->dynamic = 0; /* 3 */
414 hash->mask = compute_mask(nchains); /* 4 */
415 clear_table(hash); /* 5 */
416
417 assert (hash_verify(hash));
418
419 return hash;
420 }
421
422 /*
423 * Reset the hash scanner so that the next element retrieved by
424 * hash_scan_next() shall be the first element on the first non-empty chain.
425 * Notes:
426 * 1. Locate the first non empty chain.
427 * 2. If an empty chain is found, remember which one it is and set the next
428 * pointer to refer to its first element.
429 * 3. Otherwise if a chain is not found, set the next pointer to NULL
430 * so that hash_scan_next() shall indicate failure.
431 */
432
433 void hash_scan_begin(hscan_t *scan, hash_t *hash)
434 {
435 hash_val_t nchains = hash->nchains;
436 hash_val_t chain;
437
438 scan->table = hash;
439
440 /* 1 */
441
442 for (chain = 0; chain < nchains && hash->table[chain] == 0; chain++)
443 ;
444
445 if (chain < nchains) { /* 2 */
446 scan->chain = chain;
447 scan->next = hash->table[chain];
448 } else { /* 3 */
449 scan->next = NULL;
450 }
451 }
452
453 /*
454 * Retrieve the next node from the hash table, and update the pointer
455 * for the next invocation of hash_scan_next().
456 * Notes:
457 * 1. Remember the next pointer in a temporary value so that it can be
458 * returned.
459 * 2. This assertion essentially checks whether the module has been properly
460 * initialized. The first point of interaction with the module should be
461 * either hash_create() or hash_init(), both of which set hash_val_t_bit to
462 * a non zero value.
463 * 3. If the next pointer we are returning is not NULL, then the user is
464 * allowed to call hash_scan_next() again. We prepare the new next pointer
465 * for that call right now. That way the user is allowed to delete the node
466 * we are about to return, since we will no longer be needing it to locate
467 * the next node.
468 * 4. If there is a next node in the chain (next->next), then that becomes the
469 * new next node, otherwise ...
470 * 5. We have exhausted the current chain, and must locate the next subsequent
471 * non-empty chain in the table.
472 * 6. If a non-empty chain is found, the first element of that chain becomes
473 * the new next node. Otherwise there is no new next node and we set the
474 * pointer to NULL so that the next time hash_scan_next() is called, a null
475 * pointer shall be immediately returned.
476 */
477
478
479 hnode_t *hash_scan_next(hscan_t *scan)
480 {
481 hnode_t *next = scan->next; /* 1 */
482 hash_t *hash = scan->table;
483 hash_val_t chain = scan->chain + 1;
484 hash_val_t nchains = hash->nchains;
485
486 assert (hash_val_t_bit != 0); /* 2 */
487
488 if (next) { /* 3 */
489 if (next->next) { /* 4 */
490 scan->next = next->next;
491 } else {
492 while (chain < nchains && hash->table[chain] == 0) /* 5 */
493 chain++;
494 if (chain < nchains) { /* 6 */
495 scan->chain = chain;
496 scan->next = hash->table[chain];
497 } else {
498 scan->next = NULL;
499 }
500 }
501 }
502 return next;
503 }
504
505 /*
506 * Insert a node into the hash table.
507 * Notes:
508 * 1. It's illegal to insert more than the maximum number of nodes. The client
509 * should verify that the hash table is not full before attempting an
510 * insertion.
511 * 2. The same key may not be inserted into a table twice.
512 * 3. If the table is dynamic and the load factor is already at >= 2,
513 * grow the table.
514 * 4. We take the bottom N bits of the hash value to derive the chain index,
515 * where N is the base 2 logarithm of the size of the hash table.
516 */
517
518 void hash_insert(hash_t *hash, hnode_t *node, const void *key)
519 {
520 hash_val_t hkey, chain;
521
522 assert (hash_val_t_bit != 0);
523 assert (node->next == NULL);
524 assert (hash->nodecount < hash->maxcount); /* 1 */
525 assert (hash_lookup(hash, key) == NULL); /* 2 */
526
527 if (hash->dynamic && hash->nodecount >= hash->highmark) /* 3 */
528 grow_table(hash);
529
530 hkey = hash->function(key);
531 chain = hkey & hash->mask; /* 4 */
532
533 node->key = key;
534 node->hkey = hkey;
535 node->next = hash->table[chain];
536 hash->table[chain] = node;
537 hash->nodecount++;
538
539 assert (hash_verify(hash));
540 }
541
542 /*
543 * Find a node in the hash table and return a pointer to it.
544 * Notes:
545 * 1. We hash the key and keep the entire hash value. As an optimization, when
546 * we descend down the chain, we can compare hash values first and only if
547 * hash values match do we perform a full key comparison.
548 * 2. To locate the chain from among 2^N chains, we look at the lower N bits of
549 * the hash value by anding them with the current mask.
550 * 3. Looping through the chain, we compare the stored hash value inside each
551 * node against our computed hash. If they match, then we do a full
552 * comparison between the unhashed keys. If these match, we have located the
553 * entry.
554 */
555
556 hnode_t *hash_lookup(hash_t *hash, const void *key)
557 {
558 hash_val_t hkey, chain;
559 hnode_t *nptr;
560
561 hkey = hash->function(key); /* 1 */
562 chain = hkey & hash->mask; /* 2 */
563
564 for (nptr = hash->table[chain]; nptr; nptr = nptr->next) { /* 3 */
565 if (nptr->hkey == hkey && hash->compare(nptr->key, key) == 0)
566 return nptr;
567 }
568
569 return NULL;
570 }
571
572 /*
573 * Delete the given node from the hash table. Since the chains
574 * are singly linked, we must locate the start of the node's chain
575 * and traverse.
576 * Notes:
577 * 1. The node must belong to this hash table, and its key must not have
578 * been tampered with.
579 * 2. If this deletion will take the node count below the low mark, we
580 * shrink the table now.
581 * 3. Determine which chain the node belongs to, and fetch the pointer
582 * to the first node in this chain.
583 * 4. If the node being deleted is the first node in the chain, then
584 * simply update the chain head pointer.
585 * 5. Otherwise advance to the node's predecessor, and splice out
586 * by updating the predecessor's next pointer.
587 * 6. Indicate that the node is no longer in a hash table.
588 */
589
590 hnode_t *hash_delete(hash_t *hash, hnode_t *node)
591 {
592 hash_val_t chain;
593 hnode_t *hptr;
594
595 assert (hash_lookup(hash, node->key) == node); /* 1 */
596 assert (hash_val_t_bit != 0);
597
598 if (hash->dynamic && hash->nodecount <= hash->lowmark
599 && hash->nodecount > INIT_SIZE)
600 shrink_table(hash); /* 2 */
601
602 chain = node->hkey & hash->mask; /* 3 */
603 hptr = hash->table[chain];
604
605 if (hptr == node) { /* 4 */
606 hash->table[chain] = node->next;
607 } else {
608 while (hptr->next != node) { /* 5 */
609 assert (hptr != 0);
610 hptr = hptr->next;
611 }
612 assert (hptr->next == node);
613 hptr->next = node->next;
614 }
615
616 hash->nodecount--;
617 assert (hash_verify(hash));
618
619 node->next = NULL; /* 6 */
620 return node;
621 }
622
623 int hash_alloc_insert(hash_t *hash, const void *key, void *data)
624 {
625 hnode_t *node = hash->allocnode(hash->context);
626
627 if (node) {
628 hnode_init(node, data);
629 hash_insert(hash, node, key);
630 return 1;
631 }
632 return 0;
633 }
634
635 void hash_delete_free(hash_t *hash, hnode_t *node)
636 {
637 hash_delete(hash, node);
638 hash->freenode(node, hash->context);
639 }
640
641 /*
642 * Exactly like hash_delete, except does not trigger table shrinkage. This is to be
643 * used from within a hash table scan operation. See notes for hash_delete.
644 */
645
646 hnode_t *hash_scan_delete(hash_t *hash, hnode_t *node)
647 {
648 hash_val_t chain;
649 hnode_t *hptr;
650
651 assert (hash_lookup(hash, node->key) == node);
652 assert (hash_val_t_bit != 0);
653
654 chain = node->hkey & hash->mask;
655 hptr = hash->table[chain];
656
657 if (hptr == node) {
658 hash->table[chain] = node->next;
659 } else {
660 while (hptr->next != node)
661 hptr = hptr->next;
662 hptr->next = node->next;
663 }
664
665 hash->nodecount--;
666 assert (hash_verify(hash));
667 node->next = NULL;
668
669 return node;
670 }
671
672 /*
673 * Like hash_delete_free but based on hash_scan_delete.
674 */
675
676 void hash_scan_delfree(hash_t *hash, hnode_t *node)
677 {
678 hash_scan_delete(hash, node);
679 hash->freenode(node, hash->context);
680 }
681
682 /*
683 * Verify whether the given object is a valid hash table. This means
684 * Notes:
685 * 1. If the hash table is dynamic, verify whether the high and
686 * low expansion/shrinkage thresholds are powers of two.
687 * 2. Count all nodes in the table, and test each hash value
688 * to see whether it is correct for the node's chain.
689 */
690
691 int hash_verify(hash_t *hash)
692 {
693 hashcount_t count = 0;
694 hash_val_t chain;
695 hnode_t *hptr;
696
697 if (hash->dynamic) { /* 1 */
698 if (hash->lowmark >= hash->highmark)
699 return 0;
700 if (!is_power_of_two(hash->highmark))
701 return 0;
702 if (!is_power_of_two(hash->lowmark))
703 return 0;
704 }
705
706 for (chain = 0; chain < hash->nchains; chain++) { /* 2 */
707 for (hptr = hash->table[chain]; hptr != 0; hptr = hptr->next) {
708 if ((hptr->hkey & hash->mask) != chain)
709 return 0;
710 count++;
711 }
712 }
713
714 if (count != hash->nodecount)
715 return 0;
716
717 return 1;
718 }
719
720 /*
721 * Test whether the hash table is full and return 1 if this is true,
722 * 0 if it is false.
723 */
724
725 #undef hash_isfull
726 int hash_isfull(hash_t *hash)
727 {
728 return hash->nodecount == hash->maxcount;
729 }
730
731 /*
732 * Test whether the hash table is empty and return 1 if this is true,
733 * 0 if it is false.
734 */
735
736 #undef hash_isempty
737 int hash_isempty(hash_t *hash)
738 {
739 return hash->nodecount == 0;
740 }
741
742 static hnode_t *hnode_alloc(void *context)
743 {
744 (void)context;
745 return malloc(sizeof *hnode_alloc(NULL));
746 }
747
748 static void hnode_free(hnode_t *node, void *context)
749 {
750 (void)context;
751 free(node);
752 }
753
754
755 /*
756 * Create a hash table node dynamically and assign it the given data.
757 */
758
759 hnode_t *hnode_create(void *data)
760 {
761 hnode_t *node = malloc(sizeof *node);
762 if (node) {
763 node->data = data;
764 node->next = NULL;
765 }
766 return node;
767 }
768
769 /*
770 * Initialize a client-supplied node
771 */
772
773 hnode_t *hnode_init(hnode_t *hnode, void *data)
774 {
775 hnode->data = data;
776 hnode->next = NULL;
777 return hnode;
778 }
779
780 /*
781 * Destroy a dynamically allocated node.
782 */
783
784 void hnode_destroy(hnode_t *hnode)
785 {
786 free(hnode);
787 }
788
789 #undef hnode_put
790 void hnode_put(hnode_t *node, void *data)
791 {
792 node->data = data;
793 }
794
795 #undef hnode_get
796 void *hnode_get(hnode_t *node)
797 {
798 return node->data;
799 }
800
801 #undef hnode_getkey
802 const void *hnode_getkey(hnode_t *node)
803 {
804 return node->key;
805 }
806
807 #undef hash_count
808 hashcount_t hash_count(hash_t *hash)
809 {
810 return hash->nodecount;
811 }
812
813 #undef hash_size
814 hashcount_t hash_size(hash_t *hash)
815 {
816 return hash->nchains;
817 }
818
819 static hash_val_t hash_fun_default(const void *key)
820 {
821 static unsigned long randbox[] = {
822 0x49848f1bU, 0xe6255dbaU, 0x36da5bdcU, 0x47bf94e9U,
823 0x8cbcce22U, 0x559fc06aU, 0xd268f536U, 0xe10af79aU,
824 0xc1af4d69U, 0x1d2917b5U, 0xec4c304dU, 0x9ee5016cU,
825 0x69232f74U, 0xfead7bb3U, 0xe9089ab6U, 0xf012f6aeU,
826 };
827
828 const unsigned char *str = key;
829 hash_val_t acc = 0;
830
831 while (*str) {
832 acc ^= randbox[(*str + acc) & 0xf];
833 acc = (acc << 1) | (acc >> 31);
834 acc &= 0xffffffffU;
835 acc ^= randbox[((*str++ >> 4) + acc) & 0xf];
836 acc = (acc << 2) | (acc >> 30);
837 acc &= 0xffffffffU;
838 }
839 return acc;
840 }
841
842 static int hash_comp_default(const void *key1, const void *key2)
843 {
844 return strcmp(key1, key2);
845 }
846
847 #ifdef KAZLIB_TEST_MAIN
848
849 #include <stdio.h>
850 #include <ctype.h>
851 #include <stdarg.h>
852
853 typedef char input_t[256];
854
855 static int tokenize(char *string, ...)
856 {
857 char **tokptr;
858 va_list arglist;
859 int tokcount = 0;
860
861 va_start(arglist, string);
862 tokptr = va_arg(arglist, char **);
863 while (tokptr) {
864 while (*string && isspace((unsigned char) *string))
865 string++;
866 if (!*string)
867 break;
868 *tokptr = string;
869 while (*string && !isspace((unsigned char) *string))
870 string++;
871 tokptr = va_arg(arglist, char **);
872 tokcount++;
873 if (!*string)
874 break;
875 *string++ = 0;
876 }
877 va_end(arglist);
878
879 return tokcount;
880 }
881
882 static char *dupstring(char *str)
883 {
884 int sz = strlen(str) + 1;
885 char *new = malloc(sz);
886 if (new)
887 memcpy(new, str, sz);
888 return new;
889 }
890
891 static hnode_t *new_node(void *c)
892 {
893 static hnode_t few[5];
894 static int count;
895
896 if (count < 5)
897 return few + count++;
898
899 return NULL;
900 }
901
902 static void del_node(hnode_t *n, void *c)
903 {
904 }
905
906 int main(void)
907 {
908 input_t in;
909 hash_t *h = hash_create(HASHCOUNT_T_MAX, 0, 0);
910 hnode_t *hn;
911 hscan_t hs;
912 char *tok1, *tok2, *val;
913 const char *key;
914 int prompt = 0;
915
916 char *help =
917 "a <key> <val> add value to hash table\n"
918 "d <key> delete value from hash table\n"
919 "l <key> lookup value in hash table\n"
920 "n show size of hash table\n"
921 "c show number of entries\n"
922 "t dump whole hash table\n"
923 "+ increase hash table (private func)\n"
924 "- decrease hash table (private func)\n"
925 "b print hash_t_bit value\n"
926 "p turn prompt on\n"
927 "s switch to non-functioning allocator\n"
928 "q quit";
929
930 if (!h)
931 puts("hash_create failed");
932
933 for (;;) {
934 if (prompt)
935 putchar('>');
936 fflush(stdout);
937
938 if (!fgets(in, sizeof(input_t), stdin))
939 break;
940
941 switch(in[0]) {
942 case '?':
943 puts(help);
944 break;
945 case 'b':
946 printf("%d\n", hash_val_t_bit);
947 break;
948 case 'a':
949 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) {
950 puts("what?");
951 break;
952 }
953 key = dupstring(tok1);
954 val = dupstring(tok2);
955
956 if (!key || !val) {
957 puts("out of memory");
958 free((void *) key);
959 free(val);
960 }
961
962 if (!hash_alloc_insert(h, key, val)) {
963 puts("hash_alloc_insert failed");
964 free((void *) key);
965 free(val);
966 break;
967 }
968 break;
969 case 'd':
970 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
971 puts("what?");
972 break;
973 }
974 hn = hash_lookup(h, tok1);
975 if (!hn) {
976 puts("hash_lookup failed");
977 break;
978 }
979 val = hnode_get(hn);
980 key = hnode_getkey(hn);
981 hash_scan_delfree(h, hn);
982 free((void *) key);
983 free(val);
984 break;
985 case 'l':
986 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
987 puts("what?");
988 break;
989 }
990 hn = hash_lookup(h, tok1);
991 if (!hn) {
992 puts("hash_lookup failed");
993 break;
994 }
995 val = hnode_get(hn);
996 puts(val);
997 break;
998 case 'n':
999 printf("%lu\n", (unsigned long) hash_size(h));
1000 break;
1001 case 'c':
1002 printf("%lu\n", (unsigned long) hash_count(h));
1003 break;
1004 case 't':
1005 hash_scan_begin(&hs, h);
1006 while ((hn = hash_scan_next(&hs)))
1007 printf("%s\t%s\n", (char*) hnode_getkey(hn),
1008 (char*) hnode_get(hn));
1009 break;
1010 case '+':
1011 grow_table(h); /* private function */
1012 break;
1013 case '-':
1014 shrink_table(h); /* private function */
1015 break;
1016 case 'q':
1017 exit(0);
1018 break;
1019 case '\0':
1020 break;
1021 case 'p':
1022 prompt = 1;
1023 break;
1024 case 's':
1025 hash_set_allocator(h, new_node, del_node, NULL);
1026 break;
1027 default:
1028 putchar('?');
1029 putchar('\n');
1030 break;
1031 }
1032 }
1033
1034 return 0;
1035 }
1036
1037 #endif