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 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__ */