Hash table
[D-Bus secret internal implementation details]

DBusHashTable data structure. More...


Data Structures
struct	DBusHashIter
	Hash iterator object. More...
Typedefs
typedef int(*)	KeyCompareFunc (const void key_a, const void key_b)
	Key comparison function.
typedef DBusHashTable	DBusHashTable
	Public opaque hash table object.
typedef DBusHashIter	DBusHashIter
	Public opaque hash table iterator object.
typedef DBusPreallocatedHash	DBusPreallocatedHash
	A preallocated hash entry.
Enumerations
enum	DBusHashType { DBUS_HASH_STRING, DBUS_HASH_TWO_STRINGS, DBUS_HASH_INT, DBUS_HASH_POINTER, DBUS_HASH_ULONG }
	Indicates the type of a key in the hash table. More...
Functions
DBusHashTable *	_dbus_hash_table_new (DBusHashType type, DBusFreeFunction key_free_function, DBusFreeFunction value_free_function)
	Constructs a new hash table.
DBusHashTable *	_dbus_hash_table_ref (DBusHashTable *table)
	Increments the reference count for a hash table.
void	_dbus_hash_table_unref (DBusHashTable *table)
	Decrements the reference count for a hash table, freeing the hash table if the count reaches zero.
void	_dbus_hash_table_remove_all (DBusHashTable *table)
	Removed all entries from a hash table.
void	_dbus_hash_iter_init (DBusHashTable table, DBusHashIter iter)
	Initializes a hash table iterator.
dbus_bool_t	_dbus_hash_iter_next (DBusHashIter *iter)
	Move the hash iterator forward one step, to the next hash entry.
void	_dbus_hash_iter_remove_entry (DBusHashIter *iter)
	Removes the current entry from the hash table.
void *	_dbus_hash_iter_get_value (DBusHashIter *iter)
	Gets the value of the current entry.
void	_dbus_hash_iter_set_value (DBusHashIter iter, void value)
	Sets the value of the current entry.
int	_dbus_hash_iter_get_int_key (DBusHashIter *iter)
	Gets the key for the current entry.
unsigned long	_dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
	Gets the key for the current entry.
const char *	_dbus_hash_iter_get_string_key (DBusHashIter *iter)
	Gets the key for the current entry.
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_lookup_string (DBusHashTable table, const char key)
	Looks up the value for a given string in a hash table of type DBUS_HASH_STRING.
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.
void *	_dbus_hash_table_lookup_ulong (DBusHashTable *table, unsigned long key)
	Looks up the value for a given integer in a hash table of type DBUS_HASH_ULONG.
dbus_bool_t	_dbus_hash_table_remove_string (DBusHashTable table, const char key)
	Removes the hash entry for the given key.
dbus_bool_t	_dbus_hash_table_remove_int (DBusHashTable *table, int key)
	Removes the hash entry for the given key.
dbus_bool_t	_dbus_hash_table_remove_ulong (DBusHashTable *table, unsigned long key)
	Removes the hash entry for the given key.
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_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_ulong (DBusHashTable table, unsigned long key, void value)
	Creates a hash entry with the given key and value.
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 allocating any memory.
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.
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_table_preallocate_entry().
int	_dbus_hash_table_get_n_entries (DBusHashTable *table)
	Gets the number of hash entries in a hash table.
const char *	_dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
void *	_dbus_hash_table_lookup_two_strings (DBusHashTable table, const char key)
void *	_dbus_hash_table_lookup_pointer (DBusHashTable table, void key)
dbus_bool_t	_dbus_hash_table_remove_two_strings (DBusHashTable table, const char key)
dbus_bool_t	_dbus_hash_table_remove_pointer (DBusHashTable table, void key)
dbus_bool_t	_dbus_hash_table_insert_two_strings (DBusHashTable table, char key, void *value)
dbus_bool_t	_dbus_hash_table_insert_pointer (DBusHashTable table, void key, void *value)

Detailed Description

DBusHashTable data structure.

Types and functions related to DBusHashTable.

Enumeration Type Documentation

enum DBusHashType

Indicates the type of a key in the hash table.

Enumerator:

DBUS_HASH_STRING	Hash keys are strings.
DBUS_HASH_TWO_STRINGS	Hash key is two strings in one memory block, i.e. foo\0bar\0
DBUS_HASH_INT	Hash keys are integers.
DBUS_HASH_POINTER	Hash keys are pointers.
DBUS_HASH_ULONG	Hash keys are unsigned long.

Definition at line 58 of file dbus-hash.h.

Function Documentation

int _dbus_hash_iter_get_int_key ( DBusHashIter * iter )

Gets the key for the current entry.

Only works for hash tables of type DBUS_HASH_INT.

Parameters:

iter

the hash table iterator.

Definition at line 672 of file dbus-hash.c.

References _dbus_assert, _DBUS_POINTER_TO_INT, DBusRealHashIter::entry, DBusHashEntry::key, NULL, and DBusRealHashIter::table.

const char * _dbus_hash_iter_get_string_key ( DBusHashIter * iter )

Gets the key for the current entry.

Only works for hash tables of type DBUS_HASH_STRING

Parameters:

iter

the hash table iterator.

Definition at line 709 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::entry, DBusHashEntry::key, NULL, and DBusRealHashIter::table.

unsigned long _dbus_hash_iter_get_ulong_key ( DBusHashIter * iter )

Gets the key for the current entry.

Only works for hash tables of type DBUS_HASH_ULONG.

Parameters:

iter

the hash table iterator.

Definition at line 691 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::entry, DBusHashEntry::key, NULL, and DBusRealHashIter::table.

void * _dbus_hash_iter_get_value ( DBusHashIter * iter )

Gets the value of the current entry.

Parameters:

iter

the hash table iterator.

Definition at line 626 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::entry, NULL, DBusRealHashIter::table, and DBusHashEntry::value.

void _dbus_hash_iter_init	(	DBusHashTable *	table,
		DBusHashIter *	iter
	)

Initializes a hash table iterator.

To iterate over all entries in a hash table, use the following code (the printf assumes a hash from strings to strings obviously):

 DBusHashIter iter;

 _dbus_hash_iter_init (table, &iter);
 while (_dbus_hash_iter_next (&iter))
   {
      printf ("The first key is %s and value is %s\n",
              _dbus_hash_iter_get_string_key (&iter),
              _dbus_hash_iter_get_value (&iter));
   }

The iterator is initialized pointing "one before" the first hash entry. The first call to _dbus_hash_iter_next() moves it onto the first valid entry or returns FALSE if the hash table is empty. Subsequent calls move to the next valid entry or return FALSE if there are no more entries.

Note that it is guaranteed to be safe to remove a hash entry during iteration, but it is not safe to add a hash entry.

Parameters:

	table	the hash table to iterate over.
	iter	the iterator to initialize.

Definition at line 530 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::bucket, DBusRealHashIter::entry, n_entries, DBusRealHashIter::n_entries_on_init, DBusRealHashIter::next_bucket, DBusRealHashIter::next_entry, NULL, and DBusRealHashIter::table.

Referenced by _dbus_hash_table_remove_all().

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.

It's efficient because you can get, set, and optionally create the hash entry while only running the hash function one time.

Note that while calling _dbus_hash_iter_next() on the iterator filled in by this function may work, it's completely undefined which entries are after this iter and which are before it. So it would be silly to iterate using this iterator.

If the hash entry is created, its value will be initialized to all bits zero.

FALSE may be returned due to memory allocation failure, or because create_if_not_found was FALSE and the entry did not exist.

If create_if_not_found is TRUE and the entry is created, the hash table takes ownership of the key that's passed in.

For a hash table of type DBUS_HASH_INT, cast the int key to the key parameter using _DBUS_INT_TO_POINTER().

Parameters:

	table	the hash table.
	key	the hash key.
	create_if_not_found	if TRUE, create the entry if it didn't exist.
	iter	the iterator to initialize.

Returns:: TRUE if the hash entry now exists (and the iterator is thus valid).

Definition at line 773 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::bucket, buckets, DBusRealHashIter::entry, FALSE, find_function, n_entries, DBusRealHashIter::n_entries_on_init, DBusHashEntry::next, DBusRealHashIter::next_bucket, DBusRealHashIter::next_entry, NULL, DBusRealHashIter::table, and TRUE.

dbus_bool_t _dbus_hash_iter_next ( DBusHashIter * iter )

Move the hash iterator forward one step, to the next hash entry.

The documentation for _dbus_hash_iter_init() explains in more detail.

Parameters:

iter

the iterator to move forward.

Returns:: FALSE if there are no more entries to move to.

Definition at line 556 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::bucket, buckets, DBusRealHashIter::entry, FALSE, n_buckets, n_entries, DBusRealHashIter::n_entries_on_init, DBusHashEntry::next, DBusRealHashIter::next_bucket, DBusRealHashIter::next_entry, NULL, DBusRealHashIter::table, and TRUE.

Referenced by _dbus_hash_table_remove_all().

void _dbus_hash_iter_remove_entry ( DBusHashIter * iter )

Removes the current entry from the hash table.

If a key_free_function or value_free_function was provided to _dbus_hash_table_new(), frees the key and/or value for this entry.

Parameters:

iter

the hash table iterator.

Definition at line 605 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::bucket, DBusRealHashIter::entry, NULL, and DBusRealHashIter::table.

Referenced by _dbus_hash_table_remove_all().

void _dbus_hash_iter_set_value	(	DBusHashIter *	iter,
		void *	value
	)

Sets the value of the current entry.

If the hash table has a value_free_function it will be used to free the previous value. The hash table will own the passed-in value (it will not be copied).

Parameters:

	iter	the hash table iterator.
	value	the new value.

Definition at line 649 of file dbus-hash.c.

References _dbus_assert, DBusRealHashIter::entry, free_value_function, NULL, DBusRealHashIter::table, and DBusHashEntry::value.

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.

Parameters:

	table	the hash table
	preallocated	the preallocated data

Definition at line 1643 of file dbus-hash.c.

References _dbus_assert, _dbus_mem_pool_dealloc(), entry_pool, and NULL.

int _dbus_hash_table_get_n_entries ( DBusHashTable * table )

Gets the number of hash entries in a hash table.

Parameters:

table

the hash table.

Returns:: the number of entries in the table.

Definition at line 1701 of file dbus-hash.c.

References n_entries.

dbus_bool_t _dbus_hash_table_insert_int	(	DBusHashTable *	table,
		int	key,
		void *	value
	)

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.

Parameters:

	table	the hash table.
	key	the hash entry key.
	value	the hash entry value.

Definition at line 1508 of file dbus-hash.c.

References _dbus_assert, _DBUS_INT_TO_POINTER, DBUS_HASH_INT, FALSE, find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, NULL, TRUE, and DBusHashEntry::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.

Returns FALSE if memory for the new hash entry can't be allocated.

Parameters:

	table	the hash table.
	key	the hash entry key.
	value	the hash entry value.

Definition at line 1431 of file dbus-hash.c.

References _dbus_assert, _dbus_hash_table_insert_string_preallocated(), _dbus_hash_table_preallocate_entry(), DBUS_HASH_STRING, FALSE, key_type, NULL, and TRUE.

Referenced by _dbus_user_database_lookup(), and _dbus_user_database_lookup_group().

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_table_preallocate_entry().

This function cannot fail due to lack of memory. The DBusPreallocatedHash object is consumed and should not be reused or freed. Otherwise this function works just like _dbus_hash_table_insert_string().

Parameters:

	table	the hash table
	preallocated	the preallocated data
	key	the hash key
	value	the value

Definition at line 1670 of file dbus-hash.c.

References _dbus_assert, DBUS_HASH_STRING, find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, NULL, TRUE, and DBusHashEntry::value.

Referenced by _dbus_hash_table_insert_string().

dbus_bool_t _dbus_hash_table_insert_ulong	(	DBusHashTable *	table,
		unsigned long	key,
		void *	value
	)

Creates a hash entry with the given key and value.

Returns FALSE if memory for the new hash entry can't be allocated.

Parameters:

	table	the hash table.
	key	the hash entry key.
	value	the hash entry value.

Definition at line 1593 of file dbus-hash.c.

References _dbus_assert, DBUS_HASH_ULONG, FALSE, find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, NULL, TRUE, and DBusHashEntry::value.

Referenced by _dbus_user_database_lookup(), and _dbus_user_database_lookup_group().

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.

Returns NULL if the value is not present. (A not-present entry is indistinguishable from an entry with a value of NULL.)

Parameters:

	table	the hash table.
	key	the integer to look up.

Returns:: the value of the hash entry.

Definition at line 1202 of file dbus-hash.c.

References _dbus_assert, _DBUS_INT_TO_POINTER, DBUS_HASH_INT, FALSE, find_function, key_type, NULL, and DBusHashEntry::value.

Referenced by _dbus_connection_queue_received_message_link(), and dbus_connection_dispatch().

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.

Returns NULL if the value is not present. (A not-present entry is indistinguishable from an entry with a value of NULL.)

Parameters:

	table	the hash table.
	key	the string to look up.

Returns:: the value of the hash entry.

Definition at line 1150 of file dbus-hash.c.

References _dbus_assert, DBUS_HASH_STRING, FALSE, find_function, key_type, NULL, and DBusHashEntry::value.

Referenced by _dbus_user_database_lookup(), and _dbus_user_database_lookup_group().

void * _dbus_hash_table_lookup_ulong	(	DBusHashTable *	table,
		unsigned long	key
	)

Looks up the value for a given integer in a hash table of type DBUS_HASH_ULONG.

Returns NULL if the value is not present. (A not-present entry is indistinguishable from an entry with a value of NULL.)

Parameters:

	table	the hash table.
	key	the integer to look up.

Returns:: the value of the hash entry.

Definition at line 1255 of file dbus-hash.c.

References _dbus_assert, DBUS_HASH_ULONG, FALSE, find_function, key_type, NULL, and DBusHashEntry::value.

Referenced by _dbus_user_database_lookup(), and _dbus_user_database_lookup_group().

DBusHashTable * _dbus_hash_table_new	(	DBusHashType	type,
		DBusFreeFunction	key_free_function,
		DBusFreeFunction	value_free_function
	)

Constructs a new hash table.

Should be freed with _dbus_hash_table_unref(). If memory cannot be allocated for the hash table, returns NULL.

Parameters:

	type	the type of hash key to use.
	key_free_function	function to free hash keys.
	value_free_function	function to free hash values.

Returns:: a new DBusHashTable or NULL if no memory.

Definition at line 292 of file dbus-hash.c.

References _dbus_assert, _dbus_assert_not_reached, _dbus_mem_pool_new(), _DBUS_N_ELEMENTS, buckets, dbus_free(), DBUS_HASH_INT, DBUS_HASH_POINTER, DBUS_HASH_STRING, DBUS_HASH_TWO_STRINGS, DBUS_HASH_ULONG, dbus_new0, DBUS_SMALL_HASH_TABLE, down_shift, entry_pool, find_function, free_key_function, free_value_function, hi_rebuild_size, key_type, lo_rebuild_size, mask, n_buckets, n_entries, NULL, REBUILD_MULTIPLIER, refcount, static_buckets, and TRUE.

Referenced by _dbus_connection_new_for_transport(), and _dbus_user_database_new().

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 allocating any memory.

Parameters:

table

the hash table

Returns:: the preallocated data, or NULL if no memory

Definition at line 1626 of file dbus-hash.c.

Referenced by _dbus_hash_table_insert_string().

DBusHashTable * _dbus_hash_table_ref ( DBusHashTable * table )

Increments the reference count for a hash table.

Parameters:

table

the hash table to add a reference to.

Returns:: the hash table.

Definition at line 360 of file dbus-hash.c.

References refcount.

void _dbus_hash_table_remove_all ( DBusHashTable * table )

Removed all entries from a hash table.

Parameters:

table

the hash table to remove all entries from.

Definition at line 431 of file dbus-hash.c.

References _dbus_hash_iter_init(), _dbus_hash_iter_next(), and _dbus_hash_iter_remove_entry().

Referenced by _dbus_user_database_flush().

dbus_bool_t _dbus_hash_table_remove_int	(	DBusHashTable *	table,
		int	key
	)

Removes the hash entry for the given key.

If no hash entry for the key exists, does nothing.

Parameters:

	table	the hash table.
	key	the hash key.

Returns:: TRUE if the entry existed

Definition at line 1337 of file dbus-hash.c.

References _dbus_assert, _DBUS_INT_TO_POINTER, DBUS_HASH_INT, FALSE, find_function, key_type, NULL, and TRUE.

dbus_bool_t _dbus_hash_table_remove_string	(	DBusHashTable *	table,
		const char *	key
	)

Removes the hash entry for the given key.

If no hash entry for the key exists, does nothing.

Parameters:

	table	the hash table.
	key	the hash key.

Returns:: TRUE if the entry existed

Definition at line 1279 of file dbus-hash.c.

References _dbus_assert, DBUS_HASH_STRING, FALSE, find_function, key_type, NULL, and TRUE.

dbus_bool_t _dbus_hash_table_remove_ulong	(	DBusHashTable *	table,
		unsigned long	key
	)

Removes the hash entry for the given key.

If no hash entry for the key exists, does nothing.

Parameters:

	table	the hash table.
	key	the hash key.

Returns:: TRUE if the entry existed

Definition at line 1396 of file dbus-hash.c.

References _dbus_assert, DBUS_HASH_ULONG, FALSE, find_function, key_type, NULL, and TRUE.

Referenced by _dbus_user_database_lookup(), and _dbus_user_database_lookup_group().

void _dbus_hash_table_unref ( DBusHashTable * table )

Decrements the reference count for a hash table, freeing the hash table if the count reaches zero.

Parameters:

table

the hash table to remove a reference from.

Definition at line 374 of file dbus-hash.c.

References _dbus_mem_pool_free(), buckets, dbus_free(), entry_pool, n_buckets, DBusHashEntry::next, NULL, refcount, and static_buckets.

Referenced by _dbus_connection_new_for_transport(), and _dbus_user_database_unref().

Generated on Tue Feb 24 16:40:40 2009 for D-Bus by

1.5.1

Hash table [D-Bus secret internal implementation details]

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

Function Documentation

Hash table
[D-Bus secret internal implementation details]