glib/gnode.h

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