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, 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   for (i = i; i < cache->cache_count; i++) {
 185     if (cache->sorted && cache->cache[i].data &&
 186         cache->cache[i].data[0] != data[0])
 187       break;
 188
 189     if (cache->cache[i].data &&
 190         !memcmp(cache->cache[i].data, data, strlen(cache->cache[i].data)))
 191       silc_idcache_list_add(list, &(cache->cache[i]));
 192   }
 193
 194   if (!silc_idcache_list_count(list))
 195     return FALSE;
 196
 197   if (ret)
 198     *ret = list;
 199   else
 200     silc_idcache_list_free(list);
 201
 202   return TRUE;
 203 }
 204
 205 /* Find ID Cache entry by data. The data maybe anything that must
 206    match exactly. Returns one cache entry. */
 207
 208 int silc_idcache_find_by_data_one(SilcIDCache cache, char *data,
 209                                   SilcIDCacheEntry *ret)
 210 {
 211   int i;
 212
 213   if (!cache || !cache->cache || !data)
 214     return FALSE;
 215
 216   if (cache->sorted)
 217     i = cache->fast_access[(int)data[0]];
 218   else
 219     i = 0;
 220
 221   for (i = i; i < cache->cache_count; i++)
 222     if (cache->cache[i].data &&
 223         !memcmp(cache->cache[i].data, data, strlen(cache->cache[i].data))) {
 224       if (ret)
 225         *ret = &(cache->cache[i]);
 226       return TRUE;
 227     }
 228
 229   return FALSE;
 230 }
 231
 232 /* Find ID Cache entry by data, loosely. The data don't have to be 100%
 233    match. This ignores data case-sensitivity when searching with this
 234    function. Returns list of cache entries. */
 235
 236 int silc_idcache_find_by_data_loose(SilcIDCache cache, char *data,
 237                                     SilcIDCacheList *ret)
 238 {
 239   int i, c;
 240   SilcIDCacheList list;
 241
 242   if (!cache || !cache->cache || !data)
 243     return FALSE;
 244
 245   list = silc_idcache_list_alloc();
 246
 247   c = tolower((int)data[0]);
 248
 249   if (cache->sorted)
 250     i = cache->fast_access[c];
 251   else
 252     i = 0;
 253
 254   for (i = i; i < cache->cache_count; i++) {
 255     if (cache->sorted && cache->cache[i].data &&
 256         cache->cache[i].data[0] != (char)c)
 257       break;
 258
 259     if (cache->cache[i].data &&
 260         !strcasecmp(cache->cache[i].data, data))
 261       silc_idcache_list_add(list, &(cache->cache[i]));
 262   }
 263
 264   if (cache->sorted) {
 265     c = toupper((int)data[0]);
 266     i = cache->fast_access[c];
 267
 268     for (i = i; i < cache->cache_count; i++) {
 269       if (cache->sorted && cache->cache[i].data &&
 270           cache->cache[i].data[0] != (char)c)
 271         break;
 272
 273       if (cache->cache[i].data &&
 274           !strcasecmp(cache->cache[i].data, data))
 275         silc_idcache_list_add(list, &(cache->cache[i]));
 276     }
 277   }
 278
 279   if (!silc_idcache_list_count(list))
 280     return FALSE;
 281
 282   if (ret)
 283     *ret = list;
 284   else
 285     silc_idcache_list_free(list);
 286
 287   return TRUE;
 288 }
 289
 290 /* Find ID Cache entry by ID. Returns list of cache entries. If `id' is
 291    SILC_ID_CACHE_ANY this returns all ID's of type `type'. */
 292
 293 int silc_idcache_find_by_id(SilcIDCache cache, void *id, SilcIdType type,
 294                             SilcIDCacheList *ret)
 295 {
 296   int i, id_len;
 297   SilcIDCacheList list;
 298
 299   if (!cache || !cache->cache || !id)
 300     return FALSE;
 301
 302   id_len = silc_id_get_len(type);
 303
 304   list = silc_idcache_list_alloc();
 305
 306   if (id != SILC_ID_CACHE_ANY) {
 307     for (i = 0; i < cache->cache_count; i++)
 308       if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len))
 309         silc_idcache_list_add(list, &(cache->cache[i]));
 310   } else {
 311     for (i = 0; i < cache->cache_count; i++)
 312       if (cache->cache[i].id && cache->cache[i].type == type)
 313         silc_idcache_list_add(list, &(cache->cache[i]));
 314   }
 315
 316   if (!silc_idcache_list_count(list))
 317     return FALSE;
 318
 319   if (ret)
 320     *ret = list;
 321   else
 322     silc_idcache_list_free(list);
 323
 324   return TRUE;
 325 }
 326
 327 /* Find ID Cache entry by ID. Returns one cache entry. */
 328
 329 int silc_idcache_find_by_id_one(SilcIDCache cache, void *id, SilcIdType type,
 330                                 SilcIDCacheEntry *ret)
 331 {
 332   int i, id_len;
 333
 334   if (!cache || !cache->cache || !id)
 335     return FALSE;
 336
 337   id_len = silc_id_get_len(type);
 338
 339   for (i = 0; i < cache->cache_count; i++)
 340     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 341       if (ret)
 342         *ret = &(cache->cache[i]);
 343       return TRUE;
 344     }
 345
 346   return FALSE;
 347 }
 348
 349 /* Finds cache entry by context. */
 350
 351 int silc_idcache_find_by_context(SilcIDCache cache, void *context,
 352                                  SilcIDCacheEntry *ret)
 353 {
 354   int i;
 355
 356   if (!cache || !cache->cache || !context)
 357     return FALSE;
 358
 359   for (i = 0; i < cache->cache_count; i++)
 360     if (cache->cache[i].context && cache->cache[i].context == context) {
 361       if (ret)
 362         *ret = &(cache->cache[i]);
 363       return TRUE;
 364     }
 365
 366   return FALSE;
 367 }
 368
 369 /* Add new entry to the cache. Returns TRUE or FALSE. If `sort' is TRUE
 370    then the cache is sorted after the new entry has been added. The
 371    cache must be sorted in order for the fast access feature to work,
 372    however, it is not mandatory. */
 373
 374 int silc_idcache_add(SilcIDCache cache, char *data, SilcIdType id_type,
 375                      void *id, void *context, int sort)
 376 {
 377   int i;
 378   unsigned int count;
 379   unsigned long curtime = time(NULL);
 380   SilcIDCacheEntry c;
 381
 382   if (!cache || !cache->cache)
 383     return FALSE;
 384
 385   SILC_LOG_DEBUG(("Adding cache entry"));
 386
 387   c = cache->cache;
 388   count = cache->cache_count;
 389
 390   if (c == NULL) {
 391     c = silc_calloc(5, sizeof(*c));
 392     count = 5;
 393   }
 394
 395   /* See if it exists already */
 396   /* XXX this slows down this function. */
 397   if (silc_idcache_find_by_id(cache, id, id_type, NULL))
 398     return FALSE;
 399
 400   for (i = 0; i < count; i++) {
 401     if (c[i].data == NULL && c[i].id == NULL) {
 402       c[i].data = data;
 403       c[i].type = id_type;
 404       c[i].id = id;
 405       c[i].expire = curtime + SILC_ID_CACHE_EXPIRE;
 406       c[i].context = context;
 407       break;
 408     }
 409   }
 410
 411   if (i == count) {
 412     c = silc_realloc(c, sizeof(*c) * (count + 5));
 413     for (i = count; i < count + 5; i++) {
 414       c[i].data = NULL;
 415       c[i].id = NULL;
 416     }
 417     c[count].data = data;
 418     c[count].type = id_type;
 419     c[count].id = id;
 420     c[count].expire = curtime + SILC_ID_CACHE_EXPIRE;
 421     c[count].context = context;
 422     count += 5;
 423   }
 424
 425   cache->cache = c;
 426   cache->cache_count = count;
 427   cache->sorted = sort;
 428
 429   if (sort)
 430     silc_idcache_sort_by_data(cache);
 431
 432   return TRUE;
 433 }
 434
 435 /* Delete cache entry from cache. */
 436 /* XXX */
 437
 438 int silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old)
 439 {
 440
 441   return TRUE;
 442 }
 443
 444 /* XXX */
 445
 446 int silc_idcache_del_by_data(SilcIDCache cache, char *data)
 447 {
 448
 449   return TRUE;
 450 }
 451
 452 /* Deletes ID cache entry by ID. */
 453
 454 int silc_idcache_del_by_id(SilcIDCache cache, SilcIdType type, void *id)
 455 {
 456   int i, id_len;
 457
 458   if (!cache || !cache->cache || !id)
 459     return FALSE;
 460
 461   id_len = silc_id_get_len(type);
 462
 463   for (i = 0; i < cache->cache_count; i++)
 464     if (cache->cache[i].id && !memcmp(cache->cache[i].id, id, id_len)) {
 465       cache->cache[i].id = NULL;
 466       cache->cache[i].data = NULL;
 467       cache->cache[i].type = 0;
 468       cache->cache[i].context = NULL;
 469       return TRUE;
 470     }
 471
 472   return FALSE;
 473 }
 474
 475 /* Deletes all ID entries from cache. Free's memory as well. */
 476
 477 int silc_idcache_del_all(SilcIDCache cache)
 478 {
 479   if (!cache || !cache->cache)
 480     return FALSE;
 481
 482   silc_free(cache->cache);
 483   cache->cache = NULL;
 484   cache->cache_count = 0;
 485
 486   return TRUE;
 487 }
 488
 489 /* Purges the cache by removing expired cache entires. This does not
 490    free any memory though. */
 491
 492 int silc_idcache_purge(SilcIDCache cache)
 493 {
 494   SilcIDCacheEntry c;
 495   unsigned long curtime = time(NULL);
 496   int i;
 497
 498   if (!cache || !cache->cache)
 499     return FALSE;
 500
 501   c = cache->cache;
 502
 503   for (i = 0; i < cache->cache_count; i++) {
 504     if (c[i].data &&
 505         (c[i].expire == 0 || c[i].expire < curtime)) {
 506       c[i].id = NULL;
 507       c[i].data = NULL;
 508       c[i].type = 0;
 509       c[i].expire = 0;
 510       c[i].context = NULL;
 511     }
 512   }
 513
 514   return TRUE;
 515 }
 516
 517 /* Allocates ID cache list. */
 518
 519 static SilcIDCacheList silc_idcache_list_alloc()
 520 {
 521   SilcIDCacheList list;
 522
 523   list = silc_calloc(1, sizeof(*list));
 524
 525   return list;
 526 }
 527
 528 /* Adds cache entry to the ID cache list. If needed reallocates memory
 529    for the list. */
 530
 531 static void silc_idcache_list_add(SilcIDCacheList list, SilcIDCacheEntry cache)
 532 {
 533   int i;
 534
 535   /* Try to add to static cache */
 536   if (!list->cache_dyn_count)
 537     for (i = 0; i < sizeof(list->cache); i++) {
 538       if (!list->cache[i]) {
 539         list->cache[i] = cache;
 540         list->cache_count++;
 541         return;
 542       }
 543     }
 544
 545   /* Static cache is full, allocate dynamic cache */
 546   for (i = 0; i < list->cache_dyn_count; i++) {
 547     if (!list->cache_dyn[i]) {
 548       list->cache_dyn[i] = cache;
 549       list->cache_count++;
 550       break;
 551     }
 552   }
 553
 554   if (i >= list->cache_dyn_count) {
 555     int k;
 556
 557     i += 5;
 558     list->cache_dyn = silc_realloc(list->cache_dyn,
 559                                    sizeof(*list->cache) * (i));
 560
 561     /* NULL the reallocated area */
 562     for (k = list->cache_dyn_count; k < i; k++)
 563       list->cache_dyn[k] = NULL;
 564
 565     list->cache_dyn[list->cache_dyn_count] = cache;
 566     list->cache_dyn_count = i;
 567     list->cache_count++;
 568   }
 569 }
 570
 571 /* Returns number of cache entries in the ID cache list. */
 572
 573 int silc_idcache_list_count(SilcIDCacheList list)
 574 {
 575   return list->cache_count;
 576 }
 577
 578 /* Returns first entry from the ID cache list. */
 579
 580 int silc_idcache_list_first(SilcIDCacheList list, SilcIDCacheEntry *ret)
 581 {
 582   list->pos = 0;
 583
 584   if (!list->cache[list->pos])
 585     return FALSE;
 586
 587   if (ret)
 588     *ret = list->cache[list->pos];
 589
 590   return TRUE;
 591 }
 592
 593 /* Returns next entry from the ID cache list. */
 594
 595 int silc_idcache_list_next(SilcIDCacheList list, SilcIDCacheEntry *ret)
 596 {
 597   int dyn = FALSE;
 598   list->pos++;
 599
 600   if (list->pos >= sizeof(list->cache)) {
 601     list->pos = 0;
 602     dyn = TRUE;
 603   }
 604
 605   if (dyn && list->pos >= list->cache_dyn_count)
 606     return FALSE;
 607
 608   if (!dyn && !list->cache[list->pos])
 609     return FALSE;
 610
 611   if (dyn && !list->cache_dyn[list->pos])
 612     return FALSE;
 613
 614   if (ret) {
 615     if (!dyn)
 616       *ret = list->cache[list->pos];
 617     else
 618       *ret = list->cache_dyn[list->pos];
 619   }
 620
 621   return TRUE;
 622 }
 623
 624 /* Free's ID cache list. User must free the list object returned by
 625    any of the searching functions. */
 626
 627 void silc_idcache_list_free(SilcIDCacheList list)
 628 {
 629   if (list) {
 630     if (list->cache_dyn)
 631       silc_free(list->cache_dyn);
 632     silc_free(list);
 633   }
 634 }