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