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