<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Hash table implementation details</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.2.15 -->
<center>
<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="modules.html">Modules</a> <a class="qindex" href="annotated.html">Data Structures</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Data Fields</a> <a class="qindex" href="pages.html">Related Pages</a> </center>
<hr><h1>Hash table implementation details<br>
<small>
[<a class="el" href="group__DBusInternals.html">D-BUS internal implementation details</a>]</small>
</h1><a class="el" href="structDBusHashTable.html">DBusHashTable</a> implementation details.
<a href="#_details">More...</a><table border=0 cellpadding=0 cellspacing=0>
<tr><td colspan=2><br><h2>Data Structures</h2></td></tr>
<tr><td nowrap align=right valign=top>struct </td><td valign=bottom><a class="el" href="structDBusHashEntry.html">DBusHashEntry</a></td></tr>
<tr><td> </td><td><font size=-1><em>Internal representation of a hash entry.</em> <a href="structDBusHashEntry.html#_details">More...</a><em></em></font><br><br></td></tr>
<tr><td nowrap align=right valign=top>struct </td><td valign=bottom><a class="el" href="structDBusHashTable.html">DBusHashTable</a></td></tr>
<tr><td> </td><td><font size=-1><em>Internals of DBusHashTable.</em> <a href="structDBusHashTable.html#_details">More...</a><em></em></font><br><br></td></tr>
<tr><td nowrap align=right valign=top>struct </td><td valign=bottom><a class="el" href="structDBusRealHashIter.html">DBusRealHashIter</a></td></tr>
<tr><td> </td><td><font size=-1><em>Internals of <a class="el" href="structDBusHashIter.html">DBusHashIter</a>.</em> <a href="structDBusRealHashIter.html#_details">More...</a><em></em></font><br><br></td></tr>
<tr><td colspan=2><br><h2>Defines</h2></td></tr>
<tr><td nowrap align=right valign=top><a name="a13" doxytag="DBusHashTableInternals::REBUILD_MULTIPLIER"></a>
#define </td><td valign=bottom><a class="el" href="group__DBusHashTableInternals.html#a13">REBUILD_MULTIPLIER</a> 3</td></tr>
<tr><td> </td><td><font size=-1><em>When there are this many entries per bucket, on average, rebuild the hash table to make it larger.</em></font><br><br></td></tr>
<tr><td nowrap align=right valign=top>#define </td><td valign=bottom><a class="el" href="group__DBusHashTableInternals.html#a14">RANDOM_INDEX</a>(table, i) (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)</td></tr>
<tr><td> </td><td><font size=-1><em>Takes a preliminary integer hash value and produces an index into a hash tables bucket list.</em> <a href="#a14">More...</a><em></em></font><br><br></td></tr>
<tr><td nowrap align=right valign=top>#define </td><td valign=bottom><a class="el" href="group__DBusHashTableInternals.html#a15">DBUS_SMALL_HASH_TABLE</a> 4</td></tr>
<tr><td> </td><td><font size=-1><em>Initial number of buckets in hash table (hash table statically allocates its buckets for this size and below).</em> <a href="#a15">More...</a><em></em></font><br><br></td></tr>
<tr><td colspan=2><br><h2>Typedefs</h2></td></tr>
<tr><td nowrap align=right valign=top><a name="a0" doxytag="DBusHashTableInternals::DBusHashEntry"></a>
typedef DBusHashEntry </td><td valign=bottom><a class="el" href="group__DBusHashTableInternals.html#a0">DBusHashEntry</a></td></tr>
<tr><td> </td><td><font size=-1><em>Typedef for <a class="el" href="structDBusHashEntry.html">DBusHashEntry</a>.</em></font><br><br></td></tr>
<tr><td nowrap align=right valign=top><a name="a1" doxytag="DBusHashTableInternals::DBusFindEntryFunction"></a>
typedef <a class="el" href="structDBusHashEntry.html">DBusHashEntry</a> *(* </td><td valign=bottom><a class="el" href="group__DBusHashTableInternals.html#a1">DBusFindEntryFunction</a> )(<a class="el" href="structDBusHashTable.html">DBusHashTable</a> *table, void *key, <a class="el" href="group__DBusTypes.html#a2">dbus_bool_t</a> create_if_not_found, <a class="el" href="structDBusHashEntry.html">DBusHashEntry</a> ***bucket, DBusPreallocatedHash *preallocated)</td></tr>
<tr><td> </td><td><font size=-1><em>Function used to find and optionally create a hash entry.</em></font><br><br></td></tr>
<tr><td colspan=2><br><h2>Functions</h2></td></tr>
<tr><td nowrap align=right valign=top><a class="el" href="group__DBusTypes.html#a2">dbus_bool_t</a> </td><td valign=bottom><a class="el" href="group__DBusHashTableInternals.html#a12">_dbus_hash_test</a> (void)</td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
<a class="el" href="structDBusHashTable.html">DBusHashTable</a> implementation details.
<p>
<p>
The guts of <a class="el" href="structDBusHashTable.html">DBusHashTable</a>. <hr><h2>Define Documentation</h2>
<a name="a15" doxytag="dbus-hash.c::DBUS_SMALL_HASH_TABLE"></a><p>
<table width="100%" cellpadding="2" cellspacing="0" border="0">
<tr>
<td class="md">
<table cellpadding="0" cellspacing="0" border="0">
<tr>
<td class="md" nowrap valign="top"> #define DBUS_SMALL_HASH_TABLE 4
</table>
</td>
</tr>
</table>
<table cellspacing=5 cellpadding=0 border=0>
<tr>
<td>
</td>
<td>
<p>
Initial number of buckets in hash table (hash table statically allocates its buckets for this size and below).
<p>
The initial mask has to be synced to this.
<p>
Definition at line <a class="el" href="dbus-hash_8c-source.html#l00129">129</a> of file <a class="el" href="dbus-hash_8c-source.html">dbus-hash.c</a>. </td>
</tr>
</table>
<a name="a14" doxytag="dbus-hash.c::RANDOM_INDEX"></a><p>
<table width="100%" cellpadding="2" cellspacing="0" border="0">
<tr>
<td class="md">
<table cellpadding="0" cellspacing="0" border="0">
<tr>
<td class="md" nowrap valign="top"> #define RANDOM_INDEX</td>
<td class="md" valign="top">( </td>
<td class="md" nowrap valign="top">table, <tr>
<td></td>
<td></td>
<td class="md" nowrap>i </td>
<td class="mdname1" valign="top" nowrap> </td>
<td class="md" valign="top">) </td>
<td class="md" nowrap> (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
</table>
</td>
</tr>
</table>
<table cellspacing=5 cellpadding=0 border=0>
<tr>
<td>
</td>
<td>
<p>
Takes a preliminary integer hash value and produces an index into a hash tables bucket list.
<p>
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.)
<p>
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?
<p>
Definition at line <a class="el" href="dbus-hash_8c-source.html#l00121">121</a> of file <a class="el" href="dbus-hash_8c-source.html">dbus-hash.c</a>. </td>
</tr>
</table>
<hr><h2>Function Documentation</h2>
<a name="a12" doxytag="dbus-hash.c::_dbus_hash_test"></a><p>
<table width="100%" cellpadding="2" cellspacing="0" border="0">
<tr>
<td class="md">
<table cellpadding="0" cellspacing="0" border="0">
<tr>
<td class="md" nowrap valign="top"> <a class="el" href="group__DBusTypes.html#a2">dbus_bool_t</a> _dbus_hash_test </td>
<td class="md" valign="top">( </td>
<td class="md" nowrap valign="top">void </td>
<td class="mdname1" valign="top" nowrap> </td>
<td class="md" valign="top">) </td>
<td class="md" nowrap></td>
</tr>
</table>
</td>
</tr>
</table>
<table cellspacing=5 cellpadding=0 border=0>
<tr>
<td>
</td>
<td>
<p>
Unit test for <a class="el" href="structDBusHashTable.html">DBusHashTable</a> <dl compact><dt><b>
Returns: </b><dd>
<a class="el" href="group__DBusMacros.html#a2">TRUE</a> on success. </dl>
<p>
Definition at line <a class="el" href="dbus-hash_8c-source.html#l01719">1719</a> of file <a class="el" href="dbus-hash_8c-source.html">dbus-hash.c</a>. </td>
</tr>
</table>
<hr><address align="right"><small>Generated on Wed Jun 9 05:01:27 2004 for D-BUS by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0
width=110 height=53></a>1.2.15 </small></address>
</body>
</html>
distrib
>
Mandriva
>
2007.0
>
x86_64
>
media
>
main-release
>
by-pkgid
>
926d2d1e3111287cee1b0a4fad4fb4f6
>
files
>
175
