summaryrefslogtreecommitdiffstats
path: root/dbus/dbus-hash.c
diff options
context:
space:
mode:
authorHavoc Pennington <hp@redhat.com>2003-08-18 15:27:33 +0000
committerHavoc Pennington <hp@redhat.com>2003-08-18 15:27:33 +0000
commit95717a938b237d12211935f6a7467ef610288fe5 (patch)
tree9182521c86f31e74ad642eb19b431a433859c85f /dbus/dbus-hash.c
parent7c3693a53b4eba0db1aebe1edab5ded21eb7757f (diff)
2003-08-17 Havoc Pennington <hp@pobox.com>
This doesn't compile yet, but syncing up so I can hack on it from work. What are branches for if not broken code? ;-) * dbus/dbus-protocol.h: remove DBUS_HEADER_FIELD_NAME, add DBUS_HEADER_FIELD_INTERFACE, DBUS_HEADER_FIELD_MEMBER, DBUS_HEADER_FIELD_ERROR_NAME * dbus/dbus-hash.c: Introduce DBUS_HASH_TWO_STRINGS as hack to use for the interface+member pairs (string_hash): change to use g_str_hash algorithm (find_direct_function, find_string_function): refactor these to share most code. * dbus/dbus-message.c: port all of this over to support interface/member fields instead of name field * dbus/dbus-object-registry.c: port over * dbus/dbus-string.c (_dbus_string_validate_interface): rename from _dbus_string_validate_name * bus/dbus-daemon-1.1: change file format for the <deny>/<allow> stuff to match new message naming scheme * bus/policy.c: port over * bus/config-parser.c: parse new format
Diffstat (limited to 'dbus/dbus-hash.c')
-rw-r--r--dbus/dbus-hash.c378
1 files changed, 290 insertions, 88 deletions
diff --git a/dbus/dbus-hash.c b/dbus/dbus-hash.c
index 2c410010..f4547815 100644
--- a/dbus/dbus-hash.c
+++ b/dbus/dbus-hash.c
@@ -221,26 +221,32 @@ typedef struct
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);
-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);
+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 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,
+ DBusHashEntry **bucket,
+ DBusHashEntry *entry);
+static void free_entry (DBusHashTable *table,
+ DBusHashEntry *entry);
+static void free_entry_data (DBusHashTable *table,
+ DBusHashEntry *entry);
/** @} */
@@ -323,6 +329,9 @@ _dbus_hash_table_new (DBusHashType type,
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;
@@ -685,6 +694,24 @@ _dbus_hash_iter_get_string_key (DBusHashIter *iter)
}
/**
+ * 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
@@ -803,64 +830,63 @@ add_entry (DBusHashTable *table,
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;
- /* FIXME the hash function in GLib is better than this one */
-
- result = 0;
- while (TRUE)
- {
- c = *str;
- str++;
- if (c == 0)
- break;
-
- result += (result << 3) + c;
- }
+ 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 result;
+ return h;
}
+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,
- DBusPreallocatedHash *preallocated)
+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]);
@@ -878,50 +904,75 @@ find_string_function (DBusHashTable *table,
entry = add_entry (table, idx, key, bucket, preallocated);
else if (preallocated)
_dbus_hash_table_free_preallocated_entry (table, preallocated);
-
+
return entry;
}
static DBusHashEntry*
-find_direct_function (DBusHashTable *table,
+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 int
+two_strings_cmp (const char *a,
+ const char *b)
+{
+ size_t len_a;
+ size_t len_b;
+ int res;
- idx = RANDOM_INDEX (table, key) & table->mask;
+ res = strcmp (a, b);
+ if (res != 0)
+ return res;
- /* 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]);
+ len_a = strlen (a);
+ len_b = strlen (b);
- if (preallocated)
- _dbus_hash_table_free_preallocated_entry (table, preallocated);
-
- return entry;
- }
-
- entry = entry->next;
- }
+ return strcmp (a + len_a + 1, b + len_b + 1);
+}
- /* Entry not found. Add a new one to the bucket. */
- if (create_if_not_found)
- entry = add_entry (table, idx, key, bucket, preallocated);
- else if (preallocated)
- _dbus_hash_table_free_preallocated_entry (table, preallocated);
+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 entry;
+ 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,
+ 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
@@ -1021,6 +1072,9 @@ rebuild_table (DBusHashTable *table)
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:
@@ -1070,6 +1124,31 @@ _dbus_hash_table_lookup_string (DBusHashTable *table,
}
/**
+ * 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
@@ -1184,6 +1263,34 @@ _dbus_hash_table_remove_string (DBusHashTable *table,
* @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)
{
@@ -1312,6 +1419,40 @@ _dbus_hash_table_insert_string (DBusHashTable *table,
* @param value the hash entry value.
*/
dbus_bool_t
+_dbus_hash_table_insert_two_strings (DBusHashTable *table,
+ char *key,
+ void *value)
+{
+ DBusPreallocatedHash *preallocated;
+
+ _dbus_assert (table->key_type == DBUS_HASH_TWO_STRINGS);
+
+ 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)
@@ -1536,6 +1677,28 @@ count_entries (DBusHashTable *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
@@ -1548,6 +1711,7 @@ _dbus_hash_test (void)
DBusHashTable *table1;
DBusHashTable *table2;
DBusHashTable *table3;
+ DBusHashTable *table4;
DBusHashIter iter;
#define N_HASH_KEYS 5000
char **keys;
@@ -1569,7 +1733,16 @@ _dbus_hash_test (void)
i = 0;
while (i < N_HASH_KEYS)
{
- sprintf (keys[i], "Hash key %d", i);
+ 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");
@@ -1588,6 +1761,12 @@ _dbus_hash_test (void)
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
@@ -1624,10 +1803,22 @@ _dbus_hash_test (void)
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_string (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);
@@ -1640,6 +1831,10 @@ _dbus_hash_test (void)
value = _dbus_hash_table_lookup_ulong (table3, i);
_dbus_assert (value != NULL);
_dbus_assert (strcmp (value, keys[i]) == 0);
+
+ value = _dbus_hash_table_lookup_ulong (table4, i);
+ _dbus_assert (value != NULL);
+ _dbus_assert (strcmp (value, keys[i]) == 0);
++i;
}
@@ -1654,9 +1849,13 @@ _dbus_hash_test (void)
_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;
}
@@ -1664,12 +1863,15 @@ _dbus_hash_test (void)
_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