ltt/branches/poly/lttv/modules/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__ */