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