85#include "dbus-internals.h"
86#include "dbus-mempool.h"
87#include <dbus/dbus-test-tap.h>
111#define REBUILD_MULTIPLIER 3
129#define RANDOM_INDEX(table, i) \
130 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
137#define DBUS_SMALL_HASH_TABLE 4
165 dbus_bool_t create_if_not_found,
236 dbus_bool_t create_if_not_found,
241 dbus_bool_t create_if_not_found,
244static unsigned int string_hash (
const char *str);
304 if (entry_pool ==
NULL)
383 while (entry !=
NULL)
387 free_entry (table, entry);
400 while (entry !=
NULL)
402 free_entry_data (table, entry);
459 free_entry_data (table, entry);
473 if (*bucket == entry)
474 *bucket = entry->
next;
480 while (prev->
next != entry)
489 free_entry (table, entry);
694 return (uintptr_t) real->
entry->
key;
750 dbus_bool_t create_if_not_found,
761 entry = (* table->
find_function) (table, key, create_if_not_found, &bucket,
NULL);
772 if (create_if_not_found)
820 if (!rebuild_table (table))
829 idx = string_hash (entry->
key) & table->
mask;
843 *bucket = &(table->
buckets[idx]);
857 if (preallocated ==
NULL)
859 entry = alloc_entry (table);
872 add_allocated_entry (table, entry, idx, key, bucket);
882string_hash (
const char *str)
888 for (p += 1; *p !=
'\0'; p++)
889 h = (h << 5) - h + *p;
902 dbus_bool_t create_if_not_found,
913 while (entry !=
NULL)
915 if ((compare_func ==
NULL && key == entry->
key) ||
916 (compare_func !=
NULL && (* compare_func) (key, entry->
key) == 0))
919 *bucket = &(table->
buckets[idx]);
930 if (create_if_not_found)
932 entry = add_entry (table, idx, key, bucket, preallocated);
939 else if (preallocated)
950 dbus_bool_t create_if_not_found,
956 idx = string_hash (key) & table->
mask;
958 return find_generic_function (table, key, idx,
966 dbus_bool_t create_if_not_found,
975 return find_generic_function (table, key, idx,
976 NULL, create_if_not_found, bucket,
1035 table->
mask = (table->
mask << 2) + 3;
1047 printf (
"%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
1048 growing ?
"GROW" :
"SHRINK",
1049 table->lo_rebuild_size,
1050 table->hi_rebuild_size,
1066 for (old_chain = old_buckets; old_size > 0; old_size--, old_chain++)
1068 for (entry = *old_chain; entry !=
NULL; entry = *old_chain)
1073 *old_chain = entry->
next;
1077 idx = string_hash (entry->
key) & table->
mask;
1089 bucket = &(table->
buckets[idx]);
1090 entry->
next = *bucket;
1123 return entry->
value;
1148 return entry->
value;
1173 return entry->
value;
1199 remove_entry (table, bucket, entry);
1227 remove_entry (table, bucket, entry);
1255 remove_entry (table, bucket, entry);
1287 if (preallocated ==
NULL)
1332 entry->
value = value;
1372 entry->
key = (
void*) key;
1373 entry->
value = value;
1390 entry = alloc_entry (table);
1451 entry->
value = value;
1484 dbus_bool_t retval =
FALSE;
1500 for (i = 0; array[i] !=
NULL; i++)
1507 char *hash_key, *hash_value;
1516 hash_key, hash_value))
1523 if (array[i] !=
NULL)
1571 const char *key, *value;
#define DBUS_SMALL_HASH_TABLE
Initial number of buckets in hash table (hash table statically allocates its buckets for this size an...
#define REBUILD_MULTIPLIER
When there are this many entries per bucket, on average, rebuild the hash table to make it larger.
#define RANDOM_INDEX(table, i)
Takes a preliminary integer hash value and produces an index into a hash tables bucket list.
DBusHashEntry *(* DBusFindEntryFunction)(DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashEntry ***bucket, DBusPreallocatedHash *preallocated)
Function used to find and optionally create a hash entry.
int _dbus_hash_table_get_n_entries(DBusHashTable *table)
Gets the number of hash entries in a hash table.
DBusHashTable * _dbus_hash_table_ref(DBusHashTable *table)
Increments the reference count for a hash table.
dbus_bool_t _dbus_hash_table_remove_uintptr(DBusHashTable *table, uintptr_t key)
Removes the hash entry for the given key.
void * _dbus_hash_iter_get_value(DBusHashIter *iter)
Gets the value of the current entry.
struct DBusPreallocatedHash DBusPreallocatedHash
A preallocated hash entry.
dbus_bool_t _dbus_hash_table_insert_int(DBusHashTable *table, int key, void *value)
Creates a hash entry with the given key and value.
dbus_bool_t _dbus_hash_table_insert_string(DBusHashTable *table, char *key, void *value)
Creates a hash entry with the given key and value.
dbus_bool_t _dbus_hash_table_from_array(DBusHashTable *table, char **array, char delimiter)
Imports a string array into a hash table The hash table needs to be initialized with string keys,...
uintptr_t _dbus_hash_iter_get_uintptr_key(DBusHashIter *iter)
Gets the key for the current entry.
void * _dbus_hash_table_lookup_uintptr(DBusHashTable *table, uintptr_t key)
Looks up the value for a given integer in a hash table of type DBUS_HASH_UINTPTR.
void _dbus_hash_table_unref(DBusHashTable *table)
Decrements the reference count for a hash table, freeing the hash table if the count reaches zero.
int(* KeyCompareFunc)(const void *key_a, const void *key_b)
Key comparison function.
dbus_bool_t _dbus_hash_iter_next(DBusHashIter *iter)
Move the hash iterator forward one step, to the next hash entry.
int _dbus_hash_iter_get_int_key(DBusHashIter *iter)
Gets the key for the current entry.
void _dbus_hash_iter_init(DBusHashTable *table, DBusHashIter *iter)
Initializes a hash table iterator.
void _dbus_hash_table_free_preallocated_entry(DBusHashTable *table, DBusPreallocatedHash *preallocated)
Frees an opaque DBusPreallocatedHash that was not used in order to insert into the hash table.
DBusHashTable * _dbus_hash_table_new(DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function)
Constructs a new hash table.
dbus_bool_t _dbus_hash_table_remove_int(DBusHashTable *table, int key)
Removes the hash entry for the given key.
DBusPreallocatedHash * _dbus_hash_table_preallocate_entry(DBusHashTable *table)
Preallocate an opaque data blob that allows us to insert into the hash table at a later time without ...
dbus_bool_t _dbus_hash_table_remove_string(DBusHashTable *table, const char *key)
Removes the hash entry for the given key.
char ** _dbus_hash_table_to_array(DBusHashTable *table, char delimiter)
Creates a string array from a hash table.
void _dbus_hash_iter_set_value(DBusHashIter *iter, void *value)
Sets the value of the current entry.
DBusHashType
Indicates the type of a key in the hash table.
void * _dbus_hash_table_lookup_string(DBusHashTable *table, const char *key)
Looks up the value for a given string in a hash table of type DBUS_HASH_STRING.
dbus_bool_t _dbus_hash_iter_lookup(DBusHashTable *table, void *key, dbus_bool_t create_if_not_found, DBusHashIter *iter)
A low-level but efficient interface for manipulating the hash table.
void _dbus_hash_table_remove_all(DBusHashTable *table)
Removed all entries from a hash table.
const char * _dbus_hash_iter_get_string_key(DBusHashIter *iter)
Gets the key for the current entry.
dbus_bool_t _dbus_hash_table_insert_uintptr(DBusHashTable *table, uintptr_t key, void *value)
Creates a hash entry with the given key and value.
void _dbus_hash_iter_remove_entry(DBusHashIter *iter)
Removes the current entry from the hash table.
void _dbus_hash_table_insert_string_preallocated(DBusHashTable *table, DBusPreallocatedHash *preallocated, char *key, void *value)
Inserts a string-keyed entry into the hash table, using a preallocated data block from _dbus_hash_tab...
void * _dbus_hash_table_lookup_int(DBusHashTable *table, int key)
Looks up the value for a given integer in a hash table of type DBUS_HASH_INT.
@ DBUS_HASH_INT
Hash keys are integers.
@ DBUS_HASH_UINTPTR
Hash keys are integer capable to hold a pointer.
@ DBUS_HASH_STRING
Hash keys are strings.
#define _DBUS_INT_TO_POINTER(integer)
Safely stuffs an integer into a pointer, to be extracted later with _DBUS_POINTER_TO_INT.
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
#define _DBUS_INT_MAX
Maximum value of type "int".
#define _DBUS_POINTER_TO_INT(pointer)
Safely casts a void* to an integer; should only be used on void* that actually contain integers,...
#define _DBUS_N_ELEMENTS(array)
Computes the number of elements in a fixed-size array using sizeof().
#define NULL
A null pointer, defined appropriately for C or C++.
#define TRUE
Expands to "1".
#define FALSE
Expands to "0".
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
dbus_bool_t _dbus_mem_pool_dealloc(DBusMemPool *pool, void *element)
Deallocates an object previously created with _dbus_mem_pool_alloc().
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
DBusMemPool * _dbus_mem_pool_new(int element_size, dbus_bool_t zero_elements)
Creates a new memory pool, or returns NULL on failure.
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
void dbus_free(void *memory)
Frees a block of memory previously allocated by dbus_malloc() or dbus_malloc0().
#define dbus_new0(type, count)
Safe macro for using dbus_malloc0().
void dbus_free_string_array(char **str_array)
Frees a NULL-terminated array of strings.
dbus_bool_t _dbus_string_set_length(DBusString *str, int length)
Sets the length of a string.
dbus_bool_t _dbus_string_append(DBusString *str, const char *buffer)
Appends a nul-terminated C-style string to a DBusString.
dbus_bool_t _dbus_string_init(DBusString *str)
Initializes a string.
dbus_bool_t _dbus_string_steal_data(DBusString *str, char **data_return)
Like _dbus_string_get_data(), but removes the gotten data from the original string.
dbus_bool_t _dbus_string_split_on_byte(DBusString *source, unsigned char byte, DBusString *tail)
Looks for the first occurance of a byte, deletes that byte, and moves everything after the byte to th...
void _dbus_string_free(DBusString *str)
Frees a string created by _dbus_string_init(), and fills it with the same contents as _DBUS_STRING_IN...
dbus_bool_t _dbus_string_append_printf(DBusString *str, const char *format,...)
Appends a printf-style formatted string to the DBusString.
Internal representation of a hash entry.
DBusHashEntry * next
Pointer to next entry in this hash bucket, or NULL for end of chain.
Internals of DBusHashTable.
DBusHashEntry ** buckets
Pointer to bucket array.
DBusHashType key_type
Type of keys used in this table.
int hi_rebuild_size
Enlarge table when n_entries gets to be this large.
int n_buckets
Total number of buckets allocated at **buckets.
int down_shift
Shift count used in hashing function.
DBusFreeFunction free_key_function
Function to free keys.
int lo_rebuild_size
Shrink table when n_entries gets below this.
DBusFindEntryFunction find_function
Function for finding entries.
int refcount
Reference count.
DBusMemPool * entry_pool
Memory pool for hash entries.
int mask
Mask value used in hashing function.
DBusHashEntry * static_buckets[DBUS_SMALL_HASH_TABLE]
Bucket array used for small tables (to avoid mallocs and frees).
DBusFreeFunction free_value_function
Function to free values.
int n_entries
Total number of entries present in table.
Internals fields of DBusMemPool.
Internals of DBusHashIter.
DBusHashTable * table
Pointer to table containing entry.
DBusHashEntry * next_entry
Next entry to be iterated onto in current bucket.
DBusHashEntry * entry
Current hash entry.
int n_entries_on_init
used to detect table resize since initialization
DBusHashEntry ** bucket
Pointer to bucket that points to first entry in this entry's chain: used for deleting the entry.
int next_bucket
index of next bucket