glib-2.0/glib/gnode.h

0001 /* GLIB - Library of useful routines for C programming
0002  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
0003  *
0004  * SPDX-License-Identifier: LGPL-2.1-or-later
0005  *
0006  * This library is free software; you can redistribute it and/or
0007  * modify it under the terms of the GNU Lesser General Public
0008  * License as published by the Free Software Foundation; either
0009  * version 2.1 of the License, or (at your option) any later version.
0010  *
0011  * This library is distributed in the hope that it will be useful,
0012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0014  * Lesser General Public License for more details.
0015  *
0016  * You should have received a copy of the GNU Lesser General Public
0017  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
0018  */
0019
0020 /*
0021  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
0022  * file for a list of people on the GLib Team.  See the ChangeLog
0023  * files for a list of changes.  These files are distributed with
0024  * GLib at ftp://ftp.gtk.org/pub/gtk/.
0025  */
0026
0027 #ifndef __G_NODE_H__
0028 #define __G_NODE_H__
0029
0030 #if !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION)
0031 #error "Only <glib.h> can be included directly."
0032 #endif
0033
0034 #include <glib/gmem.h>
0035
0036 G_BEGIN_DECLS
0037
0038 typedef struct _GNode       GNode;
0039
0040 /* Tree traverse flags */
0041 typedef enum
0042 {
0043   G_TRAVERSE_LEAVES     = 1 << 0,
0044   G_TRAVERSE_NON_LEAVES = 1 << 1,
0045   G_TRAVERSE_ALL        = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
0046   G_TRAVERSE_MASK       = 0x03,
0047   G_TRAVERSE_LEAFS      = G_TRAVERSE_LEAVES,
0048   G_TRAVERSE_NON_LEAFS  = G_TRAVERSE_NON_LEAVES
0049 } GTraverseFlags;
0050
0051 /* Tree traverse orders */
0052 typedef enum
0053 {
0054   G_IN_ORDER,
0055   G_PRE_ORDER,
0056   G_POST_ORDER,
0057   G_LEVEL_ORDER
0058 } GTraverseType;
0059
0060 typedef gboolean    (*GNodeTraverseFunc)    (GNode         *node,
0061                          gpointer   data);
0062 typedef void        (*GNodeForeachFunc) (GNode         *node,
0063                          gpointer   data);
0064
0065 /* N-way tree implementation
0066  */
0067 struct _GNode
0068 {
0069   gpointer data;
0070   GNode   *next;
0071   GNode   *prev;
0072   GNode   *parent;
0073   GNode   *children;
0074 };
0075
0076 /**
0077  * G_NODE_IS_ROOT:
0078  * @node: a #GNode
0079  *
0080  * Returns %TRUE if a #GNode is the root of a tree.
0081  *
0082  * Returns: %TRUE if the #GNode is the root of a tree
0083  *     (i.e. it has no parent or siblings)
0084  */
0085 #define  G_NODE_IS_ROOT(node)   (((GNode*) (node))->parent == NULL && \
0086                  ((GNode*) (node))->prev == NULL && \
0087                  ((GNode*) (node))->next == NULL)
0088
0089 /**
0090  * G_NODE_IS_LEAF:
0091  * @node: a #GNode
0092  *
0093  * Returns %TRUE if a #GNode is a leaf node.
0094  *
0095  * Returns: %TRUE if the #GNode is a leaf node
0096  *     (i.e. it has no children)
0097  */
0098 #define  G_NODE_IS_LEAF(node)   (((GNode*) (node))->children == NULL)
0099
0100 GLIB_AVAILABLE_IN_ALL
0101 GNode*   g_node_new     (gpointer      data);
0102 GLIB_AVAILABLE_IN_ALL
0103 void     g_node_destroy     (GNode        *root);
0104 GLIB_AVAILABLE_IN_ALL
0105 void     g_node_unlink      (GNode        *node);
0106 GLIB_AVAILABLE_IN_ALL
0107 GNode*   g_node_copy_deep       (GNode            *node,
0108                  GCopyFunc         copy_func,
0109                  gpointer          data);
0110 GLIB_AVAILABLE_IN_ALL
0111 GNode*   g_node_copy            (GNode            *node);
0112 GLIB_AVAILABLE_IN_ALL
0113 GNode*   g_node_insert      (GNode        *parent,
0114                  gint          position,
0115                  GNode        *node);
0116 GLIB_AVAILABLE_IN_ALL
0117 GNode*   g_node_insert_before   (GNode        *parent,
0118                  GNode        *sibling,
0119                  GNode        *node);
0120 GLIB_AVAILABLE_IN_ALL
0121 GNode*   g_node_insert_after    (GNode            *parent,
0122                  GNode            *sibling,
0123                  GNode            *node);
0124 GLIB_AVAILABLE_IN_ALL
0125 GNode*   g_node_prepend     (GNode        *parent,
0126                  GNode        *node);
0127 GLIB_AVAILABLE_IN_ALL
0128 guint    g_node_n_nodes     (GNode        *root,
0129                  GTraverseFlags    flags);
0130 GLIB_AVAILABLE_IN_ALL
0131 GNode*   g_node_get_root    (GNode        *node);
0132 GLIB_AVAILABLE_IN_ALL
0133 gboolean g_node_is_ancestor (GNode        *node,
0134                  GNode        *descendant);
0135 GLIB_AVAILABLE_IN_ALL
0136 guint    g_node_depth       (GNode        *node);
0137 GLIB_AVAILABLE_IN_ALL
0138 GNode*   g_node_find        (GNode        *root,
0139                  GTraverseType     order,
0140                  GTraverseFlags    flags,
0141                  gpointer      data);
0142
0143 /* convenience macros */
0144 /**
0145  * g_node_append:
0146  * @parent: the #GNode to place the new #GNode under
0147  * @node: the #GNode to insert
0148  *
0149  * Inserts a #GNode as the last child of the given parent.
0150  *
0151  * Returns: the inserted #GNode
0152  */
0153 #define g_node_append(parent, node)             \
0154      g_node_insert_before ((parent), NULL, (node))
0155
0156 /**
0157  * g_node_insert_data:
0158  * @parent: the #GNode to place the new #GNode under
0159  * @position: the position to place the new #GNode at. If position is -1,
0160  *     the new #GNode is inserted as the last child of @parent
0161  * @data: the data for the new #GNode
0162  *
0163  * Inserts a new #GNode at the given position.
0164  *
0165  * Returns: the new #GNode
0166  */
0167 #define g_node_insert_data(parent, position, data)      \
0168      g_node_insert ((parent), (position), g_node_new (data))
0169
0170 /**
0171  * g_node_insert_data_after:
0172  * @parent: the #GNode to place the new #GNode under
0173  * @sibling: the sibling #GNode to place the new #GNode after
0174  * @data: the data for the new #GNode
0175  *
0176  * Inserts a new #GNode after the given sibling.
0177  *
0178  * Returns: the new #GNode
0179  */
0180
0181 #define g_node_insert_data_after(parent, sibling, data) \
0182      g_node_insert_after ((parent), (sibling), g_node_new (data))
0183 /**
0184  * g_node_insert_data_before:
0185  * @parent: the #GNode to place the new #GNode under
0186  * @sibling: the sibling #GNode to place the new #GNode before
0187  * @data: the data for the new #GNode
0188  *
0189  * Inserts a new #GNode before the given sibling.
0190  *
0191  * Returns: the new #GNode
0192  */
0193 #define g_node_insert_data_before(parent, sibling, data)    \
0194      g_node_insert_before ((parent), (sibling), g_node_new (data))
0195
0196 /**
0197  * g_node_prepend_data:
0198  * @parent: the #GNode to place the new #GNode under
0199  * @data: the data for the new #GNode
0200  *
0201  * Inserts a new #GNode as the first child of the given parent.
0202  *
0203  * Returns: the new #GNode
0204  */
0205 #define g_node_prepend_data(parent, data)           \
0206      g_node_prepend ((parent), g_node_new (data))
0207
0208 /**
0209  * g_node_append_data:
0210  * @parent: the #GNode to place the new #GNode under
0211  * @data: the data for the new #GNode
0212  *
0213  * Inserts a new #GNode as the last child of the given parent.
0214  *
0215  * Returns: the new #GNode
0216  */
0217 #define g_node_append_data(parent, data)            \
0218      g_node_insert_before ((parent), NULL, g_node_new (data))
0219
0220 /* traversal function, assumes that 'node' is root
0221  * (only traverses 'node' and its subtree).
0222  * this function is just a high level interface to
0223  * low level traversal functions, optimized for speed.
0224  */
0225 GLIB_AVAILABLE_IN_ALL
0226 void     g_node_traverse    (GNode        *root,
0227                  GTraverseType     order,
0228                  GTraverseFlags    flags,
0229                  gint          max_depth,
0230                  GNodeTraverseFunc func,
0231                  gpointer      data);
0232
0233 /* return the maximum tree height starting with 'node', this is an expensive
0234  * operation, since we need to visit all nodes. this could be shortened by
0235  * adding 'guint height' to struct _GNode, but then again, this is not very
0236  * often needed, and would make g_node_insert() more time consuming.
0237  */
0238 GLIB_AVAILABLE_IN_ALL
0239 guint    g_node_max_height   (GNode *root);
0240
0241 GLIB_AVAILABLE_IN_ALL
0242 void     g_node_children_foreach (GNode       *node,
0243                   GTraverseFlags   flags,
0244                   GNodeForeachFunc func,
0245                   gpointer     data);
0246 GLIB_AVAILABLE_IN_ALL
0247 void     g_node_reverse_children (GNode       *node);
0248 GLIB_AVAILABLE_IN_ALL
0249 guint    g_node_n_children   (GNode       *node);
0250 GLIB_AVAILABLE_IN_ALL
0251 GNode*   g_node_nth_child    (GNode       *node,
0252                   guint        n);
0253 GLIB_AVAILABLE_IN_ALL
0254 GNode*   g_node_last_child   (GNode       *node);
0255 GLIB_AVAILABLE_IN_ALL
0256 GNode*   g_node_find_child   (GNode       *node,
0257                   GTraverseFlags   flags,
0258                   gpointer     data);
0259 GLIB_AVAILABLE_IN_ALL
0260 gint     g_node_child_position   (GNode       *node,
0261                   GNode       *child);
0262 GLIB_AVAILABLE_IN_ALL
0263 gint     g_node_child_index  (GNode       *node,
0264                   gpointer     data);
0265
0266 GLIB_AVAILABLE_IN_ALL
0267 GNode*   g_node_first_sibling    (GNode       *node);
0268 GLIB_AVAILABLE_IN_ALL
0269 GNode*   g_node_last_sibling     (GNode       *node);
0270
0271 /**
0272  * g_node_prev_sibling:
0273  * @node: a #GNode
0274  *
0275  * Gets the previous sibling of a #GNode.
0276  *
0277  * Returns: the previous sibling of @node, or %NULL if @node is the first
0278  *     node or %NULL
0279  */
0280 #define  g_node_prev_sibling(node)  ((node) ? \
0281                      ((GNode*) (node))->prev : NULL)
0282
0283 /**
0284  * g_node_next_sibling:
0285  * @node: a #GNode
0286  *
0287  * Gets the next sibling of a #GNode.
0288  *
0289  * Returns: the next sibling of @node, or %NULL if @node is the last node
0290  *     or %NULL
0291  */
0292 #define  g_node_next_sibling(node)  ((node) ? \
0293                      ((GNode*) (node))->next : NULL)
0294
0295 /**
0296  * g_node_first_child:
0297  * @node: a #GNode
0298  *
0299  * Gets the first child of a #GNode.
0300  *
0301  * Returns: the first child of @node, or %NULL if @node is %NULL
0302  *     or has no children
0303  */
0304 #define  g_node_first_child(node)   ((node) ? \
0305                      ((GNode*) (node))->children : NULL)
0306
0307 G_END_DECLS
0308
0309 #endif /* __G_NODE_H__ */