williamr@2: /* GLIB - Library of useful routines for C programming
williamr@2:  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
williamr@2:  * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.
williamr@2:  *
williamr@2:  * This library is free software; you can redistribute it and/or
williamr@2:  * modify it under the terms of the GNU Lesser General Public
williamr@2:  * License as published by the Free Software Foundation; either
williamr@2:  * version 2 of the License, or (at your option) any later version.
williamr@2:  *
williamr@2:  * This library is distributed in the hope that it will be useful,
williamr@2:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
williamr@2:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
williamr@2:  * Lesser General Public License for more details.
williamr@2:  *
williamr@2:  * You should have received a copy of the GNU Lesser General Public
williamr@2:  * License along with this library; if not, write to the
williamr@2:  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
williamr@2:  * Boston, MA 02111-1307, USA.
williamr@2:  */
williamr@2: 
williamr@2: /*
williamr@2:  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
williamr@2:  * file for a list of people on the GLib Team.  See the ChangeLog
williamr@2:  * files for a list of changes.  These files are distributed with
williamr@2:  * GLib at ftp://ftp.gtk.org/pub/gtk/. 
williamr@2:  */
williamr@2: 
williamr@2: #ifndef __G_NODE_H__
williamr@2: #define __G_NODE_H__
williamr@2: 
williamr@2: #include <_ansi.h>
williamr@2: #include <glib/gmem.h>
williamr@2: 
williamr@2: G_BEGIN_DECLS
williamr@2: 
williamr@2: typedef struct _GNode		GNode;
williamr@2: 
williamr@2: /* Tree traverse flags */
williamr@2: typedef enum
williamr@2: {
williamr@2:   G_TRAVERSE_LEAVES     = 1 << 0,
williamr@2:   G_TRAVERSE_NON_LEAVES = 1 << 1,
williamr@2:   G_TRAVERSE_ALL        = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
williamr@2:   G_TRAVERSE_MASK       = 0x03,
williamr@2:   G_TRAVERSE_LEAFS      = G_TRAVERSE_LEAVES,
williamr@2:   G_TRAVERSE_NON_LEAFS  = G_TRAVERSE_NON_LEAVES
williamr@2: } GTraverseFlags;
williamr@2: 
williamr@2: /* Tree traverse orders */
williamr@2: typedef enum
williamr@2: {
williamr@2:   G_IN_ORDER,
williamr@2:   G_PRE_ORDER,
williamr@2:   G_POST_ORDER,
williamr@2:   G_LEVEL_ORDER
williamr@2: } GTraverseType;
williamr@2: 
williamr@2: typedef gboolean	(*GNodeTraverseFunc)	(GNode	       *node,
williamr@2: 						 gpointer	data);
williamr@2: typedef void		(*GNodeForeachFunc)	(GNode	       *node,
williamr@2: 						 gpointer	data);
williamr@2: typedef gpointer	(*GCopyFunc)            (gconstpointer  src,
williamr@2:                                                  gpointer       data);
williamr@2: 
williamr@2: /* N-way tree implementation
williamr@2:  */
williamr@2: struct _GNode
williamr@2: {
williamr@2:   gpointer data;
williamr@2:   GNode	  *next;
williamr@2:   GNode	  *prev;
williamr@2:   GNode	  *parent;
williamr@2:   GNode	  *children;
williamr@2: };
williamr@2: 
williamr@2: #define	 G_NODE_IS_ROOT(node)	(((GNode*) (node))->parent == NULL && \
williamr@2: 				 ((GNode*) (node))->prev == NULL && \
williamr@2: 				 ((GNode*) (node))->next == NULL)
williamr@2: #define	 G_NODE_IS_LEAF(node)	(((GNode*) (node))->children == NULL)
williamr@2: 
williamr@2: IMPORT_C GNode*	 g_node_new		(gpointer	   data);
williamr@2: IMPORT_C void	 g_node_destroy		(GNode		  *root);
williamr@2: IMPORT_C void	 g_node_unlink		(GNode		  *node);
williamr@2: IMPORT_C GNode*   g_node_copy_deep       (GNode            *node,
williamr@2: 				 GCopyFunc         copy_func,
williamr@2: 				 gpointer          data);
williamr@2: IMPORT_C GNode*   g_node_copy            (GNode            *node);
williamr@2: IMPORT_C GNode*	 g_node_insert		(GNode		  *parent,
williamr@2: 				 gint		   position,
williamr@2: 				 GNode		  *node);
williamr@2: IMPORT_C GNode*	 g_node_insert_before	(GNode		  *parent,
williamr@2: 				 GNode		  *sibling,
williamr@2: 				 GNode		  *node);
williamr@2: IMPORT_C GNode*   g_node_insert_after    (GNode            *parent,
williamr@2: 				 GNode            *sibling,
williamr@2: 				 GNode            *node); 
williamr@2: IMPORT_C GNode*	 g_node_prepend		(GNode		  *parent,
williamr@2: 				 GNode		  *node);
williamr@2: IMPORT_C guint	 g_node_n_nodes		(GNode		  *root,
williamr@2: 				 GTraverseFlags	   flags);
williamr@2: IMPORT_C GNode*	 g_node_get_root	(GNode		  *node);
williamr@2: IMPORT_C gboolean g_node_is_ancestor	(GNode		  *node,
williamr@2: 				 GNode		  *descendant);
williamr@2: IMPORT_C guint	 g_node_depth		(GNode		  *node);
williamr@2: IMPORT_C GNode*	 g_node_find		(GNode		  *root,
williamr@2: 				 GTraverseType	   order,
williamr@2: 				 GTraverseFlags	   flags,
williamr@2: 				 gpointer	   data);
williamr@2: 
williamr@2: /* convenience macros */
williamr@2: #define g_node_append(parent, node)				\
williamr@2:      g_node_insert_before ((parent), NULL, (node))
williamr@2: #define	g_node_insert_data(parent, position, data)		\
williamr@2:      g_node_insert ((parent), (position), g_node_new (data))
williamr@2: #define	g_node_insert_data_before(parent, sibling, data)	\
williamr@2:      g_node_insert_before ((parent), (sibling), g_node_new (data))
williamr@2: #define	g_node_prepend_data(parent, data)			\
williamr@2:      g_node_prepend ((parent), g_node_new (data))
williamr@2: #define	g_node_append_data(parent, data)			\
williamr@2:      g_node_insert_before ((parent), NULL, g_node_new (data))
williamr@2: 
williamr@2: /* traversal function, assumes that `node' is root
williamr@2:  * (only traverses `node' and its subtree).
williamr@2:  * this function is just a high level interface to
williamr@2:  * low level traversal functions, optimized for speed.
williamr@2:  */
williamr@2: IMPORT_C void	 g_node_traverse	(GNode		  *root,
williamr@2: 				 GTraverseType	   order,
williamr@2: 				 GTraverseFlags	   flags,
williamr@2: 				 gint		   max_depth,
williamr@2: 				 GNodeTraverseFunc func,
williamr@2: 				 gpointer	   data);
williamr@2: 
williamr@2: /* return the maximum tree height starting with `node', this is an expensive
williamr@2:  * operation, since we need to visit all nodes. this could be shortened by
williamr@2:  * adding `guint height' to struct _GNode, but then again, this is not very
williamr@2:  * often needed, and would make g_node_insert() more time consuming.
williamr@2:  */
williamr@2: IMPORT_C guint	 g_node_max_height	 (GNode *root);
williamr@2: 
williamr@2: IMPORT_C void	 g_node_children_foreach (GNode		  *node,
williamr@2: 				  GTraverseFlags   flags,
williamr@2: 				  GNodeForeachFunc func,
williamr@2: 				  gpointer	   data);
williamr@2: IMPORT_C void	 g_node_reverse_children (GNode		  *node);
williamr@2: IMPORT_C guint	 g_node_n_children	 (GNode		  *node);
williamr@2: IMPORT_C GNode*	 g_node_nth_child	 (GNode		  *node,
williamr@2: 				  guint		   n);
williamr@2: IMPORT_C GNode*	 g_node_last_child	 (GNode		  *node);
williamr@2: IMPORT_C GNode*	 g_node_find_child	 (GNode		  *node,
williamr@2: 				  GTraverseFlags   flags,
williamr@2: 				  gpointer	   data);
williamr@2: IMPORT_C gint	 g_node_child_position	 (GNode		  *node,
williamr@2: 				  GNode		  *child);
williamr@2: IMPORT_C gint	 g_node_child_index	 (GNode		  *node,
williamr@2: 				  gpointer	   data);
williamr@2: 
williamr@2: IMPORT_C GNode*	 g_node_first_sibling	 (GNode		  *node);
williamr@2: IMPORT_C GNode*	 g_node_last_sibling	 (GNode		  *node);
williamr@2: 
williamr@2: #define	 g_node_prev_sibling(node)	((node) ? \
williamr@2: 					 ((GNode*) (node))->prev : NULL)
williamr@2: #define	 g_node_next_sibling(node)	((node) ? \
williamr@2: 					 ((GNode*) (node))->next : NULL)
williamr@2: #define	 g_node_first_child(node)	((node) ? \
williamr@2: 					 ((GNode*) (node))->children : NULL)
williamr@2: 
williamr@2: #ifndef G_DISABLE_DEPRECATED
williamr@2: IMPORT_C void     g_node_push_allocator  (gpointer          dummy);
williamr@2: IMPORT_C void     g_node_pop_allocator   (void);
williamr@2: #endif
williamr@2: G_END_DECLS
williamr@2: 
williamr@2: #endif /* __G_NODE_H__ */