5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2003 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
28 #include "silcincludes.h"
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 {
66 SilcHashTableEntry *table;
67 SilcUInt32 table_size;
68 SilcUInt32 entry_count;
69 SilcHashFunction hash;
70 SilcHashCompare compare;
71 SilcHashDestructor destructor;
72 void *hash_user_context;
73 void *compare_user_context;
74 void *destructor_user_context;
75 unsigned int auto_rehash : 1;
78 /* Prime sizes for the hash table. The size of the table will always
80 const SilcUInt32 primesize[42] =
82 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
83 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
84 65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
85 4194319, 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 bool 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 */
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_calloc(1, sizeof(*e->next));
287 e->next->context = context;
291 SILC_HT_DEBUG(("New key"));
292 *entry = silc_calloc(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) */
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_calloc(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(SilcUInt32 table_size,
351 SilcHashFunction hash,
352 void *hash_user_context,
353 SilcHashCompare compare,
354 void *compare_user_context,
355 SilcHashDestructor destructor,
356 void *destructor_user_context,
360 SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
365 ht = silc_calloc(1, sizeof(*ht));
368 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
370 primesize[SILC_HASH_TABLE_SIZE],
376 ht->table_size = size_index;
378 ht->compare = compare;
379 ht->destructor = destructor;
380 ht->hash_user_context = hash_user_context;
381 ht->compare_user_context = compare_user_context;
382 ht->destructor_user_context = destructor_user_context;
383 ht->auto_rehash = auto_rehash;
388 /* Frees the hash table. The destructor function provided in the
389 silc_hash_table_alloc will be called for all keys in the hash table. */
391 void silc_hash_table_free(SilcHashTable ht)
393 SilcHashTableEntry e, tmp;
396 for (i = 0; i < primesize[ht->table_size]; i++) {
400 ht->destructor(e->key, e->context, ht->destructor_user_context);
407 silc_free(ht->table);
411 /* Returns the size of the hash table */
413 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
415 return primesize[ht->table_size];
418 /* Returns the number of the entires in the hash table. If there is more
419 entries in the table thatn the size of the hash table calling the
420 silc_hash_table_rehash is recommended. */
422 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
424 return ht->entry_count;
427 /* Adds new entry to the hash table. The `key' is hashed using the
428 hash function and the both `key' and `context' will be saved to the
429 hash table. This function quarantees that the entry is always added
430 to the hash table reliably (it is collision resistant). */
432 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
434 silc_hash_table_add_internal(ht, key, context, ht->hash,
435 ht->hash_user_context);
438 /* Same as above but with specific hash function and user context. */
440 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
441 SilcHashFunction hash, void *hash_user_context)
443 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
446 /* Same as above but if the `key' already exists in the hash table
447 the old key and the old context will be replace with the `key' and
448 the `context. The destructor function will be called for the
449 replaced key and context. */
451 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
453 silc_hash_table_replace_internal(ht, key, context, ht->hash,
454 ht->hash_user_context);
457 /* Same as above but with specific hash function. */
459 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
460 SilcHashFunction hash,
461 void *hash_user_context)
463 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
466 /* Removes the entry from the hash table by the provided `key'. This will
467 call the destructor funtion for the found entry. Return TRUE if the
468 entry was removed successfully and FALSE otherwise. */
470 bool silc_hash_table_del(SilcHashTable ht, void *key)
472 SilcHashTableEntry *entry, prev, e;
474 entry = silc_hash_table_find_internal(ht, key, &prev,
475 ht->hash, ht->hash_user_context,
476 ht->compare, ht->compare_user_context);
482 if (!prev && e->next)
484 if (!prev && e->next == NULL)
489 prev->next = e->next;
492 ht->destructor(e->key, e->context, ht->destructor_user_context);
497 if (SILC_HASH_REHASH_DEC)
498 silc_hash_table_rehash(ht, 0);
503 /* Same as above but with specific hash and compare functions. */
505 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
506 SilcHashFunction hash,
507 void *hash_user_context,
508 SilcHashCompare compare,
509 void *compare_user_context,
510 SilcHashDestructor destructor,
511 void *destructor_user_context)
513 SilcHashTableEntry *entry, prev, e;
515 entry = silc_hash_table_find_internal(ht, key, &prev,
516 hash ? hash : ht->hash,
517 hash_user_context ? hash_user_context :
518 ht->hash_user_context,
519 compare ? compare : ht->compare,
520 compare_user_context ?
521 compare_user_context :
522 ht->compare_user_context);
528 if (!prev && e->next)
530 if (!prev && e->next == NULL)
535 prev->next = e->next;
538 destructor(e->key, e->context, destructor_user_context);
541 ht->destructor(e->key, e->context, ht->destructor_user_context);
547 if (SILC_HASH_REHASH_DEC)
548 silc_hash_table_rehash(ht, 0);
553 /* Same as above but verifies that the context associated with the `key'
554 matches the `context'. This is handy to use with hash tables that may
555 have duplicate keys. In that case the `context' may be used to check
556 whether the correct entry is being deleted. */
558 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
561 SilcHashTableEntry *entry, prev, e;
563 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
565 ht->hash_user_context,
567 ht->compare_user_context);
573 if (!prev && e->next)
575 if (!prev && e->next == NULL)
580 prev->next = e->next;
583 ht->destructor(e->key, e->context, ht->destructor_user_context);
588 if (SILC_HASH_REHASH_DEC)
589 silc_hash_table_rehash(ht, 0);
594 /* Same as above but with specific hash and compare functions. */
596 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
598 SilcHashFunction hash,
599 void *hash_user_context,
600 SilcHashCompare compare,
601 void *compare_user_context,
602 SilcHashDestructor destructor,
603 void *destructor_user_context)
605 SilcHashTableEntry *entry, prev, e;
607 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
608 hash ? hash : ht->hash,
611 ht->hash_user_context,
613 compare : ht->compare,
614 compare_user_context ?
615 compare_user_context :
616 ht->compare_user_context);
622 if (!prev && e->next)
624 if (!prev && e->next == NULL)
629 prev->next = e->next;
632 destructor(e->key, e->context, destructor_user_context);
635 ht->destructor(e->key, e->context, ht->destructor_user_context);
641 if (SILC_HASH_REHASH_DEC)
642 silc_hash_table_rehash(ht, 0);
647 /* Finds the entry in the hash table by the provided `key' as fast as
648 possible. Return TRUE if the entry was found and FALSE otherwise.
649 The found entry is returned to the `ret_key' and `ret_context',
650 respectively. If the `ret_key and `ret_context' are NULL then this
651 maybe used only to check whether given key exists in the table. */
653 bool silc_hash_table_find(SilcHashTable ht, void *key,
654 void **ret_key, void **ret_context)
656 return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
657 NULL, NULL, NULL, NULL);
660 /* Same as above but with specified hash and comparison functions. */
662 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
663 void **ret_key, void **ret_context,
664 SilcHashFunction hash,
665 void *hash_user_context,
666 SilcHashCompare compare,
667 void *compare_user_context)
669 SilcHashTableEntry *entry;
671 entry = silc_hash_table_find_internal_simple(ht, key,
672 hash ? hash : ht->hash,
675 ht->hash_user_context,
678 compare_user_context ?
679 compare_user_context :
680 ht->compare_user_context);
685 *ret_key = (*entry)->key;
687 *ret_context = (*entry)->context;
692 /* Same as silc_hash_table_find but finds with specific context. */
694 bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
695 void *context, void **ret_key)
697 return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
698 NULL, NULL, NULL, NULL);
701 /* Same as above but with specified hash and comparison functions. */
703 bool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
704 void *context, void **ret_key,
705 SilcHashFunction hash,
706 void *hash_user_context,
707 SilcHashCompare compare,
708 void *compare_user_context)
710 SilcHashTableEntry *entry;
712 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
713 hash ? hash : ht->hash,
716 ht->hash_user_context,
719 compare_user_context ?
720 compare_user_context :
721 ht->compare_user_context);
722 if (!entry || !(*entry))
726 *ret_key = (*entry)->key;
731 /* As the hash table is collision resistant it is possible to save duplicate
732 keys to the hash table. This function can be used to find all keys
733 and contexts from the hash table that are found using the `key'. The
734 `foreach' is called for every found key. */
736 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
737 SilcHashForeach foreach, void *user_context)
739 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
740 ht->compare, ht->compare_user_context,
741 foreach, user_context);
744 /* Same as above but with specific hash and comparison functions. */
746 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
747 SilcHashFunction hash,
748 void *hash_user_context,
749 SilcHashCompare compare,
750 void *compare_user_context,
751 SilcHashForeach foreach,
752 void *foreach_user_context)
754 silc_hash_table_find_internal_all(ht, key,
755 hash ? hash : ht->hash,
758 ht->hash_user_context,
761 compare_user_context ?
762 compare_user_context :
763 ht->compare_user_context,
764 foreach, foreach_user_context);
767 /* Traverse all entrys in the hash table and call the `foreach' for
768 every entry with the `user_context' context. */
770 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
773 SilcHashTableEntry e, tmp;
780 auto_rehash = ht->auto_rehash;
781 ht->auto_rehash = FALSE;
782 for (i = 0; i < primesize[ht->table_size]; i++) {
785 /* Entry may become invalid inside the `foreach' */
787 foreach(e->key, e->context, user_context);
791 ht->auto_rehash = auto_rehash;
794 /* Rehashs the hash table. The size of the new hash table is provided
795 as `new_size'. If the `new_size' is zero then this routine will make
796 the new table of a suitable size. Note that this operation may be
799 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
802 SilcHashTableEntry *table, e, tmp;
803 SilcUInt32 table_size, size_index;
806 SILC_HT_DEBUG(("Start"));
809 silc_hash_table_primesize(new_size, &size_index);
811 silc_hash_table_primesize(ht->entry_count, &size_index);
813 if (size_index == ht->table_size)
816 SILC_HT_DEBUG(("Rehashing"));
818 /* Take old hash table */
820 table_size = ht->table_size;
821 auto_rehash = ht->auto_rehash;
822 ht->auto_rehash = FALSE;
824 /* Allocate new table */
825 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
828 ht->table_size = size_index;
832 for (i = 0; i < primesize[table_size]; i++) {
835 silc_hash_table_add(ht, e->key, e->context);
839 /* Remove old entry */
844 ht->auto_rehash = auto_rehash;
846 /* Remove old table */
850 /* Same as above but with specific hash function. */
852 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
853 SilcHashFunction hash,
854 void *hash_user_context)
857 SilcHashTableEntry *table, e, tmp;
858 SilcUInt32 table_size, size_index;
861 SILC_HT_DEBUG(("Start"));
864 silc_hash_table_primesize(new_size, &size_index);
866 silc_hash_table_primesize(ht->entry_count, &size_index);
868 if (size_index == ht->table_size)
871 SILC_HT_DEBUG(("Rehashing"));
873 /* Take old hash table */
875 table_size = ht->table_size;
876 auto_rehash = ht->auto_rehash;
877 ht->auto_rehash = FALSE;
879 /* Allocate new table */
880 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
883 ht->table_size = size_index;
887 for (i = 0; i < primesize[table_size]; i++) {
890 silc_hash_table_add_ext(ht, e->key, e->context, hash,
895 /* Remove old entry */
900 ht->auto_rehash = auto_rehash;
902 /* Remove old table */
906 /* Prepares the `htl' list structure sent as argument to be used in the
907 hash table traversing with the silc_hash_table_get. Usage:
908 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
910 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
915 htl->auto_rehash = ht->auto_rehash;
917 /* Disallow rehashing of the table while traversing the table */
918 ht->auto_rehash = FALSE;
921 /* Resets the `htl' SilcHashTableList. */
923 void silc_hash_table_list_reset(SilcHashTableList *htl)
925 /* Set back the original auto rehash value to the table */
926 htl->ht->auto_rehash = htl->auto_rehash;
929 /* Returns always the next entry in the hash table into the `key' and
930 `context' and TRUE. If this returns FALSE then there are no anymore
931 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
933 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
935 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
937 if (!htl->ht->entry_count)
940 while (!entry && htl->index < primesize[htl->ht->table_size]) {
941 entry = htl->ht->table[htl->index];
948 htl->entry = entry->next;
953 *context = entry->context;