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
  80 /**
  81  * @defgroup DBusHashTable Hash table
  82  * @ingroup  DBusInternals
  83  * @brief DBusHashTable data structure
  84  *
  85  * Types and functions related to DBusHashTable.
  86  */
  87
  88 /**
  89  * @defgroup DBusHashTableInternals Hash table implementation details
  90  * @ingroup  DBusInternals
  91  * @brief DBusHashTable implementation details
  92  *
  93  * The guts of DBusHashTable.
  94  *
  95  * @{
  96  */
  97
  98 /**
  99  * When there are this many entries per bucket, on average, rebuild
 100  * the hash table to make it larger.
 101  */
 102 #define REBUILD_MULTIPLIER  3
 103
 104 /**
 105  * Takes a preliminary integer hash value and produces an index into a
 106  * hash tables bucket list.  The idea is to make it so that
 107  * preliminary values that are arbitrarily similar will end up in
 108  * different buckets.  The hash function was taken from a
 109  * random-number generator. (This is used to hash integers.)
 110  */
 111 #define RANDOM_INDEX(table, i) \
 112     (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
 113
 114 /**
 115  * Initial number of buckets in hash table (hash table statically
 116  * allocates its buckets for this size and below).
 117  */
 118 #define DBUS_SMALL_HASH_TABLE 4
 119
 120 /**
 121  * Typedef for DBusHashEntry
 122  */
 123 typedef struct DBusHashEntry DBusHashEntry;
 124
 125 /**
 126  * @brief Internal representation of a hash entry.
 127  *
 128  * A single entry (key-value pair) in the hash table.
 129  * Internal to hash table implementation.
 130  */
 131 struct DBusHashEntry
 132 {
 133   DBusHashEntry *next;    /**< Pointer to next entry in this
 134                            * hash bucket, or #NULL for end of
 135                            * chain.
 136                            */
 137   void *key;              /**< Hash key */
 138   void *value;            /**< Hash value */
 139 };
 140
 141 /**
 142  * Function used to find and optionally create a hash entry.
 143  */
 144 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable   *table,
 145                                                   void            *key,
 146                                                   dbus_bool_t      create_if_not_found,
 147                                                   DBusHashEntry ***bucket);
 148
 149 /**
 150  * @brief Internals of DBusHashTable.
 151  *
 152  * Hash table internals. Hash tables are opaque objects, they must be
 153  * used via accessor functions.
 154  */
 155 struct DBusHashTable {
 156   int refcount;                       /**< Reference count */
 157
 158   DBusHashEntry **buckets;            /**< Pointer to bucket array.  Each
 159                                        * element points to first entry in
 160                                        * bucket's hash chain, or #NULL.
 161                                        */
 162   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
 163                                        /**< Bucket array used for small tables
 164                                         * (to avoid mallocs and frees).
 165                                         */
 166   int n_buckets;                       /**< Total number of buckets allocated
 167                                         * at **buckets.
 168                                         */
 169   int n_entries;                       /**< Total number of entries present
 170                                         * in table.
 171                                         */
 172   int rebuild_size;                    /**< Enlarge table when numEntries gets
 173                                         * to be this large.
 174                                         */
 175   int down_shift;                      /**< Shift count used in hashing
 176                                         * function.  Designed to use high-
 177                                         * order bits of randomized keys.
 178                                         */
 179   int mask;                            /**< Mask value used in hashing
 180                                         * function.
 181                                         */
 182   DBusHashType key_type;               /**< Type of keys used in this table */
 183
 184
 185   DBusFindEntryFunction find_function; /**< Function for finding entries */
 186
 187   DBusFreeFunction free_key_function;   /**< Function to free keys */
 188   DBusFreeFunction free_value_function; /**< Function to free values */
 189 };
 190
 191 /**
 192  * @brief Internals of DBusHashIter.
 193  */
 194 typedef struct
 195 {
 196   DBusHashTable *table;     /**< Pointer to table containing entry. */
 197   DBusHashEntry **bucket;   /**< Pointer to bucket that points to
 198                              * first entry in this entry's chain:
 199                              * used for deleting the entry.
 200                              */
 201   DBusHashEntry *entry;      /**< Current hash entry */
 202   DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
 203   int next_bucket;           /**< index of next bucket */
 204   int n_entries_on_init;     /**< used to detect table resize since initialization */
 205 } DBusRealHashIter;
 206
 207 static DBusHashEntry* find_int_function    (DBusHashTable   *table,
 208                                             void            *key,
 209                                             dbus_bool_t      create_if_not_found,
 210                                             DBusHashEntry ***bucket);
 211 static DBusHashEntry* find_string_function (DBusHashTable   *table,
 212                                             void            *key,
 213                                             dbus_bool_t      create_if_not_found,
 214                                             DBusHashEntry ***bucket);
 215 static unsigned int   string_hash          (const char      *str);
 216 static void           rebuild_table        (DBusHashTable   *table);
 217 static DBusHashEntry* alloc_entry          (DBusHashTable   *table);
 218 static void           remove_entry         (DBusHashTable   *table,
 219                                             DBusHashEntry  **bucket,
 220                                             DBusHashEntry   *entry);
 221 static void           free_entry           (DBusHashTable   *table,
 222                                             DBusHashEntry   *entry);
 223
 224 /** @} */
 225
 226 /**
 227  * @addtogroup DBusHashTable
 228  * @{
 229  */
 230
 231 /**
 232  * @typedef DBusHashIter
 233  *
 234  * Public opaque hash table iterator object.
 235  */
 236
 237 /**
 238  * @typedef DBusHashTable
 239  *
 240  * Public opaque hash table object.
 241  */
 242
 243 /**
 244  * @typedef DBusHashType
 245  *
 246  * Indicates the type of a key in the hash table.
 247  */
 248
 249 /**
 250  * Constructs a new hash table. Should be freed with
 251  * _dbus_hash_table_unref(). If memory cannot be
 252  * allocated for the hash table, returns #NULL.
 253  *
 254  * @param type the type of hash key to use.
 255  * @param key_free_function function to free hash keys.
 256  * @param value_free_function function to free hash values.
 257  * @returns a new DBusHashTable or #NULL if no memory.
 258  */
 259 DBusHashTable*
 260 _dbus_hash_table_new (DBusHashType     type,
 261                       DBusFreeFunction key_free_function,
 262                       DBusFreeFunction value_free_function)
 263 {
 264   DBusHashTable *table;
 265
 266   table = dbus_new0 (DBusHashTable, 1);
 267   if (table == NULL)
 268     return NULL;
 269
 270   table->refcount = 1;
 271
 272   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
 273
 274   table->buckets = table->static_buckets;
 275   table->n_buckets = DBUS_SMALL_HASH_TABLE;
 276   table->n_entries = 0;
 277   table->rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
 278   table->down_shift = 28;
 279   table->mask = 3;
 280   table->key_type = type;
 281
 282   switch (table->key_type)
 283     {
 284     case DBUS_HASH_INT:
 285       table->find_function = find_int_function;
 286       break;
 287     case DBUS_HASH_STRING:
 288       table->find_function = find_string_function;
 289       break;
 290     default:
 291       _dbus_assert_not_reached ("Unknown hash table type");
 292       break;
 293     }
 294
 295   table->free_key_function = key_free_function;
 296   table->free_value_function = value_free_function;
 297
 298   return table;
 299 }
 300
 301
 302 /**
 303  * Increments the reference count for a hash table.
 304  *
 305  * @param table the hash table to add a reference to.
 306  */
 307 void
 308 _dbus_hash_table_ref (DBusHashTable *table)
 309 {
 310   table->refcount += 1;
 311 }
 312
 313 /**
 314  * Decrements the reference count for a hash table,
 315  * freeing the hash table if the count reaches zero.
 316  *
 317  * @param table the hash table to remove a reference from.
 318  */
 319 void
 320 _dbus_hash_table_unref (DBusHashTable *table)
 321 {
 322   table->refcount -= 1;
 323
 324   if (table->refcount == 0)
 325     {
 326       DBusHashEntry *entry;
 327       DBusHashEntry *next;
 328       int i;
 329
 330       /* Free the entries in the table. */
 331
 332       for (i = 0; i < table->n_buckets; i++)
 333         {
 334           entry = table->buckets[i];
 335           while (entry != NULL)
 336             {
 337               next = entry->next;
 338
 339               free_entry (table, entry);
 340
 341               entry = next;
 342             }
 343         }
 344
 345       /* Free the bucket array, if it was dynamically allocated. */
 346       if (table->buckets != table->static_buckets)
 347         dbus_free (table->buckets);
 348
 349       dbus_free (table);
 350     }
 351 }
 352
 353 static DBusHashEntry*
 354 alloc_entry (DBusHashTable *table)
 355 {
 356   DBusHashEntry *entry;
 357
 358   entry = dbus_new0 (DBusHashEntry, 1);
 359
 360   return entry;
 361 }
 362
 363 static void
 364 free_entry (DBusHashTable  *table,
 365             DBusHashEntry  *entry)
 366 {
 367   if (table->free_key_function)
 368     (* table->free_key_function) (entry->key);
 369   if (table->free_value_function)
 370     (* table->free_value_function) (entry->value);
 371
 372   dbus_free (entry);
 373 }
 374
 375 static void
 376 remove_entry (DBusHashTable  *table,
 377               DBusHashEntry **bucket,
 378               DBusHashEntry  *entry)
 379 {
 380   _dbus_assert (table != NULL);
 381   _dbus_assert (bucket != NULL);
 382   _dbus_assert (*bucket != NULL);
 383   _dbus_assert (entry != NULL);
 384
 385   if (*bucket == entry)
 386     *bucket = entry->next;
 387   else
 388     {
 389       DBusHashEntry *prev;
 390       prev = *bucket;
 391
 392       while (prev->next != entry)
 393         prev = prev->next;
 394
 395       _dbus_assert (prev != NULL);
 396
 397       prev->next = entry->next;
 398     }
 399
 400   table->n_entries -= 1;
 401   free_entry (table, entry);
 402 }
 403
 404 /**
 405  * Initializes a hash table iterator. To iterate over all entries in a
 406  * hash table, use the following code (the printf assumes a hash
 407  * from strings to strings obviously):
 408  *
 409  * @code
 410  * DBusHashIter iter;
 411  *
 412  * _dbus_hash_iter_init (table, &iter);
 413  * while (_dbus_hash_iter_next (&iter))
 414  *   {
 415  *      printf ("The first key is %s and value is %s\n",
 416  *              _dbus_hash_iter_get_string_key (&iter),
 417  *              _dbus_hash_iter_get_value (&iter));
 418  *   }
 419  *
 420  *
 421  * @endcode
 422  *
 423  * The iterator is initialized pointing "one before" the first hash
 424  * entry. The first call to _dbus_hash_iter_next() moves it onto
 425  * the first valid entry or returns #FALSE if the hash table is
 426  * empty. Subsequent calls move to the next valid entry or return
 427  * #FALSE if there are no more entries.
 428  *
 429  * Note that it is guaranteed to be safe to remove a hash entry during
 430  * iteration, but it is not safe to add a hash entry.
 431  *
 432  * @param table the hash table to iterate over.
 433  * @param iter the iterator to initialize.
 434  */
 435 void
 436 _dbus_hash_iter_init (DBusHashTable *table,
 437                       DBusHashIter  *iter)
 438 {
 439   DBusRealHashIter *real;
 440
 441   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 442
 443   real = (DBusRealHashIter*) iter;
 444
 445   real->table = table;
 446   real->bucket = NULL;
 447   real->entry = NULL;
 448   real->next_entry = NULL;
 449   real->next_bucket = 0;
 450   real->n_entries_on_init = table->n_entries;
 451 }
 452
 453 /**
 454  * Move the hash iterator forward one step, to the next hash entry.
 455  * The documentation for _dbus_hash_iter_init() explains in more
 456  * detail.
 457  *
 458  * @param iter the iterator to move forward.
 459  * @returns #FALSE if there are no more entries to move to.
 460  */
 461 dbus_bool_t
 462 _dbus_hash_iter_next (DBusHashIter  *iter)
 463 {
 464   DBusRealHashIter *real;
 465
 466   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 467
 468   real = (DBusRealHashIter*) iter;
 469
 470   /* if this assertion failed someone probably added hash entries
 471    * during iteration, which is bad.
 472    */
 473   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
 474
 475   /* Remember that real->entry may have been deleted */
 476
 477   while (real->next_entry == NULL)
 478     {
 479       if (real->next_bucket >= real->table->n_buckets)
 480         {
 481           /* invalidate iter and return false */
 482           real->entry = NULL;
 483           real->table = NULL;
 484           real->bucket = NULL;
 485           return FALSE;
 486         }
 487
 488       real->bucket = &(real->table->buckets[real->next_bucket]);
 489       real->next_entry = *(real->bucket);
 490       real->next_bucket += 1;
 491     }
 492
 493   _dbus_assert (real->next_entry != NULL);
 494   _dbus_assert (real->bucket != NULL);
 495
 496   real->entry = real->next_entry;
 497   real->next_entry = real->entry->next;
 498
 499   return TRUE;
 500 }
 501
 502 /**
 503  * Removes the current entry from the hash table.
 504  * If a key_free_function or value_free_function
 505  * was provided to _dbus_hash_table_new(),
 506  * frees the key and/or value for this entry.
 507  *
 508  * @param iter the hash table iterator.
 509  */
 510 void
 511 _dbus_hash_iter_remove_entry (DBusHashIter *iter)
 512 {
 513   DBusRealHashIter *real;
 514
 515   real = (DBusRealHashIter*) iter;
 516
 517   _dbus_assert (real->table != NULL);
 518   _dbus_assert (real->entry != NULL);
 519   _dbus_assert (real->bucket != NULL);
 520
 521   remove_entry (real->table, real->bucket, real->entry);
 522
 523   real->entry = NULL; /* make it crash if you try to use this entry */
 524 }
 525
 526 /**
 527  * Gets the value of the current entry.
 528  *
 529  * @param iter the hash table iterator.
 530  */
 531 void*
 532 _dbus_hash_iter_get_value (DBusHashIter *iter)
 533 {
 534   DBusRealHashIter *real;
 535
 536   real = (DBusRealHashIter*) iter;
 537
 538   _dbus_assert (real->table != NULL);
 539   _dbus_assert (real->entry != NULL);
 540
 541   return real->entry->value;
 542 }
 543
 544 /**
 545  * Sets the value of the current entry.
 546  * If the hash table has a value_free_function
 547  * it will be used to free the previous value.
 548  * The hash table will own the passed-in value
 549  * (it will not be copied).
 550  *
 551  * @param iter the hash table iterator.
 552  * @param value the new value.
 553  */
 554 void
 555 _dbus_hash_iter_set_value (DBusHashIter *iter,
 556                            void         *value)
 557 {
 558   DBusRealHashIter *real;
 559
 560   real = (DBusRealHashIter*) iter;
 561
 562   _dbus_assert (real->table != NULL);
 563   _dbus_assert (real->entry != NULL);
 564
 565   if (real->table->free_value_function && value != real->entry->value)
 566     (* real->table->free_value_function) (real->entry->value);
 567
 568   real->entry->value = value;
 569 }
 570
 571 /**
 572  * Gets the key for the current entry.
 573  * Only works for hash tables of type #DBUS_HASH_INT.
 574  *
 575  * @param iter the hash table iterator.
 576  */
 577 int
 578 _dbus_hash_iter_get_int_key (DBusHashIter *iter)
 579 {
 580   DBusRealHashIter *real;
 581
 582   real = (DBusRealHashIter*) iter;
 583
 584   _dbus_assert (real->table != NULL);
 585   _dbus_assert (real->entry != NULL);
 586
 587   return _DBUS_POINTER_TO_INT (real->entry->key);
 588 }
 589
 590 /**
 591  * Gets the key for the current entry.
 592  * Only works for hash tables of type #DBUS_HASH_STRING
 593  * @param iter the hash table iterator.
 594  */
 595 const char*
 596 _dbus_hash_iter_get_string_key (DBusHashIter *iter)
 597 {
 598   DBusRealHashIter *real;
 599
 600   real = (DBusRealHashIter*) iter;
 601
 602   _dbus_assert (real->table != NULL);
 603   _dbus_assert (real->entry != NULL);
 604
 605   return real->entry->key;
 606 }
 607
 608 /**
 609  * A low-level but efficient interface for manipulating the hash
 610  * table.  It's efficient because you can get, set, and optionally
 611  * create the hash entry while only running the hash function one
 612  * time.
 613  *
 614  * Note that while calling _dbus_hash_iter_next() on the iterator
 615  * filled in by this function may work, it's completely
 616  * undefined which entries are after this iter and which
 617  * are before it. So it would be silly to iterate using this
 618  * iterator.
 619  *
 620  * If the hash entry is created, its value will be initialized
 621  * to all bits zero.
 622  *
 623  * #FALSE may be returned due to memory allocation failure, or
 624  * because create_if_not_found was #FALSE and the entry
 625  * did not exist.
 626  *
 627  * For a hash table of type #DBUS_HASH_INT, cast the int
 628  * key to the key parameter using #_DBUS_INT_TO_POINTER().
 629  *
 630  * @param table the hash table.
 631  * @param key the hash key.
 632  * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
 633  * @param iter the iterator to initialize.
 634  * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
 635  */
 636 dbus_bool_t
 637 _dbus_hash_iter_lookup (DBusHashTable *table,
 638                         void          *key,
 639                         dbus_bool_t    create_if_not_found,
 640                         DBusHashIter  *iter)
 641 {
 642   DBusRealHashIter *real;
 643   DBusHashEntry *entry;
 644   DBusHashEntry **bucket;
 645
 646   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
 647
 648   real = (DBusRealHashIter*) iter;
 649
 650   entry = (* table->find_function) (table, key, create_if_not_found, &bucket);
 651
 652   if (entry == NULL)
 653     return FALSE;
 654
 655   real->table = table;
 656   real->bucket = bucket;
 657   real->entry = entry;
 658   real->next_entry = entry->next;
 659   real->next_bucket = (bucket - table->buckets) + 1;
 660   real->n_entries_on_init = table->n_entries;
 661
 662   _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
 663
 664   return TRUE;
 665 }
 666
 667 static DBusHashEntry*
 668 add_entry (DBusHashTable   *table,
 669            unsigned int     idx,
 670            void            *key,
 671            DBusHashEntry ***bucket)
 672 {
 673   DBusHashEntry  *entry;
 674   DBusHashEntry **b;
 675
 676   entry = alloc_entry (table);
 677   if (entry == NULL)
 678     {
 679       if (bucket)
 680         *bucket = NULL;
 681       return NULL;
 682     }
 683
 684   entry->key = key;
 685
 686   b = &(table->buckets[idx]);
 687   entry->next = *b;
 688   *b = entry;
 689
 690   if (bucket)
 691     *bucket = b;
 692
 693   table->n_entries += 1;
 694
 695   if (table->n_entries >= table->rebuild_size)
 696     rebuild_table (table);
 697
 698   return entry;
 699 }
 700
 701 static unsigned int
 702 string_hash (const char *str)
 703 {
 704   register unsigned int result;
 705   register int c;
 706
 707   /*
 708    * I tried a zillion different hash functions and asked many other
 709    * people for advice.  Many people had their own favorite functions,
 710    * all different, but no-one had much idea why they were good ones.
 711    * I chose the one below (multiply by 9 and add new character)
 712    * because of the following reasons:
 713    *
 714    * 1. Multiplying by 10 is perfect for keys that are decimal strings,
 715    *    and multiplying by 9 is just about as good.
 716    * 2. Times-9 is (shift-left-3) plus (old).  This means that each
 717    *    character's bits hang around in the low-order bits of the
 718    *    hash value for ever, plus they spread fairly rapidly up to
 719    *    the high-order bits to fill out the hash value.  This seems
 720    *    works well both for decimal and non-decimal strings.
 721    */
 722
 723   result = 0;
 724   while (TRUE)
 725     {
 726       c = *str;
 727       str++;
 728       if (c == 0)
 729         break;
 730
 731       result += (result << 3) + c;
 732     }
 733
 734   return result;
 735 }
 736
 737 static DBusHashEntry*
 738 find_string_function (DBusHashTable   *table,
 739                       void            *key,
 740                       dbus_bool_t      create_if_not_found,
 741                       DBusHashEntry ***bucket)
 742 {
 743   DBusHashEntry *entry;
 744   unsigned int idx;
 745
 746   if (bucket)
 747     *bucket = NULL;
 748
 749   idx = string_hash (key) & table->mask;
 750
 751   /* Search all of the entries in this bucket. */
 752   entry = table->buckets[idx];
 753   while (entry != NULL)
 754     {
 755       if (strcmp (key, entry->key) == 0)
 756         {
 757           if (bucket)
 758             *bucket = &(table->buckets[idx]);
 759           return entry;
 760         }
 761
 762       entry = entry->next;
 763     }
 764
 765   if (create_if_not_found)
 766     entry = add_entry (table, idx, key, bucket);
 767
 768   return entry;
 769 }
 770
 771 static DBusHashEntry*
 772 find_int_function (DBusHashTable   *table,
 773                    void            *key,
 774                    dbus_bool_t      create_if_not_found,
 775                    DBusHashEntry ***bucket)
 776 {
 777   DBusHashEntry *entry;
 778   unsigned int idx;
 779
 780   if (bucket)
 781     *bucket = NULL;
 782
 783   idx = RANDOM_INDEX (table, key) & table->mask;
 784
 785   /* Search all of the entries in this bucket. */
 786   entry = table->buckets[idx];
 787   while (entry != NULL)
 788     {
 789       if (key == entry->key)
 790         {
 791           if (bucket)
 792             *bucket = &(table->buckets[idx]);
 793           return entry;
 794         }
 795
 796       entry = entry->next;
 797     }
 798
 799   /* Entry not found.  Add a new one to the bucket. */
 800   if (create_if_not_found)
 801     entry = add_entry (table, idx, key, bucket);
 802
 803   return entry;
 804 }
 805
 806 static void
 807 rebuild_table (DBusHashTable *table)
 808 {
 809   int old_size;
 810   DBusHashEntry **old_buckets;
 811   DBusHashEntry **old_chain;
 812   DBusHashEntry *entry;
 813
 814   /*
 815    * Allocate and initialize the new bucket array, and set up
 816    * hashing constants for new array size.
 817    */
 818
 819   old_size = table->n_buckets;
 820   old_buckets = table->buckets;
 821
 822   table->n_buckets *= 4;
 823   table->buckets = dbus_new0 (DBusHashEntry*, table->n_buckets);
 824   if (table->buckets == NULL)
 825     {
 826       /* out of memory, yay - just don't reallocate, the table will
 827        * still work, albeit more slowly.
 828        */
 829       table->n_buckets /= 4;
 830       table->buckets = old_buckets;
 831       return;
 832     }
 833
 834   table->rebuild_size *= 4;
 835   table->down_shift -= 2;
 836   table->mask = (table->mask << 2) + 3;
 837
 838   /*
 839    * Rehash all of the existing entries into the new bucket array.
 840    */
 841
 842   for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
 843     {
 844       for (entry = *old_chain; entry != NULL; entry = *old_chain)
 845         {
 846           unsigned int idx;
 847           DBusHashEntry **bucket;
 848
 849           *old_chain = entry->next;
 850           switch (table->key_type)
 851             {
 852             case DBUS_HASH_STRING:
 853               idx = string_hash (entry->key) & table->mask;
 854               break;
 855             case DBUS_HASH_INT:
 856               idx = RANDOM_INDEX (table, entry->key);
 857               break;
 858             default:
 859               idx = 0;
 860               _dbus_assert_not_reached ("Unknown hash table type");
 861               break;
 862             }
 863
 864           bucket = &(table->buckets[idx]);
 865           entry->next = *bucket;
 866           *bucket = entry;
 867         }
 868     }
 869
 870   /* Free the old bucket array, if it was dynamically allocated. */
 871
 872   if (old_buckets != table->static_buckets)
 873     dbus_free (old_buckets);
 874 }
 875
 876 /**
 877  * Looks up the value for a given string in a hash table
 878  * of type #DBUS_HASH_STRING. Returns %NULL if the value
 879  * is not present. (A not-present entry is indistinguishable
 880  * from an entry with a value of %NULL.)
 881  * @param table the hash table.
 882  * @param key the string to look up.
 883  * @returns the value of the hash entry.
 884  */
 885 void*
 886 _dbus_hash_table_lookup_string (DBusHashTable *table,
 887                                 const char    *key)
 888 {
 889   DBusHashEntry *entry;
 890
 891   _dbus_assert (table->key_type == DBUS_HASH_STRING);
 892
 893   entry = (* table->find_function) (table, (char*) key, FALSE, NULL);
 894
 895   if (entry)
 896     return entry->value;
 897   else
 898     return NULL;
 899 }
 900
 901 /**
 902  * Looks up the value for a given integer in a hash table
 903  * of type #DBUS_HASH_INT. Returns %NULL if the value
 904  * is not present. (A not-present entry is indistinguishable
 905  * from an entry with a value of %NULL.)
 906  * @param table the hash table.
 907  * @param key the integer to look up.
 908  * @returns the value of the hash entry.
 909  */
 910 void*
 911 _dbus_hash_table_lookup_int (DBusHashTable *table,
 912                              int            key)
 913 {
 914   DBusHashEntry *entry;
 915
 916   _dbus_assert (table->key_type == DBUS_HASH_INT);
 917
 918   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL);
 919
 920   if (entry)
 921     return entry->value;
 922   else
 923     return NULL;
 924 }
 925
 926 /**
 927  * Removes the hash entry for the given key. If no hash entry
 928  * for the key exists, does nothing.
 929  *
 930  * @param table the hash table.
 931  * @param key the hash key.
 932  */
 933 void
 934 _dbus_hash_table_remove_string (DBusHashTable *table,
 935                                 const char    *key)
 936 {
 937   DBusHashEntry *entry;
 938   DBusHashEntry **bucket;
 939
 940   _dbus_assert (table->key_type == DBUS_HASH_STRING);
 941
 942   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
 943
 944   if (entry)
 945     remove_entry (table, bucket, entry);
 946 }
 947
 948 /**
 949  * Removes the hash entry for the given key. If no hash entry
 950  * for the key exists, does nothing.
 951  *
 952  * @param table the hash table.
 953  * @param key the hash key.
 954  */
 955 void
 956 _dbus_hash_table_remove_int (DBusHashTable *table,
 957                              int            key)
 958 {
 959   DBusHashEntry *entry;
 960   DBusHashEntry **bucket;
 961
 962   _dbus_assert (table->key_type == DBUS_HASH_INT);
 963
 964   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
 965
 966   if (entry)
 967     remove_entry (table, bucket, entry);
 968 }
 969
 970 /**
 971  * Creates a hash entry with the given key and value.
 972  * The key and value are not copied; they are stored
 973  * in the hash table by reference. If an entry with the
 974  * given key already exists, the previous key and value
 975  * are overwritten (and freed if the hash table has
 976  * a key_free_function and/or value_free_function).
 977  *
 978  * Returns #FALSE if memory for the new hash entry
 979  * can't be allocated.
 980  *
 981  * @param table the hash table.
 982  * @param key the hash entry key.
 983  * @param value the hash entry value.
 984  */
 985 dbus_bool_t
 986 _dbus_hash_table_insert_string (DBusHashTable *table,
 987                                 char          *key,
 988                                 void          *value)
 989 {
 990   DBusHashEntry *entry;
 991
 992   _dbus_assert (table->key_type == DBUS_HASH_STRING);
 993
 994   entry = (* table->find_function) (table, key, TRUE, NULL);
 995
 996   if (entry == NULL)
 997     return FALSE; /* no memory */
 998
 999   if (table->free_key_function && entry->key != key)
1000     (* table->free_key_function) (entry->key);
1001
1002   if (table->free_value_function && entry->value != value)
1003     (* table->free_value_function) (entry->value);
1004
1005   entry->key = key;
1006   entry->value = value;
1007
1008   return TRUE;
1009 }
1010
1011 /**
1012  * Creates a hash entry with the given key and value.
1013  * The key and value are not copied; they are stored
1014  * in the hash table by reference. If an entry with the
1015  * given key already exists, the previous key and value
1016  * are overwritten (and freed if the hash table has
1017  * a key_free_function and/or value_free_function).
1018  *
1019  * Returns #FALSE if memory for the new hash entry
1020  * can't be allocated.
1021  *
1022  * @param table the hash table.
1023  * @param key the hash entry key.
1024  * @param value the hash entry value.
1025  */
1026 dbus_bool_t
1027 _dbus_hash_table_insert_int (DBusHashTable *table,
1028                              int            key,
1029                              void          *value)
1030 {
1031   DBusHashEntry *entry;
1032
1033   _dbus_assert (table->key_type == DBUS_HASH_INT);
1034
1035   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL);
1036
1037   if (entry == NULL)
1038     return FALSE; /* no memory */
1039
1040   if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1041     (* table->free_key_function) (entry->key);
1042
1043   if (table->free_value_function && entry->value != value)
1044     (* table->free_value_function) (entry->value);
1045
1046   entry->key = _DBUS_INT_TO_POINTER (key);
1047   entry->value = value;
1048
1049   return TRUE;
1050 }
1051
1052 /**
1053  * Gets the number of hash entries in a hash table.
1054  *
1055  * @param table the hash table.
1056  * @returns the number of entries in the table.
1057  */
1058 int
1059 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1060 {
1061   return table->n_entries;
1062 }
1063
1064 /** @} */
1065
1066 #ifdef DBUS_BUILD_TESTS
1067 #include "dbus-test.h"
1068 #include <stdio.h>
1069
1070 static int
1071 count_entries (DBusHashTable *table)
1072 {
1073   DBusHashIter iter;
1074   int count;
1075
1076   count = 0;
1077   _dbus_hash_iter_init (table, &iter);
1078   while (_dbus_hash_iter_next (&iter))
1079     ++count;
1080
1081   _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1082
1083   return count;
1084 }
1085
1086 /**
1087  * @ingroup DBusHashTableInternals
1088  * Unit test for DBusHashTable
1089  * @returns #TRUE on success.
1090  */
1091 dbus_bool_t
1092 _dbus_hash_test (void)
1093 {
1094   int i;
1095   DBusHashTable *table1;
1096   DBusHashTable *table2;
1097   DBusHashIter iter;
1098
1099   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1100                                  dbus_free, dbus_free);
1101   if (table1 == NULL)
1102     return FALSE;
1103
1104   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1105                                  NULL, dbus_free);
1106   if (table2 == NULL)
1107     return FALSE;
1108
1109   /* Insert and remove a bunch of stuff, counting the table in between
1110    * to be sure it's not broken and that iteration works
1111    */
1112   i = 0;
1113   while (i < 3000)
1114     {
1115       char buf[256];
1116       sprintf (buf, "Hash key %d", i);
1117       void *value;
1118       char *key;
1119
1120       key = _dbus_strdup (buf);
1121       if (key == NULL)
1122         return FALSE;
1123       value = _dbus_strdup ("Value!");
1124       if (value == NULL)
1125         return FALSE;
1126
1127       if (!_dbus_hash_table_insert_string (table1,
1128                                            key, value))
1129         return FALSE;
1130
1131       value = _dbus_strdup (buf);
1132       if (value == NULL)
1133         return FALSE;
1134
1135       if (!_dbus_hash_table_insert_int (table2,
1136                                         i, value))
1137         return FALSE;
1138
1139       _dbus_assert (count_entries (table1) == i + 1);
1140       _dbus_assert (count_entries (table2) == i + 1);
1141
1142       value = _dbus_hash_table_lookup_string (table1, buf);
1143       _dbus_assert (value != NULL);
1144       _dbus_assert (strcmp (value, "Value!") == 0);
1145
1146       value = _dbus_hash_table_lookup_int (table2, i);
1147       _dbus_assert (value != NULL);
1148       _dbus_assert (strcmp (value, buf) == 0);
1149
1150       ++i;
1151     }
1152
1153   --i;
1154   while (i >= 0)
1155     {
1156       char buf[256];
1157       sprintf (buf, "Hash key %d", i);
1158
1159       _dbus_hash_table_remove_string (table1,
1160                                       buf);
1161
1162       _dbus_hash_table_remove_int (table2, i);
1163
1164       _dbus_assert (count_entries (table1) == i);
1165       _dbus_assert (count_entries (table2) == i);
1166
1167       --i;
1168     }
1169
1170   _dbus_hash_table_ref (table1);
1171   _dbus_hash_table_ref (table2);
1172   _dbus_hash_table_unref (table1);
1173   _dbus_hash_table_unref (table2);
1174   _dbus_hash_table_unref (table1);
1175   _dbus_hash_table_unref (table2);
1176
1177
1178   /* Insert a bunch of stuff then check
1179    * that iteration works correctly (finds the right
1180    * values, iter_set_value works, etc.)
1181    */
1182   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1183                                  dbus_free, dbus_free);
1184   if (table1 == NULL)
1185     return FALSE;
1186
1187   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1188                                  NULL, dbus_free);
1189   if (table2 == NULL)
1190     return FALSE;
1191
1192   i = 0;
1193   while (i < 5000)
1194     {
1195       char buf[256];
1196       sprintf (buf, "Hash key %d", i);
1197       char *key;
1198       void *value;
1199
1200       key = _dbus_strdup (buf);
1201       if (key == NULL)
1202         return FALSE;
1203       value = _dbus_strdup ("Value!");
1204       if (value == NULL)
1205         return FALSE;
1206
1207       if (!_dbus_hash_table_insert_string (table1,
1208                                            key, value))
1209         return FALSE;
1210
1211       value = _dbus_strdup (buf);
1212       if (value == NULL)
1213         return FALSE;
1214
1215       if (!_dbus_hash_table_insert_int (table2,
1216                                         i, value))
1217         return FALSE;
1218
1219       _dbus_assert (count_entries (table1) == i + 1);
1220       _dbus_assert (count_entries (table2) == i + 1);
1221
1222       ++i;
1223     }
1224
1225   _dbus_hash_iter_init (table1, &iter);
1226   while (_dbus_hash_iter_next (&iter))
1227     {
1228       const char *key;
1229       void *value;
1230
1231       key = _dbus_hash_iter_get_string_key (&iter);
1232       value = _dbus_hash_iter_get_value (&iter);
1233
1234       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1235
1236       value = _dbus_strdup ("Different value!");
1237       if (value == NULL)
1238         return FALSE;
1239
1240       _dbus_hash_iter_set_value (&iter, value);
1241
1242       _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
1243     }
1244
1245   _dbus_hash_iter_init (table1, &iter);
1246   while (_dbus_hash_iter_next (&iter))
1247     {
1248       _dbus_hash_iter_remove_entry (&iter);
1249       _dbus_assert (count_entries (table1) == i - 1);
1250       --i;
1251     }
1252
1253   _dbus_hash_iter_init (table2, &iter);
1254   while (_dbus_hash_iter_next (&iter))
1255     {
1256       int key;
1257       void *value;
1258
1259       key = _dbus_hash_iter_get_int_key (&iter);
1260       value = _dbus_hash_iter_get_value (&iter);
1261
1262       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1263
1264       value = _dbus_strdup ("Different value!");
1265       if (value == NULL)
1266         return FALSE;
1267
1268       _dbus_hash_iter_set_value (&iter, value);
1269
1270       _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
1271     }
1272
1273   i = count_entries (table2);
1274   _dbus_hash_iter_init (table2, &iter);
1275   while (_dbus_hash_iter_next (&iter))
1276     {
1277       _dbus_hash_iter_remove_entry (&iter);
1278       _dbus_assert (count_entries (table2) + 1 == i);
1279       --i;
1280     }
1281
1282   _dbus_hash_table_unref (table1);
1283   _dbus_hash_table_unref (table2);
1284
1285
1286   /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
1287    * be sure that interface works.
1288    */
1289   table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
1290                                  dbus_free, dbus_free);
1291   if (table1 == NULL)
1292     return FALSE;
1293
1294   table2 = _dbus_hash_table_new (DBUS_HASH_INT,
1295                                  NULL, dbus_free);
1296   if (table2 == NULL)
1297     return FALSE;
1298
1299   i = 0;
1300   while (i < 3000)
1301     {
1302       char buf[256];
1303       sprintf (buf, "Hash key %d", i);
1304       void *value;
1305       char *key;
1306
1307       key = _dbus_strdup (buf);
1308       if (key == NULL)
1309         return FALSE;
1310       value = _dbus_strdup ("Value!");
1311       if (value == NULL)
1312         return FALSE;
1313
1314       if (!_dbus_hash_iter_lookup (table1,
1315                                    key, TRUE, &iter))
1316         return FALSE;
1317       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1318       _dbus_hash_iter_set_value (&iter, value);
1319
1320       value = _dbus_strdup (buf);
1321       if (value == NULL)
1322         return FALSE;
1323
1324       if (!_dbus_hash_iter_lookup (table2,
1325                                    _DBUS_INT_TO_POINTER (i), TRUE, &iter))
1326         return FALSE;
1327       _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
1328       _dbus_hash_iter_set_value (&iter, value);
1329
1330       _dbus_assert (count_entries (table1) == i + 1);
1331       _dbus_assert (count_entries (table2) == i + 1);
1332
1333       if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
1334         return FALSE;
1335
1336       value = _dbus_hash_iter_get_value (&iter);
1337       _dbus_assert (value != NULL);
1338       _dbus_assert (strcmp (value, "Value!") == 0);
1339
1340       /* Iterate just to be sure it works, though
1341        * it's a stupid thing to do
1342        */
1343       while (_dbus_hash_iter_next (&iter))
1344         ;
1345
1346       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1347         return FALSE;
1348
1349       value = _dbus_hash_iter_get_value (&iter);
1350       _dbus_assert (value != NULL);
1351       _dbus_assert (strcmp (value, buf) == 0);
1352
1353       /* Iterate just to be sure it works, though
1354        * it's a stupid thing to do
1355        */
1356       while (_dbus_hash_iter_next (&iter))
1357         ;
1358
1359       ++i;
1360     }
1361
1362   --i;
1363   while (i >= 0)
1364     {
1365       char buf[256];
1366       sprintf (buf, "Hash key %d", i);
1367
1368       if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
1369         _dbus_assert_not_reached ("hash entry should have existed");
1370       _dbus_hash_iter_remove_entry (&iter);
1371
1372       if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
1373         _dbus_assert_not_reached ("hash entry should have existed");
1374       _dbus_hash_iter_remove_entry (&iter);
1375
1376       _dbus_assert (count_entries (table1) == i);
1377       _dbus_assert (count_entries (table2) == i);
1378
1379       --i;
1380     }
1381
1382   _dbus_hash_table_unref (table1);
1383   _dbus_hash_table_unref (table2);
1384
1385
1386   return TRUE;
1387 }
1388
1389 #endif