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