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