lib/silccore/silcidcache.c

   1 /*
   2
   3   silcidcache.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 "silcidcache.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 name_table
  46
  47        Hash table using the name 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 name_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   bool dyn;
  94 };
  95
  96 /* Allocates new ID cache object. The initial amount of allocated entries
  97    can be sent as argument. If `count' is 0 the system uses default values.
  98    The `id_type' defines the types of the ID's that will be saved to the
  99    cache. */
 100
 101 SilcIDCache silc_idcache_alloc(uint32 count, SilcIdType id_type,
 102                                SilcIDCacheDestructor destructor)
 103 {
 104   SilcIDCache cache;
 105
 106   SILC_LOG_DEBUG(("Allocating new cache"));
 107
 108   cache = silc_calloc(1, sizeof(*cache));
 109   cache->id_table = silc_hash_table_alloc(count, silc_hash_id,
 110                                           (void *)(uint32)id_type,
 111                                           silc_hash_id_compare,
 112                                           (void *)(uint32)id_type,
 113                                           silc_idcache_destructor, NULL,
 114                                           FALSE);
 115   cache->name_table = silc_hash_table_alloc(count, silc_hash_string, NULL,
 116                                             silc_hash_string_compare, NULL,
 117                                             NULL, NULL, FALSE);
 118   cache->context_table = silc_hash_table_alloc(count, silc_hash_ptr, NULL,
 119                                                NULL, NULL, NULL, NULL, FALSE);
 120   cache->destructor = destructor;
 121   cache->type = id_type;
 122
 123   return cache;
 124 }
 125
 126 /* Frees ID cache object and cache entries */
 127
 128 void silc_idcache_free(SilcIDCache cache)
 129 {
 130   if (cache) {
 131     silc_hash_table_free(cache->id_table);
 132     silc_hash_table_free(cache->name_table);
 133     silc_hash_table_free(cache->context_table);
 134     silc_free(cache);
 135   }
 136 }
 137
 138 /* Add new entry to the cache. Returns TRUE if the entry was added and
 139    FALSE if it could not be added. The `name' is the name associated with
 140    the ID, the `id' the actual ID and the `context' a used specific context.
 141    If the `expire' is TRUE the entry expires in default time and if FALSE
 142    the entry never expires from the cache. */
 143
 144 bool silc_idcache_add(SilcIDCache cache, char *name, void *id,
 145                       void *context, int expire)
 146 {
 147   SilcIDCacheEntry c;
 148   uint32 curtime = time(NULL);
 149
 150   SILC_LOG_DEBUG(("Adding cache entry"));
 151
 152   /* Allocate new cache entry */
 153   c = silc_calloc(1, sizeof(*c));
 154   c->id = id;
 155   c->name = name;
 156   c->expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 157   c->context = context;
 158
 159   /* Add the new entry to the hash tables */
 160
 161   if (id)
 162     silc_hash_table_add(cache->id_table, id, c);
 163   if (name)
 164     silc_hash_table_add(cache->name_table, name, c);
 165   if (context)
 166     silc_hash_table_add(cache->context_table, context, c);
 167
 168   /* See whether we have time to rehash the tables */
 169   if ((silc_hash_table_count(cache->id_table) / 2) >
 170       silc_hash_table_size(cache->id_table)) {
 171     silc_hash_table_rehash(cache->id_table, 0);
 172     silc_hash_table_rehash(cache->name_table, 0);
 173     silc_hash_table_rehash(cache->context_table, 0);
 174   }
 175
 176   return TRUE;
 177 }
 178
 179 /* Destructor for the ID Cache entry */
 180
 181 static void silc_idcache_destructor(void *key, void *context,
 182                                     void *user_context)
 183 {
 184   silc_free(context);
 185 }
 186
 187 /* Delete cache entry from cache. */
 188
 189 bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 190 {
 191   bool ret = FALSE;
 192
 193   SILC_LOG_DEBUG(("Deleting cache entry"));
 194
 195   if (old->name)
 196     ret = silc_hash_table_del_by_context(cache->name_table, old->name, old);
 197   if (old->context)
 198     ret = silc_hash_table_del(cache->context_table, old->context);
 199   if (old->id)
 200     ret = silc_hash_table_del(cache->id_table, old->id);
 201
 202   return ret;
 203 }
 204
 205 /* Deletes ID cache entry by ID. */
 206
 207 bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
 208 {
 209   SilcIDCacheEntry c;
 210
 211   if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
 212     return FALSE;
 213
 214   return silc_idcache_del(cache, c);
 215 }
 216
 217 /* Same as above but with specific hash and comparison functions. If the
 218    functions are NULL then default values are used. */
 219
 220 bool silc_idcache_del_by_id_ext(SilcIDCache cache, void *id,
 221                                 SilcHashFunction hash,
 222                                 void *hash_context,
 223                                 SilcHashCompare compare,
 224                                 void *compare_context)
 225 {
 226   SilcIDCacheEntry c;
 227   bool ret = FALSE;
 228
 229   SILC_LOG_DEBUG(("Deleting cache entry"));
 230
 231   if (!silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)&c,
 232                                 hash, hash_context, compare,
 233                                 compare_context))
 234     return FALSE;
 235
 236   if (c->name)
 237     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 238   if (c->context)
 239     ret = silc_hash_table_del(cache->context_table, c->context);
 240   if (c->id)
 241     ret = silc_hash_table_del_ext(cache->id_table, c->id, hash,
 242                                   hash_context, compare, compare_context,
 243                                   NULL, NULL);
 244
 245   return ret;
 246 }
 247
 248 /* Deletes ID cache entry by context. */
 249
 250 bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
 251 {
 252   SilcIDCacheEntry c;
 253   bool ret = FALSE;
 254
 255   SILC_LOG_DEBUG(("Deleting cache entry"));
 256
 257   if (!silc_hash_table_find(cache->context_table, context, NULL, (void *)&c))
 258     return FALSE;
 259
 260   if (c->name)
 261     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 262   if (c->context)
 263     ret = silc_hash_table_del(cache->context_table, c->context);
 264   if (c->id)
 265     ret = silc_hash_table_del_by_context(cache->id_table, c->id, c);
 266
 267   return ret;
 268 }
 269
 270 /* Deletes all ID entries from cache. Free's memory as well. */
 271
 272 bool silc_idcache_del_all(SilcIDCache cache)
 273 {
 274   silc_hash_table_free(cache->id_table);
 275   silc_hash_table_free(cache->name_table);
 276   silc_hash_table_free(cache->context_table);
 277
 278   return TRUE;
 279 }
 280
 281 static void silc_idcache_destructor_dummy(void *key, void *context,
 282                                           void *user_context)
 283 {
 284   /* Dummy - nothing */
 285 }
 286
 287 /* Foreach callback fro silc_idcache_purge. */
 288
 289 static void silc_idcache_purge_foreach(void *key, void *context,
 290                                        void *user_context)
 291 {
 292   SilcIDCache cache = (SilcIDCache)user_context;
 293   uint32 curtime = time(NULL);
 294   SilcIDCacheEntry c = (SilcIDCacheEntry)context;
 295
 296   if (c->expire && c->expire < curtime) {
 297     /* Remove the entry from the hash tables */
 298     if (c->name)
 299       silc_hash_table_del_by_context(cache->name_table, c->name, c);
 300     if (c->context)
 301       silc_hash_table_del(cache->context_table, c->context);
 302     if (c->id)
 303       silc_hash_table_del_by_context_ext(cache->id_table, c->id, c,
 304                                          NULL, NULL, NULL, NULL,
 305                                          silc_idcache_destructor_dummy, NULL);
 306
 307     /* Call the destructor */
 308     if (cache->destructor)
 309       cache->destructor(cache, c);
 310
 311     /* Free the entry, it has been deleted from the hash tables */
 312     silc_free(c);
 313   }
 314 }
 315
 316 /* Purges the cache by removing expired cache entires. Note that this
 317    may be very slow operation. */
 318
 319 bool silc_idcache_purge(SilcIDCache cache)
 320 {
 321   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 322   return TRUE;
 323 }
 324
 325 /* Purges the specific entry by context. */
 326
 327 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 328 {
 329   SilcIDCacheEntry c;
 330   bool ret = FALSE;
 331
 332   if (!silc_hash_table_find(cache->context_table, context, NULL,
 333                             (void *)&c))
 334     return FALSE;
 335
 336     /* Remove the entry from the hash tables */
 337   if (c->name)
 338     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 339   if (c->context)
 340     ret = silc_hash_table_del(cache->context_table, c->context);
 341   if (c->id)
 342     ret =
 343       silc_hash_table_del_by_context_ext(cache->id_table, c->id, c,
 344                                          NULL, NULL, NULL, NULL,
 345                                          silc_idcache_destructor_dummy, NULL);
 346
 347   /* Call the destructor */
 348   if (cache->destructor)
 349     cache->destructor(cache, c);
 350
 351   /* Free the entry, it has been deleted from the hash tables */
 352   silc_free(c);
 353
 354   return ret;
 355 }
 356
 357 /* Callback that is called by the hash table routine when traversing
 358    entrys in the hash table. */
 359
 360 static void silc_idcache_get_all_foreach(void *key, void *context,
 361                                          void *user_context)
 362 {
 363   SilcIDCacheList list = (SilcIDCacheList)user_context;
 364   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 365 }
 366
 367 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 368
 369 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 370 {
 371   SilcIDCacheList list;
 372
 373   if (!ret)
 374     return TRUE;
 375
 376   list = silc_idcache_list_alloc();
 377   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 378
 379   if (silc_idcache_list_count(list) == 0) {
 380     silc_idcache_list_free(list);
 381     return FALSE;
 382   }
 383
 384   *ret = list;
 385
 386   return TRUE;
 387 }
 388
 389 /* Find ID Cache entry by ID. May return multiple entries. */
 390
 391 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 392                              SilcIDCacheList *ret)
 393 {
 394   SilcIDCacheList list;
 395
 396   list = silc_idcache_list_alloc();
 397
 398   if (!ret)
 399     return TRUE;
 400
 401   silc_hash_table_find_foreach(cache->id_table, id,
 402                                silc_idcache_get_all_foreach, list);
 403
 404   if (silc_idcache_list_count(list) == 0) {
 405     silc_idcache_list_free(list);
 406     return FALSE;
 407   }
 408
 409   *ret = list;
 410
 411   return TRUE;
 412 }
 413
 414 /* Find specific ID with specific hash function and comparison functions.
 415    If `hash' is NULL then the default hash funtion is used and if `compare'
 416    is NULL default comparison function is used. */
 417
 418 bool silc_idcache_find_by_id_one_ext(SilcIDCache cache, void *id,
 419                                      SilcHashFunction hash,
 420                                      void *hash_context,
 421                                      SilcHashCompare compare,
 422                                      void *compare_context,
 423                                      SilcIDCacheEntry *ret)
 424 {
 425   return silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
 426                                   hash, hash_context, compare,
 427                                   compare_context);
 428 }
 429
 430 /* Find one specific ID entry. */
 431
 432 bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
 433                                  SilcIDCacheEntry *ret)
 434 {
 435   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 436 }
 437
 438 /* Finds cache entry by context. */
 439
 440 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 441                                   SilcIDCacheEntry *ret)
 442 {
 443   return silc_hash_table_find(cache->context_table, context, NULL,
 444                               (void *)ret);
 445 }
 446
 447 /* Find ID Cache entry by name. Returns list of cache entries. */
 448
 449 bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
 450                                SilcIDCacheList *ret)
 451 {
 452   SilcIDCacheList list;
 453
 454   list = silc_idcache_list_alloc();
 455
 456   if (!ret)
 457     return TRUE;
 458
 459   silc_hash_table_find_foreach(cache->name_table, name,
 460                                silc_idcache_get_all_foreach, list);
 461
 462   if (silc_idcache_list_count(list) == 0) {
 463     silc_idcache_list_free(list);
 464     return FALSE;
 465   }
 466
 467   *ret = list;
 468
 469   return TRUE;
 470 }
 471
 472 /* Find ID Cache entry by name. Returns one cache entry. */
 473
 474 bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
 475                                    SilcIDCacheEntry *ret)
 476 {
 477   if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
 478     return FALSE;
 479
 480   return TRUE;
 481 }
 482
 483 /* Allocates ID cache list. */
 484
 485 static SilcIDCacheList silc_idcache_list_alloc()
 486 {
 487   SilcIDCacheList list;
 488
 489   list = silc_calloc(1, sizeof(*list));
 490
 491   return list;
 492 }
 493
 494 /* Adds cache entry to the ID cache list. If needed reallocates memory
 495    for the list. */
 496
 497 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 498 {
 499   int i;
 500
 501   /* Try to add to static cache */
 502   if (!list->cache_dyn_count)
 503     for (i = 0; i < (sizeof(list->cache) / sizeof(list->cache[0])); i++) {
 504       if (!list->cache[i]) {
 505         list->cache[i] = cache;
 506         list->cache_count++;
 507         return;
 508       }
 509     }
 510
 511   /* Static cache is full, allocate dynamic cache */
 512   for (i = 0; i < list->cache_dyn_count; i++) {
 513     if (!list->cache_dyn[i]) {
 514       list->cache_dyn[i] = cache;
 515       list->cache_count++;
 516       break;
 517     }
 518   }
 519
 520   if (i >= list->cache_dyn_count) {
 521     int k;
 522
 523     i = list->cache_dyn_count;
 524     list->cache_dyn = silc_realloc(list->cache_dyn,
 525                                    sizeof(*list->cache_dyn) * (i + 5));
 526
 527     /* NULL the reallocated area */
 528     for (k = i; k < (i + 5); k++)
 529       list->cache_dyn[k] = NULL;
 530
 531     list->cache_dyn[i] = cache;
 532     list->cache_count++;
 533     list->cache_dyn_count += 5;
 534   }
 535 }
 536
 537 /* Returns number of cache entries in the ID cache list. */
 538
 539 int silc_idcache_list_count(SilcIDCacheList list)
 540 {
 541   return list->cache_count;
 542 }
 543
 544 /* Returns first entry from the ID cache list. */
 545
 546 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 547 {
 548   list->pos = 0;
 549
 550   if (!list->cache[list->pos])
 551     return FALSE;
 552
 553   if (ret)
 554     *ret = list->cache[list->pos];
 555
 556   return TRUE;
 557 }
 558
 559 /* Returns next entry from the ID cache list. */
 560
 561 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 562 {
 563   list->pos++;
 564
 565   if (!list->dyn &&
 566       list->pos >= (sizeof(list->cache) / sizeof(list->cache[0]))) {
 567     list->pos = 0;
 568     list->dyn = TRUE;
 569   }
 570
 571   if (list->dyn && list->pos >= list->cache_dyn_count)
 572     return FALSE;
 573
 574   if (!list->dyn && !list->cache[list->pos])
 575     return FALSE;
 576
 577   if (list->dyn && !list->cache_dyn[list->pos])
 578     return FALSE;
 579
 580   if (ret) {
 581     if (!list->dyn)
 582       *ret = list->cache[list->pos];
 583     else
 584       *ret = list->cache_dyn[list->pos];
 585   }
 586
 587   return TRUE;
 588 }
 589
 590 /* Frees ID cache list. User must free the list object returned by
 591    any of the searching functions. */
 592
 593 void silc_idcache_list_free(SilcIDCacheList list)
 594 {
 595   if (list) {
 596     if (list->cache_dyn)
 597       silc_free(list->cache_dyn);
 598     silc_free(list);
 599   }
 600 }