hash_tables.sgml

GLib是GTK+和GNOME工程的基础底层核心程序库

<refentry id="glib-Hash-Tables">
<refmeta>
<refentrytitle>Hash Tables</refentrytitle>
<manvolnum>3</manvolnum>
<refmiscinfo>GLIB Library</refmiscinfo>
</refmeta>

<refnamediv>
<refname>Hash Tables</refname><refpurpose>associations between keys and values so that given a key the value
can be found quickly.</refpurpose>
</refnamediv>

<refsynopsisdiv><title>Synopsis</title>
<synopsis>

#include &lt;glib.h&gt;


struct      <link linkend="GHashTable">GHashTable</link>;
<link linkend="GHashTable">GHashTable</link>* <link linkend="g-hash-table-new">g_hash_table_new</link>                (<link linkend="GHashFunc">GHashFunc</link> hash_func,
                                             <link linkend="GEqualFunc">GEqualFunc</link> key_equal_func);
<link linkend="GHashTable">GHashTable</link>* <link linkend="g-hash-table-new-full">g_hash_table_new_full</link>           (<link linkend="GHashFunc">GHashFunc</link> hash_func,
                                             <link linkend="GEqualFunc">GEqualFunc</link> key_equal_func,
                                             <link linkend="GDestroyNotify">GDestroyNotify</link> key_destroy_func,
                                             <link linkend="GDestroyNotify">GDestroyNotify</link> value_destroy_func);
<link linkend="guint">guint</link>       (<link linkend="GHashFunc">*GHashFunc</link>)                    (<link linkend="gconstpointer">gconstpointer</link> key);
<link linkend="gboolean">gboolean</link>    (<link linkend="GEqualFunc">*GEqualFunc</link>)                   (<link linkend="gconstpointer">gconstpointer</link> a,
                                             <link linkend="gconstpointer">gconstpointer</link> b);
void        <link linkend="g-hash-table-insert">g_hash_table_insert</link>             (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gpointer">gpointer</link> key,
                                             <link linkend="gpointer">gpointer</link> value);
void        <link linkend="g-hash-table-replace">g_hash_table_replace</link>            (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gpointer">gpointer</link> key,
                                             <link linkend="gpointer">gpointer</link> value);
<link linkend="guint">guint</link>       <link linkend="g-hash-table-size">g_hash_table_size</link>               (<link linkend="GHashTable">GHashTable</link> *hash_table);
<link linkend="gpointer">gpointer</link>    <link linkend="g-hash-table-lookup">g_hash_table_lookup</link>             (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gconstpointer">gconstpointer</link> key);
<link linkend="gboolean">gboolean</link>    <link linkend="g-hash-table-lookup-extended">g_hash_table_lookup_extended</link>    (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gconstpointer">gconstpointer</link> lookup_key,
                                             <link linkend="gpointer">gpointer</link> *orig_key,
                                             <link linkend="gpointer">gpointer</link> *value);
void        <link linkend="g-hash-table-foreach">g_hash_table_foreach</link>            (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="GHFunc">GHFunc</link> func,
                                             <link linkend="gpointer">gpointer</link> user_data);
void        (<link linkend="GHFunc">*GHFunc</link>)                       (<link linkend="gpointer">gpointer</link> key,
                                             <link linkend="gpointer">gpointer</link> value,
                                             <link linkend="gpointer">gpointer</link> user_data);
<link linkend="gboolean">gboolean</link>    <link linkend="g-hash-table-remove">g_hash_table_remove</link>             (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gconstpointer">gconstpointer</link> key);
<link linkend="gboolean">gboolean</link>    <link linkend="g-hash-table-steal">g_hash_table_steal</link>              (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gconstpointer">gconstpointer</link> key);
<link linkend="guint">guint</link>       <link linkend="g-hash-table-foreach-remove">g_hash_table_foreach_remove</link>     (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="GHRFunc">GHRFunc</link> func,
                                             <link linkend="gpointer">gpointer</link> user_data);
<link linkend="guint">guint</link>       <link linkend="g-hash-table-foreach-steal">g_hash_table_foreach_steal</link>      (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="GHRFunc">GHRFunc</link> func,
                                             <link linkend="gpointer">gpointer</link> user_data);
<link linkend="gboolean">gboolean</link>    (<link linkend="GHRFunc">*GHRFunc</link>)                      (<link linkend="gpointer">gpointer</link> key,
                                             <link linkend="gpointer">gpointer</link> value,
                                             <link linkend="gpointer">gpointer</link> user_data);
#define     <link linkend="g-hash-table-freeze">g_hash_table_freeze</link>             (hash_table)
#define     <link linkend="g-hash-table-thaw">g_hash_table_thaw</link>               (hash_table)
void        <link linkend="g-hash-table-destroy">g_hash_table_destroy</link>            (<link linkend="GHashTable">GHashTable</link> *hash_table);

<link linkend="gboolean">gboolean</link>    <link linkend="g-direct-equal">g_direct_equal</link>                  (<link linkend="gconstpointer">gconstpointer</link> v,
                                             <link linkend="gconstpointer">gconstpointer</link> v2);
<link linkend="guint">guint</link>       <link linkend="g-direct-hash">g_direct_hash</link>                   (<link linkend="gconstpointer">gconstpointer</link> v);
<link linkend="gboolean">gboolean</link>    <link linkend="g-int-equal">g_int_equal</link>                     (<link linkend="gconstpointer">gconstpointer</link> v,
                                             <link linkend="gconstpointer">gconstpointer</link> v2);
<link linkend="guint">guint</link>       <link linkend="g-int-hash">g_int_hash</link>                      (<link linkend="gconstpointer">gconstpointer</link> v);
<link linkend="gboolean">gboolean</link>    <link linkend="g-str-equal">g_str_equal</link>                     (<link linkend="gconstpointer">gconstpointer</link> v,
                                             <link linkend="gconstpointer">gconstpointer</link> v2);
<link linkend="guint">guint</link>       <link linkend="g-str-hash">g_str_hash</link>                      (<link linkend="gconstpointer">gconstpointer</link> v);
</synopsis>
</refsynopsisdiv>





<refsect1>
<title>Description</title>
<para>
A <link linkend="GHashTable">GHashTable</link> provides associations between keys and values which
is optimized so that given a key, the associated value can be found
very quickly.
</para>
<para>
Note that neither keys nor values are copied when inserted into the
<link linkend="GHashTable">GHashTable</link>, so they must exist for the lifetime of the <link linkend="GHashTable">GHashTable</link>.
This means that the use of static strings is OK, but temporary
strings (i.e. those created in buffers and those returned by GTK+ widgets)
should be copied with <link linkend="g-strdup">g_strdup</link>() before being inserted.
</para>
<para>
If keys or values are dynamically allocated, you must be careful to ensure
that they are freed when they are removed from the <link linkend="GHashTable">GHashTable</link>, and also
when they are overwritten by new insertions into the <link linkend="GHashTable">GHashTable</link>.
It is also not advisable to mix static strings and dynamically-allocated
strings in a <link linkend="GHashTable">GHashTable</link>, because it then becomes difficult to determine
whether the string should be freed.
</para>
<para>
To create a <link linkend="GHashTable">GHashTable</link>, use <link linkend="g-hash-table-new">g_hash_table_new</link>().
</para>
<para>
To insert a key and value into a <link linkend="GHashTable">GHashTable</link>, use <link linkend="g-hash-table-insert">g_hash_table_insert</link>().
</para>
<para>
To lookup a value corresponding to a given key, use <link linkend="g-hash-table-lookup">g_hash_table_lookup</link>()
and <link linkend="g-hash-table-lookup-extended">g_hash_table_lookup_extended</link>().
</para>
<para>
To remove a key and value, use <link linkend="g-hash-table-remove">g_hash_table_remove</link>().
</para>
<para>
To call a function for each key and value pair use <link linkend="g-hash-table-foreach">g_hash_table_foreach</link>().
</para>
<para>
To destroy a <link linkend="GHashTable">GHashTable</link> use <link linkend="g-hash-table-destroy">g_hash_table_destroy</link>().
</para>
</refsect1>

<refsect1>
<title>Details</title>
<refsect2>
<title><anchor id="GHashTable">struct GHashTable</title>
<programlisting>struct GHashTable;</programlisting>
<para>
The <structname>GHashTable</structname> struct is an opaque data structure to represent a
<link linkend="glib-Hash-Tables">Hash Table</link>.
It should only be accessed via the following functions.
</para></refsect2>
<refsect2>
<title><anchor id="g-hash-table-new">g_hash_table_new ()</title>
<programlisting><link linkend="GHashTable">GHashTable</link>* g_hash_table_new                (<link linkend="GHashFunc">GHashFunc</link> hash_func,
                                             <link linkend="GEqualFunc">GEqualFunc</link> key_equal_func);</programlisting>
<para>
Creates a new <link linkend="GHashTable">GHashTable</link>.</para>
<para>

</para><informaltable pgwide="1" frame="none" role="params">
<tgroup cols="2">
<colspec colwidth="2*">
<colspec colwidth="8*">
<tbody>
<row><entry align="right"><parameter>hash_func</parameter>&nbsp;:</entry>
<entry> a function to create a hash value from a key.
  Hash values are used to determine where keys are stored within the
  <link linkend="GHashTable">GHashTable</link> data structure. The <link linkend="g-direct-hash">g_direct_hash</link>(), <link linkend="g-int-hash">g_int_hash</link>() and 
  <link linkend="g-str-hash">g_str_hash</link>() functions are provided for some common types of keys. 
  If hash_func is <literal>NULL</literal>, <link linkend="g-direct-hash">g_direct_hash</link>() is used.
</entry></row>
<row><entry align="right"><parameter>key_equal_func</parameter>&nbsp;:</entry>
<entry> a function to check two keys for equality.  This is
  used when looking up keys in the <link linkend="GHashTable">GHashTable</link>.  The <link linkend="g-direct-equal">g_direct_equal</link>(),
  <link linkend="g-int-equal">g_int_equal</link>() and <link linkend="g-str-equal">g_str_equal</link>() functions are provided for the most
  common types of keys. If <parameter>key_equal_func</parameter> is <literal>NULL</literal>, keys are compared
  directly in a similar fashion to <link linkend="g-direct-equal">g_direct_equal</link>(), but without the
  overhead of a function call.
</entry></row>
<row><entry align="right"><emphasis>Returns</emphasis> :</entry><entry> a new <link linkend="GHashTable">GHashTable</link>.
</entry></row>
</tbody></tgroup></informaltable></refsect2>
<refsect2>
<title><anchor id="g-hash-table-new-full">g_hash_table_new_full ()</title>
<programlisting><link linkend="GHashTable">GHashTable</link>* g_hash_table_new_full           (<link linkend="GHashFunc">GHashFunc</link> hash_func,
                                             <link linkend="GEqualFunc">GEqualFunc</link> key_equal_func,
                                             <link linkend="GDestroyNotify">GDestroyNotify</link> key_destroy_func,
                                             <link linkend="GDestroyNotify">GDestroyNotify</link> value_destroy_func);</programlisting>
<para>
Creates a new <link linkend="GHashTable">GHashTable</link> like <link linkend="g-hash-table-new">g_hash_table_new</link>() and allows to specify
functions to free the memory allocated for the key and value that get 
called when removing the entry from the <link linkend="GHashTable">GHashTable</link>.</para>
<para>

</para><informaltable pgwide="1" frame="none" role="params">
<tgroup cols="2">
<colspec colwidth="2*">
<colspec colwidth="8*">
<tbody>
<row><entry align="right"><parameter>hash_func</parameter>&nbsp;:</entry>
<entry> a function to create a hash value from a key.
</entry></row>
<row><entry align="right"><parameter>key_equal_func</parameter>&nbsp;:</entry>
<entry> a function to check two keys for equality.
</entry></row>
<row><entry align="right"><parameter>key_destroy_func</parameter>&nbsp;:</entry>
<entry> a function to free the memory allocated for the key 
  used when removing the entry from the <link linkend="GHashTable">GHashTable</link> or <literal>NULL</literal> if you 
  don't want to supply such a function.
</entry></row>
<row><entry align="right"><parameter>value_destroy_func</parameter>&nbsp;:</entry>
<entry> a function to free the memory allocated for the 
  value used when removing the entry from the <link linkend="GHashTable">GHashTable</link> or <literal>NULL</literal> if 
  you don't want to supply such a function.
</entry></row>
<row><entry align="right"><emphasis>Returns</emphasis> :</entry><entry> a new <link linkend="GHashTable">GHashTable</link>.
</entry></row>
</tbody></tgroup></informaltable></refsect2>
<refsect2>
<title><anchor id="GHashFunc">GHashFunc ()</title>
<programlisting><link linkend="guint">guint</link>       (*GHashFunc)                    (<link linkend="gconstpointer">gconstpointer</link> key);</programlisting>
<para>
Specifies the type of the hash function which is passed to
<link linkend="g-hash-table-new">g_hash_table_new</link>() when a <link linkend="GHashTable">GHashTable</link> is created.
</para>
<para>
The function is passed a key and should return a <link linkend="guint">guint</link> hash value.
The functions <link linkend="g-direct-hash">g_direct_hash</link>(), <link linkend="g-int-hash">g_int_hash</link>() and <link linkend="g-str-hash">g_str_hash</link>() provide
hash functions which can be used when the key is a <link linkend="gpointer">gpointer</link>, <link linkend="gint">gint</link>, and 
<link linkend="gchar">gchar</link>* respectively.
</para>
<para>
FIXME: Need more here.
The hash values should be evenly distributed over a fairly large range?
The modulus is taken with the hash table size (a prime number)
to find the 'bucket' to place each key into.
The function should also be very fast, since it is called for each key
lookup.
</para><informaltable pgwide="1" frame="none" role="params">
<tgroup cols="2">
<colspec colwidth="2*">
<colspec colwidth="8*">
<tbody>
<row><entry align="right"><parameter>key</parameter>&nbsp;:</entry>
<entry>a key.
</entry></row>
<row><entry align="right"><emphasis>Returns</emphasis> :</entry><entry>the hash value corresponding to the key.


</entry></row>
</tbody></tgroup></informaltable></refsect2>
<refsect2>
<title><anchor id="GEqualFunc">GEqualFunc ()</title>
<programlisting><link linkend="gboolean">gboolean</link>    (*GEqualFunc)                   (<link linkend="gconstpointer">gconstpointer</link> a,
                                             <link linkend="gconstpointer">gconstpointer</link> b);</programlisting>
<para>
Specifies the type of a function used to test two values for
equality. The function should return <literal>TRUE</literal> if both values are equal and
<literal>FALSE</literal> otherwise.
</para><informaltable pgwide="1" frame="none" role="params">
<tgroup cols="2">
<colspec colwidth="2*">
<colspec colwidth="8*">
<tbody>
<row><entry align="right"><parameter>a</parameter>&nbsp;:</entry>
<entry>a value.
</entry></row>
<row><entry align="right"><parameter>b</parameter>&nbsp;:</entry>
<entry>a value to compare with.
</entry></row>
<row><entry align="right"><emphasis>Returns</emphasis> :</entry><entry><literal>TRUE</literal> if <parameter>a</parameter> = <parameter>b</parameter>; <literal>FALSE</literal> otherwise.


</entry></row>
</tbody></tgroup></informaltable></refsect2>
<refsect2>
<title><anchor id="g-hash-table-insert">g_hash_table_insert ()</title>
<programlisting>void        g_hash_table_insert             (<link linkend="GHashTable">GHashTable</link> *hash_table,
                                             <link linkend="gpointer">gpointer</link> key,
                                             <link linkend="gpointer">gpointer</link> value);</programlisting>
<para>