--- /dev/null
+/* -*- 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 "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) \
+ (((((long) (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_ULONG:
+ 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_ULONG.
+ *
+ * @param iter the hash table iterator.
+ */
+unsigned long
+_dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
+{
+ DBusRealHashIter *real;
+
+ real = (DBusRealHashIter*) iter;
+
+ _dbus_assert (real->table != NULL);
+ _dbus_assert (real->entry != NULL);
+
+ return (unsigned long) 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_ULONG:
+ 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_ULONG. 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_ulong (DBusHashTable *table,
+ unsigned long key)
+{
+ DBusHashEntry *entry;
+
+ _dbus_assert (table->key_type == DBUS_HASH_ULONG);
+
+ 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_ulong (DBusHashTable *table,
+ unsigned long key)
+{
+ DBusHashEntry *entry;
+ DBusHashEntry **bucket;
+
+ _dbus_assert (table->key_type == DBUS_HASH_ULONG);
+
+ 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_ulong (DBusHashTable *table,
+ unsigned long key,
+ void *value)
+{
+ DBusHashEntry *entry;
+
+ _dbus_assert (table->key_type == DBUS_HASH_ULONG);
+
+ 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_ULONG,
+ 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_ulong (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_ulong (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_ulong (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 */
projects / monky / blobdiff