5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2006 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 {
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[] =
82 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
83 1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
84 14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
85 131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
86 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
89 /* Find appropriate size for the hash table. The size will be a prime. */
91 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
95 for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); i++)
96 if (primesize[i] >= size) {
98 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
103 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
104 return primesize[i - 1];
107 /* Internal routine to find entry in the hash table by `key'. Returns
108 the previous entry (if exists) as well. */
110 static inline SilcHashTableEntry *
111 silc_hash_table_find_internal(SilcHashTable ht, void *key,
112 SilcHashTableEntry *prev_entry,
113 SilcHashFunction hash, void *hash_user_context,
114 SilcHashCompare compare,
115 void *compare_user_context)
117 SilcHashTableEntry *entry, prev = NULL;
118 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
120 SILC_HT_DEBUG(("index %d key %p", i, key));
122 entry = &ht->table[i];
124 while (*entry && !compare((*entry)->key, key, compare_user_context)) {
126 entry = &(*entry)->next;
129 while (*entry && (*entry)->key != key) {
131 entry = &(*entry)->next;
139 /* Internal routine to find entry in the hash table by `key' and `context'.
140 Returns the previous entry (if exists) as well to `prev_entry'. */
142 static inline SilcHashTableEntry *
143 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
145 SilcHashTableEntry *prev_entry,
146 SilcHashFunction hash,
147 void *hash_user_context,
148 SilcHashCompare compare,
149 void *compare_user_context)
151 SilcHashTableEntry *entry, prev = NULL;
152 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
154 SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
156 entry = &ht->table[i];
159 if (compare((*entry)->key, key, compare_user_context) &&
160 (*entry)->context == context)
163 entry = &(*entry)->next;
167 if ((*entry)->key == key && (*entry)->context == context)
170 entry = &(*entry)->next;
179 /* Internal routine to find entry in the hash table by `key'. */
181 static inline SilcHashTableEntry *
182 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
183 SilcHashFunction hash,
184 void *hash_user_context,
185 SilcHashCompare compare,
186 void *compare_user_context)
188 SilcHashTableEntry *entry;
189 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
191 SILC_HT_DEBUG(("index %d key %p", i, key));
193 entry = &ht->table[i];
195 while (*entry && !compare((*entry)->key, key, compare_user_context))
196 entry = &(*entry)->next;
198 while (*entry && (*entry)->key != key)
199 entry = &(*entry)->next;
205 /* Internal routine to find all keys by `key'. This may return multiple
206 entries if multiple entries with same key exists. With specific
207 hash and comparison functions. */
210 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
211 SilcHashFunction hash,
212 void *hash_user_context,
213 SilcHashCompare compare,
214 void *compare_user_context,
215 SilcHashForeach foreach,
216 void *foreach_user_context)
218 SilcHashTableEntry e, tmp;
219 SilcBool auto_rehash, found = FALSE;
220 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
222 SILC_HT_DEBUG(("index %d key %p", i, key));
224 /* Disallow auto rehashing while going through the table since we call
225 the `foreach' function which could alter the table. */
226 auto_rehash = ht->auto_rehash;
227 ht->auto_rehash = FALSE;
233 if (compare(e->key, key, compare_user_context)) {
235 foreach(e->key, e->context, foreach_user_context);
244 foreach(e->key, e->context, foreach_user_context);
250 /* If nothing was found call with NULL context the callback */
252 foreach(key, NULL, foreach_user_context);
254 ht->auto_rehash = auto_rehash;
257 /* Internal routine to add new key to the hash table */
259 static inline SilcBool
260 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
261 SilcHashFunction hash,
262 void *hash_user_context)
264 SilcHashTableEntry *entry;
265 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
267 SILC_HT_DEBUG(("index %d key %p", i, key));
269 entry = &ht->table[i];
271 /* The entry exists already. We have a collision, add it to the
272 list to avoid collision. */
273 SilcHashTableEntry e, tmp;
282 SILC_HT_DEBUG(("Collision; adding new key to list"));
284 e->next = silc_calloc(1, sizeof(*e->next));
288 e->next->context = context;
292 SILC_HT_DEBUG(("New key"));
293 *entry = silc_calloc(1, sizeof(**entry));
297 (*entry)->context = context;
301 if (SILC_HASH_REHASH_INC)
302 silc_hash_table_rehash(ht, 0);
307 /* Internal routine to replace old key with new one (if it exists) */
309 static inline SilcBool
310 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
311 SilcHashFunction hash,
312 void *hash_user_context)
314 SilcHashTableEntry *entry;
315 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
317 SILC_HT_DEBUG(("index %d key %p", i, key));
319 entry = &ht->table[i];
321 /* The entry exists already. We have a collision, replace the old
324 ht->destructor((*entry)->key, (*entry)->context,
325 ht->destructor_user_context);
328 *entry = silc_calloc(1, sizeof(**entry));
335 (*entry)->context = context;
337 if (SILC_HASH_REHASH_INC)
338 silc_hash_table_rehash(ht, 0);
343 /* Allocates new hash table and returns it. If the `table_size' is not
344 zero then the hash table size is the size provided. If zero then the
345 default size will be used. Note that if the `table_size' is provided
346 it should be a prime. The `hash', `compare' and `destructor' are
347 the hash function, the key comparison function and key and context
348 destructor function, respectively. The `hash' is mandatory, the others
351 SilcHashTable silc_hash_table_alloc(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;
366 ht = silc_calloc(1, sizeof(*ht));
369 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
371 primesize[SILC_HASH_TABLE_SIZE],
377 ht->table_size = size_index;
379 ht->compare = compare;
380 ht->destructor = destructor;
381 ht->hash_user_context = hash_user_context;
382 ht->compare_user_context = compare_user_context;
383 ht->destructor_user_context = destructor_user_context;
384 ht->auto_rehash = auto_rehash;
389 /* Frees the hash table. The destructor function provided in the
390 silc_hash_table_alloc will be called for all keys in the hash table. */
392 void silc_hash_table_free(SilcHashTable ht)
394 SilcHashTableEntry e, tmp;
397 for (i = 0; i < primesize[ht->table_size]; i++) {
401 ht->destructor(e->key, e->context, ht->destructor_user_context);
408 silc_free(ht->table);
412 /* Returns the size of the hash table */
414 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
416 return primesize[ht->table_size];
419 /* Returns the number of the entires in the hash table. If there is more
420 entries in the table thatn the size of the hash table calling the
421 silc_hash_table_rehash is recommended. */
423 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
425 return ht->entry_count;
428 /* Adds new entry to the hash table. The `key' is hashed using the
429 hash function and the both `key' and `context' will be saved to the
430 hash table. This function quarantees that the entry is always added
431 to the hash table reliably (it is collision resistant). */
433 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context)
435 return silc_hash_table_add_internal(ht, key, context, ht->hash,
436 ht->hash_user_context);
439 /* Same as above but with specific hash function and user context. */
441 SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
442 SilcHashFunction hash,
443 void *hash_user_context)
445 return silc_hash_table_add_internal(ht, key, context,
446 hash, hash_user_context);
449 /* Same as above but if the `key' already exists in the hash table
450 the old key and the old context will be replace with the `key' and
451 the `context. The destructor function will be called for the
452 replaced key and context. */
454 SilcBool silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
456 return silc_hash_table_replace_internal(ht, key, context, ht->hash,
457 ht->hash_user_context);
460 /* Same as above but with specific hash function. */
462 SilcBool silc_hash_table_replace_ext(SilcHashTable ht, void *key,
464 SilcHashFunction hash,
465 void *hash_user_context)
467 return silc_hash_table_replace_internal(ht, key, context,
468 hash, hash_user_context);
471 /* Removes the entry from the hash table by the provided `key'. This will
472 call the destructor funtion for the found entry. Return TRUE if the
473 entry was removed successfully and FALSE otherwise. */
475 SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
477 SilcHashTableEntry *entry, prev, e;
479 entry = silc_hash_table_find_internal(ht, key, &prev,
480 ht->hash, ht->hash_user_context,
481 ht->compare, ht->compare_user_context);
487 if (!prev && e->next)
489 if (!prev && e->next == NULL)
494 prev->next = e->next;
497 ht->destructor(e->key, e->context, ht->destructor_user_context);
502 if (SILC_HASH_REHASH_DEC)
503 silc_hash_table_rehash(ht, 0);
508 /* Same as above but with specific hash and compare functions. */
510 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
511 SilcHashFunction hash,
512 void *hash_user_context,
513 SilcHashCompare compare,
514 void *compare_user_context,
515 SilcHashDestructor destructor,
516 void *destructor_user_context)
518 SilcHashTableEntry *entry, prev, e;
520 entry = silc_hash_table_find_internal(ht, key, &prev,
521 hash ? hash : ht->hash,
522 hash_user_context ? hash_user_context :
523 ht->hash_user_context,
524 compare ? compare : ht->compare,
525 compare_user_context ?
526 compare_user_context :
527 ht->compare_user_context);
533 if (!prev && e->next)
535 if (!prev && e->next == NULL)
540 prev->next = e->next;
543 destructor(e->key, e->context, destructor_user_context);
546 ht->destructor(e->key, e->context, ht->destructor_user_context);
552 if (SILC_HASH_REHASH_DEC)
553 silc_hash_table_rehash(ht, 0);
558 /* Same as above but verifies that the context associated with the `key'
559 matches the `context'. This is handy to use with hash tables that may
560 have duplicate keys. In that case the `context' may be used to check
561 whether the correct entry is being deleted. */
563 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
566 SilcHashTableEntry *entry, prev, e;
568 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
570 ht->hash_user_context,
572 ht->compare_user_context);
578 if (!prev && e->next)
580 if (!prev && e->next == NULL)
585 prev->next = e->next;
588 ht->destructor(e->key, e->context, ht->destructor_user_context);
593 if (SILC_HASH_REHASH_DEC)
594 silc_hash_table_rehash(ht, 0);
599 /* Same as above but with specific hash and compare functions. */
601 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
603 SilcHashFunction hash,
604 void *hash_user_context,
605 SilcHashCompare compare,
606 void *compare_user_context,
607 SilcHashDestructor destructor,
608 void *destructor_user_context)
610 SilcHashTableEntry *entry, prev, e;
612 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
613 hash ? hash : ht->hash,
616 ht->hash_user_context,
618 compare : ht->compare,
619 compare_user_context ?
620 compare_user_context :
621 ht->compare_user_context);
627 if (!prev && e->next)
629 if (!prev && e->next == NULL)
634 prev->next = e->next;
637 destructor(e->key, e->context, destructor_user_context);
640 ht->destructor(e->key, e->context, ht->destructor_user_context);
646 if (SILC_HASH_REHASH_DEC)
647 silc_hash_table_rehash(ht, 0);
652 /* Finds the entry in the hash table by the provided `key' as fast as
653 possible. Return TRUE if the entry was found and FALSE otherwise.
654 The found entry is returned to the `ret_key' and `ret_context',
655 respectively. If the `ret_key and `ret_context' are NULL then this
656 maybe used only to check whether given key exists in the table. */
658 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
659 void **ret_key, void **ret_context)
661 return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
662 NULL, NULL, NULL, NULL);
665 /* Same as above but with specified hash and comparison functions. */
667 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
668 void **ret_key, void **ret_context,
669 SilcHashFunction hash,
670 void *hash_user_context,
671 SilcHashCompare compare,
672 void *compare_user_context)
674 SilcHashTableEntry *entry;
676 entry = silc_hash_table_find_internal_simple(ht, key,
677 hash ? hash : ht->hash,
680 ht->hash_user_context,
683 compare_user_context ?
684 compare_user_context :
685 ht->compare_user_context);
690 *ret_key = (*entry)->key;
692 *ret_context = (*entry)->context;
697 /* Same as silc_hash_table_find but finds with specific context. */
699 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
700 void *context, void **ret_key)
702 return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
703 NULL, NULL, NULL, NULL);
706 /* Same as above but with specified hash and comparison functions. */
708 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
709 void *context, void **ret_key,
710 SilcHashFunction hash,
711 void *hash_user_context,
712 SilcHashCompare compare,
713 void *compare_user_context)
715 SilcHashTableEntry *entry;
717 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
718 hash ? hash : ht->hash,
721 ht->hash_user_context,
724 compare_user_context ?
725 compare_user_context :
726 ht->compare_user_context);
727 if (!entry || !(*entry))
731 *ret_key = (*entry)->key;
736 /* As the hash table is collision resistant it is possible to save duplicate
737 keys to the hash table. This function can be used to find all keys
738 and contexts from the hash table that are found using the `key'. The
739 `foreach' is called for every found key. */
741 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
742 SilcHashForeach foreach, void *user_context)
744 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
745 ht->compare, ht->compare_user_context,
746 foreach, user_context);
749 /* Same as above but with specific hash and comparison functions. */
751 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
752 SilcHashFunction hash,
753 void *hash_user_context,
754 SilcHashCompare compare,
755 void *compare_user_context,
756 SilcHashForeach foreach,
757 void *foreach_user_context)
759 silc_hash_table_find_internal_all(ht, key,
760 hash ? hash : ht->hash,
763 ht->hash_user_context,
766 compare_user_context ?
767 compare_user_context :
768 ht->compare_user_context,
769 foreach, foreach_user_context);
772 /* Traverse all entrys in the hash table and call the `foreach' for
773 every entry with the `user_context' context. */
775 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
778 SilcHashTableEntry e, tmp;
780 SilcBool auto_rehash;
785 auto_rehash = ht->auto_rehash;
786 ht->auto_rehash = FALSE;
787 for (i = 0; i < primesize[ht->table_size]; i++) {
790 /* Entry may become invalid inside the `foreach' */
792 foreach(e->key, e->context, user_context);
796 ht->auto_rehash = auto_rehash;
799 /* Rehashs the hash table. The size of the new hash table is provided
800 as `new_size'. If the `new_size' is zero then this routine will make
801 the new table of a suitable size. Note that this operation may be
804 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
807 SilcHashTableEntry *table, e, tmp;
808 SilcUInt32 table_size, size_index;
809 SilcBool auto_rehash;
811 SILC_HT_DEBUG(("Start"));
814 silc_hash_table_primesize(new_size, &size_index);
816 silc_hash_table_primesize(ht->entry_count, &size_index);
818 if (size_index == ht->table_size)
821 SILC_HT_DEBUG(("Rehashing"));
823 /* Take old hash table */
825 table_size = ht->table_size;
826 auto_rehash = ht->auto_rehash;
827 ht->auto_rehash = FALSE;
829 /* Allocate new table */
830 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
833 ht->table_size = size_index;
837 for (i = 0; i < primesize[table_size]; i++) {
840 silc_hash_table_add(ht, e->key, e->context);
844 /* Remove old entry */
849 ht->auto_rehash = auto_rehash;
851 /* Remove old table */
855 /* Same as above but with specific hash function. */
857 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
858 SilcHashFunction hash,
859 void *hash_user_context)
862 SilcHashTableEntry *table, e, tmp;
863 SilcUInt32 table_size, size_index;
864 SilcBool auto_rehash;
866 SILC_HT_DEBUG(("Start"));
869 silc_hash_table_primesize(new_size, &size_index);
871 silc_hash_table_primesize(ht->entry_count, &size_index);
873 if (size_index == ht->table_size)
876 SILC_HT_DEBUG(("Rehashing"));
878 /* Take old hash table */
880 table_size = ht->table_size;
881 auto_rehash = ht->auto_rehash;
882 ht->auto_rehash = FALSE;
884 /* Allocate new table */
885 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
888 ht->table_size = size_index;
892 for (i = 0; i < primesize[table_size]; i++) {
895 silc_hash_table_add_ext(ht, e->key, e->context, hash,
900 /* Remove old entry */
905 ht->auto_rehash = auto_rehash;
907 /* Remove old table */
911 /* Prepares the `htl' list structure sent as argument to be used in the
912 hash table traversing with the silc_hash_table_get. Usage:
913 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
915 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
920 htl->auto_rehash = ht->auto_rehash;
922 /* Disallow rehashing of the table while traversing the table */
923 ht->auto_rehash = FALSE;
926 /* Resets the `htl' SilcHashTableList. */
928 void silc_hash_table_list_reset(SilcHashTableList *htl)
930 /* Set back the original auto rehash value to the table */
931 htl->ht->auto_rehash = htl->auto_rehash;
934 /* Returns always the next entry in the hash table into the `key' and
935 `context' and TRUE. If this returns FALSE then there are no anymore
936 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
938 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
941 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
943 if (!htl->ht->entry_count)
946 while (!entry && htl->index < primesize[htl->ht->table_size]) {
947 entry = htl->ht->table[htl->index];
954 htl->entry = entry->next;
959 *context = entry->context;