From 93d996a32e1f9bacb93c2c35f3e80921c6f44fa8 Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Wed, 12 Jul 2000 05:54:01 +0000 Subject: [PATCH] Major rewrite of whole ID Cache system. --- lib/silccore/idcache.c | 564 ++++++++++++++++++++++++++++++++++------- lib/silccore/idcache.h | 58 +++-- 2 files changed, 518 insertions(+), 104 deletions(-) diff --git a/lib/silccore/idcache.c b/lib/silccore/idcache.c index 0d3f4e9b..5f322004 100644 --- a/lib/silccore/idcache.c +++ b/lib/silccore/idcache.c @@ -17,10 +17,12 @@ GNU General Public License for more details. */ -/* XXX: This ID cache system sucks and must be rewritten! */ /* * $Id$ * $Log$ + * Revision 1.3 2000/07/12 05:54:01 priikone + * Major rewrite of whole ID Cache system. + * * Revision 1.2 2000/07/05 06:06:35 priikone * Global cosmetic change. * @@ -31,100 +33,378 @@ */ #include "silcincludes.h" +#include "idcache.h" + +/* Static prototypes */ +static int silc_idcache_sorter(const void *a, const void *b); +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: + + SilcIDCacheEntry cache + + Table of the cache entries allocated by silc_idcache_add function. + This table is reallocated when new entry is added into the cache. + + unsigned int cache_count + + Number of cache entries in the cache. + + int sorted + + 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. + +*/ +struct SilcIDCacheStruct { + SilcIDCacheEntry cache; + unsigned int cache_count; + int sorted; + int fast_access[256]; +}; + +/* + 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; + unsigned int cache_dyn_count; + unsigned int cache_count; + unsigned int 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. */ + +SilcIDCache silc_idcache_alloc(unsigned int count) +{ + 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)); + + return cache; +} + +/* Free's ID cache object and cache entries */ + +void silc_idcache_free(SilcIDCache cache) +{ + if (cache) { + silc_free(cache->cache); + silc_free(cache); + } +} /* qsort() sorter function. */ static int silc_idcache_sorter(const void *a, const void *b) { - SilcIDCache *a1, *b1; - - a1 = (SilcIDCache *)a; - b1 = (SilcIDCache *)b; + SilcIDCacheEntry a1, b1; + + a1 = (SilcIDCacheEntry)a; + b1 = (SilcIDCacheEntry)b; + if (!a1->data && !b1->data) + return 0; + + if (!a1->data) + return -1; + + if (!b1->data) + return 1; + return a1->data[0] - b1->data[0]; } -/* Sorts given cache by data */ +/* Sorts given cache by data. After sorting this updates the fast access + table that can be used to access the cache faster. */ -void silc_idcache_sort_by_data(SilcIDCache *cache, unsigned int count) +void silc_idcache_sort_by_data(SilcIDCache cache) { - qsort(cache, count, sizeof(*cache), silc_idcache_sorter); + 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; } /* Find ID Cache entry by data. The data maybe anything that must - match exactly. */ + match exactly. Returns list of cache entries. */ -int silc_idcache_find_by_data(SilcIDCache *cache, unsigned int cache_count, - char *data, SilcIDCache **ret) +int silc_idcache_find_by_data(SilcIDCache cache, char *data, + SilcIDCacheList *ret) { 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; + + for (i = i; i < cache->cache_count; i++) { + if (cache->sorted && cache->cache[i].data && + cache->cache[i].data[0] != data[0]) + break; + + if (cache->cache[i].data && + !memcmp(cache->cache[i].data, data, strlen(data))) + silc_idcache_list_add(list, &(cache->cache[i])); + } - if (cache == NULL) + if (!silc_idcache_list_count(list)) return FALSE; - if (data == NULL) + if (ret) + *ret = list; + else + silc_idcache_list_free(list); + + return TRUE; +} + +/* Find ID Cache entry by data. The data maybe anything that must + match exactly. Returns one cache entry. */ + +int silc_idcache_find_by_data_one(SilcIDCache cache, char *data, + SilcIDCacheEntry *ret) +{ + int i; + + if (!cache || !cache->cache || !data) return FALSE; - for (i = 0; i < cache_count; i++) - if (cache[i].data && !memcmp(cache[i].data, data, strlen(data))) { + if (cache->sorted) + i = cache->fast_access[(int)data[0]]; + else + i = 0; + + for (i = i; i < cache->cache_count; i++) + if (cache->cache[i].data && + !memcmp(cache->cache[i].data, data, strlen(data))) { if (ret) - *ret = &(cache[i]); + *ret = &(cache->cache[i]); return TRUE; } return FALSE; } -/* Find ID Cache entry by ID. */ +/* 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. */ + +int silc_idcache_find_by_data_loose(SilcIDCache cache, char *data, + SilcIDCacheList *ret) +{ + 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; + + 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)) + return FALSE; + + if (ret) + *ret = list; + else + silc_idcache_list_free(list); + + return TRUE; +} + +/* Find ID Cache entry by ID. Returns list of cache entries. */ +/* XXX this may be useless, need for list really? */ -int silc_idcache_find_by_id(SilcIDCache *cache, unsigned int cache_count, - void *id, SilcIdType type, SilcIDCache **ret) +int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type, + SilcIDCacheList *ret) { int i, id_len; + SilcIDCacheList list; - if (cache == NULL) + if (!cache || !cache->cache || !id) return FALSE; - if (id == NULL) + id_len = silc_id_get_len(type); + + list = silc_idcache_list_alloc(); + + 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])); + + if (!silc_idcache_list_count(list)) + return FALSE; + + if (ret) + *ret = list; + else + silc_idcache_list_free(list); + + return TRUE; +} + +/* Find ID Cache entry by ID. Returns one cache entry. */ + +int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type, + 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_count; i++) - if (cache[i].id && !memcmp(cache[i].id, id, id_len)) { + 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; + } + + return FALSE; +} + +/* Finds cache entry by context. */ + +int silc_idcache_find_by_context(SilcIDCache cache, void *context, + SilcIDCacheEntry *ret) +{ + 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[i]); + *ret = &(cache->cache[i]); return TRUE; } return FALSE; } -/* Add new entry to the cache. Returns number of allocated cache - entries in the cache. */ +/* 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. */ -int silc_idcache_add(SilcIDCache **cache, unsigned int cache_count, - char *data, SilcIdType id_type, void *id, - void *context) +int silc_idcache_add(SilcIDCache cache, char *data, SilcIdType id_type, + void *id, void *context, int sort) { - SilcIDCache *c; int i; + unsigned int count; unsigned long curtime = time(NULL); + SilcIDCacheEntry c; + + if (!cache || !cache->cache) + return FALSE; SILC_LOG_DEBUG(("Adding cache entry")); - c = *cache; + c = cache->cache; + count = cache->cache_count; if (c == NULL) { c = silc_calloc(5, sizeof(*c)); - cache_count = 5; + count = 5; } /* See if it exists already */ - if (silc_idcache_find_by_id(c, cache_count, id, id_type, NULL) == TRUE) - return cache_count; + /* XXX this slows down this function. */ + if (silc_idcache_find_by_id(cache, id, id_type, NULL)) + return FALSE; - for (i = 0; i < cache_count; i++) { + for (i = 0; i < count; i++) { if (c[i].data == NULL) { c[i].data = data; c[i].type = id_type; @@ -135,29 +415,34 @@ int silc_idcache_add(SilcIDCache **cache, unsigned int cache_count, } } - if (i == cache_count) { - c = silc_realloc(c, sizeof(*c) * (cache_count + 5)); - for (i = cache_count; i < cache_count + 5; i++) { + 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[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; + c[count].data = data; + c[count].type = id_type; + c[count].id = id; + c[count].expire = curtime + SILC_ID_CACHE_EXPIRE; + c[count].context = context; + count += 5; } - *cache = c; + cache->cache = c; + cache->cache_count = count; + cache->sorted = sort; - return cache_count; + if (sort) + silc_idcache_sort_by_data(cache); + + return TRUE; } /* Delete cache entry from cache. */ /* XXX */ -int silc_idcache_del(SilcIDCache *cache, SilcIDCache *old) +int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old) { return TRUE; @@ -165,8 +450,7 @@ int silc_idcache_del(SilcIDCache *cache, SilcIDCache *old) /* XXX */ -int silc_idcache_del_by_data(SilcIDCache *cache, unsigned int cache_count, - char *data) +int silc_idcache_del_by_data(SilcIDCache cache, char *data) { return TRUE; @@ -174,25 +458,21 @@ int silc_idcache_del_by_data(SilcIDCache *cache, unsigned int cache_count, /* Deletes ID cache entry by ID. */ -int silc_idcache_del_by_id(SilcIDCache *cache, unsigned int cache_count, - SilcIdType type, void *id) +int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id) { int i, id_len; - if (cache == NULL) - return FALSE; - - if (id == NULL) + if (!cache || !cache->cache || !id) return FALSE; id_len = silc_id_get_len(type); - 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; + 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; } @@ -201,24 +481,14 @@ int silc_idcache_del_by_id(SilcIDCache *cache, unsigned int cache_count, /* Deletes all ID entries from cache. Free's memory as well. */ -int silc_idcache_del_all(SilcIDCache **cache, unsigned int cache_count) +int silc_idcache_del_all(SilcIDCache cache) { - SilcIDCache *c = *cache; - int i; - - if (c == NULL) + if (!cache || !cache->cache) return FALSE; - 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; - } - - silc_free(*cache); - *cache = NULL; + silc_free(cache->cache); + cache->cache = NULL; + cache->cache_count = 0; return TRUE; } @@ -226,24 +496,146 @@ int silc_idcache_del_all(SilcIDCache **cache, unsigned int cache_count) /* Purges the cache by removing expired cache entires. This does not free any memory though. */ -int silc_idcache_purge(SilcIDCache *cache, unsigned int cache_count) +int silc_idcache_purge(SilcIDCache cache) { + SilcIDCacheEntry c; unsigned long curtime = time(NULL); int i; - if (cache == NULL) + if (!cache || !cache->cache) return FALSE; - 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; + c = cache->cache; + + for (i = 0; i < cache->cache_count; i++) { + if (c[i].data && + (c[i].expire == 0 || c[i].expire < curtime)) { + c[i].id = NULL; + c[i].data = NULL; + c[i].type = 0; + c[i].expire = 0; + c[i].context = NULL; } } return TRUE; } + +/* Allocates ID cache list. */ + +static SilcIDCacheList silc_idcache_list_alloc() +{ + SilcIDCacheList list; + + list = silc_calloc(1, sizeof(*list)); + + return list; +} + +/* Adds cache entry to the ID cache list. If needed reallocates memory + for the list. */ + +static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache) +{ + int i; + + /* 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; + } + } + + /* 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; + } + } + + if (i >= list->cache_dyn_count) { + int k; + + 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++; + } +} + +/* Returns number of cache entries in the ID cache list. */ + +int silc_idcache_list_count(SilcIDCacheList list) +{ + return list->cache_count; +} + +/* Returns first entry from the ID cache list. */ + +int 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]; + + return TRUE; +} + +/* Returns next entry from the ID cache list. */ + +int 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); + } +} diff --git a/lib/silccore/idcache.h b/lib/silccore/idcache.h index 074dc48e..87030db0 100644 --- a/lib/silccore/idcache.h +++ b/lib/silccore/idcache.h @@ -4,7 +4,7 @@ Author: Pekka Riikonen - Copyright (C) 1997 - 2000 Pekka Riikonen + Copyright (C) 2000 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 @@ -22,7 +22,12 @@ #define IDCACHE_H /* - SilcIDCache structure. + Silc ID Cache Entry object. + + 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. char *data @@ -55,25 +60,42 @@ typedef struct { void *id; unsigned long expire; void *context; -} SilcIDCache; +} *SilcIDCacheEntry; + +/* Forward declaration for SILC ID Cache object. */ +typedef struct SilcIDCacheStruct *SilcIDCache; + +/* Forward declaration for ID Cache List */ +typedef struct SilcIDCacheListStruct *SilcIDCacheList; #define SILC_ID_CACHE_EXPIRE 3600 /* Prototypes */ -void silc_idcache_sort_by_data(SilcIDCache *cache, unsigned int count); -int silc_idcache_find_by_data(SilcIDCache *cache, unsigned int cache_count, - char *data, SilcIDCache **ret); -int silc_idcache_find_by_id(SilcIDCache *cache, unsigned int cache_count, - void *id, SilcIdType type, SilcIDCache **ret); -int silc_idcache_add(SilcIDCache **cache, unsigned int cache_count, - char *data, SilcIdType id_type, void *id, - void *context); -int silc_idcache_del(SilcIDCache *cache, SilcIDCache *old); -int silc_idcache_del_by_data(SilcIDCache *cache, unsigned int cache_count, - char *data); -int silc_idcache_del_by_id(SilcIDCache *cache, unsigned int cache_count, - SilcIdType type, void *id); -int silc_idcache_del_all(SilcIDCache **cache, unsigned int cache_count); -int silc_idcache_purge(SilcIDCache *cache, unsigned int cache_count); +SilcIDCache silc_idcache_alloc(unsigned int count); +void silc_idcache_free(SilcIDCache cache); +void silc_idcache_sort_by_data(SilcIDCache cache); +int silc_idcache_find_by_data(SilcIDCache cache, char *data, + SilcIDCacheList *ret); +int silc_idcache_find_by_data_one(SilcIDCache cache, char *data, + SilcIDCacheEntry *ret); +int silc_idcache_find_by_data_loose(SilcIDCache cache, 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, char *data, SilcIdType id_type, + void *id, void *context, int sort); +int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old); +int silc_idcache_del_by_data(SilcIDCache cache, 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_list_count(SilcIDCacheList list); +int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret); +int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret); +void silc_idcache_list_free(SilcIDCacheList list); #endif -- 2.24.0