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