Branch data Line data Source code
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 : 2104 : g_node_new (gpointer data)
72 : : {
73 : 2104 : GNode *node = g_node_alloc0 ();
74 : 2104 : node->data = data;
75 : 2104 : return node;
76 : : }
77 : :
78 : : static void
79 : 439 : g_nodes_free (GNode *node)
80 : : {
81 : 2543 : while (node)
82 : : {
83 : 2104 : GNode *next = node->next;
84 : 2104 : if (node->children)
85 : 428 : g_nodes_free (node->children);
86 : 2104 : g_node_free (node);
87 : 2104 : node = next;
88 : : }
89 : 439 : }
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 : 11 : g_node_destroy (GNode *root)
100 : : {
101 : 11 : g_return_if_fail (root != NULL);
102 : :
103 : 11 : if (!G_NODE_IS_ROOT (root))
104 : 1 : g_node_unlink (root);
105 : :
106 : 11 : 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 : 2 : g_node_unlink (GNode *node)
117 : : {
118 : 2 : g_return_if_fail (node != NULL);
119 : :
120 : 2 : if (node->prev)
121 : 1 : node->prev->next = node->next;
122 : 1 : else if (node->parent)
123 : 1 : node->parent->children = node->next;
124 : 2 : node->parent = NULL;
125 : 2 : if (node->next)
126 : : {
127 : 2 : node->next->prev = node->prev;
128 : 2 : node->next = NULL;
129 : : }
130 : 2 : 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 : 4 : g_node_copy_deep (GNode *node,
148 : : GCopyFunc copy_func,
149 : : gpointer data)
150 : : {
151 : 4 : GNode *new_node = NULL;
152 : :
153 : 4 : if (copy_func == NULL)
154 : 0 : return g_node_copy (node);
155 : :
156 : 4 : if (node)
157 : : {
158 : : GNode *child, *new_child;
159 : :
160 : 4 : new_node = g_node_new (copy_func (node->data, data));
161 : :
162 : 7 : for (child = g_node_last_child (node); child; child = child->prev)
163 : : {
164 : 3 : new_child = g_node_copy_deep (child, copy_func, data);
165 : 3 : g_node_prepend (new_node, new_child);
166 : : }
167 : : }
168 : :
169 : 4 : 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 : 4 : g_node_copy (GNode *node)
183 : : {
184 : 4 : GNode *new_node = NULL;
185 : :
186 : 4 : if (node)
187 : : {
188 : : GNode *child;
189 : :
190 : 4 : new_node = g_node_new (node->data);
191 : :
192 : 7 : for (child = g_node_last_child (node); child; child = child->prev)
193 : 3 : g_node_prepend (new_node, g_node_copy (child));
194 : : }
195 : :
196 : 4 : 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 : 8 : g_node_insert (GNode *parent,
212 : : gint position,
213 : : GNode *node)
214 : : {
215 : 8 : g_return_val_if_fail (parent != NULL, node);
216 : 8 : g_return_val_if_fail (node != NULL, node);
217 : 8 : g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
218 : :
219 : 8 : if (position > 0)
220 : 6 : return g_node_insert_before (parent,
221 : : g_node_nth_child (parent, position),
222 : : node);
223 : 2 : else if (position == 0)
224 : 1 : return g_node_prepend (parent, node);
225 : : else /* if (position < 0) */
226 : 1 : 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 : 2092 : g_node_insert_before (GNode *parent,
242 : : GNode *sibling,
243 : : GNode *node)
244 : : {
245 : 2092 : g_return_val_if_fail (parent != NULL, node);
246 : 2092 : g_return_val_if_fail (node != NULL, node);
247 : 2092 : g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
248 : 2092 : if (sibling)
249 : 11 : g_return_val_if_fail (sibling->parent == parent, node);
250 : :
251 : 2092 : node->parent = parent;
252 : :
253 : 2092 : if (sibling)
254 : : {
255 : 11 : if (sibling->prev)
256 : : {
257 : 4 : node->prev = sibling->prev;
258 : 4 : node->prev->next = node;
259 : 4 : node->next = sibling;
260 : 4 : sibling->prev = node;
261 : : }
262 : : else
263 : : {
264 : 7 : node->parent->children = node;
265 : 7 : node->next = sibling;
266 : 7 : sibling->prev = node;
267 : : }
268 : : }
269 : : else
270 : : {
271 : 2081 : if (parent->children)
272 : : {
273 : 1654 : sibling = parent->children;
274 : 4114 : while (sibling->next)
275 : 2460 : sibling = sibling->next;
276 : 1654 : node->prev = sibling;
277 : 1654 : sibling->next = node;
278 : : }
279 : : else
280 : 427 : node->parent->children = node;
281 : : }
282 : :
283 : 2092 : 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 : 3 : g_node_insert_after (GNode *parent,
299 : : GNode *sibling,
300 : : GNode *node)
301 : : {
302 : 3 : g_return_val_if_fail (parent != NULL, node);
303 : 3 : g_return_val_if_fail (node != NULL, node);
304 : 3 : g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
305 : 3 : if (sibling)
306 : 1 : g_return_val_if_fail (sibling->parent == parent, node);
307 : :
308 : 3 : node->parent = parent;
309 : :
310 : 3 : if (sibling)
311 : : {
312 : 1 : if (sibling->next)
313 : : {
314 : 1 : sibling->next->prev = node;
315 : : }
316 : 1 : node->next = sibling->next;
317 : 1 : node->prev = sibling;
318 : 1 : sibling->next = node;
319 : : }
320 : : else
321 : : {
322 : 2 : if (parent->children)
323 : : {
324 : 1 : node->next = parent->children;
325 : 1 : parent->children->prev = node;
326 : : }
327 : 2 : parent->children = node;
328 : : }
329 : :
330 : 3 : 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 : 10 : g_node_prepend (GNode *parent,
344 : : GNode *node)
345 : : {
346 : 10 : g_return_val_if_fail (parent != NULL, node);
347 : :
348 : 10 : 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 : 1 : g_node_get_root (GNode *node)
361 : : {
362 : 1 : g_return_val_if_fail (node != NULL, NULL);
363 : :
364 : 3 : while (node->parent)
365 : 2 : node = node->parent;
366 : :
367 : 1 : 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 : 3 : g_node_is_ancestor (GNode *node,
383 : : GNode *descendant)
384 : : {
385 : 3 : g_return_val_if_fail (node != NULL, FALSE);
386 : 3 : g_return_val_if_fail (descendant != NULL, FALSE);
387 : :
388 : 6 : while (descendant)
389 : : {
390 : 5 : if (descendant->parent == node)
391 : 2 : return TRUE;
392 : :
393 : 3 : descendant = descendant->parent;
394 : : }
395 : :
396 : 1 : 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 : 3 : g_node_depth (GNode *node)
412 : : {
413 : 3 : guint depth = 0;
414 : :
415 : 9 : while (node)
416 : : {
417 : 6 : depth++;
418 : 6 : node = node->parent;
419 : : }
420 : :
421 : 3 : 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 : 2 : g_node_reverse_children (GNode *node)
433 : : {
434 : : GNode *child;
435 : : GNode *last;
436 : :
437 : 2 : g_return_if_fail (node != NULL);
438 : :
439 : 2 : child = node->children;
440 : 2 : last = NULL;
441 : 9 : while (child)
442 : : {
443 : 7 : last = child;
444 : 7 : child = last->next;
445 : 7 : last->next = last->prev;
446 : 7 : last->prev = child;
447 : : }
448 : 2 : 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 : 2067 : g_node_max_height (GNode *root)
465 : : {
466 : : GNode *child;
467 : 2067 : guint max_height = 0;
468 : :
469 : 2067 : if (!root)
470 : 0 : return 0;
471 : :
472 : 2067 : child = root->children;
473 : 4130 : while (child)
474 : : {
475 : : guint tmp_height;
476 : :
477 : 2063 : tmp_height = g_node_max_height (child);
478 : 2063 : if (tmp_height > max_height)
479 : 826 : max_height = tmp_height;
480 : 2063 : child = child->next;
481 : : }
482 : :
483 : 2067 : return max_height + 1;
484 : : }
485 : :
486 : : static gboolean
487 : 92 : g_node_traverse_pre_order (GNode *node,
488 : : GTraverseFlags flags,
489 : : GNodeTraverseFunc func,
490 : : gpointer data)
491 : : {
492 : 92 : if (node->children)
493 : : {
494 : : GNode *child;
495 : :
496 : 79 : if ((flags & G_TRAVERSE_NON_LEAFS) &&
497 : 37 : func (node, data))
498 : 4 : return TRUE;
499 : :
500 : 38 : child = node->children;
501 : 98 : while (child)
502 : : {
503 : : GNode *current;
504 : :
505 : 79 : current = child;
506 : 79 : child = current->next;
507 : 79 : if (g_node_traverse_pre_order (current, flags, func, data))
508 : 19 : return TRUE;
509 : : }
510 : : }
511 : 92 : else if ((flags & G_TRAVERSE_LEAFS) &&
512 : 42 : func (node, data))
513 : 6 : return TRUE;
514 : :
515 : 63 : return FALSE;
516 : : }
517 : :
518 : : static gboolean
519 : 53 : g_node_depth_traverse_pre_order (GNode *node,
520 : : GTraverseFlags flags,
521 : : guint depth,
522 : : GNodeTraverseFunc func,
523 : : gpointer data)
524 : : {
525 : 53 : if (node->children)
526 : : {
527 : : GNode *child;
528 : :
529 : 64 : if ((flags & G_TRAVERSE_NON_LEAFS) &&
530 : 32 : func (node, data))
531 : 4 : return TRUE;
532 : :
533 : 28 : depth--;
534 : 28 : if (!depth)
535 : 6 : return FALSE;
536 : :
537 : 22 : child = node->children;
538 : 53 : while (child)
539 : : {
540 : : GNode *current;
541 : :
542 : 41 : current = child;
543 : 41 : child = current->next;
544 : 41 : if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
545 : 10 : return TRUE;
546 : : }
547 : : }
548 : 42 : else if ((flags & G_TRAVERSE_LEAFS) &&
549 : 21 : func (node, data))
550 : 3 : return TRUE;
551 : :
552 : 30 : return FALSE;
553 : : }
554 : :
555 : : static gboolean
556 : 88 : g_node_traverse_post_order (GNode *node,
557 : : GTraverseFlags flags,
558 : : GNodeTraverseFunc func,
559 : : gpointer data)
560 : : {
561 : 88 : if (node->children)
562 : : {
563 : : GNode *child;
564 : :
565 : 36 : child = node->children;
566 : 91 : while (child)
567 : : {
568 : : GNode *current;
569 : :
570 : 77 : current = child;
571 : 77 : child = current->next;
572 : 77 : if (g_node_traverse_post_order (current, flags, func, data))
573 : 22 : return TRUE;
574 : : }
575 : :
576 : 28 : if ((flags & G_TRAVERSE_NON_LEAFS) &&
577 : 14 : func (node, data))
578 : 3 : return TRUE;
579 : :
580 : : }
581 : 104 : else if ((flags & G_TRAVERSE_LEAFS) &&
582 : 52 : func (node, data))
583 : 7 : return TRUE;
584 : :
585 : 56 : return FALSE;
586 : : }
587 : :
588 : : static gboolean
589 : 56 : g_node_depth_traverse_post_order (GNode *node,
590 : : GTraverseFlags flags,
591 : : guint depth,
592 : : GNodeTraverseFunc func,
593 : : gpointer data)
594 : : {
595 : 56 : if (node->children)
596 : : {
597 : 32 : depth--;
598 : 32 : if (depth)
599 : : {
600 : : GNode *child;
601 : :
602 : 24 : child = node->children;
603 : 59 : while (child)
604 : : {
605 : : GNode *current;
606 : :
607 : 45 : current = child;
608 : 45 : child = current->next;
609 : 45 : if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
610 : 10 : return TRUE;
611 : : }
612 : : }
613 : :
614 : 44 : if ((flags & G_TRAVERSE_NON_LEAFS) &&
615 : 22 : func (node, data))
616 : 4 : return TRUE;
617 : :
618 : : }
619 : 48 : else if ((flags & G_TRAVERSE_LEAFS) &&
620 : 24 : func (node, data))
621 : 3 : return TRUE;
622 : :
623 : 39 : return FALSE;
624 : : }
625 : :
626 : : static gboolean
627 : 87 : g_node_traverse_in_order (GNode *node,
628 : : GTraverseFlags flags,
629 : : GNodeTraverseFunc func,
630 : : gpointer data)
631 : : {
632 : 87 : if (node->children)
633 : : {
634 : : GNode *child;
635 : : GNode *current;
636 : :
637 : 38 : child = node->children;
638 : 38 : current = child;
639 : 38 : child = current->next;
640 : :
641 : 38 : if (g_node_traverse_in_order (current, flags, func, data))
642 : 12 : return TRUE;
643 : :
644 : 49 : if ((flags & G_TRAVERSE_NON_LEAFS) &&
645 : 23 : func (node, data))
646 : 3 : return TRUE;
647 : :
648 : 48 : while (child)
649 : : {
650 : 37 : current = child;
651 : 37 : child = current->next;
652 : 37 : if (g_node_traverse_in_order (current, flags, func, data))
653 : 12 : return TRUE;
654 : : }
655 : : }
656 : 98 : else if ((flags & G_TRAVERSE_LEAFS) &&
657 : 49 : func (node, data))
658 : 8 : return TRUE;
659 : :
660 : 52 : return FALSE;
661 : : }
662 : :
663 : : static gboolean
664 : 52 : g_node_depth_traverse_in_order (GNode *node,
665 : : GTraverseFlags flags,
666 : : guint depth,
667 : : GNodeTraverseFunc func,
668 : : gpointer data)
669 : : {
670 : 52 : if (node->children)
671 : : {
672 : 30 : depth--;
673 : 30 : if (depth)
674 : : {
675 : : GNode *child;
676 : : GNode *current;
677 : :
678 : 23 : child = node->children;
679 : 23 : current = child;
680 : 23 : child = current->next;
681 : :
682 : 23 : if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
683 : 6 : return TRUE;
684 : :
685 : 34 : if ((flags & G_TRAVERSE_NON_LEAFS) &&
686 : 17 : func (node, data))
687 : 3 : return TRUE;
688 : :
689 : 28 : while (child)
690 : : {
691 : 18 : current = child;
692 : 18 : child = current->next;
693 : 18 : if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
694 : 4 : return TRUE;
695 : : }
696 : : }
697 : 14 : else if ((flags & G_TRAVERSE_NON_LEAFS) &&
698 : 7 : func (node, data))
699 : 1 : return TRUE;
700 : : }
701 : 44 : else if ((flags & G_TRAVERSE_LEAFS) &&
702 : 22 : func (node, data))
703 : 3 : return TRUE;
704 : :
705 : 35 : return FALSE;
706 : : }
707 : :
708 : : static gboolean
709 : 349 : g_node_traverse_level (GNode *node,
710 : : GTraverseFlags flags,
711 : : guint level,
712 : : GNodeTraverseFunc func,
713 : : gpointer data,
714 : : gboolean *more_levels)
715 : : {
716 : 349 : if (level == 0)
717 : : {
718 : 200 : if (node->children)
719 : : {
720 : 97 : *more_levels = TRUE;
721 : 97 : return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
722 : : }
723 : : else
724 : : {
725 : 103 : return (flags & G_TRAVERSE_LEAFS) && func (node, data);
726 : : }
727 : : }
728 : : else
729 : : {
730 : 149 : node = node->children;
731 : :
732 : 375 : while (node)
733 : : {
734 : 255 : if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
735 : 29 : return TRUE;
736 : :
737 : 226 : node = node->next;
738 : : }
739 : : }
740 : :
741 : 120 : return FALSE;
742 : : }
743 : :
744 : : static gboolean
745 : 34 : 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 : 34 : level = 0;
755 : 99 : while (depth < 0 || level != (guint) depth)
756 : : {
757 : 94 : more_levels = FALSE;
758 : 94 : if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
759 : 17 : return TRUE;
760 : 77 : if (!more_levels)
761 : 12 : break;
762 : 65 : level++;
763 : : }
764 : 17 : 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().
804 : : *
805 : : * The different orders are illustrated here:
806 : : *
807 : : * - In order: A, B, C, D, E, F, G, H, I
808 : : * <picture>
809 : : * <source srcset="Sorted_binary_tree_inorder-dark.svg"
810 : : * media="(prefers-color-scheme: dark)">
811 : : * <img src="Sorted_binary_tree_inorder.svg"
812 : : * alt="Sorted binary tree, in-order traversal">
813 : : * </picture>
814 : : * - Pre order: F, B, A, D, C, E, G, I, H
815 : : * <picture>
816 : : * <source srcset="Sorted_binary_tree_preorder-dark.svg"
817 : : * media="(prefers-color-scheme: dark)">
818 : : * <img src="Sorted_binary_tree_preorder.svg"
819 : : * alt="Sorted binary tree, pre-order traversal">
820 : : * </picture>
821 : : * - Post order: A, C, E, D, B, H, I, G, F
822 : : * <picture>
823 : : * <source srcset="Sorted_binary_tree_postorder-dark.svg"
824 : : * media="(prefers-color-scheme: dark)">
825 : : * <img src="Sorted_binary_tree_postorder.svg"
826 : : * alt="Sorted binary tree, post-order traversal">
827 : : * </picture>
828 : : * - Level order: F, B, G, A, D, I, C, E, H
829 : : * <picture>
830 : : * <source srcset="Sorted_binary_tree_breadth-first_traversal-dark.svg"
831 : : * media="(prefers-color-scheme: dark)">
832 : : * <img src="Sorted_binary_tree_breadth-first_traversal.svg"
833 : : * alt="Sorted binary tree, breadth-first level order traversal">
834 : : * </picture>
835 : : */
836 : :
837 : : /**
838 : : * GTraverseFlags:
839 : : * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
840 : : * been introduced in 2.6, for older version use
841 : : * %G_TRAVERSE_LEAFS.
842 : : * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
843 : : * name has been introduced in 2.6, for older
844 : : * version use %G_TRAVERSE_NON_LEAFS.
845 : : * @G_TRAVERSE_ALL: all nodes should be visited.
846 : : * @G_TRAVERSE_MASK: a mask of all traverse flags.
847 : : * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
848 : : * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
849 : : *
850 : : * Specifies which nodes are visited during several of the tree
851 : : * functions, including g_node_traverse() and g_node_find().
852 : : **/
853 : : /**
854 : : * GNodeTraverseFunc:
855 : : * @node: a #GNode.
856 : : * @data: user data passed to g_node_traverse().
857 : : *
858 : : * Specifies the type of function passed to g_node_traverse(). The
859 : : * function is called with each of the nodes visited, together with the
860 : : * user data passed to g_node_traverse(). If the function returns
861 : : * %TRUE, then the traversal is stopped.
862 : : *
863 : : * Returns: %TRUE to stop the traversal.
864 : : **/
865 : : void
866 : 104 : g_node_traverse (GNode *root,
867 : : GTraverseType order,
868 : : GTraverseFlags flags,
869 : : gint depth,
870 : : GNodeTraverseFunc func,
871 : : gpointer data)
872 : : {
873 : 104 : g_return_if_fail (root != NULL);
874 : 104 : g_return_if_fail (func != NULL);
875 : 104 : g_return_if_fail (order <= G_LEVEL_ORDER);
876 : 104 : g_return_if_fail (flags <= G_TRAVERSE_MASK);
877 : 104 : g_return_if_fail (depth == -1 || depth > 0);
878 : :
879 : 104 : switch (order)
880 : : {
881 : 25 : case G_PRE_ORDER:
882 : 25 : if (depth < 0)
883 : 13 : g_node_traverse_pre_order (root, flags, func, data);
884 : : else
885 : 12 : g_node_depth_traverse_pre_order (root, flags, depth, func, data);
886 : 25 : break;
887 : 22 : case G_POST_ORDER:
888 : 22 : if (depth < 0)
889 : 11 : g_node_traverse_post_order (root, flags, func, data);
890 : : else
891 : 11 : g_node_depth_traverse_post_order (root, flags, depth, func, data);
892 : 22 : break;
893 : 23 : case G_IN_ORDER:
894 : 23 : if (depth < 0)
895 : 12 : g_node_traverse_in_order (root, flags, func, data);
896 : : else
897 : 11 : g_node_depth_traverse_in_order (root, flags, depth, func, data);
898 : 23 : break;
899 : 34 : case G_LEVEL_ORDER:
900 : 34 : g_node_depth_traverse_level (root, flags, depth, func, data);
901 : 34 : break;
902 : : }
903 : : }
904 : :
905 : : static gboolean
906 : 10 : g_node_find_func (GNode *node,
907 : : gpointer data)
908 : : {
909 : 10 : gpointer *d = data;
910 : :
911 : 10 : if (*d != node->data)
912 : 9 : return FALSE;
913 : :
914 : 1 : *(++d) = node;
915 : :
916 : 1 : return TRUE;
917 : : }
918 : :
919 : : /**
920 : : * g_node_find:
921 : : * @root: the root #GNode of the tree to search
922 : : * @order: the order in which nodes are visited - %G_IN_ORDER,
923 : : * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
924 : : * @flags: which types of children are to be searched, one of
925 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
926 : : * @data: the data to find
927 : : *
928 : : * Finds a #GNode in a tree.
929 : : *
930 : : * Returns: the found #GNode, or %NULL if the data is not found
931 : : */
932 : : GNode*
933 : 2 : g_node_find (GNode *root,
934 : : GTraverseType order,
935 : : GTraverseFlags flags,
936 : : gpointer data)
937 : : {
938 : : gpointer d[2];
939 : :
940 : 2 : g_return_val_if_fail (root != NULL, NULL);
941 : 2 : g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
942 : 2 : g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
943 : :
944 : 2 : d[0] = data;
945 : 2 : d[1] = NULL;
946 : :
947 : 2 : g_node_traverse (root, order, flags, -1, g_node_find_func, d);
948 : :
949 : 2 : return d[1];
950 : : }
951 : :
952 : : static void
953 : 2082 : g_node_count_func (GNode *node,
954 : : GTraverseFlags flags,
955 : : guint *n)
956 : : {
957 : 2082 : if (node->children)
958 : : {
959 : : GNode *child;
960 : :
961 : 422 : if (flags & G_TRAVERSE_NON_LEAFS)
962 : 418 : (*n)++;
963 : :
964 : 422 : child = node->children;
965 : 2500 : while (child)
966 : : {
967 : 2078 : g_node_count_func (child, flags, n);
968 : 2078 : child = child->next;
969 : : }
970 : : }
971 : 1660 : else if (flags & G_TRAVERSE_LEAFS)
972 : 1653 : (*n)++;
973 : 2082 : }
974 : :
975 : : /**
976 : : * g_node_n_nodes:
977 : : * @root: a #GNode
978 : : * @flags: which types of children are to be counted, one of
979 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
980 : : *
981 : : * Gets the number of nodes in a tree.
982 : : *
983 : : * Returns: the number of nodes in the tree
984 : : */
985 : : guint
986 : 4 : g_node_n_nodes (GNode *root,
987 : : GTraverseFlags flags)
988 : : {
989 : 4 : guint n = 0;
990 : :
991 : 4 : g_return_val_if_fail (root != NULL, 0);
992 : 4 : g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
993 : :
994 : 4 : g_node_count_func (root, flags, &n);
995 : :
996 : 4 : return n;
997 : : }
998 : :
999 : : /**
1000 : : * g_node_last_child:
1001 : : * @node: a #GNode (must not be %NULL)
1002 : : *
1003 : : * Gets the last child of a #GNode.
1004 : : *
1005 : : * Returns: the last child of @node, or %NULL if @node has no children
1006 : : */
1007 : : GNode*
1008 : 8 : g_node_last_child (GNode *node)
1009 : : {
1010 : 8 : g_return_val_if_fail (node != NULL, NULL);
1011 : :
1012 : 8 : node = node->children;
1013 : 8 : if (node)
1014 : 6 : while (node->next)
1015 : 4 : node = node->next;
1016 : :
1017 : 8 : return node;
1018 : : }
1019 : :
1020 : : /**
1021 : : * g_node_nth_child:
1022 : : * @node: a #GNode
1023 : : * @n: the index of the desired child
1024 : : *
1025 : : * Gets a child of a #GNode, using the given index.
1026 : : * The first child is at index 0. If the index is
1027 : : * too big, %NULL is returned.
1028 : : *
1029 : : * Returns: the child of @node at index @n
1030 : : */
1031 : : GNode*
1032 : 13 : g_node_nth_child (GNode *node,
1033 : : guint n)
1034 : : {
1035 : 13 : g_return_val_if_fail (node != NULL, NULL);
1036 : :
1037 : 13 : node = node->children;
1038 : 13 : if (node)
1039 : 28 : while ((n-- > 0) && node)
1040 : 15 : node = node->next;
1041 : :
1042 : 13 : return node;
1043 : : }
1044 : :
1045 : : /**
1046 : : * g_node_n_children:
1047 : : * @node: a #GNode
1048 : : *
1049 : : * Gets the number of children of a #GNode.
1050 : : *
1051 : : * Returns: the number of children of @node
1052 : : */
1053 : : guint
1054 : 10 : g_node_n_children (GNode *node)
1055 : : {
1056 : 10 : guint n = 0;
1057 : :
1058 : 10 : g_return_val_if_fail (node != NULL, 0);
1059 : :
1060 : 10 : node = node->children;
1061 : 46 : while (node)
1062 : : {
1063 : 36 : n++;
1064 : 36 : node = node->next;
1065 : : }
1066 : :
1067 : 10 : return n;
1068 : : }
1069 : :
1070 : : /**
1071 : : * g_node_find_child:
1072 : : * @node: a #GNode
1073 : : * @flags: which types of children are to be searched, one of
1074 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1075 : : * @data: the data to find
1076 : : *
1077 : : * Finds the first child of a #GNode with the given data.
1078 : : *
1079 : : * Returns: the found child #GNode, or %NULL if the data is not found
1080 : : */
1081 : : GNode*
1082 : 3 : g_node_find_child (GNode *node,
1083 : : GTraverseFlags flags,
1084 : : gpointer data)
1085 : : {
1086 : 3 : g_return_val_if_fail (node != NULL, NULL);
1087 : 3 : g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
1088 : :
1089 : 3 : node = node->children;
1090 : 6 : while (node)
1091 : : {
1092 : 5 : if (node->data == data)
1093 : : {
1094 : 2 : if (G_NODE_IS_LEAF (node))
1095 : : {
1096 : 1 : if (flags & G_TRAVERSE_LEAFS)
1097 : 1 : return node;
1098 : : }
1099 : : else
1100 : : {
1101 : 1 : if (flags & G_TRAVERSE_NON_LEAFS)
1102 : 1 : return node;
1103 : : }
1104 : : }
1105 : 3 : node = node->next;
1106 : : }
1107 : :
1108 : 1 : return NULL;
1109 : : }
1110 : :
1111 : : /**
1112 : : * g_node_child_position:
1113 : : * @node: a #GNode
1114 : : * @child: a child of @node
1115 : : *
1116 : : * Gets the position of a #GNode with respect to its siblings.
1117 : : * @child must be a child of @node. The first child is numbered 0,
1118 : : * the second 1, and so on.
1119 : : *
1120 : : * Returns: the position of @child with respect to its siblings
1121 : : */
1122 : : gint
1123 : 4 : g_node_child_position (GNode *node,
1124 : : GNode *child)
1125 : : {
1126 : 4 : guint n = 0;
1127 : :
1128 : 4 : g_return_val_if_fail (node != NULL, -1);
1129 : 4 : g_return_val_if_fail (child != NULL, -1);
1130 : 4 : g_return_val_if_fail (child->parent == node, -1);
1131 : :
1132 : 4 : node = node->children;
1133 : 10 : while (node)
1134 : : {
1135 : 10 : if (node == child)
1136 : 4 : return n;
1137 : 6 : n++;
1138 : 6 : node = node->next;
1139 : : }
1140 : :
1141 : 0 : return -1;
1142 : : }
1143 : :
1144 : : /**
1145 : : * g_node_child_index:
1146 : : * @node: a #GNode
1147 : : * @data: the data to find
1148 : : *
1149 : : * Gets the position of the first child of a #GNode
1150 : : * which contains the given data.
1151 : : *
1152 : : * Returns: the index of the child of @node which contains
1153 : : * @data, or -1 if the data is not found
1154 : : */
1155 : : gint
1156 : 4 : g_node_child_index (GNode *node,
1157 : : gpointer data)
1158 : : {
1159 : 4 : guint n = 0;
1160 : :
1161 : 4 : g_return_val_if_fail (node != NULL, -1);
1162 : :
1163 : 4 : node = node->children;
1164 : 10 : while (node)
1165 : : {
1166 : 9 : if (node->data == data)
1167 : 3 : return n;
1168 : 6 : n++;
1169 : 6 : node = node->next;
1170 : : }
1171 : :
1172 : 1 : return -1;
1173 : : }
1174 : :
1175 : : /**
1176 : : * g_node_first_sibling:
1177 : : * @node: a #GNode
1178 : : *
1179 : : * Gets the first sibling of a #GNode.
1180 : : * This could possibly be the node itself.
1181 : : *
1182 : : * Returns: the first sibling of @node
1183 : : */
1184 : : GNode*
1185 : 3 : g_node_first_sibling (GNode *node)
1186 : : {
1187 : 3 : g_return_val_if_fail (node != NULL, NULL);
1188 : :
1189 : 3 : if (node->parent)
1190 : 2 : return node->parent->children;
1191 : :
1192 : 1 : while (node->prev)
1193 : 0 : node = node->prev;
1194 : :
1195 : 1 : return node;
1196 : : }
1197 : :
1198 : : /**
1199 : : * g_node_last_sibling:
1200 : : * @node: a #GNode
1201 : : *
1202 : : * Gets the last sibling of a #GNode.
1203 : : * This could possibly be the node itself.
1204 : : *
1205 : : * Returns: the last sibling of @node
1206 : : */
1207 : : GNode*
1208 : 3 : g_node_last_sibling (GNode *node)
1209 : : {
1210 : 3 : g_return_val_if_fail (node != NULL, NULL);
1211 : :
1212 : 6 : while (node->next)
1213 : 3 : node = node->next;
1214 : :
1215 : 3 : return node;
1216 : : }
1217 : :
1218 : : /**
1219 : : * g_node_children_foreach:
1220 : : * @node: a #GNode
1221 : : * @flags: which types of children are to be visited, one of
1222 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1223 : : * @func: (scope call): the function to call for each visited node
1224 : : * @data: user data to pass to the function
1225 : : *
1226 : : * Calls a function for each of the children of a #GNode. Note that it
1227 : : * doesn't descend beneath the child nodes. @func must not do anything
1228 : : * that would modify the structure of the tree.
1229 : : */
1230 : : /**
1231 : : * GNodeForeachFunc:
1232 : : * @node: a #GNode.
1233 : : * @data: user data passed to g_node_children_foreach().
1234 : : *
1235 : : * Specifies the type of function passed to g_node_children_foreach().
1236 : : * The function is called with each child node, together with the user
1237 : : * data passed to g_node_children_foreach().
1238 : : **/
1239 : : void
1240 : 3 : g_node_children_foreach (GNode *node,
1241 : : GTraverseFlags flags,
1242 : : GNodeForeachFunc func,
1243 : : gpointer data)
1244 : : {
1245 : 3 : g_return_if_fail (node != NULL);
1246 : 3 : g_return_if_fail (flags <= G_TRAVERSE_MASK);
1247 : 3 : g_return_if_fail (func != NULL);
1248 : :
1249 : 3 : node = node->children;
1250 : 12 : while (node)
1251 : : {
1252 : : GNode *current;
1253 : :
1254 : 9 : current = node;
1255 : 9 : node = current->next;
1256 : 9 : if (G_NODE_IS_LEAF (current))
1257 : : {
1258 : 6 : if (flags & G_TRAVERSE_LEAFS)
1259 : 4 : func (current, data);
1260 : : }
1261 : : else
1262 : : {
1263 : 3 : if (flags & G_TRAVERSE_NON_LEAFS)
1264 : 2 : func (current, data);
1265 : : }
1266 : : }
1267 : : }
|
