Gtk+/Gnome Application Development - Data Structures

Gtk+/Gnome Application Development
Prev	Home	Next

GTree

To create and destroy a GTree, use the constructor-destructor pair displayed in Figure 17. GCompareFunc is the same qsort()-style comparison function described for GSList; in this case it's used to compare keys in the tree.

#include <glib.h>

GTree* g_tree_new(GCompareFunc key_compare_func);

void g_tree_destroy(GTree* tree);

Figure 17. Creating and destroying balanced binary trees

Functions for manipulating the contents of the tree are shown in Figure 18. All very straightforward; g_tree_insert() overwrites any existing value, so be careful if the existing value is your only pointer to a chunk of allocated memory. If g_tree_lookup() fails to find the key, it returns NULL, otherwise it returns the associated value. Both keys and values have type gpointer, but the GPOINTER_TO_INT() and GPOINTER_TO_UINT() macros allow you to use integers instead.

#include <glib.h>

void g_tree_insert(GTree* tree, gpointer key, gpointer value);

void g_tree_remove(GTree* tree, gpointer key);

gpointer g_tree_lookup(GTree* tree, gpointer key);

Figure 18. Manipulating GTree contents

There are two functions which give you an idea how large the tree is, shown in Figure 19.

#include <glib.h>

gint g_tree_nnodes(GTree* tree);

gint g_tree_height(GTree* tree);

Figure 19. Determining the size of a GTree

Using g_tree_traverse() (Figure 20) you can walk the entire tree. To use it, you provide a GTraverseFunc, which is passed each key-value pair and a data argument you give to g_tree_traverse(). Traversal continues as long as the GTraverseFunc returns FALSE; if it ever returns TRUE then traversal stops. You can use this to search the tree by value. Here is the definition of GTraverseFunc:

typedef gint (*GTraverseFunc)(gpointer key, gpointer value, gpointer data);

GTraverseType is an enumeration; there are four possible values. Here are their meanings with respect to GTree.

G_IN_ORDER first recurses the left child of the node (the "lower" key according to your GCompareFunc), then calls the traversal function on the key-value pair of the current node, then recurses the right child. This traversal is in order from lowest to highest, according to your GCompareFunc.
G_PRE_ORDER calls the traversal function on the key-value pair of the current node, then recurses the left child, then recurses the right child.
G_POST_ORDER recurses the left child, then recurses the right child, and finally calls the traversal function on the current node's key-value pair.
G_LEVEL_ORDER is only meaningful for GNode, it is not allowed with GTree.

#include <glib.h>

void g_tree_traverse(GTree* tree, GTraverseFunc traverse_func, GTraverseType traverse_type, gpointer data);

Figure 20. Traversing GTree