5 Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
7 Copyright (C) 2000 Pekka Riikonen
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
23 * Revision 1.6 2000/07/26 07:03:20 priikone
24 * Use ID check as well in silc_idcache_add.
26 * Revision 1.5 2000/07/18 06:51:48 priikone
27 * Use length of data found from cache instead of length of searched
30 * Revision 1.4 2000/07/17 11:46:36 priikone
33 * Revision 1.3 2000/07/12 05:54:01 priikone
34 * Major rewrite of whole ID Cache system.
36 * Revision 1.2 2000/07/05 06:06:35 priikone
37 * Global cosmetic change.
39 * Revision 1.1.1.1 2000/06/27 11:36:55 priikone
40 * Imported from internal CVS/Added Log headers.
45 #include "silcincludes.h"
48 /* Static prototypes */
49 static int silc_idcache_sorter(const void *a, const void *b);
50 static SilcIDCacheList silc_idcache_list_alloc();
51 static void silc_idcache_list_add(SilcIDCacheList list,
52 SilcIDCacheEntry cache);
57 This is context for the ID cache system. This includes all the cache
58 entries and other internal data. This is read-only object and not
59 visible outside this cache system.
61 Fields are as follows:
63 SilcIDCacheEntry cache
65 Table of the cache entries allocated by silc_idcache_add function.
66 This table is reallocated when new entry is added into the cache.
68 unsigned int cache_count
70 Number of cache entries in the cache.
74 Boolean value to indicate whether the cache is sorted or not. If
75 cache is not sorted the fast access (described next) cannot be used.
76 Sorting can be done by calling sorting function or when adding new
81 Table to provide fast access into the cache by index. When searching
82 by data this table is used to get the index to the first occurence
83 of that data (or part of the data) in the cache. Purpose of this
84 is to provide faster access to the cache when searching by data.
85 This is updated by silc_idcache_add and sorting functions.
88 struct SilcIDCacheStruct {
89 SilcIDCacheEntry cache;
90 unsigned int cache_count;
98 This is returned when searching the cache. Enumeration functions are
99 provided to traverse the list; actually this is used as table not as
102 By default the found cache entries are saved into the static cache
103 table to provide access without reallocation. However, if the static
104 table is full, rest of the cache entries are dynamically allocated
105 into `cache_dyn' table. Traversing functions automatically handles
109 struct SilcIDCacheListStruct {
110 SilcIDCacheEntry cache[64];
111 SilcIDCacheEntry *cache_dyn;
112 unsigned int cache_dyn_count;
113 unsigned int cache_count;
117 /* Allocates new ID cache object. The initial amount of allocated entries
118 can be sent as argument. If `count' is 0 the system uses default values. */
120 SilcIDCache silc_idcache_alloc(unsigned int count)
124 SILC_LOG_DEBUG(("Allocating new cache"));
126 cache = silc_calloc(1, sizeof(*cache));
127 cache->cache = silc_calloc(count ? count : 5, sizeof(*cache->cache));
128 cache->cache_count = count ? count : 5;
129 memset(cache->fast_access, -1, sizeof(cache->fast_access));
134 /* Free's ID cache object and cache entries */
136 void silc_idcache_free(SilcIDCache cache)
139 silc_free(cache->cache);
144 /* qsort() sorter function. */
146 static int silc_idcache_sorter(const void *a, const void *b)
148 SilcIDCacheEntry a1, b1;
150 a1 = (SilcIDCacheEntry)a;
151 b1 = (SilcIDCacheEntry)b;
153 if (!a1->data && !b1->data)
162 return a1->data[0] - b1->data[0];
165 /* Sorts given cache by data. After sorting this updates the fast access
166 table that can be used to access the cache faster. */
168 void silc_idcache_sort_by_data(SilcIDCache cache)
172 qsort(cache->cache, cache->cache_count,
173 sizeof(*cache->cache), silc_idcache_sorter);
175 memset(cache->fast_access, -1, sizeof(cache->fast_access));
177 /* Update the fast access table (this of course takes its own time when
178 the cache is very large). */
179 for (i = 0; i < cache->cache_count; i++) {
180 if (cache->cache[i].data &&
181 cache->fast_access[(int)cache->cache[i].data[0]] == -1)
182 cache->fast_access[(int)cache->cache[i].data[0]] = i;
185 cache->sorted = TRUE;
188 /* Find ID Cache entry by data. The data maybe anything that must
189 match exactly. Returns list of cache entries. */
191 int silc_idcache_find_by_data(SilcIDCache cache, char *data,
192 SilcIDCacheList *ret)
195 SilcIDCacheList list;
197 if (!cache || !cache->cache || !data)
200 list = silc_idcache_list_alloc();
203 i = cache->fast_access[(int)data[0]];
207 for (i = i; i < cache->cache_count; i++) {
208 if (cache->sorted && cache->cache[i].data &&
209 cache->cache[i].data[0] != data[0])
212 if (cache->cache[i].data &&
213 !memcmp(cache->cache[i].data, data, strlen(cache->cache[i].data)))
214 silc_idcache_list_add(list, &(cache->cache[i]));
217 if (!silc_idcache_list_count(list))
223 silc_idcache_list_free(list);
228 /* Find ID Cache entry by data. The data maybe anything that must
229 match exactly. Returns one cache entry. */
231 int silc_idcache_find_by_data_one(SilcIDCache cache, char *data,
232 SilcIDCacheEntry *ret)
236 if (!cache || !cache->cache || !data)
240 i = cache->fast_access[(int)data[0]];
244 for (i = i; i < cache->cache_count; i++)
245 if (cache->cache[i].data &&
246 !memcmp(cache->cache[i].data, data, strlen(cache->cache[i].data))) {
248 *ret = &(cache->cache[i]);
255 /* Find ID Cache entry by data, loosely. The data don't have to be 100%
256 match. This ignores data case-sensitivity when searching with this
257 function. Returns list of cache entries. */
259 int silc_idcache_find_by_data_loose(SilcIDCache cache, char *data,
260 SilcIDCacheList *ret)
263 SilcIDCacheList list;
265 if (!cache || !cache->cache || !data)
268 list = silc_idcache_list_alloc();
270 c = tolower((int)data[0]);
273 i = cache->fast_access[c];
277 for (i = i; i < cache->cache_count; i++) {
278 if (cache->sorted && cache->cache[i].data &&
279 cache->cache[i].data[0] != (char)c)
282 if (cache->cache[i].data &&
283 !strcasecmp(cache->cache[i].data, data))
284 silc_idcache_list_add(list, &(cache->cache[i]));
288 c = toupper((int)data[0]);
289 i = cache->fast_access[c];
291 for (i = i; i < cache->cache_count; i++) {
292 if (cache->sorted && cache->cache[i].data &&
293 cache->cache[i].data[0] != (char)c)
296 if (cache->cache[i].data &&
297 !strcasecmp(cache->cache[i].data, data))
298 silc_idcache_list_add(list, &(cache->cache[i]));
302 if (!silc_idcache_list_count(list))
308 silc_idcache_list_free(list);
313 /* Find ID Cache entry by ID. Returns list of cache entries. If `id' is
314 SILC_ID_CACHE_ANY this returns all ID's of type `type'. */
316 int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
317 SilcIDCacheList *ret)
320 SilcIDCacheList list;
322 if (!cache || !cache->cache || !id)
325 id_len = silc_id_get_len(type);
327 list = silc_idcache_list_alloc();
329 if (id != SILC_ID_CACHE_ANY) {
330 for (i = 0; i < cache->cache_count; i++)
331 if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len))
332 silc_idcache_list_add(list, &(cache->cache[i]));
334 for (i = 0; i < cache->cache_count; i++)
335 if (cache->cache[i].id && cache->cache[i].type == type)
336 silc_idcache_list_add(list, &(cache->cache[i]));
339 if (!silc_idcache_list_count(list))
345 silc_idcache_list_free(list);
350 /* Find ID Cache entry by ID. Returns one cache entry. */
352 int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
353 SilcIDCacheEntry *ret)
357 if (!cache || !cache->cache || !id)
360 id_len = silc_id_get_len(type);
362 for (i = 0; i < cache->cache_count; i++)
363 if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
365 *ret = &(cache->cache[i]);
372 /* Finds cache entry by context. */
374 int silc_idcache_find_by_context(SilcIDCache cache, void *context,
375 SilcIDCacheEntry *ret)
379 if (!cache || !cache->cache || !context)
382 for (i = 0; i < cache->cache_count; i++)
383 if (cache->cache[i].context && cache->cache[i].context == context) {
385 *ret = &(cache->cache[i]);
392 /* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
393 then the cache is sorted after the new entry has been added. The
394 cache must be sorted in order for the fast access feature to work,
395 however, it is not mandatory. */
397 int silc_idcache_add(SilcIDCache cache, char *data, SilcIdType id_type,
398 void *id, void *context, int sort)
402 unsigned long curtime = time(NULL);
405 if (!cache || !cache->cache)
408 SILC_LOG_DEBUG(("Adding cache entry"));
411 count = cache->cache_count;
414 c = silc_calloc(5, sizeof(*c));
418 /* See if it exists already */
419 /* XXX this slows down this function. */
420 if (silc_idcache_find_by_id(cache, id, id_type, NULL))
423 for (i = 0; i < count; i++) {
424 if (c[i].data == NULL && c[i].id == NULL) {
428 c[i].expire = curtime + SILC_ID_CACHE_EXPIRE;
429 c[i].context = context;
435 c = silc_realloc(c, sizeof(*c) * (count + 5));
436 for (i = count; i < count + 5; i++) {
440 c[count].data = data;
441 c[count].type = id_type;
443 c[count].expire = curtime + SILC_ID_CACHE_EXPIRE;
444 c[count].context = context;
449 cache->cache_count = count;
450 cache->sorted = sort;
453 silc_idcache_sort_by_data(cache);
458 /* Delete cache entry from cache. */
461 int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
469 int silc_idcache_del_by_data(SilcIDCache cache, char *data)
475 /* Deletes ID cache entry by ID. */
477 int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
481 if (!cache || !cache->cache || !id)
484 id_len = silc_id_get_len(type);
486 for (i = 0; i < cache->cache_count; i++)
487 if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
488 cache->cache[i].id = NULL;
489 cache->cache[i].data = NULL;
490 cache->cache[i].type = 0;
491 cache->cache[i].context = NULL;
498 /* Deletes all ID entries from cache. Free's memory as well. */
500 int silc_idcache_del_all(SilcIDCache cache)
502 if (!cache || !cache->cache)
505 silc_free(cache->cache);
507 cache->cache_count = 0;
512 /* Purges the cache by removing expired cache entires. This does not
513 free any memory though. */
515 int silc_idcache_purge(SilcIDCache cache)
518 unsigned long curtime = time(NULL);
521 if (!cache || !cache->cache)
526 for (i = 0; i < cache->cache_count; i++) {
528 (c[i].expire == 0 || c[i].expire < curtime)) {
540 /* Allocates ID cache list. */
542 static SilcIDCacheList silc_idcache_list_alloc()
544 SilcIDCacheList list;
546 list = silc_calloc(1, sizeof(*list));
551 /* Adds cache entry to the ID cache list. If needed reallocates memory
554 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
558 /* Try to add to static cache */
559 if (!list->cache_dyn_count)
560 for (i = 0; i < sizeof(list->cache); i++) {
561 if (!list->cache[i]) {
562 list->cache[i] = cache;
568 /* Static cache is full, allocate dynamic cache */
569 for (i = 0; i < list->cache_dyn_count; i++) {
570 if (!list->cache_dyn[i]) {
571 list->cache_dyn[i] = cache;
577 if (i >= list->cache_dyn_count) {
581 list->cache_dyn = silc_realloc(list->cache_dyn,
582 sizeof(*list->cache) * (i));
584 /* NULL the reallocated area */
585 for (k = list->cache_dyn_count; k < i; k++)
586 list->cache_dyn[k] = NULL;
588 list->cache_dyn[list->cache_dyn_count] = cache;
589 list->cache_dyn_count = i;
594 /* Returns number of cache entries in the ID cache list. */
596 int silc_idcache_list_count(SilcIDCacheList list)
598 return list->cache_count;
601 /* Returns first entry from the ID cache list. */
603 int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
607 if (!list->cache[list->pos])
611 *ret = list->cache[list->pos];
616 /* Returns next entry from the ID cache list. */
618 int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
623 if (list->pos >= sizeof(list->cache)) {
628 if (dyn && list->pos >= list->cache_dyn_count)
631 if (!dyn && !list->cache[list->pos])
634 if (dyn && !list->cache_dyn[list->pos])
639 *ret = list->cache[list->pos];
641 *ret = list->cache_dyn[list->pos];
647 /* Free's ID cache list. User must free the list object returned by
648 any of the searching functions. */
650 void silc_idcache_list_free(SilcIDCacheList list)
654 silc_free(list->cache_dyn);