lib/silccore/idcache.c

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