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