2 * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library 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.
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 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library 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.
20 /* A Red-Black Tree implementation used specifically by GtkTreeView.
22 #ifndef __GTK_RBTREE_H__
23 #define __GTK_RBTREE_H__
33 GTK_RBNODE_BLACK = 1 << 0,
34 GTK_RBNODE_RED = 1 << 1,
35 GTK_RBNODE_IS_PARENT = 1 << 2,
36 GTK_RBNODE_IS_SELECTED = 1 << 3,
37 GTK_RBNODE_IS_PRELIT = 1 << 4,
38 GTK_RBNODE_INVALID = 1 << 7,
39 GTK_RBNODE_COLUMN_INVALID = 1 << 8,
40 GTK_RBNODE_DESCENDANTS_INVALID = 1 << 9,
41 GTK_RBNODE_NON_COLORS = GTK_RBNODE_IS_PARENT |
42 GTK_RBNODE_IS_SELECTED |
43 GTK_RBNODE_IS_PRELIT |
45 GTK_RBNODE_COLUMN_INVALID |
46 GTK_RBNODE_DESCENDANTS_INVALID
49 typedef struct _GtkRBTree GtkRBTree;
50 typedef struct _GtkRBNode GtkRBNode;
51 typedef struct _GtkRBTreeView GtkRBTreeView;
53 typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree *tree,
61 GtkRBTree *parent_tree;
62 GtkRBNode *parent_node;
73 /* count is the number of nodes beneath us, plus 1 for ourselves.
74 * i.e. node->left->count + node->right->count + 1
77 /* count the number of total nodes beneath us, including nodes
79 * i.e. node->left->count + node->right->count + node->children->root->count + 1
83 /* this is the total of sizes of
84 * node->left, node->right, our own height, and the height
85 * of all trees in ->children, iff children exists because
86 * the thing is expanded.
95 #define GTK_RBNODE_GET_COLOR(node) (node?(((node->flags>K_RBNODE_RED)==GTK_RBNODE_RED)?GTK_RBNODE_RED:GTK_RBNODE_BLACK):GTK_RBNODE_BLACK)
96 #define GTK_RBNODE_SET_COLOR(node,color) if((node->flags&color)!=color)node->flags=node->flags^(GTK_RBNODE_RED|GTK_RBNODE_BLACK)
97 #define GTK_RBNODE_GET_HEIGHT(node) (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
98 #define GTK_RBNODE_SET_FLAG(node, flag) G_STMT_START{ (node->flags|=flag); }G_STMT_END
99 #define GTK_RBNODE_UNSET_FLAG(node, flag) G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
100 #define GTK_RBNODE_FLAG_SET(node, flag) (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
103 GtkRBTree *_gtk_rbtree_new (void);
104 void _gtk_rbtree_free (GtkRBTree *tree);
105 void _gtk_rbtree_remove (GtkRBTree *tree);
106 void _gtk_rbtree_destroy (GtkRBTree *tree);
107 GtkRBNode *_gtk_rbtree_insert_before (GtkRBTree *tree,
111 GtkRBNode *_gtk_rbtree_insert_after (GtkRBTree *tree,
115 void _gtk_rbtree_remove_node (GtkRBTree *tree,
117 void _gtk_rbtree_reorder (GtkRBTree *tree,
120 GtkRBNode *_gtk_rbtree_find_count (GtkRBTree *tree,
122 void _gtk_rbtree_node_set_height (GtkRBTree *tree,
125 void _gtk_rbtree_node_mark_invalid(GtkRBTree *tree,
127 void _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
129 void _gtk_rbtree_column_invalid (GtkRBTree *tree);
130 void _gtk_rbtree_mark_invalid (GtkRBTree *tree);
131 void _gtk_rbtree_set_fixed_height (GtkRBTree *tree,
133 gboolean mark_valid);
134 gint _gtk_rbtree_node_find_offset (GtkRBTree *tree,
136 guint _gtk_rbtree_node_get_index (GtkRBTree *tree,
138 gboolean _gtk_rbtree_find_index (GtkRBTree *tree,
140 GtkRBTree **new_tree,
141 GtkRBNode **new_node);
142 gint _gtk_rbtree_find_offset (GtkRBTree *tree,
144 GtkRBTree **new_tree,
145 GtkRBNode **new_node);
146 void _gtk_rbtree_traverse (GtkRBTree *tree,
149 GtkRBTreeTraverseFunc func,
151 GtkRBNode *_gtk_rbtree_next (GtkRBTree *tree,
153 GtkRBNode *_gtk_rbtree_prev (GtkRBTree *tree,
155 void _gtk_rbtree_next_full (GtkRBTree *tree,
157 GtkRBTree **new_tree,
158 GtkRBNode **new_node);
159 void _gtk_rbtree_prev_full (GtkRBTree *tree,
161 GtkRBTree **new_tree,
162 GtkRBNode **new_node);
164 gint _gtk_rbtree_get_depth (GtkRBTree *tree);
166 /* This func checks the integrity of the tree */
167 #ifdef G_ENABLE_DEBUG
168 void _gtk_rbtree_test (const gchar *where,
170 void _gtk_rbtree_debug_spew (GtkRBTree *tree);
177 #endif /* __GTK_RBTREE_H__ */