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