lib/silccore/idcache.c

   1 /*
   2
   3   idcache.c
   4
   5   Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
   6
   7   Copyright (C) 2000 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 int silc_idcache_sorter(const void *a, const void *b);
  27 static SilcIDCacheList silc_idcache_list_alloc();
  28 static void silc_idcache_list_add(SilcIDCacheList list,
  29                                   SilcIDCacheEntry cache);
  30
  31 /*
  32    SILC ID Cache object.
  33
  34    This is context for the ID cache system. This includes all the cache
  35    entries and other internal data. This is read-only object and not
  36    visible outside this cache system.
  37
  38    Fields are as follows:
  39
  40    SilcIDCacheEntry cache
  41
  42        Table of the cache entries allocated by silc_idcache_add function.
  43        This table is reallocated when new entry is added into the cache.
  44
  45    uint32 cache_count
  46
  47        Number of cache entries in the cache.
  48
  49    int sorted
  50
  51        Boolean value to indicate whether the cache is sorted or not. If
  52        cache is not sorted the fast access (described next) cannot be used.
  53        Sorting can be done by calling sorting function or when adding new
  54        entries to the cache.
  55
  56    int fast_access[];
  57
  58        Table to provide fast access into the cache by index. When searching
  59        by data this table is used to get the index to the first occurence
  60        of that data (or part of the data) in the cache. Purpose of this
  61        is to provide faster access to the cache when searching by data.
  62        This is updated by silc_idcache_add and sorting functions.
  63
  64    SilcIDCacheDestructor destructor
  65
  66        Destructor callback that is called when an cache entry expires or is
  67        purged from the ID cache. The application must not free cache entry
  68        because the library will do it automatically. The appliation, however,
  69        is responsible of freeing any data in the entry.
  70
  71 */
  72 struct SilcIDCacheStruct {
  73   SilcIDCacheEntry cache;
  74   uint32 cache_count;
  75   int sorted;
  76   int fast_access[256];
  77   SilcIDCacheDestructor destructor;
  78 };
  79
  80 /*
  81    ID Cache list.
  82
  83    This is returned when searching the cache. Enumeration functions are
  84    provided to traverse the list; actually this is used as table not as
  85    list. :)
  86
  87    By default the found cache entries are saved into the static cache
  88    table to provide access without reallocation. However, if the static
  89    table is full, rest of the cache entries are dynamically allocated
  90    into `cache_dyn' table. Traversing functions automatically handles
  91    these situations.
  92
  93 */
  94 struct SilcIDCacheListStruct {
  95   SilcIDCacheEntry cache[64];
  96   SilcIDCacheEntry *cache_dyn;
  97   uint32 cache_dyn_count;
  98   uint32 cache_count;
  99   uint32 pos;
 100 };
 101
 102 /* Allocates new ID cache object. The initial amount of allocated entries
 103    can be sent as argument. If `count' is 0 the system uses default values. */
 104
 105 SilcIDCache silc_idcache_alloc(uint32 count,
 106                                SilcIDCacheDestructor destructor)
 107 {
 108   SilcIDCache cache;
 109
 110   SILC_LOG_DEBUG(("Allocating new cache"));
 111
 112   cache = silc_calloc(1, sizeof(*cache));
 113   cache->cache = silc_calloc(count ? count : 5, sizeof(*cache->cache));
 114   cache->cache_count = count ? count : 5;
 115   memset(cache->fast_access, -1, sizeof(cache->fast_access));
 116   cache->destructor = destructor;
 117
 118   return cache;
 119 }
 120
 121 /* Free's ID cache object and cache entries */
 122
 123 void silc_idcache_free(SilcIDCache cache)
 124 {
 125   if (cache) {
 126     silc_free(cache->cache);
 127     silc_free(cache);
 128   }
 129 }
 130
 131 /* qsort() sorter function. */
 132
 133 static int silc_idcache_sorter(const void *a, const void *b)
 134 {
 135   SilcIDCacheEntry a1, b1;
 136
 137   a1 = (SilcIDCacheEntry)a;
 138   b1 = (SilcIDCacheEntry)b;
 139
 140   if (!a1->data && !b1->data)
 141     return 0;
 142
 143   if (!a1->data)
 144     return -1;
 145
 146   if (!b1->data)
 147     return 1;
 148
 149   return a1->data[0] - b1->data[0];
 150 }
 151
 152 /* Sorts given cache by data. After sorting this updates the fast access
 153    table that can be used to access the cache faster. */
 154
 155 void silc_idcache_sort_by_data(SilcIDCache cache)
 156 {
 157   int i;
 158
 159   qsort(cache->cache, cache->cache_count,
 160         sizeof(*cache->cache), silc_idcache_sorter);
 161
 162   memset(cache->fast_access, -1, sizeof(cache->fast_access));
 163
 164   /* Update the fast access table (this of course takes its own time when
 165      the cache is very large). */
 166   for (i = 0; i < cache->cache_count; i++) {
 167     if (cache->cache[i].data &&
 168         cache->fast_access[(int)cache->cache[i].data[0]] == -1)
 169       cache->fast_access[(int)cache->cache[i].data[0]] = i;
 170   }
 171
 172   cache->sorted = TRUE;
 173 }
 174
 175 /* Find ID Cache entry by data. The data maybe anything that must
 176    match exactly. Returns list of cache entries. */
 177
 178 int silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data,
 179                               SilcIDCacheList *ret)
 180 {
 181   int i;
 182   SilcIDCacheList list;
 183
 184   if (!cache || !cache->cache || !data)
 185     return FALSE;
 186
 187   list = silc_idcache_list_alloc();
 188
 189   if (cache->sorted)
 190     i = cache->fast_access[(int)data[0]];
 191   else
 192     i = 0;
 193
 194   if (i == -1)
 195     i = 0;
 196
 197   for (i = i; i < cache->cache_count; i++) {
 198     if (cache->sorted && cache->cache[i].data &&
 199         cache->cache[i].data[0] != data[0])
 200       break;
 201
 202     if (cache->cache[i].data &&
 203         !memcmp(cache->cache[i].data, data, cache->cache[i].data_len))
 204       silc_idcache_list_add(list, &(cache->cache[i]));
 205   }
 206
 207   if (!silc_idcache_list_count(list)) {
 208     silc_idcache_list_free(list);
 209     return FALSE;
 210   }
 211
 212   if (ret)
 213     *ret = list;
 214   else
 215     silc_idcache_list_free(list);
 216
 217   return TRUE;
 218 }
 219
 220 /* Find ID Cache entry by data. The data maybe anything that must
 221    match exactly. Returns one cache entry. */
 222
 223 int silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
 224                                   SilcIDCacheEntry *ret)
 225 {
 226   int i;
 227
 228   if (!cache || !cache->cache || !data)
 229     return FALSE;
 230
 231   if (cache->sorted)
 232     i = cache->fast_access[(int)data[0]];
 233   else
 234     i = 0;
 235
 236   if (i == -1)
 237     i = 0;
 238
 239   for (i = i; i < cache->cache_count; i++)
 240     if (cache->cache[i].data &&
 241         !memcmp(cache->cache[i].data, data, cache->cache[i].data_len)) {
 242       if (ret)
 243         *ret = &(cache->cache[i]);
 244       return TRUE;
 245     }
 246
 247   return FALSE;
 248 }
 249
 250 /* Find ID Cache entry by data, loosely. The data don't have to be 100%
 251    match. This ignores data case-sensitivity when searching with this
 252    function. Returns list of cache entries. */
 253
 254 int silc_idcache_find_by_data_loose(SilcIDCache cache, unsigned char *data,
 255                                     SilcIDCacheList *ret)
 256 {
 257   int i, c;
 258   SilcIDCacheList list;
 259
 260   if (!cache || !cache->cache || !data)
 261     return FALSE;
 262
 263   list = silc_idcache_list_alloc();
 264
 265   c = tolower((int)data[0]);
 266
 267   if (cache->sorted)
 268     i = cache->fast_access[c];
 269   else
 270     i = 0;
 271
 272   if (i == -1)
 273     i = 0;
 274
 275   for (i = i; i < cache->cache_count; i++) {
 276     if (cache->sorted && cache->cache[i].data &&
 277         cache->cache[i].data[0] != (char)c)
 278       break;
 279
 280     if (cache->cache[i].data &&
 281         !strcasecmp(cache->cache[i].data, data))
 282       silc_idcache_list_add(list, &(cache->cache[i]));
 283   }
 284
 285   if (cache->sorted) {
 286     c = toupper((int)data[0]);
 287     i = cache->fast_access[c];
 288
 289     for (i = i; i < cache->cache_count; i++) {
 290       if (cache->sorted && cache->cache[i].data &&
 291           cache->cache[i].data[0] != (char)c)
 292         break;
 293
 294       if (cache->cache[i].data &&
 295           !strcasecmp(cache->cache[i].data, data))
 296         silc_idcache_list_add(list, &(cache->cache[i]));
 297     }
 298   }
 299
 300   if (!silc_idcache_list_count(list)) {
 301     silc_idcache_list_free(list);
 302     return FALSE;
 303   }
 304
 305   if (ret)
 306     *ret = list;
 307   else
 308     silc_idcache_list_free(list);
 309
 310   return TRUE;
 311 }
 312
 313 /* Find ID Cache entry by ID. Returns list of cache entries. If `id' is
 314    SILC_ID_CACHE_ANY this returns all ID's of type `type'. */
 315
 316 int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
 317                             SilcIDCacheList *ret)
 318 {
 319   int i, id_len;
 320   SilcIDCacheList list;
 321
 322   if (!cache || !cache->cache || !id)
 323     return FALSE;
 324
 325   id_len = silc_id_get_len(type);
 326
 327   list = silc_idcache_list_alloc();
 328
 329   if (id != SILC_ID_CACHE_ANY) {
 330     for (i = 0; i < cache->cache_count; i++)
 331       if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len))
 332         silc_idcache_list_add(list, &(cache->cache[i]));
 333   } else {
 334     for (i = 0; i < cache->cache_count; i++)
 335       if (cache->cache[i].id && cache->cache[i].type == type)
 336         silc_idcache_list_add(list, &(cache->cache[i]));
 337   }
 338
 339   if (!silc_idcache_list_count(list)) {
 340     silc_idcache_list_free(list);
 341     return FALSE;
 342   }
 343
 344   if (ret)
 345     *ret = list;
 346   else
 347     silc_idcache_list_free(list);
 348
 349   return TRUE;
 350 }
 351
 352 /* Find ID Cache entry by ID. Returns one cache entry. */
 353
 354 int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
 355                                 SilcIDCacheEntry *ret)
 356 {
 357   int i, id_len;
 358
 359   if (!cache || !cache->cache || !id)
 360     return FALSE;
 361
 362   id_len = silc_id_get_len(type);
 363
 364   for (i = 0; i < cache->cache_count; i++)
 365     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 366       if (ret)
 367         *ret = &(cache->cache[i]);
 368       return TRUE;
 369     }
 370
 371   return FALSE;
 372 }
 373
 374 /* Finds cache entry by context. */
 375
 376 int silc_idcache_find_by_context(SilcIDCache cache, void *context,
 377                                  SilcIDCacheEntry *ret)
 378 {
 379   int i;
 380
 381   if (!cache || !cache->cache || !context)
 382     return FALSE;
 383
 384   for (i = 0; i < cache->cache_count; i++)
 385     if (cache->cache[i].context && cache->cache[i].context == context) {
 386       if (ret)
 387         *ret = &(cache->cache[i]);
 388       return TRUE;
 389     }
 390
 391   return FALSE;
 392 }
 393
 394 /* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
 395    then the cache is sorted after the new entry has been added. The
 396    cache must be sorted in order for the fast access feature to work,
 397    however, it is not mandatory. */
 398
 399 int silc_idcache_add(SilcIDCache cache, unsigned char *data,
 400                      uint32 data_len, SilcIdType id_type, void *id,
 401                      void *context, int sort, int expire)
 402 {
 403   int i;
 404   uint32 count;
 405   uint32 curtime = time(NULL);
 406   SilcIDCacheEntry c;
 407
 408   if (!cache || !cache->cache)
 409     return FALSE;
 410
 411   SILC_LOG_DEBUG(("Adding cache entry"));
 412
 413   c = cache->cache;
 414   count = cache->cache_count;
 415
 416   if (c == NULL) {
 417     c = silc_calloc(5, sizeof(*c));
 418     count = 5;
 419   }
 420
 421   /* See if it exists already */
 422   /* XXX this slows down this function. */
 423   if (silc_idcache_find_by_id(cache, id, id_type, NULL))
 424     return FALSE;
 425
 426   for (i = 0; i < count; i++) {
 427     if (c[i].data == NULL && c[i].id == NULL) {
 428       c[i].data = data;
 429       c[i].data_len = data_len;
 430       c[i].type = id_type;
 431       c[i].id = id;
 432       c[i].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 433       c[i].context = context;
 434       break;
 435     }
 436   }
 437
 438   if (i == count) {
 439     c = silc_realloc(c, sizeof(*c) * (count + 5));
 440     for (i = count; i < count + 5; i++) {
 441       c[i].data = NULL;
 442       c[i].id = NULL;
 443     }
 444     c[count].data = data;
 445     c[count].data_len = data_len;
 446     c[count].type = id_type;
 447     c[count].id = id;
 448     c[count].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 449     c[count].context = context;
 450     count += 5;
 451   }
 452
 453   cache->cache = c;
 454   cache->cache_count = count;
 455   cache->sorted = sort;
 456
 457   if (sort)
 458     silc_idcache_sort_by_data(cache);
 459
 460   return TRUE;
 461 }
 462
 463 /* Delete cache entry from cache. */
 464 /* XXX */
 465
 466 int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 467 {
 468
 469   return TRUE;
 470 }
 471
 472 /* XXX */
 473
 474 int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data)
 475 {
 476
 477   return TRUE;
 478 }
 479
 480 /* Deletes ID cache entry by ID. */
 481
 482 int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
 483 {
 484   int i, id_len;
 485
 486   if (!cache || !cache->cache || !id)
 487     return FALSE;
 488
 489   id_len = silc_id_get_len(type);
 490
 491   for (i = 0; i < cache->cache_count; i++)
 492     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 493       cache->cache[i].id = NULL;
 494       cache->cache[i].data = NULL;
 495       cache->cache[i].type = 0;
 496       cache->cache[i].context = NULL;
 497       return TRUE;
 498     }
 499
 500   return FALSE;
 501 }
 502
 503 /* Deletes all ID entries from cache. Free's memory as well. */
 504
 505 int silc_idcache_del_all(SilcIDCache cache)
 506 {
 507   if (!cache || !cache->cache)
 508     return FALSE;
 509
 510   silc_free(cache->cache);
 511   cache->cache = NULL;
 512   cache->cache_count = 0;
 513
 514   return TRUE;
 515 }
 516
 517 /* Purges the cache by removing expired cache entires. This does not
 518    free any memory though. */
 519
 520 int silc_idcache_purge(SilcIDCache cache)
 521 {
 522   SilcIDCacheEntry c;
 523   uint32 curtime = time(NULL);
 524   int i;
 525
 526   if (!cache || !cache->cache)
 527     return FALSE;
 528
 529   c = cache->cache;
 530
 531   for (i = 0; i < cache->cache_count; i++) {
 532     if (c[i].data && c[i].expire && c[i].expire < curtime) {
 533
 534       /* Call the destructor */
 535       if (cache->destructor)
 536         cache->destructor(cache, &c[i]);
 537
 538       c[i].id = NULL;
 539       c[i].data = NULL;
 540       c[i].type = 0;
 541       c[i].expire = 0;
 542       c[i].context = NULL;
 543     }
 544   }
 545
 546   return TRUE;
 547 }
 548
 549 /* Purges the specific entry by context. */
 550
 551 int silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 552 {
 553   SilcIDCacheEntry entry;
 554
 555   if (!silc_idcache_find_by_context(cache, context, &entry))
 556     return FALSE;
 557
 558   /* Call the destructor */
 559   if (cache->destructor)
 560     cache->destructor(cache, entry);
 561
 562   entry->id = NULL;
 563   entry->data = NULL;
 564   entry->type = 0;
 565   entry->expire = 0;
 566   entry->context = NULL;
 567   return TRUE;
 568 }
 569
 570 /* Allocates ID cache list. */
 571
 572 static SilcIDCacheList silc_idcache_list_alloc()
 573 {
 574   SilcIDCacheList list;
 575
 576   list = silc_calloc(1, sizeof(*list));
 577
 578   return list;
 579 }
 580
 581 /* Adds cache entry to the ID cache list. If needed reallocates memory
 582    for the list. */
 583
 584 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 585 {
 586   int i;
 587
 588   /* Try to add to static cache */
 589   if (!list->cache_dyn_count)
 590     for (i = 0; i < sizeof(list->cache); i++) {
 591       if (!list->cache[i]) {
 592         list->cache[i] = cache;
 593         list->cache_count++;
 594         return;
 595       }
 596     }
 597
 598   /* Static cache is full, allocate dynamic cache */
 599   for (i = 0; i < list->cache_dyn_count; i++) {
 600     if (!list->cache_dyn[i]) {
 601       list->cache_dyn[i] = cache;
 602       list->cache_count++;
 603       break;
 604     }
 605   }
 606
 607   if (i >= list->cache_dyn_count) {
 608     int k;
 609
 610     i += 5;
 611     list->cache_dyn = silc_realloc(list->cache_dyn,
 612                                    sizeof(*list->cache) * (i));
 613
 614     /* NULL the reallocated area */
 615     for (k = list->cache_dyn_count; k < i; k++)
 616       list->cache_dyn[k] = NULL;
 617
 618     list->cache_dyn[list->cache_dyn_count] = cache;
 619     list->cache_dyn_count = i;
 620     list->cache_count++;
 621   }
 622 }
 623
 624 /* Returns number of cache entries in the ID cache list. */
 625
 626 int silc_idcache_list_count(SilcIDCacheList list)
 627 {
 628   return list->cache_count;
 629 }
 630
 631 /* Returns first entry from the ID cache list. */
 632
 633 int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 634 {
 635   list->pos = 0;
 636
 637   if (!list->cache[list->pos])
 638     return FALSE;
 639
 640   if (ret)
 641     *ret = list->cache[list->pos];
 642
 643   return TRUE;
 644 }
 645
 646 /* Returns next entry from the ID cache list. */
 647
 648 int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 649 {
 650   int dyn = FALSE;
 651   list->pos++;
 652
 653   if (list->pos >= sizeof(list->cache)) {
 654     list->pos = 0;
 655     dyn = TRUE;
 656   }
 657
 658   if (dyn && list->pos >= list->cache_dyn_count)
 659     return FALSE;
 660
 661   if (!dyn && !list->cache[list->pos])
 662     return FALSE;
 663
 664   if (dyn && !list->cache_dyn[list->pos])
 665     return FALSE;
 666
 667   if (ret) {
 668     if (!dyn)
 669       *ret = list->cache[list->pos];
 670     else
 671       *ret = list->cache_dyn[list->pos];
 672   }
 673
 674   return TRUE;
 675 }
 676
 677 /* Free's ID cache list. User must free the list object returned by
 678    any of the searching functions. */
 679
 680 void silc_idcache_list_free(SilcIDCacheList list)
 681 {
 682   if (list) {
 683     if (list->cache_dyn)
 684       silc_free(list->cache_dyn);
 685     silc_free(list);
 686   }
 687 }