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