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, 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)
477 SilcHashTableEntry *entry, prev, e;
479 entry = silc_hash_table_find_internal(ht, key, &prev,
480 hash ? hash : ht->hash,
481 hash_user_context ? hash_user_context :
482 ht->hash_user_context,
483 compare ? compare : ht->compare,
484 compare_user_context ?
485 compare_user_context :
486 ht->compare_user_context);
492 if (!prev && e->next)
494 if (!prev && e->next == NULL)
499 prev->next = e->next;
502 ht->destructor(e->key, e->context, ht->destructor_user_context);
507 if (SILC_HASH_REHASH_DEC)
508 silc_hash_table_rehash(ht, 0);
513 /* Same as above but verifies that the context associated with the `key'
514 matches the `context'. This is handy to use with hash tables that may
515 have duplicate keys. In that case the `context' may be used to check
516 whether the correct entry is being deleted. */
518 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
521 SilcHashTableEntry *entry, prev, e;
523 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
525 ht->hash_user_context,
527 ht->compare_user_context);
533 if (!prev && e->next)
535 if (!prev && e->next == NULL)
540 prev->next = e->next;
543 ht->destructor(e->key, e->context, ht->destructor_user_context);
548 if (SILC_HASH_REHASH_DEC)
549 silc_hash_table_rehash(ht, 0);
554 /* Same as above but with specific hash and compare functions. */
556 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
558 SilcHashFunction hash,
559 void *hash_user_context,
560 SilcHashCompare compare,
561 void *compare_user_context)
563 SilcHashTableEntry *entry, prev, e;
565 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
566 hash ? hash : ht->hash,
569 ht->hash_user_context,
571 compare : ht->compare,
572 compare_user_context ?
573 compare_user_context :
574 ht->compare_user_context);
580 if (!prev && e->next)
582 if (!prev && e->next == NULL)
587 prev->next = e->next;
590 ht->destructor(e->key, e->context, ht->destructor_user_context);
595 if (SILC_HASH_REHASH_DEC)
596 silc_hash_table_rehash(ht, 0);
601 /* Finds the entry in the hash table by the provided `key' as fast as
602 possible. Return TRUE if the entry was found and FALSE otherwise.
603 The found entry is returned to the `ret_key' and `ret_context',
604 respectively. If the `ret_key and `ret_context' are NULL then this
605 maybe used only to check whether given key exists in the table. */
607 bool silc_hash_table_find(SilcHashTable ht, void *key,
608 void **ret_key, void **ret_context)
610 SilcHashTableEntry *entry;
612 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
613 ht->hash_user_context,
615 ht->compare_user_context);
620 *ret_key = (*entry)->key;
622 *ret_context = (*entry)->context;
627 /* Same as above but with specified hash and comparison functions. */
629 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
630 void **ret_key, void **ret_context,
631 SilcHashFunction hash,
632 void *hash_user_context,
633 SilcHashCompare compare,
634 void *compare_user_context)
636 SilcHashTableEntry *entry;
638 entry = silc_hash_table_find_internal_simple(ht, key,
639 hash ? hash : ht->hash,
642 ht->hash_user_context,
645 compare_user_context ?
646 compare_user_context :
647 ht->compare_user_context);
652 *ret_key = (*entry)->key;
654 *ret_context = (*entry)->context;
659 /* As the hash table is collision resistant it is possible to save duplicate
660 keys to the hash table. This function can be used to find all keys
661 and contexts from the hash table that are found using the `key'. The
662 `foreach' is called for every found key. */
664 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
665 SilcHashForeach foreach, void *user_context)
667 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
668 ht->compare, ht->compare_user_context,
669 foreach, user_context);
672 /* Same as above but with specific hash and comparison functions. */
674 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
675 SilcHashFunction hash,
676 void *hash_user_context,
677 SilcHashCompare compare,
678 void *compare_user_context,
679 SilcHashForeach foreach,
680 void *foreach_user_context)
682 silc_hash_table_find_internal_all(ht, key,
683 hash ? hash : ht->hash,
686 ht->hash_user_context,
689 compare_user_context ?
690 compare_user_context :
691 ht->compare_user_context,
692 foreach, foreach_user_context);
695 /* Traverse all entrys in the hash table and call the `foreach' for
696 every entry with the `user_context' context. */
698 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
701 SilcHashTableEntry e, tmp;
707 for (i = 0; i < primesize[ht->table_size]; i++) {
710 /* Entry may become invalid inside the `foreach' */
712 foreach(e->key, e->context, user_context);
718 /* Rehashs the hash table. The size of the new hash table is provided
719 as `new_size'. If the `new_size' is zero then this routine will make
720 the new table of a suitable size. Note that this operation may be
723 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
726 SilcHashTableEntry *table, e, tmp;
727 uint32 table_size, size_index;
729 SILC_HT_DEBUG(("Start"));
732 silc_hash_table_primesize(new_size, &size_index);
734 silc_hash_table_primesize(ht->entry_count, &size_index);
736 if (size_index == ht->table_size)
739 SILC_HT_DEBUG(("Rehashing"));
741 /* Take old hash table */
743 table_size = ht->table_size;
745 /* Allocate new table */
746 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
747 ht->table_size = size_index;
751 for (i = 0; i < primesize[table_size]; i++) {
754 silc_hash_table_add(ht, e->key, e->context);
758 /* Remove old entry */
763 /* Remove old table */
767 /* Same as above but with specific hash function. */
769 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
770 SilcHashFunction hash,
771 void *hash_user_context)
774 SilcHashTableEntry *table, e, tmp;
775 uint32 table_size, size_index;
777 SILC_HT_DEBUG(("Start"));
780 silc_hash_table_primesize(new_size, &size_index);
782 silc_hash_table_primesize(ht->entry_count, &size_index);
784 if (size_index == ht->table_size)
787 SILC_HT_DEBUG(("Rehashing"));
789 /* Take old hash table */
791 table_size = ht->table_size;
793 /* Allocate new table */
794 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
795 ht->table_size = size_index;
799 for (i = 0; i < primesize[table_size]; i++) {
802 silc_hash_table_add_ext(ht, e->key, e->context, hash,
807 /* Remove old entry */
812 /* Remove old table */
816 /* Prepares the `htl' list structure sent as argument to be used in the
817 hash table traversing with the silc_hash_table_get. Usage:
818 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
820 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
827 /* Returns always the next entry in the hash table into the `key' and
828 `context' and TRUE. If this returns FALSE then there are no anymore
829 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
831 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
833 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
835 if (!htl->ht->entry_count)
838 while (!entry && htl->index < primesize[htl->ht->table_size]) {
839 entry = htl->ht->table[htl->index];
846 htl->entry = entry->next;
851 *context = entry->context;