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