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