X-Git-Url: http://git.silcnet.org/gitweb/?p=silc.git;a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilchashtable.c;h=d7bca802f7cd99575a29cd98797433ce5ddeb5fc;hp=3f93747e163f7d0ef0b18deff591a61256463306;hb=a818c5b5411bbc4436d1c5f011236985c96bb787;hpb=0d805c373cb74658990551a5a2725f0d07b2d6c7 diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c index 3f93747e..d7bca802 100644 --- a/lib/silcutil/silchashtable.c +++ b/lib/silcutil/silchashtable.c @@ -1,33 +1,55 @@ /* - silchashtable.c + silchashtable.c - Author: Pekka Riikonen + Author: Pekka Riikonen - Copyright (C) 2001 Pekka Riikonen + Copyright (C) 2001 - 2002 Pekka Riikonen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - + the Free Software Foundation; version 2 of the License. + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. */ -/* Implementation of collision resistant hash table. */ +/* Implementation of collision resistant hash table. This is a hash table + that provides a reliable (what you add stays there, and duplicate keys + are allowed) with as fast reference to the key as possible. If duplicate + keys are a lot in the hash table the lookup gets slower of course. + However, this is reliable and no data is lost at any point. If you know + that you never have duplicate keys then this is as fast as any simple + hash table. */ /* $Id$ */ #include "silcincludes.h" #include "silchashtable.h" +/* Define to 1 if you want hash table debug enabled */ +#define SILC_HASH_TABLE_DEBUG 0 + +#if SILC_HASH_TABLE_DEBUG == 1 +#define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt) +#else +#define SILC_HT_DEBUG(fmt) +#endif + /* Default size of the hash table (index to prime table) */ #define SILC_HASH_TABLE_SIZE 3 /* Produce the index by hashing the key */ -#define SILC_HASH_TABLE_HASH (ht->hash(key) % primesize[ht->table_size]) +#define SILC_HASH_TABLE_HASH(f, c) \ + ((f)(key, (c)) % primesize[ht->table_size]) + +/* Check whether need to rehash */ +#define SILC_HASH_REHASH_INC \ + (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size]) +#define SILC_HASH_REHASH_DEC \ + (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \ + ht->entry_count > primesize[SILC_HASH_TABLE_SIZE]) /* One entry in the hash table. Includes the key and the associated context. The `next' pointer is non-NULL if two (or more) different @@ -42,16 +64,20 @@ typedef struct SilcHashTableEntryStruct { /* Hash table. */ struct SilcHashTableStruct { SilcHashTableEntry *table; - uint32 table_size; - uint32 entry_count; + SilcUInt32 table_size; + SilcUInt32 entry_count; SilcHashFunction hash; SilcHashCompare compare; SilcHashDestructor destructor; + void *hash_user_context; + void *compare_user_context; + void *destructor_user_context; + bool auto_rehash; }; /* Prime sizes for the hash table. The size of the table will always be one of these. */ -const uint32 primesize[42] = +const SilcUInt32 primesize[42] = { 1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031, 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431, @@ -61,31 +87,40 @@ const uint32 primesize[42] = /* Find appropriate size for the hash table. The size will be a prime. */ -static uint32 silc_hash_table_primesize(uint32 size, uint32 *index) +static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index) { int i; for (i = 0; i < sizeof(primesize); i++) if (primesize[i] >= size) { *index = i; + SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index])); return primesize[i]; } *index = i - 1; + SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index])); return primesize[i - 1]; } -/* Internal routine to find entry in the hash table by `key'. */ +/* Internal routine to find entry in the hash table by `key'. Returns + the previous entry (if exists) as well. */ static inline SilcHashTableEntry * silc_hash_table_find_internal(SilcHashTable ht, void *key, - SilcHashTableEntry *prev_entry) + SilcHashTableEntry *prev_entry, + SilcHashFunction hash, void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context) { SilcHashTableEntry *entry, prev = NULL; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); - entry = &ht->table[SILC_HASH_TABLE_HASH]; - if (ht->compare) { - while (*entry && ht->compare((*entry)->key, key) == FALSE) { + SILC_HT_DEBUG(("index %d key %p", i, key)); + + entry = &ht->table[i]; + if (compare) { + while (*entry && !compare((*entry)->key, key, compare_user_context)) { prev = *entry; entry = &(*entry)->next; } @@ -100,6 +135,197 @@ silc_hash_table_find_internal(SilcHashTable ht, void *key, return entry; } +/* Internal routine to find entry in the hash table by `key' and `context'. + Returns the previous entry (if exists) as well. */ + +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) +{ + SilcHashTableEntry *entry, prev = NULL; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + + SILC_HT_DEBUG(("index %d key %p context %p", i, key, context)); + + entry = &ht->table[i]; + if (ht->compare) { + while (*entry) { + if (compare((*entry)->key, key, compare_user_context) && + (*entry)->context == context) + break; + prev = *entry; + entry = &(*entry)->next; + } + } else { + while (*entry) { + if ((*entry)->key == key && (*entry)->context == context) + break; + prev = *entry; + entry = &(*entry)->next; + } + } + + *prev_entry = prev; + return entry; +} + +/* Internal routine to find entry in the hash table by `key'. */ + +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) +{ + SilcHashTableEntry *entry; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + + SILC_HT_DEBUG(("index %d key %p", i, key)); + + entry = &ht->table[i]; + if (compare) { + while (*entry && !compare((*entry)->key, key, compare_user_context)) + entry = &(*entry)->next; + } else { + while (*entry && (*entry)->key != key) + entry = &(*entry)->next; + } + + return entry; +} + +/* Internal routine to find all keys by `key'. This may return multiple + entries if multiple entries with same key exists. With specific + hash and comparison functions. */ + +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) +{ + SilcHashTableEntry *entry, *tmp; + bool auto_rehash; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + + SILC_HT_DEBUG(("index %d key %p", i, key)); + + /* Disallow auto rehashing while going through the table since we call + the `foreach' function which could alter the table. */ + auto_rehash = ht->auto_rehash; + ht->auto_rehash = FALSE; + + entry = &ht->table[i]; + if (compare) { + while (*entry) { + if (compare((*entry)->key, key, compare_user_context)) { + tmp = &(*entry)->next; + foreach((*entry)->key, (*entry)->context, foreach_user_context); + entry = tmp; + continue; + } + entry = &(*entry)->next; + } + } else { + while (*entry) { + if ((*entry)->key == key) { + tmp = &(*entry)->next; + foreach((*entry)->key, (*entry)->context, foreach_user_context); + entry = tmp; + continue; + } + entry = &(*entry)->next; + } + } + + ht->auto_rehash = auto_rehash; +} + +/* Internal routine to add new key to the hash table */ + +static inline void +silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, + void *hash_user_context) +{ + SilcHashTableEntry *entry; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + + SILC_HT_DEBUG(("index %d key %p", i, key)); + + entry = &ht->table[i]; + if (*entry) { + /* The entry exists already. We have a collision, add it to the + list to avoid collision. */ + SilcHashTableEntry e, tmp; + + e = *entry; + tmp = e->next; + while (tmp) { + e = tmp; + tmp = tmp->next; + } + + SILC_HT_DEBUG(("Collision; adding new key to list")); + + e->next = silc_calloc(1, sizeof(*e->next)); + e->next->key = key; + e->next->context = context; + ht->entry_count++; + } else { + /* New key */ + SILC_HT_DEBUG(("New key")); + *entry = silc_calloc(1, sizeof(**entry)); + (*entry)->key = key; + (*entry)->context = context; + ht->entry_count++; + } + + if (SILC_HASH_REHASH_INC) + silc_hash_table_rehash(ht, 0); +} + +/* Internal routine to replace old key with new one (if it exists) */ + +static inline void +silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, + void *hash_user_context) +{ + SilcHashTableEntry *entry; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + + SILC_HT_DEBUG(("index %d key %p", i, key)); + + entry = &ht->table[i]; + if (*entry) { + /* The entry exists already. We have a collision, replace the old + key and context. */ + if (ht->destructor) + ht->destructor((*entry)->key, (*entry)->context, + ht->destructor_user_context); + } else { + /* New key */ + *entry = silc_calloc(1, sizeof(**entry)); + ht->entry_count++; + } + + (*entry)->key = key; + (*entry)->context = context; + + if (SILC_HASH_REHASH_INC) + silc_hash_table_rehash(ht, 0); +} + /* Allocates new hash table and returns it. If the `table_size' is not zero then the hash table size is the size provided. If zero then the default size will be used. Note that if the `table_size' is provided @@ -108,13 +334,17 @@ silc_hash_table_find_internal(SilcHashTable ht, void *key, destructor function, respectively. The `hash' is mandatory, the others are optional. */ -SilcHashTable silc_hash_table_alloc(uint32 table_size, +SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size, SilcHashFunction hash, + void *hash_user_context, SilcHashCompare compare, - SilcHashDestructor destructor) + void *compare_user_context, + SilcHashDestructor destructor, + void *destructor_user_context, + bool auto_rehash) { SilcHashTable ht; - uint32 size_index = SILC_HASH_TABLE_SIZE; + SilcUInt32 size_index = SILC_HASH_TABLE_SIZE; if (!hash) return NULL; @@ -128,6 +358,10 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, ht->hash = hash; ht->compare = compare; ht->destructor = destructor; + ht->hash_user_context = hash_user_context; + ht->compare_user_context = compare_user_context; + ht->destructor_user_context = destructor_user_context; + ht->auto_rehash = auto_rehash; return ht; } @@ -144,7 +378,7 @@ void silc_hash_table_free(SilcHashTable ht) e = ht->table[i]; while (e) { if (ht->destructor) - ht->destructor(e->key, e->context); + ht->destructor(e->key, e->context, ht->destructor_user_context); tmp = e; e = e->next; silc_free(tmp); @@ -157,7 +391,7 @@ void silc_hash_table_free(SilcHashTable ht) /* Returns the size of the hash table */ -uint32 silc_hash_table_size(SilcHashTable ht) +SilcUInt32 silc_hash_table_size(SilcHashTable ht) { return primesize[ht->table_size]; } @@ -166,7 +400,7 @@ uint32 silc_hash_table_size(SilcHashTable ht) entries in the table thatn the size of the hash table calling the silc_hash_table_rehash is recommended. */ -uint32 silc_hash_table_count(SilcHashTable ht) +SilcUInt32 silc_hash_table_count(SilcHashTable ht) { return ht->entry_count; } @@ -178,33 +412,16 @@ uint32 silc_hash_table_count(SilcHashTable ht) void silc_hash_table_add(SilcHashTable ht, void *key, void *context) { - SilcHashTableEntry *entry; - uint32 index = SILC_HASH_TABLE_HASH; - - entry = &ht->table[index]; - if (*entry) { - /* The entry exists already. We have a collision, add it to the - list to avoid collision. */ - SilcHashTableEntry e, tmp; + silc_hash_table_add_internal(ht, key, context, ht->hash, + ht->hash_user_context); +} - e = *entry; - tmp = e->next; - while (tmp) { - e = tmp; - tmp = tmp->next; - } +/* Same as above but with specific hash function and user context. */ - e->next = silc_calloc(1, sizeof(*e->next)); - e->next->key = key; - e->next->context = context; - ht->entry_count++; - } else { - /* New key */ - *entry = silc_calloc(1, sizeof(**entry)); - (*entry)->key = key; - (*entry)->context = context; - ht->entry_count++; - } +void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, void *hash_user_context) +{ + silc_hash_table_add_internal(ht, key, context, hash, hash_user_context); } /* Same as above but if the `key' already exists in the hash table @@ -214,23 +431,17 @@ void silc_hash_table_add(SilcHashTable ht, void *key, void *context) void silc_hash_table_replace(SilcHashTable ht, void *key, void *context) { - SilcHashTableEntry *entry; - uint32 index = SILC_HASH_TABLE_HASH; + silc_hash_table_replace_internal(ht, key, context, ht->hash, + ht->hash_user_context); +} - entry = &ht->table[index]; - if (*entry) { - /* The entry exists already. We have a collision, replace the old - key and context. */ - if (ht->destructor) - ht->destructor((*entry)->key, (*entry)->context); - } else { - /* New key */ - *entry = silc_calloc(1, sizeof(**entry)); - ht->entry_count++; - } +/* Same as above but with specific hash function. */ - (*entry)->key = key; - (*entry)->context = context; +void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, + void *hash_user_context) +{ + silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context); } /* Removes the entry from the hash table by the provided `key'. This will @@ -241,7 +452,9 @@ bool silc_hash_table_del(SilcHashTable ht, void *key) { SilcHashTableEntry *entry, prev, e; - entry = silc_hash_table_find_internal(ht, key, &prev); + entry = silc_hash_table_find_internal(ht, key, &prev, + ht->hash, ht->hash_user_context, + ht->compare, ht->compare_user_context); if (*entry == NULL) return FALSE; @@ -257,11 +470,158 @@ bool silc_hash_table_del(SilcHashTable ht, void *key) prev->next = e->next; if (ht->destructor) - ht->destructor(e->key, e->context); + ht->destructor(e->key, e->context, ht->destructor_user_context); silc_free(e); ht->entry_count--; + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + + return TRUE; +} + +/* Same as above but with specific hash and compare functions. */ + +bool 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) +{ + SilcHashTableEntry *entry, prev, e; + + entry = silc_hash_table_find_internal(ht, key, &prev, + hash ? hash : ht->hash, + hash_user_context ? hash_user_context : + ht->hash_user_context, + compare ? compare : ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context); + if (*entry == NULL) + return FALSE; + + e = *entry; + + if (!prev && e->next) + *entry = e->next; + if (!prev && e->next == NULL) + *entry = NULL; + if (prev) + prev->next = NULL; + if (prev && e->next) + prev->next = e->next; + + if (destructor) { + destructor(e->key, e->context, destructor_user_context); + } else { + if (ht->destructor) + ht->destructor(e->key, e->context, ht->destructor_user_context); + } + silc_free(e); + + ht->entry_count--; + + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + + return TRUE; +} + +/* Same as above but verifies that the context associated with the `key' + matches the `context'. This is handy to use with hash tables that may + have duplicate keys. In that case the `context' may be used to check + whether the correct entry is being deleted. */ + +bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, + void *context) +{ + SilcHashTableEntry *entry, prev, e; + + entry = silc_hash_table_find_internal_context(ht, key, context, &prev, + ht->hash, + ht->hash_user_context, + ht->compare, + ht->compare_user_context); + if (*entry == NULL) + return FALSE; + + e = *entry; + + if (!prev && e->next) + *entry = e->next; + if (!prev && e->next == NULL) + *entry = NULL; + if (prev) + prev->next = NULL; + if (prev && e->next) + prev->next = e->next; + + if (ht->destructor) + ht->destructor(e->key, e->context, ht->destructor_user_context); + silc_free(e); + + ht->entry_count--; + + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + + return TRUE; +} + +/* Same as above but with specific hash and compare functions. */ + +bool 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) +{ + SilcHashTableEntry *entry, prev, e; + + entry = silc_hash_table_find_internal_context(ht, key, context, &prev, + hash ? hash : ht->hash, + hash_user_context ? + hash_user_context : + ht->hash_user_context, + compare ? + compare : ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context); + if (*entry == NULL) + return FALSE; + + e = *entry; + + if (!prev && e->next) + *entry = e->next; + if (!prev && e->next == NULL) + *entry = NULL; + if (prev) + prev->next = NULL; + if (prev && e->next) + prev->next = e->next; + + if (destructor) { + destructor(e->key, e->context, destructor_user_context); + } else { + if (ht->destructor) + ht->destructor(e->key, e->context, ht->destructor_user_context); + } + silc_free(e); + + ht->entry_count--; + + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + return TRUE; } @@ -274,9 +634,44 @@ bool silc_hash_table_del(SilcHashTable ht, void *key) bool silc_hash_table_find(SilcHashTable ht, void *key, void **ret_key, void **ret_context) { - SilcHashTableEntry *entry, prev; + SilcHashTableEntry *entry; + + entry = silc_hash_table_find_internal_simple(ht, key, ht->hash, + ht->hash_user_context, + ht->compare, + ht->compare_user_context); + if (*entry == NULL) + return FALSE; + + if (ret_key) + *ret_key = (*entry)->key; + if (ret_context) + *ret_context = (*entry)->context; + + return TRUE; +} + +/* Same as above but with specified hash and comparison functions. */ + +bool 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) +{ + SilcHashTableEntry *entry; - entry = silc_hash_table_find_internal(ht, key, &prev); + entry = silc_hash_table_find_internal_simple(ht, key, + hash ? hash : ht->hash, + hash_user_context ? + hash_user_context : + ht->hash_user_context, + compare ? compare : + ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context); if (*entry == NULL) return FALSE; @@ -288,28 +683,100 @@ bool silc_hash_table_find(SilcHashTable ht, void *key, return TRUE; } +/* As the hash table is collision resistant it is possible to save duplicate + keys to the hash table. This function can be used to find all keys + and contexts from the hash table that are found using the `key'. The + `foreach' is called for every found key. */ + +void silc_hash_table_find_foreach(SilcHashTable ht, void *key, + SilcHashForeach foreach, void *user_context) +{ + silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context, + ht->compare, ht->compare_user_context, + foreach, user_context); +} + +/* Same as above but with specific hash and comparison functions. */ + +void 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) +{ + silc_hash_table_find_internal_all(ht, key, + hash ? hash : ht->hash, + hash_user_context ? + hash_user_context : + ht->hash_user_context, + compare ? compare : + ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context, + foreach, foreach_user_context); +} + +/* Traverse all entrys in the hash table and call the `foreach' for + every entry with the `user_context' context. */ + +void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, + void *user_context) +{ + SilcHashTableEntry e, tmp; + int i; + bool auto_rehash; + + if (!foreach) + return; + + auto_rehash = ht->auto_rehash; + ht->auto_rehash = FALSE; + for (i = 0; i < primesize[ht->table_size]; i++) { + e = ht->table[i]; + while (e) { + /* Entry may become invalid inside the `foreach' */ + tmp = e->next; + foreach(e->key, e->context, user_context); + e = tmp; + } + } + ht->auto_rehash = auto_rehash; +} + /* Rehashs the hash table. The size of the new hash table is provided as `new_size'. If the `new_size' is zero then this routine will make the new table of a suitable size. Note that this operation may be very slow. */ -void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size) +void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size) { int i; SilcHashTableEntry *table, e, tmp; - uint32 table_size, size_index; + SilcUInt32 table_size, size_index; + + SILC_HT_DEBUG(("Start")); + + if (new_size) + silc_hash_table_primesize(new_size, &size_index); + else + silc_hash_table_primesize(ht->entry_count, &size_index); + + if (size_index == ht->table_size) + return; + + SILC_HT_DEBUG(("Rehashing")); /* Take old hash table */ table = ht->table; table_size = ht->table_size; /* Allocate new table */ - ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size, - &size_index) : - silc_hash_table_primesize(ht->entry_count, - &size_index), - sizeof(*ht->table)); + ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table)); ht->table_size = size_index; + ht->entry_count = 0; /* Rehash */ for (i = 0; i < primesize[table_size]; i++) { @@ -327,3 +794,104 @@ void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size) /* Remove old table */ silc_free(table); } + +/* Same as above but with specific hash function. */ + +void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size, + SilcHashFunction hash, + void *hash_user_context) +{ + int i; + SilcHashTableEntry *table, e, tmp; + SilcUInt32 table_size, size_index; + + SILC_HT_DEBUG(("Start")); + + if (new_size) + silc_hash_table_primesize(new_size, &size_index); + else + silc_hash_table_primesize(ht->entry_count, &size_index); + + if (size_index == ht->table_size) + return; + + SILC_HT_DEBUG(("Rehashing")); + + /* Take old hash table */ + table = ht->table; + table_size = ht->table_size; + + /* Allocate new table */ + ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table)); + ht->table_size = size_index; + ht->entry_count = 0; + + /* Rehash */ + for (i = 0; i < primesize[table_size]; i++) { + e = table[i]; + while (e) { + silc_hash_table_add_ext(ht, e->key, e->context, hash, + hash_user_context); + tmp = e; + e = e->next; + + /* Remove old entry */ + silc_free(tmp); + } + } + + /* Remove old table */ + silc_free(table); +} + +/* Prepares the `htl' list structure sent as argument to be used in the + hash table traversing with the silc_hash_table_get. Usage: + SilcHashTableList htl; silc_hash_table_list(ht, &htl); */ + +void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl) +{ + htl->ht = ht; + htl->entry = NULL; + htl->index = 0; + htl->auto_rehash = ht->auto_rehash; + + /* Disallow rehashing of the table while traversing the table */ + ht->auto_rehash = FALSE; +} + +/* Resets the `htl' SilcHashTableList. */ + +void silc_hash_table_list_reset(SilcHashTableList *htl) +{ + /* Set back the original auto rehash value to the table */ + htl->ht->auto_rehash = htl->auto_rehash; +} + +/* Returns always the next entry in the hash table into the `key' and + `context' and TRUE. If this returns FALSE then there are no anymore + any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */ + +bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context) +{ + SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry; + + if (!htl->ht->entry_count) + return FALSE; + + while (!entry && htl->index < primesize[htl->ht->table_size]) { + entry = htl->ht->table[htl->index]; + htl->index++; + } + + if (!entry) + return FALSE; + + htl->entry = entry->next; + + if (key) + *key = entry->key; + if (context) + *context = entry->context; + + return TRUE; +}