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    unsigned int 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   unsigned int 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   unsigned int cache_dyn_count;
  98   unsigned int cache_count;
  99   unsigned int 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(unsigned int 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, strlen(cache->cache[i].data)))
 204       silc_idcache_list_add(list, &(cache->cache[i]));
 205   }
 206
 207   if (!silc_idcache_list_count(list))
 208     return FALSE;
 209
 210   if (ret)
 211     *ret = list;
 212   else
 213     silc_idcache_list_free(list);
 214
 215   return TRUE;
 216 }
 217
 218 /* Find ID Cache entry by data. The data maybe anything that must
 219    match exactly. Returns one cache entry. */
 220
 221 int silc_idcache_find_by_data_one(SilcIDCache cache, unsigned char *data,
 222                                   SilcIDCacheEntry *ret)
 223 {
 224   int i;
 225
 226   if (!cache || !cache->cache || !data)
 227     return FALSE;
 228
 229   if (cache->sorted)
 230     i = cache->fast_access[(int)data[0]];
 231   else
 232     i = 0;
 233
 234   if (i == -1)
 235     i = 0;
 236
 237   for (i = i; i < cache->cache_count; i++)
 238     if (cache->cache[i].data &&
 239         !memcmp(cache->cache[i].data, data, strlen(cache->cache[i].data))) {
 240       if (ret)
 241         *ret = &(cache->cache[i]);
 242       return TRUE;
 243     }
 244
 245   return FALSE;
 246 }
 247
 248 /* Find ID Cache entry by data, loosely. The data don't have to be 100%
 249    match. This ignores data case-sensitivity when searching with this
 250    function. Returns list of cache entries. */
 251
 252 int silc_idcache_find_by_data_loose(SilcIDCache cache, unsigned char *data,
 253                                     SilcIDCacheList *ret)
 254 {
 255   int i, c;
 256   SilcIDCacheList list;
 257
 258   if (!cache || !cache->cache || !data)
 259     return FALSE;
 260
 261   list = silc_idcache_list_alloc();
 262
 263   c = tolower((int)data[0]);
 264
 265   if (cache->sorted)
 266     i = cache->fast_access[c];
 267   else
 268     i = 0;
 269
 270   if (i == -1)
 271     i = 0;
 272
 273   for (i = i; i < cache->cache_count; i++) {
 274     if (cache->sorted && cache->cache[i].data &&
 275         cache->cache[i].data[0] != (char)c)
 276       break;
 277
 278     if (cache->cache[i].data &&
 279         !strcasecmp(cache->cache[i].data, data))
 280       silc_idcache_list_add(list, &(cache->cache[i]));
 281   }
 282
 283   if (cache->sorted) {
 284     c = toupper((int)data[0]);
 285     i = cache->fast_access[c];
 286
 287     for (i = i; i < cache->cache_count; i++) {
 288       if (cache->sorted && cache->cache[i].data &&
 289           cache->cache[i].data[0] != (char)c)
 290         break;
 291
 292       if (cache->cache[i].data &&
 293           !strcasecmp(cache->cache[i].data, data))
 294         silc_idcache_list_add(list, &(cache->cache[i]));
 295     }
 296   }
 297
 298   if (!silc_idcache_list_count(list))
 299     return FALSE;
 300
 301   if (ret)
 302     *ret = list;
 303   else
 304     silc_idcache_list_free(list);
 305
 306   return TRUE;
 307 }
 308
 309 /* Find ID Cache entry by ID. Returns list of cache entries. If `id' is
 310    SILC_ID_CACHE_ANY this returns all ID's of type `type'. */
 311
 312 int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
 313                             SilcIDCacheList *ret)
 314 {
 315   int i, id_len;
 316   SilcIDCacheList list;
 317
 318   if (!cache || !cache->cache || !id)
 319     return FALSE;
 320
 321   id_len = silc_id_get_len(type);
 322
 323   list = silc_idcache_list_alloc();
 324
 325   if (id != SILC_ID_CACHE_ANY) {
 326     for (i = 0; i < cache->cache_count; i++)
 327       if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len))
 328         silc_idcache_list_add(list, &(cache->cache[i]));
 329   } else {
 330     for (i = 0; i < cache->cache_count; i++)
 331       if (cache->cache[i].id && cache->cache[i].type == type)
 332         silc_idcache_list_add(list, &(cache->cache[i]));
 333   }
 334
 335   if (!silc_idcache_list_count(list))
 336     return FALSE;
 337
 338   if (ret)
 339     *ret = list;
 340   else
 341     silc_idcache_list_free(list);
 342
 343   return TRUE;
 344 }
 345
 346 /* Find ID Cache entry by ID. Returns one cache entry. */
 347
 348 int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
 349                                 SilcIDCacheEntry *ret)
 350 {
 351   int i, id_len;
 352
 353   if (!cache || !cache->cache || !id)
 354     return FALSE;
 355
 356   id_len = silc_id_get_len(type);
 357
 358   for (i = 0; i < cache->cache_count; i++)
 359     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 360       if (ret)
 361         *ret = &(cache->cache[i]);
 362       return TRUE;
 363     }
 364
 365   return FALSE;
 366 }
 367
 368 /* Finds cache entry by context. */
 369
 370 int silc_idcache_find_by_context(SilcIDCache cache, void *context,
 371                                  SilcIDCacheEntry *ret)
 372 {
 373   int i;
 374
 375   if (!cache || !cache->cache || !context)
 376     return FALSE;
 377
 378   for (i = 0; i < cache->cache_count; i++)
 379     if (cache->cache[i].context && cache->cache[i].context == context) {
 380       if (ret)
 381         *ret = &(cache->cache[i]);
 382       return TRUE;
 383     }
 384
 385   return FALSE;
 386 }
 387
 388 /* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
 389    then the cache is sorted after the new entry has been added. The
 390    cache must be sorted in order for the fast access feature to work,
 391    however, it is not mandatory. */
 392
 393 int silc_idcache_add(SilcIDCache cache, unsigned char *data,
 394                      SilcIdType id_type, void *id, void *context, int sort,
 395                      int expire)
 396 {
 397   int i;
 398   unsigned int count;
 399   unsigned long curtime = time(NULL);
 400   SilcIDCacheEntry c;
 401
 402   if (!cache || !cache->cache)
 403     return FALSE;
 404
 405   SILC_LOG_DEBUG(("Adding cache entry"));
 406
 407   c = cache->cache;
 408   count = cache->cache_count;
 409
 410   if (c == NULL) {
 411     c = silc_calloc(5, sizeof(*c));
 412     count = 5;
 413   }
 414
 415   /* See if it exists already */
 416   /* XXX this slows down this function. */
 417   if (silc_idcache_find_by_id(cache, id, id_type, NULL))
 418     return FALSE;
 419
 420   for (i = 0; i < count; i++) {
 421     if (c[i].data == NULL && c[i].id == NULL) {
 422       c[i].data = data;
 423       c[i].type = id_type;
 424       c[i].id = id;
 425       c[i].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 426       c[i].context = context;
 427       break;
 428     }
 429   }
 430
 431   if (i == count) {
 432     c = silc_realloc(c, sizeof(*c) * (count + 5));
 433     for (i = count; i < count + 5; i++) {
 434       c[i].data = NULL;
 435       c[i].id = NULL;
 436     }
 437     c[count].data = data;
 438     c[count].type = id_type;
 439     c[count].id = id;
 440     c[count].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 441     c[count].context = context;
 442     count += 5;
 443   }
 444
 445   cache->cache = c;
 446   cache->cache_count = count;
 447   cache->sorted = sort;
 448
 449   if (sort)
 450     silc_idcache_sort_by_data(cache);
 451
 452   return TRUE;
 453 }
 454
 455 /* Delete cache entry from cache. */
 456 /* XXX */
 457
 458 int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 459 {
 460
 461   return TRUE;
 462 }
 463
 464 /* XXX */
 465
 466 int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data)
 467 {
 468
 469   return TRUE;
 470 }
 471
 472 /* Deletes ID cache entry by ID. */
 473
 474 int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
 475 {
 476   int i, id_len;
 477
 478   if (!cache || !cache->cache || !id)
 479     return FALSE;
 480
 481   id_len = silc_id_get_len(type);
 482
 483   for (i = 0; i < cache->cache_count; i++)
 484     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 485       cache->cache[i].id = NULL;
 486       cache->cache[i].data = NULL;
 487       cache->cache[i].type = 0;
 488       cache->cache[i].context = NULL;
 489       return TRUE;
 490     }
 491
 492   return FALSE;
 493 }
 494
 495 /* Deletes all ID entries from cache. Free's memory as well. */
 496
 497 int silc_idcache_del_all(SilcIDCache cache)
 498 {
 499   if (!cache || !cache->cache)
 500     return FALSE;
 501
 502   silc_free(cache->cache);
 503   cache->cache = NULL;
 504   cache->cache_count = 0;
 505
 506   return TRUE;
 507 }
 508
 509 /* Purges the cache by removing expired cache entires. This does not
 510    free any memory though. */
 511
 512 int silc_idcache_purge(SilcIDCache cache)
 513 {
 514   SilcIDCacheEntry c;
 515   unsigned long curtime = time(NULL);
 516   int i;
 517
 518   if (!cache || !cache->cache)
 519     return FALSE;
 520
 521   c = cache->cache;
 522
 523   for (i = 0; i < cache->cache_count; i++) {
 524     if (c[i].data && c[i].expire < curtime) {
 525
 526       /* Call the destructor */
 527       if (cache->destructor)
 528         cache->destructor(cache, &c[i]);
 529
 530       c[i].id = NULL;
 531       c[i].data = NULL;
 532       c[i].type = 0;
 533       c[i].expire = 0;
 534       c[i].context = NULL;
 535     }
 536   }
 537
 538   return TRUE;
 539 }
 540
 541 /* Purges the specific entry by context. */
 542
 543 int silc_idcache_purge_by_context(SilcIDCache cache, void *context)
 544 {
 545   SilcIDCacheEntry entry;
 546
 547   if (!silc_idcache_find_by_context(cache, context, &entry))
 548     return FALSE;
 549
 550   /* Call the destructor */
 551   if (cache->destructor)
 552     cache->destructor(cache, entry);
 553
 554   entry->id = NULL;
 555   entry->data = NULL;
 556   entry->type = 0;
 557   entry->expire = 0;
 558   entry->context = NULL;
 559   return TRUE;
 560 }
 561
 562 /* Allocates ID cache list. */
 563
 564 static SilcIDCacheList silc_idcache_list_alloc()
 565 {
 566   SilcIDCacheList list;
 567
 568   list = silc_calloc(1, sizeof(*list));
 569
 570   return list;
 571 }
 572
 573 /* Adds cache entry to the ID cache list. If needed reallocates memory
 574    for the list. */
 575
 576 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 577 {
 578   int i;
 579
 580   /* Try to add to static cache */
 581   if (!list->cache_dyn_count)
 582     for (i = 0; i < sizeof(list->cache); i++) {
 583       if (!list->cache[i]) {
 584         list->cache[i] = cache;
 585         list->cache_count++;
 586         return;
 587       }
 588     }
 589
 590   /* Static cache is full, allocate dynamic cache */
 591   for (i = 0; i < list->cache_dyn_count; i++) {
 592     if (!list->cache_dyn[i]) {
 593       list->cache_dyn[i] = cache;
 594       list->cache_count++;
 595       break;
 596     }
 597   }
 598
 599   if (i >= list->cache_dyn_count) {
 600     int k;
 601
 602     i += 5;
 603     list->cache_dyn = silc_realloc(list->cache_dyn,
 604                                    sizeof(*list->cache) * (i));
 605
 606     /* NULL the reallocated area */
 607     for (k = list->cache_dyn_count; k < i; k++)
 608       list->cache_dyn[k] = NULL;
 609
 610     list->cache_dyn[list->cache_dyn_count] = cache;
 611     list->cache_dyn_count = i;
 612     list->cache_count++;
 613   }
 614 }
 615
 616 /* Returns number of cache entries in the ID cache list. */
 617
 618 int silc_idcache_list_count(SilcIDCacheList list)
 619 {
 620   return list->cache_count;
 621 }
 622
 623 /* Returns first entry from the ID cache list. */
 624
 625 int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 626 {
 627   list->pos = 0;
 628
 629   if (!list->cache[list->pos])
 630     return FALSE;
 631
 632   if (ret)
 633     *ret = list->cache[list->pos];
 634
 635   return TRUE;
 636 }
 637
 638 /* Returns next entry from the ID cache list. */
 639
 640 int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 641 {
 642   int dyn = FALSE;
 643   list->pos++;
 644
 645   if (list->pos >= sizeof(list->cache)) {
 646     list->pos = 0;
 647     dyn = TRUE;
 648   }
 649
 650   if (dyn && list->pos >= list->cache_dyn_count)
 651     return FALSE;
 652
 653   if (!dyn && !list->cache[list->pos])
 654     return FALSE;
 655
 656   if (dyn && !list->cache_dyn[list->pos])
 657     return FALSE;
 658
 659   if (ret) {
 660     if (!dyn)
 661       *ret = list->cache[list->pos];
 662     else
 663       *ret = list->cache_dyn[list->pos];
 664   }
 665
 666   return TRUE;
 667 }
 668
 669 /* Free's ID cache list. User must free the list object returned by
 670    any of the searching functions. */
 671
 672 void silc_idcache_list_free(SilcIDCacheList list)
 673 {
 674   if (list) {
 675     if (list->cache_dyn)
 676       silc_free(list->cache_dyn);
 677     silc_free(list);
 678   }
 679 }