gtkrbtree.h 6.83 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/* gtkrbtree.h
 * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

20 21
/* A Red-Black Tree implementation used specifically by GtkTreeView.
 */
22 23 24
#ifndef __GTK_RBTREE_H__
#define __GTK_RBTREE_H__

Matthias Clasen's avatar
Matthias Clasen committed
25 26
#include <glib.h>

27 28 29

G_BEGIN_DECLS

30 31 32 33 34 35 36 37

typedef enum
{
  GTK_RBNODE_BLACK = 1 << 0,
  GTK_RBNODE_RED = 1 << 1,
  GTK_RBNODE_IS_PARENT = 1 << 2,
  GTK_RBNODE_IS_SELECTED = 1 << 3,
  GTK_RBNODE_IS_PRELIT = 1 << 4,
38
  GTK_RBNODE_INVALID = 1 << 7,
Jonathan Blandford's avatar
Jonathan Blandford committed
39 40 41 42 43 44 45 46
  GTK_RBNODE_COLUMN_INVALID = 1 << 8,
  GTK_RBNODE_DESCENDANTS_INVALID = 1 << 9,
  GTK_RBNODE_NON_COLORS = GTK_RBNODE_IS_PARENT |
  			  GTK_RBNODE_IS_SELECTED |
  			  GTK_RBNODE_IS_PRELIT |
                          GTK_RBNODE_INVALID |
                          GTK_RBNODE_COLUMN_INVALID |
                          GTK_RBNODE_DESCENDANTS_INVALID
47 48 49 50 51 52 53
} GtkRBNodeColor;

typedef struct _GtkRBTree GtkRBTree;
typedef struct _GtkRBNode GtkRBNode;
typedef struct _GtkRBTreeView GtkRBTreeView;

typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree  *tree,
54 55
                                       GtkRBNode  *node,
                                       gpointer  data);
56 57 58 59 60 61 62 63 64 65 66

struct _GtkRBTree
{
  GtkRBNode *root;
  GtkRBNode *nil;
  GtkRBTree *parent_tree;
  GtkRBNode *parent_node;
};

struct _GtkRBNode
{
67 68 69 70 71 72 73 74 75 76 77 78 79 80
  guint flags : 14;

  /* We keep track of whether the aggregate count of children plus 1
   * for the node itself comes to an even number.  The parity flag is
   * the total count of children mod 2, where the total count of
   * children gets computed in the same way that the total offset gets
   * computed. i.e. not the same as the "count" field below which
   * doesn't include children. We could replace parity with a
   * full-size int field here, and then take % 2 to get the parity flag,
   * but that would use extra memory.
   */

  guint parity : 1;
  
81 82 83 84
  GtkRBNode *left;
  GtkRBNode *right;
  GtkRBNode *parent;

Havoc Pennington's avatar
Havoc Pennington committed
85 86 87 88
  /* count is the number of nodes beneath us, plus 1 for ourselves.
   * i.e. node->left->count + node->right->count + 1
   */
  gint count;
89
  
Havoc Pennington's avatar
Havoc Pennington committed
90 91 92 93 94
  /* this is the total of sizes of
   * node->left, node->right, our own height, and the height
   * of all trees in ->children, iff children exists because
   * the thing is expanded.
   */
95
  gint offset;
96 97

  /* Child trees */
98 99 100
  GtkRBTree *children;
};

Jonathan Blandford's avatar
Jonathan Blandford committed
101

102 103 104 105 106 107 108 109 110 111 112 113 114 115
#define GTK_RBNODE_GET_COLOR(node)		(node?(((node->flags&GTK_RBNODE_RED)==GTK_RBNODE_RED)?GTK_RBNODE_RED:GTK_RBNODE_BLACK):GTK_RBNODE_BLACK)
#define GTK_RBNODE_SET_COLOR(node,color) 	if((node->flags&color)!=color)node->flags=node->flags^(GTK_RBNODE_RED|GTK_RBNODE_BLACK)
#define GTK_RBNODE_GET_HEIGHT(node) 		(node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
#define GTK_RBNODE_SET_FLAG(node, flag)   	G_STMT_START{ (node->flags|=flag); }G_STMT_END
#define GTK_RBNODE_UNSET_FLAG(node, flag) 	G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
#define GTK_RBNODE_FLAG_SET(node, flag) 	(node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)


GtkRBTree *_gtk_rbtree_new              (void);
void       _gtk_rbtree_free             (GtkRBTree              *tree);
void       _gtk_rbtree_remove           (GtkRBTree              *tree);
void       _gtk_rbtree_destroy          (GtkRBTree              *tree);
GtkRBNode *_gtk_rbtree_insert_before    (GtkRBTree              *tree,
					 GtkRBNode              *node,
Jonathan Blandford's avatar
Jonathan Blandford committed
116 117
					 gint                    height,
					 gboolean                valid);
118 119
GtkRBNode *_gtk_rbtree_insert_after     (GtkRBTree              *tree,
					 GtkRBNode              *node,
Jonathan Blandford's avatar
Jonathan Blandford committed
120 121
					 gint                    height,
					 gboolean                valid);
122 123
void       _gtk_rbtree_remove_node      (GtkRBTree              *tree,
					 GtkRBNode              *node);
124 125 126
void       _gtk_rbtree_reorder          (GtkRBTree              *tree,
					 gint                   *new_order,
					 gint                    length);
127 128 129 130 131
GtkRBNode *_gtk_rbtree_find_count       (GtkRBTree              *tree,
					 gint                    count);
void       _gtk_rbtree_node_set_height  (GtkRBTree              *tree,
					 GtkRBNode              *node,
					 gint                    height);
132 133 134 135
void       _gtk_rbtree_node_mark_invalid(GtkRBTree              *tree,
					 GtkRBNode              *node);
void       _gtk_rbtree_node_mark_valid  (GtkRBTree              *tree,
					 GtkRBNode              *node);
Jonathan Blandford's avatar
Jonathan Blandford committed
136
void       _gtk_rbtree_column_invalid   (GtkRBTree              *tree);
137
void       _gtk_rbtree_mark_invalid     (GtkRBTree              *tree);
138
void       _gtk_rbtree_set_fixed_height (GtkRBTree              *tree,
139 140
					 gint                    height,
					 gboolean                mark_valid);
141 142
gint       _gtk_rbtree_node_find_offset (GtkRBTree              *tree,
					 GtkRBNode              *node);
143 144
gint       _gtk_rbtree_node_find_parity (GtkRBTree              *tree,
					 GtkRBNode              *node);
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
gint       _gtk_rbtree_find_offset      (GtkRBTree              *tree,
					 gint                    offset,
					 GtkRBTree             **new_tree,
					 GtkRBNode             **new_node);
void       _gtk_rbtree_traverse         (GtkRBTree              *tree,
					 GtkRBNode              *node,
					 GTraverseType           order,
					 GtkRBTreeTraverseFunc   func,
					 gpointer                data);
GtkRBNode *_gtk_rbtree_next             (GtkRBTree              *tree,
					 GtkRBNode              *node);
GtkRBNode *_gtk_rbtree_prev             (GtkRBTree              *tree,
					 GtkRBNode              *node);
void       _gtk_rbtree_next_full        (GtkRBTree              *tree,
					 GtkRBNode              *node,
					 GtkRBTree             **new_tree,
					 GtkRBNode             **new_node);
void       _gtk_rbtree_prev_full        (GtkRBTree              *tree,
					 GtkRBNode              *node,
					 GtkRBTree             **new_tree,
					 GtkRBNode             **new_node);

167
gint       _gtk_rbtree_get_depth        (GtkRBTree              *tree);
168

169
/* This func checks the integrity of the tree */
170
#ifdef G_ENABLE_DEBUG  
171 172
void       _gtk_rbtree_test             (const gchar            *where,
                                         GtkRBTree              *tree);
173
void       _gtk_rbtree_debug_spew       (GtkRBTree              *tree);
174
#endif
175

176 177 178

G_END_DECLS

179 180

#endif /* __GTK_RBTREE_H__ */