lib/silcutil/silchashtable.c

   1 /*
   2
   3   silchashtable.c
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2001 - 2003 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; version 2 of the License.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18 */
  19 /* Implementation of collision resistant hash table. This is a hash table
  20    that provides a reliable (what you add stays there, and duplicate keys
  21    are allowed) with as fast reference to the key as possible. If duplicate
  22    keys are a lot in the hash table the lookup gets slower of course.
  23    However, this is reliable and no data is lost at any point. If you know
  24    that you never have duplicate keys then this is as fast as any simple
  25    hash table. */
  26 /* $Id$ */
  27
  28 #include "silcincludes.h"
  29 #include "silchashtable.h"
  30
  31 /* Define to 1 if you want hash table debug enabled */
  32 #define SILC_HASH_TABLE_DEBUG 0
  33
  34 #if SILC_HASH_TABLE_DEBUG == 1
  35 #define SILC_HT_DEBUG(fmt) SILC_LOG_DEBUG(fmt)
  36 #else
  37 #define SILC_HT_DEBUG(fmt)
  38 #endif
  39
  40 /* Default size of the hash table (index to prime table) */
  41 #define SILC_HASH_TABLE_SIZE 3
  42
  43 /* Produce the index by hashing the key */
  44 #define SILC_HASH_TABLE_HASH(f, c) \
  45   ((f)(key, (c)) % primesize[ht->table_size])
  46
  47 /* Check whether need to rehash */
  48 #define SILC_HASH_REHASH_INC \
  49   (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
  50 #define SILC_HASH_REHASH_DEC \
  51   (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
  52    ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
  53
  54 /* One entry in the hash table. Includes the key and the associated
  55    context. The `next' pointer is non-NULL if two (or more) different
  56    keys hashed to same value.  The pointer is the pointer to the next
  57    entry. */
  58 typedef struct SilcHashTableEntryStruct {
  59   void *key;
  60   void *context;
  61   struct SilcHashTableEntryStruct *next;
  62 } *SilcHashTableEntry;
  63
  64 /* Hash table. */
  65 struct SilcHashTableStruct {
  66   SilcHashTableEntry *table;
  67   SilcUInt32 table_size;
  68   SilcUInt32 entry_count;
  69   SilcHashFunction hash;
  70   SilcHashCompare compare;
  71   SilcHashDestructor destructor;
  72   void *hash_user_context;
  73   void *compare_user_context;
  74   void *destructor_user_context;
  75   unsigned int auto_rehash : 1;
  76 };
  77
  78 /* Prime sizes for the hash table. The size of the table will always
  79    be one of these. */
  80 const SilcUInt32 primesize[42] =
  81 {
  82   1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031,
  83   1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431,
  84   65537, 106721, 131101, 262147, 360163, 524309, 810343, 1048583, 2097169,
  85   4194319, 6153409, 8388617, 13845163, 16777259, 33554467, 67108879
  86 };
  87
  88 /* Find appropriate size for the hash table. The size will be a prime. */
  89
  90 static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index)
  91 {
  92   int i;
  93
  94   for (i = 0; i < sizeof(primesize) / sizeof(primesize[0]); i++)
  95     if (primesize[i] >= size) {
  96       *index = i;
  97       SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
  98       return primesize[i];
  99     }
 100
 101   *index = i - 1;
 102   SILC_HT_DEBUG(("sizeof of the hash table is %d", primesize[*index]));
 103   return primesize[i - 1];
 104 }
 105
 106 /* Internal routine to find entry in the hash table by `key'. Returns
 107    the previous entry (if exists) as well. */
 108
 109 static inline SilcHashTableEntry *
 110 silc_hash_table_find_internal(SilcHashTable ht, void *key,
 111                               SilcHashTableEntry *prev_entry,
 112                               SilcHashFunction hash, void *hash_user_context,
 113                               SilcHashCompare compare,
 114                               void *compare_user_context)
 115 {
 116   SilcHashTableEntry *entry, prev = NULL;
 117   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 118
 119   SILC_HT_DEBUG(("index %d key %p", i, key));
 120
 121   entry = &ht->table[i];
 122   if (compare) {
 123     while (*entry && !compare((*entry)->key, key, compare_user_context)) {
 124       prev = *entry;
 125       entry = &(*entry)->next;
 126     }
 127   } else {
 128     while (*entry && (*entry)->key != key) {
 129       prev = *entry;
 130       entry = &(*entry)->next;
 131     }
 132   }
 133
 134   *prev_entry = prev;
 135   return entry;
 136 }
 137
 138 /* Internal routine to find entry in the hash table by `key' and `context'.
 139    Returns the previous entry (if exists) as well to `prev_entry'. */
 140
 141 static inline SilcHashTableEntry *
 142 silc_hash_table_find_internal_context(SilcHashTable ht, void *key,
 143                                       void *context,
 144                                       SilcHashTableEntry *prev_entry,
 145                                       SilcHashFunction hash,
 146                                       void *hash_user_context,
 147                                       SilcHashCompare compare,
 148                                       void *compare_user_context)
 149 {
 150   SilcHashTableEntry *entry, prev = NULL;
 151   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 152
 153   SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
 154
 155   entry = &ht->table[i];
 156   if (ht->compare) {
 157     while (*entry) {
 158       if (compare((*entry)->key, key, compare_user_context) &&
 159           (*entry)->context == context)
 160         break;
 161       prev = *entry;
 162       entry = &(*entry)->next;
 163     }
 164   } else {
 165     while (*entry) {
 166       if ((*entry)->key == key && (*entry)->context == context)
 167         break;
 168       prev = *entry;
 169       entry = &(*entry)->next;
 170     }
 171   }
 172
 173   if (prev_entry)
 174     *prev_entry = prev;
 175   return entry;
 176 }
 177
 178 /* Internal routine to find entry in the hash table by `key'. */
 179
 180 static inline SilcHashTableEntry *
 181 silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
 182                                      SilcHashFunction hash,
 183                                      void *hash_user_context,
 184                                      SilcHashCompare compare,
 185                                      void *compare_user_context)
 186 {
 187   SilcHashTableEntry *entry;
 188   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 189
 190   SILC_HT_DEBUG(("index %d key %p", i, key));
 191
 192   entry = &ht->table[i];
 193   if (compare) {
 194     while (*entry && !compare((*entry)->key, key, compare_user_context))
 195       entry = &(*entry)->next;
 196   } else {
 197     while (*entry && (*entry)->key != key)
 198       entry = &(*entry)->next;
 199   }
 200
 201   return entry;
 202 }
 203
 204 /* Internal routine to find all keys by `key'. This may return multiple
 205    entries if multiple entries with same key exists. With specific
 206    hash and comparison functions. */
 207
 208 static inline void
 209 silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
 210                                   SilcHashFunction hash,
 211                                   void *hash_user_context,
 212                                   SilcHashCompare compare,
 213                                   void *compare_user_context,
 214                                   SilcHashForeach foreach,
 215                                   void *foreach_user_context)
 216 {
 217   SilcHashTableEntry e, tmp;
 218   bool auto_rehash, found = FALSE;
 219   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 220
 221   SILC_HT_DEBUG(("index %d key %p", i, key));
 222
 223   /* Disallow auto rehashing while going through the table since we call
 224      the `foreach' function which could alter the table. */
 225   auto_rehash = ht->auto_rehash;
 226   ht->auto_rehash = FALSE;
 227
 228   e = ht->table[i];
 229   if (compare) {
 230     while (e) {
 231       tmp = e->next;
 232       if (compare(e->key, key, compare_user_context)) {
 233         found = TRUE;
 234         foreach(e->key, e->context, foreach_user_context);
 235       }
 236       e = tmp;
 237     }
 238   } else {
 239     while (e) {
 240       tmp = e->next;
 241       if (e->key == key) {
 242         found = TRUE;
 243         foreach(e->key, e->context, foreach_user_context);
 244       }
 245       e = tmp;
 246     }
 247   }
 248
 249   /* If nothing was found call with NULL context the callback */
 250   if (!found)
 251     foreach(key, NULL, foreach_user_context);
 252
 253   ht->auto_rehash = auto_rehash;
 254 }
 255
 256 /* Internal routine to add new key to the hash table */
 257
 258 static inline bool
 259 silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
 260                              SilcHashFunction hash,
 261                              void *hash_user_context)
 262 {
 263   SilcHashTableEntry *entry;
 264   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 265
 266   SILC_HT_DEBUG(("index %d key %p", i, key));
 267
 268   entry = &ht->table[i];
 269   if (*entry) {
 270     /* The entry exists already. We have a collision, add it to the
 271        list to avoid collision. */
 272     SilcHashTableEntry e, tmp;
 273
 274     e = *entry;
 275     tmp = e->next;
 276     while (tmp) {
 277       e = tmp;
 278       tmp = tmp->next;
 279     }
 280
 281     SILC_HT_DEBUG(("Collision; adding new key to list"));
 282
 283     e->next = silc_calloc(1, sizeof(*e->next));
 284     if (!e->next)
 285       return FALSE;
 286     e->next->key = key;
 287     e->next->context = context;
 288     ht->entry_count++;
 289   } else {
 290     /* New key */
 291     SILC_HT_DEBUG(("New key"));
 292     *entry = silc_calloc(1, sizeof(**entry));
 293     if (!(*entry))
 294       return FALSE;
 295     (*entry)->key = key;
 296     (*entry)->context = context;
 297     ht->entry_count++;
 298   }
 299
 300   if (SILC_HASH_REHASH_INC)
 301     silc_hash_table_rehash(ht, 0);
 302
 303   return TRUE;
 304 }
 305
 306 /* Internal routine to replace old key with new one (if it exists) */
 307
 308 static inline bool
 309 silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
 310                                  SilcHashFunction hash,
 311                                  void *hash_user_context)
 312 {
 313   SilcHashTableEntry *entry;
 314   SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 315
 316   SILC_HT_DEBUG(("index %d key %p", i, key));
 317
 318   entry = &ht->table[i];
 319   if (*entry) {
 320     /* The entry exists already. We have a collision, replace the old
 321        key and context. */
 322     if (ht->destructor)
 323       ht->destructor((*entry)->key, (*entry)->context,
 324                      ht->destructor_user_context);
 325   } else {
 326     /* New key */
 327     *entry = silc_calloc(1, sizeof(**entry));
 328     if (!(*entry))
 329       return FALSE;
 330     ht->entry_count++;
 331   }
 332
 333   (*entry)->key = key;
 334   (*entry)->context = context;
 335
 336   if (SILC_HASH_REHASH_INC)
 337     silc_hash_table_rehash(ht, 0);
 338
 339   return TRUE;
 340 }
 341
 342 /* Allocates new hash table and returns it.  If the `table_size' is not
 343    zero then the hash table size is the size provided. If zero then the
 344    default size will be used. Note that if the `table_size' is provided
 345    it should be a prime. The `hash', `compare' and `destructor' are
 346    the hash function, the key comparison function and key and context
 347    destructor function, respectively. The `hash' is mandatory, the others
 348    are optional. */
 349
 350 SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size,
 351                                     SilcHashFunction hash,
 352                                     void *hash_user_context,
 353                                     SilcHashCompare compare,
 354                                     void *compare_user_context,
 355                                     SilcHashDestructor destructor,
 356                                     void *destructor_user_context,
 357                                     bool auto_rehash)
 358 {
 359   SilcHashTable ht;
 360   SilcUInt32 size_index = SILC_HASH_TABLE_SIZE;
 361
 362   if (!hash)
 363     return NULL;
 364
 365   ht = silc_calloc(1, sizeof(*ht));
 366   if (!ht)
 367     return NULL;
 368   ht->table = silc_calloc(table_size ? silc_hash_table_primesize(table_size,
 369                                                                  &size_index) :
 370                           primesize[SILC_HASH_TABLE_SIZE],
 371                           sizeof(*ht->table));
 372   if (!ht->table) {
 373     silc_free(ht);
 374     return NULL;
 375   }
 376   ht->table_size = size_index;
 377   ht->hash = hash;
 378   ht->compare = compare;
 379   ht->destructor = destructor;
 380   ht->hash_user_context = hash_user_context;
 381   ht->compare_user_context = compare_user_context;
 382   ht->destructor_user_context = destructor_user_context;
 383   ht->auto_rehash = auto_rehash;
 384
 385   return ht;
 386 }
 387
 388 /* Frees the hash table. The destructor function provided in the
 389    silc_hash_table_alloc will be called for all keys in the hash table. */
 390
 391 void silc_hash_table_free(SilcHashTable ht)
 392 {
 393   SilcHashTableEntry e, tmp;
 394   int i;
 395
 396   for (i = 0; i < primesize[ht->table_size]; i++) {
 397     e = ht->table[i];
 398     while (e) {
 399       if (ht->destructor)
 400         ht->destructor(e->key, e->context, ht->destructor_user_context);
 401       tmp = e;
 402       e = e->next;
 403       silc_free(tmp);
 404     }
 405   }
 406
 407   silc_free(ht->table);
 408   silc_free(ht);
 409 }
 410
 411 /* Returns the size of the hash table */
 412
 413 SilcUInt32 silc_hash_table_size(SilcHashTable ht)
 414 {
 415   return primesize[ht->table_size];
 416 }
 417
 418 /* Returns the number of the entires in the hash table. If there is more
 419    entries in the table thatn the size of the hash table calling the
 420    silc_hash_table_rehash is recommended. */
 421
 422 SilcUInt32 silc_hash_table_count(SilcHashTable ht)
 423 {
 424   return ht->entry_count;
 425 }
 426
 427 /* Adds new entry to the hash table. The `key' is hashed using the
 428    hash function and the both `key' and `context' will be saved to the
 429    hash table. This function quarantees that the entry is always added
 430    to the hash table reliably (it is collision resistant). */
 431
 432 void silc_hash_table_add(SilcHashTable ht, void *key, void *context)
 433 {
 434   silc_hash_table_add_internal(ht, key, context, ht->hash,
 435                                ht->hash_user_context);
 436 }
 437
 438 /* Same as above but with specific hash function and user context. */
 439
 440 void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context,
 441                              SilcHashFunction hash, void *hash_user_context)
 442 {
 443   silc_hash_table_add_internal(ht, key, context, hash, hash_user_context);
 444 }
 445
 446 /* Same as above but if the `key' already exists in the hash table
 447    the old key and the old context will be replace with the `key' and
 448    the `context. The destructor function will be called for the
 449    replaced key and context. */
 450
 451 void silc_hash_table_replace(SilcHashTable ht, void *key, void *context)
 452 {
 453   silc_hash_table_replace_internal(ht, key, context, ht->hash,
 454                                    ht->hash_user_context);
 455 }
 456
 457 /* Same as above but with specific hash function. */
 458
 459 void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context,
 460                                  SilcHashFunction hash,
 461                                  void *hash_user_context)
 462 {
 463   silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context);
 464 }
 465
 466 /* Removes the entry from the hash table by the provided `key'. This will
 467    call the destructor funtion for the found entry. Return TRUE if the
 468    entry was removed successfully and FALSE otherwise. */
 469
 470 bool silc_hash_table_del(SilcHashTable ht, void *key)
 471 {
 472   SilcHashTableEntry *entry, prev, e;
 473
 474   entry = silc_hash_table_find_internal(ht, key, &prev,
 475                                         ht->hash, ht->hash_user_context,
 476                                         ht->compare, ht->compare_user_context);
 477   if (*entry == NULL)
 478     return FALSE;
 479
 480   e = *entry;
 481
 482   if (!prev && e->next)
 483     *entry = e->next;
 484   if (!prev && e->next == NULL)
 485     *entry = NULL;
 486   if (prev)
 487     prev->next = NULL;
 488   if (prev && e->next)
 489     prev->next = e->next;
 490
 491   if (ht->destructor)
 492     ht->destructor(e->key, e->context, ht->destructor_user_context);
 493   silc_free(e);
 494
 495   ht->entry_count--;
 496
 497   if (SILC_HASH_REHASH_DEC)
 498     silc_hash_table_rehash(ht, 0);
 499
 500   return TRUE;
 501 }
 502
 503 /* Same as above but with specific hash and compare functions. */
 504
 505 bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
 506                              SilcHashFunction hash,
 507                              void *hash_user_context,
 508                              SilcHashCompare compare,
 509                              void *compare_user_context,
 510                              SilcHashDestructor destructor,
 511                              void *destructor_user_context)
 512 {
 513   SilcHashTableEntry *entry, prev, e;
 514
 515   entry = silc_hash_table_find_internal(ht, key, &prev,
 516                                         hash ? hash : ht->hash,
 517                                         hash_user_context ? hash_user_context :
 518                                         ht->hash_user_context,
 519                                         compare ? compare : ht->compare,
 520                                         compare_user_context ?
 521                                         compare_user_context :
 522                                         ht->compare_user_context);
 523   if (*entry == NULL)
 524     return FALSE;
 525
 526   e = *entry;
 527
 528   if (!prev && e->next)
 529     *entry = e->next;
 530   if (!prev && e->next == NULL)
 531     *entry = NULL;
 532   if (prev)
 533     prev->next = NULL;
 534   if (prev && e->next)
 535     prev->next = e->next;
 536
 537   if (destructor) {
 538     destructor(e->key, e->context, destructor_user_context);
 539   } else {
 540     if (ht->destructor)
 541       ht->destructor(e->key, e->context, ht->destructor_user_context);
 542   }
 543   silc_free(e);
 544
 545   ht->entry_count--;
 546
 547   if (SILC_HASH_REHASH_DEC)
 548     silc_hash_table_rehash(ht, 0);
 549
 550   return TRUE;
 551 }
 552
 553 /* Same as above but verifies that the context associated with the `key'
 554    matches the `context'. This is handy to use with hash tables that may
 555    have duplicate keys. In that case the `context' may be used to check
 556    whether the correct entry is being deleted. */
 557
 558 bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 559                                     void *context)
 560 {
 561   SilcHashTableEntry *entry, prev, e;
 562
 563   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 564                                                 ht->hash,
 565                                                 ht->hash_user_context,
 566                                                 ht->compare,
 567                                                 ht->compare_user_context);
 568   if (*entry == NULL)
 569     return FALSE;
 570
 571   e = *entry;
 572
 573   if (!prev && e->next)
 574     *entry = e->next;
 575   if (!prev && e->next == NULL)
 576     *entry = NULL;
 577   if (prev)
 578     prev->next = NULL;
 579   if (prev && e->next)
 580     prev->next = e->next;
 581
 582   if (ht->destructor)
 583     ht->destructor(e->key, e->context, ht->destructor_user_context);
 584   silc_free(e);
 585
 586   ht->entry_count--;
 587
 588   if (SILC_HASH_REHASH_DEC)
 589     silc_hash_table_rehash(ht, 0);
 590
 591   return TRUE;
 592 }
 593
 594 /* Same as above but with specific hash and compare functions. */
 595
 596 bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
 597                                         void *context,
 598                                         SilcHashFunction hash,
 599                                         void *hash_user_context,
 600                                         SilcHashCompare compare,
 601                                         void *compare_user_context,
 602                                         SilcHashDestructor destructor,
 603                                         void *destructor_user_context)
 604 {
 605   SilcHashTableEntry *entry, prev, e;
 606
 607   entry = silc_hash_table_find_internal_context(ht, key, context, &prev,
 608                                                 hash ? hash : ht->hash,
 609                                                 hash_user_context ?
 610                                                 hash_user_context :
 611                                                 ht->hash_user_context,
 612                                                 compare ?
 613                                                 compare : ht->compare,
 614                                                 compare_user_context ?
 615                                                 compare_user_context :
 616                                                 ht->compare_user_context);
 617   if (*entry == NULL)
 618     return FALSE;
 619
 620   e = *entry;
 621
 622   if (!prev && e->next)
 623     *entry = e->next;
 624   if (!prev && e->next == NULL)
 625     *entry = NULL;
 626   if (prev)
 627     prev->next = NULL;
 628   if (prev && e->next)
 629     prev->next = e->next;
 630
 631   if (destructor) {
 632     destructor(e->key, e->context, destructor_user_context);
 633   } else {
 634     if (ht->destructor)
 635       ht->destructor(e->key, e->context, ht->destructor_user_context);
 636   }
 637   silc_free(e);
 638
 639   ht->entry_count--;
 640
 641   if (SILC_HASH_REHASH_DEC)
 642     silc_hash_table_rehash(ht, 0);
 643
 644   return TRUE;
 645 }
 646
 647 /* Finds the entry in the hash table by the provided `key' as fast as
 648    possible. Return TRUE if the entry was found and FALSE otherwise.
 649    The found entry is returned to the `ret_key' and `ret_context',
 650    respectively. If the `ret_key and `ret_context' are NULL then this
 651    maybe used only to check whether given key exists in the table. */
 652
 653 bool silc_hash_table_find(SilcHashTable ht, void *key,
 654                           void **ret_key, void **ret_context)
 655 {
 656   SilcHashTableEntry *entry;
 657
 658   entry = silc_hash_table_find_internal_simple(ht, key, ht->hash,
 659                                                ht->hash_user_context,
 660                                                ht->compare,
 661                                                ht->compare_user_context);
 662   if (*entry == NULL)
 663     return FALSE;
 664
 665   if (ret_key)
 666     *ret_key = (*entry)->key;
 667   if (ret_context)
 668     *ret_context = (*entry)->context;
 669
 670   return TRUE;
 671 }
 672
 673 /* Same as above but with specified hash and comparison functions. */
 674
 675 bool silc_hash_table_find_ext(SilcHashTable ht, void *key,
 676                               void **ret_key, void **ret_context,
 677                               SilcHashFunction hash,
 678                               void *hash_user_context,
 679                               SilcHashCompare compare,
 680                               void *compare_user_context)
 681 {
 682   SilcHashTableEntry *entry;
 683
 684   entry = silc_hash_table_find_internal_simple(ht, key,
 685                                                hash ? hash : ht->hash,
 686                                                hash_user_context ?
 687                                                hash_user_context :
 688                                                ht->hash_user_context,
 689                                                compare ? compare :
 690                                                ht->compare,
 691                                                compare_user_context ?
 692                                                compare_user_context :
 693                                                ht->compare_user_context);
 694   if (*entry == NULL)
 695     return FALSE;
 696
 697   if (ret_key)
 698     *ret_key = (*entry)->key;
 699   if (ret_context)
 700     *ret_context = (*entry)->context;
 701
 702   return TRUE;
 703 }
 704
 705 /* Same as silc_hash_table_find but finds with specific context. */
 706
 707 bool silc_hash_table_find_by_context(SilcHashTable ht, void *key,
 708                                      void *context, void **ret_key)
 709 {
 710   SilcHashTableEntry *entry;
 711
 712   entry = silc_hash_table_find_internal_context(ht, key, context, NULL,
 713                                                 ht->hash,
 714                                                 ht->hash_user_context,
 715                                                 ht->compare,
 716                                                 ht->compare_user_context);
 717   if (!entry || !(*entry))
 718     return FALSE;
 719
 720   if (ret_key)
 721     *ret_key = (*entry)->key;
 722
 723   return TRUE;
 724 }
 725
 726 /* As the hash table is collision resistant it is possible to save duplicate
 727    keys to the hash table. This function can be used to find all keys
 728    and contexts from the hash table that are found using the `key'. The
 729    `foreach' is called for every found key. */
 730
 731 void silc_hash_table_find_foreach(SilcHashTable ht, void *key,
 732                                   SilcHashForeach foreach, void *user_context)
 733 {
 734   silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context,
 735                                     ht->compare, ht->compare_user_context,
 736                                     foreach, user_context);
 737 }
 738
 739 /* Same as above but with specific hash and comparison functions. */
 740
 741 void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key,
 742                                       SilcHashFunction hash,
 743                                       void *hash_user_context,
 744                                       SilcHashCompare compare,
 745                                       void *compare_user_context,
 746                                       SilcHashForeach foreach,
 747                                       void *foreach_user_context)
 748 {
 749   silc_hash_table_find_internal_all(ht, key,
 750                                     hash ? hash : ht->hash,
 751                                     hash_user_context ?
 752                                     hash_user_context :
 753                                     ht->hash_user_context,
 754                                     compare ? compare :
 755                                     ht->compare,
 756                                     compare_user_context ?
 757                                     compare_user_context :
 758                                     ht->compare_user_context,
 759                                     foreach, foreach_user_context);
 760 }
 761
 762 /* Traverse all entrys in the hash table and call the `foreach' for
 763    every entry with the `user_context' context. */
 764
 765 void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach,
 766                              void *user_context)
 767 {
 768   SilcHashTableEntry e, tmp;
 769   int i;
 770   bool auto_rehash;
 771
 772   if (!foreach)
 773     return;
 774
 775   auto_rehash = ht->auto_rehash;
 776   ht->auto_rehash = FALSE;
 777   for (i = 0; i < primesize[ht->table_size]; i++) {
 778     e = ht->table[i];
 779     while (e) {
 780       /* Entry may become invalid inside the `foreach' */
 781       tmp = e->next;
 782       foreach(e->key, e->context, user_context);
 783       e = tmp;
 784     }
 785   }
 786   ht->auto_rehash = auto_rehash;
 787 }
 788
 789 /* Rehashs the hash table. The size of the new hash table is provided
 790    as `new_size'. If the `new_size' is zero then this routine will make
 791    the new table of a suitable size. Note that this operation may be
 792    very slow. */
 793
 794 void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size)
 795 {
 796   int i;
 797   SilcHashTableEntry *table, e, tmp;
 798   SilcUInt32 table_size, size_index;
 799   bool auto_rehash;
 800
 801   SILC_HT_DEBUG(("Start"));
 802
 803   if (new_size)
 804     silc_hash_table_primesize(new_size, &size_index);
 805   else
 806     silc_hash_table_primesize(ht->entry_count, &size_index);
 807
 808   if (size_index == ht->table_size)
 809     return;
 810
 811   SILC_HT_DEBUG(("Rehashing"));
 812
 813   /* Take old hash table */
 814   table = ht->table;
 815   table_size = ht->table_size;
 816   auto_rehash = ht->auto_rehash;
 817   ht->auto_rehash = FALSE;
 818
 819   /* Allocate new table */
 820   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 821   if (!ht->table)
 822     return;
 823   ht->table_size = size_index;
 824   ht->entry_count = 0;
 825
 826   /* Rehash */
 827   for (i = 0; i < primesize[table_size]; i++) {
 828     e = table[i];
 829     while (e) {
 830       silc_hash_table_add(ht, e->key, e->context);
 831       tmp = e;
 832       e = e->next;
 833
 834       /* Remove old entry */
 835       silc_free(tmp);
 836     }
 837   }
 838
 839   ht->auto_rehash = auto_rehash;
 840
 841   /* Remove old table */
 842   silc_free(table);
 843 }
 844
 845 /* Same as above but with specific hash function. */
 846
 847 void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size,
 848                                 SilcHashFunction hash,
 849                                 void *hash_user_context)
 850 {
 851   int i;
 852   SilcHashTableEntry *table, e, tmp;
 853   SilcUInt32 table_size, size_index;
 854   bool auto_rehash;
 855
 856   SILC_HT_DEBUG(("Start"));
 857
 858   if (new_size)
 859     silc_hash_table_primesize(new_size, &size_index);
 860   else
 861     silc_hash_table_primesize(ht->entry_count, &size_index);
 862
 863   if (size_index == ht->table_size)
 864     return;
 865
 866   SILC_HT_DEBUG(("Rehashing"));
 867
 868   /* Take old hash table */
 869   table = ht->table;
 870   table_size = ht->table_size;
 871   auto_rehash = ht->auto_rehash;
 872   ht->auto_rehash = FALSE;
 873
 874   /* Allocate new table */
 875   ht->table = silc_calloc(primesize[size_index], sizeof(*ht->table));
 876   if (!ht->table)
 877     return;
 878   ht->table_size = size_index;
 879   ht->entry_count = 0;
 880
 881   /* Rehash */
 882   for (i = 0; i < primesize[table_size]; i++) {
 883     e = table[i];
 884     while (e) {
 885       silc_hash_table_add_ext(ht, e->key, e->context, hash,
 886                               hash_user_context);
 887       tmp = e;
 888       e = e->next;
 889
 890       /* Remove old entry */
 891       silc_free(tmp);
 892     }
 893   }
 894
 895   ht->auto_rehash = auto_rehash;
 896
 897   /* Remove old table */
 898   silc_free(table);
 899 }
 900
 901 /* Prepares the `htl' list structure sent as argument to be used in the
 902    hash table traversing with the silc_hash_table_get. Usage:
 903    SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
 904
 905 void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl)
 906 {
 907   htl->ht = ht;
 908   htl->entry = NULL;
 909   htl->index = 0;
 910   htl->auto_rehash = ht->auto_rehash;
 911
 912   /* Disallow rehashing of the table while traversing the table */
 913   ht->auto_rehash = FALSE;
 914 }
 915
 916 /* Resets the `htl' SilcHashTableList. */
 917
 918 void silc_hash_table_list_reset(SilcHashTableList *htl)
 919 {
 920   /* Set back the original auto rehash value to the table */
 921   htl->ht->auto_rehash = htl->auto_rehash;
 922 }
 923
 924 /* Returns always the next entry in the hash table into the `key' and
 925    `context' and TRUE.  If this returns FALSE then there are no anymore
 926    any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
 927
 928 bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
 929 {
 930   SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
 931
 932   if (!htl->ht->entry_count)
 933     return FALSE;
 934
 935   while (!entry && htl->index < primesize[htl->ht->table_size]) {
 936     entry = htl->ht->table[htl->index];
 937     htl->index++;
 938   }
 939
 940   if (!entry)
 941     return FALSE;
 942
 943   htl->entry = entry->next;
 944
 945   if (key)
 946     *key = entry->key;
 947   if (context)
 948     *context = entry->context;
 949
 950   return TRUE;
 951 }