5 Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
7 Copyright (C) 2001 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; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
20 /* Implementation of collision resistant hash table. This is a hash table
21 that provides a reliable (what you add stays there, and duplicate keys
22 are allowed) with as fast reference to the key as possible. If duplicate
23 keys are a lot in the hash table the lookup gets slower of course.
24 However, this is reliable and no data is lost at any point. If you know
25 that you never have duplicate keys then this is as fast as any simple
29 #include "silcincludes.h"
30 #include "silchashtable.h"
32 /* Define to 1 if you want hash table debug enabled */
33 #define SILC_HASH_TABLE_DEBUG 0
35 #if SILC_HASH_TABLE_DEBUG == 1
36 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
38 #define SILC_HT_DEBUG(fmt)
41 /* Default size of the hash table (index to prime table) */
42 #define SILC_HASH_TABLE_SIZE 3
44 /* Produce the index by hashing the key */
45 #define SILC_HASH_TABLE_HASH_F(f, c) \
46 ((f)(key, (c)) % primesize[ht->table_size])
48 /* Check whether need to rehash */
49 #define SILC_HASH_REHASH_INC \
50 (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
51 #define SILC_HASH_REHASH_DEC \
52 (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
53 ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
55 /* One entry in the hash table. Includes the key and the associated
56 context. The `next' pointer is non-NULL if two (or more) different
57 keys hashed to same value. The pointer is the pointer to the next
59 typedef struct SilcHashTableEntryStruct {
62 struct SilcHashTableEntryStruct *next;
63 } *SilcHashTableEntry;
66 struct SilcHashTableStruct {
67 SilcHashTableEntry *table;
70 SilcHashFunction hash;
71 SilcHashCompare compare;
72 SilcHashDestructor destructor;
73 void *hash_user_context;
74 void *compare_user_context;
75 void *destructor_user_context;
79 /* Prime sizes for the hash table. The size of the table will always
81 const uint32 primesize[42] =
83 1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
84 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
85 65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
86 4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
89 /* Find appropriate size for the hash table. The size will be a prime. */
91 static uint32 silc_hash_table_primesize(uint32 size, uint32 *index)
95 for (i = 0; i < sizeof(primesize); 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 uint32 i = SILC_HASH_TABLE_HASH_F(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. */
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 uint32 i = SILC_HASH_TABLE_HASH_F(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;
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 uint32 i = SILC_HASH_TABLE_HASH_F(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 *entry;
218 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
220 SILC_HT_DEBUG(("index %d key %p", i, key));
222 entry = &ht->table[i];
225 if (compare((*entry)->key, key, compare_user_context))
226 foreach((*entry)->key, (*entry)->context, foreach_user_context);
227 entry = &(*entry)->next;
231 if ((*entry)->key == key)
232 foreach((*entry)->key, (*entry)->context, foreach_user_context);
233 entry = &(*entry)->next;
238 /* Internal routine to add new key to the hash table */
241 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
242 SilcHashFunction hash,
243 void *hash_user_context)
245 SilcHashTableEntry *entry;
246 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
248 SILC_HT_DEBUG(("index %d key %p", i, key));
250 entry = &ht->table[i];
252 /* The entry exists already. We have a collision, add it to the
253 list to avoid collision. */
254 SilcHashTableEntry e, tmp;
263 SILC_HT_DEBUG(("Collision; adding new key to list"));
265 e->next = silc_calloc(1, sizeof(*e->next));
267 e->next->context = context;
271 SILC_HT_DEBUG(("New key"));
272 *entry = silc_calloc(1, sizeof(**entry));
274 (*entry)->context = context;
278 if (SILC_HASH_REHASH_INC)
279 silc_hash_table_rehash(ht, 0);
282 /* Internal routine to replace old key with new one (if it exists) */
285 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
286 SilcHashFunction hash,
287 void *hash_user_context)
289 SilcHashTableEntry *entry;
290 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
292 SILC_HT_DEBUG(("index %d key %p", i, key));
294 entry = &ht->table[i];
296 /* The entry exists already. We have a collision, replace the old
299 ht->destructor((*entry)->key, (*entry)->context,
300 ht->destructor_user_context);
303 *entry = silc_calloc(1, sizeof(**entry));
308 (*entry)->context = context;
311 /* Allocates new hash table and returns it. If the `table_size' is not
312 zero then the hash table size is the size provided. If zero then the
313 default size will be used. Note that if the `table_size' is provided
314 it should be a prime. The `hash', `compare' and `destructor' are
315 the hash function, the key comparison function and key and context
316 destructor function, respectively. The `hash' is mandatory, the others
319 SilcHashTable silc_hash_table_alloc(uint32 table_size,
320 SilcHashFunction hash,
321 void *hash_user_context,
322 SilcHashCompare compare,
323 void *compare_user_context,
324 SilcHashDestructor destructor,
325 void *destructor_user_context,
329 uint32 size_index = SILC_HASH_TABLE_SIZE;
334 ht = silc_calloc(1, sizeof(*ht));
335 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
337 primesize[SILC_HASH_TABLE_SIZE],
339 ht->table_size = size_index;
341 ht->compare = compare;
342 ht->destructor = destructor;
343 ht->hash_user_context = hash_user_context;
344 ht->compare_user_context = compare_user_context;
345 ht->destructor_user_context = destructor_user_context;
346 ht->auto_rehash = auto_rehash;
351 /* Frees the hash table. The destructor function provided in the
352 silc_hash_table_alloc will be called for all keys in the hash table. */
354 void silc_hash_table_free(SilcHashTable ht)
356 SilcHashTableEntry e, tmp;
359 for (i = 0; i < primesize[ht->table_size]; i++) {
363 ht->destructor(e->key, e->context, ht->destructor_user_context);
370 silc_free(ht->table);
374 /* Returns the size of the hash table */
376 uint32 silc_hash_table_size(SilcHashTable ht)
378 return primesize[ht->table_size];
381 /* Returns the number of the entires in the hash table. If there is more
382 entries in the table thatn the size of the hash table calling the
383 silc_hash_table_rehash is recommended. */
385 uint32 silc_hash_table_count(SilcHashTable ht)
387 return ht->entry_count;
390 /* Adds new entry to the hash table. The `key' is hashed using the
391 hash function and the both `key' and `context' will be saved to the
392 hash table. This function quarantees that the entry is always added
393 to the hash table reliably (it is collision resistant). */
395 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
397 silc_hash_table_add_internal(ht, key, context, ht->hash,
398 ht->hash_user_context);
401 /* Same as above but with specific hash function and user context. */
403 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
404 SilcHashFunction hash, void *hash_user_context)
406 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
409 /* Same as above but if the `key' already exists in the hash table
410 the old key and the old context will be replace with the `key' and
411 the `context. The destructor function will be called for the
412 replaced key and context. */
414 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
416 silc_hash_table_replace_internal(ht, key, context, ht->hash,
417 ht->hash_user_context);
420 /* Same as above but with specific hash function. */
422 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
423 SilcHashFunction hash,
424 void *hash_user_context)
426 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
429 /* Removes the entry from the hash table by the provided `key'. This will
430 call the destructor funtion for the found entry. Return TRUE if the
431 entry was removed successfully and FALSE otherwise. */
433 bool silc_hash_table_del(SilcHashTable ht, void *key)
435 SilcHashTableEntry *entry, prev, e;
437 entry = silc_hash_table_find_internal(ht, key, &prev,
438 ht->hash, ht->hash_user_context,
439 ht->compare, ht->compare_user_context);
445 if (!prev && e->next)
447 if (!prev && e->next == NULL)
452 prev->next = e->next;
455 ht->destructor(e->key, e->context, ht->destructor_user_context);
460 if (SILC_HASH_REHASH_DEC)
461 silc_hash_table_rehash(ht, 0);
466 /* Same as above but with specific hash and compare functions. */
468 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
469 SilcHashFunction hash,
470 void *hash_user_context,
471 SilcHashCompare compare,
472 void *compare_user_context)
474 SilcHashTableEntry *entry, prev, e;
476 entry = silc_hash_table_find_internal(ht, key, &prev,
477 hash ? hash : ht->hash,
478 hash_user_context ? hash_user_context :
479 ht->hash_user_context,
480 compare ? compare : ht->compare,
481 compare_user_context ?
482 compare_user_context :
483 ht->compare_user_context);
489 if (!prev && e->next)
491 if (!prev && e->next == NULL)
496 prev->next = e->next;
499 ht->destructor(e->key, e->context, ht->destructor_user_context);
504 if (SILC_HASH_REHASH_DEC)
505 silc_hash_table_rehash(ht, 0);
510 /* Same as above but verifies that the context associated with the `key'
511 matches the `context'. This is handy to use with hash tables that may
512 have duplicate keys. In that case the `context' may be used to check
513 whether the correct entry is being deleted. */
515 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
518 SilcHashTableEntry *entry, prev, e;
520 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
522 ht->hash_user_context,
524 ht->compare_user_context);
530 if (!prev && e->next)
532 if (!prev && e->next == NULL)
537 prev->next = e->next;
540 ht->destructor(e->key, e->context, ht->destructor_user_context);
545 if (SILC_HASH_REHASH_DEC)
546 silc_hash_table_rehash(ht, 0);
551 /* Same as above but with specific hash and compare functions. */
553 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
555 SilcHashFunction hash,
556 void *hash_user_context,
557 SilcHashCompare compare,
558 void *compare_user_context)
560 SilcHashTableEntry *entry, prev, e;
562 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
563 hash ? hash : ht->hash,
566 ht->hash_user_context,
568 compare : ht->compare,
569 compare_user_context ?
570 compare_user_context :
571 ht->compare_user_context);
577 if (!prev && e->next)
579 if (!prev && e->next == NULL)
584 prev->next = e->next;
587 ht->destructor(e->key, e->context, ht->destructor_user_context);
592 if (SILC_HASH_REHASH_DEC)
593 silc_hash_table_rehash(ht, 0);
598 /* Finds the entry in the hash table by the provided `key' as fast as
599 possible. Return TRUE if the entry was found and FALSE otherwise.
600 The found entry is returned to the `ret_key' and `ret_context',
601 respectively. If the `ret_key and `ret_context' are NULL then this
602 maybe used only to check whether given key exists in the table. */
604 bool silc_hash_table_find(SilcHashTable ht, void *key,
605 void **ret_key, void **ret_context)
607 SilcHashTableEntry *entry;
609 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
610 ht->hash_user_context,
612 ht->compare_user_context);
617 *ret_key = (*entry)->key;
619 *ret_context = (*entry)->context;
624 /* Same as above but with specified hash and comparison functions. */
626 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
627 void **ret_key, void **ret_context,
628 SilcHashFunction hash,
629 void *hash_user_context,
630 SilcHashCompare compare,
631 void *compare_user_context)
633 SilcHashTableEntry *entry;
635 entry = silc_hash_table_find_internal_simple(ht, key,
636 hash ? hash : ht->hash,
639 ht->hash_user_context,
642 compare_user_context ?
643 compare_user_context :
644 ht->compare_user_context);
649 *ret_key = (*entry)->key;
651 *ret_context = (*entry)->context;
656 /* As the hash table is collision resistant it is possible to save duplicate
657 keys to the hash table. This function can be used to find all keys
658 and contexts from the hash table that are found using the `key'. The
659 `foreach' is called for every found key. */
661 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
662 SilcHashForeach foreach, void *user_context)
664 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
665 ht->compare, ht->compare_user_context,
666 foreach, user_context);
669 /* Same as above but with specific hash and comparison functions. */
671 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
672 SilcHashFunction hash,
673 void *hash_user_context,
674 SilcHashCompare compare,
675 void *compare_user_context,
676 SilcHashForeach foreach,
677 void *foreach_user_context)
679 silc_hash_table_find_internal_all(ht, key,
680 hash ? hash : ht->hash,
683 ht->hash_user_context,
686 compare_user_context ?
687 compare_user_context :
688 ht->compare_user_context,
689 foreach, foreach_user_context);
692 /* Traverse all entrys in the hash table and call the `foreach' for
693 every entry with the `user_context' context. */
695 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
698 SilcHashTableEntry e, tmp;
704 for (i = 0; i < primesize[ht->table_size]; i++) {
707 /* Entry may become invalid inside the `foreach' */
709 foreach(e->key, e->context, user_context);
715 /* Rehashs the hash table. The size of the new hash table is provided
716 as `new_size'. If the `new_size' is zero then this routine will make
717 the new table of a suitable size. Note that this operation may be
720 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
723 SilcHashTableEntry *table, e, tmp;
724 uint32 table_size, size_index;
726 /* Take old hash table */
728 table_size = ht->table_size;
730 /* Allocate new table */
731 ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
733 silc_hash_table_primesize(ht->entry_count,
736 ht->table_size = size_index;
739 for (i = 0; i < primesize[table_size]; i++) {
742 silc_hash_table_add(ht, e->key, e->context);
746 /* Remove old entry */
751 /* Remove old table */
755 /* Same as above but with specific hash function. */
757 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
758 SilcHashFunction hash,
759 void *hash_user_context)
762 SilcHashTableEntry *table, e, tmp;
763 uint32 table_size, size_index;
765 SILC_HT_DEBUG(("Rehashing"));
767 /* Take old hash table */
769 table_size = ht->table_size;
771 /* Allocate new table */
772 ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
774 silc_hash_table_primesize(ht->entry_count,
777 ht->table_size = size_index;
781 for (i = 0; i < primesize[table_size]; i++) {
784 silc_hash_table_add_ext(ht, e->key, e->context, hash,
789 /* Remove old entry */
794 /* Remove old table */
798 /* Prepares the `htl' list structure sent as argument to be used in the
799 hash table traversing with the silc_hash_table_get. Usage:
800 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
802 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
809 /* Returns always the next entry in the hash table into the `key' and
810 `context' and TRUE. If this returns FALSE then there are no anymore
811 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
813 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
815 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
817 if (!htl->ht->entry_count)
820 while (!entry && htl->index < primesize[htl->ht->table_size]) {
821 entry = htl->ht->table[htl->index];
828 htl->entry = entry->next;
833 *context = entry->context;