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