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
GNU General Public License for more details.
*/
-/* XXX: This ID cache system sucks and must be rewritten! */
-/*
- * $Id$
- * $Log$
- * Revision 1.2 2000/07/05 06:06:35 priikone
- * Global cosmetic change.
- *
- * Revision 1.1.1.1 2000/06/27 11:36:55 priikone
- * Imported from internal CVS/Added Log headers.
- *
- *
- */
+/* $Id$ */
#include "silcincludes.h"
+#include "idcache.h"
+
+/* Static prototypes */
+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);
+
+/*
+ SILC ID Cache object.
+
+ This is context for the ID cache system. This includes all the cache
+ entries and other internal data. This is read-only object and not
+ visible outside this cache system.
+
+ Fields are as follows:
+
+ SilcHashTable id_table
+
+ Hash table using the ID as the key.
+
+ SilcHashTable name_table
+
+ Hash table using the name as the key.
-/* qsort() sorter function. */
+ SilcHashTable context_table
-static int silc_idcache_sorter(const void *a, const void *b)
+ Hash table using the context as the key.
+
+ SilcIDCacheDestructor destructor
+
+ Destructor callback that is called when an cache entry expires or is
+ purged from the ID cache. The application must not free cache entry
+ 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 {
+ SilcHashTable id_table;
+ SilcHashTable name_table;
+ SilcHashTable context_table;
+ SilcIDCacheDestructor destructor;
+ SilcIdType type;
+};
+
+/*
+ ID Cache list.
+
+ This is returned when searching the cache. Enumeration functions are
+ provided to traverse the list; actually this is used as table not as
+ list. :)
+
+ By default the found cache entries are saved into the static cache
+ table to provide access without reallocation. However, if the static
+ table is full, rest of the cache entries are dynamically allocated
+ into `cache_dyn' table. Traversing functions automatically handles
+ these situations.
+
+*/
+struct SilcIDCacheListStruct {
+ SilcIDCacheEntry cache[64];
+ SilcIDCacheEntry *cache_dyn;
+ 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.
+ The `id_type' defines the types of the ID's that will be saved to the
+ cache. */
+
+SilcIDCache silc_idcache_alloc(uint32 count, SilcIdType id_type,
+ SilcIDCacheDestructor destructor)
{
- SilcIDCache *a1, *b1;
-
- a1 = (SilcIDCache *)a;
- b1 = (SilcIDCache *)b;
-
- return a1->data[0] - b1->data[0];
+ SilcIDCache cache;
+
+ SILC_LOG_DEBUG(("Allocating new cache"));
+
+ cache = silc_calloc(1, sizeof(*cache));
+ 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->name_table = silc_hash_table_alloc(count, silc_hash_string, NULL,
+ silc_hash_string_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;
}
-/* Sorts given cache by data */
+/* Free's ID cache object and cache entries */
-void silc_idcache_sort_by_data(SilcIDCache *cache, unsigned int count)
+void silc_idcache_free(SilcIDCache cache)
{
- qsort(cache, count, sizeof(*cache), silc_idcache_sorter);
+ if (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);
+ }
}
-/* Find ID Cache entry by data. The data maybe anything that must
- match exactly. */
+/* Add new entry to the cache. */
-int silc_idcache_find_by_data(SilcIDCache *cache, unsigned int cache_count,
- char *data, SilcIDCache **ret)
+bool silc_idcache_add(SilcIDCache cache, char *name, void *id,
+ void *context, int expire)
{
- int i;
+ SilcIDCacheEntry c;
+ uint32 curtime = time(NULL);
- if (cache == NULL)
- return FALSE;
+ SILC_LOG_DEBUG(("Adding cache entry"));
- if (data == NULL)
- return FALSE;
+ /* 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);
+ }
- for (i = 0; i < cache_count; i++)
- if (cache[i].data && !memcmp(cache[i].data, data, strlen(data))) {
- if (ret)
- *ret = &(cache[i]);
- return TRUE;
- }
+ return TRUE;
+}
+
+/* Destructor for the ID Cache entry */
- return FALSE;
+static void silc_idcache_destructor(void *key, void *context,
+ void *user_context)
+{
+ silc_free(context);
+}
+
+/* Delete cache entry from cache. */
+
+bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
+{
+ bool ret = FALSE;
+
+ SILC_LOG_DEBUG(("Deleting cache entry"));
+
+ 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);
+
+ return ret;
}
-/* Find ID Cache entry by ID. */
+/* Deletes ID cache entry by ID. */
-int silc_idcache_find_by_id(SilcIDCache *cache, unsigned int cache_count,
- void *id, SilcIdType type, SilcIDCache **ret)
+bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
{
- int i, id_len;
+ SilcIDCacheEntry c;
- if (cache == NULL)
+ if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
return FALSE;
- if (id == NULL)
+ return silc_idcache_del(cache, c);
+}
+
+/* Same as above but with specific hash and comparison functions. If the
+ functions are NULL then default values are used. */
+
+bool silc_idcache_del_by_id_ext(SilcIDCache cache, void *id,
+ SilcHashFunction hash,
+ void *hash_context,
+ SilcHashCompare compare,
+ void *compare_context)
+{
+ SilcIDCacheEntry c;
+ bool ret = FALSE;
+
+ SILC_LOG_DEBUG(("Deleting cache entry"));
+
+ if (!silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)&c,
+ hash, hash_context, compare,
+ compare_context))
return FALSE;
- id_len = silc_id_get_len(type);
+ 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);
- for (i = 0; i < cache_count; i++)
- if (cache[i].id && !memcmp(cache[i].id, id, id_len)) {
- if (ret)
- *ret = &(cache[i]);
- return TRUE;
- }
+ return ret;
+}
+
+/* Deletes ID cache entry by context. */
+
+bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
+{
+ SilcIDCacheEntry c;
+ bool ret = FALSE;
+
+ SILC_LOG_DEBUG(("Deleting cache entry"));
+
+ if (!silc_hash_table_find(cache->context_table, context, NULL, (void *)&c))
+ return FALSE;
+
+ 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);
- return FALSE;
+ return ret;
}
-/* Add new entry to the cache. Returns number of allocated cache
- entries in the cache. */
+/* Deletes all ID entries from cache. Free's memory as well. */
-int silc_idcache_add(SilcIDCache **cache, unsigned int cache_count,
- char *data, SilcIdType id_type, void *id,
- void *context)
+bool silc_idcache_del_all(SilcIDCache cache)
{
- SilcIDCache *c;
- int i;
- unsigned long curtime = time(NULL);
+ silc_hash_table_free(cache->id_table);
+ silc_hash_table_free(cache->name_table);
+ silc_hash_table_free(cache->context_table);
- SILC_LOG_DEBUG(("Adding cache entry"));
+ return TRUE;
+}
- c = *cache;
+/* Foreach callback fro silc_idcache_purge. */
- if (c == NULL) {
- c = silc_calloc(5, sizeof(*c));
- cache_count = 5;
- }
+static void silc_idcache_purge_foreach(void *key, void *context,
+ void *user_context)
+{
+ SilcIDCache cache = (SilcIDCache)user_context;
+ uint32 curtime = time(NULL);
+ SilcIDCacheEntry c = (SilcIDCacheEntry)context;
- /* See if it exists already */
- if (silc_idcache_find_by_id(c, cache_count, id, id_type, NULL) == TRUE)
- return cache_count;
-
- for (i = 0; i < cache_count; i++) {
- if (c[i].data == NULL) {
- c[i].data = data;
- c[i].type = id_type;
- c[i].id = id;
- c[i].expire = curtime + SILC_ID_CACHE_EXPIRE;
- c[i].context = context;
- break;
- }
- }
+ if (c->expire && c->expire < curtime) {
+ /* Call the destructor */
+ if (cache->destructor)
+ cache->destructor(cache, c);
- if (i == cache_count) {
- c = silc_realloc(c, sizeof(*c) * (cache_count + 5));
- for (i = cache_count; i < cache_count + 5; i++) {
- c[i].data = NULL;
- c[i].id = NULL;
- }
- c[cache_count].data = data;
- c[cache_count].type = id_type;
- c[cache_count].id = id;
- c[cache_count].expire = curtime + SILC_ID_CACHE_EXPIRE;
- c[cache_count].context = context;
- cache_count += 5;
+ /* Delete the entry */
+ silc_idcache_del(cache, c);
}
+}
- *cache = c;
+/* Purges the cache by removing expired cache entires. Note that this
+ may be very slow operation. */
- return cache_count;
+bool silc_idcache_purge(SilcIDCache cache)
+{
+ silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
+ return TRUE;
}
-/* Delete cache entry from cache. */
-/* XXX */
+/* Purges the specific entry by context. */
-int silc_idcache_del(SilcIDCache *cache, SilcIDCache *old)
+bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
{
+ SilcIDCacheEntry entry;
+
+ if (!silc_hash_table_find(cache->context_table, context, NULL,
+ (void *)&entry))
+ return FALSE;
+
+ /* Call the destructor */
+ if (cache->destructor)
+ cache->destructor(cache, entry);
+
+ return silc_idcache_del(cache, entry);
+}
+
+/* Callback that is called by the hash table routine when traversing
+ entrys in the hash table. */
+
+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);
+}
+
+/* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
+
+bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
+{
+ SilcIDCacheList list;
+
+ if (!ret)
+ return TRUE;
+
+ 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;
+ }
+
+ *ret = list;
return TRUE;
}
-/* XXX */
+/* Find ID Cache entry by ID. May return multiple entries. */
-int silc_idcache_del_by_data(SilcIDCache *cache, unsigned int cache_count,
- char *data)
+bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
+ SilcIDCacheList *ret)
{
+ SilcIDCacheList list;
+
+ list = silc_idcache_list_alloc();
+
+ if (!ret)
+ return TRUE;
+
+ silc_hash_table_find_foreach(cache->id_table, id,
+ silc_idcache_get_all_foreach, list);
+
+ if (silc_idcache_list_count(list) == 0) {
+ silc_idcache_list_free(list);
+ return FALSE;
+ }
+
+ *ret = list;
return TRUE;
}
-/* Deletes ID cache entry by ID. */
+/* 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. */
+
+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 silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
+ hash, hash_context, compare,
+ compare_context);
+}
+
+/* Find one specific ID entry. */
-int silc_idcache_del_by_id(SilcIDCache *cache, unsigned int cache_count,
- SilcIdType type, void *id)
+bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
+ SilcIDCacheEntry *ret)
{
- int i, id_len;
+ return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
+}
+
+/* Finds cache entry by context. */
+
+bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
+ SilcIDCacheEntry *ret)
+{
+ return silc_hash_table_find(cache->context_table, context, NULL,
+ (void *)ret);
+}
+
+/* Find ID Cache entry by name. Returns list of cache entries. */
+
+bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
+ SilcIDCacheList *ret)
+{
+ SilcIDCacheList list;
+
+ list = silc_idcache_list_alloc();
+
+ if (!ret)
+ return TRUE;
- if (cache == NULL)
+ silc_hash_table_find_foreach(cache->name_table, name,
+ silc_idcache_get_all_foreach, list);
+
+ if (silc_idcache_list_count(list) == 0) {
+ silc_idcache_list_free(list);
return FALSE;
+ }
+
+ *ret = list;
+
+ return TRUE;
+}
+
+/* Find ID Cache entry by name. Returns one cache entry. */
- if (id == NULL)
+bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
+ SilcIDCacheEntry *ret)
+{
+ if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
return FALSE;
- id_len = silc_id_get_len(type);
+ return TRUE;
+}
- for (i = 0; i < cache_count; i++)
- if (cache[i].id && !memcmp(cache[i].id, id, id_len)) {
- cache[i].id = NULL;
- cache[i].data = NULL;
- cache[i].type = 0;
- cache[i].context = NULL;
- return TRUE;
- }
+/* Allocates ID cache list. */
+
+static SilcIDCacheList silc_idcache_list_alloc()
+{
+ SilcIDCacheList list;
- return FALSE;
+ list = silc_calloc(1, sizeof(*list));
+
+ return list;
}
-/* Deletes all ID entries from cache. Free's memory as well. */
+/* Adds cache entry to the ID cache list. If needed reallocates memory
+ for the list. */
-int silc_idcache_del_all(SilcIDCache **cache, unsigned int cache_count)
+static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
{
- SilcIDCache *c = *cache;
int i;
- if (c == NULL)
- return FALSE;
+ /* Try to add to static cache */
+ if (!list->cache_dyn_count)
+ for (i = 0; i < sizeof(list->cache); i++) {
+ if (!list->cache[i]) {
+ list->cache[i] = cache;
+ list->cache_count++;
+ return;
+ }
+ }
- for (i = 0; i < cache_count; i++) {
- c[i].id = NULL;
- c[i].data = NULL;
- c[i].type = 0;
- c[i].expire = 0;
- c[i].context = NULL;
+ /* Static cache is full, allocate dynamic cache */
+ for (i = 0; i < list->cache_dyn_count; i++) {
+ if (!list->cache_dyn[i]) {
+ list->cache_dyn[i] = cache;
+ list->cache_count++;
+ break;
+ }
}
- silc_free(*cache);
- *cache = NULL;
+ if (i >= list->cache_dyn_count) {
+ int k;
- return TRUE;
+ i += 5;
+ list->cache_dyn = silc_realloc(list->cache_dyn,
+ sizeof(*list->cache) * (i));
+
+ /* NULL the reallocated area */
+ for (k = list->cache_dyn_count; k < i; k++)
+ list->cache_dyn[k] = NULL;
+
+ list->cache_dyn[list->cache_dyn_count] = cache;
+ list->cache_dyn_count = i;
+ list->cache_count++;
+ }
}
-/* Purges the cache by removing expired cache entires. This does not
- free any memory though. */
+/* Returns number of cache entries in the ID cache list. */
-int silc_idcache_purge(SilcIDCache *cache, unsigned int cache_count)
+int silc_idcache_list_count(SilcIDCacheList list)
{
- unsigned long curtime = time(NULL);
- int i;
+ return list->cache_count;
+}
- if (cache == NULL)
+/* Returns first entry from the ID cache list. */
+
+bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
+{
+ list->pos = 0;
+
+ if (!list->cache[list->pos])
return FALSE;
+
+ if (ret)
+ *ret = list->cache[list->pos];
- for (i = 0; i < cache_count; i++) {
- if (cache[i].data &&
- (cache[i].expire == 0 || cache[i].expire < curtime)) {
- cache[i].id = NULL;
- cache[i].data = NULL;
- cache[i].type = 0;
- cache[i].expire = 0;
- cache[i].context = NULL;
- }
+ return TRUE;
+}
+
+/* Returns next entry from the ID cache list. */
+
+bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
+{
+ int dyn = FALSE;
+ list->pos++;
+
+ if (list->pos >= sizeof(list->cache)) {
+ list->pos = 0;
+ dyn = TRUE;
}
+ if (dyn && list->pos >= list->cache_dyn_count)
+ return FALSE;
+
+ if (!dyn && !list->cache[list->pos])
+ return FALSE;
+
+ if (dyn && !list->cache_dyn[list->pos])
+ return FALSE;
+
+ if (ret) {
+ if (!dyn)
+ *ret = list->cache[list->pos];
+ else
+ *ret = list->cache_dyn[list->pos];
+ }
+
return TRUE;
}
+
+/* Free's ID cache list. User must free the list object returned by
+ any of the searching functions. */
+
+void silc_idcache_list_free(SilcIDCacheList list)
+{
+ if (list) {
+ if (list->cache_dyn)
+ silc_free(list->cache_dyn);
+ silc_free(list);
+ }
+}