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 #include "dbus-mempool.h"
  80
  81 /**
  82  * @defgroup DBusHashTable Hash table
  83  * @ingroup  DBusInternals
  84  * @brief DBusHashTable data structure
  85  *
  86  * Types and functions related to DBusHashTable.
  87  */
  88
  89 /**
  90  * @defgroup DBusHashTableInternals Hash table implementation details
  91  * @ingroup  DBusInternals
  92  * @brief DBusHashTable implementation details
  93  *
  94  * The guts of DBusHashTable.
  95  *
  96  * @{
  97  */
  98
  99 /**
 100  * When there are this many entries per bucket, on average, rebuild
 101  * the hash table to make it larger.
 102  */
 103 #define REBUILD_MULTIPLIER  3
 104
 105 /**
 106  * Takes a preliminary integer hash value and produces an index into a
 107  * hash tables bucket list.  The idea is to make it so that
 108  * preliminary values that are arbitrarily similar will end up in
 109  * different buckets.  The hash function was taken from a
 110  * random-number generator. (This is used to hash integers.)
 111  *
 112  * The down_shift drops off the high bits of the hash index, and
 113  * decreases as we increase the number of hash buckets (to keep more
 114  * range in the hash index). The mask also strips high bits and strips
 115  * fewer high bits as the number of hash buckets increases.
 116  * I don't understand two things: why is the initial downshift 28
 117  * to keep 4 bits when the initial mask is 011 to keep 2 bits,
 118  * and why do we have both a mask and a downshift?
 119  *
 120  */
 121 #define RANDOM_INDEX(table, i) \
 122     (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
 123
 124 /**
 125  * Initial number of buckets in hash table (hash table statically
 126  * allocates its buckets for this size and below).
 127  * The initial mask has to be synced to this.
 128  */
 129 #define DBUS_SMALL_HASH_TABLE 4
 130
 131 /**
 132  * Typedef for DBusHashEntry
 133  */
 134 typedef struct DBusHashEntry DBusHashEntry;
 135
 136 /**
 137  * @brief Internal representation of a hash entry.
 138  *
 139  * A single entry (key-value pair) in the hash table.
 140  * Internal to hash table implementation.
 141  */
 142 struct DBusHashEntry
 143 {
 144   DBusHashEntry *next;    /**< Pointer to next entry in this
 145                            * hash bucket, or #NULL for end of
 146                            * chain.
 147                            */
 148   void *key;              /**< Hash key */
 149   void *value;            /**< Hash value */
 150 };
 151
 152 /**
 153  * Function used to find and optionally create a hash entry.
 154  */
 155 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable        *table,
 156                                                   void                 *key,
 157                                                   dbus_bool_t           create_if_not_found,
 158                                                   DBusHashEntry      ***bucket,
 159                                                   DBusPreallocatedHash *preallocated);
 160
 161 /**
 162  * @brief Internals of DBusHashTable.
 163  *
 164  * Hash table internals. Hash tables are opaque objects, they must be
 165  * used via accessor functions.
 166  */
 167 struct DBusHashTable {
 168   int refcount;                       /**< Reference count */
 169
 170   DBusHashEntry **buckets;            /**< Pointer to bucket array.  Each
 171                                        * element points to first entry in
 172                                        * bucket's hash chain, or #NULL.
 173                                        */
 174   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
 175                                        /**< Bucket array used for small tables
 176                                         * (to avoid mallocs and frees).
 177                                         */
 178   int n_buckets;                       /**< Total number of buckets allocated
 179                                         * at **buckets.
 180                                         */
 181   int n_entries;                       /**< Total number of entries present
 182                                         * in table.
 183                                         */
 184   int hi_rebuild_size;                 /**< Enlarge table when n_entries gets
 185                                         * to be this large.
 186                                         */
 187   int lo_rebuild_size;                 /**< Shrink table when n_entries gets
 188                                         * below this.
 189                                         */
 190   int down_shift;                      /**< Shift count used in hashing
 191                                         * function.  Designed to use high-
 192                                         * order bits of randomized keys.
 193                                         */
 194   int mask;                            /**< Mask value used in hashing
 195                                         * function.
 196                                         */
 197   DBusHashType key_type;               /**< Type of keys used in this table */
 198
 199
 200   DBusFindEntryFunction find_function; /**< Function for finding entries */
 201
 202   DBusFreeFunction free_key_function;   /**< Function to free keys */
 203   DBusFreeFunction free_value_function; /**< Function to free values */
 204
 205   DBusMemPool *entry_pool;              /**< Memory pool for hash entries */
 206 };
 207
 208 /**
 209  * @brief Internals of DBusHashIter.
 210  */
 211 typedef struct
 212 {
 213   DBusHashTable *table;     /**< Pointer to table containing entry. */
 214   DBusHashEntry **bucket;   /**< Pointer to bucket that points to
 215                              * first entry in this entry's chain:
 216                              * used for deleting the entry.
 217                              */
 218   DBusHashEntry *entry;      /**< Current hash entry */
 219   DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
 220   int next_bucket;           /**< index of next bucket */
 221   int n_entries_on_init;     /**< used to detect table resize since initialization */
 222 } DBusRealHashIter;
 223
 224 static DBusHashEntry* find_direct_function (DBusHashTable          *table,
 225                                             void                   *key,
 226                                             dbus_bool_t             create_if_not_found,
 227                                             DBusHashEntry        ***bucket,
 228                                             DBusPreallocatedHash   *preallocated);
 229 static DBusHashEntry* find_string_function (DBusHashTable          *table,
 230                                             void                   *key,
 231                                             dbus_bool_t             create_if_not_found,
 232                                             DBusHashEntry        ***bucket,
 233                                             DBusPreallocatedHash   *preallocated);
 234 static unsigned int   string_hash          (const char             *str);
 235 static void           rebuild_table        (DBusHashTable          *table);
 236 static DBusHashEntry* alloc_entry          (DBusHashTable          *table);
 237 static void           remove_entry         (DBusHashTable          *table,
 238                                             DBusHashEntry         **bucket,
 239                                             DBusHashEntry          *entry);
 240 static void           free_entry           (DBusHashTable          *table,
 241                                             DBusHashEntry          *entry);
 242 static void           free_entry_data      (DBusHashTable          *table,
 243                                             DBusHashEntry          *entry);
 244
 245
 246 /** @} */
 247
 248 /**
 249  * @addtogroup DBusHashTable
 250  * @{
 251  */
 252
 253 /**
 254  * @typedef DBusHashIter
 255  *
 256  * Public opaque hash table iterator object.
 257  */
 258
 259 /**
 260  * @typedef DBusHashTable
 261  *
 262  * Public opaque hash table object.
 263  */
 264
 265 /**
 266  * @typedef DBusHashType
 267  *
 268  * Indicates the type of a key in the hash table.
 269  */
 270
 271 /**
 272  * Constructs a new hash table. Should be freed with
 273  * _dbus_hash_table_unref(). If memory cannot be
 274  * allocated for the hash table, returns #NULL.
 275  *
 276  * @param type the type of hash key to use.
 277  * @param key_free_function function to free hash keys.
 278  * @param value_free_function function to free hash values.
 279  * @returns a new DBusHashTable or #NULL if no memory.
 280  */
 281 DBusHashTable*
 282 _dbus_hash_table_new (DBusHashType     type,
 283                       DBusFreeFunction key_free_function,
 284                       DBusFreeFunction value_free_function)
 285 {
 286   DBusHashTable *table;
 287   DBusMemPool *entry_pool;
 288
 289   table = dbus_new0 (DBusHashTable, 1);
 290   if (table == NULL)
 291     return NULL;
 292
 293   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
 294   if (entry_pool == NULL)
 295     {
 296       dbus_free (table);
 297       return NULL;
 298     }
 299
 300   table->refcount = 1;
 301   table->entry_pool = entry_pool;
 302
 303   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
 304
 305   table->buckets = table->static_buckets;
 306   table->n_buckets = DBUS_SMALL_HASH_TABLE;
 307   table->n_entries = 0;
 308   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
 309   table->lo_rebuild_size = 0;
 310   table->down_shift = 28;
 311   table->mask = 3;
 312   table->key_type = type;
 313
 314   _dbus_assert (table->mask < table->n_buckets);
 315
 316   switch (table->key_type)
 317     {
 318     case DBUS_HASH_INT:
 319     case DBUS_HASH_POINTER:
 320     case DBUS_HASH_ULONG:
 321       table->find_function = find_direct_function;
 322       break;
 323     case DBUS_HASH_STRING:
 324       table->find_function = find_string_function;
 325       break;
 326     default:
 327       _dbus_assert_not_reached ("Unknown hash table type");
 328       break;
 329     }
 330
 331   table->free_key_function = key_free_function;
 332   table->free_value_function = value_free_function;
 333
 334   return table;
 335 }
 336
 337
 338 /**
 339  * Increments the reference count for a hash table.
 340  *
 341  * @param table the hash table to add a reference to.
 342  */
 343 void
 344 _dbus_hash_table_ref (DBusHashTable *table)
 345 {
 346   table->refcount += 1;
 347 }
 348
 349 /**
 350  * Decrements the reference count for a hash table,
 351  * freeing the hash table if the count reaches zero.
 352  *
 353  * @param table the hash table to remove a reference from.
 354  */
 355 void
 356 _dbus_hash_table_unref (DBusHashTable *table)
 357 {
 358   table->refcount -= 1;
 359
 360   if (table->refcount == 0)
 361     {
 362 #if 0
 363       DBusHashEntry *entry;
 364       DBusHashEntry *next;
 365       int i;
 366
 367       /* Free the entries in the table. */
 368       for (i = 0; i < table->n_buckets; i++)
 369         {
 370           entry = table->buckets[i];
 371           while (entry != NULL)
 372             {
 373               next = entry->next;
 374
 375               free_entry (table, entry);
 376
 377               entry = next;
 378             }
 379         }
 380 #else
 381       DBusHashEntry *entry;
 382       int i;
 383
 384       /* Free the entries in the table. */
 385       for (i = 0; i < table->n_buckets; i++)
 386         {
 387           entry = table->buckets[i];
 388           while (entry != NULL)
 389             {
 390               free_entry_data (table, entry);
 391
 392               entry = entry->next;
 393             }
 394         }
 395       /* We can do this very quickly with memory pools ;-) */
 396       _dbus_mem_pool_free (table->entry_pool);
 397 #endif
 398
 399       /* Free the bucket array, if it was dynamically allocated. */
 400       if (table->buckets != table->static_buckets)
 401         dbus_free (table->buckets);
 402
 403       dbus_free (table);
 404     }
 405 }
 406
 407 static DBusHashEntry*
 408 alloc_entry (DBusHashTable *table)
 409 {
 410   DBusHashEntry *entry;
 411
 412   entry = _dbus_mem_pool_alloc (table->entry_pool);
 413
 414   return entry;
 415 }
 416
 417 static void
 418 free_entry_data (DBusHashTable  *table,
 419                  DBusHashEntry  *entry)
 420 {
 421   if (table->free_key_function)
 422     (* table->free_key_function) (entry->key);
 423   if (table->free_value_function)
 424     (* table->free_value_function) (entry->value);
 425 }
 426
 427 static void
 428 free_entry (DBusHashTable  *table,
 429             DBusHashEntry  *entry)
 430 {
 431   free_entry_data (table, entry);
 432   _dbus_mem_pool_dealloc (table->entry_pool, entry);
 433 }
 434
 435 static void
 436 remove_entry (DBusHashTable  *table,
 437               DBusHashEntry **bucket,
 438               DBusHashEntry  *entry)
 439 {
 440   _dbus_assert (table != NULL);
 441   _dbus_assert (bucket != NULL);
 442   _dbus_assert (*bucket != NULL);
 443   _dbus_assert (entry != NULL);
 444
 445   if (*bucket == entry)
 446     *bucket = entry->next;
 447   else
 448     {
 449       DBusHashEntry *prev;
 450       prev = *bucket;
 451
 452       while (prev->next != entry)
 453         prev = prev->next;
 454
 455       _dbus_assert (prev != NULL);
 456
 457       prev->next = entry->next;
 458     }
 459
 460   table->n_entries -= 1;
 461   free_entry (table, entry);
 462 }
 463
 464 /**
 465  * Initializes a hash table iterator. To iterate over all entries in a
 466  * hash table, use the following code (the printf assumes a hash
 467  * from strings to strings obviously):
 468  *
 469  * @code
 470  * DBusHashIter iter;
 471  *
 472  * _dbus_hash_iter_init (table, &iter);
 473  * while (_dbus_hash_iter_next (&iter))
 474  *   {
 475  *      printf ("The first key is %s and value is %s\n",
 476  *              _dbus_hash_iter_get_string_key (&iter),
 477  *              _dbus_hash_iter_get_value (&iter));
 478  *   }
 479  *
 480  *
 481  * @endcode
 482  *
 483  * The iterator is initialized pointing "one before" the first hash
 484  * entry. The first call to _dbus_hash_iter_next() moves it onto
 485  * the first valid entry or returns #FALSE if the hash table is
 486  * empty. Subsequent calls move to the next valid entry or return
 487  * #FALSE if there are no more entries.
 488  *
 489  * Note that it is guaranteed to be safe to remove a hash entry during
 490  * iteration, but it is not safe to add a hash entry.
 491  *
 492  * @param table the hash table to iterate over.
 493  * @param iter the iterator to initialize.
 494  */
 495 void
 496 _dbus_hash_iter_init (DBusHashTable *table,
 497                       DBusHashIter  *iter)
 498 {
 499   DBusRealHashIter *real;
 500
 501   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 502
 503   real = (DBusRealHashIter*) iter;
 504
 505   real->table = table;
 506   real->bucket = NULL;
 507   real->entry = NULL;
 508   real->next_entry = NULL;
 509   real->next_bucket = 0;
 510   real->n_entries_on_init = table->n_entries;
 511 }
 512
 513 /**
 514  * Move the hash iterator forward one step, to the next hash entry.
 515  * The documentation for _dbus_hash_iter_init() explains in more
 516  * detail.
 517  *
 518  * @param iter the iterator to move forward.
 519  * @returns #FALSE if there are no more entries to move to.
 520  */
 521 dbus_bool_t
 522 _dbus_hash_iter_next (DBusHashIter  *iter)
 523 {
 524   DBusRealHashIter *real;
 525
 526   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 527
 528   real = (DBusRealHashIter*) iter;
 529
 530   /* if this assertion failed someone probably added hash entries
 531    * during iteration, which is bad.
 532    */
 533   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
 534
 535   /* Remember that real->entry may have been deleted */
 536
 537   while (real->next_entry == NULL)
 538     {
 539       if (real->next_bucket >= real->table->n_buckets)
 540         {
 541           /* invalidate iter and return false */
 542           real->entry = NULL;
 543           real->table = NULL;
 544           real->bucket = NULL;
 545           return FALSE;
 546         }
 547
 548       real->bucket = &(real->table->buckets[real->next_bucket]);
 549       real->next_entry = *(real->bucket);
 550       real->next_bucket += 1;
 551     }
 552
 553   _dbus_assert (real->next_entry != NULL);
 554   _dbus_assert (real->bucket != NULL);
 555
 556   real->entry = real->next_entry;
 557   real->next_entry = real->entry->next;
 558
 559   return TRUE;
 560 }
 561
 562 /**
 563  * Removes the current entry from the hash table.
 564  * If a key_free_function or value_free_function
 565  * was provided to _dbus_hash_table_new(),
 566  * frees the key and/or value for this entry.
 567  *
 568  * @param iter the hash table iterator.
 569  */
 570 void
 571 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
 572 {
 573   DBusRealHashIter *real;
 574
 575   real = (DBusRealHashIter*) iter;
 576
 577   _dbus_assert (real->table != NULL);
 578   _dbus_assert (real->entry != NULL);
 579   _dbus_assert (real->bucket != NULL);
 580
 581   remove_entry (real->table, real->bucket, real->entry);
 582
 583   real->entry = NULL; /* make it crash if you try to use this entry */
 584 }
 585
 586 /**
 587  * Gets the value of the current entry.
 588  *
 589  * @param iter the hash table iterator.
 590  */
 591 void*
 592 _dbus_hash_iter_get_value (DBusHashIter *iter)
 593 {
 594   DBusRealHashIter *real;
 595
 596   real = (DBusRealHashIter*) iter;
 597
 598   _dbus_assert (real->table != NULL);
 599   _dbus_assert (real->entry != NULL);
 600
 601   return real->entry->value;
 602 }
 603
 604 /**
 605  * Sets the value of the current entry.
 606  * If the hash table has a value_free_function
 607  * it will be used to free the previous value.
 608  * The hash table will own the passed-in value
 609  * (it will not be copied).
 610  *
 611  * @param iter the hash table iterator.
 612  * @param value the new value.
 613  */
 614 void
 615 _dbus_hash_iter_set_value (DBusHashIter *iter,
 616                            void         *value)
 617 {
 618   DBusRealHashIter *real;
 619
 620   real = (DBusRealHashIter*) iter;
 621
 622   _dbus_assert (real->table != NULL);
 623   _dbus_assert (real->entry != NULL);
 624
 625   if (real->table->free_value_function && value != real->entry->value)
 626     (* real->table->free_value_function) (real->entry->value);
 627
 628   real->entry->value = value;
 629 }
 630
 631 /**
 632  * Gets the key for the current entry.
 633  * Only works for hash tables of type #DBUS_HASH_INT.
 634  *
 635  * @param iter the hash table iterator.
 636  */
 637 int
 638 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
 639 {
 640   DBusRealHashIter *real;
 641
 642   real = (DBusRealHashIter*) iter;
 643
 644   _dbus_assert (real->table != NULL);
 645   _dbus_assert (real->entry != NULL);
 646
 647   return _DBUS_POINTER_TO_INT (real->entry->key);
 648 }
 649
 650 /**
 651  * Gets the key for the current entry.
 652  * Only works for hash tables of type #DBUS_HASH_ULONG.
 653  *
 654  * @param iter the hash table iterator.
 655  */
 656 unsigned long
 657 _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
 658 {
 659   DBusRealHashIter *real;
 660
 661   real = (DBusRealHashIter*) iter;
 662
 663   _dbus_assert (real->table != NULL);
 664   _dbus_assert (real->entry != NULL);
 665
 666   return (unsigned long) real->entry->key;
 667 }
 668
 669 /**
 670  * Gets the key for the current entry.
 671  * Only works for hash tables of type #DBUS_HASH_STRING
 672  * @param iter the hash table iterator.
 673  */
 674 const char*
 675 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
 676 {
 677   DBusRealHashIter *real;
 678
 679   real = (DBusRealHashIter*) iter;
 680
 681   _dbus_assert (real->table != NULL);
 682   _dbus_assert (real->entry != NULL);
 683
 684   return real->entry->key;
 685 }
 686
 687 /**
 688  * A low-level but efficient interface for manipulating the hash
 689  * table.  It's efficient because you can get, set, and optionally
 690  * create the hash entry while only running the hash function one
 691  * time.
 692  *
 693  * Note that while calling _dbus_hash_iter_next() on the iterator
 694  * filled in by this function may work, it's completely
 695  * undefined which entries are after this iter and which
 696  * are before it. So it would be silly to iterate using this
 697  * iterator.
 698  *
 699  * If the hash entry is created, its value will be initialized
 700  * to all bits zero.
 701  *
 702  * #FALSE may be returned due to memory allocation failure, or
 703  * because create_if_not_found was #FALSE and the entry
 704  * did not exist.
 705  *
 706  * If create_if_not_found is #TRUE and the entry is created, the hash
 707  * table takes ownership of the key that's passed in.
 708  *
 709  * For a hash table of type #DBUS_HASH_INT, cast the int
 710  * key to the key parameter using #_DBUS_INT_TO_POINTER().
 711  *
 712  * @param table the hash table.
 713  * @param key the hash key.
 714  * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
 715  * @param iter the iterator to initialize.
 716  * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
 717  */
 718 dbus_bool_t
 719 _dbus_hash_iter_lookup (DBusHashTable *table,
 720                         void          *key,
 721                         dbus_bool_t    create_if_not_found,
 722                         DBusHashIter  *iter)
 723 {
 724   DBusRealHashIter *real;
 725   DBusHashEntry *entry;
 726   DBusHashEntry **bucket;
 727
 728   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 729
 730   real = (DBusRealHashIter*) iter;
 731
 732   entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
 733
 734   if (entry == NULL)
 735     return FALSE;
 736
 737   real->table = table;
 738   real->bucket = bucket;
 739   real->entry = entry;
 740   real->next_entry = entry->next;
 741   real->next_bucket = (bucket - table->buckets) + 1;
 742   real->n_entries_on_init = table->n_entries;
 743
 744   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
 745
 746   return TRUE;
 747 }
 748
 749 static void
 750 add_allocated_entry (DBusHashTable   *table,
 751                      DBusHashEntry   *entry,
 752                      unsigned int     idx,
 753                      void            *key,
 754                      DBusHashEntry ***bucket)
 755 {
 756   DBusHashEntry **b;
 757
 758   entry->key = key;
 759
 760   b = &(table->buckets[idx]);
 761   entry->next = *b;
 762   *b = entry;
 763
 764   if (bucket)
 765     *bucket = b;
 766
 767   table->n_entries += 1;
 768
 769   /* note we ONLY rebuild when ADDING - because you can iterate over a
 770    * table and remove entries safely.
 771    */
 772   if (table->n_entries >= table->hi_rebuild_size ||
 773       table->n_entries < table->lo_rebuild_size)
 774     rebuild_table (table);
 775 }
 776
 777 static DBusHashEntry*
 778 add_entry (DBusHashTable        *table,
 779            unsigned int          idx,
 780            void                 *key,
 781            DBusHashEntry      ***bucket,
 782            DBusPreallocatedHash *preallocated)
 783 {
 784   DBusHashEntry  *entry;
 785
 786   if (preallocated == NULL)
 787     {
 788       entry = alloc_entry (table);
 789       if (entry == NULL)
 790         {
 791           if (bucket)
 792             *bucket = NULL;
 793           return NULL;
 794         }
 795     }
 796   else
 797     {
 798       entry = (DBusHashEntry*) preallocated;
 799     }
 800
 801   add_allocated_entry (table, entry, idx, key, bucket);
 802
 803   return entry;
 804 }
 805
 806 static unsigned int
 807 string_hash (const char *str)
 808 {
 809   register unsigned int result;
 810   register int c;
 811
 812   /*
 813    * I tried a zillion different hash functions and asked many other
 814    * people for advice.  Many people had their own favorite functions,
 815    * all different, but no-one had much idea why they were good ones.
 816    * I chose the one below (multiply by 9 and add new character)
 817    * because of the following reasons:
 818    *
 819    * 1. Multiplying by 10 is perfect for keys that are decimal strings,
 820    *    and multiplying by 9 is just about as good.
 821    * 2. Times-9 is (shift-left-3) plus (old).  This means that each
 822    *    character's bits hang around in the low-order bits of the
 823    *    hash value for ever, plus they spread fairly rapidly up to
 824    *    the high-order bits to fill out the hash value.  This seems
 825    *    works well both for decimal and non-decimal strings.
 826    */
 827
 828   /* FIXME the hash function in GLib is better than this one */
 829
 830   result = 0;
 831   while (TRUE)
 832     {
 833       c = *str;
 834       str++;
 835       if (c == 0)
 836         break;
 837
 838       result += (result << 3) + c;
 839     }
 840
 841   return result;
 842 }
 843
 844 static DBusHashEntry*
 845 find_string_function (DBusHashTable        *table,
 846                       void                 *key,
 847                       dbus_bool_t           create_if_not_found,
 848                       DBusHashEntry      ***bucket,
 849                       DBusPreallocatedHash *preallocated)
 850 {
 851   DBusHashEntry *entry;
 852   unsigned int idx;
 853
 854   if (bucket)
 855     *bucket = NULL;
 856
 857   idx = string_hash (key) & table->mask;
 858
 859   /* Search all of the entries in this bucket. */
 860   entry = table->buckets[idx];
 861   while (entry != NULL)
 862     {
 863       if (strcmp (key, entry->key) == 0)
 864         {
 865           if (bucket)
 866             *bucket = &(table->buckets[idx]);
 867
 868           if (preallocated)
 869             _dbus_hash_table_free_preallocated_entry (table, preallocated);
 870
 871           return entry;
 872         }
 873
 874       entry = entry->next;
 875     }
 876
 877   if (create_if_not_found)
 878     entry = add_entry (table, idx, key, bucket, preallocated);
 879   else if (preallocated)
 880     _dbus_hash_table_free_preallocated_entry (table, preallocated);
 881
 882   return entry;
 883 }
 884
 885 static DBusHashEntry*
 886 find_direct_function (DBusHashTable        *table,
 887                       void                 *key,
 888                       dbus_bool_t           create_if_not_found,
 889                       DBusHashEntry      ***bucket,
 890                       DBusPreallocatedHash *preallocated)
 891 {
 892   DBusHashEntry *entry;
 893   unsigned int idx;
 894
 895   if (bucket)
 896     *bucket = NULL;
 897
 898   idx = RANDOM_INDEX (table, key) & table->mask;
 899
 900   /* Search all of the entries in this bucket. */
 901   entry = table->buckets[idx];
 902   while (entry != NULL)
 903     {
 904       if (key == entry->key)
 905         {
 906           if (bucket)
 907             *bucket = &(table->buckets[idx]);
 908
 909           if (preallocated)
 910             _dbus_hash_table_free_preallocated_entry (table, preallocated);
 911
 912           return entry;
 913         }
 914
 915       entry = entry->next;
 916     }
 917
 918   /* Entry not found.  Add a new one to the bucket. */
 919   if (create_if_not_found)
 920     entry = add_entry (table, idx, key, bucket, preallocated);
 921   else if (preallocated)
 922     _dbus_hash_table_free_preallocated_entry (table, preallocated);
 923
 924   return entry;
 925 }
 926
 927 static void
 928 rebuild_table (DBusHashTable *table)
 929 {
 930   int old_size;
 931   int new_buckets;
 932   DBusHashEntry **old_buckets;
 933   DBusHashEntry **old_chain;
 934   DBusHashEntry *entry;
 935   dbus_bool_t growing;
 936
 937   /*
 938    * Allocate and initialize the new bucket array, and set up
 939    * hashing constants for new array size.
 940    */
 941
 942   growing = table->n_entries >= table->hi_rebuild_size;
 943
 944   old_size = table->n_buckets;
 945   old_buckets = table->buckets;
 946
 947   if (growing)
 948     {
 949       /* overflow paranoia */
 950       if (table->n_buckets < _DBUS_INT_MAX / 4 &&
 951           table->down_shift >= 0)
 952         new_buckets = table->n_buckets * 4;
 953       else
 954         return; /* can't grow anymore */
 955     }
 956   else
 957     {
 958       new_buckets = table->n_buckets / 4;
 959       if (new_buckets < DBUS_SMALL_HASH_TABLE)
 960         return; /* don't bother shrinking this far */
 961     }
 962
 963   table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
 964   if (table->buckets == NULL)
 965     {
 966       /* out of memory, yay - just don't reallocate, the table will
 967        * still work, albeit more slowly.
 968        */
 969       table->buckets = old_buckets;
 970       return;
 971     }
 972
 973   table->n_buckets = new_buckets;
 974
 975   if (growing)
 976     {
 977       table->lo_rebuild_size = table->hi_rebuild_size;
 978       table->hi_rebuild_size *= 4;
 979
 980       table->down_shift -= 2;               /* keep 2 more high bits */
 981       table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
 982     }
 983   else
 984     {
 985       table->hi_rebuild_size = table->lo_rebuild_size;
 986       table->lo_rebuild_size /= 4;
 987
 988       table->down_shift += 2;         /* keep 2 fewer high bits */
 989       table->mask = table->mask >> 2; /* keep 2 fewer high bits */
 990     }
 991
 992 #if 0
 993   printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
 994           growing ? "GROW" : "SHRINK",
 995           table->lo_rebuild_size,
 996           table->hi_rebuild_size,
 997           table->down_shift,
 998           table->mask);
 999 #endif
1000
1001   _dbus_assert (table->lo_rebuild_size >= 0);
1002   _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
1003   _dbus_assert (table->mask != 0);
1004   /* the mask is essentially the max index */
1005   _dbus_assert (table->mask < table->n_buckets);
1006
1007   /*
1008    * Rehash all of the existing entries into the new bucket array.
1009    */
1010
1011   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1012     {
1013       for (entry = *old_chain; entry != NULL; entry = *old_chain)
1014         {
1015           unsigned int idx;
1016           DBusHashEntry **bucket;
1017
1018           *old_chain = entry->next;
1019           switch (table->key_type)
1020             {
1021             case DBUS_HASH_STRING:
1022               idx = string_hash (entry->key) & table->mask;
1023               break;
1024             case DBUS_HASH_INT:
1025             case DBUS_HASH_ULONG:
1026             case DBUS_HASH_POINTER:
1027               idx = RANDOM_INDEX (table, entry->key);
1028               break;
1029             default:
1030               idx = 0;
1031               _dbus_assert_not_reached ("Unknown hash table type");
1032               break;
1033             }
1034
1035           bucket = &(table->buckets[idx]);
1036           entry->next = *bucket;
1037           *bucket = entry;
1038         }
1039     }
1040
1041   /* Free the old bucket array, if it was dynamically allocated. */
1042
1043   if (old_buckets != table->static_buckets)
1044     dbus_free (old_buckets);
1045 }
1046
1047 /**
1048  * Looks up the value for a given string in a hash table
1049  * of type #DBUS_HASH_STRING. Returns %NULL if the value
1050  * is not present. (A not-present entry is indistinguishable
1051  * from an entry with a value of %NULL.)
1052  * @param table the hash table.
1053  * @param key the string to look up.
1054  * @returns the value of the hash entry.
1055  */
1056 void*
1057 _dbus_hash_table_lookup_string (DBusHashTable *table,
1058                                 const char    *key)
1059 {
1060   DBusHashEntry *entry;
1061
1062   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1063
1064   entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1065
1066   if (entry)
1067     return entry->value;
1068   else
1069     return NULL;
1070 }
1071
1072 /**
1073  * Looks up the value for a given integer in a hash table
1074  * of type #DBUS_HASH_INT. Returns %NULL if the value
1075  * is not present. (A not-present entry is indistinguishable
1076  * from an entry with a value of %NULL.)
1077  * @param table the hash table.
1078  * @param key the integer to look up.
1079  * @returns the value of the hash entry.
1080  */
1081 void*
1082 _dbus_hash_table_lookup_int (DBusHashTable *table,
1083                              int            key)
1084 {
1085   DBusHashEntry *entry;
1086
1087   _dbus_assert (table->key_type == DBUS_HASH_INT);
1088
1089   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1090
1091   if (entry)
1092     return entry->value;
1093   else
1094     return NULL;
1095 }
1096
1097 /**
1098  * Looks up the value for a given integer in a hash table
1099  * of type #DBUS_HASH_POINTER. Returns %NULL if the value
1100  * is not present. (A not-present entry is indistinguishable
1101  * from an entry with a value of %NULL.)
1102  * @param table the hash table.
1103  * @param key the integer to look up.
1104  * @returns the value of the hash entry.
1105  */
1106 void*
1107 _dbus_hash_table_lookup_pointer (DBusHashTable *table,
1108                                  void          *key)
1109 {
1110   DBusHashEntry *entry;
1111
1112   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1113
1114   entry = (* table->find_function) (table, key, FALSE, NULL, NULL);
1115
1116   if (entry)
1117     return entry->value;
1118   else
1119     return NULL;
1120 }
1121
1122 /**
1123  * Looks up the value for a given integer in a hash table
1124  * of type #DBUS_HASH_ULONG. Returns %NULL if the value
1125  * is not present. (A not-present entry is indistinguishable
1126  * from an entry with a value of %NULL.)
1127  * @param table the hash table.
1128  * @param key the integer to look up.
1129  * @returns the value of the hash entry.
1130  */
1131 void*
1132 _dbus_hash_table_lookup_ulong (DBusHashTable *table,
1133                                unsigned long  key)
1134 {
1135   DBusHashEntry *entry;
1136
1137   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
1138
1139   entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1140
1141   if (entry)
1142     return entry->value;
1143   else
1144     return NULL;
1145 }
1146
1147 /**
1148  * Removes the hash entry for the given key. If no hash entry
1149  * for the key exists, does nothing.
1150  *
1151  * @param table the hash table.
1152  * @param key the hash key.
1153  * @returns #TRUE if the entry existed
1154  */
1155 dbus_bool_t
1156 _dbus_hash_table_remove_string (DBusHashTable *table,
1157                                 const char    *key)
1158 {
1159   DBusHashEntry *entry;
1160   DBusHashEntry **bucket;
1161
1162   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1163
1164   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1165
1166   if (entry)
1167     {
1168       remove_entry (table, bucket, entry);
1169       return TRUE;
1170     }
1171   else
1172     return FALSE;
1173 }
1174
1175 /**
1176  * Removes the hash entry for the given key. If no hash entry
1177  * for the key exists, does nothing.
1178  *
1179  * @param table the hash table.
1180  * @param key the hash key.
1181  * @returns #TRUE if the entry existed
1182  */
1183 dbus_bool_t
1184 _dbus_hash_table_remove_int (DBusHashTable *table,
1185                              int            key)
1186 {
1187   DBusHashEntry *entry;
1188   DBusHashEntry **bucket;
1189
1190   _dbus_assert (table->key_type == DBUS_HASH_INT);
1191
1192   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1193
1194   if (entry)
1195     {
1196       remove_entry (table, bucket, entry);
1197       return TRUE;
1198     }
1199   else
1200     return FALSE;
1201 }
1202
1203 /**
1204  * Removes the hash entry for the given key. If no hash entry
1205  * for the key exists, does nothing.
1206  *
1207  * @param table the hash table.
1208  * @param key the hash key.
1209  * @returns #TRUE if the entry existed
1210  */
1211 dbus_bool_t
1212 _dbus_hash_table_remove_pointer (DBusHashTable *table,
1213                                  void          *key)
1214 {
1215   DBusHashEntry *entry;
1216   DBusHashEntry **bucket;
1217
1218   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1219
1220   entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);
1221
1222   if (entry)
1223     {
1224       remove_entry (table, bucket, entry);
1225       return TRUE;
1226     }
1227   else
1228     return FALSE;
1229 }
1230
1231
1232 /**
1233  * Removes the hash entry for the given key. If no hash entry
1234  * for the key exists, does nothing.
1235  *
1236  * @param table the hash table.
1237  * @param key the hash key.
1238  * @returns #TRUE if the entry existed
1239  */
1240 dbus_bool_t
1241 _dbus_hash_table_remove_ulong (DBusHashTable *table,
1242                                unsigned long  key)
1243 {
1244   DBusHashEntry *entry;
1245   DBusHashEntry **bucket;
1246
1247   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
1248
1249   entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1250
1251   if (entry)
1252     {
1253       remove_entry (table, bucket, entry);
1254       return TRUE;
1255     }
1256   else
1257     return FALSE;
1258 }
1259
1260 /**
1261  * Creates a hash entry with the given key and value.
1262  * The key and value are not copied; they are stored
1263  * in the hash table by reference. If an entry with the
1264  * given key already exists, the previous key and value
1265  * are overwritten (and freed if the hash table has
1266  * a key_free_function and/or value_free_function).
1267  *
1268  * Returns #FALSE if memory for the new hash entry
1269  * can't be allocated.
1270  *
1271  * @param table the hash table.
1272  * @param key the hash entry key.
1273  * @param value the hash entry value.
1274  */
1275 dbus_bool_t
1276 _dbus_hash_table_insert_string (DBusHashTable *table,
1277                                 char          *key,
1278                                 void          *value)
1279 {
1280   DBusPreallocatedHash *preallocated;
1281
1282   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1283
1284   preallocated = _dbus_hash_table_preallocate_entry (table);
1285   if (preallocated == NULL)
1286     return FALSE;
1287
1288   _dbus_hash_table_insert_string_preallocated (table, preallocated,
1289                                                key, value);
1290
1291   return TRUE;
1292 }
1293
1294 /**
1295  * Creates a hash entry with the given key and value.
1296  * The key and value are not copied; they are stored
1297  * in the hash table by reference. If an entry with the
1298  * given key already exists, the previous key and value
1299  * are overwritten (and freed if the hash table has
1300  * a key_free_function and/or value_free_function).
1301  *
1302  * Returns #FALSE if memory for the new hash entry
1303  * can't be allocated.
1304  *
1305  * @param table the hash table.
1306  * @param key the hash entry key.
1307  * @param value the hash entry value.
1308  */
1309 dbus_bool_t
1310 _dbus_hash_table_insert_int (DBusHashTable *table,
1311                              int            key,
1312                              void          *value)
1313 {
1314   DBusHashEntry *entry;
1315
1316   _dbus_assert (table->key_type == DBUS_HASH_INT);
1317
1318   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1319
1320   if (entry == NULL)
1321     return FALSE; /* no memory */
1322
1323   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1324     (* table->free_key_function) (entry->key);
1325
1326   if (table->free_value_function && entry->value != value)
1327     (* table->free_value_function) (entry->value);
1328
1329   entry->key = _DBUS_INT_TO_POINTER (key);
1330   entry->value = value;
1331
1332   return TRUE;
1333 }
1334
1335 /**
1336  * Creates a hash entry with the given key and value.
1337  * The key and value are not copied; they are stored
1338  * in the hash table by reference. If an entry with the
1339  * given key already exists, the previous key and value
1340  * are overwritten (and freed if the hash table has
1341  * a key_free_function and/or value_free_function).
1342  *
1343  * Returns #FALSE if memory for the new hash entry
1344  * can't be allocated.
1345  *
1346  * @param table the hash table.
1347  * @param key the hash entry key.
1348  * @param value the hash entry value.
1349  */
1350 dbus_bool_t
1351 _dbus_hash_table_insert_pointer (DBusHashTable *table,
1352                                  void          *key,
1353                                  void          *value)
1354 {
1355   DBusHashEntry *entry;
1356
1357   _dbus_assert (table->key_type == DBUS_HASH_POINTER);
1358
1359   entry = (* table->find_function) (table, key, TRUE, NULL, NULL);
1360
1361   if (entry == NULL)
1362     return FALSE; /* no memory */
1363
1364   if (table->free_key_function && entry->key != key)
1365     (* table->free_key_function) (entry->key);
1366
1367   if (table->free_value_function && entry->value != value)
1368     (* table->free_value_function) (entry->value);
1369
1370   entry->key = key;
1371   entry->value = value;
1372
1373   return TRUE;
1374 }
1375
1376
1377 /**
1378  * Creates a hash entry with the given key and value.
1379  * The key and value are not copied; they are stored
1380  * in the hash table by reference. If an entry with the
1381  * given key already exists, the previous key and value
1382  * are overwritten (and freed if the hash table has
1383  * a key_free_function and/or value_free_function).
1384  *
1385  * Returns #FALSE if memory for the new hash entry
1386  * can't be allocated.
1387  *
1388  * @param table the hash table.
1389  * @param key the hash entry key.
1390  * @param value the hash entry value.
1391  */
1392 dbus_bool_t
1393 _dbus_hash_table_insert_ulong (DBusHashTable *table,
1394                                unsigned long  key,
1395                                void          *value)
1396 {
1397   DBusHashEntry *entry;
1398
1399   _dbus_assert (table->key_type == DBUS_HASH_ULONG);
1400
1401   entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1402
1403   if (entry == NULL)
1404     return FALSE; /* no memory */
1405
1406   if (table->free_key_function && entry->key != (void*) key)
1407     (* table->free_key_function) (entry->key);
1408
1409   if (table->free_value_function && entry->value != value)
1410     (* table->free_value_function) (entry->value);
1411
1412   entry->key = (void*) key;
1413   entry->value = value;
1414
1415   return TRUE;
1416 }
1417
1418 /**
1419  * Preallocate an opaque data blob that allows us to insert into the
1420  * hash table at a later time without allocating any memory.
1421  *
1422  * @param table the hash table
1423  * @returns the preallocated data, or #NULL if no memory
1424  */
1425 DBusPreallocatedHash*
1426 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
1427 {
1428   DBusHashEntry *entry;
1429
1430   entry = alloc_entry (table);
1431
1432   return (DBusPreallocatedHash*) entry;
1433 }
1434
1435 /**
1436  * Frees an opaque DBusPreallocatedHash that was *not* used
1437  * in order to insert into the hash table.
1438  *
1439  * @param table the hash table
1440  * @param preallocated the preallocated data
1441  */
1442 void
1443 _dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
1444                                           DBusPreallocatedHash *preallocated)
1445 {
1446   DBusHashEntry *entry;
1447
1448   _dbus_assert (preallocated != NULL);
1449
1450   entry = (DBusHashEntry*) preallocated;
1451
1452   /* Don't use free_entry(), since this entry has no key/data */
1453   _dbus_mem_pool_dealloc (table->entry_pool, entry);
1454 }
1455
1456 /**
1457  * Inserts a string-keyed entry into the hash table, using a
1458  * preallocated data block from
1459  * _dbus_hash_table_preallocate_entry(). This function cannot fail due
1460  * to lack of memory. The DBusPreallocatedHash object is consumed and
1461  * should not be reused or freed. Otherwise this function works
1462  * just like _dbus_hash_table_insert_string().
1463  *
1464  * @param table the hash table
1465  * @param preallocated the preallocated data
1466  * @param key the hash key
1467  * @param value the value
1468  */
1469 void
1470 _dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
1471                                              DBusPreallocatedHash *preallocated,
1472                                              char                 *key,
1473                                              void                 *value)
1474 {
1475   DBusHashEntry *entry;
1476
1477   _dbus_assert (table->key_type == DBUS_HASH_STRING);
1478   _dbus_assert (preallocated != NULL);
1479
1480   entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1481
1482   _dbus_assert (entry != NULL);
1483
1484   if (table->free_key_function && entry->key != key)
1485     (* table->free_key_function) (entry->key);
1486
1487   if (table->free_value_function && entry->value != value)
1488     (* table->free_value_function) (entry->value);
1489
1490   entry->key = key;
1491   entry->value = value;
1492 }
1493
1494 /**
1495  * Gets the number of hash entries in a hash table.
1496  *
1497  * @param table the hash table.
1498  * @returns the number of entries in the table.
1499  */
1500 int
1501 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1502 {
1503   return table->n_entries;
1504 }
1505
1506 /** @} */
1507
1508 #ifdef DBUS_BUILD_TESTS
1509 #include "dbus-test.h"
1510 #include <stdio.h>
1511
1512 /* If you're wondering why the hash table test takes
1513  * forever to run, it's because we call this function
1514  * in inner loops thus making things quadratic.
1515  */
1516 static int
1517 count_entries (DBusHashTable *table)
1518 {
1519   DBusHashIter iter;
1520   int count;
1521
1522   count = 0;
1523   _dbus_hash_iter_init (table, &iter);
1524   while (_dbus_hash_iter_next (&iter))
1525     ++count;
1526
1527   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1528
1529   return count;
1530 }
1531
1532 /**
1533  * @ingroup DBusHashTableInternals
1534  * Unit test for DBusHashTable
1535  * @returns #TRUE on success.
1536  */
1537 dbus_bool_t
1538 _dbus_hash_test (void)
1539 {
1540   int i;
1541   DBusHashTable *table1;
1542   DBusHashTable *table2;
1543   DBusHashTable *table3;
1544   DBusHashIter iter;
1545 #define N_HASH_KEYS 5000
1546   char **keys;
1547   dbus_bool_t ret = FALSE;
1548
1549   keys = dbus_new (char *, N_HASH_KEYS);
1550   if (keys == NULL)
1551     _dbus_assert_not_reached ("no memory");
1552
1553   for (i = 0; i < N_HASH_KEYS; i++)
1554     {
1555       keys[i] = dbus_malloc (128);
1556
1557       if (keys[i] == NULL)
1558         _dbus_assert_not_reached ("no memory");
1559     }
1560
1561   printf ("Computing test hash keys...\n");
1562   i = 0;
1563   while (i < N_HASH_KEYS)
1564     {
1565       sprintf (keys[i], "Hash key %d", i);
1566       ++i;
1567     }
1568   printf ("... done.\n");
1569
1570   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1571                                  dbus_free, dbus_free);
1572   if (table1 == NULL)
1573     goto out;
1574
1575   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1576                                  NULL, dbus_free);
1577   if (table2 == NULL)
1578     goto out;
1579
1580   table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
1581                                  NULL, dbus_free);
1582   if (table3 == NULL)
1583     goto out;
1584
1585   /* Insert and remove a bunch of stuff, counting the table in between
1586    * to be sure it's not broken and that iteration works
1587    */
1588   i = 0;
1589   while (i < 3000)
1590     {
1591       void *value;
1592       char *key;
1593
1594       key = _dbus_strdup (keys[i]);
1595       if (key == NULL)
1596         goto out;
1597       value = _dbus_strdup ("Value!");
1598       if (value == NULL)
1599         goto out;
1600
1601       if (!_dbus_hash_table_insert_string (table1,
1602                                            key, value))
1603         goto out;
1604
1605       value = _dbus_strdup (keys[i]);
1606       if (value == NULL)
1607         goto out;
1608
1609       if (!_dbus_hash_table_insert_int (table2,
1610                                         i, value))
1611         goto out;
1612
1613       value = _dbus_strdup (keys[i]);
1614       if (value == NULL)
1615         goto out;
1616
1617       if (!_dbus_hash_table_insert_ulong (table3,
1618                                           i, value))
1619         goto out;
1620
1621       _dbus_assert (count_entries (table1) == i + 1);
1622       _dbus_assert (count_entries (table2) == i + 1);
1623       _dbus_assert (count_entries (table3) == i + 1);
1624
1625       value = _dbus_hash_table_lookup_string (table1, keys[i]);
1626       _dbus_assert (value != NULL);
1627       _dbus_assert (strcmp (value, "Value!") == 0);
1628
1629       value = _dbus_hash_table_lookup_int (table2, i);
1630       _dbus_assert (value != NULL);
1631       _dbus_assert (strcmp (value, keys[i]) == 0);
1632
1633       value = _dbus_hash_table_lookup_ulong (table3, i);
1634       _dbus_assert (value != NULL);
1635       _dbus_assert (strcmp (value, keys[i]) == 0);
1636
1637       ++i;
1638     }
1639
1640   --i;
1641   while (i >= 0)
1642     {
1643       _dbus_hash_table_remove_string (table1,
1644                                       keys[i]);
1645
1646       _dbus_hash_table_remove_int (table2, i);
1647
1648       _dbus_hash_table_remove_ulong (table3, i);
1649
1650       _dbus_assert (count_entries (table1) == i);
1651       _dbus_assert (count_entries (table2) == i);
1652       _dbus_assert (count_entries (table3) == i);
1653
1654       --i;
1655     }
1656
1657   _dbus_hash_table_ref (table1);
1658   _dbus_hash_table_ref (table2);
1659   _dbus_hash_table_ref (table3);
1660   _dbus_hash_table_unref (table1);
1661   _dbus_hash_table_unref (table2);
1662   _dbus_hash_table_unref (table3);
1663   _dbus_hash_table_unref (table1);
1664   _dbus_hash_table_unref (table2);
1665   _dbus_hash_table_unref (table3);
1666   table3 = NULL;
1667
1668   /* Insert a bunch of stuff then check
1669    * that iteration works correctly (finds the right
1670    * values, iter_set_value works, etc.)
1671    */
1672   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1673                                  dbus_free, dbus_free);
1674   if (table1 == NULL)
1675     goto out;
1676
1677   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1678                                  NULL, dbus_free);
1679   if (table2 == NULL)
1680     goto out;
1681
1682   i = 0;
1683   while (i < 5000)
1684     {
1685       char *key;
1686       void *value;
1687
1688       key = _dbus_strdup (keys[i]);
1689       if (key == NULL)
1690         goto out;
1691       value = _dbus_strdup ("Value!");
1692       if (value == NULL)
1693         goto out;
1694
1695       if (!_dbus_hash_table_insert_string (table1,
1696                                            key, value))
1697         goto out;
1698
1699       value = _dbus_strdup (keys[i]);
1700       if (value == NULL)
1701         goto out;
1702
1703       if (!_dbus_hash_table_insert_int (table2,
1704                                         i, value))
1705         goto out;
1706
1707       _dbus_assert (count_entries (table1) == i + 1);
1708       _dbus_assert (count_entries (table2) == i + 1);
1709
1710       ++i;
1711     }
1712
1713   _dbus_hash_iter_init (table1, &iter);
1714   while (_dbus_hash_iter_next (&iter))
1715     {
1716       const char *key;
1717       void *value;
1718
1719       key = _dbus_hash_iter_get_string_key (&iter);
1720       value = _dbus_hash_iter_get_value (&iter);
1721
1722       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1723
1724       value = _dbus_strdup ("Different value!");
1725       if (value == NULL)
1726         goto out;
1727
1728       _dbus_hash_iter_set_value (&iter, value);
1729
1730       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1731     }
1732
1733   _dbus_hash_iter_init (table1, &iter);
1734   while (_dbus_hash_iter_next (&iter))
1735     {
1736       _dbus_hash_iter_remove_entry (&iter);
1737       _dbus_assert (count_entries (table1) == i - 1);
1738       --i;
1739     }
1740
1741   _dbus_hash_iter_init (table2, &iter);
1742   while (_dbus_hash_iter_next (&iter))
1743     {
1744       int key;
1745       void *value;
1746
1747       key = _dbus_hash_iter_get_int_key (&iter);
1748       value = _dbus_hash_iter_get_value (&iter);
1749
1750       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1751
1752       value = _dbus_strdup ("Different value!");
1753       if (value == NULL)
1754         goto out;
1755
1756       _dbus_hash_iter_set_value (&iter, value);
1757
1758       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1759     }
1760
1761   i = count_entries (table2);
1762   _dbus_hash_iter_init (table2, &iter);
1763   while (_dbus_hash_iter_next (&iter))
1764     {
1765       _dbus_hash_iter_remove_entry (&iter);
1766       _dbus_assert (count_entries (table2) + 1 == i);
1767       --i;
1768     }
1769
1770   /* add/remove interleaved, to check that we grow/shrink the table
1771    * appropriately
1772    */
1773   i = 0;
1774   while (i < 1000)
1775     {
1776       char *key;
1777       void *value;
1778
1779       key = _dbus_strdup (keys[i]);
1780       if (key == NULL)
1781         goto out;
1782
1783       value = _dbus_strdup ("Value!");
1784       if (value == NULL)
1785         goto out;
1786
1787       if (!_dbus_hash_table_insert_string (table1,
1788                                            key, value))
1789         goto out;
1790
1791       ++i;
1792     }
1793
1794   --i;
1795   while (i >= 0)
1796     {
1797       char *key;
1798       void *value;
1799
1800       key = _dbus_strdup (keys[i]);
1801       if (key == NULL)
1802         goto out;
1803       value = _dbus_strdup ("Value!");
1804       if (value == NULL)
1805         goto out;
1806
1807       if (!_dbus_hash_table_remove_string (table1, keys[i]))
1808         goto out;
1809
1810       if (!_dbus_hash_table_insert_string (table1,
1811                                            key, value))
1812         goto out;
1813
1814       if (!_dbus_hash_table_remove_string (table1, keys[i]))
1815         goto out;
1816
1817       _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);
1818
1819       --i;
1820     }
1821
1822   /* nuke these tables */
1823   _dbus_hash_table_unref (table1);
1824   _dbus_hash_table_unref (table2);
1825
1826
1827   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1828    * be sure that interface works.
1829    */
1830   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1831                                  dbus_free, dbus_free);
1832   if (table1 == NULL)
1833     goto out;
1834
1835   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1836                                  NULL, dbus_free);
1837   if (table2 == NULL)
1838     goto out;
1839
1840   i = 0;
1841   while (i < 3000)
1842     {
1843       void *value;
1844       char *key;
1845
1846       key = _dbus_strdup (keys[i]);
1847       if (key == NULL)
1848         goto out;
1849       value = _dbus_strdup ("Value!");
1850       if (value == NULL)
1851         goto out;
1852
1853       if (!_dbus_hash_iter_lookup (table1,
1854                                    key, TRUE, &iter))
1855         goto out;
1856       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1857       _dbus_hash_iter_set_value (&iter, value);
1858
1859       value = _dbus_strdup (keys[i]);
1860       if (value == NULL)
1861         goto out;
1862
1863       if (!_dbus_hash_iter_lookup (table2,
1864                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1865         goto out;
1866       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1867       _dbus_hash_iter_set_value (&iter, value);
1868
1869       _dbus_assert (count_entries (table1) == i + 1);
1870       _dbus_assert (count_entries (table2) == i + 1);
1871
1872       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1873         goto out;
1874
1875       value = _dbus_hash_iter_get_value (&iter);
1876       _dbus_assert (value != NULL);
1877       _dbus_assert (strcmp (value, "Value!") == 0);
1878
1879       /* Iterate just to be sure it works, though
1880        * it's a stupid thing to do
1881        */
1882       while (_dbus_hash_iter_next (&iter))
1883         ;
1884
1885       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1886         goto out;
1887
1888       value = _dbus_hash_iter_get_value (&iter);
1889       _dbus_assert (value != NULL);
1890       _dbus_assert (strcmp (value, keys[i]) == 0);
1891
1892       /* Iterate just to be sure it works, though
1893        * it's a stupid thing to do
1894        */
1895       while (_dbus_hash_iter_next (&iter))
1896         ;
1897
1898       ++i;
1899     }
1900
1901   --i;
1902   while (i >= 0)
1903     {
1904       if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
1905         _dbus_assert_not_reached ("hash entry should have existed");
1906       _dbus_hash_iter_remove_entry (&iter);
1907
1908       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1909         _dbus_assert_not_reached ("hash entry should have existed");
1910       _dbus_hash_iter_remove_entry (&iter);
1911
1912       _dbus_assert (count_entries (table1) == i);
1913       _dbus_assert (count_entries (table2) == i);
1914
1915       --i;
1916     }
1917
1918   _dbus_hash_table_unref (table1);
1919   _dbus_hash_table_unref (table2);
1920
1921   ret = TRUE;
1922
1923  out:
1924   for (i = 0; i < N_HASH_KEYS; i++)
1925     dbus_free (keys[i]);
1926
1927   dbus_free (keys);
1928
1929   return ret;
1930 }
1931
1932 #endif /* DBUS_BUILD_TESTS */