1/* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * GNode: N-way tree implementation.
5 * Copyright (C) 1998 Tim Janik
6 *
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.1 of the License, or (at your option) any later version.
11 *
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.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 */
20
21/*
22 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
23 * file for a list of people on the GLib Team. See the ChangeLog
24 * files for a list of changes. These files are distributed with
25 * GLib at ftp://ftp.gtk.org/pub/gtk/.
26 */
27
28/*
29 * MT safe
30 */
31
32#include "config.h"
33
34#include "gnode.h"
35
36#include "gslice.h"
37
38#include "gtestutils.h"
39
40/**
41 * SECTION:trees-nary
42 * @title: N-ary Trees
43 * @short_description: trees of data with any number of branches
44 *
45 * The #GNode struct and its associated functions provide a N-ary tree
46 * data structure, where nodes in the tree can contain arbitrary data.
47 *
48 * To create a new tree use g_node_new().
49 *
50 * To insert a node into a tree use g_node_insert(),
51 * g_node_insert_before(), g_node_append() and g_node_prepend().
52 *
53 * To create a new node and insert it into a tree use
54 * g_node_insert_data(), g_node_insert_data_after(),
55 * g_node_insert_data_before(), g_node_append_data()
56 * and g_node_prepend_data().
57 *
58 * To reverse the children of a node use g_node_reverse_children().
59 *
60 * To find a node use g_node_get_root(), g_node_find(),
61 * g_node_find_child(), g_node_child_index(), g_node_child_position(),
62 * g_node_first_child(), g_node_last_child(), g_node_nth_child(),
63 * g_node_first_sibling(), g_node_prev_sibling(), g_node_next_sibling()
64 * or g_node_last_sibling().
65 *
66 * To get information about a node or tree use G_NODE_IS_LEAF(),
67 * G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(),
68 * g_node_n_children(), g_node_is_ancestor() or g_node_max_height().
69 *
70 * To traverse a tree, calling a function for each node visited in the
71 * traversal, use g_node_traverse() or g_node_children_foreach().
72 *
73 * To remove a node or subtree from a tree use g_node_unlink() or
74 * g_node_destroy().
75 **/
76
77/**
78 * GNode:
79 * @data: contains the actual data of the node.
80 * @next: points to the node's next sibling (a sibling is another
81 * #GNode with the same parent).
82 * @prev: points to the node's previous sibling.
83 * @parent: points to the parent of the #GNode, or is %NULL if the
84 * #GNode is the root of the tree.
85 * @children: points to the first child of the #GNode. The other
86 * children are accessed by using the @next pointer of each
87 * child.
88 *
89 * The #GNode struct represents one node in a [n-ary tree][glib-N-ary-Trees].
90 **/
91
92#define g_node_alloc0() g_slice_new0 (GNode)
93#define g_node_free(node) g_slice_free (GNode, node)
94
95/* --- functions --- */
96/**
97 * g_node_new:
98 * @data: the data of the new node
99 *
100 * Creates a new #GNode containing the given data.
101 * Used to create the first node in a tree.
102 *
103 * Returns: a new #GNode
104 */
105GNode*
106g_node_new (gpointer data)
107{
108 GNode *node = g_node_alloc0 ();
109 node->data = data;
110 return node;
111}
112
113static void
114g_nodes_free (GNode *node)
115{
116 while (node)
117 {
118 GNode *next = node->next;
119 if (node->children)
120 g_nodes_free (node: node->children);
121 g_node_free (node);
122 node = next;
123 }
124}
125
126/**
127 * g_node_destroy:
128 * @root: the root of the tree/subtree to destroy
129 *
130 * Removes @root and its children from the tree, freeing any memory
131 * allocated.
132 */
133void
134g_node_destroy (GNode *root)
135{
136 g_return_if_fail (root != NULL);
137
138 if (!G_NODE_IS_ROOT (root))
139 g_node_unlink (node: root);
140
141 g_nodes_free (node: root);
142}
143
144/**
145 * g_node_unlink:
146 * @node: the #GNode to unlink, which becomes the root of a new tree
147 *
148 * Unlinks a #GNode from a tree, resulting in two separate trees.
149 */
150void
151g_node_unlink (GNode *node)
152{
153 g_return_if_fail (node != NULL);
154
155 if (node->prev)
156 node->prev->next = node->next;
157 else if (node->parent)
158 node->parent->children = node->next;
159 node->parent = NULL;
160 if (node->next)
161 {
162 node->next->prev = node->prev;
163 node->next = NULL;
164 }
165 node->prev = NULL;
166}
167
168/**
169 * g_node_copy_deep:
170 * @node: a #GNode
171 * @copy_func: the function which is called to copy the data inside each node,
172 * or %NULL to use the original data.
173 * @data: data to pass to @copy_func
174 *
175 * Recursively copies a #GNode and its data.
176 *
177 * Returns: a new #GNode containing copies of the data in @node.
178 *
179 * Since: 2.4
180 **/
181GNode*
182g_node_copy_deep (GNode *node,
183 GCopyFunc copy_func,
184 gpointer data)
185{
186 GNode *new_node = NULL;
187
188 if (copy_func == NULL)
189 return g_node_copy (node);
190
191 if (node)
192 {
193 GNode *child, *new_child;
194
195 new_node = g_node_new (data: copy_func (node->data, data));
196
197 for (child = g_node_last_child (node); child; child = child->prev)
198 {
199 new_child = g_node_copy_deep (node: child, copy_func, data);
200 g_node_prepend (parent: new_node, node: new_child);
201 }
202 }
203
204 return new_node;
205}
206
207/**
208 * g_node_copy:
209 * @node: a #GNode
210 *
211 * Recursively copies a #GNode (but does not deep-copy the data inside the
212 * nodes, see g_node_copy_deep() if you need that).
213 *
214 * Returns: a new #GNode containing the same data pointers
215 */
216GNode*
217g_node_copy (GNode *node)
218{
219 GNode *new_node = NULL;
220
221 if (node)
222 {
223 GNode *child;
224
225 new_node = g_node_new (data: node->data);
226
227 for (child = g_node_last_child (node); child; child = child->prev)
228 g_node_prepend (parent: new_node, node: g_node_copy (node: child));
229 }
230
231 return new_node;
232}
233
234/**
235 * g_node_insert:
236 * @parent: the #GNode to place @node under
237 * @position: the position to place @node at, with respect to its siblings
238 * If position is -1, @node is inserted as the last child of @parent
239 * @node: the #GNode to insert
240 *
241 * Inserts a #GNode beneath the parent at the given position.
242 *
243 * Returns: the inserted #GNode
244 */
245GNode*
246g_node_insert (GNode *parent,
247 gint position,
248 GNode *node)
249{
250 g_return_val_if_fail (parent != NULL, node);
251 g_return_val_if_fail (node != NULL, node);
252 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
253
254 if (position > 0)
255 return g_node_insert_before (parent,
256 sibling: g_node_nth_child (node: parent, n: position),
257 node);
258 else if (position == 0)
259 return g_node_prepend (parent, node);
260 else /* if (position < 0) */
261 return g_node_append (parent, node);
262}
263
264/**
265 * g_node_insert_before:
266 * @parent: the #GNode to place @node under
267 * @sibling: the sibling #GNode to place @node before.
268 * If sibling is %NULL, the node is inserted as the last child of @parent.
269 * @node: the #GNode to insert
270 *
271 * Inserts a #GNode beneath the parent before the given sibling.
272 *
273 * Returns: the inserted #GNode
274 */
275GNode*
276g_node_insert_before (GNode *parent,
277 GNode *sibling,
278 GNode *node)
279{
280 g_return_val_if_fail (parent != NULL, node);
281 g_return_val_if_fail (node != NULL, node);
282 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
283 if (sibling)
284 g_return_val_if_fail (sibling->parent == parent, node);
285
286 node->parent = parent;
287
288 if (sibling)
289 {
290 if (sibling->prev)
291 {
292 node->prev = sibling->prev;
293 node->prev->next = node;
294 node->next = sibling;
295 sibling->prev = node;
296 }
297 else
298 {
299 node->parent->children = node;
300 node->next = sibling;
301 sibling->prev = node;
302 }
303 }
304 else
305 {
306 if (parent->children)
307 {
308 sibling = parent->children;
309 while (sibling->next)
310 sibling = sibling->next;
311 node->prev = sibling;
312 sibling->next = node;
313 }
314 else
315 node->parent->children = node;
316 }
317
318 return node;
319}
320
321/**
322 * g_node_insert_after:
323 * @parent: the #GNode to place @node under
324 * @sibling: the sibling #GNode to place @node after.
325 * If sibling is %NULL, the node is inserted as the first child of @parent.
326 * @node: the #GNode to insert
327 *
328 * Inserts a #GNode beneath the parent after the given sibling.
329 *
330 * Returns: the inserted #GNode
331 */
332GNode*
333g_node_insert_after (GNode *parent,
334 GNode *sibling,
335 GNode *node)
336{
337 g_return_val_if_fail (parent != NULL, node);
338 g_return_val_if_fail (node != NULL, node);
339 g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
340 if (sibling)
341 g_return_val_if_fail (sibling->parent == parent, node);
342
343 node->parent = parent;
344
345 if (sibling)
346 {
347 if (sibling->next)
348 {
349 sibling->next->prev = node;
350 }
351 node->next = sibling->next;
352 node->prev = sibling;
353 sibling->next = node;
354 }
355 else
356 {
357 if (parent->children)
358 {
359 node->next = parent->children;
360 parent->children->prev = node;
361 }
362 parent->children = node;
363 }
364
365 return node;
366}
367
368/**
369 * g_node_prepend:
370 * @parent: the #GNode to place the new #GNode under
371 * @node: the #GNode to insert
372 *
373 * Inserts a #GNode as the first child of the given parent.
374 *
375 * Returns: the inserted #GNode
376 */
377GNode*
378g_node_prepend (GNode *parent,
379 GNode *node)
380{
381 g_return_val_if_fail (parent != NULL, node);
382
383 return g_node_insert_before (parent, sibling: parent->children, node);
384}
385
386/**
387 * g_node_get_root:
388 * @node: a #GNode
389 *
390 * Gets the root of a tree.
391 *
392 * Returns: the root of the tree
393 */
394GNode*
395g_node_get_root (GNode *node)
396{
397 g_return_val_if_fail (node != NULL, NULL);
398
399 while (node->parent)
400 node = node->parent;
401
402 return node;
403}
404
405/**
406 * g_node_is_ancestor:
407 * @node: a #GNode
408 * @descendant: a #GNode
409 *
410 * Returns %TRUE if @node is an ancestor of @descendant.
411 * This is true if node is the parent of @descendant,
412 * or if node is the grandparent of @descendant etc.
413 *
414 * Returns: %TRUE if @node is an ancestor of @descendant
415 */
416gboolean
417g_node_is_ancestor (GNode *node,
418 GNode *descendant)
419{
420 g_return_val_if_fail (node != NULL, FALSE);
421 g_return_val_if_fail (descendant != NULL, FALSE);
422
423 while (descendant)
424 {
425 if (descendant->parent == node)
426 return TRUE;
427
428 descendant = descendant->parent;
429 }
430
431 return FALSE;
432}
433
434/**
435 * g_node_depth:
436 * @node: a #GNode
437 *
438 * Gets the depth of a #GNode.
439 *
440 * If @node is %NULL the depth is 0. The root node has a depth of 1.
441 * For the children of the root node the depth is 2. And so on.
442 *
443 * Returns: the depth of the #GNode
444 */
445guint
446g_node_depth (GNode *node)
447{
448 guint depth = 0;
449
450 while (node)
451 {
452 depth++;
453 node = node->parent;
454 }
455
456 return depth;
457}
458
459/**
460 * g_node_reverse_children:
461 * @node: a #GNode.
462 *
463 * Reverses the order of the children of a #GNode.
464 * (It doesn't change the order of the grandchildren.)
465 */
466void
467g_node_reverse_children (GNode *node)
468{
469 GNode *child;
470 GNode *last;
471
472 g_return_if_fail (node != NULL);
473
474 child = node->children;
475 last = NULL;
476 while (child)
477 {
478 last = child;
479 child = last->next;
480 last->next = last->prev;
481 last->prev = child;
482 }
483 node->children = last;
484}
485
486/**
487 * g_node_max_height:
488 * @root: a #GNode
489 *
490 * Gets the maximum height of all branches beneath a #GNode.
491 * This is the maximum distance from the #GNode to all leaf nodes.
492 *
493 * If @root is %NULL, 0 is returned. If @root has no children,
494 * 1 is returned. If @root has children, 2 is returned. And so on.
495 *
496 * Returns: the maximum height of the tree beneath @root
497 */
498guint
499g_node_max_height (GNode *root)
500{
501 GNode *child;
502 guint max_height = 0;
503
504 if (!root)
505 return 0;
506
507 child = root->children;
508 while (child)
509 {
510 guint tmp_height;
511
512 tmp_height = g_node_max_height (root: child);
513 if (tmp_height > max_height)
514 max_height = tmp_height;
515 child = child->next;
516 }
517
518 return max_height + 1;
519}
520
521static gboolean
522g_node_traverse_pre_order (GNode *node,
523 GTraverseFlags flags,
524 GNodeTraverseFunc func,
525 gpointer data)
526{
527 if (node->children)
528 {
529 GNode *child;
530
531 if ((flags & G_TRAVERSE_NON_LEAFS) &&
532 func (node, data))
533 return TRUE;
534
535 child = node->children;
536 while (child)
537 {
538 GNode *current;
539
540 current = child;
541 child = current->next;
542 if (g_node_traverse_pre_order (node: current, flags, func, data))
543 return TRUE;
544 }
545 }
546 else if ((flags & G_TRAVERSE_LEAFS) &&
547 func (node, data))
548 return TRUE;
549
550 return FALSE;
551}
552
553static gboolean
554g_node_depth_traverse_pre_order (GNode *node,
555 GTraverseFlags flags,
556 guint depth,
557 GNodeTraverseFunc func,
558 gpointer data)
559{
560 if (node->children)
561 {
562 GNode *child;
563
564 if ((flags & G_TRAVERSE_NON_LEAFS) &&
565 func (node, data))
566 return TRUE;
567
568 depth--;
569 if (!depth)
570 return FALSE;
571
572 child = node->children;
573 while (child)
574 {
575 GNode *current;
576
577 current = child;
578 child = current->next;
579 if (g_node_depth_traverse_pre_order (node: current, flags, depth, func, data))
580 return TRUE;
581 }
582 }
583 else if ((flags & G_TRAVERSE_LEAFS) &&
584 func (node, data))
585 return TRUE;
586
587 return FALSE;
588}
589
590static gboolean
591g_node_traverse_post_order (GNode *node,
592 GTraverseFlags flags,
593 GNodeTraverseFunc func,
594 gpointer data)
595{
596 if (node->children)
597 {
598 GNode *child;
599
600 child = node->children;
601 while (child)
602 {
603 GNode *current;
604
605 current = child;
606 child = current->next;
607 if (g_node_traverse_post_order (node: current, flags, func, data))
608 return TRUE;
609 }
610
611 if ((flags & G_TRAVERSE_NON_LEAFS) &&
612 func (node, data))
613 return TRUE;
614
615 }
616 else if ((flags & G_TRAVERSE_LEAFS) &&
617 func (node, data))
618 return TRUE;
619
620 return FALSE;
621}
622
623static gboolean
624g_node_depth_traverse_post_order (GNode *node,
625 GTraverseFlags flags,
626 guint depth,
627 GNodeTraverseFunc func,
628 gpointer data)
629{
630 if (node->children)
631 {
632 depth--;
633 if (depth)
634 {
635 GNode *child;
636
637 child = node->children;
638 while (child)
639 {
640 GNode *current;
641
642 current = child;
643 child = current->next;
644 if (g_node_depth_traverse_post_order (node: current, flags, depth, func, data))
645 return TRUE;
646 }
647 }
648
649 if ((flags & G_TRAVERSE_NON_LEAFS) &&
650 func (node, data))
651 return TRUE;
652
653 }
654 else if ((flags & G_TRAVERSE_LEAFS) &&
655 func (node, data))
656 return TRUE;
657
658 return FALSE;
659}
660
661static gboolean
662g_node_traverse_in_order (GNode *node,
663 GTraverseFlags flags,
664 GNodeTraverseFunc func,
665 gpointer data)
666{
667 if (node->children)
668 {
669 GNode *child;
670 GNode *current;
671
672 child = node->children;
673 current = child;
674 child = current->next;
675
676 if (g_node_traverse_in_order (node: current, flags, func, data))
677 return TRUE;
678
679 if ((flags & G_TRAVERSE_NON_LEAFS) &&
680 func (node, data))
681 return TRUE;
682
683 while (child)
684 {
685 current = child;
686 child = current->next;
687 if (g_node_traverse_in_order (node: current, flags, func, data))
688 return TRUE;
689 }
690 }
691 else if ((flags & G_TRAVERSE_LEAFS) &&
692 func (node, data))
693 return TRUE;
694
695 return FALSE;
696}
697
698static gboolean
699g_node_depth_traverse_in_order (GNode *node,
700 GTraverseFlags flags,
701 guint depth,
702 GNodeTraverseFunc func,
703 gpointer data)
704{
705 if (node->children)
706 {
707 depth--;
708 if (depth)
709 {
710 GNode *child;
711 GNode *current;
712
713 child = node->children;
714 current = child;
715 child = current->next;
716
717 if (g_node_depth_traverse_in_order (node: current, flags, depth, func, data))
718 return TRUE;
719
720 if ((flags & G_TRAVERSE_NON_LEAFS) &&
721 func (node, data))
722 return TRUE;
723
724 while (child)
725 {
726 current = child;
727 child = current->next;
728 if (g_node_depth_traverse_in_order (node: current, flags, depth, func, data))
729 return TRUE;
730 }
731 }
732 else if ((flags & G_TRAVERSE_NON_LEAFS) &&
733 func (node, data))
734 return TRUE;
735 }
736 else if ((flags & G_TRAVERSE_LEAFS) &&
737 func (node, data))
738 return TRUE;
739
740 return FALSE;
741}
742
743static gboolean
744g_node_traverse_level (GNode *node,
745 GTraverseFlags flags,
746 guint level,
747 GNodeTraverseFunc func,
748 gpointer data,
749 gboolean *more_levels)
750{
751 if (level == 0)
752 {
753 if (node->children)
754 {
755 *more_levels = TRUE;
756 return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
757 }
758 else
759 {
760 return (flags & G_TRAVERSE_LEAFS) && func (node, data);
761 }
762 }
763 else
764 {
765 node = node->children;
766
767 while (node)
768 {
769 if (g_node_traverse_level (node, flags, level: level - 1, func, data, more_levels))
770 return TRUE;
771
772 node = node->next;
773 }
774 }
775
776 return FALSE;
777}
778
779static gboolean
780g_node_depth_traverse_level (GNode *node,
781 GTraverseFlags flags,
782 gint depth,
783 GNodeTraverseFunc func,
784 gpointer data)
785{
786 guint level;
787 gboolean more_levels;
788
789 level = 0;
790 while (depth < 0 || level != (guint) depth)
791 {
792 more_levels = FALSE;
793 if (g_node_traverse_level (node, flags, level, func, data, more_levels: &more_levels))
794 return TRUE;
795 if (!more_levels)
796 break;
797 level++;
798 }
799 return FALSE;
800}
801
802/**
803 * g_node_traverse:
804 * @root: the root #GNode of the tree to traverse
805 * @order: the order in which nodes are visited - %G_IN_ORDER,
806 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER.
807 * @flags: which types of children are to be visited, one of
808 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
809 * @max_depth: the maximum depth of the traversal. Nodes below this
810 * depth will not be visited. If max_depth is -1 all nodes in
811 * the tree are visited. If depth is 1, only the root is visited.
812 * If depth is 2, the root and its children are visited. And so on.
813 * @func: the function to call for each visited #GNode
814 * @data: user data to pass to the function
815 *
816 * Traverses a tree starting at the given root #GNode.
817 * It calls the given function for each node visited.
818 * The traversal can be halted at any point by returning %TRUE from @func.
819 * @func must not do anything that would modify the structure of the tree.
820 */
821
822/**
823 * GTraverseType:
824 * @G_IN_ORDER: vists a node's left child first, then the node itself,
825 * then its right child. This is the one to use if you
826 * want the output sorted according to the compare
827 * function.
828 * @G_PRE_ORDER: visits a node, then its children.
829 * @G_POST_ORDER: visits the node's children, then the node itself.
830 * @G_LEVEL_ORDER: is not implemented for
831 * [balanced binary trees][glib-Balanced-Binary-Trees].
832 * For [n-ary trees][glib-N-ary-Trees], it
833 * vists the root node first, then its children, then
834 * its grandchildren, and so on. Note that this is less
835 * efficient than the other orders.
836 *
837 * Specifies the type of traversal performed by g_tree_traverse(),
838 * g_node_traverse() and g_node_find(). The different orders are
839 * illustrated here:
840 * - In order: A, B, C, D, E, F, G, H, I
841 * ![](Sorted_binary_tree_inorder.svg)
842 * - Pre order: F, B, A, D, C, E, G, I, H
843 * ![](Sorted_binary_tree_preorder.svg)
844 * - Post order: A, C, E, D, B, H, I, G, F
845 * ![](Sorted_binary_tree_postorder.svg)
846 * - Level order: F, B, G, A, D, I, C, E, H
847 * ![](Sorted_binary_tree_breadth-first_traversal.svg)
848 */
849
850/**
851 * GTraverseFlags:
852 * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
853 * been introduced in 2.6, for older version use
854 * %G_TRAVERSE_LEAFS.
855 * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
856 * name has been introduced in 2.6, for older
857 * version use %G_TRAVERSE_NON_LEAFS.
858 * @G_TRAVERSE_ALL: all nodes should be visited.
859 * @G_TRAVERSE_MASK: a mask of all traverse flags.
860 * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
861 * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
862 *
863 * Specifies which nodes are visited during several of the tree
864 * functions, including g_node_traverse() and g_node_find().
865 **/
866/**
867 * GNodeTraverseFunc:
868 * @node: a #GNode.
869 * @data: user data passed to g_node_traverse().
870 *
871 * Specifies the type of function passed to g_node_traverse(). The
872 * function is called with each of the nodes visited, together with the
873 * user data passed to g_node_traverse(). If the function returns
874 * %TRUE, then the traversal is stopped.
875 *
876 * Returns: %TRUE to stop the traversal.
877 **/
878void
879g_node_traverse (GNode *root,
880 GTraverseType order,
881 GTraverseFlags flags,
882 gint depth,
883 GNodeTraverseFunc func,
884 gpointer data)
885{
886 g_return_if_fail (root != NULL);
887 g_return_if_fail (func != NULL);
888 g_return_if_fail (order <= G_LEVEL_ORDER);
889 g_return_if_fail (flags <= G_TRAVERSE_MASK);
890 g_return_if_fail (depth == -1 || depth > 0);
891
892 switch (order)
893 {
894 case G_PRE_ORDER:
895 if (depth < 0)
896 g_node_traverse_pre_order (node: root, flags, func, data);
897 else
898 g_node_depth_traverse_pre_order (node: root, flags, depth, func, data);
899 break;
900 case G_POST_ORDER:
901 if (depth < 0)
902 g_node_traverse_post_order (node: root, flags, func, data);
903 else
904 g_node_depth_traverse_post_order (node: root, flags, depth, func, data);
905 break;
906 case G_IN_ORDER:
907 if (depth < 0)
908 g_node_traverse_in_order (node: root, flags, func, data);
909 else
910 g_node_depth_traverse_in_order (node: root, flags, depth, func, data);
911 break;
912 case G_LEVEL_ORDER:
913 g_node_depth_traverse_level (node: root, flags, depth, func, data);
914 break;
915 }
916}
917
918static gboolean
919g_node_find_func (GNode *node,
920 gpointer data)
921{
922 gpointer *d = data;
923
924 if (*d != node->data)
925 return FALSE;
926
927 *(++d) = node;
928
929 return TRUE;
930}
931
932/**
933 * g_node_find:
934 * @root: the root #GNode of the tree to search
935 * @order: the order in which nodes are visited - %G_IN_ORDER,
936 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
937 * @flags: which types of children are to be searched, one of
938 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
939 * @data: the data to find
940 *
941 * Finds a #GNode in a tree.
942 *
943 * Returns: the found #GNode, or %NULL if the data is not found
944 */
945GNode*
946g_node_find (GNode *root,
947 GTraverseType order,
948 GTraverseFlags flags,
949 gpointer data)
950{
951 gpointer d[2];
952
953 g_return_val_if_fail (root != NULL, NULL);
954 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
955 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
956
957 d[0] = data;
958 d[1] = NULL;
959
960 g_node_traverse (root, order, flags, depth: -1, func: g_node_find_func, data: d);
961
962 return d[1];
963}
964
965static void
966g_node_count_func (GNode *node,
967 GTraverseFlags flags,
968 guint *n)
969{
970 if (node->children)
971 {
972 GNode *child;
973
974 if (flags & G_TRAVERSE_NON_LEAFS)
975 (*n)++;
976
977 child = node->children;
978 while (child)
979 {
980 g_node_count_func (node: child, flags, n);
981 child = child->next;
982 }
983 }
984 else if (flags & G_TRAVERSE_LEAFS)
985 (*n)++;
986}
987
988/**
989 * g_node_n_nodes:
990 * @root: a #GNode
991 * @flags: which types of children are to be counted, one of
992 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
993 *
994 * Gets the number of nodes in a tree.
995 *
996 * Returns: the number of nodes in the tree
997 */
998guint
999g_node_n_nodes (GNode *root,
1000 GTraverseFlags flags)
1001{
1002 guint n = 0;
1003
1004 g_return_val_if_fail (root != NULL, 0);
1005 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
1006
1007 g_node_count_func (node: root, flags, n: &n);
1008
1009 return n;
1010}
1011
1012/**
1013 * g_node_last_child:
1014 * @node: a #GNode (must not be %NULL)
1015 *
1016 * Gets the last child of a #GNode.
1017 *
1018 * Returns: the last child of @node, or %NULL if @node has no children
1019 */
1020GNode*
1021g_node_last_child (GNode *node)
1022{
1023 g_return_val_if_fail (node != NULL, NULL);
1024
1025 node = node->children;
1026 if (node)
1027 while (node->next)
1028 node = node->next;
1029
1030 return node;
1031}
1032
1033/**
1034 * g_node_nth_child:
1035 * @node: a #GNode
1036 * @n: the index of the desired child
1037 *
1038 * Gets a child of a #GNode, using the given index.
1039 * The first child is at index 0. If the index is
1040 * too big, %NULL is returned.
1041 *
1042 * Returns: the child of @node at index @n
1043 */
1044GNode*
1045g_node_nth_child (GNode *node,
1046 guint n)
1047{
1048 g_return_val_if_fail (node != NULL, NULL);
1049
1050 node = node->children;
1051 if (node)
1052 while ((n-- > 0) && node)
1053 node = node->next;
1054
1055 return node;
1056}
1057
1058/**
1059 * g_node_n_children:
1060 * @node: a #GNode
1061 *
1062 * Gets the number of children of a #GNode.
1063 *
1064 * Returns: the number of children of @node
1065 */
1066guint
1067g_node_n_children (GNode *node)
1068{
1069 guint n = 0;
1070
1071 g_return_val_if_fail (node != NULL, 0);
1072
1073 node = node->children;
1074 while (node)
1075 {
1076 n++;
1077 node = node->next;
1078 }
1079
1080 return n;
1081}
1082
1083/**
1084 * g_node_find_child:
1085 * @node: a #GNode
1086 * @flags: which types of children are to be searched, one of
1087 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1088 * @data: the data to find
1089 *
1090 * Finds the first child of a #GNode with the given data.
1091 *
1092 * Returns: the found child #GNode, or %NULL if the data is not found
1093 */
1094GNode*
1095g_node_find_child (GNode *node,
1096 GTraverseFlags flags,
1097 gpointer data)
1098{
1099 g_return_val_if_fail (node != NULL, NULL);
1100 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
1101
1102 node = node->children;
1103 while (node)
1104 {
1105 if (node->data == data)
1106 {
1107 if (G_NODE_IS_LEAF (node))
1108 {
1109 if (flags & G_TRAVERSE_LEAFS)
1110 return node;
1111 }
1112 else
1113 {
1114 if (flags & G_TRAVERSE_NON_LEAFS)
1115 return node;
1116 }
1117 }
1118 node = node->next;
1119 }
1120
1121 return NULL;
1122}
1123
1124/**
1125 * g_node_child_position:
1126 * @node: a #GNode
1127 * @child: a child of @node
1128 *
1129 * Gets the position of a #GNode with respect to its siblings.
1130 * @child must be a child of @node. The first child is numbered 0,
1131 * the second 1, and so on.
1132 *
1133 * Returns: the position of @child with respect to its siblings
1134 */
1135gint
1136g_node_child_position (GNode *node,
1137 GNode *child)
1138{
1139 guint n = 0;
1140
1141 g_return_val_if_fail (node != NULL, -1);
1142 g_return_val_if_fail (child != NULL, -1);
1143 g_return_val_if_fail (child->parent == node, -1);
1144
1145 node = node->children;
1146 while (node)
1147 {
1148 if (node == child)
1149 return n;
1150 n++;
1151 node = node->next;
1152 }
1153
1154 return -1;
1155}
1156
1157/**
1158 * g_node_child_index:
1159 * @node: a #GNode
1160 * @data: the data to find
1161 *
1162 * Gets the position of the first child of a #GNode
1163 * which contains the given data.
1164 *
1165 * Returns: the index of the child of @node which contains
1166 * @data, or -1 if the data is not found
1167 */
1168gint
1169g_node_child_index (GNode *node,
1170 gpointer data)
1171{
1172 guint n = 0;
1173
1174 g_return_val_if_fail (node != NULL, -1);
1175
1176 node = node->children;
1177 while (node)
1178 {
1179 if (node->data == data)
1180 return n;
1181 n++;
1182 node = node->next;
1183 }
1184
1185 return -1;
1186}
1187
1188/**
1189 * g_node_first_sibling:
1190 * @node: a #GNode
1191 *
1192 * Gets the first sibling of a #GNode.
1193 * This could possibly be the node itself.
1194 *
1195 * Returns: the first sibling of @node
1196 */
1197GNode*
1198g_node_first_sibling (GNode *node)
1199{
1200 g_return_val_if_fail (node != NULL, NULL);
1201
1202 if (node->parent)
1203 return node->parent->children;
1204
1205 while (node->prev)
1206 node = node->prev;
1207
1208 return node;
1209}
1210
1211/**
1212 * g_node_last_sibling:
1213 * @node: a #GNode
1214 *
1215 * Gets the last sibling of a #GNode.
1216 * This could possibly be the node itself.
1217 *
1218 * Returns: the last sibling of @node
1219 */
1220GNode*
1221g_node_last_sibling (GNode *node)
1222{
1223 g_return_val_if_fail (node != NULL, NULL);
1224
1225 while (node->next)
1226 node = node->next;
1227
1228 return node;
1229}
1230
1231/**
1232 * g_node_children_foreach:
1233 * @node: a #GNode
1234 * @flags: which types of children are to be visited, one of
1235 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1236 * @func: the function to call for each visited node
1237 * @data: user data to pass to the function
1238 *
1239 * Calls a function for each of the children of a #GNode. Note that it
1240 * doesn't descend beneath the child nodes. @func must not do anything
1241 * that would modify the structure of the tree.
1242 */
1243/**
1244 * GNodeForeachFunc:
1245 * @node: a #GNode.
1246 * @data: user data passed to g_node_children_foreach().
1247 *
1248 * Specifies the type of function passed to g_node_children_foreach().
1249 * The function is called with each child node, together with the user
1250 * data passed to g_node_children_foreach().
1251 **/
1252void
1253g_node_children_foreach (GNode *node,
1254 GTraverseFlags flags,
1255 GNodeForeachFunc func,
1256 gpointer data)
1257{
1258 g_return_if_fail (node != NULL);
1259 g_return_if_fail (flags <= G_TRAVERSE_MASK);
1260 g_return_if_fail (func != NULL);
1261
1262 node = node->children;
1263 while (node)
1264 {
1265 GNode *current;
1266
1267 current = node;
1268 node = current->next;
1269 if (G_NODE_IS_LEAF (current))
1270 {
1271 if (flags & G_TRAVERSE_LEAFS)
1272 func (current, data);
1273 }
1274 else
1275 {
1276 if (flags & G_TRAVERSE_NON_LEAFS)
1277 func (current, data);
1278 }
1279 }
1280}
1281

source code of gtk/subprojects/glib/glib/gnode.c