GNode

A GNode is an N-way tree, implemented as a doubly linked list with parent and child lists. Thus, most list operations have analogues in the GNode API. You can also walk the tree in various ways. Here's the declaration for a node:

typedef struct _GNode GNode;

struct _GNode
{
  gpointer data;
  GNode   *next;
  GNode   *prev;
  GNode   *parent;
  GNode   *children;
};

There are macros to access GNode members, shown in Figure 21. As with GList, the data member is intended to be used directly. These macros return the next, prev, and children members respectively; they also check whether their argument is NULL before dereferencing it, and return NULL if it is.

#include <glib.h>

To create a node, the usual _new() function is provided (Figure 22). g_node_new() creates a childless and parentless node containing data. Typically g_node_new() is used only to create the root node; convenience macros are provided which automatically create new nodes as needed.

#include <glib.h>

To build a tree the fundamental operations shown in Figure 23 are used. Each operation returns the just-added node, for convenience when writing loops or recursing the tree. Unlike GList, it is safe to ignore the return value.

#include <glib.h>

The convenience macros shown in Figure 24 are implemented in terms of the fundamental operations. g_node_append() is analagous to g_node_prepend(); the rest take a data argument, automatically allocate a node for it, and call the corresponding basic operation.

#include <glib.h>

To remove a node from the tree, there are two functions shown in Figure 25. g_node_destroy() removes the node from a tree, destroying it and all its children. g_node_unlink() removes a node and makes it into a root node; i.e., it converts a subtree into an independent tree.

#include <glib.h>

There are two macros for detecting the top and bottom of a GNode tree, shown in Figure 26. A root node is defined as a node with no parent or siblings. A leaf node has no children.

#include <glib.h>

You can ask glib to report useful information about a GNode, including the number of nodes it contains, its root node, its depth, and the node containing a particular data pointer. These functions are shown in Figure 27.

GTraverseType was introduced earlier, with respect to GTree; here are the possible values for GNode:

• G_IN_ORDER first recurses the leftmost child of the node, then visits the node itself, then recurses the rest of the node's children. This isn't very useful; mostly it is intended for use with GTree.

• G_PRE_ORDER visits the current node, then recurses each child in turn.

• G_POST_ORDER recurses each child in order, then visits the current node.

• G_LEVEL_ORDER first visits the node itself; then each of the node's children; then the children of the children; then the children of the children of the children; and so on. That is, it visits each node of depth 0, then each node of depth 1, then each node of depth 2, etc.

GNode's tree-traversal functions have a GTraverseFlags argument. This is a bitfield used to change the nature of the traversal. Currently there are only three flags---you can visit only leaf nodes, only non-leaf nodes, or all nodes:

• G_TRAVERSE_LEAFS means to traverse only leaf nodes.

• G_TRAVERSE_NON_LEAFS means to traverse only non-leaf nodes.

• G_TRAVERSE_ALL is simply a shortcut for (G_TRAVERSE_LEAFS | G_TRAVERSE_NON_LEAFS).

#include <glib.h>

The remaining GNode functions are straightforward; most of them are simply operations on the node's list of children. Figure 28 lists them. There are two function typedefs unique to GNode:

typedef gboolean (*GNodeTraverseFunc) (GNode* node, gpointer data);
typedef void (*GNodeForeachFunc) (GNode* node, gpointer data);

These are called with a pointer to the node being visited, and the user data you provide. A GNodeTraverseFunc can return TRUE to stop whatever traversal is in progress; thus you can use GNodeTraverseFunc in combination with g_node_traverse() to search the tree by value.

#include <glib.h>