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