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/**
64 * GCopyFunc:
65 * @src: (not nullable): A pointer to the data which should be copied
66 * @data: Additional data
67 *
68 * A function of this signature is used to copy the node data
69 * when doing a deep-copy of a tree.
70 *
71 * Returns: (not nullable): A pointer to the copy
72 *
73 * Since: 2.4
74 */
75typedef gpointer (*GCopyFunc) (gconstpointer src,
76 gpointer data);
77
78/* N-way tree implementation
79 */
80struct _GNode
81{
82 gpointer data;
83 GNode *next;
84 GNode *prev;
85 GNode *parent;
86 GNode *children;
87};
88
89/**
90 * G_NODE_IS_ROOT:
91 * @node: a #GNode
92 *
93 * Returns %TRUE if a #GNode is the root of a tree.
94 *
95 * Returns: %TRUE if the #GNode is the root of a tree
96 * (i.e. it has no parent or siblings)
97 */
98#define G_NODE_IS_ROOT(node) (((GNode*) (node))->parent == NULL && \
99 ((GNode*) (node))->prev == NULL && \
100 ((GNode*) (node))->next == NULL)
101
102/**
103 * G_NODE_IS_LEAF:
104 * @node: a #GNode
105 *
106 * Returns %TRUE if a #GNode is a leaf node.
107 *
108 * Returns: %TRUE if the #GNode is a leaf node
109 * (i.e. it has no children)
110 */
111#define G_NODE_IS_LEAF(node) (((GNode*) (node))->children == NULL)
112
113GLIB_AVAILABLE_IN_ALL
114GNode* g_node_new (gpointer data);
115GLIB_AVAILABLE_IN_ALL
116void g_node_destroy (GNode *root);
117GLIB_AVAILABLE_IN_ALL
118void g_node_unlink (GNode *node);
119GLIB_AVAILABLE_IN_ALL
120GNode* g_node_copy_deep (GNode *node,
121 GCopyFunc copy_func,
122 gpointer data);
123GLIB_AVAILABLE_IN_ALL
124GNode* g_node_copy (GNode *node);
125GLIB_AVAILABLE_IN_ALL
126GNode* g_node_insert (GNode *parent,
127 gint position,
128 GNode *node);
129GLIB_AVAILABLE_IN_ALL
130GNode* g_node_insert_before (GNode *parent,
131 GNode *sibling,
132 GNode *node);
133GLIB_AVAILABLE_IN_ALL
134GNode* g_node_insert_after (GNode *parent,
135 GNode *sibling,
136 GNode *node);
137GLIB_AVAILABLE_IN_ALL
138GNode* g_node_prepend (GNode *parent,
139 GNode *node);
140GLIB_AVAILABLE_IN_ALL
141guint g_node_n_nodes (GNode *root,
142 GTraverseFlags flags);
143GLIB_AVAILABLE_IN_ALL
144GNode* g_node_get_root (GNode *node);
145GLIB_AVAILABLE_IN_ALL
146gboolean g_node_is_ancestor (GNode *node,
147 GNode *descendant);
148GLIB_AVAILABLE_IN_ALL
149guint g_node_depth (GNode *node);
150GLIB_AVAILABLE_IN_ALL
151GNode* g_node_find (GNode *root,
152 GTraverseType order,
153 GTraverseFlags flags,
154 gpointer data);
155
156/* convenience macros */
157/**
158 * g_node_append:
159 * @parent: the #GNode to place the new #GNode under
160 * @node: the #GNode to insert
161 *
162 * Inserts a #GNode as the last child of the given parent.
163 *
164 * Returns: the inserted #GNode
165 */
166#define g_node_append(parent, node) \
167 g_node_insert_before ((parent), NULL, (node))
168
169/**
170 * g_node_insert_data:
171 * @parent: the #GNode to place the new #GNode under
172 * @position: the position to place the new #GNode at. If position is -1,
173 * the new #GNode is inserted as the last child of @parent
174 * @data: the data for the new #GNode
175 *
176 * Inserts a new #GNode at the given position.
177 *
178 * Returns: the new #GNode
179 */
180#define g_node_insert_data(parent, position, data) \
181 g_node_insert ((parent), (position), g_node_new (data))
182
183/**
184 * g_node_insert_data_after:
185 * @parent: the #GNode to place the new #GNode under
186 * @sibling: the sibling #GNode to place the new #GNode after
187 * @data: the data for the new #GNode
188 *
189 * Inserts a new #GNode after the given sibling.
190 *
191 * Returns: the new #GNode
192 */
193
194#define g_node_insert_data_after(parent, sibling, data) \
195 g_node_insert_after ((parent), (sibling), g_node_new (data))
196/**
197 * g_node_insert_data_before:
198 * @parent: the #GNode to place the new #GNode under
199 * @sibling: the sibling #GNode to place the new #GNode before
200 * @data: the data for the new #GNode
201 *
202 * Inserts a new #GNode before the given sibling.
203 *
204 * Returns: the new #GNode
205 */
206#define g_node_insert_data_before(parent, sibling, data) \
207 g_node_insert_before ((parent), (sibling), g_node_new (data))
208
209/**
210 * g_node_prepend_data:
211 * @parent: the #GNode to place the new #GNode under
212 * @data: the data for the new #GNode
213 *
214 * Inserts a new #GNode as the first child of the given parent.
215 *
216 * Returns: the new #GNode
217 */
218#define g_node_prepend_data(parent, data) \
219 g_node_prepend ((parent), g_node_new (data))
220
221/**
222 * g_node_append_data:
223 * @parent: the #GNode to place the new #GNode under
224 * @data: the data for the new #GNode
225 *
226 * Inserts a new #GNode as the last child of the given parent.
227 *
228 * Returns: the new #GNode
229 */
230#define g_node_append_data(parent, data) \
231 g_node_insert_before ((parent), NULL, g_node_new (data))
232
233/* traversal function, assumes that 'node' is root
234 * (only traverses 'node' and its subtree).
235 * this function is just a high level interface to
236 * low level traversal functions, optimized for speed.
237 */
238GLIB_AVAILABLE_IN_ALL
239void g_node_traverse (GNode *root,
240 GTraverseType order,
241 GTraverseFlags flags,
242 gint max_depth,
243 GNodeTraverseFunc func,
244 gpointer data);
245
246/* return the maximum tree height starting with 'node', this is an expensive
247 * operation, since we need to visit all nodes. this could be shortened by
248 * adding 'guint height' to struct _GNode, but then again, this is not very
249 * often needed, and would make g_node_insert() more time consuming.
250 */
251GLIB_AVAILABLE_IN_ALL
252guint g_node_max_height (GNode *root);
253
254GLIB_AVAILABLE_IN_ALL
255void g_node_children_foreach (GNode *node,
256 GTraverseFlags flags,
257 GNodeForeachFunc func,
258 gpointer data);
259GLIB_AVAILABLE_IN_ALL
260void g_node_reverse_children (GNode *node);
261GLIB_AVAILABLE_IN_ALL
262guint g_node_n_children (GNode *node);
263GLIB_AVAILABLE_IN_ALL
264GNode* g_node_nth_child (GNode *node,
265 guint n);
266GLIB_AVAILABLE_IN_ALL
267GNode* g_node_last_child (GNode *node);
268GLIB_AVAILABLE_IN_ALL
269GNode* g_node_find_child (GNode *node,
270 GTraverseFlags flags,
271 gpointer data);
272GLIB_AVAILABLE_IN_ALL
273gint g_node_child_position (GNode *node,
274 GNode *child);
275GLIB_AVAILABLE_IN_ALL
276gint g_node_child_index (GNode *node,
277 gpointer data);
278
279GLIB_AVAILABLE_IN_ALL
280GNode* g_node_first_sibling (GNode *node);
281GLIB_AVAILABLE_IN_ALL
282GNode* g_node_last_sibling (GNode *node);
283
284/**
285 * g_node_prev_sibling:
286 * @node: a #GNode
287 *
288 * Gets the previous sibling of a #GNode.
289 *
290 * Returns: the previous sibling of @node, or %NULL if @node is the first
291 * node or %NULL
292 */
293#define g_node_prev_sibling(node) ((node) ? \
294 ((GNode*) (node))->prev : NULL)
295
296/**
297 * g_node_next_sibling:
298 * @node: a #GNode
299 *
300 * Gets the next sibling of a #GNode.
301 *
302 * Returns: the next sibling of @node, or %NULL if @node is the last node
303 * or %NULL
304 */
305#define g_node_next_sibling(node) ((node) ? \
306 ((GNode*) (node))->next : NULL)
307
308/**
309 * g_node_first_child:
310 * @node: a #GNode
311 *
312 * Gets the first child of a #GNode.
313 *
314 * Returns: the first child of @node, or %NULL if @node is %NULL
315 * or has no children
316 */
317#define g_node_first_child(node) ((node) ? \
318 ((GNode*) (node))->children : NULL)
319
320G_END_DECLS
321
322#endif /* __G_NODE_H__ */
323