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 | |
26 | G_BEGIN_DECLS |
27 | |
28 | |
29 | typedef 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 | |
47 | typedef struct _GtkTreeRBTree GtkTreeRBTree; |
48 | typedef struct _GtkTreeRBNode GtkTreeRBNode; |
49 | typedef struct _GtkTreeRBTreeView GtkTreeRBTreeView; |
50 | |
51 | typedef void (*GtkTreeRBTreeTraverseFunc) (GtkTreeRBTree *tree, |
52 | GtkTreeRBNode *node, |
53 | gpointer data); |
54 | |
55 | struct _GtkTreeRBTree |
56 | { |
57 | GtkTreeRBNode *root; |
58 | GtkTreeRBTree *parent_tree; |
59 | GtkTreeRBNode *parent_node; |
60 | }; |
61 | |
62 | struct _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>K_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 | |
101 | GtkTreeRBTree * gtk_tree_rbtree_new (void); |
102 | void gtk_tree_rbtree_free (GtkTreeRBTree *tree); |
103 | void gtk_tree_rbtree_remove (GtkTreeRBTree *tree); |
104 | void gtk_tree_rbtree_destroy (GtkTreeRBTree *tree); |
105 | GtkTreeRBNode * gtk_tree_rbtree_insert_before (GtkTreeRBTree *tree, |
106 | GtkTreeRBNode *node, |
107 | int height, |
108 | gboolean valid); |
109 | GtkTreeRBNode * gtk_tree_rbtree_insert_after (GtkTreeRBTree *tree, |
110 | GtkTreeRBNode *node, |
111 | int height, |
112 | gboolean valid); |
113 | void gtk_tree_rbtree_remove_node (GtkTreeRBTree *tree, |
114 | GtkTreeRBNode *node); |
115 | gboolean gtk_tree_rbtree_is_nil (GtkTreeRBNode *node); |
116 | void gtk_tree_rbtree_reorder (GtkTreeRBTree *tree, |
117 | int *new_order, |
118 | int length); |
119 | gboolean gtk_tree_rbtree_contains (GtkTreeRBTree *tree, |
120 | GtkTreeRBTree *potential_child); |
121 | GtkTreeRBNode * gtk_tree_rbtree_find_count (GtkTreeRBTree *tree, |
122 | int count); |
123 | void gtk_tree_rbtree_node_set_height (GtkTreeRBTree *tree, |
124 | GtkTreeRBNode *node, |
125 | int height); |
126 | void gtk_tree_rbtree_node_mark_invalid (GtkTreeRBTree *tree, |
127 | GtkTreeRBNode *node); |
128 | void gtk_tree_rbtree_node_mark_valid (GtkTreeRBTree *tree, |
129 | GtkTreeRBNode *node); |
130 | void gtk_tree_rbtree_column_invalid (GtkTreeRBTree *tree); |
131 | void gtk_tree_rbtree_mark_invalid (GtkTreeRBTree *tree); |
132 | void gtk_tree_rbtree_set_fixed_height (GtkTreeRBTree *tree, |
133 | int height, |
134 | gboolean mark_valid); |
135 | int gtk_tree_rbtree_node_find_offset (GtkTreeRBTree *tree, |
136 | GtkTreeRBNode *node); |
137 | guint gtk_tree_rbtree_node_get_index (GtkTreeRBTree *tree, |
138 | GtkTreeRBNode *node); |
139 | gboolean gtk_tree_rbtree_find_index (GtkTreeRBTree *tree, |
140 | guint index, |
141 | GtkTreeRBTree **new_tree, |
142 | GtkTreeRBNode **new_node); |
143 | int gtk_tree_rbtree_find_offset (GtkTreeRBTree *tree, |
144 | int offset, |
145 | GtkTreeRBTree **new_tree, |
146 | GtkTreeRBNode **new_node); |
147 | void gtk_tree_rbtree_traverse (GtkTreeRBTree *tree, |
148 | GtkTreeRBNode *node, |
149 | GTraverseType order, |
150 | GtkTreeRBTreeTraverseFunc func, |
151 | gpointer data); |
152 | GtkTreeRBNode * gtk_tree_rbtree_first (GtkTreeRBTree *tree); |
153 | GtkTreeRBNode * gtk_tree_rbtree_next (GtkTreeRBTree *tree, |
154 | GtkTreeRBNode *node); |
155 | GtkTreeRBNode * gtk_tree_rbtree_prev (GtkTreeRBTree *tree, |
156 | GtkTreeRBNode *node); |
157 | void gtk_tree_rbtree_next_full (GtkTreeRBTree *tree, |
158 | GtkTreeRBNode *node, |
159 | GtkTreeRBTree **new_tree, |
160 | GtkTreeRBNode **new_node); |
161 | void gtk_tree_rbtree_prev_full (GtkTreeRBTree *tree, |
162 | GtkTreeRBNode *node, |
163 | GtkTreeRBTree **new_tree, |
164 | GtkTreeRBNode **new_node); |
165 | |
166 | int gtk_tree_rbtree_get_depth (GtkTreeRBTree *tree); |
167 | |
168 | |
169 | G_END_DECLS |
170 | |
171 | |
172 | #endif /* __GTK_TREE_RBTREE_PRIVATE_H__ */ |
173 | |