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 data_table
  46
  47        Hash table using the data 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 data_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->data_table = silc_hash_table_alloc(count, silc_hash_data, NULL,
 114                                             silc_hash_data_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->data_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, unsigned char *data,
 139                       uint32 data_len, void *id, void *context, int expire)
 140 {
 141   SilcIDCacheEntry c;
 142   uint32 curtime = time(NULL);
 143
 144   SILC_LOG_DEBUG(("Adding cache entry"));
 145
 146   /* See if entry with this ID already exists. */
 147   if (silc_hash_table_find(cache->id_table, id, NULL, NULL))
 148     return FALSE;
 149
 150   /* Allocate new cache entry */
 151   c = silc_calloc(1, sizeof(*c));
 152   c->data = data;
 153   c->data_len = data_len;
 154   c->id = id;
 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   silc_hash_table_add(cache->id_table, id, c);
 161   if (data)
 162     silc_hash_table_add_ext(cache->data_table, data, c,
 163                             silc_hash_data, (void *)data_len);
 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->data_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;
 191
 192   ret = silc_hash_table_del_by_context_ext(cache->data_table, old->data, old,
 193                                            silc_hash_data,
 194                                            (void *)old->data_len,
 195                                            silc_hash_data_compare,
 196                                            (void *)old->data_len);
 197   ret = silc_hash_table_del(cache->context_table, old->context);
 198   ret = silc_hash_table_del(cache->id_table, old->id);
 199
 200   return ret;
 201 }
 202
 203 /* Deletes ID cache entry by ID. */
 204
 205 bool silc_idcache_del_by_id(SilcIDCache cache, void *id)
 206 {
 207   SilcIDCacheEntry c;
 208
 209   if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c))
 210     return FALSE;
 211
 212   return silc_idcache_del(cache, c);
 213 }
 214
 215 /* Deletes ID cache entry by context. */
 216
 217 bool silc_idcache_del_by_context(SilcIDCache cache, void *context)
 218 {
 219   SilcIDCacheEntry c;
 220
 221   if (!silc_hash_table_find(cache->context_table, context, NULL, (void *)&c))
 222     return FALSE;
 223
 224   return silc_idcache_del(cache, c);
 225 }
 226
 227 /* Deletes all ID entries from cache. Free's memory as well. */
 228
 229 bool silc_idcache_del_all(SilcIDCache cache)
 230 {
 231   silc_hash_table_free(cache->id_table);
 232   silc_hash_table_free(cache->data_table);
 233   silc_hash_table_free(cache->context_table);
 234
 235   return TRUE;
 236 }
 237
 238 /* Foreach callback fro silc_idcache_purge. */
 239
 240 static void silc_idcache_purge_foreach(void *key, void *context,
 241                                        void *user_context)
 242 {
 243   SilcIDCache cache = (SilcIDCache)user_context;
 244   uint32 curtime = time(NULL);
 245   SilcIDCacheEntry c = (SilcIDCacheEntry)context;
 246
 247   if (c->expire && c->expire < curtime) {
 248     /* Call the destructor */
 249     if (cache->destructor)
 250       cache->destructor(cache, c);
 251
 252     /* Delete the entry */
 253     silc_idcache_del(cache, c);
 254   }
 255 }
 256
 257 /* Purges the cache by removing expired cache entires. Note that this
 258    may be very slow operation. */
 259
 260 bool silc_idcache_purge(SilcIDCache cache)
 261 {
 262   silc_hash_table_foreach(cache->id_table, silc_idcache_purge_foreach, cache);
 263   return TRUE;
 264 }
 265
 266 /* Purges the specific entry by context. */
 267
 268 bool silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 269 {
 270   SilcIDCacheEntry entry;
 271
 272   if (!silc_hash_table_find(cache->context_table, context, NULL,
 273                             (void *)&entry))
 274     return FALSE;
 275
 276   /* Call the destructor */
 277   if (cache->destructor)
 278     cache->destructor(cache, entry);
 279
 280   return silc_idcache_del(cache, entry);
 281 }
 282
 283 /* Callback that is called by the hash table routine when traversing
 284    entrys in the hash table. */
 285
 286 static void silc_idcache_get_all_foreach(void *key, void *context,
 287                                          void *user_context)
 288 {
 289   SilcIDCacheList list = (SilcIDCacheList)user_context;
 290   silc_idcache_list_add(list, (SilcIDCacheEntry)context);
 291 }
 292
 293 /* Returns all cache entrys from the ID cache to the `ret' ID Cache List. */
 294
 295 bool silc_idcache_get_all(SilcIDCache cache, SilcIDCacheList *ret)
 296 {
 297   SilcIDCacheList list;
 298
 299   if (!ret)
 300     return TRUE;
 301
 302   list = silc_idcache_list_alloc();
 303   silc_hash_table_foreach(cache->id_table, silc_idcache_get_all_foreach, list);
 304
 305   if (silc_idcache_list_count(list) == 0) {
 306     silc_idcache_list_free(list);
 307     return FALSE;
 308   }
 309
 310   *ret = list;
 311
 312   return TRUE;
 313 }
 314
 315 /* Find ID Cache entry by ID. */
 316
 317 bool silc_idcache_find_by_id(SilcIDCache cache, void *id,
 318                              SilcIDCacheEntry *ret)
 319 {
 320   return silc_hash_table_find(cache->id_table, id, NULL, (void *)ret);
 321 }
 322
 323 /* Finds cache entry by context. */
 324
 325 bool silc_idcache_find_by_context(SilcIDCache cache, void *context,
 326                                   SilcIDCacheEntry *ret)
 327 {
 328   return silc_hash_table_find(cache->context_table, context, NULL,
 329                               (void *)ret);
 330 }
 331
 332 /* Find ID Cache entry by data. The data maybe anything that must
 333    match exactly. Returns list of cache entries. */
 334
 335 bool silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
 336                                unsigned int data_len, SilcIDCacheList *ret)
 337 {
 338   SilcIDCacheList list;
 339
 340   list = silc_idcache_list_alloc();
 341
 342   if (!ret)
 343     return TRUE;
 344
 345   silc_hash_table_find_foreach_ext(cache->data_table, data,
 346                                    silc_hash_data, (void *)data_len,
 347                                    silc_hash_data_compare, (void *)data_len,
 348                                    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 data. The data maybe anything that must
 361    match exactly. Returns one cache entry. */
 362
 363 bool silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
 364                                    unsigned int data_len,
 365                                    SilcIDCacheEntry *ret)
 366 {
 367   SilcIDCacheEntry c;
 368
 369   if (!silc_hash_table_find_ext(cache->data_table, data, NULL, (void *)&c,
 370                                 silc_hash_data, (void *)data_len,
 371                                 silc_hash_data_compare, (void *)data_len))
 372     return FALSE;
 373
 374   if (ret)
 375     *ret = c;
 376
 377   return TRUE;
 378 }
 379
 380 /* Allocates ID cache list. */
 381
 382 static SilcIDCacheList silc_idcache_list_alloc()
 383 {
 384   SilcIDCacheList list;
 385
 386   list = silc_calloc(1, sizeof(*list));
 387
 388   return list;
 389 }
 390
 391 /* Adds cache entry to the ID cache list. If needed reallocates memory
 392    for the list. */
 393
 394 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 395 {
 396   int i;
 397
 398   /* Try to add to static cache */
 399   if (!list->cache_dyn_count)
 400     for (i = 0; i < sizeof(list->cache); i++) {
 401       if (!list->cache[i]) {
 402         list->cache[i] = cache;
 403         list->cache_count++;
 404         return;
 405       }
 406     }
 407
 408   /* Static cache is full, allocate dynamic cache */
 409   for (i = 0; i < list->cache_dyn_count; i++) {
 410     if (!list->cache_dyn[i]) {
 411       list->cache_dyn[i] = cache;
 412       list->cache_count++;
 413       break;
 414     }
 415   }
 416
 417   if (i >= list->cache_dyn_count) {
 418     int k;
 419
 420     i += 5;
 421     list->cache_dyn = silc_realloc(list->cache_dyn,
 422                                    sizeof(*list->cache) * (i));
 423
 424     /* NULL the reallocated area */
 425     for (k = list->cache_dyn_count; k < i; k++)
 426       list->cache_dyn[k] = NULL;
 427
 428     list->cache_dyn[list->cache_dyn_count] = cache;
 429     list->cache_dyn_count = i;
 430     list->cache_count++;
 431   }
 432 }
 433
 434 /* Returns number of cache entries in the ID cache list. */
 435
 436 int silc_idcache_list_count(SilcIDCacheList list)
 437 {
 438   return list->cache_count;
 439 }
 440
 441 /* Returns first entry from the ID cache list. */
 442
 443 bool silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 444 {
 445   list->pos = 0;
 446
 447   if (!list->cache[list->pos])
 448     return FALSE;
 449
 450   if (ret)
 451     *ret = list->cache[list->pos];
 452
 453   return TRUE;
 454 }
 455
 456 /* Returns next entry from the ID cache list. */
 457
 458 bool silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 459 {
 460   int dyn = FALSE;
 461   list->pos++;
 462
 463   if (list->pos >= sizeof(list->cache)) {
 464     list->pos = 0;
 465     dyn = TRUE;
 466   }
 467
 468   if (dyn && list->pos >= list->cache_dyn_count)
 469     return FALSE;
 470
 471   if (!dyn && !list->cache[list->pos])
 472     return FALSE;
 473
 474   if (dyn && !list->cache_dyn[list->pos])
 475     return FALSE;
 476
 477   if (ret) {
 478     if (!dyn)
 479       *ret = list->cache[list->pos];
 480     else
 481       *ret = list->cache_dyn[list->pos];
 482   }
 483
 484   return TRUE;
 485 }
 486
 487 /* Free's ID cache list. User must free the list object returned by
 488    any of the searching functions. */
 489
 490 void silc_idcache_list_free(SilcIDCacheList list)
 491 {
 492   if (list) {
 493     if (list->cache_dyn)
 494       silc_free(list->cache_dyn);
 495     silc_free(list);
 496   }
 497 }