dbus/dbus-hash.c

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