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