1 /*
2
3 silchashtable.c
4
5 Author: Pekka Riikonen <priikone@silcnet.org>
6
7 Copyright (C) 2001 - 2006 Pekka Riikonen
8
9 The contents of this file are subject to one of the Licenses specified
10 in the COPYING file; You may not use this file except in compliance
11 with the License.
12
13 The software distributed under the License is distributed on an "AS IS"
14 basis, in the hope that it will be useful, but WITHOUT WARRANTY OF ANY
15 KIND, either expressed or implied. See the COPYING file for more
16 information.
17
18 */
19 /* Implementation of collision resistant hash table. This is a hash table
20 that provides a reliable (what you add stays there, and duplicate keys
21 are allowed) with as fast reference to the key as possible. If duplicate
22 keys are a lot in the hash table the lookup gets slower of course.
23 However, this is reliable and no data is lost at any point. If you know
24 that you never have duplicate keys then this is as fast as any simple
25 hash table. */
26 /* $Id$ */
27
28 #include "silc.h"
29 #include "silchashtable.h"
30
31 /* Define to 1 if you want hash table debug enabled */
32 #define SILC_HASH_TABLE_DEBUG 0
33
34 #if SILC_HASH_TABLE_DEBUG == 1
35 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
36 #else
37 #define SILC_HT_DEBUG(fmt)
38 #endif
39
40 /* Default size of the hash table (index to prime table) */
41 #define SILC_HASH_TABLE_SIZE 2
42
43 /* Produce the index by hashing the key */
44 #define SILC_HASH_TABLE_HASH(f, c) \
45 ((f)(key, (c)) % primesize[ht->table_size])
46
47 /* Check whether need to rehash */
48 #define SILC_HASH_REHASH_INC \
49 (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
50 #define SILC_HASH_REHASH_DEC \
51 (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
52 ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
53
54 /* One entry in the hash table. Includes the key and the associated
55 context. The `next' pointer is non-NULL if two (or more) different
56 keys hashed to same value. The pointer is the pointer to the next
57 entry. */
58 typedef struct SilcHashTableEntryStruct {
59 void *key;
60 void *context;
61 struct SilcHashTableEntryStruct *next;
62 } *SilcHashTableEntry;
63
64 /* Hash table. */
65 struct SilcHashTableStruct {
66 SilcHashTableEntry *table;
67 SilcUInt32 table_size;
68 SilcUInt32 entry_count;
69 SilcHashFunction hash;
70 SilcHashCompare compare;
71 SilcHashDestructor destructor;
72 void *hash_user_context;
73 void *compare_user_context;
74 void *destructor_user_context;
75 unsigned int auto_rehash : 1;
76 };
77
78 /* Prime sizes for the hash table. The size of the table will always
79 be one of these. */
80 const SilcUInt32 primesize[] =
81 {
82 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
83 1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
84 14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
85 131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
86 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
87 };
88
89 /* Find appropriate size for the hash table. The size will be a prime. */
90
silc_hash_table_primesize(SilcUInt32 size,SilcUInt32 * index)91 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
92 {
93 int i;
94
95 for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); i++)
96 if (primesize[i] >= size) {
97 *index = i;
98 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
99 return primesize[i];
100 }
101
102 *index = i - 1;
103 SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
104 return primesize[i - 1];
105 }
106
107 /* Internal routine to find entry in the hash table by `key'. Returns
108 the previous entry (if exists) as well. */
109
110 static inline SilcHashTableEntry *
silc_hash_table_find_internal(SilcHashTable ht,void * key,SilcHashTableEntry * prev_entry,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context)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)
116 {
117 SilcHashTableEntry *entry, prev = NULL;
118 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
119
120 SILC_HT_DEBUG(("index %d key %p", i, key));
121
122 entry = &ht->table[i];
123 if (compare) {
124 while (*entry && !compare((*entry)->key, key, compare_user_context)) {
125 prev = *entry;
126 entry = &(*entry)->next;
127 }
128 } else {
129 while (*entry && (*entry)->key != key) {
130 prev = *entry;
131 entry = &(*entry)->next;
132 }
133 }
134
135 *prev_entry = prev;
136 return entry;
137 }
138
139 /* Internal routine to find entry in the hash table by `key' and `context'.
140 Returns the previous entry (if exists) as well to `prev_entry'. */
141
142 static inline SilcHashTableEntry *
silc_hash_table_find_internal_context(SilcHashTable ht,void * key,void * context,SilcHashTableEntry * prev_entry,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context)143 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
144 void *context,
145 SilcHashTableEntry *prev_entry,
146 SilcHashFunction hash,
147 void *hash_user_context,
148 SilcHashCompare compare,
149 void *compare_user_context)
150 {
151 SilcHashTableEntry *entry, prev = NULL;
152 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
153
154 SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
155
156 entry = &ht->table[i];
157 if (ht->compare) {
158 while (*entry) {
159 if (compare((*entry)->key, key, compare_user_context) &&
160 (*entry)->context == context)
161 break;
162 prev = *entry;
163 entry = &(*entry)->next;
164 }
165 } else {
166 while (*entry) {
167 if ((*entry)->key == key && (*entry)->context == context)
168 break;
169 prev = *entry;
170 entry = &(*entry)->next;
171 }
172 }
173
174 if (prev_entry)
175 *prev_entry = prev;
176 return entry;
177 }
178
179 /* Internal routine to find entry in the hash table by `key'. */
180
181 static inline SilcHashTableEntry *
silc_hash_table_find_internal_simple(SilcHashTable ht,void * key,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context)182 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
183 SilcHashFunction hash,
184 void *hash_user_context,
185 SilcHashCompare compare,
186 void *compare_user_context)
187 {
188 SilcHashTableEntry *entry;
189 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
190
191 SILC_HT_DEBUG(("index %d key %p", i, key));
192
193 entry = &ht->table[i];
194 if (compare) {
195 while (*entry && !compare((*entry)->key, key, compare_user_context))
196 entry = &(*entry)->next;
197 } else {
198 while (*entry && (*entry)->key != key)
199 entry = &(*entry)->next;
200 }
201
202 return entry;
203 }
204
205 /* Internal routine to find all keys by `key'. This may return multiple
206 entries if multiple entries with same key exists. With specific
207 hash and comparison functions. */
208
209 static inline void
silc_hash_table_find_internal_all(SilcHashTable ht,void * key,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context,SilcHashForeach foreach,void * foreach_user_context)210 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
211 SilcHashFunction hash,
212 void *hash_user_context,
213 SilcHashCompare compare,
214 void *compare_user_context,
215 SilcHashForeach foreach,
216 void *foreach_user_context)
217 {
218 SilcHashTableEntry e, tmp;
219 SilcBool auto_rehash, found = FALSE;
220 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
221
222 SILC_HT_DEBUG(("index %d key %p", i, key));
223
224 /* Disallow auto rehashing while going through the table since we call
225 the `foreach' function which could alter the table. */
226 auto_rehash = ht->auto_rehash;
227 ht->auto_rehash = FALSE;
228
229 e = ht->table[i];
230 if (compare) {
231 while (e) {
232 tmp = e->next;
233 if (compare(e->key, key, compare_user_context)) {
234 found = TRUE;
235 foreach(e->key, e->context, foreach_user_context);
236 }
237 e = tmp;
238 }
239 } else {
240 while (e) {
241 tmp = e->next;
242 if (e->key == key) {
243 found = TRUE;
244 foreach(e->key, e->context, foreach_user_context);
245 }
246 e = tmp;
247 }
248 }
249
250 /* If nothing was found call with NULL context the callback */
251 if (!found)
252 foreach(key, NULL, foreach_user_context);
253
254 ht->auto_rehash = auto_rehash;
255 }
256
257 /* Internal routine to add new key to the hash table */
258
259 static inline SilcBool
silc_hash_table_add_internal(SilcHashTable ht,void * key,void * context,SilcHashFunction hash,void * hash_user_context)260 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
261 SilcHashFunction hash,
262 void *hash_user_context)
263 {
264 SilcHashTableEntry *entry;
265 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
266
267 SILC_HT_DEBUG(("index %d key %p", i, key));
268
269 entry = &ht->table[i];
270 if (*entry) {
271 /* The entry exists already. We have a collision, add it to the
272 list to avoid collision. */
273 SilcHashTableEntry e, tmp;
274
275 e = *entry;
276 tmp = e->next;
277 while (tmp) {
278 e = tmp;
279 tmp = tmp->next;
280 }
281
282 SILC_HT_DEBUG(("Collision; adding new key to list"));
283
284 e->next = silc_calloc(1, sizeof(*e->next));
285 if (!e->next)
286 return FALSE;
287 e->next->key = key;
288 e->next->context = context;
289 ht->entry_count++;
290 } else {
291 /* New key */
292 SILC_HT_DEBUG(("New key"));
293 *entry = silc_calloc(1, sizeof(**entry));
294 if (!(*entry))
295 return FALSE;
296 (*entry)->key = key;
297 (*entry)->context = context;
298 ht->entry_count++;
299 }
300
301 if (SILC_HASH_REHASH_INC)
302 silc_hash_table_rehash(ht, 0);
303
304 return TRUE;
305 }
306
307 /* Internal routine to replace old key with new one (if it exists) */
308
309 static inline SilcBool
silc_hash_table_replace_internal(SilcHashTable ht,void * key,void * context,SilcHashFunction hash,void * hash_user_context)310 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
311 SilcHashFunction hash,
312 void *hash_user_context)
313 {
314 SilcHashTableEntry *entry;
315 SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
316
317 SILC_HT_DEBUG(("index %d key %p", i, key));
318
319 entry = &ht->table[i];
320 if (*entry) {
321 /* The entry exists already. We have a collision, replace the old
322 key and context. */
323 if (ht->destructor)
324 ht->destructor((*entry)->key, (*entry)->context,
325 ht->destructor_user_context);
326 } else {
327 /* New key */
328 *entry = silc_calloc(1, sizeof(**entry));
329 if (!(*entry))
330 return FALSE;
331 ht->entry_count++;
332 }
333
334 (*entry)->key = key;
335 (*entry)->context = context;
336
337 if (SILC_HASH_REHASH_INC)
338 silc_hash_table_rehash(ht, 0);
339
340 return TRUE;
341 }
342
343 /* Allocates new hash table and returns it. If the `table_size' is not
344 zero then the hash table size is the size provided. If zero then the
345 default size will be used. Note that if the `table_size' is provided
346 it should be a prime. The `hash', `compare' and `destructor' are
347 the hash function, the key comparison function and key and context
348 destructor function, respectively. The `hash' is mandatory, the others
349 are optional. */
350
silc_hash_table_alloc(SilcUInt32 table_size,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context,SilcHashDestructor destructor,void * destructor_user_context,SilcBool auto_rehash)351 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
352 SilcHashFunction hash,
353 void *hash_user_context,
354 SilcHashCompare compare,
355 void *compare_user_context,
356 SilcHashDestructor destructor,
357 void *destructor_user_context,
358 SilcBool auto_rehash)
359 {
360 SilcHashTable ht;
361 SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
362
363 if (!hash)
364 return NULL;
365
366 ht = silc_calloc(1, sizeof(*ht));
367 if (!ht)
368 return NULL;
369 ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
370 &size_index) :
371 primesize[SILC_HASH_TABLE_SIZE],
372 sizeof(*ht->table));
373 if (!ht->table) {
374 silc_free(ht);
375 return NULL;
376 }
377 ht->table_size = size_index;
378 ht->hash = hash;
379 ht->compare = compare;
380 ht->destructor = destructor;
381 ht->hash_user_context = hash_user_context;
382 ht->compare_user_context = compare_user_context;
383 ht->destructor_user_context = destructor_user_context;
384 ht->auto_rehash = auto_rehash;
385
386 return ht;
387 }
388
389 /* Frees the hash table. The destructor function provided in the
390 silc_hash_table_alloc will be called for all keys in the hash table. */
391
silc_hash_table_free(SilcHashTable ht)392 void silc_hash_table_free(SilcHashTable ht)
393 {
394 SilcHashTableEntry e, tmp;
395 int i;
396
397 for (i = 0; i < primesize[ht->table_size]; i++) {
398 e = ht->table[i];
399 while (e) {
400 if (ht->destructor)
401 ht->destructor(e->key, e->context, ht->destructor_user_context);
402 tmp = e;
403 e = e->next;
404 silc_free(tmp);
405 }
406 }
407
408 silc_free(ht->table);
409 silc_free(ht);
410 }
411
412 /* Returns the size of the hash table */
413
silc_hash_table_size(SilcHashTable ht)414 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
415 {
416 return primesize[ht->table_size];
417 }
418
419 /* Returns the number of the entires in the hash table. If there is more
420 entries in the table thatn the size of the hash table calling the
421 silc_hash_table_rehash is recommended. */
422
silc_hash_table_count(SilcHashTable ht)423 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
424 {
425 return ht->entry_count;
426 }
427
428 /* Adds new entry to the hash table. The `key' is hashed using the
429 hash function and the both `key' and `context' will be saved to the
430 hash table. This function quarantees that the entry is always added
431 to the hash table reliably (it is collision resistant). */
432
silc_hash_table_add(SilcHashTable ht,void * key,void * context)433 SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context)
434 {
435 return silc_hash_table_add_internal(ht, key, context, ht->hash,
436 ht->hash_user_context);
437 }
438
439 /* Same as above but with specific hash function and user context. */
440
silc_hash_table_add_ext(SilcHashTable ht,void * key,void * context,SilcHashFunction hash,void * hash_user_context)441 SilcBool silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
442 SilcHashFunction hash,
443 void *hash_user_context)
444 {
445 return silc_hash_table_add_internal(ht, key, context,
446 hash, hash_user_context);
447 }
448
449 /* Same as above but if the `key' already exists in the hash table
450 the old key and the old context will be replace with the `key' and
451 the `context. The destructor function will be called for the
452 replaced key and context. */
453
silc_hash_table_replace(SilcHashTable ht,void * key,void * context)454 SilcBool silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
455 {
456 return silc_hash_table_replace_internal(ht, key, context, ht->hash,
457 ht->hash_user_context);
458 }
459
460 /* Same as above but with specific hash function. */
461
silc_hash_table_replace_ext(SilcHashTable ht,void * key,void * context,SilcHashFunction hash,void * hash_user_context)462 SilcBool silc_hash_table_replace_ext(SilcHashTable ht, void *key,
463 void *context,
464 SilcHashFunction hash,
465 void *hash_user_context)
466 {
467 return silc_hash_table_replace_internal(ht, key, context,
468 hash, hash_user_context);
469 }
470
471 /* Removes the entry from the hash table by the provided `key'. This will
472 call the destructor funtion for the found entry. Return TRUE if the
473 entry was removed successfully and FALSE otherwise. */
474
silc_hash_table_del(SilcHashTable ht,void * key)475 SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
476 {
477 SilcHashTableEntry *entry, prev, e;
478
479 entry = silc_hash_table_find_internal(ht, key, &prev,
480 ht->hash, ht->hash_user_context,
481 ht->compare, ht->compare_user_context);
482 if (*entry == NULL)
483 return FALSE;
484
485 e = *entry;
486
487 if (!prev && e->next)
488 *entry = e->next;
489 if (!prev && e->next == NULL)
490 *entry = NULL;
491 if (prev)
492 prev->next = NULL;
493 if (prev && e->next)
494 prev->next = e->next;
495
496 if (ht->destructor)
497 ht->destructor(e->key, e->context, ht->destructor_user_context);
498 silc_free(e);
499
500 ht->entry_count--;
501
502 if (SILC_HASH_REHASH_DEC)
503 silc_hash_table_rehash(ht, 0);
504
505 return TRUE;
506 }
507
508 /* Same as above but with specific hash and compare functions. */
509
silc_hash_table_del_ext(SilcHashTable ht,void * key,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context,SilcHashDestructor destructor,void * destructor_user_context)510 SilcBool silc_hash_table_del_ext(SilcHashTable ht, void *key,
511 SilcHashFunction hash,
512 void *hash_user_context,
513 SilcHashCompare compare,
514 void *compare_user_context,
515 SilcHashDestructor destructor,
516 void *destructor_user_context)
517 {
518 SilcHashTableEntry *entry, prev, e;
519
520 entry = silc_hash_table_find_internal(ht, key, &prev,
521 hash ? hash : ht->hash,
522 hash_user_context ? hash_user_context :
523 ht->hash_user_context,
524 compare ? compare : ht->compare,
525 compare_user_context ?
526 compare_user_context :
527 ht->compare_user_context);
528 if (*entry == NULL)
529 return FALSE;
530
531 e = *entry;
532
533 if (!prev && e->next)
534 *entry = e->next;
535 if (!prev && e->next == NULL)
536 *entry = NULL;
537 if (prev)
538 prev->next = NULL;
539 if (prev && e->next)
540 prev->next = e->next;
541
542 if (destructor) {
543 destructor(e->key, e->context, destructor_user_context);
544 } else {
545 if (ht->destructor)
546 ht->destructor(e->key, e->context, ht->destructor_user_context);
547 }
548 silc_free(e);
549
550 ht->entry_count--;
551
552 if (SILC_HASH_REHASH_DEC)
553 silc_hash_table_rehash(ht, 0);
554
555 return TRUE;
556 }
557
558 /* Same as above but verifies that the context associated with the `key'
559 matches the `context'. This is handy to use with hash tables that may
560 have duplicate keys. In that case the `context' may be used to check
561 whether the correct entry is being deleted. */
562
silc_hash_table_del_by_context(SilcHashTable ht,void * key,void * context)563 SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
564 void *context)
565 {
566 SilcHashTableEntry *entry, prev, e;
567
568 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
569 ht->hash,
570 ht->hash_user_context,
571 ht->compare,
572 ht->compare_user_context);
573 if (*entry == NULL)
574 return FALSE;
575
576 e = *entry;
577
578 if (!prev && e->next)
579 *entry = e->next;
580 if (!prev && e->next == NULL)
581 *entry = NULL;
582 if (prev)
583 prev->next = NULL;
584 if (prev && e->next)
585 prev->next = e->next;
586
587 if (ht->destructor)
588 ht->destructor(e->key, e->context, ht->destructor_user_context);
589 silc_free(e);
590
591 ht->entry_count--;
592
593 if (SILC_HASH_REHASH_DEC)
594 silc_hash_table_rehash(ht, 0);
595
596 return TRUE;
597 }
598
599 /* Same as above but with specific hash and compare functions. */
600
silc_hash_table_del_by_context_ext(SilcHashTable ht,void * key,void * context,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context,SilcHashDestructor destructor,void * destructor_user_context)601 SilcBool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
602 void *context,
603 SilcHashFunction hash,
604 void *hash_user_context,
605 SilcHashCompare compare,
606 void *compare_user_context,
607 SilcHashDestructor destructor,
608 void *destructor_user_context)
609 {
610 SilcHashTableEntry *entry, prev, e;
611
612 entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
613 hash ? hash : ht->hash,
614 hash_user_context ?
615 hash_user_context :
616 ht->hash_user_context,
617 compare ?
618 compare : ht->compare,
619 compare_user_context ?
620 compare_user_context :
621 ht->compare_user_context);
622 if (*entry == NULL)
623 return FALSE;
624
625 e = *entry;
626
627 if (!prev && e->next)
628 *entry = e->next;
629 if (!prev && e->next == NULL)
630 *entry = NULL;
631 if (prev)
632 prev->next = NULL;
633 if (prev && e->next)
634 prev->next = e->next;
635
636 if (destructor) {
637 destructor(e->key, e->context, destructor_user_context);
638 } else {
639 if (ht->destructor)
640 ht->destructor(e->key, e->context, ht->destructor_user_context);
641 }
642 silc_free(e);
643
644 ht->entry_count--;
645
646 if (SILC_HASH_REHASH_DEC)
647 silc_hash_table_rehash(ht, 0);
648
649 return TRUE;
650 }
651
652 /* Finds the entry in the hash table by the provided `key' as fast as
653 possible. Return TRUE if the entry was found and FALSE otherwise.
654 The found entry is returned to the `ret_key' and `ret_context',
655 respectively. If the `ret_key and `ret_context' are NULL then this
656 maybe used only to check whether given key exists in the table. */
657
silc_hash_table_find(SilcHashTable ht,void * key,void ** ret_key,void ** ret_context)658 SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
659 void **ret_key, void **ret_context)
660 {
661 return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
662 NULL, NULL, NULL, NULL);
663 }
664
665 /* Same as above but with specified hash and comparison functions. */
666
silc_hash_table_find_ext(SilcHashTable ht,void * key,void ** ret_key,void ** ret_context,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context)667 SilcBool silc_hash_table_find_ext(SilcHashTable ht, void *key,
668 void **ret_key, void **ret_context,
669 SilcHashFunction hash,
670 void *hash_user_context,
671 SilcHashCompare compare,
672 void *compare_user_context)
673 {
674 SilcHashTableEntry *entry;
675
676 entry = silc_hash_table_find_internal_simple(ht, key,
677 hash ? hash : ht->hash,
678 hash_user_context ?
679 hash_user_context :
680 ht->hash_user_context,
681 compare ? compare :
682 ht->compare,
683 compare_user_context ?
684 compare_user_context :
685 ht->compare_user_context);
686 if (*entry == NULL)
687 return FALSE;
688
689 if (ret_key)
690 *ret_key = (*entry)->key;
691 if (ret_context)
692 *ret_context = (*entry)->context;
693
694 return TRUE;
695 }
696
697 /* Same as silc_hash_table_find but finds with specific context. */
698
silc_hash_table_find_by_context(SilcHashTable ht,void * key,void * context,void ** ret_key)699 SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
700 void *context, void **ret_key)
701 {
702 return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
703 NULL, NULL, NULL, NULL);
704 }
705
706 /* Same as above but with specified hash and comparison functions. */
707
silc_hash_table_find_by_context_ext(SilcHashTable ht,void * key,void * context,void ** ret_key,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context)708 SilcBool silc_hash_table_find_by_context_ext(SilcHashTable ht, void *key,
709 void *context, void **ret_key,
710 SilcHashFunction hash,
711 void *hash_user_context,
712 SilcHashCompare compare,
713 void *compare_user_context)
714 {
715 SilcHashTableEntry *entry;
716
717 entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
718 hash ? hash : ht->hash,
719 hash_user_context ?
720 hash_user_context :
721 ht->hash_user_context,
722 compare ? compare :
723 ht->compare,
724 compare_user_context ?
725 compare_user_context :
726 ht->compare_user_context);
727 if (!entry || !(*entry))
728 return FALSE;
729
730 if (ret_key)
731 *ret_key = (*entry)->key;
732
733 return TRUE;
734 }
735
736 /* As the hash table is collision resistant it is possible to save duplicate
737 keys to the hash table. This function can be used to find all keys
738 and contexts from the hash table that are found using the `key'. The
739 `foreach' is called for every found key. */
740
silc_hash_table_find_foreach(SilcHashTable ht,void * key,SilcHashForeach foreach,void * user_context)741 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
742 SilcHashForeach foreach, void *user_context)
743 {
744 silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
745 ht->compare, ht->compare_user_context,
746 foreach, user_context);
747 }
748
749 /* Same as above but with specific hash and comparison functions. */
750
silc_hash_table_find_foreach_ext(SilcHashTable ht,void * key,SilcHashFunction hash,void * hash_user_context,SilcHashCompare compare,void * compare_user_context,SilcHashForeach foreach,void * foreach_user_context)751 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
752 SilcHashFunction hash,
753 void *hash_user_context,
754 SilcHashCompare compare,
755 void *compare_user_context,
756 SilcHashForeach foreach,
757 void *foreach_user_context)
758 {
759 silc_hash_table_find_internal_all(ht, key,
760 hash ? hash : ht->hash,
761 hash_user_context ?
762 hash_user_context :
763 ht->hash_user_context,
764 compare ? compare :
765 ht->compare,
766 compare_user_context ?
767 compare_user_context :
768 ht->compare_user_context,
769 foreach, foreach_user_context);
770 }
771
772 /* Traverse all entrys in the hash table and call the `foreach' for
773 every entry with the `user_context' context. */
774
silc_hash_table_foreach(SilcHashTable ht,SilcHashForeach foreach,void * user_context)775 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
776 void *user_context)
777 {
778 SilcHashTableEntry e, tmp;
779 int i;
780 SilcBool auto_rehash;
781
782 if (!foreach)
783 return;
784
785 auto_rehash = ht->auto_rehash;
786 ht->auto_rehash = FALSE;
787 for (i = 0; i < primesize[ht->table_size]; i++) {
788 e = ht->table[i];
789 while (e) {
790 /* Entry may become invalid inside the `foreach' */
791 tmp = e->next;
792 foreach(e->key, e->context, user_context);
793 e = tmp;
794 }
795 }
796 ht->auto_rehash = auto_rehash;
797 }
798
799 /* Rehashs the hash table. The size of the new hash table is provided
800 as `new_size'. If the `new_size' is zero then this routine will make
801 the new table of a suitable size. Note that this operation may be
802 very slow. */
803
silc_hash_table_rehash(SilcHashTable ht,SilcUInt32 new_size)804 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
805 {
806 int i;
807 SilcHashTableEntry *table, e, tmp;
808 SilcUInt32 table_size, size_index;
809 SilcBool auto_rehash;
810
811 SILC_HT_DEBUG(("Start"));
812
813 if (new_size)
814 silc_hash_table_primesize(new_size, &size_index);
815 else
816 silc_hash_table_primesize(ht->entry_count, &size_index);
817
818 if (size_index == ht->table_size)
819 return;
820
821 SILC_HT_DEBUG(("Rehashing"));
822
823 /* Take old hash table */
824 table = ht->table;
825 table_size = ht->table_size;
826 auto_rehash = ht->auto_rehash;
827 ht->auto_rehash = FALSE;
828
829 /* Allocate new table */
830 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
831 if (!ht->table)
832 return;
833 ht->table_size = size_index;
834 ht->entry_count = 0;
835
836 /* Rehash */
837 for (i = 0; i < primesize[table_size]; i++) {
838 e = table[i];
839 while (e) {
840 silc_hash_table_add(ht, e->key, e->context);
841 tmp = e;
842 e = e->next;
843
844 /* Remove old entry */
845 silc_free(tmp);
846 }
847 }
848
849 ht->auto_rehash = auto_rehash;
850
851 /* Remove old table */
852 silc_free(table);
853 }
854
855 /* Same as above but with specific hash function. */
856
silc_hash_table_rehash_ext(SilcHashTable ht,SilcUInt32 new_size,SilcHashFunction hash,void * hash_user_context)857 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
858 SilcHashFunction hash,
859 void *hash_user_context)
860 {
861 int i;
862 SilcHashTableEntry *table, e, tmp;
863 SilcUInt32 table_size, size_index;
864 SilcBool auto_rehash;
865
866 SILC_HT_DEBUG(("Start"));
867
868 if (new_size)
869 silc_hash_table_primesize(new_size, &size_index);
870 else
871 silc_hash_table_primesize(ht->entry_count, &size_index);
872
873 if (size_index == ht->table_size)
874 return;
875
876 SILC_HT_DEBUG(("Rehashing"));
877
878 /* Take old hash table */
879 table = ht->table;
880 table_size = ht->table_size;
881 auto_rehash = ht->auto_rehash;
882 ht->auto_rehash = FALSE;
883
884 /* Allocate new table */
885 ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
886 if (!ht->table)
887 return;
888 ht->table_size = size_index;
889 ht->entry_count = 0;
890
891 /* Rehash */
892 for (i = 0; i < primesize[table_size]; i++) {
893 e = table[i];
894 while (e) {
895 silc_hash_table_add_ext(ht, e->key, e->context, hash,
896 hash_user_context);
897 tmp = e;
898 e = e->next;
899
900 /* Remove old entry */
901 silc_free(tmp);
902 }
903 }
904
905 ht->auto_rehash = auto_rehash;
906
907 /* Remove old table */
908 silc_free(table);
909 }
910
911 /* Prepares the `htl' list structure sent as argument to be used in the
912 hash table traversing with the silc_hash_table_get. Usage:
913 SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
914
silc_hash_table_list(SilcHashTable ht,SilcHashTableList * htl)915 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
916 {
917 htl->ht = ht;
918 htl->entry = NULL;
919 htl->index = 0;
920 htl->auto_rehash = ht->auto_rehash;
921
922 /* Disallow rehashing of the table while traversing the table */
923 ht->auto_rehash = FALSE;
924 }
925
926 /* Resets the `htl' SilcHashTableList. */
927
silc_hash_table_list_reset(SilcHashTableList * htl)928 void silc_hash_table_list_reset(SilcHashTableList *htl)
929 {
930 /* Set back the original auto rehash value to the table */
931 htl->ht->auto_rehash = htl->auto_rehash;
932 }
933
934 /* Returns always the next entry in the hash table into the `key' and
935 `context' and TRUE. If this returns FALSE then there are no anymore
936 any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
937
silc_hash_table_get(SilcHashTableList * htl,void ** key,void ** context)938 SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
939 void **context)
940 {
941 SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
942
943 if (!htl->ht->entry_count)
944 return FALSE;
945
946 while (!entry && htl->index < primesize[htl->ht->table_size]) {
947 entry = htl->ht->table[htl->index];
948 htl->index++;
949 }
950
951 if (!entry)
952 return FALSE;
953
954 htl->entry = entry->next;
955
956 if (key)
957 *key = entry->key;
958 if (context)
959 *context = entry->context;
960
961 return TRUE;
962 }
963