• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19 
20 /*
21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
22  * file for a list of people on the GLib Team.  See the ChangeLog
23  * files for a list of changes.  These files are distributed with
24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
25  */
26 
27 #if defined(G_DISABLE_SINGLE_INCLUDES) && !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION)
28 #error "Only <glib.h> can be included directly."
29 #endif
30 
31 #ifndef __G_NODE_H__
32 #define __G_NODE_H__
33 
34 #include <glib/gmem.h>
35 
36 G_BEGIN_DECLS
37 
38 typedef struct _GNode		GNode;
39 
40 /* Tree traverse flags */
41 typedef enum
42 {
43   G_TRAVERSE_LEAVES     = 1 << 0,
44   G_TRAVERSE_NON_LEAVES = 1 << 1,
45   G_TRAVERSE_ALL        = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
46   G_TRAVERSE_MASK       = 0x03,
47   G_TRAVERSE_LEAFS      = G_TRAVERSE_LEAVES,
48   G_TRAVERSE_NON_LEAFS  = G_TRAVERSE_NON_LEAVES
49 } GTraverseFlags;
50 
51 /* Tree traverse orders */
52 typedef enum
53 {
54   G_IN_ORDER,
55   G_PRE_ORDER,
56   G_POST_ORDER,
57   G_LEVEL_ORDER
58 } GTraverseType;
59 
60 typedef gboolean	(*GNodeTraverseFunc)	(GNode	       *node,
61 						 gpointer	data);
62 typedef void		(*GNodeForeachFunc)	(GNode	       *node,
63 						 gpointer	data);
64 
65 /**
66  * GCopyFunc:
67  * @src: A pointer to the data which should be copied
68  * @data: Additional data
69  *
70  * A function of this signature is used to copy the node data
71  * when doing a deep-copy of a tree.
72  *
73  * Returns: A pointer to the copy
74  *
75  * Since: 2.4
76  */
77 typedef gpointer	(*GCopyFunc)            (gconstpointer  src,
78                                                  gpointer       data);
79 
80 /* N-way tree implementation
81  */
82 struct _GNode
83 {
84   gpointer data;
85   GNode	  *next;
86   GNode	  *prev;
87   GNode	  *parent;
88   GNode	  *children;
89 };
90 
91 /**
92  * G_NODE_IS_ROOT:
93  * @node: a #GNode
94  *
95  * Returns %TRUE if a #GNode is the root of a tree.
96  *
97  * Returns: %TRUE if the #GNode is the root of a tree
98  *     (i.e. it has no parent or siblings)
99  */
100 #define	 G_NODE_IS_ROOT(node)	(((GNode*) (node))->parent == NULL && \
101 				 ((GNode*) (node))->prev == NULL && \
102 				 ((GNode*) (node))->next == NULL)
103 
104 /**
105  * G_NODE_IS_LEAF:
106  * @node: a #GNode
107  *
108  * Returns %TRUE if a #GNode is a leaf node.
109  *
110  * Returns: %TRUE if the #GNode is a leaf node
111  *     (i.e. it has no children)
112  */
113 #define	 G_NODE_IS_LEAF(node)	(((GNode*) (node))->children == NULL)
114 
115 GNode*	 g_node_new		(gpointer	   data);
116 void	 g_node_destroy		(GNode		  *root);
117 void	 g_node_unlink		(GNode		  *node);
118 GNode*   g_node_copy_deep       (GNode            *node,
119 				 GCopyFunc         copy_func,
120 				 gpointer          data);
121 GNode*   g_node_copy            (GNode            *node);
122 GNode*	 g_node_insert		(GNode		  *parent,
123 				 gint		   position,
124 				 GNode		  *node);
125 GNode*	 g_node_insert_before	(GNode		  *parent,
126 				 GNode		  *sibling,
127 				 GNode		  *node);
128 GNode*   g_node_insert_after    (GNode            *parent,
129 				 GNode            *sibling,
130 				 GNode            *node);
131 GNode*	 g_node_prepend		(GNode		  *parent,
132 				 GNode		  *node);
133 guint	 g_node_n_nodes		(GNode		  *root,
134 				 GTraverseFlags	   flags);
135 GNode*	 g_node_get_root	(GNode		  *node);
136 gboolean g_node_is_ancestor	(GNode		  *node,
137 				 GNode		  *descendant);
138 guint	 g_node_depth		(GNode		  *node);
139 GNode*	 g_node_find		(GNode		  *root,
140 				 GTraverseType	   order,
141 				 GTraverseFlags	   flags,
142 				 gpointer	   data);
143 
144 /* convenience macros */
145 /**
146  * g_node_append:
147  * @parent: the #GNode to place the new #GNode under
148  * @node: the #GNode to insert
149  *
150  * Inserts a #GNode as the last child of the given parent.
151  *
152  * Returns: the inserted #GNode
153  */
154 #define g_node_append(parent, node)				\
155      g_node_insert_before ((parent), NULL, (node))
156 
157 /**
158  * g_node_insert_data:
159  * @parent: the #GNode to place the new #GNode under
160  * @position: the position to place the new #GNode at. If position is -1,
161  *     the new #GNode is inserted as the last child of @parent
162  * @data: the data for the new #GNode
163  *
164  * Inserts a new #GNode at the given position.
165  *
166  * Returns: the new #GNode
167  */
168 #define	g_node_insert_data(parent, position, data)		\
169      g_node_insert ((parent), (position), g_node_new (data))
170 
171 /**
172  * g_node_insert_data_before:
173  * @parent: the #GNode to place the new #GNode under
174  * @sibling: the sibling #GNode to place the new #GNode before
175  * @data: the data for the new #GNode
176  *
177  * Inserts a new #GNode before the given sibling.
178  *
179  * Returns: the new #GNode
180  */
181 #define	g_node_insert_data_before(parent, sibling, data)	\
182      g_node_insert_before ((parent), (sibling), g_node_new (data))
183 
184 /**
185  * g_node_prepend_data:
186  * @parent: the #GNode to place the new #GNode under
187  * @data: the data for the new #GNode
188  *
189  * Inserts a new #GNode as the first child of the given parent.
190  *
191  * Returns: the new #GNode
192  */
193 #define	g_node_prepend_data(parent, data)			\
194      g_node_prepend ((parent), g_node_new (data))
195 
196 /**
197  * g_node_append_data:
198  * @parent: the #GNode to place the new #GNode under
199  * @data: the data for the new #GNode
200  *
201  * Inserts a new #GNode as the last child of the given parent.
202  *
203  * Returns: the new #GNode
204  */
205 #define	g_node_append_data(parent, data)			\
206      g_node_insert_before ((parent), NULL, g_node_new (data))
207 
208 /* traversal function, assumes that `node' is root
209  * (only traverses `node' and its subtree).
210  * this function is just a high level interface to
211  * low level traversal functions, optimized for speed.
212  */
213 void	 g_node_traverse	(GNode		  *root,
214 				 GTraverseType	   order,
215 				 GTraverseFlags	   flags,
216 				 gint		   max_depth,
217 				 GNodeTraverseFunc func,
218 				 gpointer	   data);
219 
220 /* return the maximum tree height starting with `node', this is an expensive
221  * operation, since we need to visit all nodes. this could be shortened by
222  * adding `guint height' to struct _GNode, but then again, this is not very
223  * often needed, and would make g_node_insert() more time consuming.
224  */
225 guint	 g_node_max_height	 (GNode *root);
226 
227 void	 g_node_children_foreach (GNode		  *node,
228 				  GTraverseFlags   flags,
229 				  GNodeForeachFunc func,
230 				  gpointer	   data);
231 void	 g_node_reverse_children (GNode		  *node);
232 guint	 g_node_n_children	 (GNode		  *node);
233 GNode*	 g_node_nth_child	 (GNode		  *node,
234 				  guint		   n);
235 GNode*	 g_node_last_child	 (GNode		  *node);
236 GNode*	 g_node_find_child	 (GNode		  *node,
237 				  GTraverseFlags   flags,
238 				  gpointer	   data);
239 gint	 g_node_child_position	 (GNode		  *node,
240 				  GNode		  *child);
241 gint	 g_node_child_index	 (GNode		  *node,
242 				  gpointer	   data);
243 
244 GNode*	 g_node_first_sibling	 (GNode		  *node);
245 GNode*	 g_node_last_sibling	 (GNode		  *node);
246 
247 /**
248  * g_node_prev_sibling:
249  * @node: a #GNode
250  *
251  * Gets the previous sibling of a #GNode.
252  *
253  * Returns: the previous sibling of @node, or %NULL if @node is %NULL
254  */
255 #define	 g_node_prev_sibling(node)	((node) ? \
256 					 ((GNode*) (node))->prev : NULL)
257 
258 /**
259  * g_node_next_sibling:
260  * @node: a #GNode
261  *
262  * Gets the next sibling of a #GNode.
263  *
264  * Returns: the next sibling of @node, or %NULL if @node is %NULL
265  */
266 #define	 g_node_next_sibling(node)	((node) ? \
267 					 ((GNode*) (node))->next : NULL)
268 
269 /**
270  * g_node_first_child:
271  * @node: a #GNode
272  *
273  * Gets the first child of a #GNode.
274  *
275  * Returns: the first child of @node, or %NULL if @node is %NULL
276  *     or has no children
277  */
278 #define	 g_node_first_child(node)	((node) ? \
279 					 ((GNode*) (node))->children : NULL)
280 
281 #ifndef G_DISABLE_DEPRECATED
282 void     g_node_push_allocator  (gpointer          dummy);
283 void     g_node_pop_allocator   (void);
284 #endif
285 
286 G_END_DECLS
287 
288 #endif /* __G_NODE_H__ */
289