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