Ardour  9.0-pre0-582-g084a23a80d
gtkrbtree.h
Go to the documentation of this file.
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 #include <glib.h>
26 
27 
28 G_BEGIN_DECLS
29 
30 
31 typedef enum
32 {
33  GTK_RBNODE_BLACK = 1 << 0,
34  GTK_RBNODE_RED = 1 << 1,
52 
53 typedef struct _GtkRBTree GtkRBTree;
54 typedef struct _GtkRBNode GtkRBNode;
55 typedef struct _GtkRBTreeView GtkRBTreeView;
56 
57 typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree *tree,
58  GtkRBNode *node,
59  gpointer data);
60 
61 struct _GtkRBTree
62 {
67 };
68 
69 struct _GtkRBNode
70 {
71  guint flags : 14;
72 
73  /* We keep track of whether the aggregate count of children plus 1
74  * for the node itself comes to an even number. The parity flag is
75  * the total count of children mod 2, where the total count of
76  * children gets computed in the same way that the total offset gets
77  * computed. i.e. not the same as the "count" field below which
78  * doesn't include children. We could replace parity with a
79  * full-size int field here, and then take % 2 to get the parity flag,
80  * but that would use extra memory.
81  */
82 
83  guint parity : 1;
84 
88 
89  /* count is the number of nodes beneath us, plus 1 for ourselves.
90  * i.e. node->left->count + node->right->count + 1
91  */
92  gint count;
93 
94  /* this is the total of sizes of
95  * node->left, node->right, our own height, and the height
96  * of all trees in ->children, iff children exists because
97  * the thing is expanded.
98  */
99  gint offset;
100 
101  /* Child trees */
103 };
104 
105 
106 #define GTK_RBNODE_GET_COLOR(node) (node?(((node->flags&GTK_RBNODE_RED)==GTK_RBNODE_RED)?GTK_RBNODE_RED:GTK_RBNODE_BLACK):GTK_RBNODE_BLACK)
107 #define GTK_RBNODE_SET_COLOR(node,color) if((node->flags&color)!=color)node->flags=node->flags^(GTK_RBNODE_RED|GTK_RBNODE_BLACK)
108 #define GTK_RBNODE_GET_HEIGHT(node) (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
109 #define GTK_RBNODE_SET_FLAG(node, flag) G_STMT_START{ (node->flags|=flag); }G_STMT_END
110 #define GTK_RBNODE_UNSET_FLAG(node, flag) G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
111 #define GTK_RBNODE_FLAG_SET(node, flag) (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
112 
113 
119  GtkRBNode *node,
120  gint height,
121  gboolean valid);
123  GtkRBNode *node,
124  gint height,
125  gboolean valid);
127  GtkRBNode *node);
129  gint *new_order,
130  gint length);
132  gint count);
134  GtkRBNode *node,
135  gint height);
137  GtkRBNode *node);
139  GtkRBNode *node);
143  gint height,
144  gboolean mark_valid);
146  GtkRBNode *node);
148  GtkRBNode *node);
150  gint offset,
151  GtkRBTree **new_tree,
152  GtkRBNode **new_node);
154  GtkRBNode *node,
155  GTraverseType order,
157  gpointer data);
159  GtkRBNode *node);
161  GtkRBNode *node);
163  GtkRBNode *node,
164  GtkRBTree **new_tree,
165  GtkRBNode **new_node);
167  GtkRBNode *node,
168  GtkRBTree **new_tree,
169  GtkRBNode **new_node);
170 
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 
181 G_END_DECLS
182 
183 
184 #endif /* __GTK_RBTREE_H__ */
GtkRBNode * _gtk_rbtree_prev(GtkRBTree *tree, GtkRBNode *node)
void _gtk_rbtree_traverse(GtkRBTree *tree, GtkRBNode *node, GTraverseType order, GtkRBTreeTraverseFunc func, gpointer data)
void _gtk_rbtree_column_invalid(GtkRBTree *tree)
GtkRBNode * _gtk_rbtree_insert_after(GtkRBTree *tree, GtkRBNode *node, gint height, gboolean valid)
gint _gtk_rbtree_node_find_parity(GtkRBTree *tree, GtkRBNode *node)
void _gtk_rbtree_mark_invalid(GtkRBTree *tree)
void _gtk_rbtree_node_mark_valid(GtkRBTree *tree, GtkRBNode *node)
void _gtk_rbtree_prev_full(GtkRBTree *tree, GtkRBNode *node, GtkRBTree **new_tree, GtkRBNode **new_node)
void _gtk_rbtree_free(GtkRBTree *tree)
void _gtk_rbtree_set_fixed_height(GtkRBTree *tree, gint height, gboolean mark_valid)
gint _gtk_rbtree_node_find_offset(GtkRBTree *tree, GtkRBNode *node)
gint _gtk_rbtree_find_offset(GtkRBTree *tree, gint offset, GtkRBTree **new_tree, GtkRBNode **new_node)
GtkRBTree * _gtk_rbtree_new(void)
struct _GtkRBTreeView GtkRBTreeView
Definition: gtkrbtree.h:55
void _gtk_rbtree_reorder(GtkRBTree *tree, gint *new_order, gint length)
void _gtk_rbtree_remove(GtkRBTree *tree)
GtkRBNode * _gtk_rbtree_insert_before(GtkRBTree *tree, GtkRBNode *node, gint height, gboolean valid)
gint _gtk_rbtree_get_depth(GtkRBTree *tree)
void _gtk_rbtree_next_full(GtkRBTree *tree, GtkRBNode *node, GtkRBTree **new_tree, GtkRBNode **new_node)
void _gtk_rbtree_destroy(GtkRBTree *tree)
void _gtk_rbtree_remove_node(GtkRBTree *tree, GtkRBNode *node)
void(* GtkRBTreeTraverseFunc)(GtkRBTree *tree, GtkRBNode *node, gpointer data)
Definition: gtkrbtree.h:57
GtkRBNode * _gtk_rbtree_find_count(GtkRBTree *tree, gint count)
GtkRBNodeColor
Definition: gtkrbtree.h:32
@ GTK_RBNODE_IS_SEMI_EXPANDED
Definition: gtkrbtree.h:39
@ GTK_RBNODE_DESCENDANTS_INVALID
Definition: gtkrbtree.h:42
@ GTK_RBNODE_BLACK
Definition: gtkrbtree.h:33
@ GTK_RBNODE_IS_PARENT
Definition: gtkrbtree.h:35
@ GTK_RBNODE_IS_SELECTED
Definition: gtkrbtree.h:36
@ GTK_RBNODE_IS_PRELIT
Definition: gtkrbtree.h:37
@ GTK_RBNODE_INVALID
Definition: gtkrbtree.h:40
@ GTK_RBNODE_NON_COLORS
Definition: gtkrbtree.h:43
@ GTK_RBNODE_COLUMN_INVALID
Definition: gtkrbtree.h:41
@ GTK_RBNODE_IS_SEMI_COLLAPSED
Definition: gtkrbtree.h:38
@ GTK_RBNODE_RED
Definition: gtkrbtree.h:34
void _gtk_rbtree_node_mark_invalid(GtkRBTree *tree, GtkRBNode *node)
void _gtk_rbtree_node_set_height(GtkRBTree *tree, GtkRBNode *node, gint height)
GtkRBNode * _gtk_rbtree_next(GtkRBTree *tree, GtkRBNode *node)
PBD::PropertyDescriptor< uint32_t > order
PBD::PropertyDescriptor< timecnt_t > length
GtkRBNode * right
Definition: gtkrbtree.h:86
gint offset
Definition: gtkrbtree.h:99
gint count
Definition: gtkrbtree.h:92
GtkRBTree * children
Definition: gtkrbtree.h:102
GtkRBNode * left
Definition: gtkrbtree.h:85
guint flags
Definition: gtkrbtree.h:71
guint parity
Definition: gtkrbtree.h:83
GtkRBNode * parent
Definition: gtkrbtree.h:87
GtkRBTree * parent_tree
Definition: gtkrbtree.h:65
GtkRBNode * root
Definition: gtkrbtree.h:63
GtkRBNode * nil
Definition: gtkrbtree.h:64
GtkRBNode * parent_node
Definition: gtkrbtree.h:66
gint height
Definition: xcursors.h:1