-/* -*- mode: C; c-file-style: "gnu" -*- */
-/* dbus-hash.c Generic hash table utility (internal to D-BUS implementation)
+/* -*- 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.
*
* 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
+ * code from tclHash.c; the Tcl license follows this standad D-Bus
* license information.
*
- * Licensed under the Academic Free License version 1.2
+ * 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
*
* 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
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
*/
/*
* 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
* 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)
+ (((((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 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.
*/
/**
* 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);
+typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
+ void *key,
+ dbus_bool_t create_if_not_found,
+ DBusHashEntry ***bucket,
+ DBusPreallocatedHash *preallocated);
/**
- * Hash table internal members. Hash tables are opaque objects,
- * they must be used via accessor functions.
+ * @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 */
int n_entries; /**< Total number of entries present
* in table.
*/
- int rebuild_size; /**< Enlarge table when numEntries gets
+ 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.
DBusFreeFunction free_key_function; /**< Function to free keys */
DBusFreeFunction free_value_function; /**< Function to free values */
+
+ DBusMemPool *entry_pool; /**< Memory pool for hash entries */
};
-/**
- * Internals of DBusHashIter.
+/**
+ * @brief Internals of DBusHashIter.
*/
typedef struct
{
int n_entries_on_init; /**< used to detect table resize since initialization */
} DBusRealHashIter;
-static DBusHashEntry* find_int_function (DBusHashTable *table,
- void *key,
- dbus_bool_t create_if_not_found,
- DBusHashEntry ***bucket);
-static DBusHashEntry* find_string_function (DBusHashTable *table,
- void *key,
- dbus_bool_t create_if_not_found,
- DBusHashEntry ***bucket);
-static unsigned int string_hash (const char *str);
-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);
+_DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
+
+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);
+static unsigned int string_hash (const char *str);
+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);
+
/** @} */
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->rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
+ 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:
- table->find_function = find_int_function;
+ case DBUS_HASH_UINTPTR:
+ table->find_function = find_direct_function;
break;
case DBUS_HASH_STRING:
table->find_function = find_string_function;
* Increments the reference count for a hash table.
*
* @param table the hash table to add a reference to.
+ * @returns the hash table.
*/
-void
+DBusHashTable *
_dbus_hash_table_ref (DBusHashTable *table)
{
table->refcount += 1;
+
+ return table;
}
/**
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];
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);
}
}
+/**
+ * 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_new0 (DBusHashEntry, 1);
-
+ entry = _dbus_mem_pool_alloc (table->entry_pool);
+
return entry;
}
static void
-free_entry (DBusHashTable *table,
- DBusHashEntry *entry)
+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);
-
- dbus_free (entry);
+}
+
+static void
+free_entry (DBusHashTable *table,
+ DBusHashEntry *entry)
+{
+ free_entry_data (table, entry);
+ _dbus_mem_pool_dealloc (table->entry_pool, entry);
}
static void
/**
* 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.
*/
* 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().
*
real = (DBusRealHashIter*) iter;
- entry = (* table->find_function) (table, key, create_if_not_found, &bucket);
+ entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
if (entry == NULL)
return FALSE;
return TRUE;
}
-static DBusHashEntry*
-add_entry (DBusHashTable *table,
- unsigned int idx,
- void *key,
- DBusHashEntry ***bucket)
+static void
+add_allocated_entry (DBusHashTable *table,
+ DBusHashEntry *entry,
+ unsigned int idx,
+ void *key,
+ DBusHashEntry ***bucket)
{
- DBusHashEntry *entry;
- DBusHashEntry **b;
-
- entry = alloc_entry (table);
- if (entry == NULL)
- {
- if (bucket)
- *bucket = NULL;
- return NULL;
- }
+ DBusHashEntry **b;
entry->key = key;
*bucket = b;
table->n_entries += 1;
-
- if (table->n_entries >= table->rebuild_size)
+
+ /* 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)
{
- register unsigned int result;
- register int c;
+ const char *p = str;
+ unsigned int h = *p;
- /*
- * I tried a zillion different hash functions and asked many other
- * people for advice. Many people had their own favorite functions,
- * all different, but no-one had much idea why they were good ones.
- * I chose the one below (multiply by 9 and add new character)
- * because of the following reasons:
- *
- * 1. Multiplying by 10 is perfect for keys that are decimal strings,
- * and multiplying by 9 is just about as good.
- * 2. Times-9 is (shift-left-3) plus (old). This means that each
- * character's bits hang around in the low-order bits of the
- * hash value for ever, plus they spread fairly rapidly up to
- * the high-order bits to fill out the hash value. This seems
- * works well both for decimal and non-decimal strings.
- */
+ if (h)
+ for (p += 1; *p != '\0'; p++)
+ h = (h << 5) - h + *p;
- result = 0;
- while (TRUE)
- {
- c = *str;
- str++;
- if (c == 0)
- break;
-
- result += (result << 3) + c;
- }
-
- return result;
+ return h;
}
+/** Key comparison function */
+typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
+
static DBusHashEntry*
-find_string_function (DBusHashTable *table,
- void *key,
- dbus_bool_t create_if_not_found,
- DBusHashEntry ***bucket)
+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;
- unsigned int idx;
if (bucket)
*bucket = NULL;
-
- idx = string_hash (key) & table->mask;
/* Search all of the entries in this bucket. */
entry = table->buckets[idx];
while (entry != NULL)
{
- if (strcmp (key, entry->key) == 0)
+ 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;
}
}
if (create_if_not_found)
- entry = add_entry (table, idx, key, bucket);
-
+ entry = add_entry (table, idx, key, bucket, preallocated);
+ else if (preallocated)
+ _dbus_hash_table_free_preallocated_entry (table, preallocated);
+
return entry;
}
static DBusHashEntry*
-find_int_function (DBusHashTable *table,
- void *key,
- dbus_bool_t create_if_not_found,
- DBusHashEntry ***bucket)
+find_string_function (DBusHashTable *table,
+ void *key,
+ dbus_bool_t create_if_not_found,
+ DBusHashEntry ***bucket,
+ DBusPreallocatedHash *preallocated)
{
- DBusHashEntry *entry;
unsigned int idx;
+
+ idx = string_hash (key) & table->mask;
- if (bucket)
- *bucket = NULL;
+ return find_generic_function (table, key, idx,
+ (KeyCompareFunc) strcmp, create_if_not_found, bucket,
+ preallocated);
+}
+
+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;
- /* Search all of the entries in this bucket. */
- entry = table->buckets[idx];
- while (entry != NULL)
- {
- if (key == entry->key)
- {
- if (bucket)
- *bucket = &(table->buckets[idx]);
- return entry;
- }
-
- entry = entry->next;
- }
- /* Entry not found. Add a new one to the bucket. */
- if (create_if_not_found)
- entry = add_entry (table, idx, key, bucket);
-
- return entry;
+ 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;
- table->n_buckets *= 4;
- table->buckets = dbus_new0 (DBusHashEntry*, table->n_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->n_buckets /= 4;
table->buckets = old_buckets;
return;
}
- table->rebuild_size *= 4;
- table->down_shift -= 2;
- table->mask = (table->mask << 2) + 3;
+ 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.
*/
idx = string_hash (entry->key) & table->mask;
break;
case DBUS_HASH_INT:
+ case DBUS_HASH_UINTPTR:
idx = RANDOM_INDEX (table, entry->key);
break;
default:
_dbus_assert_not_reached ("Unknown hash table type");
break;
}
-
+
bucket = &(table->buckets[idx]);
entry->next = *bucket;
*bucket = entry;
_dbus_assert (table->key_type == DBUS_HASH_STRING);
- entry = (* table->find_function) (table, (char*) key, FALSE, NULL);
+ entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
if (entry)
return entry->value;
_dbus_assert (table->key_type == DBUS_HASH_INT);
- entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL);
+ entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
+
+ if (entry)
+ return entry->value;
+ else
+ return NULL;
+}
+
+/**
+ * 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;
*
* @param table the hash table.
* @param key the hash key.
+ * @returns #TRUE if the entry existed
*/
-void
+dbus_bool_t
_dbus_hash_table_remove_string (DBusHashTable *table,
const char *key)
{
_dbus_assert (table->key_type == DBUS_HASH_STRING);
- entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
+ entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
if (entry)
- remove_entry (table, bucket, entry);
+ {
+ remove_entry (table, bucket, entry);
+ return TRUE;
+ }
+ else
+ return FALSE;
}
/**
*
* @param table the hash table.
* @param key the hash key.
+ * @returns #TRUE if the entry existed
*/
-void
+dbus_bool_t
_dbus_hash_table_remove_int (DBusHashTable *table,
int key)
{
_dbus_assert (table->key_type == DBUS_HASH_INT);
- entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
+ entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
if (entry)
- remove_entry (table, bucket, entry);
+ {
+ remove_entry (table, bucket, entry);
+ return TRUE;
+ }
+ else
+ return FALSE;
+}
+
+/**
+ * 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;
}
/**
char *key,
void *value)
{
- DBusHashEntry *entry;
+ 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;
+}
+
+/**
+ * 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, key, TRUE, NULL);
+ 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 != key)
+ 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 = key;
+
+ entry->key = _DBUS_INT_TO_POINTER (key);
entry->value = value;
return TRUE;
* @param value the hash entry value.
*/
dbus_bool_t
-_dbus_hash_table_insert_int (DBusHashTable *table,
- int key,
- void *value)
+_dbus_hash_table_insert_uintptr (DBusHashTable *table,
+ uintptr_t key,
+ void *value)
{
DBusHashEntry *entry;
- _dbus_assert (table->key_type == DBUS_HASH_INT);
+ _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
- entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL);
+ entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
if (entry == NULL)
return FALSE; /* no memory */
- if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
+ 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 = _DBUS_INT_TO_POINTER (key);
+ 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.
/** @} */
-#ifdef DBUS_BUILD_TESTS
+#ifdef DBUS_ENABLE_EMBEDDED_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)
{
int i;
DBusHashTable *table1;
DBusHashTable *table2;
+ DBusHashTable *table3;
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;
+
+ len = sprintf (keys[i], "Hash key %d", i);
+ _dbus_assert (*(keys[i] + len) == '\0');
+ ++i;
+ }
+ printf ("... done.\n");
table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
dbus_free, dbus_free);
if (table1 == NULL)
- return FALSE;
+ goto out;
table2 = _dbus_hash_table_new (DBUS_HASH_INT,
NULL, dbus_free);
if (table2 == NULL)
- return FALSE;
+ goto out;
+
+ table3 = _dbus_hash_table_new (DBUS_HASH_UINTPTR,
+ NULL, dbus_free);
+ if (table3 == 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)
{
- char buf[256];
- sprintf (buf, "Hash key %d", i);
void *value;
char *key;
- key = _dbus_strdup (buf);
+ key = _dbus_strdup (keys[i]);
if (key == NULL)
- return FALSE;
+ goto out;
value = _dbus_strdup ("Value!");
if (value == NULL)
- return FALSE;
+ goto out;
if (!_dbus_hash_table_insert_string (table1,
key, value))
- return FALSE;
+ goto out;
- value = _dbus_strdup (buf);
+ value = _dbus_strdup (keys[i]);
if (value == NULL)
- return FALSE;
+ goto out;
if (!_dbus_hash_table_insert_int (table2,
i, value))
- return FALSE;
+ goto out;
+
+ value = _dbus_strdup (keys[i]);
+ if (value == NULL)
+ goto out;
+ if (!_dbus_hash_table_insert_uintptr (table3,
+ i, value))
+ goto out;
+
_dbus_assert (count_entries (table1) == i + 1);
_dbus_assert (count_entries (table2) == i + 1);
+ _dbus_assert (count_entries (table3) == i + 1);
- value = _dbus_hash_table_lookup_string (table1, buf);
+ 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, buf) == 0);
-
+ _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);
+
++i;
}
--i;
while (i >= 0)
{
- char buf[256];
- sprintf (buf, "Hash key %d", i);
-
_dbus_hash_table_remove_string (table1,
- buf);
+ keys[i]);
_dbus_hash_table_remove_int (table2, i);
+ _dbus_hash_table_remove_uintptr (table3, i);
+
_dbus_assert (count_entries (table1) == i);
_dbus_assert (count_entries (table2) == i);
+ _dbus_assert (count_entries (table3) == i);
--i;
}
_dbus_hash_table_ref (table1);
_dbus_hash_table_ref (table2);
+ _dbus_hash_table_ref (table3);
_dbus_hash_table_unref (table1);
_dbus_hash_table_unref (table2);
+ _dbus_hash_table_unref (table3);
_dbus_hash_table_unref (table1);
_dbus_hash_table_unref (table2);
-
+ _dbus_hash_table_unref (table3);
+ table3 = NULL;
/* Insert a bunch of stuff then check
* that iteration works correctly (finds the right
table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
dbus_free, dbus_free);
if (table1 == NULL)
- return FALSE;
+ goto out;
table2 = _dbus_hash_table_new (DBUS_HASH_INT,
NULL, dbus_free);
if (table2 == NULL)
- return FALSE;
+ goto out;
i = 0;
while (i < 5000)
{
- char buf[256];
- sprintf (buf, "Hash key %d", i);
char *key;
void *value;
- key = _dbus_strdup (buf);
+ key = _dbus_strdup (keys[i]);
if (key == NULL)
- return FALSE;
+ goto out;
value = _dbus_strdup ("Value!");
if (value == NULL)
- return FALSE;
+ goto out;
if (!_dbus_hash_table_insert_string (table1,
key, value))
- return FALSE;
+ goto out;
- value = _dbus_strdup (buf);
+ value = _dbus_strdup (keys[i]);
if (value == NULL)
- return FALSE;
+ goto out;
if (!_dbus_hash_table_insert_int (table2,
i, value))
- return FALSE;
+ goto out;
_dbus_assert (count_entries (table1) == i + 1);
_dbus_assert (count_entries (table2) == i + 1);
value = _dbus_strdup ("Different value!");
if (value == NULL)
- return FALSE;
+ goto out;
_dbus_hash_iter_set_value (&iter, value);
value = _dbus_strdup ("Different value!");
if (value == NULL)
- return FALSE;
+ goto out;
_dbus_hash_iter_set_value (&iter, value);
_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);
table1 = _dbus_hash_table_new (DBUS_HASH_STRING,
dbus_free, dbus_free);
if (table1 == NULL)
- return FALSE;
+ goto out;
table2 = _dbus_hash_table_new (DBUS_HASH_INT,
NULL, dbus_free);
if (table2 == NULL)
- return FALSE;
+ goto out;
i = 0;
while (i < 3000)
{
- char buf[256];
- sprintf (buf, "Hash key %d", i);
void *value;
char *key;
- key = _dbus_strdup (buf);
+ key = _dbus_strdup (keys[i]);
if (key == NULL)
- return FALSE;
+ goto out;
value = _dbus_strdup ("Value!");
if (value == NULL)
- return FALSE;
+ goto out;
if (!_dbus_hash_iter_lookup (table1,
key, TRUE, &iter))
- return FALSE;
+ goto out;
_dbus_assert (_dbus_hash_iter_get_value (&iter) == NULL);
_dbus_hash_iter_set_value (&iter, value);
- value = _dbus_strdup (buf);
+ value = _dbus_strdup (keys[i]);
if (value == NULL)
- return FALSE;
+ goto out;
if (!_dbus_hash_iter_lookup (table2,
_DBUS_INT_TO_POINTER (i), TRUE, &iter))
- return FALSE;
+ 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, buf, FALSE, &iter))
- return FALSE;
+ if (!_dbus_hash_iter_lookup (table1, keys[i], FALSE, &iter))
+ goto out;
value = _dbus_hash_iter_get_value (&iter);
_dbus_assert (value != NULL);
;
if (!_dbus_hash_iter_lookup (table2, _DBUS_INT_TO_POINTER (i), FALSE, &iter))
- return FALSE;
+ goto out;
value = _dbus_hash_iter_get_value (&iter);
_dbus_assert (value != NULL);
- _dbus_assert (strcmp (value, buf) == 0);
+ _dbus_assert (strcmp (value, keys[i]) == 0);
/* Iterate just to be sure it works, though
* it's a stupid thing to do
--i;
while (i >= 0)
{
- char buf[256];
- sprintf (buf, "Hash key %d", i);
-
- if (!_dbus_hash_iter_lookup (table1, buf, FALSE, &iter))
+ 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);
_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 TRUE;
+ return ret;
}
-#endif
+#endif /* DBUS_ENABLE_EMBEDDED_TESTS */
projects / platform / upstream / dbus.git / blobdiff