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_LEAFS      = 1 << 0,
  40   G_TRAVERSE_NON_LEAFS  = 1 << 1,
  41   G_TRAVERSE_ALL        = G_TRAVERSE_LEAFS | G_TRAVERSE_NON_LEAFS,
  42   G_TRAVERSE_MASK       = 0x03
  43 } GTraverseFlags;
  44
  45 /* Tree traverse orders */
  46 typedef enum
  47 {
  48   G_IN_ORDER,
  49   G_PRE_ORDER,
  50   G_POST_ORDER,
  51   G_LEVEL_ORDER
  52 } GTraverseType;
  53
  54 typedef gboolean        (*GNodeTraverseFunc)    (GNode         *node,
  55                                                  gpointer       data);
  56 typedef void            (*GNodeForeachFunc)     (GNode         *node,
  57                                                  gpointer       data);
  58 typedef gpointer        (*GCopyFunc)            (gconstpointer  src,
  59                                                  gpointer       data);
  60
  61 /* N-way tree implementation
  62  */
  63 struct _GNode
  64 {
  65   gpointer data;
  66   GNode   *next;
  67   GNode   *prev;
  68   GNode   *parent;
  69   GNode   *children;
  70 };
  71
  72 #define  G_NODE_IS_ROOT(node)   (((GNode*) (node))->parent == NULL && \
  73                                  ((GNode*) (node))->prev == NULL && \
  74                                  ((GNode*) (node))->next == NULL)
  75 #define  G_NODE_IS_LEAF(node)   (((GNode*) (node))->children == NULL)
  76
  77 void     g_node_push_allocator  (GAllocator       *allocator);
  78 void     g_node_pop_allocator   (void);
  79 GNode*   g_node_new             (gpointer          data);
  80 void     g_node_destroy         (GNode            *root);
  81 void     g_node_unlink          (GNode            *node);
  82 GNode*   g_node_copy_deep       (GNode            *node,
  83                                  GCopyFunc         copy_func,
  84                                  gpointer          data);
  85 GNode*   g_node_copy            (GNode            *node);
  86 GNode*   g_node_insert          (GNode            *parent,
  87                                  gint              position,
  88                                  GNode            *node);
  89 GNode*   g_node_insert_before   (GNode            *parent,
  90                                  GNode            *sibling,
  91                                  GNode            *node);
  92 GNode*   g_node_insert_after    (GNode            *parent,
  93                                  GNode            *sibling,
  94                                  GNode            *node);
  95 GNode*   g_node_prepend         (GNode            *parent,
  96                                  GNode            *node);
  97 guint    g_node_n_nodes         (GNode            *root,
  98                                  GTraverseFlags    flags);
  99 GNode*   g_node_get_root        (GNode            *node);
 100 gboolean g_node_is_ancestor     (GNode            *node,
 101                                  GNode            *descendant);
 102 guint    g_node_depth           (GNode            *node);
 103 GNode*   g_node_find            (GNode            *root,
 104                                  GTraverseType     order,
 105                                  GTraverseFlags    flags,
 106                                  gpointer          data);
 107
 108 /* convenience macros */
 109 #define g_node_append(parent, node)                             \
 110      g_node_insert_before ((parent), NULL, (node))
 111 #define g_node_insert_data(parent, position, data)              \
 112      g_node_insert ((parent), (position), g_node_new (data))
 113 #define g_node_insert_data_before(parent, sibling, data)        \
 114      g_node_insert_before ((parent), (sibling), g_node_new (data))
 115 #define g_node_prepend_data(parent, data)                       \
 116      g_node_prepend ((parent), g_node_new (data))
 117 #define g_node_append_data(parent, data)                        \
 118      g_node_insert_before ((parent), NULL, g_node_new (data))
 119
 120 /* traversal function, assumes that `node' is root
 121  * (only traverses `node' and its subtree).
 122  * this function is just a high level interface to
 123  * low level traversal functions, optimized for speed.
 124  */
 125 void     g_node_traverse        (GNode            *root,
 126                                  GTraverseType     order,
 127                                  GTraverseFlags    flags,
 128                                  gint              max_depth,
 129                                  GNodeTraverseFunc func,
 130                                  gpointer          data);
 131
 132 /* return the maximum tree height starting with `node', this is an expensive
 133  * operation, since we need to visit all nodes. this could be shortened by
 134  * adding `guint height' to struct _GNode, but then again, this is not very
 135  * often needed, and would make g_node_insert() more time consuming.
 136  */
 137 guint    g_node_max_height       (GNode *root);
 138
 139 void     g_node_children_foreach (GNode           *node,
 140                                   GTraverseFlags   flags,
 141                                   GNodeForeachFunc func,
 142                                   gpointer         data);
 143 void     g_node_reverse_children (GNode           *node);
 144 guint    g_node_n_children       (GNode           *node);
 145 GNode*   g_node_nth_child        (GNode           *node,
 146                                   guint            n);
 147 GNode*   g_node_last_child       (GNode           *node);
 148 GNode*   g_node_find_child       (GNode           *node,
 149                                   GTraverseFlags   flags,
 150                                   gpointer         data);
 151 gint     g_node_child_position   (GNode           *node,
 152                                   GNode           *child);
 153 gint     g_node_child_index      (GNode           *node,
 154                                   gpointer         data);
 155
 156 GNode*   g_node_first_sibling    (GNode           *node);
 157 GNode*   g_node_last_sibling     (GNode           *node);
 158
 159 #define  g_node_prev_sibling(node)      ((node) ? \
 160                                          ((GNode*) (node))->prev : NULL)
 161 #define  g_node_next_sibling(node)      ((node) ? \
 162                                          ((GNode*) (node))->next : NULL)
 163 #define  g_node_first_child(node)       ((node) ? \
 164                                          ((GNode*) (node))->children : NULL)
 165
 166 G_END_DECLS
 167
 168 #endif /* __G_NODE_H__ */