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