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 /* Free's 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. */
 138
 139 bool silc_idcache_add(SilcIDCache cache, char *name, void *id,
 140                       void *context, int expire)
 141 {
 142   SilcIDCacheEntry c;
 143   uint32 curtime = time(NULL);
 144
 145   SILC_LOG_DEBUG(("Adding cache entry"));
 146
 147   /* Allocate new cache entry */
 148   c = silc_calloc(1, sizeof(*c));
 149   c->id = id;
 150   c->name = name;
 151   c->expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 152   c->context = context;
 153
 154   /* Add the new entry to the hash tables */
 155
 156   if (id)
 157     silc_hash_table_add(cache->id_table, id, c);
 158   if (name)
 159     silc_hash_table_add(cache->name_table, name, c);
 160   if (context)
 161     silc_hash_table_add(cache->context_table, context, c);
 162
 163   /* See whether we have time to rehash the tables */
 164   if ((silc_hash_table_count(cache->id_table) / 2) >
 165       silc_hash_table_size(cache->id_table)) {
 166     silc_hash_table_rehash(cache->id_table, 0);
 167     silc_hash_table_rehash(cache->name_table, 0);
 168     silc_hash_table_rehash(cache->context_table, 0);
 169   }
 170
 171   return TRUE;
 172 }
 173
 174 /* Destructor for the ID Cache entry */
 175
 176 static void silc_idcache_destructor(void *key, void *context,
 177                                     void *user_context)
 178 {
 179   silc_free(context);
 180 }
 181
 182 /* Delete cache entry from cache. */
 183
 184 bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 185 {
 186   bool ret = FALSE;
 187
 188   SILC_LOG_DEBUG(("Deleting cache entry"));
 189
 190   if (old->name)
 191     ret = silc_hash_table_del_by_context(cache->name_table, old->name, old);
 192   if (old->context)
 193     ret = silc_hash_table_del(cache->context_table, old->context);
 194   if (old->id)
 195     ret = silc_hash_table_del(cache->id_table, old->id);
 196
 197   return ret;
 198 }
 199
 200 /* Deletes ID cache entry by ID. */
 201
 202 bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
 203 {
 204   SilcIDCacheEntry c;
 205
 206   if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
 207     return FALSE;
 208
 209   return silc_idcache_del(cache, c);
 210 }
 211
 212 /* Same as above but with specific hash and comparison functions. If the
 213    functions are NULL then default values are used. */
 214
 215 bool silc_idcache_del_by_id_ext(SilcIDCache cache, void *id,
 216                                 SilcHashFunction hash,
 217                                 void *hash_context,
 218                                 SilcHashCompare compare,
 219                                 void *compare_context)
 220 {
 221   SilcIDCacheEntry c;
 222   bool ret = FALSE;
 223
 224   SILC_LOG_DEBUG(("Deleting cache entry"));
 225
 226   if (!silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)&c,
 227                                 hash, hash_context, compare,
 228                                 compare_context))
 229     return FALSE;
 230
 231   if (c->name)
 232     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 233   if (c->context)
 234     ret = silc_hash_table_del(cache->context_table, c->context);
 235   if (c->id)
 236     ret = silc_hash_table_del_ext(cache->id_table, c->id, hash,
 237                                   hash_context, compare, compare_context);
 238
 239   return ret;
 240 }
 241
 242 /* Deletes ID cache entry by context. */
 243
 244 bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
 245 {
 246   SilcIDCacheEntry c;
 247   bool ret = FALSE;
 248
 249   SILC_LOG_DEBUG(("Deleting cache entry"));
 250
 251   if (!silc_hash_table_find(cache->context_table, context, NULL, (void *)&c))
 252     return FALSE;
 253
 254   if (c->name)
 255     ret = silc_hash_table_del_by_context(cache->name_table, c->name, c);
 256   if (c->context)
 257     ret = silc_hash_table_del(cache->context_table, c->context);
 258   if (c->id)
 259     ret = silc_hash_table_del_by_context(cache->id_table, c->id, c);
 260
 261   return ret;
 262 }
 263
 264 /* Deletes all ID entries from cache. Free's memory as well. */
 265
 266 bool silc_idcache_del_all(SilcIDCache cache)
 267 {
 268   silc_hash_table_free(cache->id_table);
 269   silc_hash_table_free(cache->name_table);
 270   silc_hash_table_free(cache->context_table);
 271
 272   return TRUE;
 273 }
 274
 275 /* Foreach callback fro silc_idcache_purge. */
 276
 277 static void silc_idcache_purge_foreach(void *key, void *context,
 278                                        void *user_context)
 279 {
 280   SilcIDCache cache = (SilcIDCache)user_context;
 281   uint32 curtime = time(NULL);
 282   SilcIDCacheEntry c = (SilcIDCacheEntry)context;
 283
 284   if (c->expire && c->expire < curtime) {
 285     /* Call the destructor */
 286     if (cache->destructor)
 287       cache->destructor(cache, c);
 288
 289     /* Delete the entry */
 290     silc_idcache_del(cache, c);
 291   }
 292 }
 293
 294 /* Purges the cache by removing expired cache entires. Note that this
 295    may be very slow operation. */
 296
 297 bool silc_idcache_purge(SilcIDCache cache)
 298 {
 299   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 300   return TRUE;
 301 }
 302
 303 /* Purges the specific entry by context. */
 304
 305 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 306 {
 307   SilcIDCacheEntry entry;
 308   bool ret = FALSE;
 309
 310   if (!silc_hash_table_find(cache->context_table, context, NULL,
 311                             (void *)&entry))
 312     return FALSE;
 313
 314   /* Call the destructor */
 315   if (cache->destructor)
 316     cache->destructor(cache, entry);
 317
 318   if (entry->name)
 319     ret = silc_hash_table_del_by_context(cache->name_table, entry->name,
 320                                          entry);
 321   if (entry->context)
 322     ret = silc_hash_table_del(cache->context_table, entry->context);
 323   if (entry->id)
 324     ret = silc_hash_table_del_by_context(cache->id_table, entry->id, entry);
 325
 326   return ret;
 327 }
 328
 329 /* Callback that is called by the hash table routine when traversing
 330    entrys in the hash table. */
 331
 332 static void silc_idcache_get_all_foreach(void *key, void *context,
 333                                          void *user_context)
 334 {
 335   SilcIDCacheList list = (SilcIDCacheList)user_context;
 336   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 337 }
 338
 339 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 340
 341 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 342 {
 343   SilcIDCacheList list;
 344
 345   if (!ret)
 346     return TRUE;
 347
 348   list = silc_idcache_list_alloc();
 349   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 350
 351   if (silc_idcache_list_count(list) == 0) {
 352     silc_idcache_list_free(list);
 353     return FALSE;
 354   }
 355
 356   *ret = list;
 357
 358   return TRUE;
 359 }
 360
 361 /* Find ID Cache entry by ID. May return multiple entries. */
 362
 363 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 364                              SilcIDCacheList *ret)
 365 {
 366   SilcIDCacheList list;
 367
 368   list = silc_idcache_list_alloc();
 369
 370   if (!ret)
 371     return TRUE;
 372
 373   silc_hash_table_find_foreach(cache->id_table, id,
 374                                silc_idcache_get_all_foreach, list);
 375
 376   if (silc_idcache_list_count(list) == 0) {
 377     silc_idcache_list_free(list);
 378     return FALSE;
 379   }
 380
 381   *ret = list;
 382
 383   return TRUE;
 384 }
 385
 386 /* Find specific ID with specific hash function and comparison functions.
 387    If `hash' is NULL then the default hash funtion is used and if `compare'
 388    is NULL default comparison function is used. */
 389
 390 bool silc_idcache_find_by_id_one_ext(SilcIDCache cache, void *id,
 391                                      SilcHashFunction hash,
 392                                      void *hash_context,
 393                                      SilcHashCompare compare,
 394                                      void *compare_context,
 395                                      SilcIDCacheEntry *ret)
 396 {
 397   return silc_hash_table_find_ext(cache->id_table, id, NULL, (void *)ret,
 398                                   hash, hash_context, compare,
 399                                   compare_context);
 400 }
 401
 402 /* Find one specific ID entry. */
 403
 404 bool silc_idcache_find_by_id_one(SilcIDCache cache, void *id,
 405                                  SilcIDCacheEntry *ret)
 406 {
 407   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 408 }
 409
 410 /* Finds cache entry by context. */
 411
 412 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 413                                   SilcIDCacheEntry *ret)
 414 {
 415   return silc_hash_table_find(cache->context_table, context, NULL,
 416                               (void *)ret);
 417 }
 418
 419 /* Find ID Cache entry by name. Returns list of cache entries. */
 420
 421 bool silc_idcache_find_by_name(SilcIDCache cache, char *name,
 422                                SilcIDCacheList *ret)
 423 {
 424   SilcIDCacheList list;
 425
 426   list = silc_idcache_list_alloc();
 427
 428   if (!ret)
 429     return TRUE;
 430
 431   silc_hash_table_find_foreach(cache->name_table, name,
 432                                silc_idcache_get_all_foreach, list);
 433
 434   if (silc_idcache_list_count(list) == 0) {
 435     silc_idcache_list_free(list);
 436     return FALSE;
 437   }
 438
 439   *ret = list;
 440
 441   return TRUE;
 442 }
 443
 444 /* Find ID Cache entry by name. Returns one cache entry. */
 445
 446 bool silc_idcache_find_by_name_one(SilcIDCache cache, char *name,
 447                                    SilcIDCacheEntry *ret)
 448 {
 449   if (!silc_hash_table_find(cache->name_table, name, NULL, (void *)ret))
 450     return FALSE;
 451
 452   return TRUE;
 453 }
 454
 455 /* Allocates ID cache list. */
 456
 457 static SilcIDCacheList silc_idcache_list_alloc()
 458 {
 459   SilcIDCacheList list;
 460
 461   list = silc_calloc(1, sizeof(*list));
 462
 463   return list;
 464 }
 465
 466 /* Adds cache entry to the ID cache list. If needed reallocates memory
 467    for the list. */
 468
 469 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 470 {
 471   int i;
 472
 473   /* Try to add to static cache */
 474   if (!list->cache_dyn_count)
 475     for (i = 0; i < sizeof(list->cache); i++) {
 476       if (!list->cache[i]) {
 477         list->cache[i] = cache;
 478         list->cache_count++;
 479         return;
 480       }
 481     }
 482
 483   /* Static cache is full, allocate dynamic cache */
 484   for (i = 0; i < list->cache_dyn_count; i++) {
 485     if (!list->cache_dyn[i]) {
 486       list->cache_dyn[i] = cache;
 487       list->cache_count++;
 488       break;
 489     }
 490   }
 491
 492   if (i >= list->cache_dyn_count) {
 493     int k;
 494
 495     i += 5;
 496     list->cache_dyn = silc_realloc(list->cache_dyn,
 497                                    sizeof(*list->cache) * (i));
 498
 499     /* NULL the reallocated area */
 500     for (k = list->cache_dyn_count; k < i; k++)
 501       list->cache_dyn[k] = NULL;
 502
 503     list->cache_dyn[list->cache_dyn_count] = cache;
 504     list->cache_dyn_count = i;
 505     list->cache_count++;
 506   }
 507 }
 508
 509 /* Returns number of cache entries in the ID cache list. */
 510
 511 int silc_idcache_list_count(SilcIDCacheList list)
 512 {
 513   return list->cache_count;
 514 }
 515
 516 /* Returns first entry from the ID cache list. */
 517
 518 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 519 {
 520   list->pos = 0;
 521
 522   if (!list->cache[list->pos])
 523     return FALSE;
 524
 525   if (ret)
 526     *ret = list->cache[list->pos];
 527
 528   return TRUE;
 529 }
 530
 531 /* Returns next entry from the ID cache list. */
 532
 533 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 534 {
 535   int dyn = FALSE;
 536   list->pos++;
 537
 538   if (list->pos >= sizeof(list->cache)) {
 539     list->pos = 0;
 540     dyn = TRUE;
 541   }
 542
 543   if (dyn && list->pos >= list->cache_dyn_count)
 544     return FALSE;
 545
 546   if (!dyn && !list->cache[list->pos])
 547     return FALSE;
 548
 549   if (dyn && !list->cache_dyn[list->pos])
 550     return FALSE;
 551
 552   if (ret) {
 553     if (!dyn)
 554       *ret = list->cache[list->pos];
 555     else
 556       *ret = list->cache_dyn[list->pos];
 557   }
 558
 559   return TRUE;
 560 }
 561
 562 /* Free's ID cache list. User must free the list object returned by
 563    any of the searching functions. */
 564
 565 void silc_idcache_list_free(SilcIDCacheList list)
 566 {
 567   if (list) {
 568     if (list->cache_dyn)
 569       silc_free(list->cache_dyn);
 570     silc_free(list);
 571   }
 572 }