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  * Portions copyright (c) 2006-2009 Nokia Corporation.  All rights reserved.

     7  *

     8  * This library is free software; you can redistribute it and/or

     9  * modify it under the terms of the GNU Lesser General Public

    10  * License as published by the Free Software Foundation; either

    11  * version 2 of the License, or (at your option) any later version.

    12  *

    13  * This library is distributed in the hope that it will be useful,

    14  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU

    16  * Lesser General Public License for more details.

    17  *

    18  * You should have received a copy of the GNU Lesser General Public

    19  * License along with this library; if not, write to the

    20  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

    21  * Boston, MA 02111-1307, USA.

    22  */

    23 

    24 /*

    25  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

    26  * file for a list of people on the GLib Team.  See the ChangeLog

    27  * files for a list of changes.  These files are distributed with

    28  * GLib at ftp://ftp.gtk.org/pub/gtk/. 

    29  */

    30 

    31 /* 

    32  * MT safe

    33  */

    34 

    35 #include "config.h"

    36 

    37 #include "glib.h"

    38 #include "galias.h"

    39 

    40 EXPORT_C void g_node_push_allocator (gpointer dummy) { /* present for binary compat only */ }

    41 EXPORT_C void g_node_pop_allocator  (void)           { /* present for binary compat only */ }

    42 

    43 #define g_node_alloc0()         g_slice_new0 (GNode)

    44 #define g_node_free(node)       g_slice_free (GNode, node)

    45 

    46 /* --- functions --- */

    47 /**

    48  * g_node_new:

    49  * @data: the data of the new node

    50  *

    51  * Creates a new #GNode containing the given data.

    52  * Used to create the first node in a tree.

    53  *

    54  * Returns: a new #GNode

    55  */

    56 EXPORT_C GNode*

    57 g_node_new (gpointer data)

    58 {

    59   GNode *node = g_node_alloc0 ();

    60   node->data = data;

    61   return node;

    62 }

    63 

    64 static void

    65 g_nodes_free (GNode *node)

    66 {

    67   while (node)

    68     {

    69       GNode *next = node->next;

    70       if (node->children)

    71         g_nodes_free (node->children);

    72       g_node_free (node);

    73       node = next;

    74     }

    75 }

    76 

    77 /**

    78  * g_node_destroy:

    79  * @root: the root of the tree/subtree to destroy

    80  *

    81  * Removes @root and its children from the tree, freeing any memory

    82  * allocated.

    83  */

    84 EXPORT_C void

    85 g_node_destroy (GNode *root)

    86 {

    87   g_return_if_fail (root != NULL);

    88   

    89   if (!G_NODE_IS_ROOT (root))

    90     g_node_unlink (root);

    91   

    92   g_nodes_free (root);

    93 }

    94 

    95 /**

    96  * g_node_unlink:

    97  * @node: the #GNode to unlink, which becomes the root of a new tree

    98  *

    99  * Unlinks a #GNode from a tree, resulting in two separate trees.

   100  */

   101 EXPORT_C void

   102 g_node_unlink (GNode *node)

   103 {

   104   g_return_if_fail (node != NULL);

   105   

   106   if (node->prev)

   107     node->prev->next = node->next;

   108   else if (node->parent)

   109     node->parent->children = node->next;

   110   node->parent = NULL;

   111   if (node->next)

   112     {

   113       node->next->prev = node->prev;

   114       node->next = NULL;

   115     }

   116   node->prev = NULL;

   117 }

   118 

   119 /**

   120  * g_node_copy_deep:

   121  * @node: a #GNode

   122  * @copy_func: the function which is called to copy the data inside each node,

   123  *   or %NULL to use the original data.

   124  * @data: data to pass to @copy_func

   125  * 

   126  * Recursively copies a #GNode and its data.

   127  * 

   128  * Return value: a new #GNode containing copies of the data in @node.

   129  *

   130  * Since: 2.4

   131  **/

   132 EXPORT_C GNode*

   133 g_node_copy_deep (GNode     *node, 

   134 		  GCopyFunc  copy_func,

   135 		  gpointer   data)

   136 {

   137   GNode *new_node = NULL;

   138 

   139   if (copy_func == NULL)

   140 	return g_node_copy (node);

   141 

   142   if (node)

   143     {

   144       GNode *child, *new_child;

   145       

   146       new_node = g_node_new (copy_func (node->data, data));

   147       

   148       for (child = g_node_last_child (node); child; child = child->prev) 

   149 	{

   150 	  new_child = g_node_copy_deep (child, copy_func, data);

   151 	  g_node_prepend (new_node, new_child);

   152 	}

   153     }

   154   

   155   return new_node;

   156 }

   157 

   158 /**

   159  * g_node_copy:

   160  * @node: a #GNode

   161  *

   162  * Recursively copies a #GNode (but does not deep-copy the data inside the 

   163  * nodes, see g_node_copy_deep() if you need that).

   164  *

   165  * Returns: a new #GNode containing the same data pointers

   166  */

   167 EXPORT_C GNode*

   168 g_node_copy (GNode *node)

   169 {

   170   GNode *new_node = NULL;

   171   

   172   if (node)

   173     {

   174       GNode *child;

   175       

   176       new_node = g_node_new (node->data);

   177       

   178       for (child = g_node_last_child (node); child; child = child->prev)

   179 	g_node_prepend (new_node, g_node_copy (child));

   180     }

   181   

   182   return new_node;

   183 }

   184 

   185 /**

   186  * g_node_insert:

   187  * @parent: the #GNode to place @node under

   188  * @position: the position to place @node at, with respect to its siblings

   189  *     If position is -1, @node is inserted as the last child of @parent

   190  * @node: the #GNode to insert

   191  *

   192  * Inserts a #GNode beneath the parent at the given position.

   193  *

   194  * Returns: the inserted #GNode

   195  */

   196 EXPORT_C GNode*

   197 g_node_insert (GNode *parent,

   198 	       gint   position,

   199 	       GNode *node)

   200 {

   201   g_return_val_if_fail (parent != NULL, node);

   202   g_return_val_if_fail (node != NULL, node);

   203   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);

   204   

   205   if (position > 0)

   206     return g_node_insert_before (parent,

   207 				 g_node_nth_child (parent, position),

   208 				 node);

   209   else if (position == 0)

   210     return g_node_prepend (parent, node);

   211   else /* if (position < 0) */

   212     return g_node_append (parent, node);

   213 }

   214 

   215 /**

   216  * g_node_insert_before:

   217  * @parent: the #GNode to place @node under

   218  * @sibling: the sibling #GNode to place @node before. 

   219  *     If sibling is %NULL, the node is inserted as the last child of @parent.

   220  * @node: the #GNode to insert

   221  *

   222  * Inserts a #GNode beneath the parent before the given sibling.

   223  *

   224  * Returns: the inserted #GNode

   225  */

   226 EXPORT_C GNode*

   227 g_node_insert_before (GNode *parent,

   228 		      GNode *sibling,

   229 		      GNode *node)

   230 {

   231   g_return_val_if_fail (parent != NULL, node);

   232   g_return_val_if_fail (node != NULL, node);

   233   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);

   234   if (sibling)

   235     g_return_val_if_fail (sibling->parent == parent, node);

   236   

   237   node->parent = parent;

   238   

   239   if (sibling)

   240     {

   241       if (sibling->prev)

   242 	{

   243 	  node->prev = sibling->prev;

   244 	  node->prev->next = node;

   245 	  node->next = sibling;

   246 	  sibling->prev = node;

   247 	}

   248       else

   249 	{

   250 	  node->parent->children = node;

   251 	  node->next = sibling;

   252 	  sibling->prev = node;

   253 	}

   254     }

   255   else

   256     {

   257       if (parent->children)

   258 	{

   259 	  sibling = parent->children;

   260 	  while (sibling->next)

   261 	    sibling = sibling->next;

   262 	  node->prev = sibling;

   263 	  sibling->next = node;

   264 	}

   265       else

   266 	node->parent->children = node;

   267     }

   268 

   269   return node;

   270 }

   271 

   272 /**

   273  * g_node_insert_after:

   274  * @parent: the #GNode to place @node under

   275  * @sibling: the sibling #GNode to place @node after. 

   276  *     If sibling is %NULL, the node is inserted as the first child of @parent.

   277  * @node: the #GNode to insert

   278  *

   279  * Inserts a #GNode beneath the parent after the given sibling.

   280  *

   281  * Returns: the inserted #GNode

   282  */

   283 EXPORT_C GNode*

   284 g_node_insert_after (GNode *parent,

   285 		     GNode *sibling,

   286 		     GNode *node)

   287 {

   288   g_return_val_if_fail (parent != NULL, node);

   289   g_return_val_if_fail (node != NULL, node);

   290   g_return_val_if_fail (G_NODE_IS_ROOT (node), node);

   291   if (sibling)

   292     g_return_val_if_fail (sibling->parent == parent, node);

   293 

   294   node->parent = parent;

   295 

   296   if (sibling)

   297     {

   298       if (sibling->next)

   299 	{

   300 	  sibling->next->prev = node;

   301 	}

   302       node->next = sibling->next;

   303       node->prev = sibling;

   304       sibling->next = node;

   305     }

   306   else

   307     {

   308       if (parent->children)

   309 	{

   310 	  node->next = parent->children;

   311 	  parent->children->prev = node;

   312 	}

   313       parent->children = node;

   314     }

   315 

   316   return node;

   317 }

   318 

   319 /**

   320  * g_node_prepend:

   321  * @parent: the #GNode to place the new #GNode under

   322  * @node: the #GNode to insert

   323  *

   324  * Inserts a #GNode as the first child of the given parent.

   325  *

   326  * Returns: the inserted #GNode

   327  */

   328 EXPORT_C GNode*

   329 g_node_prepend (GNode *parent,

   330 		GNode *node)

   331 {

   332   g_return_val_if_fail (parent != NULL, node);

   333   

   334   return g_node_insert_before (parent, parent->children, node);

   335 }

   336 

   337 /**

   338  * g_node_get_root:

   339  * @node: a #GNode

   340  *

   341  * Gets the root of a tree.

   342  *

   343  * Returns: the root of the tree

   344  */

   345 EXPORT_C GNode*

   346 g_node_get_root (GNode *node)

   347 {

   348   g_return_val_if_fail (node != NULL, NULL);

   349   

   350   while (node->parent)

   351     node = node->parent;

   352   

   353   return node;

   354 }

   355 

   356 /**

   357  * g_node_is_ancestor:

   358  * @node: a #GNode

   359  * @descendant: a #GNode

   360  *

   361  * Returns %TRUE if @node is an ancestor of @descendant.

   362  * This is true if node is the parent of @descendant, 

   363  * or if node is the grandparent of @descendant etc.

   364  *

   365  * Returns: %TRUE if @node is an ancestor of @descendant

   366  */

   367 EXPORT_C gboolean

   368 g_node_is_ancestor (GNode *node,

   369 		    GNode *descendant)

   370 {

   371   g_return_val_if_fail (node != NULL, FALSE);

   372   g_return_val_if_fail (descendant != NULL, FALSE);

   373   

   374   while (descendant)

   375     {

   376       if (descendant->parent == node)

   377 	return TRUE;

   378       

   379       descendant = descendant->parent;

   380     }

   381   

   382   return FALSE;

   383 }

   384 

   385 /**

   386  * g_node_depth:

   387  * @node: a #GNode

   388  *

   389  * Gets the depth of a #GNode.

   390  *

   391  * If @node is %NULL the depth is 0. The root node has a depth of 1.

   392  * For the children of the root node the depth is 2. And so on.

   393  *

   394  * Returns: the depth of the #GNode

   395  */

   396 EXPORT_C guint

   397 g_node_depth (GNode *node)

   398 {

   399   guint depth = 0;

   400   

   401   while (node)

   402     {

   403       depth++;

   404       node = node->parent;

   405     }

   406   

   407   return depth;

   408 }

   409 

   410 /**

   411  * g_node_reverse_children:

   412  * @node: a #GNode.

   413  *

   414  * Reverses the order of the children of a #GNode.

   415  * (It doesn't change the order of the grandchildren.)

   416  */

   417 EXPORT_C void

   418 g_node_reverse_children (GNode *node)

   419 {

   420   GNode *child;

   421   GNode *last;

   422   

   423   g_return_if_fail (node != NULL);

   424   

   425   child = node->children;

   426   last = NULL;

   427   while (child)

   428     {

   429       last = child;

   430       child = last->next;

   431       last->next = last->prev;

   432       last->prev = child;

   433     }

   434   node->children = last;

   435 }

   436 

   437 /**

   438  * g_node_max_height:

   439  * @root: a #GNode

   440  *

   441  * Gets the maximum height of all branches beneath a #GNode.

   442  * This is the maximum distance from the #GNode to all leaf nodes.

   443  *

   444  * If @root is %NULL, 0 is returned. If @root has no children, 

   445  * 1 is returned. If @root has children, 2 is returned. And so on.

   446  *

   447  * Returns: the maximum height of the tree beneath @root

   448  */

   449 EXPORT_C guint

   450 g_node_max_height (GNode *root)

   451 {

   452   GNode *child;

   453   guint max_height = 0;

   454   

   455   if (!root)

   456     return 0;

   457   

   458   child = root->children;

   459   while (child)

   460     {

   461       guint tmp_height;

   462       

   463       tmp_height = g_node_max_height (child);

   464       if (tmp_height > max_height)

   465 	max_height = tmp_height;

   466       child = child->next;

   467     }

   468   

   469   return max_height + 1;

   470 }

   471 

   472 static gboolean

   473 g_node_traverse_pre_order (GNode	    *node,

   474 			   GTraverseFlags    flags,

   475 			   GNodeTraverseFunc func,

   476 			   gpointer	     data)

   477 {

   478   if (node->children)

   479     {

   480       GNode *child;

   481       

   482       if ((flags & G_TRAVERSE_NON_LEAFS) &&

   483 	  func (node, data))

   484 	return TRUE;

   485       

   486       child = node->children;

   487       while (child)

   488 	{

   489 	  GNode *current;

   490 	  

   491 	  current = child;

   492 	  child = current->next;

   493 	  if (g_node_traverse_pre_order (current, flags, func, data))

   494 	    return TRUE;

   495 	}

   496     }

   497   else if ((flags & G_TRAVERSE_LEAFS) &&

   498 	   func (node, data))

   499     return TRUE;

   500   

   501   return FALSE;

   502 }

   503 

   504 static gboolean

   505 g_node_depth_traverse_pre_order (GNode		  *node,

   506 				 GTraverseFlags	   flags,

   507 				 guint		   depth,

   508 				 GNodeTraverseFunc func,

   509 				 gpointer	   data)

   510 {

   511   if (node->children)

   512     {

   513       GNode *child;

   514       

   515       if ((flags & G_TRAVERSE_NON_LEAFS) &&

   516 	  func (node, data))

   517 	return TRUE;

   518       

   519       depth--;

   520       if (!depth)

   521 	return FALSE;

   522       

   523       child = node->children;

   524       while (child)

   525 	{

   526 	  GNode *current;

   527 	  

   528 	  current = child;

   529 	  child = current->next;

   530 	  if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))

   531 	    return TRUE;

   532 	}

   533     }

   534   else if ((flags & G_TRAVERSE_LEAFS) &&

   535 	   func (node, data))

   536     return TRUE;

   537   

   538   return FALSE;

   539 }

   540 

   541 static gboolean

   542 g_node_traverse_post_order (GNode	     *node,

   543 			    GTraverseFlags    flags,

   544 			    GNodeTraverseFunc func,

   545 			    gpointer	      data)

   546 {

   547   if (node->children)

   548     {

   549       GNode *child;

   550       

   551       child = node->children;

   552       while (child)

   553 	{

   554 	  GNode *current;

   555 	  

   556 	  current = child;

   557 	  child = current->next;

   558 	  if (g_node_traverse_post_order (current, flags, func, data))

   559 	    return TRUE;

   560 	}

   561       

   562       if ((flags & G_TRAVERSE_NON_LEAFS) &&

   563 	  func (node, data))

   564 	return TRUE;

   565       

   566     }

   567   else if ((flags & G_TRAVERSE_LEAFS) &&

   568 	   func (node, data))

   569     return TRUE;

   570   

   571   return FALSE;

   572 }

   573 

   574 static gboolean

   575 g_node_depth_traverse_post_order (GNode		   *node,

   576 				  GTraverseFlags    flags,

   577 				  guint		    depth,

   578 				  GNodeTraverseFunc func,

   579 				  gpointer	    data)

   580 {

   581   if (node->children)

   582     {

   583       depth--;

   584       if (depth)

   585 	{

   586 	  GNode *child;

   587 	  

   588 	  child = node->children;

   589 	  while (child)

   590 	    {

   591 	      GNode *current;

   592 	      

   593 	      current = child;

   594 	      child = current->next;

   595 	      if (g_node_depth_traverse_post_order (current, flags, depth, func, data))

   596 		return TRUE;

   597 	    }

   598 	}

   599       

   600       if ((flags & G_TRAVERSE_NON_LEAFS) &&

   601 	  func (node, data))

   602 	return TRUE;

   603       

   604     }

   605   else if ((flags & G_TRAVERSE_LEAFS) &&

   606 	   func (node, data))

   607     return TRUE;

   608   

   609   return FALSE;

   610 }

   611 

   612 static gboolean

   613 g_node_traverse_in_order (GNode		   *node,

   614 			  GTraverseFlags    flags,

   615 			  GNodeTraverseFunc func,

   616 			  gpointer	    data)

   617 {

   618   if (node->children)

   619     {

   620       GNode *child;

   621       GNode *current;

   622       

   623       child = node->children;

   624       current = child;

   625       child = current->next;

   626       

   627       if (g_node_traverse_in_order (current, flags, func, data))

   628 	return TRUE;

   629       

   630       if ((flags & G_TRAVERSE_NON_LEAFS) &&

   631 	  func (node, data))

   632 	return TRUE;

   633       

   634       while (child)

   635 	{

   636 	  current = child;

   637 	  child = current->next;

   638 	  if (g_node_traverse_in_order (current, flags, func, data))

   639 	    return TRUE;

   640 	}

   641     }

   642   else if ((flags & G_TRAVERSE_LEAFS) &&

   643 	   func (node, data))

   644     return TRUE;

   645   

   646   return FALSE;

   647 }

   648 

   649 static gboolean

   650 g_node_depth_traverse_in_order (GNode		 *node,

   651 				GTraverseFlags	  flags,

   652 				guint		  depth,

   653 				GNodeTraverseFunc func,

   654 				gpointer	  data)

   655 {

   656   if (node->children)

   657     {

   658       depth--;

   659       if (depth)

   660 	{

   661 	  GNode *child;

   662 	  GNode *current;

   663 	  

   664 	  child = node->children;

   665 	  current = child;

   666 	  child = current->next;

   667 	  

   668 	  if (g_node_depth_traverse_in_order (current, flags, depth, func, data))

   669 	    return TRUE;

   670 	  

   671 	  if ((flags & G_TRAVERSE_NON_LEAFS) &&

   672 	      func (node, data))

   673 	    return TRUE;

   674 	  

   675 	  while (child)

   676 	    {

   677 	      current = child;

   678 	      child = current->next;

   679 	      if (g_node_depth_traverse_in_order (current, flags, depth, func, data))

   680 		return TRUE;

   681 	    }

   682 	}

   683       else if ((flags & G_TRAVERSE_NON_LEAFS) &&

   684 	       func (node, data))

   685 	return TRUE;

   686     }

   687   else if ((flags & G_TRAVERSE_LEAFS) &&

   688 	   func (node, data))

   689     return TRUE;

   690   

   691   return FALSE;

   692 }

   693 

   694 static gboolean

   695 g_node_traverse_level (GNode		 *node,

   696 		       GTraverseFlags	  flags,

   697 		       guint		  level,

   698 		       GNodeTraverseFunc  func,

   699 		       gpointer	          data,

   700 		       gboolean          *more_levels)

   701 {

   702   if (level == 0) 

   703     {

   704       if (node->children)

   705 	{

   706 	  *more_levels = TRUE;

   707 	  return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);

   708 	}

   709       else

   710 	{

   711 	  return (flags & G_TRAVERSE_LEAFS) && func (node, data);

   712 	}

   713     }

   714   else 

   715     {

   716       node = node->children;

   717       

   718       while (node)

   719 	{

   720 	  if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))

   721 	    return TRUE;

   722 

   723 	  node = node->next;

   724 	}

   725     }

   726 

   727   return FALSE;

   728 }

   729 

   730 static gboolean

   731 g_node_depth_traverse_level (GNode             *node,

   732 			     GTraverseFlags	flags,

   733 			     guint		depth,

   734 			     GNodeTraverseFunc  func,

   735 			     gpointer	        data)

   736 {

   737   guint level;

   738   gboolean more_levels;

   739 

   740   level = 0;  

   741   while (level != depth) 

   742     {

   743       more_levels = FALSE;

   744       if (g_node_traverse_level (node, flags, level, func, data, &more_levels))

   745 	return TRUE;

   746       if (!more_levels)

   747 	break;

   748       level++;

   749     }

   750   return FALSE;

   751 }

   752 

   753 /**

   754  * g_node_traverse:

   755  * @root: the root #GNode of the tree to traverse

   756  * @order: the order in which nodes are visited - %G_IN_ORDER, 

   757  *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER.

   758  * @flags: which types of children are to be visited, one of 

   759  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES

   760  * @max_depth: the maximum depth of the traversal. Nodes below this

   761  *     depth will not be visited. If max_depth is -1 all nodes in 

   762  *     the tree are visited. If depth is 1, only the root is visited. 

   763  *     If depth is 2, the root and its children are visited. And so on.

   764  * @func: the function to call for each visited #GNode

   765  * @data: user data to pass to the function

   766  *

   767  * Traverses a tree starting at the given root #GNode.

   768  * It calls the given function for each node visited.

   769  * The traversal can be halted at any point by returning %TRUE from @func.

   770  */

   771 EXPORT_C void

   772 g_node_traverse (GNode		  *root,

   773 		 GTraverseType	   order,

   774 		 GTraverseFlags	   flags,

   775 		 gint		   depth,

   776 		 GNodeTraverseFunc func,

   777 		 gpointer	   data)

   778 {

   779   g_return_if_fail (root != NULL);

   780   g_return_if_fail (func != NULL);

   781   g_return_if_fail (order <= G_LEVEL_ORDER);

   782   g_return_if_fail (flags <= G_TRAVERSE_MASK);

   783   g_return_if_fail (depth == -1 || depth > 0);

   784   

   785   switch (order)

   786     {

   787     case G_PRE_ORDER:

   788       if (depth < 0)

   789 	g_node_traverse_pre_order (root, flags, func, data);

   790       else

   791 	g_node_depth_traverse_pre_order (root, flags, depth, func, data);

   792       break;

   793     case G_POST_ORDER:

   794       if (depth < 0)

   795 	g_node_traverse_post_order (root, flags, func, data);

   796       else

   797 	g_node_depth_traverse_post_order (root, flags, depth, func, data);

   798       break;

   799     case G_IN_ORDER:

   800       if (depth < 0)

   801 	g_node_traverse_in_order (root, flags, func, data);

   802       else

   803 	g_node_depth_traverse_in_order (root, flags, depth, func, data);

   804       break;

   805     case G_LEVEL_ORDER:

   806       g_node_depth_traverse_level (root, flags, depth, func, data);

   807       break;

   808     }

   809 }

   810 

   811 static gboolean

   812 g_node_find_func (GNode	   *node,

   813 		  gpointer  data)

   814 {

   815   gpointer *d = data;

   816   

   817   if (*d != node->data)

   818     return FALSE;

   819   

   820   *(++d) = node;

   821   

   822   return TRUE;

   823 }

   824 

   825 /**

   826  * g_node_find:

   827  * @root: the root #GNode of the tree to search

   828  * @order: the order in which nodes are visited - %G_IN_ORDER, 

   829  *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER

   830  * @flags: which types of children are to be searched, one of 

   831  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES

   832  * @data: the data to find

   833  *

   834  * Finds a #GNode in a tree.

   835  *

   836  * Returns: the found #GNode, or %NULL if the data is not found

   837  */

   838 EXPORT_C GNode*

   839 g_node_find (GNode	    *root,

   840 	     GTraverseType   order,

   841 	     GTraverseFlags  flags,

   842 	     gpointer        data)

   843 {

   844   gpointer d[2];

   845   

   846   g_return_val_if_fail (root != NULL, NULL);

   847   g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);

   848   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);

   849   

   850   d[0] = data;

   851   d[1] = NULL;

   852   

   853   g_node_traverse (root, order, flags, -1, g_node_find_func, d);

   854   

   855   return d[1];

   856 }

   857 

   858 static void

   859 g_node_count_func (GNode	 *node,

   860 		   GTraverseFlags flags,

   861 		   guint	 *n)

   862 {

   863   if (node->children)

   864     {

   865       GNode *child;

   866       

   867       if (flags & G_TRAVERSE_NON_LEAFS)

   868 	(*n)++;

   869       

   870       child = node->children;

   871       while (child)

   872 	{

   873 	  g_node_count_func (child, flags, n);

   874 	  child = child->next;

   875 	}

   876     }

   877   else if (flags & G_TRAVERSE_LEAFS)

   878     (*n)++;

   879 }

   880 

   881 /**

   882  * g_node_n_nodes:

   883  * @root: a #GNode

   884  * @flags: which types of children are to be counted, one of 

   885  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES

   886  *

   887  * Gets the number of nodes in a tree.

   888  *

   889  * Returns: the number of nodes in the tree

   890  */

   891 EXPORT_C guint

   892 g_node_n_nodes (GNode	       *root,

   893 		GTraverseFlags  flags)

   894 {

   895   guint n = 0;

   896   

   897   g_return_val_if_fail (root != NULL, 0);

   898   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);

   899   

   900   g_node_count_func (root, flags, &n);

   901   

   902   return n;

   903 }

   904 

   905 /**

   906  * g_node_last_child:

   907  * @node: a #GNode (must not be %NULL)

   908  *

   909  * Gets the last child of a #GNode.

   910  *

   911  * Returns: the last child of @node, or %NULL if @node has no children

   912  */

   913 EXPORT_C GNode*

   914 g_node_last_child (GNode *node)

   915 {

   916   g_return_val_if_fail (node != NULL, NULL);

   917   

   918   node = node->children;

   919   if (node)

   920     while (node->next)

   921       node = node->next;

   922   

   923   return node;

   924 }

   925 

   926 /**

   927  * g_node_nth_child:

   928  * @node: a #GNode

   929  * @n: the index of the desired child

   930  *

   931  * Gets a child of a #GNode, using the given index.

   932  * The first child is at index 0. If the index is 

   933  * too big, %NULL is returned.

   934  *

   935  * Returns: the child of @node at index @n

   936  */

   937 EXPORT_C GNode*

   938 g_node_nth_child (GNode *node,

   939 		  guint	 n)

   940 {

   941   g_return_val_if_fail (node != NULL, NULL);

   942   

   943   node = node->children;

   944   if (node)

   945     while ((n-- > 0) && node)

   946       node = node->next;

   947   

   948   return node;

   949 }

   950 

   951 /**

   952  * g_node_n_children:

   953  * @node: a #GNode

   954  *

   955  * Gets the number of children of a #GNode.

   956  *

   957  * Returns: the number of children of @node

   958  */

   959 EXPORT_C guint

   960 g_node_n_children (GNode *node)

   961 {

   962   guint n = 0;

   963   

   964   g_return_val_if_fail (node != NULL, 0);

   965   

   966   node = node->children;

   967   while (node)

   968     {

   969       n++;

   970       node = node->next;

   971     }

   972   

   973   return n;

   974 }

   975 

   976 /**

   977  * g_node_find_child:

   978  * @node: a #GNode

   979  * @flags: which types of children are to be searched, one of 

   980  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES

   981  * @data: the data to find

   982  *

   983  * Finds the first child of a #GNode with the given data.

   984  *

   985  * Returns: the found child #GNode, or %NULL if the data is not found

   986  */

   987 EXPORT_C GNode*

   988 g_node_find_child (GNode	  *node,

   989 		   GTraverseFlags  flags,

   990 		   gpointer	   data)

   991 {

   992   g_return_val_if_fail (node != NULL, NULL);

   993   g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);

   994   

   995   node = node->children;

   996   while (node)

   997     {

   998       if (node->data == data)

   999 	{

  1000 	  if (G_NODE_IS_LEAF (node))

  1001 	    {

  1002 	      if (flags & G_TRAVERSE_LEAFS)

  1003 		return node;

  1004 	    }

  1005 	  else

  1006 	    {

  1007 	      if (flags & G_TRAVERSE_NON_LEAFS)

  1008 		return node;

  1009 	    }

  1010 	}

  1011       node = node->next;

  1012     }

  1013   

  1014   return NULL;

  1015 }

  1016 

  1017 /**

  1018  * g_node_child_position:

  1019  * @node: a #GNode

  1020  * @child: a child of @node

  1021  *

  1022  * Gets the position of a #GNode with respect to its siblings.

  1023  * @child must be a child of @node. The first child is numbered 0, 

  1024  * the second 1, and so on.

  1025  *

  1026  * Returns: the position of @child with respect to its siblings

  1027  */

  1028 EXPORT_C gint

  1029 g_node_child_position (GNode *node,

  1030 		       GNode *child)

  1031 {

  1032   guint n = 0;

  1033   

  1034   g_return_val_if_fail (node != NULL, -1);

  1035   g_return_val_if_fail (child != NULL, -1);

  1036   g_return_val_if_fail (child->parent == node, -1);

  1037   

  1038   node = node->children;

  1039   while (node)

  1040     {

  1041       if (node == child)

  1042 	return n;

  1043       n++;

  1044       node = node->next;

  1045     }

  1046   

  1047   return -1;

  1048 }

  1049 

  1050 /**

  1051  * g_node_child_index:

  1052  * @node: a #GNode

  1053  * @data: the data to find

  1054  *

  1055  * Gets the position of the first child of a #GNode 

  1056  * which contains the given data.

  1057  *

  1058  * Returns: the index of the child of @node which contains 

  1059  *     @data, or -1 if the data is not found

  1060  */

  1061 EXPORT_C gint

  1062 g_node_child_index (GNode    *node,

  1063 		    gpointer  data)

  1064 {

  1065   guint n = 0;

  1066   

  1067   g_return_val_if_fail (node != NULL, -1);

  1068   

  1069   node = node->children;

  1070   while (node)

  1071     {

  1072       if (node->data == data)

  1073 	return n;

  1074       n++;

  1075       node = node->next;

  1076     }

  1077   

  1078   return -1;

  1079 }

  1080 

  1081 /**

  1082  * g_node_first_sibling:

  1083  * @node: a #GNode

  1084  *

  1085  * Gets the first sibling of a #GNode.

  1086  * This could possibly be the node itself.

  1087  *

  1088  * Returns: the first sibling of @node

  1089  */

  1090 EXPORT_C GNode*

  1091 g_node_first_sibling (GNode *node)

  1092 {

  1093   g_return_val_if_fail (node != NULL, NULL);

  1094   

  1095   if (node->parent)

  1096     return node->parent->children;

  1097   

  1098   while (node->prev)

  1099     node = node->prev;

  1100   

  1101   return node;

  1102 }

  1103 

  1104 /**

  1105  * g_node_last_sibling:

  1106  * @node: a #GNode

  1107  *

  1108  * Gets the last sibling of a #GNode.

  1109  * This could possibly be the node itself.

  1110  *

  1111  * Returns: the last sibling of @node

  1112  */

  1113 EXPORT_C GNode*

  1114 g_node_last_sibling (GNode *node)

  1115 {

  1116   g_return_val_if_fail (node != NULL, NULL);

  1117   

  1118   while (node->next)

  1119     node = node->next;

  1120   

  1121   return node;

  1122 }

  1123 

  1124 /**

  1125  * g_node_children_foreach:

  1126  * @node: a #GNode

  1127  * @flags: which types of children are to be visited, one of 

  1128  *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES

  1129  * @func: the function to call for each visited node

  1130  * @data: user data to pass to the function

  1131  *

  1132  * Calls a function for each of the children of a #GNode.

  1133  * Note that it doesn't descend beneath the child nodes.

  1134  */

  1135 EXPORT_C void