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