| /* GLIB - Library of useful routines for C programming |
| * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
| * |
| * GNode: N-way tree implementation. |
| * Copyright (C) 1998 Tim Janik |
| * |
| * SPDX-License-Identifier: LGPL-2.1-or-later |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public |
| * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
| */ |
| |
| /* |
| * Modified by the GLib Team and others 1997-2000. See the AUTHORS |
| * file for a list of people on the GLib Team. See the ChangeLog |
| * files for a list of changes. These files are distributed with |
| * GLib at ftp://ftp.gtk.org/pub/gtk/. |
| */ |
| |
| /* |
| * MT safe |
| */ |
| |
| #include "config.h" |
| |
| #include "gnode.h" |
| |
| #include "gslice.h" |
| |
| #include "gtestutils.h" |
| |
| /** |
| * GNode: |
| * @data: contains the actual data of the node. |
| * @next: points to the node's next sibling (a sibling is another |
| * #GNode with the same parent). |
| * @prev: points to the node's previous sibling. |
| * @parent: points to the parent of the #GNode, or is %NULL if the |
| * #GNode is the root of the tree. |
| * @children: points to the first child of the #GNode. The other |
| * children are accessed by using the @next pointer of each |
| * child. |
| * |
| * The #GNode struct represents one node in a [n-ary tree][glib-N-ary-Trees]. |
| **/ |
| |
| #define g_node_alloc0() g_slice_new0 (GNode) |
| #define g_node_free(node) g_slice_free (GNode, node) |
| |
| /* --- functions --- */ |
| /** |
| * g_node_new: |
| * @data: the data of the new node |
| * |
| * Creates a new #GNode containing the given data. |
| * Used to create the first node in a tree. |
| * |
| * Returns: a new #GNode |
| */ |
| GNode* |
| g_node_new (gpointer data) |
| { |
| GNode *node = g_node_alloc0 (); |
| node->data = data; |
| return node; |
| } |
| |
| static void |
| g_nodes_free (GNode *node) |
| { |
| while (node) |
| { |
| GNode *next = node->next; |
| if (node->children) |
| g_nodes_free (node->children); |
| g_node_free (node); |
| node = next; |
| } |
| } |
| |
| /** |
| * g_node_destroy: |
| * @root: the root of the tree/subtree to destroy |
| * |
| * Removes @root and its children from the tree, freeing any memory |
| * allocated. |
| */ |
| void |
| g_node_destroy (GNode *root) |
| { |
| g_return_if_fail (root != NULL); |
| |
| if (!G_NODE_IS_ROOT (root)) |
| g_node_unlink (root); |
| |
| g_nodes_free (root); |
| } |
| |
| /** |
| * g_node_unlink: |
| * @node: the #GNode to unlink, which becomes the root of a new tree |
| * |
| * Unlinks a #GNode from a tree, resulting in two separate trees. |
| */ |
| void |
| g_node_unlink (GNode *node) |
| { |
| g_return_if_fail (node != NULL); |
| |
| if (node->prev) |
| node->prev->next = node->next; |
| else if (node->parent) |
| node->parent->children = node->next; |
| node->parent = NULL; |
| if (node->next) |
| { |
| node->next->prev = node->prev; |
| node->next = NULL; |
| } |
| node->prev = NULL; |
| } |
| |
| /** |
| * g_node_copy_deep: |
| * @node: a #GNode |
| * @copy_func: (scope call): the function which is called to copy the data |
| * inside each node, or %NULL to use the original data. |
| * @data: data to pass to @copy_func |
| * |
| * Recursively copies a #GNode and its data. |
| * |
| * Returns: a new #GNode containing copies of the data in @node. |
| * |
| * Since: 2.4 |
| **/ |
| GNode* |
| g_node_copy_deep (GNode *node, |
| GCopyFunc copy_func, |
| gpointer data) |
| { |
| GNode *new_node = NULL; |
| |
| if (copy_func == NULL) |
| return g_node_copy (node); |
| |
| if (node) |
| { |
| GNode *child, *new_child; |
| |
| new_node = g_node_new (copy_func (node->data, data)); |
| |
| for (child = g_node_last_child (node); child; child = child->prev) |
| { |
| new_child = g_node_copy_deep (child, copy_func, data); |
| g_node_prepend (new_node, new_child); |
| } |
| } |
| |
| return new_node; |
| } |
| |
| /** |
| * g_node_copy: |
| * @node: a #GNode |
| * |
| * Recursively copies a #GNode (but does not deep-copy the data inside the |
| * nodes, see g_node_copy_deep() if you need that). |
| * |
| * Returns: a new #GNode containing the same data pointers |
| */ |
| GNode* |
| g_node_copy (GNode *node) |
| { |
| GNode *new_node = NULL; |
| |
| if (node) |
| { |
| GNode *child; |
| |
| new_node = g_node_new (node->data); |
| |
| for (child = g_node_last_child (node); child; child = child->prev) |
| g_node_prepend (new_node, g_node_copy (child)); |
| } |
| |
| return new_node; |
| } |
| |
| /** |
| * g_node_insert: |
| * @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 |
| * |
| * Inserts a #GNode beneath the parent at the given position. |
| * |
| * Returns: the inserted #GNode |
| */ |
| GNode* |
| g_node_insert (GNode *parent, |
| gint position, |
| GNode *node) |
| { |
| g_return_val_if_fail (parent != NULL, node); |
| g_return_val_if_fail (node != NULL, node); |
| g_return_val_if_fail (G_NODE_IS_ROOT (node), node); |
| |
| if (position > 0) |
| return g_node_insert_before (parent, |
| g_node_nth_child (parent, position), |
| node); |
| else if (position == 0) |
| return g_node_prepend (parent, node); |
| else /* if (position < 0) */ |
| return g_node_append (parent, node); |
| } |
| |
| /** |
| * g_node_insert_before: |
| * @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 |
| * |
| * Inserts a #GNode beneath the parent before the given sibling. |
| * |
| * Returns: the inserted #GNode |
| */ |
| GNode* |
| g_node_insert_before (GNode *parent, |
| GNode *sibling, |
| GNode *node) |
| { |
| g_return_val_if_fail (parent != NULL, node); |
| g_return_val_if_fail (node != NULL, node); |
| g_return_val_if_fail (G_NODE_IS_ROOT (node), node); |
| if (sibling) |
| g_return_val_if_fail (sibling->parent == parent, node); |
| |
| node->parent = parent; |
| |
| if (sibling) |
| { |
| if (sibling->prev) |
| { |
| node->prev = sibling->prev; |
| node->prev->next = node; |
| node->next = sibling; |
| sibling->prev = node; |
| } |
| else |
| { |
| node->parent->children = node; |
| node->next = sibling; |
| sibling->prev = node; |
| } |
| } |
| else |
| { |
| if (parent->children) |
| { |
| sibling = parent->children; |
| while (sibling->next) |
| sibling = sibling->next; |
| node->prev = sibling; |
| sibling->next = node; |
| } |
| else |
| node->parent->children = node; |
| } |
| |
| return node; |
| } |
| |
| /** |
| * g_node_insert_after: |
| * @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 |
| * |
| * Inserts a #GNode beneath the parent after the given sibling. |
| * |
| * Returns: the inserted #GNode |
| */ |
| GNode* |
| g_node_insert_after (GNode *parent, |
| GNode *sibling, |
| GNode *node) |
| { |
| g_return_val_if_fail (parent != NULL, node); |
| g_return_val_if_fail (node != NULL, node); |
| g_return_val_if_fail (G_NODE_IS_ROOT (node), node); |
| if (sibling) |
| g_return_val_if_fail (sibling->parent == parent, node); |
| |
| node->parent = parent; |
| |
| if (sibling) |
| { |
| if (sibling->next) |
| { |
| sibling->next->prev = node; |
| } |
| node->next = sibling->next; |
| node->prev = sibling; |
| sibling->next = node; |
| } |
| else |
| { |
| if (parent->children) |
| { |
| node->next = parent->children; |
| parent->children->prev = node; |
| } |
| parent->children = node; |
| } |
| |
| return node; |
| } |
| |
| /** |
| * g_node_prepend: |
| * @parent: the #GNode to place the new #GNode under |
| * @node: the #GNode to insert |
| * |
| * Inserts a #GNode as the first child of the given parent. |
| * |
| * Returns: the inserted #GNode |
| */ |
| GNode* |
| g_node_prepend (GNode *parent, |
| GNode *node) |
| { |
| g_return_val_if_fail (parent != NULL, node); |
| |
| return g_node_insert_before (parent, parent->children, node); |
| } |
| |
| /** |
| * g_node_get_root: |
| * @node: a #GNode |
| * |
| * Gets the root of a tree. |
| * |
| * Returns: the root of the tree |
| */ |
| GNode* |
| g_node_get_root (GNode *node) |
| { |
| g_return_val_if_fail (node != NULL, NULL); |
| |
| while (node->parent) |
| node = node->parent; |
| |
| return node; |
| } |
| |
| /** |
| * g_node_is_ancestor: |
| * @node: a #GNode |
| * @descendant: a #GNode |
| * |
| * 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. |
| * |
| * Returns: %TRUE if @node is an ancestor of @descendant |
| */ |
| gboolean |
| g_node_is_ancestor (GNode *node, |
| GNode *descendant) |
| { |
| g_return_val_if_fail (node != NULL, FALSE); |
| g_return_val_if_fail (descendant != NULL, FALSE); |
| |
| while (descendant) |
| { |
| if (descendant->parent == node) |
| return TRUE; |
| |
| descendant = descendant->parent; |
| } |
| |
| return FALSE; |
| } |
| |
| /** |
| * g_node_depth: |
| * @node: a #GNode |
| * |
| * Gets the depth of a #GNode. |
| * |
| * 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. |
| * |
| * Returns: the depth of the #GNode |
| */ |
| guint |
| g_node_depth (GNode *node) |
| { |
| guint depth = 0; |
| |
| while (node) |
| { |
| depth++; |
| node = node->parent; |
| } |
| |
| return depth; |
| } |
| |
| /** |
| * g_node_reverse_children: |
| * @node: a #GNode. |
| * |
| * Reverses the order of the children of a #GNode. |
| * (It doesn't change the order of the grandchildren.) |
| */ |
| void |
| g_node_reverse_children (GNode *node) |
| { |
| GNode *child; |
| GNode *last; |
| |
| g_return_if_fail (node != NULL); |
| |
| child = node->children; |
| last = NULL; |
| while (child) |
| { |
| last = child; |
| child = last->next; |
| last->next = last->prev; |
| last->prev = child; |
| } |
| node->children = last; |
| } |
| |
| /** |
| * g_node_max_height: |
| * @root: a #GNode |
| * |
| * Gets the maximum height of all branches beneath a #GNode. |
| * This is the maximum distance from the #GNode to all leaf nodes. |
| * |
| * 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. |
| * |
| * Returns: the maximum height of the tree beneath @root |
| */ |
| guint |
| g_node_max_height (GNode *root) |
| { |
| GNode *child; |
| guint max_height = 0; |
| |
| if (!root) |
| return 0; |
| |
| child = root->children; |
| while (child) |
| { |
| guint tmp_height; |
| |
| tmp_height = g_node_max_height (child); |
| if (tmp_height > max_height) |
| max_height = tmp_height; |
| child = child->next; |
| } |
| |
| return max_height + 1; |
| } |
| |
| static gboolean |
| g_node_traverse_pre_order (GNode *node, |
| GTraverseFlags flags, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| if (node->children) |
| { |
| GNode *child; |
| |
| if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| child = node->children; |
| while (child) |
| { |
| GNode *current; |
| |
| current = child; |
| child = current->next; |
| if (g_node_traverse_pre_order (current, flags, func, data)) |
| return TRUE; |
| } |
| } |
| else if ((flags & G_TRAVERSE_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_depth_traverse_pre_order (GNode *node, |
| GTraverseFlags flags, |
| guint depth, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| if (node->children) |
| { |
| GNode *child; |
| |
| if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| depth--; |
| if (!depth) |
| return FALSE; |
| |
| child = node->children; |
| while (child) |
| { |
| GNode *current; |
| |
| current = child; |
| child = current->next; |
| if (g_node_depth_traverse_pre_order (current, flags, depth, func, data)) |
| return TRUE; |
| } |
| } |
| else if ((flags & G_TRAVERSE_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_traverse_post_order (GNode *node, |
| GTraverseFlags flags, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| if (node->children) |
| { |
| GNode *child; |
| |
| child = node->children; |
| while (child) |
| { |
| GNode *current; |
| |
| current = child; |
| child = current->next; |
| if (g_node_traverse_post_order (current, flags, func, data)) |
| return TRUE; |
| } |
| |
| if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| } |
| else if ((flags & G_TRAVERSE_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_depth_traverse_post_order (GNode *node, |
| GTraverseFlags flags, |
| guint depth, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| if (node->children) |
| { |
| depth--; |
| if (depth) |
| { |
| GNode *child; |
| |
| child = node->children; |
| while (child) |
| { |
| GNode *current; |
| |
| current = child; |
| child = current->next; |
| if (g_node_depth_traverse_post_order (current, flags, depth, func, data)) |
| return TRUE; |
| } |
| } |
| |
| if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| } |
| else if ((flags & G_TRAVERSE_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_traverse_in_order (GNode *node, |
| GTraverseFlags flags, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| if (node->children) |
| { |
| GNode *child; |
| GNode *current; |
| |
| child = node->children; |
| current = child; |
| child = current->next; |
| |
| if (g_node_traverse_in_order (current, flags, func, data)) |
| return TRUE; |
| |
| if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| while (child) |
| { |
| current = child; |
| child = current->next; |
| if (g_node_traverse_in_order (current, flags, func, data)) |
| return TRUE; |
| } |
| } |
| else if ((flags & G_TRAVERSE_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_depth_traverse_in_order (GNode *node, |
| GTraverseFlags flags, |
| guint depth, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| if (node->children) |
| { |
| depth--; |
| if (depth) |
| { |
| GNode *child; |
| GNode *current; |
| |
| child = node->children; |
| current = child; |
| child = current->next; |
| |
| if (g_node_depth_traverse_in_order (current, flags, depth, func, data)) |
| return TRUE; |
| |
| if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| while (child) |
| { |
| current = child; |
| child = current->next; |
| if (g_node_depth_traverse_in_order (current, flags, depth, func, data)) |
| return TRUE; |
| } |
| } |
| else if ((flags & G_TRAVERSE_NON_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| } |
| else if ((flags & G_TRAVERSE_LEAFS) && |
| func (node, data)) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_traverse_level (GNode *node, |
| GTraverseFlags flags, |
| guint level, |
| GNodeTraverseFunc func, |
| gpointer data, |
| gboolean *more_levels) |
| { |
| if (level == 0) |
| { |
| if (node->children) |
| { |
| *more_levels = TRUE; |
| return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data); |
| } |
| else |
| { |
| return (flags & G_TRAVERSE_LEAFS) && func (node, data); |
| } |
| } |
| else |
| { |
| node = node->children; |
| |
| while (node) |
| { |
| if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels)) |
| return TRUE; |
| |
| node = node->next; |
| } |
| } |
| |
| return FALSE; |
| } |
| |
| static gboolean |
| g_node_depth_traverse_level (GNode *node, |
| GTraverseFlags flags, |
| gint depth, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| guint level; |
| gboolean more_levels; |
| |
| level = 0; |
| while (depth < 0 || level != (guint) depth) |
| { |
| more_levels = FALSE; |
| if (g_node_traverse_level (node, flags, level, func, data, &more_levels)) |
| return TRUE; |
| if (!more_levels) |
| break; |
| level++; |
| } |
| return FALSE; |
| } |
| |
| /** |
| * g_node_traverse: |
| * @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_LEAVES and %G_TRAVERSE_NON_LEAVES |
| * @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: (scope call): the function to call for each visited #GNode |
| * @data: user data to pass to the function |
| * |
| * 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. |
| * @func must not do anything that would modify the structure of the tree. |
| */ |
| |
| /** |
| * GTraverseType: |
| * @G_IN_ORDER: vists a node's left child first, then the node itself, |
| * then its right child. This is the one to use if you |
| * want the output sorted according to the compare |
| * function. |
| * @G_PRE_ORDER: visits a node, then its children. |
| * @G_POST_ORDER: visits the node's children, then the node itself. |
| * @G_LEVEL_ORDER: is not implemented for |
| * [balanced binary trees][glib-Balanced-Binary-Trees]. |
| * For [n-ary trees][glib-N-ary-Trees], it |
| * vists the root node first, then its children, then |
| * its grandchildren, and so on. Note that this is less |
| * efficient than the other orders. |
| * |
| * Specifies the type of traversal performed by g_tree_traverse(), |
| * g_node_traverse() and g_node_find(). The different orders are |
| * illustrated here: |
| * - In order: A, B, C, D, E, F, G, H, I |
| * ![](Sorted_binary_tree_inorder.svg) |
| * - Pre order: F, B, A, D, C, E, G, I, H |
| * ![](Sorted_binary_tree_preorder.svg) |
| * - Post order: A, C, E, D, B, H, I, G, F |
| * ![](Sorted_binary_tree_postorder.svg) |
| * - Level order: F, B, G, A, D, I, C, E, H |
| * ![](Sorted_binary_tree_breadth-first_traversal.svg) |
| */ |
| |
| /** |
| * GTraverseFlags: |
| * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has |
| * been introduced in 2.6, for older version use |
| * %G_TRAVERSE_LEAFS. |
| * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This |
| * name has been introduced in 2.6, for older |
| * version use %G_TRAVERSE_NON_LEAFS. |
| * @G_TRAVERSE_ALL: all nodes should be visited. |
| * @G_TRAVERSE_MASK: a mask of all traverse flags. |
| * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES. |
| * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES. |
| * |
| * Specifies which nodes are visited during several of the tree |
| * functions, including g_node_traverse() and g_node_find(). |
| **/ |
| /** |
| * GNodeTraverseFunc: |
| * @node: a #GNode. |
| * @data: user data passed to g_node_traverse(). |
| * |
| * 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. |
| * |
| * Returns: %TRUE to stop the traversal. |
| **/ |
| void |
| g_node_traverse (GNode *root, |
| GTraverseType order, |
| GTraverseFlags flags, |
| gint depth, |
| GNodeTraverseFunc func, |
| gpointer data) |
| { |
| g_return_if_fail (root != NULL); |
| g_return_if_fail (func != NULL); |
| g_return_if_fail (order <= G_LEVEL_ORDER); |
| g_return_if_fail (flags <= G_TRAVERSE_MASK); |
| g_return_if_fail (depth == -1 || depth > 0); |
| |
| switch (order) |
| { |
| case G_PRE_ORDER: |
| if (depth < 0) |
| g_node_traverse_pre_order (root, flags, func, data); |
| else |
| g_node_depth_traverse_pre_order (root, flags, depth, func, data); |
| break; |
| case G_POST_ORDER: |
| if (depth < 0) |
| g_node_traverse_post_order (root, flags, func, data); |
| else |
| g_node_depth_traverse_post_order (root, flags, depth, func, data); |
| break; |
| case G_IN_ORDER: |
| if (depth < 0) |
| g_node_traverse_in_order (root, flags, func, data); |
| else |
| g_node_depth_traverse_in_order (root, flags, depth, func, data); |
| break; |
| case G_LEVEL_ORDER: |
| g_node_depth_traverse_level (root, flags, depth, func, data); |
| break; |
| } |
| } |
| |
| static gboolean |
| g_node_find_func (GNode *node, |
| gpointer data) |
| { |
| gpointer *d = data; |
| |
| if (*d != node->data) |
| return FALSE; |
| |
| *(++d) = node; |
| |
| return TRUE; |
| } |
| |
| /** |
| * g_node_find: |
| * @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_LEAVES and %G_TRAVERSE_NON_LEAVES |
| * @data: the data to find |
| * |
| * Finds a #GNode in a tree. |
| * |
| * Returns: the found #GNode, or %NULL if the data is not found |
| */ |
| GNode* |
| g_node_find (GNode *root, |
| GTraverseType order, |
| GTraverseFlags flags, |
| gpointer data) |
| { |
| gpointer d[2]; |
| |
| g_return_val_if_fail (root != NULL, NULL); |
| g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL); |
| g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL); |
| |
| d[0] = data; |
| d[1] = NULL; |
| |
| g_node_traverse (root, order, flags, -1, g_node_find_func, d); |
| |
| return d[1]; |
| } |
| |
| static void |
| g_node_count_func (GNode *node, |
| GTraverseFlags flags, |
| guint *n) |
| { |
| if (node->children) |
| { |
| GNode *child; |
| |
| if (flags & G_TRAVERSE_NON_LEAFS) |
| (*n)++; |
| |
| child = node->children; |
| while (child) |
| { |
| g_node_count_func (child, flags, n); |
| child = child->next; |
| } |
| } |
| else if (flags & G_TRAVERSE_LEAFS) |
| (*n)++; |
| } |
| |
| /** |
| * g_node_n_nodes: |
| * @root: a #GNode |
| * @flags: which types of children are to be counted, one of |
| * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES |
| * |
| * Gets the number of nodes in a tree. |
| * |
| * Returns: the number of nodes in the tree |
| */ |
| guint |
| g_node_n_nodes (GNode *root, |
| GTraverseFlags flags) |
| { |
| guint n = 0; |
| |
| g_return_val_if_fail (root != NULL, 0); |
| g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0); |
| |
| g_node_count_func (root, flags, &n); |
| |
| return n; |
| } |
| |
| /** |
| * g_node_last_child: |
| * @node: a #GNode (must not be %NULL) |
| * |
| * Gets the last child of a #GNode. |
| * |
| * Returns: the last child of @node, or %NULL if @node has no children |
| */ |
| GNode* |
| g_node_last_child (GNode *node) |
| { |
| g_return_val_if_fail (node != NULL, NULL); |
| |
| node = node->children; |
| if (node) |
| while (node->next) |
| node = node->next; |
| |
| return node; |
| } |
| |
| /** |
| * g_node_nth_child: |
| * @node: a #GNode |
| * @n: the index of the desired child |
| * |
| * 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. |
| * |
| * Returns: the child of @node at index @n |
| */ |
| GNode* |
| g_node_nth_child (GNode *node, |
| guint n) |
| { |
| g_return_val_if_fail (node != NULL, NULL); |
| |
| node = node->children; |
| if (node) |
| while ((n-- > 0) && node) |
| node = node->next; |
| |
| return node; |
| } |
| |
| /** |
| * g_node_n_children: |
| * @node: a #GNode |
| * |
| * Gets the number of children of a #GNode. |
| * |
| * Returns: the number of children of @node |
| */ |
| guint |
| g_node_n_children (GNode *node) |
| { |
| guint n = 0; |
| |
| g_return_val_if_fail (node != NULL, 0); |
| |
| node = node->children; |
| while (node) |
| { |
| n++; |
| node = node->next; |
| } |
| |
| return n; |
| } |
| |
| /** |
| * g_node_find_child: |
| * @node: a #GNode |
| * @flags: which types of children are to be searched, one of |
| * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES |
| * @data: the data to find |
| * |
| * Finds the first child of a #GNode with the given data. |
| * |
| * Returns: the found child #GNode, or %NULL if the data is not found |
| */ |
| GNode* |
| g_node_find_child (GNode *node, |
| GTraverseFlags flags, |
| gpointer data) |
| { |
| g_return_val_if_fail (node != NULL, NULL); |
| g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL); |
| |
| node = node->children; |
| while (node) |
| { |
| if (node->data == data) |
| { |
| if (G_NODE_IS_LEAF (node)) |
| { |
| if (flags & G_TRAVERSE_LEAFS) |
| return node; |
| } |
| else |
| { |
| if (flags & G_TRAVERSE_NON_LEAFS) |
| return node; |
| } |
| } |
| node = node->next; |
| } |
| |
| return NULL; |
| } |
| |
| /** |
| * g_node_child_position: |
| * @node: a #GNode |
| * @child: a child of @node |
| * |
| * 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. |
| * |
| * Returns: the position of @child with respect to its siblings |
| */ |
| gint |
| g_node_child_position (GNode *node, |
| GNode *child) |
| { |
| guint n = 0; |
| |
| g_return_val_if_fail (node != NULL, -1); |
| g_return_val_if_fail (child != NULL, -1); |
| g_return_val_if_fail (child->parent == node, -1); |
| |
| node = node->children; |
| while (node) |
| { |
| if (node == child) |
| return n; |
| n++; |
| node = node->next; |
| } |
| |
| return -1; |
| } |
| |
| /** |
| * g_node_child_index: |
| * @node: a #GNode |
| * @data: the data to find |
| * |
| * Gets the position of the first child of a #GNode |
| * which contains the given data. |
| * |
| * Returns: the index of the child of @node which contains |
| * @data, or -1 if the data is not found |
| */ |
| gint |
| g_node_child_index (GNode *node, |
| gpointer data) |
| { |
| guint n = 0; |
| |
| g_return_val_if_fail (node != NULL, -1); |
| |
| node = node->children; |
| while (node) |
| { |
| if (node->data == data) |
| return n; |
| n++; |
| node = node->next; |
| } |
| |
| return -1; |
| } |
| |
| /** |
| * g_node_first_sibling: |
| * @node: a #GNode |
| * |
| * Gets the first sibling of a #GNode. |
| * This could possibly be the node itself. |
| * |
| * Returns: the first sibling of @node |
| */ |
| GNode* |
| g_node_first_sibling (GNode *node) |
| { |
| g_return_val_if_fail (node != NULL, NULL); |
| |
| if (node->parent) |
| return node->parent->children; |
| |
| while (node->prev) |
| node = node->prev; |
| |
| return node; |
| } |
| |
| /** |
| * g_node_last_sibling: |
| * @node: a #GNode |
| * |
| * Gets the last sibling of a #GNode. |
| * This could possibly be the node itself. |
| * |
| * Returns: the last sibling of @node |
| */ |
| GNode* |
| g_node_last_sibling (GNode *node) |
| { |
| g_return_val_if_fail (node != NULL, NULL); |
| |
| while (node->next) |
| node = node->next; |
| |
| return node; |
| } |
| |
| /** |
| * g_node_children_foreach: |
| * @node: a #GNode |
| * @flags: which types of children are to be visited, one of |
| * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES |
| * @func: (scope call): the function to call for each visited node |
| * @data: user data to pass to the function |
| * |
| * Calls a function for each of the children of a #GNode. Note that it |
| * doesn't descend beneath the child nodes. @func must not do anything |
| * that would modify the structure of the tree. |
| */ |
| /** |
| * GNodeForeachFunc: |
| * @node: a #GNode. |
| * @data: user data passed to g_node_children_foreach(). |
| * |
| * 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(). |
| **/ |
| void |
| g_node_children_foreach (GNode *node, |
| GTraverseFlags flags, |
| GNodeForeachFunc func, |
| gpointer data) |
| { |
| g_return_if_fail (node != NULL); |
| g_return_if_fail (flags <= G_TRAVERSE_MASK); |
| g_return_if_fail (func != NULL); |
| |
| node = node->children; |
| while (node) |
| { |
| GNode *current; |
| |
| current = node; |
| node = current->next; |
| if (G_NODE_IS_LEAF (current)) |
| { |
| if (flags & G_TRAVERSE_LEAFS) |
| func (current, data); |
| } |
| else |
| { |
| if (flags & G_TRAVERSE_NON_LEAFS) |
| func (current, data); |
| } |
| } |
| } |