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