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 * SPDX-License-Identifier: LGPL-2.1-or-later
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
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 [n-ary tree][glib-N-ary-Trees].
94 #define g_node_alloc0() g_slice_new0 (GNode)
95 #define g_node_free(node) g_slice_free (GNode, node)
97 /* --- functions --- */
100 * @data: the data of the new node
102 * Creates a new #GNode containing the given data.
103 * Used to create the first node in a tree.
105 * Returns: a new #GNode
108 g_node_new (gpointer data)
110 GNode *node = g_node_alloc0 ();
116 g_nodes_free (GNode *node)
120 GNode *next = node->next;
122 g_nodes_free (node->children);
130 * @root: the root of the tree/subtree to destroy
132 * Removes @root and its children from the tree, freeing any memory
136 g_node_destroy (GNode *root)
138 g_return_if_fail (root != NULL);
140 if (!G_NODE_IS_ROOT (root))
141 g_node_unlink (root);
148 * @node: the #GNode to unlink, which becomes the root of a new tree
150 * Unlinks a #GNode from a tree, resulting in two separate trees.
153 g_node_unlink (GNode *node)
155 g_return_if_fail (node != NULL);
158 node->prev->next = node->next;
159 else if (node->parent)
160 node->parent->children = node->next;
164 node->next->prev = node->prev;
173 * @copy_func: the function which is called to copy the data inside each node,
174 * or %NULL to use the original data.
175 * @data: data to pass to @copy_func
177 * Recursively copies a #GNode and its data.
179 * Returns: a new #GNode containing copies of the data in @node.
184 g_node_copy_deep (GNode *node,
188 GNode *new_node = NULL;
190 if (copy_func == NULL)
191 return g_node_copy (node);
195 GNode *child, *new_child;
197 new_node = g_node_new (copy_func (node->data, data));
199 for (child = g_node_last_child (node); child; child = child->prev)
201 new_child = g_node_copy_deep (child, copy_func, data);
202 g_node_prepend (new_node, new_child);
213 * Recursively copies a #GNode (but does not deep-copy the data inside the
214 * nodes, see g_node_copy_deep() if you need that).
216 * Returns: a new #GNode containing the same data pointers
219 g_node_copy (GNode *node)
221 GNode *new_node = NULL;
227 new_node = g_node_new (node->data);
229 for (child = g_node_last_child (node); child; child = child->prev)
230 g_node_prepend (new_node, g_node_copy (child));
238 * @parent: the #GNode to place @node under
239 * @position: the position to place @node at, with respect to its siblings
240 * If position is -1, @node is inserted as the last child of @parent
241 * @node: the #GNode to insert
243 * Inserts a #GNode beneath the parent at the given position.
245 * Returns: the inserted #GNode
248 g_node_insert (GNode *parent,
252 g_return_val_if_fail (parent != NULL, node);
253 g_return_val_if_fail (node != NULL, node);
254 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
257 return g_node_insert_before (parent,
258 g_node_nth_child (parent, position),
260 else if (position == 0)
261 return g_node_prepend (parent, node);
262 else /* if (position < 0) */
263 return g_node_append (parent, node);
267 * g_node_insert_before:
268 * @parent: the #GNode to place @node under
269 * @sibling: the sibling #GNode to place @node before.
270 * If sibling is %NULL, the node is inserted as the last child of @parent.
271 * @node: the #GNode to insert
273 * Inserts a #GNode beneath the parent before the given sibling.
275 * Returns: the inserted #GNode
278 g_node_insert_before (GNode *parent,
282 g_return_val_if_fail (parent != NULL, node);
283 g_return_val_if_fail (node != NULL, node);
284 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
286 g_return_val_if_fail (sibling->parent == parent, node);
288 node->parent = parent;
294 node->prev = sibling->prev;
295 node->prev->next = node;
296 node->next = sibling;
297 sibling->prev = node;
301 node->parent->children = node;
302 node->next = sibling;
303 sibling->prev = node;
308 if (parent->children)
310 sibling = parent->children;
311 while (sibling->next)
312 sibling = sibling->next;
313 node->prev = sibling;
314 sibling->next = node;
317 node->parent->children = node;
324 * g_node_insert_after:
325 * @parent: the #GNode to place @node under
326 * @sibling: the sibling #GNode to place @node after.
327 * If sibling is %NULL, the node is inserted as the first child of @parent.
328 * @node: the #GNode to insert
330 * Inserts a #GNode beneath the parent after the given sibling.
332 * Returns: the inserted #GNode
335 g_node_insert_after (GNode *parent,
339 g_return_val_if_fail (parent != NULL, node);
340 g_return_val_if_fail (node != NULL, node);
341 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
343 g_return_val_if_fail (sibling->parent == parent, node);
345 node->parent = parent;
351 sibling->next->prev = node;
353 node->next = sibling->next;
354 node->prev = sibling;
355 sibling->next = node;
359 if (parent->children)
361 node->next = parent->children;
362 parent->children->prev = node;
364 parent->children = node;
372 * @parent: the #GNode to place the new #GNode under
373 * @node: the #GNode to insert
375 * Inserts a #GNode as the first child of the given parent.
377 * Returns: the inserted #GNode
380 g_node_prepend (GNode *parent,
383 g_return_val_if_fail (parent != NULL, node);
385 return g_node_insert_before (parent, parent->children, node);
392 * Gets the root of a tree.
394 * Returns: the root of the tree
397 g_node_get_root (GNode *node)
399 g_return_val_if_fail (node != NULL, NULL);
408 * g_node_is_ancestor:
410 * @descendant: a #GNode
412 * Returns %TRUE if @node is an ancestor of @descendant.
413 * This is true if node is the parent of @descendant,
414 * or if node is the grandparent of @descendant etc.
416 * Returns: %TRUE if @node is an ancestor of @descendant
419 g_node_is_ancestor (GNode *node,
422 g_return_val_if_fail (node != NULL, FALSE);
423 g_return_val_if_fail (descendant != NULL, FALSE);
427 if (descendant->parent == node)
430 descendant = descendant->parent;
440 * Gets the depth of a #GNode.
442 * If @node is %NULL the depth is 0. The root node has a depth of 1.
443 * For the children of the root node the depth is 2. And so on.
445 * Returns: the depth of the #GNode
448 g_node_depth (GNode *node)
462 * g_node_reverse_children:
465 * Reverses the order of the children of a #GNode.
466 * (It doesn't change the order of the grandchildren.)
469 g_node_reverse_children (GNode *node)
474 g_return_if_fail (node != NULL);
476 child = node->children;
482 last->next = last->prev;
485 node->children = last;
492 * Gets the maximum height of all branches beneath a #GNode.
493 * This is the maximum distance from the #GNode to all leaf nodes.
495 * If @root is %NULL, 0 is returned. If @root has no children,
496 * 1 is returned. If @root has children, 2 is returned. And so on.
498 * Returns: the maximum height of the tree beneath @root
501 g_node_max_height (GNode *root)
504 guint max_height = 0;
509 child = root->children;
514 tmp_height = g_node_max_height (child);
515 if (tmp_height > max_height)
516 max_height = tmp_height;
520 return max_height + 1;
524 g_node_traverse_pre_order (GNode *node,
525 GTraverseFlags flags,
526 GNodeTraverseFunc func,
533 if ((flags & G_TRAVERSE_NON_LEAFS) &&
537 child = node->children;
543 child = current->next;
544 if (g_node_traverse_pre_order (current, flags, func, data))
548 else if ((flags & G_TRAVERSE_LEAFS) &&
556 g_node_depth_traverse_pre_order (GNode *node,
557 GTraverseFlags flags,
559 GNodeTraverseFunc func,
566 if ((flags & G_TRAVERSE_NON_LEAFS) &&
574 child = node->children;
580 child = current->next;
581 if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
585 else if ((flags & G_TRAVERSE_LEAFS) &&
593 g_node_traverse_post_order (GNode *node,
594 GTraverseFlags flags,
595 GNodeTraverseFunc func,
602 child = node->children;
608 child = current->next;
609 if (g_node_traverse_post_order (current, flags, func, data))
613 if ((flags & G_TRAVERSE_NON_LEAFS) &&
618 else if ((flags & G_TRAVERSE_LEAFS) &&
626 g_node_depth_traverse_post_order (GNode *node,
627 GTraverseFlags flags,
629 GNodeTraverseFunc func,
639 child = node->children;
645 child = current->next;
646 if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
651 if ((flags & G_TRAVERSE_NON_LEAFS) &&
656 else if ((flags & G_TRAVERSE_LEAFS) &&
664 g_node_traverse_in_order (GNode *node,
665 GTraverseFlags flags,
666 GNodeTraverseFunc func,
674 child = node->children;
676 child = current->next;
678 if (g_node_traverse_in_order (current, flags, func, data))
681 if ((flags & G_TRAVERSE_NON_LEAFS) &&
688 child = current->next;
689 if (g_node_traverse_in_order (current, flags, func, data))
693 else if ((flags & G_TRAVERSE_LEAFS) &&
701 g_node_depth_traverse_in_order (GNode *node,
702 GTraverseFlags flags,
704 GNodeTraverseFunc func,
715 child = node->children;
717 child = current->next;
719 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
722 if ((flags & G_TRAVERSE_NON_LEAFS) &&
729 child = current->next;
730 if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
734 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
738 else if ((flags & G_TRAVERSE_LEAFS) &&
746 g_node_traverse_level (GNode *node,
747 GTraverseFlags flags,
749 GNodeTraverseFunc func,
751 gboolean *more_levels)
758 return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
762 return (flags & G_TRAVERSE_LEAFS) && func (node, data);
767 node = node->children;
771 if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
782 g_node_depth_traverse_level (GNode *node,
783 GTraverseFlags flags,
785 GNodeTraverseFunc func,
789 gboolean more_levels;
792 while (depth < 0 || level != (guint) depth)
795 if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
806 * @root: the root #GNode of the tree to traverse
807 * @order: the order in which nodes are visited - %G_IN_ORDER,
808 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER.
809 * @flags: which types of children are to be visited, one of
810 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
811 * @max_depth: the maximum depth of the traversal. Nodes below this
812 * depth will not be visited. If max_depth is -1 all nodes in
813 * the tree are visited. If depth is 1, only the root is visited.
814 * If depth is 2, the root and its children are visited. And so on.
815 * @func: the function to call for each visited #GNode
816 * @data: user data to pass to the function
818 * Traverses a tree starting at the given root #GNode.
819 * It calls the given function for each node visited.
820 * The traversal can be halted at any point by returning %TRUE from @func.
821 * @func must not do anything that would modify the structure of the tree.
826 * @G_IN_ORDER: vists a node's left child first, then the node itself,
827 * then its right child. This is the one to use if you
828 * want the output sorted according to the compare
830 * @G_PRE_ORDER: visits a node, then its children.
831 * @G_POST_ORDER: visits the node's children, then the node itself.
832 * @G_LEVEL_ORDER: is not implemented for
833 * [balanced binary trees][glib-Balanced-Binary-Trees].
834 * For [n-ary trees][glib-N-ary-Trees], it
835 * vists the root node first, then its children, then
836 * its grandchildren, and so on. Note that this is less
837 * efficient than the other orders.
839 * Specifies the type of traversal performed by g_tree_traverse(),
840 * g_node_traverse() and g_node_find(). The different orders are
842 * - In order: A, B, C, D, E, F, G, H, I
843 * ![](Sorted_binary_tree_inorder.svg)
844 * - Pre order: F, B, A, D, C, E, G, I, H
845 * ![](Sorted_binary_tree_preorder.svg)
846 * - Post order: A, C, E, D, B, H, I, G, F
847 * ![](Sorted_binary_tree_postorder.svg)
848 * - Level order: F, B, G, A, D, I, C, E, H
849 * ![](Sorted_binary_tree_breadth-first_traversal.svg)
854 * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
855 * been introduced in 2.6, for older version use
857 * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
858 * name has been introduced in 2.6, for older
859 * version use %G_TRAVERSE_NON_LEAFS.
860 * @G_TRAVERSE_ALL: all nodes should be visited.
861 * @G_TRAVERSE_MASK: a mask of all traverse flags.
862 * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
863 * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
865 * Specifies which nodes are visited during several of the tree
866 * functions, including g_node_traverse() and g_node_find().
871 * @data: user data passed to g_node_traverse().
873 * Specifies the type of function passed to g_node_traverse(). The
874 * function is called with each of the nodes visited, together with the
875 * user data passed to g_node_traverse(). If the function returns
876 * %TRUE, then the traversal is stopped.
878 * Returns: %TRUE to stop the traversal.
881 g_node_traverse (GNode *root,
883 GTraverseFlags flags,
885 GNodeTraverseFunc func,
888 g_return_if_fail (root != NULL);
889 g_return_if_fail (func != NULL);
890 g_return_if_fail (order <= G_LEVEL_ORDER);
891 g_return_if_fail (flags <= G_TRAVERSE_MASK);
892 g_return_if_fail (depth == -1 || depth > 0);
898 g_node_traverse_pre_order (root, flags, func, data);
900 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
904 g_node_traverse_post_order (root, flags, func, data);
906 g_node_depth_traverse_post_order (root, flags, depth, func, data);
910 g_node_traverse_in_order (root, flags, func, data);
912 g_node_depth_traverse_in_order (root, flags, depth, func, data);
915 g_node_depth_traverse_level (root, flags, depth, func, data);
921 g_node_find_func (GNode *node,
926 if (*d != node->data)
936 * @root: the root #GNode of the tree to search
937 * @order: the order in which nodes are visited - %G_IN_ORDER,
938 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
939 * @flags: which types of children are to be searched, one of
940 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
941 * @data: the data to find
943 * Finds a #GNode in a tree.
945 * Returns: the found #GNode, or %NULL if the data is not found
948 g_node_find (GNode *root,
950 GTraverseFlags flags,
955 g_return_val_if_fail (root != NULL, NULL);
956 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
957 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
962 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
968 g_node_count_func (GNode *node,
969 GTraverseFlags flags,
976 if (flags & G_TRAVERSE_NON_LEAFS)
979 child = node->children;
982 g_node_count_func (child, flags, n);
986 else if (flags & G_TRAVERSE_LEAFS)
993 * @flags: which types of children are to be counted, one of
994 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
996 * Gets the number of nodes in a tree.
998 * Returns: the number of nodes in the tree
1001 g_node_n_nodes (GNode *root,
1002 GTraverseFlags flags)
1006 g_return_val_if_fail (root != NULL, 0);
1007 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
1009 g_node_count_func (root, flags, &n);
1015 * g_node_last_child:
1016 * @node: a #GNode (must not be %NULL)
1018 * Gets the last child of a #GNode.
1020 * Returns: the last child of @node, or %NULL if @node has no children
1023 g_node_last_child (GNode *node)
1025 g_return_val_if_fail (node != NULL, NULL);
1027 node = node->children;
1038 * @n: the index of the desired child
1040 * Gets a child of a #GNode, using the given index.
1041 * The first child is at index 0. If the index is
1042 * too big, %NULL is returned.
1044 * Returns: the child of @node at index @n
1047 g_node_nth_child (GNode *node,
1050 g_return_val_if_fail (node != NULL, NULL);
1052 node = node->children;
1054 while ((n-- > 0) && node)
1061 * g_node_n_children:
1064 * Gets the number of children of a #GNode.
1066 * Returns: the number of children of @node
1069 g_node_n_children (GNode *node)
1073 g_return_val_if_fail (node != NULL, 0);
1075 node = node->children;
1086 * g_node_find_child:
1088 * @flags: which types of children are to be searched, one of
1089 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1090 * @data: the data to find
1092 * Finds the first child of a #GNode with the given data.
1094 * Returns: the found child #GNode, or %NULL if the data is not found
1097 g_node_find_child (GNode *node,
1098 GTraverseFlags flags,
1101 g_return_val_if_fail (node != NULL, NULL);
1102 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
1104 node = node->children;
1107 if (node->data == data)
1109 if (G_NODE_IS_LEAF (node))
1111 if (flags & G_TRAVERSE_LEAFS)
1116 if (flags & G_TRAVERSE_NON_LEAFS)
1127 * g_node_child_position:
1129 * @child: a child of @node
1131 * Gets the position of a #GNode with respect to its siblings.
1132 * @child must be a child of @node. The first child is numbered 0,
1133 * the second 1, and so on.
1135 * Returns: the position of @child with respect to its siblings
1138 g_node_child_position (GNode *node,
1143 g_return_val_if_fail (node != NULL, -1);
1144 g_return_val_if_fail (child != NULL, -1);
1145 g_return_val_if_fail (child->parent == node, -1);
1147 node = node->children;
1160 * g_node_child_index:
1162 * @data: the data to find
1164 * Gets the position of the first child of a #GNode
1165 * which contains the given data.
1167 * Returns: the index of the child of @node which contains
1168 * @data, or -1 if the data is not found
1171 g_node_child_index (GNode *node,
1176 g_return_val_if_fail (node != NULL, -1);
1178 node = node->children;
1181 if (node->data == data)
1191 * g_node_first_sibling:
1194 * Gets the first sibling of a #GNode.
1195 * This could possibly be the node itself.
1197 * Returns: the first sibling of @node
1200 g_node_first_sibling (GNode *node)
1202 g_return_val_if_fail (node != NULL, NULL);
1205 return node->parent->children;
1214 * g_node_last_sibling:
1217 * Gets the last sibling of a #GNode.
1218 * This could possibly be the node itself.
1220 * Returns: the last sibling of @node
1223 g_node_last_sibling (GNode *node)
1225 g_return_val_if_fail (node != NULL, NULL);
1234 * g_node_children_foreach:
1236 * @flags: which types of children are to be visited, one of
1237 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1238 * @func: the function to call for each visited node
1239 * @data: user data to pass to the function
1241 * Calls a function for each of the children of a #GNode. Note that it
1242 * doesn't descend beneath the child nodes. @func must not do anything
1243 * that would modify the structure of the tree.
1248 * @data: user data passed to g_node_children_foreach().
1250 * Specifies the type of function passed to g_node_children_foreach().
1251 * The function is called with each child node, together with the user
1252 * data passed to g_node_children_foreach().
1255 g_node_children_foreach (GNode *node,
1256 GTraverseFlags flags,
1257 GNodeForeachFunc func,
1260 g_return_if_fail (node != NULL);
1261 g_return_if_fail (flags <= G_TRAVERSE_MASK);
1262 g_return_if_fail (func != NULL);
1264 node = node->children;
1270 node = current->next;
1271 if (G_NODE_IS_LEAF (current))
1273 if (flags & G_TRAVERSE_LEAFS)
1274 func (current, data);
1278 if (flags & G_TRAVERSE_NON_LEAFS)
1279 func (current, data);