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