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