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
 243   return ret;
 244 }
 245
 246 /* Deletes ID cache entry by context. */
 247
 248 bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
 249 {
 250   SilcIDCacheEntry c;
 251   bool ret = FALSE;
 252
 253   SILC_LOG_DEBUG(("Deleting cache entry"));
 254
 255   if (!silc_hash_table_find(cache->context_table, context, NULL, (void *)&c))
 256     return FALSE;
 257
 258   if (c->name)
 259     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 260   if (c->context)
 261     ret = silc_hash_table_del(cache->context_table, c->context);
 262   if (c->id)
 263     ret = silc_hash_table_del_by_context(cache->id_table, c->id, c);
 264
 265   return ret;
 266 }
 267
 268 /* Deletes all ID entries from cache. Free's memory as well. */
 269
 270 bool silc_idcache_del_all(SilcIDCache cache)
 271 {
 272   silc_hash_table_free(cache->id_table);
 273   silc_hash_table_free(cache->name_table);
 274   silc_hash_table_free(cache->context_table);
 275
 276   return TRUE;
 277 }
 278
 279 /* Foreach callback fro silc_idcache_purge. */
 280
 281 static void silc_idcache_purge_foreach(void *key, void *context,
 282                                        void *user_context)
 283 {
 284   SilcIDCache cache = (SilcIDCache)user_context;
 285   uint32 curtime = time(NULL);
 286   SilcIDCacheEntry c = (SilcIDCacheEntry)context;
 287
 288   if (c->expire && c->expire < curtime) {
 289     /* Call the destructor */
 290     if (cache->destructor)
 291       cache->destructor(cache, c);
 292
 293     /* Delete the entry */
 294     silc_idcache_del(cache, c);
 295   }
 296 }
 297
 298 /* Purges the cache by removing expired cache entires. Note that this
 299    may be very slow operation. */
 300
 301 bool silc_idcache_purge(SilcIDCache cache)
 302 {
 303   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 304   return TRUE;
 305 }
 306
 307 /* Purges the specific entry by context. */
 308
 309 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 310 {
 311   SilcIDCacheEntry entry;
 312   bool ret = FALSE;
 313
 314   if (!silc_hash_table_find(cache->context_table, context, NULL,
 315                             (void *)&entry))
 316     return FALSE;
 317
 318   /* Call the destructor */
 319   if (cache->destructor)
 320     cache->destructor(cache, entry);
 321
 322   if (entry->name)
 323     ret = silc_hash_table_del_by_context(cache->name_table, entry->name,
 324                                          entry);
 325   if (entry->context)
 326     ret = silc_hash_table_del(cache->context_table, entry->context);
 327   if (entry->id)
 328     ret = silc_hash_table_del_by_context(cache->id_table, entry->id, entry);
 329
 330   return ret;
 331 }
 332
 333 /* Callback that is called by the hash table routine when traversing
 334    entrys in the hash table. */
 335
 336 static void silc_idcache_get_all_foreach(void *key, void *context,
 337                                          void *user_context)
 338 {
 339   SilcIDCacheList list = (SilcIDCacheList)user_context;
 340   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 341 }
 342
 343 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 344
 345 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 346 {
 347   SilcIDCacheList list;
 348
 349   if (!ret)
 350     return TRUE;
 351
 352   list = silc_idcache_list_alloc();
 353   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 354
 355   if (silc_idcache_list_count(list) == 0) {
 356     silc_idcache_list_free(list);
 357     return FALSE;
 358   }
 359
 360   *ret = list;
 361
 362   return TRUE;
 363 }
 364
 365 /* Find ID Cache entry by ID. May return multiple entries. */
 366
 367 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 368                              SilcIDCacheList *ret)
 369 {
 370   SilcIDCacheList list;
 371
 372   list = silc_idcache_list_alloc();
 373
 374   if (!ret)
 375     return TRUE;
 376
 377   silc_hash_table_find_foreach(cache->id_table, id,
 378                                silc_idcache_get_all_foreach, list);
 379
 380   if (silc_idcache_list_count(list) == 0) {
 381     silc_idcache_list_free(list);
 382     return FALSE;
 383   }
 384
 385   *ret = list;
 386
 387   return TRUE;
 388 }
 389
 390 /* Find specific ID with specific hash function and comparison functions.
 391    If `hash' is NULL then the default hash funtion is used and if `compare'
 392    is NULL default comparison function is used. */
 393
 394 bool silc_idcache_find_by_id_one_ext(SilcIDCache cache, void *id,
 395                                      SilcHashFunction hash,
 396                                      void *hash_context,
 397                                      SilcHashCompare compare,
 398                                      void *compare_context,
 399                                      SilcIDCacheEntry *ret)
 400 {
 401   return silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
 402                                   hash, hash_context, compare,
 403                                   compare_context);
 404 }
 405
 406 /* Find one specific ID entry. */
 407
 408 bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
 409                                  SilcIDCacheEntry *ret)
 410 {
 411   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 412 }
 413
 414 /* Finds cache entry by context. */
 415
 416 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 417                                   SilcIDCacheEntry *ret)
 418 {
 419   return silc_hash_table_find(cache->context_table, context, NULL,
 420                               (void *)ret);
 421 }
 422
 423 /* Find ID Cache entry by name. Returns list of cache entries. */
 424
 425 bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
 426                                SilcIDCacheList *ret)
 427 {
 428   SilcIDCacheList list;
 429
 430   list = silc_idcache_list_alloc();
 431
 432   if (!ret)
 433     return TRUE;
 434
 435   silc_hash_table_find_foreach(cache->name_table, name,
 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 ID Cache entry by name. Returns one cache entry. */
 449
 450 bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
 451                                    SilcIDCacheEntry *ret)
 452 {
 453   if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
 454     return FALSE;
 455
 456   return TRUE;
 457 }
 458
 459 /* Allocates ID cache list. */
 460
 461 static SilcIDCacheList silc_idcache_list_alloc()
 462 {
 463   SilcIDCacheList list;
 464
 465   list = silc_calloc(1, sizeof(*list));
 466
 467   return list;
 468 }
 469
 470 /* Adds cache entry to the ID cache list. If needed reallocates memory
 471    for the list. */
 472
 473 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 474 {
 475   int i;
 476
 477   /* Try to add to static cache */
 478   if (!list->cache_dyn_count)
 479     for (i = 0; i < sizeof(list->cache); i++) {
 480       if (!list->cache[i]) {
 481         list->cache[i] = cache;
 482         list->cache_count++;
 483         return;
 484       }
 485     }
 486
 487   /* Static cache is full, allocate dynamic cache */
 488   for (i = 0; i < list->cache_dyn_count; i++) {
 489     if (!list->cache_dyn[i]) {
 490       list->cache_dyn[i] = cache;
 491       list->cache_count++;
 492       break;
 493     }
 494   }
 495
 496   if (i >= list->cache_dyn_count) {
 497     int k;
 498
 499     i += 5;
 500     list->cache_dyn = silc_realloc(list->cache_dyn,
 501                                    sizeof(*list->cache) * (i));
 502
 503     /* NULL the reallocated area */
 504     for (k = list->cache_dyn_count; k < i; k++)
 505       list->cache_dyn[k] = NULL;
 506
 507     list->cache_dyn[list->cache_dyn_count] = cache;
 508     list->cache_dyn_count = i;
 509     list->cache_count++;
 510   }
 511 }
 512
 513 /* Returns number of cache entries in the ID cache list. */
 514
 515 int silc_idcache_list_count(SilcIDCacheList list)
 516 {
 517   return list->cache_count;
 518 }
 519
 520 /* Returns first entry from the ID cache list. */
 521
 522 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 523 {
 524   list->pos = 0;
 525
 526   if (!list->cache[list->pos])
 527     return FALSE;
 528
 529   if (ret)
 530     *ret = list->cache[list->pos];
 531
 532   return TRUE;
 533 }
 534
 535 /* Returns next entry from the ID cache list. */
 536
 537 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 538 {
 539   int dyn = FALSE;
 540   list->pos++;
 541
 542   if (list->pos >= sizeof(list->cache)) {
 543     list->pos = 0;
 544     dyn = TRUE;
 545   }
 546
 547   if (dyn && list->pos >= list->cache_dyn_count)
 548     return FALSE;
 549
 550   if (!dyn && !list->cache[list->pos])
 551     return FALSE;
 552
 553   if (dyn && !list->cache_dyn[list->pos])
 554     return FALSE;
 555
 556   if (ret) {
 557     if (!dyn)
 558       *ret = list->cache[list->pos];
 559     else
 560       *ret = list->cache_dyn[list->pos];
 561   }
 562
 563   return TRUE;
 564 }
 565
 566 /* Frees ID cache list. User must free the list object returned by
 567    any of the searching functions. */
 568
 569 void silc_idcache_list_free(SilcIDCacheList list)
 570 {
 571   if (list) {
 572     if (list->cache_dyn)
 573       silc_free(list->cache_dyn);
 574     silc_free(list);
 575   }
 576 }