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.
- unsigned int cache_count
+ SilcHashTable name_table
- Number of cache entries in the cache.
+ Hash table using the name 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;
- unsigned int cache_count;
- int sorted;
- int fast_access[256];
+ SilcHashTable id_table;
+ SilcHashTable name_table;
+ SilcHashTable context_table;
SilcIDCacheDestructor destructor;
+ SilcIdType type;
};
/*
struct SilcIDCacheListStruct {
SilcIDCacheEntry cache[64];
SilcIDCacheEntry *cache_dyn;
- unsigned int cache_dyn_count;
- unsigned int cache_count;
- unsigned int pos;
+ uint32 cache_dyn_count;
+ uint32 cache_count;
+ uint32 pos;
};
/* 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(unsigned int 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,
+ FALSE);
+ cache->name_table = silc_hash_table_alloc(count, silc_hash_string, NULL,
+ silc_hash_string_compare, NULL,
+ NULL, NULL, FALSE);
+ cache->context_table = silc_hash_table_alloc(count, silc_hash_ptr, NULL,
+ NULL, NULL, NULL, NULL, FALSE);
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->name_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, char *name, void *id,
+ void *context, int expire)
{
- SilcIDCacheEntry a1, b1;
-
- a1 = (SilcIDCacheEntry)a;
- b1 = (SilcIDCacheEntry)b;
-
- if (!a1->data && !b1->data)
- return 0;
+ SilcIDCacheEntry c;
+ uint32 curtime = time(NULL);
- if (!a1->data)
- return -1;
+ SILC_LOG_DEBUG(("Adding cache entry"));
- if (!b1->data)
- return 1;
+ /* Allocate new cache entry */
+ c = silc_calloc(1, sizeof(*c));
+ c->id = id;
+ c->name = name;
+ c->expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
+ c->context = context;
+
+ /* Add the new entry to the hash tables */
+
+ if (id)
+ silc_hash_table_add(cache->id_table, id, c);
+ if (name)
+ silc_hash_table_add(cache->name_table, name, c);
+ 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->name_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;
+ bool ret = FALSE;
- if (!cache || !cache->cache || !data)
- return FALSE;
+ SILC_LOG_DEBUG(("Deleting cache entry"));
- list = silc_idcache_list_alloc();
+ if (old->name)
+ ret = silc_hash_table_del_by_context(cache->name_table, old->name, old);
+ if (old->context)
+ ret = silc_hash_table_del(cache->context_table, old->context);
+ if (old->id)
+ ret = silc_hash_table_del(cache->id_table, old->id);
- if (cache->sorted)
- i = cache->fast_access[(int)data[0]];
- else
- i = 0;
-
- if (i == -1)
- i = 0;
+ return ret;
+}
- for (i = i; i < cache->cache_count; i++) {
- if (cache->sorted && cache->cache[i].data &&
- cache->cache[i].data[0] != data[0])
- break;
+/* Deletes ID cache entry by ID. */
- if (cache->cache[i].data &&
- !memcmp(cache->cache[i].data, data, cache->cache[i].data_len))
- silc_idcache_list_add(list, &(cache->cache[i]));
- }
+bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
+{
+ SilcIDCacheEntry c;
- if (!silc_idcache_list_count(list))
+ if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
return FALSE;
- if (ret)
- *ret = list;
- else
- silc_idcache_list_free(list);
-
- return TRUE;
+ return silc_idcache_del(cache, c);
}
-/* Find ID Cache entry by data. The data maybe anything that must
- match exactly. Returns one cache entry. */
+/* Same as above but with specific hash and comparison functions. If the
+ functions are NULL then default values are used. */
-int silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
- SilcIDCacheEntry *ret)
+bool silc_idcache_del_by_id_ext(SilcIDCache cache, void *id,
+ SilcHashFunction hash,
+ void *hash_context,
+ SilcHashCompare compare,
+ void *compare_context)
{
- int i;
-
- if (!cache || !cache->cache || !data)
- return FALSE;
+ SilcIDCacheEntry c;
+ bool ret = FALSE;
- if (cache->sorted)
- i = cache->fast_access[(int)data[0]];
- else
- i = 0;
+ SILC_LOG_DEBUG(("Deleting cache entry"));
- if (i == -1)
- i = 0;
+ if (!silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)&c,
+ hash, hash_context, compare,
+ compare_context))
+ return FALSE;
- 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;
- }
+ if (c->name)
+ ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
+ if (c->context)
+ ret = silc_hash_table_del(cache->context_table, c->context);
+ if (c->id)
+ ret = silc_hash_table_del_ext(cache->id_table, c->id, hash,
+ hash_context, compare, compare_context);
- 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 ID cache entry by context. */
-int silc_idcache_find_by_data_loose(SilcIDCache cache, unsigned char *data,
- SilcIDCacheList *ret)
+bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
{
- 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;
+ SilcIDCacheEntry c;
+ bool ret = FALSE;
- if (i == -1)
- i = 0;
+ SILC_LOG_DEBUG(("Deleting cache entry"));
- 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_hash_table_find(cache->context_table, context, NULL, (void *)&c))
+ return FALSE;
- if (cache->sorted) {
- c = toupper((int)data[0]);
- i = cache->fast_access[c];
+ if (c->name)
+ ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
+ if (c->context)
+ ret = silc_hash_table_del(cache->context_table, c->context);
+ if (c->id)
+ ret = silc_hash_table_del_by_context(cache->id_table, c->id, c);
- for (i = i; i < cache->cache_count; i++) {
- if (cache->sorted && cache->cache[i].data &&
- cache->cache[i].data[0] != (char)c)
- break;
+ return ret;
+}
- 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))
- return FALSE;
+/* Deletes all ID entries from cache. Free's memory as well. */
- if (ret)
- *ret = list;
- else
- silc_idcache_list_free(list);
+bool silc_idcache_del_all(SilcIDCache cache)
+{
+ silc_hash_table_free(cache->id_table);
+ silc_hash_table_free(cache->name_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, id_len;
- SilcIDCacheList list;
+ SilcIDCache cache = (SilcIDCache)user_context;
+ uint32 curtime = time(NULL);
+ SilcIDCacheEntry c = (SilcIDCacheEntry)context;
- if (!cache || !cache->cache || !id)
- return FALSE;
-
- id_len = silc_id_get_len(type);
-
- 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 && !memcmp(cache->cache[i].id, id, id_len))
- 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]));
+ /* Delete the entry */
+ silc_idcache_del(cache, c);
}
+}
- if (!silc_idcache_list_count(list))
- return FALSE;
-
- 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, id_len;
+ SilcIDCacheEntry entry;
+ bool ret = FALSE;
- if (!cache || !cache->cache || !id)
+ if (!silc_hash_table_find(cache->context_table, context, NULL,
+ (void *)&entry))
return FALSE;
- id_len = silc_id_get_len(type);
+ /* Call the destructor */
+ if (cache->destructor)
+ cache->destructor(cache, entry);
+
+ if (entry->name)
+ ret = silc_hash_table_del_by_context(cache->name_table, entry->name,
+ entry);
+ if (entry->context)
+ ret = silc_hash_table_del(cache->context_table, entry->context);
+ if (entry->id)
+ ret = silc_hash_table_del_by_context(cache->id_table, entry->id, entry);
+
+ return ret;
+}
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
- if (ret)
- *ret = &(cache->cache[i]);
- return TRUE;
- }
+/* Callback that is called by the hash table routine when traversing
+ entrys in the hash table. */
- return FALSE;
+static void silc_idcache_get_all_foreach(void *key, void *context,
+ void *user_context)
+{
+ SilcIDCacheList list = (SilcIDCacheList)user_context;
+ silc_idcache_list_add(list, (SilcIDCacheEntry)context);
}
-/* Finds cache entry by context. */
+/* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
-int silc_idcache_find_by_context(SilcIDCache cache, void *context,
- SilcIDCacheEntry *ret)
+bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
{
- int i;
+ SilcIDCacheList list;
+
+ if (!ret)
+ return TRUE;
- if (!cache || !cache->cache || !context)
+ list = silc_idcache_list_alloc();
+ silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
+
+ if (silc_idcache_list_count(list) == 0) {
+ silc_idcache_list_free(list);
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;
- }
+ *ret = list;
- return FALSE;
+ return TRUE;
}
-/* 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. */
+/* Find ID Cache entry by ID. May return multiple entries. */
-int silc_idcache_add(SilcIDCache cache, unsigned char *data,
- unsigned int data_len, SilcIdType id_type, void *id,
- void *context, int sort, int expire)
+bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
+ SilcIDCacheList *ret)
{
- int i;
- unsigned int count;
- unsigned long curtime = time(NULL);
- SilcIDCacheEntry c;
-
- if (!cache || !cache->cache)
- return FALSE;
+ SilcIDCacheList list;
- SILC_LOG_DEBUG(("Adding cache entry"));
+ list = silc_idcache_list_alloc();
- c = cache->cache;
- count = cache->cache_count;
+ if (!ret)
+ return TRUE;
- if (c == NULL) {
- c = silc_calloc(5, sizeof(*c));
- count = 5;
- }
+ silc_hash_table_find_foreach(cache->id_table, id,
+ 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 specific ID with specific hash function and comparison functions.
+ If `hash' is NULL then the default hash funtion is used and if `compare'
+ is NULL default comparison function is used. */
-int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
+bool silc_idcache_find_by_id_one_ext(SilcIDCache cache, void *id,
+ SilcHashFunction hash,
+ void *hash_context,
+ SilcHashCompare compare,
+ void *compare_context,
+ SilcIDCacheEntry *ret)
{
-
- return TRUE;
+ return silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
+ hash, hash_context, compare,
+ compare_context);
}
-/* XXX */
+/* Find one specific ID entry. */
-int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data)
+bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
+ SilcIDCacheEntry *ret)
{
-
- return TRUE;
+ return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
}
-/* Deletes ID cache entry by ID. */
+/* Finds cache entry by context. */
-int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
+bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
+ SilcIDCacheEntry *ret)
{
- int i, id_len;
-
- if (!cache || !cache->cache || !id)
- return FALSE;
-
- id_len = silc_id_get_len(type);
-
- for (i = 0; i < cache->cache_count; i++)
- if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
- cache->cache[i].id = NULL;
- cache->cache[i].data = NULL;
- cache->cache[i].type = 0;
- cache->cache[i].context = NULL;
- return TRUE;
- }
-
- return FALSE;
+ return silc_hash_table_find(cache->context_table, context, NULL,
+ (void *)ret);
}
-/* Deletes all ID entries from cache. Free's memory as well. */
+/* Find ID Cache entry by name. Returns list of cache entries. */
-int silc_idcache_del_all(SilcIDCache cache)
+bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
+ SilcIDCacheList *ret)
{
- if (!cache || !cache->cache)
- return FALSE;
-
- silc_free(cache->cache);
- cache->cache = NULL;
- cache->cache_count = 0;
+ SilcIDCacheList list;
- return TRUE;
-}
+ list = silc_idcache_list_alloc();
-/* Purges the cache by removing expired cache entires. This does not
- free any memory though. */
+ if (!ret)
+ return TRUE;
-int silc_idcache_purge(SilcIDCache cache)
-{
- SilcIDCacheEntry c;
- unsigned long curtime = time(NULL);
- int i;
+ silc_hash_table_find_foreach(cache->name_table, name,
+ silc_idcache_get_all_foreach, list);
- if (!cache || !cache->cache)
+ if (silc_idcache_list_count(list) == 0) {
+ silc_idcache_list_free(list);
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;
- }
}
+ *ret = list;
+
return TRUE;
}
-/* Purges the specific entry by context. */
+/* Find ID Cache entry by name. Returns one cache entry. */
-int silc_idcache_purge_by_context(SilcIDCache cache, void *context)
+bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
+ SilcIDCacheEntry *ret)
{
- SilcIDCacheEntry entry;
-
- if (!silc_idcache_find_by_context(cache, context, &entry))
+ if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
return FALSE;
- /* 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++;
projects / silc.git / blobdiff