lib/silcutil/silchashtable.c

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