5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2008 Pekka Riikonen
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; version 2 of the License.
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.
19 /* Implementation of collision resistant hash table. This is a hash table
20 that provides a reliable (what you add stays there, and duplicate keys
21 are allowed) with as fast reference to the key as possible. If duplicate
22 keys are a lot in the hash table the lookup gets slower of course.
23 However, this is reliable and no data is lost at any point. If you know
24 that you never have duplicate keys then this is as fast as any simple
27 #include "silcruntime.h"
29 /* Define to 1 if you want hash table debug enabled */
30 #define SILC_HASH_TABLE_DEBUG 0
32 #if SILC_HASH_TABLE_DEBUG == 1
33 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
35 #define SILC_HT_DEBUG(fmt)
38 /* Default size of the hash table (index to prime table) */
39 #define SILC_HASH_TABLE_SIZE 2
41 /* Produce the index by hashing the key */
42 #define SILC_HASH_TABLE_HASH(f, c) \
43 ((f)(key, (c)) % primesize[ht->table_size])
45 /* Check whether need to rehash */
46 #define SILC_HASH_REHASH_INC \
47 (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
48 #define SILC_HASH_REHASH_DEC \
49 (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
50 ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
52 /* One entry in the hash table. Includes the key and the associated
53 context. The `next' pointer is non-NULL if two (or more) different
54 keys hashed to same value. The pointer is the pointer to the next
56 typedef struct SilcHashTableEntryStruct {
59 struct SilcHashTableEntryStruct *next;
60 } *SilcHashTableEntry;
63 struct SilcHashTableStruct {
65 SilcHashTableEntry *table;
66 SilcUInt32 table_size;
67 SilcUInt32 entry_count;
68 SilcHashFunction hash;
69 SilcHashCompare compare;
70 SilcHashDestructor destructor;
71 void *hash_user_context;
72 void *compare_user_context;
73 void *destructor_user_context;
74 unsigned int auto_rehash : 1;
77 /* Prime sizes for the hash table. The size of the table will always
79 const SilcUInt32 primesize[] =
81 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
82 1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
83 14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
84 131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
85 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
88 /* Find appropriate size for the hash table. The size will be a prime. */
90 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
94 for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); i++)
95 if (primesize[i] >= size) {
97 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
102 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
103 return primesize[i - 1];
106 /* Internal routine to find entry in the hash table by `key'. Returns
107 the previous entry (if exists) as well. */
109 static inline SilcHashTableEntry *
110 silc_hash_table_find_internal(SilcHashTable ht, void *key,
111 SilcHashTableEntry *prev_entry,
112 SilcHashFunction hash, void *hash_user_context,
113 SilcHashCompare compare,
114 void *compare_user_context)
116 SilcHashTableEntry *entry, prev = NULL;
117 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
119 SILC_HT_DEBUG(("index %d key %p", i, key));
121 entry = &ht->table[i];
123 while (*entry && !compare((*entry)->key, key, compare_user_context)) {
125 entry = &(*entry)->next;
128 while (*entry && (*entry)->key != key) {
130 entry = &(*entry)->next;
138 /* Internal routine to find entry in the hash table by `key' and `context'.
139 Returns the previous entry (if exists) as well to `prev_entry'. */
141 static inline SilcHashTableEntry *
142 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
144 SilcHashTableEntry *prev_entry,
145 SilcHashFunction hash,
146 void *hash_user_context,
147 SilcHashCompare compare,
148 void *compare_user_context)
150 SilcHashTableEntry *entry, prev = NULL;
151 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
153 SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
155 entry = &ht->table[i];
158 if (compare((*entry)->key, key, compare_user_context) &&
159 (*entry)->context == context)
162 entry = &(*entry)->next;
166 if ((*entry)->key == key && (*entry)->context == context)
169 entry = &(*entry)->next;
178 /* Internal routine to find entry in the hash table by `key'. */
180 static inline SilcHashTableEntry *
181 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
182 SilcHashFunction hash,
183 void *hash_user_context,
184 SilcHashCompare compare,
185 void *compare_user_context)
187 SilcHashTableEntry *entry;
188 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
190 SILC_HT_DEBUG(("index %d key %p", i, key));
192 entry = &ht->table[i];
194 while (*entry && !compare((*entry)->key, key, compare_user_context))
195 entry = &(*entry)->next;
197 while (*entry && (*entry)->key != key)
198 entry = &(*entry)->next;
204 /* Internal routine to find all keys by `key'. This may return multiple
205 entries if multiple entries with same key exists. With specific
206 hash and comparison functions. */
209 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
210 SilcHashFunction hash,
211 void *hash_user_context,
212 SilcHashCompare compare,
213 void *compare_user_context,
214 SilcHashForeach foreach,
215 void *foreach_user_context)
217 SilcHashTableEntry e, tmp;
218 SilcBool auto_rehash, found = FALSE;
219 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
221 SILC_HT_DEBUG(("index %d key %p", i, key));
223 /* Disallow auto rehashing while going through the table since we call
224 the `foreach' function which could alter the table. */
225 auto_rehash = ht->auto_rehash;
226 ht->auto_rehash = FALSE;
232 if (compare(e->key, key, compare_user_context)) {
234 foreach(e->key, e->context, foreach_user_context);
243 foreach(e->key, e->context, foreach_user_context);
249 /* If nothing was found call with NULL context the callback */
251 foreach(key, NULL, foreach_user_context);
253 ht->auto_rehash = auto_rehash;
256 /* Internal routine to add new key to the hash table */
258 static inline SilcBool
259 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
260 SilcHashFunction hash,
261 void *hash_user_context)
263 SilcHashTableEntry *entry;
264 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
266 SILC_HT_DEBUG(("index %d key %p", i, key));
268 entry = &ht->table[i];
270 /* The entry exists already. We have a collision, add it to the
271 list to avoid collision. */
272 SilcHashTableEntry e, tmp;
281 SILC_HT_DEBUG(("Collision; adding new key to list"));
283 e->next = silc_scalloc(ht->stack, 1, sizeof(*e->next));
287 e->next->context = context;
291 SILC_HT_DEBUG(("New key"));
292 *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
296 (*entry)->context = context;
300 if (SILC_HASH_REHASH_INC)
301 silc_hash_table_rehash(ht, 0);
306 /* Internal routine to replace old key with new one (if it exists) */
308 static inline SilcBool
309 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
310 SilcHashFunction hash,
311 void *hash_user_context)
313 SilcHashTableEntry *entry;
314 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
316 SILC_HT_DEBUG(("index %d key %p", i, key));
318 entry = &ht->table[i];
320 /* The entry exists already. We have a collision, replace the old
323 ht->destructor((*entry)->key, (*entry)->context,
324 ht->destructor_user_context);
327 *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
334 (*entry)->context = context;
336 if (SILC_HASH_REHASH_INC)
337 silc_hash_table_rehash(ht, 0);
342 /* Allocates new hash table and returns it. If the `table_size' is not
343 zero then the hash table size is the size provided. If zero then the
344 default size will be used. Note that if the `table_size' is provided
345 it should be a prime. The `hash', `compare' and `destructor' are
346 the hash function, the key comparison function and key and context
347 destructor function, respectively. The `hash' is mandatory, the others
350 SilcHashTable silc_hash_table_alloc(SilcStack stack,
351 SilcUInt32 table_size,
352 SilcHashFunction hash,
353 void *hash_user_context,
354 SilcHashCompare compare,
355 void *compare_user_context,
356 SilcHashDestructor destructor,
357 void *destructor_user_context,
358 SilcBool auto_rehash)
361 SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
364 silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
369 stack = silc_stack_alloc(0, stack);
371 ht = silc_scalloc(stack, 1, sizeof(*ht));
373 silc_stack_free(stack);
376 ht->table = silc_scalloc(stack,
377 table_size ? silc_hash_table_primesize(table_size,
379 primesize[SILC_HASH_TABLE_SIZE],
382 silc_stack_free(stack);
383 silc_sfree(stack, ht);
387 ht->table_size = size_index;
389 ht->compare = compare;
390 ht->destructor = destructor;
391 ht->hash_user_context = hash_user_context;
392 ht->compare_user_context = compare_user_context;
393 ht->destructor_user_context = destructor_user_context;
394 ht->auto_rehash = auto_rehash;
399 /* Frees the hash table. The destructor function provided in the
400 silc_hash_table_alloc will be called for all keys in the hash table. */
402 void silc_hash_table_free(SilcHashTable ht)
404 SilcStack stack = ht->stack;
405 SilcHashTableEntry e, tmp;
408 for (i = 0; i < primesize[ht->table_size]; i++) {
412 ht->destructor(e->key, e->context, ht->destructor_user_context);
415 silc_sfree(stack, tmp);
419 silc_sfree(stack, ht->table);
420 silc_sfree(stack, ht);
421 silc_stack_free(stack);
424 /* Returns the size of the hash table */
426 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
428 return primesize[ht->table_size];
431 /* Returns the number of the entires in the hash table. If there is more
432 entries in the table thatn the size of the hash table calling the
433 silc_hash_table_rehash is recommended. */
435 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
437 return ht->entry_count;
440 /* Adds new entry to the hash table. The `key' is hashed using the
441 hash function and the both `key' and `context' will be saved to the
442 hash table. This function quarantees that the entry is always added
443 to the hash table reliably (it is collision resistant). */
445 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context)
447 return silc_hash_table_add_internal(ht, key, context, ht->hash,
448 ht->hash_user_context);
451 /* Same as above but with specific hash function and user context. */
453 SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
454 SilcHashFunction hash,
455 void *hash_user_context)
457 return silc_hash_table_add_internal(ht, key, context,
458 hash, hash_user_context);
461 /* Same as above but if the `key' already exists in the hash table
462 the old key and the old context will be replace with the `key' and
463 the `context. The destructor function will be called for the
464 replaced key and context. */
466 SilcBool silc_hash_table_set(SilcHashTable ht, void *key, void *context)
468 return silc_hash_table_replace_internal(ht, key, context, ht->hash,
469 ht->hash_user_context);
472 /* Same as above but with specific hash function. */
474 SilcBool silc_hash_table_set_ext(SilcHashTable ht, void *key,
476 SilcHashFunction hash,
477 void *hash_user_context)
479 return silc_hash_table_replace_internal(ht, key, context,
480 hash, hash_user_context);
483 /* Removes the entry from the hash table by the provided `key'. This will
484 call the destructor funtion for the found entry. Return TRUE if the
485 entry was removed successfully and FALSE otherwise. */
487 SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
489 SilcHashTableEntry *entry, prev, e;
491 entry = silc_hash_table_find_internal(ht, key, &prev,
492 ht->hash, ht->hash_user_context,
493 ht->compare, ht->compare_user_context);
494 if (*entry == NULL) {
495 silc_set_errno(SILC_ERR_NOT_FOUND);
501 if (!prev && e->next)
503 if (!prev && e->next == NULL)
508 prev->next = e->next;
511 ht->destructor(e->key, e->context, ht->destructor_user_context);
512 silc_sfree(ht->stack, e);
516 if (SILC_HASH_REHASH_DEC)
517 silc_hash_table_rehash(ht, 0);
522 /* Same as above but with specific hash and compare functions. */
524 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
525 SilcHashFunction hash,
526 void *hash_user_context,
527 SilcHashCompare compare,
528 void *compare_user_context,
529 SilcHashDestructor destructor,
530 void *destructor_user_context)
532 SilcHashTableEntry *entry, prev, e;
534 entry = silc_hash_table_find_internal(ht, key, &prev,
535 hash ? hash : ht->hash,
536 hash_user_context ? hash_user_context :
537 ht->hash_user_context,
538 compare ? compare : ht->compare,
539 compare_user_context ?
540 compare_user_context :
541 ht->compare_user_context);
542 if (*entry == NULL) {
543 silc_set_errno(SILC_ERR_NOT_FOUND);
549 if (!prev && e->next)
551 if (!prev && e->next == NULL)
556 prev->next = e->next;
559 destructor(e->key, e->context, destructor_user_context);
562 ht->destructor(e->key, e->context, ht->destructor_user_context);
564 silc_sfree(ht->stack, e);
568 if (SILC_HASH_REHASH_DEC)
569 silc_hash_table_rehash(ht, 0);
574 /* Same as above but verifies that the context associated with the `key'
575 matches the `context'. This is handy to use with hash tables that may
576 have duplicate keys. In that case the `context' may be used to check
577 whether the correct entry is being deleted. */
579 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
582 SilcHashTableEntry *entry, prev, e;
584 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
586 ht->hash_user_context,
588 ht->compare_user_context);
589 if (*entry == NULL) {
590 silc_set_errno(SILC_ERR_NOT_FOUND);
596 if (!prev && e->next)
598 if (!prev && e->next == NULL)
603 prev->next = e->next;
606 ht->destructor(e->key, e->context, ht->destructor_user_context);
607 silc_sfree(ht->stack, e);
611 if (SILC_HASH_REHASH_DEC)
612 silc_hash_table_rehash(ht, 0);
617 /* Same as above but with specific hash and compare functions. */
619 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
621 SilcHashFunction hash,
622 void *hash_user_context,
623 SilcHashCompare compare,
624 void *compare_user_context,
625 SilcHashDestructor destructor,
626 void *destructor_user_context)
628 SilcHashTableEntry *entry, prev, e;
630 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
631 hash ? hash : ht->hash,
634 ht->hash_user_context,
636 compare : ht->compare,
637 compare_user_context ?
638 compare_user_context :
639 ht->compare_user_context);
640 if (*entry == NULL) {
641 silc_set_errno(SILC_ERR_NOT_FOUND);
647 if (!prev && e->next)
649 if (!prev && e->next == NULL)
654 prev->next = e->next;
657 destructor(e->key, e->context, destructor_user_context);
660 ht->destructor(e->key, e->context, ht->destructor_user_context);
662 silc_sfree(ht->stack, e);
666 if (SILC_HASH_REHASH_DEC)
667 silc_hash_table_rehash(ht, 0);
672 /* Finds the entry in the hash table by the provided `key' as fast as
673 possible. Return TRUE if the entry was found and FALSE otherwise.
674 The found entry is returned to the `ret_key' and `ret_context',
675 respectively. If the `ret_key and `ret_context' are NULL then this
676 maybe used only to check whether given key exists in the table. */
678 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
679 void **ret_key, void **ret_context)
681 return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
682 NULL, NULL, NULL, NULL);
685 /* Same as above but with specified hash and comparison functions. */
687 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
688 void **ret_key, void **ret_context,
689 SilcHashFunction hash,
690 void *hash_user_context,
691 SilcHashCompare compare,
692 void *compare_user_context)
694 SilcHashTableEntry *entry;
696 entry = silc_hash_table_find_internal_simple(ht, key,
697 hash ? hash : ht->hash,
700 ht->hash_user_context,
703 compare_user_context ?
704 compare_user_context :
705 ht->compare_user_context);
706 if (*entry == NULL) {
707 silc_set_errno(SILC_ERR_NOT_FOUND);
712 *ret_key = (*entry)->key;
714 *ret_context = (*entry)->context;
719 /* Same as silc_hash_table_find but finds with specific context. */
721 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
722 void *context, void **ret_key)
724 return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
725 NULL, NULL, NULL, NULL);
728 /* Same as above but with specified hash and comparison functions. */
730 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
731 void *context, void **ret_key,
732 SilcHashFunction hash,
733 void *hash_user_context,
734 SilcHashCompare compare,
735 void *compare_user_context)
737 SilcHashTableEntry *entry;
739 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
740 hash ? hash : ht->hash,
743 ht->hash_user_context,
746 compare_user_context ?
747 compare_user_context :
748 ht->compare_user_context);
749 if (!entry || !(*entry)) {
750 silc_set_errno(SILC_ERR_NOT_FOUND);
755 *ret_key = (*entry)->key;
760 /* As the hash table is collision resistant it is possible to save duplicate
761 keys to the hash table. This function can be used to find all keys
762 and contexts from the hash table that are found using the `key'. The
763 `foreach' is called for every found key. */
765 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
766 SilcHashForeach foreach, void *user_context)
768 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
769 ht->compare, ht->compare_user_context,
770 foreach, user_context);
773 /* Same as above but with specific hash and comparison functions. */
775 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
776 SilcHashFunction hash,
777 void *hash_user_context,
778 SilcHashCompare compare,
779 void *compare_user_context,
780 SilcHashForeach foreach,
781 void *foreach_user_context)
783 silc_hash_table_find_internal_all(ht, key,
784 hash ? hash : ht->hash,
787 ht->hash_user_context,
790 compare_user_context ?
791 compare_user_context :
792 ht->compare_user_context,
793 foreach, foreach_user_context);
796 /* Traverse all entrys in the hash table and call the `foreach' for
797 every entry with the `user_context' context. */
799 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
802 SilcHashTableEntry e, tmp;
804 SilcBool auto_rehash;
809 auto_rehash = ht->auto_rehash;
810 ht->auto_rehash = FALSE;
811 for (i = 0; i < primesize[ht->table_size]; i++) {
814 /* Entry may become invalid inside the `foreach' */
816 foreach(e->key, e->context, user_context);
820 ht->auto_rehash = auto_rehash;
823 /* Rehashs the hash table. The size of the new hash table is provided
824 as `new_size'. If the `new_size' is zero then this routine will make
825 the new table of a suitable size. Note that this operation may be
828 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
831 SilcHashTableEntry *table, e, tmp;
832 SilcUInt32 table_size, size_index;
833 SilcBool auto_rehash;
835 SILC_HT_DEBUG(("Start"));
838 silc_hash_table_primesize(new_size, &size_index);
840 silc_hash_table_primesize(ht->entry_count, &size_index);
842 if (size_index == ht->table_size)
845 SILC_HT_DEBUG(("Rehashing"));
847 /* Take old hash table */
849 table_size = ht->table_size;
850 auto_rehash = ht->auto_rehash;
851 ht->auto_rehash = FALSE;
853 /* Allocate new table */
854 ht->table = silc_scalloc(ht->stack,
855 primesize[size_index], sizeof(*ht->table));
858 ht->table_size = size_index;
862 for (i = 0; i < primesize[table_size]; i++) {
865 silc_hash_table_add(ht, e->key, e->context);
869 /* Remove old entry */
870 silc_sfree(ht->stack, tmp);
874 ht->auto_rehash = auto_rehash;
876 /* Remove old table */
877 silc_sfree(ht->stack, table);
880 /* Same as above but with specific hash function. */
882 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
883 SilcHashFunction hash,
884 void *hash_user_context)
887 SilcHashTableEntry *table, e, tmp;
888 SilcUInt32 table_size, size_index;
889 SilcBool auto_rehash;
891 SILC_HT_DEBUG(("Start"));
894 silc_hash_table_primesize(new_size, &size_index);
896 silc_hash_table_primesize(ht->entry_count, &size_index);
898 if (size_index == ht->table_size)
901 SILC_HT_DEBUG(("Rehashing"));
903 /* Take old hash table */
905 table_size = ht->table_size;
906 auto_rehash = ht->auto_rehash;
907 ht->auto_rehash = FALSE;
909 /* Allocate new table */
910 ht->table = silc_scalloc(ht->stack,
911 primesize[size_index], sizeof(*ht->table));
914 ht->table_size = size_index;
918 for (i = 0; i < primesize[table_size]; i++) {
921 silc_hash_table_add_ext(ht, e->key, e->context, hash,
926 /* Remove old entry */
927 silc_sfree(ht->stack, tmp);
931 ht->auto_rehash = auto_rehash;
933 /* Remove old table */
934 silc_sfree(ht->stack, table);
937 /* Prepares the `htl' list structure sent as argument to be used in the
938 hash table traversing with the silc_hash_table_get. Usage:
939 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
941 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
946 htl->auto_rehash = ht->auto_rehash;
948 /* Disallow rehashing of the table while traversing the table */
949 ht->auto_rehash = FALSE;
952 /* Resets the `htl' SilcHashTableList. */
954 void silc_hash_table_list_reset(SilcHashTableList *htl)
956 /* Set back the original auto rehash value to the table */
957 htl->ht->auto_rehash = htl->auto_rehash;
960 /* Returns always the next entry in the hash table into the `key' and
961 `context' and TRUE. If this returns FALSE then there are no anymore
962 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
964 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
967 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
969 if (!htl->ht->entry_count)
972 while (!entry && htl->index < primesize[htl->ht->table_size]) {
973 entry = htl->ht->table[htl->index];
980 htl->entry = entry->next;
985 *context = entry->context;
990 /**************************** Utility functions *****************************/
992 /* Case sensitive hashing */
994 SilcUInt32 silc_hash_string(void *key, void *user_context)
996 char *s = (char *)key;
1012 /* Case-insensitive hashing */
1014 SilcUInt32 silc_hash_string_case(void *key, void *user_context)
1016 char *s = (char *)key;
1019 while (*s != '\0') {
1020 h += tolower((int)*s);
1033 /* Hash UTF-8 string */
1035 SilcUInt32 silc_hash_utf8_string(void *key, void *user_context)
1037 char *s = (char *)key;
1040 while (*s != '\0') {
1053 /* Basic hash function to hash integers. */
1055 SilcUInt32 silc_hash_uint(void *key, void *user_context)
1057 return SILC_PTR_TO_32(key);
1060 /* Basic hash funtion to hash pointers. */
1062 SilcUInt32 silc_hash_ptr(void *key, void *user_context)
1064 return SILC_PTR_TO_32(key);
1067 /* Hash binary data. The `user_context' is the data length. */
1069 SilcUInt32 silc_hash_data(void *key, void *user_context)
1071 SilcUInt32 len = SILC_PTR_TO_32(user_context), h, i;
1072 unsigned char *data = (char *)key;
1074 h = (data[0] * data[len - 1] + 1) * len;
1076 for (i = 0; i < len; i++) {
1089 /* Compares two strings. */
1091 SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context)
1093 return !strcmp((char *)key1, (char *)key2);
1096 /* Compares two strings, ignores case. */
1098 SilcBool silc_hash_string_case_compare(void *key1, void *key2,
1101 return !strcasecmp((char *)key1, (char *)key2);
1104 /* Compares binary data. */
1106 SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context)
1108 SilcUInt32 len = SILC_PTR_TO_32(user_context);
1109 return !memcmp(key1, key2, len);
1112 /* Compares UTF-8 string. */
1114 SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context)
1116 int l1 = strlen((char *)key1);
1117 int l2 = strlen((char *)key2);
1120 return !memcmp(key1, key2, l2);
1123 /* Generic destructor */
1125 void silc_hash_destructor(void *key, void *context, void *user_context)