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