Pileus Git - ~andy/gtk/blob - gtk/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, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 /* A Red-Black Tree implementation used specifically by GtkTreeView.
  19  */
  20 #ifndef __GTK_RBTREE_H__
  21 #define __GTK_RBTREE_H__
  22
  23 #include <glib.h>
  24
  25
  26 G_BEGIN_DECLS
  27
  28
  29 typedef enum
  30 {
  31   GTK_RBNODE_BLACK = 1 << 0,
  32   GTK_RBNODE_RED = 1 << 1,
  33   GTK_RBNODE_IS_PARENT = 1 << 2,
  34   GTK_RBNODE_IS_SELECTED = 1 << 3,
  35   GTK_RBNODE_IS_PRELIT = 1 << 4,
  36   GTK_RBNODE_INVALID = 1 << 7,
  37   GTK_RBNODE_COLUMN_INVALID = 1 << 8,
  38   GTK_RBNODE_DESCENDANTS_INVALID = 1 << 9,
  39   GTK_RBNODE_NON_COLORS = GTK_RBNODE_IS_PARENT |
  40                           GTK_RBNODE_IS_SELECTED |
  41                           GTK_RBNODE_IS_PRELIT |
  42                           GTK_RBNODE_INVALID |
  43                           GTK_RBNODE_COLUMN_INVALID |
  44                           GTK_RBNODE_DESCENDANTS_INVALID
  45 } GtkRBNodeColor;
  46
  47 typedef struct _GtkRBTree GtkRBTree;
  48 typedef struct _GtkRBNode GtkRBNode;
  49 typedef struct _GtkRBTreeView GtkRBTreeView;
  50
  51 typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree  *tree,
  52                                        GtkRBNode  *node,
  53                                        gpointer  data);
  54
  55 struct _GtkRBTree
  56 {
  57   GtkRBNode *root;
  58   GtkRBTree *parent_tree;
  59   GtkRBNode *parent_node;
  60 };
  61
  62 struct _GtkRBNode
  63 {
  64   guint flags : 14;
  65
  66   GtkRBNode *left;
  67   GtkRBNode *right;
  68   GtkRBNode *parent;
  69
  70   /* count is the number of nodes beneath us, plus 1 for ourselves.
  71    * i.e. node->left->count + node->right->count + 1
  72    */
  73   gint count;
  74   /* count the number of total nodes beneath us, including nodes
  75    * of children trees.
  76    * i.e. node->left->count + node->right->count + node->children->root->count + 1
  77    */
  78   guint total_count;
  79
  80   /* this is the total of sizes of
  81    * node->left, node->right, our own height, and the height
  82    * of all trees in ->children, iff children exists because
  83    * the thing is expanded.
  84    */
  85   gint offset;
  86
  87   /* Child trees */
  88   GtkRBTree *children;
  89 };
  90
  91
  92 #define GTK_RBNODE_GET_COLOR(node)              (node?(((node->flags&GTK_RBNODE_RED)==GTK_RBNODE_RED)?GTK_RBNODE_RED:GTK_RBNODE_BLACK):GTK_RBNODE_BLACK)
  93 #define GTK_RBNODE_SET_COLOR(node,color)        if((node->flags&color)!=color)node->flags=node->flags^(GTK_RBNODE_RED|GTK_RBNODE_BLACK)
  94 #define GTK_RBNODE_GET_HEIGHT(node)             (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
  95 #define GTK_RBNODE_SET_FLAG(node, flag)         G_STMT_START{ (node->flags|=flag); }G_STMT_END
  96 #define GTK_RBNODE_UNSET_FLAG(node, flag)       G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
  97 #define GTK_RBNODE_FLAG_SET(node, flag)         (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
  98
  99
 100 GtkRBTree *_gtk_rbtree_new              (void);
 101 void       _gtk_rbtree_free             (GtkRBTree              *tree);
 102 void       _gtk_rbtree_remove           (GtkRBTree              *tree);
 103 void       _gtk_rbtree_destroy          (GtkRBTree              *tree);
 104 GtkRBNode *_gtk_rbtree_insert_before    (GtkRBTree              *tree,
 105                                          GtkRBNode              *node,
 106                                          gint                    height,
 107                                          gboolean                valid);
 108 GtkRBNode *_gtk_rbtree_insert_after     (GtkRBTree              *tree,
 109                                          GtkRBNode              *node,
 110                                          gint                    height,
 111                                          gboolean                valid);
 112 void       _gtk_rbtree_remove_node      (GtkRBTree              *tree,
 113                                          GtkRBNode              *node);
 114 gboolean   _gtk_rbtree_is_nil           (GtkRBNode              *node);
 115 void       _gtk_rbtree_reorder          (GtkRBTree              *tree,
 116                                          gint                   *new_order,
 117                                          gint                    length);
 118 gboolean   _gtk_rbtree_contains         (GtkRBTree              *tree,
 119                                          GtkRBTree              *potential_child);
 120 GtkRBNode *_gtk_rbtree_find_count       (GtkRBTree              *tree,
 121                                          gint                    count);
 122 void       _gtk_rbtree_node_set_height  (GtkRBTree              *tree,
 123                                          GtkRBNode              *node,
 124                                          gint                    height);
 125 void       _gtk_rbtree_node_mark_invalid(GtkRBTree              *tree,
 126                                          GtkRBNode              *node);
 127 void       _gtk_rbtree_node_mark_valid  (GtkRBTree              *tree,
 128                                          GtkRBNode              *node);
 129 void       _gtk_rbtree_column_invalid   (GtkRBTree              *tree);
 130 void       _gtk_rbtree_mark_invalid     (GtkRBTree              *tree);
 131 void       _gtk_rbtree_set_fixed_height (GtkRBTree              *tree,
 132                                          gint                    height,
 133                                          gboolean                mark_valid);
 134 gint       _gtk_rbtree_node_find_offset (GtkRBTree              *tree,
 135                                          GtkRBNode              *node);
 136 guint      _gtk_rbtree_node_get_index   (GtkRBTree              *tree,
 137                                          GtkRBNode              *node);
 138 gboolean   _gtk_rbtree_find_index       (GtkRBTree              *tree,
 139                                          guint                   index,
 140                                          GtkRBTree             **new_tree,
 141                                          GtkRBNode             **new_node);
 142 gint       _gtk_rbtree_find_offset      (GtkRBTree              *tree,
 143                                          gint                    offset,
 144                                          GtkRBTree             **new_tree,
 145                                          GtkRBNode             **new_node);
 146 void       _gtk_rbtree_traverse         (GtkRBTree              *tree,
 147                                          GtkRBNode              *node,
 148                                          GTraverseType           order,
 149                                          GtkRBTreeTraverseFunc   func,
 150                                          gpointer                data);
 151 GtkRBNode *_gtk_rbtree_first            (GtkRBTree              *tree);
 152 GtkRBNode *_gtk_rbtree_next             (GtkRBTree              *tree,
 153                                          GtkRBNode              *node);
 154 GtkRBNode *_gtk_rbtree_prev             (GtkRBTree              *tree,
 155                                          GtkRBNode              *node);
 156 void       _gtk_rbtree_next_full        (GtkRBTree              *tree,
 157                                          GtkRBNode              *node,
 158                                          GtkRBTree             **new_tree,
 159                                          GtkRBNode             **new_node);
 160 void       _gtk_rbtree_prev_full        (GtkRBTree              *tree,
 161                                          GtkRBNode              *node,
 162                                          GtkRBTree             **new_tree,
 163                                          GtkRBNode             **new_node);
 164
 165 gint       _gtk_rbtree_get_depth        (GtkRBTree              *tree);
 166
 167
 168 G_END_DECLS
 169
 170
 171 #endif /* __GTK_RBTREE_H__ */