diff -r 000000000000 -r e4d67989cc36 glib/libglib/src/gnode.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/glib/libglib/src/gnode.c	Tue Feb 02 02:01:42 2010 +0200
@@ -0,0 +1,917 @@
+/* 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
+ * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.
+ *
+ * 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 "glib.h"
+#include "galias.h"
+
+EXPORT_C void g_node_push_allocator (gpointer dummy) { /* present for binary compat only */ }
+EXPORT_C 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 --- */
+EXPORT_C 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;
+    }
+}
+
+EXPORT_C 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);
+}
+
+EXPORT_C 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
+ **/
+EXPORT_C 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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);
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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);
+}
+
+EXPORT_C GNode*
+g_node_get_root (GNode *node)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  while (node->parent)
+    node = node->parent;
+  
+  return node;
+}
+
+EXPORT_C 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;
+}
+
+/* returns 1 for root, 2 for first level children,
+ * 3 for children's children...
+ */
+EXPORT_C guint
+g_node_depth (GNode *node)
+{
+  register guint depth = 0;
+  
+  while (node)
+    {
+      depth++;
+      node = node->parent;
+    }
+  
+  return depth;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C guint
+g_node_max_height (GNode *root)
+{
+  register GNode *child;
+  register guint max_height = 0;
+  
+  if (!root)
+    return 0;
+  
+  child = root->children;
+  while (child)
+    {
+      register 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)
+	{
+	  register 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)
+	{
+	  register 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)
+	{
+	  register 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)
+	    {
+	      register 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;
+      register 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;
+	  register 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;
+}
+
+EXPORT_C 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)
+{
+  register gpointer *d = data;
+  
+  if (*d != node->data)
+    return FALSE;
+  
+  *(++d) = node;
+  
+  return TRUE;
+}
+
+EXPORT_C 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)++;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C gint
+g_node_child_position (GNode *node,
+		       GNode *child)
+{
+  register 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;
+}
+
+EXPORT_C gint
+g_node_child_index (GNode   *node,
+		    gpointer data)
+{
+  register 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;
+}
+
+EXPORT_C 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;
+}
+
+EXPORT_C GNode*
+g_node_last_sibling (GNode *node)
+{
+  g_return_val_if_fail (node != NULL, NULL);
+  
+  while (node->next)
+    node = node->next;
+  
+  return node;
+}
+
+EXPORT_C 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)
+    {
+      register 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);
+	}
+    }
+}
+
+#define __G_NODE_C__
+#include "galiasdef.c"