|
1 /* GLIB - Library of useful routines for C programming |
|
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
|
3 * Portions copyright (c) 2006 Nokia Corporation. All rights reserved. |
|
4 * |
|
5 * This library is free software; you can redistribute it and/or |
|
6 * modify it under the terms of the GNU Lesser General Public |
|
7 * License as published by the Free Software Foundation; either |
|
8 * version 2 of the License, or (at your option) any later version. |
|
9 * |
|
10 * This library is distributed in the hope that it will be useful, |
|
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
13 * Lesser General Public License for more details. |
|
14 * |
|
15 * You should have received a copy of the GNU Lesser General Public |
|
16 * License along with this library; if not, write to the |
|
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
|
18 * Boston, MA 02111-1307, USA. |
|
19 */ |
|
20 |
|
21 /* |
|
22 * Modified by the GLib Team and others 1997-2000. See the AUTHORS |
|
23 * file for a list of people on the GLib Team. See the ChangeLog |
|
24 * files for a list of changes. These files are distributed with |
|
25 * GLib at ftp://ftp.gtk.org/pub/gtk/. |
|
26 */ |
|
27 |
|
28 #ifndef __G_NODE_H__ |
|
29 #define __G_NODE_H__ |
|
30 |
|
31 #include <_ansi.h> |
|
32 #include <glib/gmem.h> |
|
33 |
|
34 G_BEGIN_DECLS |
|
35 |
|
36 typedef struct _GNode GNode; |
|
37 |
|
38 /* Tree traverse flags */ |
|
39 typedef 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 */ |
|
50 typedef enum |
|
51 { |
|
52 G_IN_ORDER, |
|
53 G_PRE_ORDER, |
|
54 G_POST_ORDER, |
|
55 G_LEVEL_ORDER |
|
56 } GTraverseType; |
|
57 |
|
58 typedef gboolean (*GNodeTraverseFunc) (GNode *node, |
|
59 gpointer data); |
|
60 typedef void (*GNodeForeachFunc) (GNode *node, |
|
61 gpointer data); |
|
62 typedef gpointer (*GCopyFunc) (gconstpointer src, |
|
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 #define G_NODE_IS_ROOT(node) (((GNode*) (node))->parent == NULL && \ |
|
77 ((GNode*) (node))->prev == NULL && \ |
|
78 ((GNode*) (node))->next == NULL) |
|
79 #define G_NODE_IS_LEAF(node) (((GNode*) (node))->children == NULL) |
|
80 |
|
81 IMPORT_C GNode* g_node_new (gpointer data); |
|
82 IMPORT_C void g_node_destroy (GNode *root); |
|
83 IMPORT_C void g_node_unlink (GNode *node); |
|
84 IMPORT_C GNode* g_node_copy_deep (GNode *node, |
|
85 GCopyFunc copy_func, |
|
86 gpointer data); |
|
87 IMPORT_C GNode* g_node_copy (GNode *node); |
|
88 IMPORT_C GNode* g_node_insert (GNode *parent, |
|
89 gint position, |
|
90 GNode *node); |
|
91 IMPORT_C GNode* g_node_insert_before (GNode *parent, |
|
92 GNode *sibling, |
|
93 GNode *node); |
|
94 IMPORT_C GNode* g_node_insert_after (GNode *parent, |
|
95 GNode *sibling, |
|
96 GNode *node); |
|
97 IMPORT_C GNode* g_node_prepend (GNode *parent, |
|
98 GNode *node); |
|
99 IMPORT_C guint g_node_n_nodes (GNode *root, |
|
100 GTraverseFlags flags); |
|
101 IMPORT_C GNode* g_node_get_root (GNode *node); |
|
102 IMPORT_C gboolean g_node_is_ancestor (GNode *node, |
|
103 GNode *descendant); |
|
104 IMPORT_C guint g_node_depth (GNode *node); |
|
105 IMPORT_C GNode* g_node_find (GNode *root, |
|
106 GTraverseType order, |
|
107 GTraverseFlags flags, |
|
108 gpointer data); |
|
109 |
|
110 /* convenience macros */ |
|
111 #define g_node_append(parent, node) \ |
|
112 g_node_insert_before ((parent), NULL, (node)) |
|
113 #define g_node_insert_data(parent, position, data) \ |
|
114 g_node_insert ((parent), (position), g_node_new (data)) |
|
115 #define g_node_insert_data_before(parent, sibling, data) \ |
|
116 g_node_insert_before ((parent), (sibling), g_node_new (data)) |
|
117 #define g_node_prepend_data(parent, data) \ |
|
118 g_node_prepend ((parent), g_node_new (data)) |
|
119 #define g_node_append_data(parent, data) \ |
|
120 g_node_insert_before ((parent), NULL, g_node_new (data)) |
|
121 |
|
122 /* traversal function, assumes that `node' is root |
|
123 * (only traverses `node' and its subtree). |
|
124 * this function is just a high level interface to |
|
125 * low level traversal functions, optimized for speed. |
|
126 */ |
|
127 IMPORT_C void g_node_traverse (GNode *root, |
|
128 GTraverseType order, |
|
129 GTraverseFlags flags, |
|
130 gint max_depth, |
|
131 GNodeTraverseFunc func, |
|
132 gpointer data); |
|
133 |
|
134 /* return the maximum tree height starting with `node', this is an expensive |
|
135 * operation, since we need to visit all nodes. this could be shortened by |
|
136 * adding `guint height' to struct _GNode, but then again, this is not very |
|
137 * often needed, and would make g_node_insert() more time consuming. |
|
138 */ |
|
139 IMPORT_C guint g_node_max_height (GNode *root); |
|
140 |
|
141 IMPORT_C void g_node_children_foreach (GNode *node, |
|
142 GTraverseFlags flags, |
|
143 GNodeForeachFunc func, |
|
144 gpointer data); |
|
145 IMPORT_C void g_node_reverse_children (GNode *node); |
|
146 IMPORT_C guint g_node_n_children (GNode *node); |
|
147 IMPORT_C GNode* g_node_nth_child (GNode *node, |
|
148 guint n); |
|
149 IMPORT_C GNode* g_node_last_child (GNode *node); |
|
150 IMPORT_C GNode* g_node_find_child (GNode *node, |
|
151 GTraverseFlags flags, |
|
152 gpointer data); |
|
153 IMPORT_C gint g_node_child_position (GNode *node, |
|
154 GNode *child); |
|
155 IMPORT_C gint g_node_child_index (GNode *node, |
|
156 gpointer data); |
|
157 |
|
158 IMPORT_C GNode* g_node_first_sibling (GNode *node); |
|
159 IMPORT_C GNode* g_node_last_sibling (GNode *node); |
|
160 |
|
161 #define g_node_prev_sibling(node) ((node) ? \ |
|
162 ((GNode*) (node))->prev : NULL) |
|
163 #define g_node_next_sibling(node) ((node) ? \ |
|
164 ((GNode*) (node))->next : NULL) |
|
165 #define g_node_first_child(node) ((node) ? \ |
|
166 ((GNode*) (node))->children : NULL) |
|
167 |
|
168 #ifndef G_DISABLE_DEPRECATED |
|
169 IMPORT_C void g_node_push_allocator (gpointer dummy); |
|
170 IMPORT_C void g_node_pop_allocator (void); |
|
171 #endif |
|
172 G_END_DECLS |
|
173 |
|
174 #endif /* __G_NODE_H__ */ |