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