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