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