Main Page   Modules   Data Structures   File List   Data Fields   Related Pages  

Hash table
[D-BUS internal implementation details]

DBusHashTable data structure. More...

Typedefs

typedef int(* KeyCompareFunc )(const void *key_a, const void *key_b)
 Key comparison function.

typedef DBusHashIter DBusHashIter
 Public opaque hash table iterator object.

typedef DBusHashTable DBusHashTable
 Public opaque hash table object.


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. More...

DBusHashTable * _dbus_hash_table_ref (DBusHashTable *table)
 Increments the reference count for a hash table. More...

void _dbus_hash_table_unref (DBusHashTable *table)
 Decrements the reference count for a hash table, freeing the hash table if the count reaches zero. More...

void _dbus_hash_iter_init (DBusHashTable *table, DBusHashIter *iter)
 Initializes a hash table iterator. More...

dbus_bool_t _dbus_hash_iter_next (DBusHashIter *iter)
 Move the hash iterator forward one step, to the next hash entry. More...

void _dbus_hash_iter_remove_entry (DBusHashIter *iter)
 Removes the current entry from the hash table. More...

void * _dbus_hash_iter_get_value (DBusHashIter *iter)
 Gets the value of the current entry. More...

void _dbus_hash_iter_set_value (DBusHashIter *iter, void *value)
 Sets the value of the current entry. More...

int _dbus_hash_iter_get_int_key (DBusHashIter *iter)
 Gets the key for the current entry. More...

unsigned long _dbus_hash_iter_get_ulong_key (DBusHashIter *iter)
 Gets the key for the current entry. More...

const char * _dbus_hash_iter_get_string_key (DBusHashIter *iter)
 Gets the key for the current entry. More...

const char * _dbus_hash_iter_get_two_strings_key (DBusHashIter *iter)
 Gets the key for the current entry. More...

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. More...

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. More...

void * _dbus_hash_table_lookup_two_strings (DBusHashTable *table, const char *key)
 Looks up the value for a given string in a hash table of type DBUS_HASH_TWO_STRINGS. More...

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. More...

void * _dbus_hash_table_lookup_pointer (DBusHashTable *table, void *key)
 Looks up the value for a given integer in a hash table of type DBUS_HASH_POINTER. More...

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. More...

dbus_bool_t _dbus_hash_table_remove_string (DBusHashTable *table, const char *key)
 Removes the hash entry for the given key. More...

dbus_bool_t _dbus_hash_table_remove_two_strings (DBusHashTable *table, const char *key)
 Removes the hash entry for the given key. More...

dbus_bool_t _dbus_hash_table_remove_int (DBusHashTable *table, int key)
 Removes the hash entry for the given key. More...

dbus_bool_t _dbus_hash_table_remove_pointer (DBusHashTable *table, void *key)
 Removes the hash entry for the given key. More...

dbus_bool_t _dbus_hash_table_remove_ulong (DBusHashTable *table, unsigned long key)
 Removes the hash entry for the given key. More...

dbus_bool_t _dbus_hash_table_insert_string (DBusHashTable *table, char *key, void *value)
 Creates a hash entry with the given key and value. More...

dbus_bool_t _dbus_hash_table_insert_two_strings (DBusHashTable *table, char *key, void *value)
 Creates a hash entry with the given key and value. More...

dbus_bool_t _dbus_hash_table_insert_int (DBusHashTable *table, int key, void *value)
 Creates a hash entry with the given key and value. More...

dbus_bool_t _dbus_hash_table_insert_pointer (DBusHashTable *table, void *key, void *value)
 Creates a hash entry with the given key and value. More...

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. More...

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. More...

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. More...

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

int _dbus_hash_table_get_n_entries (DBusHashTable *table)
 Gets the number of hash entries in a hash table. More...


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.

Enumeration values:
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 53 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 650 of file dbus-hash.c.

References DBusRealHashIter::entry, DBusHashEntry::key, 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 687 of file dbus-hash.c.

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

const char* _dbus_hash_iter_get_two_strings_key DBusHashIter   iter
 

Gets the key for the current entry.

Only works for hash tables of type DBUS_HASH_TWO_STRINGS

Parameters:
iter  the hash table iterator.

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

References DBusRealHashIter::entry, DBusHashEntry::key, 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 669 of file dbus-hash.c.

References DBusRealHashIter::entry, DBusHashEntry::key, 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 604 of file dbus-hash.c.

References DBusRealHashIter::entry, 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 508 of file dbus-hash.c.

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

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 749 of file dbus-hash.c.

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

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 534 of file dbus-hash.c.

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

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 583 of file dbus-hash.c.

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

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 627 of file dbus-hash.c.

References DBusRealHashIter::entry, free_value_function, 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 1602 of file dbus-hash.c.

References entry_pool.

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 1660 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 1467 of file dbus-hash.c.

References find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, and DBusHashEntry::value.

dbus_bool_t _dbus_hash_table_insert_pointer DBusHashTable   table,
void *    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 1510 of file dbus-hash.c.

References find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, 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.

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 1392 of file dbus-hash.c.

References key_type.

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 1629 of file dbus-hash.c.

References find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, and DBusHashEntry::value.

dbus_bool_t _dbus_hash_table_insert_two_strings DBusHashTable   table,
char *    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 1426 of file dbus-hash.c.

References find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, and DBusHashEntry::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.

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 1552 of file dbus-hash.c.

References find_function, free_key_function, free_value_function, DBusHashEntry::key, key_type, and DBusHashEntry::value.

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 1165 of file dbus-hash.c.

References find_function, key_type, and DBusHashEntry::value.

void* _dbus_hash_table_lookup_pointer DBusHashTable   table,
void *    key
 

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

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 1192 of file dbus-hash.c.

References find_function, key_type, and DBusHashEntry::value.

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 1115 of file dbus-hash.c.

References find_function, key_type, and DBusHashEntry::value.

void* _dbus_hash_table_lookup_two_strings DBusHashTable   table,
const char *    key
 

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

Parameters:
table  the hash table.
key  the string to look up.
Returns:
the value of the hash entry.

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

References find_function, key_type, and DBusHashEntry::value.

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 1218 of file dbus-hash.c.

References find_function, key_type, and DBusHashEntry::value.

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 288 of file dbus-hash.c.

References buckets, 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, refcount, and static_buckets.

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 1585 of file dbus-hash.c.

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 354 of file dbus-hash.c.

References refcount.

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 1298 of file dbus-hash.c.

References find_function, and key_type.

dbus_bool_t _dbus_hash_table_remove_pointer DBusHashTable   table,
void *    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 1328 of file dbus-hash.c.

References find_function, and key_type.

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 1242 of file dbus-hash.c.

References find_function, and key_type.

dbus_bool_t _dbus_hash_table_remove_two_strings 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 1270 of file dbus-hash.c.

References find_function, and key_type.

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 1357 of file dbus-hash.c.

References find_function, and key_type.

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 368 of file dbus-hash.c.

References buckets, entry_pool, n_buckets, DBusHashEntry::next, refcount, and static_buckets.


Generated on Wed Jun 9 05:01:27 2004 for D-BUS by doxygen1.2.15