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;
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);
499 if (!prev && e->next)
501 if (!prev && e->next == NULL)
506 prev->next = e->next;
509 ht->destructor(e->key, e->context, ht->destructor_user_context);
510 silc_sfree(ht->stack, e);
514 if (SILC_HASH_REHASH_DEC)
515 silc_hash_table_rehash(ht, 0);
520 /* Same as above but with specific hash and compare functions. */
522 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
523 SilcHashFunction hash,
524 void *hash_user_context,
525 SilcHashCompare compare,
526 void *compare_user_context,
527 SilcHashDestructor destructor,
528 void *destructor_user_context)
530 SilcHashTableEntry *entry, prev, e;
532 entry = silc_hash_table_find_internal(ht, key, &prev,
533 hash ? hash : ht->hash,
534 hash_user_context ? hash_user_context :
535 ht->hash_user_context,
536 compare ? compare : ht->compare,
537 compare_user_context ?
538 compare_user_context :
539 ht->compare_user_context);
545 if (!prev && e->next)
547 if (!prev && e->next == NULL)
552 prev->next = e->next;
555 destructor(e->key, e->context, destructor_user_context);
558 ht->destructor(e->key, e->context, ht->destructor_user_context);
560 silc_sfree(ht->stack, e);
564 if (SILC_HASH_REHASH_DEC)
565 silc_hash_table_rehash(ht, 0);
570 /* Same as above but verifies that the context associated with the `key'
571 matches the `context'. This is handy to use with hash tables that may
572 have duplicate keys. In that case the `context' may be used to check
573 whether the correct entry is being deleted. */
575 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
578 SilcHashTableEntry *entry, prev, e;
580 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
582 ht->hash_user_context,
584 ht->compare_user_context);
590 if (!prev && e->next)
592 if (!prev && e->next == NULL)
597 prev->next = e->next;
600 ht->destructor(e->key, e->context, ht->destructor_user_context);
601 silc_sfree(ht->stack, e);
605 if (SILC_HASH_REHASH_DEC)
606 silc_hash_table_rehash(ht, 0);
611 /* Same as above but with specific hash and compare functions. */
613 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
615 SilcHashFunction hash,
616 void *hash_user_context,
617 SilcHashCompare compare,
618 void *compare_user_context,
619 SilcHashDestructor destructor,
620 void *destructor_user_context)
622 SilcHashTableEntry *entry, prev, e;
624 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
625 hash ? hash : ht->hash,
628 ht->hash_user_context,
630 compare : ht->compare,
631 compare_user_context ?
632 compare_user_context :
633 ht->compare_user_context);
639 if (!prev && e->next)
641 if (!prev && e->next == NULL)
646 prev->next = e->next;
649 destructor(e->key, e->context, destructor_user_context);
652 ht->destructor(e->key, e->context, ht->destructor_user_context);
654 silc_sfree(ht->stack, e);
658 if (SILC_HASH_REHASH_DEC)
659 silc_hash_table_rehash(ht, 0);
664 /* Finds the entry in the hash table by the provided `key' as fast as
665 possible. Return TRUE if the entry was found and FALSE otherwise.
666 The found entry is returned to the `ret_key' and `ret_context',
667 respectively. If the `ret_key and `ret_context' are NULL then this
668 maybe used only to check whether given key exists in the table. */
670 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
671 void **ret_key, void **ret_context)
673 return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
674 NULL, NULL, NULL, NULL);
677 /* Same as above but with specified hash and comparison functions. */
679 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
680 void **ret_key, void **ret_context,
681 SilcHashFunction hash,
682 void *hash_user_context,
683 SilcHashCompare compare,
684 void *compare_user_context)
686 SilcHashTableEntry *entry;
688 entry = silc_hash_table_find_internal_simple(ht, key,
689 hash ? hash : ht->hash,
692 ht->hash_user_context,
695 compare_user_context ?
696 compare_user_context :
697 ht->compare_user_context);
702 *ret_key = (*entry)->key;
704 *ret_context = (*entry)->context;
709 /* Same as silc_hash_table_find but finds with specific context. */
711 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
712 void *context, void **ret_key)
714 return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
715 NULL, NULL, NULL, NULL);
718 /* Same as above but with specified hash and comparison functions. */
720 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
721 void *context, void **ret_key,
722 SilcHashFunction hash,
723 void *hash_user_context,
724 SilcHashCompare compare,
725 void *compare_user_context)
727 SilcHashTableEntry *entry;
729 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
730 hash ? hash : ht->hash,
733 ht->hash_user_context,
736 compare_user_context ?
737 compare_user_context :
738 ht->compare_user_context);
739 if (!entry || !(*entry))
743 *ret_key = (*entry)->key;
748 /* As the hash table is collision resistant it is possible to save duplicate
749 keys to the hash table. This function can be used to find all keys
750 and contexts from the hash table that are found using the `key'. The
751 `foreach' is called for every found key. */
753 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
754 SilcHashForeach foreach, void *user_context)
756 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
757 ht->compare, ht->compare_user_context,
758 foreach, user_context);
761 /* Same as above but with specific hash and comparison functions. */
763 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
764 SilcHashFunction hash,
765 void *hash_user_context,
766 SilcHashCompare compare,
767 void *compare_user_context,
768 SilcHashForeach foreach,
769 void *foreach_user_context)
771 silc_hash_table_find_internal_all(ht, key,
772 hash ? hash : ht->hash,
775 ht->hash_user_context,
778 compare_user_context ?
779 compare_user_context :
780 ht->compare_user_context,
781 foreach, foreach_user_context);
784 /* Traverse all entrys in the hash table and call the `foreach' for
785 every entry with the `user_context' context. */
787 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
790 SilcHashTableEntry e, tmp;
792 SilcBool auto_rehash;
797 auto_rehash = ht->auto_rehash;
798 ht->auto_rehash = FALSE;
799 for (i = 0; i < primesize[ht->table_size]; i++) {
802 /* Entry may become invalid inside the `foreach' */
804 foreach(e->key, e->context, user_context);
808 ht->auto_rehash = auto_rehash;
811 /* Rehashs the hash table. The size of the new hash table is provided
812 as `new_size'. If the `new_size' is zero then this routine will make
813 the new table of a suitable size. Note that this operation may be
816 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
819 SilcHashTableEntry *table, e, tmp;
820 SilcUInt32 table_size, size_index;
821 SilcBool auto_rehash;
823 SILC_HT_DEBUG(("Start"));
826 silc_hash_table_primesize(new_size, &size_index);
828 silc_hash_table_primesize(ht->entry_count, &size_index);
830 if (size_index == ht->table_size)
833 SILC_HT_DEBUG(("Rehashing"));
835 /* Take old hash table */
837 table_size = ht->table_size;
838 auto_rehash = ht->auto_rehash;
839 ht->auto_rehash = FALSE;
841 /* Allocate new table */
842 ht->table = silc_scalloc(ht->stack,
843 primesize[size_index], sizeof(*ht->table));
846 ht->table_size = size_index;
850 for (i = 0; i < primesize[table_size]; i++) {
853 silc_hash_table_add(ht, e->key, e->context);
857 /* Remove old entry */
858 silc_sfree(ht->stack, tmp);
862 ht->auto_rehash = auto_rehash;
864 /* Remove old table */
865 silc_sfree(ht->stack, table);
868 /* Same as above but with specific hash function. */
870 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
871 SilcHashFunction hash,
872 void *hash_user_context)
875 SilcHashTableEntry *table, e, tmp;
876 SilcUInt32 table_size, size_index;
877 SilcBool auto_rehash;
879 SILC_HT_DEBUG(("Start"));
882 silc_hash_table_primesize(new_size, &size_index);
884 silc_hash_table_primesize(ht->entry_count, &size_index);
886 if (size_index == ht->table_size)
889 SILC_HT_DEBUG(("Rehashing"));
891 /* Take old hash table */
893 table_size = ht->table_size;
894 auto_rehash = ht->auto_rehash;
895 ht->auto_rehash = FALSE;
897 /* Allocate new table */
898 ht->table = silc_scalloc(ht->stack,
899 primesize[size_index], sizeof(*ht->table));
902 ht->table_size = size_index;
906 for (i = 0; i < primesize[table_size]; i++) {
909 silc_hash_table_add_ext(ht, e->key, e->context, hash,
914 /* Remove old entry */
915 silc_sfree(ht->stack, tmp);
919 ht->auto_rehash = auto_rehash;
921 /* Remove old table */
922 silc_sfree(ht->stack, table);
925 /* Prepares the `htl' list structure sent as argument to be used in the
926 hash table traversing with the silc_hash_table_get. Usage:
927 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
929 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
934 htl->auto_rehash = ht->auto_rehash;
936 /* Disallow rehashing of the table while traversing the table */
937 ht->auto_rehash = FALSE;
940 /* Resets the `htl' SilcHashTableList. */
942 void silc_hash_table_list_reset(SilcHashTableList *htl)
944 /* Set back the original auto rehash value to the table */
945 htl->ht->auto_rehash = htl->auto_rehash;
948 /* Returns always the next entry in the hash table into the `key' and
949 `context' and TRUE. If this returns FALSE then there are no anymore
950 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
952 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
955 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
957 if (!htl->ht->entry_count)
960 while (!entry && htl->index < primesize[htl->ht->table_size]) {
961 entry = htl->ht->table[htl->index];
968 htl->entry = entry->next;
973 *context = entry->context;