z29.html

GTK+_ Gnome Application Development

static void 
append_foreach(gpointer data, gpointer user_data)
{
  AppendContext* ac = (AppendContext*) user_data;
  gchar* oldstring = (gchar*) data;

  efficient_append(&ac->list, &ac->list_end, 
                   g_strconcat(oldstring, ac->append, NULL));
}

GSList*
copy_with_append(GSList* list_of_strings, const gchar* append)
{
  AppendContext ac;

  ac.list = NULL;
  ac.list_end = NULL;
  ac.append = append;

  g_slist_foreach(list_of_strings, append_foreach, &ac);

  return ac.list;
}
</pre>
            </td>
          </tr>
        </table>
        <p>
          glib and GTK+ use the "function pointer and user data"
          idiom heavily. If you have functional programming
          experience, this is much like using lambda expressions to
          create a <i class="FIRSTTERM">closure</i>. (A closure
          combines a function with an <i class="FIRSTTERM">
          environment</i>---a set of name-value bindings. In this
          case the "environment" is the user data you pass to <tt
          class="FUNCTION">append_foreach()</tt>, and the "closure"
          is the combination of the function pointer and the user
          data.)
        </p>
        <div class="FIGURE">
          <a name="FL-LISTACCESS"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-LISTACCESS.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">GSList* <tt class= 
              "FUNCTION">g_slist_find</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>, gpointer <tt
              class="PARAMETER"><i>data</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_nth</tt></code>(GSList* <tt class= 
              "PARAMETER"><i>list</i></tt>, guint <tt class= 
              "PARAMETER"><i>n</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gpointer <tt class= 
              "FUNCTION">g_slist_nth_data</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>, guint <tt class= 
              "PARAMETER"><i>n</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_last</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">gint <tt class=
              "FUNCTION">g_slist_index</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>, gpointer <tt
              class="PARAMETER"><i>data</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">void <tt class=
              "FUNCTION">g_slist_foreach</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>, GFunc <tt class= 
              "PARAMETER"><i>func</i></tt>, gpointer <tt class= 
              "PARAMETER"><i>user_data</i></tt>);</code>
            </p>
          </div>
          <p>
            <b>Figure 14. Accessing data in a linked list</b>
          </p>
        </div>
        <p>
          There are some handy list-manipulation routines, listed
          in <a href="z29.html#FL-LISTMANIP">Figure 15</a>. With
          the exception of <tt class="FUNCTION">
          g_slist_copy()</tt>, all of these affect the lists
          in-place. Which means you must assign the return value
          and forget about the passed-in pointer, just as you do
          when adding or removing list elements. <tt class=
          "FUNCTION">g_slist_copy()</tt> returns a newly-allocated
          list, so you can continue to use both lists and must free
          both lists eventually.
        </p>
        <div class="FIGURE">
          <a name="FL-LISTMANIP"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-LISTMANIP.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_slist_length</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_concat</tt></code>(GSList* <tt
              class="PARAMETER"><i>list1</i></tt>, GSList* <tt
              class="PARAMETER"><i>list2</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_reverse</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_copy</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>);</code>
            </p>
          </div>
          <p>
            <b>Figure 15. Manipulating a linked list</b>
          </p>
        </div>
        <p>
          Finally, there are some provisions for sorted lists,
          shown in <a href="z29.html#FL-LISTSORTED">Figure 16</a>.
          To use these, you must write a <span class="STRUCTNAME">
          GCompareFunc</span>, which is just like the comparison
          function in the standard C <tt class="FUNCTION">
          qsort()</tt>. Using glib types, this becomes:
        </p>
        <table border="0" bgcolor="#E0E0E0" width="100%">
          <tr>
            <td>
<pre class="PROGRAMLISTING">
&#13;typedef gint (*GCompareFunc) (gconstpointer a, gconstpointer b);&#13;
</pre>
            </td>
          </tr>
        </table>
        <p>
          If <span class="STRUCTNAME">a &lt; b</span>, the function
          should return a negative value; if <span class=
          "STRUCTNAME">a &gt; b</span> a positive value; if <span
          class="STRUCTNAME">a == b</span> it should return 0.
        </p>
        <p>
          Once you have a comparison function, you can insert an
          element into an already-sorted list, or sort an entire
          list. Lists are sorted in ascending order. You can even
          recycle your <span class="STRUCTNAME">GCompareFunc</span>
          to find list elements, using <tt class="FUNCTION">
          g_slist_find_custom()</tt>. (A word of caution: <span
          class="STRUCTNAME">GCompareFunc</span> is used
          inconsistently in glib; sometimes it glib expects an
          equality predicate instead of a <tt class="FUNCTION">
          qsort()</tt>-style function. However, the usage is
          consistent within the list API.)
        </p>
        <p>
          Be careful with sorted lists; misusing them can rapidly
          become very inefficient. For example, <tt class=
          "FUNCTION">g_slist_insert_sorted()</tt> is an O(n)
          operation, but if you use it in a loop to insert multiple
          elements the loop runs in exponential time. It's better
          to simply prepend all your elements, then call <tt class= 
          "FUNCTION">g_slist_sort()</tt>.
        </p>
        <div class="FIGURE">
          <a name="FL-LISTSORTED"></a>
          <div class="FUNCSYNOPSIS">
            <a name="FL-LISTSORTED.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">GSList* <tt class= 
              "FUNCTION">g_slist_insert_sorted</tt></code>(GSList*
              <tt class="PARAMETER"><i>list</i></tt>, gpointer <tt
              class="PARAMETER"><i>data</i></tt>, GCompareFunc <tt
              class="PARAMETER"><i>func</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_sort</tt></code>(GSList* <tt
              class="PARAMETER"><i>list</i></tt>, GCompareFunc <tt
              class="PARAMETER"><i>func</i></tt>);</code>
            </p>
            <p>
              <code><code class="FUNCDEF">GSList* <tt class= 
              "FUNCTION">g_slist_find_custom</tt></code>(GSList*
              <tt class="PARAMETER"><i>list</i></tt>, gpointer <tt
              class="PARAMETER"><i>data</i></tt>, GCompareFunc <tt
              class="PARAMETER"><i>func</i></tt>);</code>
            </p>
          </div>
          <p>
            <b>Figure 16. Sorted lists</b>
          </p>
        </div>
      </div>
      <div class="SECT2">
        <h2 class="SECT2">
          <a name="Z31">Trees</a>
        </h2>
        <p>
          There are two different kinds of tree in glib; <span
          class="STRUCTNAME">GTree</span> is your basic balanced
          binary tree, useful to store key-value pairs sorted by
          key; <span class="STRUCTNAME">GNode</span> stores
          arbitrary tree-structured data, such as a parse tree or
          taxonomy.
        </p>
        <div class="SECT3">
          <h3 class="SECT3">
            <a name="Z32">GTree</a>
          </h3>
          <p>
            To create and destroy a <span class="STRUCTNAME">
            GTree</span>, use the constructor-destructor pair
            displayed in <a href="z29.html#FL-TREECONSTRUCT">Figure
            17</a>. <span class="STRUCTNAME">GCompareFunc</span> is
            the same <tt class="FUNCTION">qsort()</tt>-style
            comparison function described for <span class= 
            "STRUCTNAME">GSList</span>; in this case it's used to
            compare keys in the tree.
          </p>
          <div class="FIGURE">
            <a name="FL-TREECONSTRUCT"></a>
            <div class="FUNCSYNOPSIS">
              <a name="FL-TREECONSTRUCT.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">GTree* <tt class= 
                "FUNCTION">g_tree_new</tt></code>(GCompareFunc <tt
                class="PARAMETER"><i>
                key_compare_func</i></tt>);</code>
              </p>
              <p>
                <code><code class="FUNCDEF">void <tt class=
                "FUNCTION">g_tree_destroy</tt></code>(GTree* <tt
                class="PARAMETER"><i>tree</i></tt>);</code>
              </p>
            </div>
            <p>
              <b>Figure 17. Creating and destroying balanced binary
              trees</b>
            </p>
          </div>
          <p>
            Functions for manipulating the contents of the tree are
            shown in <a href="z29.html#FL-TREEMANIP">Figure 18</a>.
            All very straightforward; <tt class="FUNCTION">
            g_tree_insert()</tt> overwrites any existing value, so
            be careful if the existing value is your only pointer
            to a chunk of allocated memory. If <tt class=
            "FUNCTION">g_tree_lookup()</tt> fails to find the key,
            it returns <span class="STRUCTNAME">NULL</span>,
            otherwise it returns the associated value. Both keys
            and values have type <span class="STRUCTNAME">
            gpointer</span>, but the <tt class="FUNCTION">
            GPOINTER_TO_INT()</tt> and <tt class="FUNCTION">
            GPOINTER_TO_UINT()</tt> macros allow you to use
            integers instead.
          </p>
          <div class="FIGURE">
            <a name="FL-TREEMANIP"></a>
            <div class="FUNCSYNOPSIS">
              <a name="FL-TREEMANIP.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_tree_insert</tt></code>(GTree* <tt
                class="PARAMETER"><i>tree</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_tree_remove</tt></code>(GTree* <tt
                class="PARAMETER"><i>tree</i></tt>, gpointer <tt