1/* gtkrbtreeprivate.h
2 * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
3 *
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.
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 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18/* A Red-Black Tree implementation used specifically by GtkTreeView.
19 */
20#ifndef __GTK_TREE_RBTREE_PRIVATE_H__
21#define __GTK_TREE_RBTREE_PRIVATE_H__
22
23#include <glib.h>
24
25
26G_BEGIN_DECLS
27
28
29typedef enum
30{
31 GTK_TREE_RBNODE_BLACK = 1 << 0,
32 GTK_TREE_RBNODE_RED = 1 << 1,
33 GTK_TREE_RBNODE_IS_PARENT = 1 << 2,
34 GTK_TREE_RBNODE_IS_SELECTED = 1 << 3,
35 GTK_TREE_RBNODE_IS_PRELIT = 1 << 4,
36 GTK_TREE_RBNODE_INVALID = 1 << 7,
37 GTK_TREE_RBNODE_COLUMN_INVALID = 1 << 8,
38 GTK_TREE_RBNODE_DESCENDANTS_INVALID = 1 << 9,
39 GTK_TREE_RBNODE_NON_COLORS = GTK_TREE_RBNODE_IS_PARENT |
40 GTK_TREE_RBNODE_IS_SELECTED |
41 GTK_TREE_RBNODE_IS_PRELIT |
42 GTK_TREE_RBNODE_INVALID |
43 GTK_TREE_RBNODE_COLUMN_INVALID |
44 GTK_TREE_RBNODE_DESCENDANTS_INVALID
45} GtkTreeRBNodeColor;
46
47typedef struct _GtkTreeRBTree GtkTreeRBTree;
48typedef struct _GtkTreeRBNode GtkTreeRBNode;
49typedef struct _GtkTreeRBTreeView GtkTreeRBTreeView;
50
51typedef void (*GtkTreeRBTreeTraverseFunc) (GtkTreeRBTree *tree,
52 GtkTreeRBNode *node,
53 gpointer data);
54
55struct _GtkTreeRBTree
56{
57 GtkTreeRBNode *root;
58 GtkTreeRBTree *parent_tree;
59 GtkTreeRBNode *parent_node;
60};
61
62struct _GtkTreeRBNode
63{
64 guint flags : 14;
65
66 /* count is the number of nodes beneath us, plus 1 for ourselves.
67 * i.e. node->left->count + node->right->count + 1
68 */
69 int count;
70
71 GtkTreeRBNode *left;
72 GtkTreeRBNode *right;
73 GtkTreeRBNode *parent;
74
75 /* count the number of total nodes beneath us, including nodes
76 * of children trees.
77 * i.e. node->left->count + node->right->count + node->children->root->count + 1
78 */
79 guint total_count;
80
81 /* this is the total of sizes of
82 * node->left, node->right, our own height, and the height
83 * of all trees in ->children, iff children exists because
84 * the thing is expanded.
85 */
86 int offset;
87
88 /* Child trees */
89 GtkTreeRBTree *children;
90};
91
92
93#define GTK_TREE_RBNODE_GET_COLOR(node) (node?(((node->flags&GTK_TREE_RBNODE_RED)==GTK_TREE_RBNODE_RED)?GTK_TREE_RBNODE_RED:GTK_TREE_RBNODE_BLACK):GTK_TREE_RBNODE_BLACK)
94#define GTK_TREE_RBNODE_SET_COLOR(node,color) if((node->flags&color)!=color)node->flags=node->flags^(GTK_TREE_RBNODE_RED|GTK_TREE_RBNODE_BLACK)
95#define GTK_TREE_RBNODE_GET_HEIGHT(node) (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
96#define GTK_TREE_RBNODE_SET_FLAG(node, flag) G_STMT_START{ (node->flags|=flag); }G_STMT_END
97#define GTK_TREE_RBNODE_UNSET_FLAG(node, flag) G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
98#define GTK_TREE_RBNODE_FLAG_SET(node, flag) (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
99
100
101GtkTreeRBTree * gtk_tree_rbtree_new (void);
102void gtk_tree_rbtree_free (GtkTreeRBTree *tree);
103void gtk_tree_rbtree_remove (GtkTreeRBTree *tree);
104void gtk_tree_rbtree_destroy (GtkTreeRBTree *tree);
105GtkTreeRBNode * gtk_tree_rbtree_insert_before (GtkTreeRBTree *tree,
106 GtkTreeRBNode *node,
107 int height,
108 gboolean valid);
109GtkTreeRBNode * gtk_tree_rbtree_insert_after (GtkTreeRBTree *tree,
110 GtkTreeRBNode *node,
111 int height,
112 gboolean valid);
113void gtk_tree_rbtree_remove_node (GtkTreeRBTree *tree,
114 GtkTreeRBNode *node);
115gboolean gtk_tree_rbtree_is_nil (GtkTreeRBNode *node);
116void gtk_tree_rbtree_reorder (GtkTreeRBTree *tree,
117 int *new_order,
118 int length);
119gboolean gtk_tree_rbtree_contains (GtkTreeRBTree *tree,
120 GtkTreeRBTree *potential_child);
121GtkTreeRBNode * gtk_tree_rbtree_find_count (GtkTreeRBTree *tree,
122 int count);
123void gtk_tree_rbtree_node_set_height (GtkTreeRBTree *tree,
124 GtkTreeRBNode *node,
125 int height);
126void gtk_tree_rbtree_node_mark_invalid (GtkTreeRBTree *tree,
127 GtkTreeRBNode *node);
128void gtk_tree_rbtree_node_mark_valid (GtkTreeRBTree *tree,
129 GtkTreeRBNode *node);
130void gtk_tree_rbtree_column_invalid (GtkTreeRBTree *tree);
131void gtk_tree_rbtree_mark_invalid (GtkTreeRBTree *tree);
132void gtk_tree_rbtree_set_fixed_height (GtkTreeRBTree *tree,
133 int height,
134 gboolean mark_valid);
135int gtk_tree_rbtree_node_find_offset (GtkTreeRBTree *tree,
136 GtkTreeRBNode *node);
137guint gtk_tree_rbtree_node_get_index (GtkTreeRBTree *tree,
138 GtkTreeRBNode *node);
139gboolean gtk_tree_rbtree_find_index (GtkTreeRBTree *tree,
140 guint index,
141 GtkTreeRBTree **new_tree,
142 GtkTreeRBNode **new_node);
143int gtk_tree_rbtree_find_offset (GtkTreeRBTree *tree,
144 int offset,
145 GtkTreeRBTree **new_tree,
146 GtkTreeRBNode **new_node);
147void gtk_tree_rbtree_traverse (GtkTreeRBTree *tree,
148 GtkTreeRBNode *node,
149 GTraverseType order,
150 GtkTreeRBTreeTraverseFunc func,
151 gpointer data);
152GtkTreeRBNode * gtk_tree_rbtree_first (GtkTreeRBTree *tree);
153GtkTreeRBNode * gtk_tree_rbtree_next (GtkTreeRBTree *tree,
154 GtkTreeRBNode *node);
155GtkTreeRBNode * gtk_tree_rbtree_prev (GtkTreeRBTree *tree,
156 GtkTreeRBNode *node);
157void gtk_tree_rbtree_next_full (GtkTreeRBTree *tree,
158 GtkTreeRBNode *node,
159 GtkTreeRBTree **new_tree,
160 GtkTreeRBNode **new_node);
161void gtk_tree_rbtree_prev_full (GtkTreeRBTree *tree,
162 GtkTreeRBNode *node,
163 GtkTreeRBTree **new_tree,
164 GtkTreeRBNode **new_node);
165
166int gtk_tree_rbtree_get_depth (GtkTreeRBTree *tree);
167
168
169G_END_DECLS
170
171
172#endif /* __GTK_TREE_RBTREE_PRIVATE_H__ */
173

source code of gtk/gtk/gtktreerbtreeprivate.h