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__ */ |
310 | |