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;
69 SilcHashFunction hash;
70 SilcHashCompare compare;
71 SilcHashDestructor destructor;
72 void *hash_user_context;
73 void *compare_user_context;
74 void *destructor_user_context;
78 /* Prime sizes for the hash table. The size of the table will always
80 const uint32 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 uint32 silc_hash_table_primesize(uint32 size, uint32 *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 uint32 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. */
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 uint32 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;
177 /* Internal routine to find entry in the hash table by `key'. */
179 static inline SilcHashTableEntry *
180 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
181 SilcHashFunction hash,
182 void *hash_user_context,
183 SilcHashCompare compare,
184 void *compare_user_context)
186 SilcHashTableEntry *entry;
187 uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
189 SILC_HT_DEBUG(("index %d key %p", i, key));
191 entry = &ht->table[i];
193 while (*entry && !compare((*entry)->key, key, compare_user_context))
194 entry = &(*entry)->next;
196 while (*entry && (*entry)->key != key)
197 entry = &(*entry)->next;
203 /* Internal routine to find all keys by `key'. This may return multiple
204 entries if multiple entries with same key exists. With specific
205 hash and comparison functions. */
208 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
209 SilcHashFunction hash,
210 void *hash_user_context,
211 SilcHashCompare compare,
212 void *compare_user_context,
213 SilcHashForeach foreach,
214 void *foreach_user_context)
216 SilcHashTableEntry *entry, *tmp;
218 uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
220 SILC_HT_DEBUG(("index %d key %p", i, key));
222 /* Disallow auto rehashing while going through the table since we call
223 the `foreach' function which could alter the table. */
224 auto_rehash = ht->auto_rehash;
225 ht->auto_rehash = FALSE;
227 entry = &ht->table[i];
230 if (compare((*entry)->key, key, compare_user_context)) {
231 tmp = &(*entry)->next;
232 foreach((*entry)->key, (*entry)->context, foreach_user_context);
236 entry = &(*entry)->next;
240 if ((*entry)->key == key) {
241 tmp = &(*entry)->next;
242 foreach((*entry)->key, (*entry)->context, foreach_user_context);
246 entry = &(*entry)->next;
250 ht->auto_rehash = auto_rehash;
253 /* Internal routine to add new key to the hash table */
256 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
257 SilcHashFunction hash,
258 void *hash_user_context)
260 SilcHashTableEntry *entry;
261 uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
263 SILC_HT_DEBUG(("index %d key %p", i, key));
265 entry = &ht->table[i];
267 /* The entry exists already. We have a collision, add it to the
268 list to avoid collision. */
269 SilcHashTableEntry e, tmp;
278 SILC_HT_DEBUG(("Collision; adding new key to list"));
280 e->next = silc_calloc(1, sizeof(*e->next));
282 e->next->context = context;
286 SILC_HT_DEBUG(("New key"));
287 *entry = silc_calloc(1, sizeof(**entry));
289 (*entry)->context = context;
293 if (SILC_HASH_REHASH_INC)
294 silc_hash_table_rehash(ht, 0);
297 /* Internal routine to replace old key with new one (if it exists) */
300 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
301 SilcHashFunction hash,
302 void *hash_user_context)
304 SilcHashTableEntry *entry;
305 uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
307 SILC_HT_DEBUG(("index %d key %p", i, key));
309 entry = &ht->table[i];
311 /* The entry exists already. We have a collision, replace the old
314 ht->destructor((*entry)->key, (*entry)->context,
315 ht->destructor_user_context);
318 *entry = silc_calloc(1, sizeof(**entry));
323 (*entry)->context = context;
325 if (SILC_HASH_REHASH_INC)
326 silc_hash_table_rehash(ht, 0);
329 /* Allocates new hash table and returns it. If the `table_size' is not
330 zero then the hash table size is the size provided. If zero then the
331 default size will be used. Note that if the `table_size' is provided
332 it should be a prime. The `hash', `compare' and `destructor' are
333 the hash function, the key comparison function and key and context
334 destructor function, respectively. The `hash' is mandatory, the others
337 SilcHashTable silc_hash_table_alloc(uint32 table_size,
338 SilcHashFunction hash,
339 void *hash_user_context,
340 SilcHashCompare compare,
341 void *compare_user_context,
342 SilcHashDestructor destructor,
343 void *destructor_user_context,
347 uint32 size_index = SILC_HASH_TABLE_SIZE;
352 ht = silc_calloc(1, sizeof(*ht));
353 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
355 primesize[SILC_HASH_TABLE_SIZE],
357 ht->table_size = size_index;
359 ht->compare = compare;
360 ht->destructor = destructor;
361 ht->hash_user_context = hash_user_context;
362 ht->compare_user_context = compare_user_context;
363 ht->destructor_user_context = destructor_user_context;
364 ht->auto_rehash = auto_rehash;
369 /* Frees the hash table. The destructor function provided in the
370 silc_hash_table_alloc will be called for all keys in the hash table. */
372 void silc_hash_table_free(SilcHashTable ht)
374 SilcHashTableEntry e, tmp;
377 for (i = 0; i < primesize[ht->table_size]; i++) {
381 ht->destructor(e->key, e->context, ht->destructor_user_context);
388 silc_free(ht->table);
392 /* Returns the size of the hash table */
394 uint32 silc_hash_table_size(SilcHashTable ht)
396 return primesize[ht->table_size];
399 /* Returns the number of the entires in the hash table. If there is more
400 entries in the table thatn the size of the hash table calling the
401 silc_hash_table_rehash is recommended. */
403 uint32 silc_hash_table_count(SilcHashTable ht)
405 return ht->entry_count;
408 /* Adds new entry to the hash table. The `key' is hashed using the
409 hash function and the both `key' and `context' will be saved to the
410 hash table. This function quarantees that the entry is always added
411 to the hash table reliably (it is collision resistant). */
413 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
415 silc_hash_table_add_internal(ht, key, context, ht->hash,
416 ht->hash_user_context);
419 /* Same as above but with specific hash function and user context. */
421 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
422 SilcHashFunction hash, void *hash_user_context)
424 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
427 /* Same as above but if the `key' already exists in the hash table
428 the old key and the old context will be replace with the `key' and
429 the `context. The destructor function will be called for the
430 replaced key and context. */
432 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
434 silc_hash_table_replace_internal(ht, key, context, ht->hash,
435 ht->hash_user_context);
438 /* Same as above but with specific hash function. */
440 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
441 SilcHashFunction hash,
442 void *hash_user_context)
444 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
447 /* Removes the entry from the hash table by the provided `key'. This will
448 call the destructor funtion for the found entry. Return TRUE if the
449 entry was removed successfully and FALSE otherwise. */
451 bool silc_hash_table_del(SilcHashTable ht, void *key)
453 SilcHashTableEntry *entry, prev, e;
455 entry = silc_hash_table_find_internal(ht, key, &prev,
456 ht->hash, ht->hash_user_context,
457 ht->compare, ht->compare_user_context);
463 if (!prev && e->next)
465 if (!prev && e->next == NULL)
470 prev->next = e->next;
473 ht->destructor(e->key, e->context, ht->destructor_user_context);
478 if (SILC_HASH_REHASH_DEC)
479 silc_hash_table_rehash(ht, 0);
484 /* Same as above but with specific hash and compare functions. */
486 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
487 SilcHashFunction hash,
488 void *hash_user_context,
489 SilcHashCompare compare,
490 void *compare_user_context,
491 SilcHashDestructor destructor,
492 void *destructor_user_context)
494 SilcHashTableEntry *entry, prev, e;
496 entry = silc_hash_table_find_internal(ht, key, &prev,
497 hash ? hash : ht->hash,
498 hash_user_context ? hash_user_context :
499 ht->hash_user_context,
500 compare ? compare : ht->compare,
501 compare_user_context ?
502 compare_user_context :
503 ht->compare_user_context);
509 if (!prev && e->next)
511 if (!prev && e->next == NULL)
516 prev->next = e->next;
519 destructor(e->key, e->context, destructor_user_context);
522 ht->destructor(e->key, e->context, ht->destructor_user_context);
528 if (SILC_HASH_REHASH_DEC)
529 silc_hash_table_rehash(ht, 0);
534 /* Same as above but verifies that the context associated with the `key'
535 matches the `context'. This is handy to use with hash tables that may
536 have duplicate keys. In that case the `context' may be used to check
537 whether the correct entry is being deleted. */
539 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
542 SilcHashTableEntry *entry, prev, e;
544 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
546 ht->hash_user_context,
548 ht->compare_user_context);
554 if (!prev && e->next)
556 if (!prev && e->next == NULL)
561 prev->next = e->next;
564 ht->destructor(e->key, e->context, ht->destructor_user_context);
569 if (SILC_HASH_REHASH_DEC)
570 silc_hash_table_rehash(ht, 0);
575 /* Same as above but with specific hash and compare functions. */
577 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
579 SilcHashFunction hash,
580 void *hash_user_context,
581 SilcHashCompare compare,
582 void *compare_user_context,
583 SilcHashDestructor destructor,
584 void *destructor_user_context)
586 SilcHashTableEntry *entry, prev, e;
588 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
589 hash ? hash : ht->hash,
592 ht->hash_user_context,
594 compare : ht->compare,
595 compare_user_context ?
596 compare_user_context :
597 ht->compare_user_context);
603 if (!prev && e->next)
605 if (!prev && e->next == NULL)
610 prev->next = e->next;
613 destructor(e->key, e->context, destructor_user_context);
616 ht->destructor(e->key, e->context, ht->destructor_user_context);
622 if (SILC_HASH_REHASH_DEC)
623 silc_hash_table_rehash(ht, 0);
628 /* Finds the entry in the hash table by the provided `key' as fast as
629 possible. Return TRUE if the entry was found and FALSE otherwise.
630 The found entry is returned to the `ret_key' and `ret_context',
631 respectively. If the `ret_key and `ret_context' are NULL then this
632 maybe used only to check whether given key exists in the table. */
634 bool silc_hash_table_find(SilcHashTable ht, void *key,
635 void **ret_key, void **ret_context)
637 SilcHashTableEntry *entry;
639 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
640 ht->hash_user_context,
642 ht->compare_user_context);
647 *ret_key = (*entry)->key;
649 *ret_context = (*entry)->context;
654 /* Same as above but with specified hash and comparison functions. */
656 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
657 void **ret_key, void **ret_context,
658 SilcHashFunction hash,
659 void *hash_user_context,
660 SilcHashCompare compare,
661 void *compare_user_context)
663 SilcHashTableEntry *entry;
665 entry = silc_hash_table_find_internal_simple(ht, key,
666 hash ? hash : ht->hash,
669 ht->hash_user_context,
672 compare_user_context ?
673 compare_user_context :
674 ht->compare_user_context);
679 *ret_key = (*entry)->key;
681 *ret_context = (*entry)->context;
686 /* As the hash table is collision resistant it is possible to save duplicate
687 keys to the hash table. This function can be used to find all keys
688 and contexts from the hash table that are found using the `key'. The
689 `foreach' is called for every found key. */
691 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
692 SilcHashForeach foreach, void *user_context)
694 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
695 ht->compare, ht->compare_user_context,
696 foreach, user_context);
699 /* Same as above but with specific hash and comparison functions. */
701 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
702 SilcHashFunction hash,
703 void *hash_user_context,
704 SilcHashCompare compare,
705 void *compare_user_context,
706 SilcHashForeach foreach,
707 void *foreach_user_context)
709 silc_hash_table_find_internal_all(ht, key,
710 hash ? hash : ht->hash,
713 ht->hash_user_context,
716 compare_user_context ?
717 compare_user_context :
718 ht->compare_user_context,
719 foreach, foreach_user_context);
722 /* Traverse all entrys in the hash table and call the `foreach' for
723 every entry with the `user_context' context. */
725 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
728 SilcHashTableEntry e, tmp;
735 auto_rehash = ht->auto_rehash;
736 ht->auto_rehash = FALSE;
737 for (i = 0; i < primesize[ht->table_size]; i++) {
740 /* Entry may become invalid inside the `foreach' */
742 foreach(e->key, e->context, user_context);
746 ht->auto_rehash = auto_rehash;
749 /* Rehashs the hash table. The size of the new hash table is provided
750 as `new_size'. If the `new_size' is zero then this routine will make
751 the new table of a suitable size. Note that this operation may be
754 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
757 SilcHashTableEntry *table, e, tmp;
758 uint32 table_size, size_index;
760 SILC_HT_DEBUG(("Start"));
763 silc_hash_table_primesize(new_size, &size_index);
765 silc_hash_table_primesize(ht->entry_count, &size_index);
767 if (size_index == ht->table_size)
770 SILC_HT_DEBUG(("Rehashing"));
772 /* Take old hash table */
774 table_size = ht->table_size;
776 /* Allocate new table */
777 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
778 ht->table_size = size_index;
782 for (i = 0; i < primesize[table_size]; i++) {
785 silc_hash_table_add(ht, e->key, e->context);
789 /* Remove old entry */
794 /* Remove old table */
798 /* Same as above but with specific hash function. */
800 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
801 SilcHashFunction hash,
802 void *hash_user_context)
805 SilcHashTableEntry *table, e, tmp;
806 uint32 table_size, size_index;
808 SILC_HT_DEBUG(("Start"));
811 silc_hash_table_primesize(new_size, &size_index);
813 silc_hash_table_primesize(ht->entry_count, &size_index);
815 if (size_index == ht->table_size)
818 SILC_HT_DEBUG(("Rehashing"));
820 /* Take old hash table */
822 table_size = ht->table_size;
824 /* Allocate new table */
825 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
826 ht->table_size = size_index;
830 for (i = 0; i < primesize[table_size]; i++) {
833 silc_hash_table_add_ext(ht, e->key, e->context, hash,
838 /* Remove old entry */
843 /* Remove old table */
847 /* Prepares the `htl' list structure sent as argument to be used in the
848 hash table traversing with the silc_hash_table_get. Usage:
849 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
851 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
856 htl->auto_rehash = ht->auto_rehash;
858 /* Disallow rehashing of the table while traversing the table */
859 ht->auto_rehash = FALSE;
862 /* Resets the `htl' SilcHashTableList. */
864 void silc_hash_table_list_reset(SilcHashTableList *htl)
866 /* Set back the original auto rehash value to the table */
867 htl->ht->auto_rehash = htl->auto_rehash;
870 /* Returns always the next entry in the hash table into the `key' and
871 `context' and TRUE. If this returns FALSE then there are no anymore
872 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
874 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
876 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
878 if (!htl->ht->entry_count)
881 while (!entry && htl->index < primesize[htl->ht->table_size]) {
882 entry = htl->ht->table[htl->index];
889 htl->entry = entry->next;
894 *context = entry->context;