xref: /external/dbus/dbus/dbus-hash.c

/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
/* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
 *
 * Copyright (C) 2002  Red Hat, Inc.
 * Copyright (c) 1991-1993 The Regents of the University of California.
 * Copyright (c) 1994 Sun Microsystems, Inc.
 *
 * Hash table implementation based on generic/tclHash.c from the Tcl
 * source code. The original Tcl license applies to portions of the
 * code from tclHash.c; the Tcl license follows this standad D-Bus
 * license information.
 *
 * Licensed under the Academic Free License version 2.1
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */
/*
 * The following copyright applies to code from the Tcl distribution.
 *
 * Copyright (c) 1991-1993 The Regents of the University of California.
 * Copyright (c) 1994 Sun Microsystems, Inc.
 *
 * This software is copyrighted by the Regents of the University of
 * California, Sun Microsystems, Inc., Scriptics Corporation, and
 * other parties.  The following terms apply to all files associated
 * with the software unless explicitly disclaimed in individual files.
 *
 * The authors hereby grant permission to use, copy, modify,
 * distribute, and license this software and its documentation for any
 * purpose, provided that existing copyright notices are retained in
 * all copies and that this notice is included verbatim in any
 * distributions. No written agreement, license, or royalty fee is
 * required for any of the authorized uses.  Modifications to this
 * software may be copyrighted by their authors and need not follow
 * the licensing terms described here, provided that the new terms are
 * clearly indicated on the first page of each file where they apply.
 *
 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
 * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * GOVERNMENT USE: If you are acquiring this software on behalf of the
 * U.S. government, the Government shall have only "Restricted Rights"
 * in the software and related documentation as defined in the Federal
 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
 * are acquiring the software on behalf of the Department of Defense,
 * the software shall be classified as "Commercial Computer Software"
 * and the Government shall have only "Restricted Rights" as defined
 * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
 * foregoing, the authors grant the U.S. Government and others acting
 * in its behalf permission to use and distribute the software in
 * accordance with the terms specified in this license.
 */

#include <config.h>
#include "dbus-hash.h"
#include "dbus-internals.h"
#include "dbus-mempool.h"

/**
 * @defgroup DBusHashTable Hash table
 * @ingroup  DBusInternals
 * @brief DBusHashTable data structure
 *
 * Types and functions related to DBusHashTable.
 */

/**
 * @defgroup DBusHashTableInternals Hash table implementation details
 * @ingroup  DBusInternals
 * @brief DBusHashTable implementation details
 *
 * The guts of DBusHashTable.
 *
 * @{
 */

/**
 * When there are this many entries per bucket, on average, rebuild
 * the hash table to make it larger.
 */
#define REBUILD_MULTIPLIER  3

/**
 * Takes a preliminary integer hash value and produces an index into a
 * hash tables bucket list.  The idea is to make it so that
 * preliminary values that are arbitrarily similar will end up in
 * different buckets.  The hash function was taken from a
 * random-number generator. (This is used to hash integers.)
 *
 * The down_shift drops off the high bits of the hash index, and
 * decreases as we increase the number of hash buckets (to keep more
 * range in the hash index). The mask also strips high bits and strips
 * fewer high bits as the number of hash buckets increases.
 * I don't understand two things: why is the initial downshift 28
 * to keep 4 bits when the initial mask is 011 to keep 2 bits,
 * and why do we have both a mask and a downshift?
 *
 */
#define RANDOM_INDEX(table, i) \
    (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)

/**
 * Initial number of buckets in hash table (hash table statically
 * allocates its buckets for this size and below).
 * The initial mask has to be synced to this.
 */
#define DBUS_SMALL_HASH_TABLE 4

/**
 * Typedef for DBusHashEntry
 */
typedef struct DBusHashEntry DBusHashEntry;

/**
 * @brief Internal representation of a hash entry.
 *
 * A single entry (key-value pair) in the hash table.
 * Internal to hash table implementation.
 */
struct DBusHashEntry
{
  DBusHashEntry *next;    /**< Pointer to next entry in this
                           * hash bucket, or #NULL for end of
                           * chain.
                           */
  void *key;              /**< Hash key */
  void *value;            /**< Hash value */
};

/**
 * Function used to find and optionally create a hash entry.
 */
typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable        *table,
                                                  void                 *key,
                                                  dbus_bool_t           create_if_not_found,
                                                  DBusHashEntry      ***bucket,
                                                  DBusPreallocatedHash *preallocated);

/**
 * @brief Internals of DBusHashTable.
 *
 * Hash table internals. Hash tables are opaque objects, they must be
 * used via accessor functions.
 */
struct DBusHashTable {
  int refcount;                       /**< Reference count */

  DBusHashEntry **buckets;            /**< Pointer to bucket array.  Each
                                       * element points to first entry in
                                       * bucket's hash chain, or #NULL.
                                       */
  DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
                                       /**< Bucket array used for small tables
                                        * (to avoid mallocs and frees).
                                        */
  int n_buckets;                       /**< Total number of buckets allocated
                                        * at **buckets.
                                        */
  int n_entries;                       /**< Total number of entries present
                                        * in table.
                                        */
  int hi_rebuild_size;                 /**< Enlarge table when n_entries gets
                                        * to be this large.
                                        */
  int lo_rebuild_size;                 /**< Shrink table when n_entries gets
                                        * below this.
                                        */
  int down_shift;                      /**< Shift count used in hashing
                                        * function.  Designed to use high-
                                        * order bits of randomized keys.
                                        */
  int mask;                            /**< Mask value used in hashing
                                        * function.
                                        */
  DBusHashType key_type;               /**< Type of keys used in this table */


  DBusFindEntryFunction find_function; /**< Function for finding entries */

  DBusFreeFunction free_key_function;   /**< Function to free keys */
  DBusFreeFunction free_value_function; /**< Function to free values */

  DBusMemPool *entry_pool;              /**< Memory pool for hash entries */
};

/**
 * @brief Internals of DBusHashIter.
 */
typedef struct
{
  DBusHashTable *table;     /**< Pointer to table containing entry. */
  DBusHashEntry **bucket;   /**< Pointer to bucket that points to
                             * first entry in this entry's chain:
                             * used for deleting the entry.
                             */
  DBusHashEntry *entry;      /**< Current hash entry */
  DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
  int next_bucket;           /**< index of next bucket */
  int n_entries_on_init;     /**< used to detect table resize since initialization */
} DBusRealHashIter;

static DBusHashEntry* find_direct_function      (DBusHashTable          *table,
                                                 void                   *key,
                                                 dbus_bool_t             create_if_not_found,
                                                 DBusHashEntry        ***bucket,
                                                 DBusPreallocatedHash   *preallocated);
static DBusHashEntry* find_string_function      (DBusHashTable          *table,
                                                 void                   *key,
                                                 dbus_bool_t             create_if_not_found,
                                                 DBusHashEntry        ***bucket,
                                                 DBusPreallocatedHash   *preallocated);
#ifdef DBUS_BUILD_TESTS
static DBusHashEntry* find_two_strings_function (DBusHashTable          *table,
                                                 void                   *key,
                                                 dbus_bool_t             create_if_not_found,
                                                 DBusHashEntry        ***bucket,
                                                 DBusPreallocatedHash   *preallocated);
#endif
static unsigned int   string_hash               (const char             *str);
#ifdef DBUS_BUILD_TESTS
static unsigned int   two_strings_hash          (const char             *str);
#endif
static void           rebuild_table             (DBusHashTable          *table);
static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
static void           remove_entry              (DBusHashTable          *table,
                                                 DBusHashEntry         **bucket,
                                                 DBusHashEntry          *entry);
static void           free_entry                (DBusHashTable          *table,
                                                 DBusHashEntry          *entry);
static void           free_entry_data           (DBusHashTable          *table,
                                                 DBusHashEntry          *entry);


/** @} */

/**
 * @addtogroup DBusHashTable
 * @{
 */

/**
 * @typedef DBusHashIter
 *
 * Public opaque hash table iterator object.
 */

/**
 * @typedef DBusHashTable
 *
 * Public opaque hash table object.
 */

/**
 * @typedef DBusHashType
 *
 * Indicates the type of a key in the hash table.
 */

/**
 * Constructs a new hash table. Should be freed with
 * _dbus_hash_table_unref(). If memory cannot be
 * allocated for the hash table, returns #NULL.
 *
 * @param type the type of hash key to use.
 * @param key_free_function function to free hash keys.
 * @param value_free_function function to free hash values.
 * @returns a new DBusHashTable or #NULL if no memory.
 */
DBusHashTable*
_dbus_hash_table_new (DBusHashType     type,
                      DBusFreeFunction key_free_function,
                      DBusFreeFunction value_free_function)
{
  DBusHashTable *table;
  DBusMemPool *entry_pool;

  table = dbus_new0 (DBusHashTable, 1);
  if (table == NULL)
    return NULL;

  entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
  if (entry_pool == NULL)
    {
      dbus_free (table);
      return NULL;
    }

  table->refcount = 1;
  table->entry_pool = entry_pool;

  _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));

  table->buckets = table->static_buckets;
  table->n_buckets = DBUS_SMALL_HASH_TABLE;
  table->n_entries = 0;
  table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
  table->lo_rebuild_size = 0;
  table->down_shift = 28;
  table->mask = 3;
  table->key_type = type;

  _dbus_assert (table->mask < table->n_buckets);

  switch (table->key_type)
    {
    case DBUS_HASH_INT:
    case DBUS_HASH_POINTER:
    case DBUS_HASH_UINTPTR:
      table->find_function = find_direct_function;
      break;
    case DBUS_HASH_STRING:
      table->find_function = find_string_function;
      break;
    case DBUS_HASH_TWO_STRINGS:
#ifdef DBUS_BUILD_TESTS
      table->find_function = find_two_strings_function;
#endif
      break;
    default:
      _dbus_assert_not_reached ("Unknown hash table type");
      break;
    }

  table->free_key_function = key_free_function;
  table->free_value_function = value_free_function;

  return table;
}


/**
 * Increments the reference count for a hash table.
 *
 * @param table the hash table to add a reference to.
 * @returns the hash table.
 */
DBusHashTable *
_dbus_hash_table_ref (DBusHashTable *table)
{
  table->refcount += 1;

  return table;
}

/**
 * Decrements the reference count for a hash table,
 * freeing the hash table if the count reaches zero.
 *
 * @param table the hash table to remove a reference from.
 */
void
_dbus_hash_table_unref (DBusHashTable *table)
{
  table->refcount -= 1;

  if (table->refcount == 0)
    {
#if 0
      DBusHashEntry *entry;
      DBusHashEntry *next;
      int i;

      /* Free the entries in the table. */
      for (i = 0; i < table->n_buckets; i++)
        {
          entry = table->buckets[i];
          while (entry != NULL)
            {
              next = entry->next;

              free_entry (table, entry);

              entry = next;
            }
        }
#else
      DBusHashEntry *entry;
      int i;

      /* Free the entries in the table. */
      for (i = 0; i < table->n_buckets; i++)
        {
          entry = table->buckets[i];
          while (entry != NULL)
            {
              free_entry_data (table, entry);

              entry = entry->next;
            }
        }
      /* We can do this very quickly with memory pools ;-) */
      _dbus_mem_pool_free (table->entry_pool);
#endif

      /* Free the bucket array, if it was dynamically allocated. */
      if (table->buckets != table->static_buckets)
        dbus_free (table->buckets);

      dbus_free (table);
    }
}

/**
 * Removed all entries from a hash table.
 *
 * @param table the hash table to remove all entries from.
 */
void
_dbus_hash_table_remove_all (DBusHashTable *table)
{
  DBusHashIter iter;
  _dbus_hash_iter_init (table, &iter);
  while (_dbus_hash_iter_next (&iter))
    {
      _dbus_hash_iter_remove_entry(&iter);
    }
}

static DBusHashEntry*
alloc_entry (DBusHashTable *table)
{
  DBusHashEntry *entry;

  entry = _dbus_mem_pool_alloc (table->entry_pool);

  return entry;
}

static void
free_entry_data (DBusHashTable  *table,
		 DBusHashEntry  *entry)
{
  if (table->free_key_function)
    (* table->free_key_function) (entry->key);
  if (table->free_value_function)
    (* table->free_value_function) (entry->value);
}

static void
free_entry (DBusHashTable  *table,
            DBusHashEntry  *entry)
{
  free_entry_data (table, entry);
  _dbus_mem_pool_dealloc (table->entry_pool, entry);
}

static void
remove_entry (DBusHashTable  *table,
              DBusHashEntry **bucket,
              DBusHashEntry  *entry)
{
  _dbus_assert (table != NULL);
  _dbus_assert (bucket != NULL);
  _dbus_assert (*bucket != NULL);
  _dbus_assert (entry != NULL);

  if (*bucket == entry)
    *bucket = entry->next;
  else
    {
      DBusHashEntry *prev;
      prev = *bucket;

      while (prev->next != entry)
        prev = prev->next;

      _dbus_assert (prev != NULL);

      prev->next = entry->next;
    }

  table->n_entries -= 1;
  free_entry (table, entry);
}

/**
 * Initializes a hash table iterator. To iterate over all entries in a
 * hash table, use the following code (the printf assumes a hash
 * from strings to strings obviously):
 *
 * @code
 * DBusHashIter iter;
 *
 * _dbus_hash_iter_init (table, &iter);
 * while (_dbus_hash_iter_next (&iter))
 *   {
 *      printf ("The first key is %s and value is %s\n",
 *              _dbus_hash_iter_get_string_key (&iter),
 *              _dbus_hash_iter_get_value (&iter));
 *   }
 *
 *
 * @endcode
 *
 * The iterator is initialized pointing "one before" the first hash
 * entry. The first call to _dbus_hash_iter_next() moves it onto
 * the first valid entry or returns #FALSE if the hash table is
 * empty. Subsequent calls move to the next valid entry or return
 * #FALSE if there are no more entries.
 *
 * Note that it is guaranteed to be safe to remove a hash entry during
 * iteration, but it is not safe to add a hash entry.
 *
 * @param table the hash table to iterate over.
 * @param iter the iterator to initialize.
 */
void
_dbus_hash_iter_init (DBusHashTable *table,
                      DBusHashIter  *iter)
{
  DBusRealHashIter *real;

  _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));

  real = (DBusRealHashIter*) iter;

  real->table = table;
  real->bucket = NULL;
  real->entry = NULL;
  real->next_entry = NULL;
  real->next_bucket = 0;
  real->n_entries_on_init = table->n_entries;
}

/**
 * Move the hash iterator forward one step, to the next hash entry.
 * The documentation for _dbus_hash_iter_init() explains in more
 * detail.
 *
 * @param iter the iterator to move forward.
 * @returns #FALSE if there are no more entries to move to.
 */
dbus_bool_t
_dbus_hash_iter_next (DBusHashIter  *iter)
{
  DBusRealHashIter *real;

  _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));

  real = (DBusRealHashIter*) iter;

  /* if this assertion failed someone probably added hash entries
   * during iteration, which is bad.
   */
  _dbus_assert (real->n_entries_on_init >= real->table->n_entries);

  /* Remember that real->entry may have been deleted */

  while (real->next_entry == NULL)
    {
      if (real->next_bucket >= real->table->n_buckets)
        {
          /* invalidate iter and return false */
          real->entry = NULL;
          real->table = NULL;
          real->bucket = NULL;
          return FALSE;
        }

      real->bucket = &(real->table->buckets[real->next_bucket]);
      real->next_entry = *(real->bucket);
      real->next_bucket += 1;
    }

  _dbus_assert (real->next_entry != NULL);
  _dbus_assert (real->bucket != NULL);

  real->entry = real->next_entry;
  real->next_entry = real->entry->next;

  return TRUE;
}

/**
 * Removes the current entry from the hash table.
 * If a key_free_function or value_free_function
 * was provided to _dbus_hash_table_new(),
 * frees the key and/or value for this entry.
 *
 * @param iter the hash table iterator.
 */
void
_dbus_hash_iter_remove_entry (DBusHashIter *iter)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);
  _dbus_assert (real->bucket != NULL);

  remove_entry (real->table, real->bucket, real->entry);

  real->entry = NULL; /* make it crash if you try to use this entry */
}

/**
 * Gets the value of the current entry.
 *
 * @param iter the hash table iterator.
 */
void*
_dbus_hash_iter_get_value (DBusHashIter *iter)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);

  return real->entry->value;
}

/**
 * Sets the value of the current entry.
 * If the hash table has a value_free_function
 * it will be used to free the previous value.
 * The hash table will own the passed-in value
 * (it will not be copied).
 *
 * @param iter the hash table iterator.
 * @param value the new value.
 */
void
_dbus_hash_iter_set_value (DBusHashIter *iter,
                           void         *value)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);

  if (real->table->free_value_function && value != real->entry->value)
    (* real->table->free_value_function) (real->entry->value);

  real->entry->value = value;
}

/**
 * Gets the key for the current entry.
 * Only works for hash tables of type #DBUS_HASH_INT.
 *
 * @param iter the hash table iterator.
 */
int
_dbus_hash_iter_get_int_key (DBusHashIter *iter)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);

  return _DBUS_POINTER_TO_INT (real->entry->key);
}

/**
 * Gets the key for the current entry.
 * Only works for hash tables of type #DBUS_HASH_UINTPTR.
 *
 * @param iter the hash table iterator.
 */
uintptr_t
_dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);

  return (uintptr_t) real->entry->key;
}

/**
 * Gets the key for the current entry.
 * Only works for hash tables of type #DBUS_HASH_STRING
 * @param iter the hash table iterator.
 */
const char*
_dbus_hash_iter_get_string_key (DBusHashIter *iter)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);

  return real->entry->key;
}

#ifdef DBUS_BUILD_TESTS
/**
 * Gets the key for the current entry.
 * Only works for hash tables of type #DBUS_HASH_TWO_STRINGS
 * @param iter the hash table iterator.
 */
const char*
_dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
{
  DBusRealHashIter *real;

  real = (DBusRealHashIter*) iter;

  _dbus_assert (real->table != NULL);
  _dbus_assert (real->entry != NULL);

  return real->entry->key;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * A low-level but efficient interface for manipulating the hash
 * table.  It's efficient because you can get, set, and optionally
 * create the hash entry while only running the hash function one
 * time.
 *
 * Note that while calling _dbus_hash_iter_next() on the iterator
 * filled in by this function may work, it's completely
 * undefined which entries are after this iter and which
 * are before it. So it would be silly to iterate using this
 * iterator.
 *
 * If the hash entry is created, its value will be initialized
 * to all bits zero.
 *
 * #FALSE may be returned due to memory allocation failure, or
 * because create_if_not_found was #FALSE and the entry
 * did not exist.
 *
 * If create_if_not_found is #TRUE and the entry is created, the hash
 * table takes ownership of the key that's passed in.
 *
 * For a hash table of type #DBUS_HASH_INT, cast the int
 * key to the key parameter using #_DBUS_INT_TO_POINTER().
 *
 * @param table the hash table.
 * @param key the hash key.
 * @param create_if_not_found if #TRUE, create the entry if it didn't exist.
 * @param iter the iterator to initialize.
 * @returns #TRUE if the hash entry now exists (and the iterator is thus valid).
 */
dbus_bool_t
_dbus_hash_iter_lookup (DBusHashTable *table,
                        void          *key,
                        dbus_bool_t    create_if_not_found,
                        DBusHashIter  *iter)
{
  DBusRealHashIter *real;
  DBusHashEntry *entry;
  DBusHashEntry **bucket;

  _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));

  real = (DBusRealHashIter*) iter;

  entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);

  if (entry == NULL)
    return FALSE;

  real->table = table;
  real->bucket = bucket;
  real->entry = entry;
  real->next_entry = entry->next;
  real->next_bucket = (bucket - table->buckets) + 1;
  real->n_entries_on_init = table->n_entries;

  _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);

  return TRUE;
}

static void
add_allocated_entry (DBusHashTable   *table,
                     DBusHashEntry   *entry,
                     unsigned int     idx,
                     void            *key,
                     DBusHashEntry ***bucket)
{
  DBusHashEntry **b;

  entry->key = key;

  b = &(table->buckets[idx]);
  entry->next = *b;
  *b = entry;

  if (bucket)
    *bucket = b;

  table->n_entries += 1;

  /* note we ONLY rebuild when ADDING - because you can iterate over a
   * table and remove entries safely.
   */
  if (table->n_entries >= table->hi_rebuild_size ||
      table->n_entries < table->lo_rebuild_size)
    rebuild_table (table);
}

static DBusHashEntry*
add_entry (DBusHashTable        *table,
           unsigned int          idx,
           void                 *key,
           DBusHashEntry      ***bucket,
           DBusPreallocatedHash *preallocated)
{
  DBusHashEntry  *entry;

  if (preallocated == NULL)
    {
      entry = alloc_entry (table);
      if (entry == NULL)
        {
          if (bucket)
            *bucket = NULL;
          return NULL;
        }
    }
  else
    {
      entry = (DBusHashEntry*) preallocated;
    }

  add_allocated_entry (table, entry, idx, key, bucket);

  return entry;
}

/* This is g_str_hash from GLib which was
 * extensively discussed/tested/profiled
 */
static unsigned int
string_hash (const char *str)
{
  const char *p = str;
  unsigned int h = *p;

  if (h)
    for (p += 1; *p != '\0'; p++)
      h = (h << 5) - h + *p;

  return h;
}

#ifdef DBUS_BUILD_TESTS
/* This hashes a memory block with two nul-terminated strings
 * in it, used in dbus-object-registry.c at the moment.
 */
static unsigned int
two_strings_hash (const char *str)
{
  const char *p = str;
  unsigned int h = *p;

  if (h)
    for (p += 1; *p != '\0'; p++)
      h = (h << 5) - h + *p;

  for (p += 1; *p != '\0'; p++)
    h = (h << 5) - h + *p;

  return h;
}
#endif /* DBUS_BUILD_TESTS */

/** Key comparison function */
typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);

static DBusHashEntry*
find_generic_function (DBusHashTable        *table,
                       void                 *key,
                       unsigned int          idx,
                       KeyCompareFunc        compare_func,
                       dbus_bool_t           create_if_not_found,
                       DBusHashEntry      ***bucket,
                       DBusPreallocatedHash *preallocated)
{
  DBusHashEntry *entry;

  if (bucket)
    *bucket = NULL;

  /* Search all of the entries in this bucket. */
  entry = table->buckets[idx];
  while (entry != NULL)
    {
      if ((compare_func == NULL && key == entry->key) ||
          (compare_func != NULL && (* compare_func) (key, entry->key) == 0))
        {
          if (bucket)
            *bucket = &(table->buckets[idx]);

          if (preallocated)
            _dbus_hash_table_free_preallocated_entry (table, preallocated);

          return entry;
        }

      entry = entry->next;
    }

  if (create_if_not_found)
    entry = add_entry (table, idx, key, bucket, preallocated);
  else if (preallocated)
    _dbus_hash_table_free_preallocated_entry (table, preallocated);

  return entry;
}

static DBusHashEntry*
find_string_function (DBusHashTable        *table,
                      void                 *key,
                      dbus_bool_t           create_if_not_found,
                      DBusHashEntry      ***bucket,
                      DBusPreallocatedHash *preallocated)
{
  unsigned int idx;

  idx = string_hash (key) & table->mask;

  return find_generic_function (table, key, idx,
                                (KeyCompareFunc) strcmp, create_if_not_found, bucket,
                                preallocated);
}

#ifdef DBUS_BUILD_TESTS
static int
two_strings_cmp (const char *a,
                 const char *b)
{
  size_t len_a;
  size_t len_b;
  int res;

  res = strcmp (a, b);
  if (res != 0)
    return res;

  len_a = strlen (a);
  len_b = strlen (b);

  return strcmp (a + len_a + 1, b + len_b + 1);
}
#endif

#ifdef DBUS_BUILD_TESTS
static DBusHashEntry*
find_two_strings_function (DBusHashTable        *table,
                           void                 *key,
                           dbus_bool_t           create_if_not_found,
                           DBusHashEntry      ***bucket,
                           DBusPreallocatedHash *preallocated)
{
  unsigned int idx;

  idx = two_strings_hash (key) & table->mask;

  return find_generic_function (table, key, idx,
                                (KeyCompareFunc) two_strings_cmp, create_if_not_found, bucket,
                                preallocated);
}
#endif /* DBUS_BUILD_TESTS */

static DBusHashEntry*
find_direct_function (DBusHashTable        *table,
                      void                 *key,
                      dbus_bool_t           create_if_not_found,
                      DBusHashEntry      ***bucket,
                      DBusPreallocatedHash *preallocated)
{
  unsigned int idx;

  idx = RANDOM_INDEX (table, key) & table->mask;


  return find_generic_function (table, key, idx,
                                NULL, create_if_not_found, bucket,
                                preallocated);
}

static void
rebuild_table (DBusHashTable *table)
{
  int old_size;
  int new_buckets;
  DBusHashEntry **old_buckets;
  DBusHashEntry **old_chain;
  DBusHashEntry *entry;
  dbus_bool_t growing;

  /*
   * Allocate and initialize the new bucket array, and set up
   * hashing constants for new array size.
   */

  growing = table->n_entries >= table->hi_rebuild_size;

  old_size = table->n_buckets;
  old_buckets = table->buckets;

  if (growing)
    {
      /* overflow paranoia */
      if (table->n_buckets < _DBUS_INT_MAX / 4 &&
          table->down_shift >= 0)
        new_buckets = table->n_buckets * 4;
      else
        return; /* can't grow anymore */
    }
  else
    {
      new_buckets = table->n_buckets / 4;
      if (new_buckets < DBUS_SMALL_HASH_TABLE)
        return; /* don't bother shrinking this far */
    }

  table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
  if (table->buckets == NULL)
    {
      /* out of memory, yay - just don't reallocate, the table will
       * still work, albeit more slowly.
       */
      table->buckets = old_buckets;
      return;
    }

  table->n_buckets = new_buckets;

  if (growing)
    {
      table->lo_rebuild_size = table->hi_rebuild_size;
      table->hi_rebuild_size *= 4;

      table->down_shift -= 2;               /* keep 2 more high bits */
      table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
    }
  else
    {
      table->hi_rebuild_size = table->lo_rebuild_size;
      table->lo_rebuild_size /= 4;

      table->down_shift += 2;         /* keep 2 fewer high bits */
      table->mask = table->mask >> 2; /* keep 2 fewer high bits */
    }

#if 0
  printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
          growing ? "GROW" : "SHRINK",
          table->lo_rebuild_size,
          table->hi_rebuild_size,
          table->down_shift,
          table->mask);
#endif

  _dbus_assert (table->lo_rebuild_size >= 0);
  _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
  _dbus_assert (table->mask != 0);
  /* the mask is essentially the max index */
  _dbus_assert (table->mask < table->n_buckets);

  /*
   * Rehash all of the existing entries into the new bucket array.
   */

  for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
    {
      for (entry = *old_chain; entry != NULL; entry = *old_chain)
        {
          unsigned int idx;
          DBusHashEntry **bucket;

          *old_chain = entry->next;
          switch (table->key_type)
            {
            case DBUS_HASH_STRING:
              idx = string_hash (entry->key) & table->mask;
              break;
            case DBUS_HASH_TWO_STRINGS:
#ifdef DBUS_BUILD_TESTS
              idx = two_strings_hash (entry->key) & table->mask;
#else
              idx = 0;
              _dbus_assert_not_reached ("two-strings is not enabled");
#endif
              break;
            case DBUS_HASH_INT:
            case DBUS_HASH_UINTPTR:
            case DBUS_HASH_POINTER:
              idx = RANDOM_INDEX (table, entry->key);
              break;
            default:
              idx = 0;
              _dbus_assert_not_reached ("Unknown hash table type");
              break;
            }

          bucket = &(table->buckets[idx]);
          entry->next = *bucket;
          *bucket = entry;
        }
    }

  /* Free the old bucket array, if it was dynamically allocated. */

  if (old_buckets != table->static_buckets)
    dbus_free (old_buckets);
}

/**
 * Looks up the value for a given string in a hash table
 * of type #DBUS_HASH_STRING. Returns %NULL if the value
 * is not present. (A not-present entry is indistinguishable
 * from an entry with a value of %NULL.)
 * @param table the hash table.
 * @param key the string to look up.
 * @returns the value of the hash entry.
 */
void*
_dbus_hash_table_lookup_string (DBusHashTable *table,
                                const char    *key)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_STRING);

  entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);

  if (entry)
    return entry->value;
  else
    return NULL;
}

#ifdef DBUS_BUILD_TESTS
/**
 * Looks up the value for a given string in a hash table
 * of type #DBUS_HASH_TWO_STRINGS. Returns %NULL if the value
 * is not present. (A not-present entry is indistinguishable
 * from an entry with a value of %NULL.)
 * @param table the hash table.
 * @param key the string to look up.
 * @returns the value of the hash entry.
 */
void*
_dbus_hash_table_lookup_two_strings (DBusHashTable *table,
                                     const char    *key)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);

  entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);

  if (entry)
    return entry->value;
  else
    return NULL;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * Looks up the value for a given integer in a hash table
 * of type #DBUS_HASH_INT. Returns %NULL if the value
 * is not present. (A not-present entry is indistinguishable
 * from an entry with a value of %NULL.)
 * @param table the hash table.
 * @param key the integer to look up.
 * @returns the value of the hash entry.
 */
void*
_dbus_hash_table_lookup_int (DBusHashTable *table,
                             int            key)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_INT);

  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);

  if (entry)
    return entry->value;
  else
    return NULL;
}

#ifdef DBUS_BUILD_TESTS
/* disabled since it's only used for testing */
/**
 * Looks up the value for a given integer in a hash table
 * of type #DBUS_HASH_POINTER. Returns %NULL if the value
 * is not present. (A not-present entry is indistinguishable
 * from an entry with a value of %NULL.)
 * @param table the hash table.
 * @param key the integer to look up.
 * @returns the value of the hash entry.
 */
void*
_dbus_hash_table_lookup_pointer (DBusHashTable *table,
                                 void          *key)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_POINTER);

  entry = (* table->find_function) (table, key, FALSE, NULL, NULL);

  if (entry)
    return entry->value;
  else
    return NULL;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * Looks up the value for a given integer in a hash table
 * of type #DBUS_HASH_UINTPTR. Returns %NULL if the value
 * is not present. (A not-present entry is indistinguishable
 * from an entry with a value of %NULL.)
 * @param table the hash table.
 * @param key the integer to look up.
 * @returns the value of the hash entry.
 */
void*
_dbus_hash_table_lookup_uintptr (DBusHashTable *table,
                                 uintptr_t      key)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);

  entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);

  if (entry)
    return entry->value;
  else
    return NULL;
}

/**
 * Removes the hash entry for the given key. If no hash entry
 * for the key exists, does nothing.
 *
 * @param table the hash table.
 * @param key the hash key.
 * @returns #TRUE if the entry existed
 */
dbus_bool_t
_dbus_hash_table_remove_string (DBusHashTable *table,
                                const char    *key)
{
  DBusHashEntry *entry;
  DBusHashEntry **bucket;

  _dbus_assert (table->key_type == DBUS_HASH_STRING);

  entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);

  if (entry)
    {
      remove_entry (table, bucket, entry);
      return TRUE;
    }
  else
    return FALSE;
}

#ifdef DBUS_BUILD_TESTS
/**
 * Removes the hash entry for the given key. If no hash entry
 * for the key exists, does nothing.
 *
 * @param table the hash table.
 * @param key the hash key.
 * @returns #TRUE if the entry existed
 */
dbus_bool_t
_dbus_hash_table_remove_two_strings (DBusHashTable *table,
                                     const char    *key)
{
  DBusHashEntry *entry;
  DBusHashEntry **bucket;

  _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);

  entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);

  if (entry)
    {
      remove_entry (table, bucket, entry);
      return TRUE;
    }
  else
    return FALSE;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * Removes the hash entry for the given key. If no hash entry
 * for the key exists, does nothing.
 *
 * @param table the hash table.
 * @param key the hash key.
 * @returns #TRUE if the entry existed
 */
dbus_bool_t
_dbus_hash_table_remove_int (DBusHashTable *table,
                             int            key)
{
  DBusHashEntry *entry;
  DBusHashEntry **bucket;

  _dbus_assert (table->key_type == DBUS_HASH_INT);

  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);

  if (entry)
    {
      remove_entry (table, bucket, entry);
      return TRUE;
    }
  else
    return FALSE;
}

#ifdef DBUS_BUILD_TESTS
/* disabled since it's only used for testing */
/**
 * Removes the hash entry for the given key. If no hash entry
 * for the key exists, does nothing.
 *
 * @param table the hash table.
 * @param key the hash key.
 * @returns #TRUE if the entry existed
 */
dbus_bool_t
_dbus_hash_table_remove_pointer (DBusHashTable *table,
                                 void          *key)
{
  DBusHashEntry *entry;
  DBusHashEntry **bucket;

  _dbus_assert (table->key_type == DBUS_HASH_POINTER);

  entry = (* table->find_function) (table, key, FALSE, &bucket, NULL);

  if (entry)
    {
      remove_entry (table, bucket, entry);
      return TRUE;
    }
  else
    return FALSE;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * Removes the hash entry for the given key. If no hash entry
 * for the key exists, does nothing.
 *
 * @param table the hash table.
 * @param key the hash key.
 * @returns #TRUE if the entry existed
 */
dbus_bool_t
_dbus_hash_table_remove_uintptr (DBusHashTable *table,
                                 uintptr_t      key)
{
  DBusHashEntry *entry;
  DBusHashEntry **bucket;

  _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);

  entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);

  if (entry)
    {
      remove_entry (table, bucket, entry);
      return TRUE;
    }
  else
    return FALSE;
}

/**
 * Creates a hash entry with the given key and value.
 * The key and value are not copied; they are stored
 * in the hash table by reference. If an entry with the
 * given key already exists, the previous key and value
 * are overwritten (and freed if the hash table has
 * a key_free_function and/or value_free_function).
 *
 * Returns #FALSE if memory for the new hash entry
 * can't be allocated.
 *
 * @param table the hash table.
 * @param key the hash entry key.
 * @param value the hash entry value.
 */
dbus_bool_t
_dbus_hash_table_insert_string (DBusHashTable *table,
                                char          *key,
                                void          *value)
{
  DBusPreallocatedHash *preallocated;

  _dbus_assert (table->key_type == DBUS_HASH_STRING);

  preallocated = _dbus_hash_table_preallocate_entry (table);
  if (preallocated == NULL)
    return FALSE;

  _dbus_hash_table_insert_string_preallocated (table, preallocated,
                                               key, value);

  return TRUE;
}

#ifdef DBUS_BUILD_TESTS
/**
 * Creates a hash entry with the given key and value.
 * The key and value are not copied; they are stored
 * in the hash table by reference. If an entry with the
 * given key already exists, the previous key and value
 * are overwritten (and freed if the hash table has
 * a key_free_function and/or value_free_function).
 *
 * Returns #FALSE if memory for the new hash entry
 * can't be allocated.
 *
 * @param table the hash table.
 * @param key the hash entry key.
 * @param value the hash entry value.
 */
dbus_bool_t
_dbus_hash_table_insert_two_strings (DBusHashTable *table,
                                     char          *key,
                                     void          *value)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);

  entry = (* table->find_function) (table, key, TRUE, NULL, NULL);

  if (entry == NULL)
    return FALSE; /* no memory */

  if (table->free_key_function && entry->key != key)
    (* table->free_key_function) (entry->key);

  if (table->free_value_function && entry->value != value)
    (* table->free_value_function) (entry->value);

  entry->key = key;
  entry->value = value;

  return TRUE;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * Creates a hash entry with the given key and value.
 * The key and value are not copied; they are stored
 * in the hash table by reference. If an entry with the
 * given key already exists, the previous key and value
 * are overwritten (and freed if the hash table has
 * a key_free_function and/or value_free_function).
 *
 * Returns #FALSE if memory for the new hash entry
 * can't be allocated.
 *
 * @param table the hash table.
 * @param key the hash entry key.
 * @param value the hash entry value.
 */
dbus_bool_t
_dbus_hash_table_insert_int (DBusHashTable *table,
                             int            key,
                             void          *value)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_INT);

  entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);

  if (entry == NULL)
    return FALSE; /* no memory */

  if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
    (* table->free_key_function) (entry->key);

  if (table->free_value_function && entry->value != value)
    (* table->free_value_function) (entry->value);

  entry->key = _DBUS_INT_TO_POINTER (key);
  entry->value = value;

  return TRUE;
}

#ifdef DBUS_BUILD_TESTS
/* disabled since it's only used for testing */
/**
 * Creates a hash entry with the given key and value.
 * The key and value are not copied; they are stored
 * in the hash table by reference. If an entry with the
 * given key already exists, the previous key and value
 * are overwritten (and freed if the hash table has
 * a key_free_function and/or value_free_function).
 *
 * Returns #FALSE if memory for the new hash entry
 * can't be allocated.
 *
 * @param table the hash table.
 * @param key the hash entry key.
 * @param value the hash entry value.
 */
dbus_bool_t
_dbus_hash_table_insert_pointer (DBusHashTable *table,
                                 void          *key,
                                 void          *value)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_POINTER);

  entry = (* table->find_function) (table, key, TRUE, NULL, NULL);

  if (entry == NULL)
    return FALSE; /* no memory */

  if (table->free_key_function && entry->key != key)
    (* table->free_key_function) (entry->key);

  if (table->free_value_function && entry->value != value)
    (* table->free_value_function) (entry->value);

  entry->key = key;
  entry->value = value;

  return TRUE;
}
#endif /* DBUS_BUILD_TESTS */

/**
 * Creates a hash entry with the given key and value.
 * The key and value are not copied; they are stored
 * in the hash table by reference. If an entry with the
 * given key already exists, the previous key and value
 * are overwritten (and freed if the hash table has
 * a key_free_function and/or value_free_function).
 *
 * Returns #FALSE if memory for the new hash entry
 * can't be allocated.
 *
 * @param table the hash table.
 * @param key the hash entry key.
 * @param value the hash entry value.
 */
dbus_bool_t
_dbus_hash_table_insert_uintptr (DBusHashTable *table,
                                 uintptr_t      key,
                                 void          *value)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);

  entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);

  if (entry == NULL)
    return FALSE; /* no memory */

  if (table->free_key_function && entry->key != (void*) key)
    (* table->free_key_function) (entry->key);

  if (table->free_value_function && entry->value != value)
    (* table->free_value_function) (entry->value);

  entry->key = (void*) key;
  entry->value = value;

  return TRUE;
}

/**
 * Preallocate an opaque data blob that allows us to insert into the
 * hash table at a later time without allocating any memory.
 *
 * @param table the hash table
 * @returns the preallocated data, or #NULL if no memory
 */
DBusPreallocatedHash*
_dbus_hash_table_preallocate_entry (DBusHashTable *table)
{
  DBusHashEntry *entry;

  entry = alloc_entry (table);

  return (DBusPreallocatedHash*) entry;
}

/**
 * Frees an opaque DBusPreallocatedHash that was *not* used
 * in order to insert into the hash table.
 *
 * @param table the hash table
 * @param preallocated the preallocated data
 */
void
_dbus_hash_table_free_preallocated_entry (DBusHashTable        *table,
                                          DBusPreallocatedHash *preallocated)
{
  DBusHashEntry *entry;

  _dbus_assert (preallocated != NULL);

  entry = (DBusHashEntry*) preallocated;

  /* Don't use free_entry(), since this entry has no key/data */
  _dbus_mem_pool_dealloc (table->entry_pool, entry);
}

/**
 * Inserts a string-keyed entry into the hash table, using a
 * preallocated data block from
 * _dbus_hash_table_preallocate_entry(). This function cannot fail due
 * to lack of memory. The DBusPreallocatedHash object is consumed and
 * should not be reused or freed. Otherwise this function works
 * just like _dbus_hash_table_insert_string().
 *
 * @param table the hash table
 * @param preallocated the preallocated data
 * @param key the hash key
 * @param value the value
 */
void
_dbus_hash_table_insert_string_preallocated (DBusHashTable        *table,
                                             DBusPreallocatedHash *preallocated,
                                             char                 *key,
                                             void                 *value)
{
  DBusHashEntry *entry;

  _dbus_assert (table->key_type == DBUS_HASH_STRING);
  _dbus_assert (preallocated != NULL);

  entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);

  _dbus_assert (entry != NULL);

  if (table->free_key_function && entry->key != key)
    (* table->free_key_function) (entry->key);

  if (table->free_value_function && entry->value != value)
    (* table->free_value_function) (entry->value);

  entry->key = key;
  entry->value = value;
}

/**
 * Gets the number of hash entries in a hash table.
 *
 * @param table the hash table.
 * @returns the number of entries in the table.
 */
int
_dbus_hash_table_get_n_entries (DBusHashTable *table)
{
  return table->n_entries;
}

/** @} */

#ifdef DBUS_BUILD_TESTS
#include "dbus-test.h"
#include <stdio.h>

/* If you're wondering why the hash table test takes
 * forever to run, it's because we call this function
 * in inner loops thus making things quadratic.
 */
static int
count_entries (DBusHashTable *table)
{
  DBusHashIter iter;
  int count;

  count = 0;
  _dbus_hash_iter_init (table, &iter);
  while (_dbus_hash_iter_next (&iter))
    ++count;

  _dbus_assert (count == _dbus_hash_table_get_n_entries (table));

  return count;
}

/* Copy the foo\0bar\0 double string thing */
static char*
_dbus_strdup2 (const char *str)
{
  size_t len;
  char *copy;

  if (str == NULL)
    return NULL;

  len = strlen (str);
  len += strlen ((str + len + 1));

  copy = dbus_malloc (len + 2);
  if (copy == NULL)
    return NULL;

  memcpy (copy, str, len + 2);

  return copy;
}

/**
 * @ingroup DBusHashTableInternals
 * Unit test for DBusHashTable
 * @returns #TRUE on success.
 */
dbus_bool_t
_dbus_hash_test (void)
{
  int i;
  DBusHashTable *table1;
  DBusHashTable *table2;
  DBusHashTable *table3;
  DBusHashTable *table4;
  DBusHashIter iter;
#define N_HASH_KEYS 5000
  char **keys;
  dbus_bool_t ret = FALSE;

  keys = dbus_new (char *, N_HASH_KEYS);
  if (keys == NULL)
    _dbus_assert_not_reached ("no memory");

  for (i = 0; i < N_HASH_KEYS; i++)
    {
      keys[i] = dbus_malloc (128);

      if (keys[i] == NULL)
	_dbus_assert_not_reached ("no memory");
    }

  printf ("Computing test hash keys...\n");
  i = 0;
  while (i < N_HASH_KEYS)
    {
      int len;

      /* all the hash keys are TWO_STRINGS, but
       * then we can also use those as regular strings.
       */

      len = sprintf (keys[i], "Hash key %d", i);
      sprintf (keys[i] + len + 1, "Two string %d", i);
      _dbus_assert (*(keys[i] + len) == '\0');
      _dbus_assert (*(keys[i] + len + 1) != '\0');
      ++i;
    }
  printf ("... done.\n");

  table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
                                 dbus_free, dbus_free);
  if (table1 == NULL)
    goto out;

  table2 = _dbus_hash_table_new (DBUS_HASH_INT,
                                 NULL, dbus_free);
  if (table2 == NULL)
    goto out;

  table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
                                 NULL, dbus_free);
  if (table3 == NULL)
    goto out;

  table4 = _dbus_hash_table_new (DBUS_HASH_TWO_STRINGS,
                                 dbus_free, dbus_free);
  if (table4 == NULL)
    goto out;


  /* Insert and remove a bunch of stuff, counting the table in between
   * to be sure it's not broken and that iteration works
   */
  i = 0;
  while (i < 3000)
    {
      void *value;
      char *key;

      key = _dbus_strdup (keys[i]);
      if (key == NULL)
        goto out;
      value = _dbus_strdup ("Value!");
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_string (table1,
                                           key, value))
        goto out;

      value = _dbus_strdup (keys[i]);
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_int (table2,
                                        i, value))
        goto out;

      value = _dbus_strdup (keys[i]);
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_uintptr (table3,
                                          i, value))
        goto out;

      key = _dbus_strdup2 (keys[i]);
      if (key == NULL)
        goto out;
      value = _dbus_strdup ("Value!");
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_two_strings (table4,
                                                key, value))
        goto out;

      _dbus_assert (count_entries (table1) == i + 1);
      _dbus_assert (count_entries (table2) == i + 1);
      _dbus_assert (count_entries (table3) == i + 1);
      _dbus_assert (count_entries (table4) == i + 1);

      value = _dbus_hash_table_lookup_string (table1, keys[i]);
      _dbus_assert (value != NULL);
      _dbus_assert (strcmp (value, "Value!") == 0);

      value = _dbus_hash_table_lookup_int (table2, i);
      _dbus_assert (value != NULL);
      _dbus_assert (strcmp (value, keys[i]) == 0);

      value = _dbus_hash_table_lookup_uintptr (table3, i);
      _dbus_assert (value != NULL);
      _dbus_assert (strcmp (value, keys[i]) == 0);

      value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
      _dbus_assert (value != NULL);
      _dbus_assert (strcmp (value, "Value!") == 0);

      ++i;
    }

  --i;
  while (i >= 0)
    {
      _dbus_hash_table_remove_string (table1,
                                      keys[i]);

      _dbus_hash_table_remove_int (table2, i);

      _dbus_hash_table_remove_uintptr (table3, i);

      _dbus_hash_table_remove_two_strings (table4,
                                           keys[i]);

      _dbus_assert (count_entries (table1) == i);
      _dbus_assert (count_entries (table2) == i);
      _dbus_assert (count_entries (table3) == i);
      _dbus_assert (count_entries (table4) == i);

      --i;
    }

  _dbus_hash_table_ref (table1);
  _dbus_hash_table_ref (table2);
  _dbus_hash_table_ref (table3);
  _dbus_hash_table_ref (table4);
  _dbus_hash_table_unref (table1);
  _dbus_hash_table_unref (table2);
  _dbus_hash_table_unref (table3);
  _dbus_hash_table_unref (table4);
  _dbus_hash_table_unref (table1);
  _dbus_hash_table_unref (table2);
  _dbus_hash_table_unref (table3);
  _dbus_hash_table_unref (table4);
  table3 = NULL;

  /* Insert a bunch of stuff then check
   * that iteration works correctly (finds the right
   * values, iter_set_value works, etc.)
   */
  table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
                                 dbus_free, dbus_free);
  if (table1 == NULL)
    goto out;

  table2 = _dbus_hash_table_new (DBUS_HASH_INT,
                                 NULL, dbus_free);
  if (table2 == NULL)
    goto out;

  i = 0;
  while (i < 5000)
    {
      char *key;
      void *value;

      key = _dbus_strdup (keys[i]);
      if (key == NULL)
        goto out;
      value = _dbus_strdup ("Value!");
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_string (table1,
                                           key, value))
        goto out;

      value = _dbus_strdup (keys[i]);
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_int (table2,
                                        i, value))
        goto out;

      _dbus_assert (count_entries (table1) == i + 1);
      _dbus_assert (count_entries (table2) == i + 1);

      ++i;
    }

  _dbus_hash_iter_init (table1, &iter);
  while (_dbus_hash_iter_next (&iter))
    {
      const char *key;
      void *value;

      key = _dbus_hash_iter_get_string_key (&iter);
      value = _dbus_hash_iter_get_value (&iter);

      _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);

      value = _dbus_strdup ("Different value!");
      if (value == NULL)
        goto out;

      _dbus_hash_iter_set_value (&iter, value);

      _dbus_assert (_dbus_hash_table_lookup_string (table1, key) == value);
    }

  _dbus_hash_iter_init (table1, &iter);
  while (_dbus_hash_iter_next (&iter))
    {
      _dbus_hash_iter_remove_entry (&iter);
      _dbus_assert (count_entries (table1) == i - 1);
      --i;
    }

  _dbus_hash_iter_init (table2, &iter);
  while (_dbus_hash_iter_next (&iter))
    {
      int key;
      void *value;

      key = _dbus_hash_iter_get_int_key (&iter);
      value = _dbus_hash_iter_get_value (&iter);

      _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);

      value = _dbus_strdup ("Different value!");
      if (value == NULL)
        goto out;

      _dbus_hash_iter_set_value (&iter, value);

      _dbus_assert (_dbus_hash_table_lookup_int (table2, key) == value);
    }

  i = count_entries (table2);
  _dbus_hash_iter_init (table2, &iter);
  while (_dbus_hash_iter_next (&iter))
    {
      _dbus_hash_iter_remove_entry (&iter);
      _dbus_assert (count_entries (table2) + 1 == i);
      --i;
    }

  /* add/remove interleaved, to check that we grow/shrink the table
   * appropriately
   */
  i = 0;
  while (i < 1000)
    {
      char *key;
      void *value;

      key = _dbus_strdup (keys[i]);
      if (key == NULL)
        goto out;

      value = _dbus_strdup ("Value!");
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_insert_string (table1,
                                           key, value))
        goto out;

      ++i;
    }

  --i;
  while (i >= 0)
    {
      char *key;
      void *value;

      key = _dbus_strdup (keys[i]);
      if (key == NULL)
        goto out;
      value = _dbus_strdup ("Value!");
      if (value == NULL)
        goto out;

      if (!_dbus_hash_table_remove_string (table1, keys[i]))
        goto out;

      if (!_dbus_hash_table_insert_string (table1,
                                           key, value))
        goto out;

      if (!_dbus_hash_table_remove_string (table1, keys[i]))
        goto out;

      _dbus_assert (_dbus_hash_table_get_n_entries (table1) == i);

      --i;
    }

  /* nuke these tables */
  _dbus_hash_table_unref (table1);
  _dbus_hash_table_unref (table2);


  /* Now do a bunch of things again using _dbus_hash_iter_lookup() to
   * be sure that interface works.
   */
  table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
                                 dbus_free, dbus_free);
  if (table1 == NULL)
    goto out;

  table2 = _dbus_hash_table_new (DBUS_HASH_INT,
                                 NULL, dbus_free);
  if (table2 == NULL)
    goto out;

  i = 0;
  while (i < 3000)
    {
      void *value;
      char *key;

      key = _dbus_strdup (keys[i]);
      if (key == NULL)
        goto out;
      value = _dbus_strdup ("Value!");
      if (value == NULL)
        goto out;

      if (!_dbus_hash_iter_lookup (table1,
                                   key, TRUE, &iter))
        goto out;
      _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
      _dbus_hash_iter_set_value (&iter, value);

      value = _dbus_strdup (keys[i]);
      if (value == NULL)
        goto out;

      if (!_dbus_hash_iter_lookup (table2,
                                   _DBUS_INT_TO_POINTER (i), TRUE, &iter))
        goto out;
      _dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
      _dbus_hash_iter_set_value (&iter, value);

      _dbus_assert (count_entries (table1) == i + 1);
      _dbus_assert (count_entries (table2) == i + 1);

      if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
        goto out;

      value = _dbus_hash_iter_get_value (&iter);
      _dbus_assert (value != NULL);
      _dbus_assert (strcmp (value, "Value!") == 0);

      /* Iterate just to be sure it works, though
       * it's a stupid thing to do
       */
      while (_dbus_hash_iter_next (&iter))
        ;

      if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
        goto out;

      value = _dbus_hash_iter_get_value (&iter);
      _dbus_assert (value != NULL);
      _dbus_assert (strcmp (value, keys[i]) == 0);

      /* Iterate just to be sure it works, though
       * it's a stupid thing to do
       */
      while (_dbus_hash_iter_next (&iter))
        ;

      ++i;
    }

  --i;
  while (i >= 0)
    {
      if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
        _dbus_assert_not_reached ("hash entry should have existed");
      _dbus_hash_iter_remove_entry (&iter);

      if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
        _dbus_assert_not_reached ("hash entry should have existed");
      _dbus_hash_iter_remove_entry (&iter);

      _dbus_assert (count_entries (table1) == i);
      _dbus_assert (count_entries (table2) == i);

      --i;
    }

  _dbus_hash_table_unref (table1);
  _dbus_hash_table_unref (table2);

  ret = TRUE;

 out:
  for (i = 0; i < N_HASH_KEYS; i++)
    dbus_free (keys[i]);

  dbus_free (keys);

  return ret;
}

#endif /* DBUS_BUILD_TESTS */