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   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 (!context)
 309     return;
 310
 311   if (c->expire && c->expire < curtime) {
 312     /* Remove the entry from the hash tables */
 313     if (c->name)
 314       silc_hash_table_del_by_context(cache->name_table, c->name, c);
 315     if (c->context)
 316       silc_hash_table_del(cache->context_table, c->context);
 317     if (c->id)
 318       silc_hash_table_del_by_context_ext(cache->id_table, c->id, c,
 319                                          NULL, NULL, NULL, NULL,
 320                                          silc_idcache_destructor_dummy, NULL);
 321
 322     /* Call the destructor */
 323     if (cache->destructor)
 324       cache->destructor(cache, c);
 325
 326     /* Free the entry, it has been deleted from the hash tables */
 327     silc_free(c);
 328   }
 329 }
 330
 331 /* Purges the cache by removing expired cache entires. Note that this
 332    may be very slow operation. */
 333
 334 bool silc_idcache_purge(SilcIDCache cache)
 335 {
 336   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 337   return TRUE;
 338 }
 339
 340 /* Purges the specific entry by context. */
 341
 342 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 343 {
 344   SilcIDCacheEntry c;
 345   bool ret = FALSE;
 346
 347   if (!silc_hash_table_find(cache->context_table, context, NULL,
 348                             (void *)&c))
 349     return FALSE;
 350
 351     /* Remove the entry from the hash tables */
 352   if (c->name)
 353     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 354   if (c->context)
 355     ret = silc_hash_table_del(cache->context_table, c->context);
 356   if (c->id)
 357     ret =
 358       silc_hash_table_del_by_context_ext(cache->id_table, c->id, c,
 359                                          NULL, NULL, NULL, NULL,
 360                                          silc_idcache_destructor_dummy, NULL);
 361
 362   /* Call the destructor */
 363   if (cache->destructor)
 364     cache->destructor(cache, c);
 365
 366   /* Free the entry, it has been deleted from the hash tables */
 367   silc_free(c);
 368
 369   return ret;
 370 }
 371
 372 /* Callback that is called by the hash table routine when traversing
 373    entrys in the hash table. */
 374
 375 static void silc_idcache_get_all_foreach(void *key, void *context,
 376                                          void *user_context)
 377 {
 378   SilcIDCacheList list = (SilcIDCacheList)user_context;
 379   if (!context)
 380     return;
 381   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 382 }
 383
 384 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 385
 386 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 387 {
 388   SilcIDCacheList list;
 389
 390   if (!ret)
 391     return TRUE;
 392
 393   list = silc_idcache_list_alloc();
 394   if (!list)
 395     return FALSE;
 396   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 397
 398   if (silc_idcache_list_count(list) == 0) {
 399     silc_idcache_list_free(list);
 400     return FALSE;
 401   }
 402
 403   *ret = list;
 404
 405   return TRUE;
 406 }
 407
 408 /* Find ID Cache entry by ID. May return multiple entries. */
 409
 410 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 411                              SilcIDCacheList *ret)
 412 {
 413   SilcIDCacheList list;
 414
 415   list = silc_idcache_list_alloc();
 416   if (!list)
 417     return FALSE;
 418
 419   if (!ret)
 420     return TRUE;
 421
 422   silc_hash_table_find_foreach(cache->id_table, id,
 423                                silc_idcache_get_all_foreach, list);
 424
 425   if (silc_idcache_list_count(list) == 0) {
 426     silc_idcache_list_free(list);
 427     return FALSE;
 428   }
 429
 430   *ret = list;
 431
 432   return TRUE;
 433 }
 434
 435 /* Find specific ID with specific hash function and comparison functions.
 436    If `hash' is NULL then the default hash funtion is used and if `compare'
 437    is NULL default comparison function is used. */
 438
 439 bool silc_idcache_find_by_id_one_ext(SilcIDCache cache, void *id,
 440                                      SilcHashFunction hash,
 441                                      void *hash_context,
 442                                      SilcHashCompare compare,
 443                                      void *compare_context,
 444                                      SilcIDCacheEntry *ret)
 445 {
 446   return silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
 447                                   hash, hash_context, compare,
 448                                   compare_context);
 449 }
 450
 451 /* Find one specific ID entry. */
 452
 453 bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
 454                                  SilcIDCacheEntry *ret)
 455 {
 456   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 457 }
 458
 459 /* Finds cache entry by context. */
 460
 461 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 462                                   SilcIDCacheEntry *ret)
 463 {
 464   return silc_hash_table_find(cache->context_table, context, NULL,
 465                               (void *)ret);
 466 }
 467
 468 /* Find ID Cache entry by name. Returns list of cache entries. */
 469
 470 bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
 471                                SilcIDCacheList *ret)
 472 {
 473   SilcIDCacheList list;
 474
 475   list = silc_idcache_list_alloc();
 476   if (!list)
 477     return FALSE;
 478
 479   if (!ret)
 480     return TRUE;
 481
 482   silc_hash_table_find_foreach(cache->name_table, name,
 483                                silc_idcache_get_all_foreach, list);
 484
 485   if (silc_idcache_list_count(list) == 0) {
 486     silc_idcache_list_free(list);
 487     return FALSE;
 488   }
 489
 490   *ret = list;
 491
 492   return TRUE;
 493 }
 494
 495 /* Find ID Cache entry by name. Returns one cache entry. */
 496
 497 bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
 498                                    SilcIDCacheEntry *ret)
 499 {
 500   if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
 501     return FALSE;
 502
 503   return TRUE;
 504 }
 505
 506 /* Allocates ID cache list. */
 507
 508 static SilcIDCacheList silc_idcache_list_alloc()
 509 {
 510   SilcIDCacheList list;
 511
 512   list = silc_calloc(1, sizeof(*list));
 513   if (!list)
 514     return FALSE;
 515
 516   return list;
 517 }
 518
 519 /* Adds cache entry to the ID cache list. If needed reallocates memory
 520    for the list. */
 521
 522 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 523 {
 524   int i;
 525
 526   /* Try to add to static cache */
 527   if (!list->cache_dyn_count)
 528     for (i = 0; i < (sizeof(list->cache) / sizeof(list->cache[0])); i++) {
 529       if (!list->cache[i]) {
 530         list->cache[i] = cache;
 531         list->cache_count++;
 532         return;
 533       }
 534     }
 535
 536   /* Static cache is full, allocate dynamic cache */
 537   for (i = 0; i < list->cache_dyn_count; i++) {
 538     if (!list->cache_dyn[i]) {
 539       list->cache_dyn[i] = cache;
 540       list->cache_count++;
 541       break;
 542     }
 543   }
 544
 545   if (i >= list->cache_dyn_count) {
 546     int k;
 547
 548     i = list->cache_dyn_count;
 549     list->cache_dyn = silc_realloc(list->cache_dyn,
 550                                    sizeof(*list->cache_dyn) * (i + 5));
 551     if (!list->cache_dyn)
 552       return;
 553
 554     /* NULL the reallocated area */
 555     for (k = i; k < (i + 5); k++)
 556       list->cache_dyn[k] = NULL;
 557
 558     list->cache_dyn[i] = cache;
 559     list->cache_count++;
 560     list->cache_dyn_count += 5;
 561   }
 562 }
 563
 564 /* Returns number of cache entries in the ID cache list. */
 565
 566 int silc_idcache_list_count(SilcIDCacheList list)
 567 {
 568   return list->cache_count;
 569 }
 570
 571 /* Returns first entry from the ID cache list. */
 572
 573 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 574 {
 575   list->pos = 0;
 576
 577   if (!list->cache[list->pos])
 578     return FALSE;
 579
 580   if (ret)
 581     *ret = list->cache[list->pos];
 582
 583   return TRUE;
 584 }
 585
 586 /* Returns next entry from the ID cache list. */
 587
 588 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 589 {
 590   list->pos++;
 591
 592   if (!list->dyn &&
 593       list->pos >= (sizeof(list->cache) / sizeof(list->cache[0]))) {
 594     list->pos = 0;
 595     list->dyn = TRUE;
 596   }
 597
 598   if (list->dyn && list->pos >= list->cache_dyn_count)
 599     return FALSE;
 600
 601   if (!list->dyn && !list->cache[list->pos])
 602     return FALSE;
 603
 604   if (list->dyn && !list->cache_dyn[list->pos])
 605     return FALSE;
 606
 607   if (ret) {
 608     if (!list->dyn)
 609       *ret = list->cache[list->pos];
 610     else
 611       *ret = list->cache_dyn[list->pos];
 612   }
 613
 614   return TRUE;
 615 }
 616
 617 /* Frees ID cache list. User must free the list object returned by
 618    any of the searching functions. */
 619
 620 void silc_idcache_list_free(SilcIDCacheList list)
 621 {
 622   if (list) {
 623     if (list->cache_dyn)
 624       silc_free(list->cache_dyn);
 625     silc_free(list);
 626   }
 627 }