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