lib/silccore/silcidcache.c

   1 /*
   2
   3   silcidcache.c
   4
   5   Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
   6
   7   Copyright (C) 2000 - 2005 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; version 2 of the License.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18 */
  19 /* $Id$ */
  20
  21 #include "silcincludes.h"
  22 #include "silcidcache.h"
  23
  24 /* Static prototypes */
  25 static void silc_idcache_destructor(void *key, void *context,
  26                                     void *user_context);
  27 static SilcIDCacheList silc_idcache_list_alloc();
  28 static void silc_idcache_list_add(SilcIDCacheList list,
  29                                   SilcIDCacheEntry cache);
  30
  31 /*
  32    SILC ID Cache object.
  33
  34    This is context for the ID cache system. This includes all the cache
  35    entries and other internal data. This is read-only object and not
  36    visible outside this cache system.
  37
  38    Fields are as follows:
  39
  40    SilcHashTable id_table
  41
  42        Hash table using the ID as the key.
  43
  44    SilcHashTable name_table
  45
  46        Hash table using the name as the key.
  47
  48    SilcHashTable context_table
  49
  50        Hash table using the context as the key.
  51
  52    SilcIDCacheDestructor destructor
  53
  54        Destructor callback that is called when an cache entry expires or is
  55        purged from the ID cache. The application must not free cache entry
  56        because the library will do it automatically. The appliation, however,
  57        is responsible of freeing any data in the entry.
  58
  59    SilcIdType id_type
  60
  61        Indicates the type of the ID's this cache holds.
  62
  63 */
  64 struct SilcIDCacheStruct {
  65   SilcHashTable id_table;
  66   SilcHashTable name_table;
  67   SilcHashTable context_table;
  68   SilcIDCacheDestructor destructor;
  69   void *context;
  70   SilcIdType type;
  71   unsigned int delete_id : 1;
  72   unsigned int delete_name : 1;
  73 };
  74
  75 /*
  76    ID Cache list.
  77
  78    This is returned when searching the cache. Enumeration functions are
  79    provided to traverse the list; actually this is used as table not as
  80    list. :)
  81
  82    By default the found cache entries are saved into the static cache
  83    table to provide access without reallocation. However, if the static
  84    table is full, rest of the cache entries are dynamically allocated
  85    into `cache_dyn' table. Traversing functions automatically handles
  86    these situations.
  87
  88 */
  89 struct SilcIDCacheListStruct {
  90   SilcIDCacheEntry cache[128];
  91   SilcIDCacheEntry *cache_dyn;
  92   SilcUInt32 cache_dyn_count;
  93   SilcUInt32 cache_count;
  94   SilcUInt32 pos;
  95   bool dyn;
  96 };
  97
  98 /* Allocates new ID cache object. The initial amount of allocated entries
  99    can be sent as argument. If `count' is 0 the system uses default values.
 100    The `id_type' defines the types of the ID's that will be saved to the
 101    cache. */
 102
 103 SilcIDCache silc_idcache_alloc(SilcUInt32 count, SilcIdType id_type,
 104                                SilcIDCacheDestructor destructor,
 105                                void *destructor_context,
 106                                bool delete_id, bool delete_name)
 107 {
 108   SilcIDCache cache;
 109
 110   SILC_LOG_DEBUG(("Allocating new cache"));
 111
 112   cache = silc_calloc(1, sizeof(*cache));
 113   if (!cache)
 114     return NULL;
 115   cache->id_table = silc_hash_table_alloc(count, silc_hash_id,
 116                                           SILC_32_TO_PTR(id_type),
 117                                           silc_hash_id_compare,
 118                                           SILC_32_TO_PTR(id_type),
 119                                           silc_idcache_destructor,
 120                                           cache, TRUE);
 121   cache->name_table = silc_hash_table_alloc(count, silc_hash_utf8_string, NULL,
 122                                             silc_hash_utf8_compare, NULL,
 123                                             NULL, NULL, TRUE);
 124   cache->context_table = silc_hash_table_alloc(count, silc_hash_ptr, NULL,
 125                                                NULL, NULL, NULL, NULL, TRUE);
 126   cache->destructor = destructor;
 127   cache->context = destructor_context;
 128   cache->type = id_type;
 129   cache->delete_id = delete_id;
 130   cache->delete_name = delete_name;
 131
 132   if (!cache->id_table || !cache->name_table || !cache->context_table) {
 133     if (cache->id_table)
 134       silc_hash_table_free(cache->id_table);
 135     if (cache->name_table)
 136       silc_hash_table_free(cache->name_table);
 137     if (cache->context_table)
 138       silc_hash_table_free(cache->context_table);
 139     silc_free(cache);
 140     return NULL;
 141   }
 142
 143   return cache;
 144 }
 145
 146 /* Frees ID cache object and cache entries */
 147
 148 void silc_idcache_free(SilcIDCache cache)
 149 {
 150   if (cache) {
 151     silc_hash_table_free(cache->id_table);
 152     silc_hash_table_free(cache->name_table);
 153     silc_hash_table_free(cache->context_table);
 154     silc_free(cache);
 155   }
 156 }
 157
 158 /* Add new entry to the cache. Returns TRUE if the entry was added and
 159    FALSE if it could not be added. The `name' is the name associated with
 160    the ID, the `id' the actual ID and the `context' a used specific context.
 161    If the `expire' is TRUE the entry expires in default time and if FALSE
 162    the entry never expires from the cache. */
 163
 164 bool silc_idcache_add(SilcIDCache cache, char *name, void *id,
 165                       void *context, int expire, SilcIDCacheEntry *ret)
 166 {
 167   SilcIDCacheEntry c;
 168
 169   SILC_LOG_DEBUG(("Adding cache entry"));
 170
 171   /* Allocate new cache entry */
 172   c = silc_calloc(1, sizeof(*c));
 173   if (!c)
 174     return FALSE;
 175   c->id = id;
 176   c->name = name;
 177   c->expire = expire;
 178   c->context = context;
 179
 180   /* Add the new entry to the hash tables */
 181
 182   if (id)
 183     silc_hash_table_add(cache->id_table, id, c);
 184   if (name)
 185     silc_hash_table_add(cache->name_table, name, c);
 186   if (context)
 187     silc_hash_table_add(cache->context_table, context, c);
 188
 189   if (ret)
 190     *ret = c;
 191
 192   return TRUE;
 193 }
 194
 195 /* Destructor for the ID Cache entry */
 196
 197 static void silc_idcache_destructor(void *key, void *context,
 198                                     void *user_context)
 199 {
 200   SilcIDCacheEntry c = context;
 201   if (c) {
 202     SilcIDCache cache = user_context;
 203     if (cache) {
 204       if (cache->delete_id)
 205         silc_free(c->id);
 206       if (cache->delete_name)
 207         silc_free(c->name);
 208     }
 209     memset(c, 'F', sizeof(*c));
 210     silc_free(c);
 211   }
 212 }
 213
 214 /* Delete cache entry from cache. */
 215
 216 bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 217 {
 218   bool ret = FALSE;
 219
 220   SILC_LOG_DEBUG(("Deleting cache entry"));
 221
 222   if (old->name)
 223     ret = silc_hash_table_del_by_context(cache->name_table, old->name, old);
 224   if (old->context)
 225     ret = silc_hash_table_del(cache->context_table, old->context);
 226   if (old->id)
 227     ret = silc_hash_table_del(cache->id_table, old->id);
 228   else {
 229     silc_idcache_destructor(NULL, old, NULL);
 230     ret = TRUE;
 231   }
 232
 233   return ret;
 234 }
 235
 236 /* Deletes ID cache entry by ID. */
 237
 238 bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
 239 {
 240   SilcIDCacheEntry c;
 241
 242   if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
 243     return FALSE;
 244
 245   return silc_idcache_del(cache, c);
 246 }
 247
 248 /* Same as above but with specific hash and comparison functions. If the
 249    functions are NULL then default values are used. */
 250
 251 bool silc_idcache_del_by_id_ext(SilcIDCache cache, void *id,
 252                                 SilcHashFunction hash,
 253                                 void *hash_context,
 254                                 SilcHashCompare compare,
 255                                 void *compare_context)
 256 {
 257   SilcIDCacheEntry c;
 258   bool ret = FALSE;
 259
 260   SILC_LOG_DEBUG(("Deleting cache entry"));
 261
 262   if (!silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)&c,
 263                                 hash, hash_context, compare,
 264                                 compare_context))
 265     return FALSE;
 266
 267   if (c->name)
 268     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 269   if (c->context)
 270     ret = silc_hash_table_del(cache->context_table, c->context);
 271   if (c->id)
 272     ret = silc_hash_table_del_ext(cache->id_table, c->id, hash,
 273                                   hash_context, compare, compare_context,
 274                                   NULL, NULL);
 275   return ret;
 276 }
 277
 278 /* Deletes ID cache entry by context. */
 279
 280 bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
 281 {
 282   SilcIDCacheEntry c;
 283   bool ret = FALSE;
 284
 285   SILC_LOG_DEBUG(("Deleting cache entry"));
 286
 287   if (!silc_hash_table_find(cache->context_table, context, NULL, (void *)&c))
 288     return FALSE;
 289
 290   if (c->name)
 291     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 292   if (c->context)
 293     ret = silc_hash_table_del(cache->context_table, c->context);
 294   if (c->id)
 295     ret = silc_hash_table_del_by_context(cache->id_table, c->id, c);
 296   else {
 297     silc_idcache_destructor(NULL, c, NULL);
 298     ret = TRUE;
 299   }
 300
 301   return ret;
 302 }
 303
 304 /* Deletes all ID entries from cache. Free's memory as well. */
 305
 306 bool silc_idcache_del_all(SilcIDCache cache)
 307 {
 308   silc_hash_table_free(cache->id_table);
 309   silc_hash_table_free(cache->name_table);
 310   silc_hash_table_free(cache->context_table);
 311
 312   return TRUE;
 313 }
 314
 315 static void silc_idcache_destructor_dummy(void *key, void *context,
 316                                           void *user_context)
 317 {
 318   /* Dummy - nothing */
 319 }
 320
 321 /* Foreach callback fro silc_idcache_purge. */
 322
 323 static void silc_idcache_purge_foreach(void *key, void *context,
 324                                        void *user_context)
 325 {
 326   SilcIDCache cache = (SilcIDCache)user_context;
 327   SilcUInt32 curtime = time(NULL);
 328   SilcIDCacheEntry c = (SilcIDCacheEntry)context;
 329   bool ret = FALSE;
 330
 331   if (!context)
 332     return;
 333
 334   if (c->expire && c->expire < curtime) {
 335     /* Remove the entry from the hash tables */
 336     if (c->name)
 337       ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 338     if (c->context)
 339       ret = silc_hash_table_del(cache->context_table, c->context);
 340     if (c->id)
 341       ret =
 342         silc_hash_table_del_by_context_ext(cache->id_table, c->id, c,
 343                                            NULL, NULL, NULL, NULL,
 344                                            silc_idcache_destructor_dummy,
 345                                            NULL);
 346     if (ret == TRUE) {
 347       /* Call the destructor */
 348       if (cache->destructor)
 349         cache->destructor(cache, c, cache->context);
 350
 351       /* Free the entry, it has been deleted from the hash tables */
 352       silc_idcache_destructor(NULL, c, NULL);
 353     }
 354   }
 355 }
 356
 357 /* Purges the cache by removing expired cache entires. Note that this
 358    may be very slow operation. */
 359
 360 bool silc_idcache_purge(SilcIDCache cache)
 361 {
 362   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 363   return TRUE;
 364 }
 365
 366 /* Purges the specific entry by context. */
 367
 368 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 369 {
 370   SilcIDCacheEntry c;
 371   bool ret = FALSE;
 372
 373   if (!silc_hash_table_find(cache->context_table, context, NULL,
 374                             (void *)&c))
 375     return FALSE;
 376
 377     /* Remove the entry from the hash tables */
 378   if (c->name)
 379     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 380   if (c->context)
 381     ret = silc_hash_table_del(cache->context_table, c->context);
 382   if (c->id)
 383     ret =
 384       silc_hash_table_del_by_context_ext(cache->id_table, c->id, c,
 385                                          NULL, NULL, NULL, NULL,
 386                                          silc_idcache_destructor_dummy, NULL);
 387   if (ret == TRUE) {
 388     /* Call the destructor */
 389     if (cache->destructor)
 390       cache->destructor(cache, c, cache->context);
 391
 392     /* Free the entry, it has been deleted from the hash tables */
 393     silc_idcache_destructor(NULL, c, NULL);
 394   }
 395
 396   return ret;
 397 }
 398
 399 /* Callback that is called by the hash table routine when traversing
 400    entrys in the hash table. */
 401
 402 static void silc_idcache_get_all_foreach(void *key, void *context,
 403                                          void *user_context)
 404 {
 405   SilcIDCacheList list = (SilcIDCacheList)user_context;
 406   if (!context)
 407     return;
 408   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 409 }
 410
 411 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 412
 413 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 414 {
 415   SilcIDCacheList list;
 416
 417   if (!ret)
 418     return TRUE;
 419
 420   list = silc_idcache_list_alloc();
 421   if (!list)
 422     return FALSE;
 423   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 424
 425   if (silc_idcache_list_count(list) == 0) {
 426     silc_idcache_list_free(list);
 427     return FALSE;
 428   }
 429
 430   *ret = list;
 431
 432   return TRUE;
 433 }
 434
 435 /* Find ID Cache entry by ID. May return multiple entries. */
 436
 437 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 438                              SilcIDCacheList *ret)
 439 {
 440   SilcIDCacheList list;
 441
 442   list = silc_idcache_list_alloc();
 443   if (!list)
 444     return FALSE;
 445
 446   if (!ret)
 447     return TRUE;
 448
 449   silc_hash_table_find_foreach(cache->id_table, id,
 450                                silc_idcache_get_all_foreach, list);
 451
 452   if (silc_idcache_list_count(list) == 0) {
 453     silc_idcache_list_free(list);
 454     return FALSE;
 455   }
 456
 457   *ret = list;
 458
 459   return TRUE;
 460 }
 461
 462 /* Find specific ID with specific hash function and comparison functions.
 463    If `hash' is NULL then the default hash funtion is used and if `compare'
 464    is NULL default comparison function is used. */
 465
 466 bool silc_idcache_find_by_id_one_ext(SilcIDCache cache, void *id,
 467                                      SilcHashFunction hash,
 468                                      void *hash_context,
 469                                      SilcHashCompare compare,
 470                                      void *compare_context,
 471                                      SilcIDCacheEntry *ret)
 472 {
 473   return silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
 474                                   hash, hash_context, compare,
 475                                   compare_context);
 476 }
 477
 478 /* Find one specific ID entry. */
 479
 480 bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
 481                                  SilcIDCacheEntry *ret)
 482 {
 483   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 484 }
 485
 486 /* Finds cache entry by context. */
 487
 488 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 489                                   SilcIDCacheEntry *ret)
 490 {
 491   return silc_hash_table_find(cache->context_table, context, NULL,
 492                               (void *)ret);
 493 }
 494
 495 /* Find ID Cache entry by name. Returns list of cache entries. */
 496
 497 bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
 498                                SilcIDCacheList *ret)
 499 {
 500   SilcIDCacheList list;
 501
 502   list = silc_idcache_list_alloc();
 503   if (!list)
 504     return FALSE;
 505
 506   if (!ret)
 507     return TRUE;
 508
 509   silc_hash_table_find_foreach(cache->name_table, name,
 510                                silc_idcache_get_all_foreach, list);
 511
 512   if (silc_idcache_list_count(list) == 0) {
 513     silc_idcache_list_free(list);
 514     return FALSE;
 515   }
 516
 517   *ret = list;
 518
 519   return TRUE;
 520 }
 521
 522 /* Find ID Cache entry by name. Returns one cache entry. */
 523
 524 bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
 525                                    SilcIDCacheEntry *ret)
 526 {
 527   if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
 528     return FALSE;
 529
 530   return TRUE;
 531 }
 532
 533 /* Allocates ID cache list. */
 534
 535 static SilcIDCacheList silc_idcache_list_alloc()
 536 {
 537   SilcIDCacheList list;
 538
 539   list = silc_calloc(1, sizeof(*list));
 540   if (!list)
 541     return FALSE;
 542
 543   return list;
 544 }
 545
 546 /* Adds cache entry to the ID cache list. If needed reallocates memory
 547    for the list. */
 548
 549 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 550 {
 551   int i;
 552
 553   /* Try to add to static cache */
 554   if (!list->cache_dyn_count)
 555     for (i = 0; i < (sizeof(list->cache) / sizeof(list->cache[0])); i++) {
 556       if (!list->cache[i]) {
 557         list->cache[i] = cache;
 558         list->cache_count++;
 559         return;
 560       }
 561     }
 562
 563   /* Static cache is full, allocate dynamic cache */
 564   for (i = 0; i < list->cache_dyn_count; i++) {
 565     if (!list->cache_dyn[i]) {
 566       list->cache_dyn[i] = cache;
 567       list->cache_count++;
 568       break;
 569     }
 570   }
 571
 572   if (i >= list->cache_dyn_count) {
 573     int k;
 574
 575     i = list->cache_dyn_count;
 576     list->cache_dyn = silc_realloc(list->cache_dyn,
 577                                    sizeof(*list->cache_dyn) * (i + 5));
 578     if (!list->cache_dyn)
 579       return;
 580
 581     /* NULL the reallocated area */
 582     for (k = i; k < (i + 5); k++)
 583       list->cache_dyn[k] = NULL;
 584
 585     list->cache_dyn[i] = cache;
 586     list->cache_count++;
 587     list->cache_dyn_count += 5;
 588   }
 589 }
 590
 591 /* Returns number of cache entries in the ID cache list. */
 592
 593 int silc_idcache_list_count(SilcIDCacheList list)
 594 {
 595   return list->cache_count;
 596 }
 597
 598 /* Returns first entry from the ID cache list. */
 599
 600 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 601 {
 602   list->pos = 0;
 603
 604   if (!list->cache[list->pos])
 605     return FALSE;
 606
 607   if (ret)
 608     *ret = list->cache[list->pos];
 609
 610   return TRUE;
 611 }
 612
 613 /* Returns next entry from the ID cache list. */
 614
 615 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 616 {
 617   list->pos++;
 618
 619   if (!list->dyn &&
 620       list->pos >= (sizeof(list->cache) / sizeof(list->cache[0]))) {
 621     list->pos = 0;
 622     list->dyn = TRUE;
 623   }
 624
 625   if (list->dyn && list->pos >= list->cache_dyn_count)
 626     return FALSE;
 627
 628   if (!list->dyn && !list->cache[list->pos])
 629     return FALSE;
 630
 631   if (list->dyn && !list->cache_dyn[list->pos])
 632     return FALSE;
 633
 634   if (ret) {
 635     if (!list->dyn)
 636       *ret = list->cache[list->pos];
 637     else
 638       *ret = list->cache_dyn[list->pos];
 639   }
 640
 641   return TRUE;
 642 }
 643
 644 /* Frees ID cache list. User must free the list object returned by
 645    any of the searching functions. */
 646
 647 void silc_idcache_list_free(SilcIDCacheList list)
 648 {
 649   if (list) {
 650     if (list->cache_dyn)
 651       silc_free(list->cache_dyn);
 652     silc_free(list);
 653   }
 654 }