78 #include "dbus-hash.h"
79 #include "dbus-internals.h"
80 #include "dbus-mempool.h"
104 #define REBUILD_MULTIPLIER 3
122 #define RANDOM_INDEX(table, i) \
123 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
130 #define DBUS_SMALL_HASH_TABLE 4
235 #ifdef DBUS_BUILD_TESTS
242 static unsigned int string_hash (
const char *str);
243 #ifdef DBUS_BUILD_TESTS
244 static unsigned int two_strings_hash (
const char *str);
305 if (entry_pool ==
NULL)
338 #ifdef DBUS_BUILD_TESTS
390 while (entry !=
NULL)
394 free_entry (table, entry);
407 while (entry !=
NULL)
409 free_entry_data (table, entry);
466 free_entry_data (table, entry);
480 if (*bucket == entry)
481 *bucket = entry->
next;
487 while (prev->
next != entry)
496 free_entry (table, entry);
701 return (uintptr_t) real->
entry->
key;
722 #ifdef DBUS_BUILD_TESTS
729 _dbus_hash_iter_get_two_strings_key (
DBusHashIter *iter)
787 entry = (* table->
find_function) (table, key, create_if_not_found, &bucket,
NULL);
829 rebuild_table (table);
841 if (preallocated ==
NULL)
843 entry = alloc_entry (table);
856 add_allocated_entry (table, entry, idx, key, bucket);
865 string_hash (
const char *str)
871 for (p += 1; *p !=
'\0'; p++)
872 h = (h << 5) - h + *p;
877 #ifdef DBUS_BUILD_TESTS
882 two_strings_hash (
const char *str)
888 for (p += 1; *p !=
'\0'; p++)
889 h = (h << 5) - h + *p;
891 for (p += 1; *p !=
'\0'; p++)
892 h = (h << 5) - h + *p;
917 while (entry !=
NULL)
919 if ((compare_func ==
NULL && key == entry->
key) ||
920 (compare_func !=
NULL && (* compare_func) (key, entry->
key) == 0))
923 *bucket = &(table->
buckets[idx]);
934 if (create_if_not_found)
935 entry = add_entry (table, idx, key, bucket, preallocated);
936 else if (preallocated)
951 idx = string_hash (key) & table->
mask;
953 return find_generic_function (table, key, idx,
958 #ifdef DBUS_BUILD_TESTS
960 two_strings_cmp (
const char *a,
974 return strcmp (a + len_a + 1, b + len_b + 1);
978 #ifdef DBUS_BUILD_TESTS
988 idx = two_strings_hash (key) & table->
mask;
990 return find_generic_function (table, key, idx,
1008 return find_generic_function (table, key, idx,
1009 NULL, create_if_not_found, bucket,
1067 table->
mask = (table->
mask << 2) + 3;
1079 printf (
"%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
1080 growing ?
"GROW" :
"SHRINK",
1097 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1099 for (entry = *old_chain; entry !=
NULL; entry = *old_chain)
1104 *old_chain = entry->
next;
1108 idx = string_hash (entry->
key) & table->
mask;
1111 #ifdef DBUS_BUILD_TESTS
1112 idx = two_strings_hash (entry->
key) & table->
mask;
1129 bucket = &(table->
buckets[idx]);
1130 entry->
next = *bucket;
1161 return entry->
value;
1166 #ifdef DBUS_BUILD_TESTS
1187 return entry->
value;
1213 return entry->
value;
1218 #ifdef DBUS_BUILD_TESTS
1237 entry = (* table->
find_function) (table, key, FALSE, NULL, NULL);
1240 return entry->
value;
1266 return entry->
value;
1292 remove_entry (table, bucket, entry);
1299 #ifdef DBUS_BUILD_TESTS
1321 remove_entry (table, bucket, entry);
1350 remove_entry (table, bucket, entry);
1357 #ifdef DBUS_BUILD_TESTS
1376 entry = (* table->
find_function) (table, key, FALSE, &bucket, NULL);
1380 remove_entry (table, bucket, entry);
1409 remove_entry (table, bucket, entry);
1441 if (preallocated == NULL)
1450 #ifdef DBUS_BUILD_TESTS
1487 entry->
value = value;
1529 entry->
value = value;
1534 #ifdef DBUS_BUILD_TESTS
1572 entry->
value = value;
1613 entry->
key = (
void*) key;
1614 entry->
value = value;
1631 entry = alloc_entry (table);
1692 entry->
value = value;
1709 #ifdef DBUS_BUILD_TESTS
1710 #include "dbus-test.h"
1735 _dbus_strdup2 (
const char *str)
1744 len += strlen ((str + len + 1));
1750 memcpy (copy, str, len + 2);
1761 _dbus_hash_test (
void)
1769 #define N_HASH_KEYS 5000
1773 keys =
dbus_new (
char *, N_HASH_KEYS);
1777 for (i = 0; i < N_HASH_KEYS; i++)
1781 if (keys[i] == NULL)
1785 printf (
"Computing test hash keys...\n");
1787 while (i < N_HASH_KEYS)
1795 len = sprintf (keys[i],
"Hash key %d", i);
1796 sprintf (keys[i] + len + 1,
"Two string %d", i);
1801 printf (
"... done.\n");
1860 key = _dbus_strdup2 (keys[i]);
1867 if (!_dbus_hash_table_insert_two_strings (table4,
1888 value = _dbus_hash_table_lookup_two_strings (table4, keys[i]);
1905 _dbus_hash_table_remove_two_strings (table4,
2023 i = count_entries (table2);
2186 for (i = 0; i < N_HASH_KEYS; i++)