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