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