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, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #ifndef __GTK_RBTREE_H__
  21 #define __GTK_RBTREE_H__
  22
  23 #ifdef __cplusplus
  24 extern "C" {
  25 #endif /* __cplusplus */
  26
  27 #include <glib.h>
  28 typedef enum
  29 {
  30   GTK_RBNODE_BLACK = 1 << 0,
  31   GTK_RBNODE_RED = 1 << 1,
  32   GTK_RBNODE_IS_PARENT = 1 << 2,
  33   GTK_RBNODE_IS_SELECTED = 1 << 3,
  34   GTK_RBNODE_IS_PRELIT = 1 << 4,
  35   GTK_RBNODE_IS_VIEW = 1 << 5
  36 } GtkRBNodeColor;
  37
  38 typedef struct _GtkRBTree GtkRBTree;
  39 typedef struct _GtkRBNode GtkRBNode;
  40 typedef struct _GtkRBTreeView GtkRBTreeView;
  41
  42 typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree  *tree,
  43                                        GtkRBNode  *node,
  44                                        gpointer  data);
  45
  46 struct _GtkRBTree
  47 {
  48   GtkRBNode *root;
  49   GtkRBNode *nil;
  50   GtkRBTree *parent_tree;
  51   GtkRBNode *parent_node;
  52 };
  53
  54 struct _GtkRBNode
  55 {
  56   guint flags;
  57   GtkRBNode *left;
  58   GtkRBNode *right;
  59   GtkRBNode *parent;
  60   gint count;  /* aggregate number of children we have */
  61   gint offset; /* aggregate of the heights of all our children */
  62   GtkRBTree *children;
  63 };
  64
  65 struct _GtkRBNodeView
  66 {
  67   GtkRBNode parent;
  68   gint offset;
  69   GtkRBTree *children;
  70 };
  71
  72 #define GTK_RBNODE_GET_COLOR(node)              (node?(((node->flags&GTK_RBNODE_RED)==GTK_RBNODE_RED)?GTK_RBNODE_RED:GTK_RBNODE_BLACK):GTK_RBNODE_BLACK)
  73 #define GTK_RBNODE_SET_COLOR(node,color)        if((node->flags&color)!=color)node->flags=node->flags^(GTK_RBNODE_RED|GTK_RBNODE_BLACK)
  74 #define GTK_RBNODE_GET_HEIGHT(node)             (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
  75 #define GTK_RBNODE_SET_FLAG(node, flag)         G_STMT_START{ (node->flags|=flag); }G_STMT_END
  76 #define GTK_RBNODE_UNSET_FLAG(node, flag)       G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
  77 #define GTK_RBNODE_FLAG_SET(node, flag)         (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
  78
  79
  80 void       _gtk_rbtree_push_allocator   (GAllocator             *allocator);
  81 void       _gtk_rbtree_pop_allocator    (void);
  82 GtkRBTree *_gtk_rbtree_new              (void);
  83 void       _gtk_rbtree_free             (GtkRBTree              *tree);
  84 void       _gtk_rbtree_remove           (GtkRBTree              *tree);
  85 void       _gtk_rbtree_destroy          (GtkRBTree              *tree);
  86 GtkRBNode *_gtk_rbtree_insert_before    (GtkRBTree              *tree,
  87                                          GtkRBNode              *node,
  88                                          gint                    height);
  89 GtkRBNode *_gtk_rbtree_insert_after     (GtkRBTree              *tree,
  90                                          GtkRBNode              *node,
  91                                          gint                    height);
  92 void       _gtk_rbtree_remove_node      (GtkRBTree              *tree,
  93                                          GtkRBNode              *node);
  94 GtkRBNode *_gtk_rbtree_find_count       (GtkRBTree              *tree,
  95                                          gint                    count);
  96 void       _gtk_rbtree_node_set_height  (GtkRBTree              *tree,
  97                                          GtkRBNode              *node,
  98                                          gint                    height);
  99 gint       _gtk_rbtree_node_find_offset (GtkRBTree              *tree,
 100                                          GtkRBNode              *node);
 101 gint       _gtk_rbtree_find_offset      (GtkRBTree              *tree,
 102                                          gint                    offset,
 103                                          GtkRBTree             **new_tree,
 104                                          GtkRBNode             **new_node);
 105 void       _gtk_rbtree_traverse         (GtkRBTree              *tree,
 106                                          GtkRBNode              *node,
 107                                          GTraverseType           order,
 108                                          GtkRBTreeTraverseFunc   func,
 109                                          gpointer                data);
 110 GtkRBNode *_gtk_rbtree_next             (GtkRBTree              *tree,
 111                                          GtkRBNode              *node);
 112 GtkRBNode *_gtk_rbtree_prev             (GtkRBTree              *tree,
 113                                          GtkRBNode              *node);
 114 void       _gtk_rbtree_next_full        (GtkRBTree              *tree,
 115                                          GtkRBNode              *node,
 116                                          GtkRBTree             **new_tree,
 117                                          GtkRBNode             **new_node);
 118 void       _gtk_rbtree_prev_full        (GtkRBTree              *tree,
 119                                          GtkRBNode              *node,
 120                                          GtkRBTree             **new_tree,
 121                                          GtkRBNode             **new_node);
 122
 123
 124 /* This func just checks the integrity of the tree */
 125 /* It will go away later. */
 126 void       _gtk_rbtree_test             (GtkRBTree              *tree);
 127
 128
 129 #ifdef __cplusplus
 130 }
 131 #endif /* __cplusplus */
 132
 133 #endif /* __GTK_RBTREE_H__ */