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