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__
27 #endif /* __cplusplus */
32 GTK_RBNODE_BLACK
= 1 << 0,
33 GTK_RBNODE_RED
= 1 << 1,
34 GTK_RBNODE_IS_PARENT
= 1 << 2,
35 GTK_RBNODE_IS_SELECTED
= 1 << 3,
36 GTK_RBNODE_IS_PRELIT
= 1 << 4,
37 GTK_RBNODE_IS_SEMI_COLLAPSED
= 1 << 5,
38 GTK_RBNODE_IS_SEMI_EXPANDED
= 1 << 6,
39 GTK_RBNODE_INVALID
= 1 << 7,
40 GTK_RBNODE_COLUMN_INVALID
= 1 << 8,
41 GTK_RBNODE_DESCENDANTS_INVALID
= 1 << 9,
42 GTK_RBNODE_NON_COLORS
= GTK_RBNODE_IS_PARENT
|
43 GTK_RBNODE_IS_SELECTED
|
44 GTK_RBNODE_IS_PRELIT
|
45 GTK_RBNODE_IS_SEMI_COLLAPSED
|
46 GTK_RBNODE_IS_SEMI_EXPANDED
|
48 GTK_RBNODE_COLUMN_INVALID
|
49 GTK_RBNODE_DESCENDANTS_INVALID
52 typedef struct _GtkRBTree GtkRBTree
;
53 typedef struct _GtkRBNode GtkRBNode
;
54 typedef struct _GtkRBTreeView GtkRBTreeView
;
56 typedef void (*GtkRBTreeTraverseFunc
) (GtkRBTree
*tree
,
64 GtkRBTree
*parent_tree
;
65 GtkRBNode
*parent_node
;
72 /* We keep track of whether the aggregate count of children plus 1
73 * for the node itself comes to an even number. The parity flag is
74 * the total count of children mod 2, where the total count of
75 * children gets computed in the same way that the total offset gets
76 * computed. i.e. not the same as the "count" field below which
77 * doesn't include children. We could replace parity with a
78 * full-size int field here, and then take % 2 to get the parity flag,
79 * but that would use extra memory.
88 /* count is the number of nodes beneath us, plus 1 for ourselves.
89 * i.e. node->left->count + node->right->count + 1
93 /* this is the total of sizes of
94 * node->left, node->right, our own height, and the height
95 * of all trees in ->children, iff children exists because
96 * the thing is expanded.
105 #define GTK_RBNODE_GET_COLOR(node) (node?(((node->flags>K_RBNODE_RED)==GTK_RBNODE_RED)?GTK_RBNODE_RED:GTK_RBNODE_BLACK):GTK_RBNODE_BLACK)
106 #define GTK_RBNODE_SET_COLOR(node,color) if((node->flags&color)!=color)node->flags=node->flags^(GTK_RBNODE_RED|GTK_RBNODE_BLACK)
107 #define GTK_RBNODE_GET_HEIGHT(node) (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
108 #define GTK_RBNODE_SET_FLAG(node, flag) G_STMT_START{ (node->flags|=flag); }G_STMT_END
109 #define GTK_RBNODE_UNSET_FLAG(node, flag) G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
110 #define GTK_RBNODE_FLAG_SET(node, flag) (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
113 void _gtk_rbtree_push_allocator (GAllocator
*allocator
);
114 void _gtk_rbtree_pop_allocator (void);
115 GtkRBTree
*_gtk_rbtree_new (void);
116 void _gtk_rbtree_free (GtkRBTree
*tree
);
117 void _gtk_rbtree_remove (GtkRBTree
*tree
);
118 void _gtk_rbtree_destroy (GtkRBTree
*tree
);
119 GtkRBNode
*_gtk_rbtree_insert_before (GtkRBTree
*tree
,
123 GtkRBNode
*_gtk_rbtree_insert_after (GtkRBTree
*tree
,
127 void _gtk_rbtree_remove_node (GtkRBTree
*tree
,
129 void _gtk_rbtree_reorder (GtkRBTree
*tree
,
132 GtkRBNode
*_gtk_rbtree_find_count (GtkRBTree
*tree
,
134 void _gtk_rbtree_node_set_height (GtkRBTree
*tree
,
137 void _gtk_rbtree_node_mark_invalid(GtkRBTree
*tree
,
139 void _gtk_rbtree_node_mark_valid (GtkRBTree
*tree
,
141 void _gtk_rbtree_column_invalid (GtkRBTree
*tree
);
142 void _gtk_rbtree_mark_invalid (GtkRBTree
*tree
);
143 void _gtk_rbtree_set_fixed_height (GtkRBTree
*tree
,
145 gint
_gtk_rbtree_node_find_offset (GtkRBTree
*tree
,
147 gint
_gtk_rbtree_node_find_parity (GtkRBTree
*tree
,
149 gint
_gtk_rbtree_find_offset (GtkRBTree
*tree
,
151 GtkRBTree
**new_tree
,
152 GtkRBNode
**new_node
);
153 void _gtk_rbtree_traverse (GtkRBTree
*tree
,
156 GtkRBTreeTraverseFunc func
,
158 GtkRBNode
*_gtk_rbtree_next (GtkRBTree
*tree
,
160 GtkRBNode
*_gtk_rbtree_prev (GtkRBTree
*tree
,
162 void _gtk_rbtree_next_full (GtkRBTree
*tree
,
164 GtkRBTree
**new_tree
,
165 GtkRBNode
**new_node
);
166 void _gtk_rbtree_prev_full (GtkRBTree
*tree
,
168 GtkRBTree
**new_tree
,
169 GtkRBNode
**new_node
);
171 gint
_gtk_rbtree_get_depth (GtkRBTree
*tree
);
173 /* This func checks the integrity of the tree */
174 #ifdef G_ENABLE_DEBUG
175 void _gtk_rbtree_test (const gchar
*where
,
177 void _gtk_rbtree_debug_spew (GtkRBTree
*tree
);
182 #endif /* __cplusplus */
184 #endif /* __GTK_RBTREE_H__ */