1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * SPDX-License-Identifier: LGPL-2.1-or-later
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
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 #ifndef __G_NODE_H__
28 #define __G_NODE_H__
29
30 #if !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION)
31 #error "Only <glib.h> can be included directly."
32 #endif
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 /* N-way tree implementation
66 */
67 struct _GNode
68 {
69 gpointer data;
70 GNode *next;
71 GNode *prev;
72 GNode *parent;
73 GNode *children;
74 };
75
76 /**
77 * G_NODE_IS_ROOT:
78 * @node: a #GNode
79 *
80 * Returns %TRUE if a #GNode is the root of a tree.
81 *
82 * Returns: %TRUE if the #GNode is the root of a tree
83 * (i.e. it has no parent or siblings)
84 */
85 #define G_NODE_IS_ROOT(node) (((GNode*) (node))->parent == NULL && \
86 ((GNode*) (node))->prev == NULL && \
87 ((GNode*) (node))->next == NULL)
88
89 /**
90 * G_NODE_IS_LEAF:
91 * @node: a #GNode
92 *
93 * Returns %TRUE if a #GNode is a leaf node.
94 *
95 * Returns: %TRUE if the #GNode is a leaf node
96 * (i.e. it has no children)
97 */
98 #define G_NODE_IS_LEAF(node) (((GNode*) (node))->children == NULL)
99
100 GLIB_AVAILABLE_IN_ALL
101 GNode* g_node_new (gpointer data);
102 GLIB_AVAILABLE_IN_ALL
103 void g_node_destroy (GNode *root);
104 GLIB_AVAILABLE_IN_ALL
105 void g_node_unlink (GNode *node);
106 GLIB_AVAILABLE_IN_ALL
107 GNode* g_node_copy_deep (GNode *node,
108 GCopyFunc copy_func,
109 gpointer data);
110 GLIB_AVAILABLE_IN_ALL
111 GNode* g_node_copy (GNode *node);
112 GLIB_AVAILABLE_IN_ALL
113 GNode* g_node_insert (GNode *parent,
114 gint position,
115 GNode *node);
116 GLIB_AVAILABLE_IN_ALL
117 GNode* g_node_insert_before (GNode *parent,
118 GNode *sibling,
119 GNode *node);
120 GLIB_AVAILABLE_IN_ALL
121 GNode* g_node_insert_after (GNode *parent,
122 GNode *sibling,
123 GNode *node);
124 GLIB_AVAILABLE_IN_ALL
125 GNode* g_node_prepend (GNode *parent,
126 GNode *node);
127 GLIB_AVAILABLE_IN_ALL
128 guint g_node_n_nodes (GNode *root,
129 GTraverseFlags flags);
130 GLIB_AVAILABLE_IN_ALL
131 GNode* g_node_get_root (GNode *node);
132 GLIB_AVAILABLE_IN_ALL
133 gboolean g_node_is_ancestor (GNode *node,
134 GNode *descendant);
135 GLIB_AVAILABLE_IN_ALL
136 guint g_node_depth (GNode *node);
137 GLIB_AVAILABLE_IN_ALL
138 GNode* g_node_find (GNode *root,
139 GTraverseType order,
140 GTraverseFlags flags,
141 gpointer data);
142
143 /* convenience macros */
144 /**
145 * g_node_append:
146 * @parent: the #GNode to place the new #GNode under
147 * @node: the #GNode to insert
148 *
149 * Inserts a #GNode as the last child of the given parent.
150 *
151 * Returns: the inserted #GNode
152 */
153 #define g_node_append(parent, node) \
154 g_node_insert_before ((parent), NULL, (node))
155
156 /**
157 * g_node_insert_data:
158 * @parent: the #GNode to place the new #GNode under
159 * @position: the position to place the new #GNode at. If position is -1,
160 * the new #GNode is inserted as the last child of @parent
161 * @data: the data for the new #GNode
162 *
163 * Inserts a new #GNode at the given position.
164 *
165 * Returns: the new #GNode
166 */
167 #define g_node_insert_data(parent, position, data) \
168 g_node_insert ((parent), (position), g_node_new (data))
169
170 /**
171 * g_node_insert_data_after:
172 * @parent: the #GNode to place the new #GNode under
173 * @sibling: the sibling #GNode to place the new #GNode after
174 * @data: the data for the new #GNode
175 *
176 * Inserts a new #GNode after the given sibling.
177 *
178 * Returns: the new #GNode
179 */
180
181 #define g_node_insert_data_after(parent, sibling, data) \
182 g_node_insert_after ((parent), (sibling), g_node_new (data))
183 /**
184 * g_node_insert_data_before:
185 * @parent: the #GNode to place the new #GNode under
186 * @sibling: the sibling #GNode to place the new #GNode before
187 * @data: the data for the new #GNode
188 *
189 * Inserts a new #GNode before the given sibling.
190 *
191 * Returns: the new #GNode
192 */
193 #define g_node_insert_data_before(parent, sibling, data) \
194 g_node_insert_before ((parent), (sibling), g_node_new (data))
195
196 /**
197 * g_node_prepend_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 first child of the given parent.
202 *
203 * Returns: the new #GNode
204 */
205 #define g_node_prepend_data(parent, data) \
206 g_node_prepend ((parent), g_node_new (data))
207
208 /**
209 * g_node_append_data:
210 * @parent: the #GNode to place the new #GNode under
211 * @data: the data for the new #GNode
212 *
213 * Inserts a new #GNode as the last child of the given parent.
214 *
215 * Returns: the new #GNode
216 */
217 #define g_node_append_data(parent, data) \
218 g_node_insert_before ((parent), NULL, g_node_new (data))
219
220 /* traversal function, assumes that 'node' is root
221 * (only traverses 'node' and its subtree).
222 * this function is just a high level interface to
223 * low level traversal functions, optimized for speed.
224 */
225 GLIB_AVAILABLE_IN_ALL
226 void g_node_traverse (GNode *root,
227 GTraverseType order,
228 GTraverseFlags flags,
229 gint max_depth,
230 GNodeTraverseFunc func,
231 gpointer data);
232
233 /* return the maximum tree height starting with 'node', this is an expensive
234 * operation, since we need to visit all nodes. this could be shortened by
235 * adding 'guint height' to struct _GNode, but then again, this is not very
236 * often needed, and would make g_node_insert() more time consuming.
237 */
238 GLIB_AVAILABLE_IN_ALL
239 guint g_node_max_height (GNode *root);
240
241 GLIB_AVAILABLE_IN_ALL
242 void g_node_children_foreach (GNode *node,
243 GTraverseFlags flags,
244 GNodeForeachFunc func,
245 gpointer data);
246 GLIB_AVAILABLE_IN_ALL
247 void g_node_reverse_children (GNode *node);
248 GLIB_AVAILABLE_IN_ALL
249 guint g_node_n_children (GNode *node);
250 GLIB_AVAILABLE_IN_ALL
251 GNode* g_node_nth_child (GNode *node,
252 guint n);
253 GLIB_AVAILABLE_IN_ALL
254 GNode* g_node_last_child (GNode *node);
255 GLIB_AVAILABLE_IN_ALL
256 GNode* g_node_find_child (GNode *node,
257 GTraverseFlags flags,
258 gpointer data);
259 GLIB_AVAILABLE_IN_ALL
260 gint g_node_child_position (GNode *node,
261 GNode *child);
262 GLIB_AVAILABLE_IN_ALL
263 gint g_node_child_index (GNode *node,
264 gpointer data);
265
266 GLIB_AVAILABLE_IN_ALL
267 GNode* g_node_first_sibling (GNode *node);
268 GLIB_AVAILABLE_IN_ALL
269 GNode* g_node_last_sibling (GNode *node);
270
271 /**
272 * g_node_prev_sibling:
273 * @node: a #GNode
274 *
275 * Gets the previous sibling of a #GNode.
276 *
277 * Returns: the previous sibling of @node, or %NULL if @node is the first
278 * node or %NULL
279 */
280 #define g_node_prev_sibling(node) ((node) ? \
281 ((GNode*) (node))->prev : NULL)
282
283 /**
284 * g_node_next_sibling:
285 * @node: a #GNode
286 *
287 * Gets the next sibling of a #GNode.
288 *
289 * Returns: the next sibling of @node, or %NULL if @node is the last node
290 * or %NULL
291 */
292 #define g_node_next_sibling(node) ((node) ? \
293 ((GNode*) (node))->next : NULL)
294
295 /**
296 * g_node_first_child:
297 * @node: a #GNode
298 *
299 * Gets the first child of a #GNode.
300 *
301 * Returns: the first child of @node, or %NULL if @node is %NULL
302 * or has no children
303 */
304 #define g_node_first_child(node) ((node) ? \
305 ((GNode*) (node))->children : NULL)
306
307 G_END_DECLS
308
309 #endif /* __G_NODE_H__ */