gnode.h

00001 /* GLIB - Library of useful routines for C programming
00002  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
00003  * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU Lesser General Public
00007  * License as published by the Free Software Foundation; either
00008  * version 2 of the License, or (at your option) any later version.
00009  *
00010  * This library is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * Lesser General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU Lesser General Public
00016  * License along with this library; if not, write to the
00017  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00018  * Boston, MA 02111-1307, USA.
00019  */
00020 
00021 /*
00022  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
00023  * file for a list of people on the GLib Team.  See the ChangeLog
00024  * files for a list of changes.  These files are distributed with
00025  * GLib at ftp://ftp.gtk.org/pub/gtk/. 
00026  */
00027 
00028 #ifndef __G_NODE_H__
00029 #define __G_NODE_H__
00030 
00031 #include <_ansi.h>
00032 #include <glib/gmem.h>
00033 
00034 G_BEGIN_DECLS
00035 
00036 typedef struct _GNode           GNode;
00037 
00038 /* Tree traverse flags */
00039 typedef enum
00040 {
00041   G_TRAVERSE_LEAVES     = 1 << 0,
00042   G_TRAVERSE_NON_LEAVES = 1 << 1,
00043   G_TRAVERSE_ALL        = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
00044   G_TRAVERSE_MASK       = 0x03,
00045   G_TRAVERSE_LEAFS      = G_TRAVERSE_LEAVES,
00046   G_TRAVERSE_NON_LEAFS  = G_TRAVERSE_NON_LEAVES
00047 } GTraverseFlags;
00048 
00049 /* Tree traverse orders */
00050 typedef enum
00051 {
00052   G_IN_ORDER,
00053   G_PRE_ORDER,
00054   G_POST_ORDER,
00055   G_LEVEL_ORDER
00056 } GTraverseType;
00057 
00058 typedef gboolean        (*GNodeTraverseFunc)    (GNode         *node,
00059                                                  gpointer       data);
00060 typedef void            (*GNodeForeachFunc)     (GNode         *node,
00061                                                  gpointer       data);
00062 typedef gpointer        (*GCopyFunc)            (gconstpointer  src,
00063                                                  gpointer       data);
00064 
00065 /* N-way tree implementation
00066  */
00067 struct _GNode
00068 {
00069   gpointer data;
00070   GNode   *next;
00071   GNode   *prev;
00072   GNode   *parent;
00073   GNode   *children;
00074 };
00075 
00076 #define  G_NODE_IS_ROOT(node)   (((GNode*) (node))->parent == NULL && \
00077                                  ((GNode*) (node))->prev == NULL && \
00078                                  ((GNode*) (node))->next == NULL)
00079 #define  G_NODE_IS_LEAF(node)   (((GNode*) (node))->children == NULL)
00080 
00081 IMPORT_C GNode*  g_node_new             (gpointer          data);
00082 IMPORT_C void    g_node_destroy         (GNode            *root);
00083 IMPORT_C void    g_node_unlink          (GNode            *node);
00084 IMPORT_C GNode*   g_node_copy_deep       (GNode            *node,
00085                                  GCopyFunc         copy_func,
00086                                  gpointer          data);
00087 IMPORT_C GNode*   g_node_copy            (GNode            *node);
00088 IMPORT_C GNode*  g_node_insert          (GNode            *parent,
00089                                  gint              position,
00090                                  GNode            *node);
00091 IMPORT_C GNode*  g_node_insert_before   (GNode            *parent,
00092                                  GNode            *sibling,
00093                                  GNode            *node);
00094 IMPORT_C GNode*   g_node_insert_after    (GNode            *parent,
00095                                  GNode            *sibling,
00096                                  GNode            *node); 
00097 IMPORT_C GNode*  g_node_prepend         (GNode            *parent,
00098                                  GNode            *node);
00099 IMPORT_C guint   g_node_n_nodes         (GNode            *root,
00100                                  GTraverseFlags    flags);
00101 IMPORT_C GNode*  g_node_get_root        (GNode            *node);
00102 IMPORT_C gboolean g_node_is_ancestor    (GNode            *node,
00103                                  GNode            *descendant);
00104 IMPORT_C guint   g_node_depth           (GNode            *node);
00105 IMPORT_C GNode*  g_node_find            (GNode            *root,
00106                                  GTraverseType     order,
00107                                  GTraverseFlags    flags,
00108                                  gpointer          data);
00109 
00110 /* convenience macros */
00111 #define g_node_append(parent, node)                             \
00112      g_node_insert_before ((parent), NULL, (node))
00113 #define g_node_insert_data(parent, position, data)              \
00114      g_node_insert ((parent), (position), g_node_new (data))
00115 #define g_node_insert_data_before(parent, sibling, data)        \
00116      g_node_insert_before ((parent), (sibling), g_node_new (data))
00117 #define g_node_prepend_data(parent, data)                       \
00118      g_node_prepend ((parent), g_node_new (data))
00119 #define g_node_append_data(parent, data)                        \
00120      g_node_insert_before ((parent), NULL, g_node_new (data))
00121 
00122 /* traversal function, assumes that `node' is root
00123  * (only traverses `node' and its subtree).
00124  * this function is just a high level interface to
00125  * low level traversal functions, optimized for speed.
00126  */
00127 IMPORT_C void    g_node_traverse        (GNode            *root,
00128                                  GTraverseType     order,
00129                                  GTraverseFlags    flags,
00130                                  gint              max_depth,
00131                                  GNodeTraverseFunc func,
00132                                  gpointer          data);
00133 
00134 /* return the maximum tree height starting with `node', this is an expensive
00135  * operation, since we need to visit all nodes. this could be shortened by
00136  * adding `guint height' to struct _GNode, but then again, this is not very
00137  * often needed, and would make g_node_insert() more time consuming.
00138  */
00139 IMPORT_C guint   g_node_max_height       (GNode *root);
00140 
00141 IMPORT_C void    g_node_children_foreach (GNode           *node,
00142                                   GTraverseFlags   flags,
00143                                   GNodeForeachFunc func,
00144                                   gpointer         data);
00145 IMPORT_C void    g_node_reverse_children (GNode           *node);
00146 IMPORT_C guint   g_node_n_children       (GNode           *node);
00147 IMPORT_C GNode*  g_node_nth_child        (GNode           *node,
00148                                   guint            n);
00149 IMPORT_C GNode*  g_node_last_child       (GNode           *node);
00150 IMPORT_C GNode*  g_node_find_child       (GNode           *node,
00151                                   GTraverseFlags   flags,
00152                                   gpointer         data);
00153 IMPORT_C gint    g_node_child_position   (GNode           *node,
00154                                   GNode           *child);
00155 IMPORT_C gint    g_node_child_index      (GNode           *node,
00156                                   gpointer         data);
00157 
00158 IMPORT_C GNode*  g_node_first_sibling    (GNode           *node);
00159 IMPORT_C GNode*  g_node_last_sibling     (GNode           *node);
00160 
00161 #define  g_node_prev_sibling(node)      ((node) ? \
00162                                          ((GNode*) (node))->prev : NULL)
00163 #define  g_node_next_sibling(node)      ((node) ? \
00164                                          ((GNode*) (node))->next : NULL)
00165 #define  g_node_first_child(node)       ((node) ? \
00166                                          ((GNode*) (node))->children : NULL)
00167 
00168 #ifndef G_DISABLE_DEPRECATED
00169 IMPORT_C void     g_node_push_allocator  (gpointer          dummy);
00170 IMPORT_C void     g_node_pop_allocator   (void);
00171 #endif
00172 G_END_DECLS
00173 
00174 #endif /* __G_NODE_H__ */