nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 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 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 */
105 GNode*
106 g_node_new (gpointer data)
107 {
108 GNode *node = g_node_alloc0 ();
109 node->data = data;
110 return node;
111 }
112  
113 static void
114 g_nodes_free (GNode *node)
115 {
116 while (node)
117 {
118 GNode *next = node->next;
119 if (node->children)
120 g_nodes_free (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 */
133 void
134 g_node_destroy (GNode *root)
135 {
136 g_return_if_fail (root != NULL);
137  
138 if (!G_NODE_IS_ROOT (root))
139 g_node_unlink (root);
140  
141 g_nodes_free (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 */
150 void
151 g_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 **/
181 GNode*
182 g_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 (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 (child, copy_func, data);
200 g_node_prepend (new_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 */
216 GNode*
217 g_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 (node->data);
226  
227 for (child = g_node_last_child (node); child; child = child->prev)
228 g_node_prepend (new_node, g_node_copy (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 */
245 GNode*
246 g_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 g_node_nth_child (parent, 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 */
275 GNode*
276 g_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 */
332 GNode*
333 g_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 */
377 GNode*
378 g_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, 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 */
394 GNode*
395 g_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 */
416 gboolean
417 g_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 */
445 guint
446 g_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 */
466 void
467 g_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 */
498 guint
499 g_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 (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  
521 static gboolean
522 g_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 (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  
553 static gboolean
554 g_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 (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  
590 static gboolean
591 g_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 (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  
623 static gboolean
624 g_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 (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  
661 static gboolean
662 g_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 (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 (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  
698 static gboolean
699 g_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 (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 (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  
743 static gboolean
744 g_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 - 1, func, data, more_levels))
770 return TRUE;
771  
772 node = node->next;
773 }
774 }
775  
776 return FALSE;
777 }
778  
779 static gboolean
780 g_node_depth_traverse_level (GNode *node,
781 GTraverseFlags flags,
782 guint depth,
783 GNodeTraverseFunc func,
784 gpointer data)
785 {
786 guint level;
787 gboolean more_levels;
788  
789 level = 0;
790 while (level != depth)
791 {
792 more_levels = FALSE;
793 if (g_node_traverse_level (node, flags, level, func, data, &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 */
820  
821 /**
822 * GTraverseType:
823 * @G_IN_ORDER: vists a node's left child first, then the node itself,
824 * then its right child. This is the one to use if you
825 * want the output sorted according to the compare
826 * function.
827 * @G_PRE_ORDER: visits a node, then its children.
828 * @G_POST_ORDER: visits the node's children, then the node itself.
829 * @G_LEVEL_ORDER: is not implemented for
830 * [balanced binary trees][glib-Balanced-Binary-Trees].
831 * For [n-ary trees][glib-N-ary-Trees], it
832 * vists the root node first, then its children, then
833 * its grandchildren, and so on. Note that this is less
834 * efficient than the other orders.
835 *
836 * Specifies the type of traveral performed by g_tree_traverse(),
837 * g_node_traverse() and g_node_find(). The different orders are
838 * illustrated here:
839 * - In order: A, B, C, D, E, F, G, H, I
840 * ![](Sorted_binary_tree_inorder.svg)
841 * - Pre order: F, B, A, D, C, E, G, I, H
842 * ![](Sorted_binary_tree_preorder.svg)
843 * - Post order: A, C, E, D, B, H, I, G, F
844 * ![](Sorted_binary_tree_postorder.svg)
845 * - Level order: F, B, G, A, D, I, C, E, H
846 * ![](Sorted_binary_tree_breadth-first_traversal.svg)
847 */
848  
849 /**
850 * GTraverseFlags:
851 * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
852 * been introduced in 2.6, for older version use
853 * %G_TRAVERSE_LEAFS.
854 * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
855 * name has been introduced in 2.6, for older
856 * version use %G_TRAVERSE_NON_LEAFS.
857 * @G_TRAVERSE_ALL: all nodes should be visited.
858 * @G_TRAVERSE_MASK: a mask of all traverse flags.
859 * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
860 * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
861 *
862 * Specifies which nodes are visited during several of the tree
863 * functions, including g_node_traverse() and g_node_find().
864 **/
865 /**
866 * GNodeTraverseFunc:
867 * @node: a #GNode.
868 * @data: user data passed to g_node_traverse().
869 *
870 * Specifies the type of function passed to g_node_traverse(). The
871 * function is called with each of the nodes visited, together with the
872 * user data passed to g_node_traverse(). If the function returns
873 * %TRUE, then the traversal is stopped.
874 *
875 * Returns: %TRUE to stop the traversal.
876 **/
877 void
878 g_node_traverse (GNode *root,
879 GTraverseType order,
880 GTraverseFlags flags,
881 gint depth,
882 GNodeTraverseFunc func,
883 gpointer data)
884 {
885 g_return_if_fail (root != NULL);
886 g_return_if_fail (func != NULL);
887 g_return_if_fail (order <= G_LEVEL_ORDER);
888 g_return_if_fail (flags <= G_TRAVERSE_MASK);
889 g_return_if_fail (depth == -1 || depth > 0);
890  
891 switch (order)
892 {
893 case G_PRE_ORDER:
894 if (depth < 0)
895 g_node_traverse_pre_order (root, flags, func, data);
896 else
897 g_node_depth_traverse_pre_order (root, flags, depth, func, data);
898 break;
899 case G_POST_ORDER:
900 if (depth < 0)
901 g_node_traverse_post_order (root, flags, func, data);
902 else
903 g_node_depth_traverse_post_order (root, flags, depth, func, data);
904 break;
905 case G_IN_ORDER:
906 if (depth < 0)
907 g_node_traverse_in_order (root, flags, func, data);
908 else
909 g_node_depth_traverse_in_order (root, flags, depth, func, data);
910 break;
911 case G_LEVEL_ORDER:
912 g_node_depth_traverse_level (root, flags, depth, func, data);
913 break;
914 }
915 }
916  
917 static gboolean
918 g_node_find_func (GNode *node,
919 gpointer data)
920 {
921 gpointer *d = data;
922  
923 if (*d != node->data)
924 return FALSE;
925  
926 *(++d) = node;
927  
928 return TRUE;
929 }
930  
931 /**
932 * g_node_find:
933 * @root: the root #GNode of the tree to search
934 * @order: the order in which nodes are visited - %G_IN_ORDER,
935 * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
936 * @flags: which types of children are to be searched, one of
937 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
938 * @data: the data to find
939 *
940 * Finds a #GNode in a tree.
941 *
942 * Returns: the found #GNode, or %NULL if the data is not found
943 */
944 GNode*
945 g_node_find (GNode *root,
946 GTraverseType order,
947 GTraverseFlags flags,
948 gpointer data)
949 {
950 gpointer d[2];
951  
952 g_return_val_if_fail (root != NULL, NULL);
953 g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
954 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
955  
956 d[0] = data;
957 d[1] = NULL;
958  
959 g_node_traverse (root, order, flags, -1, g_node_find_func, d);
960  
961 return d[1];
962 }
963  
964 static void
965 g_node_count_func (GNode *node,
966 GTraverseFlags flags,
967 guint *n)
968 {
969 if (node->children)
970 {
971 GNode *child;
972  
973 if (flags & G_TRAVERSE_NON_LEAFS)
974 (*n)++;
975  
976 child = node->children;
977 while (child)
978 {
979 g_node_count_func (child, flags, n);
980 child = child->next;
981 }
982 }
983 else if (flags & G_TRAVERSE_LEAFS)
984 (*n)++;
985 }
986  
987 /**
988 * g_node_n_nodes:
989 * @root: a #GNode
990 * @flags: which types of children are to be counted, one of
991 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
992 *
993 * Gets the number of nodes in a tree.
994 *
995 * Returns: the number of nodes in the tree
996 */
997 guint
998 g_node_n_nodes (GNode *root,
999 GTraverseFlags flags)
1000 {
1001 guint n = 0;
1002  
1003 g_return_val_if_fail (root != NULL, 0);
1004 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
1005  
1006 g_node_count_func (root, flags, &n);
1007  
1008 return n;
1009 }
1010  
1011 /**
1012 * g_node_last_child:
1013 * @node: a #GNode (must not be %NULL)
1014 *
1015 * Gets the last child of a #GNode.
1016 *
1017 * Returns: the last child of @node, or %NULL if @node has no children
1018 */
1019 GNode*
1020 g_node_last_child (GNode *node)
1021 {
1022 g_return_val_if_fail (node != NULL, NULL);
1023  
1024 node = node->children;
1025 if (node)
1026 while (node->next)
1027 node = node->next;
1028  
1029 return node;
1030 }
1031  
1032 /**
1033 * g_node_nth_child:
1034 * @node: a #GNode
1035 * @n: the index of the desired child
1036 *
1037 * Gets a child of a #GNode, using the given index.
1038 * The first child is at index 0. If the index is
1039 * too big, %NULL is returned.
1040 *
1041 * Returns: the child of @node at index @n
1042 */
1043 GNode*
1044 g_node_nth_child (GNode *node,
1045 guint n)
1046 {
1047 g_return_val_if_fail (node != NULL, NULL);
1048  
1049 node = node->children;
1050 if (node)
1051 while ((n-- > 0) && node)
1052 node = node->next;
1053  
1054 return node;
1055 }
1056  
1057 /**
1058 * g_node_n_children:
1059 * @node: a #GNode
1060 *
1061 * Gets the number of children of a #GNode.
1062 *
1063 * Returns: the number of children of @node
1064 */
1065 guint
1066 g_node_n_children (GNode *node)
1067 {
1068 guint n = 0;
1069  
1070 g_return_val_if_fail (node != NULL, 0);
1071  
1072 node = node->children;
1073 while (node)
1074 {
1075 n++;
1076 node = node->next;
1077 }
1078  
1079 return n;
1080 }
1081  
1082 /**
1083 * g_node_find_child:
1084 * @node: a #GNode
1085 * @flags: which types of children are to be searched, one of
1086 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1087 * @data: the data to find
1088 *
1089 * Finds the first child of a #GNode with the given data.
1090 *
1091 * Returns: the found child #GNode, or %NULL if the data is not found
1092 */
1093 GNode*
1094 g_node_find_child (GNode *node,
1095 GTraverseFlags flags,
1096 gpointer data)
1097 {
1098 g_return_val_if_fail (node != NULL, NULL);
1099 g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
1100  
1101 node = node->children;
1102 while (node)
1103 {
1104 if (node->data == data)
1105 {
1106 if (G_NODE_IS_LEAF (node))
1107 {
1108 if (flags & G_TRAVERSE_LEAFS)
1109 return node;
1110 }
1111 else
1112 {
1113 if (flags & G_TRAVERSE_NON_LEAFS)
1114 return node;
1115 }
1116 }
1117 node = node->next;
1118 }
1119  
1120 return NULL;
1121 }
1122  
1123 /**
1124 * g_node_child_position:
1125 * @node: a #GNode
1126 * @child: a child of @node
1127 *
1128 * Gets the position of a #GNode with respect to its siblings.
1129 * @child must be a child of @node. The first child is numbered 0,
1130 * the second 1, and so on.
1131 *
1132 * Returns: the position of @child with respect to its siblings
1133 */
1134 gint
1135 g_node_child_position (GNode *node,
1136 GNode *child)
1137 {
1138 guint n = 0;
1139  
1140 g_return_val_if_fail (node != NULL, -1);
1141 g_return_val_if_fail (child != NULL, -1);
1142 g_return_val_if_fail (child->parent == node, -1);
1143  
1144 node = node->children;
1145 while (node)
1146 {
1147 if (node == child)
1148 return n;
1149 n++;
1150 node = node->next;
1151 }
1152  
1153 return -1;
1154 }
1155  
1156 /**
1157 * g_node_child_index:
1158 * @node: a #GNode
1159 * @data: the data to find
1160 *
1161 * Gets the position of the first child of a #GNode
1162 * which contains the given data.
1163 *
1164 * Returns: the index of the child of @node which contains
1165 * @data, or -1 if the data is not found
1166 */
1167 gint
1168 g_node_child_index (GNode *node,
1169 gpointer data)
1170 {
1171 guint n = 0;
1172  
1173 g_return_val_if_fail (node != NULL, -1);
1174  
1175 node = node->children;
1176 while (node)
1177 {
1178 if (node->data == data)
1179 return n;
1180 n++;
1181 node = node->next;
1182 }
1183  
1184 return -1;
1185 }
1186  
1187 /**
1188 * g_node_first_sibling:
1189 * @node: a #GNode
1190 *
1191 * Gets the first sibling of a #GNode.
1192 * This could possibly be the node itself.
1193 *
1194 * Returns: the first sibling of @node
1195 */
1196 GNode*
1197 g_node_first_sibling (GNode *node)
1198 {
1199 g_return_val_if_fail (node != NULL, NULL);
1200  
1201 if (node->parent)
1202 return node->parent->children;
1203  
1204 while (node->prev)
1205 node = node->prev;
1206  
1207 return node;
1208 }
1209  
1210 /**
1211 * g_node_last_sibling:
1212 * @node: a #GNode
1213 *
1214 * Gets the last sibling of a #GNode.
1215 * This could possibly be the node itself.
1216 *
1217 * Returns: the last sibling of @node
1218 */
1219 GNode*
1220 g_node_last_sibling (GNode *node)
1221 {
1222 g_return_val_if_fail (node != NULL, NULL);
1223  
1224 while (node->next)
1225 node = node->next;
1226  
1227 return node;
1228 }
1229  
1230 /**
1231 * g_node_children_foreach:
1232 * @node: a #GNode
1233 * @flags: which types of children are to be visited, one of
1234 * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1235 * @func: the function to call for each visited node
1236 * @data: user data to pass to the function
1237 *
1238 * Calls a function for each of the children of a #GNode.
1239 * Note that it doesn't descend beneath the child nodes.
1240 */
1241 /**
1242 * GNodeForeachFunc:
1243 * @node: a #GNode.
1244 * @data: user data passed to g_node_children_foreach().
1245 *
1246 * Specifies the type of function passed to g_node_children_foreach().
1247 * The function is called with each child node, together with the user
1248 * data passed to g_node_children_foreach().
1249 **/
1250 void
1251 g_node_children_foreach (GNode *node,
1252 GTraverseFlags flags,
1253 GNodeForeachFunc func,
1254 gpointer data)
1255 {
1256 g_return_if_fail (node != NULL);
1257 g_return_if_fail (flags <= G_TRAVERSE_MASK);
1258 g_return_if_fail (func != NULL);
1259  
1260 node = node->children;
1261 while (node)
1262 {
1263 GNode *current;
1264  
1265 current = node;
1266 node = current->next;
1267 if (G_NODE_IS_LEAF (current))
1268 {
1269 if (flags & G_TRAVERSE_LEAFS)
1270 func (current, data);
1271 }
1272 else
1273 {
1274 if (flags & G_TRAVERSE_NON_LEAFS)
1275 func (current, data);
1276 }
1277 }
1278 }