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