/*
- 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];
}
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", i, key));
- entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
+ entry = &ht->table[i];
if (compare) {
while (*entry && !compare((*entry)->key, key, compare_user_context)) {
prev = *entry;
}
/* Internal routine to find entry in the hash table by `key' and `context'.
- Returns the previous entry (if exists) as well. */
+ Returns the previous entry (if exists) as well to `prev_entry'. */
static inline SilcHashTableEntry *
silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
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_F(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 && !compare((*entry)->key, key, compare_user_context) &&
- (*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;
}
}
- *prev_entry = prev;
+ if (prev_entry)
+ *prev_entry = prev;
return entry;
}
void *compare_user_context)
{
SilcHashTableEntry *entry;
+ SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
- entry = &ht->table[SILC_HASH_TABLE_HASH_F(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;
SilcHashForeach foreach,
void *foreach_user_context)
{
- SilcHashTableEntry *entry;
+ SilcHashTableEntry *entry, *tmp;
+ bool auto_rehash;
+ SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
- entry = &ht->table[SILC_HASH_TABLE_HASH_F(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))
+ 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)
+ 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 */
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) */
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);
+
+ SILC_HT_DEBUG(("index %d key %p", i, key));
- entry = &ht->table[index];
+ entry = &ht->table[i];
if (*entry) {
/* The entry exists already. We have a collision, replace the old
key and context. */
(*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)
{
- silc_hash_table_replace_internal(ht, key, context, NULL, NULL);
+ silc_hash_table_replace_internal(ht, key, context, ht->hash,
+ ht->hash_user_context);
}
/* Same as above but with specific hash function. */
ht->entry_count--;
+ if (SILC_HASH_REHASH_DEC)
+ silc_hash_table_rehash(ht, 0);
+
return TRUE;
}
SilcHashFunction hash,
void *hash_user_context,
SilcHashCompare compare,
- void *compare_user_context)
+ void *compare_user_context,
+ SilcHashDestructor destructor,
+ void *destructor_user_context)
{
SilcHashTableEntry *entry, prev, e;
if (prev && e->next)
prev->next = e->next;
- if (ht->destructor)
- ht->destructor(e->key, e->context, ht->destructor_user_context);
+ 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;
}
ht->entry_count--;
+ if (SILC_HASH_REHASH_DEC)
+ silc_hash_table_rehash(ht, 0);
+
return TRUE;
}
SilcHashFunction hash,
void *hash_user_context,
SilcHashCompare compare,
- void *compare_user_context)
+ void *compare_user_context,
+ SilcHashDestructor destructor,
+ void *destructor_user_context)
{
SilcHashTableEntry *entry, prev, e;
if (prev && e->next)
prev->next = e->next;
- if (ht->destructor)
- ht->destructor(e->key, e->context, ht->destructor_user_context);
+ 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;
}
return TRUE;
}
+/* Same as silc_hash_table_find but finds with specific context. */
+
+bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
+ void *context, void **ret_key)
+{
+ SilcHashTableEntry *entry;
+
+ entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
+ ht->hash,
+ ht->hash_user_context,
+ ht->compare,
+ ht->compare_user_context);
+ if (!entry || !(*entry))
+ return FALSE;
+
+ if (ret_key)
+ *ret_key = (*entry)->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
{
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