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
237 static unsigned int string_hash (
const char *str);
297 if (entry_pool ==
NULL)
376 while (entry !=
NULL)
380 free_entry (table, entry);
393 while (entry !=
NULL)
395 free_entry_data (table, entry);
452 free_entry_data (table, entry);
466 if (*bucket == entry)
467 *bucket = entry->
next;
473 while (prev->
next != entry)
482 free_entry (table, entry);
687 return (uintptr_t) real->
entry->
key;
754 entry = (* table->
find_function) (table, key, create_if_not_found, &bucket,
NULL);
759 if (create_if_not_found)
804 rebuild_table (table);
816 if (preallocated ==
NULL)
818 entry = alloc_entry (table);
831 add_allocated_entry (table, entry, idx, key, bucket);
840 string_hash (
const char *str)
846 for (p += 1; *p !=
'\0'; p++)
847 h = (h << 5) - h + *p;
871 while (entry !=
NULL)
873 if ((compare_func ==
NULL && key == entry->
key) ||
874 (compare_func !=
NULL && (* compare_func) (key, entry->
key) == 0))
877 *bucket = &(table->
buckets[idx]);
888 if (create_if_not_found)
889 entry = add_entry (table, idx, key, bucket, preallocated);
890 else if (preallocated)
905 idx = string_hash (key) & table->
mask;
907 return find_generic_function (table, key, idx,
924 return find_generic_function (table, key, idx,
925 NULL, create_if_not_found, bucket,
983 table->
mask = (table->
mask << 2) + 3;
995 printf (
"%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
996 growing ?
"GROW" :
"SHRINK",
1014 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1016 for (entry = *old_chain; entry !=
NULL; entry = *old_chain)
1021 *old_chain = entry->
next;
1025 idx = string_hash (entry->
key) & table->
mask;
1037 bucket = &(table->
buckets[idx]);
1038 entry->
next = *bucket;
1069 return entry->
value;
1094 return entry->
value;
1119 return entry->
value;
1145 remove_entry (table, bucket, entry);
1173 remove_entry (table, bucket, entry);
1201 remove_entry (table, bucket, entry);
1233 if (preallocated ==
NULL)
1278 entry->
value = value;
1318 entry->
key = (
void*) key;
1319 entry->
value = value;
1336 entry = alloc_entry (table);
1397 entry->
value = value;
1446 for (i = 0; array[i] !=
NULL; i++)
1453 char *hash_key, *hash_value;
1462 hash_key, hash_value))
1469 if (array[i] !=
NULL)
1517 const char *key, *value;
1543 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1544 #include "dbus-test.h"
1567 static inline void *
1571 void **_ptr = (
void **) ptr;
1586 _dbus_hash_test (
void)
1593 #define N_HASH_KEYS 5000
1596 char *str_key =
NULL;
1597 char *str_value =
NULL;
1599 keys =
dbus_new (
char *, N_HASH_KEYS);
1603 for (i = 0; i < N_HASH_KEYS; i++)
1607 if (keys[i] ==
NULL)
1611 printf (
"Computing test hash keys...\n");
1613 while (i < N_HASH_KEYS)
1617 len = sprintf (keys[i],
"Hash key %d", i);
1621 printf (
"... done.\n");
1644 const void *out_value;
1647 if (str_key ==
NULL)
1650 if (str_value ==
NULL)
1655 steal (&str_value)))
1659 if (str_value ==
NULL)
1663 i, steal (&str_value)))
1667 if (str_value ==
NULL)
1671 i, steal (&str_value)))
1739 if (str_key ==
NULL)
1742 if (str_value ==
NULL)
1747 steal (&str_value)))
1751 if (str_value ==
NULL)
1755 i, steal (&str_value)))
1776 if (str_value ==
NULL)
1804 if (str_value ==
NULL)
1812 i = count_entries (table2);
1828 if (str_key ==
NULL)
1832 if (str_value ==
NULL)
1837 steal (&str_value)))
1847 if (str_key ==
NULL)
1850 if (str_value ==
NULL)
1858 steal (&str_value)))
1890 const void *out_value;
1893 if (str_key ==
NULL)
1896 if (str_value ==
NULL)
1900 steal (&str_key),
TRUE, &iter))
1906 if (str_value ==
NULL)
1970 for (i = 0; i < N_HASH_KEYS; i++)