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