+Thu May 17 18:15:12 EEST 2001 Pekka Riikonen <priikone@poseidon.pspt.fi>
+
+ * Added new function silc_hash_table_find_all to return all keys
+ in the hash table by the specified key. As the hash table is
+ collision resistant it also makes it possible to have several
+ duplicate keys in the hash table. This function may be used to
+ find all of the keys from the hash.
+
+ Added user_context arguments to the SilcHashFunction,
+ SilcHashCompare and SilcHashDestructor to deliver user specified
+ context.
+
+ Added new fuctions silc_hash_table_find[_all]_ext to do
+ extended lookup with specified hash and compare functions and
+ specified user contexts.
+
+ Added new function silc_hash_table_add_ext to add the key
+ with specified hash function and user context.
+
+ Added new function silc_hash_table_foreach to traverse all
+ entrys in the hash table. Added SilcHashForeach callback
+ function.
+
+ Added new function silc_hash_table_del_by_context to delete
+ the entry only if the context associated with the key matches.
+
+ Affected files are lib/silcutil/silchashtable.[ch].
+
+ * Removed silc_hash_[server/client/channel]_id and added just
+ silc_hash_id to the lib/silcutil/silcutil.[ch]. Added also
+ silc_hash_id_compare to compare two ID's using as the hash table
+ comparison function. Added also silc_hash_data to hash
+ binary data and silc_hash_data_compare to compare it.
+
+ * Removed silc_idlist_find_client_by_hash as it is not needed
+ anymore. Affected file silcd/idlist.[ch].
+
+ * Rewrote the entire ID Cache system (in lib/silccore/idcache.[ch])
+ to use internally the SilcHashTable. The new ID Cache is a lot
+ faster than the old one. Some of the ID Cache interface was also
+ rewritten and obsolete and stupid functions were removed.
+
Wed May 16 23:03:30 EEST 2001 Pekka Riikonen <priikone@poseidon.pspt.fi>
* Added entry_count field to the SilcHashTable to keep the number
own resolver stuff (through scheduler, if possible without writing
too much own stuff) or use threads.
- o The ID List must be optimized. When the lists grow the searching
- becomes a lot slower and is some cases the lists are searched many
- times, like with channel messages (twice at least). Some sort of
- hash tables should replace the lists. Thus, the ID cache should be
- rewritten to use hash tables internally.
-
o The backup router support described in the protocol specification
should be done at some point.
o silc_id_render supports only IPv4 based ID's in the file
lib/silcutil/silcutil.c.
- o All the ID Cache routines has not been implemented in
- lib/silccore/idcache.c.
-
o Compression routines are missing. The protocol supports packet
compression thus it must be implemented. SILC Comp API must be
defined. zlib package is already included into the lib dir (in CVS,
return TRUE;
}
-/* Finds client by nickname hash. */
-
-SilcClientEntry
-silc_idlist_find_client_by_hash(SilcIDList id_list, char *nickname,
- SilcHash md5hash, SilcIDCacheEntry *ret_entry)
-{
- SilcIDCacheList list = NULL;
- SilcIDCacheEntry id_cache = NULL;
- SilcClientEntry client = NULL;
- unsigned char hash[32];
-
- SILC_LOG_DEBUG(("Client by hash"));
-
- silc_hash_make(md5hash, nickname, strlen(nickname), hash);
-
- if (!silc_idcache_find_by_id(id_list->clients, SILC_ID_CACHE_ANY,
- SILC_ID_CLIENT, &list))
- return NULL;
-
- if (!silc_idcache_list_first(list, &id_cache)) {
- silc_idcache_list_free(list);
- return NULL;
- }
-
- while (id_cache) {
- client = (SilcClientEntry)id_cache->context;
-
- if (client && SILC_ID_COMPARE_HASH(client->id, hash))
- break;
-
- id_cache = NULL;
- client = NULL;
-
- if (!silc_idcache_list_next(list, &id_cache))
- break;
- }
-
- silc_idcache_list_free(list);
-
- if (ret_entry)
- *ret_entry = id_cache;
-
- SILC_LOG_DEBUG(("Found"));
-
- return client;
-}
-
/* Finds client by Client ID */
SilcClientEntry
SilcClientEntry **clients,
uint32 *clients_count);
SilcClientEntry
-silc_idlist_find_client_by_hash(SilcIDList id_list, char *nickname,
- SilcHash md5hash, SilcIDCacheEntry *ret_entry);
-SilcClientEntry
silc_idlist_find_client_by_id(SilcIDList id_list, SilcClientID *id,
SilcIDCacheEntry *ret_entry);
SilcClientEntry
SilcBuffer idp;
/* Go through all clients in the list */
- if (silc_idcache_find_by_id(id_list->clients, SILC_ID_CACHE_ANY,
+ if (silc_idcache_find_by_id(id_list->servers, SILC_ID_CACHE_ANY,
SILC_ID_SERVER, &list)) {
if (silc_idcache_list_first(list, &id_cache)) {
while (id_cache) {
Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
- Copyright (C) 2000 Pekka Riikonen
+ Copyright (C) 2000 - 2001 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
#include "idcache.h"
/* Static prototypes */
-static int silc_idcache_sorter(const void *a, const void *b);
+static void silc_idcache_destructor(void *key, void *context,
+ void *user_context);
static SilcIDCacheList silc_idcache_list_alloc();
static void silc_idcache_list_add(SilcIDCacheList list,
SilcIDCacheEntry cache);
Fields are as follows:
- SilcIDCacheEntry cache
+ SilcHashTable id_table
- Table of the cache entries allocated by silc_idcache_add function.
- This table is reallocated when new entry is added into the cache.
+ Hash table using the ID as the key.
- uint32 cache_count
+ SilcHashTable data_table
- Number of cache entries in the cache.
+ Hash table using the data as the key.
- int sorted
+ SilcHashTable context_table
- Boolean value to indicate whether the cache is sorted or not. If
- cache is not sorted the fast access (described next) cannot be used.
- Sorting can be done by calling sorting function or when adding new
- entries to the cache.
-
- int fast_access[];
-
- Table to provide fast access into the cache by index. When searching
- by data this table is used to get the index to the first occurence
- of that data (or part of the data) in the cache. Purpose of this
- is to provide faster access to the cache when searching by data.
- This is updated by silc_idcache_add and sorting functions.
+ Hash table using the context as the key.
SilcIDCacheDestructor destructor
because the library will do it automatically. The appliation, however,
is responsible of freeing any data in the entry.
+ SilcIdType id_type
+
+ Indicates the type of the ID's this cache holds.
+
*/
struct SilcIDCacheStruct {
- SilcIDCacheEntry cache;
- uint32 cache_count;
- int sorted;
- int fast_access[256];
+ SilcHashTable id_table;
+ SilcHashTable data_table;
+ SilcHashTable context_table;
SilcIDCacheDestructor destructor;
+ SilcIdType type;
};
/*
};
/* Allocates new ID cache object. The initial amount of allocated entries
- can be sent as argument. If `count' is 0 the system uses default values. */
+ can be sent as argument. If `count' is 0 the system uses default values.
+ The `id_type' defines the types of the ID's that will be saved to the
+ cache. */
-SilcIDCache silc_idcache_alloc(uint32 count,
+SilcIDCache silc_idcache_alloc(uint32 count, SilcIdType id_type,
SilcIDCacheDestructor destructor)
{
SilcIDCache cache;
SILC_LOG_DEBUG(("Allocating new cache"));
cache = silc_calloc(1, sizeof(*cache));
- cache->cache = silc_calloc(count ? count : 5, sizeof(*cache->cache));
- cache->cache_count = count ? count : 5;
- memset(cache->fast_access, -1, sizeof(cache->fast_access));
+ cache->id_table = silc_hash_table_alloc(count, silc_hash_id,
+ (void *)(uint32)id_type,
+ silc_hash_id_compare,
+ (void *)(uint32)id_type,
+ silc_idcache_destructor, NULL);
+ cache->data_table = silc_hash_table_alloc(count, silc_hash_data, NULL,
+ silc_hash_data_compare, NULL,
+ NULL, NULL);
+ cache->context_table = silc_hash_table_alloc(count, silc_hash_ptr, NULL,
+ NULL, NULL, NULL, NULL);
cache->destructor = destructor;
+ cache->type = id_type;
return cache;
}
void silc_idcache_free(SilcIDCache cache)
{
if (cache) {
- silc_free(cache->cache);
+ silc_hash_table_free(cache->id_table);
+ silc_hash_table_free(cache->data_table);
+ silc_hash_table_free(cache->context_table);
silc_free(cache);
}
}
-/* qsort() sorter function. */
+/* Add new entry to the cache. */
-static int silc_idcache_sorter(const void *a, const void *b)
+bool silc_idcache_add(SilcIDCache cache, unsigned char *data,
+ uint32 data_len, void *id, void *context, int expire)
{
- SilcIDCacheEntry a1, b1;
+ SilcIDCacheEntry c;
+ uint32 curtime = time(NULL);
- a1 = (SilcIDCacheEntry)a;
- b1 = (SilcIDCacheEntry)b;
-
- if (!a1->data && !b1->data)
- return 0;
+ SILC_LOG_DEBUG(("Adding cache entry"));
- if (!a1->data)
- return -1;
+ /* See if entry with this ID already exists. */
+ if (silc_hash_table_find(cache->id_table, id, NULL, NULL))
+ return FALSE;
- if (!b1->data)
- return 1;
+ /* Allocate new cache entry */
+ c = silc_calloc(1, sizeof(*c));
+ c->data = data;
+ c->data_len = data_len;
+ c->id = id;
+ c->expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
+ c->context = context;
+
+ /* Add the new entry to the hash tables */
+
+ silc_hash_table_add(cache->id_table, id, c);
+ if (data)
+ silc_hash_table_add_ext(cache->data_table, data, c,
+ silc_hash_data, (void *)data_len);
+ if (context)
+ silc_hash_table_add(cache->context_table, context, c);
+
+ /* See whether we have time to rehash the tables */
+ if ((silc_hash_table_count(cache->id_table) * 2) >
+ silc_hash_table_size(cache->id_table)) {
+ silc_hash_table_rehash(cache->id_table, 0);
+ silc_hash_table_rehash(cache->data_table, 0);
+ silc_hash_table_rehash(cache->context_table, 0);
+ }
- return a1->data[0] - b1->data[0];
+ return TRUE;
}
-/* Sorts given cache by data. After sorting this updates the fast access
- table that can be used to access the cache faster. */
+/* Destructor for the ID Cache entry */
-void silc_idcache_sort_by_data(SilcIDCache cache)
+static void silc_idcache_destructor(void *key, void *context,
+ void *user_context)
{
- int i;
-
- qsort(cache->cache, cache->cache_count,
- sizeof(*cache->cache), silc_idcache_sorter);
-
- memset(cache->fast_access, -1, sizeof(cache->fast_access));
-
- /* Update the fast access table (this of course takes its own time when
- the cache is very large). */
- for (i = 0; i < cache->cache_count; i++) {
- if (cache->cache[i].data &&
- cache->fast_access[(int)cache->cache[i].data[0]] == -1)
- cache->fast_access[(int)cache->cache[i].data[0]] = i;
- }
-
- cache->sorted = TRUE;
+ silc_free(context);
}
-/* Find ID Cache entry by data. The data maybe anything that must
- match exactly. Returns list of cache entries. */
+/* Delete cache entry from cache. */
-int silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
- SilcIDCacheList *ret)
+bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
{
- int i;
- SilcIDCacheList list;
-
- if (!cache || !cache->cache || !data)
- return FALSE;
-
- list = silc_idcache_list_alloc();
-
- if (cache->sorted)
- i = cache->fast_access[(int)data[0]];
- else
- i = 0;
-
- if (i == -1)
- i = 0;
-
- for (i = i; i < cache->cache_count; i++) {
- if (cache->sorted && cache->cache[i].data &&
- cache->cache[i].data[0] != data[0])
- break;
+ bool ret;
- if (cache->cache[i].data &&
- !memcmp(cache->cache[i].data, data, cache->cache[i].data_len))
- silc_idcache_list_add(list, &(cache->cache[i]));
- }
-
- if (!silc_idcache_list_count(list)) {
- silc_idcache_list_free(list);
- return FALSE;
- }
+ ret = silc_hash_table_del_by_context(cache->data_table, old->data,
+ old->context);
+ ret = silc_hash_table_del(cache->context_table, old->context);
+ ret = silc_hash_table_del(cache->id_table, old->id);
- if (ret)
- *ret = list;
- else
- silc_idcache_list_free(list);
-
- return TRUE;
+ return ret;
}
-/* Find ID Cache entry by data. The data maybe anything that must
- match exactly. Returns one cache entry. */
+/* Deletes ID cache entry by ID. */
-int silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
- SilcIDCacheEntry *ret)
+bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
{
- int i;
+ bool ret;
+ SilcIDCacheEntry c;
- if (!cache || !cache->cache || !data)
+ if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
return FALSE;
- if (cache->sorted)
- i = cache->fast_access[(int)data[0]];
- else
- i = 0;
-
- if (i == -1)
- i = 0;
+ ret = silc_hash_table_del_by_context(cache->data_table, c->data,
+ c->context);
+ ret = silc_hash_table_del(cache->context_table, c->context);
+ ret = silc_hash_table_del(cache->id_table, c->id);
- for (i = i; i < cache->cache_count; i++)
- if (cache->cache[i].data &&
- !memcmp(cache->cache[i].data, data, cache->cache[i].data_len)) {
- if (ret)
- *ret = &(cache->cache[i]);
- return TRUE;
- }
-
- return FALSE;
+ return ret;
}
-/* Find ID Cache entry by data, loosely. The data don't have to be 100%
- match. This ignores data case-sensitivity when searching with this
- function. Returns list of cache entries. */
+/* Deletes all ID entries from cache. Free's memory as well. */
-int silc_idcache_find_by_data_loose(SilcIDCache cache, unsigned char *data,
- SilcIDCacheList *ret)
+bool silc_idcache_del_all(SilcIDCache cache)
{
- int i, c;
- SilcIDCacheList list;
-
- if (!cache || !cache->cache || !data)
- return FALSE;
-
- list = silc_idcache_list_alloc();
-
- c = tolower((int)data[0]);
-
- if (cache->sorted)
- i = cache->fast_access[c];
- else
- i = 0;
-
- if (i == -1)
- i = 0;
-
- for (i = i; i < cache->cache_count; i++) {
- if (cache->sorted && cache->cache[i].data &&
- cache->cache[i].data[0] != (char)c)
- break;
-
- if (cache->cache[i].data &&
- !strcasecmp(cache->cache[i].data, data))
- silc_idcache_list_add(list, &(cache->cache[i]));
- }
-
- if (cache->sorted) {
- c = toupper((int)data[0]);
- i = cache->fast_access[c];
-
- for (i = i; i < cache->cache_count; i++) {
- if (cache->sorted && cache->cache[i].data &&
- cache->cache[i].data[0] != (char)c)
- break;
-
- if (cache->cache[i].data &&
- !strcasecmp(cache->cache[i].data, data))
- silc_idcache_list_add(list, &(cache->cache[i]));
- }
- }
-
- if (!silc_idcache_list_count(list)) {
- silc_idcache_list_free(list);
- return FALSE;
- }
-
- if (ret)
- *ret = list;
- else
- silc_idcache_list_free(list);
-
+ silc_hash_table_free(cache->id_table);
+ silc_hash_table_free(cache->data_table);
+ silc_hash_table_free(cache->context_table);
return TRUE;
}
-/* Find ID Cache entry by ID. Returns list of cache entries. If `id' is
- SILC_ID_CACHE_ANY this returns all ID's of type `type'. */
+/* Foreach callback fro silc_idcache_purge. */
-int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
- SilcIDCacheList *ret)
+static void silc_idcache_purge_foreach(void *key, void *context,
+ void *user_context)
{
- int i;
- SilcIDCacheList list;
-
- if (!cache || !cache->cache || !id)
- return FALSE;
+ SilcIDCache cache = (SilcIDCache)user_context;
+ uint32 curtime = time(NULL);
+ SilcIDCacheEntry c = (SilcIDCacheEntry)context;
- list = silc_idcache_list_alloc();
+ if (c->expire && c->expire < curtime) {
+ /* Call the destructor */
+ if (cache->destructor)
+ cache->destructor(cache, c);
- if (id != SILC_ID_CACHE_ANY) {
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].id && SILC_ID_COMPARE_TYPE(cache->cache[i].id,
- id, type))
- silc_idcache_list_add(list, &(cache->cache[i]));
- } else {
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].id && cache->cache[i].type == type)
- silc_idcache_list_add(list, &(cache->cache[i]));
- }
-
- if (!silc_idcache_list_count(list)) {
- silc_idcache_list_free(list);
- return FALSE;
+ /* Delete the entry */
+ silc_idcache_del(cache, c);
}
+}
- if (ret)
- *ret = list;
- else
- silc_idcache_list_free(list);
+/* Purges the cache by removing expired cache entires. Note that this
+ may be very slow operation. */
+bool silc_idcache_purge(SilcIDCache cache)
+{
+ silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
return TRUE;
}
-/* Find ID Cache entry by ID. Returns one cache entry. */
+/* Purges the specific entry by context. */
-int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
- SilcIDCacheEntry *ret)
+bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
{
- int i;
+ SilcIDCacheEntry entry;
- if (!cache || !cache->cache || !id)
+ if (!silc_hash_table_find(cache->context_table, context, NULL,
+ (void *)&entry))
return FALSE;
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].id && SILC_ID_COMPARE_TYPE(cache->cache[i].id,
- id, type)) {
- if (ret)
- *ret = &(cache->cache[i]);
- return TRUE;
- }
-
- return FALSE;
+ /* Call the destructor */
+ if (cache->destructor)
+ cache->destructor(cache, entry);
+
+ return silc_idcache_del(cache, entry);
}
-/* Finds cache entry by context. */
+/* Callback that is called by the hash table routine when traversing
+ all entrys in the hash table. */
-int silc_idcache_find_by_context(SilcIDCache cache, void *context,
- SilcIDCacheEntry *ret)
+static void silc_idcache_get_all_foreach(void *key, void *context,
+ void *user_context)
{
- int i;
-
- if (!cache || !cache->cache || !context)
- return FALSE;
-
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].context && cache->cache[i].context == context) {
- if (ret)
- *ret = &(cache->cache[i]);
- return TRUE;
- }
-
- return FALSE;
+ SilcIDCacheList list = (SilcIDCacheList)user_context;
+ silc_idcache_list_add(list, (SilcIDCacheEntry)context);
}
-/* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
- then the cache is sorted after the new entry has been added. The
- cache must be sorted in order for the fast access feature to work,
- however, it is not mandatory. */
+/* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
-int silc_idcache_add(SilcIDCache cache, unsigned char *data,
- uint32 data_len, SilcIdType id_type, void *id,
- void *context, int sort, int expire)
+bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
{
- int i;
- uint32 count;
- uint32 curtime = time(NULL);
- SilcIDCacheEntry c;
-
- if (!cache || !cache->cache)
- return FALSE;
-
- SILC_LOG_DEBUG(("Adding cache entry"));
+ SilcIDCacheList list;
- c = cache->cache;
- count = cache->cache_count;
+ if (!ret)
+ return TRUE;
- if (c == NULL) {
- c = silc_calloc(5, sizeof(*c));
- count = 5;
- }
+ list = silc_idcache_list_alloc();
+ silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
- /* See if it exists already */
- /* XXX this slows down this function. */
- if (silc_idcache_find_by_id(cache, id, id_type, NULL))
+ if (silc_idcache_list_count(list) == 0) {
+ silc_idcache_list_free(list);
return FALSE;
-
- for (i = 0; i < count; i++) {
- if (c[i].data == NULL && c[i].id == NULL) {
- c[i].data = data;
- c[i].data_len = data_len;
- c[i].type = id_type;
- c[i].id = id;
- c[i].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
- c[i].context = context;
- break;
- }
- }
-
- if (i == count) {
- c = silc_realloc(c, sizeof(*c) * (count + 5));
- for (i = count; i < count + 5; i++) {
- c[i].data = NULL;
- c[i].id = NULL;
- }
- c[count].data = data;
- c[count].data_len = data_len;
- c[count].type = id_type;
- c[count].id = id;
- c[count].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
- c[count].context = context;
- count += 5;
}
- cache->cache = c;
- cache->cache_count = count;
- cache->sorted = sort;
-
- if (sort)
- silc_idcache_sort_by_data(cache);
+ *ret = list;
return TRUE;
}
-/* Delete cache entry from cache. */
-/* XXX */
+/* Find ID Cache entry by ID. */
-int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
+bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
+ SilcIDCacheEntry *ret)
{
-
- return TRUE;
+ return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
}
-/* XXX */
+/* Finds cache entry by context. */
-int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data)
+bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
+ SilcIDCacheEntry *ret)
{
-
- return TRUE;
+ return silc_hash_table_find(cache->context_table, context, NULL,
+ (void *)ret);
}
-/* Deletes ID cache entry by ID. */
+/* Find ID Cache entry by data. The data maybe anything that must
+ match exactly. Returns list of cache entries. */
-int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
+bool silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
+ unsigned int data_len, SilcIDCacheList *ret)
{
+ SilcIDCacheList list;
+ void **contexts;
+ unsigned int count;
int i;
- if (!cache || !cache->cache || !id)
+ if (!silc_hash_table_find_all_ext(cache->data_table, data, NULL, &contexts,
+ &count, silc_hash_data, (void *)data_len,
+ silc_hash_data_compare, (void *)data_len))
return FALSE;
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].id && SILC_ID_COMPARE_TYPE(cache->cache[i].id,
- id, type)) {
- cache->cache[i].id = NULL;
- cache->cache[i].data = NULL;
- cache->cache[i].type = 0;
- cache->cache[i].context = NULL;
- return TRUE;
- }
-
- return FALSE;
-}
+ if (!ret) {
+ silc_free(contexts);
+ return TRUE;
+ }
-/* Deletes all ID entries from cache. Free's memory as well. */
+ list = silc_idcache_list_alloc();
-int silc_idcache_del_all(SilcIDCache cache)
-{
- if (!cache || !cache->cache)
- return FALSE;
+ for (i = 0; i < count; i++)
+ silc_idcache_list_add(list, (SilcIDCacheEntry)contexts[i]);
+ silc_free(contexts);
- silc_free(cache->cache);
- cache->cache = NULL;
- cache->cache_count = 0;
+ *ret = list;
return TRUE;
}
-/* Purges the cache by removing expired cache entires. This does not
- free any memory though. */
+/* Find ID Cache entry by data. The data maybe anything that must
+ match exactly. Returns one cache entry. */
-int silc_idcache_purge(SilcIDCache cache)
+bool silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
+ unsigned int data_len,
+ SilcIDCacheEntry *ret)
{
SilcIDCacheEntry c;
- uint32 curtime = time(NULL);
- int i;
- if (!cache || !cache->cache)
+ if (!silc_hash_table_find_ext(cache->data_table, data, NULL, (void *)&c,
+ silc_hash_data, (void *)data_len,
+ silc_hash_data_compare, (void *)data_len))
return FALSE;
- c = cache->cache;
-
- for (i = 0; i < cache->cache_count; i++) {
- if (c[i].data && c[i].expire && c[i].expire < curtime) {
-
- /* Call the destructor */
- if (cache->destructor)
- cache->destructor(cache, &c[i]);
-
- c[i].id = NULL;
- c[i].data = NULL;
- c[i].type = 0;
- c[i].expire = 0;
- c[i].context = NULL;
- }
- }
-
- return TRUE;
-}
-
-/* Purges the specific entry by context. */
-
-int silc_idcache_purge_by_context(SilcIDCache cache, void *context)
-{
- SilcIDCacheEntry entry;
-
- if (!silc_idcache_find_by_context(cache, context, &entry))
- return FALSE;
+ if (ret)
+ *ret = c;
- /* Call the destructor */
- if (cache->destructor)
- cache->destructor(cache, entry);
-
- entry->id = NULL;
- entry->data = NULL;
- entry->type = 0;
- entry->expire = 0;
- entry->context = NULL;
return TRUE;
}
/* Returns first entry from the ID cache list. */
-int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
+bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
{
list->pos = 0;
/* Returns next entry from the ID cache list. */
-int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
+bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
{
int dyn = FALSE;
list->pos++;
Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
- Copyright (C) 2000 Pekka Riikonen
+ Copyright (C) 2000 - 2001 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
This is one entry in the SILC ID Cache system. Contents of this is
allocated outside the ID cache system, however, all the fields are
filled with ID cache utility functions. The ID cache system does not
- allocate any of these fields nor free them.
+ allocate any of these fields nor free them. The system assumes that
+ the type of the ID in a specific ID Cache context are of the same
+ type. One should not mix different types of ID's (eg. Client ID and
+ Server ID) to the same ID Cache context.
unsigned char *data
uint32 data_len;
The data that is usually used to find the data from the cache.
For example for Client ID's this is nickname.
- SilcIdType type
-
- Type of the ID.
-
void *id
The actual ID.
typedef struct {
unsigned char *data;
uint32 data_len;
- SilcIdType type;
void *id;
uint32 expire;
void *context;
#define SILC_ID_CACHE_EXPIRE_DEF (time(NULL) + SILC_ID_CACHE_EXPIRE)
/* Prototypes */
-SilcIDCache silc_idcache_alloc(uint32 count,
+SilcIDCache silc_idcache_alloc(uint32 count, SilcIdType id_type,
SilcIDCacheDestructor destructor);
void silc_idcache_free(SilcIDCache cache);
-void silc_idcache_sort_by_data(SilcIDCache cache);
-int silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
- SilcIDCacheList *ret);
-int silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
+bool silc_idcache_add(SilcIDCache cache, unsigned char *data,
+ uint32 data_len, void *id, void *context, int expire);
+bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old);
+bool silc_idcache_del_by_id(SilcIDCache cache, void *id);
+bool silc_idcache_del_all(SilcIDCache cache);
+bool silc_idcache_purge(SilcIDCache cache);
+bool silc_idcache_purge_by_context(SilcIDCache cache, void *context);
+bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret);
+bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
+ SilcIDCacheEntry *ret);
+bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
SilcIDCacheEntry *ret);
-int silc_idcache_find_by_data_loose(SilcIDCache cache, unsigned char *data,
- SilcIDCacheList *ret);
-int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
- SilcIDCacheList *ret);
-int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
- SilcIDCacheEntry *ret);
-int silc_idcache_find_by_context(SilcIDCache cache, void *context,
- SilcIDCacheEntry *ret);
-int silc_idcache_add(SilcIDCache cache, unsigned char *data,
- uint32 data_len, SilcIdType id_type, void *id,
- void *context, int sort, int expire);
-int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old);
-int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data);
-int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id);
-int silc_idcache_del_all(SilcIDCache cache);
-int silc_idcache_purge(SilcIDCache cache);
-int silc_idcache_purge_by_context(SilcIDCache cache, void *context);
+bool silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
+ unsigned int data_len, SilcIDCacheList *ret);
+bool silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
+ unsigned int data_len,
+ SilcIDCacheEntry *ret);
int silc_idcache_list_count(SilcIDCacheList list);
-int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret);
-int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret);
+bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret);
+bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret);
void silc_idcache_list_free(SilcIDCacheList list);
#endif
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"
#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 \
+ (ht->hash(key, ht->hash_user_context) % primesize[ht->table_size])
+#define SILC_HASH_TABLE_HASH_F(f, c) \
+ ((f)(key, (c)) % primesize[ht->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
SilcHashFunction hash;
SilcHashCompare compare;
SilcHashDestructor destructor;
+ void *hash_user_context;
+ void *compare_user_context;
+ void *destructor_user_context;
};
/* Prime sizes for the hash table. The size of the table will always
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,
entry = &ht->table[SILC_HASH_TABLE_HASH];
if (ht->compare) {
- while (*entry && ht->compare((*entry)->key, key) == FALSE) {
+ while (*entry && ht->compare((*entry)->key, key, ht->compare_user_context)
+ == FALSE) {
prev = *entry;
entry = &(*entry)->next;
}
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)
+{
+ SilcHashTableEntry *entry, prev = NULL;
+
+ entry = &ht->table[SILC_HASH_TABLE_HASH];
+ if (ht->compare) {
+ while (*entry && ht->compare((*entry)->key, key, ht->compare_user_context)
+ == FALSE && (*entry)->context != context) {
+ prev = *entry;
+ entry = &(*entry)->next;
+ }
+ } else {
+ while (*entry && (*entry)->key != key && (*entry)->context != context) {
+ 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;
+
+ if (hash)
+ entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)];
+ else
+ entry = &ht->table[SILC_HASH_TABLE_HASH];
+ 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)
+{
+ SilcHashTableEntry *entry;
+
+ *entries = NULL;
+ *count = 0;
+
+ entry = &ht->table[SILC_HASH_TABLE_HASH];
+ if (compare) {
+ while (*entry) {
+ if (compare((*entry)->key, key, 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 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;
+ uint32 index = (hash ? SILC_HASH_TABLE_HASH :
+ SILC_HASH_TABLE_HASH_F(hash, hash_user_context));
+
+ 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;
+
+ e = *entry;
+ tmp = e->next;
+ while (tmp) {
+ e = tmp;
+ tmp = tmp->next;
+ }
+
+ 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++;
+ }
+}
+
/* 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
SilcHashTable silc_hash_table_alloc(uint32 table_size,
SilcHashFunction hash,
+ void *hash_user_context,
SilcHashCompare compare,
- SilcHashDestructor destructor)
+ void *compare_user_context,
+ SilcHashDestructor destructor,
+ void *destructor_user_context)
{
SilcHashTable ht;
uint32 size_index = SILC_HASH_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;
return 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);
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, NULL, NULL);
+}
- 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
/* 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((*entry)->key, (*entry)->context,
+ ht->destructor_user_context);
} else {
/* New key */
*entry = silc_calloc(1, sizeof(**entry));
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--;
+
+ 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);
+ 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--;
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(ht, key, &prev);
+ entry = silc_hash_table_find_internal_simple(ht, key, NULL, NULL,
+ NULL, NULL);
+ if (*entry == NULL)
+ return FALSE;
+
+ if (ret_key)
+ *ret_key = (*entry)->key;
+ if (ret_context)
+ *ret_context = (*entry)->context;
+
+ 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,
+ 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_simple(ht, key,
+ hash, hash_user_context,
+ compare, compare_user_context);
if (*entry == NULL)
return FALSE;
return TRUE;
}
+/* Same as above but with specified hash and comparison functions. */
+
+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)
+{
+ 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_free(entries);
+
+ return TRUE;
+}
+
+/* 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;
+
+ if (!foreach)
+ return;
+
+ 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;
+ }
+ }
+}
+
/* 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
/* A type for the hash function. This function is used to hash the
provided key value `key' and return the index for the hash table. */
-typedef uint32 (*SilcHashFunction)(void *key);
+typedef uint32 (*SilcHashFunction)(void *key, void *user_context);
/* A comparison funtion that is called to compare the two keys `key1' and
`key2'. If they are equal this must return TRUE or FALSE otherwise.
The application provides this function when allocating a new hash table. */
-typedef bool (*SilcHashCompare)(void *key1, void *key2);
+typedef bool (*SilcHashCompare)(void *key1, void *key2, void *user_context);
/* A destructor callback that the library will call to destroy the
`key' and `context'. The appliation provides the function when
allocating a new hash table. */
-typedef void (*SilcHashDestructor)(void *key, void *context);
+typedef void (*SilcHashDestructor)(void *key, void *context,
+ void *user_context);
+
+/* Foreach function. This is called when traversing the entrys in the
+ hash table using silc_hash_table_foreach. */
+typedef void (*SilcHashForeach)(void *key, void *context, void *user_context);
/* Prototypes */
SilcHashTable silc_hash_table_alloc(uint32 table_size,
SilcHashFunction hash,
+ void *hash_user_context,
SilcHashCompare compare,
- SilcHashDestructor destructor);
+ void *compare_user_context,
+ SilcHashDestructor destructor,
+ void *destructor_user_context);
void silc_hash_table_free(SilcHashTable ht);
uint32 silc_hash_table_size(SilcHashTable ht);
uint32 silc_hash_table_count(SilcHashTable ht);
void silc_hash_table_add(SilcHashTable ht, void *key, void *context);
+void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
+ SilcHashFunction hash, void *hash_user_context);
void silc_hash_table_replace(SilcHashTable ht, void *key, void *context);
bool silc_hash_table_del(SilcHashTable ht, void *key);
+bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
+ void *context);
bool silc_hash_table_find(SilcHashTable ht, void *key,
void **ret_key, void **ret_context);
+bool silc_hash_table_find_all(SilcHashTable ht, void *key,
+ void ***ret_keys, void ***ret_contexts,
+ unsigned int *ret_count);
+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);
+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_foreach(SilcHashTable ht, SilcHashForeach foreach,
+ void *user_context);
void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size);
#endif
/* Basic has function to hash strings. May be used with the SilcHashTable. */
-uint32 silc_hash_string(void *key)
+uint32 silc_hash_string(void *key, void *user_context)
{
char *s = (char *)key;
uint32 h = 0, g;
/* Basic hash function to hash integers. May be used with the SilcHashTable. */
-uint32 silc_hash_uint(void *key)
+uint32 silc_hash_uint(void *key, void *user_context)
{
return *(uint32 *)key;
}
/* Basic hash funtion to hash pointers. May be used with the SilcHashTable. */
-uint32 silc_hash_ptr(void *key)
+uint32 silc_hash_ptr(void *key, void *user_context)
{
return (uint32)key;
}
-/* Hash a Server ID. */
+/* Hash a ID. The `user_context' is the ID type. */
-uint32 silc_hash_server_id(void *key)
+uint32 silc_hash_id(void *key, void *user_context)
{
- SilcServerID *id = (SilcServerID *)key;
- int i;
- uint32 h;
+ SilcIdType id_type = (SilcIdType)(uint32)user_context;
+ uint32 h = 0;
- h = id->port * id->rnd;
- for (i = 0; i < id->ip.data_len; i++)
- h ^= id->ip.data[i];
+ switch (id_type) {
+ case SILC_ID_CLIENT:
+ {
+ SilcClientID *id = (SilcClientID *)key;
+ int i;
+ uint32 h;
+
+ h = id->rnd;
+ for (i = 0; i < sizeof(id->hash); i++)
+ h ^= id->hash[i];
+ for (i = 0; i < id->ip.data_len; i++)
+ h ^= id->ip.data[i];
+
+ return h;
+ }
+ break;
+ case SILC_ID_SERVER:
+ {
+ SilcServerID *id = (SilcServerID *)key;
+ int i;
+ uint32 h;
+
+ h = id->port * id->rnd;
+ for (i = 0; i < id->ip.data_len; i++)
+ h ^= id->ip.data[i];
+
+ return h;
+ }
+ break;
+ case SILC_ID_CHANNEL:
+ {
+ SilcChannelID *id = (SilcChannelID *)key;
+ int i;
+ uint32 h;
+
+ h = id->port * id->rnd;
+ for (i = 0; i < id->ip.data_len; i++)
+ h ^= id->ip.data[i];
+
+ return h;
+ }
+ break;
+ default:
+ break;
+ }
return h;
}
-/* Hash a Client ID. */
+/* Hash binary data. The `user_context' is the data length. */
-uint32 silc_hash_client_id(void *key)
+uint32 silc_hash_data(void *key, void *user_context)
{
- SilcClientID *id = (SilcClientID *)key;
+ uint32 len = (uint32)user_context, h = 0;
+ unsigned char *data = (unsigned char *)key;
int i;
- uint32 h;
- h = id->rnd;
- for (i = 0; i < sizeof(id->hash); i++)
- h ^= id->hash[i];
- for (i = 0; i < id->ip.data_len; i++)
- h ^= id->ip.data[i];
+ h = (data[0] * data[len - 1] + 1) * len;
+ for (i = 0; i < len; i++)
+ h ^= data[i];
return h;
}
-/* Hash a Channel ID. */
+/* Compares two ID's. May be used as SilcHashTable comparison function. */
-uint32 silc_hash_channel_id(void *key)
+bool silc_hash_id_compare(void *key1, void *key2, void *user_context)
{
- SilcChannelID *id = (SilcChannelID *)key;
- int i;
- uint32 h;
+ SilcIdType id_type = (SilcIdType)(uint32)user_context;
+ return SILC_ID_COMPARE_TYPE(key1, key2, id_type);
+}
- h = id->port * id->rnd;
- for (i = 0; i < id->ip.data_len; i++)
- h ^= id->ip.data[i];
+/* Compares binary data. May be used as SilcHashTable comparison function. */
- return h;
+bool silc_hash_data_compare(void *key1, void *key2, void *user_context)
+{
+ uint32 len = (uint32)user_context;
+ return !memcmp(key1, key2, len);
}
int silc_string_match(const char *string1, const char *string2);
char *silc_get_username();
char *silc_get_real_name();
-uint32 silc_hash_string(void *key);
-uint32 silc_hash_uint(void *key);
-uint32 silc_hash_ptr(void *key);
-uint32 silc_hash_server_id(void *key);
-uint32 silc_hash_client_id(void *key);
-uint32 silc_hash_channel_id(void *key);
+uint32 silc_hash_string(void *key, void *user_context);
+uint32 silc_hash_uint(void *key, void *user_context);
+uint32 silc_hash_ptr(void *key, void *user_context);
+uint32 silc_hash_id(void *key, void *user_context);
+uint32 silc_hash_data(void *key, void *user_context);
+bool silc_hash_id_compare(void *key1, void *key2, void *user_context);
+bool silc_hash_data_compare(void *key1, void *key2, void *user_context);
#endif
projects / silc.git / commitdiff