/*
- silchashtable.c
+ silchashtable.c
- Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
+ Author: Pekka Riikonen <priikone@silcnet.org>
- 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
#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, ht->hash_user_context) % primesize[ht->table_size])
-#define SILC_HASH_TABLE_HASH_F(f, c) \
+#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
keys hashed to same value. The pointer is the pointer to the next
/* 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,
/* 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];
}
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, ht->compare_user_context)
- == 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;
}
static inline SilcHashTableEntry *
silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
void *context,
- 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);
+
+ SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
- entry = &ht->table[SILC_HASH_TABLE_HASH];
+ entry = &ht->table[i];
if (ht->compare) {
- while (*entry && ht->compare((*entry)->key, key, ht->compare_user_context)
- == FALSE && (*entry)->context != context) {
+ while (*entry) {
+ if (compare((*entry)->key, key, compare_user_context) &&
+ (*entry)->context == context)
+ break;
prev = *entry;
entry = &(*entry)->next;
}
} else {
- while (*entry && (*entry)->key != key && (*entry)->context != context) {
+ while (*entry) {
+ if ((*entry)->key == key && (*entry)->context == context)
+ break;
prev = *entry;
entry = &(*entry)->next;
}
void *compare_user_context)
{
SilcHashTableEntry *entry;
+ SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
- if (hash)
- entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
- else
- entry = &ht->table[SILC_HASH_TABLE_HASH];
+ 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 if (ht->compare) {
- while (*entry && !ht->compare((*entry)->key, key,
- ht->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. */
-
-static inline bool
-silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
- SilcHashTableEntry **entries,
- uint32 *count)
-{
- SilcHashTableEntry *entry;
-
- *entries = NULL;
- *count = 0;
-
- entry = &ht->table[SILC_HASH_TABLE_HASH];
- if (ht->compare) {
- while (*entry) {
- if (ht->compare((*entry)->key, key, ht->compare_user_context)) {
- *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1));
- (*entries)[*count] = *entry;
- (*count)++;
- }
- entry = &(*entry)->next;
- }
- } else {
- while (*entry) {
- if ((*entry)->key == key) {
- *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1));
- (*entries)[*count] = *entry;
- (*count)++;
- }
- entry = &(*entry)->next;
- }
- }
-
- return *entries ? TRUE : FALSE;
-}
-
/* 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 bool
-silc_hash_table_find_internal_all_ext(SilcHashTable ht, void *key,
- SilcHashTableEntry **entries,
- uint32 *count,
- SilcHashFunction hash,
- void *hash_user_context,
- SilcHashCompare compare,
- void *compare_user_context)
+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;
+ 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));
- *entries = NULL;
- *count = 0;
+ /* 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[SILC_HASH_TABLE_HASH];
+ entry = &ht->table[i];
if (compare) {
while (*entry) {
if (compare((*entry)->key, key, compare_user_context)) {
- *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1));
- (*entries)[*count] = *entry;
- (*count)++;
+ tmp = &(*entry)->next;
+ foreach((*entry)->key, (*entry)->context, foreach_user_context);
+ entry = tmp;
+ continue;
}
entry = &(*entry)->next;
}
} else {
while (*entry) {
if ((*entry)->key == key) {
- *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1));
- (*entries)[*count] = *entry;
- (*count)++;
+ tmp = &(*entry)->next;
+ foreach((*entry)->key, (*entry)->context, foreach_user_context);
+ entry = tmp;
+ continue;
}
entry = &(*entry)->next;
}
}
- return *entries ? TRUE : FALSE;
+ ht->auto_rehash = auto_rehash;
}
/* Internal routine to add new key to the hash table */
void *hash_user_context)
{
SilcHashTableEntry *entry;
- uint32 index = (hash ? SILC_HASH_TABLE_HASH :
- SILC_HASH_TABLE_HASH_F(hash, hash_user_context));
+ SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
- entry = &ht->table[index];
+ 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. */
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
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,
void *compare_user_context,
SilcHashDestructor destructor,
- void *destructor_user_context)
+ 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;
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;
}
/* 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];
}
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;
}
void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
{
- silc_hash_table_add_internal(ht, key, context, NULL, NULL);
+ silc_hash_table_add_internal(ht, key, context, ht->hash,
+ ht->hash_user_context);
}
/* Same as above but with specific hash function and user 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,
- ht->destructor_user_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
{
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;
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;
}
{
SilcHashTableEntry *entry, prev, e;
- entry = silc_hash_table_find_internal_context(ht, key, context, &prev);
+ 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;
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;
}
{
SilcHashTableEntry *entry;
- entry = silc_hash_table_find_internal_simple(ht, key, NULL, NULL,
- NULL, NULL);
+ 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;
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 return all keys
- and contexts from the hash table that are found using the `key'. */
-
-bool silc_hash_table_find_all(SilcHashTable ht, void *key,
- void ***ret_keys, void ***ret_contexts,
- unsigned int *ret_count)
-{
- SilcHashTableEntry *entries;
- uint32 count;
- int i;
-
- if (!silc_hash_table_find_internal_all(ht, key, &entries, &count))
- return FALSE;
-
- if (ret_keys)
- *ret_keys = silc_calloc(count, sizeof(**ret_keys));
- if (ret_contexts)
- *ret_contexts = silc_calloc(count, sizeof(**ret_contexts));
- if (ret_count)
- *ret_count = count;
-
- if (ret_keys && ret_count) {
- for (i = 0; i < count; i++) {
- (*ret_keys)[i] = entries[i]->key;
- (*ret_contexts)[i] = entries[i]->context;
- }
- } else if (ret_keys && !ret_contexts) {
- for (i = 0; i < count; i++)
- (*ret_keys)[i] = entries[i]->key;
- } else if (!ret_keys && ret_contexts) {
- for (i = 0; i < count; i++)
- (*ret_contexts)[i] = entries[i]->context;
- }
-
- silc_free(entries);
-
- return TRUE;
-}
-
/* Same as above but with specified hash and comparison functions. */
bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
SilcHashTableEntry *entry;
entry = silc_hash_table_find_internal_simple(ht, key,
- hash, hash_user_context,
- compare, compare_user_context);
+ 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;
return TRUE;
}
-/* Same as above but with specified hash and comparison functions. */
+/* 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. */
-bool silc_hash_table_find_all_ext(SilcHashTable ht, void *key,
- void ***ret_keys, void ***ret_contexts,
- unsigned int *ret_count,
- SilcHashFunction hash,
- void *hash_user_context,
- SilcHashCompare compare,
- void *compare_user_context)
+void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
+ SilcHashForeach foreach, void *user_context)
{
- SilcHashTableEntry *entries;
- uint32 count;
- int i;
-
- if (!silc_hash_table_find_internal_all_ext(ht, key, &entries, &count,
- hash, hash_user_context,
- compare, compare_user_context))
- return FALSE;
-
- if (ret_keys)
- *ret_keys = silc_calloc(count, sizeof(**ret_keys));
- if (ret_contexts)
- *ret_contexts = silc_calloc(count, sizeof(**ret_contexts));
- if (ret_count)
- *ret_count = count;
-
- if (ret_keys && ret_count) {
- for (i = 0; i < count; i++) {
- (*ret_keys)[i] = entries[i]->key;
- (*ret_contexts)[i] = entries[i]->context;
- }
- } else if (ret_keys && !ret_contexts) {
- for (i = 0; i < count; i++)
- (*ret_keys)[i] = entries[i]->key;
- } else if (!ret_keys && ret_contexts) {
- for (i = 0; i < count; i++)
- (*ret_contexts)[i] = entries[i]->context;
- }
+ silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
+ ht->compare, ht->compare_user_context,
+ foreach, user_context);
+}
- silc_free(entries);
+/* Same as above but with specific hash and comparison functions. */
- return TRUE;
+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
{
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) {
e = tmp;
}
}
+ ht->auto_rehash = auto_rehash;
}
/* Rehashs the hash table. The size of the new hash table is provided
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++) {
/* 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;
+}
projects / silc.git / blobdiff