dbus/dbus-hash.c

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