z29.html

GTK+_ Gnome Application Development

                "FUNCTION">g_node_n_children</tt></code>(GNode* <tt
                class="PARAMETER"><i>node</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">GNode* <tt class= 
                "FUNCTION">g_node_nth_child</tt></code>(GNode* <tt
                class="PARAMETER"><i>node</i></tt>, guint <tt
                class="PARAMETER"><i>n</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">GNode* <tt class= 
                "FUNCTION">g_node_last_child</tt></code>(GNode* <tt
                class="PARAMETER"><i>node</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">GNode* <tt class= 
                "FUNCTION">g_node_find_child</tt></code>(GNode* <tt
                class="PARAMETER"><i>node</i></tt>, GTraverseFlags
                <tt class="PARAMETER"><i>flags</i></tt>, gpointer
                <tt class="PARAMETER"><i>data</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">gint <tt class=
                "FUNCTION">g_node_child_position</tt></code>(GNode*
                <tt class="PARAMETER"><i>node</i></tt>, GNode* <tt
                class="PARAMETER"><i>child</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">gint <tt class=
                "FUNCTION">g_node_child_index</tt></code>(GNode*
                <tt class="PARAMETER"><i>node</i></tt>, gpointer
                <tt class="PARAMETER"><i>data</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">GNode* <tt class= 
                "FUNCTION">g_node_first_sibling</tt></code>(GNode*
                <tt class="PARAMETER"><i>node</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">GNode* <tt class= 
                "FUNCTION">g_node_last_sibling</tt></code>(GNode*
                <tt class="PARAMETER"><i>node</i></tt>);</code>
              </p>
            </div>
            <p>
              <b>Figure 28. Accessing a <span class="STRUCTNAME">
              GNode</span></b>
            </p>
          </div>
        </div>
      </div>
      <div class="SECT2">
        <h2 class="SECT2">
          <a name="Z34">Hash Tables</a>
        </h2>
        <p>
          <span class="STRUCTNAME">GHashTable</span> is a simple
          hash table implementation, providing an associative array
          with constant-time lookups. To use the hash table, you
          must provide a <span class="STRUCTNAME">GHashFunc</span>,
          which should return a positive integer when passed a hash
          key:
        </p>
        <table border="0" bgcolor="#E0E0E0" width="100%">
          <tr>
            <td>
<pre class="PROGRAMLISTING">
&#13;typedef guint (*GHashFunc) (gconstpointer key);&#13;
</pre>
            </td>
          </tr>
        </table>
        <p>
          Each returned <span class="STRUCTNAME">guint</span>
          (modulus the size of the table) corresponds to a "slot"
          or "bucket" in the hash; <span class="STRUCTNAME">
          GHashTable</span> handles collisions by storing a linked
          list of key-value pairs in each slot. Thus, the <span
          class="STRUCTNAME">guint</span> values returned by your
          <span class="STRUCTNAME">GHashFunc</span> must be fairly
          evenly distributed over the set of possible <span class= 
          "STRUCTNAME">guint</span> values, or the hash table will
          degenerate into a linked list. Your <span class= 
          "STRUCTNAME">GHashFunc</span> must also be fast, since it
          is used for every lookup.
        </p>
        <p>
          In addition to <span class="STRUCTNAME">GHashFunc</span>,
          a <span class="STRUCTNAME">GCompareFunc</span> is
          required to test keys for equality. Somewhat
          unpleasantly, <span class="STRUCTNAME">GHashTable</span>
          does not use <span class="STRUCTNAME">GCompareFunc</span>
          in the same way <span class="STRUCTNAME">GSList</span>
          and <span class="STRUCTNAME">GTree</span> do, although
          the function signature is the same. Here <span class= 
          "STRUCTNAME">GCompareFunc</span> is expected to be an
          equality operator, returning <span class="STRUCTNAME">
          TRUE</span> if its arguments are equal. It should <i
          class="EMPHASIS">not</i> be a <span class="STRUCTNAME">
          qsort()</span>-style comparison function. The key
          comparison function is used to find the correct key-value
          pair when hash collisions result in more than one pair in
          the same hash slot.
        </p>
        <p>
          To create and destroy a <span class="STRUCTNAME">
          GHashTable</span>, use the constructor and destructor
          listed in <a href="z29.html#FL-HASHNEW">Figure 29</a>.
          Remember that glib has no way of knowing how to destroy
          the data contained in your hash table; it only destroys
          the table itself.
        </p>
        <div class="FIGURE">
          <a name="FL-HASHNEW"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-HASHNEW.SYNOPSIS"></a>
            <table border="0" bgcolor="#E0E0E0" width="100%">
              <tr>
                <td>
<pre class="FUNCSYNOPSISINFO">
#include &lt;glib.h&gt;
</pre>
                </td>
              </tr>
            </table>
            <p>
              <code><code class="FUNCDEF">GHashTable* <tt class= 
              "FUNCTION">g_hash_table_new</tt></code>(GHashFunc <tt
              class="PARAMETER"><i>hash_func</i></tt>, GCompareFunc
              <tt class="PARAMETER"><i>
              key_compare_func</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">void <tt class=
              "FUNCTION">
              g_hash_table_destroy</tt></code>(GHashTable* <tt
              class="PARAMETER"><i>hash_table</i></tt>);</code>
            </p>
          </div>
          <p>
            <b>Figure 29. <span class="STRUCTNAME">
            GHashTable</span></b>
          </p>
        </div>
        <p>
          Ready-to-use hash and comparison functions are provided
          for the most common keys: integers, pointers, and
          strings. These are listed in <a href= 
          "z29.html#FL-HASHFUNCS">Figure 30</a>. The functions for
          integers accept a pointer to a <span class="STRUCTNAME">
          gint</span>, rather than the <span class="STRUCTNAME">
          gint</span> itself. If you pass <span class="STRUCTNAME">
          NULL</span> as the hash function argument to <tt class= 
          "FUNCTION">g_hash_table_new()</tt>, <tt class="FUNCTION">
          g_direct_hash()</tt> is used by default. If you pass
          <span class="STRUCTNAME">NULL</span> as the key equality
          function, then simple pointer comparison is used
          (equivalent to <span class="STRUCTNAME">
          g_direct_equal()</span>, but without a function call).
        </p>
        <div class="FIGURE">
          <a name="FL-HASHFUNCS"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-HASHFUNCS.SYNOPSIS"></a>
            <table border="0" bgcolor="#E0E0E0" width="100%">
              <tr>
                <td>
<pre class="FUNCSYNOPSISINFO">
#include &lt;glib.h&gt;
</pre>
                </td>
              </tr>
            </table>
            <p>
              <code><code class="FUNCDEF">guint <tt class=
              "FUNCTION">g_int_hash</tt></code>(gconstpointer <tt
              class="PARAMETER"><i>v</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gint <tt class=
              "FUNCTION">g_int_equal</tt></code>(gconstpointer <tt
              class="PARAMETER"><i>v1</i></tt>, gconstpointer <tt
              class="PARAMETER"><i>v2</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">guint <tt class=
              "FUNCTION">g_direct_hash</tt></code>(gconstpointer
              <tt class="PARAMETER"><i>v</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gint <tt class=
              "FUNCTION">g_direct_equal</tt></code>(gconstpointer
              <tt class="PARAMETER"><i>v1</i></tt>, gconstpointer
              <tt class="PARAMETER"><i>v2</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">guint <tt class=
              "FUNCTION">g_str_hash</tt></code>(gconstpointer <tt
              class="PARAMETER"><i>v</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gint <tt class=
              "FUNCTION">g_str_equal</tt></code>(gconstpointer <tt
              class="PARAMETER"><i>v1</i></tt>, gconstpointer <tt
              class="PARAMETER"><i>v2</i></tt>);</code>
            </p>
          </div>
          <p>
            <b>Figure 30. Pre-written hashes/comparisons</b>
          </p>
        </div>
        <p>
          Manipulating the hash is simple. The routines are
          summarized in <a href="z29.html#FL-HASHMANIP">Figure
          31</a>. Insertions do <i class="EMPHASIS">not</i> copy
          the key or value; these are entered into the table
          exactly as you provide them, overwriting any pre-existing
          key-value pair with the same key ("same" is defined by
          your hash and equality functions, remember). If this is a
          problem, you must do a lookup or remove before you
          insert. Be especially careful if you dynamically allocate
          keys or values.
        </p>
        <p>
          The simple <tt class="FUNCTION">
          g_hash_table_lookup()</tt> returns the value it finds
          associated with <span class="STRUCTNAME">key</span>, or
          <span class="STRUCTNAME">NULL</span> if there is no
          value. Sometimes this won't do. For example, <span class= 
          "STRUCTNAME">NULL</span> may be a valid value in itself.
          If you're using strings as keys, especially dynamically
          allocated strings, knowing that a key is in the table
          might not be enough; you might want to retrieve the exact
          <span class="STRUCTNAME">gchar*</span> the hash table is
          using to represent key <span class="STRUCTNAME">
          "foo"</span>. A second lookup function is provided for
          cases like these. <tt class="FUNCTION">
          g_hash_table_lookup_extended()</tt> returns <span class= 
          "STRUCTNAME">TRUE</span> if the lookup succeeded; if it
          returns <span class="STRUCTNAME">TRUE</span>, it places
          the key and value it found in the locations it's given.
        </p>
        <div class="FIGURE">
          <a name="FL-HASHMANIP"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-HASHMANIP.SYNOPSIS"></a>
            <table border="0" bgcolor="#E0E0E0" width="100%">
              <tr>
                <td>
<pre class="FUNCSYNOPSISINFO">
#include &lt;glib.h&gt;
</pre>
                </td>
              </tr>
            </table>
            <p>
              <code><code class="FUNCDEF">void <tt class=
              "FUNCTION">
              g_hash_table_insert</tt></code>(GHashTable* <tt
              class="PARAMETER"><i>hash_table</i></tt>, gpointer
              <tt class="PARAMETER"><i>key</i></tt>, gpointer <tt
              class="PARAMETER"><i>value</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">void <tt class=
              "FUNCTION">g_hash_table_remove</tt></code>(GHashTable
              * <tt class="PARAMETER"><i>hash_table</i></tt>,
              gconstpointer <tt class="PARAMETER"><i>
              key</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gpointer <tt class= 
              "FUNCTION">g_hash_table_lookup</tt></code>(GHashTable
              * <tt class="PARAMETER"><i>hash_table</i></tt>,
              gconstpointer <tt class="PARAMETER"><i>
              key</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gboolean <tt class= 
              "FUNCTION">
              g_hash_table_lookup_extended</tt></code>(GHashTable*
              <tt class="PARAMETER"><i>hash_table</i></tt>,
              gconstpointer <tt class="PARAMETER"><i>
              lookup_key</i></tt>, gpointer* <tt class="PARAMETER">
              <i>orig_key</i></tt>, gpointer* <tt class=
              "PARAMETER"><i>value</i></tt>);</code>
            </p>
          </div>
          <p>
            <b>Figure 31. Manipulating <span class="STRUCTNAME">
            GHashTable</span></b>
          </p>
        </div>
        <p>
          <span class="STRUCTNAME">GHashTable</span> keeps an
          internal array whose size is a prime number. It also
          keeps a count of the number of key-value pairs stored in
          the table. If the average number of pairs per available
          slot drops below 0.3 (or so), the array is made smaller;
          if it goes above 3, the array is made larger to reduce
          collisions. Resizing happens automatically whenever you
          insert or remove pairs from the table. This ensures the
          hash table's memory use is optimal. Unfortunately, it is
          inefficient to rebuild the hash table over and over if
          you're doing a large number of insertions or removals. To
          solve the problem, the hash table can be <i class= 
          "FIRSTTERM">frozen</i>, meaning that resizing is
          temporarily suppressed. When you're done adding and
          removing items, you simply <i class="FIRSTTERM">thaw</i>
          the table, resulting in a single optimal-size
          calculation. (Be careful though; a frozen table can end
          up with many hash collisions if you add large quantities
          of data. This should be fine as long as you thaw before
          you do any lookups.) The functions are in <a href= 
          "z29.html#FL-HASHFREEZE">Figure 32</a>.
        </p>
        <div class="FIGURE">
          <a name="FL-HASHFREEZE"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-HASHFREEZE.SYNOPSIS"></a>
            <table border="0"