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 /* Default size of the hash table (index to prime table) */
33 #define SILC_HASH_TABLE_SIZE 3
35 /* Produce the index by hashing the key */
36 #define SILC_HASH_TABLE_HASH \
37 (ht->hash(key, ht->hash_user_context) % primesize[ht->table_size])
38 #define SILC_HASH_TABLE_HASH_F(f, c) \
39 ((f)(key, (c)) % primesize[ht->table_size])
41 /* One entry in the hash table. Includes the key and the associated
42 context. The `next' pointer is non-NULL if two (or more) different
43 keys hashed to same value. The pointer is the pointer to the next
45 typedef struct SilcHashTableEntryStruct {
48 struct SilcHashTableEntryStruct *next;
49 } *SilcHashTableEntry;
52 struct SilcHashTableStruct {
53 SilcHashTableEntry *table;
56 SilcHashFunction hash;
57 SilcHashCompare compare;
58 SilcHashDestructor destructor;
59 void *hash_user_context;
60 void *compare_user_context;
61 void *destructor_user_context;
64 /* Prime sizes for the hash table. The size of the table will always
66 const uint32 primesize[42] =
68 1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
69 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
70 65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
71 4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
74 /* Find appropriate size for the hash table. The size will be a prime. */
76 static uint32 silc_hash_table_primesize(uint32 size, uint32 *index)
80 for (i = 0; i < sizeof(primesize); i++)
81 if (primesize[i] >= size) {
87 return primesize[i - 1];
90 /* Internal routine to find entry in the hash table by `key'. Returns
91 the previous entry (if exists) as well. */
93 static inline SilcHashTableEntry *
94 silc_hash_table_find_internal(SilcHashTable ht, void *key,
95 SilcHashTableEntry *prev_entry,
96 SilcHashFunction hash, void *hash_user_context,
97 SilcHashCompare compare,
98 void *compare_user_context)
100 SilcHashTableEntry *entry, prev = NULL;
102 entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
104 while (*entry && !compare((*entry)->key, key, compare_user_context)) {
106 entry = &(*entry)->next;
109 while (*entry && (*entry)->key != key) {
111 entry = &(*entry)->next;
119 /* Internal routine to find entry in the hash table by `key' and `context'.
120 Returns the previous entry (if exists) as well. */
122 static inline SilcHashTableEntry *
123 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
125 SilcHashTableEntry *prev_entry,
126 SilcHashFunction hash,
127 void *hash_user_context,
128 SilcHashCompare compare,
129 void *compare_user_context)
131 SilcHashTableEntry *entry, prev = NULL;
133 entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
135 while (*entry && !compare((*entry)->key, key, compare_user_context) &&
136 (*entry)->context != context) {
138 entry = &(*entry)->next;
141 while (*entry && (*entry)->key != key && (*entry)->context != context) {
143 entry = &(*entry)->next;
151 /* Internal routine to find entry in the hash table by `key'. */
153 static inline SilcHashTableEntry *
154 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
155 SilcHashFunction hash,
156 void *hash_user_context,
157 SilcHashCompare compare,
158 void *compare_user_context)
160 SilcHashTableEntry *entry;
162 entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
164 while (*entry && !compare((*entry)->key, key, compare_user_context))
165 entry = &(*entry)->next;
167 while (*entry && (*entry)->key != key)
168 entry = &(*entry)->next;
174 /* Internal routine to find all keys by `key'. This may return multiple
175 entries if multiple entries with same key exists. With specific
176 hash and comparison functions. */
179 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
180 SilcHashFunction hash,
181 void *hash_user_context,
182 SilcHashCompare compare,
183 void *compare_user_context,
184 SilcHashForeach foreach,
185 void *foreach_user_context)
187 SilcHashTableEntry *entry;
189 entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
192 if (compare((*entry)->key, key, compare_user_context))
193 foreach((*entry)->key, (*entry)->context, foreach_user_context);
194 entry = &(*entry)->next;
198 if ((*entry)->key == key)
199 foreach((*entry)->key, (*entry)->context, foreach_user_context);
200 entry = &(*entry)->next;
205 /* Internal routine to add new key to the hash table */
208 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
209 SilcHashFunction hash,
210 void *hash_user_context)
212 SilcHashTableEntry *entry;
213 uint32 index = (hash ? SILC_HASH_TABLE_HASH :
214 SILC_HASH_TABLE_HASH_F(hash, hash_user_context));
216 entry = &ht->table[index];
218 /* The entry exists already. We have a collision, add it to the
219 list to avoid collision. */
220 SilcHashTableEntry e, tmp;
229 e->next = silc_calloc(1, sizeof(*e->next));
231 e->next->context = context;
235 *entry = silc_calloc(1, sizeof(**entry));
237 (*entry)->context = context;
242 /* Internal routine to replace old key with new one (if it exists) */
245 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
246 SilcHashFunction hash,
247 void *hash_user_context)
249 SilcHashTableEntry *entry;
250 uint32 index = (hash ? SILC_HASH_TABLE_HASH :
251 SILC_HASH_TABLE_HASH_F(hash, hash_user_context));
253 entry = &ht->table[index];
255 /* The entry exists already. We have a collision, replace the old
258 ht->destructor((*entry)->key, (*entry)->context,
259 ht->destructor_user_context);
262 *entry = silc_calloc(1, sizeof(**entry));
267 (*entry)->context = context;
270 /* Allocates new hash table and returns it. If the `table_size' is not
271 zero then the hash table size is the size provided. If zero then the
272 default size will be used. Note that if the `table_size' is provided
273 it should be a prime. The `hash', `compare' and `destructor' are
274 the hash function, the key comparison function and key and context
275 destructor function, respectively. The `hash' is mandatory, the others
278 SilcHashTable silc_hash_table_alloc(uint32 table_size,
279 SilcHashFunction hash,
280 void *hash_user_context,
281 SilcHashCompare compare,
282 void *compare_user_context,
283 SilcHashDestructor destructor,
284 void *destructor_user_context)
287 uint32 size_index = SILC_HASH_TABLE_SIZE;
292 ht = silc_calloc(1, sizeof(*ht));
293 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
295 primesize[SILC_HASH_TABLE_SIZE],
297 ht->table_size = size_index;
299 ht->compare = compare;
300 ht->destructor = destructor;
301 ht->hash_user_context = hash_user_context;
302 ht->compare_user_context = compare_user_context;
303 ht->destructor_user_context = destructor_user_context;
308 /* Frees the hash table. The destructor function provided in the
309 silc_hash_table_alloc will be called for all keys in the hash table. */
311 void silc_hash_table_free(SilcHashTable ht)
313 SilcHashTableEntry e, tmp;
316 for (i = 0; i < primesize[ht->table_size]; i++) {
320 ht->destructor(e->key, e->context, ht->destructor_user_context);
327 silc_free(ht->table);
331 /* Returns the size of the hash table */
333 uint32 silc_hash_table_size(SilcHashTable ht)
335 return primesize[ht->table_size];
338 /* Returns the number of the entires in the hash table. If there is more
339 entries in the table thatn the size of the hash table calling the
340 silc_hash_table_rehash is recommended. */
342 uint32 silc_hash_table_count(SilcHashTable ht)
344 return ht->entry_count;
347 /* Adds new entry to the hash table. The `key' is hashed using the
348 hash function and the both `key' and `context' will be saved to the
349 hash table. This function quarantees that the entry is always added
350 to the hash table reliably (it is collision resistant). */
352 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
354 silc_hash_table_add_internal(ht, key, context, NULL, NULL);
357 /* Same as above but with specific hash function and user context. */
359 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
360 SilcHashFunction hash, void *hash_user_context)
362 silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
365 /* Same as above but if the `key' already exists in the hash table
366 the old key and the old context will be replace with the `key' and
367 the `context. The destructor function will be called for the
368 replaced key and context. */
370 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
372 silc_hash_table_replace_internal(ht, key, context, NULL, NULL);
375 /* Same as above but with specific hash function. */
377 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
378 SilcHashFunction hash,
379 void *hash_user_context)
381 silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
384 /* Removes the entry from the hash table by the provided `key'. This will
385 call the destructor funtion for the found entry. Return TRUE if the
386 entry was removed successfully and FALSE otherwise. */
388 bool silc_hash_table_del(SilcHashTable ht, void *key)
390 SilcHashTableEntry *entry, prev, e;
392 entry = silc_hash_table_find_internal(ht, key, &prev,
393 ht->hash, ht->hash_user_context,
394 ht->compare, ht->compare_user_context);
400 if (!prev && e->next)
402 if (!prev && e->next == NULL)
407 prev->next = e->next;
410 ht->destructor(e->key, e->context, ht->destructor_user_context);
418 /* Same as above but with specific hash and compare functions. */
420 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
421 SilcHashFunction hash,
422 void *hash_user_context,
423 SilcHashCompare compare,
424 void *compare_user_context)
426 SilcHashTableEntry *entry, prev, e;
428 entry = silc_hash_table_find_internal(ht, key, &prev,
429 hash ? hash : ht->hash,
430 hash_user_context ? hash_user_context :
431 ht->hash_user_context,
432 compare ? compare : ht->compare,
433 compare_user_context ?
434 compare_user_context :
435 ht->compare_user_context);
441 if (!prev && e->next)
443 if (!prev && e->next == NULL)
448 prev->next = e->next;
451 ht->destructor(e->key, e->context, ht->destructor_user_context);
459 /* Same as above but verifies that the context associated with the `key'
460 matches the `context'. This is handy to use with hash tables that may
461 have duplicate keys. In that case the `context' may be used to check
462 whether the correct entry is being deleted. */
464 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
467 SilcHashTableEntry *entry, prev, e;
469 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
471 ht->hash_user_context,
473 ht->compare_user_context);
479 if (!prev && e->next)
481 if (!prev && e->next == NULL)
486 prev->next = e->next;
489 ht->destructor(e->key, e->context, ht->destructor_user_context);
497 /* Same as above but with specific hash and compare functions. */
499 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
501 SilcHashFunction hash,
502 void *hash_user_context,
503 SilcHashCompare compare,
504 void *compare_user_context)
506 SilcHashTableEntry *entry, prev, e;
508 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
509 hash ? hash : ht->hash,
512 ht->hash_user_context,
514 compare : ht->compare,
515 compare_user_context ?
516 compare_user_context :
517 ht->compare_user_context);
523 if (!prev && e->next)
525 if (!prev && e->next == NULL)
530 prev->next = e->next;
533 ht->destructor(e->key, e->context, ht->destructor_user_context);
541 /* Finds the entry in the hash table by the provided `key' as fast as
542 possible. Return TRUE if the entry was found and FALSE otherwise.
543 The found entry is returned to the `ret_key' and `ret_context',
544 respectively. If the `ret_key and `ret_context' are NULL then this
545 maybe used only to check whether given key exists in the table. */
547 bool silc_hash_table_find(SilcHashTable ht, void *key,
548 void **ret_key, void **ret_context)
550 SilcHashTableEntry *entry;
552 entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
553 ht->hash_user_context,
555 ht->compare_user_context);
560 *ret_key = (*entry)->key;
562 *ret_context = (*entry)->context;
567 /* Same as above but with specified hash and comparison functions. */
569 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
570 void **ret_key, void **ret_context,
571 SilcHashFunction hash,
572 void *hash_user_context,
573 SilcHashCompare compare,
574 void *compare_user_context)
576 SilcHashTableEntry *entry;
578 entry = silc_hash_table_find_internal_simple(ht, key,
579 hash ? hash : ht->hash,
582 ht->hash_user_context,
585 compare_user_context ?
586 compare_user_context :
587 ht->compare_user_context);
592 *ret_key = (*entry)->key;
594 *ret_context = (*entry)->context;
599 /* As the hash table is collision resistant it is possible to save duplicate
600 keys to the hash table. This function can be used to find all keys
601 and contexts from the hash table that are found using the `key'. The
602 `foreach' is called for every found key. */
604 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
605 SilcHashForeach foreach, void *user_context)
607 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
608 ht->compare, ht->compare_user_context,
609 foreach, user_context);
612 /* Same as above but with specific hash and comparison functions. */
614 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
615 SilcHashFunction hash,
616 void *hash_user_context,
617 SilcHashCompare compare,
618 void *compare_user_context,
619 SilcHashForeach foreach,
620 void *foreach_user_context)
622 silc_hash_table_find_internal_all(ht, key,
623 hash ? hash : ht->hash,
626 ht->hash_user_context,
629 compare_user_context ?
630 compare_user_context :
631 ht->compare_user_context,
632 foreach, foreach_user_context);
635 /* Traverse all entrys in the hash table and call the `foreach' for
636 every entry with the `user_context' context. */
638 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
641 SilcHashTableEntry e, tmp;
647 for (i = 0; i < primesize[ht->table_size]; i++) {
650 /* Entry may become invalid inside the `foreach' */
652 foreach(e->key, e->context, user_context);
658 /* Rehashs the hash table. The size of the new hash table is provided
659 as `new_size'. If the `new_size' is zero then this routine will make
660 the new table of a suitable size. Note that this operation may be
663 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
666 SilcHashTableEntry *table, e, tmp;
667 uint32 table_size, size_index;
669 /* Take old hash table */
671 table_size = ht->table_size;
673 /* Allocate new table */
674 ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
676 silc_hash_table_primesize(ht->entry_count,
679 ht->table_size = size_index;
682 for (i = 0; i < primesize[table_size]; i++) {
685 silc_hash_table_add(ht, e->key, e->context);
689 /* Remove old entry */
694 /* Remove old table */