dbus/dbus-hash.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* dbus-hash.c Generic hash table utility (internal to D-BUS implementation)
   3  *
   4  * Copyright (C) 2002  Red Hat, Inc.
   5  * Copyright (c) 1991-1993 The Regents of the University of California.
   6  * Copyright (c) 1994 Sun Microsystems, Inc.
   7  *
   8  * Hash table implementation based on generic/tclHash.c from the Tcl
   9  * source code. The original Tcl license applies to portions of the
  10  * code from tclHash.c; the Tcl license follows this standad D-BUS
  11  * license information.
  12  *
  13  * Licensed under the Academic Free License version 1.2
  14  *
  15  * This program is free software; you can redistribute it and/or modify
  16  * it under the terms of the GNU General Public License as published by
  17  * the Free Software Foundation; either version 2 of the License, or
  18  * (at your option) any later version.
  19  *
  20  * This program is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  * GNU General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License
  26  * along with this program; if not, write to the Free Software
  27  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  28  *
  29  */
  30 /*
  31  * The following copyright applies to code from the Tcl distribution.
  32  *
  33  * Copyright (c) 1991-1993 The Regents of the University of California.
  34  * Copyright (c) 1994 Sun Microsystems, Inc.
  35  *
  36  * This software is copyrighted by the Regents of the University of
  37  * California, Sun Microsystems, Inc., Scriptics Corporation, and
  38  * other parties.  The following terms apply to all files associated
  39  * with the software unless explicitly disclaimed in individual files.
  40  *
  41  * The authors hereby grant permission to use, copy, modify,
  42  * distribute, and license this software and its documentation for any
  43  * purpose, provided that existing copyright notices are retained in
  44  * all copies and that this notice is included verbatim in any
  45  * distributions. No written agreement, license, or royalty fee is
  46  * required for any of the authorized uses.  Modifications to this
  47  * software may be copyrighted by their authors and need not follow
  48  * the licensing terms described here, provided that the new terms are
  49  * clearly indicated on the first page of each file where they apply.
  50  *
  51  * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
  52  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
  53  * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
  54  * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
  55  * OF THE POSSIBILITY OF SUCH DAMAGE.
  56  *
  57  * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
  58  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  59  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
  60  * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
  61  * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
  62  * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  63  *
  64  * GOVERNMENT USE: If you are acquiring this software on behalf of the
  65  * U.S. government, the Government shall have only "Restricted Rights"
  66  * in the software and related documentation as defined in the Federal
  67  * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
  68  * are acquiring the software on behalf of the Department of Defense,
  69  * the software shall be classified as "Commercial Computer Software"
  70  * and the Government shall have only "Restricted Rights" as defined
  71  * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
  72  * foregoing, the authors grant the U.S. Government and others acting
  73  * in its behalf permission to use and distribute the software in
  74  * accordance with the terms specified in this license.
  75  */
  76
  77 #include "dbus-hash.h"
  78 #include "dbus-internals.h"
  79
  80 /**
  81  * @defgroup DBusHashTable Hash table
  82  * @ingroup  DBusInternals
  83  * @brief DBusHashTable data structure
  84  *
  85  * Types and functions related to DBusHashTable.
  86  */
  87
  88 /**
  89  * @defgroup DBusHashTableInternals Hash table implementation details
  90  * @ingroup  DBusInternals
  91  * @brief DBusHashTable implementation details
  92  *
  93  * The guts of DBusHashTable.
  94  *
  95  * @todo rebuild_table() should be modified to also shrink the hash bucket
  96  * array when appropriate; otherwise if a hash table has been
  97  * very large but is now small, iteration becomes inefficient.
  98  * We should still only shrink when adding hash entries though, not
  99  * when removing them, so that you can still iterate over the hash
 100  * removing entries. So if you added 5000, removed 4000, the
 101  * shrinking would happen next time an entry was added.
 102  * @{
 103  */
 104
 105 /**
 106  * When there are this many entries per bucket, on average, rebuild
 107  * the hash table to make it larger.
 108  */
 109 #define REBUILD_MULTIPLIER  3
 110
 111 /**
 112  * Takes a preliminary integer hash value and produces an index into a
 113  * hash tables bucket list.  The idea is to make it so that
 114  * preliminary values that are arbitrarily similar will end up in
 115  * different buckets.  The hash function was taken from a
 116  * random-number generator. (This is used to hash integers.)
 117  */
 118 #define RANDOM_INDEX(table, i) \
 119     (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
 120
 121 /**
 122  * Initial number of buckets in hash table (hash table statically
 123  * allocates its buckets for this size and below).
 124  */
 125 #define DBUS_SMALL_HASH_TABLE 4
 126
 127 /**
 128  * Typedef for DBusHashEntry
 129  */
 130 typedef struct DBusHashEntry DBusHashEntry;
 131
 132 /**
 133  * @brief Internal representation of a hash entry.
 134  *
 135  * A single entry (key-value pair) in the hash table.
 136  * Internal to hash table implementation.
 137  */
 138 struct DBusHashEntry
 139 {
 140   DBusHashEntry *next;    /**< Pointer to next entry in this
 141                            * hash bucket, or #NULL for end of
 142                            * chain.
 143                            */
 144   void *key;              /**< Hash key */
 145   void *value;            /**< Hash value */
 146 };
 147
 148 /**
 149  * Function used to find and optionally create a hash entry.
 150  */
 151 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable   *table,
 152                                                   void            *key,
 153                                                   dbus_bool_t      create_if_not_found,
 154                                                   DBusHashEntry ***bucket);
 155
 156 /**
 157  * @brief Internals of DBusHashTable.
 158  *
 159  * Hash table internals. Hash tables are opaque objects, they must be
 160  * used via accessor functions.
 161  */
 162 struct DBusHashTable {
 163   int refcount;                       /**< Reference count */
 164
 165   DBusHashEntry **buckets;            /**< Pointer to bucket array.  Each
 166                                        * element points to first entry in
 167                                        * bucket's hash chain, or #NULL.
 168                                        */
 169   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
 170                                        /**< Bucket array used for small tables
 171                                         * (to avoid mallocs and frees).
 172                                         */
 173   int n_buckets;                       /**< Total number of buckets allocated
 174                                         * at **buckets.
 175                                         */
 176   int n_entries;                       /**< Total number of entries present
 177                                         * in table.
 178                                         */
 179   int rebuild_size;                    /**< Enlarge table when numEntries gets
 180                                         * to be this large.
 181                                         */
 182   int down_shift;                      /**< Shift count used in hashing
 183                                         * function.  Designed to use high-
 184                                         * order bits of randomized keys.
 185                                         */
 186   int mask;                            /**< Mask value used in hashing
 187                                         * function.
 188                                         */
 189   DBusHashType key_type;               /**< Type of keys used in this table */
 190
 191
 192   DBusFindEntryFunction find_function; /**< Function for finding entries */
 193
 194   DBusFreeFunction free_key_function;   /**< Function to free keys */
 195   DBusFreeFunction free_value_function; /**< Function to free values */
 196 };
 197
 198 /**
 199  * @brief Internals of DBusHashIter.
 200  */
 201 typedef struct
 202 {
 203   DBusHashTable *table;     /**< Pointer to table containing entry. */
 204   DBusHashEntry **bucket;   /**< Pointer to bucket that points to
 205                              * first entry in this entry's chain:
 206                              * used for deleting the entry.
 207                              */
 208   DBusHashEntry *entry;      /**< Current hash entry */
 209   DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
 210   int next_bucket;           /**< index of next bucket */
 211   int n_entries_on_init;     /**< used to detect table resize since initialization */
 212 } DBusRealHashIter;
 213
 214 static DBusHashEntry* find_int_function    (DBusHashTable   *table,
 215                                             void            *key,
 216                                             dbus_bool_t      create_if_not_found,
 217                                             DBusHashEntry ***bucket);
 218 static DBusHashEntry* find_string_function (DBusHashTable   *table,
 219                                             void            *key,
 220                                             dbus_bool_t      create_if_not_found,
 221                                             DBusHashEntry ***bucket);
 222 static unsigned int   string_hash          (const char      *str);
 223 static void           rebuild_table        (DBusHashTable   *table);
 224 static DBusHashEntry* alloc_entry          (DBusHashTable   *table);
 225 static void           remove_entry         (DBusHashTable   *table,
 226                                             DBusHashEntry  **bucket,
 227                                             DBusHashEntry   *entry);
 228 static void           free_entry           (DBusHashTable   *table,
 229                                             DBusHashEntry   *entry);
 230
 231 /** @} */
 232
 233 /**
 234  * @addtogroup DBusHashTable
 235  * @{
 236  */
 237
 238 /**
 239  * @typedef DBusHashIter
 240  *
 241  * Public opaque hash table iterator object.
 242  */
 243
 244 /**
 245  * @typedef DBusHashTable
 246  *
 247  * Public opaque hash table object.
 248  */
 249
 250 /**
 251  * @typedef DBusHashType
 252  *
 253  * Indicates the type of a key in the hash table.
 254  */
 255
 256 /**
 257  * Constructs a new hash table. Should be freed with
 258  * _dbus_hash_table_unref(). If memory cannot be
 259  * allocated for the hash table, returns #NULL.
 260  *
 261  * @param type the type of hash key to use.
 262  * @param key_free_function function to free hash keys.
 263  * @param value_free_function function to free hash values.
 264  * @returns a new DBusHashTable or #NULL if no memory.
 265  */
 266 DBusHashTable*
 267 _dbus_hash_table_new (DBusHashType     type,
 268                       DBusFreeFunction key_free_function,
 269                       DBusFreeFunction value_free_function)
 270 {
 271   DBusHashTable *table;
 272
 273   table = dbus_new0 (DBusHashTable, 1);
 274   if (table == NULL)
 275     return NULL;
 276
 277   table->refcount = 1;
 278
 279   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
 280
 281   table->buckets = table->static_buckets;
 282   table->n_buckets = DBUS_SMALL_HASH_TABLE;
 283   table->n_entries = 0;
 284   table->rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
 285   table->down_shift = 28;
 286   table->mask = 3;
 287   table->key_type = type;
 288
 289   switch (table->key_type)
 290     {
 291     case DBUS_HASH_INT:
 292       table->find_function = find_int_function;
 293       break;
 294     case DBUS_HASH_STRING:
 295       table->find_function = find_string_function;
 296       break;
 297     default:
 298       _dbus_assert_not_reached ("Unknown hash table type");
 299       break;
 300     }
 301
 302   table->free_key_function = key_free_function;
 303   table->free_value_function = value_free_function;
 304
 305   return table;
 306 }
 307
 308
 309 /**
 310  * Increments the reference count for a hash table.
 311  *
 312  * @param table the hash table to add a reference to.
 313  */
 314 void
 315 _dbus_hash_table_ref (DBusHashTable *table)
 316 {
 317   table->refcount += 1;
 318 }
 319
 320 /**
 321  * Decrements the reference count for a hash table,
 322  * freeing the hash table if the count reaches zero.
 323  *
 324  * @param table the hash table to remove a reference from.
 325  */
 326 void
 327 _dbus_hash_table_unref (DBusHashTable *table)
 328 {
 329   table->refcount -= 1;
 330
 331   if (table->refcount == 0)
 332     {
 333       DBusHashEntry *entry;
 334       DBusHashEntry *next;
 335       int i;
 336
 337       /* Free the entries in the table. */
 338
 339       for (i = 0; i < table->n_buckets; i++)
 340         {
 341           entry = table->buckets[i];
 342           while (entry != NULL)
 343             {
 344               next = entry->next;
 345
 346               free_entry (table, entry);
 347
 348               entry = next;
 349             }
 350         }
 351
 352       /* Free the bucket array, if it was dynamically allocated. */
 353       if (table->buckets != table->static_buckets)
 354         dbus_free (table->buckets);
 355
 356       dbus_free (table);
 357     }
 358 }
 359
 360 static DBusHashEntry*
 361 alloc_entry (DBusHashTable *table)
 362 {
 363   DBusHashEntry *entry;
 364
 365   entry = dbus_new0 (DBusHashEntry, 1);
 366
 367   return entry;
 368 }
 369
 370 static void
 371 free_entry (DBusHashTable  *table,
 372             DBusHashEntry  *entry)
 373 {
 374   if (table->free_key_function)
 375     (* table->free_key_function) (entry->key);
 376   if (table->free_value_function)
 377     (* table->free_value_function) (entry->value);
 378
 379   dbus_free (entry);
 380 }
 381
 382 static void
 383 remove_entry (DBusHashTable  *table,
 384               DBusHashEntry **bucket,
 385               DBusHashEntry  *entry)
 386 {
 387   _dbus_assert (table != NULL);
 388   _dbus_assert (bucket != NULL);
 389   _dbus_assert (*bucket != NULL);
 390   _dbus_assert (entry != NULL);
 391
 392   if (*bucket == entry)
 393     *bucket = entry->next;
 394   else
 395     {
 396       DBusHashEntry *prev;
 397       prev = *bucket;
 398
 399       while (prev->next != entry)
 400         prev = prev->next;
 401
 402       _dbus_assert (prev != NULL);
 403
 404       prev->next = entry->next;
 405     }
 406
 407   table->n_entries -= 1;
 408   free_entry (table, entry);
 409 }
 410
 411 /**
 412  * Initializes a hash table iterator. To iterate over all entries in a
 413  * hash table, use the following code (the printf assumes a hash
 414  * from strings to strings obviously):
 415  *
 416  * @code
 417  * DBusHashIter iter;
 418  *
 419  * _dbus_hash_iter_init (table, &iter);
 420  * while (_dbus_hash_iter_next (&iter))
 421  *   {
 422  *      printf ("The first key is %s and value is %s\n",
 423  *              _dbus_hash_iter_get_string_key (&iter),
 424  *              _dbus_hash_iter_get_value (&iter));
 425  *   }
 426  *
 427  *
 428  * @endcode
 429  *
 430  * The iterator is initialized pointing "one before" the first hash
 431  * entry. The first call to _dbus_hash_iter_next() moves it onto
 432  * the first valid entry or returns #FALSE if the hash table is
 433  * empty. Subsequent calls move to the next valid entry or return
 434  * #FALSE if there are no more entries.
 435  *
 436  * Note that it is guaranteed to be safe to remove a hash entry during
 437  * iteration, but it is not safe to add a hash entry.
 438  *
 439  * @param table the hash table to iterate over.
 440  * @param iter the iterator to initialize.
 441  */
 442 void
 443 _dbus_hash_iter_init (DBusHashTable *table,
 444                       DBusHashIter  *iter)
 445 {
 446   DBusRealHashIter *real;
 447
 448   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 449
 450   real = (DBusRealHashIter*) iter;
 451
 452   real->table = table;
 453   real->bucket = NULL;
 454   real->entry = NULL;
 455   real->next_entry = NULL;
 456   real->next_bucket = 0;
 457   real->n_entries_on_init = table->n_entries;
 458 }
 459
 460 /**
 461  * Move the hash iterator forward one step, to the next hash entry.
 462  * The documentation for _dbus_hash_iter_init() explains in more
 463  * detail.
 464  *
 465  * @param iter the iterator to move forward.
 466  * @returns #FALSE if there are no more entries to move to.
 467  */
 468 dbus_bool_t
 469 _dbus_hash_iter_next (DBusHashIter  *iter)
 470 {
 471   DBusRealHashIter *real;
 472
 473   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 474
 475   real = (DBusRealHashIter*) iter;
 476
 477   /* if this assertion failed someone probably added hash entries
 478    * during iteration, which is bad.
 479    */
 480   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
 481
 482   /* Remember that real->entry may have been deleted */
 483
 484   while (real->next_entry == NULL)
 485     {
 486       if (real->next_bucket >= real->table->n_buckets)
 487         {
 488           /* invalidate iter and return false */
 489           real->entry = NULL;
 490           real->table = NULL;
 491           real->bucket = NULL;
 492           return FALSE;
 493         }
 494
 495       real->bucket = &(real->table->buckets[real->next_bucket]);
 496       real->next_entry = *(real->bucket);
 497       real->next_bucket += 1;
 498     }
 499
 500   _dbus_assert (real->next_entry != NULL);
 501   _dbus_assert (real->bucket != NULL);
 502
 503   real->entry = real->next_entry;
 504   real->next_entry = real->entry->next;
 505
 506   return TRUE;
 507 }
 508
 509 /**
 510  * Removes the current entry from the hash table.
 511  * If a key_free_function or value_free_function
 512  * was provided to _dbus_hash_table_new(),
 513  * frees the key and/or value for this entry.
 514  *
 515  * @param iter the hash table iterator.
 516  */
 517 void
 518 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
 519 {
 520   DBusRealHashIter *real;
 521
 522   real = (DBusRealHashIter*) iter;
 523
 524   _dbus_assert (real->table != NULL);
 525   _dbus_assert (real->entry != NULL);
 526   _dbus_assert (real->bucket != NULL);
 527
 528   remove_entry (real->table, real->bucket, real->entry);
 529
 530   real->entry = NULL; /* make it crash if you try to use this entry */
 531 }
 532
 533 /**
 534  * Gets the value of the current entry.
 535  *
 536  * @param iter the hash table iterator.
 537  */
 538 void*
 539 _dbus_hash_iter_get_value (DBusHashIter *iter)
 540 {
 541   DBusRealHashIter *real;
 542
 543   real = (DBusRealHashIter*) iter;
 544
 545   _dbus_assert (real->table != NULL);
 546   _dbus_assert (real->entry != NULL);
 547
 548   return real->entry->value;
 549 }
 550
 551 /**
 552  * Sets the value of the current entry.
 553  * If the hash table has a value_free_function
 554  * it will be used to free the previous value.
 555  * The hash table will own the passed-in value
 556  * (it will not be copied).
 557  *
 558  * @param iter the hash table iterator.
 559  * @param value the new value.
 560  */
 561 void
 562 _dbus_hash_iter_set_value (DBusHashIter *iter,
 563                            void         *value)
 564 {
 565   DBusRealHashIter *real;
 566
 567   real = (DBusRealHashIter*) iter;
 568
 569   _dbus_assert (real->table != NULL);
 570   _dbus_assert (real->entry != NULL);
 571
 572   if (real->table->free_value_function && value != real->entry->value)
 573     (* real->table->free_value_function) (real->entry->value);
 574
 575   real->entry->value = value;
 576 }
 577
 578 /**
 579  * Gets the key for the current entry.
 580  * Only works for hash tables of type #DBUS_HASH_INT.
 581  *
 582  * @param iter the hash table iterator.
 583  */
 584 int
 585 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
 586 {
 587   DBusRealHashIter *real;
 588
 589   real = (DBusRealHashIter*) iter;
 590
 591   _dbus_assert (real->table != NULL);
 592   _dbus_assert (real->entry != NULL);
 593
 594   return _DBUS_POINTER_TO_INT (real->entry->key);
 595 }
 596
 597 /**
 598  * Gets the key for the current entry.
 599  * Only works for hash tables of type #DBUS_HASH_STRING
 600  * @param iter the hash table iterator.
 601  */
 602 const char*
 603 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
 604 {
 605   DBusRealHashIter *real;
 606
 607   real = (DBusRealHashIter*) iter;
 608
 609   _dbus_assert (real->table != NULL);
 610   _dbus_assert (real->entry != NULL);
 611
 612   return real->entry->key;
 613 }
 614
 615 /**
 616  * A low-level but efficient interface for manipulating the hash
 617  * table.  It's efficient because you can get, set, and optionally
 618  * create the hash entry while only running the hash function one
 619  * time.
 620  *
 621  * Note that while calling _dbus_hash_iter_next() on the iterator
 622  * filled in by this function may work, it's completely
 623  * undefined which entries are after this iter and which
 624  * are before it. So it would be silly to iterate using this
 625  * iterator.
 626  *
 627  * If the hash entry is created, its value will be initialized
 628  * to all bits zero.
 629  *
 630  * #FALSE may be returned due to memory allocation failure, or
 631  * because create_if_not_found was #FALSE and the entry
 632  * did not exist.
 633  *
 634  * For a hash table of type #DBUS_HASH_INT, cast the int
 635  * key to the key parameter using #_DBUS_INT_TO_POINTER().
 636  *
 637  * @param table the hash table.
 638  * @param key the hash key.
 639  * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
 640  * @param iter the iterator to initialize.
 641  * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
 642  */
 643 dbus_bool_t
 644 _dbus_hash_iter_lookup (DBusHashTable *table,
 645                         void          *key,
 646                         dbus_bool_t    create_if_not_found,
 647                         DBusHashIter  *iter)
 648 {
 649   DBusRealHashIter *real;
 650   DBusHashEntry *entry;
 651   DBusHashEntry **bucket;
 652
 653   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 654
 655   real = (DBusRealHashIter*) iter;
 656
 657   entry = (* table->find_function) (table, key, create_if_not_found, &bucket);
 658
 659   if (entry == NULL)
 660     return FALSE;
 661
 662   real->table = table;
 663   real->bucket = bucket;
 664   real->entry = entry;
 665   real->next_entry = entry->next;
 666   real->next_bucket = (bucket - table->buckets) + 1;
 667   real->n_entries_on_init = table->n_entries;
 668
 669   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
 670
 671   return TRUE;
 672 }
 673
 674 static DBusHashEntry*
 675 add_entry (DBusHashTable   *table,
 676            unsigned int     idx,
 677            void            *key,
 678            DBusHashEntry ***bucket)
 679 {
 680   DBusHashEntry  *entry;
 681   DBusHashEntry **b;
 682
 683   entry = alloc_entry (table);
 684   if (entry == NULL)
 685     {
 686       if (bucket)
 687         *bucket = NULL;
 688       return NULL;
 689     }
 690
 691   entry->key = key;
 692
 693   b = &(table->buckets[idx]);
 694   entry->next = *b;
 695   *b = entry;
 696
 697   if (bucket)
 698     *bucket = b;
 699
 700   table->n_entries += 1;
 701
 702   if (table->n_entries >= table->rebuild_size)
 703     rebuild_table (table);
 704
 705   return entry;
 706 }
 707
 708 static unsigned int
 709 string_hash (const char *str)
 710 {
 711   register unsigned int result;
 712   register int c;
 713
 714   /*
 715    * I tried a zillion different hash functions and asked many other
 716    * people for advice.  Many people had their own favorite functions,
 717    * all different, but no-one had much idea why they were good ones.
 718    * I chose the one below (multiply by 9 and add new character)
 719    * because of the following reasons:
 720    *
 721    * 1. Multiplying by 10 is perfect for keys that are decimal strings,
 722    *    and multiplying by 9 is just about as good.
 723    * 2. Times-9 is (shift-left-3) plus (old).  This means that each
 724    *    character's bits hang around in the low-order bits of the
 725    *    hash value for ever, plus they spread fairly rapidly up to
 726    *    the high-order bits to fill out the hash value.  This seems
 727    *    works well both for decimal and non-decimal strings.
 728    */
 729
 730   result = 0;
 731   while (TRUE)
 732     {
 733       c = *str;
 734       str++;
 735       if (c == 0)
 736         break;
 737
 738       result += (result << 3) + c;
 739     }
 740
 741   return result;
 742 }
 743
 744 static DBusHashEntry*
 745 find_string_function (DBusHashTable   *table,
 746                       void            *key,
 747                       dbus_bool_t      create_if_not_found,
 748                       DBusHashEntry ***bucket)
 749 {
 750   DBusHashEntry *entry;
 751   unsigned int idx;
 752
 753   if (bucket)
 754     *bucket = NULL;
 755
 756   idx = string_hash (key) & table->mask;
 757
 758   /* Search all of the entries in this bucket. */
 759   entry = table->buckets[idx];
 760   while (entry != NULL)
 761     {
 762       if (strcmp (key, entry->key) == 0)
 763         {
 764           if (bucket)
 765             *bucket = &(table->buckets[idx]);
 766           return entry;
 767         }
 768
 769       entry = entry->next;
 770     }
 771
 772   if (create_if_not_found)
 773     entry = add_entry (table, idx, key, bucket);
 774
 775   return entry;
 776 }
 777
 778 static DBusHashEntry*
 779 find_int_function (DBusHashTable   *table,
 780                    void            *key,
 781                    dbus_bool_t      create_if_not_found,
 782                    DBusHashEntry ***bucket)
 783 {
 784   DBusHashEntry *entry;
 785   unsigned int idx;
 786
 787   if (bucket)
 788     *bucket = NULL;
 789
 790   idx = RANDOM_INDEX (table, key) & table->mask;
 791
 792   /* Search all of the entries in this bucket. */
 793   entry = table->buckets[idx];
 794   while (entry != NULL)
 795     {
 796       if (key == entry->key)
 797         {
 798           if (bucket)
 799             *bucket = &(table->buckets[idx]);
 800           return entry;
 801         }
 802
 803       entry = entry->next;
 804     }
 805
 806   /* Entry not found.  Add a new one to the bucket. */
 807   if (create_if_not_found)
 808     entry = add_entry (table, idx, key, bucket);
 809
 810   return entry;
 811 }
 812
 813 static void
 814 rebuild_table (DBusHashTable *table)
 815 {
 816   int old_size;
 817   DBusHashEntry **old_buckets;
 818   DBusHashEntry **old_chain;
 819   DBusHashEntry *entry;
 820
 821   /*
 822    * Allocate and initialize the new bucket array, and set up
 823    * hashing constants for new array size.
 824    */
 825
 826   old_size = table->n_buckets;
 827   old_buckets = table->buckets;
 828
 829   table->n_buckets *= 4;
 830   table->buckets = dbus_new0 (DBusHashEntry*, table->n_buckets);
 831   if (table->buckets == NULL)
 832     {
 833       /* out of memory, yay - just don't reallocate, the table will
 834        * still work, albeit more slowly.
 835        */
 836       table->n_buckets /= 4;
 837       table->buckets = old_buckets;
 838       return;
 839     }
 840
 841   table->rebuild_size *= 4;
 842   table->down_shift -= 2;
 843   table->mask = (table->mask << 2) + 3;
 844
 845   /*
 846    * Rehash all of the existing entries into the new bucket array.
 847    */
 848
 849   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
 850     {
 851       for (entry = *old_chain; entry != NULL; entry = *old_chain)
 852         {
 853           unsigned int idx;
 854           DBusHashEntry **bucket;
 855
 856           *old_chain = entry->next;
 857           switch (table->key_type)
 858             {
 859             case DBUS_HASH_STRING:
 860               idx = string_hash (entry->key) & table->mask;
 861               break;
 862             case DBUS_HASH_INT:
 863               idx = RANDOM_INDEX (table, entry->key);
 864               break;
 865             default:
 866               idx = 0;
 867               _dbus_assert_not_reached ("Unknown hash table type");
 868               break;
 869             }
 870
 871           bucket = &(table->buckets[idx]);
 872           entry->next = *bucket;
 873           *bucket = entry;
 874         }
 875     }
 876
 877   /* Free the old bucket array, if it was dynamically allocated. */
 878
 879   if (old_buckets != table->static_buckets)
 880     dbus_free (old_buckets);
 881 }
 882
 883 /**
 884  * Looks up the value for a given string in a hash table
 885  * of type #DBUS_HASH_STRING. Returns %NULL if the value
 886  * is not present. (A not-present entry is indistinguishable
 887  * from an entry with a value of %NULL.)
 888  * @param table the hash table.
 889  * @param key the string to look up.
 890  * @returns the value of the hash entry.
 891  */
 892 void*
 893 _dbus_hash_table_lookup_string (DBusHashTable *table,
 894                                 const char    *key)
 895 {
 896   DBusHashEntry *entry;
 897
 898   _dbus_assert (table->key_type == DBUS_HASH_STRING);
 899
 900   entry = (* table->find_function) (table, (char*) key, FALSE, NULL);
 901
 902   if (entry)
 903     return entry->value;
 904   else
 905     return NULL;
 906 }
 907
 908 /**
 909  * Looks up the value for a given integer in a hash table
 910  * of type #DBUS_HASH_INT. Returns %NULL if the value
 911  * is not present. (A not-present entry is indistinguishable
 912  * from an entry with a value of %NULL.)
 913  * @param table the hash table.
 914  * @param key the integer to look up.
 915  * @returns the value of the hash entry.
 916  */
 917 void*
 918 _dbus_hash_table_lookup_int (DBusHashTable *table,
 919                              int            key)
 920 {
 921   DBusHashEntry *entry;
 922
 923   _dbus_assert (table->key_type == DBUS_HASH_INT);
 924
 925   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL);
 926
 927   if (entry)
 928     return entry->value;
 929   else
 930     return NULL;
 931 }
 932
 933 /**
 934  * Removes the hash entry for the given key. If no hash entry
 935  * for the key exists, does nothing.
 936  *
 937  * @param table the hash table.
 938  * @param key the hash key.
 939  * @returns #TRUE if the entry existed
 940  */
 941 dbus_bool_t
 942 _dbus_hash_table_remove_string (DBusHashTable *table,
 943                                 const char    *key)
 944 {
 945   DBusHashEntry *entry;
 946   DBusHashEntry **bucket;
 947
 948   _dbus_assert (table->key_type == DBUS_HASH_STRING);
 949
 950   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
 951
 952   if (entry)
 953     {
 954       remove_entry (table, bucket, entry);
 955       return TRUE;
 956     }
 957   else
 958     return FALSE;
 959 }
 960
 961 /**
 962  * Removes the hash entry for the given key. If no hash entry
 963  * for the key exists, does nothing.
 964  *
 965  * @param table the hash table.
 966  * @param key the hash key.
 967  * @returns #TRUE if the entry existed
 968  */
 969 dbus_bool_t
 970 _dbus_hash_table_remove_int (DBusHashTable *table,
 971                              int            key)
 972 {
 973   DBusHashEntry *entry;
 974   DBusHashEntry **bucket;
 975
 976   _dbus_assert (table->key_type == DBUS_HASH_INT);
 977
 978   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
 979
 980   if (entry)
 981     {
 982       remove_entry (table, bucket, entry);
 983       return TRUE;
 984     }
 985   else
 986     return FALSE;
 987 }
 988
 989 /**
 990  * Creates a hash entry with the given key and value.
 991  * The key and value are not copied; they are stored
 992  * in the hash table by reference. If an entry with the
 993  * given key already exists, the previous key and value
 994  * are overwritten (and freed if the hash table has
 995  * a key_free_function and/or value_free_function).
 996  *
 997  * Returns #FALSE if memory for the new hash entry
 998  * can't be allocated.
 999  *
1000  * @param table the hash table.
1001  * @param key the hash entry key.
1002  * @param value the hash entry value.
1003  */
1004 dbus_bool_t
1005 _dbus_hash_table_insert_string (DBusHashTable *table,
1006                                 char          *key,
1007                                 void          *value)
1008 {
1009   DBusHashEntry *entry;
1010
1011   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1012
1013   entry = (* table->find_function) (table, key, TRUE, NULL);
1014
1015   if (entry == NULL)
1016     return FALSE; /* no memory */
1017
1018   if (table->free_key_function && entry->key != key)
1019     (* table->free_key_function) (entry->key);
1020
1021   if (table->free_value_function && entry->value != value)
1022     (* table->free_value_function) (entry->value);
1023
1024   entry->key = key;
1025   entry->value = value;
1026
1027   return TRUE;
1028 }
1029
1030 /**
1031  * Creates a hash entry with the given key and value.
1032  * The key and value are not copied; they are stored
1033  * in the hash table by reference. If an entry with the
1034  * given key already exists, the previous key and value
1035  * are overwritten (and freed if the hash table has
1036  * a key_free_function and/or value_free_function).
1037  *
1038  * Returns #FALSE if memory for the new hash entry
1039  * can't be allocated.
1040  *
1041  * @param table the hash table.
1042  * @param key the hash entry key.
1043  * @param value the hash entry value.
1044  */
1045 dbus_bool_t
1046 _dbus_hash_table_insert_int (DBusHashTable *table,
1047                              int            key,
1048                              void          *value)
1049 {
1050   DBusHashEntry *entry;
1051
1052   _dbus_assert (table->key_type == DBUS_HASH_INT);
1053
1054   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL);
1055
1056   if (entry == NULL)
1057     return FALSE; /* no memory */
1058
1059   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1060     (* table->free_key_function) (entry->key);
1061
1062   if (table->free_value_function && entry->value != value)
1063     (* table->free_value_function) (entry->value);
1064
1065   entry->key = _DBUS_INT_TO_POINTER (key);
1066   entry->value = value;
1067
1068   return TRUE;
1069 }
1070
1071 /**
1072  * Gets the number of hash entries in a hash table.
1073  *
1074  * @param table the hash table.
1075  * @returns the number of entries in the table.
1076  */
1077 int
1078 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1079 {
1080   return table->n_entries;
1081 }
1082
1083 /** @} */
1084
1085 #ifdef DBUS_BUILD_TESTS
1086 #include "dbus-test.h"
1087 #include <stdio.h>
1088
1089 static int
1090 count_entries (DBusHashTable *table)
1091 {
1092   DBusHashIter iter;
1093   int count;
1094
1095   count = 0;
1096   _dbus_hash_iter_init (table, &iter);
1097   while (_dbus_hash_iter_next (&iter))
1098     ++count;
1099
1100   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1101
1102   return count;
1103 }
1104
1105 /**
1106  * @ingroup DBusHashTableInternals
1107  * Unit test for DBusHashTable
1108  * @returns #TRUE on success.
1109  */
1110 dbus_bool_t
1111 _dbus_hash_test (void)
1112 {
1113   int i;
1114   DBusHashTable *table1;
1115   DBusHashTable *table2;
1116   DBusHashIter iter;
1117
1118   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1119                                  dbus_free, dbus_free);
1120   if (table1 == NULL)
1121     return FALSE;
1122
1123   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1124                                  NULL, dbus_free);
1125   if (table2 == NULL)
1126     return FALSE;
1127
1128   /* Insert and remove a bunch of stuff, counting the table in between
1129    * to be sure it's not broken and that iteration works
1130    */
1131   i = 0;
1132   while (i < 3000)
1133     {
1134       char buf[256];
1135       sprintf (buf, "Hash key %d", i);
1136       void *value;
1137       char *key;
1138
1139       key = _dbus_strdup (buf);
1140       if (key == NULL)
1141         return FALSE;
1142       value = _dbus_strdup ("Value!");
1143       if (value == NULL)
1144         return FALSE;
1145
1146       if (!_dbus_hash_table_insert_string (table1,
1147                                            key, value))
1148         return FALSE;
1149
1150       value = _dbus_strdup (buf);
1151       if (value == NULL)
1152         return FALSE;
1153
1154       if (!_dbus_hash_table_insert_int (table2,
1155                                         i, value))
1156         return FALSE;
1157
1158       _dbus_assert (count_entries (table1) == i + 1);
1159       _dbus_assert (count_entries (table2) == i + 1);
1160
1161       value = _dbus_hash_table_lookup_string (table1, buf);
1162       _dbus_assert (value != NULL);
1163       _dbus_assert (strcmp (value, "Value!") == 0);
1164
1165       value = _dbus_hash_table_lookup_int (table2, i);
1166       _dbus_assert (value != NULL);
1167       _dbus_assert (strcmp (value, buf) == 0);
1168
1169       ++i;
1170     }
1171
1172   --i;
1173   while (i >= 0)
1174     {
1175       char buf[256];
1176       sprintf (buf, "Hash key %d", i);
1177
1178       _dbus_hash_table_remove_string (table1,
1179                                       buf);
1180
1181       _dbus_hash_table_remove_int (table2, i);
1182
1183       _dbus_assert (count_entries (table1) == i);
1184       _dbus_assert (count_entries (table2) == i);
1185
1186       --i;
1187     }
1188
1189   _dbus_hash_table_ref (table1);
1190   _dbus_hash_table_ref (table2);
1191   _dbus_hash_table_unref (table1);
1192   _dbus_hash_table_unref (table2);
1193   _dbus_hash_table_unref (table1);
1194   _dbus_hash_table_unref (table2);
1195
1196
1197   /* Insert a bunch of stuff then check
1198    * that iteration works correctly (finds the right
1199    * values, iter_set_value works, etc.)
1200    */
1201   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1202                                  dbus_free, dbus_free);
1203   if (table1 == NULL)
1204     return FALSE;
1205
1206   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1207                                  NULL, dbus_free);
1208   if (table2 == NULL)
1209     return FALSE;
1210
1211   i = 0;
1212   while (i < 5000)
1213     {
1214       char buf[256];
1215       sprintf (buf, "Hash key %d", i);
1216       char *key;
1217       void *value;
1218
1219       key = _dbus_strdup (buf);
1220       if (key == NULL)
1221         return FALSE;
1222       value = _dbus_strdup ("Value!");
1223       if (value == NULL)
1224         return FALSE;
1225
1226       if (!_dbus_hash_table_insert_string (table1,
1227                                            key, value))
1228         return FALSE;
1229
1230       value = _dbus_strdup (buf);
1231       if (value == NULL)
1232         return FALSE;
1233
1234       if (!_dbus_hash_table_insert_int (table2,
1235                                         i, value))
1236         return FALSE;
1237
1238       _dbus_assert (count_entries (table1) == i + 1);
1239       _dbus_assert (count_entries (table2) == i + 1);
1240
1241       ++i;
1242     }
1243
1244   _dbus_hash_iter_init (table1, &iter);
1245   while (_dbus_hash_iter_next (&iter))
1246     {
1247       const char *key;
1248       void *value;
1249
1250       key = _dbus_hash_iter_get_string_key (&iter);
1251       value = _dbus_hash_iter_get_value (&iter);
1252
1253       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1254
1255       value = _dbus_strdup ("Different value!");
1256       if (value == NULL)
1257         return FALSE;
1258
1259       _dbus_hash_iter_set_value (&iter, value);
1260
1261       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1262     }
1263
1264   _dbus_hash_iter_init (table1, &iter);
1265   while (_dbus_hash_iter_next (&iter))
1266     {
1267       _dbus_hash_iter_remove_entry (&iter);
1268       _dbus_assert (count_entries (table1) == i - 1);
1269       --i;
1270     }
1271
1272   _dbus_hash_iter_init (table2, &iter);
1273   while (_dbus_hash_iter_next (&iter))
1274     {
1275       int key;
1276       void *value;
1277
1278       key = _dbus_hash_iter_get_int_key (&iter);
1279       value = _dbus_hash_iter_get_value (&iter);
1280
1281       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1282
1283       value = _dbus_strdup ("Different value!");
1284       if (value == NULL)
1285         return FALSE;
1286
1287       _dbus_hash_iter_set_value (&iter, value);
1288
1289       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1290     }
1291
1292   i = count_entries (table2);
1293   _dbus_hash_iter_init (table2, &iter);
1294   while (_dbus_hash_iter_next (&iter))
1295     {
1296       _dbus_hash_iter_remove_entry (&iter);
1297       _dbus_assert (count_entries (table2) + 1 == i);
1298       --i;
1299     }
1300
1301   _dbus_hash_table_unref (table1);
1302   _dbus_hash_table_unref (table2);
1303
1304
1305   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1306    * be sure that interface works.
1307    */
1308   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1309                                  dbus_free, dbus_free);
1310   if (table1 == NULL)
1311     return FALSE;
1312
1313   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1314                                  NULL, dbus_free);
1315   if (table2 == NULL)
1316     return FALSE;
1317
1318   i = 0;
1319   while (i < 3000)
1320     {
1321       char buf[256];
1322       sprintf (buf, "Hash key %d", i);
1323       void *value;
1324       char *key;
1325
1326       key = _dbus_strdup (buf);
1327       if (key == NULL)
1328         return FALSE;
1329       value = _dbus_strdup ("Value!");
1330       if (value == NULL)
1331         return FALSE;
1332
1333       if (!_dbus_hash_iter_lookup (table1,
1334                                    key, TRUE, &iter))
1335         return FALSE;
1336       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1337       _dbus_hash_iter_set_value (&iter, value);
1338
1339       value = _dbus_strdup (buf);
1340       if (value == NULL)
1341         return FALSE;
1342
1343       if (!_dbus_hash_iter_lookup (table2,
1344                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1345         return FALSE;
1346       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1347       _dbus_hash_iter_set_value (&iter, value);
1348
1349       _dbus_assert (count_entries (table1) == i + 1);
1350       _dbus_assert (count_entries (table2) == i + 1);
1351
1352       if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
1353         return FALSE;
1354
1355       value = _dbus_hash_iter_get_value (&iter);
1356       _dbus_assert (value != NULL);
1357       _dbus_assert (strcmp (value, "Value!") == 0);
1358
1359       /* Iterate just to be sure it works, though
1360        * it's a stupid thing to do
1361        */
1362       while (_dbus_hash_iter_next (&iter))
1363         ;
1364
1365       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1366         return FALSE;
1367
1368       value = _dbus_hash_iter_get_value (&iter);
1369       _dbus_assert (value != NULL);
1370       _dbus_assert (strcmp (value, buf) == 0);
1371
1372       /* Iterate just to be sure it works, though
1373        * it's a stupid thing to do
1374        */
1375       while (_dbus_hash_iter_next (&iter))
1376         ;
1377
1378       ++i;
1379     }
1380
1381   --i;
1382   while (i >= 0)
1383     {
1384       char buf[256];
1385       sprintf (buf, "Hash key %d", i);
1386
1387       if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
1388         _dbus_assert_not_reached ("hash entry should have existed");
1389       _dbus_hash_iter_remove_entry (&iter);
1390
1391       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1392         _dbus_assert_not_reached ("hash entry should have existed");
1393       _dbus_hash_iter_remove_entry (&iter);
1394
1395       _dbus_assert (count_entries (table1) == i);
1396       _dbus_assert (count_entries (table2) == i);
1397
1398       --i;
1399     }
1400
1401   _dbus_hash_table_unref (table1);
1402   _dbus_hash_table_unref (table2);
1403
1404
1405   return TRUE;
1406 }
1407
1408 #endif