glib/gnode.c

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