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