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;
 320   SilcIDCacheList list;
 321
 322   if (!cache || !cache->cache || !id)
 323     return FALSE;
 324
 325   list = silc_idcache_list_alloc();
 326
 327   if (id != SILC_ID_CACHE_ANY) {
 328     for (i = 0; i < cache->cache_count; i++)
 329       if (cache->cache[i].id && silc_id_compare(cache->cache[i].id, id, type))
 330         silc_idcache_list_add(list, &(cache->cache[i]));
 331   } else {
 332     for (i = 0; i < cache->cache_count; i++)
 333       if (cache->cache[i].id && cache->cache[i].type == type)
 334         silc_idcache_list_add(list, &(cache->cache[i]));
 335   }
 336
 337   if (!silc_idcache_list_count(list)) {
 338     silc_idcache_list_free(list);
 339     return FALSE;
 340   }
 341
 342   if (ret)
 343     *ret = list;
 344   else
 345     silc_idcache_list_free(list);
 346
 347   return TRUE;
 348 }
 349
 350 /* Find ID Cache entry by ID. Returns one cache entry. */
 351
 352 int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
 353                                 SilcIDCacheEntry *ret)
 354 {
 355   int i;
 356
 357   if (!cache || !cache->cache || !id)
 358     return FALSE;
 359
 360   for (i = 0; i < cache->cache_count; i++)
 361     if (cache->cache[i].id && silc_id_compare(cache->cache[i].id, id, type)) {
 362       if (ret)
 363         *ret = &(cache->cache[i]);
 364       return TRUE;
 365     }
 366
 367   return FALSE;
 368 }
 369
 370 /* Finds cache entry by context. */
 371
 372 int silc_idcache_find_by_context(SilcIDCache cache, void *context,
 373                                  SilcIDCacheEntry *ret)
 374 {
 375   int i;
 376
 377   if (!cache || !cache->cache || !context)
 378     return FALSE;
 379
 380   for (i = 0; i < cache->cache_count; i++)
 381     if (cache->cache[i].context && cache->cache[i].context == context) {
 382       if (ret)
 383         *ret = &(cache->cache[i]);
 384       return TRUE;
 385     }
 386
 387   return FALSE;
 388 }
 389
 390 /* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
 391    then the cache is sorted after the new entry has been added. The
 392    cache must be sorted in order for the fast access feature to work,
 393    however, it is not mandatory. */
 394
 395 int silc_idcache_add(SilcIDCache cache, unsigned char *data,
 396                      uint32 data_len, SilcIdType id_type, void *id,
 397                      void *context, int sort, int expire)
 398 {
 399   int i;
 400   uint32 count;
 401   uint32 curtime = time(NULL);
 402   SilcIDCacheEntry c;
 403
 404   if (!cache || !cache->cache)
 405     return FALSE;
 406
 407   SILC_LOG_DEBUG(("Adding cache entry"));
 408
 409   c = cache->cache;
 410   count = cache->cache_count;
 411
 412   if (c == NULL) {
 413     c = silc_calloc(5, sizeof(*c));
 414     count = 5;
 415   }
 416
 417   /* See if it exists already */
 418   /* XXX this slows down this function. */
 419   if (silc_idcache_find_by_id(cache, id, id_type, NULL))
 420     return FALSE;
 421
 422   for (i = 0; i < count; i++) {
 423     if (c[i].data == NULL && c[i].id == NULL) {
 424       c[i].data = data;
 425       c[i].data_len = data_len;
 426       c[i].type = id_type;
 427       c[i].id = id;
 428       c[i].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 429       c[i].context = context;
 430       break;
 431     }
 432   }
 433
 434   if (i == count) {
 435     c = silc_realloc(c, sizeof(*c) * (count + 5));
 436     for (i = count; i < count + 5; i++) {
 437       c[i].data = NULL;
 438       c[i].id = NULL;
 439     }
 440     c[count].data = data;
 441     c[count].data_len = data_len;
 442     c[count].type = id_type;
 443     c[count].id = id;
 444     c[count].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 445     c[count].context = context;
 446     count += 5;
 447   }
 448
 449   cache->cache = c;
 450   cache->cache_count = count;
 451   cache->sorted = sort;
 452
 453   if (sort)
 454     silc_idcache_sort_by_data(cache);
 455
 456   return TRUE;
 457 }
 458
 459 /* Delete cache entry from cache. */
 460 /* XXX */
 461
 462 int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 463 {
 464
 465   return TRUE;
 466 }
 467
 468 /* XXX */
 469
 470 int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data)
 471 {
 472
 473   return TRUE;
 474 }
 475
 476 /* Deletes ID cache entry by ID. */
 477
 478 int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
 479 {
 480   int i;
 481
 482   if (!cache || !cache->cache || !id)
 483     return FALSE;
 484
 485   for (i = 0; i < cache->cache_count; i++)
 486     if (cache->cache[i].id && silc_id_compare(cache->cache[i].id, id, type)) {
 487       cache->cache[i].id = NULL;
 488       cache->cache[i].data = NULL;
 489       cache->cache[i].type = 0;
 490       cache->cache[i].context = NULL;
 491       return TRUE;
 492     }
 493
 494   return FALSE;
 495 }
 496
 497 /* Deletes all ID entries from cache. Free's memory as well. */
 498
 499 int silc_idcache_del_all(SilcIDCache cache)
 500 {
 501   if (!cache || !cache->cache)
 502     return FALSE;
 503
 504   silc_free(cache->cache);
 505   cache->cache = NULL;
 506   cache->cache_count = 0;
 507
 508   return TRUE;
 509 }
 510
 511 /* Purges the cache by removing expired cache entires. This does not
 512    free any memory though. */
 513
 514 int silc_idcache_purge(SilcIDCache cache)
 515 {
 516   SilcIDCacheEntry c;
 517   uint32 curtime = time(NULL);
 518   int i;
 519
 520   if (!cache || !cache->cache)
 521     return FALSE;
 522
 523   c = cache->cache;
 524
 525   for (i = 0; i < cache->cache_count; i++) {
 526     if (c[i].data && c[i].expire && c[i].expire < curtime) {
 527
 528       /* Call the destructor */
 529       if (cache->destructor)
 530         cache->destructor(cache, &c[i]);
 531
 532       c[i].id = NULL;
 533       c[i].data = NULL;
 534       c[i].type = 0;
 535       c[i].expire = 0;
 536       c[i].context = NULL;
 537     }
 538   }
 539
 540   return TRUE;
 541 }
 542
 543 /* Purges the specific entry by context. */
 544
 545 int silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 546 {
 547   SilcIDCacheEntry entry;
 548
 549   if (!silc_idcache_find_by_context(cache, context, &entry))
 550     return FALSE;
 551
 552   /* Call the destructor */
 553   if (cache->destructor)
 554     cache->destructor(cache, entry);
 555
 556   entry->id = NULL;
 557   entry->data = NULL;
 558   entry->type = 0;
 559   entry->expire = 0;
 560   entry->context = NULL;
 561   return TRUE;
 562 }
 563
 564 /* Allocates ID cache list. */
 565
 566 static SilcIDCacheList silc_idcache_list_alloc()
 567 {
 568   SilcIDCacheList list;
 569
 570   list = silc_calloc(1, sizeof(*list));
 571
 572   return list;
 573 }
 574
 575 /* Adds cache entry to the ID cache list. If needed reallocates memory
 576    for the list. */
 577
 578 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 579 {
 580   int i;
 581
 582   /* Try to add to static cache */
 583   if (!list->cache_dyn_count)
 584     for (i = 0; i < sizeof(list->cache); i++) {
 585       if (!list->cache[i]) {
 586         list->cache[i] = cache;
 587         list->cache_count++;
 588         return;
 589       }
 590     }
 591
 592   /* Static cache is full, allocate dynamic cache */
 593   for (i = 0; i < list->cache_dyn_count; i++) {
 594     if (!list->cache_dyn[i]) {
 595       list->cache_dyn[i] = cache;
 596       list->cache_count++;
 597       break;
 598     }
 599   }
 600
 601   if (i >= list->cache_dyn_count) {
 602     int k;
 603
 604     i += 5;
 605     list->cache_dyn = silc_realloc(list->cache_dyn,
 606                                    sizeof(*list->cache) * (i));
 607
 608     /* NULL the reallocated area */
 609     for (k = list->cache_dyn_count; k < i; k++)
 610       list->cache_dyn[k] = NULL;
 611
 612     list->cache_dyn[list->cache_dyn_count] = cache;
 613     list->cache_dyn_count = i;
 614     list->cache_count++;
 615   }
 616 }
 617
 618 /* Returns number of cache entries in the ID cache list. */
 619
 620 int silc_idcache_list_count(SilcIDCacheList list)
 621 {
 622   return list->cache_count;
 623 }
 624
 625 /* Returns first entry from the ID cache list. */
 626
 627 int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 628 {
 629   list->pos = 0;
 630
 631   if (!list->cache[list->pos])
 632     return FALSE;
 633
 634   if (ret)
 635     *ret = list->cache[list->pos];
 636
 637   return TRUE;
 638 }
 639
 640 /* Returns next entry from the ID cache list. */
 641
 642 int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 643 {
 644   int dyn = FALSE;
 645   list->pos++;
 646
 647   if (list->pos >= sizeof(list->cache)) {
 648     list->pos = 0;
 649     dyn = TRUE;
 650   }
 651
 652   if (dyn && list->pos >= list->cache_dyn_count)
 653     return FALSE;
 654
 655   if (!dyn && !list->cache[list->pos])
 656     return FALSE;
 657
 658   if (dyn && !list->cache_dyn[list->pos])
 659     return FALSE;
 660
 661   if (ret) {
 662     if (!dyn)
 663       *ret = list->cache[list->pos];
 664     else
 665       *ret = list->cache_dyn[list->pos];
 666   }
 667
 668   return TRUE;
 669 }
 670
 671 /* Free's ID cache list. User must free the list object returned by
 672    any of the searching functions. */
 673
 674 void silc_idcache_list_free(SilcIDCacheList list)
 675 {
 676   if (list) {
 677     if (list->cache_dyn)
 678       silc_free(list->cache_dyn);
 679     silc_free(list);
 680   }
 681 }