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.1 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, see <http://www.gnu.org/licenses/>.
16 */
17
18/*
19 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
20 * file for a list of people on the GLib Team. See the ChangeLog
21 * files for a list of changes. These files are distributed with
22 * GLib at ftp://ftp.gtk.org/pub/gtk/.
23 */
24
25#ifndef __G_NODE_H__
26#define __G_NODE_H__
27
28#if !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION)
29#error "Only <glib.h> can be included directly."
30#endif
31
32#include <glib/gmem.h>
33
34G_BEGIN_DECLS
35
36typedef struct _GNode GNode;
37
38/* Tree traverse flags */
39typedef enum
40{
41 G_TRAVERSE_LEAVES = 1 << 0,
42 G_TRAVERSE_NON_LEAVES = 1 << 1,
43 G_TRAVERSE_ALL = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
44 G_TRAVERSE_MASK = 0x03,
45 G_TRAVERSE_LEAFS = G_TRAVERSE_LEAVES,
46 G_TRAVERSE_NON_LEAFS = G_TRAVERSE_NON_LEAVES
47} GTraverseFlags;
48
49/* Tree traverse orders */
50typedef enum
51{
52 G_IN_ORDER,
53 G_PRE_ORDER,
54 G_POST_ORDER,
55 G_LEVEL_ORDER
56} GTraverseType;
57
58typedef gboolean (*GNodeTraverseFunc) (GNode *node,
59 gpointer data);
60typedef void (*GNodeForeachFunc) (GNode *node,
61 gpointer data);
62
63/* N-way tree implementation
64 */
65struct _GNode
66{
67 gpointer data;
68 GNode *next;
69 GNode *prev;
70 GNode *parent;
71 GNode *children;
72};
73
74/**
75 * G_NODE_IS_ROOT:
76 * @node: a #GNode
77 *
78 * Returns %TRUE if a #GNode is the root of a tree.
79 *
80 * Returns: %TRUE if the #GNode is the root of a tree
81 * (i.e. it has no parent or siblings)
82 */
83#define G_NODE_IS_ROOT(node) (((GNode*) (node))->parent == NULL && \
84 ((GNode*) (node))->prev == NULL && \
85 ((GNode*) (node))->next == NULL)
86
87/**
88 * G_NODE_IS_LEAF:
89 * @node: a #GNode
90 *
91 * Returns %TRUE if a #GNode is a leaf node.
92 *
93 * Returns: %TRUE if the #GNode is a leaf node
94 * (i.e. it has no children)
95 */
96#define G_NODE_IS_LEAF(node) (((GNode*) (node))->children == NULL)
97
98GLIB_AVAILABLE_IN_ALL
99GNode* g_node_new (gpointer data);
100GLIB_AVAILABLE_IN_ALL
101void g_node_destroy (GNode *root);
102GLIB_AVAILABLE_IN_ALL
103void g_node_unlink (GNode *node);
104GLIB_AVAILABLE_IN_ALL
105GNode* g_node_copy_deep (GNode *node,
106 GCopyFunc copy_func,
107 gpointer data);
108GLIB_AVAILABLE_IN_ALL
109GNode* g_node_copy (GNode *node);
110GLIB_AVAILABLE_IN_ALL
111GNode* g_node_insert (GNode *parent,
112 gint position,
113 GNode *node);
114GLIB_AVAILABLE_IN_ALL
115GNode* g_node_insert_before (GNode *parent,
116 GNode *sibling,
117 GNode *node);
118GLIB_AVAILABLE_IN_ALL
119GNode* g_node_insert_after (GNode *parent,
120 GNode *sibling,
121 GNode *node);
122GLIB_AVAILABLE_IN_ALL
123GNode* g_node_prepend (GNode *parent,
124 GNode *node);
125GLIB_AVAILABLE_IN_ALL
126guint g_node_n_nodes (GNode *root,
127 GTraverseFlags flags);
128GLIB_AVAILABLE_IN_ALL
129GNode* g_node_get_root (GNode *node);
130GLIB_AVAILABLE_IN_ALL
131gboolean g_node_is_ancestor (GNode *node,
132 GNode *descendant);
133GLIB_AVAILABLE_IN_ALL
134guint g_node_depth (GNode *node);
135GLIB_AVAILABLE_IN_ALL
136GNode* g_node_find (GNode *root,
137 GTraverseType order,
138 GTraverseFlags flags,
139 gpointer data);
140
141/* convenience macros */
142/**
143 * g_node_append:
144 * @parent: the #GNode to place the new #GNode under
145 * @node: the #GNode to insert
146 *
147 * Inserts a #GNode as the last child of the given parent.
148 *
149 * Returns: the inserted #GNode
150 */
151#define g_node_append(parent, node) \
152 g_node_insert_before ((parent), NULL, (node))
153
154/**
155 * g_node_insert_data:
156 * @parent: the #GNode to place the new #GNode under
157 * @position: the position to place the new #GNode at. If position is -1,
158 * the new #GNode is inserted as the last child of @parent
159 * @data: the data for the new #GNode
160 *
161 * Inserts a new #GNode at the given position.
162 *
163 * Returns: the new #GNode
164 */
165#define g_node_insert_data(parent, position, data) \
166 g_node_insert ((parent), (position), g_node_new (data))
167
168/**
169 * g_node_insert_data_after:
170 * @parent: the #GNode to place the new #GNode under
171 * @sibling: the sibling #GNode to place the new #GNode after
172 * @data: the data for the new #GNode
173 *
174 * Inserts a new #GNode after the given sibling.
175 *
176 * Returns: the new #GNode
177 */
178
179#define g_node_insert_data_after(parent, sibling, data) \
180 g_node_insert_after ((parent), (sibling), g_node_new (data))
181/**
182 * g_node_insert_data_before:
183 * @parent: the #GNode to place the new #GNode under
184 * @sibling: the sibling #GNode to place the new #GNode before
185 * @data: the data for the new #GNode
186 *
187 * Inserts a new #GNode before the given sibling.
188 *
189 * Returns: the new #GNode
190 */
191#define g_node_insert_data_before(parent, sibling, data) \
192 g_node_insert_before ((parent), (sibling), g_node_new (data))
193
194/**
195 * g_node_prepend_data:
196 * @parent: the #GNode to place the new #GNode under
197 * @data: the data for the new #GNode
198 *
199 * Inserts a new #GNode as the first child of the given parent.
200 *
201 * Returns: the new #GNode
202 */
203#define g_node_prepend_data(parent, data) \
204 g_node_prepend ((parent), g_node_new (data))
205
206/**
207 * g_node_append_data:
208 * @parent: the #GNode to place the new #GNode under
209 * @data: the data for the new #GNode
210 *
211 * Inserts a new #GNode as the last child of the given parent.
212 *
213 * Returns: the new #GNode
214 */
215#define g_node_append_data(parent, data) \
216 g_node_insert_before ((parent), NULL, g_node_new (data))
217
218/* traversal function, assumes that 'node' is root
219 * (only traverses 'node' and its subtree).
220 * this function is just a high level interface to
221 * low level traversal functions, optimized for speed.
222 */
223GLIB_AVAILABLE_IN_ALL
224void g_node_traverse (GNode *root,
225 GTraverseType order,
226 GTraverseFlags flags,
227 gint max_depth,
228 GNodeTraverseFunc func,
229 gpointer data);
230
231/* return the maximum tree height starting with 'node', this is an expensive
232 * operation, since we need to visit all nodes. this could be shortened by
233 * adding 'guint height' to struct _GNode, but then again, this is not very
234 * often needed, and would make g_node_insert() more time consuming.
235 */
236GLIB_AVAILABLE_IN_ALL
237guint g_node_max_height (GNode *root);
238
239GLIB_AVAILABLE_IN_ALL
240void g_node_children_foreach (GNode *node,
241 GTraverseFlags flags,
242 GNodeForeachFunc func,
243 gpointer data);
244GLIB_AVAILABLE_IN_ALL
245void g_node_reverse_children (GNode *node);
246GLIB_AVAILABLE_IN_ALL
247guint g_node_n_children (GNode *node);
248GLIB_AVAILABLE_IN_ALL
249GNode* g_node_nth_child (GNode *node,
250 guint n);
251GLIB_AVAILABLE_IN_ALL
252GNode* g_node_last_child (GNode *node);
253GLIB_AVAILABLE_IN_ALL
254GNode* g_node_find_child (GNode *node,
255 GTraverseFlags flags,
256 gpointer data);
257GLIB_AVAILABLE_IN_ALL
258gint g_node_child_position (GNode *node,
259 GNode *child);
260GLIB_AVAILABLE_IN_ALL
261gint g_node_child_index (GNode *node,
262 gpointer data);
263
264GLIB_AVAILABLE_IN_ALL
265GNode* g_node_first_sibling (GNode *node);
266GLIB_AVAILABLE_IN_ALL
267GNode* g_node_last_sibling (GNode *node);
268
269/**
270 * g_node_prev_sibling:
271 * @node: a #GNode
272 *
273 * Gets the previous sibling of a #GNode.
274 *
275 * Returns: the previous sibling of @node, or %NULL if @node is the first
276 * node or %NULL
277 */
278#define g_node_prev_sibling(node) ((node) ? \
279 ((GNode*) (node))->prev : NULL)
280
281/**
282 * g_node_next_sibling:
283 * @node: a #GNode
284 *
285 * Gets the next sibling of a #GNode.
286 *
287 * Returns: the next sibling of @node, or %NULL if @node is the last node
288 * or %NULL
289 */
290#define g_node_next_sibling(node) ((node) ? \
291 ((GNode*) (node))->next : NULL)
292
293/**
294 * g_node_first_child:
295 * @node: a #GNode
296 *
297 * Gets the first child of a #GNode.
298 *
299 * Returns: the first child of @node, or %NULL if @node is %NULL
300 * or has no children
301 */
302#define g_node_first_child(node) ((node) ? \
303 ((GNode*) (node))->children : NULL)
304
305G_END_DECLS
306
307#endif /* __G_NODE_H__ */
308