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