N-ary Trees
<!-- ##### SECTION Short_Description ##### -->
-
+trees of data with any number of branches.
<!-- ##### SECTION Long_Description ##### -->
<para>
-
+The #GNode struct and its associated functions provide a N-ary tree data
+structure, where nodes in the tree can contain arbitrary data.
+</para>
+<para>
+To create a new tree use g_node_new().
+</para>
+<para>
+To insert a node into a tree use g_node_insert(), g_node_insert_before(),
+g_node_append() and g_node_prepend().
+</para>
+<para>
+To create a new node and insert it into a tree use g_node_insert_data(),
+g_node_insert_data_before(), g_node_append_data() and g_node_prepend_data().
+</para>
+<para>
+To reverse the children of a node use g_node_reverse_children().
+</para>
+<para>
+To find a node use g_node_get_root(), g_node_find(), g_node_find_child(),
+g_node_child_index(), g_node_child_position(),
+g_node_first_child(), g_node_last_child(),
+g_node_nth_child(), g_node_first_sibling(), g_node_prev_sibling(),
+g_node_next_sibling() or g_node_last_sibling().
+</para>
+<para>
+To get information about a node or tree use G_NODE_IS_LEAF(),
+G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(), g_node_n_children(),
+g_node_is_ancestor() or g_node_max_height().
+</para>
+<para>
+To traverse a tree, calling a function for each node visited in the
+traversal, use g_node_traverse() or g_node_children_foreach().
+</para>
+<para>
+To remove a node or subtree from a tree use g_node_unlink() or
+g_node_destroy().
</para>
<!-- ##### SECTION See_Also ##### -->
<!-- ##### STRUCT GNode ##### -->
<para>
-
+The <structname>GNode</structname> struct represents one node in a
+<link linkend="glib-N-ary-Trees">N-ary Tree</link>.
+The <structfield>data</structfield> field contains the actual data of the node.
+The <structfield>next</structfield> and <structfield>prev</structfield>
+fields point to the node's siblings (a sibling is another <structname>GNode</structname> with the
+same parent).
+The <structfield>parent</structfield> field points to the parent of the <structname>GNode</structname>,
+or is %NULL if the <structname>GNode</structname> is the root of the tree.
+The <structfield>children</structfield> field points to the first child of the
+<structname>GNode</structname>. The other children are accessed by using the
+<structfield>next</structfield> pointer of each child.
</para>
@data:
<!-- ##### FUNCTION g_node_new ##### -->
<para>
-
+Creates a new #GNode containing the given data.
+Used to create the first node in a tree.
</para>
-@data:
-@Returns:
+@data: the data of the new node.
+@Returns: a new #GNode.
<!-- ##### FUNCTION g_node_copy ##### -->
<para>
+Recursively copies a #GNode (but does not deep-copy the data inside the nodes,
+see g_node_copy_deep() if you need that).
+</para>
+@node: a #GNode.
+@Returns: a new #GNode containing the same data pointers.
+
+
+<!-- ##### USER_FUNCTION GCopyFunc ##### -->
+<para>
+A function of this signature is used to copy the node data when doing a deep-copy
+of a tree.
</para>
-@node:
-@Returns:
+@src: A pointer to the data which should be copied.
+@data: Additional data.
+@Returns: A pointer to the copy.
+@Since: 2.4
-<!-- ##### FUNCTION g_node_insert ##### -->
+<!-- ##### FUNCTION g_node_copy_deep ##### -->
<para>
</para>
-@parent:
-@position:
@node:
+@copy_func:
+@data:
@Returns:
+<!-- ##### FUNCTION g_node_insert ##### -->
+<para>
+Inserts a #GNode beneath the parent at the given position.
+</para>
+
+@parent: the #GNode to place @node under.
+@position: the position to place @node at, with respect to its siblings.
+If position is -1, @node is inserted as the last child of @parent.
+@node: the #GNode to insert.
+@Returns: the inserted #GNode.
+
+
<!-- ##### FUNCTION g_node_insert_before ##### -->
<para>
+Inserts a #GNode beneath the parent before the given sibling.
+</para>
+
+@parent: the #GNode to place @node under.
+@sibling: the sibling #GNode to place @node before. If sibling is %NULL,
+the node is inserted as the last child of @parent.
+@node: the #GNode to insert.
+@Returns: the inserted #GNode.
+
+<!-- ##### FUNCTION g_node_insert_after ##### -->
+<para>
+Inserts a #GNode beneath the parent after the given sibling.
</para>
-@parent:
-@sibling:
-@node:
-@Returns:
+@parent: the #GNode to place @node under.
+@sibling: the sibling #GNode to place @node after. If sibling is %NULL,
+the node is inserted as the first child of @parent.
+@node: the #GNode to insert.
+@Returns: the inserted #GNode.
<!-- ##### MACRO g_node_append ##### -->
<para>
-
+Inserts a #GNode as the last child of the given parent.
</para>
-@parent:
-@node:
+@parent: the #GNode to place the new #GNode under.
+@node: the #GNode to insert.
+@Returns: the inserted #GNode.
<!-- ##### FUNCTION g_node_prepend ##### -->
<para>
-
+Inserts a #GNode as the first child of the given parent.
</para>
-@parent:
-@node:
-@Returns:
+@parent: the #GNode to place the new #GNode under.
+@node: the #GNode to insert.
+@Returns: the inserted #GNode.
<!-- ##### MACRO g_node_insert_data ##### -->
<para>
-
+Inserts a new #GNode at the given position.
</para>
-@parent:
-@position:
-@data:
+@parent: the #GNode to place the new #GNode under.
+@position: the position to place the new #GNode at.
+If position is -1, the new #GNode is inserted as the last child of @parent.
+@data: the data for the new #GNode.
+@Returns: the new #GNode.
<!-- ##### MACRO g_node_insert_data_before ##### -->
<para>
-
+Inserts a new #GNode before the given sibling.
</para>
-@parent:
-@sibling:
-@data:
+@parent: the #GNode to place the new #GNode under.
+@sibling: the sibling #GNode to place the new #GNode before.
+@data: the data for the new #GNode.
+@Returns: the new #GNode.
<!-- ##### MACRO g_node_append_data ##### -->
<para>
-
+Inserts a new #GNode as the last child of the given parent.
</para>
-@parent:
-@data:
+@parent: the #GNode to place the new #GNode under.
+@data: the data for the new #GNode.
+@Returns: the new #GNode.
<!-- ##### MACRO g_node_prepend_data ##### -->
<para>
-
+Inserts a new #GNode as the first child of the given parent.
</para>
-@parent:
-@data:
+@parent: the #GNode to place the new #GNode under.
+@data: the data for the new #GNode.
+@Returns: the new #GNode.
<!-- ##### FUNCTION g_node_reverse_children ##### -->
<para>
-
+Reverses the order of the children of a #GNode.
+(It doesn't change the order of the grandchildren.)
</para>
-@node:
+@node: a #GNode.
<!-- ##### FUNCTION g_node_traverse ##### -->
<para>
-
+Traverses a tree starting at the given root #GNode.
+It calls the given function for each node visited.
+The traversal can be halted at any point by returning %TRUE from @func.
</para>
-@root:
-@order:
-@flags:
-@max_depth:
-@func:
-@data:
+@root: the root #GNode of the tree to traverse.
+@order: the order in which nodes are visited - %G_IN_ORDER, %G_PRE_ORDER,
+%G_POST_ORDER, or %G_LEVEL_ORDER.
+@flags: which types of children are to be visited, one of %G_TRAVERSE_ALL,
+%G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
+@max_depth: the maximum depth of the traversal. Nodes below this
+depth will not be visited. If max_depth is -1 all nodes in the tree are
+visited. If depth is 1, only the root is visited. If depth is 2, the root
+and its children are visited. And so on.
+@func: the function to call for each visited #GNode.
+@data: user data to pass to the function.
<!-- ##### ENUM GTraverseFlags ##### -->
<para>
-
+Specifies which nodes are visited during several of the tree functions,
+including g_node_traverse() and g_node_find().
</para>
-@G_TRAVERSE_LEAFS:
-@G_TRAVERSE_NON_LEAFS:
-@G_TRAVERSE_ALL:
+@G_TRAVERSE_LEAFS: only leaf nodes should be visited.
+@G_TRAVERSE_NON_LEAFS: only non-leaf nodes should be visited.
+@G_TRAVERSE_ALL: all nodes should be visited.
@G_TRAVERSE_MASK:
<!-- ##### USER_FUNCTION GNodeTraverseFunc ##### -->
<para>
-
+Specifies the type of function passed to g_node_traverse().
+The function is called with each of the nodes visited, together with the
+user data passed to g_node_traverse().
+If the function returns %TRUE, then the traversal is stopped.
</para>
-@node:
-@data:
-@Returns:
+@node: a #GNode.
+@data: user data passed to g_node_traverse().
+@Returns: %TRUE to stop the traversal.
<!-- ##### FUNCTION g_node_children_foreach ##### -->
<para>
-
+Calls a function for each of the children of a #GNode.
+Note that it doesn't descend beneath the child nodes.
</para>
-@node:
-@flags:
-@func:
-@data:
+@node: a #GNode.
+@flags: which types of children are to be visited, one of %G_TRAVERSE_ALL,
+%G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
+@func: the function to call for each visited node.
+@data: user data to pass to the function.
<!-- ##### USER_FUNCTION GNodeForeachFunc ##### -->
<para>
-
+Specifies the type of function passed to g_node_children_foreach().
+The function is called with each child node, together with the user data
+passed to g_node_children_foreach().
</para>
-@node:
-@data:
+@node: a #GNode.
+@data: user data passed to g_node_children_foreach().
<!-- ##### FUNCTION g_node_get_root ##### -->
<para>
-
+Gets the root of a tree.
</para>
-@node:
-@Returns:
+@node: a #GNode.
+@Returns: the root of the tree.
<!-- ##### FUNCTION g_node_find ##### -->
<para>
-
+Finds a #GNode in a tree.
</para>
-@root:
-@order:
-@flags:
-@data:
-@Returns:
+@root: the root #GNode of the tree to search.
+@order: the order in which nodes are visited - %G_IN_ORDER, %G_PRE_ORDER,
+%G_POST_ORDER, or %G_LEVEL_ORDER.
+@flags: which types of children are to be searched, one of %G_TRAVERSE_ALL,
+%G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
+@data: the data to find.
+@Returns: the found #GNode, or %NULL if the data is not found.
<!-- ##### FUNCTION g_node_find_child ##### -->
<para>
-
+Finds the first child of a #GNode with the given data.
</para>
-@node:
-@flags:
-@data:
-@Returns:
+@node: a #GNode.
+@flags: which types of children are to be searched, one of %G_TRAVERSE_ALL,
+%G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
+@data: the data to find.
+@Returns: the found child #GNode, or %NULL if the data is not found.
<!-- ##### FUNCTION g_node_child_index ##### -->
<para>
-
+Gets the position of the first child of a #GNode which contains the given data.
</para>
-@node:
-@data:
-@Returns:
+@node: a #GNode.
+@data: the data to find.
+@Returns: the index of the child of @node which contains @data, or -1
+if the data is not found.
<!-- ##### FUNCTION g_node_child_position ##### -->
<para>
-
+Gets the position of a #GNode with respect to its siblings.
+@child must be a child of @node.
+The first child is numbered 0, the second 1, and so on.
</para>
-@node:
-@child:
-@Returns:
+@node: a #GNode.
+@child: a child of @node.
+@Returns: the position of @child with respect to its siblings.
<!-- ##### MACRO g_node_first_child ##### -->
<para>
-
+Gets the first child of a #GNode.
</para>
-@node:
+@node: a #GNode.
+@Returns: the last child of @node, or %NULL if @node is %NULL or has no children.
<!-- ##### FUNCTION g_node_last_child ##### -->
<para>
-
+Gets the last child of a #GNode.
</para>
-@node:
-@Returns:
+@node: a #GNode (must not be %NULL).
+@Returns: the last child of @node, or %NULL if @node has no children.
<!-- ##### FUNCTION g_node_nth_child ##### -->
<para>
-
+Gets a child of a #GNode, using the given index.
+The first child is at index 0. If the index is too big, %NULL is returned.
</para>
-@node:
-@n:
-@Returns:
+@node: a #GNode.
+@n: the index of the desired child.
+@Returns: the child of @node at index @n.
<!-- ##### FUNCTION g_node_first_sibling ##### -->
<para>
-
+Gets the first sibling of a #GNode.
+This could possibly be the node itself.
</para>
-@node:
-@Returns:
+@node: a #GNode.
+@Returns: the first sibling of @node.
<!-- ##### MACRO g_node_next_sibling ##### -->
<para>
-
+Gets the next sibling of a #GNode.
</para>
-@node:
+@node: a #GNode.
+@Returns: the next sibling of @node, or %NULL if @node is %NULL.
<!-- ##### MACRO g_node_prev_sibling ##### -->
<para>
-
+Gets the previous sibling of a #GNode.
</para>
-@node:
+@node: a #GNode.
+@Returns: the previous sibling of @node, or %NULL if @node is %NULL.
<!-- ##### FUNCTION g_node_last_sibling ##### -->
<para>
-
+Gets the last sibling of a #GNode.
+This could possibly be the node itself.
</para>
-@node:
-@Returns:
+@node: a #GNode.
+@Returns: the last sibling of @node.
<!-- ##### MACRO G_NODE_IS_LEAF ##### -->
<para>
-
+Returns %TRUE if a #GNode is a leaf node.
</para>
-@node:
+@node: a #GNode.
+@Returns: %TRUE if the #GNode is a leaf node (i.e. it has no children).
<!-- ##### MACRO G_NODE_IS_ROOT ##### -->
<para>
-
+Returns %TRUE if a #GNode is the root of a tree.
</para>
-@node:
+@node: a #GNode.
+@Returns: %TRUE if the #GNode is the root of a tree (i.e. it has no parent
+or siblings).
<!-- ##### FUNCTION g_node_depth ##### -->
<para>
-
+Gets the depth of a #GNode.
+</para>
+<para>
+If @node is %NULL the depth is 0.
+The root node has a depth of 1.
+For the children of the root node the depth is 2. And so on.
</para>
-@node:
-@Returns:
+@node: a #GNode.
+@Returns: the depth of the #GNode.
<!-- ##### FUNCTION g_node_n_nodes ##### -->
<para>
-
+Gets the number of nodes in a tree.
</para>
-@root:
-@flags:
-@Returns:
+@root: a #GNode.
+@flags: which types of children are to be counted, one of %G_TRAVERSE_ALL,
+%G_TRAVERSE_LEAFS and %G_TRAVERSE_NON_LEAFS.
+@Returns: the number of nodes in the tree.
<!-- ##### FUNCTION g_node_n_children ##### -->
<para>
-
+Gets the number of children of a #GNode.
</para>
-@node:
-@Returns:
+@node: a #GNode.
+@Returns: the number of children of @node.
<!-- ##### FUNCTION g_node_is_ancestor ##### -->
<para>
-
+Returns %TRUE if @node is an ancestor of @descendant.
+This is true if node is the parent of @descendant, or if node is the
+grandparent of @descendant etc.
</para>
-@node:
-@descendant:
-@Returns:
+@node: a #GNode.
+@descendant: a #GNode.
+@Returns: %TRUE if @node is an ancestor of @descendant.
<!-- ##### FUNCTION g_node_max_height ##### -->
<para>
-
+Gets the maximum height of all branches beneath a #GNode.
+This is the maximum distance from the #GNode to all leaf nodes.
+</para>
+<para>
+If @root is %NULL, 0 is returned. If @root has no children, 1 is returned.
+If @root has children, 2 is returned. And so on.
</para>
-@root:
-@Returns:
+@root: a #GNode.
+@Returns: the maximum height of the tree beneath @root.
<!-- ##### FUNCTION g_node_unlink ##### -->
<para>
-
+Unlinks a #GNode from a tree, resulting in two separate trees.
</para>
-@node:
+@node: the #GNode to unlink, which becomes the root of a new tree.
<!-- ##### FUNCTION g_node_destroy ##### -->
<para>
-
+Removes the #GNode and its children from the tree, freeing any memory
+allocated.
</para>
-@root:
+@root: the root of the tree/subtree to destroy.
<!-- ##### FUNCTION g_node_push_allocator ##### -->
<para>
-
+Sets the allocator to use to allocate #GNode elements.
+Use g_node_pop_allocator() to restore the previous allocator.
</para>
-@allocator:
+@allocator: the #GAllocator to use when allocating #GNode elements.
<!-- ##### FUNCTION g_node_pop_allocator ##### -->
<para>
-
+Restores the previous #GAllocator, used when allocating #GNode elements.
</para>
projects / platform / upstream / glib.git / blobdiff