← Back to branch summary

~ubuntu-branches/ubuntu/utopic/rhythmbox/utopic-proposed

« back to all changes in this revision

Viewing changes to widgets/gtkrbtree.h

Tags: upstream-0.9.2
Import upstream version 0.9.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
widgets/gtkrbtree.h
1
 
/* gtkrbtree.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, write to the
16
 
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17
 
 * Boston, MA 02111-1307, USA.
18
 
 */
19
 
 
20
 
/* A Red-Black Tree implementation used specifically by GtkTreeView.
21
 
 */
22
 
#ifndef __GTK_RBTREE_H__
23
 
#define __GTK_RBTREE_H__
24
 
 
25
 
#ifdef __cplusplus
26
 
extern "C" {
27
 
#endif /* __cplusplus */
28
 
 
29
 
#include <glib.h>
30
 
typedef enum
31
 
{
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 |
47
 
                          GTK_RBNODE_INVALID |
48
 
                          GTK_RBNODE_COLUMN_INVALID |
49
 
                          GTK_RBNODE_DESCENDANTS_INVALID
50
 
} GtkRBNodeColor;
51
 
 
52
 
typedef struct _GtkRBTree GtkRBTree;
53
 
typedef struct _GtkRBNode GtkRBNode;
54
 
typedef struct _GtkRBTreeView GtkRBTreeView;
55
 
 
56
 
typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree  *tree,
57
 
                                       GtkRBNode  *node,
58
 
                                       gpointer  data);
59
 
 
60
 
struct _GtkRBTree
61
 
{
62
 
  GtkRBNode *root;
63
 
  GtkRBNode *nil;
64
 
  GtkRBTree *parent_tree;
65
 
  GtkRBNode *parent_node;
66
 
};
67
 
 
68
 
struct _GtkRBNode
69
 
{
70
 
  guint flags : 14;
71
 
 
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.
80
 
   */
81
 
 
82
 
  guint parity : 1;
83
 
  
84
 
  GtkRBNode *left;
85
 
  GtkRBNode *right;
86
 
  GtkRBNode *parent;
87
 
 
88
 
  /* count is the number of nodes beneath us, plus 1 for ourselves.
89
 
   * i.e. node->left->count + node->right->count + 1
90
 
   */
91
 
  gint count;
92
 
  
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.
97
 
   */
98
 
  gint offset;
99
 
 
100
 
  /* Child trees */
101
 
  GtkRBTree *children;
102
 
};
103
 
 
104
 
 
105
 
#define GTK_RBNODE_GET_COLOR(node)              (node?(((node->flags&GTK_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)
111
 
 
112
 
 
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,
120
 
                                         GtkRBNode              *node,
121
 
                                         gint                    height,
122
 
                                         gboolean                valid);
123
 
GtkRBNode *_gtk_rbtree_insert_after     (GtkRBTree              *tree,
124
 
                                         GtkRBNode              *node,
125
 
                                         gint                    height,
126
 
                                         gboolean                valid);
127
 
void       _gtk_rbtree_remove_node      (GtkRBTree              *tree,
128
 
                                         GtkRBNode              *node);
129
 
void       _gtk_rbtree_reorder          (GtkRBTree              *tree,
130
 
                                         gint                   *new_order,
131
 
                                         gint                    length);
132
 
GtkRBNode *_gtk_rbtree_find_count       (GtkRBTree              *tree,
133
 
                                         gint                    count);
134
 
void       _gtk_rbtree_node_set_height  (GtkRBTree              *tree,
135
 
                                         GtkRBNode              *node,
136
 
                                         gint                    height);
137
 
void       _gtk_rbtree_node_mark_invalid(GtkRBTree              *tree,
138
 
                                         GtkRBNode              *node);
139
 
void       _gtk_rbtree_node_mark_valid  (GtkRBTree              *tree,
140
 
                                         GtkRBNode              *node);
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,
144
 
                                         gint                    height);
145
 
gint       _gtk_rbtree_node_find_offset (GtkRBTree              *tree,
146
 
                                         GtkRBNode              *node);
147
 
gint       _gtk_rbtree_node_find_parity (GtkRBTree              *tree,
148
 
                                         GtkRBNode              *node);
149
 
gint       _gtk_rbtree_find_offset      (GtkRBTree              *tree,
150
 
                                         gint                    offset,
151
 
                                         GtkRBTree             **new_tree,
152
 
                                         GtkRBNode             **new_node);
153
 
void       _gtk_rbtree_traverse         (GtkRBTree              *tree,
154
 
                                         GtkRBNode              *node,
155
 
                                         GTraverseType           order,
156
 
                                         GtkRBTreeTraverseFunc   func,
157
 
                                         gpointer                data);
158
 
GtkRBNode *_gtk_rbtree_next             (GtkRBTree              *tree,
159
 
                                         GtkRBNode              *node);
160
 
GtkRBNode *_gtk_rbtree_prev             (GtkRBTree              *tree,
161
 
                                         GtkRBNode              *node);
162
 
void       _gtk_rbtree_next_full        (GtkRBTree              *tree,
163
 
                                         GtkRBNode              *node,
164
 
                                         GtkRBTree             **new_tree,
165
 
                                         GtkRBNode             **new_node);
166
 
void       _gtk_rbtree_prev_full        (GtkRBTree              *tree,
167
 
                                         GtkRBNode              *node,
168
 
                                         GtkRBTree             **new_tree,
169
 
                                         GtkRBNode             **new_node);
170
 
 
171
 
gint       _gtk_rbtree_get_depth        (GtkRBTree              *tree);
172
 
 
173
 
/* This func checks the integrity of the tree */
174
 
#ifdef G_ENABLE_DEBUG  
175
 
void       _gtk_rbtree_test             (const gchar            *where,
176
 
                                         GtkRBTree              *tree);
177
 
void       _gtk_rbtree_debug_spew       (GtkRBTree              *tree);
178
 
#endif
179
 
 
180
 
#ifdef __cplusplus
181
 
}
182
 
#endif /* __cplusplus */
183
 
 
184
 
#endif /* __GTK_RBTREE_H__ */