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, cache->cache[i].data_len))
 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, cache->cache[i].data_len)) {
 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                      unsigned int data_len, SilcIdType id_type, void *id,
 395                      void *context, int sort, 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].data_len = data_len;
 424       c[i].type = id_type;
 425       c[i].id = id;
 426       c[i].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 427       c[i].context = context;
 428       break;
 429     }
 430   }
 431
 432   if (i == count) {
 433     c = silc_realloc(c, sizeof(*c) * (count + 5));
 434     for (i = count; i < count + 5; i++) {
 435       c[i].data = NULL;
 436       c[i].id = NULL;
 437     }
 438     c[count].data = data;
 439     c[count].data_len = data_len;
 440     c[count].type = id_type;
 441     c[count].id = id;
 442     c[count].expire = (expire ? (curtime + SILC_ID_CACHE_EXPIRE) : 0);
 443     c[count].context = context;
 444     count += 5;
 445   }
 446
 447   cache->cache = c;
 448   cache->cache_count = count;
 449   cache->sorted = sort;
 450
 451   if (sort)
 452     silc_idcache_sort_by_data(cache);
 453
 454   return TRUE;
 455 }
 456
 457 /* Delete cache entry from cache. */
 458 /* XXX */
 459
 460 int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 461 {
 462
 463   return TRUE;
 464 }
 465
 466 /* XXX */
 467
 468 int silc_idcache_del_by_data(SilcIDCache cache, unsigned char *data)
 469 {
 470
 471   return TRUE;
 472 }
 473
 474 /* Deletes ID cache entry by ID. */
 475
 476 int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
 477 {
 478   int i, id_len;
 479
 480   if (!cache || !cache->cache || !id)
 481     return FALSE;
 482
 483   id_len = silc_id_get_len(type);
 484
 485   for (i = 0; i < cache->cache_count; i++)
 486     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 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   unsigned long 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 }