lib/silccore/idcache.c

   1 /*
   2
   3   idcache.c
   4
   5   Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
   6
   7   Copyright (C) 2000 - 2001 Pekka Riikonen
   8
   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.
  13
  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.
  18
  19 */
  20 /* $Id$ */
  21
  22 #include "silcincludes.h"
  23 #include "idcache.h"
  24
  25 /* Static prototypes */
  26 static void silc_idcache_destructor(void *key, void *context,
  27                                     void *user_context);
  28 static SilcIDCacheList silc_idcache_list_alloc();
  29 static void silc_idcache_list_add(SilcIDCacheList list,
  30                                   SilcIDCacheEntry cache);
  31
  32 /*
  33    SILC ID Cache object.
  34
  35    This is context for the ID cache system. This includes all the cache
  36    entries and other internal data. This is read-only object and not
  37    visible outside this cache system.
  38
  39    Fields are as follows:
  40
  41    SilcHashTable id_table
  42
  43        Hash table using the ID as the key.
  44
  45    SilcHashTable data_table
  46
  47        Hash table using the data as the key.
  48
  49    SilcHashTable context_table
  50
  51        Hash table using the context as the key.
  52
  53    SilcIDCacheDestructor destructor
  54
  55        Destructor callback that is called when an cache entry expires or is
  56        purged from the ID cache. The application must not free cache entry
  57        because the library will do it automatically. The appliation, however,
  58        is responsible of freeing any data in the entry.
  59
  60    SilcIdType id_type
  61
  62        Indicates the type of the ID's this cache holds.
  63
  64 */
  65 struct SilcIDCacheStruct {
  66   SilcHashTable id_table;
  67   SilcHashTable data_table;
  68   SilcHashTable context_table;
  69   SilcIDCacheDestructor destructor;
  70   SilcIdType type;
  71 };
  72
  73 /*
  74    ID Cache list.
  75
  76    This is returned when searching the cache. Enumeration functions are
  77    provided to traverse the list; actually this is used as table not as
  78    list. :)
  79
  80    By default the found cache entries are saved into the static cache
  81    table to provide access without reallocation. However, if the static
  82    table is full, rest of the cache entries are dynamically allocated
  83    into `cache_dyn' table. Traversing functions automatically handles
  84    these situations.
  85
  86 */
  87 struct SilcIDCacheListStruct {
  88   SilcIDCacheEntry cache[64];
  89   SilcIDCacheEntry *cache_dyn;
  90   uint32 cache_dyn_count;
  91   uint32 cache_count;
  92   uint32 pos;
  93 };
  94
  95 /* Allocates new ID cache object. The initial amount of allocated entries
  96    can be sent as argument. If `count' is 0 the system uses default values.
  97    The `id_type' defines the types of the ID's that will be saved to the
  98    cache. */
  99
 100 SilcIDCache silc_idcache_alloc(uint32 count, SilcIdType id_type,
 101                                SilcIDCacheDestructor destructor)
 102 {
 103   SilcIDCache cache;
 104
 105   SILC_LOG_DEBUG(("Allocating new cache"));
 106
 107   cache = silc_calloc(1, sizeof(*cache));
 108   cache->id_table = silc_hash_table_alloc(count, silc_hash_id,
 109                                           (void *)(uint32)id_type,
 110                                           silc_hash_id_compare,
 111                                           (void *)(uint32)id_type,
 112                                           silc_idcache_destructor, NULL);
 113   cache->data_table = silc_hash_table_alloc(count, silc_hash_data, NULL,
 114                                             silc_hash_data_compare, NULL,
 115                                             NULL, NULL);
 116   cache->context_table = silc_hash_table_alloc(count, silc_hash_ptr, NULL,
 117                                                NULL, NULL, NULL, NULL);
 118   cache->destructor = destructor;
 119   cache->type = id_type;
 120
 121   return cache;
 122 }
 123
 124 /* Free's ID cache object and cache entries */
 125
 126 void silc_idcache_free(SilcIDCache cache)
 127 {
 128   if (cache) {
 129     silc_hash_table_free(cache->id_table);
 130     silc_hash_table_free(cache->data_table);
 131     silc_hash_table_free(cache->context_table);
 132     silc_free(cache);
 133   }
 134 }
 135
 136 /* Add new entry to the cache. */
 137
 138 bool silc_idcache_add(SilcIDCache cache, unsigned char *data,
 139                       uint32 data_len, void *id, void *context, int expire)
 140 {
 141   SilcIDCacheEntry c;
 142   uint32 curtime = time(NULL);
 143
 144   SILC_LOG_DEBUG(("Adding cache entry"));
 145
 146   /* See if entry with this ID already exists. */
 147   if (silc_hash_table_find(cache->id_table, id, NULL, NULL))
 148     return FALSE;
 149
 150   /* Allocate new cache entry */
 151   c = silc_calloc(1, sizeof(*c));
 152   c->data = data;
 153   c->data_len = data_len;
 154   c->id = id;
 155   c->expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 156   c->context = context;
 157
 158   /* Add the new entry to the hash tables */
 159
 160   silc_hash_table_add(cache->id_table, id, c);
 161   if (data)
 162     silc_hash_table_add_ext(cache->data_table, data, c,
 163                             silc_hash_data, (void *)data_len);
 164   if (context)
 165     silc_hash_table_add(cache->context_table, context, c);
 166
 167   /* See whether we have time to rehash the tables */
 168   if ((silc_hash_table_count(cache->id_table) * 2) >
 169       silc_hash_table_size(cache->id_table)) {
 170     silc_hash_table_rehash(cache->id_table, 0);
 171     silc_hash_table_rehash(cache->data_table, 0);
 172     silc_hash_table_rehash(cache->context_table, 0);
 173   }
 174
 175   return TRUE;
 176 }
 177
 178 /* Destructor for the ID Cache entry */
 179
 180 static void silc_idcache_destructor(void *key, void *context,
 181                                     void *user_context)
 182 {
 183   silc_free(context);
 184 }
 185
 186 /* Delete cache entry from cache. */
 187
 188 bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 189 {
 190   bool ret;
 191
 192   ret = silc_hash_table_del_by_context(cache->data_table, old->data,
 193                                        old->context);
 194   ret = silc_hash_table_del(cache->context_table, old->context);
 195   ret = silc_hash_table_del(cache->id_table, old->id);
 196
 197   return ret;
 198 }
 199
 200 /* Deletes ID cache entry by ID. */
 201
 202 bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
 203 {
 204   bool ret;
 205   SilcIDCacheEntry c;
 206
 207   if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
 208     return FALSE;
 209
 210   ret = silc_hash_table_del_by_context(cache->data_table, c->data,
 211                                        c->context);
 212   ret = silc_hash_table_del(cache->context_table, c->context);
 213   ret = silc_hash_table_del(cache->id_table, c->id);
 214
 215   return ret;
 216 }
 217
 218 /* Deletes all ID entries from cache. Free's memory as well. */
 219
 220 bool silc_idcache_del_all(SilcIDCache cache)
 221 {
 222   silc_hash_table_free(cache->id_table);
 223   silc_hash_table_free(cache->data_table);
 224   silc_hash_table_free(cache->context_table);
 225   return TRUE;
 226 }
 227
 228 /* Foreach callback fro silc_idcache_purge. */
 229
 230 static void silc_idcache_purge_foreach(void *key, void *context,
 231                                        void *user_context)
 232 {
 233   SilcIDCache cache = (SilcIDCache)user_context;
 234   uint32 curtime = time(NULL);
 235   SilcIDCacheEntry c = (SilcIDCacheEntry)context;
 236
 237   if (c->expire && c->expire < curtime) {
 238     /* Call the destructor */
 239     if (cache->destructor)
 240       cache->destructor(cache, c);
 241
 242     /* Delete the entry */
 243     silc_idcache_del(cache, c);
 244   }
 245 }
 246
 247 /* Purges the cache by removing expired cache entires. Note that this
 248    may be very slow operation. */
 249
 250 bool silc_idcache_purge(SilcIDCache cache)
 251 {
 252   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 253   return TRUE;
 254 }
 255
 256 /* Purges the specific entry by context. */
 257
 258 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 259 {
 260   SilcIDCacheEntry entry;
 261
 262   if (!silc_hash_table_find(cache->context_table, context, NULL,
 263                             (void *)&entry))
 264     return FALSE;
 265
 266   /* Call the destructor */
 267   if (cache->destructor)
 268     cache->destructor(cache, entry);
 269
 270   return silc_idcache_del(cache, entry);
 271 }
 272
 273 /* Callback that is called by the hash table routine when traversing
 274    all entrys in the hash table. */
 275
 276 static void silc_idcache_get_all_foreach(void *key, void *context,
 277                                          void *user_context)
 278 {
 279   SilcIDCacheList list = (SilcIDCacheList)user_context;
 280   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 281 }
 282
 283 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 284
 285 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 286 {
 287   SilcIDCacheList list;
 288
 289   if (!ret)
 290     return TRUE;
 291
 292   list = silc_idcache_list_alloc();
 293   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 294
 295   if (silc_idcache_list_count(list) == 0) {
 296     silc_idcache_list_free(list);
 297     return FALSE;
 298   }
 299
 300   *ret = list;
 301
 302   return TRUE;
 303 }
 304
 305 /* Find ID Cache entry by ID. */
 306
 307 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 308                              SilcIDCacheEntry *ret)
 309 {
 310   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 311 }
 312
 313 /* Finds cache entry by context. */
 314
 315 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 316                                   SilcIDCacheEntry *ret)
 317 {
 318   return silc_hash_table_find(cache->context_table, context, NULL,
 319                               (void *)ret);
 320 }
 321
 322 /* Find ID Cache entry by data. The data maybe anything that must
 323    match exactly. Returns list of cache entries. */
 324
 325 bool silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
 326                                unsigned int data_len, SilcIDCacheList *ret)
 327 {
 328   SilcIDCacheList list;
 329   void **contexts;
 330   unsigned int count;
 331   int i;
 332
 333   if (!silc_hash_table_find_all_ext(cache->data_table, data, NULL, &contexts,
 334                                     &count, silc_hash_data, (void *)data_len,
 335                                     silc_hash_data_compare, (void *)data_len))
 336     return FALSE;
 337
 338   if (!ret) {
 339     silc_free(contexts);
 340     return TRUE;
 341   }
 342
 343   list = silc_idcache_list_alloc();
 344
 345   for (i = 0; i < count; i++)
 346     silc_idcache_list_add(list, (SilcIDCacheEntry)contexts[i]);
 347   silc_free(contexts);
 348
 349   *ret = list;
 350
 351   return TRUE;
 352 }
 353
 354 /* Find ID Cache entry by data. The data maybe anything that must
 355    match exactly. Returns one cache entry. */
 356
 357 bool silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
 358                                    unsigned int data_len,
 359                                    SilcIDCacheEntry *ret)
 360 {
 361   SilcIDCacheEntry c;
 362
 363   if (!silc_hash_table_find_ext(cache->data_table, data, NULL, (void *)&c,
 364                                 silc_hash_data, (void *)data_len,
 365                                 silc_hash_data_compare, (void *)data_len))
 366     return FALSE;
 367
 368   if (ret)
 369     *ret = c;
 370
 371   return TRUE;
 372 }
 373
 374 /* Allocates ID cache list. */
 375
 376 static SilcIDCacheList silc_idcache_list_alloc()
 377 {
 378   SilcIDCacheList list;
 379
 380   list = silc_calloc(1, sizeof(*list));
 381
 382   return list;
 383 }
 384
 385 /* Adds cache entry to the ID cache list. If needed reallocates memory
 386    for the list. */
 387
 388 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 389 {
 390   int i;
 391
 392   /* Try to add to static cache */
 393   if (!list->cache_dyn_count)
 394     for (i = 0; i < sizeof(list->cache); i++) {
 395       if (!list->cache[i]) {
 396         list->cache[i] = cache;
 397         list->cache_count++;
 398         return;
 399       }
 400     }
 401
 402   /* Static cache is full, allocate dynamic cache */
 403   for (i = 0; i < list->cache_dyn_count; i++) {
 404     if (!list->cache_dyn[i]) {
 405       list->cache_dyn[i] = cache;
 406       list->cache_count++;
 407       break;
 408     }
 409   }
 410
 411   if (i >= list->cache_dyn_count) {
 412     int k;
 413
 414     i += 5;
 415     list->cache_dyn = silc_realloc(list->cache_dyn,
 416                                    sizeof(*list->cache) * (i));
 417
 418     /* NULL the reallocated area */
 419     for (k = list->cache_dyn_count; k < i; k++)
 420       list->cache_dyn[k] = NULL;
 421
 422     list->cache_dyn[list->cache_dyn_count] = cache;
 423     list->cache_dyn_count = i;
 424     list->cache_count++;
 425   }
 426 }
 427
 428 /* Returns number of cache entries in the ID cache list. */
 429
 430 int silc_idcache_list_count(SilcIDCacheList list)
 431 {
 432   return list->cache_count;
 433 }
 434
 435 /* Returns first entry from the ID cache list. */
 436
 437 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 438 {
 439   list->pos = 0;
 440
 441   if (!list->cache[list->pos])
 442     return FALSE;
 443
 444   if (ret)
 445     *ret = list->cache[list->pos];
 446
 447   return TRUE;
 448 }
 449
 450 /* Returns next entry from the ID cache list. */
 451
 452 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 453 {
 454   int dyn = FALSE;
 455   list->pos++;
 456
 457   if (list->pos >= sizeof(list->cache)) {
 458     list->pos = 0;
 459     dyn = TRUE;
 460   }
 461
 462   if (dyn && list->pos >= list->cache_dyn_count)
 463     return FALSE;
 464
 465   if (!dyn && !list->cache[list->pos])
 466     return FALSE;
 467
 468   if (dyn && !list->cache_dyn[list->pos])
 469     return FALSE;
 470
 471   if (ret) {
 472     if (!dyn)
 473       *ret = list->cache[list->pos];
 474     else
 475       *ret = list->cache_dyn[list->pos];
 476   }
 477
 478   return TRUE;
 479 }
 480
 481 /* Free's ID cache list. User must free the list object returned by
 482    any of the searching functions. */
 483
 484 void silc_idcache_list_free(SilcIDCacheList list)
 485 {
 486   if (list) {
 487     if (list->cache_dyn)
 488       silc_free(list->cache_dyn);
 489     silc_free(list);
 490   }
 491 }