dbus/dbus-hash.c

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