5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2001 - 2002 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 3
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 1, 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); 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));
285 e->next->context = context;
289 SILC_HT_DEBUG(("New key"));
290 *entry = silc_calloc(1, sizeof(**entry));
292 (*entry)->context = context;
296 if (SILC_HASH_REHASH_INC)
297 silc_hash_table_rehash(ht, 0);
300 /* Internal routine to replace old key with new one (if it exists) */
303 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
304 SilcHashFunction hash,
305 void *hash_user_context)
307 SilcHashTableEntry *entry;
308 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
310 SILC_HT_DEBUG(("index %d key %p", i, key));
312 entry = &ht->table[i];
314 /* The entry exists already. We have a collision, replace the old
317 ht->destructor((*entry)->key, (*entry)->context,
318 ht->destructor_user_context);
321 *entry = silc_calloc(1, sizeof(**entry));
326 (*entry)->context = context;
328 if (SILC_HASH_REHASH_INC)
329 silc_hash_table_rehash(ht, 0);
332 /* Allocates new hash table and returns it. If the `table_size' is not
333 zero then the hash table size is the size provided. If zero then the
334 default size will be used. Note that if the `table_size' is provided
335 it should be a prime. The `hash', `compare' and `destructor' are
336 the hash function, the key comparison function and key and context
337 destructor function, respectively. The `hash' is mandatory, the others
340 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
341 SilcHashFunction hash,
342 void *hash_user_context,
343 SilcHashCompare compare,
344 void *compare_user_context,
345 SilcHashDestructor destructor,
346 void *destructor_user_context,
350 SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
355 ht = silc_calloc(1, sizeof(*ht));
356 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
358 primesize[SILC_HASH_TABLE_SIZE],
360 ht->table_size = size_index;
362 ht->compare = compare;
363 ht->destructor = destructor;
364 ht->hash_user_context = hash_user_context;
365 ht->compare_user_context = compare_user_context;
366 ht->destructor_user_context = destructor_user_context;
367 ht->auto_rehash = auto_rehash;
372 /* Frees the hash table. The destructor function provided in the
373 silc_hash_table_alloc will be called for all keys in the hash table. */
375 void silc_hash_table_free(SilcHashTable ht)
377 SilcHashTableEntry e, tmp;
380 for (i = 0; i < primesize[ht->table_size]; i++) {
384 ht->destructor(e->key, e->context, ht->destructor_user_context);
391 silc_free(ht->table);
395 /* Returns the size of the hash table */
397 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
399 return primesize[ht->table_size];
402 /* Returns the number of the entires in the hash table. If there is more
403 entries in the table thatn the size of the hash table calling the
404 silc_hash_table_rehash is recommended. */
406 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
408 return ht->entry_count;
411 /* Adds new entry to the hash table. The `key' is hashed using the
412 hash function and the both `key' and `context' will be saved to the
413 hash table. This function quarantees that the entry is always added
414 to the hash table reliably (it is collision resistant). */
416 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
418 silc_hash_table_add_internal(ht, key, context, ht->hash,
419 ht->hash_user_context);
422 /* Same as above but with specific hash function and user context. */
424 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
425 SilcHashFunction hash, void *hash_user_context)
427 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
430 /* Same as above but if the `key' already exists in the hash table
431 the old key and the old context will be replace with the `key' and
432 the `context. The destructor function will be called for the
433 replaced key and context. */
435 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
437 silc_hash_table_replace_internal(ht, key, context, ht->hash,
438 ht->hash_user_context);
441 /* Same as above but with specific hash function. */
443 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
444 SilcHashFunction hash,
445 void *hash_user_context)
447 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
450 /* Removes the entry from the hash table by the provided `key'. This will
451 call the destructor funtion for the found entry. Return TRUE if the
452 entry was removed successfully and FALSE otherwise. */
454 bool silc_hash_table_del(SilcHashTable ht, void *key)
456 SilcHashTableEntry *entry, prev, e;
458 entry = silc_hash_table_find_internal(ht, key, &prev,
459 ht->hash, ht->hash_user_context,
460 ht->compare, ht->compare_user_context);
466 if (!prev && e->next)
468 if (!prev && e->next == NULL)
473 prev->next = e->next;
476 ht->destructor(e->key, e->context, ht->destructor_user_context);
481 if (SILC_HASH_REHASH_DEC)
482 silc_hash_table_rehash(ht, 0);
487 /* Same as above but with specific hash and compare functions. */
489 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
490 SilcHashFunction hash,
491 void *hash_user_context,
492 SilcHashCompare compare,
493 void *compare_user_context,
494 SilcHashDestructor destructor,
495 void *destructor_user_context)
497 SilcHashTableEntry *entry, prev, e;
499 entry = silc_hash_table_find_internal(ht, key, &prev,
500 hash ? hash : ht->hash,
501 hash_user_context ? hash_user_context :
502 ht->hash_user_context,
503 compare ? compare : ht->compare,
504 compare_user_context ?
505 compare_user_context :
506 ht->compare_user_context);
512 if (!prev && e->next)
514 if (!prev && e->next == NULL)
519 prev->next = e->next;
522 destructor(e->key, e->context, destructor_user_context);
525 ht->destructor(e->key, e->context, ht->destructor_user_context);
531 if (SILC_HASH_REHASH_DEC)
532 silc_hash_table_rehash(ht, 0);
537 /* Same as above but verifies that the context associated with the `key'
538 matches the `context'. This is handy to use with hash tables that may
539 have duplicate keys. In that case the `context' may be used to check
540 whether the correct entry is being deleted. */
542 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
545 SilcHashTableEntry *entry, prev, e;
547 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
549 ht->hash_user_context,
551 ht->compare_user_context);
557 if (!prev && e->next)
559 if (!prev && e->next == NULL)
564 prev->next = e->next;
567 ht->destructor(e->key, e->context, ht->destructor_user_context);
572 if (SILC_HASH_REHASH_DEC)
573 silc_hash_table_rehash(ht, 0);
578 /* Same as above but with specific hash and compare functions. */
580 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
582 SilcHashFunction hash,
583 void *hash_user_context,
584 SilcHashCompare compare,
585 void *compare_user_context,
586 SilcHashDestructor destructor,
587 void *destructor_user_context)
589 SilcHashTableEntry *entry, prev, e;
591 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
592 hash ? hash : ht->hash,
595 ht->hash_user_context,
597 compare : ht->compare,
598 compare_user_context ?
599 compare_user_context :
600 ht->compare_user_context);
606 if (!prev && e->next)
608 if (!prev && e->next == NULL)
613 prev->next = e->next;
616 destructor(e->key, e->context, destructor_user_context);
619 ht->destructor(e->key, e->context, ht->destructor_user_context);
625 if (SILC_HASH_REHASH_DEC)
626 silc_hash_table_rehash(ht, 0);
631 /* Finds the entry in the hash table by the provided `key' as fast as
632 possible. Return TRUE if the entry was found and FALSE otherwise.
633 The found entry is returned to the `ret_key' and `ret_context',
634 respectively. If the `ret_key and `ret_context' are NULL then this
635 maybe used only to check whether given key exists in the table. */
637 bool silc_hash_table_find(SilcHashTable ht, void *key,
638 void **ret_key, void **ret_context)
640 SilcHashTableEntry *entry;
642 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
643 ht->hash_user_context,
645 ht->compare_user_context);
650 *ret_key = (*entry)->key;
652 *ret_context = (*entry)->context;
657 /* Same as above but with specified hash and comparison functions. */
659 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
660 void **ret_key, void **ret_context,
661 SilcHashFunction hash,
662 void *hash_user_context,
663 SilcHashCompare compare,
664 void *compare_user_context)
666 SilcHashTableEntry *entry;
668 entry = silc_hash_table_find_internal_simple(ht, key,
669 hash ? hash : ht->hash,
672 ht->hash_user_context,
675 compare_user_context ?
676 compare_user_context :
677 ht->compare_user_context);
682 *ret_key = (*entry)->key;
684 *ret_context = (*entry)->context;
689 /* Same as silc_hash_table_find but finds with specific context. */
691 bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
692 void *context, void **ret_key)
694 SilcHashTableEntry *entry;
696 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
698 ht->hash_user_context,
700 ht->compare_user_context);
701 if (!entry || !(*entry))
705 *ret_key = (*entry)->key;
710 /* As the hash table is collision resistant it is possible to save duplicate
711 keys to the hash table. This function can be used to find all keys
712 and contexts from the hash table that are found using the `key'. The
713 `foreach' is called for every found key. */
715 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
716 SilcHashForeach foreach, void *user_context)
718 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
719 ht->compare, ht->compare_user_context,
720 foreach, user_context);
723 /* Same as above but with specific hash and comparison functions. */
725 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
726 SilcHashFunction hash,
727 void *hash_user_context,
728 SilcHashCompare compare,
729 void *compare_user_context,
730 SilcHashForeach foreach,
731 void *foreach_user_context)
733 silc_hash_table_find_internal_all(ht, key,
734 hash ? hash : ht->hash,
737 ht->hash_user_context,
740 compare_user_context ?
741 compare_user_context :
742 ht->compare_user_context,
743 foreach, foreach_user_context);
746 /* Traverse all entrys in the hash table and call the `foreach' for
747 every entry with the `user_context' context. */
749 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
752 SilcHashTableEntry e, tmp;
759 auto_rehash = ht->auto_rehash;
760 ht->auto_rehash = FALSE;
761 for (i = 0; i < primesize[ht->table_size]; i++) {
764 /* Entry may become invalid inside the `foreach' */
766 foreach(e->key, e->context, user_context);
770 ht->auto_rehash = auto_rehash;
773 /* Rehashs the hash table. The size of the new hash table is provided
774 as `new_size'. If the `new_size' is zero then this routine will make
775 the new table of a suitable size. Note that this operation may be
778 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
781 SilcHashTableEntry *table, e, tmp;
782 SilcUInt32 table_size, size_index;
784 SILC_HT_DEBUG(("Start"));
787 silc_hash_table_primesize(new_size, &size_index);
789 silc_hash_table_primesize(ht->entry_count, &size_index);
791 if (size_index == ht->table_size)
794 SILC_HT_DEBUG(("Rehashing"));
796 /* Take old hash table */
798 table_size = ht->table_size;
800 /* Allocate new table */
801 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
802 ht->table_size = size_index;
806 for (i = 0; i < primesize[table_size]; i++) {
809 silc_hash_table_add(ht, e->key, e->context);
813 /* Remove old entry */
818 /* Remove old table */
822 /* Same as above but with specific hash function. */
824 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
825 SilcHashFunction hash,
826 void *hash_user_context)
829 SilcHashTableEntry *table, e, tmp;
830 SilcUInt32 table_size, size_index;
832 SILC_HT_DEBUG(("Start"));
835 silc_hash_table_primesize(new_size, &size_index);
837 silc_hash_table_primesize(ht->entry_count, &size_index);
839 if (size_index == ht->table_size)
842 SILC_HT_DEBUG(("Rehashing"));
844 /* Take old hash table */
846 table_size = ht->table_size;
848 /* Allocate new table */
849 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
850 ht->table_size = size_index;
854 for (i = 0; i < primesize[table_size]; i++) {
857 silc_hash_table_add_ext(ht, e->key, e->context, hash,
862 /* Remove old entry */
867 /* Remove old table */
871 /* Prepares the `htl' list structure sent as argument to be used in the
872 hash table traversing with the silc_hash_table_get. Usage:
873 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
875 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
880 htl->auto_rehash = ht->auto_rehash;
882 /* Disallow rehashing of the table while traversing the table */
883 ht->auto_rehash = FALSE;
886 /* Resets the `htl' SilcHashTableList. */
888 void silc_hash_table_list_reset(SilcHashTableList *htl)
890 /* Set back the original auto rehash value to the table */
891 htl->ht->auto_rehash = htl->auto_rehash;
894 /* Returns always the next entry in the hash table into the `key' and
895 `context' and TRUE. If this returns FALSE then there are no anymore
896 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
898 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
900 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
902 if (!htl->ht->entry_count)
905 while (!entry && htl->index < primesize[htl->ht->table_size]) {
906 entry = htl->ht->table[htl->index];
913 htl->entry = entry->next;
918 *context = entry->context;