-/* -*- 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"
*
*/
#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
int n_entries_on_init; /**< used to detect table resize since initialization */
} DBusRealHashIter;
+_DBUS_STATIC_ASSERT (sizeof (DBusRealHashIter) == sizeof (DBusHashIter));
+
static DBusHashEntry* find_direct_function (DBusHashTable *table,
void *key,
dbus_bool_t create_if_not_found,
dbus_bool_t create_if_not_found,
DBusHashEntry ***bucket,
DBusPreallocatedHash *preallocated);
-static DBusHashEntry* find_two_strings_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 unsigned int two_strings_hash (const char *str);
static void rebuild_table (DBusHashTable *table);
static DBusHashEntry* alloc_entry (DBusHashTable *table);
static void remove_entry (DBusHashTable *table,
switch (table->key_type)
{
case DBUS_HASH_INT:
- case DBUS_HASH_POINTER:
- case DBUS_HASH_ULONG:
+ 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:
- table->find_function = find_two_strings_function;
- break;
default:
_dbus_assert_not_reached ("Unknown hash table type");
break;
* 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;
}
/**
}
}
+/**
+ * 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)
{
/**
* Gets the key for the current entry.
- * Only works for hash tables of type #DBUS_HASH_ULONG.
+ * Only works for hash tables of type #DBUS_HASH_UINTPTR.
*
* @param iter the hash table iterator.
*/
-unsigned long
-_dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
+uintptr_t
+_dbus_hash_iter_get_uintptr_key (DBusHashIter *iter)
{
DBusRealHashIter *real;
_dbus_assert (real->table != NULL);
_dbus_assert (real->entry != NULL);
- return (unsigned long) real->entry->key;
+ return (uintptr_t) real->entry->key;
}
/**
}
/**
- * 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;
-}
-
-/**
* 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
return h;
}
-/* 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;
-}
-
+/** Key comparison function */
typedef int (* KeyCompareFunc) (const void *key_a, const void *key_b);
static DBusHashEntry*
preallocated);
}
-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);
-}
-
-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);
-}
-
static DBusHashEntry*
find_direct_function (DBusHashTable *table,
void *key,
case DBUS_HASH_STRING:
idx = string_hash (entry->key) & table->mask;
break;
- case DBUS_HASH_TWO_STRINGS:
- idx = two_strings_hash (entry->key) & table->mask;
- break;
case DBUS_HASH_INT:
- case DBUS_HASH_ULONG:
- case DBUS_HASH_POINTER:
+ case DBUS_HASH_UINTPTR:
idx = RANDOM_INDEX (table, entry->key);
break;
default:
}
/**
- * 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;
-}
-
-/**
* 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
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
+ * 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.
* @returns the value of the hash entry.
*/
void*
-_dbus_hash_table_lookup_ulong (DBusHashTable *table,
- unsigned long key)
+_dbus_hash_table_lookup_uintptr (DBusHashTable *table,
+ uintptr_t key)
{
DBusHashEntry *entry;
- _dbus_assert (table->key_type == DBUS_HASH_ULONG);
+ _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
* @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;
-}
-
-/**
- * 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)
{
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.
* @returns #TRUE if the entry existed
*/
dbus_bool_t
-_dbus_hash_table_remove_pointer (DBusHashTable *table,
- void *key)
+_dbus_hash_table_remove_uintptr (DBusHashTable *table,
+ uintptr_t 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);
+ _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
* @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;
-}
-
-/**
- * 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)
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
* @param value the hash entry value.
*/
dbus_bool_t
-_dbus_hash_table_insert_pointer (DBusHashTable *table,
- void *key,
+_dbus_hash_table_insert_uintptr (DBusHashTable *table,
+ uintptr_t 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);
+ _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
/** @} */
-#ifdef DBUS_BUILD_TESTS
+#ifdef DBUS_ENABLE_EMBEDDED_TESTS
#include "dbus-test.h"
#include <stdio.h>
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
DBusHashTable *table1;
DBusHashTable *table2;
DBusHashTable *table3;
- DBusHashTable *table4;
DBusHashIter iter;
#define N_HASH_KEYS 5000
char **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");
if (table2 == NULL)
goto out;
- table3 = _dbus_hash_table_new (DBUS_HASH_ULONG,
+ 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
*/
if (value == NULL)
goto out;
- if (!_dbus_hash_table_insert_ulong (table3,
+ 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 (value != NULL);
_dbus_assert (strcmp (value, keys[i]) == 0);
- value = _dbus_hash_table_lookup_ulong (table3, i);
+ 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;
}
_dbus_hash_table_remove_int (table2, i);
- _dbus_hash_table_remove_ulong (table3, 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
return ret;
}
-#endif /* DBUS_BUILD_TESTS */
+#endif /* DBUS_ENABLE_EMBEDDED_TESTS */
projects / platform / upstream / dbus.git / blobdiff