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