glib inlined into SameTime

git-svn-id: http://svn.miranda-ng.org/main/trunk@8685 1316c22d-e87f-b044-9b9b-93d7a3e3ba9c

1 files changed, 1279 insertions, 0 deletions

diff --git a/protocols/Sametime/src/glib/gnode.c b/protocols/Sametime/src/glib/gnode.c
new file mode 100644
index 0000000000..22d19379c7
--- /dev/null
+++ b/protocols/Sametime/src/glib/gnode.c
@@ -0,0 +1,1279 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ *
+ * GNode: N-way tree implementation.
+ * Copyright (C) 1998 Tim Janik
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/*
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/.
+ */
+
+/*
+ * MT safe
+ */
+
+#include "config.h"
+
+#include "gnode.h"
+
+#include "gtestutils.h"
+
+/**
+ * SECTION: trees-nary
+ * @title: N-ary Trees
+ * @short_description: trees of data with any number of branches
+ *
+ * The #GNode struct and its associated functions provide a N-ary tree
+ * data structure, where nodes in the tree can contain arbitrary data.
+ *
+ * To create a new tree use g_node_new().
+ *
+ * To insert a node into a tree use g_node_insert(),
+ * g_node_insert_before(), g_node_append() and g_node_prepend().
+ *
+ * To create a new node and insert it into a tree use
+ * g_node_insert_data(), g_node_insert_data_before(),
+ * g_node_append_data() and g_node_prepend_data().
+ *
+ * To reverse the children of a node use g_node_reverse_children().
+ *
+ * To find a node use g_node_get_root(), g_node_find(),
+ * g_node_find_child(), g_node_child_index(), g_node_child_position(),
+ * g_node_first_child(), g_node_last_child(), g_node_nth_child(),
+ * g_node_first_sibling(), g_node_prev_sibling(), g_node_next_sibling()
+ * or g_node_last_sibling().
+ *
+ * To get information about a node or tree use G_NODE_IS_LEAF(),
+ * G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(),
+ * g_node_n_children(), g_node_is_ancestor() or g_node_max_height().
+ *
+ * To traverse a tree, calling a function for each node visited in the
+ * traversal, use g_node_traverse() or g_node_children_foreach().
+ *
+ * To remove a node or subtree from a tree use g_node_unlink() or
+ * g_node_destroy().
+ **/
+
+/**
+ * GNode:
+ * @data: contains the actual data of the node.
+ * @next: points to the node's next sibling (a sibling is another
+ *        #GNode with the same parent).
+ * @prev: points to the node's previous sibling.
+ * @parent: points to the parent of the #GNode, or is %NULL if the
+ *          #GNode is the root of the tree.
+ * @children: points to the first child of the #GNode.  The other
+ *            children are accessed by using the @next pointer of each
+ *            child.
+ *
+ * The #GNode struct represents one node in a
+ * <link linkend="glib-N-ary-Trees">N-ary Tree</link>. fields
+ **/
+
+/**
+ * g_node_push_allocator:
+ * @dummy: the #GAllocator to use when allocating #GNode elements.
+ *
+ * Sets the allocator to use to allocate #GNode elements. Use
+ * g_node_pop_allocator() to restore the previous allocator.
+ *
+ * Note that this function is not available if GLib has been compiled
+ * with <option>--disable-mem-pools</option>
+ *
+ * Deprecated:2.10: It does nothing, since #GNode has been converted to
+ *                  the <link linkend="glib-Memory-Slices">slice
+ *                  allocator</link>
+ **/
+void g_node_push_allocator (gpointer dummy) { /* present for binary compat only */ }
+
+/**
+ * g_node_pop_allocator:
+ *
+ * Restores the previous #GAllocator, used when allocating #GNode
+ * elements.
+ *
+ * Note that this function is not available if GLib has been compiled
+ * with <option>--disable-mem-pools</option>
+ *
+ * Deprecated:2.10: It does nothing, since #GNode has been converted to
+ *                  the <link linkend="glib-Memory-Slices">slice
+ *                  allocator</link>
+ **/
+void g_node_pop_allocator  (void)           { /* present for binary compat only */ }
+
+#define g_node_alloc0()         g_slice_new0 (GNode)
+#define g_node_free(node)       g_slice_free (GNode, node)
+
+/* --- functions --- */
+/**
+ * g_node_new:
+ * @data: the data of the new node
+ *
+ * Creates a new #GNode containing the given data.
+ * Used to create the first node in a tree.
+ *
+ * Returns: a new #GNode
+ */
+GNode*
+g_node_new (gpointer data)
+{
+  GNode *node = g_node_alloc0 ();
+  node->data = data;
+  return node;
+}
+
+static void
+g_nodes_free (GNode *node)
+{
+  while (node)
+    {
+      GNode *next = node->next;
+      if (node->children)
+        g_nodes_free (node->children);
+      g_node_free (node);
+      node = next;
+    }
+}
+
+/**
+ * g_node_destroy:
+ * @root: the root of the tree/subtree to destroy
+ *
+ * Removes @root and its children from the tree, freeing any memory
+ * allocated.
+ */
+void
+g_node_destroy (GNode *root)
+{
+  g_return_if_fail (root != NULL);
+  
+  if (!G_NODE_IS_ROOT (root))
+    g_node_unlink (root);
+  
+  g_nodes_free (root);
+}
+
+/**
+ * g_node_unlink:
+ * @node: the #GNode to unlink, which becomes the root of a new tree
+ *
+ * Unlinks a #GNode from a tree, resulting in two separate trees.
+ */
+void
+g_node_unlink (GNode *node)
+{
+  g_return_if_fail (node != NULL);
+  
+  if (node->prev)
+    node->prev->next = node->next;
+  else if (node->parent)
+    node->parent->children = node->next;
+  node->parent = NULL;
+  if (node->next)
+    {
+      node->next->prev = node->prev;
+      node->next = NULL;
+    }
+  node->prev = NULL;
+}
+
+/**
+ * g_node_copy_deep:
+ * @node: a #GNode
+ * @copy_func: the function which is called to copy the data inside each node,
+ *   or %NULL to use the original data.
+ * @data: data to pass to @copy_func
+ * 
+ * Recursively copies a #GNode and its data.
+ * 
+ * Return value: a new #GNode containing copies of the data in @node.
+ *
+ * Since: 2.4
+ **/
+GNode*
+g_node_copy_deep (GNode     *node, 
+		  GCopyFunc  copy_func,
+		  gpointer   data)
+{
+  GNode *new_node = NULL;
+
+  if (copy_func == NULL)
+	return g_node_copy (node);
+
+  if (node)
+    {
+      GNode *child, *new_child;
+      
+      new_node = g_node_new (copy_func (node->data, data));
+      
+      for (child = g_node_last_child (node); child; child = child->prev) 
+	{
+	  new_child = g_node_copy_deep (child, copy_func, data);
+	  g_node_prepend (new_node, new_child);
+	}
+    }
+  
+  return new_node;
+}
+
+/**
+ * g_node_copy:
+ * @node: a #GNode
+ *
+ * Recursively copies a #GNode (but does not deep-copy the data inside the 
+ * nodes, see g_node_copy_deep() if you need that).
+ *
+ * Returns: a new #GNode containing the same data pointers
+ */
+GNode*
+g_node_copy (GNode *node)
+{
+  GNode *new_node = NULL;
+  
+  if (node)
+    {
+      GNode *child;
+      
+      new_node = g_node_new (node->data);
+      
+      for (child = g_node_last_child (node); child; child = child->prev)
+	g_node_prepend (new_node, g_node_copy (child));
+    }
+  
+  return new_node;
+}
+
+/**
+ * g_node_insert:
+ * @parent: the #GNode to place @node under
+ * @position: the position to place @node at, with respect to its siblings
+ *     If position is -1, @node is inserted as the last child of @parent
+ * @node: the #GNode to insert
+ *
+ * Inserts a #GNode beneath the parent at the given position.
+ *
+ * Returns: the inserted #GNode
+ */
+GNode*
+g_node_insert (GNode *parent,
+	       gint   position,
+	       GNode *node)
+{
+  g_return_val_if_fail (parent != NULL, node);
+  g_return_val_if_fail (node != NULL, node);
+  g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
+  
+  if (position > 0)
+    return g_node_insert_before (parent,
+				 g_node_nth_child (parent, position),
+				 node);
+  else if (position == 0)
+    return g_node_prepend (parent, node);
+  else /* if (position < 0) */
+    return g_node_append (parent, node);
+}
+
+/**
+ * g_node_insert_before:
+ * @parent: the #GNode to place @node under
+ * @sibling: the sibling #GNode to place @node before. 
+ *     If sibling is %NULL, the node is inserted as the last child of @parent.
+ * @node: the #GNode to insert
+ *
+ * Inserts a #GNode beneath the parent before the given sibling.
+ *
+ * Returns: the inserted #GNode
+ */
+GNode*
+g_node_insert_before (GNode *parent,
+		      GNode *sibling,
+		      GNode *node)
+{
+  g_return_val_if_fail (parent != NULL, node);
+  g_return_val_if_fail (node != NULL, node);
+  g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
+  if (sibling)
+    g_return_val_if_fail (sibling->parent == parent, node);
+  
+  node->parent = parent;
+  
+  if (sibling)
+    {
+      if (sibling->prev)
+	{
+	  node->prev = sibling->prev;
+	  node->prev->next = node;
+	  node->next = sibling;
+	  sibling->prev = node;
+	}
+      else
+	{
+	  node->parent->children = node;
+	  node->next = sibling;
+	  sibling->prev = node;
+	}
+    }
+  else
+    {
+      if (parent->children)
+	{
+	  sibling = parent->children;
+	  while (sibling->next)
+	    sibling = sibling->next;
+	  node->prev = sibling;
+	  sibling->next = node;
+	}
+      else
+	node->parent->children = node;
+    }
+
+  return node;
+}
+
+/**
+ * g_node_insert_after:
+ * @parent: the #GNode to place @node under
+ * @sibling: the sibling #GNode to place @node after. 
+ *     If sibling is %NULL, the node is inserted as the first child of @parent.
+ * @node: the #GNode to insert
+ *
+ * Inserts a #GNode beneath the parent after the given sibling.
+ *
+ * Returns: the inserted #GNode
+ */
+GNode*
+g_node_insert_after (GNode *parent,
+		     GNode *sibling,
+		     GNode *node)
+{
+  g_return_val_if_fail (parent != NULL, node);
+  g_return_val_if_fail (node != NULL, node);
+  g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
+  if (sibling)
+    g_return_val_if_fail (sibling->parent == parent, node);
+
+  node->parent = parent;
+
+  if (sibling)
+    {
+      if (sibling->next)
+	{
+	  sibling->next->prev = node;
+	}
+      node->next = sibling->next;
+      node->prev = sibling;
+      sibling->next = node;
+    }
+  else
+    {
+      if (parent->children)
+	{
+	  node->next = parent->children;
+	  parent->children->prev = node;
+	}
+      parent->children = node;
+    }
+
+  return node;
+}
+
+/**
+ * g_node_prepend:
+ * @parent: the #GNode to place the new #GNode under
+ * @node: the #GNode to insert
+ *
+ * Inserts a #GNode as the first child of the given parent.
+ *
+ * Returns: the inserted #GNode
+ */
+GNode*
+g_node_prepend (GNode *parent,
+		GNode *node)
+{
+  g_return_val_if_fail (parent != NULL, node);
+  
+  return g_node_insert_before (parent, parent->children, node);
+}
+
+/**
+ * g_node_get_root:
+ * @node: a #GNode
+ *
+ * Gets the root of a tree.
+ *
+ * Returns: the root of the tree
+ */
+GNode*
+g_node_get_root (GNode *node)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  while (node->parent)
+    node = node->parent;
+  
+  return node;
+}
+
+/**
+ * g_node_is_ancestor:
+ * @node: a #GNode
+ * @descendant: a #GNode
+ *
+ * Returns %TRUE if @node is an ancestor of @descendant.
+ * This is true if node is the parent of @descendant, 
+ * or if node is the grandparent of @descendant etc.
+ *
+ * Returns: %TRUE if @node is an ancestor of @descendant
+ */
+gboolean
+g_node_is_ancestor (GNode *node,
+		    GNode *descendant)
+{
+  g_return_val_if_fail (node != NULL, FALSE);
+  g_return_val_if_fail (descendant != NULL, FALSE);
+  
+  while (descendant)
+    {
+      if (descendant->parent == node)
+	return TRUE;
+      
+      descendant = descendant->parent;
+    }
+  
+  return FALSE;
+}
+
+/**
+ * g_node_depth:
+ * @node: a #GNode
+ *
+ * Gets the depth of a #GNode.
+ *
+ * If @node is %NULL the depth is 0. The root node has a depth of 1.
+ * For the children of the root node the depth is 2. And so on.
+ *
+ * Returns: the depth of the #GNode
+ */
+guint
+g_node_depth (GNode *node)
+{
+  guint depth = 0;
+  
+  while (node)
+    {
+      depth++;
+      node = node->parent;
+    }
+  
+  return depth;
+}
+
+/**
+ * g_node_reverse_children:
+ * @node: a #GNode.
+ *
+ * Reverses the order of the children of a #GNode.
+ * (It doesn't change the order of the grandchildren.)
+ */
+void
+g_node_reverse_children (GNode *node)
+{
+  GNode *child;
+  GNode *last;
+  
+  g_return_if_fail (node != NULL);
+  
+  child = node->children;
+  last = NULL;
+  while (child)
+    {
+      last = child;
+      child = last->next;
+      last->next = last->prev;
+      last->prev = child;
+    }
+  node->children = last;
+}
+
+/**
+ * g_node_max_height:
+ * @root: a #GNode
+ *
+ * Gets the maximum height of all branches beneath a #GNode.
+ * This is the maximum distance from the #GNode to all leaf nodes.
+ *
+ * If @root is %NULL, 0 is returned. If @root has no children, 
+ * 1 is returned. If @root has children, 2 is returned. And so on.
+ *
+ * Returns: the maximum height of the tree beneath @root
+ */
+guint
+g_node_max_height (GNode *root)
+{
+  GNode *child;
+  guint max_height = 0;
+  
+  if (!root)
+    return 0;
+  
+  child = root->children;
+  while (child)
+    {
+      guint tmp_height;
+      
+      tmp_height = g_node_max_height (child);
+      if (tmp_height > max_height)
+	max_height = tmp_height;
+      child = child->next;
+    }
+  
+  return max_height + 1;
+}
+
+static gboolean
+g_node_traverse_pre_order (GNode	    *node,
+			   GTraverseFlags    flags,
+			   GNodeTraverseFunc func,
+			   gpointer	     data)
+{
+  if (node->children)
+    {
+      GNode *child;
+      
+      if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	  func (node, data))
+	return TRUE;
+      
+      child = node->children;
+      while (child)
+	{
+	  GNode *current;
+	  
+	  current = child;
+	  child = current->next;
+	  if (g_node_traverse_pre_order (current, flags, func, data))
+	    return TRUE;
+	}
+    }
+  else if ((flags & G_TRAVERSE_LEAFS) &&
+	   func (node, data))
+    return TRUE;
+  
+  return FALSE;
+}
+
+static gboolean
+g_node_depth_traverse_pre_order (GNode		  *node,
+				 GTraverseFlags	   flags,
+				 guint		   depth,
+				 GNodeTraverseFunc func,
+				 gpointer	   data)
+{
+  if (node->children)
+    {
+      GNode *child;
+      
+      if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	  func (node, data))
+	return TRUE;
+      
+      depth--;
+      if (!depth)
+	return FALSE;
+      
+      child = node->children;
+      while (child)
+	{
+	  GNode *current;
+	  
+	  current = child;
+	  child = current->next;
+	  if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
+	    return TRUE;
+	}
+    }
+  else if ((flags & G_TRAVERSE_LEAFS) &&
+	   func (node, data))
+    return TRUE;
+  
+  return FALSE;
+}
+
+static gboolean
+g_node_traverse_post_order (GNode	     *node,
+			    GTraverseFlags    flags,
+			    GNodeTraverseFunc func,
+			    gpointer	      data)
+{
+  if (node->children)
+    {
+      GNode *child;
+      
+      child = node->children;
+      while (child)
+	{
+	  GNode *current;
+	  
+	  current = child;
+	  child = current->next;
+	  if (g_node_traverse_post_order (current, flags, func, data))
+	    return TRUE;
+	}
+      
+      if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	  func (node, data))
+	return TRUE;
+      
+    }
+  else if ((flags & G_TRAVERSE_LEAFS) &&
+	   func (node, data))
+    return TRUE;
+  
+  return FALSE;
+}
+
+static gboolean
+g_node_depth_traverse_post_order (GNode		   *node,
+				  GTraverseFlags    flags,
+				  guint		    depth,
+				  GNodeTraverseFunc func,
+				  gpointer	    data)
+{
+  if (node->children)
+    {
+      depth--;
+      if (depth)
+	{
+	  GNode *child;
+	  
+	  child = node->children;
+	  while (child)
+	    {
+	      GNode *current;
+	      
+	      current = child;
+	      child = current->next;
+	      if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
+		return TRUE;
+	    }
+	}
+      
+      if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	  func (node, data))
+	return TRUE;
+      
+    }
+  else if ((flags & G_TRAVERSE_LEAFS) &&
+	   func (node, data))
+    return TRUE;
+  
+  return FALSE;
+}
+
+static gboolean
+g_node_traverse_in_order (GNode		   *node,
+			  GTraverseFlags    flags,
+			  GNodeTraverseFunc func,
+			  gpointer	    data)
+{
+  if (node->children)
+    {
+      GNode *child;
+      GNode *current;
+      
+      child = node->children;
+      current = child;
+      child = current->next;
+      
+      if (g_node_traverse_in_order (current, flags, func, data))
+	return TRUE;
+      
+      if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	  func (node, data))
+	return TRUE;
+      
+      while (child)
+	{
+	  current = child;
+	  child = current->next;
+	  if (g_node_traverse_in_order (current, flags, func, data))
+	    return TRUE;
+	}
+    }
+  else if ((flags & G_TRAVERSE_LEAFS) &&
+	   func (node, data))
+    return TRUE;
+  
+  return FALSE;
+}
+
+static gboolean
+g_node_depth_traverse_in_order (GNode		 *node,
+				GTraverseFlags	  flags,
+				guint		  depth,
+				GNodeTraverseFunc func,
+				gpointer	  data)
+{
+  if (node->children)
+    {
+      depth--;
+      if (depth)
+	{
+	  GNode *child;
+	  GNode *current;
+	  
+	  child = node->children;
+	  current = child;
+	  child = current->next;
+	  
+	  if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
+	    return TRUE;
+	  
+	  if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	      func (node, data))
+	    return TRUE;
+	  
+	  while (child)
+	    {
+	      current = child;
+	      child = current->next;
+	      if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
+		return TRUE;
+	    }
+	}
+      else if ((flags & G_TRAVERSE_NON_LEAFS) &&
+	       func (node, data))
+	return TRUE;
+    }
+  else if ((flags & G_TRAVERSE_LEAFS) &&
+	   func (node, data))
+    return TRUE;
+  
+  return FALSE;
+}
+
+static gboolean
+g_node_traverse_level (GNode		 *node,
+		       GTraverseFlags	  flags,
+		       guint		  level,
+		       GNodeTraverseFunc  func,
+		       gpointer	          data,
+		       gboolean          *more_levels)
+{
+  if (level == 0) 
+    {
+      if (node->children)
+	{
+	  *more_levels = TRUE;
+	  return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
+	}
+      else
+	{
+	  return (flags & G_TRAVERSE_LEAFS) && func (node, data);
+	}
+    }
+  else 
+    {
+      node = node->children;
+      
+      while (node)
+	{
+	  if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
+	    return TRUE;
+
+	  node = node->next;
+	}
+    }
+
+  return FALSE;
+}
+
+static gboolean
+g_node_depth_traverse_level (GNode             *node,
+			     GTraverseFlags	flags,
+			     guint		depth,
+			     GNodeTraverseFunc  func,
+			     gpointer	        data)
+{
+  guint level;
+  gboolean more_levels;
+
+  level = 0;  
+  while (level != depth) 
+    {
+      more_levels = FALSE;
+      if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
+	return TRUE;
+      if (!more_levels)
+	break;
+      level++;
+    }
+  return FALSE;
+}
+
+/**
+ * g_node_traverse:
+ * @root: the root #GNode of the tree to traverse
+ * @order: the order in which nodes are visited - %G_IN_ORDER, 
+ *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER.
+ * @flags: which types of children are to be visited, one of 
+ *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
+ * @max_depth: the maximum depth of the traversal. Nodes below this
+ *     depth will not be visited. If max_depth is -1 all nodes in 
+ *     the tree are visited. If depth is 1, only the root is visited. 
+ *     If depth is 2, the root and its children are visited. And so on.
+ * @func: the function to call for each visited #GNode
+ * @data: user data to pass to the function
+ *
+ * Traverses a tree starting at the given root #GNode.
+ * It calls the given function for each node visited.
+ * The traversal can be halted at any point by returning %TRUE from @func.
+ */
+/**
+ * GTraverseFlags:
+ * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
+ *                     been introduced in 2.6, for older version use
+ *                     %G_TRAVERSE_LEAFS.
+ * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
+ *                         name has been introduced in 2.6, for older
+ *                         version use %G_TRAVERSE_NON_LEAFS.
+ * @G_TRAVERSE_ALL: all nodes should be visited.
+ * @G_TRAVERSE_MASK: a mask of all traverse flags.
+ * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
+ * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
+ *
+ * Specifies which nodes are visited during several of the tree
+ * functions, including g_node_traverse() and g_node_find().
+ **/
+/**
+ * GNodeTraverseFunc:
+ * @node: a #GNode.
+ * @data: user data passed to g_node_traverse().
+ * @Returns: %TRUE to stop the traversal.
+ *
+ * Specifies the type of function passed to g_node_traverse(). The
+ * function is called with each of the nodes visited, together with the
+ * user data passed to g_node_traverse(). If the function returns
+ * %TRUE, then the traversal is stopped.
+ **/
+void
+g_node_traverse (GNode		  *root,
+		 GTraverseType	   order,
+		 GTraverseFlags	   flags,
+		 gint		   depth,
+		 GNodeTraverseFunc func,
+		 gpointer	   data)
+{
+  g_return_if_fail (root != NULL);
+  g_return_if_fail (func != NULL);
+  g_return_if_fail (order <= G_LEVEL_ORDER);
+  g_return_if_fail (flags <= G_TRAVERSE_MASK);
+  g_return_if_fail (depth == -1 || depth > 0);
+  
+  switch (order)
+    {
+    case G_PRE_ORDER:
+      if (depth < 0)
+	g_node_traverse_pre_order (root, flags, func, data);
+      else
+	g_node_depth_traverse_pre_order (root, flags, depth, func, data);
+      break;
+    case G_POST_ORDER:
+      if (depth < 0)
+	g_node_traverse_post_order (root, flags, func, data);
+      else
+	g_node_depth_traverse_post_order (root, flags, depth, func, data);
+      break;
+    case G_IN_ORDER:
+      if (depth < 0)
+	g_node_traverse_in_order (root, flags, func, data);
+      else
+	g_node_depth_traverse_in_order (root, flags, depth, func, data);
+      break;
+    case G_LEVEL_ORDER:
+      g_node_depth_traverse_level (root, flags, depth, func, data);
+      break;
+    }
+}
+
+static gboolean
+g_node_find_func (GNode	   *node,
+		  gpointer  data)
+{
+  gpointer *d = data;
+  
+  if (*d != node->data)
+    return FALSE;
+  
+  *(++d) = node;
+  
+  return TRUE;
+}
+
+/**
+ * g_node_find:
+ * @root: the root #GNode of the tree to search
+ * @order: the order in which nodes are visited - %G_IN_ORDER, 
+ *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
+ * @flags: which types of children are to be searched, one of 
+ *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
+ * @data: the data to find
+ *
+ * Finds a #GNode in a tree.
+ *
+ * Returns: the found #GNode, or %NULL if the data is not found
+ */
+GNode*
+g_node_find (GNode	    *root,
+	     GTraverseType   order,
+	     GTraverseFlags  flags,
+	     gpointer        data)
+{
+  gpointer d[2];
+  
+  g_return_val_if_fail (root != NULL, NULL);
+  g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
+  g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
+  
+  d[0] = data;
+  d[1] = NULL;
+  
+  g_node_traverse (root, order, flags, -1, g_node_find_func, d);
+  
+  return d[1];
+}
+
+static void
+g_node_count_func (GNode	 *node,
+		   GTraverseFlags flags,
+		   guint	 *n)
+{
+  if (node->children)
+    {
+      GNode *child;
+      
+      if (flags & G_TRAVERSE_NON_LEAFS)
+	(*n)++;
+      
+      child = node->children;
+      while (child)
+	{
+	  g_node_count_func (child, flags, n);
+	  child = child->next;
+	}
+    }
+  else if (flags & G_TRAVERSE_LEAFS)
+    (*n)++;
+}
+
+/**
+ * g_node_n_nodes:
+ * @root: a #GNode
+ * @flags: which types of children are to be counted, one of 
+ *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
+ *
+ * Gets the number of nodes in a tree.
+ *
+ * Returns: the number of nodes in the tree
+ */
+guint
+g_node_n_nodes (GNode	       *root,
+		GTraverseFlags  flags)
+{
+  guint n = 0;
+  
+  g_return_val_if_fail (root != NULL, 0);
+  g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
+  
+  g_node_count_func (root, flags, &n);
+  
+  return n;
+}
+
+/**
+ * g_node_last_child:
+ * @node: a #GNode (must not be %NULL)
+ *
+ * Gets the last child of a #GNode.
+ *
+ * Returns: the last child of @node, or %NULL if @node has no children
+ */
+GNode*
+g_node_last_child (GNode *node)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  node = node->children;
+  if (node)
+    while (node->next)
+      node = node->next;
+  
+  return node;
+}
+
+/**
+ * g_node_nth_child:
+ * @node: a #GNode
+ * @n: the index of the desired child
+ *
+ * Gets a child of a #GNode, using the given index.
+ * The first child is at index 0. If the index is 
+ * too big, %NULL is returned.
+ *
+ * Returns: the child of @node at index @n
+ */
+GNode*
+g_node_nth_child (GNode *node,
+		  guint	 n)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  node = node->children;
+  if (node)
+    while ((n-- > 0) && node)
+      node = node->next;
+  
+  return node;
+}
+
+/**
+ * g_node_n_children:
+ * @node: a #GNode
+ *
+ * Gets the number of children of a #GNode.
+ *
+ * Returns: the number of children of @node
+ */
+guint
+g_node_n_children (GNode *node)
+{
+  guint n = 0;
+  
+  g_return_val_if_fail (node != NULL, 0);
+  
+  node = node->children;
+  while (node)
+    {
+      n++;
+      node = node->next;
+    }
+  
+  return n;
+}
+
+/**
+ * g_node_find_child:
+ * @node: a #GNode
+ * @flags: which types of children are to be searched, one of 
+ *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
+ * @data: the data to find
+ *
+ * Finds the first child of a #GNode with the given data.
+ *
+ * Returns: the found child #GNode, or %NULL if the data is not found
+ */
+GNode*
+g_node_find_child (GNode	  *node,
+		   GTraverseFlags  flags,
+		   gpointer	   data)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
+  
+  node = node->children;
+  while (node)
+    {
+      if (node->data == data)
+	{
+	  if (G_NODE_IS_LEAF (node))
+	    {
+	      if (flags & G_TRAVERSE_LEAFS)
+		return node;
+	    }
+	  else
+	    {
+	      if (flags & G_TRAVERSE_NON_LEAFS)
+		return node;
+	    }
+	}
+      node = node->next;
+    }
+  
+  return NULL;
+}
+
+/**
+ * g_node_child_position:
+ * @node: a #GNode
+ * @child: a child of @node
+ *
+ * Gets the position of a #GNode with respect to its siblings.
+ * @child must be a child of @node. The first child is numbered 0, 
+ * the second 1, and so on.
+ *
+ * Returns: the position of @child with respect to its siblings
+ */
+gint
+g_node_child_position (GNode *node,
+		       GNode *child)
+{
+  guint n = 0;
+  
+  g_return_val_if_fail (node != NULL, -1);
+  g_return_val_if_fail (child != NULL, -1);
+  g_return_val_if_fail (child->parent == node, -1);
+  
+  node = node->children;
+  while (node)
+    {
+      if (node == child)
+	return n;
+      n++;
+      node = node->next;
+    }
+  
+  return -1;
+}
+
+/**
+ * g_node_child_index:
+ * @node: a #GNode
+ * @data: the data to find
+ *
+ * Gets the position of the first child of a #GNode 
+ * which contains the given data.
+ *
+ * Returns: the index of the child of @node which contains 
+ *     @data, or -1 if the data is not found
+ */
+gint
+g_node_child_index (GNode    *node,
+		    gpointer  data)
+{
+  guint n = 0;
+  
+  g_return_val_if_fail (node != NULL, -1);
+  
+  node = node->children;
+  while (node)
+    {
+      if (node->data == data)
+	return n;
+      n++;
+      node = node->next;
+    }
+  
+  return -1;
+}
+
+/**
+ * g_node_first_sibling:
+ * @node: a #GNode
+ *
+ * Gets the first sibling of a #GNode.
+ * This could possibly be the node itself.
+ *
+ * Returns: the first sibling of @node
+ */
+GNode*
+g_node_first_sibling (GNode *node)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  if (node->parent)
+    return node->parent->children;
+  
+  while (node->prev)
+    node = node->prev;
+  
+  return node;
+}
+
+/**
+ * g_node_last_sibling:
+ * @node: a #GNode
+ *
+ * Gets the last sibling of a #GNode.
+ * This could possibly be the node itself.
+ *
+ * Returns: the last sibling of @node
+ */
+GNode*
+g_node_last_sibling (GNode *node)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  while (node->next)
+    node = node->next;
+  
+  return node;
+}
+
+/**
+ * g_node_children_foreach:
+ * @node: a #GNode
+ * @flags: which types of children are to be visited, one of 
+ *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
+ * @func: the function to call for each visited node
+ * @data: user data to pass to the function
+ *
+ * Calls a function for each of the children of a #GNode.
+ * Note that it doesn't descend beneath the child nodes.
+ */
+/**
+ * GNodeForeachFunc:
+ * @node: a #GNode.
+ * @data: user data passed to g_node_children_foreach().
+ *
+ * Specifies the type of function passed to g_node_children_foreach().
+ * The function is called with each child node, together with the user
+ * data passed to g_node_children_foreach().
+ **/
+void
+g_node_children_foreach (GNode		  *node,
+			 GTraverseFlags	   flags,
+			 GNodeForeachFunc  func,
+			 gpointer	   data)
+{
+  g_return_if_fail (node != NULL);
+  g_return_if_fail (flags <= G_TRAVERSE_MASK);
+  g_return_if_fail (func != NULL);
+  
+  node = node->children;
+  while (node)
+    {
+      GNode *current;
+      
+      current = node;
+      node = current->next;
+      if (G_NODE_IS_LEAF (current))
+	{
+	  if (flags & G_TRAVERSE_LEAFS)
+	    func (current, data);
+	}
+      else
+	{
+	  if (flags & G_TRAVERSE_NON_LEAFS)
+	    func (current, data);
+	}
+    }
+}