Author: Pekka Riikonen <priikone@silcnet.org>
- Copyright (C) 2001 - 2006 Pekka Riikonen
+ Copyright (C) 2001 - 2008 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
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 "silc.h"
-#include "silchashtable.h"
+#include "silcruntime.h"
/* Define to 1 if you want hash table debug enabled */
#define SILC_HASH_TABLE_DEBUG 0
/* Hash table. */
struct SilcHashTableStruct {
+ SilcStack stack;
SilcHashTableEntry *table;
SilcUInt32 table_size;
SilcUInt32 entry_count;
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;
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,
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 */
the `context. The destructor function will be called for the
replaced key and context. */
-SilcBool silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
+SilcBool silc_hash_table_set(SilcHashTable ht, void *key, void *context)
{
return silc_hash_table_replace_internal(ht, key, context, ht->hash,
ht->hash_user_context);
/* Same as above but with specific hash function. */
-SilcBool silc_hash_table_replace_ext(SilcHashTable ht, void *key,
- void *context,
- SilcHashFunction hash,
- void *hash_user_context)
+SilcBool silc_hash_table_set_ext(SilcHashTable ht, void *key,
+ void *context,
+ SilcHashFunction hash,
+ void *hash_user_context)
{
return silc_hash_table_replace_internal(ht, key, context,
hash, hash_user_context);
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. */
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)
+ 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--;
whether the correct entry is being deleted. */
SilcBool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
- void *context)
+ 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. */
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)
+ 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--;
maybe used only to check whether given key exists in the table. */
SilcBool silc_hash_table_find(SilcHashTable ht, void *key,
- void **ret_key, void **ret_context)
+ void **ret_key, void **ret_context)
{
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. */
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)
+ 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. */
SilcBool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
- void *context, void **ret_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)
+ void *context, void **ret_key,
+ 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 || !(*entry))
+ if (!entry || !(*entry)) {
+ silc_set_errno(SILC_ERR_NOT_FOUND);
return FALSE;
+ }
if (ret_key)
*ret_key = (*entry)->key;
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. */
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
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);
+}
+
+/* Generic destructor */
+
+void silc_hash_destructor(void *key, void *context, void *user_context)
+{
+ silc_free(key);
+ silc_free(context);
+}
projects / runtime.git / blobdiff