index.html
Main Page
|
modules.html
Modules
|
namespaces.html
Namespace List
|
hierarchy.html
Class Hierarchy
|
annotated.html
Data Structures
|
dirs.html
Directories
|
files.html
File List
|
namespacemembers.html
Namespace Members
|
functions.html
Data Fields
|
pages.html
Related Pages
Hash table implementation details
[
group__DBusInternals.html
D-BUS internal implementation details
]
structDBusHashTable.html
DBusHashTable
implementation details.
#_details
More...
Data Structures
struct
structDBusHashEntry.html
DBusHashEntry
Internal representation of a hash entry.
structDBusHashEntry.html#_details
More...
struct
structDBusHashTable.html
DBusHashTable
Internals of DBusHashTable.
structDBusHashTable.html#_details
More...
struct
structDBusRealHashIter.html
DBusRealHashIter
Internals of
structDBusHashIter.html
DBusHashIter
.
structDBusRealHashIter.html#_details
More...
Defines
#define
group__DBusHashTableInternals.html#ga10
REBUILD_MULTIPLIER
3
When there are this many entries per bucket, on average, rebuild the hash table to make it larger.
#define
group__DBusHashTableInternals.html#ga11
RANDOM_INDEX
(table, i)   (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
Takes a preliminary integer hash value and produces an index into a hash tables bucket list.
#ga11
#define
group__DBusHashTableInternals.html#ga12
DBUS_SMALL_HASH_TABLE
4
Initial number of buckets in hash table (hash table statically allocates its buckets for this size and below).
#ga12
Typedefs
typedef
structDBusHashEntry.html
DBusHashEntry
group__DBusHashTableInternals.html#ga0
DBusHashEntry
Typedef for
structDBusHashEntry.html
DBusHashEntry
.
typedef
structDBusHashEntry.html
DBusHashEntry
*(*
group__DBusHashTableInternals.html#ga1
DBusFindEntryFunction
)(
structDBusHashTable.html
DBusHashTable
*table, void *key,
group__DBusTypes.html#ga2
dbus_bool_t
create_if_not_found,
structDBusHashEntry.html
DBusHashEntry
***bucket, DBusPreallocatedHash *preallocated)
Function used to find and optionally create a hash entry.
Detailed Description
structDBusHashTable.html
DBusHashTable
implementation details.
The guts of
structDBusHashTable.html
DBusHashTable
.
Define Documentation
#define DBUS_SMALL_HASH_TABLE   4
Initial number of buckets in hash table (hash table statically allocates its buckets for this size and below).
The initial mask has to be synced to this.
Definition at line
dbus-hash_8c-source.html#l00129
129
of file
dbus-hash_8c-source.html
dbus-hash.c
.
Referenced by
dbus-hash_8c-source.html#l00292
_dbus_hash_table_new()
.
#define RANDOM_INDEX
(
table,
i
)
(((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
Takes a preliminary integer hash value and produces an index into a hash tables bucket list.
The idea is to make it so that preliminary values that are arbitrarily similar will end up in different buckets. The hash function was taken from a random-number generator. (This is used to hash integers.)
The down_shift drops off the high bits of the hash index, and decreases as we increase the number of hash buckets (to keep more range in the hash index). The mask also strips high bits and strips fewer high bits as the number of hash buckets increases. I don't understand two things: why is the initial downshift 28 to keep 4 bits when the initial mask is 011 to keep 2 bits, and why do we have both a mask and a downshift?
Definition at line
dbus-hash_8c-source.html#l00121
121
of file
dbus-hash_8c-source.html
dbus-hash.c
.
Generated on Tue Sep 13 00:15:28 2005 for D-BUS by
http://www.doxygen.org/index.html
doxygen
1.4.4
