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