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 | */ |
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: 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 (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 | */ |
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 (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 | */ |
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 (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 | */ |
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 | 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 | */ |
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, 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 | */ |
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 (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 | |
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 (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 | |
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 (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 | |
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 (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 | |
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 (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 | |
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 (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 | |
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 (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 | |
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: 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 | 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 | **/ |
878 | void |
879 | g_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 | |
918 | static gboolean |
919 | g_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 | */ |
945 | GNode* |
946 | g_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 | |
965 | static void |
966 | g_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 | */ |
998 | guint |
999 | g_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 | */ |
1020 | GNode* |
1021 | g_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 | */ |
1044 | GNode* |
1045 | g_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 | */ |
1066 | guint |
1067 | g_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 | */ |
1094 | GNode* |
1095 | g_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 | */ |
1135 | gint |
1136 | g_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 | */ |
1168 | gint |
1169 | g_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 | */ |
1197 | GNode* |
1198 | g_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 | */ |
1220 | GNode* |
1221 | g_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 | **/ |
1252 | void |
1253 | g_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 | |