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(). The different orders are
804 : : * illustrated here:
805 : : * - In order: A, B, C, D, E, F, G, H, I
806 : : * 
807 : : * - Pre order: F, B, A, D, C, E, G, I, H
808 : : * 
809 : : * - Post order: A, C, E, D, B, H, I, G, F
810 : : * 
811 : : * - Level order: F, B, G, A, D, I, C, E, H
812 : : * 
813 : : */
814 : :
815 : : /**
816 : : * GTraverseFlags:
817 : : * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
818 : : * been introduced in 2.6, for older version use
819 : : * %G_TRAVERSE_LEAFS.
820 : : * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
821 : : * name has been introduced in 2.6, for older
822 : : * version use %G_TRAVERSE_NON_LEAFS.
823 : : * @G_TRAVERSE_ALL: all nodes should be visited.
824 : : * @G_TRAVERSE_MASK: a mask of all traverse flags.
825 : : * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
826 : : * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
827 : : *
828 : : * Specifies which nodes are visited during several of the tree
829 : : * functions, including g_node_traverse() and g_node_find().
830 : : **/
831 : : /**
832 : : * GNodeTraverseFunc:
833 : : * @node: a #GNode.
834 : : * @data: user data passed to g_node_traverse().
835 : : *
836 : : * Specifies the type of function passed to g_node_traverse(). The
837 : : * function is called with each of the nodes visited, together with the
838 : : * user data passed to g_node_traverse(). If the function returns
839 : : * %TRUE, then the traversal is stopped.
840 : : *
841 : : * Returns: %TRUE to stop the traversal.
842 : : **/
843 : : void
844 : 104 : g_node_traverse (GNode *root,
845 : : GTraverseType order,
846 : : GTraverseFlags flags,
847 : : gint depth,
848 : : GNodeTraverseFunc func,
849 : : gpointer data)
850 : : {
851 : 104 : g_return_if_fail (root != NULL);
852 : 104 : g_return_if_fail (func != NULL);
853 : 104 : g_return_if_fail (order <= G_LEVEL_ORDER);
854 : 104 : g_return_if_fail (flags <= G_TRAVERSE_MASK);
855 : 104 : g_return_if_fail (depth == -1 || depth > 0);
856 : :
857 [ + + + + : 104 : switch (order)
- ]
858 : : {
859 : 25 : case G_PRE_ORDER:
860 [ + + ]: 25 : if (depth < 0)
861 : 13 : g_node_traverse_pre_order (root, flags, func, data);
862 : : else
863 : 12 : g_node_depth_traverse_pre_order (root, flags, depth, func, data);
864 : 25 : break;
865 : 22 : case G_POST_ORDER:
866 [ + + ]: 22 : if (depth < 0)
867 : 11 : g_node_traverse_post_order (root, flags, func, data);
868 : : else
869 : 11 : g_node_depth_traverse_post_order (root, flags, depth, func, data);
870 : 22 : break;
871 : 23 : case G_IN_ORDER:
872 [ + + ]: 23 : if (depth < 0)
873 : 12 : g_node_traverse_in_order (root, flags, func, data);
874 : : else
875 : 11 : g_node_depth_traverse_in_order (root, flags, depth, func, data);
876 : 23 : break;
877 : 34 : case G_LEVEL_ORDER:
878 : 34 : g_node_depth_traverse_level (root, flags, depth, func, data);
879 : 34 : break;
880 : : }
881 : : }
882 : :
883 : : static gboolean
884 : 10 : g_node_find_func (GNode *node,
885 : : gpointer data)
886 : : {
887 : 10 : gpointer *d = data;
888 : :
889 [ + + ]: 10 : if (*d != node->data)
890 : 9 : return FALSE;
891 : :
892 : 1 : *(++d) = node;
893 : :
894 : 1 : return TRUE;
895 : : }
896 : :
897 : : /**
898 : : * g_node_find:
899 : : * @root: the root #GNode of the tree to search
900 : : * @order: the order in which nodes are visited - %G_IN_ORDER,
901 : : * %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
902 : : * @flags: which types of children are to be searched, one of
903 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
904 : : * @data: the data to find
905 : : *
906 : : * Finds a #GNode in a tree.
907 : : *
908 : : * Returns: the found #GNode, or %NULL if the data is not found
909 : : */
910 : : GNode*
911 : 2 : g_node_find (GNode *root,
912 : : GTraverseType order,
913 : : GTraverseFlags flags,
914 : : gpointer data)
915 : : {
916 : : gpointer d[2];
917 : :
918 : 2 : g_return_val_if_fail (root != NULL, NULL);
919 : 2 : g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
920 : 2 : g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
921 : :
922 : 2 : d[0] = data;
923 : 2 : d[1] = NULL;
924 : :
925 : 2 : g_node_traverse (root, order, flags, -1, g_node_find_func, d);
926 : :
927 : 2 : return d[1];
928 : : }
929 : :
930 : : static void
931 : 2082 : g_node_count_func (GNode *node,
932 : : GTraverseFlags flags,
933 : : guint *n)
934 : : {
935 [ + + ]: 2082 : if (node->children)
936 : : {
937 : : GNode *child;
938 : :
939 [ + + ]: 422 : if (flags & G_TRAVERSE_NON_LEAFS)
940 : 418 : (*n)++;
941 : :
942 : 422 : child = node->children;
943 [ + + ]: 2500 : while (child)
944 : : {
945 : 2078 : g_node_count_func (child, flags, n);
946 : 2078 : child = child->next;
947 : : }
948 : : }
949 [ + + ]: 1660 : else if (flags & G_TRAVERSE_LEAFS)
950 : 1653 : (*n)++;
951 : 2082 : }
952 : :
953 : : /**
954 : : * g_node_n_nodes:
955 : : * @root: a #GNode
956 : : * @flags: which types of children are to be counted, one of
957 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
958 : : *
959 : : * Gets the number of nodes in a tree.
960 : : *
961 : : * Returns: the number of nodes in the tree
962 : : */
963 : : guint
964 : 4 : g_node_n_nodes (GNode *root,
965 : : GTraverseFlags flags)
966 : : {
967 : 4 : guint n = 0;
968 : :
969 : 4 : g_return_val_if_fail (root != NULL, 0);
970 : 4 : g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
971 : :
972 : 4 : g_node_count_func (root, flags, &n);
973 : :
974 : 4 : return n;
975 : : }
976 : :
977 : : /**
978 : : * g_node_last_child:
979 : : * @node: a #GNode (must not be %NULL)
980 : : *
981 : : * Gets the last child of a #GNode.
982 : : *
983 : : * Returns: the last child of @node, or %NULL if @node has no children
984 : : */
985 : : GNode*
986 : 8 : g_node_last_child (GNode *node)
987 : : {
988 : 8 : g_return_val_if_fail (node != NULL, NULL);
989 : :
990 : 8 : node = node->children;
991 [ + + ]: 8 : if (node)
992 [ + + ]: 6 : while (node->next)
993 : 4 : node = node->next;
994 : :
995 : 8 : return node;
996 : : }
997 : :
998 : : /**
999 : : * g_node_nth_child:
1000 : : * @node: a #GNode
1001 : : * @n: the index of the desired child
1002 : : *
1003 : : * Gets a child of a #GNode, using the given index.
1004 : : * The first child is at index 0. If the index is
1005 : : * too big, %NULL is returned.
1006 : : *
1007 : : * Returns: the child of @node at index @n
1008 : : */
1009 : : GNode*
1010 : 13 : g_node_nth_child (GNode *node,
1011 : : guint n)
1012 : : {
1013 : 13 : g_return_val_if_fail (node != NULL, NULL);
1014 : :
1015 : 13 : node = node->children;
1016 [ + - ]: 13 : if (node)
1017 [ + + + + ]: 28 : while ((n-- > 0) && node)
1018 : 15 : node = node->next;
1019 : :
1020 : 13 : return node;
1021 : : }
1022 : :
1023 : : /**
1024 : : * g_node_n_children:
1025 : : * @node: a #GNode
1026 : : *
1027 : : * Gets the number of children of a #GNode.
1028 : : *
1029 : : * Returns: the number of children of @node
1030 : : */
1031 : : guint
1032 : 10 : g_node_n_children (GNode *node)
1033 : : {
1034 : 10 : guint n = 0;
1035 : :
1036 : 10 : g_return_val_if_fail (node != NULL, 0);
1037 : :
1038 : 10 : node = node->children;
1039 [ + + ]: 46 : while (node)
1040 : : {
1041 : 36 : n++;
1042 : 36 : node = node->next;
1043 : : }
1044 : :
1045 : 10 : return n;
1046 : : }
1047 : :
1048 : : /**
1049 : : * g_node_find_child:
1050 : : * @node: a #GNode
1051 : : * @flags: which types of children are to be searched, one of
1052 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1053 : : * @data: the data to find
1054 : : *
1055 : : * Finds the first child of a #GNode with the given data.
1056 : : *
1057 : : * Returns: the found child #GNode, or %NULL if the data is not found
1058 : : */
1059 : : GNode*
1060 : 3 : g_node_find_child (GNode *node,
1061 : : GTraverseFlags flags,
1062 : : gpointer data)
1063 : : {
1064 : 3 : g_return_val_if_fail (node != NULL, NULL);
1065 : 3 : g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
1066 : :
1067 : 3 : node = node->children;
1068 [ + + ]: 6 : while (node)
1069 : : {
1070 [ + + ]: 5 : if (node->data == data)
1071 : : {
1072 [ + + ]: 2 : if (G_NODE_IS_LEAF (node))
1073 : : {
1074 [ + - ]: 1 : if (flags & G_TRAVERSE_LEAFS)
1075 : 1 : return node;
1076 : : }
1077 : : else
1078 : : {
1079 [ + - ]: 1 : if (flags & G_TRAVERSE_NON_LEAFS)
1080 : 1 : return node;
1081 : : }
1082 : : }
1083 : 3 : node = node->next;
1084 : : }
1085 : :
1086 : 1 : return NULL;
1087 : : }
1088 : :
1089 : : /**
1090 : : * g_node_child_position:
1091 : : * @node: a #GNode
1092 : : * @child: a child of @node
1093 : : *
1094 : : * Gets the position of a #GNode with respect to its siblings.
1095 : : * @child must be a child of @node. The first child is numbered 0,
1096 : : * the second 1, and so on.
1097 : : *
1098 : : * Returns: the position of @child with respect to its siblings
1099 : : */
1100 : : gint
1101 : 4 : g_node_child_position (GNode *node,
1102 : : GNode *child)
1103 : : {
1104 : 4 : guint n = 0;
1105 : :
1106 : 4 : g_return_val_if_fail (node != NULL, -1);
1107 : 4 : g_return_val_if_fail (child != NULL, -1);
1108 : 4 : g_return_val_if_fail (child->parent == node, -1);
1109 : :
1110 : 4 : node = node->children;
1111 [ + - ]: 10 : while (node)
1112 : : {
1113 [ + + ]: 10 : if (node == child)
1114 : 4 : return n;
1115 : 6 : n++;
1116 : 6 : node = node->next;
1117 : : }
1118 : :
1119 : 0 : return -1;
1120 : : }
1121 : :
1122 : : /**
1123 : : * g_node_child_index:
1124 : : * @node: a #GNode
1125 : : * @data: the data to find
1126 : : *
1127 : : * Gets the position of the first child of a #GNode
1128 : : * which contains the given data.
1129 : : *
1130 : : * Returns: the index of the child of @node which contains
1131 : : * @data, or -1 if the data is not found
1132 : : */
1133 : : gint
1134 : 4 : g_node_child_index (GNode *node,
1135 : : gpointer data)
1136 : : {
1137 : 4 : guint n = 0;
1138 : :
1139 : 4 : g_return_val_if_fail (node != NULL, -1);
1140 : :
1141 : 4 : node = node->children;
1142 [ + + ]: 10 : while (node)
1143 : : {
1144 [ + + ]: 9 : if (node->data == data)
1145 : 3 : return n;
1146 : 6 : n++;
1147 : 6 : node = node->next;
1148 : : }
1149 : :
1150 : 1 : return -1;
1151 : : }
1152 : :
1153 : : /**
1154 : : * g_node_first_sibling:
1155 : : * @node: a #GNode
1156 : : *
1157 : : * Gets the first sibling of a #GNode.
1158 : : * This could possibly be the node itself.
1159 : : *
1160 : : * Returns: the first sibling of @node
1161 : : */
1162 : : GNode*
1163 : 3 : g_node_first_sibling (GNode *node)
1164 : : {
1165 : 3 : g_return_val_if_fail (node != NULL, NULL);
1166 : :
1167 [ + + ]: 3 : if (node->parent)
1168 : 2 : return node->parent->children;
1169 : :
1170 [ - + ]: 1 : while (node->prev)
1171 : 0 : node = node->prev;
1172 : :
1173 : 1 : return node;
1174 : : }
1175 : :
1176 : : /**
1177 : : * g_node_last_sibling:
1178 : : * @node: a #GNode
1179 : : *
1180 : : * Gets the last sibling of a #GNode.
1181 : : * This could possibly be the node itself.
1182 : : *
1183 : : * Returns: the last sibling of @node
1184 : : */
1185 : : GNode*
1186 : 3 : g_node_last_sibling (GNode *node)
1187 : : {
1188 : 3 : g_return_val_if_fail (node != NULL, NULL);
1189 : :
1190 [ + + ]: 6 : while (node->next)
1191 : 3 : node = node->next;
1192 : :
1193 : 3 : return node;
1194 : : }
1195 : :
1196 : : /**
1197 : : * g_node_children_foreach:
1198 : : * @node: a #GNode
1199 : : * @flags: which types of children are to be visited, one of
1200 : : * %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1201 : : * @func: (scope call): the function to call for each visited node
1202 : : * @data: user data to pass to the function
1203 : : *
1204 : : * Calls a function for each of the children of a #GNode. Note that it
1205 : : * doesn't descend beneath the child nodes. @func must not do anything
1206 : : * that would modify the structure of the tree.
1207 : : */
1208 : : /**
1209 : : * GNodeForeachFunc:
1210 : : * @node: a #GNode.
1211 : : * @data: user data passed to g_node_children_foreach().
1212 : : *
1213 : : * Specifies the type of function passed to g_node_children_foreach().
1214 : : * The function is called with each child node, together with the user
1215 : : * data passed to g_node_children_foreach().
1216 : : **/
1217 : : void
1218 : 3 : g_node_children_foreach (GNode *node,
1219 : : GTraverseFlags flags,
1220 : : GNodeForeachFunc func,
1221 : : gpointer data)
1222 : : {
1223 : 3 : g_return_if_fail (node != NULL);
1224 : 3 : g_return_if_fail (flags <= G_TRAVERSE_MASK);
1225 : 3 : g_return_if_fail (func != NULL);
1226 : :
1227 : 3 : node = node->children;
1228 [ + + ]: 12 : while (node)
1229 : : {
1230 : : GNode *current;
1231 : :
1232 : 9 : current = node;
1233 : 9 : node = current->next;
1234 [ + + ]: 9 : if (G_NODE_IS_LEAF (current))
1235 : : {
1236 [ + + ]: 6 : if (flags & G_TRAVERSE_LEAFS)
1237 : 4 : func (current, data);
1238 : : }
1239 : : else
1240 : : {
1241 [ + + ]: 3 : if (flags & G_TRAVERSE_NON_LEAFS)
1242 : 2 : func (current, data);
1243 : : }
1244 : : }
1245 : : }
|
