glib-Balanced-Binary-Trees.html [plain text]
<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Balanced Binary Trees</title><meta name="generator" content="DocBook XSL Stylesheets V1.65.1"><link rel="home" href="index.html" title="GLib Reference Manual"><link rel="up" href="glib-data-types.html" title="GLib Data Types"><link rel="previous" href="glib-Byte-Arrays.html" title="Byte Arrays"><link rel="next" href="glib-N-ary-Trees.html" title="N-ary Trees"><link rel="chapter" href="glib.html" title="GLib Overview"><link rel="refentry" href="glib-building.html" title="Compiling the GLib package"><link rel="refentry" href="glib-cross-compiling.html" title="Cross-compiling the GLib package"><link rel="refentry" href="glib-compiling.html" title="Compiling GLib Applications"><link rel="refentry" href="glib-running.html" title="Running GLib Applications"><link rel="refentry" href="glib-changes.html" title="Changes to GLib"><link rel="refentry" href="glib-resources.html" title="Mailing lists and bug reports"><link rel="chapter" href="glib-fundamentals.html" title="GLib Fundamentals"><link rel="refentry" href="glib-Basic-Types.html" title="Basic Types"><link rel="refentry" href="glib-Limits-of-Basic-Types.html" title="Limits of Basic Types"><link rel="refentry" href="glib-Standard-Macros.html" title="Standard Macros"><link rel="refentry" href="glib-Type-Conversion-Macros.html" title="Type Conversion Macros"><link rel="refentry" href="glib-Byte-Order-Macros.html" title="Byte Order Macros"><link rel="refentry" href="glib-Numerical-Definitions.html" title="Numerical Definitions"><link rel="refentry" href="glib-Miscellaneous-Macros.html" title="Miscellaneous Macros"><link rel="refentry" href="glib-Atomic-Operations.html" title="Atomic Operations"><link rel="chapter" href="glib-core.html" title="GLib Core Application Support"><link rel="refentry" href="glib-The-Main-Event-Loop.html" title="The Main Event Loop"><link rel="refentry" href="glib-Threads.html" title="
Threads"><link rel="refentry" href="glib-Thread-Pools.html" title="Thread Pools"><link rel="refentry" href="glib-Asynchronous-Queues.html" title="Asynchronous Queues"><link rel="refentry" href="glib-Dynamic-Loading-of-Modules.html" title="Dynamic Loading of Modules"><link rel="refentry" href="glib-Memory-Allocation.html" title="Memory Allocation"><link rel="refentry" href="glib-IO-Channels.html" title="IO Channels"><link rel="refentry" href="glib-Error-Reporting.html" title="Error Reporting"><link rel="refentry" href="glib-Warnings-and-Assertions.html" title="Message Output and Debugging Functions"><link rel="refentry" href="glib-Message-Logging.html" title="Message Logging"><link rel="chapter" href="glib-utilities.html" title="GLib Utilities"><link rel="refentry" href="glib-String-Utility-Functions.html" title="String Utility Functions"><link rel="refentry" href="glib-Character-Set-Conversion.html" title="Character Set Conversion"><link rel="refentry" href="glib-Unicode-Manipulation.html" title="Unicode Manipulation"><link rel="refentry" href="glib-I18N.html" title="Internationalization"><link rel="refentry" href="glib-Date-and-Time-Functions.html" title="Date and Time Functions"><link rel="refentry" href="glib-Random-Numbers.html" title="Random Numbers"><link rel="refentry" href="glib-Hook-Functions.html" title="Hook Functions"><link rel="refentry" href="glib-Miscellaneous-Utility-Functions.html" title="Miscellaneous Utility Functions"><link rel="refentry" href="glib-Lexical-Scanner.html" title="Lexical Scanner"><link rel="refentry" href="glib-Automatic-String-Completion.html" title="Automatic String Completion"><link rel="refentry" href="glib-Timers.html" title="Timers"><link rel="refentry" href="glib-Spawning-Processes.html" title="Spawning Processes"><link rel="refentry" href="glib-File-Utilities.html" title="File Utilities"><link rel="refentry" href="glib-Shell-related-Utilities.html" title="Shell-related Utilities"><link rel="refentry" href="glib-Glob-style-pattern-matching.html" title="Glob-style pattern matching"><link rel="refentry" href="glib-Simple-XML-Subset-Parser.html" title="Simple XML Subset Parser"><link rel="refentry" href="glib-Windows-Compatability-Functions.html" title="Windows Compatibility Functions"><link rel="chapter" href="glib-data-types.html" title="GLib Data Types"><link rel="refentry" href="glib-Memory-Chunks.html" title="Memory Chunks"><link rel="refentry" href="glib-Doubly-Linked-Lists.html" title="Doubly-Linked Lists"><link rel="refentry" href="glib-Singly-Linked-Lists.html" title="Singly-Linked Lists"><link rel="refentry" href="glib-Double-ended-Queues.html" title="Double-ended Queues"><link rel="refentry" href="glib-Trash-Stacks.html" title="Trash Stacks"><link rel="refentry" href="glib-Hash-Tables.html" title="Hash Tables"><link rel="refentry" href="glib-Strings.html" title="Strings"><link rel="refentry" href="glib-String-Chunks.html" title="String Chunks"><link rel="refentry" href="glib-Arrays.html" title="Arrays"><link rel="refentry" href="glib-Pointer-Arrays.html" title="Pointer Arrays"><link rel="refentry" href="glib-Byte-Arrays.html" title="Byte Arrays"><link rel="refentry" href="glib-Balanced-Binary-Trees.html" title="Balanced Binary Trees"><link rel="refentry" href="glib-N-ary-Trees.html" title="N-ary Trees"><link rel="refentry" href="glib-Quarks.html" title="Quarks"><link rel="refentry" href="glib-Keyed-Data-Lists.html" title="Keyed Data Lists"><link rel="refentry" href="glib-Datasets.html" title="Datasets"><link rel="refentry" href="glib-Relations-and-Tuples.html" title="Relations and Tuples"><link rel="refentry" href="glib-Caches.html" title="Caches"><link rel="refentry" href="glib-Memory-Allocators.html" title="Memory Allocators"><link rel="chapter" href="tools.html" title="GLib Tools"><link rel="refentry" href="glib-gettextize.html" title="glib-gettextize"><link rel="index" href="ix01.html" title="Index"><link rel="section" href="glib-Balanced-Binary-Trees.html#id3304923" title="Description"><link rel="section" href="glib-Balanced-Binary-Trees.html#id3305114" title="Details"><meta name="generator" content="GTK-Doc V1.2 (XML mode)"><link rel="stylesheet" href="style.css" type="text/css"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><table class="navigation" width="100%" summary="Navigation header" cellpadding="2" cellspacing="2"><tr valign="middle"><td><a accesskey="p" href="glib-Byte-Arrays.html"><img src="left.png" width="24" height="24" border="0" alt="Prev"></a></td><td><a accesskey="u" href="glib-data-types.html"><img src="up.png" width="24" height="24" border="0" alt="Up"></a></td><td><a accesskey="h" href="index.html"><img src="home.png" width="24" height="24" border="0" alt="Home"></a></td><th width="100%" align="center">GLib Reference Manual</th><td><a accesskey="n" href="glib-N-ary-Trees.html"><img src="right.png" width="24" height="24" border="0" alt="Next"></a></td></tr></table><div class="refentry" lang="en"><a name="glib-Balanced-Binary-Trees"></a><div class="titlepage"><div></div><div></div></div><div class="refnamediv"><h2><span class="refentrytitle">Balanced Binary Trees</span></h2><p>Balanced Binary Trees — a sorted collection of key/value pairs optimized for searching
and traversing in order.</p></div><div class="refsynopsisdiv"><h2>Synopsis</h2><pre class="synopsis">
#include <glib.h>
struct <a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>;
<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* <a href="glib-Balanced-Binary-Trees.html#g-tree-new">g_tree_new</a> (<a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> key_compare_func);
<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* <a href="glib-Balanced-Binary-Trees.html#g-tree-new-with-data">g_tree_new_with_data</a> (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data);
<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* <a href="glib-Balanced-Binary-Trees.html#g-tree-new-full">g_tree_new_full</a> (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data,
<a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> key_destroy_func,
<a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> value_destroy_func);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-insert">g_tree_insert</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> value);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-replace">g_tree_replace</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> value);
<a href="glib-Basic-Types.html#gint">gint</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-nnodes">g_tree_nnodes</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);
<a href="glib-Basic-Types.html#gint">gint</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-height">g_tree_height</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);
<a href="glib-Basic-Types.html#gpointer">gpointer</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-lookup">g_tree_lookup</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);
<a href="glib-Basic-Types.html#gboolean">gboolean</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-lookup-extended">g_tree_lookup_extended</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> lookup_key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> *orig_key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> *value);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-foreach">g_tree_foreach</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">GTraverseFunc</a> func,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> user_data);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-traverse">g_tree_traverse</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">GTraverseFunc</a> traverse_func,
<a href="glib-Balanced-Binary-Trees.html#GTraverseType">GTraverseType</a> traverse_type,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> user_data);
<a href="glib-Basic-Types.html#gboolean">gboolean</a> (<a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">*GTraverseFunc</a>) (<a href="glib-Basic-Types.html#gpointer">gpointer</a> key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> value,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> data);
enum <a href="glib-Balanced-Binary-Trees.html#GTraverseType">GTraverseType</a>;
<a href="glib-Basic-Types.html#gpointer">gpointer</a> <a href="glib-Balanced-Binary-Trees.html#g-tree-search">g_tree_search</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> search_func,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> user_data);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-remove">g_tree_remove</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-steal">g_tree_steal</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);
void <a href="glib-Balanced-Binary-Trees.html#g-tree-destroy">g_tree_destroy</a> (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);
</pre></div><div class="refsect1" lang="en"><a name="id3304923"></a><h2>Description</h2><p>
The <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> structure and its associated functions provide a sorted collection
of key/value pairs optimized for searching and traversing in order.
</p><p>
To create a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> use <a href="glib-Balanced-Binary-Trees.html#g-tree-new"><tt class="function">g_tree_new()</tt></a>.
</p><p>
To insert a key/value pair into a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> use <a href="glib-Balanced-Binary-Trees.html#g-tree-insert"><tt class="function">g_tree_insert()</tt></a>.
</p><p>
To lookup the value corresponding to a given key, use <a href="glib-Balanced-Binary-Trees.html#g-tree-lookup"><tt class="function">g_tree_lookup()</tt></a> and
<a href="glib-Balanced-Binary-Trees.html#g-tree-lookup-extended"><tt class="function">g_tree_lookup_extended()</tt></a>.
</p><p>
To find out the number of nodes in a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, use <a href="glib-Balanced-Binary-Trees.html#g-tree-nnodes"><tt class="function">g_tree_nnodes()</tt></a>.
To get the height of a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, use <a href="glib-Balanced-Binary-Trees.html#g-tree-height"><tt class="function">g_tree_height()</tt></a>.
</p><p>
To traverse a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, calling a function for each node visited in the
traversal, use <a href="glib-Balanced-Binary-Trees.html#g-tree-foreach"><tt class="function">g_tree_foreach()</tt></a>.
</p><p>
To remove a key/value pair use <a href="glib-Balanced-Binary-Trees.html#g-tree-remove"><tt class="function">g_tree_remove()</tt></a>.
</p><p>
To destroy a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, use <a href="glib-Balanced-Binary-Trees.html#g-tree-destroy"><tt class="function">g_tree_destroy()</tt></a>.
</p></div><div class="refsect1" lang="en"><a name="id3305114"></a><h2>Details</h2><div class="refsect2" lang="en"><a name="id3305119"></a><h3><a name="GTree"></a>struct GTree</h3><a class="indexterm" name="id3305130"></a><pre class="programlisting">struct GTree;</pre><p>
The <span class="structname">GTree</span> struct is an opaque data structure representing a
<a href="glib-Balanced-Binary-Trees.html" title="Balanced Binary Trees">Balanced Binary Tree</a>.
It should be accessed only by using the following functions.
</p></div><hr><div class="refsect2" lang="en"><a name="id3305159"></a><h3><a name="g-tree-new"></a>g_tree_new ()</h3><a class="indexterm" name="id3305169"></a><pre class="programlisting"><a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* g_tree_new (<a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> key_compare_func);</pre><p>
Creates a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>key_compare_func</tt></i> :</span></td><td> the function used to order the nodes in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
It should return values similar to the standard <tt class="function">strcmp()</tt> 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.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3305267"></a><h3><a name="g-tree-new-with-data"></a>g_tree_new_with_data ()</h3><a class="indexterm" name="id3305278"></a><pre class="programlisting"><a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* g_tree_new_with_data (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data);</pre><p>
Creates a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> with a comparison function that accepts user data.
See <a href="glib-Balanced-Binary-Trees.html#g-tree-new"><tt class="function">g_tree_new()</tt></a> for more details.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>key_compare_func</tt></i> :</span></td><td> <tt class="function">qsort()</tt>-style comparison function.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key_compare_data</tt></i> :</span></td><td> data to pass to comparison function.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3305399"></a><h3><a name="g-tree-new-full"></a>g_tree_new_full ()</h3><a class="indexterm" name="id3305409"></a><pre class="programlisting"><a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a>* g_tree_new_full (<a href="glib-Doubly-Linked-Lists.html#GCompareDataFunc">GCompareDataFunc</a> key_compare_func,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key_compare_data,
<a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> key_destroy_func,
<a href="glib-Datasets.html#GDestroyNotify">GDestroyNotify</a> value_destroy_func);</pre><p>
Creates a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> like <a href="glib-Balanced-Binary-Trees.html#g-tree-new"><tt class="function">g_tree_new()</tt></a> and allows to specify functions
to free the memory allocated for the key and value that get called when
removing the entry from the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>key_compare_func</tt></i> :</span></td><td> <tt class="function">qsort()</tt>-style comparison function.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key_compare_data</tt></i> :</span></td><td> data to pass to comparison function.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key_destroy_func</tt></i> :</span></td><td> a function to free the memory allocated for the key
used when removing the entry from the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> or <tt class="literal">NULL</tt> if you don't
want to supply such a function.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>value_destroy_func</tt></i> :</span></td><td> a function to free the memory allocated for the
value used when removing the entry from the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> or <tt class="literal">NULL</tt> if you
don't want to supply such a function.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> a new <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3305615"></a><h3><a name="g-tree-insert"></a>g_tree_insert ()</h3><a class="indexterm" name="id3305626"></a><pre class="programlisting">void g_tree_insert (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> value);</pre><p>
Inserts a key/value pair into a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>. If the given key already exists
in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> its corresponding value is set to the new value. If you
supplied a value_destroy_func when creating the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, the old value is
freed using that function. If you supplied a <i class="parameter"><tt>key_destroy_func</tt></i> when
creating the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, the passed key is freed using that function.
</p><p>
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.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key</tt></i> :</span></td><td> the key to insert.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>value</tt></i> :</span></td><td> the value corresponding to the key.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3305774"></a><h3><a name="g-tree-replace"></a>g_tree_replace ()</h3><a class="indexterm" name="id3305786"></a><pre class="programlisting">void g_tree_replace (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> value);</pre><p>
Inserts a new key and value into a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> similar to <a href="glib-Balanced-Binary-Trees.html#g-tree-insert"><tt class="function">g_tree_insert()</tt></a>.
The difference is that if the key already exists in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, it gets
replaced by the new key. If you supplied a <i class="parameter"><tt>value_destroy_func</tt></i> when
creating the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, the old value is freed using that function. If you
supplied a <i class="parameter"><tt>key_destroy_func</tt></i> when creating the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, the old key is
freed using that function.
</p><p>
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.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key</tt></i> :</span></td><td> the key to insert.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>value</tt></i> :</span></td><td> the value corresponding to the key.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3305951"></a><h3><a name="g-tree-nnodes"></a>g_tree_nnodes ()</h3><a class="indexterm" name="id3305961"></a><pre class="programlisting"><a href="glib-Basic-Types.html#gint">gint</a> g_tree_nnodes (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);</pre><p>
Gets the number of nodes in a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> the number of nodes in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306045"></a><h3><a name="g-tree-height"></a>g_tree_height ()</h3><a class="indexterm" name="id3306056"></a><pre class="programlisting"><a href="glib-Basic-Types.html#gint">gint</a> g_tree_height (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);</pre><p>
Gets the height of a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</p><p>
If the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> contains no nodes, the height is 0.
If the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> contains only one root node the height is 1.
If the root node has children the height is 2, etc.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> the height of the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306161"></a><h3><a name="g-tree-lookup"></a>g_tree_lookup ()</h3><a class="indexterm" name="id3306171"></a><pre class="programlisting"><a href="glib-Basic-Types.html#gpointer">gpointer</a> g_tree_lookup (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);</pre><p>
Gets the value corresponding to the given key. Since a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> is
automatically balanced as key/value pairs are added, key lookup is very
fast.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key</tt></i> :</span></td><td> the key to look up.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> the value corresponding to the key.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306271"></a><h3><a name="g-tree-lookup-extended"></a>g_tree_lookup_extended ()</h3><a class="indexterm" name="id3306282"></a><pre class="programlisting"><a href="glib-Basic-Types.html#gboolean">gboolean</a> g_tree_lookup_extended (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> lookup_key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> *orig_key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> *value);</pre><p>
Looks up a key in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>, returning the original key and the
associated value and a <a href="glib-Basic-Types.html#gboolean"><span class="type">gboolean</span></a> which is <tt class="literal">TRUE</tt> if the key was found. This
is useful if you need to free the memory allocated for the original key,
for example before calling <a href="glib-Balanced-Binary-Trees.html#g-tree-remove"><tt class="function">g_tree_remove()</tt></a>.</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>lookup_key</tt></i> :</span></td><td> the key to look up.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>orig_key</tt></i> :</span></td><td> returns the original key.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>value</tt></i> :</span></td><td> returns the value associated with the key.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> <tt class="literal">TRUE</tt> if the key was found in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306462"></a><h3><a name="g-tree-foreach"></a>g_tree_foreach ()</h3><a class="indexterm" name="id3306473"></a><pre class="programlisting">void g_tree_foreach (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">GTraverseFunc</a> func,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> user_data);</pre><p>
Calls the given function for each of the key/value pairs in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
The function is passed the key and value of each pair, and the given
<i class="parameter"><tt>data</tt></i> parameter. The tree is traversed in sorted order.
</p><p>
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 <a href="glib-Balanced-Binary-Trees.html#GTraverseFunc"><span class="type">GTraverseFunc</span></a> as you walk over
the tree, then walk the list and remove each item.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>func</tt></i> :</span></td><td> the function to call for each node visited. If this function
returns <tt class="literal">TRUE</tt>, the traversal is stopped.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>user_data</tt></i> :</span></td><td> user data to pass to the function.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306614"></a><h3><a name="g-tree-traverse"></a>g_tree_traverse ()</h3><a class="indexterm" name="id3306625"></a><pre class="programlisting">void g_tree_traverse (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Balanced-Binary-Trees.html#GTraverseFunc">GTraverseFunc</a> traverse_func,
<a href="glib-Balanced-Binary-Trees.html#GTraverseType">GTraverseType</a> traverse_type,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> user_data);</pre><div class="warning" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Warning</h3><p><tt class="literal">g_tree_traverse</tt> 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 <a href="glib-Balanced-Binary-Trees.html#g-tree-foreach"><tt class="function">g_tree_foreach()</tt></a>
instead. If you really need to visit nodes in a different order, consider
using an <a href="glib-N-ary-Trees.html" title="N-ary Trees">N-ary Tree</a>.</p></div><p>
Calls the given function for each node in the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>traverse_func</tt></i> :</span></td><td> the function to call for each node visited. If this
function returns <tt class="literal">TRUE</tt>, the traversal is stopped.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>traverse_type</tt></i> :</span></td><td> the order in which nodes are visited, one of <tt class="literal">G_IN_ORDER</tt>,
<tt class="literal">G_PRE_ORDER</tt> and <tt class="literal">G_POST_ORDER</tt>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>user_data</tt></i> :</span></td><td> user data to pass to the function.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306818"></a><h3><a name="GTraverseFunc"></a>GTraverseFunc ()</h3><a class="indexterm" name="id3306829"></a><pre class="programlisting"><a href="glib-Basic-Types.html#gboolean">gboolean</a> (*GTraverseFunc) (<a href="glib-Basic-Types.html#gpointer">gpointer</a> key,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> value,
<a href="glib-Basic-Types.html#gpointer">gpointer</a> data);</pre><p>
Specifies the type of function passed to <a href="glib-Balanced-Binary-Trees.html#g-tree-traverse"><tt class="function">g_tree_traverse()</tt></a>.
It is passed the key and value of each node, together with
the <i class="parameter"><tt>user_data</tt></i> parameter passed to <a href="glib-Balanced-Binary-Trees.html#g-tree-traverse"><tt class="function">g_tree_traverse()</tt></a>.
If the function returns <tt class="literal">TRUE</tt>, the traversal is stopped.
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>key</tt></i> :</span></td><td>a key of a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> node.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>value</tt></i> :</span></td><td>the value corresponding to the key.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>data</tt></i> :</span></td><td>user data passed to <a href="glib-Balanced-Binary-Trees.html#g-tree-traverse"><tt class="function">g_tree_traverse()</tt></a>.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td><tt class="literal">TRUE</tt> to stop the traversal.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3306988"></a><h3><a name="GTraverseType"></a>enum GTraverseType</h3><a class="indexterm" name="id3306998"></a><pre class="programlisting">typedef enum
{
G_IN_ORDER,
G_PRE_ORDER,
G_POST_ORDER,
G_LEVEL_ORDER
} GTraverseType;
</pre><p>
Specifies the type of traveral performed by <a href="glib-Balanced-Binary-Trees.html#g-tree-traverse"><tt class="function">g_tree_traverse()</tt></a>,
<a href="glib-N-ary-Trees.html#g-node-traverse"><tt class="function">g_node_traverse()</tt></a> and <a href="glib-N-ary-Trees.html#g-node-find"><tt class="function">g_node_find()</tt></a>.
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><tt class="literal">G_IN_ORDER</tt></span></td><td>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.
</td></tr><tr><td><span class="term"><tt class="literal">G_PRE_ORDER</tt></span></td><td>visits a node, then its children.
</td></tr><tr><td><span class="term"><tt class="literal">G_POST_ORDER</tt></span></td><td>visits the node's children, then the node itself.
</td></tr><tr><td><span class="term"><tt class="literal">G_LEVEL_ORDER</tt></span></td><td>is not implemented for
<a href="glib-Balanced-Binary-Trees.html" title="Balanced Binary Trees">Balanced Binary Trees</a>.
For <a href="glib-N-ary-Trees.html" title="N-ary Trees">N-ary Trees</a>, 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.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3307133"></a><h3><a name="g-tree-search"></a>g_tree_search ()</h3><a class="indexterm" name="id3307143"></a><pre class="programlisting"><a href="glib-Basic-Types.html#gpointer">gpointer</a> g_tree_search (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Doubly-Linked-Lists.html#GCompareFunc">GCompareFunc</a> search_func,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> user_data);</pre><p>
Searches a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> using <i class="parameter"><tt>search_func</tt></i>.
</p><p>
The <i class="parameter"><tt>search_func</tt></i> is called with a pointer to the key of a key/value pair in the tree,
and the passed in <i class="parameter"><tt>user_data</tt></i>. If <i class="parameter"><tt>search_func</tt></i> returns 0 for a key/value pair, then
<tt class="function">g_tree_search_func()</tt> will return the value of that pair. If <i class="parameter"><tt>search_func</tt></i> returns -1,
searching will proceed among the key/value pairs that have a smaller key; if <i class="parameter"><tt>search_func</tt></i>
returns 1, searching will proceed among the key/value pairs that have a larger key.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>search_func</tt></i> :</span></td><td> a function used to search the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>user_data</tt></i> :</span></td><td> the data passed as the second argument to the <i class="parameter"><tt>search_func</tt></i>
function.
</td></tr><tr><td><span class="term"><span class="emphasis"><em>Returns</em></span> :</span></td><td> the value corresponding to the found key, or <tt class="literal">NULL</tt> if the key
was not found.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3307341"></a><h3><a name="g-tree-remove"></a>g_tree_remove ()</h3><a class="indexterm" name="id3307352"></a><pre class="programlisting">void g_tree_remove (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);</pre><p>
Removes a key/value pair from a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</p><p>
If the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> was created using <a href="glib-Balanced-Binary-Trees.html#g-tree-new-full"><tt class="function">g_tree_new_full()</tt></a>, 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.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key</tt></i> :</span></td><td> the key to remove.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3307464"></a><h3><a name="g-tree-steal"></a>g_tree_steal ()</h3><a class="indexterm" name="id3307475"></a><pre class="programlisting">void g_tree_steal (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree,
<a href="glib-Basic-Types.html#gconstpointer">gconstpointer</a> key);</pre><p>
Removes a key and its associated value from a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> without calling
the key and value destroy functions.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr><tr><td><span class="term"><i class="parameter"><tt>key</tt></i> :</span></td><td> the key to remove.
</td></tr></tbody></table></div></div><hr><div class="refsect2" lang="en"><a name="id3307564"></a><h3><a name="g-tree-destroy"></a>g_tree_destroy ()</h3><a class="indexterm" name="id3307574"></a><pre class="programlisting">void g_tree_destroy (<a href="glib-Balanced-Binary-Trees.html#GTree">GTree</a> *tree);</pre><p>
Destroys the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>. If keys and/or values are dynamically allocated, you
should either free them first or create the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a> using <a href="glib-Balanced-Binary-Trees.html#g-tree-new-full"><tt class="function">g_tree_new_full()</tt></a>.
In the latter case the destroy functions you supplied will be called on
all keys and values before destroying the <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.</p><p>
</p><div class="variablelist"><table border="0"><col align="left" valign="top"><tbody><tr><td><span class="term"><i class="parameter"><tt>tree</tt></i> :</span></td><td> a <a href="glib-Balanced-Binary-Trees.html#GTree"><span class="type">GTree</span></a>.
</td></tr></tbody></table></div></div></div></div><table class="navigation" width="100%" summary="Navigation footer" cellpadding="2" cellspacing="0"><tr valign="middle"><td align="left"><a accesskey="p" href="glib-Byte-Arrays.html"><b><< Byte Arrays</b></a></td><td align="right"><a accesskey="n" href="glib-N-ary-Trees.html"><b>N-ary Trees >></b></a></td></tr></table></body></html>