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 \
46 (ht->hash(key, ht->hash_user_context) % primesize[ht->table_size])
47 #define SILC_HASH_TABLE_HASH_F(f, c) \
48 ((f)(key, (c)) % primesize[ht->table_size])
50 /* One entry in the hash table. Includes the key and the associated
51 context. The `next' pointer is non-NULL if two (or more) different
52 keys hashed to same value. The pointer is the pointer to the next
54 typedef struct SilcHashTableEntryStruct {
57 struct SilcHashTableEntryStruct *next;
58 } *SilcHashTableEntry;
61 struct SilcHashTableStruct {
62 SilcHashTableEntry *table;
65 SilcHashFunction hash;
66 SilcHashCompare compare;
67 SilcHashDestructor destructor;
68 void *hash_user_context;
69 void *compare_user_context;
70 void *destructor_user_context;
73 /* Prime sizes for the hash table. The size of the table will always
75 const uint32 primesize[42] =
77 1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
78 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
79 65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
80 4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
83 /* Find appropriate size for the hash table. The size will be a prime. */
85 static uint32 silc_hash_table_primesize(uint32 size, uint32 *index)
89 for (i = 0; i < sizeof(primesize); i++)
90 if (primesize[i] >= size) {
92 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
97 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
98 return primesize[i - 1];
101 /* Internal routine to find entry in the hash table by `key'. Returns
102 the previous entry (if exists) as well. */
104 static inline SilcHashTableEntry *
105 silc_hash_table_find_internal(SilcHashTable ht, void *key,
106 SilcHashTableEntry *prev_entry,
107 SilcHashFunction hash, void *hash_user_context,
108 SilcHashCompare compare,
109 void *compare_user_context)
111 SilcHashTableEntry *entry, prev = NULL;
112 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
114 SILC_HT_DEBUG(("index %d key %p", i, key));
116 entry = &ht->table[i];
118 while (*entry && !compare((*entry)->key, key, compare_user_context)) {
120 entry = &(*entry)->next;
123 while (*entry && (*entry)->key != key) {
125 entry = &(*entry)->next;
133 /* Internal routine to find entry in the hash table by `key' and `context'.
134 Returns the previous entry (if exists) as well. */
136 static inline SilcHashTableEntry *
137 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
139 SilcHashTableEntry *prev_entry,
140 SilcHashFunction hash,
141 void *hash_user_context,
142 SilcHashCompare compare,
143 void *compare_user_context)
145 SilcHashTableEntry *entry, prev = NULL;
146 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
148 SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
150 entry = &ht->table[i];
153 if (compare((*entry)->key, key, compare_user_context) &&
154 (*entry)->context == context)
157 entry = &(*entry)->next;
161 if ((*entry)->key == key && (*entry)->context == context)
164 entry = &(*entry)->next;
172 /* Internal routine to find entry in the hash table by `key'. */
174 static inline SilcHashTableEntry *
175 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
176 SilcHashFunction hash,
177 void *hash_user_context,
178 SilcHashCompare compare,
179 void *compare_user_context)
181 SilcHashTableEntry *entry;
182 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
184 SILC_HT_DEBUG(("index %d key %p", i, key));
186 entry = &ht->table[i];
188 while (*entry && !compare((*entry)->key, key, compare_user_context))
189 entry = &(*entry)->next;
191 while (*entry && (*entry)->key != key)
192 entry = &(*entry)->next;
198 /* Internal routine to find all keys by `key'. This may return multiple
199 entries if multiple entries with same key exists. With specific
200 hash and comparison functions. */
203 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
204 SilcHashFunction hash,
205 void *hash_user_context,
206 SilcHashCompare compare,
207 void *compare_user_context,
208 SilcHashForeach foreach,
209 void *foreach_user_context)
211 SilcHashTableEntry *entry;
212 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
214 SILC_HT_DEBUG(("index %d key %p", i, key));
216 entry = &ht->table[i];
219 if (compare((*entry)->key, key, compare_user_context))
220 foreach((*entry)->key, (*entry)->context, foreach_user_context);
221 entry = &(*entry)->next;
225 if ((*entry)->key == key)
226 foreach((*entry)->key, (*entry)->context, foreach_user_context);
227 entry = &(*entry)->next;
232 /* Internal routine to add new key to the hash table */
235 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
236 SilcHashFunction hash,
237 void *hash_user_context)
239 SilcHashTableEntry *entry;
240 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
242 SILC_HT_DEBUG(("index %d key %p", i, key));
244 entry = &ht->table[i];
246 /* The entry exists already. We have a collision, add it to the
247 list to avoid collision. */
248 SilcHashTableEntry e, tmp;
257 SILC_HT_DEBUG(("Collision; adding new key to list"));
259 e->next = silc_calloc(1, sizeof(*e->next));
261 e->next->context = context;
265 SILC_HT_DEBUG(("New key"));
266 *entry = silc_calloc(1, sizeof(**entry));
268 (*entry)->context = context;
273 /* Internal routine to replace old key with new one (if it exists) */
276 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
277 SilcHashFunction hash,
278 void *hash_user_context)
280 SilcHashTableEntry *entry;
281 uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
283 SILC_HT_DEBUG(("index %d key %p", i, key));
285 entry = &ht->table[i];
287 /* The entry exists already. We have a collision, replace the old
290 ht->destructor((*entry)->key, (*entry)->context,
291 ht->destructor_user_context);
294 *entry = silc_calloc(1, sizeof(**entry));
299 (*entry)->context = context;
302 /* Allocates new hash table and returns it. If the `table_size' is not
303 zero then the hash table size is the size provided. If zero then the
304 default size will be used. Note that if the `table_size' is provided
305 it should be a prime. The `hash', `compare' and `destructor' are
306 the hash function, the key comparison function and key and context
307 destructor function, respectively. The `hash' is mandatory, the others
310 SilcHashTable silc_hash_table_alloc(uint32 table_size,
311 SilcHashFunction hash,
312 void *hash_user_context,
313 SilcHashCompare compare,
314 void *compare_user_context,
315 SilcHashDestructor destructor,
316 void *destructor_user_context)
319 uint32 size_index = SILC_HASH_TABLE_SIZE;
324 ht = silc_calloc(1, sizeof(*ht));
325 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
327 primesize[SILC_HASH_TABLE_SIZE],
329 ht->table_size = size_index;
331 ht->compare = compare;
332 ht->destructor = destructor;
333 ht->hash_user_context = hash_user_context;
334 ht->compare_user_context = compare_user_context;
335 ht->destructor_user_context = destructor_user_context;
340 /* Frees the hash table. The destructor function provided in the
341 silc_hash_table_alloc will be called for all keys in the hash table. */
343 void silc_hash_table_free(SilcHashTable ht)
345 SilcHashTableEntry e, tmp;
348 for (i = 0; i < primesize[ht->table_size]; i++) {
352 ht->destructor(e->key, e->context, ht->destructor_user_context);
359 silc_free(ht->table);
363 /* Returns the size of the hash table */
365 uint32 silc_hash_table_size(SilcHashTable ht)
367 return primesize[ht->table_size];
370 /* Returns the number of the entires in the hash table. If there is more
371 entries in the table thatn the size of the hash table calling the
372 silc_hash_table_rehash is recommended. */
374 uint32 silc_hash_table_count(SilcHashTable ht)
376 return ht->entry_count;
379 /* Adds new entry to the hash table. The `key' is hashed using the
380 hash function and the both `key' and `context' will be saved to the
381 hash table. This function quarantees that the entry is always added
382 to the hash table reliably (it is collision resistant). */
384 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
386 silc_hash_table_add_internal(ht, key, context, ht->hash,
387 ht->hash_user_context);
390 /* Same as above but with specific hash function and user context. */
392 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
393 SilcHashFunction hash, void *hash_user_context)
395 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
398 /* Same as above but if the `key' already exists in the hash table
399 the old key and the old context will be replace with the `key' and
400 the `context. The destructor function will be called for the
401 replaced key and context. */
403 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
405 silc_hash_table_replace_internal(ht, key, context, ht->hash,
406 ht->hash_user_context);
409 /* Same as above but with specific hash function. */
411 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
412 SilcHashFunction hash,
413 void *hash_user_context)
415 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
418 /* Removes the entry from the hash table by the provided `key'. This will
419 call the destructor funtion for the found entry. Return TRUE if the
420 entry was removed successfully and FALSE otherwise. */
422 bool silc_hash_table_del(SilcHashTable ht, void *key)
424 SilcHashTableEntry *entry, prev, e;
426 entry = silc_hash_table_find_internal(ht, key, &prev,
427 ht->hash, ht->hash_user_context,
428 ht->compare, ht->compare_user_context);
434 if (!prev && e->next)
436 if (!prev && e->next == NULL)
441 prev->next = e->next;
444 ht->destructor(e->key, e->context, ht->destructor_user_context);
452 /* Same as above but with specific hash and compare functions. */
454 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
455 SilcHashFunction hash,
456 void *hash_user_context,
457 SilcHashCompare compare,
458 void *compare_user_context)
460 SilcHashTableEntry *entry, prev, e;
462 entry = silc_hash_table_find_internal(ht, key, &prev,
463 hash ? hash : ht->hash,
464 hash_user_context ? hash_user_context :
465 ht->hash_user_context,
466 compare ? compare : ht->compare,
467 compare_user_context ?
468 compare_user_context :
469 ht->compare_user_context);
475 if (!prev && e->next)
477 if (!prev && e->next == NULL)
482 prev->next = e->next;
485 ht->destructor(e->key, e->context, ht->destructor_user_context);
493 /* Same as above but verifies that the context associated with the `key'
494 matches the `context'. This is handy to use with hash tables that may
495 have duplicate keys. In that case the `context' may be used to check
496 whether the correct entry is being deleted. */
498 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
501 SilcHashTableEntry *entry, prev, e;
503 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
505 ht->hash_user_context,
507 ht->compare_user_context);
513 if (!prev && e->next)
515 if (!prev && e->next == NULL)
520 prev->next = e->next;
523 ht->destructor(e->key, e->context, ht->destructor_user_context);
531 /* Same as above but with specific hash and compare functions. */
533 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
535 SilcHashFunction hash,
536 void *hash_user_context,
537 SilcHashCompare compare,
538 void *compare_user_context)
540 SilcHashTableEntry *entry, prev, e;
542 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
543 hash ? hash : ht->hash,
546 ht->hash_user_context,
548 compare : ht->compare,
549 compare_user_context ?
550 compare_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);
575 /* Finds the entry in the hash table by the provided `key' as fast as
576 possible. Return TRUE if the entry was found and FALSE otherwise.
577 The found entry is returned to the `ret_key' and `ret_context',
578 respectively. If the `ret_key and `ret_context' are NULL then this
579 maybe used only to check whether given key exists in the table. */
581 bool silc_hash_table_find(SilcHashTable ht, void *key,
582 void **ret_key, void **ret_context)
584 SilcHashTableEntry *entry;
586 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
587 ht->hash_user_context,
589 ht->compare_user_context);
594 *ret_key = (*entry)->key;
596 *ret_context = (*entry)->context;
601 /* Same as above but with specified hash and comparison functions. */
603 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
604 void **ret_key, void **ret_context,
605 SilcHashFunction hash,
606 void *hash_user_context,
607 SilcHashCompare compare,
608 void *compare_user_context)
610 SilcHashTableEntry *entry;
612 entry = silc_hash_table_find_internal_simple(ht, key,
613 hash ? hash : ht->hash,
616 ht->hash_user_context,
619 compare_user_context ?
620 compare_user_context :
621 ht->compare_user_context);
626 *ret_key = (*entry)->key;
628 *ret_context = (*entry)->context;
633 /* As the hash table is collision resistant it is possible to save duplicate
634 keys to the hash table. This function can be used to find all keys
635 and contexts from the hash table that are found using the `key'. The
636 `foreach' is called for every found key. */
638 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
639 SilcHashForeach foreach, void *user_context)
641 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
642 ht->compare, ht->compare_user_context,
643 foreach, user_context);
646 /* Same as above but with specific hash and comparison functions. */
648 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
649 SilcHashFunction hash,
650 void *hash_user_context,
651 SilcHashCompare compare,
652 void *compare_user_context,
653 SilcHashForeach foreach,
654 void *foreach_user_context)
656 silc_hash_table_find_internal_all(ht, key,
657 hash ? hash : ht->hash,
660 ht->hash_user_context,
663 compare_user_context ?
664 compare_user_context :
665 ht->compare_user_context,
666 foreach, foreach_user_context);
669 /* Traverse all entrys in the hash table and call the `foreach' for
670 every entry with the `user_context' context. */
672 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
675 SilcHashTableEntry e, tmp;
681 for (i = 0; i < primesize[ht->table_size]; i++) {
684 /* Entry may become invalid inside the `foreach' */
686 foreach(e->key, e->context, user_context);
692 /* Rehashs the hash table. The size of the new hash table is provided
693 as `new_size'. If the `new_size' is zero then this routine will make
694 the new table of a suitable size. Note that this operation may be
697 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
700 SilcHashTableEntry *table, e, tmp;
701 uint32 table_size, size_index;
703 /* Take old hash table */
705 table_size = ht->table_size;
707 /* Allocate new table */
708 ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
710 silc_hash_table_primesize(ht->entry_count,
713 ht->table_size = size_index;
716 for (i = 0; i < primesize[table_size]; i++) {
719 silc_hash_table_add(ht, e->key, e->context);
723 /* Remove old entry */
728 /* Remove old table */
732 /* Same as above but with specific hash function. */
734 void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
735 SilcHashFunction hash,
736 void *hash_user_context)
739 SilcHashTableEntry *table, e, tmp;
740 uint32 table_size, size_index;
742 SILC_HT_DEBUG(("Rehashing"));
744 /* Take old hash table */
746 table_size = ht->table_size;
748 /* Allocate new table */
749 ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
751 silc_hash_table_primesize(ht->entry_count,
754 ht->table_size = size_index;
757 for (i = 0; i < primesize[table_size]; i++) {
760 silc_hash_table_add_ext(ht, e->key, e->context, hash,
765 /* Remove old entry */
770 /* Remove old table */