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  * @Returns: %TRUE to stop the traversal.
 844  *
 845  * Specifies the type of function passed to g_node_traverse(). The
 846  * function is called with each of the nodes visited, together with the
 847  * user data passed to g_node_traverse(). If the function returns
 848  * %TRUE, then the traversal is stopped.
 849  **/
 850 void
 851 g_node_traverse (GNode            *root,
 852                  GTraverseType     order,
 853                  GTraverseFlags    flags,
 854                  gint              depth,
 855                  GNodeTraverseFunc func,
 856                  gpointer          data)
 857 {
 858   g_return_if_fail (root != NULL);
 859   g_return_if_fail (func != NULL);
 860   g_return_if_fail (order <= G_LEVEL_ORDER);
 861   g_return_if_fail (flags <= G_TRAVERSE_MASK);
 862   g_return_if_fail (depth == -1 || depth > 0);
 863
 864   switch (order)
 865     {
 866     case G_PRE_ORDER:
 867       if (depth < 0)
 868         g_node_traverse_pre_order (root, flags, func, data);
 869       else
 870         g_node_depth_traverse_pre_order (root, flags, depth, func, data);
 871       break;
 872     case G_POST_ORDER:
 873       if (depth < 0)
 874         g_node_traverse_post_order (root, flags, func, data);
 875       else
 876         g_node_depth_traverse_post_order (root, flags, depth, func, data);
 877       break;
 878     case G_IN_ORDER:
 879       if (depth < 0)
 880         g_node_traverse_in_order (root, flags, func, data);
 881       else
 882         g_node_depth_traverse_in_order (root, flags, depth, func, data);
 883       break;
 884     case G_LEVEL_ORDER:
 885       g_node_depth_traverse_level (root, flags, depth, func, data);
 886       break;
 887     }
 888 }
 889
 890 static gboolean
 891 g_node_find_func (GNode    *node,
 892                   gpointer  data)
 893 {
 894   gpointer *d = data;
 895
 896   if (*d != node->data)
 897     return FALSE;
 898
 899   *(++d) = node;
 900
 901   return TRUE;
 902 }
 903
 904 /**
 905  * g_node_find:
 906  * @root: the root #GNode of the tree to search
 907  * @order: the order in which nodes are visited - %G_IN_ORDER,
 908  *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
 909  * @flags: which types of children are to be searched, one of
 910  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
 911  * @data: the data to find
 912  *
 913  * Finds a #GNode in a tree.
 914  *
 915  * Returns: the found #GNode, or %NULL if the data is not found
 916  */
 917 GNode*
 918 g_node_find (GNode          *root,
 919              GTraverseType   order,
 920              GTraverseFlags  flags,
 921              gpointer        data)
 922 {
 923   gpointer d[2];
 924
 925   g_return_val_if_fail (root != NULL, NULL);
 926   g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
 927   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
 928
 929   d[0] = data;
 930   d[1] = NULL;
 931
 932   g_node_traverse (root, order, flags, -1, g_node_find_func, d);
 933
 934   return d[1];
 935 }
 936
 937 static void
 938 g_node_count_func (GNode         *node,
 939                    GTraverseFlags flags,
 940                    guint         *n)
 941 {
 942   if (node->children)
 943     {
 944       GNode *child;
 945
 946       if (flags & G_TRAVERSE_NON_LEAFS)
 947         (*n)++;
 948
 949       child = node->children;
 950       while (child)
 951         {
 952           g_node_count_func (child, flags, n);
 953           child = child->next;
 954         }
 955     }
 956   else if (flags & G_TRAVERSE_LEAFS)
 957     (*n)++;
 958 }
 959
 960 /**
 961  * g_node_n_nodes:
 962  * @root: a #GNode
 963  * @flags: which types of children are to be counted, one of
 964  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
 965  *
 966  * Gets the number of nodes in a tree.
 967  *
 968  * Returns: the number of nodes in the tree
 969  */
 970 guint
 971 g_node_n_nodes (GNode          *root,
 972                 GTraverseFlags  flags)
 973 {
 974   guint n = 0;
 975
 976   g_return_val_if_fail (root != NULL, 0);
 977   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
 978
 979   g_node_count_func (root, flags, &n);
 980
 981   return n;
 982 }
 983
 984 /**
 985  * g_node_last_child:
 986  * @node: a #GNode (must not be %NULL)
 987  *
 988  * Gets the last child of a #GNode.
 989  *
 990  * Returns: the last child of @node, or %NULL if @node has no children
 991  */
 992 GNode*
 993 g_node_last_child (GNode *node)
 994 {
 995   g_return_val_if_fail (node != NULL, NULL);
 996
 997   node = node->children;
 998   if (node)
 999     while (node->next)
1000       node = node->next;
1001
1002   return node;
1003 }
1004
1005 /**
1006  * g_node_nth_child:
1007  * @node: a #GNode
1008  * @n: the index of the desired child
1009  *
1010  * Gets a child of a #GNode, using the given index.
1011  * The first child is at index 0. If the index is
1012  * too big, %NULL is returned.
1013  *
1014  * Returns: the child of @node at index @n
1015  */
1016 GNode*
1017 g_node_nth_child (GNode *node,
1018                   guint  n)
1019 {
1020   g_return_val_if_fail (node != NULL, NULL);
1021
1022   node = node->children;
1023   if (node)
1024     while ((n-- > 0) && node)
1025       node = node->next;
1026
1027   return node;
1028 }
1029
1030 /**
1031  * g_node_n_children:
1032  * @node: a #GNode
1033  *
1034  * Gets the number of children of a #GNode.
1035  *
1036  * Returns: the number of children of @node
1037  */
1038 guint
1039 g_node_n_children (GNode *node)
1040 {
1041   guint n = 0;
1042
1043   g_return_val_if_fail (node != NULL, 0);
1044
1045   node = node->children;
1046   while (node)
1047     {
1048       n++;
1049       node = node->next;
1050     }
1051
1052   return n;
1053 }
1054
1055 /**
1056  * g_node_find_child:
1057  * @node: a #GNode
1058  * @flags: which types of children are to be searched, one of
1059  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1060  * @data: the data to find
1061  *
1062  * Finds the first child of a #GNode with the given data.
1063  *
1064  * Returns: the found child #GNode, or %NULL if the data is not found
1065  */
1066 GNode*
1067 g_node_find_child (GNode          *node,
1068                    GTraverseFlags  flags,
1069                    gpointer        data)
1070 {
1071   g_return_val_if_fail (node != NULL, NULL);
1072   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
1073
1074   node = node->children;
1075   while (node)
1076     {
1077       if (node->data == data)
1078         {
1079           if (G_NODE_IS_LEAF (node))
1080             {
1081               if (flags & G_TRAVERSE_LEAFS)
1082                 return node;
1083             }
1084           else
1085             {
1086               if (flags & G_TRAVERSE_NON_LEAFS)
1087                 return node;
1088             }
1089         }
1090       node = node->next;
1091     }
1092
1093   return NULL;
1094 }
1095
1096 /**
1097  * g_node_child_position:
1098  * @node: a #GNode
1099  * @child: a child of @node
1100  *
1101  * Gets the position of a #GNode with respect to its siblings.
1102  * @child must be a child of @node. The first child is numbered 0,
1103  * the second 1, and so on.
1104  *
1105  * Returns: the position of @child with respect to its siblings
1106  */
1107 gint
1108 g_node_child_position (GNode *node,
1109                        GNode *child)
1110 {
1111   guint n = 0;
1112
1113   g_return_val_if_fail (node != NULL, -1);
1114   g_return_val_if_fail (child != NULL, -1);
1115   g_return_val_if_fail (child->parent == node, -1);
1116
1117   node = node->children;
1118   while (node)
1119     {
1120       if (node == child)
1121         return n;
1122       n++;
1123       node = node->next;
1124     }
1125
1126   return -1;
1127 }
1128
1129 /**
1130  * g_node_child_index:
1131  * @node: a #GNode
1132  * @data: the data to find
1133  *
1134  * Gets the position of the first child of a #GNode
1135  * which contains the given data.
1136  *
1137  * Returns: the index of the child of @node which contains
1138  *     @data, or -1 if the data is not found
1139  */
1140 gint
1141 g_node_child_index (GNode    *node,
1142                     gpointer  data)
1143 {
1144   guint n = 0;
1145
1146   g_return_val_if_fail (node != NULL, -1);
1147
1148   node = node->children;
1149   while (node)
1150     {
1151       if (node->data == data)
1152         return n;
1153       n++;
1154       node = node->next;
1155     }
1156
1157   return -1;
1158 }
1159
1160 /**
1161  * g_node_first_sibling:
1162  * @node: a #GNode
1163  *
1164  * Gets the first sibling of a #GNode.
1165  * This could possibly be the node itself.
1166  *
1167  * Returns: the first sibling of @node
1168  */
1169 GNode*
1170 g_node_first_sibling (GNode *node)
1171 {
1172   g_return_val_if_fail (node != NULL, NULL);
1173
1174   if (node->parent)
1175     return node->parent->children;
1176
1177   while (node->prev)
1178     node = node->prev;
1179
1180   return node;
1181 }
1182
1183 /**
1184  * g_node_last_sibling:
1185  * @node: a #GNode
1186  *
1187  * Gets the last sibling of a #GNode.
1188  * This could possibly be the node itself.
1189  *
1190  * Returns: the last sibling of @node
1191  */
1192 GNode*
1193 g_node_last_sibling (GNode *node)
1194 {
1195   g_return_val_if_fail (node != NULL, NULL);
1196
1197   while (node->next)
1198     node = node->next;
1199
1200   return node;
1201 }
1202
1203 /**
1204  * g_node_children_foreach:
1205  * @node: a #GNode
1206  * @flags: which types of children are to be visited, one of
1207  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
1208  * @func: the function to call for each visited node
1209  * @data: user data to pass to the function
1210  *
1211  * Calls a function for each of the children of a #GNode.
1212  * Note that it doesn't descend beneath the child nodes.
1213  */
1214 /**
1215  * GNodeForeachFunc:
1216  * @node: a #GNode.
1217  * @data: user data passed to g_node_children_foreach().
1218  *
1219  * Specifies the type of function passed to g_node_children_foreach().
1220  * The function is called with each child node, together with the user
1221  * data passed to g_node_children_foreach().
1222  **/
1223 void
1224 g_node_children_foreach (GNode            *node,
1225                          GTraverseFlags    flags,
1226                          GNodeForeachFunc  func,
1227                          gpointer          data)
1228 {
1229   g_return_if_fail (node != NULL);
1230   g_return_if_fail (flags <= G_TRAVERSE_MASK);
1231   g_return_if_fail (func != NULL);
1232
1233   node = node->children;
1234   while (node)
1235     {
1236       GNode *current;
1237
1238       current = node;
1239       node = current->next;
1240       if (G_NODE_IS_LEAF (current))
1241         {
1242           if (flags & G_TRAVERSE_LEAFS)
1243             func (current, data);
1244         }
1245       else
1246         {
1247           if (flags & G_TRAVERSE_NON_LEAFS)
1248             func (current, data);
1249         }
1250     }
1251 }