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