5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2007 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
29 #include "silchashtable.h"
31 /* Define to 1 if you want hash table debug enabled */
32 #define SILC_HASH_TABLE_DEBUG 0
34 #if SILC_HASH_TABLE_DEBUG == 1
35 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
37 #define SILC_HT_DEBUG(fmt)
40 /* Default size of the hash table (index to prime table) */
41 #define SILC_HASH_TABLE_SIZE 2
43 /* Produce the index by hashing the key */
44 #define SILC_HASH_TABLE_HASH(f, c) \
45 ((f)(key, (c)) % primesize[ht->table_size])
47 /* Check whether need to rehash */
48 #define SILC_HASH_REHASH_INC \
49 (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
50 #define SILC_HASH_REHASH_DEC \
51 (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
52 ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
54 /* One entry in the hash table. Includes the key and the associated
55 context. The `next' pointer is non-NULL if two (or more) different
56 keys hashed to same value. The pointer is the pointer to the next
58 typedef struct SilcHashTableEntryStruct {
61 struct SilcHashTableEntryStruct *next;
62 } *SilcHashTableEntry;
65 struct SilcHashTableStruct {
67 SilcHashTableEntry *table;
68 SilcUInt32 table_size;
69 SilcUInt32 entry_count;
70 SilcHashFunction hash;
71 SilcHashCompare compare;
72 SilcHashDestructor destructor;
73 void *hash_user_context;
74 void *compare_user_context;
75 void *destructor_user_context;
76 unsigned int auto_rehash : 1;
79 /* Prime sizes for the hash table. The size of the table will always
81 const SilcUInt32 primesize[] =
83 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
84 1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
85 14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
86 131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
87 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
90 /* Find appropriate size for the hash table. The size will be a prime. */
92 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
96 for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); i++)
97 if (primesize[i] >= size) {
99 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
104 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
105 return primesize[i - 1];
108 /* Internal routine to find entry in the hash table by `key'. Returns
109 the previous entry (if exists) as well. */
111 static inline SilcHashTableEntry *
112 silc_hash_table_find_internal(SilcHashTable ht, void *key,
113 SilcHashTableEntry *prev_entry,
114 SilcHashFunction hash, void *hash_user_context,
115 SilcHashCompare compare,
116 void *compare_user_context)
118 SilcHashTableEntry *entry, prev = NULL;
119 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
121 SILC_HT_DEBUG(("index %d key %p", i, key));
123 entry = &ht->table[i];
125 while (*entry && !compare((*entry)->key, key, compare_user_context)) {
127 entry = &(*entry)->next;
130 while (*entry && (*entry)->key != key) {
132 entry = &(*entry)->next;
140 /* Internal routine to find entry in the hash table by `key' and `context'.
141 Returns the previous entry (if exists) as well to `prev_entry'. */
143 static inline SilcHashTableEntry *
144 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
146 SilcHashTableEntry *prev_entry,
147 SilcHashFunction hash,
148 void *hash_user_context,
149 SilcHashCompare compare,
150 void *compare_user_context)
152 SilcHashTableEntry *entry, prev = NULL;
153 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
155 SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
157 entry = &ht->table[i];
160 if (compare((*entry)->key, key, compare_user_context) &&
161 (*entry)->context == context)
164 entry = &(*entry)->next;
168 if ((*entry)->key == key && (*entry)->context == context)
171 entry = &(*entry)->next;
180 /* Internal routine to find entry in the hash table by `key'. */
182 static inline SilcHashTableEntry *
183 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
184 SilcHashFunction hash,
185 void *hash_user_context,
186 SilcHashCompare compare,
187 void *compare_user_context)
189 SilcHashTableEntry *entry;
190 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
192 SILC_HT_DEBUG(("index %d key %p", i, key));
194 entry = &ht->table[i];
196 while (*entry && !compare((*entry)->key, key, compare_user_context))
197 entry = &(*entry)->next;
199 while (*entry && (*entry)->key != key)
200 entry = &(*entry)->next;
206 /* Internal routine to find all keys by `key'. This may return multiple
207 entries if multiple entries with same key exists. With specific
208 hash and comparison functions. */
211 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
212 SilcHashFunction hash,
213 void *hash_user_context,
214 SilcHashCompare compare,
215 void *compare_user_context,
216 SilcHashForeach foreach,
217 void *foreach_user_context)
219 SilcHashTableEntry e, tmp;
220 SilcBool auto_rehash, found = FALSE;
221 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
223 SILC_HT_DEBUG(("index %d key %p", i, key));
225 /* Disallow auto rehashing while going through the table since we call
226 the `foreach' function which could alter the table. */
227 auto_rehash = ht->auto_rehash;
228 ht->auto_rehash = FALSE;
234 if (compare(e->key, key, compare_user_context)) {
236 foreach(e->key, e->context, foreach_user_context);
245 foreach(e->key, e->context, foreach_user_context);
251 /* If nothing was found call with NULL context the callback */
253 foreach(key, NULL, foreach_user_context);
255 ht->auto_rehash = auto_rehash;
258 /* Internal routine to add new key to the hash table */
260 static inline SilcBool
261 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
262 SilcHashFunction hash,
263 void *hash_user_context)
265 SilcHashTableEntry *entry;
266 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
268 SILC_HT_DEBUG(("index %d key %p", i, key));
270 entry = &ht->table[i];
272 /* The entry exists already. We have a collision, add it to the
273 list to avoid collision. */
274 SilcHashTableEntry e, tmp;
283 SILC_HT_DEBUG(("Collision; adding new key to list"));
285 e->next = silc_scalloc(ht->stack, 1, sizeof(*e->next));
289 e->next->context = context;
293 SILC_HT_DEBUG(("New key"));
294 *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
298 (*entry)->context = context;
302 if (SILC_HASH_REHASH_INC)
303 silc_hash_table_rehash(ht, 0);
308 /* Internal routine to replace old key with new one (if it exists) */
310 static inline SilcBool
311 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
312 SilcHashFunction hash,
313 void *hash_user_context)
315 SilcHashTableEntry *entry;
316 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
318 SILC_HT_DEBUG(("index %d key %p", i, key));
320 entry = &ht->table[i];
322 /* The entry exists already. We have a collision, replace the old
325 ht->destructor((*entry)->key, (*entry)->context,
326 ht->destructor_user_context);
329 *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
336 (*entry)->context = context;
338 if (SILC_HASH_REHASH_INC)
339 silc_hash_table_rehash(ht, 0);
344 /* Allocates new hash table and returns it. If the `table_size' is not
345 zero then the hash table size is the size provided. If zero then the
346 default size will be used. Note that if the `table_size' is provided
347 it should be a prime. The `hash', `compare' and `destructor' are
348 the hash function, the key comparison function and key and context
349 destructor function, respectively. The `hash' is mandatory, the others
352 SilcHashTable silc_hash_table_alloc(SilcStack stack,
353 SilcUInt32 table_size,
354 SilcHashFunction hash,
355 void *hash_user_context,
356 SilcHashCompare compare,
357 void *compare_user_context,
358 SilcHashDestructor destructor,
359 void *destructor_user_context,
360 SilcBool auto_rehash)
363 SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
366 silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
371 stack = silc_stack_alloc(0, stack);
373 ht = silc_scalloc(stack, 1, sizeof(*ht));
375 silc_stack_free(stack);
378 ht->table = silc_scalloc(stack,
379 table_size ? silc_hash_table_primesize(table_size,
381 primesize[SILC_HASH_TABLE_SIZE],
384 silc_stack_free(stack);
385 silc_sfree(stack, ht);
389 ht->table_size = size_index;
391 ht->compare = compare;
392 ht->destructor = destructor;
393 ht->hash_user_context = hash_user_context;
394 ht->compare_user_context = compare_user_context;
395 ht->destructor_user_context = destructor_user_context;
396 ht->auto_rehash = auto_rehash;
401 /* Frees the hash table. The destructor function provided in the
402 silc_hash_table_alloc will be called for all keys in the hash table. */
404 void silc_hash_table_free(SilcHashTable ht)
406 SilcStack stack = ht->stack;
407 SilcHashTableEntry e, tmp;
410 for (i = 0; i < primesize[ht->table_size]; i++) {
414 ht->destructor(e->key, e->context, ht->destructor_user_context);
417 silc_sfree(stack, tmp);
421 silc_sfree(stack, ht->table);
422 silc_sfree(stack, ht);
423 silc_stack_free(stack);
426 /* Returns the size of the hash table */
428 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
430 return primesize[ht->table_size];
433 /* Returns the number of the entires in the hash table. If there is more
434 entries in the table thatn the size of the hash table calling the
435 silc_hash_table_rehash is recommended. */
437 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
439 return ht->entry_count;
442 /* Adds new entry to the hash table. The `key' is hashed using the
443 hash function and the both `key' and `context' will be saved to the
444 hash table. This function quarantees that the entry is always added
445 to the hash table reliably (it is collision resistant). */
447 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context)
449 return silc_hash_table_add_internal(ht, key, context, ht->hash,
450 ht->hash_user_context);
453 /* Same as above but with specific hash function and user context. */
455 SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
456 SilcHashFunction hash,
457 void *hash_user_context)
459 return silc_hash_table_add_internal(ht, key, context,
460 hash, hash_user_context);
463 /* Same as above but if the `key' already exists in the hash table
464 the old key and the old context will be replace with the `key' and
465 the `context. The destructor function will be called for the
466 replaced key and context. */
468 SilcBool silc_hash_table_set(SilcHashTable ht, void *key, void *context)
470 return silc_hash_table_replace_internal(ht, key, context, ht->hash,
471 ht->hash_user_context);
474 /* Same as above but with specific hash function. */
476 SilcBool silc_hash_table_set_ext(SilcHashTable ht, void *key,
478 SilcHashFunction hash,
479 void *hash_user_context)
481 return silc_hash_table_replace_internal(ht, key, context,
482 hash, hash_user_context);
485 /* Removes the entry from the hash table by the provided `key'. This will
486 call the destructor funtion for the found entry. Return TRUE if the
487 entry was removed successfully and FALSE otherwise. */
489 SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
491 SilcHashTableEntry *entry, prev, e;
493 entry = silc_hash_table_find_internal(ht, key, &prev,
494 ht->hash, ht->hash_user_context,
495 ht->compare, ht->compare_user_context);
496 if (*entry == NULL) {
497 silc_set_errno(SILC_ERR_NOT_FOUND);
503 if (!prev && e->next)
505 if (!prev && e->next == NULL)
510 prev->next = e->next;
513 ht->destructor(e->key, e->context, ht->destructor_user_context);
514 silc_sfree(ht->stack, e);
518 if (SILC_HASH_REHASH_DEC)
519 silc_hash_table_rehash(ht, 0);
524 /* Same as above but with specific hash and compare functions. */
526 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
527 SilcHashFunction hash,
528 void *hash_user_context,
529 SilcHashCompare compare,
530 void *compare_user_context,
531 SilcHashDestructor destructor,
532 void *destructor_user_context)
534 SilcHashTableEntry *entry, prev, e;
536 entry = silc_hash_table_find_internal(ht, key, &prev,
537 hash ? hash : ht->hash,
538 hash_user_context ? hash_user_context :
539 ht->hash_user_context,
540 compare ? compare : ht->compare,
541 compare_user_context ?
542 compare_user_context :
543 ht->compare_user_context);
544 if (*entry == NULL) {
545 silc_set_errno(SILC_ERR_NOT_FOUND);
551 if (!prev && e->next)
553 if (!prev && e->next == NULL)
558 prev->next = e->next;
561 destructor(e->key, e->context, destructor_user_context);
564 ht->destructor(e->key, e->context, ht->destructor_user_context);
566 silc_sfree(ht->stack, e);
570 if (SILC_HASH_REHASH_DEC)
571 silc_hash_table_rehash(ht, 0);
576 /* Same as above but verifies that the context associated with the `key'
577 matches the `context'. This is handy to use with hash tables that may
578 have duplicate keys. In that case the `context' may be used to check
579 whether the correct entry is being deleted. */
581 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
584 SilcHashTableEntry *entry, prev, e;
586 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
588 ht->hash_user_context,
590 ht->compare_user_context);
591 if (*entry == NULL) {
592 silc_set_errno(SILC_ERR_NOT_FOUND);
598 if (!prev && e->next)
600 if (!prev && e->next == NULL)
605 prev->next = e->next;
608 ht->destructor(e->key, e->context, ht->destructor_user_context);
609 silc_sfree(ht->stack, e);
613 if (SILC_HASH_REHASH_DEC)
614 silc_hash_table_rehash(ht, 0);
619 /* Same as above but with specific hash and compare functions. */
621 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
623 SilcHashFunction hash,
624 void *hash_user_context,
625 SilcHashCompare compare,
626 void *compare_user_context,
627 SilcHashDestructor destructor,
628 void *destructor_user_context)
630 SilcHashTableEntry *entry, prev, e;
632 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
633 hash ? hash : ht->hash,
636 ht->hash_user_context,
638 compare : ht->compare,
639 compare_user_context ?
640 compare_user_context :
641 ht->compare_user_context);
642 if (*entry == NULL) {
643 silc_set_errno(SILC_ERR_NOT_FOUND);
649 if (!prev && e->next)
651 if (!prev && e->next == NULL)
656 prev->next = e->next;
659 destructor(e->key, e->context, destructor_user_context);
662 ht->destructor(e->key, e->context, ht->destructor_user_context);
664 silc_sfree(ht->stack, e);
668 if (SILC_HASH_REHASH_DEC)
669 silc_hash_table_rehash(ht, 0);
674 /* Finds the entry in the hash table by the provided `key' as fast as
675 possible. Return TRUE if the entry was found and FALSE otherwise.
676 The found entry is returned to the `ret_key' and `ret_context',
677 respectively. If the `ret_key and `ret_context' are NULL then this
678 maybe used only to check whether given key exists in the table. */
680 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
681 void **ret_key, void **ret_context)
683 return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
684 NULL, NULL, NULL, NULL);
687 /* Same as above but with specified hash and comparison functions. */
689 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
690 void **ret_key, void **ret_context,
691 SilcHashFunction hash,
692 void *hash_user_context,
693 SilcHashCompare compare,
694 void *compare_user_context)
696 SilcHashTableEntry *entry;
698 entry = silc_hash_table_find_internal_simple(ht, key,
699 hash ? hash : ht->hash,
702 ht->hash_user_context,
705 compare_user_context ?
706 compare_user_context :
707 ht->compare_user_context);
708 if (*entry == NULL) {
709 silc_set_errno(SILC_ERR_NOT_FOUND);
714 *ret_key = (*entry)->key;
716 *ret_context = (*entry)->context;
721 /* Same as silc_hash_table_find but finds with specific context. */
723 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
724 void *context, void **ret_key)
726 return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
727 NULL, NULL, NULL, NULL);
730 /* Same as above but with specified hash and comparison functions. */
732 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
733 void *context, void **ret_key,
734 SilcHashFunction hash,
735 void *hash_user_context,
736 SilcHashCompare compare,
737 void *compare_user_context)
739 SilcHashTableEntry *entry;
741 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
742 hash ? hash : ht->hash,
745 ht->hash_user_context,
748 compare_user_context ?
749 compare_user_context :
750 ht->compare_user_context);
751 if (!entry || !(*entry)) {
752 silc_set_errno(SILC_ERR_NOT_FOUND);
757 *ret_key = (*entry)->key;
762 /* As the hash table is collision resistant it is possible to save duplicate
763 keys to the hash table. This function can be used to find all keys
764 and contexts from the hash table that are found using the `key'. The
765 `foreach' is called for every found key. */
767 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
768 SilcHashForeach foreach, void *user_context)
770 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
771 ht->compare, ht->compare_user_context,
772 foreach, user_context);
775 /* Same as above but with specific hash and comparison functions. */
777 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
778 SilcHashFunction hash,
779 void *hash_user_context,
780 SilcHashCompare compare,
781 void *compare_user_context,
782 SilcHashForeach foreach,
783 void *foreach_user_context)
785 silc_hash_table_find_internal_all(ht, key,
786 hash ? hash : ht->hash,
789 ht->hash_user_context,
792 compare_user_context ?
793 compare_user_context :
794 ht->compare_user_context,
795 foreach, foreach_user_context);
798 /* Traverse all entrys in the hash table and call the `foreach' for
799 every entry with the `user_context' context. */
801 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
804 SilcHashTableEntry e, tmp;
806 SilcBool auto_rehash;
811 auto_rehash = ht->auto_rehash;
812 ht->auto_rehash = FALSE;
813 for (i = 0; i < primesize[ht->table_size]; i++) {
816 /* Entry may become invalid inside the `foreach' */
818 foreach(e->key, e->context, user_context);
822 ht->auto_rehash = auto_rehash;
825 /* Rehashs the hash table. The size of the new hash table is provided
826 as `new_size'. If the `new_size' is zero then this routine will make
827 the new table of a suitable size. Note that this operation may be
830 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
833 SilcHashTableEntry *table, e, tmp;
834 SilcUInt32 table_size, size_index;
835 SilcBool auto_rehash;
837 SILC_HT_DEBUG(("Start"));
840 silc_hash_table_primesize(new_size, &size_index);
842 silc_hash_table_primesize(ht->entry_count, &size_index);
844 if (size_index == ht->table_size)
847 SILC_HT_DEBUG(("Rehashing"));
849 /* Take old hash table */
851 table_size = ht->table_size;
852 auto_rehash = ht->auto_rehash;
853 ht->auto_rehash = FALSE;
855 /* Allocate new table */
856 ht->table = silc_scalloc(ht->stack,
857 primesize[size_index], sizeof(*ht->table));
860 ht->table_size = size_index;
864 for (i = 0; i < primesize[table_size]; i++) {
867 silc_hash_table_add(ht, e->key, e->context);
871 /* Remove old entry */
872 silc_sfree(ht->stack, tmp);
876 ht->auto_rehash = auto_rehash;
878 /* Remove old table */
879 silc_sfree(ht->stack, table);
882 /* Same as above but with specific hash function. */
884 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
885 SilcHashFunction hash,
886 void *hash_user_context)
889 SilcHashTableEntry *table, e, tmp;
890 SilcUInt32 table_size, size_index;
891 SilcBool auto_rehash;
893 SILC_HT_DEBUG(("Start"));
896 silc_hash_table_primesize(new_size, &size_index);
898 silc_hash_table_primesize(ht->entry_count, &size_index);
900 if (size_index == ht->table_size)
903 SILC_HT_DEBUG(("Rehashing"));
905 /* Take old hash table */
907 table_size = ht->table_size;
908 auto_rehash = ht->auto_rehash;
909 ht->auto_rehash = FALSE;
911 /* Allocate new table */
912 ht->table = silc_scalloc(ht->stack,
913 primesize[size_index], sizeof(*ht->table));
916 ht->table_size = size_index;
920 for (i = 0; i < primesize[table_size]; i++) {
923 silc_hash_table_add_ext(ht, e->key, e->context, hash,
928 /* Remove old entry */
929 silc_sfree(ht->stack, tmp);
933 ht->auto_rehash = auto_rehash;
935 /* Remove old table */
936 silc_sfree(ht->stack, table);
939 /* Prepares the `htl' list structure sent as argument to be used in the
940 hash table traversing with the silc_hash_table_get. Usage:
941 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
943 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
948 htl->auto_rehash = ht->auto_rehash;
950 /* Disallow rehashing of the table while traversing the table */
951 ht->auto_rehash = FALSE;
954 /* Resets the `htl' SilcHashTableList. */
956 void silc_hash_table_list_reset(SilcHashTableList *htl)
958 /* Set back the original auto rehash value to the table */
959 htl->ht->auto_rehash = htl->auto_rehash;
962 /* Returns always the next entry in the hash table into the `key' and
963 `context' and TRUE. If this returns FALSE then there are no anymore
964 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
966 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
969 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
971 if (!htl->ht->entry_count)
974 while (!entry && htl->index < primesize[htl->ht->table_size]) {
975 entry = htl->ht->table[htl->index];
982 htl->entry = entry->next;
987 *context = entry->context;
992 /**************************** Utility functions *****************************/
994 /* Case sensitive hashing */
996 SilcUInt32 silc_hash_string(void *key, void *user_context)
998 char *s = (char *)key;
1001 while (*s != '\0') {
1014 /* Case-insensitive hashing */
1016 SilcUInt32 silc_hash_string_case(void *key, void *user_context)
1018 char *s = (char *)key;
1021 while (*s != '\0') {
1022 h += tolower((int)*s);
1035 /* Hash UTF-8 string */
1037 SilcUInt32 silc_hash_utf8_string(void *key, void *user_context)
1039 char *s = (char *)key;
1042 while (*s != '\0') {
1055 /* Basic hash function to hash integers. */
1057 SilcUInt32 silc_hash_uint(void *key, void *user_context)
1059 return SILC_PTR_TO_32(key);
1062 /* Basic hash funtion to hash pointers. */
1064 SilcUInt32 silc_hash_ptr(void *key, void *user_context)
1066 return SILC_PTR_TO_32(key);
1069 /* Hash binary data. The `user_context' is the data length. */
1071 SilcUInt32 silc_hash_data(void *key, void *user_context)
1073 SilcUInt32 len = SILC_PTR_TO_32(user_context), h, i;
1074 unsigned char *data = (char *)key;
1076 h = (data[0] * data[len - 1] + 1) * len;
1078 for (i = 0; i < len; i++) {
1091 /* Compares two strings. */
1093 SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context)
1095 return !strcmp((char *)key1, (char *)key2);
1098 /* Compares two strings, ignores case. */
1100 SilcBool silc_hash_string_case_compare(void *key1, void *key2,
1103 return !strcasecmp((char *)key1, (char *)key2);
1106 /* Compares binary data. */
1108 SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context)
1110 SilcUInt32 len = SILC_PTR_TO_32(user_context);
1111 return !memcmp(key1, key2, len);
1114 /* Compares UTF-8 string. */
1116 SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context)
1118 int l1 = strlen((char *)key1);
1119 int l2 = strlen((char *)key2);
1122 return !memcmp(key1, key2, l2);