<refentry id="glib-Balanced-Binary-Trees"> <refmeta> <refentrytitle>Balanced Binary Trees</refentrytitle> <manvolnum>3</manvolnum> <refmiscinfo>GLIB Library</refmiscinfo> </refmeta> <refnamediv> <refname>Balanced Binary Trees</refname><refpurpose>a sorted collection of key/value pairs optimized for searching and traversing in order.</refpurpose> </refnamediv> <refsynopsisdiv><title>Synopsis</title> <synopsis> #include <glib.h> struct <link linkend="GTree">GTree</link>; <link linkend="GTree">GTree</link>* <link linkend="g-tree-new">g_tree_new</link> (<link linkend="GCompareFunc">GCompareFunc</link> key_compare_func); <link linkend="GTree">GTree</link>* <link linkend="g-tree-new-with-data">g_tree_new_with_data</link> (<link linkend="GCompareDataFunc">GCompareDataFunc</link> key_compare_func, <link linkend="gpointer">gpointer</link> key_compare_data); <link linkend="GTree">GTree</link>* <link linkend="g-tree-new-full">g_tree_new_full</link> (<link linkend="GCompareDataFunc">GCompareDataFunc</link> key_compare_func, <link linkend="gpointer">gpointer</link> key_compare_data, <link linkend="GDestroyNotify">GDestroyNotify</link> key_destroy_func, <link linkend="GDestroyNotify">GDestroyNotify</link> value_destroy_func); <link linkend="void">void</link> <link linkend="g-tree-insert">g_tree_insert</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="gpointer">gpointer</link> key, <link linkend="gpointer">gpointer</link> value); <link linkend="void">void</link> <link linkend="g-tree-replace">g_tree_replace</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="gpointer">gpointer</link> key, <link linkend="gpointer">gpointer</link> value); <link linkend="gint">gint</link> <link linkend="g-tree-nnodes">g_tree_nnodes</link> (<link linkend="GTree">GTree</link> *tree); <link linkend="gint">gint</link> <link linkend="g-tree-height">g_tree_height</link> (<link linkend="GTree">GTree</link> *tree); <link linkend="gpointer">gpointer</link> <link linkend="g-tree-lookup">g_tree_lookup</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> key); <link linkend="gboolean">gboolean</link> <link linkend="g-tree-lookup-extended">g_tree_lookup_extended</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> lookup_key, <link linkend="gpointer">gpointer</link> *orig_key, <link linkend="gpointer">gpointer</link> *value); <link linkend="void">void</link> <link linkend="g-tree-foreach">g_tree_foreach</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="GTraverseFunc">GTraverseFunc</link> func, <link linkend="gpointer">gpointer</link> user_data); <link linkend="void">void</link> <link linkend="g-tree-traverse">g_tree_traverse</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="GTraverseFunc">GTraverseFunc</link> traverse_func, <link linkend="GTraverseType">GTraverseType</link> traverse_type, <link linkend="gpointer">gpointer</link> user_data); <link linkend="gboolean">gboolean</link> (<link linkend="GTraverseFunc">*GTraverseFunc</link>) (<link linkend="gpointer">gpointer</link> key, <link linkend="gpointer">gpointer</link> value, <link linkend="gpointer">gpointer</link> data); enum <link linkend="GTraverseType">GTraverseType</link>; <link linkend="gpointer">gpointer</link> <link linkend="g-tree-search">g_tree_search</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="GCompareFunc">GCompareFunc</link> search_func, <link linkend="gconstpointer">gconstpointer</link> user_data); <link linkend="void">void</link> <link linkend="g-tree-remove">g_tree_remove</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> key); <link linkend="void">void</link> <link linkend="g-tree-steal">g_tree_steal</link> (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> key); <link linkend="void">void</link> <link linkend="g-tree-destroy">g_tree_destroy</link> (<link linkend="GTree">GTree</link> *tree); </synopsis> </refsynopsisdiv> <refsect1> <title>Description</title> <para> The <link linkend="GTree"><type>GTree</type></link> structure and its associated functions provide a sorted collection of key/value pairs optimized for searching and traversing in order. </para> <para> To create a new <link linkend="GTree"><type>GTree</type></link> use <link linkend="g-tree-new"><function>g_tree_new()</function></link>. </para> <para> To insert a key/value pair into a <link linkend="GTree"><type>GTree</type></link> use <link linkend="g-tree-insert"><function>g_tree_insert()</function></link>. </para> <para> To lookup the value corresponding to a given key, use <link linkend="g-tree-lookup"><function>g_tree_lookup()</function></link> and <link linkend="g-tree-lookup-extended"><function>g_tree_lookup_extended()</function></link>. </para> <para> To find out the number of nodes in a <link linkend="GTree"><type>GTree</type></link>, use <link linkend="g-tree-nnodes"><function>g_tree_nnodes()</function></link>. To get the height of a <link linkend="GTree"><type>GTree</type></link>, use <link linkend="g-tree-height"><function>g_tree_height()</function></link>. </para> <para> To traverse a <link linkend="GTree"><type>GTree</type></link>, calling a function for each node visited in the traversal, use <link linkend="g-tree-foreach"><function>g_tree_foreach()</function></link>. </para> <para> To remove a key/value pair use <link linkend="g-tree-remove"><function>g_tree_remove()</function></link>. </para> <para> To destroy a <link linkend="GTree"><type>GTree</type></link>, use <link linkend="g-tree-destroy"><function>g_tree_destroy()</function></link>. </para> </refsect1> <refsect1> <title>Details</title> <refsect2> <title><anchor id="GTree"/>struct GTree</title> <indexterm><primary>GTree</primary></indexterm><programlisting>struct GTree;</programlisting> <para> The <structname>GTree</structname> struct is an opaque data structure representing a <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It should be accessed only by using the following functions. </para></refsect2> <refsect2> <title><anchor id="g-tree-new"/>g_tree_new ()</title> <indexterm><primary>g_tree_new</primary></indexterm><programlisting><link linkend="GTree">GTree</link>* g_tree_new (<link linkend="GCompareFunc">GCompareFunc</link> key_compare_func);</programlisting> <para> Creates a new <link linkend="GTree"><type>GTree</type></link>.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>key_compare_func</parameter> :</term> <listitem><simpara> the function used to order the nodes in the <link linkend="GTree"><type>GTree</type></link>. It should return values similar to the standard <link linkend="strcmp"><function>strcmp()</function></link> function - 0 if the two arguments are equal, a negative value if the first argument comes before the second, or a positive value if the first argument comes after the second. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> a new <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-new-with-data"/>g_tree_new_with_data ()</title> <indexterm><primary>g_tree_new_with_data</primary></indexterm><programlisting><link linkend="GTree">GTree</link>* g_tree_new_with_data (<link linkend="GCompareDataFunc">GCompareDataFunc</link> key_compare_func, <link linkend="gpointer">gpointer</link> key_compare_data);</programlisting> <para> Creates a new <link linkend="GTree"><type>GTree</type></link> with a comparison function that accepts user data. See <link linkend="g-tree-new"><function>g_tree_new()</function></link> for more details.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>key_compare_func</parameter> :</term> <listitem><simpara> <link linkend="qsort"><function>qsort()</function></link>-style comparison function. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key_compare_data</parameter> :</term> <listitem><simpara> data to pass to comparison function. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> a new <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-new-full"/>g_tree_new_full ()</title> <indexterm><primary>g_tree_new_full</primary></indexterm><programlisting><link linkend="GTree">GTree</link>* g_tree_new_full (<link linkend="GCompareDataFunc">GCompareDataFunc</link> key_compare_func, <link linkend="gpointer">gpointer</link> key_compare_data, <link linkend="GDestroyNotify">GDestroyNotify</link> key_destroy_func, <link linkend="GDestroyNotify">GDestroyNotify</link> value_destroy_func);</programlisting> <para> Creates a new <link linkend="GTree"><type>GTree</type></link> like <link linkend="g-tree-new"><function>g_tree_new()</function></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="GTree"><type>GTree</type></link>.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>key_compare_func</parameter> :</term> <listitem><simpara> <link linkend="qsort"><function>qsort()</function></link>-style comparison function. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key_compare_data</parameter> :</term> <listitem><simpara> data to pass to comparison function. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key_destroy_func</parameter> :</term> <listitem><simpara> a function to free the memory allocated for the key used when removing the entry from the <link linkend="GTree"><type>GTree</type></link> or <literal>NULL</literal> if you don't want to supply such a function. </simpara></listitem></varlistentry> <varlistentry><term><parameter>value_destroy_func</parameter> :</term> <listitem><simpara> a function to free the memory allocated for the value used when removing the entry from the <link linkend="GTree"><type>GTree</type></link> or <literal>NULL</literal> if you don't want to supply such a function. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> a new <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-insert"/>g_tree_insert ()</title> <indexterm><primary>g_tree_insert</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_insert (<link linkend="GTree">GTree</link> *tree, <link linkend="gpointer">gpointer</link> key, <link linkend="gpointer">gpointer</link> value);</programlisting> <para> Inserts a key/value pair into a <link linkend="GTree"><type>GTree</type></link>. If the given key already exists in the <link linkend="GTree"><type>GTree</type></link> its corresponding value is set to the new value. If you supplied a value_destroy_func when creating the <link linkend="GTree"><type>GTree</type></link>, the old value is freed using that function. If you supplied a <parameter>key_destroy_func</parameter> when creating the <link linkend="GTree"><type>GTree</type></link>, the passed key is freed using that function. </para> <para> The tree is automatically 'balanced' as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key</parameter> :</term> <listitem><simpara> the key to insert. </simpara></listitem></varlistentry> <varlistentry><term><parameter>value</parameter> :</term> <listitem><simpara> the value corresponding to the key. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-replace"/>g_tree_replace ()</title> <indexterm><primary>g_tree_replace</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_replace (<link linkend="GTree">GTree</link> *tree, <link linkend="gpointer">gpointer</link> key, <link linkend="gpointer">gpointer</link> value);</programlisting> <para> Inserts a new key and value into a <link linkend="GTree"><type>GTree</type></link> similar to <link linkend="g-tree-insert"><function>g_tree_insert()</function></link>. The difference is that if the key already exists in the <link linkend="GTree"><type>GTree</type></link>, it gets replaced by the new key. If you supplied a <parameter>value_destroy_func</parameter> when creating the <link linkend="GTree"><type>GTree</type></link>, the old value is freed using that function. If you supplied a <parameter>key_destroy_func</parameter> when creating the <link linkend="GTree"><type>GTree</type></link>, the old key is freed using that function. </para> <para> The tree is automatically 'balanced' as new key/value pairs are added, so that the distance from the root to every leaf is as small as possible.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key</parameter> :</term> <listitem><simpara> the key to insert. </simpara></listitem></varlistentry> <varlistentry><term><parameter>value</parameter> :</term> <listitem><simpara> the value corresponding to the key. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-nnodes"/>g_tree_nnodes ()</title> <indexterm><primary>g_tree_nnodes</primary></indexterm><programlisting><link linkend="gint">gint</link> g_tree_nnodes (<link linkend="GTree">GTree</link> *tree);</programlisting> <para> Gets the number of nodes in a <link linkend="GTree"><type>GTree</type></link>.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> the number of nodes in the <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-height"/>g_tree_height ()</title> <indexterm><primary>g_tree_height</primary></indexterm><programlisting><link linkend="gint">gint</link> g_tree_height (<link linkend="GTree">GTree</link> *tree);</programlisting> <para> Gets the height of a <link linkend="GTree"><type>GTree</type></link>. </para> <para> If the <link linkend="GTree"><type>GTree</type></link> contains no nodes, the height is 0. If the <link linkend="GTree"><type>GTree</type></link> contains only one root node the height is 1. If the root node has children the height is 2, etc.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> the height of the <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-lookup"/>g_tree_lookup ()</title> <indexterm><primary>g_tree_lookup</primary></indexterm><programlisting><link linkend="gpointer">gpointer</link> g_tree_lookup (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> key);</programlisting> <para> Gets the value corresponding to the given key. Since a <link linkend="GTree"><type>GTree</type></link> is automatically balanced as key/value pairs are added, key lookup is very fast.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key</parameter> :</term> <listitem><simpara> the key to look up. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> the value corresponding to the key. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-lookup-extended"/>g_tree_lookup_extended ()</title> <indexterm><primary>g_tree_lookup_extended</primary></indexterm><programlisting><link linkend="gboolean">gboolean</link> g_tree_lookup_extended (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> lookup_key, <link linkend="gpointer">gpointer</link> *orig_key, <link linkend="gpointer">gpointer</link> *value);</programlisting> <para> Looks up a key in the <link linkend="GTree"><type>GTree</type></link>, returning the original key and the associated value and a <link linkend="gboolean"><type>gboolean</type></link> which is <literal>TRUE</literal> if the key was found. This is useful if you need to free the memory allocated for the original key, for example before calling <link linkend="g-tree-remove"><function>g_tree_remove()</function></link>.</para> <variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>lookup_key</parameter> :</term> <listitem><simpara> the key to look up. </simpara></listitem></varlistentry> <varlistentry><term><parameter>orig_key</parameter> :</term> <listitem><simpara> returns the original key. </simpara></listitem></varlistentry> <varlistentry><term><parameter>value</parameter> :</term> <listitem><simpara> returns the value associated with the key. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> <literal>TRUE</literal> if the key was found in the <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-foreach"/>g_tree_foreach ()</title> <indexterm><primary>g_tree_foreach</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_foreach (<link linkend="GTree">GTree</link> *tree, <link linkend="GTraverseFunc">GTraverseFunc</link> func, <link linkend="gpointer">gpointer</link> user_data);</programlisting> <para> Calls the given function for each of the key/value pairs in the <link linkend="GTree"><type>GTree</type></link>. The function is passed the key and value of each pair, and the given <parameter>data</parameter> parameter. The tree is traversed in sorted order. </para> <para> The tree may not be modified while iterating over it (you can't add/remove items). To remove all items matching a predicate, you need to add each item to a list in your <link linkend="GTraverseFunc"><type>GTraverseFunc</type></link> as you walk over the tree, then walk the list and remove each item.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>func</parameter> :</term> <listitem><simpara> the function to call for each node visited. If this function returns <literal>TRUE</literal>, the traversal is stopped. </simpara></listitem></varlistentry> <varlistentry><term><parameter>user_data</parameter> :</term> <listitem><simpara> user data to pass to the function. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-traverse"/>g_tree_traverse ()</title> <indexterm role="deprecated"><primary>g_tree_traverse</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_traverse (<link linkend="GTree">GTree</link> *tree, <link linkend="GTraverseFunc">GTraverseFunc</link> traverse_func, <link linkend="GTraverseType">GTraverseType</link> traverse_type, <link linkend="gpointer">gpointer</link> user_data);</programlisting> <warning><para><literal>g_tree_traverse</literal> is deprecated and should not be used in newly-written code. The order of a balanced tree is somewhat arbitrary. If you just want to visit all nodes in sorted order, use <link linkend="g-tree-foreach"><function>g_tree_foreach()</function></link> instead. If you really need to visit nodes in a different order, consider using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.</para></warning> <para> Calls the given function for each node in the <link linkend="GTree"><type>GTree</type></link>.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>traverse_func</parameter> :</term> <listitem><simpara> the function to call for each node visited. If this function returns <literal>TRUE</literal>, the traversal is stopped. </simpara></listitem></varlistentry> <varlistentry><term><parameter>traverse_type</parameter> :</term> <listitem><simpara> the order in which nodes are visited, one of <literal>G_IN_ORDER</literal>, <literal>G_PRE_ORDER</literal> and <literal>G_POST_ORDER</literal>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>user_data</parameter> :</term> <listitem><simpara> user data to pass to the function. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="GTraverseFunc"/>GTraverseFunc ()</title> <indexterm><primary>GTraverseFunc</primary></indexterm><programlisting><link linkend="gboolean">gboolean</link> (*GTraverseFunc) (<link linkend="gpointer">gpointer</link> key, <link linkend="gpointer">gpointer</link> value, <link linkend="gpointer">gpointer</link> data);</programlisting> <para> Specifies the type of function passed to <link linkend="g-tree-traverse"><function>g_tree_traverse()</function></link>. It is passed the key and value of each node, together with the <parameter>user_data</parameter> parameter passed to <link linkend="g-tree-traverse"><function>g_tree_traverse()</function></link>. If the function returns <literal>TRUE</literal>, the traversal is stopped. </para><variablelist role="params"> <varlistentry><term><parameter>key</parameter> :</term> <listitem><simpara>a key of a <link linkend="GTree"><type>GTree</type></link> node. </simpara></listitem></varlistentry> <varlistentry><term><parameter>value</parameter> :</term> <listitem><simpara>the value corresponding to the key. </simpara></listitem></varlistentry> <varlistentry><term><parameter>data</parameter> :</term> <listitem><simpara>user data passed to <link linkend="g-tree-traverse"><function>g_tree_traverse()</function></link>. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara><literal>TRUE</literal> to stop the traversal. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="GTraverseType"/>enum GTraverseType</title> <indexterm><primary>GTraverseType</primary></indexterm><programlisting>typedef enum { G_IN_ORDER, G_PRE_ORDER, G_POST_ORDER, G_LEVEL_ORDER } GTraverseType; </programlisting> <para> Specifies the type of traveral performed by <link linkend="g-tree-traverse"><function>g_tree_traverse()</function></link>, <link linkend="g-node-traverse"><function>g_node_traverse()</function></link> and <link linkend="g-node-find"><function>g_node_find()</function></link>. </para><variablelist role="enum"> <varlistentry> <term><literal>G_IN_ORDER</literal></term> <listitem><simpara>vists a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function. </simpara></listitem> </varlistentry> <varlistentry> <term><literal>G_PRE_ORDER</literal></term> <listitem><simpara>visits a node, then its children. </simpara></listitem> </varlistentry> <varlistentry> <term><literal>G_POST_ORDER</literal></term> <listitem><simpara>visits the node's children, then the node itself. </simpara></listitem> </varlistentry> <varlistentry> <term><literal>G_LEVEL_ORDER</literal></term> <listitem><simpara>is not implemented for <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Trees</link>. For <link linkend="glib-N-ary-Trees">N-ary Trees</link>, it vists the root node first, then its children, then its grandchildren, and so on. Note that this is less efficient than the other orders. </simpara></listitem> </varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-search"/>g_tree_search ()</title> <indexterm><primary>g_tree_search</primary></indexterm><programlisting><link linkend="gpointer">gpointer</link> g_tree_search (<link linkend="GTree">GTree</link> *tree, <link linkend="GCompareFunc">GCompareFunc</link> search_func, <link linkend="gconstpointer">gconstpointer</link> user_data);</programlisting> <para> Searches a <link linkend="GTree"><type>GTree</type></link> using <parameter>search_func</parameter>. </para> <para> The <parameter>search_func</parameter> is called with a pointer to the key of a key/value pair in the tree, and the passed in <parameter>user_data</parameter>. If <parameter>search_func</parameter> returns 0 for a key/value pair, then <link linkend="g-tree-search-func"><function>g_tree_search_func()</function></link> will return the value of that pair. If <parameter>search_func</parameter> returns -1, searching will proceed among the key/value pairs that have a smaller key; if <parameter>search_func</parameter> returns 1, searching will proceed among the key/value pairs that have a larger key.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>search_func</parameter> :</term> <listitem><simpara> a function used to search the <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>user_data</parameter> :</term> <listitem><simpara> the data passed as the second argument to the <parameter>search_func</parameter> function. </simpara></listitem></varlistentry> <varlistentry><term><emphasis>Returns</emphasis> :</term><listitem><simpara> the value corresponding to the found key, or <literal>NULL</literal> if the key was not found. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-remove"/>g_tree_remove ()</title> <indexterm><primary>g_tree_remove</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_remove (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> key);</programlisting> <para> Removes a key/value pair from a <link linkend="GTree"><type>GTree</type></link>. </para> <para> If the <link linkend="GTree"><type>GTree</type></link> was created using <link linkend="g-tree-new-full"><function>g_tree_new_full()</function></link>, the key and value are freed using the supplied destroy functions, otherwise you have to make sure that any dynamically allocated values are freed yourself.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key</parameter> :</term> <listitem><simpara> the key to remove. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-steal"/>g_tree_steal ()</title> <indexterm><primary>g_tree_steal</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_steal (<link linkend="GTree">GTree</link> *tree, <link linkend="gconstpointer">gconstpointer</link> key);</programlisting> <para> Removes a key and its associated value from a <link linkend="GTree"><type>GTree</type></link> without calling the key and value destroy functions.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> <varlistentry><term><parameter>key</parameter> :</term> <listitem><simpara> the key to remove. </simpara></listitem></varlistentry> </variablelist></refsect2> <refsect2> <title><anchor id="g-tree-destroy"/>g_tree_destroy ()</title> <indexterm><primary>g_tree_destroy</primary></indexterm><programlisting><link linkend="void">void</link> g_tree_destroy (<link linkend="GTree">GTree</link> *tree);</programlisting> <para> Destroys the <link linkend="GTree"><type>GTree</type></link>. If keys and/or values are dynamically allocated, you should either free them first or create the <link linkend="GTree"><type>GTree</type></link> using <link linkend="g-tree-new-full"><function>g_tree_new_full()</function></link>. In the latter case the destroy functions you supplied will be called on all keys and values before destroying the <link linkend="GTree"><type>GTree</type></link>.</para> <para> </para><variablelist role="params"> <varlistentry><term><parameter>tree</parameter> :</term> <listitem><simpara> a <link linkend="GTree"><type>GTree</type></link>. </simpara></listitem></varlistentry> </variablelist></refsect2> </refsect1> </refentry>