lib/silccore/silcidcache.c

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