5 Author: Pekka Riikonen <priikone@silcnet.org>
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, 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(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(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(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(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(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(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;
310 if (SILC_HASH_REHASH_INC)
311 silc_hash_table_rehash(ht, 0);
314 /* Allocates new hash table and returns it. If the `table_size' is not
315 zero then the hash table size is the size provided. If zero then the
316 default size will be used. Note that if the `table_size' is provided
317 it should be a prime. The `hash', `compare' and `destructor' are
318 the hash function, the key comparison function and key and context
319 destructor function, respectively. The `hash' is mandatory, the others
322 SilcHashTable silc_hash_table_alloc(uint32 table_size,
323 SilcHashFunction hash,
324 void *hash_user_context,
325 SilcHashCompare compare,
326 void *compare_user_context,
327 SilcHashDestructor destructor,
328 void *destructor_user_context,
332 uint32 size_index = SILC_HASH_TABLE_SIZE;
337 ht = silc_calloc(1, sizeof(*ht));
338 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
340 primesize[SILC_HASH_TABLE_SIZE],
342 ht->table_size = size_index;
344 ht->compare = compare;
345 ht->destructor = destructor;
346 ht->hash_user_context = hash_user_context;
347 ht->compare_user_context = compare_user_context;
348 ht->destructor_user_context = destructor_user_context;
349 ht->auto_rehash = auto_rehash;
354 /* Frees the hash table. The destructor function provided in the
355 silc_hash_table_alloc will be called for all keys in the hash table. */
357 void silc_hash_table_free(SilcHashTable ht)
359 SilcHashTableEntry e, tmp;
362 for (i = 0; i < primesize[ht->table_size]; i++) {
366 ht->destructor(e->key, e->context, ht->destructor_user_context);
373 silc_free(ht->table);
377 /* Returns the size of the hash table */
379 uint32 silc_hash_table_size(SilcHashTable ht)
381 return primesize[ht->table_size];
384 /* Returns the number of the entires in the hash table. If there is more
385 entries in the table thatn the size of the hash table calling the
386 silc_hash_table_rehash is recommended. */
388 uint32 silc_hash_table_count(SilcHashTable ht)
390 return ht->entry_count;
393 /* Adds new entry to the hash table. The `key' is hashed using the
394 hash function and the both `key' and `context' will be saved to the
395 hash table. This function quarantees that the entry is always added
396 to the hash table reliably (it is collision resistant). */
398 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
400 silc_hash_table_add_internal(ht, key, context, ht->hash,
401 ht->hash_user_context);
404 /* Same as above but with specific hash function and user context. */
406 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
407 SilcHashFunction hash, void *hash_user_context)
409 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
412 /* Same as above but if the `key' already exists in the hash table
413 the old key and the old context will be replace with the `key' and
414 the `context. The destructor function will be called for the
415 replaced key and context. */
417 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
419 silc_hash_table_replace_internal(ht, key, context, ht->hash,
420 ht->hash_user_context);
423 /* Same as above but with specific hash function. */
425 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
426 SilcHashFunction hash,
427 void *hash_user_context)
429 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
432 /* Removes the entry from the hash table by the provided `key'. This will
433 call the destructor funtion for the found entry. Return TRUE if the
434 entry was removed successfully and FALSE otherwise. */
436 bool silc_hash_table_del(SilcHashTable ht, void *key)
438 SilcHashTableEntry *entry, prev, e;
440 entry = silc_hash_table_find_internal(ht, key, &prev,
441 ht->hash, ht->hash_user_context,
442 ht->compare, ht->compare_user_context);
448 if (!prev && e->next)
450 if (!prev && e->next == NULL)
455 prev->next = e->next;
458 ht->destructor(e->key, e->context, ht->destructor_user_context);
463 if (SILC_HASH_REHASH_DEC)
464 silc_hash_table_rehash(ht, 0);
469 /* Same as above but with specific hash and compare functions. */
471 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
472 SilcHashFunction hash,
473 void *hash_user_context,
474 SilcHashCompare compare,
475 void *compare_user_context,
476 SilcHashDestructor destructor,
477 void *destructor_user_context)
479 SilcHashTableEntry *entry, prev, e;
481 entry = silc_hash_table_find_internal(ht, key, &prev,
482 hash ? hash : ht->hash,
483 hash_user_context ? hash_user_context :
484 ht->hash_user_context,
485 compare ? compare : ht->compare,
486 compare_user_context ?
487 compare_user_context :
488 ht->compare_user_context);
494 if (!prev && e->next)
496 if (!prev && e->next == NULL)
501 prev->next = e->next;
504 destructor(e->key, e->context, destructor_user_context);
507 ht->destructor(e->key, e->context, ht->destructor_user_context);
513 if (SILC_HASH_REHASH_DEC)
514 silc_hash_table_rehash(ht, 0);
519 /* Same as above but verifies that the context associated with the `key'
520 matches the `context'. This is handy to use with hash tables that may
521 have duplicate keys. In that case the `context' may be used to check
522 whether the correct entry is being deleted. */
524 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
527 SilcHashTableEntry *entry, prev, e;
529 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
531 ht->hash_user_context,
533 ht->compare_user_context);
539 if (!prev && e->next)
541 if (!prev && e->next == NULL)
546 prev->next = e->next;
549 ht->destructor(e->key, e->context, ht->destructor_user_context);
554 if (SILC_HASH_REHASH_DEC)
555 silc_hash_table_rehash(ht, 0);
560 /* Same as above but with specific hash and compare functions. */
562 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
564 SilcHashFunction hash,
565 void *hash_user_context,
566 SilcHashCompare compare,
567 void *compare_user_context,
568 SilcHashDestructor destructor,
569 void *destructor_user_context)
571 SilcHashTableEntry *entry, prev, e;
573 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
574 hash ? hash : ht->hash,
577 ht->hash_user_context,
579 compare : ht->compare,
580 compare_user_context ?
581 compare_user_context :
582 ht->compare_user_context);
588 if (!prev && e->next)
590 if (!prev && e->next == NULL)
595 prev->next = e->next;
598 destructor(e->key, e->context, destructor_user_context);
601 ht->destructor(e->key, e->context, ht->destructor_user_context);
607 if (SILC_HASH_REHASH_DEC)
608 silc_hash_table_rehash(ht, 0);
613 /* Finds the entry in the hash table by the provided `key' as fast as
614 possible. Return TRUE if the entry was found and FALSE otherwise.
615 The found entry is returned to the `ret_key' and `ret_context',
616 respectively. If the `ret_key and `ret_context' are NULL then this
617 maybe used only to check whether given key exists in the table. */
619 bool silc_hash_table_find(SilcHashTable ht, void *key,
620 void **ret_key, void **ret_context)
622 SilcHashTableEntry *entry;
624 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
625 ht->hash_user_context,
627 ht->compare_user_context);
632 *ret_key = (*entry)->key;
634 *ret_context = (*entry)->context;
639 /* Same as above but with specified hash and comparison functions. */
641 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
642 void **ret_key, void **ret_context,
643 SilcHashFunction hash,
644 void *hash_user_context,
645 SilcHashCompare compare,
646 void *compare_user_context)
648 SilcHashTableEntry *entry;
650 entry = silc_hash_table_find_internal_simple(ht, key,
651 hash ? hash : ht->hash,
654 ht->hash_user_context,
657 compare_user_context ?
658 compare_user_context :
659 ht->compare_user_context);
664 *ret_key = (*entry)->key;
666 *ret_context = (*entry)->context;
671 /* As the hash table is collision resistant it is possible to save duplicate
672 keys to the hash table. This function can be used to find all keys
673 and contexts from the hash table that are found using the `key'. The
674 `foreach' is called for every found key. */
676 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
677 SilcHashForeach foreach, void *user_context)
679 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
680 ht->compare, ht->compare_user_context,
681 foreach, user_context);
684 /* Same as above but with specific hash and comparison functions. */
686 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
687 SilcHashFunction hash,
688 void *hash_user_context,
689 SilcHashCompare compare,
690 void *compare_user_context,
691 SilcHashForeach foreach,
692 void *foreach_user_context)
694 silc_hash_table_find_internal_all(ht, key,
695 hash ? hash : ht->hash,
698 ht->hash_user_context,
701 compare_user_context ?
702 compare_user_context :
703 ht->compare_user_context,
704 foreach, foreach_user_context);
707 /* Traverse all entrys in the hash table and call the `foreach' for
708 every entry with the `user_context' context. */
710 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
713 SilcHashTableEntry e, tmp;
719 for (i = 0; i < primesize[ht->table_size]; i++) {
722 /* Entry may become invalid inside the `foreach' */
724 foreach(e->key, e->context, user_context);
730 /* Rehashs the hash table. The size of the new hash table is provided
731 as `new_size'. If the `new_size' is zero then this routine will make
732 the new table of a suitable size. Note that this operation may be
735 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
738 SilcHashTableEntry *table, e, tmp;
739 uint32 table_size, size_index;
741 SILC_HT_DEBUG(("Start"));
744 silc_hash_table_primesize(new_size, &size_index);
746 silc_hash_table_primesize(ht->entry_count, &size_index);
748 if (size_index == ht->table_size)
751 SILC_HT_DEBUG(("Rehashing"));
753 /* Take old hash table */
755 table_size = ht->table_size;
757 /* Allocate new table */
758 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
759 ht->table_size = size_index;
763 for (i = 0; i < primesize[table_size]; i++) {
766 silc_hash_table_add(ht, e->key, e->context);
770 /* Remove old entry */
775 /* Remove old table */
779 /* Same as above but with specific hash function. */
781 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
782 SilcHashFunction hash,
783 void *hash_user_context)
786 SilcHashTableEntry *table, e, tmp;
787 uint32 table_size, size_index;
789 SILC_HT_DEBUG(("Start"));
792 silc_hash_table_primesize(new_size, &size_index);
794 silc_hash_table_primesize(ht->entry_count, &size_index);
796 if (size_index == ht->table_size)
799 SILC_HT_DEBUG(("Rehashing"));
801 /* Take old hash table */
803 table_size = ht->table_size;
805 /* Allocate new table */
806 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
807 ht->table_size = size_index;
811 for (i = 0; i < primesize[table_size]; i++) {
814 silc_hash_table_add_ext(ht, e->key, e->context, hash,
819 /* Remove old entry */
824 /* Remove old table */
828 /* Prepares the `htl' list structure sent as argument to be used in the
829 hash table traversing with the silc_hash_table_get. Usage:
830 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
832 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
839 /* Returns always the next entry in the hash table into the `key' and
840 `context' and TRUE. If this returns FALSE then there are no anymore
841 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
843 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
845 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
847 if (!htl->ht->entry_count)
850 while (!entry && htl->index < primesize[htl->ht->table_size]) {
851 entry = htl->ht->table[htl->index];
858 htl->entry = entry->next;
863 *context = entry->context;