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