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