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.4  2000/07/17 11:46:36  priikone
  24  *      Added debug logging
  25  *
  26  * Revision 1.3  2000/07/12 05:54:01  priikone
  27  *      Major rewrite of whole ID Cache system.
  28  *
  29  * Revision 1.2  2000/07/05 06:06:35  priikone
  30  *      Global cosmetic change.
  31  *
  32  * Revision 1.1.1.1  2000/06/27 11:36:55  priikone
  33  *      Imported from internal CVS/Added Log headers.
  34  *
  35  *
  36  */
  37
  38 #include "silcincludes.h"
  39 #include "idcache.h"
  40
  41 /* Static prototypes */
  42 static int silc_idcache_sorter(const void *a, const void *b);
  43 static SilcIDCacheList silc_idcache_list_alloc();
  44 static void silc_idcache_list_add(SilcIDCacheList list,
  45                                   SilcIDCacheEntry cache);
  46
  47 /*
  48    SILC ID Cache object.
  49
  50    This is context for the ID cache system. This includes all the cache
  51    entries and other internal data. This is read-only object and not
  52    visible outside this cache system.
  53
  54    Fields are as follows:
  55
  56    SilcIDCacheEntry cache
  57
  58        Table of the cache entries allocated by silc_idcache_add function.
  59        This table is reallocated when new entry is added into the cache.
  60
  61    unsigned int cache_count
  62
  63        Number of cache entries in the cache.
  64
  65    int sorted
  66
  67        Boolean value to indicate whether the cache is sorted or not. If
  68        cache is not sorted the fast access (described next) cannot be used.
  69        Sorting can be done by calling sorting function or when adding new
  70        entries to the cache.
  71
  72    int fast_access[];
  73
  74        Table to provide fast access into the cache by index. When searching
  75        by data this table is used to get the index to the first occurence
  76        of that data (or part of the data) in the cache. Purpose of this
  77        is to provide faster access to the cache when searching by data.
  78        This is updated by silc_idcache_add and sorting functions.
  79
  80 */
  81 struct SilcIDCacheStruct {
  82   SilcIDCacheEntry cache;
  83   unsigned int cache_count;
  84   int sorted;
  85   int fast_access[256];
  86 };
  87
  88 /*
  89    ID Cache list.
  90
  91    This is returned when searching the cache. Enumeration functions are
  92    provided to traverse the list; actually this is used as table not as
  93    list. :)
  94
  95    By default the found cache entries are saved into the static cache
  96    table to provide access without reallocation. However, if the static
  97    table is full, rest of the cache entries are dynamically allocated
  98    into `cache_dyn' table. Traversing functions automatically handles
  99    these situations.
 100
 101 */
 102 struct SilcIDCacheListStruct {
 103   SilcIDCacheEntry cache[64];
 104   SilcIDCacheEntry *cache_dyn;
 105   unsigned int cache_dyn_count;
 106   unsigned int cache_count;
 107   unsigned int pos;
 108 };
 109
 110 /* Allocates new ID cache object. The initial amount of allocated entries
 111    can be sent as argument. If `count' is 0 the system uses default values. */
 112
 113 SilcIDCache silc_idcache_alloc(unsigned int count)
 114 {
 115   SilcIDCache cache;
 116
 117   SILC_LOG_DEBUG(("Allocating new cache"));
 118
 119   cache = silc_calloc(1, sizeof(*cache));
 120   cache->cache = silc_calloc(count ? count : 5, sizeof(*cache->cache));
 121   cache->cache_count = count ? count : 5;
 122   memset(cache->fast_access, -1, sizeof(cache->fast_access));
 123
 124   return cache;
 125 }
 126
 127 /* Free's ID cache object and cache entries */
 128
 129 void silc_idcache_free(SilcIDCache cache)
 130 {
 131   if (cache) {
 132     silc_free(cache->cache);
 133     silc_free(cache);
 134   }
 135 }
 136
 137 /* qsort() sorter function. */
 138
 139 static int silc_idcache_sorter(const void *a, const void *b)
 140 {
 141   SilcIDCacheEntry a1, b1;
 142
 143   a1 = (SilcIDCacheEntry)a;
 144   b1 = (SilcIDCacheEntry)b;
 145
 146   if (!a1->data && !b1->data)
 147     return 0;
 148
 149   if (!a1->data)
 150     return -1;
 151
 152   if (!b1->data)
 153     return 1;
 154
 155   return a1->data[0] - b1->data[0];
 156 }
 157
 158 /* Sorts given cache by data. After sorting this updates the fast access
 159    table that can be used to access the cache faster. */
 160
 161 void silc_idcache_sort_by_data(SilcIDCache cache)
 162 {
 163   int i;
 164
 165   qsort(cache->cache, cache->cache_count,
 166         sizeof(*cache->cache), silc_idcache_sorter);
 167
 168   memset(cache->fast_access, -1, sizeof(cache->fast_access));
 169
 170   /* Update the fast access table (this of course takes its own time when
 171      the cache is very large). */
 172   for (i = 0; i < cache->cache_count; i++) {
 173     if (cache->cache[i].data &&
 174         cache->fast_access[(int)cache->cache[i].data[0]] == -1)
 175       cache->fast_access[(int)cache->cache[i].data[0]] = i;
 176   }
 177
 178   cache->sorted = TRUE;
 179 }
 180
 181 /* Find ID Cache entry by data. The data maybe anything that must
 182    match exactly. Returns list of cache entries. */
 183
 184 int silc_idcache_find_by_data(SilcIDCache cache, char *data,
 185                               SilcIDCacheList *ret)
 186 {
 187   int i;
 188   SilcIDCacheList list;
 189
 190   if (!cache || !cache->cache || !data)
 191     return FALSE;
 192
 193   list = silc_idcache_list_alloc();
 194
 195   if (cache->sorted)
 196     i = cache->fast_access[(int)data[0]];
 197   else
 198     i = 0;
 199
 200   for (i = i; i < cache->cache_count; i++) {
 201     if (cache->sorted && cache->cache[i].data &&
 202         cache->cache[i].data[0] != data[0])
 203       break;
 204
 205     if (cache->cache[i].data &&
 206         !memcmp(cache->cache[i].data, data, strlen(data)))
 207       silc_idcache_list_add(list, &(cache->cache[i]));
 208   }
 209
 210   if (!silc_idcache_list_count(list))
 211     return FALSE;
 212
 213   if (ret)
 214     *ret = list;
 215   else
 216     silc_idcache_list_free(list);
 217
 218   return TRUE;
 219 }
 220
 221 /* Find ID Cache entry by data. The data maybe anything that must
 222    match exactly. Returns one cache entry. */
 223
 224 int silc_idcache_find_by_data_one(SilcIDCache cache, char *data,
 225                                   SilcIDCacheEntry *ret)
 226 {
 227   int i;
 228
 229   if (!cache || !cache->cache || !data)
 230     return FALSE;
 231
 232   if (cache->sorted)
 233     i = cache->fast_access[(int)data[0]];
 234   else
 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, strlen(data))) {
 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, 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   for (i = i; i < cache->cache_count; i++) {
 271     if (cache->sorted && cache->cache[i].data &&
 272         cache->cache[i].data[0] != (char)c)
 273       break;
 274
 275     if (cache->cache[i].data &&
 276         !strcasecmp(cache->cache[i].data, data))
 277       silc_idcache_list_add(list, &(cache->cache[i]));
 278   }
 279
 280   if (cache->sorted) {
 281     c = toupper((int)data[0]);
 282     i = cache->fast_access[c];
 283
 284     for (i = i; i < cache->cache_count; i++) {
 285       if (cache->sorted && cache->cache[i].data &&
 286           cache->cache[i].data[0] != (char)c)
 287         break;
 288
 289       if (cache->cache[i].data &&
 290           !strcasecmp(cache->cache[i].data, data))
 291         silc_idcache_list_add(list, &(cache->cache[i]));
 292     }
 293   }
 294
 295   if (!silc_idcache_list_count(list))
 296     return FALSE;
 297
 298   if (ret)
 299     *ret = list;
 300   else
 301     silc_idcache_list_free(list);
 302
 303   return TRUE;
 304 }
 305
 306 /* Find ID Cache entry by ID. Returns list of cache entries. */
 307 /* XXX this may be useless, need for list really? */
 308
 309 int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
 310                             SilcIDCacheList *ret)
 311 {
 312   int i, id_len;
 313   SilcIDCacheList list;
 314
 315   if (!cache || !cache->cache || !id)
 316     return FALSE;
 317
 318   id_len = silc_id_get_len(type);
 319
 320   list = silc_idcache_list_alloc();
 321
 322   for (i = 0; i < cache->cache_count; i++)
 323     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len))
 324       silc_idcache_list_add(list, &(cache->cache[i]));
 325
 326   if (!silc_idcache_list_count(list))
 327     return FALSE;
 328
 329   if (ret)
 330     *ret = list;
 331   else
 332     silc_idcache_list_free(list);
 333
 334   return TRUE;
 335 }
 336
 337 /* Find ID Cache entry by ID. Returns one cache entry. */
 338
 339 int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
 340                                 SilcIDCacheEntry *ret)
 341 {
 342   int i, id_len;
 343
 344   if (!cache || !cache->cache || !id)
 345     return FALSE;
 346
 347   id_len = silc_id_get_len(type);
 348
 349   for (i = 0; i < cache->cache_count; i++)
 350     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 351       if (ret)
 352         *ret = &(cache->cache[i]);
 353       return TRUE;
 354     }
 355
 356   return FALSE;
 357 }
 358
 359 /* Finds cache entry by context. */
 360
 361 int silc_idcache_find_by_context(SilcIDCache cache, void *context,
 362                                  SilcIDCacheEntry *ret)
 363 {
 364   int i;
 365
 366   if (!cache || !cache->cache || !context)
 367     return FALSE;
 368
 369   for (i = 0; i < cache->cache_count; i++)
 370     if (cache->cache[i].context && cache->cache[i].context == context) {
 371       if (ret)
 372         *ret = &(cache->cache[i]);
 373       return TRUE;
 374     }
 375
 376   return FALSE;
 377 }
 378
 379 /* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
 380    then the cache is sorted after the new entry has been added. The
 381    cache must be sorted in order for the fast access feature to work,
 382    however, it is not mandatory. */
 383
 384 int silc_idcache_add(SilcIDCache cache, char *data, 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) {
 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, 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 }