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. */
23 #include "silcincludes.h"
24 #include "silchashtable.h"
26 /* Default size of the hash table (index to prime table) */
27 #define SILC_HASH_TABLE_SIZE 3
29 /* Produce the index by hashing the key */
30 #define SILC_HASH_TABLE_HASH (ht->hash(key) % primesize[ht->table_size])
32 /* One entry in the hash table. Includes the key and the associated
33 context. The `next' pointer is non-NULL if two (or more) different
34 keys hashed to same value. The pointer is the pointer to the next
36 typedef struct SilcHashTableEntryStruct {
39 struct SilcHashTableEntryStruct *next;
40 } *SilcHashTableEntry;
43 struct SilcHashTableStruct {
44 SilcHashTableEntry *table;
47 SilcHashFunction hash;
48 SilcHashCompare compare;
49 SilcHashDestructor destructor;
52 /* Prime sizes for the hash table. The size of the table will always
54 const uint32 primesize[42] =
56 1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
57 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
58 65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
59 4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
62 /* Find appropriate size for the hash table. The size will be a prime. */
64 static uint32 silc_hash_table_primesize(uint32 size, uint32 *index)
68 for (i = 0; i < sizeof(primesize); i++)
69 if (primesize[i] >= size) {
75 return primesize[i - 1];
78 /* Internal routine to find entry in the hash table by `key'. */
80 static inline SilcHashTableEntry *
81 silc_hash_table_find_internal(SilcHashTable ht, void *key,
82 SilcHashTableEntry *prev_entry)
84 SilcHashTableEntry *entry, prev = NULL;
86 entry = &ht->table[SILC_HASH_TABLE_HASH];
88 while (*entry && ht->compare((*entry)->key, key) == FALSE) {
90 entry = &(*entry)->next;
93 while (*entry && (*entry)->key != key) {
95 entry = &(*entry)->next;
103 /* Allocates new hash table and returns it. If the `table_size' is not
104 zero then the hash table size is the size provided. If zero then the
105 default size will be used. Note that if the `table_size' is provided
106 it should be a prime. The `hash', `compare' and `destructor' are
107 the hash function, the key comparison function and key and context
108 destructor function, respectively. The `hash' is mandatory, the others
111 SilcHashTable silc_hash_table_alloc(uint32 table_size,
112 SilcHashFunction hash,
113 SilcHashCompare compare,
114 SilcHashDestructor destructor)
117 uint32 size_index = SILC_HASH_TABLE_SIZE;
122 ht = silc_calloc(1, sizeof(*ht));
123 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
125 primesize[SILC_HASH_TABLE_SIZE],
127 ht->table_size = size_index;
129 ht->compare = compare;
130 ht->destructor = destructor;
135 /* Frees the hash table. The destructor function provided in the
136 silc_hash_table_alloc will be called for all keys in the hash table. */
138 void silc_hash_table_free(SilcHashTable ht)
140 SilcHashTableEntry e, tmp;
143 for (i = 0; i < primesize[ht->table_size]; i++) {
147 ht->destructor(e->key, e->context);
154 silc_free(ht->table);
158 /* Returns the size of the hash table */
160 uint32 silc_hash_table_size(SilcHashTable ht)
162 return primesize[ht->table_size];
165 /* Returns the number of the entires in the hash table. If there is more
166 entries in the table thatn the size of the hash table calling the
167 silc_hash_table_rehash is recommended. */
169 uint32 silc_hash_table_count(SilcHashTable ht)
171 return ht->entry_count;
174 /* Adds new entry to the hash table. The `key' is hashed using the
175 hash function and the both `key' and `context' will be saved to the
176 hash table. This function quarantees that the entry is always added
177 to the hash table reliably (it is collision resistant). */
179 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
181 SilcHashTableEntry *entry;
182 uint32 index = SILC_HASH_TABLE_HASH;
184 entry = &ht->table[index];
186 /* The entry exists already. We have a collision, add it to the
187 list to avoid collision. */
188 SilcHashTableEntry e, tmp;
197 e->next = silc_calloc(1, sizeof(*e->next));
199 e->next->context = context;
203 *entry = silc_calloc(1, sizeof(**entry));
205 (*entry)->context = context;
210 /* Same as above but if the `key' already exists in the hash table
211 the old key and the old context will be replace with the `key' and
212 the `context. The destructor function will be called for the
213 replaced key and context. */
215 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
217 SilcHashTableEntry *entry;
218 uint32 index = SILC_HASH_TABLE_HASH;
220 entry = &ht->table[index];
222 /* The entry exists already. We have a collision, replace the old
225 ht->destructor((*entry)->key, (*entry)->context);
228 *entry = silc_calloc(1, sizeof(**entry));
233 (*entry)->context = context;
236 /* Removes the entry from the hash table by the provided `key'. This will
237 call the destructor funtion for the found entry. Return TRUE if the
238 entry was removed successfully and FALSE otherwise. */
240 bool silc_hash_table_del(SilcHashTable ht, void *key)
242 SilcHashTableEntry *entry, prev, e;
244 entry = silc_hash_table_find_internal(ht, key, &prev);
250 if (!prev && e->next)
252 if (!prev && e->next == NULL)
257 prev->next = e->next;
260 ht->destructor(e->key, e->context);
268 /* Finds the entry in the hash table by the provided `key' as fast as
269 possible. Return TRUE if the entry was found and FALSE otherwise.
270 The found entry is returned to the `ret_key' and `ret_context',
271 respectively. If the `ret_key and `ret_context' are NULL then this
272 maybe used only to check whether given key exists in the table. */
274 bool silc_hash_table_find(SilcHashTable ht, void *key,
275 void **ret_key, void **ret_context)
277 SilcHashTableEntry *entry, prev;
279 entry = silc_hash_table_find_internal(ht, key, &prev);
284 *ret_key = (*entry)->key;
286 *ret_context = (*entry)->context;
291 /* Rehashs the hash table. The size of the new hash table is provided
292 as `new_size'. If the `new_size' is zero then this routine will make
293 the new table of a suitable size. Note that this operation may be
296 void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
299 SilcHashTableEntry *table, e, tmp;
300 uint32 table_size, size_index;
302 /* Take old hash table */
304 table_size = ht->table_size;
306 /* Allocate new table */
307 ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size,
309 silc_hash_table_primesize(ht->entry_count,
312 ht->table_size = size_index;
315 for (i = 0; i < primesize[table_size]; i++) {
318 silc_hash_table_add(ht, e->key, e->context);
322 /* Remove old entry */
327 /* Remove old table */