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