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