williamr@2: /* GLIB - Library of useful routines for C programming
williamr@2: * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
williamr@2: * Portions copyright (c) 2006 Nokia Corporation. All rights reserved.
williamr@2: *
williamr@2: * This library is free software; you can redistribute it and/or
williamr@2: * modify it under the terms of the GNU Lesser General Public
williamr@2: * License as published by the Free Software Foundation; either
williamr@2: * version 2 of the License, or (at your option) any later version.
williamr@2: *
williamr@2: * This library is distributed in the hope that it will be useful,
williamr@2: * but WITHOUT ANY WARRANTY; without even the implied warranty of
williamr@2: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
williamr@2: * Lesser General Public License for more details.
williamr@2: *
williamr@2: * You should have received a copy of the GNU Lesser General Public
williamr@2: * License along with this library; if not, write to the
williamr@2: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
williamr@2: * Boston, MA 02111-1307, USA.
williamr@2: */
williamr@2:
williamr@2: /*
williamr@2: * Modified by the GLib Team and others 1997-2000. See the AUTHORS
williamr@2: * file for a list of people on the GLib Team. See the ChangeLog
williamr@2: * files for a list of changes. These files are distributed with
williamr@2: * GLib at ftp://ftp.gtk.org/pub/gtk/.
williamr@2: */
williamr@2:
williamr@2: #ifndef __G_NODE_H__
williamr@2: #define __G_NODE_H__
williamr@2:
williamr@2: #include <_ansi.h>
williamr@2: #include <glib/gmem.h>
williamr@2:
williamr@2: G_BEGIN_DECLS
williamr@2:
williamr@2: typedef struct _GNode GNode;
williamr@2:
williamr@2: /* Tree traverse flags */
williamr@2: typedef enum
williamr@2: {
williamr@2: G_TRAVERSE_LEAVES = 1 << 0,
williamr@2: G_TRAVERSE_NON_LEAVES = 1 << 1,
williamr@2: G_TRAVERSE_ALL = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
williamr@2: G_TRAVERSE_MASK = 0x03,
williamr@2: G_TRAVERSE_LEAFS = G_TRAVERSE_LEAVES,
williamr@2: G_TRAVERSE_NON_LEAFS = G_TRAVERSE_NON_LEAVES
williamr@2: } GTraverseFlags;
williamr@2:
williamr@2: /* Tree traverse orders */
williamr@2: typedef enum
williamr@2: {
williamr@2: G_IN_ORDER,
williamr@2: G_PRE_ORDER,
williamr@2: G_POST_ORDER,
williamr@2: G_LEVEL_ORDER
williamr@2: } GTraverseType;
williamr@2:
williamr@2: typedef gboolean (*GNodeTraverseFunc) (GNode *node,
williamr@2: gpointer data);
williamr@2: typedef void (*GNodeForeachFunc) (GNode *node,
williamr@2: gpointer data);
williamr@2: typedef gpointer (*GCopyFunc) (gconstpointer src,
williamr@2: gpointer data);
williamr@2:
williamr@2: /* N-way tree implementation
williamr@2: */
williamr@2: struct _GNode
williamr@2: {
williamr@2: gpointer data;
williamr@2: GNode *next;
williamr@2: GNode *prev;
williamr@2: GNode *parent;
williamr@2: GNode *children;
williamr@2: };
williamr@2:
williamr@2: #define G_NODE_IS_ROOT(node) (((GNode*) (node))->parent == NULL && \
williamr@2: ((GNode*) (node))->prev == NULL && \
williamr@2: ((GNode*) (node))->next == NULL)
williamr@2: #define G_NODE_IS_LEAF(node) (((GNode*) (node))->children == NULL)
williamr@2:
williamr@2: IMPORT_C GNode* g_node_new (gpointer data);
williamr@2: IMPORT_C void g_node_destroy (GNode *root);
williamr@2: IMPORT_C void g_node_unlink (GNode *node);
williamr@2: IMPORT_C GNode* g_node_copy_deep (GNode *node,
williamr@2: GCopyFunc copy_func,
williamr@2: gpointer data);
williamr@2: IMPORT_C GNode* g_node_copy (GNode *node);
williamr@2: IMPORT_C GNode* g_node_insert (GNode *parent,
williamr@2: gint position,
williamr@2: GNode *node);
williamr@2: IMPORT_C GNode* g_node_insert_before (GNode *parent,
williamr@2: GNode *sibling,
williamr@2: GNode *node);
williamr@2: IMPORT_C GNode* g_node_insert_after (GNode *parent,
williamr@2: GNode *sibling,
williamr@2: GNode *node);
williamr@2: IMPORT_C GNode* g_node_prepend (GNode *parent,
williamr@2: GNode *node);
williamr@2: IMPORT_C guint g_node_n_nodes (GNode *root,
williamr@2: GTraverseFlags flags);
williamr@2: IMPORT_C GNode* g_node_get_root (GNode *node);
williamr@2: IMPORT_C gboolean g_node_is_ancestor (GNode *node,
williamr@2: GNode *descendant);
williamr@2: IMPORT_C guint g_node_depth (GNode *node);
williamr@2: IMPORT_C GNode* g_node_find (GNode *root,
williamr@2: GTraverseType order,
williamr@2: GTraverseFlags flags,
williamr@2: gpointer data);
williamr@2:
williamr@2: /* convenience macros */
williamr@2: #define g_node_append(parent, node) \
williamr@2: g_node_insert_before ((parent), NULL, (node))
williamr@2: #define g_node_insert_data(parent, position, data) \
williamr@2: g_node_insert ((parent), (position), g_node_new (data))
williamr@2: #define g_node_insert_data_before(parent, sibling, data) \
williamr@2: g_node_insert_before ((parent), (sibling), g_node_new (data))
williamr@2: #define g_node_prepend_data(parent, data) \
williamr@2: g_node_prepend ((parent), g_node_new (data))
williamr@2: #define g_node_append_data(parent, data) \
williamr@2: g_node_insert_before ((parent), NULL, g_node_new (data))
williamr@2:
williamr@2: /* traversal function, assumes that `node' is root
williamr@2: * (only traverses `node' and its subtree).
williamr@2: * this function is just a high level interface to
williamr@2: * low level traversal functions, optimized for speed.
williamr@2: */
williamr@2: IMPORT_C void g_node_traverse (GNode *root,
williamr@2: GTraverseType order,
williamr@2: GTraverseFlags flags,
williamr@2: gint max_depth,
williamr@2: GNodeTraverseFunc func,
williamr@2: gpointer data);
williamr@2:
williamr@2: /* return the maximum tree height starting with `node', this is an expensive
williamr@2: * operation, since we need to visit all nodes. this could be shortened by
williamr@2: * adding `guint height' to struct _GNode, but then again, this is not very
williamr@2: * often needed, and would make g_node_insert() more time consuming.
williamr@2: */
williamr@2: IMPORT_C guint g_node_max_height (GNode *root);
williamr@2:
williamr@2: IMPORT_C void g_node_children_foreach (GNode *node,
williamr@2: GTraverseFlags flags,
williamr@2: GNodeForeachFunc func,
williamr@2: gpointer data);
williamr@2: IMPORT_C void g_node_reverse_children (GNode *node);
williamr@2: IMPORT_C guint g_node_n_children (GNode *node);
williamr@2: IMPORT_C GNode* g_node_nth_child (GNode *node,
williamr@2: guint n);
williamr@2: IMPORT_C GNode* g_node_last_child (GNode *node);
williamr@2: IMPORT_C GNode* g_node_find_child (GNode *node,
williamr@2: GTraverseFlags flags,
williamr@2: gpointer data);
williamr@2: IMPORT_C gint g_node_child_position (GNode *node,
williamr@2: GNode *child);
williamr@2: IMPORT_C gint g_node_child_index (GNode *node,
williamr@2: gpointer data);
williamr@2:
williamr@2: IMPORT_C GNode* g_node_first_sibling (GNode *node);
williamr@2: IMPORT_C GNode* g_node_last_sibling (GNode *node);
williamr@2:
williamr@2: #define g_node_prev_sibling(node) ((node) ? \
williamr@2: ((GNode*) (node))->prev : NULL)
williamr@2: #define g_node_next_sibling(node) ((node) ? \
williamr@2: ((GNode*) (node))->next : NULL)
williamr@2: #define g_node_first_child(node) ((node) ? \
williamr@2: ((GNode*) (node))->children : NULL)
williamr@2:
williamr@2: #ifndef G_DISABLE_DEPRECATED
williamr@2: IMPORT_C void g_node_push_allocator (gpointer dummy);
williamr@2: IMPORT_C void g_node_pop_allocator (void);
williamr@2: #endif
williamr@2: G_END_DECLS
williamr@2:
williamr@2: #endif /* __G_NODE_H__ */