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
36G_BEGIN_DECLS
37
38typedef struct _GNode GNode;
39
40/* Tree traverse flags */
41typedef 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 */
52typedef enum
53{
54 G_IN_ORDER,
55 G_PRE_ORDER,
56 G_POST_ORDER,
57 G_LEVEL_ORDER
58} GTraverseType;
59
60typedef gboolean (*GNodeTraverseFunc) (GNode *node,
61 gpointer data);
62typedef void (*GNodeForeachFunc) (GNode *node,
63 gpointer data);
64
65/* N-way tree implementation
66 */
67struct _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
100GLIB_AVAILABLE_IN_ALL
101GNode* g_node_new (gpointer data);
102GLIB_AVAILABLE_IN_ALL
103void g_node_destroy (GNode *root);
104GLIB_AVAILABLE_IN_ALL
105void g_node_unlink (GNode *node);
106GLIB_AVAILABLE_IN_ALL
107GNode* g_node_copy_deep (GNode *node,
108 GCopyFunc copy_func,
109 gpointer data);
110GLIB_AVAILABLE_IN_ALL
111GNode* g_node_copy (GNode *node);
112GLIB_AVAILABLE_IN_ALL
113GNode* g_node_insert (GNode *parent,
114 gint position,
115 GNode *node);
116GLIB_AVAILABLE_IN_ALL
117GNode* g_node_insert_before (GNode *parent,
118 GNode *sibling,
119 GNode *node);
120GLIB_AVAILABLE_IN_ALL
121GNode* g_node_insert_after (GNode *parent,
122 GNode *sibling,
123 GNode *node);
124GLIB_AVAILABLE_IN_ALL
125GNode* g_node_prepend (GNode *parent,
126 GNode *node);
127GLIB_AVAILABLE_IN_ALL
128guint g_node_n_nodes (GNode *root,
129 GTraverseFlags flags);
130GLIB_AVAILABLE_IN_ALL
131GNode* g_node_get_root (GNode *node);
132GLIB_AVAILABLE_IN_ALL
133gboolean g_node_is_ancestor (GNode *node,
134 GNode *descendant);
135GLIB_AVAILABLE_IN_ALL
136guint g_node_depth (GNode *node);
137GLIB_AVAILABLE_IN_ALL
138GNode* 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 */
225GLIB_AVAILABLE_IN_ALL
226void 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 */
238GLIB_AVAILABLE_IN_ALL
239guint g_node_max_height (GNode *root);
240
241GLIB_AVAILABLE_IN_ALL
242void g_node_children_foreach (GNode *node,
243 GTraverseFlags flags,
244 GNodeForeachFunc func,
245 gpointer data);
246GLIB_AVAILABLE_IN_ALL
247void g_node_reverse_children (GNode *node);
248GLIB_AVAILABLE_IN_ALL
249guint g_node_n_children (GNode *node);
250GLIB_AVAILABLE_IN_ALL
251GNode* g_node_nth_child (GNode *node,
252 guint n);
253GLIB_AVAILABLE_IN_ALL
254GNode* g_node_last_child (GNode *node);
255GLIB_AVAILABLE_IN_ALL
256GNode* g_node_find_child (GNode *node,
257 GTraverseFlags flags,
258 gpointer data);
259GLIB_AVAILABLE_IN_ALL
260gint g_node_child_position (GNode *node,
261 GNode *child);
262GLIB_AVAILABLE_IN_ALL
263gint g_node_child_index (GNode *node,
264 gpointer data);
265
266GLIB_AVAILABLE_IN_ALL
267GNode* g_node_first_sibling (GNode *node);
268GLIB_AVAILABLE_IN_ALL
269GNode* 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
307G_END_DECLS
308
309#endif /* __G_NODE_H__ */
310