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