Author: Pekka Riikonen <priikone@silcnet.org>
- Copyright (C) 2001 - 2003 Pekka Riikonen
+ Copyright (C) 2001 - 2007 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
hash table. */
/* $Id$ */
-#include "silcincludes.h"
+#include "silc.h"
#include "silchashtable.h"
/* Define to 1 if you want hash table debug enabled */
#endif
/* Default size of the hash table (index to prime table) */
-#define SILC_HASH_TABLE_SIZE 3
+#define SILC_HASH_TABLE_SIZE 2
/* Produce the index by hashing the key */
#define SILC_HASH_TABLE_HASH(f, c) \
/* Hash table. */
struct SilcHashTableStruct {
+ SilcStack stack;
SilcHashTableEntry *table;
SilcUInt32 table_size;
SilcUInt32 entry_count;
/* Prime sizes for the hash table. The size of the table will always
be one of these. */
-const SilcUInt32 primesize[42] =
+const SilcUInt32 primesize[] =
{
- 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,
- 65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
- 4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
+ 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
+ 1237, 1447, 2053, 2389, 2777, 3323, 4099, 5059, 6247, 7001, 8209, 10993,
+ 14057, 16411, 19181, 21089, 25033, 32771, 40009, 47431, 65537, 106721,
+ 131101, 262147, 360163, 524309, 810343, 1048583, 2097169, 4194319,
+ 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
};
/* Find appropriate size for the hash table. The size will be a prime. */
void *foreach_user_context)
{
SilcHashTableEntry e, tmp;
- bool auto_rehash, found = FALSE;
+ SilcBool auto_rehash, found = FALSE;
SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
SILC_HT_DEBUG(("index %d key %p", i, key));
/* Internal routine to add new key to the hash table */
-static inline bool
+static inline SilcBool
silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
SilcHashFunction hash,
void *hash_user_context)
SILC_HT_DEBUG(("Collision; adding new key to list"));
- e->next = silc_calloc(1, sizeof(*e->next));
+ e->next = silc_scalloc(ht->stack, 1, sizeof(*e->next));
if (!e->next)
return FALSE;
e->next->key = key;
} else {
/* New key */
SILC_HT_DEBUG(("New key"));
- *entry = silc_calloc(1, sizeof(**entry));
+ *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
if (!(*entry))
return FALSE;
(*entry)->key = key;
/* Internal routine to replace old key with new one (if it exists) */
-static inline bool
+static inline SilcBool
silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
SilcHashFunction hash,
void *hash_user_context)
ht->destructor_user_context);
} else {
/* New key */
- *entry = silc_calloc(1, sizeof(**entry));
+ *entry = silc_scalloc(ht->stack, 1, sizeof(**entry));
if (!(*entry))
return FALSE;
ht->entry_count++;
destructor function, respectively. The `hash' is mandatory, the others
are optional. */
-SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
+SilcHashTable silc_hash_table_alloc(SilcStack stack,
+ SilcUInt32 table_size,
SilcHashFunction hash,
void *hash_user_context,
SilcHashCompare compare,
void *compare_user_context,
SilcHashDestructor destructor,
void *destructor_user_context,
- bool auto_rehash)
+ SilcBool auto_rehash)
{
SilcHashTable ht;
SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
- if (!hash)
+ if (!hash) {
+ silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
return NULL;
+ }
+
+ if (stack)
+ stack = silc_stack_alloc(0, stack);
- ht = silc_calloc(1, sizeof(*ht));
- if (!ht)
+ ht = silc_scalloc(stack, 1, sizeof(*ht));
+ if (!ht) {
+ silc_stack_free(stack);
return NULL;
- ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
- &size_index) :
- primesize[SILC_HASH_TABLE_SIZE],
- sizeof(*ht->table));
+ }
+ ht->table = silc_scalloc(stack,
+ table_size ? silc_hash_table_primesize(table_size,
+ &size_index) :
+ primesize[SILC_HASH_TABLE_SIZE],
+ sizeof(*ht->table));
if (!ht->table) {
- silc_free(ht);
+ silc_stack_free(stack);
+ silc_sfree(stack, ht);
return NULL;
}
+ ht->stack = stack;
ht->table_size = size_index;
ht->hash = hash;
ht->compare = compare;
void silc_hash_table_free(SilcHashTable ht)
{
+ SilcStack stack = ht->stack;
SilcHashTableEntry e, tmp;
int i;
ht->destructor(e->key, e->context, ht->destructor_user_context);
tmp = e;
e = e->next;
- silc_free(tmp);
+ silc_sfree(stack, tmp);
}
}
- silc_free(ht->table);
- silc_free(ht);
+ silc_sfree(stack, ht->table);
+ silc_sfree(stack, ht);
+ silc_stack_free(stack);
}
/* Returns the size of the hash table */
hash table. This function quarantees that the entry is always added
to the hash table reliably (it is collision resistant). */
-void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
+SilcBool silc_hash_table_add(SilcHashTable ht, void *key, void *context)
{
- silc_hash_table_add_internal(ht, key, context, ht->hash,
- ht->hash_user_context);
+ return 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_add_ext(SilcHashTable ht, void *key, void *context,
- SilcHashFunction hash, void *hash_user_context)
+SilcBool 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);
+ return 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
the `context. The destructor function will be called for the
replaced key and context. */
-void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
+SilcBool silc_hash_table_set(SilcHashTable ht, void *key, void *context)
{
- silc_hash_table_replace_internal(ht, key, context, ht->hash,
- ht->hash_user_context);
+ return silc_hash_table_replace_internal(ht, key, context, ht->hash,
+ ht->hash_user_context);
}
/* Same as above but with specific hash function. */
-void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
+SilcBool silc_hash_table_set_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);
+ return 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
call the destructor funtion for the found entry. Return TRUE if the
entry was removed successfully and FALSE otherwise. */
-bool silc_hash_table_del(SilcHashTable ht, void *key)
+SilcBool silc_hash_table_del(SilcHashTable ht, void *key)
{
SilcHashTableEntry *entry, prev, e;
entry = silc_hash_table_find_internal(ht, key, &prev,
ht->hash, ht->hash_user_context,
ht->compare, ht->compare_user_context);
- if (*entry == NULL)
+ if (*entry == NULL) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
e = *entry;
if (ht->destructor)
ht->destructor(e->key, e->context, ht->destructor_user_context);
- silc_free(e);
+ silc_sfree(ht->stack, e);
ht->entry_count--;
/* 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)
+SilcBool 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;
compare_user_context ?
compare_user_context :
ht->compare_user_context);
- if (*entry == NULL)
+ if (*entry == NULL) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
e = *entry;
if (ht->destructor)
ht->destructor(e->key, e->context, ht->destructor_user_context);
}
- silc_free(e);
+ silc_sfree(ht->stack, e);
ht->entry_count--;
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)
+SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
+ void *context)
{
SilcHashTableEntry *entry, prev, e;
ht->hash_user_context,
ht->compare,
ht->compare_user_context);
- if (*entry == NULL)
+ if (*entry == NULL) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
e = *entry;
if (ht->destructor)
ht->destructor(e->key, e->context, ht->destructor_user_context);
- silc_free(e);
+ silc_sfree(ht->stack, e);
ht->entry_count--;
/* 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)
+SilcBool 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;
compare_user_context ?
compare_user_context :
ht->compare_user_context);
- if (*entry == NULL)
+ if (*entry == NULL) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
e = *entry;
if (ht->destructor)
ht->destructor(e->key, e->context, ht->destructor_user_context);
}
- silc_free(e);
+ silc_sfree(ht->stack, e);
ht->entry_count--;
respectively. If the `ret_key and `ret_context' are NULL then this
maybe used only to check whether given key exists in the table. */
-bool silc_hash_table_find(SilcHashTable ht, void *key,
- void **ret_key, void **ret_context)
+SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
+ void **ret_key, void **ret_context)
{
- 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;
+ return silc_hash_table_find_ext(ht, key, ret_key, ret_context,
+ NULL, NULL, NULL, NULL);
}
/* 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)
+SilcBool 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;
compare_user_context ?
compare_user_context :
ht->compare_user_context);
- if (*entry == NULL)
+ if (*entry == NULL) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
if (ret_key)
*ret_key = (*entry)->key;
/* 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)
+SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
+ void *context, void **ret_key)
+{
+ return silc_hash_table_find_by_context_ext(ht, key, context, ret_key,
+ NULL, NULL, NULL, NULL);
+}
+
+/* Same as above but with specified hash and comparison functions. */
+
+SilcBool 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)
{
SilcHashTableEntry *entry;
entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
- ht->hash,
+ 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 || !(*entry))
+ if (!entry || !(*entry)) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
if (ret_key)
*ret_key = (*entry)->key;
{
SilcHashTableEntry e, tmp;
int i;
- bool auto_rehash;
+ SilcBool auto_rehash;
if (!foreach)
return;
int i;
SilcHashTableEntry *table, e, tmp;
SilcUInt32 table_size, size_index;
- bool auto_rehash;
+ SilcBool auto_rehash;
SILC_HT_DEBUG(("Start"));
ht->auto_rehash = FALSE;
/* Allocate new table */
- ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
+ ht->table = silc_scalloc(ht->stack,
+ primesize[size_index], sizeof(*ht->table));
if (!ht->table)
return;
ht->table_size = size_index;
e = e->next;
/* Remove old entry */
- silc_free(tmp);
+ silc_sfree(ht->stack, tmp);
}
}
ht->auto_rehash = auto_rehash;
/* Remove old table */
- silc_free(table);
+ silc_sfree(ht->stack, table);
}
/* Same as above but with specific hash function. */
int i;
SilcHashTableEntry *table, e, tmp;
SilcUInt32 table_size, size_index;
- bool auto_rehash;
+ SilcBool auto_rehash;
SILC_HT_DEBUG(("Start"));
ht->auto_rehash = FALSE;
/* Allocate new table */
- ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
+ ht->table = silc_scalloc(ht->stack,
+ primesize[size_index], sizeof(*ht->table));
if (!ht->table)
return;
ht->table_size = size_index;
e = e->next;
/* Remove old entry */
- silc_free(tmp);
+ silc_sfree(ht->stack, tmp);
}
}
ht->auto_rehash = auto_rehash;
/* Remove old table */
- silc_free(table);
+ silc_sfree(ht->stack, table);
}
/* Prepares the `htl' list structure sent as argument to be used in the
`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)
+SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key,
+ void **context)
{
SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
return TRUE;
}
+
+/**************************** Utility functions *****************************/
+
+/* Case sensitive hashing */
+
+SilcUInt32 silc_hash_string(void *key, void *user_context)
+{
+ char *s = (char *)key;
+ SilcUInt32 h = 0;
+
+ while (*s != '\0') {
+ h += *s++;
+ h += (h << 10);
+ h ^= (h >> 6);
+ }
+
+ h += (h << 3);
+ h ^= (h >> 11);
+ h += (h << 15);
+
+ return h;
+}
+
+/* Case-insensitive hashing */
+
+SilcUInt32 silc_hash_string_case(void *key, void *user_context)
+{
+ char *s = (char *)key;
+ SilcUInt32 h = 0;
+
+ while (*s != '\0') {
+ h += tolower((int)*s);
+ h += (h << 10);
+ h ^= (h >> 6);
+ s++;
+ }
+
+ h += (h << 3);
+ h ^= (h >> 11);
+ h += (h << 15);
+
+ return h;
+}
+
+/* Hash UTF-8 string */
+
+SilcUInt32 silc_hash_utf8_string(void *key, void *user_context)
+{
+ char *s = (char *)key;
+ SilcUInt32 h = 0;
+
+ while (*s != '\0') {
+ h += *s++;
+ h += (h << 10);
+ h ^= (h >> 6);
+ }
+
+ h += (h << 3);
+ h ^= (h >> 11);
+ h += (h << 15);
+
+ return h;
+}
+
+/* Basic hash function to hash integers. */
+
+SilcUInt32 silc_hash_uint(void *key, void *user_context)
+{
+ return SILC_PTR_TO_32(key);
+}
+
+/* Basic hash funtion to hash pointers. */
+
+SilcUInt32 silc_hash_ptr(void *key, void *user_context)
+{
+ return SILC_PTR_TO_32(key);
+}
+
+/* Hash binary data. The `user_context' is the data length. */
+
+SilcUInt32 silc_hash_data(void *key, void *user_context)
+{
+ SilcUInt32 len = SILC_PTR_TO_32(user_context), h, i;
+ unsigned char *data = (char *)key;
+
+ h = (data[0] * data[len - 1] + 1) * len;
+
+ for (i = 0; i < len; i++) {
+ h += data[i];
+ h += (h << 10);
+ h ^= (h >> 6);
+ }
+
+ h += (h << 3);
+ h ^= (h >> 11);
+ h += (h << 15);
+
+ return h;
+}
+
+/* Compares two strings. */
+
+SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context)
+{
+ return !strcmp((char *)key1, (char *)key2);
+}
+
+/* Compares two strings, ignores case. */
+
+SilcBool silc_hash_string_case_compare(void *key1, void *key2,
+ void *user_context)
+{
+ return !strcasecmp((char *)key1, (char *)key2);
+}
+
+/* Compares binary data. */
+
+SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context)
+{
+ SilcUInt32 len = SILC_PTR_TO_32(user_context);
+ return !memcmp(key1, key2, len);
+}
+
+/* Compares UTF-8 string. */
+
+SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context)
+{
+ int l1 = strlen((char *)key1);
+ int l2 = strlen((char *)key2);
+ if (l1 != l2)
+ return FALSE;
+ return !memcmp(key1, key2, l2);
+}
projects / silc.git / blobdiff