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