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