1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * GNode: N-way tree implementation.
5 * Copyright (C) 1998 Tim Janik
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the
19 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 * Boston, MA 02111-1307, USA.
24 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
25 * file for a list of people on the GLib Team. See the ChangeLog
26 * files for a list of changes. These files are distributed with
27 * GLib at ftp://ftp.gtk.org/pub/gtk/.
40 #include "gtestutils.h"
45 * @short_description: trees of data with any number of branches
47 * The #GNode struct and its associated functions provide a N-ary tree
48 * data structure, where nodes in the tree can contain arbitrary data.
50 * To create a new tree use g_node_new().
52 * To insert a node into a tree use g_node_insert(),
53 * g_node_insert_before(), g_node_append() and g_node_prepend().
55 * To create a new node and insert it into a tree use
56 * g_node_insert_data(), g_node_insert_data_after(),
57 * g_node_insert_data_before(), g_node_append_data()
58 * and g_node_prepend_data().
60 * To reverse the children of a node use g_node_reverse_children().
62 * To find a node use g_node_get_root(), g_node_find(),
63 * g_node_find_child(), g_node_child_index(), g_node_child_position(),
64 * g_node_first_child(), g_node_last_child(), g_node_nth_child(),
65 * g_node_first_sibling(), g_node_prev_sibling(), g_node_next_sibling()
66 * or g_node_last_sibling().
68 * To get information about a node or tree use G_NODE_IS_LEAF(),
69 * G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(),
70 * g_node_n_children(), g_node_is_ancestor() or g_node_max_height().
72 * To traverse a tree, calling a function for each node visited in the
73 * traversal, use g_node_traverse() or g_node_children_foreach().
75 * To remove a node or subtree from a tree use g_node_unlink() or
81 * @data: contains the actual data of the node.
82 * @next: points to the node's next sibling (a sibling is another
83 * #GNode with the same parent).
84 * @prev: points to the node's previous sibling.
85 * @parent: points to the parent of the #GNode, or is %NULL if the
86 * #GNode is the root of the tree.
87 * @children: points to the first child of the #GNode. The other
88 * children are accessed by using the @next pointer of each
91 * The #GNode struct represents one node in a
92 * <link linkend="glib-N-ary-Trees">N-ary Tree</link>. fields
95 #define g_node_alloc0() g_slice_new0 (GNode)
96 #define g_node_free(node) g_slice_free (GNode, node)
98 /* --- functions --- */
101 * @data: the data of the new node
103 * Creates a new #GNode containing the given data.
104 * Used to create the first node in a tree.
106 * Returns: a new #GNode
109 g_node_new (gpointer data
)
111 GNode
*node
= g_node_alloc0 ();
117 g_nodes_free (GNode
*node
)
121 GNode
*next
= node
->next
;
123 g_nodes_free (node
->children
);
131 * @root: the root of the tree/subtree to destroy
133 * Removes @root and its children from the tree, freeing any memory
137 g_node_destroy (GNode
*root
)
139 g_return_if_fail (root
!= NULL
);
141 if (!G_NODE_IS_ROOT (root
))
142 g_node_unlink (root
);
149 * @node: the #GNode to unlink, which becomes the root of a new tree
151 * Unlinks a #GNode from a tree, resulting in two separate trees.
154 g_node_unlink (GNode
*node
)
156 g_return_if_fail (node
!= NULL
);
159 node
->prev
->next
= node
->next
;
160 else if (node
->parent
)
161 node
->parent
->children
= node
->next
;
165 node
->next
->prev
= node
->prev
;
174 * @copy_func: the function which is called to copy the data inside each node,
175 * or %NULL to use the original data.
176 * @data: data to pass to @copy_func
178 * Recursively copies a #GNode and its data.
180 * Return value: a new #GNode containing copies of the data in @node.
185 g_node_copy_deep (GNode
*node
,
189 GNode
*new_node
= NULL
;
191 if (copy_func
== NULL
)
192 return g_node_copy (node
);
196 GNode
*child
, *new_child
;
198 new_node
= g_node_new (copy_func (node
->data
, data
));
200 for (child
= g_node_last_child (node
); child
; child
= child
->prev
)
202 new_child
= g_node_copy_deep (child
, copy_func
, data
);
203 g_node_prepend (new_node
, new_child
);
214 * Recursively copies a #GNode (but does not deep-copy the data inside the
215 * nodes, see g_node_copy_deep() if you need that).
217 * Returns: a new #GNode containing the same data pointers
220 g_node_copy (GNode
*node
)
222 GNode
*new_node
= NULL
;
228 new_node
= g_node_new (node
->data
);
230 for (child
= g_node_last_child (node
); child
; child
= child
->prev
)
231 g_node_prepend (new_node
, g_node_copy (child
));
239 * @parent: the #GNode to place @node under
240 * @position: the position to place @node at, with respect to its siblings
241 * If position is -1, @node is inserted as the last child of @parent
242 * @node: the #GNode to insert
244 * Inserts a #GNode beneath the parent at the given position.
246 * Returns: the inserted #GNode
249 g_node_insert (GNode
*parent
,
253 g_return_val_if_fail (parent
!= NULL
, node
);
254 g_return_val_if_fail (node
!= NULL
, node
);
255 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
258 return g_node_insert_before (parent
,
259 g_node_nth_child (parent
, position
),
261 else if (position
== 0)
262 return g_node_prepend (parent
, node
);
263 else /* if (position < 0) */
264 return g_node_append (parent
, node
);
268 * g_node_insert_before:
269 * @parent: the #GNode to place @node under
270 * @sibling: the sibling #GNode to place @node before.
271 * If sibling is %NULL, the node is inserted as the last child of @parent.
272 * @node: the #GNode to insert
274 * Inserts a #GNode beneath the parent before the given sibling.
276 * Returns: the inserted #GNode
279 g_node_insert_before (GNode
*parent
,
283 g_return_val_if_fail (parent
!= NULL
, node
);
284 g_return_val_if_fail (node
!= NULL
, node
);
285 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
287 g_return_val_if_fail (sibling
->parent
== parent
, node
);
289 node
->parent
= parent
;
295 node
->prev
= sibling
->prev
;
296 node
->prev
->next
= node
;
297 node
->next
= sibling
;
298 sibling
->prev
= node
;
302 node
->parent
->children
= node
;
303 node
->next
= sibling
;
304 sibling
->prev
= node
;
309 if (parent
->children
)
311 sibling
= parent
->children
;
312 while (sibling
->next
)
313 sibling
= sibling
->next
;
314 node
->prev
= sibling
;
315 sibling
->next
= node
;
318 node
->parent
->children
= node
;
325 * g_node_insert_after:
326 * @parent: the #GNode to place @node under
327 * @sibling: the sibling #GNode to place @node after.
328 * If sibling is %NULL, the node is inserted as the first child of @parent.
329 * @node: the #GNode to insert
331 * Inserts a #GNode beneath the parent after the given sibling.
333 * Returns: the inserted #GNode
336 g_node_insert_after (GNode
*parent
,
340 g_return_val_if_fail (parent
!= NULL
, node
);
341 g_return_val_if_fail (node
!= NULL
, node
);
342 g_return_val_if_fail (G_NODE_IS_ROOT (node
), node
);
344 g_return_val_if_fail (sibling
->parent
== parent
, node
);
346 node
->parent
= parent
;
352 sibling
->next
->prev
= node
;
354 node
->next
= sibling
->next
;
355 node
->prev
= sibling
;
356 sibling
->next
= node
;
360 if (parent
->children
)
362 node
->next
= parent
->children
;
363 parent
->children
->prev
= node
;
365 parent
->children
= node
;
373 * @parent: the #GNode to place the new #GNode under
374 * @node: the #GNode to insert
376 * Inserts a #GNode as the first child of the given parent.
378 * Returns: the inserted #GNode
381 g_node_prepend (GNode
*parent
,
384 g_return_val_if_fail (parent
!= NULL
, node
);
386 return g_node_insert_before (parent
, parent
->children
, node
);
393 * Gets the root of a tree.
395 * Returns: the root of the tree
398 g_node_get_root (GNode
*node
)
400 g_return_val_if_fail (node
!= NULL
, NULL
);
409 * g_node_is_ancestor:
411 * @descendant: a #GNode
413 * Returns %TRUE if @node is an ancestor of @descendant.
414 * This is true if node is the parent of @descendant,
415 * or if node is the grandparent of @descendant etc.
417 * Returns: %TRUE if @node is an ancestor of @descendant
420 g_node_is_ancestor (GNode
*node
,
423 g_return_val_if_fail (node
!= NULL
, FALSE
);
424 g_return_val_if_fail (descendant
!= NULL
, FALSE
);
428 if (descendant
->parent
== node
)
431 descendant
= descendant
->parent
;
441 * Gets the depth of a #GNode.
443 * If @node is %NULL the depth is 0. The root node has a depth of 1.
444 * For the children of the root node the depth is 2. And so on.
446 * Returns: the depth of the #GNode
449 g_node_depth (GNode
*node
)
463 * g_node_reverse_children:
466 * Reverses the order of the children of a #GNode.
467 * (It doesn't change the order of the grandchildren.)
470 g_node_reverse_children (GNode
*node
)
475 g_return_if_fail (node
!= NULL
);
477 child
= node
->children
;
483 last
->next
= last
->prev
;
486 node
->children
= last
;
493 * Gets the maximum height of all branches beneath a #GNode.
494 * This is the maximum distance from the #GNode to all leaf nodes.
496 * If @root is %NULL, 0 is returned. If @root has no children,
497 * 1 is returned. If @root has children, 2 is returned. And so on.
499 * Returns: the maximum height of the tree beneath @root
502 g_node_max_height (GNode
*root
)
505 guint max_height
= 0;
510 child
= root
->children
;
515 tmp_height
= g_node_max_height (child
);
516 if (tmp_height
> max_height
)
517 max_height
= tmp_height
;
521 return max_height
+ 1;
525 g_node_traverse_pre_order (GNode
*node
,
526 GTraverseFlags flags
,
527 GNodeTraverseFunc func
,
534 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
538 child
= node
->children
;
544 child
= current
->next
;
545 if (g_node_traverse_pre_order (current
, flags
, func
, data
))
549 else if ((flags
& G_TRAVERSE_LEAFS
) &&
557 g_node_depth_traverse_pre_order (GNode
*node
,
558 GTraverseFlags flags
,
560 GNodeTraverseFunc func
,
567 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
575 child
= node
->children
;
581 child
= current
->next
;
582 if (g_node_depth_traverse_pre_order (current
, flags
, depth
, func
, data
))
586 else if ((flags
& G_TRAVERSE_LEAFS
) &&
594 g_node_traverse_post_order (GNode
*node
,
595 GTraverseFlags flags
,
596 GNodeTraverseFunc func
,
603 child
= node
->children
;
609 child
= current
->next
;
610 if (g_node_traverse_post_order (current
, flags
, func
, data
))
614 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
619 else if ((flags
& G_TRAVERSE_LEAFS
) &&
627 g_node_depth_traverse_post_order (GNode
*node
,
628 GTraverseFlags flags
,
630 GNodeTraverseFunc func
,
640 child
= node
->children
;
646 child
= current
->next
;
647 if (g_node_depth_traverse_post_order (current
, flags
, depth
, func
, data
))
652 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
657 else if ((flags
& G_TRAVERSE_LEAFS
) &&
665 g_node_traverse_in_order (GNode
*node
,
666 GTraverseFlags flags
,
667 GNodeTraverseFunc func
,
675 child
= node
->children
;
677 child
= current
->next
;
679 if (g_node_traverse_in_order (current
, flags
, func
, data
))
682 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
689 child
= current
->next
;
690 if (g_node_traverse_in_order (current
, flags
, func
, data
))
694 else if ((flags
& G_TRAVERSE_LEAFS
) &&
702 g_node_depth_traverse_in_order (GNode
*node
,
703 GTraverseFlags flags
,
705 GNodeTraverseFunc func
,
716 child
= node
->children
;
718 child
= current
->next
;
720 if (g_node_depth_traverse_in_order (current
, flags
, depth
, func
, data
))
723 if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
730 child
= current
->next
;
731 if (g_node_depth_traverse_in_order (current
, flags
, depth
, func
, data
))
735 else if ((flags
& G_TRAVERSE_NON_LEAFS
) &&
739 else if ((flags
& G_TRAVERSE_LEAFS
) &&
747 g_node_traverse_level (GNode
*node
,
748 GTraverseFlags flags
,
750 GNodeTraverseFunc func
,
752 gboolean
*more_levels
)
759 return (flags
& G_TRAVERSE_NON_LEAFS
) && func (node
, data
);
763 return (flags
& G_TRAVERSE_LEAFS
) && func (node
, data
);
768 node
= node
->children
;
772 if (g_node_traverse_level (node
, flags
, level
- 1, func
, data
, more_levels
))
783 g_node_depth_traverse_level (GNode
*node
,
784 GTraverseFlags flags
,
786 GNodeTraverseFunc func
,
790 gboolean more_levels
;
793 while (level
!= depth
)
796 if (g_node_traverse_level (node
, flags
, level
, func
, data
, &more_levels
))
807 * @root: the root #GNode of the tree to traverse
808 * @order: the order in which nodes are visited - %G_IN_ORDER,
809 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER.
810 * @flags: which types of children are to be visited, one of
811 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
812 * @max_depth: the maximum depth of the traversal. Nodes below this
813 * depth will not be visited. If max_depth is -1 all nodes in
814 * the tree are visited. If depth is 1, only the root is visited.
815 * If depth is 2, the root and its children are visited. And so on.
816 * @func: the function to call for each visited #GNode
817 * @data: user data to pass to the function
819 * Traverses a tree starting at the given root #GNode.
820 * It calls the given function for each node visited.
821 * The traversal can be halted at any point by returning %TRUE from @func.
825 * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
826 * been introduced in 2.6, for older version use
828 * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
829 * name has been introduced in 2.6, for older
830 * version use %G_TRAVERSE_NON_LEAFS.
831 * @G_TRAVERSE_ALL: all nodes should be visited.
832 * @G_TRAVERSE_MASK: a mask of all traverse flags.
833 * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
834 * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
836 * Specifies which nodes are visited during several of the tree
837 * functions, including g_node_traverse() and g_node_find().
842 * @data: user data passed to g_node_traverse().
844 * Specifies the type of function passed to g_node_traverse(). The
845 * function is called with each of the nodes visited, together with the
846 * user data passed to g_node_traverse(). If the function returns
847 * %TRUE, then the traversal is stopped.
849 * Returns: %TRUE to stop the traversal.
852 g_node_traverse (GNode
*root
,
854 GTraverseFlags flags
,
856 GNodeTraverseFunc func
,
859 g_return_if_fail (root
!= NULL
);
860 g_return_if_fail (func
!= NULL
);
861 g_return_if_fail (order
<= G_LEVEL_ORDER
);
862 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
863 g_return_if_fail (depth
== -1 || depth
> 0);
869 g_node_traverse_pre_order (root
, flags
, func
, data
);
871 g_node_depth_traverse_pre_order (root
, flags
, depth
, func
, data
);
875 g_node_traverse_post_order (root
, flags
, func
, data
);
877 g_node_depth_traverse_post_order (root
, flags
, depth
, func
, data
);
881 g_node_traverse_in_order (root
, flags
, func
, data
);
883 g_node_depth_traverse_in_order (root
, flags
, depth
, func
, data
);
886 g_node_depth_traverse_level (root
, flags
, depth
, func
, data
);
892 g_node_find_func (GNode
*node
,
897 if (*d
!= node
->data
)
907 * @root: the root #GNode of the tree to search
908 * @order: the order in which nodes are visited - %G_IN_ORDER,
909 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
910 * @flags: which types of children are to be searched, one of
911 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
912 * @data: the data to find
914 * Finds a #GNode in a tree.
916 * Returns: the found #GNode, or %NULL if the data is not found
919 g_node_find (GNode
*root
,
921 GTraverseFlags flags
,
926 g_return_val_if_fail (root
!= NULL
, NULL
);
927 g_return_val_if_fail (order
<= G_LEVEL_ORDER
, NULL
);
928 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
933 g_node_traverse (root
, order
, flags
, -1, g_node_find_func
, d
);
939 g_node_count_func (GNode
*node
,
940 GTraverseFlags flags
,
947 if (flags
& G_TRAVERSE_NON_LEAFS
)
950 child
= node
->children
;
953 g_node_count_func (child
, flags
, n
);
957 else if (flags
& G_TRAVERSE_LEAFS
)
964 * @flags: which types of children are to be counted, one of
965 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
967 * Gets the number of nodes in a tree.
969 * Returns: the number of nodes in the tree
972 g_node_n_nodes (GNode
*root
,
973 GTraverseFlags flags
)
977 g_return_val_if_fail (root
!= NULL
, 0);
978 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, 0);
980 g_node_count_func (root
, flags
, &n
);
987 * @node: a #GNode (must not be %NULL)
989 * Gets the last child of a #GNode.
991 * Returns: the last child of @node, or %NULL if @node has no children
994 g_node_last_child (GNode
*node
)
996 g_return_val_if_fail (node
!= NULL
, NULL
);
998 node
= node
->children
;
1009 * @n: the index of the desired child
1011 * Gets a child of a #GNode, using the given index.
1012 * The first child is at index 0. If the index is
1013 * too big, %NULL is returned.
1015 * Returns: the child of @node at index @n
1018 g_node_nth_child (GNode
*node
,
1021 g_return_val_if_fail (node
!= NULL
, NULL
);
1023 node
= node
->children
;
1025 while ((n
-- > 0) && node
)
1032 * g_node_n_children:
1035 * Gets the number of children of a #GNode.
1037 * Returns: the number of children of @node
1040 g_node_n_children (GNode
*node
)
1044 g_return_val_if_fail (node
!= NULL
, 0);
1046 node
= node
->children
;
1057 * g_node_find_child:
1059 * @flags: which types of children are to be searched, one of
1060 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1061 * @data: the data to find
1063 * Finds the first child of a #GNode with the given data.
1065 * Returns: the found child #GNode, or %NULL if the data is not found
1068 g_node_find_child (GNode
*node
,
1069 GTraverseFlags flags
,
1072 g_return_val_if_fail (node
!= NULL
, NULL
);
1073 g_return_val_if_fail (flags
<= G_TRAVERSE_MASK
, NULL
);
1075 node
= node
->children
;
1078 if (node
->data
== data
)
1080 if (G_NODE_IS_LEAF (node
))
1082 if (flags
& G_TRAVERSE_LEAFS
)
1087 if (flags
& G_TRAVERSE_NON_LEAFS
)
1098 * g_node_child_position:
1100 * @child: a child of @node
1102 * Gets the position of a #GNode with respect to its siblings.
1103 * @child must be a child of @node. The first child is numbered 0,
1104 * the second 1, and so on.
1106 * Returns: the position of @child with respect to its siblings
1109 g_node_child_position (GNode
*node
,
1114 g_return_val_if_fail (node
!= NULL
, -1);
1115 g_return_val_if_fail (child
!= NULL
, -1);
1116 g_return_val_if_fail (child
->parent
== node
, -1);
1118 node
= node
->children
;
1131 * g_node_child_index:
1133 * @data: the data to find
1135 * Gets the position of the first child of a #GNode
1136 * which contains the given data.
1138 * Returns: the index of the child of @node which contains
1139 * @data, or -1 if the data is not found
1142 g_node_child_index (GNode
*node
,
1147 g_return_val_if_fail (node
!= NULL
, -1);
1149 node
= node
->children
;
1152 if (node
->data
== data
)
1162 * g_node_first_sibling:
1165 * Gets the first sibling of a #GNode.
1166 * This could possibly be the node itself.
1168 * Returns: the first sibling of @node
1171 g_node_first_sibling (GNode
*node
)
1173 g_return_val_if_fail (node
!= NULL
, NULL
);
1176 return node
->parent
->children
;
1185 * g_node_last_sibling:
1188 * Gets the last sibling of a #GNode.
1189 * This could possibly be the node itself.
1191 * Returns: the last sibling of @node
1194 g_node_last_sibling (GNode
*node
)
1196 g_return_val_if_fail (node
!= NULL
, NULL
);
1205 * g_node_children_foreach:
1207 * @flags: which types of children are to be visited, one of
1208 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1209 * @func: the function to call for each visited node
1210 * @data: user data to pass to the function
1212 * Calls a function for each of the children of a #GNode.
1213 * Note that it doesn't descend beneath the child nodes.
1218 * @data: user data passed to g_node_children_foreach().
1220 * Specifies the type of function passed to g_node_children_foreach().
1221 * The function is called with each child node, together with the user
1222 * data passed to g_node_children_foreach().
1225 g_node_children_foreach (GNode
*node
,
1226 GTraverseFlags flags
,
1227 GNodeForeachFunc func
,
1230 g_return_if_fail (node
!= NULL
);
1231 g_return_if_fail (flags
<= G_TRAVERSE_MASK
);
1232 g_return_if_fail (func
!= NULL
);
1234 node
= node
->children
;
1240 node
= current
->next
;
1241 if (G_NODE_IS_LEAF (current
))
1243 if (flags
& G_TRAVERSE_LEAFS
)
1244 func (current
, data
);
1248 if (flags
& G_TRAVERSE_NON_LEAFS
)
1249 func (current
, data
);