[gtk] Rename GtkRBTree to GtkTreeRBTree



commit e269f43afc2c6b11e18cb528def814fed926fb3e
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Jan 6 22:28:09 2019 -0500

    Rename GtkRBTree to GtkTreeRBTree
    
    This frees up the generic name for a more
    generic rbtree implementation.

 gtk/a11y/gtktreeviewaccessible.c        |  178 ++--
 gtk/a11y/gtktreeviewaccessibleprivate.h |   20 +-
 gtk/gtkrbtree.c                         | 1738 ------------------------------
 gtk/gtkrbtreeprivate.h                  |  172 ---
 gtk/gtktreeprivate.h                    |   22 +-
 gtk/gtktreerbtree.c                     | 1744 +++++++++++++++++++++++++++++++
 gtk/gtktreerbtreeprivate.h              |  172 +++
 gtk/gtktreeselection.c                  |  180 ++--
 gtk/gtktreeview.c                       |  840 +++++++--------
 gtk/meson.build                         |    2 +-
 testsuite/gtk/meson.build               |    2 +-
 testsuite/gtk/rbtree.c                  |  314 +++---
 12 files changed, 2695 insertions(+), 2689 deletions(-)
---
diff --git a/gtk/a11y/gtktreeviewaccessible.c b/gtk/a11y/gtktreeviewaccessible.c
index 4c9f66fe9a..6a27578540 100644
--- a/gtk/a11y/gtktreeviewaccessible.c
+++ b/gtk/a11y/gtktreeviewaccessible.c
@@ -44,8 +44,8 @@ typedef struct _GtkTreeViewAccessibleCellInfo  GtkTreeViewAccessibleCellInfo;
 struct _GtkTreeViewAccessibleCellInfo
 {
   GtkCellAccessible *cell;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GtkTreeViewColumn *cell_col_ref;
   GtkTreeViewAccessible *view;
 };
@@ -58,21 +58,21 @@ static gboolean         is_cell_showing                 (GtkTreeView
                                                          GdkRectangle           *cell_rect);
 
 static void             cell_info_new                   (GtkTreeViewAccessible  *accessible,
-                                                         GtkRBTree              *tree,
-                                                         GtkRBNode              *node,
+                                                         GtkTreeRBTree          *tree,
+                                                         GtkTreeRBNode          *node,
                                                          GtkTreeViewColumn      *tv_col,
                                                          GtkCellAccessible      *cell);
 static gint             get_column_number               (GtkTreeView            *tree_view,
                                                          GtkTreeViewColumn      *column);
 
 static gboolean         get_rbtree_column_from_index    (GtkTreeView            *tree_view,
-                                                         gint                   index,
-                                                         GtkRBTree              **tree,
-                                                         GtkRBNode              **node,
-                                                         GtkTreeViewColumn      **column);
+                                                         gint                    index,
+                                                         GtkTreeRBTree         **tree,
+                                                         GtkTreeRBNode         **node,
+                                                         GtkTreeViewColumn     **column);
 
-static GtkTreeViewAccessibleCellInfo* find_cell_info    (GtkTreeViewAccessible           *view,
-                                                         GtkCellAccessible               *cell);
+static GtkTreeViewAccessibleCellInfo* find_cell_info    (GtkTreeViewAccessible  *view,
+                                                         GtkCellAccessible      *cell);
 static AtkObject *       get_header_from_column         (GtkTreeViewColumn      *tv_col);
 
 
@@ -231,7 +231,7 @@ gtk_tree_view_accessible_widget_unset (GtkAccessible *gtkaccessible)
 static gint
 get_n_rows (GtkTreeView *tree_view)
 {
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
   tree = _gtk_tree_view_get_rbtree (tree_view);
 
@@ -312,7 +312,7 @@ set_cell_data (GtkTreeView           *treeview,
 
   model = gtk_tree_view_get_model (treeview);
 
-  if (GTK_RBNODE_FLAG_SET (cell_info->node, GTK_RBNODE_IS_PARENT) &&
+  if (GTK_TREE_RBNODE_FLAG_SET (cell_info->node, GTK_TREE_RBNODE_IS_PARENT) &&
       cell_info->cell_col_ref == gtk_tree_view_get_expander_column (treeview))
     {
       is_expander = TRUE;
@@ -342,8 +342,8 @@ set_cell_data (GtkTreeView           *treeview,
 
 static GtkCellAccessible *
 peek_cell (GtkTreeViewAccessible *accessible,
-           GtkRBTree             *tree,
-           GtkRBNode             *node,
+           GtkTreeRBTree         *tree,
+           GtkTreeRBNode         *node,
            GtkTreeViewColumn     *column)
 {
   GtkTreeViewAccessibleCellInfo lookup, *cell_info;
@@ -411,12 +411,12 @@ create_cell_accessible (GtkTreeView           *treeview,
 
   return cell;
 }
-                        
+
 static GtkCellAccessible *
 create_cell (GtkTreeView           *treeview,
              GtkTreeViewAccessible *accessible,
-             GtkRBTree             *tree,
-             GtkRBNode             *node,
+             GtkTreeRBTree         *tree,
+             GtkTreeRBNode         *node,
              GtkTreeViewColumn     *column)
 {
   GtkCellAccessible *cell;
@@ -439,8 +439,8 @@ gtk_tree_view_accessible_ref_child (AtkObject *obj,
   GtkCellAccessible *cell;
   GtkTreeView *tree_view;
   GtkTreeViewColumn *tv_col;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   AtkObject *child;
 
   widget = gtk_accessible_get_widget (GTK_ACCESSIBLE (obj));
@@ -536,8 +536,8 @@ gtk_tree_view_accessible_ref_accessible_at_point (AtkComponent *component,
   gint x_pos, y_pos;
   gint bx, by;
   GtkCellAccessible *cell;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   widget = gtk_accessible_get_widget (GTK_ACCESSIBLE (component));
   if (widget == NULL)
@@ -680,8 +680,8 @@ gtk_tree_view_accessible_is_row_selected (AtkTable *table,
                                           gint      row)
 {
   GtkWidget *widget;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   if (row < 0)
     return FALSE;
@@ -690,13 +690,13 @@ gtk_tree_view_accessible_is_row_selected (AtkTable *table,
   if (widget == NULL)
     return FALSE;
 
-  if (!_gtk_rbtree_find_index (_gtk_tree_view_get_rbtree (GTK_TREE_VIEW (widget)),
-                               row,
-                               &tree,
-                               &node))
+  if (!gtk_tree_rbtree_find_index (_gtk_tree_view_get_rbtree (GTK_TREE_VIEW (widget)),
+                                   row,
+                                   &tree,
+                                   &node))
     return FALSE;
 
-  return GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED);
+  return GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED);
 }
 
 static gboolean
@@ -719,8 +719,8 @@ get_selected_rows (GtkTreeModel *model,
                    gpointer      datap)
 {
   SelectedRowsData *data = datap;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   int id;
 
   if (_gtk_tree_view_find_node (data->treeview,
@@ -730,7 +730,7 @@ get_selected_rows (GtkTreeModel *model,
       g_assert_not_reached ();
     }
 
-  id = _gtk_rbtree_node_get_index (tree, node);
+  id = gtk_tree_rbtree_node_get_index (tree, node);
 
   g_array_append_val (data->array, id);
 }
@@ -773,8 +773,8 @@ gtk_tree_view_accessible_add_row_selection (AtkTable *table,
 {
   GtkTreeView *treeview;
   GtkTreePath *path;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   if (row < 0)
     return FALSE;
@@ -783,13 +783,13 @@ gtk_tree_view_accessible_add_row_selection (AtkTable *table,
   if (treeview == NULL)
     return FALSE;
 
-  if (!_gtk_rbtree_find_index (_gtk_tree_view_get_rbtree (treeview),
-                               row,
-                               &tree,
-                               &node))
+  if (!gtk_tree_rbtree_find_index (_gtk_tree_view_get_rbtree (treeview),
+                                   row,
+                                   &tree,
+                                   &node))
     return FALSE;
 
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     return FALSE;
 
   path = _gtk_tree_path_new_from_rbtree (tree, node);
@@ -805,8 +805,8 @@ gtk_tree_view_accessible_remove_row_selection (AtkTable *table,
 {
   GtkTreeView *treeview;
   GtkTreePath *path;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   if (row < 0)
     return FALSE;
@@ -815,13 +815,13 @@ gtk_tree_view_accessible_remove_row_selection (AtkTable *table,
   if (treeview == NULL)
     return FALSE;
 
-  if (!_gtk_rbtree_find_index (_gtk_tree_view_get_rbtree (treeview),
-                               row,
-                               &tree,
-                               &node))
+  if (!gtk_tree_rbtree_find_index (_gtk_tree_view_get_rbtree (treeview),
+                                   row,
+                                   &tree,
+                                   &node))
     return FALSE;
 
-  if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+  if (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     return FALSE;
 
   path = _gtk_tree_path_new_from_rbtree (tree, node);
@@ -1218,10 +1218,10 @@ gtk_tree_view_accessible_get_renderer_state (GtkCellAccessibleParent *parent,
 
   flags = 0;
 
-  if (GTK_RBNODE_FLAG_SET (cell_info->node, GTK_RBNODE_IS_SELECTED))
+  if (GTK_TREE_RBNODE_FLAG_SET (cell_info->node, GTK_TREE_RBNODE_IS_SELECTED))
     flags |= GTK_CELL_RENDERER_SELECTED;
 
-  if (GTK_RBNODE_FLAG_SET (cell_info->node, GTK_RBNODE_IS_PRELIT))
+  if (GTK_TREE_RBNODE_FLAG_SET (cell_info->node, GTK_TREE_RBNODE_IS_PRELIT))
     flags |= GTK_CELL_RENDERER_PRELIT;
 
   if (gtk_tree_view_column_get_sort_indicator (cell_info->cell_col_ref))
@@ -1231,7 +1231,7 @@ gtk_tree_view_accessible_get_renderer_state (GtkCellAccessibleParent *parent,
 
   if (cell_info->cell_col_ref == gtk_tree_view_get_expander_column (treeview))
     {
-      if (GTK_RBNODE_FLAG_SET (cell_info->node, GTK_RBNODE_IS_PARENT))
+      if (GTK_TREE_RBNODE_FLAG_SET (cell_info->node, GTK_TREE_RBNODE_IS_PARENT))
         flags |= GTK_CELL_RENDERER_EXPANDABLE;
 
       if (cell_info->node->children)
@@ -1242,8 +1242,8 @@ gtk_tree_view_accessible_get_renderer_state (GtkCellAccessibleParent *parent,
     {
       GtkTreeViewColumn *column;
       GtkTreePath *path;
-      GtkRBTree *tree;
-      GtkRBNode *node = NULL;
+      GtkTreeRBTree *tree;
+      GtkTreeRBNode *node = NULL;
       
       gtk_tree_view_get_cursor (treeview, &path, &column);
       if (path)
@@ -1335,8 +1335,8 @@ gtk_tree_view_accessible_update_relationset (GtkCellAccessibleParent *parent,
   GtkTreeViewColumn *column;
   GtkTreeView *treeview;
   AtkRelation *relation;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   AtkObject *object;
 
   /* Don't set relations on cells that aren't direct descendants of the treeview.
@@ -1379,9 +1379,9 @@ gtk_tree_view_accessible_update_relationset (GtkCellAccessibleParent *parent,
   tree = cell_info->node->children;
   if (tree)
     {
-      for (node = _gtk_rbtree_first (tree);
+      for (node = gtk_tree_rbtree_first (tree);
            node != NULL;
-           node = _gtk_rbtree_next (tree, node))
+           node = gtk_tree_rbtree_next (tree, node))
         {
           object = ATK_OBJECT (peek_cell (accessible, tree, node, column));
           if (object == NULL)
@@ -1414,7 +1414,7 @@ gtk_tree_view_accessible_get_cell_position (GtkCellAccessibleParent *parent,
     return;
 
   if (row)
-    (*row) = _gtk_rbtree_node_get_index (cell_info->tree, cell_info->node);
+    (*row) = gtk_tree_rbtree_node_get_index (cell_info->tree, cell_info->node);
   if (column)
     (*column) = get_column_number (tree_view, cell_info->cell_col_ref);
 }
@@ -1518,7 +1518,7 @@ cell_info_get_index (GtkTreeView                     *tree_view,
 {
   int index;
 
-  index = _gtk_rbtree_node_get_index (info->tree, info->node) + 1;
+  index = gtk_tree_rbtree_node_get_index (info->tree, info->node) + 1;
   index *= get_n_columns (tree_view);
   index += get_column_number (tree_view, info->cell_col_ref);
 
@@ -1527,8 +1527,8 @@ cell_info_get_index (GtkTreeView                     *tree_view,
 
 static void
 cell_info_new (GtkTreeViewAccessible *accessible,
-               GtkRBTree             *tree,
-               GtkRBNode             *node,
+               GtkTreeRBTree         *tree,
+               GtkTreeRBNode         *node,
                GtkTreeViewColumn     *tv_col,
                GtkCellAccessible     *cell)
 {
@@ -1582,8 +1582,8 @@ get_column_number (GtkTreeView       *treeview,
 static gboolean
 get_rbtree_column_from_index (GtkTreeView        *tree_view,
                               gint                index,
-                              GtkRBTree         **tree,
-                              GtkRBNode         **node,
+                              GtkTreeRBTree     **tree,
+                              GtkTreeRBNode     **node,
                               GtkTreeViewColumn **column)
 {
   guint n_columns = get_n_columns (tree_view);
@@ -1599,10 +1599,10 @@ get_rbtree_column_from_index (GtkTreeView        *tree_view,
     {
       g_return_val_if_fail (node != NULL, FALSE);
 
-      if (!_gtk_rbtree_find_index (_gtk_tree_view_get_rbtree (tree_view),
-                                   index / n_columns,
-                                   tree,
-                                   node))
+      if (!gtk_tree_rbtree_find_index (_gtk_tree_view_get_rbtree (tree_view),
+                                       index / n_columns,
+                                       tree,
+                                       node))
         return FALSE;
     }
 
@@ -1652,9 +1652,9 @@ get_header_from_column (GtkTreeViewColumn *tv_col)
 }
 
 void
-_gtk_tree_view_accessible_add (GtkTreeView *treeview,
-                               GtkRBTree   *tree,
-                               GtkRBNode   *node)
+_gtk_tree_view_accessible_add (GtkTreeView   *treeview,
+                               GtkTreeRBTree *tree,
+                               GtkTreeRBNode *node)
 {
   GtkTreeViewAccessible *accessible;
   guint row, n_rows, n_cols, i;
@@ -1665,12 +1665,12 @@ _gtk_tree_view_accessible_add (GtkTreeView *treeview,
 
   if (node == NULL)
     {
-      row = tree->parent_tree ? _gtk_rbtree_node_get_index (tree->parent_tree, tree->parent_node) : 0;
+      row = tree->parent_tree ? gtk_tree_rbtree_node_get_index (tree->parent_tree, tree->parent_node) : 0;
       n_rows = tree->root->total_count;
     }
   else
     {
-      row = _gtk_rbtree_node_get_index (tree, node);
+      row = gtk_tree_rbtree_node_get_index (tree, node);
       n_rows = 1 + (node->children ? node->children->root->total_count : 0);
     }
 
@@ -1681,16 +1681,16 @@ _gtk_tree_view_accessible_add (GtkTreeView *treeview,
     {
       for (i = (row + 1) * n_cols; i < (row + n_rows + 1) * n_cols; i++)
         {
-         /* Pass NULL as the child object, i.e. 4th argument */
+          /* Pass NULL as the child object, i.e. 4th argument */
           g_signal_emit_by_name (accessible, "children-changed::add", i, NULL, NULL);
         }
     }
 }
 
 void
-_gtk_tree_view_accessible_remove (GtkTreeView *treeview,
-                                  GtkRBTree   *tree,
-                                  GtkRBNode   *node)
+_gtk_tree_view_accessible_remove (GtkTreeView   *treeview,
+                                  GtkTreeRBTree *tree,
+                                  GtkTreeRBNode *node)
 {
   GtkTreeViewAccessibleCellInfo *cell_info;
   GHashTableIter iter;
@@ -1705,12 +1705,12 @@ _gtk_tree_view_accessible_remove (GtkTreeView *treeview,
 
   if (node == NULL)
     {
-      row = tree->parent_tree ? _gtk_rbtree_node_get_index (tree->parent_tree, tree->parent_node) : 0;
+      row = tree->parent_tree ? gtk_tree_rbtree_node_get_index (tree->parent_tree, tree->parent_node) : 0;
       n_rows = tree->root->total_count + 1;
     }
   else
     {
-      row = _gtk_rbtree_node_get_index (tree, node);
+      row = gtk_tree_rbtree_node_get_index (tree, node);
       n_rows = 1 + (node->children ? node->children->root->total_count : 0);
 
       tree = node->children;
@@ -1732,16 +1732,16 @@ _gtk_tree_view_accessible_remove (GtkTreeView *treeview,
         {
           if (node == cell_info->node ||
               tree == cell_info->tree ||
-              (tree && _gtk_rbtree_contains (tree, cell_info->tree)))
+              (tree && gtk_tree_rbtree_contains (tree, cell_info->tree)))
             g_hash_table_iter_remove (&iter);
         }
     }
 }
 
 void
-_gtk_tree_view_accessible_changed (GtkTreeView *treeview,
-                                   GtkRBTree   *tree,
-                                   GtkRBNode   *node)
+_gtk_tree_view_accessible_changed (GtkTreeView   *treeview,
+                                   GtkTreeRBTree *tree,
+                                   GtkTreeRBNode *node)
 {
   GtkTreeViewAccessible *accessible;
   guint i;
@@ -1956,8 +1956,8 @@ _gtk_tree_view_accessible_update_focus_column (GtkTreeView       *treeview,
 {
   GtkTreeViewAccessible *accessible;
   AtkObject *obj;
-  GtkRBTree *cursor_tree;
-  GtkRBNode *cursor_node;
+  GtkTreeRBTree *cursor_tree;
+  GtkTreeRBNode *cursor_node;
   GtkCellAccessible *cell;
 
   old_focus = get_effective_focus_column (treeview, old_focus);
@@ -1994,10 +1994,10 @@ _gtk_tree_view_accessible_update_focus_column (GtkTreeView       *treeview,
 }
 
 void
-_gtk_tree_view_accessible_add_state (GtkTreeView          *treeview,
-                                     GtkRBTree            *tree,
-                                     GtkRBNode            *node,
-                                     GtkCellRendererState  state)
+_gtk_tree_view_accessible_add_state (GtkTreeView         *treeview,
+                                     GtkTreeRBTree       *tree,
+                                     GtkTreeRBNode       *node,
+                                     GtkCellRendererState state)
 {
   GtkTreeViewAccessible *accessible;
   GtkTreeViewColumn *single_column;
@@ -2059,10 +2059,10 @@ _gtk_tree_view_accessible_add_state (GtkTreeView          *treeview,
 }
 
 void
-_gtk_tree_view_accessible_remove_state (GtkTreeView          *treeview,
-                                        GtkRBTree            *tree,
-                                        GtkRBNode            *node,
-                                        GtkCellRendererState  state)
+_gtk_tree_view_accessible_remove_state (GtkTreeView         *treeview,
+                                        GtkTreeRBTree       *tree,
+                                        GtkTreeRBNode       *node,
+                                        GtkCellRendererState state)
 {
   GtkTreeViewAccessible *accessible;
   GtkTreeViewColumn *single_column;
diff --git a/gtk/a11y/gtktreeviewaccessibleprivate.h b/gtk/a11y/gtktreeviewaccessibleprivate.h
index 3c91009bac..956197883b 100644
--- a/gtk/a11y/gtktreeviewaccessibleprivate.h
+++ b/gtk/a11y/gtktreeviewaccessibleprivate.h
@@ -25,14 +25,14 @@ G_BEGIN_DECLS
 /* called by treeview code */
 void            _gtk_tree_view_accessible_reorder       (GtkTreeView       *treeview);
 void            _gtk_tree_view_accessible_add           (GtkTreeView       *treeview,
-                                                         GtkRBTree         *tree,
-                                                         GtkRBNode         *node);
+                                                         GtkTreeRBTree     *tree,
+                                                         GtkTreeRBNode     *node);
 void            _gtk_tree_view_accessible_remove        (GtkTreeView       *treeview,
-                                                         GtkRBTree         *tree,
-                                                         GtkRBNode         *node);
+                                                         GtkTreeRBTree     *tree,
+                                                         GtkTreeRBNode     *node);
 void            _gtk_tree_view_accessible_changed       (GtkTreeView       *treeview,
-                                                         GtkRBTree         *tree,
-                                                         GtkRBNode         *node);
+                                                         GtkTreeRBTree     *tree,
+                                                         GtkTreeRBNode     *node);
 
 void            _gtk_tree_view_accessible_add_column    (GtkTreeView       *treeview,
                                                          GtkTreeViewColumn *column,
@@ -52,12 +52,12 @@ void            _gtk_tree_view_accessible_update_focus_column
                                                          GtkTreeViewColumn *new_focus);
 
 void            _gtk_tree_view_accessible_add_state     (GtkTreeView       *treeview,
-                                                         GtkRBTree         *tree,
-                                                         GtkRBNode         *node,
+                                                         GtkTreeRBTree     *tree,
+                                                         GtkTreeRBNode     *node,
                                                          GtkCellRendererState state);
 void            _gtk_tree_view_accessible_remove_state  (GtkTreeView       *treeview,
-                                                         GtkRBTree         *tree,
-                                                         GtkRBNode         *node,
+                                                         GtkTreeRBTree     *tree,
+                                                         GtkTreeRBNode     *node,
                                                          GtkCellRendererState state);
 
 G_END_DECLS
diff --git a/gtk/gtktreeprivate.h b/gtk/gtktreeprivate.h
index 4990f90770..ede31a714b 100644
--- a/gtk/gtktreeprivate.h
+++ b/gtk/gtktreeprivate.h
@@ -21,7 +21,7 @@
 
 #include <gtk/gtktreeview.h>
 #include <gtk/gtktreeselection.h>
-#include <gtk/gtkrbtreeprivate.h>
+#include <gtk/gtktreerbtreeprivate.h>
 
 G_BEGIN_DECLS
 
@@ -36,21 +36,21 @@ GtkTreeSelectMode;
 
 /* functions that shouldn't be exported */
 void         _gtk_tree_selection_internal_select_node (GtkTreeSelection  *selection,
-                                                      GtkRBNode         *node,
-                                                      GtkRBTree         *tree,
+                                                      GtkTreeRBNode     *node,
+                                                      GtkTreeRBTree     *tree,
                                                       GtkTreePath       *path,
                                                        GtkTreeSelectMode  mode,
                                                       gboolean           override_browse_mode);
 void         _gtk_tree_selection_emit_changed         (GtkTreeSelection  *selection);
 gboolean     _gtk_tree_view_find_node                 (GtkTreeView       *tree_view,
                                                       GtkTreePath       *path,
-                                                      GtkRBTree        **tree,
-                                                      GtkRBNode        **node);
+                                                      GtkTreeRBTree    **tree,
+                                                      GtkTreeRBNode    **node);
 gboolean     _gtk_tree_view_get_cursor_node           (GtkTreeView       *tree_view,
-                                                      GtkRBTree        **tree,
-                                                      GtkRBNode        **node);
-GtkTreePath *_gtk_tree_path_new_from_rbtree           (GtkRBTree         *tree,
-                                                      GtkRBNode         *node);
+                                                      GtkTreeRBTree    **tree,
+                                                      GtkTreeRBNode    **node);
+GtkTreePath *_gtk_tree_path_new_from_rbtree           (GtkTreeRBTree     *tree,
+                                                      GtkTreeRBNode     *node);
 
 void         _gtk_tree_view_add_editable              (GtkTreeView       *tree_view,
                                                        GtkTreeViewColumn *column,
@@ -72,7 +72,7 @@ void         _gtk_tree_view_get_row_separator_func    (GtkTreeView
 GtkTreePath *_gtk_tree_view_get_anchor_path           (GtkTreeView                 *tree_view);
 void         _gtk_tree_view_set_anchor_path           (GtkTreeView                 *tree_view,
                                                       GtkTreePath                 *anchor_path);
-GtkRBTree *  _gtk_tree_view_get_rbtree                (GtkTreeView                 *tree_view);
+GtkTreeRBTree *    _gtk_tree_view_get_rbtree          (GtkTreeView                 *tree_view);
 
 GtkTreeViewColumn *_gtk_tree_view_get_focus_column    (GtkTreeView                 *tree_view);
 void               _gtk_tree_view_set_focus_column    (GtkTreeView                 *tree_view,
@@ -83,7 +83,7 @@ GtkTreeSelection* _gtk_tree_selection_new_with_tree_view (GtkTreeView      *tree
 void              _gtk_tree_selection_set_tree_view      (GtkTreeSelection *selection,
                                                           GtkTreeView      *tree_view);
 gboolean          _gtk_tree_selection_row_is_selectable  (GtkTreeSelection *selection,
-                                                         GtkRBNode        *node,
+                                                         GtkTreeRBNode    *node,
                                                          GtkTreePath      *path);
 
 
diff --git a/gtk/gtktreerbtree.c b/gtk/gtktreerbtree.c
new file mode 100644
index 0000000000..964b6026d1
--- /dev/null
+++ b/gtk/gtktreerbtree.c
@@ -0,0 +1,1744 @@
+/* gtktreerbtree.c
+ * 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, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+#include "gtktreerbtreeprivate.h"
+#include "gtkdebug.h"
+
+static GtkTreeRBNode *gtk_tree_rbnode_new                (GtkTreeRBTree *tree,
+                                                          gint           height);
+static void        gtk_tree_rbnode_free               (GtkTreeRBNode *node);
+static void        gtk_tree_rbnode_rotate_left        (GtkTreeRBTree *tree,
+                                                       GtkTreeRBNode *node);
+static void        gtk_tree_rbnode_rotate_right       (GtkTreeRBTree *tree,
+                                                       GtkTreeRBNode *node);
+static void        gtk_tree_rbtree_insert_fixup       (GtkTreeRBTree *tree,
+                                                       GtkTreeRBNode *node);
+static void        gtk_tree_rbtree_remove_node_fixup  (GtkTreeRBTree *tree,
+                                                       GtkTreeRBNode *node,
+                                                       GtkTreeRBNode *parent);
+static inline void fixup_validation              (GtkTreeRBTree *tree,
+                                                  GtkTreeRBNode *node);
+static inline void fixup_total_count             (GtkTreeRBTree *tree,
+                                                  GtkTreeRBNode *node);
+#ifdef G_ENABLE_DEBUG
+static void        gtk_tree_rbtree_test               (const gchar   *where,
+                                                       GtkTreeRBTree *tree);
+static void        gtk_tree_rbtree_debug_spew         (GtkTreeRBTree *tree,
+                                                       GString       *s);
+#endif
+
+static const GtkTreeRBNode nil =
+{
+  /* .flags = */ GTK_TREE_RBNODE_BLACK,
+
+  /* rest is NULL */
+};
+
+gboolean
+gtk_tree_rbtree_is_nil (GtkTreeRBNode *node)
+{
+  return node == &nil;
+}
+
+static GtkTreeRBNode *
+gtk_tree_rbnode_new (GtkTreeRBTree *tree,
+                     gint           height)
+{
+  GtkTreeRBNode *node = g_slice_new (GtkTreeRBNode);
+
+  node->left = (GtkTreeRBNode *) &nil;
+  node->right = (GtkTreeRBNode *) &nil;
+  node->parent = (GtkTreeRBNode *) &nil;
+  node->flags = GTK_TREE_RBNODE_RED;
+  node->total_count = 1;
+  node->count = 1;
+  node->children = NULL;
+  node->offset = height;
+  return node;
+}
+
+static void
+gtk_tree_rbnode_free (GtkTreeRBNode *node)
+{
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      node->left = (gpointer) 0xdeadbeef;
+      node->right = (gpointer) 0xdeadbeef;
+      node->parent = (gpointer) 0xdeadbeef;
+      node->total_count = 56789;
+      node->offset = 56789;
+      node->count = 56789;
+      node->flags = 0;
+    }
+#endif
+  g_slice_free (GtkTreeRBNode, node);
+}
+
+static void
+gtk_tree_rbnode_rotate_left (GtkTreeRBTree *tree,
+                             GtkTreeRBNode *node)
+{
+  gint node_height, right_height;
+  GtkTreeRBNode *right;
+
+  g_return_if_fail (!gtk_tree_rbtree_is_nil (node));
+  g_return_if_fail (!gtk_tree_rbtree_is_nil (node->right));
+
+  right = node->right;
+
+  node_height = GTK_TREE_RBNODE_GET_HEIGHT (node);
+  right_height = GTK_TREE_RBNODE_GET_HEIGHT (right);
+  node->right = right->left;
+  if (!gtk_tree_rbtree_is_nil (right->left))
+    right->left->parent = node;
+
+  right->parent = node->parent;
+  if (!gtk_tree_rbtree_is_nil (node->parent))
+    {
+      if (node == node->parent->left)
+        node->parent->left = right;
+      else
+        node->parent->right = right;
+    }
+  else
+    {
+      tree->root = right;
+    }
+
+  right->left = node;
+  node->parent = right;
+
+  node->count = 1 + node->left->count + node->right->count;
+  right->count = 1 + right->left->count + right->right->count;
+
+  node->offset = node_height + node->left->offset + node->right->offset +
+                 (node->children ? node->children->root->offset : 0);
+  right->offset = right_height + right->left->offset + right->right->offset +
+                  (right->children ? right->children->root->offset : 0);
+
+  fixup_validation (tree, node);
+  fixup_validation (tree, right);
+  fixup_total_count (tree, node);
+  fixup_total_count (tree, right);
+}
+
+static void
+gtk_tree_rbnode_rotate_right (GtkTreeRBTree *tree,
+                              GtkTreeRBNode *node)
+{
+  gint node_height, left_height;
+  GtkTreeRBNode *left;
+
+  g_return_if_fail (!gtk_tree_rbtree_is_nil (node));
+  g_return_if_fail (!gtk_tree_rbtree_is_nil (node->left));
+
+  left = node->left;
+
+  node_height = GTK_TREE_RBNODE_GET_HEIGHT (node);
+  left_height = GTK_TREE_RBNODE_GET_HEIGHT (left);
+
+  node->left = left->right;
+  if (!gtk_tree_rbtree_is_nil (left->right))
+    left->right->parent = node;
+
+  left->parent = node->parent;
+  if (!gtk_tree_rbtree_is_nil (node->parent))
+    {
+      if (node == node->parent->right)
+        node->parent->right = left;
+      else
+        node->parent->left = left;
+    }
+  else
+    {
+      tree->root = left;
+    }
+
+  /* link node and left */
+  left->right = node;
+  node->parent = left;
+
+  node->count = 1 + node->left->count + node->right->count;
+  left->count = 1 + left->left->count + left->right->count;
+
+  node->offset = node_height + node->left->offset + node->right->offset +
+                 (node->children ? node->children->root->offset : 0);
+  left->offset = left_height + left->left->offset + left->right->offset +
+                 (left->children ? left->children->root->offset : 0);
+
+  fixup_validation (tree, node);
+  fixup_validation (tree, left);
+  fixup_total_count (tree, node);
+  fixup_total_count (tree, left);
+}
+
+static void
+gtk_tree_rbtree_insert_fixup (GtkTreeRBTree *tree,
+                              GtkTreeRBNode *node)
+{
+  /* check Red-Black properties */
+  while (node != tree->root && GTK_TREE_RBNODE_GET_COLOR (node->parent) == GTK_TREE_RBNODE_RED)
+    {
+      /* we have a violation */
+      if (node->parent == node->parent->parent->left)
+        {
+          GtkTreeRBNode *y = node->parent->parent->right;
+          if (GTK_TREE_RBNODE_GET_COLOR (y) == GTK_TREE_RBNODE_RED)
+            {
+              /* uncle is GTK_TREE_RBNODE_RED */
+              GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (y, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
+              node = node->parent->parent;
+            }
+          else
+            {
+              /* uncle is GTK_TREE_RBNODE_BLACK */
+              if (node == node->parent->right)
+                {
+                  /* make node a left child */
+                  node = node->parent;
+                  gtk_tree_rbnode_rotate_left (tree, node);
+                }
+
+              /* recolor and rotate */
+              GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
+              gtk_tree_rbnode_rotate_right (tree, node->parent->parent);
+            }
+        }
+      else
+        {
+          /* mirror image of above code */
+          GtkTreeRBNode *y = node->parent->parent->left;
+          if (GTK_TREE_RBNODE_GET_COLOR (y) == GTK_TREE_RBNODE_RED)
+            {
+              /* uncle is GTK_TREE_RBNODE_RED */
+              GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (y, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
+              node = node->parent->parent;
+            }
+          else
+            {
+              /* uncle is GTK_TREE_RBNODE_BLACK */
+              if (node == node->parent->left)
+                {
+                  node = node->parent;
+                  gtk_tree_rbnode_rotate_right (tree, node);
+                }
+              GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
+              gtk_tree_rbnode_rotate_left (tree, node->parent->parent);
+            }
+        }
+    }
+  GTK_TREE_RBNODE_SET_COLOR (tree->root, GTK_TREE_RBNODE_BLACK);
+}
+
+static void
+gtk_tree_rbtree_remove_node_fixup (GtkTreeRBTree *tree,
+                                   GtkTreeRBNode *node,
+                                   GtkTreeRBNode *parent)
+{
+  while (node != tree->root && GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK)
+    {
+      if (node == parent->left)
+        {
+          GtkTreeRBNode *w = parent->right;
+          if (GTK_TREE_RBNODE_GET_COLOR (w) == GTK_TREE_RBNODE_RED)
+            {
+              GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_RED);
+              gtk_tree_rbnode_rotate_left (tree, parent);
+              w = parent->right;
+            }
+          if (GTK_TREE_RBNODE_GET_COLOR (w->left) == GTK_TREE_RBNODE_BLACK && GTK_TREE_RBNODE_GET_COLOR 
(w->right) == GTK_TREE_RBNODE_BLACK)
+            {
+              GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
+              node = parent;
+            }
+          else
+            {
+              if (GTK_TREE_RBNODE_GET_COLOR (w->right) == GTK_TREE_RBNODE_BLACK)
+                {
+                  GTK_TREE_RBNODE_SET_COLOR (w->left, GTK_TREE_RBNODE_BLACK);
+                  GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
+                  gtk_tree_rbnode_rotate_right (tree, w);
+                  w = parent->right;
+                }
+              GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_GET_COLOR (parent));
+              GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (w->right, GTK_TREE_RBNODE_BLACK);
+              gtk_tree_rbnode_rotate_left (tree, parent);
+              node = tree->root;
+            }
+        }
+      else
+        {
+          GtkTreeRBNode *w = parent->left;
+          if (GTK_TREE_RBNODE_GET_COLOR (w) == GTK_TREE_RBNODE_RED)
+            {
+              GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_RED);
+              gtk_tree_rbnode_rotate_right (tree, parent);
+              w = parent->left;
+            }
+          if (GTK_TREE_RBNODE_GET_COLOR (w->right) == GTK_TREE_RBNODE_BLACK && GTK_TREE_RBNODE_GET_COLOR 
(w->left) == GTK_TREE_RBNODE_BLACK)
+            {
+              GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
+              node = parent;
+            }
+          else
+            {
+              if (GTK_TREE_RBNODE_GET_COLOR (w->left) == GTK_TREE_RBNODE_BLACK)
+                {
+                  GTK_TREE_RBNODE_SET_COLOR (w->right, GTK_TREE_RBNODE_BLACK);
+                  GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
+                  gtk_tree_rbnode_rotate_left (tree, w);
+                  w = parent->left;
+                }
+              GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_GET_COLOR (parent));
+              GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_BLACK);
+              GTK_TREE_RBNODE_SET_COLOR (w->left, GTK_TREE_RBNODE_BLACK);
+              gtk_tree_rbnode_rotate_right (tree, parent);
+              node = tree->root;
+            }
+        }
+
+      parent = node->parent;
+    }
+  GTK_TREE_RBNODE_SET_COLOR (node, GTK_TREE_RBNODE_BLACK);
+}
+
+GtkTreeRBTree *
+gtk_tree_rbtree_new (void)
+{
+  GtkTreeRBTree *retval;
+
+  retval = g_new (GtkTreeRBTree, 1);
+  retval->parent_tree = NULL;
+  retval->parent_node = NULL;
+
+  retval->root = (GtkTreeRBNode *) &nil;
+
+  return retval;
+}
+
+static void
+gtk_tree_rbtree_free_helper (GtkTreeRBTree *tree,
+                             GtkTreeRBNode *node,
+                             gpointer       data)
+{
+  if (node->children)
+    gtk_tree_rbtree_free (node->children);
+
+  gtk_tree_rbnode_free (node);
+}
+
+void
+gtk_tree_rbtree_free (GtkTreeRBTree *tree)
+{
+  gtk_tree_rbtree_traverse (tree,
+                            tree->root,
+                            G_POST_ORDER,
+                            gtk_tree_rbtree_free_helper,
+                            NULL);
+
+  if (tree->parent_node &&
+      tree->parent_node->children == tree)
+    tree->parent_node->children = NULL;
+  g_free (tree);
+}
+
+static void
+gtk_rbnode_adjust (GtkTreeRBTree *tree,
+                   GtkTreeRBNode *node,
+                   int            count_diff,
+                   int            total_count_diff,
+                   int            offset_diff)
+{
+  while (tree && node && !gtk_tree_rbtree_is_nil (node))
+    {
+      fixup_validation (tree, node);
+      node->offset += offset_diff;
+      node->count += count_diff;
+      node->total_count += total_count_diff;
+
+      node = node->parent;
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+          count_diff = 0;
+        }
+    }
+}
+
+void
+gtk_tree_rbtree_remove (GtkTreeRBTree *tree)
+{
+#ifdef G_ENABLE_DEBUG
+  GtkTreeRBTree *tmp_tree;
+
+  if (GTK_DEBUG_CHECK (TREE))
+    gtk_tree_rbtree_test (G_STRLOC, tree);
+#endif
+
+  /* ugly hack to make fixup_validation work in the first iteration of the
+   * loop below */
+  GTK_TREE_RBNODE_UNSET_FLAG (tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+
+  gtk_rbnode_adjust (tree->parent_tree,
+                     tree->parent_node,
+                     0,
+                     -(int) tree->root->total_count,
+                     -tree->root->offset);
+
+#ifdef G_ENABLE_DEBUG
+  tmp_tree = tree->parent_tree;
+#endif
+
+  gtk_tree_rbtree_free (tree);
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    gtk_tree_rbtree_test (G_STRLOC, tmp_tree);
+#endif
+}
+
+
+GtkTreeRBNode *
+gtk_tree_rbtree_insert_after (GtkTreeRBTree *tree,
+                              GtkTreeRBNode *current,
+                              gint           height,
+                              gboolean       valid)
+{
+  GtkTreeRBNode *node;
+  gboolean right = TRUE;
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      GString *s;
+
+      s = g_string_new ("");
+      g_string_append_printf (s, "gtk_tree_rbtree_insert_after: %p\n", current);
+      gtk_tree_rbtree_debug_spew (tree, s);
+      g_message ("%s", s->str);
+      g_string_free (s, TRUE);
+      gtk_tree_rbtree_test (G_STRLOC, tree);
+    }
+#endif
+
+  if (current != NULL && !gtk_tree_rbtree_is_nil (current->right))
+    {
+      current = current->right;
+      while (!gtk_tree_rbtree_is_nil (current->left))
+        current = current->left;
+      right = FALSE;
+    }
+  /* setup new node */
+  node = gtk_tree_rbnode_new (tree, height);
+
+  /* insert node in tree */
+  if (current)
+    {
+      node->parent = current;
+      if (right)
+        current->right = node;
+      else
+        current->left = node;
+      gtk_rbnode_adjust (tree, node->parent,
+                         1, 1, height);
+    }
+  else
+    {
+      g_assert (gtk_tree_rbtree_is_nil (tree->root));
+      tree->root = node;
+      gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
+                         0, 1, height);
+    }
+
+  if (valid)
+    gtk_tree_rbtree_node_mark_valid (tree, node);
+  else
+    gtk_tree_rbtree_node_mark_invalid (tree, node);
+
+  gtk_tree_rbtree_insert_fixup (tree, node);
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      GString *s;
+
+      s = g_string_new ("gtk_tree_rbtree_insert_after finished...\n");
+      gtk_tree_rbtree_debug_spew (tree, s);
+      g_message ("%s", s->str);
+      g_string_free (s, TRUE);
+      gtk_tree_rbtree_test (G_STRLOC, tree);
+    }
+#endif
+
+  return node;
+}
+
+GtkTreeRBNode *
+gtk_tree_rbtree_insert_before (GtkTreeRBTree *tree,
+                               GtkTreeRBNode *current,
+                               gint           height,
+                               gboolean       valid)
+{
+  GtkTreeRBNode *node;
+  gboolean left = TRUE;
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      GString *s;
+
+      s = g_string_new ("");
+      g_string_append_printf (s, "gtk_tree_rbtree_insert_before: %p\n", current);
+      gtk_tree_rbtree_debug_spew (tree, s);
+      g_message ("%s", s->str);
+      g_string_free (s, TRUE);
+      gtk_tree_rbtree_test (G_STRLOC, tree);
+    }
+#endif
+
+  if (current != NULL && !gtk_tree_rbtree_is_nil (current->left))
+    {
+      current = current->left;
+      while (!gtk_tree_rbtree_is_nil (current->right))
+        current = current->right;
+      left = FALSE;
+    }
+
+  /* setup new node */
+  node = gtk_tree_rbnode_new (tree, height);
+
+  /* insert node in tree */
+  if (current)
+    {
+      node->parent = current;
+      if (left)
+        current->left = node;
+      else
+        current->right = node;
+      gtk_rbnode_adjust (tree, node->parent,
+                         1, 1, height);
+    }
+  else
+    {
+      g_assert (gtk_tree_rbtree_is_nil (tree->root));
+      tree->root = node;
+      gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
+                         0, 1, height);
+    }
+
+  if (valid)
+    gtk_tree_rbtree_node_mark_valid (tree, node);
+  else
+    gtk_tree_rbtree_node_mark_invalid (tree, node);
+
+  gtk_tree_rbtree_insert_fixup (tree, node);
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      GString *s;
+
+      s = g_string_new ("gtk_tree_rbtree_insert_before finished...\n");
+      gtk_tree_rbtree_debug_spew (tree, s);
+      g_message ("%s", s->str);
+      g_string_free (s, TRUE);
+      gtk_tree_rbtree_test (G_STRLOC, tree);
+    }
+#endif
+
+  return node;
+}
+
+GtkTreeRBNode *
+gtk_tree_rbtree_find_count (GtkTreeRBTree *tree,
+                            gint           count)
+{
+  GtkTreeRBNode *node;
+
+  node = tree->root;
+  while (!gtk_tree_rbtree_is_nil (node) && (node->left->count + 1 != count))
+    {
+      if (node->left->count >= count)
+        node = node->left;
+      else
+        {
+          count -= (node->left->count + 1);
+          node = node->right;
+        }
+    }
+  if (gtk_tree_rbtree_is_nil (node))
+    return NULL;
+  return node;
+}
+
+void
+gtk_tree_rbtree_node_set_height (GtkTreeRBTree *tree,
+                                 GtkTreeRBNode *node,
+                                 gint           height)
+{
+  gint diff = height - GTK_TREE_RBNODE_GET_HEIGHT (node);
+
+  if (diff == 0)
+    return;
+
+  gtk_rbnode_adjust (tree, node, 0, 0, diff);
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    gtk_tree_rbtree_test (G_STRLOC, tree);
+#endif
+}
+
+void
+gtk_tree_rbtree_node_mark_invalid (GtkTreeRBTree *tree,
+                                   GtkTreeRBNode *node)
+{
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID))
+    return;
+
+  GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_INVALID);
+  do
+    {
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID))
+        return;
+      GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+      node = node->parent;
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+        }
+    }
+  while (node);
+}
+
+#if 0
+/* Draconian version. */
+void
+gtk_tree_rbtree_node_mark_invalid (GtkTreeRBTree *tree,
+                                   GtkTreeRBNode *node)
+{
+  GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_INVALID);
+  do
+    {
+      fixup_validation (tree, node);
+      node = node->parent;
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+        }
+    }
+  while (node);
+}
+#endif
+
+void
+gtk_tree_rbtree_node_mark_valid (GtkTreeRBTree *tree,
+                                 GtkTreeRBNode *node)
+{
+  if ((!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) &&
+      (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)))
+    return;
+
+  GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_INVALID);
+  GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_COLUMN_INVALID);
+
+  do
+    {
+      if ((GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) ||
+          (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)) ||
+          (node->children && GTK_TREE_RBNODE_FLAG_SET (node->children->root, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ||
+          (GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ||
+          (GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID)))
+        return;
+
+      GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+      node = node->parent;
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+        }
+    }
+  while (node);
+}
+
+#if 0
+/* Draconian version */
+void
+gtk_tree_rbtree_node_mark_valid (GtkTreeRBTree *tree,
+                                 GtkTreeRBNode *node)
+{
+  GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_INVALID);
+  GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_COLUMN_INVALID);
+
+  do
+    {
+      fixup_validation (tree, node);
+      node = node->parent;
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+        }
+    }
+  while (node);
+}
+#endif
+/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
+ */
+void
+gtk_tree_rbtree_column_invalid (GtkTreeRBTree *tree)
+{
+  GtkTreeRBNode *node;
+
+  if (tree == NULL)
+    return;
+
+  node = gtk_tree_rbtree_first (tree);
+
+  do
+    {
+      if (!(GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)))
+        GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_COLUMN_INVALID);
+      GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+
+      if (node->children)
+        gtk_tree_rbtree_column_invalid (node->children);
+    }
+  while ((node = gtk_tree_rbtree_next (tree, node)) != NULL);
+}
+
+void
+gtk_tree_rbtree_mark_invalid (GtkTreeRBTree *tree)
+{
+  GtkTreeRBNode *node;
+
+  if (tree == NULL)
+    return;
+
+  node = gtk_tree_rbtree_first (tree);
+
+  do
+    {
+      GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_INVALID);
+      GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+
+      if (node->children)
+        gtk_tree_rbtree_mark_invalid (node->children);
+    }
+  while ((node = gtk_tree_rbtree_next (tree, node)) != NULL);
+}
+
+void
+gtk_tree_rbtree_set_fixed_height (GtkTreeRBTree *tree,
+                                  gint           height,
+                                  gboolean       mark_valid)
+{
+  GtkTreeRBNode *node;
+
+  if (tree == NULL)
+    return;
+
+  node = gtk_tree_rbtree_first (tree);
+
+  do
+    {
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID))
+        {
+          gtk_tree_rbtree_node_set_height (tree, node, height);
+          if (mark_valid)
+            gtk_tree_rbtree_node_mark_valid (tree, node);
+        }
+
+      if (node->children)
+        gtk_tree_rbtree_set_fixed_height (node->children, height, mark_valid);
+    }
+  while ((node = gtk_tree_rbtree_next (tree, node)) != NULL);
+}
+
+static void
+reorder_prepare (GtkTreeRBTree *tree,
+                 GtkTreeRBNode *node,
+                 gpointer       data)
+{
+  node->offset -= node->left->offset + node->right->offset;
+  GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+}
+
+static void
+reorder_fixup (GtkTreeRBTree *tree,
+               GtkTreeRBNode *node,
+               gpointer       data)
+{
+  node->offset += node->left->offset + node->right->offset;
+  node->count = 1 + node->left->count + node->right->count;
+  fixup_validation (tree, node);
+  fixup_total_count (tree, node);
+}
+
+static void
+reorder_copy_node (GtkTreeRBTree *tree,
+                   GtkTreeRBNode *to,
+                   GtkTreeRBNode *from)
+{
+  to->flags = (to->flags & GTK_TREE_RBNODE_NON_COLORS) | GTK_TREE_RBNODE_GET_COLOR (from);
+
+  to->left = from->left;
+  if (!gtk_tree_rbtree_is_nil (to->left))
+    to->left->parent = to;
+
+  to->right = from->right;
+  if (!gtk_tree_rbtree_is_nil (to->right))
+    to->right->parent = to;
+
+  to->parent = from->parent;
+  if (gtk_tree_rbtree_is_nil (to->parent))
+    tree->root = to;
+  else if (to->parent->left == from)
+    to->parent->left = to;
+  else if (to->parent->right == from)
+    to->parent->right = to;
+}
+
+/* It basically pulls everything out of the tree, rearranges it, and puts it
+ * back together.  Our strategy is to keep the old RBTree intact, and just
+ * rearrange the contents.  When that is done, we go through and update the
+ * heights.  There is probably a more elegant way to write this function.  If
+ * anyone wants to spend the time writing it, patches will be accepted.
+ */
+void
+gtk_tree_rbtree_reorder (GtkTreeRBTree *tree,
+                         gint          *new_order,
+                         gint           length)
+{
+  GtkTreeRBNode **nodes;
+  GtkTreeRBNode *node;
+  gint i, j;
+
+  g_return_if_fail (tree != NULL);
+  g_return_if_fail (length > 0);
+  g_return_if_fail (tree->root->count == length);
+
+  nodes = g_new (GtkTreeRBNode *, length);
+
+  gtk_tree_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL);
+
+  for (node = gtk_tree_rbtree_first (tree), i = 0;
+       node;
+       node = gtk_tree_rbtree_next (tree, node), i++)
+    {
+      nodes[i] = node;
+    }
+
+  for (i = 0; i < length; i++)
+    {
+      GtkTreeRBNode tmp = { 0, };
+      GSList *l, *cycle = NULL;
+
+      tmp.offset = -1;
+
+      /* already swapped */
+      if (nodes[i] == NULL)
+        continue;
+      /* no need to swap */
+      if (new_order[i] == i)
+        continue;
+
+      /* make a list out of the pending nodes */
+      for (j = i; new_order[j] != i; j = new_order[j])
+        {
+          cycle = g_slist_prepend (cycle, nodes[j]);
+          nodes[j] = NULL;
+        }
+
+      node = nodes[j];
+      reorder_copy_node (tree, &tmp, node);
+      for (l = cycle; l; l = l->next)
+        {
+          reorder_copy_node (tree, node, l->data);
+          node = l->data;
+        }
+
+      reorder_copy_node (tree, node, &tmp);
+      nodes[j] = NULL;
+      g_slist_free (cycle);
+    }
+
+  gtk_tree_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL);
+
+  g_free (nodes);
+}
+
+/**
+ * gtk_tree_rbtree_contains:
+ * @tree: a tree
+ * @potential_child: a potential child of @tree
+ *
+ * Checks if @potential_child is a child (direct or via intermediate
+ * trees) of @tree.
+ *
+ * Returns: %TRUE if @potentitial_child is a child of @tree.
+ **/
+gboolean
+gtk_tree_rbtree_contains (GtkTreeRBTree *tree,
+                          GtkTreeRBTree *potential_child)
+{
+  g_return_val_if_fail (tree != NULL, FALSE);
+  g_return_val_if_fail (potential_child != NULL, FALSE);
+
+  do
+    {
+      potential_child = potential_child->parent_tree;
+      if (potential_child == tree)
+        return TRUE;
+    }
+  while (potential_child != NULL);
+
+  return FALSE;
+}
+
+gint
+gtk_tree_rbtree_node_find_offset (GtkTreeRBTree *tree,
+                                  GtkTreeRBNode *node)
+{
+  GtkTreeRBNode *last;
+  gint retval;
+
+  g_assert (node);
+  g_assert (node->left);
+
+  retval = node->left->offset;
+
+  while (tree && node && !gtk_tree_rbtree_is_nil (node))
+    {
+      last = node;
+      node = node->parent;
+
+      /* Add left branch, plus children, iff we came from the right */
+      if (node->right == last)
+        retval += node->offset - node->right->offset;
+
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+
+          /* Add the parent node, plus the left branch. */
+          if (node)
+            retval += node->left->offset + GTK_TREE_RBNODE_GET_HEIGHT (node);
+        }
+    }
+  return retval;
+}
+
+guint
+gtk_tree_rbtree_node_get_index (GtkTreeRBTree *tree,
+                                GtkTreeRBNode *node)
+{
+  GtkTreeRBNode *last;
+  guint retval;
+
+  g_assert (node);
+  g_assert (node->left);
+
+  retval = node->left->total_count;
+
+  while (tree && node && !gtk_tree_rbtree_is_nil (node))
+    {
+      last = node;
+      node = node->parent;
+
+      /* Add left branch, plus children, iff we came from the right */
+      if (node->right == last)
+        retval += node->total_count - node->right->total_count;
+
+      if (gtk_tree_rbtree_is_nil (node))
+        {
+          node = tree->parent_node;
+          tree = tree->parent_tree;
+
+          /* Add the parent node, plus the left branch. */
+          if (node)
+            retval += node->left->total_count + 1; /* 1 == GTK_TREE_RBNODE_GET_PARITY() */
+        }
+    }
+
+  return retval;
+}
+
+static gint
+gtk_rbtree_real_find_offset (GtkTreeRBTree  *tree,
+                             gint            height,
+                             GtkTreeRBTree **new_tree,
+                             GtkTreeRBNode **new_node)
+{
+  GtkTreeRBNode *tmp_node;
+
+  g_assert (tree);
+
+  if (height < 0)
+    {
+      *new_tree = NULL;
+      *new_node = NULL;
+
+      return 0;
+    }
+
+
+  tmp_node = tree->root;
+  while (!gtk_tree_rbtree_is_nil (tmp_node) &&
+         (tmp_node->left->offset > height ||
+          (tmp_node->offset - tmp_node->right->offset) < height))
+    {
+      if (tmp_node->left->offset > height)
+        tmp_node = tmp_node->left;
+      else
+        {
+          height -= (tmp_node->offset - tmp_node->right->offset);
+          tmp_node = tmp_node->right;
+        }
+    }
+  if (gtk_tree_rbtree_is_nil (tmp_node))
+    {
+      *new_tree = NULL;
+      *new_node = NULL;
+      return 0;
+    }
+  if (tmp_node->children)
+    {
+      if ((tmp_node->offset -
+           tmp_node->right->offset -
+           tmp_node->children->root->offset) > height)
+        {
+          *new_tree = tree;
+          *new_node = tmp_node;
+          return (height - tmp_node->left->offset);
+        }
+      return gtk_rbtree_real_find_offset (tmp_node->children,
+                                          height - tmp_node->left->offset -
+                                          (tmp_node->offset -
+                                           tmp_node->left->offset -
+                                           tmp_node->right->offset -
+                                           tmp_node->children->root->offset),
+                                          new_tree,
+                                          new_node);
+    }
+  *new_tree = tree;
+  *new_node = tmp_node;
+  return (height - tmp_node->left->offset);
+}
+
+gint
+gtk_tree_rbtree_find_offset (GtkTreeRBTree  *tree,
+                             gint            height,
+                             GtkTreeRBTree **new_tree,
+                             GtkTreeRBNode **new_node)
+{
+  g_assert (tree);
+
+  if ((height < 0) ||
+      (height >= tree->root->offset))
+    {
+      *new_tree = NULL;
+      *new_node = NULL;
+
+      return 0;
+    }
+  return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
+}
+
+gboolean
+gtk_tree_rbtree_find_index (GtkTreeRBTree  *tree,
+                            guint           index,
+                            GtkTreeRBTree **new_tree,
+                            GtkTreeRBNode **new_node)
+{
+  GtkTreeRBNode *tmp_node;
+
+  g_assert (tree);
+
+  tmp_node = tree->root;
+  while (!gtk_tree_rbtree_is_nil (tmp_node))
+    {
+      if (tmp_node->left->total_count > index)
+        {
+          tmp_node = tmp_node->left;
+        }
+      else if (tmp_node->total_count - tmp_node->right->total_count <= index)
+        {
+          index -= tmp_node->total_count - tmp_node->right->total_count;
+          tmp_node = tmp_node->right;
+        }
+      else
+        {
+          index -= tmp_node->left->total_count;
+          break;
+        }
+    }
+  if (gtk_tree_rbtree_is_nil (tmp_node))
+    {
+      *new_tree = NULL;
+      *new_node = NULL;
+      return FALSE;
+    }
+
+  if (index > 0)
+    {
+      g_assert (tmp_node->children);
+
+      return gtk_tree_rbtree_find_index (tmp_node->children,
+                                         index - 1,
+                                         new_tree,
+                                         new_node);
+    }
+
+  *new_tree = tree;
+  *new_node = tmp_node;
+  return TRUE;
+}
+
+void
+gtk_tree_rbtree_remove_node (GtkTreeRBTree *tree,
+                             GtkTreeRBNode *node)
+{
+  GtkTreeRBNode *x, *y;
+  gint y_height;
+  guint y_total_count;
+
+  g_return_if_fail (tree != NULL);
+  g_return_if_fail (node != NULL);
+
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      GString *s;
+
+      s = g_string_new ("");
+      g_string_append_printf (s, "gtk_tree_rbtree_remove_node: %p\n", node);
+      gtk_tree_rbtree_debug_spew (tree, s);
+      g_message ("%s", s->str);
+      g_string_free (s, TRUE);
+      gtk_tree_rbtree_test (G_STRLOC, tree);
+    }
+#endif
+
+  /* make sure we're deleting a node that's actually in the tree */
+  for (x = node; !gtk_tree_rbtree_is_nil (x->parent); x = x->parent)
+    ;
+  g_return_if_fail (x == tree->root);
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    gtk_tree_rbtree_test (G_STRLOC, tree);
+#endif
+
+  if (gtk_tree_rbtree_is_nil (node->left) ||
+      gtk_tree_rbtree_is_nil (node->right))
+    {
+      y = node;
+    }
+  else
+    {
+      y = node->right;
+
+      while (!gtk_tree_rbtree_is_nil (y->left))
+        y = y->left;
+    }
+
+  y_height = GTK_TREE_RBNODE_GET_HEIGHT (y)
+             + (y->children ? y->children->root->offset : 0);
+  y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
+
+  /* x is y's only child, or nil */
+  if (!gtk_tree_rbtree_is_nil (y->left))
+    x = y->left;
+  else
+    x = y->right;
+
+  /* remove y from the parent chain */
+  if (!gtk_tree_rbtree_is_nil (x))
+    x->parent = y->parent;
+  if (!gtk_tree_rbtree_is_nil (y->parent))
+    {
+      if (y == y->parent->left)
+        y->parent->left = x;
+      else
+        y->parent->right = x;
+    }
+  else
+    {
+      tree->root = x;
+    }
+
+  /* We need to clean up the validity of the tree.
+   */
+  gtk_rbnode_adjust (tree, y, -1, -y_total_count, -y_height);
+
+  if (GTK_TREE_RBNODE_GET_COLOR (y) == GTK_TREE_RBNODE_BLACK)
+    gtk_tree_rbtree_remove_node_fixup (tree, x, y->parent);
+
+  if (y != node)
+    {
+      gint node_height, node_total_count;
+
+      /* We want to see how much we remove from the aggregate values.
+       * This is all the children we remove plus the node's values.
+       */
+      node_height = GTK_TREE_RBNODE_GET_HEIGHT (node)
+                    + (node->children ? node->children->root->offset : 0);
+      node_total_count = 1
+                         + (node->children ? node->children->root->total_count : 0);
+
+      /* Move the node over */
+      if (GTK_TREE_RBNODE_GET_COLOR (node) != GTK_TREE_RBNODE_GET_COLOR (y))
+        y->flags ^= (GTK_TREE_RBNODE_BLACK | GTK_TREE_RBNODE_RED);
+
+      y->left = node->left;
+      if (!gtk_tree_rbtree_is_nil (y->left))
+        y->left->parent = y;
+      y->right = node->right;
+      if (!gtk_tree_rbtree_is_nil (y->right))
+        y->right->parent = y;
+      y->parent = node->parent;
+      if (!gtk_tree_rbtree_is_nil (y->parent))
+        {
+          if (y->parent->left == node)
+            y->parent->left = y;
+          else
+            y->parent->right = y;
+        }
+      else
+        {
+          tree->root = y;
+        }
+      y->count = node->count;
+      y->total_count = node->total_count;
+      y->offset = node->offset;
+
+      gtk_rbnode_adjust (tree, y,
+                         0,
+                         y_total_count - node_total_count,
+                         y_height - node_height);
+    }
+
+  gtk_tree_rbnode_free (node);
+
+#ifdef G_ENABLE_DEBUG
+  if (GTK_DEBUG_CHECK (TREE))
+    {
+      GString *s;
+
+      s = g_string_new ("gtk_tree_rbtree_remove_node finished...\n");
+      gtk_tree_rbtree_debug_spew (tree, s);
+      g_message ("%s", s->str);
+      g_string_free (s, TRUE);
+      gtk_tree_rbtree_test (G_STRLOC, tree);
+    }
+#endif
+}
+
+GtkTreeRBNode *
+gtk_tree_rbtree_first (GtkTreeRBTree *tree)
+{
+  GtkTreeRBNode *node;
+
+  node = tree->root;
+
+  if (gtk_tree_rbtree_is_nil (node))
+    return NULL;
+
+  while (!gtk_tree_rbtree_is_nil (node->left))
+    node = node->left;
+
+  return node;
+}
+
+GtkTreeRBNode *
+gtk_tree_rbtree_next (GtkTreeRBTree *tree,
+                      GtkTreeRBNode *node)
+{
+  g_return_val_if_fail (tree != NULL, NULL);
+  g_return_val_if_fail (node != NULL, NULL);
+
+  /* Case 1: the node's below us. */
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    {
+      node = node->right;
+      while (!gtk_tree_rbtree_is_nil (node->left))
+        node = node->left;
+      return node;
+    }
+
+  /* Case 2: it's an ancestor */
+  while (!gtk_tree_rbtree_is_nil (node->parent))
+    {
+      if (node->parent->right == node)
+        node = node->parent;
+      else
+        return (node->parent);
+    }
+
+  /* Case 3: There is no next node */
+  return NULL;
+}
+
+GtkTreeRBNode *
+gtk_tree_rbtree_prev (GtkTreeRBTree *tree,
+                      GtkTreeRBNode *node)
+{
+  g_return_val_if_fail (tree != NULL, NULL);
+  g_return_val_if_fail (node != NULL, NULL);
+
+  /* Case 1: the node's below us. */
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    {
+      node = node->left;
+      while (!gtk_tree_rbtree_is_nil (node->right))
+        node = node->right;
+      return node;
+    }
+
+  /* Case 2: it's an ancestor */
+  while (!gtk_tree_rbtree_is_nil (node->parent))
+    {
+      if (node->parent->left == node)
+        node = node->parent;
+      else
+        return (node->parent);
+    }
+
+  /* Case 3: There is no next node */
+  return NULL;
+}
+
+void
+gtk_tree_rbtree_next_full (GtkTreeRBTree  *tree,
+                           GtkTreeRBNode  *node,
+                           GtkTreeRBTree **new_tree,
+                           GtkTreeRBNode **new_node)
+{
+  g_return_if_fail (tree != NULL);
+  g_return_if_fail (node != NULL);
+  g_return_if_fail (new_tree != NULL);
+  g_return_if_fail (new_node != NULL);
+
+  if (node->children)
+    {
+      *new_tree = node->children;
+      *new_node = (*new_tree)->root;
+      while (!gtk_tree_rbtree_is_nil ((*new_node)->left))
+        *new_node = (*new_node)->left;
+      return;
+    }
+
+  *new_tree = tree;
+  *new_node = gtk_tree_rbtree_next (tree, node);
+
+  while ((*new_node == NULL) &&
+         (*new_tree != NULL))
+    {
+      *new_node = (*new_tree)->parent_node;
+      *new_tree = (*new_tree)->parent_tree;
+      if (*new_tree)
+        *new_node = gtk_tree_rbtree_next (*new_tree, *new_node);
+    }
+}
+
+void
+gtk_tree_rbtree_prev_full (GtkTreeRBTree  *tree,
+                           GtkTreeRBNode  *node,
+                           GtkTreeRBTree **new_tree,
+                           GtkTreeRBNode **new_node)
+{
+  g_return_if_fail (tree != NULL);
+  g_return_if_fail (node != NULL);
+  g_return_if_fail (new_tree != NULL);
+  g_return_if_fail (new_node != NULL);
+
+  *new_tree = tree;
+  *new_node = gtk_tree_rbtree_prev (tree, node);
+
+  if (*new_node == NULL)
+    {
+      *new_node = (*new_tree)->parent_node;
+      *new_tree = (*new_tree)->parent_tree;
+    }
+  else
+    {
+      while ((*new_node)->children)
+        {
+          *new_tree = (*new_node)->children;
+          *new_node = (*new_tree)->root;
+          while (!gtk_tree_rbtree_is_nil ((*new_node)->right))
+            *new_node = (*new_node)->right;
+        }
+    }
+}
+
+gint
+gtk_tree_rbtree_get_depth (GtkTreeRBTree *tree)
+{
+  GtkTreeRBTree *tmp_tree;
+  gint depth = 0;
+
+  tmp_tree = tree->parent_tree;
+  while (tmp_tree)
+    {
+      ++depth;
+      tmp_tree = tmp_tree->parent_tree;
+    }
+
+  return depth;
+}
+
+static void
+gtk_tree_rbtree_traverse_pre_order (GtkTreeRBTree            *tree,
+                                    GtkTreeRBNode            *node,
+                                    GtkTreeRBTreeTraverseFunc func,
+                                    gpointer                  data)
+{
+  if (gtk_tree_rbtree_is_nil (node))
+    return;
+
+  (*func)(tree, node, data);
+  gtk_tree_rbtree_traverse_pre_order (tree, node->left, func, data);
+  gtk_tree_rbtree_traverse_pre_order (tree, node->right, func, data);
+}
+
+static void
+gtk_tree_rbtree_traverse_post_order (GtkTreeRBTree            *tree,
+                                     GtkTreeRBNode            *node,
+                                     GtkTreeRBTreeTraverseFunc func,
+                                     gpointer                  data)
+{
+  if (gtk_tree_rbtree_is_nil (node))
+    return;
+
+  gtk_tree_rbtree_traverse_post_order (tree, node->left, func, data);
+  gtk_tree_rbtree_traverse_post_order (tree, node->right, func, data);
+  (*func)(tree, node, data);
+}
+
+void
+gtk_tree_rbtree_traverse (GtkTreeRBTree            *tree,
+                          GtkTreeRBNode            *node,
+                          GTraverseType             order,
+                          GtkTreeRBTreeTraverseFunc func,
+                          gpointer                  data)
+{
+  g_return_if_fail (tree != NULL);
+  g_return_if_fail (node != NULL);
+  g_return_if_fail (func != NULL);
+  g_return_if_fail (order <= G_LEVEL_ORDER);
+
+  switch (order)
+    {
+    case G_PRE_ORDER:
+      gtk_tree_rbtree_traverse_pre_order (tree, node, func, data);
+      break;
+
+    case G_POST_ORDER:
+      gtk_tree_rbtree_traverse_post_order (tree, node, func, data);
+      break;
+
+    case G_IN_ORDER:
+    case G_LEVEL_ORDER:
+    default:
+      g_warning ("unsupported traversal order.");
+      break;
+    }
+}
+
+static inline
+void fixup_validation (GtkTreeRBTree *tree,
+                       GtkTreeRBNode *node)
+{
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+      GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) ||
+      GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
+      GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
+      (node->children != NULL && GTK_TREE_RBNODE_FLAG_SET (node->children->root, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID)))
+    {
+      GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+    }
+  else
+    {
+      GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
+    }
+}
+
+static inline
+void fixup_total_count (GtkTreeRBTree *tree,
+                        GtkTreeRBNode *node)
+{
+  node->total_count = 1 +
+                      (node->children != NULL ? node->children->root->total_count : 0) +
+                      node->left->total_count + node->right->total_count;
+}
+
+#ifdef G_ENABLE_DEBUG
+static guint
+get_total_count (GtkTreeRBNode *node)
+{
+  guint child_total = 0;
+
+  child_total += (guint) node->left->total_count;
+  child_total += (guint) node->right->total_count;
+
+  if (node->children)
+    child_total += (guint) node->children->root->total_count;
+
+  return child_total + 1;
+}
+
+static guint
+count_total (GtkTreeRBTree *tree,
+             GtkTreeRBNode *node)
+{
+  guint res;
+
+  if (gtk_tree_rbtree_is_nil (node))
+    return 0;
+
+  res =
+    count_total (tree, node->left) +
+    count_total (tree, node->right) +
+    (guint) 1 +
+    (node->children ? count_total (node->children, node->children->root) : 0);
+
+  if (res != node->total_count)
+    g_error ("total count incorrect for node");
+
+  if (get_total_count (node) != node->total_count)
+    g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
+
+  return res;
+}
+
+static gint
+_count_nodes (GtkTreeRBTree *tree,
+              GtkTreeRBNode *node)
+{
+  gint res;
+  if (gtk_tree_rbtree_is_nil (node))
+    return 0;
+
+  g_assert (node->left);
+  g_assert (node->right);
+
+  res = (_count_nodes (tree, node->left) +
+         _count_nodes (tree, node->right) + 1);
+
+  if (res != node->count)
+    g_error ("Tree failed");
+  return res;
+}
+
+static void
+gtk_tree_rbtree_test_height (GtkTreeRBTree *tree,
+                             GtkTreeRBNode *node)
+{
+  gint computed_offset = 0;
+
+  /* This whole test is sort of a useless truism. */
+
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    computed_offset += node->left->offset;
+
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    computed_offset += node->right->offset;
+
+  if (node->children && !gtk_tree_rbtree_is_nil (node->children->root))
+    computed_offset += node->children->root->offset;
+
+  if (GTK_TREE_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
+    g_error ("node has broken offset");
+
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    gtk_tree_rbtree_test_height (tree, node->left);
+
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    gtk_tree_rbtree_test_height (tree, node->right);
+
+  if (node->children && !gtk_tree_rbtree_is_nil (node->children->root))
+    gtk_tree_rbtree_test_height (node->children, node->children->root);
+}
+
+static void
+gtk_tree_rbtree_test_dirty (GtkTreeRBTree *tree,
+                            GtkTreeRBNode *node,
+                            gint           expected_dirtyness)
+{
+  if (expected_dirtyness)
+    {
+      g_assert (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) ||
+                GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+                GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
+                GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
+                (node->children && GTK_TREE_RBNODE_FLAG_SET (node->children->root, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID)));
+    }
+  else
+    {
+      g_assert (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) &&
+                !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID));
+      if (!gtk_tree_rbtree_is_nil (node->left))
+        g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+      if (!gtk_tree_rbtree_is_nil (node->right))
+        g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+      if (node->children != NULL)
+        g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+    }
+
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    gtk_tree_rbtree_test_dirty (tree, node->left, GTK_TREE_RBNODE_FLAG_SET (node->left, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    gtk_tree_rbtree_test_dirty (tree, node->right, GTK_TREE_RBNODE_FLAG_SET (node->right, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+  if (node->children != NULL && !gtk_tree_rbtree_is_nil (node->children->root))
+    gtk_tree_rbtree_test_dirty (node->children, node->children->root, GTK_TREE_RBNODE_FLAG_SET 
(node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+}
+
+static void gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree);
+
+static void
+gtk_tree_rbtree_test_structure_helper (GtkTreeRBTree *tree,
+                                       GtkTreeRBNode *node)
+{
+  g_assert (!gtk_tree_rbtree_is_nil (node));
+
+  g_assert (node->left != NULL);
+  g_assert (node->right != NULL);
+  g_assert (node->parent != NULL);
+
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    {
+      g_assert (node->left->parent == node);
+      gtk_tree_rbtree_test_structure_helper (tree, node->left);
+    }
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    {
+      g_assert (node->right->parent == node);
+      gtk_tree_rbtree_test_structure_helper (tree, node->right);
+    }
+
+  if (node->children != NULL)
+    {
+      g_assert (node->children->parent_tree == tree);
+      g_assert (node->children->parent_node == node);
+
+      gtk_tree_rbtree_test_structure (node->children);
+    }
+}
+static void
+gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree)
+{
+  g_assert (tree->root);
+  if (gtk_tree_rbtree_is_nil (tree->root))
+    return;
+
+  g_assert (gtk_tree_rbtree_is_nil (tree->root->parent));
+  gtk_tree_rbtree_test_structure_helper (tree, tree->root);
+}
+
+static void
+gtk_tree_rbtree_test (const gchar   *where,
+                      GtkTreeRBTree *tree)
+{
+  GtkTreeRBTree *tmp_tree;
+
+  if (tree == NULL)
+    return;
+
+  /* Test the entire tree */
+  tmp_tree = tree;
+  while (tmp_tree->parent_tree)
+    tmp_tree = tmp_tree->parent_tree;
+
+  if (gtk_tree_rbtree_is_nil (tmp_tree->root))
+    return;
+
+  gtk_tree_rbtree_test_structure (tmp_tree);
+
+  g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
+             _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
+
+
+  gtk_tree_rbtree_test_height (tmp_tree, tmp_tree->root);
+  gtk_tree_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_TREE_RBNODE_FLAG_SET (tmp_tree->root, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+  g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
+}
+
+static void
+gtk_tree_rbtree_debug_spew_helper (GtkTreeRBTree *tree,
+                                   GtkTreeRBNode *node,
+                                   GString       *s,
+                                   gint           depth)
+{
+  gint i;
+  for (i = 0; i < depth; i++)
+    g_string_append (s, "\t");
+
+  g_string_append_printf (s, "(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
+                          node,
+                          (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK) ? "BLACK" : " RED ",
+                          node->offset,
+                          node->total_count,
+                          (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ? 1 : 0,
+                          (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) ? 1 : 0,
+                          (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)) ? 1 : 0);
+  if (node->children != NULL)
+    {
+      g_string_append (s, "Looking at child.\n");
+      gtk_tree_rbtree_debug_spew (node->children, s);
+      g_string_append (s, "Done looking at child.\n");
+    }
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    {
+      gtk_tree_rbtree_debug_spew_helper (tree, node->left, s, depth + 1);
+    }
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    {
+      gtk_tree_rbtree_debug_spew_helper (tree, node->right, s, depth + 1);
+    }
+}
+
+static void
+gtk_tree_rbtree_debug_spew (GtkTreeRBTree *tree,
+                            GString       *s)
+{
+  g_return_if_fail (tree != NULL);
+
+  if (gtk_tree_rbtree_is_nil (tree->root))
+    g_string_append (s, "Empty tree...");
+  else
+    gtk_tree_rbtree_debug_spew_helper (tree, tree->root, s, 0);
+}
+#endif /* G_ENABLE_DEBUG */
diff --git a/gtk/gtktreerbtreeprivate.h b/gtk/gtktreerbtreeprivate.h
new file mode 100644
index 0000000000..3dece561f5
--- /dev/null
+++ b/gtk/gtktreerbtreeprivate.h
@@ -0,0 +1,172 @@
+/* gtkrbtreeprivate.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, see <http://www.gnu.org/licenses/>.
+ */
+
+/* A Red-Black Tree implementation used specifically by GtkTreeView.
+ */
+#ifndef __GTK_TREE_RBTREE_PRIVATE_H__
+#define __GTK_TREE_RBTREE_PRIVATE_H__
+
+#include <glib.h>
+
+
+G_BEGIN_DECLS
+
+
+typedef enum
+{
+  GTK_TREE_RBNODE_BLACK = 1 << 0,
+  GTK_TREE_RBNODE_RED = 1 << 1,
+  GTK_TREE_RBNODE_IS_PARENT = 1 << 2,
+  GTK_TREE_RBNODE_IS_SELECTED = 1 << 3,
+  GTK_TREE_RBNODE_IS_PRELIT = 1 << 4,
+  GTK_TREE_RBNODE_INVALID = 1 << 7,
+  GTK_TREE_RBNODE_COLUMN_INVALID = 1 << 8,
+  GTK_TREE_RBNODE_DESCENDANTS_INVALID = 1 << 9,
+  GTK_TREE_RBNODE_NON_COLORS = GTK_TREE_RBNODE_IS_PARENT |
+                            GTK_TREE_RBNODE_IS_SELECTED |
+                            GTK_TREE_RBNODE_IS_PRELIT |
+                          GTK_TREE_RBNODE_INVALID |
+                          GTK_TREE_RBNODE_COLUMN_INVALID |
+                          GTK_TREE_RBNODE_DESCENDANTS_INVALID
+} GtkTreeRBNodeColor;
+
+typedef struct _GtkTreeRBTree GtkTreeRBTree;
+typedef struct _GtkTreeRBNode GtkTreeRBNode;
+typedef struct _GtkTreeRBTreeView GtkTreeRBTreeView;
+
+typedef void (*GtkTreeRBTreeTraverseFunc) (GtkTreeRBTree  *tree,
+                                       GtkTreeRBNode  *node,
+                                       gpointer  data);
+
+struct _GtkTreeRBTree
+{
+  GtkTreeRBNode *root;
+  GtkTreeRBTree *parent_tree;
+  GtkTreeRBNode *parent_node;
+};
+
+struct _GtkTreeRBNode
+{
+  guint flags : 14;
+
+  /* count is the number of nodes beneath us, plus 1 for ourselves.
+   * i.e. node->left->count + node->right->count + 1
+   */
+  gint count;
+
+  GtkTreeRBNode *left;
+  GtkTreeRBNode *right;
+  GtkTreeRBNode *parent;
+
+  /* count the number of total nodes beneath us, including nodes
+   * of children trees.
+   * i.e. node->left->count + node->right->count + node->children->root->count + 1
+   */
+  guint total_count;
+  
+  /* 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.
+   */
+  gint offset;
+
+  /* Child trees */
+  GtkTreeRBTree *children;
+};
+
+
+#define GTK_TREE_RBNODE_GET_COLOR(node)                
(node?(((node->flags&GTK_TREE_RBNODE_RED)==GTK_TREE_RBNODE_RED)?GTK_TREE_RBNODE_RED:GTK_TREE_RBNODE_BLACK):GTK_TREE_RBNODE_BLACK)
+#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)
+#define GTK_TREE_RBNODE_GET_HEIGHT(node)                 
(node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
+#define GTK_TREE_RBNODE_SET_FLAG(node, flag)           G_STMT_START{ (node->flags|=flag); }G_STMT_END
+#define GTK_TREE_RBNODE_UNSET_FLAG(node, flag)         G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
+#define GTK_TREE_RBNODE_FLAG_SET(node, flag)         (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
+
+
+GtkTreeRBTree * gtk_tree_rbtree_new                     (void);
+void            gtk_tree_rbtree_free                    (GtkTreeRBTree                 *tree);
+void            gtk_tree_rbtree_remove                  (GtkTreeRBTree                 *tree);
+void            gtk_tree_rbtree_destroy                 (GtkTreeRBTree                 *tree);
+GtkTreeRBNode * gtk_tree_rbtree_insert_before           (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node,
+                                                         gint                           height,
+                                                         gboolean                       valid);
+GtkTreeRBNode * gtk_tree_rbtree_insert_after            (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node,
+                                                         gint                           height,
+                                                         gboolean                       valid);
+void            gtk_tree_rbtree_remove_node             (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+gboolean        gtk_tree_rbtree_is_nil                  (GtkTreeRBNode                 *node);
+void            gtk_tree_rbtree_reorder                 (GtkTreeRBTree                 *tree,
+                                                         gint                          *new_order,
+                                                         gint                           length);
+gboolean        gtk_tree_rbtree_contains                (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBTree                 *potential_child);
+GtkTreeRBNode * gtk_tree_rbtree_find_count              (GtkTreeRBTree                 *tree,
+                                                         gint                           count);
+void            gtk_tree_rbtree_node_set_height         (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node,
+                                                         gint                           height);
+void            gtk_tree_rbtree_node_mark_invalid       (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+void            gtk_tree_rbtree_node_mark_valid         (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+void            gtk_tree_rbtree_column_invalid          (GtkTreeRBTree                 *tree);
+void            gtk_tree_rbtree_mark_invalid            (GtkTreeRBTree                 *tree);
+void            gtk_tree_rbtree_set_fixed_height        (GtkTreeRBTree                 *tree,
+                                                         gint                           height,
+                                                         gboolean                       mark_valid);
+gint            gtk_tree_rbtree_node_find_offset        (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+guint           gtk_tree_rbtree_node_get_index          (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+gboolean        gtk_tree_rbtree_find_index              (GtkTreeRBTree                 *tree,
+                                                         guint                          index,
+                                                         GtkTreeRBTree                **new_tree,
+                                                         GtkTreeRBNode                **new_node);
+gint            gtk_tree_rbtree_find_offset             (GtkTreeRBTree                 *tree,
+                                                         gint                           offset,
+                                                         GtkTreeRBTree                **new_tree,
+                                                         GtkTreeRBNode                **new_node);
+void            gtk_tree_rbtree_traverse                (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node,
+                                                         GTraverseType                  order,
+                                                         GtkTreeRBTreeTraverseFunc      func,
+                                                         gpointer                       data);
+GtkTreeRBNode * gtk_tree_rbtree_first                   (GtkTreeRBTree                 *tree);
+GtkTreeRBNode * gtk_tree_rbtree_next                    (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+GtkTreeRBNode * gtk_tree_rbtree_prev                    (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node);
+void            gtk_tree_rbtree_next_full               (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node,
+                                                         GtkTreeRBTree                **new_tree,
+                                                         GtkTreeRBNode                **new_node);
+void            gtk_tree_rbtree_prev_full               (GtkTreeRBTree                 *tree,
+                                                         GtkTreeRBNode                 *node,
+                                                         GtkTreeRBTree                **new_tree,
+                                                         GtkTreeRBNode                **new_node);
+
+gint            gtk_tree_rbtree_get_depth               (GtkTreeRBTree                 *tree);
+
+
+G_END_DECLS
+
+
+#endif /* __GTK_TREE_RBTREE_PRIVATE_H__ */
diff --git a/gtk/gtktreeselection.c b/gtk/gtktreeselection.c
index a3ffdc0258..107a25aa94 100644
--- a/gtk/gtktreeselection.c
+++ b/gtk/gtktreeselection.c
@@ -19,7 +19,7 @@
 #include <string.h>
 #include "gtktreeselection.h"
 #include "gtktreeprivate.h"
-#include "gtkrbtreeprivate.h"
+#include "gtktreerbtreeprivate.h"
 #include "gtkmarshalers.h"
 #include "gtkintl.h"
 #include "gtkprivate.h"
@@ -74,8 +74,8 @@ static void gtk_tree_selection_finalize          (GObject               *object)
 static gint gtk_tree_selection_real_select_all   (GtkTreeSelection      *selection);
 static gint gtk_tree_selection_real_unselect_all (GtkTreeSelection      *selection);
 static gint gtk_tree_selection_real_select_node  (GtkTreeSelection      *selection,
-                                                 GtkRBTree             *tree,
-                                                 GtkRBNode             *node,
+                                                 GtkTreeRBTree         *tree,
+                                                 GtkTreeRBNode         *node,
                                                  gboolean               select);
 static void gtk_tree_selection_set_property      (GObject               *object,
                                                   guint                  prop_id,
@@ -313,8 +313,8 @@ gtk_tree_selection_set_mode (GtkTreeSelection *selection,
   else if (type == GTK_SELECTION_SINGLE ||
           type == GTK_SELECTION_BROWSE)
     {
-      GtkRBTree *tree = NULL;
-      GtkRBNode *node = NULL;
+      GtkTreeRBTree *tree = NULL;
+      GtkTreeRBNode *node = NULL;
       gint selected = FALSE;
       GtkTreePath *anchor_path = NULL;
 
@@ -327,7 +327,7 @@ gtk_tree_selection_set_mode (GtkTreeSelection *selection,
                                    &tree,
                                    &node);
          
-         if (node && GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+         if (node && GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
            selected = TRUE;
        }
 
@@ -473,8 +473,8 @@ gtk_tree_selection_get_selected (GtkTreeSelection  *selection,
                                 GtkTreeIter       *iter)
 {
   GtkTreeSelectionPrivate *priv;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GtkTreePath *anchor_path;
   gboolean retval = FALSE;
   gboolean found_node;
@@ -503,7 +503,7 @@ gtk_tree_selection_get_selected (GtkTreeSelection  *selection,
                                           &tree,
                                           &node);
 
-  if (found_node && GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+  if (found_node && GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     {
       /* we only want to return the anchor if it exists in the rbtree and
        * is selected.
@@ -550,8 +550,8 @@ gtk_tree_selection_get_selected_rows (GtkTreeSelection   *selection,
 {
   GtkTreeSelectionPrivate *priv;
   GList *list = NULL;
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
   GtkTreePath *path;
 
   g_return_val_if_fail (GTK_IS_TREE_SELECTION (selection), NULL);
@@ -585,18 +585,18 @@ gtk_tree_selection_get_selected_rows (GtkTreeSelection   *selection,
       return NULL;
     }
 
-  node = _gtk_rbtree_first (tree);
+  node = gtk_tree_rbtree_first (tree);
   path = gtk_tree_path_new_first ();
 
   while (node != NULL)
     {
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
        list = g_list_prepend (list, gtk_tree_path_copy (path));
 
       if (node->children)
         {
          tree = node->children;
-          node = _gtk_rbtree_first (tree);
+          node = gtk_tree_rbtree_first (tree);
 
          gtk_tree_path_append_index (path, 0);
        }
@@ -606,7 +606,7 @@ gtk_tree_selection_get_selected_rows (GtkTreeSelection   *selection,
 
          do
            {
-             node = _gtk_rbtree_next (tree, node);
+             node = gtk_tree_rbtree_next (tree, node);
              if (node != NULL)
                {
                  done = TRUE;
@@ -638,21 +638,21 @@ gtk_tree_selection_get_selected_rows (GtkTreeSelection   *selection,
 }
 
 static void
-gtk_tree_selection_count_selected_rows_helper (GtkRBTree *tree,
-                                              GtkRBNode *node,
-                                              gpointer   data)
+gtk_tree_selection_count_selected_rows_helper (GtkTreeRBTree *tree,
+                                               GtkTreeRBNode *node,
+                                               gpointer       data)
 {
   gint *count = (gint *)data;
 
   g_return_if_fail (node != NULL);
 
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     (*count)++;
 
   if (node->children)
-    _gtk_rbtree_traverse (node->children, node->children->root,
-                         G_PRE_ORDER,
-                         gtk_tree_selection_count_selected_rows_helper, data);
+    gtk_tree_rbtree_traverse (node->children, node->children->root,
+                              G_PRE_ORDER,
+                              gtk_tree_selection_count_selected_rows_helper, data);
 }
 
 /**
@@ -668,7 +668,7 @@ gtk_tree_selection_count_selected_rows (GtkTreeSelection *selection)
 {
   GtkTreeSelectionPrivate *priv;
   gint count = 0;
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
   g_return_val_if_fail (GTK_IS_TREE_SELECTION (selection), 0);
 
@@ -685,15 +685,15 @@ gtk_tree_selection_count_selected_rows (GtkTreeSelection *selection)
       priv->type == GTK_SELECTION_BROWSE)
     {
       if (gtk_tree_selection_get_selected (selection, NULL, NULL))
-       return 1;
+        return 1;
       else
-       return 0;
+        return 0;
     }
 
-  _gtk_rbtree_traverse (tree, tree->root,
-                       G_PRE_ORDER,
-                       gtk_tree_selection_count_selected_rows_helper,
-                       &count);
+  gtk_tree_rbtree_traverse (tree, tree->root,
+                            G_PRE_ORDER,
+                            gtk_tree_selection_count_selected_rows_helper,
+                            &count);
 
   return count;
 }
@@ -724,8 +724,8 @@ gtk_tree_selection_selected_foreach (GtkTreeSelection            *selection,
 {
   GtkTreeSelectionPrivate *priv;
   GtkTreePath *path;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GtkTreeIter iter;
   GtkTreeModel *model;
 
@@ -759,7 +759,7 @@ gtk_tree_selection_selected_foreach (GtkTreeSelection            *selection,
       return;
     }
 
-  node = _gtk_rbtree_first (tree);
+  node = gtk_tree_rbtree_first (tree);
 
   g_object_ref (model);
 
@@ -782,7 +782,7 @@ gtk_tree_selection_selected_foreach (GtkTreeSelection            *selection,
 
   while (node != NULL)
     {
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
         {
           gtk_tree_model_get_iter (model, &iter, path);
          (* func) (model, path, &iter, data);
@@ -794,7 +794,7 @@ gtk_tree_selection_selected_foreach (GtkTreeSelection            *selection,
       if (node->children)
        {
          tree = node->children;
-          node = _gtk_rbtree_first (tree);
+          node = gtk_tree_rbtree_first (tree);
 
          gtk_tree_path_append_index (path, 0);
        }
@@ -804,7 +804,7 @@ gtk_tree_selection_selected_foreach (GtkTreeSelection            *selection,
 
          do
            {
-             node = _gtk_rbtree_next (tree, node);
+             node = gtk_tree_rbtree_next (tree, node);
              if (node != NULL)
                {
                  done = TRUE;
@@ -857,11 +857,11 @@ out:
  **/
 void
 gtk_tree_selection_select_path (GtkTreeSelection *selection,
-                               GtkTreePath      *path)
+                                GtkTreePath      *path)
 {
   GtkTreeSelectionPrivate *priv;
-  GtkRBNode *node;
-  GtkRBTree *tree;
+  GtkTreeRBNode *node;
+  GtkTreeRBTree *tree;
   gboolean ret;
   GtkTreeSelectMode mode = 0;
 
@@ -877,7 +877,7 @@ gtk_tree_selection_select_path (GtkTreeSelection *selection,
                                  &tree,
                                  &node);
 
-  if (node == NULL || GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED) ||
+  if (node == NULL || GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED) ||
       ret == TRUE)
     return;
 
@@ -904,8 +904,8 @@ gtk_tree_selection_unselect_path (GtkTreeSelection *selection,
                                  GtkTreePath      *path)
 {
   GtkTreeSelectionPrivate *priv;
-  GtkRBNode *node;
-  GtkRBTree *tree;
+  GtkTreeRBNode *node;
+  GtkTreeRBTree *tree;
   gboolean ret;
 
   g_return_if_fail (GTK_IS_TREE_SELECTION (selection));
@@ -920,7 +920,7 @@ gtk_tree_selection_unselect_path (GtkTreeSelection *selection,
                                  &tree,
                                  &node);
 
-  if (node == NULL || !GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED) ||
+  if (node == NULL || !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED) ||
       ret == TRUE)
     return;
 
@@ -1016,8 +1016,8 @@ gtk_tree_selection_path_is_selected (GtkTreeSelection *selection,
                                     GtkTreePath      *path)
 {
   GtkTreeSelectionPrivate *priv;
-  GtkRBNode *node;
-  GtkRBTree *tree;
+  GtkTreeRBNode *node;
+  GtkTreeRBTree *tree;
   gboolean ret;
 
   g_return_val_if_fail (GTK_IS_TREE_SELECTION (selection), FALSE);
@@ -1035,7 +1035,7 @@ gtk_tree_selection_path_is_selected (GtkTreeSelection *selection,
                                  &tree,
                                  &node);
 
-  if ((node == NULL) || !GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED) ||
+  if ((node == NULL) || !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED) ||
       ret == TRUE)
     return FALSE;
 
@@ -1088,19 +1088,19 @@ struct _TempTuple {
 };
 
 static void
-select_all_helper (GtkRBTree  *tree,
-                  GtkRBNode  *node,
+select_all_helper (GtkTreeRBTree  *tree,
+                  GtkTreeRBNode  *node,
                   gpointer    data)
 {
   struct _TempTuple *tuple = data;
 
   if (node->children)
-    _gtk_rbtree_traverse (node->children,
+    gtk_tree_rbtree_traverse (node->children,
                          node->children->root,
                          G_PRE_ORDER,
                          select_all_helper,
                          data);
-  if (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+  if (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     {
       tuple->dirty = gtk_tree_selection_real_select_node (tuple->selection, tree, node, TRUE) || 
tuple->dirty;
     }
@@ -1115,7 +1115,7 @@ gtk_tree_selection_real_select_all (GtkTreeSelection *selection)
 {
   GtkTreeSelectionPrivate *priv = selection->priv;
   struct _TempTuple *tuple;
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
   tree = _gtk_tree_view_get_rbtree (priv->tree_view);
 
@@ -1127,10 +1127,10 @@ gtk_tree_selection_real_select_all (GtkTreeSelection *selection)
   tuple->selection = selection;
   tuple->dirty = FALSE;
 
-  _gtk_rbtree_traverse (tree, tree->root,
-                       G_PRE_ORDER,
-                       select_all_helper,
-                       tuple);
+  gtk_tree_rbtree_traverse (tree, tree->root,
+                            G_PRE_ORDER,
+                            select_all_helper,
+                            tuple);
   if (tuple->dirty)
     {
       g_free (tuple);
@@ -1169,19 +1169,19 @@ gtk_tree_selection_select_all (GtkTreeSelection *selection)
 }
 
 static void
-unselect_all_helper (GtkRBTree  *tree,
-                    GtkRBNode  *node,
-                    gpointer    data)
+unselect_all_helper (GtkTreeRBTree *tree,
+                     GtkTreeRBNode *node,
+                     gpointer       data)
 {
   struct _TempTuple *tuple = data;
 
   if (node->children)
-    _gtk_rbtree_traverse (node->children,
-                         node->children->root,
-                         G_PRE_ORDER,
-                         unselect_all_helper,
-                         data);
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+    gtk_tree_rbtree_traverse (node->children,
+                              node->children->root,
+                              G_PRE_ORDER,
+                              unselect_all_helper,
+                              data);
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     {
       tuple->dirty = gtk_tree_selection_real_select_node (tuple->selection, tree, node, FALSE) || 
tuple->dirty;
     }
@@ -1196,8 +1196,8 @@ gtk_tree_selection_real_unselect_all (GtkTreeSelection *selection)
   if (priv->type == GTK_SELECTION_SINGLE ||
       priv->type == GTK_SELECTION_BROWSE)
     {
-      GtkRBTree *tree = NULL;
-      GtkRBNode *node = NULL;
+      GtkTreeRBTree *tree = NULL;
+      GtkTreeRBNode *node = NULL;
       GtkTreePath *anchor_path;
 
       anchor_path = _gtk_tree_view_get_anchor_path (priv->tree_view);
@@ -1215,7 +1215,7 @@ gtk_tree_selection_real_unselect_all (GtkTreeSelection *selection)
       if (tree == NULL)
         return FALSE;
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
        {
          if (gtk_tree_selection_real_select_node (selection, tree, node, FALSE))
            {
@@ -1227,17 +1227,17 @@ gtk_tree_selection_real_unselect_all (GtkTreeSelection *selection)
     }
   else
     {
-      GtkRBTree *tree;
+      GtkTreeRBTree *tree;
 
       tuple = g_new (struct _TempTuple, 1);
       tuple->selection = selection;
       tuple->dirty = FALSE;
 
       tree = _gtk_tree_view_get_rbtree (priv->tree_view);
-      _gtk_rbtree_traverse (tree, tree->root,
-                            G_PRE_ORDER,
-                            unselect_all_helper,
-                            tuple);
+      gtk_tree_rbtree_traverse (tree, tree->root,
+                                G_PRE_ORDER,
+                                unselect_all_helper,
+                                tuple);
 
       if (tuple->dirty)
         {
@@ -1287,8 +1287,8 @@ gtk_tree_selection_real_modify_range (GtkTreeSelection *selection,
                                      GtkTreePath      *end_path)
 {
   GtkTreeSelectionPrivate *priv = selection->priv;
-  GtkRBNode *start_node = NULL, *end_node = NULL;
-  GtkRBTree *start_tree, *end_tree;
+  GtkTreeRBNode *start_node = NULL, *end_node = NULL;
+  GtkTreeRBTree *start_tree, *end_tree;
   GtkTreePath *anchor_path = NULL;
   gboolean dirty = FALSE;
 
@@ -1347,11 +1347,11 @@ gtk_tree_selection_real_modify_range (GtkTreeSelection *selection,
       if (start_node->children)
        {
          start_tree = start_node->children;
-          start_node = _gtk_rbtree_first (start_tree);
+          start_node = gtk_tree_rbtree_first (start_tree);
        }
       else
        {
-         _gtk_rbtree_next_full (start_tree, start_node, &start_tree, &start_node);
+         gtk_tree_rbtree_next_full (start_tree, start_node, &start_tree, &start_node);
          if (start_tree == NULL)
            {
              /* we just ran out of tree.  That means someone passed in bogus values.
@@ -1422,8 +1422,8 @@ gtk_tree_selection_unselect_range (GtkTreeSelection *selection,
 
 gboolean
 _gtk_tree_selection_row_is_selectable (GtkTreeSelection *selection,
-                                      GtkRBNode        *node,
-                                      GtkTreePath      *path)
+                                       GtkTreeRBNode    *node,
+                                       GtkTreePath      *path)
 {
   GtkTreeSelectionPrivate *priv = selection->priv;
   GtkTreeIter iter;
@@ -1449,7 +1449,7 @@ _gtk_tree_selection_row_is_selectable (GtkTreeSelection *selection,
 
   if (priv->user_func)
     return (*priv->user_func) (selection, model, path,
-                                   GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED),
+                                   GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED),
                                    priv->user_data);
   else
     return TRUE;
@@ -1466,11 +1466,11 @@ _gtk_tree_selection_row_is_selectable (GtkTreeSelection *selection,
  */
 void
 _gtk_tree_selection_internal_select_node (GtkTreeSelection *selection,
-                                         GtkRBNode        *node,
-                                         GtkRBTree        *tree,
-                                         GtkTreePath      *path,
+                                          GtkTreeRBNode    *node,
+                                          GtkTreeRBTree    *tree,
+                                          GtkTreePath      *path,
                                           GtkTreeSelectMode mode,
-                                         gboolean          override_browse_mode)
+                                          gboolean          override_browse_mode)
 {
   GtkTreeSelectionPrivate *priv = selection->priv;
   gint flags;
@@ -1556,7 +1556,7 @@ _gtk_tree_selection_internal_select_node (GtkTreeSelection *selection,
 
          _gtk_tree_view_set_anchor_path (priv->tree_view, path);
 
-         if ((flags & GTK_RBNODE_IS_SELECTED) == GTK_RBNODE_IS_SELECTED)
+         if ((flags & GTK_TREE_RBNODE_IS_SELECTED) == GTK_TREE_RBNODE_IS_SELECTED)
            dirty |= gtk_tree_selection_real_select_node (selection, tree, node, FALSE);
          else
            dirty |= gtk_tree_selection_real_select_node (selection, tree, node, TRUE);
@@ -1598,9 +1598,9 @@ _gtk_tree_selection_emit_changed (GtkTreeSelection *selection)
 
 static gint
 gtk_tree_selection_real_select_node (GtkTreeSelection *selection,
-                                    GtkRBTree        *tree,
-                                    GtkRBNode        *node,
-                                    gboolean          select)
+                                     GtkTreeRBTree    *tree,
+                                     GtkTreeRBNode    *node,
+                                     gboolean          select)
 {
   GtkTreeSelectionPrivate *priv = selection->priv;
   gboolean toggle = FALSE;
@@ -1610,7 +1610,7 @@ gtk_tree_selection_real_select_node (GtkTreeSelection *selection,
 
   select = !! select;
 
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED) != select)
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED) != select)
     {
       path = _gtk_tree_path_new_from_rbtree (tree, node);
       toggle = _gtk_tree_selection_row_is_selectable (selection, node, path);
@@ -1619,14 +1619,14 @@ gtk_tree_selection_real_select_node (GtkTreeSelection *selection,
 
   if (toggle)
     {
-      if (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+      if (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
         {
-          GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_IS_SELECTED);
+          GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_IS_SELECTED);
           _gtk_tree_view_accessible_add_state (priv->tree_view, tree, node, GTK_CELL_RENDERER_SELECTED);
         }
       else
         {
-          GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_IS_SELECTED);
+          GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_IS_SELECTED);
           _gtk_tree_view_accessible_remove_state (priv->tree_view, tree, node, GTK_CELL_RENDERER_SELECTED);
         }
 
diff --git a/gtk/gtktreeview.c b/gtk/gtktreeview.c
index 2bf18710b8..bf2437e3db 100644
--- a/gtk/gtktreeview.c
+++ b/gtk/gtktreeview.c
@@ -46,7 +46,7 @@
 #include "gtkmain.h"
 #include "gtkmarshalers.h"
 #include "gtkprivate.h"
-#include "gtkrbtreeprivate.h"
+#include "gtktreerbtreeprivate.h"
 #include "gtkrendericonprivate.h"
 #include "gtkscrollable.h"
 #include "gtksettingsprivate.h"
@@ -285,8 +285,8 @@ typedef struct _GtkTreeViewChild GtkTreeViewChild;
 struct _GtkTreeViewChild
 {
   GtkWidget *widget;
-  GtkRBNode *node;
-  GtkRBTree *tree;
+  GtkTreeRBNode *node;
+  GtkTreeRBTree *tree;
   GtkTreeViewColumn *column;
   GtkBorder border;
 };
@@ -308,7 +308,7 @@ struct _GtkTreeViewPrivate
   GtkTreeModel *model;
 
   /* tree information */
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
   /* Container info */
   GList *children;
@@ -344,14 +344,14 @@ struct _GtkTreeViewPrivate
   gint cursor_offset;
 
   GtkTreeRowReference *anchor;
-  GtkRBNode *cursor_node;
-  GtkRBTree *cursor_tree;
+  GtkTreeRBNode *cursor_node;
+  GtkTreeRBTree *cursor_tree;
 
   GtkTreeViewColumn *focus_column;
 
   /* Current pressed node, previously pressed, prelight */
-  GtkRBNode *button_pressed_node;
-  GtkRBTree *button_pressed_tree;
+  GtkTreeRBNode *button_pressed_node;
+  GtkTreeRBTree *button_pressed_tree;
 
   gint press_start_x;
   gint press_start_y;
@@ -359,8 +359,8 @@ struct _GtkTreeViewPrivate
   gint event_last_x;
   gint event_last_y;
 
-  GtkRBNode *prelight_node;
-  GtkRBTree *prelight_tree;
+  GtkTreeRBNode *prelight_node;
+  GtkTreeRBTree *prelight_tree;
 
   /* Cell Editing */
   GtkTreeViewColumn *edited_column;
@@ -416,11 +416,11 @@ struct _GtkTreeViewPrivate
   /* fixed height */
   gint fixed_height;
 
-  GtkRBNode *rubber_band_start_node;
-  GtkRBTree *rubber_band_start_tree;
+  GtkTreeRBNode *rubber_band_start_node;
+  GtkTreeRBTree *rubber_band_start_tree;
 
-  GtkRBNode *rubber_band_end_node;
-  GtkRBTree *rubber_band_end_tree;
+  GtkTreeRBNode *rubber_band_end_node;
+  GtkTreeRBTree *rubber_band_end_tree;
   GtkCssNode *rubber_band_cssnode;
 
   /* Scroll-to functionality when unrealized */
@@ -688,11 +688,11 @@ static void gtk_tree_view_rows_reordered                  (GtkTreeModel    *mode
                                                           gpointer         data);
 
 /* Incremental reflow */
-static gboolean validate_row             (GtkTreeView *tree_view,
-                                         GtkRBTree   *tree,
-                                         GtkRBNode   *node,
-                                         GtkTreeIter *iter,
-                                         GtkTreePath *path);
+static gboolean validate_row                              (GtkTreeView     *tree_view,
+                                                           GtkTreeRBTree   *tree,
+                                                           GtkTreeRBNode   *node,
+                                                           GtkTreeIter     *iter,
+                                                           GtkTreePath     *path);
 static void     validate_visible_area    (GtkTreeView *tree_view);
 static gboolean do_validate_rows         (GtkTreeView *tree_view,
                                          gboolean     queue_resize);
@@ -717,25 +717,25 @@ static void     gtk_tree_view_add_move_binding               (GtkBindingSet
                                                              GtkMovementStep     step,
                                                              gint                count);
 static gint     gtk_tree_view_unref_and_check_selection_tree (GtkTreeView        *tree_view,
-                                                             GtkRBTree          *tree);
+                                                             GtkTreeRBTree      *tree);
 static void     gtk_tree_view_snapshot_arrow                 (GtkTreeView        *tree_view,
                                                               GtkSnapshot        *snapshot,
-                                                             GtkRBTree          *tree,
-                                                             GtkRBNode          *node);
+                                                             GtkTreeRBTree      *tree,
+                                                             GtkTreeRBNode      *node);
 static void     gtk_tree_view_get_arrow_xrange               (GtkTreeView        *tree_view,
-                                                             GtkRBTree          *tree,
+                                                             GtkTreeRBTree      *tree,
                                                              gint               *x1,
                                                              gint               *x2);
 static void     gtk_tree_view_adjustment_changed             (GtkAdjustment      *adjustment,
                                                              GtkTreeView        *tree_view);
 static void     gtk_tree_view_build_tree                     (GtkTreeView        *tree_view,
-                                                             GtkRBTree          *tree,
+                                                             GtkTreeRBTree          *tree,
                                                              GtkTreeIter        *iter,
                                                              gint                depth,
                                                              gboolean            recurse);
 static void     gtk_tree_view_clamp_node_visible             (GtkTreeView        *tree_view,
-                                                             GtkRBTree          *tree,
-                                                             GtkRBNode          *node);
+                                                             GtkTreeRBTree      *tree,
+                                                             GtkTreeRBNode      *node);
 static void     gtk_tree_view_clamp_column_visible           (GtkTreeView        *tree_view,
                                                              GtkTreeViewColumn  *column,
                                                              gboolean            focus_to_cell);
@@ -751,13 +751,13 @@ static void     gtk_tree_view_move_cursor_start_end          (GtkTreeView
                                                              gint                count);
 static gboolean gtk_tree_view_real_collapse_row              (GtkTreeView        *tree_view,
                                                              GtkTreePath        *path,
-                                                             GtkRBTree          *tree,
-                                                             GtkRBNode          *node,
+                                                             GtkTreeRBTree      *tree,
+                                                             GtkTreeRBNode      *node,
                                                              gboolean            animate);
 static gboolean gtk_tree_view_real_expand_row                (GtkTreeView        *tree_view,
                                                              GtkTreePath        *path,
-                                                             GtkRBTree          *tree,
-                                                             GtkRBNode          *node,
+                                                             GtkTreeRBTree      *tree,
+                                                             GtkTreeRBNode      *node,
                                                              gboolean            open_all,
                                                              gboolean            animate);
 static void     gtk_tree_view_real_set_cursor                (GtkTreeView        *tree_view,
@@ -772,19 +772,19 @@ static void     update_prelight                              (GtkTreeView
                                                               int                 x,
                                                               int                 y);
 
-static inline gint gtk_tree_view_get_effective_header_height (GtkTreeView *tree_view);
+static inline gint gtk_tree_view_get_effective_header_height (GtkTreeView        *tree_view);
 
-static inline gint gtk_tree_view_get_cell_area_y_offset      (GtkTreeView *tree_view,
-                                                              GtkRBTree   *tree,
-                                                              GtkRBNode   *node);
-static inline gint gtk_tree_view_get_cell_area_height        (GtkTreeView *tree_view,
-                                                              GtkRBNode   *node);
+static inline gint gtk_tree_view_get_cell_area_y_offset      (GtkTreeView        *tree_view,
+                                                              GtkTreeRBTree      *tree,
+                                                              GtkTreeRBNode      *node);
+static inline gint gtk_tree_view_get_cell_area_height        (GtkTreeView        *tree_view,
+                                                              GtkTreeRBNode      *node);
 
-static inline gint gtk_tree_view_get_row_y_offset            (GtkTreeView *tree_view,
-                                                              GtkRBTree   *tree,
-                                                              GtkRBNode   *node);
-static inline gint gtk_tree_view_get_row_height              (GtkTreeView *tree_view,
-                                                              GtkRBNode   *node);
+static inline gint gtk_tree_view_get_row_y_offset            (GtkTreeView        *tree_view,
+                                                              GtkTreeRBTree      *tree,
+                                                              GtkTreeRBNode      *node);
+static inline gint gtk_tree_view_get_row_height              (GtkTreeView        *tree_view,
+                                                              GtkTreeRBNode      *node);
 
 /* interactive search */
 static void     gtk_tree_view_ensure_interactive_directory (GtkTreeView *tree_view);
@@ -2010,7 +2010,7 @@ gtk_tree_view_buildable_get_internal_child (GtkBuildable      *buildable,
 static void
 gtk_tree_view_free_rbtree (GtkTreeView *tree_view)
 {
-  _gtk_rbtree_free (tree_view->priv->tree);
+  gtk_tree_rbtree_free (tree_view->priv->tree);
 
   tree_view->priv->tree = NULL;
   tree_view->priv->button_pressed_node = NULL;
@@ -2786,8 +2786,8 @@ gtk_tree_view_multipress_gesture_pressed (GtkGestureMultiPress *gesture,
   gint new_y, y_offset;
   gint bin_x, bin_y;
   GtkTreePath *path;
-  GtkRBNode *node;
-  GtkRBTree *tree;
+  GtkTreeRBNode *node;
+  GtkTreeRBTree *tree;
   gint depth;
   guint button;
   GList *list;
@@ -2841,7 +2841,7 @@ gtk_tree_view_multipress_gesture_pressed (GtkGestureMultiPress *gesture,
   new_y = TREE_WINDOW_Y_TO_RBTREE_Y(tree_view, bin_y);
   if (new_y < 0)
     new_y = 0;
-  y_offset = -_gtk_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
+  y_offset = -gtk_tree_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
 
   if (node == NULL)
     {
@@ -2936,7 +2936,7 @@ gtk_tree_view_multipress_gesture_pressed (GtkGestureMultiPress *gesture,
       gtk_tree_view_column_cell_set_cell_data (column,
                                                tree_view->priv->model,
                                                &iter,
-                                               GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
+                                               GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT),
                                                node->children?TRUE:FALSE);
 
       if (tree_view->priv->anchor)
@@ -3040,8 +3040,8 @@ gtk_tree_view_drag_gesture_begin (GtkGestureDrag *gesture,
                                   GtkTreeView    *tree_view)
 {
   gint bin_x, bin_y;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   if (tree_view->priv->tree == NULL)
     {
@@ -3053,11 +3053,11 @@ gtk_tree_view_drag_gesture_begin (GtkGestureDrag *gesture,
                                                      &bin_x, &bin_y);
   tree_view->priv->press_start_x = tree_view->priv->rubber_band_x = bin_x;
   tree_view->priv->press_start_y = tree_view->priv->rubber_band_y = bin_y;
-  _gtk_rbtree_find_offset (tree_view->priv->tree, bin_y + tree_view->priv->dy,
+  gtk_tree_rbtree_find_offset (tree_view->priv->tree, bin_y + tree_view->priv->dy,
                            &tree, &node);
 
   if (tree_view->priv->rubber_banding_enable
-      && !GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED)
+      && !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED)
       && gtk_tree_selection_get_mode (tree_view->priv->selection) == GTK_SELECTION_MULTIPLE)
     {
       gboolean modify, extend;
@@ -3327,12 +3327,12 @@ gtk_tree_view_multipress_gesture_released (GtkGestureMultiPress *gesture,
  */
 
 static gboolean
-coords_are_over_arrow (GtkTreeView *tree_view,
-                       GtkRBTree   *tree,
-                       GtkRBNode   *node,
+coords_are_over_arrow (GtkTreeView   *tree_view,
+                       GtkTreeRBTree *tree,
+                       GtkTreeRBNode *node,
                        /* these are in bin window coords */
-                       gint         x,
-                       gint         y)
+                       gint           x,
+                       gint           y)
 {
   GdkRectangle arrow;
   gint x2;
@@ -3340,7 +3340,7 @@ coords_are_over_arrow (GtkTreeView *tree_view,
   if (!gtk_widget_get_realized (GTK_WIDGET (tree_view)))
     return FALSE;
 
-  if ((node->flags & GTK_RBNODE_IS_PARENT) == 0)
+  if ((node->flags & GTK_TREE_RBNODE_IS_PARENT) == 0)
     return FALSE;
 
   arrow.y = gtk_tree_view_get_row_y_offset (tree_view, tree, node);
@@ -3391,12 +3391,12 @@ remove_auto_expand_timeout (GtkTreeView *tree_view)
 }
 
 static void
-do_prelight (GtkTreeView *tree_view,
-             GtkRBTree   *tree,
-             GtkRBNode   *node,
+do_prelight (GtkTreeView   *tree_view,
+             GtkTreeRBTree *tree,
+             GtkTreeRBNode *node,
             /* these are in bin_window coords */
-             gint         x,
-             gint         y)
+             gint           x,
+             gint           y)
 {
   if (tree_view->priv->prelight_tree == tree &&
       tree_view->priv->prelight_node == node)
@@ -3428,8 +3428,8 @@ do_prelight (GtkTreeView *tree_view,
     {
       /*  Unprelight the old node and arrow  */
 
-      GTK_RBNODE_UNSET_FLAG (tree_view->priv->prelight_node,
-                            GTK_RBNODE_IS_PRELIT);
+      GTK_TREE_RBNODE_UNSET_FLAG (tree_view->priv->prelight_node,
+                            GTK_TREE_RBNODE_IS_PRELIT);
 
       if (tree_view->priv->arrow_prelit
          && gtk_tree_view_draw_expanders (tree_view))
@@ -3463,7 +3463,7 @@ do_prelight (GtkTreeView *tree_view,
       gtk_widget_queue_draw (GTK_WIDGET (tree_view));
     }
 
-  GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_IS_PRELIT);
+  GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_IS_PRELIT);
 
   gtk_widget_queue_draw (GTK_WIDGET (tree_view));
 
@@ -3476,12 +3476,12 @@ do_prelight (GtkTreeView *tree_view,
 }
 
 static void
-prelight_or_select (GtkTreeView *tree_view,
-                   GtkRBTree   *tree,
-                   GtkRBNode   *node,
+prelight_or_select (GtkTreeView   *tree_view,
+                   GtkTreeRBTree *tree,
+                   GtkTreeRBNode *node,
                    /* these are in bin_window coords */
-                   gint         x,
-                   gint         y)
+                   gint           x,
+                   gint           y)
 {
   GtkSelectionMode mode = gtk_tree_selection_get_mode (tree_view->priv->selection);
   
@@ -3493,13 +3493,13 @@ prelight_or_select (GtkTreeView *tree_view,
     {
       if (node)
        {
-         if (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+         if (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
            {
              GtkTreePath *path;
              
              path = _gtk_tree_path_new_from_rbtree (tree, node);
              gtk_tree_selection_select_path (tree_view->priv->selection, path);
-             if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+             if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
                {
                   tree_view->priv->draw_keyfocus = FALSE;
                  gtk_tree_view_real_set_cursor (tree_view, path, 0);
@@ -3531,8 +3531,8 @@ update_prelight (GtkTreeView *tree_view,
                  gint         y)
 {
   int new_y;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   if (tree_view->priv->tree == NULL)
     return;
@@ -3547,7 +3547,7 @@ update_prelight (GtkTreeView *tree_view,
   if (new_y < 0)
     new_y = 0;
 
-  _gtk_rbtree_find_offset (tree_view->priv->tree,
+  gtk_tree_rbtree_find_offset (tree_view->priv->tree,
                            new_y, &tree, &node);
 
   if (node)
@@ -3749,14 +3749,14 @@ gtk_tree_view_stop_rubber_band (GtkTreeView *tree_view)
 }
 
 static void
-gtk_tree_view_update_rubber_band_selection_range (GtkTreeView *tree_view,
-                                                GtkRBTree   *start_tree,
-                                                GtkRBNode   *start_node,
-                                                GtkRBTree   *end_tree,
-                                                GtkRBNode   *end_node,
-                                                gboolean     select,
-                                                gboolean     skip_start,
-                                                gboolean     skip_end)
+gtk_tree_view_update_rubber_band_selection_range (GtkTreeView  *tree_view,
+                                                GtkTreeRBTree *start_tree,
+                                                GtkTreeRBNode *start_node,
+                                                GtkTreeRBTree *end_tree,
+                                                GtkTreeRBNode *end_node,
+                                                gboolean       select,
+                                                gboolean       skip_start,
+                                                gboolean       skip_end)
 {
   if (start_node == end_node)
     return;
@@ -3770,7 +3770,7 @@ gtk_tree_view_update_rubber_band_selection_range (GtkTreeView *tree_view,
       /* Small optimization by assuming insensitive nodes are never
        * selected.
        */
-      if (!GTK_RBNODE_FLAG_SET (start_node, GTK_RBNODE_IS_SELECTED))
+      if (!GTK_TREE_RBNODE_FLAG_SET (start_node, GTK_TREE_RBNODE_IS_SELECTED))
         {
          GtkTreePath *path;
          gboolean selectable;
@@ -3786,33 +3786,33 @@ gtk_tree_view_update_rubber_band_selection_range (GtkTreeView *tree_view,
       if (select)
         {
          if (tree_view->priv->rubber_band_extend)
-            GTK_RBNODE_SET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+            GTK_TREE_RBNODE_SET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
          else if (tree_view->priv->rubber_band_modify)
            {
              /* Toggle the selection state */
-             if (GTK_RBNODE_FLAG_SET (start_node, GTK_RBNODE_IS_SELECTED))
-               GTK_RBNODE_UNSET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+             if (GTK_TREE_RBNODE_FLAG_SET (start_node, GTK_TREE_RBNODE_IS_SELECTED))
+               GTK_TREE_RBNODE_UNSET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
              else
-               GTK_RBNODE_SET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+               GTK_TREE_RBNODE_SET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
            }
          else
-           GTK_RBNODE_SET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+           GTK_TREE_RBNODE_SET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
        }
       else
         {
          /* Mirror the above */
          if (tree_view->priv->rubber_band_extend)
-           GTK_RBNODE_UNSET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+           GTK_TREE_RBNODE_UNSET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
          else if (tree_view->priv->rubber_band_modify)
            {
              /* Toggle the selection state */
-             if (GTK_RBNODE_FLAG_SET (start_node, GTK_RBNODE_IS_SELECTED))
-               GTK_RBNODE_UNSET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+             if (GTK_TREE_RBNODE_FLAG_SET (start_node, GTK_TREE_RBNODE_IS_SELECTED))
+               GTK_TREE_RBNODE_UNSET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
              else
-               GTK_RBNODE_SET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+               GTK_TREE_RBNODE_SET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
            }
          else
-           GTK_RBNODE_UNSET_FLAG (start_node, GTK_RBNODE_IS_SELECTED);
+           GTK_TREE_RBNODE_UNSET_FLAG (start_node, GTK_TREE_RBNODE_IS_SELECTED);
        }
 
       gtk_widget_queue_draw (GTK_WIDGET (tree_view));
@@ -3826,11 +3826,11 @@ skip_first:
       if (start_node->children)
         {
          start_tree = start_node->children;
-          start_node = _gtk_rbtree_first (start_tree);
+          start_node = gtk_tree_rbtree_first (start_tree);
        }
       else
         {
-         _gtk_rbtree_next_full (start_tree, start_node, &start_tree, &start_node);
+         gtk_tree_rbtree_next_full (start_tree, start_node, &start_tree, &start_node);
 
          if (!start_tree)
            /* Ran out of tree */
@@ -3846,8 +3846,8 @@ skip_first:
 static void
 gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
 {
-  GtkRBTree *start_tree, *end_tree;
-  GtkRBNode *start_node, *end_node;
+  GtkTreeRBTree *start_tree, *end_tree;
+  GtkTreeRBNode *start_node, *end_node;
   gdouble start_y, offset_y;
   gint bin_y;
 
@@ -3862,26 +3862,26 @@ gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
                                                      NULL, &bin_y);
   bin_y = MAX (0, bin_y + offset_y + tree_view->priv->dy);
 
-  _gtk_rbtree_find_offset (tree_view->priv->tree, MIN (tree_view->priv->press_start_y, bin_y), &start_tree, 
&start_node);
-  _gtk_rbtree_find_offset (tree_view->priv->tree, MAX (tree_view->priv->press_start_y, bin_y), &end_tree, 
&end_node);
+  gtk_tree_rbtree_find_offset (tree_view->priv->tree, MIN (tree_view->priv->press_start_y, bin_y), 
&start_tree, &start_node);
+  gtk_tree_rbtree_find_offset (tree_view->priv->tree, MAX (tree_view->priv->press_start_y, bin_y), 
&end_tree, &end_node);
 
   /* Handle the start area first */
   if (!start_node && !end_node)
     {
       if (tree_view->priv->rubber_band_start_node)
         {
-          GtkRBNode *node = tree_view->priv->rubber_band_start_node;
+          GtkTreeRBNode *node = tree_view->priv->rubber_band_start_node;
 
          if (tree_view->priv->rubber_band_modify)
            {
              /* Toggle the selection state */
-             if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
-               GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_IS_SELECTED);
+             if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
+               GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_IS_SELECTED);
              else
-               GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_IS_SELECTED);
+               GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_IS_SELECTED);
            }
           else
-            GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_IS_SELECTED);
+            GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_IS_SELECTED);
 
           gtk_widget_queue_draw (GTK_WIDGET (tree_view));
         }
@@ -3897,8 +3897,8 @@ gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
                                                       FALSE,
                                                       FALSE);
     }
-  else if (_gtk_rbtree_node_find_offset (start_tree, start_node) <
-           _gtk_rbtree_node_find_offset (tree_view->priv->rubber_band_start_tree, 
tree_view->priv->rubber_band_start_node))
+  else if (gtk_tree_rbtree_node_find_offset (start_tree, start_node) <
+           gtk_tree_rbtree_node_find_offset (tree_view->priv->rubber_band_start_tree, 
tree_view->priv->rubber_band_start_node))
     {
       /* New node is above the old one; selection became bigger */
       gtk_tree_view_update_rubber_band_selection_range (tree_view,
@@ -3910,8 +3910,8 @@ gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
                                                       FALSE,
                                                       TRUE);
     }
-  else if (_gtk_rbtree_node_find_offset (start_tree, start_node) >
-           _gtk_rbtree_node_find_offset (tree_view->priv->rubber_band_start_tree, 
tree_view->priv->rubber_band_start_node))
+  else if (gtk_tree_rbtree_node_find_offset (start_tree, start_node) >
+           gtk_tree_rbtree_node_find_offset (tree_view->priv->rubber_band_start_tree, 
tree_view->priv->rubber_band_start_node))
     {
       /* New node is below the old one; selection became smaller */
       gtk_tree_view_update_rubber_band_selection_range (tree_view,
@@ -3937,7 +3937,7 @@ gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
   else if (!end_node)
     {
       /* Find the last node in the tree */
-      _gtk_rbtree_find_offset (tree_view->priv->tree, gtk_tree_view_get_height (tree_view) - 1,
+      gtk_tree_rbtree_find_offset (tree_view->priv->tree, gtk_tree_view_get_height (tree_view) - 1,
                               &end_tree, &end_node);
 
       /* Selection reached end of the tree */
@@ -3950,8 +3950,8 @@ gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
                                                       TRUE,
                                                       FALSE);
     }
-  else if (_gtk_rbtree_node_find_offset (end_tree, end_node) >
-           _gtk_rbtree_node_find_offset (tree_view->priv->rubber_band_end_tree, 
tree_view->priv->rubber_band_end_node))
+  else if (gtk_tree_rbtree_node_find_offset (end_tree, end_node) >
+           gtk_tree_rbtree_node_find_offset (tree_view->priv->rubber_band_end_tree, 
tree_view->priv->rubber_band_end_node))
     {
       /* New node is below the old one; selection became bigger */
       gtk_tree_view_update_rubber_band_selection_range (tree_view,
@@ -3963,8 +3963,8 @@ gtk_tree_view_update_rubber_band_selection (GtkTreeView *tree_view)
                                                       TRUE,
                                                       FALSE);
     }
-  else if (_gtk_rbtree_node_find_offset (end_tree, end_node) <
-           _gtk_rbtree_node_find_offset (tree_view->priv->rubber_band_end_tree, 
tree_view->priv->rubber_band_end_node))
+  else if (gtk_tree_rbtree_node_find_offset (end_tree, end_node) <
+           gtk_tree_rbtree_node_find_offset (tree_view->priv->rubber_band_end_tree, 
tree_view->priv->rubber_band_end_node))
     {
       /* New node is above the old one; selection became smaller */
       gtk_tree_view_update_rubber_band_selection_range (tree_view,
@@ -4120,8 +4120,8 @@ gtk_tree_view_motion_controller_motion (GtkEventControllerMotion *controller,
                                         double                    y,
                                         GtkTreeView              *tree_view)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gint new_y;
   GList *list;
   gboolean cursor_set = FALSE;
@@ -4139,7 +4139,7 @@ gtk_tree_view_motion_controller_motion (GtkEventControllerMotion *controller,
                                                          &bin_x, &bin_y);
       new_y = MAX (0, TREE_WINDOW_Y_TO_RBTREE_Y (tree_view, bin_y));
 
-      _gtk_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
+      gtk_tree_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
 
       tree_view->priv->event_last_x = bin_x;
       tree_view->priv->event_last_y = bin_y;
@@ -4305,11 +4305,11 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
   GtkTreeViewPrivate *priv = gtk_tree_view_get_instance_private (tree_view);
   const int x_scroll_offset = - gtk_adjustment_get_value (priv->hadjustment);
   GtkTreePath *path;
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
   GList *list;
-  GtkRBNode *node;
-  GtkRBNode *drag_highlight = NULL;
-  GtkRBTree *drag_highlight_tree = NULL;
+  GtkTreeRBNode *node;
+  GtkTreeRBNode *drag_highlight = NULL;
+  GtkTreeRBTree *drag_highlight_tree = NULL;
   GtkTreeIter iter;
   gint new_y;
   gint y_offset, cell_offset;
@@ -4342,7 +4342,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
 
   clip = (GdkRectangle) { 0, 0, bin_window_width, bin_window_height };
   new_y = TREE_WINDOW_Y_TO_RBTREE_Y (tree_view, clip.y);
-  y_offset = -_gtk_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
+  y_offset = -gtk_tree_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
 
   if (gtk_tree_view_get_height (tree_view) < bin_window_height)
     {
@@ -4412,7 +4412,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
    * order, drawing each successive node.
    */
   
-  parity = !(_gtk_rbtree_node_get_index (tree, node) % 2);
+  parity = !(gtk_tree_rbtree_node_get_index (tree, node) % 2);
 
   do
     {
@@ -4431,10 +4431,10 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
 
       flags = 0;
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PRELIT))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PRELIT))
        flags |= GTK_CELL_RENDERER_PRELIT;
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
         flags |= GTK_CELL_RENDERER_SELECTED;
 
       /* we *need* to set cell data on all cells before the call
@@ -4449,7 +4449,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
          gtk_tree_view_column_cell_set_cell_data (column,
                                                   tree_view->priv->model,
                                                   &iter,
-                                                  GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
+                                                  GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT),
                                                   node->children?TRUE:FALSE);
         }
 
@@ -4487,7 +4487,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
           else
             flags &= ~GTK_CELL_RENDERER_FOCUSED;
 
-          if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT))
+          if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT))
             flags |= GTK_CELL_RENDERER_EXPANDABLE;
           else
             flags &= ~GTK_CELL_RENDERER_EXPANDABLE;
@@ -4540,7 +4540,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
          gtk_tree_view_column_cell_set_cell_data (column,
                                                   tree_view->priv->model,
                                                   &iter,
-                                                  GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
+                                                  GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT),
                                                   node->children?TRUE:FALSE);
 
           gtk_style_context_save (context);
@@ -4616,7 +4616,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
                 }
 
              if (gtk_tree_view_draw_expanders (tree_view)
-                 && (node->flags & GTK_RBNODE_IS_PARENT) == GTK_RBNODE_IS_PARENT)
+                 && (node->flags & GTK_TREE_RBNODE_IS_PARENT) == GTK_TREE_RBNODE_IS_PARENT)
                {
                  gtk_tree_view_snapshot_arrow (GTK_TREE_VIEW (widget),
                                                 snapshot,
@@ -4683,7 +4683,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
              if (rtl)
                x += background_area.width - 1;
 
-             if ((node->flags & GTK_RBNODE_IS_PARENT) == GTK_RBNODE_IS_PARENT
+             if ((node->flags & GTK_TREE_RBNODE_IS_PARENT) == GTK_TREE_RBNODE_IS_PARENT
                  && depth > 1)
                {
                   gtk_tree_view_snapshot_line (tree_view, snapshot,
@@ -4706,10 +4706,10 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
              if (depth > 1)
                {
                  gint i;
-                 GtkRBNode *tmp_node;
-                 GtkRBTree *tmp_tree;
+                 GtkTreeRBNode *tmp_node;
+                 GtkTreeRBTree *tmp_tree;
 
-                 if (!_gtk_rbtree_next (tree, node))
+                 if (!gtk_tree_rbtree_next (tree, node))
                     gtk_tree_view_snapshot_line (tree_view, snapshot,
                                                  GTK_TREE_VIEW_TREE_LINE,
                                                  x + expander_size * (depth - 1.5) * mult,
@@ -4729,7 +4729,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
 
                  for (i = depth - 2; i > 0; i--)
                    {
-                     if (_gtk_rbtree_next (tmp_tree, tmp_node))
+                     if (gtk_tree_rbtree_next (tmp_tree, tmp_node))
                         gtk_tree_view_snapshot_line (tree_view, snapshot,
                                                      GTK_TREE_VIEW_TREE_LINE,
                                                      x + expander_size * (i - 0.5) * mult,
@@ -4751,8 +4751,8 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
         {
           /* Draw indicator for the drop
            */
-         GtkRBTree *drag_tree = NULL;
-         GtkRBNode *drag_node = NULL;
+         GtkTreeRBTree *drag_tree = NULL;
+         GtkTreeRBNode *drag_node = NULL;
 
           gtk_style_context_save (context);
           gtk_style_context_set_state (context, gtk_style_context_get_state (context) | 
GTK_STATE_FLAG_DROP_ACTIVE);
@@ -4825,7 +4825,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
          gboolean has_child;
 
          tree = node->children;
-          node = _gtk_rbtree_first (tree);
+          node = gtk_tree_rbtree_first (tree);
 
          has_child = gtk_tree_model_iter_children (tree_view->priv->model,
                                                    &iter,
@@ -4841,7 +4841,7 @@ gtk_tree_view_bin_snapshot (GtkWidget   *widget,
 
          do
            {
-             node = _gtk_rbtree_next (tree, node);
+             node = gtk_tree_rbtree_next (tree, node);
              if (node != NULL)
                {
                  gboolean has_next = gtk_tree_model_iter_next (tree_view->priv->model, &iter);
@@ -5421,8 +5421,8 @@ gtk_tree_view_motion_controller_enter (GtkEventControllerMotion *controller,
                                        double                    y,
                                        GtkTreeView              *tree_view)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gint new_y;
 
   if (tree_view->priv->tree == NULL)
@@ -5432,7 +5432,7 @@ gtk_tree_view_motion_controller_enter (GtkEventControllerMotion *controller,
   new_y = TREE_WINDOW_Y_TO_RBTREE_Y(tree_view, y);
   if (new_y < 0)
     new_y = 0;
-  _gtk_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
+  gtk_tree_rbtree_find_offset (tree_view->priv->tree, new_y, &tree, &node);
 
   tree_view->priv->event_last_x = x;
   tree_view->priv->event_last_y = y;
@@ -5473,14 +5473,14 @@ gtk_tree_view_key_controller_focus_out (GtkEventControllerKey *key,
  */
 
 static gboolean
-node_is_visible (GtkTreeView *tree_view,
-                GtkRBTree   *tree,
-                GtkRBNode   *node)
+node_is_visible (GtkTreeView   *tree_view,
+                GtkTreeRBTree *tree,
+                GtkTreeRBNode *node)
 {
   int y;
   int height;
 
-  y = _gtk_rbtree_node_find_offset (tree, node);
+  y = gtk_tree_rbtree_node_find_offset (tree, node);
   height = gtk_tree_view_get_row_height (tree_view, node);
 
   if (y >= gtk_adjustment_get_value (tree_view->priv->vadjustment) &&
@@ -5520,10 +5520,10 @@ get_separator_height (GtkTreeView *tree_view)
 /* Returns TRUE if it updated the size
  */
 static gboolean
-validate_row (GtkTreeView *tree_view,
-             GtkRBTree   *tree,
-             GtkRBNode   *node,
-             GtkTreeIter *iter,
+validate_row (GtkTreeView   *tree_view,
+             GtkTreeRBTree *tree,
+             GtkTreeRBNode *node,
+             GtkTreeIter   *iter,
              GtkTreePath *path)
 {
   GtkTreeViewColumn *column;
@@ -5537,8 +5537,8 @@ validate_row (GtkTreeView *tree_view,
   gint expander_size;
 
   /* double check the row needs validating */
-  if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) &&
-      ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+  if (! GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) &&
+      ! GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID))
     return FALSE;
 
   is_separator = row_is_separator (tree_view, iter, NULL);
@@ -5579,14 +5579,14 @@ validate_row (GtkTreeView *tree_view,
       if (!gtk_tree_view_column_get_visible (column))
        continue;
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) && 
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) && 
          !_gtk_tree_view_column_cell_get_dirty (column))
        continue;
 
       original_width = _gtk_tree_view_column_get_requested_width (column);
 
       gtk_tree_view_column_cell_set_cell_data (column, tree_view->priv->model, iter,
-                                              GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
+                                              GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT),
                                               node->children?TRUE:FALSE);
       gtk_tree_view_column_cell_get_size (column,
                                          NULL, NULL, NULL,
@@ -5633,12 +5633,12 @@ validate_row (GtkTreeView *tree_view,
   if (draw_hgrid_lines)
     height += _TREE_VIEW_GRID_LINE_WIDTH;
 
-  if (height != GTK_RBNODE_GET_HEIGHT (node))
+  if (height != GTK_TREE_RBNODE_GET_HEIGHT (node))
     {
       retval = TRUE;
-      _gtk_rbtree_node_set_height (tree, node, height);
+      gtk_tree_rbtree_node_set_height (tree, node, height);
     }
-  _gtk_rbtree_node_mark_valid (tree, node);
+  gtk_tree_rbtree_node_mark_valid (tree, node);
   tree_view->priv->post_validation_flag = TRUE;
 
   return retval;
@@ -5651,8 +5651,8 @@ validate_visible_area (GtkTreeView *tree_view)
   GtkTreePath *path = NULL;
   GtkTreePath *above_path = NULL;
   GtkTreeIter iter;
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
   gboolean need_redraw = FALSE;
   gboolean size_changed = FALSE;
   gint total_height;
@@ -5662,7 +5662,7 @@ validate_visible_area (GtkTreeView *tree_view)
   if (tree_view->priv->tree == NULL)
     return;
 
-  if (! GTK_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_RBNODE_DESCENDANTS_INVALID) &&
+  if (! GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID) &&
       tree_view->priv->scroll_to_path == NULL)
     return;
 
@@ -5681,8 +5681,8 @@ validate_visible_area (GtkTreeView *tree_view)
        {
           /* we are going to scroll, and will update dy */
          gtk_tree_model_get_iter (tree_view->priv->model, &iter, path);
-         if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-             GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+         if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+             GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID))
            {
               gtk_widget_queue_draw (GTK_WIDGET (tree_view));
              if (validate_row (tree_view, tree, node, &iter, path))
@@ -5707,7 +5707,7 @@ validate_visible_area (GtkTreeView *tree_view)
              gint dy;
              gint height = gtk_tree_view_get_row_height (tree_view, node);
 
-             dy = _gtk_rbtree_node_find_offset (tree, node);
+             dy = gtk_tree_rbtree_node_find_offset (tree, node);
 
              if (dy >= gtk_adjustment_get_value (tree_view->priv->vadjustment) &&
                  dy + height <= (gtk_adjustment_get_value (tree_view->priv->vadjustment)
@@ -5777,7 +5777,7 @@ validate_visible_area (GtkTreeView *tree_view)
     {
       gint offset;
 
-      offset = _gtk_rbtree_find_offset (tree_view->priv->tree,
+      offset = gtk_tree_rbtree_find_offset (tree_view->priv->tree,
                                        TREE_WINDOW_Y_TO_RBTREE_Y (tree_view, 0),
                                        &tree, &node);
       if (node == NULL)
@@ -5794,8 +5794,8 @@ validate_visible_area (GtkTreeView *tree_view)
 
       gtk_tree_model_get_iter (tree_view->priv->model, &iter, path);
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-         GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+         GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID))
        {
           gtk_widget_queue_draw (GTK_WIDGET (tree_view));
          if (validate_row (tree_view, tree, node, &iter, path))
@@ -5809,17 +5809,17 @@ validate_visible_area (GtkTreeView *tree_view)
 
   /* if we do not validate any row above the new top_row, we will make sure
    * that the row immediately above top_row has been validated. (if we do not
-   * do this, _gtk_rbtree_find_offset will find the row above top_row, because
+   * do this, gtk_tree_rbtree_find_offset will find the row above top_row, because
    * when invalidated that row's height will be zero. and this will mess up
    * scrolling).
    */
   if (area_above == 0)
     {
-      GtkRBTree *tmptree;
-      GtkRBNode *tmpnode;
+      GtkTreeRBTree *tmptree;
+      GtkTreeRBNode *tmpnode;
 
       _gtk_tree_view_find_node (tree_view, above_path, &tmptree, &tmpnode);
-      _gtk_rbtree_prev_full (tmptree, tmpnode, &tmptree, &tmpnode);
+      gtk_tree_rbtree_prev_full (tmptree, tmpnode, &tmptree, &tmpnode);
 
       if (tmpnode)
         {
@@ -5829,8 +5829,8 @@ validate_visible_area (GtkTreeView *tree_view)
          tmppath = _gtk_tree_path_new_from_rbtree (tmptree, tmpnode);
          gtk_tree_model_get_iter (tree_view->priv->model, &tmpiter, tmppath);
 
-         if (GTK_RBNODE_FLAG_SET (tmpnode, GTK_RBNODE_INVALID) ||
-             GTK_RBNODE_FLAG_SET (tmpnode, GTK_RBNODE_COLUMN_INVALID))
+         if (GTK_TREE_RBNODE_FLAG_SET (tmpnode, GTK_TREE_RBNODE_INVALID) ||
+             GTK_TREE_RBNODE_FLAG_SET (tmpnode, GTK_TREE_RBNODE_COLUMN_INVALID))
            {
               gtk_widget_queue_draw (GTK_WIDGET (tree_view));
              if (validate_row (tree_view, tmptree, tmpnode, &tmpiter, tmppath))
@@ -5854,7 +5854,7 @@ validate_visible_area (GtkTreeView *tree_view)
          gboolean has_child;
 
          tree = node->children;
-          node = _gtk_rbtree_first (tree);
+          node = gtk_tree_rbtree_first (tree);
 
          has_child = gtk_tree_model_iter_children (tree_view->priv->model,
                                                    &iter,
@@ -5867,7 +5867,7 @@ validate_visible_area (GtkTreeView *tree_view)
          gboolean done = FALSE;
          do
            {
-             node = _gtk_rbtree_next (tree, node);
+             node = gtk_tree_rbtree_next (tree, node);
              if (node != NULL)
                {
                  gboolean has_next = gtk_tree_model_iter_next (tree_view->priv->model, &iter);
@@ -5901,8 +5901,8 @@ validate_visible_area (GtkTreeView *tree_view)
       if (!node)
         break;
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-         GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+         GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID))
        {
           gtk_widget_queue_draw (GTK_WIDGET (tree_view));
          if (validate_row (tree_view, tree, node, &iter, path))
@@ -5923,7 +5923,7 @@ validate_visible_area (GtkTreeView *tree_view)
   /* We walk backwards */
   while (area_above > 0)
     {
-      _gtk_rbtree_prev_full (tree, node, &tree, &node);
+      gtk_tree_rbtree_prev_full (tree, node, &tree, &node);
 
       /* Always find the new path in the tree.  We cannot just assume
        * a gtk_tree_path_prev() is enough here, as there might be children
@@ -5942,8 +5942,8 @@ validate_visible_area (GtkTreeView *tree_view)
 
       gtk_tree_model_get_iter (tree_view->priv->model, &iter, above_path);
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-         GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+         GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID))
        {
           gtk_widget_queue_draw (GTK_WIDGET (tree_view));
          if (validate_row (tree_view, tree, node, &iter, above_path))
@@ -6024,8 +6024,8 @@ initialize_fixed_height_mode (GtkTreeView *tree_view)
       GtkTreeIter iter;
       GtkTreePath *path;
 
-      GtkRBTree *tree = NULL;
-      GtkRBNode *node = NULL;
+      GtkTreeRBTree *tree = NULL;
+      GtkTreeRBNode *node = NULL;
 
       tree = tree_view->priv->tree;
       node = tree->root;
@@ -6040,7 +6040,7 @@ initialize_fixed_height_mode (GtkTreeView *tree_view)
       tree_view->priv->fixed_height = gtk_tree_view_get_row_height (tree_view, node);
     }
 
-   _gtk_rbtree_set_fixed_height (tree_view->priv->tree,
+   gtk_tree_rbtree_set_fixed_height (tree_view->priv->tree,
                                  tree_view->priv->fixed_height, TRUE);
 }
 
@@ -6055,8 +6055,8 @@ do_validate_rows (GtkTreeView *tree_view, gboolean queue_resize)
 {
   static gboolean prevent_recursion_hack = FALSE;
 
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
   gboolean validated_area = FALSE;
   gint retval = TRUE;
   GtkTreePath *path = NULL;
@@ -6092,7 +6092,7 @@ do_validate_rows (GtkTreeView *tree_view, gboolean queue_resize)
     {
       gboolean changed = FALSE;
 
-      if (! GTK_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_RBNODE_DESCENDANTS_INVALID))
+      if (! GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID))
        {
          retval = FALSE;
          goto done;
@@ -6100,7 +6100,7 @@ do_validate_rows (GtkTreeView *tree_view, gboolean queue_resize)
 
       if (path != NULL)
        {
-         node = _gtk_rbtree_next (tree, node);
+         node = gtk_tree_rbtree_next (tree, node);
          if (node != NULL)
            {
              TREE_VIEW_INTERNAL_ASSERT (gtk_tree_model_iter_next (tree_view->priv->model, &iter), FALSE);
@@ -6118,22 +6118,22 @@ do_validate_rows (GtkTreeView *tree_view, gboolean queue_resize)
          tree = tree_view->priv->tree;
          node = tree_view->priv->tree->root;
 
-         g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID));
+         g_assert (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
 
          do
            {
-             if (!_gtk_rbtree_is_nil (node->left) &&
-                 GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID))
+             if (!gtk_tree_rbtree_is_nil (node->left) &&
+                 GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID))
                {
                  node = node->left;
                }
-              else if (!_gtk_rbtree_is_nil (node->right) &&
-                      GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID))
+              else if (!gtk_tree_rbtree_is_nil (node->right) &&
+                      GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID))
                {
                  node = node->right;
                }
-             else if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-                      GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+             else if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+                      GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID))
                {
                  break;
                }
@@ -6180,7 +6180,7 @@ do_validate_rows (GtkTreeView *tree_view, gboolean queue_resize)
   if (!tree_view->priv->fixed_height_check)
    {
      if (fixed_height)
-       _gtk_rbtree_set_fixed_height (tree_view->priv->tree, prev_height, FALSE);
+       gtk_tree_rbtree_set_fixed_height (tree_view->priv->tree, prev_height, FALSE);
 
      tree_view->priv->fixed_height_check = 1;
    }
@@ -6270,7 +6270,7 @@ do_presize_handler (GtkTreeView *tree_view)
   if (tree_view->priv->mark_rows_col_dirty)
    {
       if (tree_view->priv->tree)
-       _gtk_rbtree_column_invalid (tree_view->priv->tree);
+       gtk_tree_rbtree_column_invalid (tree_view->priv->tree);
       tree_view->priv->mark_rows_col_dirty = FALSE;
     }
   validate_visible_area (tree_view);
@@ -6409,8 +6409,8 @@ gtk_tree_view_dy_to_top_row (GtkTreeView *tree_view)
 {
   gint offset;
   GtkTreePath *path;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   if (tree_view->priv->tree == NULL)
     {
@@ -6418,7 +6418,7 @@ gtk_tree_view_dy_to_top_row (GtkTreeView *tree_view)
     }
   else
     {
-      offset = _gtk_rbtree_find_offset (tree_view->priv->tree,
+      offset = gtk_tree_rbtree_find_offset (tree_view->priv->tree,
                                        tree_view->priv->dy,
                                        &tree, &node);
 
@@ -6439,8 +6439,8 @@ static void
 gtk_tree_view_top_row_to_dy (GtkTreeView *tree_view)
 {
   GtkTreePath *path;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   int new_dy;
 
   /* Avoid recursive calls */
@@ -6479,7 +6479,7 @@ gtk_tree_view_top_row_to_dy (GtkTreeView *tree_view)
       return;
     }
 
-  new_dy = _gtk_rbtree_node_find_offset (tree, node);
+  new_dy = gtk_tree_rbtree_node_find_offset (tree, node);
   new_dy += tree_view->priv->top_row_dy;
 
   if (new_dy + gtk_adjustment_get_page_size (tree_view->priv->vadjustment) > gtk_tree_view_get_height 
(tree_view))
@@ -7856,14 +7856,14 @@ gtk_tree_view_header_focus (GtkTreeView      *tree_view,
  * is already focusable, it’s the returned one.
  */
 static gboolean
-search_first_focusable_path (GtkTreeView  *tree_view,
-                            GtkTreePath **path,
-                            gboolean      search_forward,
-                            GtkRBTree   **new_tree,
-                            GtkRBNode   **new_node)
+search_first_focusable_path (GtkTreeView    *tree_view,
+                            GtkTreePath   **path,
+                            gboolean        search_forward,
+                            GtkTreeRBTree **new_tree,
+                            GtkTreeRBNode **new_node)
 {
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
 
   if (!path || !*path)
     return FALSE;
@@ -7876,9 +7876,9 @@ search_first_focusable_path (GtkTreeView  *tree_view,
   while (node && row_is_separator (tree_view, NULL, *path))
     {
       if (search_forward)
-       _gtk_rbtree_next_full (tree, node, &tree, &node);
+       gtk_tree_rbtree_next_full (tree, node, &tree, &node);
       else
-       _gtk_rbtree_prev_full (tree, node, &tree, &node);
+       gtk_tree_rbtree_prev_full (tree, node, &tree, &node);
 
       if (*path)
        gtk_tree_path_free (*path);
@@ -7988,7 +7988,7 @@ gtk_tree_view_style_updated (GtkWidget *widget)
        }
 
       tree_view->priv->fixed_height = -1;
-      _gtk_rbtree_mark_invalid (tree_view->priv->tree);
+      gtk_tree_rbtree_mark_invalid (tree_view->priv->tree);
     }
 }
 
@@ -8126,8 +8126,8 @@ gtk_tree_view_row_changed (GtkTreeModel *model,
                           gpointer      data)
 {
   GtkTreeView *tree_view = (GtkTreeView *)data;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gboolean free_path = FALSE;
   GList *list;
   GtkTreePath *cursor_path;
@@ -8170,12 +8170,12 @@ gtk_tree_view_row_changed (GtkTreeModel *model,
   if (tree_view->priv->fixed_height_mode
       && tree_view->priv->fixed_height >= 0)
     {
-      _gtk_rbtree_node_set_height (tree, node, tree_view->priv->fixed_height);
+      gtk_tree_rbtree_node_set_height (tree, node, tree_view->priv->fixed_height);
       gtk_widget_queue_draw (GTK_WIDGET (tree_view));
     }
   else
     {
-      _gtk_rbtree_node_mark_invalid (tree, node);
+      gtk_tree_rbtree_node_mark_invalid (tree, node);
       for (list = tree_view->priv->columns; list; list = list->next)
         {
           GtkTreeViewColumn *column;
@@ -8207,8 +8207,8 @@ gtk_tree_view_row_inserted (GtkTreeModel *model,
 {
   GtkTreeView *tree_view = (GtkTreeView *) data;
   gint *indices;
-  GtkRBTree *tree;
-  GtkRBNode *tmpnode = NULL;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *tmpnode = NULL;
   gint depth;
   gint i = 0;
   gint height;
@@ -8232,7 +8232,7 @@ gtk_tree_view_row_inserted (GtkTreeModel *model,
     gtk_tree_model_get_iter (model, iter, path);
 
   if (tree_view->priv->tree == NULL)
-    tree_view->priv->tree = _gtk_rbtree_new ();
+    tree_view->priv->tree = gtk_tree_rbtree_new ();
 
   tree = tree_view->priv->tree;
 
@@ -8251,7 +8251,7 @@ gtk_tree_view_row_inserted (GtkTreeModel *model,
           goto done;
        }
 
-      tmpnode = _gtk_rbtree_find_count (tree, indices[i] + 1);
+      tmpnode = gtk_tree_rbtree_find_count (tree, indices[i] + 1);
       if (tmpnode == NULL)
        {
          g_warning ("A node was inserted with a parent that's not in the tree.\n" \
@@ -8259,7 +8259,7 @@ gtk_tree_view_row_inserted (GtkTreeModel *model,
                     "before the parent was inserted.");
           goto done;
        }
-      else if (!GTK_RBNODE_FLAG_SET (tmpnode, GTK_RBNODE_IS_PARENT))
+      else if (!GTK_TREE_RBNODE_FLAG_SET (tmpnode, GTK_TREE_RBNODE_IS_PARENT))
        {
           /* FIXME enforce correct behavior on model, probably */
          /* In theory, the model should have emitted has_child_toggled here.  We
@@ -8285,13 +8285,13 @@ gtk_tree_view_row_inserted (GtkTreeModel *model,
   gtk_tree_model_ref_node (tree_view->priv->model, iter);
   if (indices[depth - 1] == 0)
     {
-      tmpnode = _gtk_rbtree_find_count (tree, 1);
-      tmpnode = _gtk_rbtree_insert_before (tree, tmpnode, height, FALSE);
+      tmpnode = gtk_tree_rbtree_find_count (tree, 1);
+      tmpnode = gtk_tree_rbtree_insert_before (tree, tmpnode, height, FALSE);
     }
   else
     {
-      tmpnode = _gtk_rbtree_find_count (tree, indices[depth - 1]);
-      tmpnode = _gtk_rbtree_insert_after (tree, tmpnode, height, FALSE);
+      tmpnode = gtk_tree_rbtree_find_count (tree, indices[depth - 1]);
+      tmpnode = gtk_tree_rbtree_insert_after (tree, tmpnode, height, FALSE);
     }
 
   _gtk_tree_view_accessible_add (tree_view, tree, tmpnode);
@@ -8300,7 +8300,7 @@ gtk_tree_view_row_inserted (GtkTreeModel *model,
   if (height > 0)
     {
       if (tree)
-        _gtk_rbtree_node_mark_valid (tree, tmpnode);
+        gtk_tree_rbtree_node_mark_valid (tree, tmpnode);
 
       if (node_visible && node_is_visible (tree_view, tree, tmpnode))
        gtk_widget_queue_resize (GTK_WIDGET (tree_view));
@@ -8322,8 +8322,8 @@ gtk_tree_view_row_has_child_toggled (GtkTreeModel *model,
   GtkTreeView *tree_view = (GtkTreeView *)data;
   GtkTreeIter real_iter;
   gboolean has_child;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gboolean free_path = FALSE;
 
   g_return_if_fail (path != NULL || iter != NULL);
@@ -8352,17 +8352,17 @@ gtk_tree_view_row_has_child_toggled (GtkTreeModel *model,
   has_child = gtk_tree_model_iter_has_child (model, &real_iter);
   /* Sanity check.
    */
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT) == has_child)
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT) == has_child)
     goto done;
 
   if (has_child)
     {
-      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_IS_PARENT);
+      GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_IS_PARENT);
       _gtk_tree_view_accessible_add_state (tree_view, tree, node, GTK_CELL_RENDERER_EXPANDABLE);
     }
   else
     {
-      GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_IS_PARENT);
+      GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_IS_PARENT);
       _gtk_tree_view_accessible_remove_state (tree_view, tree, node, GTK_CELL_RENDERER_EXPANDABLE);
     }
 
@@ -8393,16 +8393,16 @@ gtk_tree_view_row_has_child_toggled (GtkTreeModel *model,
 }
 
 static void
-check_selection_helper (GtkRBTree *tree,
-                        GtkRBNode *node,
-                        gpointer   data)
+check_selection_helper (GtkTreeRBTree *tree,
+                        GtkTreeRBNode *node,
+                        gpointer       data)
 {
   gint *value = (gint *)data;
 
-  *value |= GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED);
+  *value |= GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED);
 
   if (node->children && !*value)
-    _gtk_rbtree_traverse (node->children, node->children->root, G_POST_ORDER, check_selection_helper, data);
+    gtk_tree_rbtree_traverse (node->children, node->children->root, G_POST_ORDER, check_selection_helper, 
data);
 }
 
 static void
@@ -8411,12 +8411,12 @@ gtk_tree_view_row_deleted (GtkTreeModel *model,
                           gpointer      data)
 {
   GtkTreeView *tree_view = (GtkTreeView *)data;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GList *list;
   gboolean selection_changed = FALSE, cursor_changed = FALSE;
-  GtkRBTree *cursor_tree = NULL;
-  GtkRBNode *cursor_node = NULL;
+  GtkTreeRBTree *cursor_tree = NULL;
+  GtkTreeRBNode *cursor_node = NULL;
 
   g_return_if_fail (path != NULL);
 
@@ -8429,7 +8429,7 @@ gtk_tree_view_row_deleted (GtkTreeModel *model,
     return;
 
   /* check if the selection has been changed */
-  _gtk_rbtree_traverse (tree, node, G_POST_ORDER,
+  gtk_tree_rbtree_traverse (tree, node, G_POST_ORDER,
                         check_selection_helper, &selection_changed);
 
   for (list = tree_view->priv->columns; list; list = list->next)
@@ -8447,16 +8447,16 @@ gtk_tree_view_row_deleted (GtkTreeModel *model,
   if (tree_view->priv->cursor_node &&
       (tree_view->priv->cursor_node == node ||
        (node->children && (tree_view->priv->cursor_tree == node->children ||
-                           _gtk_rbtree_contains (node->children, tree_view->priv->cursor_tree)))))
+                           gtk_tree_rbtree_contains (node->children, tree_view->priv->cursor_tree)))))
     {
       GtkTreePath *cursor_path;
 
       cursor_tree = tree;
-      cursor_node = _gtk_rbtree_next (tree, node);
+      cursor_node = gtk_tree_rbtree_next (tree, node);
       /* find the first node that is not going to be deleted */
       while (cursor_node == NULL && cursor_tree->parent_tree)
         {
-          cursor_node = _gtk_rbtree_next (cursor_tree->parent_tree,
+          cursor_node = gtk_tree_rbtree_next (cursor_tree->parent_tree,
                                           cursor_tree->parent_node);
           cursor_tree = cursor_tree->parent_tree;
         }
@@ -8474,7 +8474,7 @@ gtk_tree_view_row_deleted (GtkTreeModel *model,
            * a focusable row.  We will step backwards to find the last
            * focusable row.
            */
-          _gtk_rbtree_prev_full (tree, node, &cursor_tree, &cursor_node);
+          gtk_tree_rbtree_prev_full (tree, node, &cursor_tree, &cursor_node);
           if (cursor_node)
             {
               cursor_path = _gtk_tree_path_new_from_rbtree (cursor_tree, cursor_node);
@@ -8499,12 +8499,12 @@ gtk_tree_view_row_deleted (GtkTreeModel *model,
                                               tree->parent_tree, tree->parent_node,
                                               GTK_CELL_RENDERER_EXPANDED);
       _gtk_tree_view_accessible_remove (tree_view, tree, NULL);
-      _gtk_rbtree_remove (tree);
+      gtk_tree_rbtree_remove (tree);
     }
   else
     {
       _gtk_tree_view_accessible_remove (tree_view, tree, node);
-      _gtk_rbtree_remove_node (tree, node);
+      gtk_tree_rbtree_remove_node (tree, node);
     }
 
   if (! gtk_tree_row_reference_valid (tree_view->priv->top_row))
@@ -8540,8 +8540,8 @@ gtk_tree_view_rows_reordered (GtkTreeModel *model,
                              gpointer      data)
 {
   GtkTreeView *tree_view = GTK_TREE_VIEW (data);
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gint len;
 
   len = gtk_tree_model_iter_n_children (model, iter);
@@ -8575,7 +8575,7 @@ gtk_tree_view_rows_reordered (GtkTreeModel *model,
   /* we need to be unprelighted */
   ensure_unprelighted (tree_view);
 
-  _gtk_rbtree_reorder (tree, new_order, len);
+  gtk_tree_rbtree_reorder (tree, new_order, len);
 
   _gtk_tree_view_accessible_reorder (tree_view);
 
@@ -8591,7 +8591,7 @@ gtk_tree_view_rows_reordered (GtkTreeModel *model,
 
 static void
 gtk_tree_view_get_background_xrange (GtkTreeView       *tree_view,
-                                     GtkRBTree         *tree,
+                                     GtkTreeRBTree     *tree,
                                      GtkTreeViewColumn *column,
                                      gint              *x1,
                                      gint              *x2)
@@ -8642,10 +8642,10 @@ gtk_tree_view_get_background_xrange (GtkTreeView       *tree_view,
 }
 
 static void
-gtk_tree_view_get_arrow_xrange (GtkTreeView *tree_view,
-                               GtkRBTree   *tree,
-                                gint        *x1,
-                                gint        *x2)
+gtk_tree_view_get_arrow_xrange (GtkTreeView   *tree_view,
+                               GtkTreeRBTree *tree,
+                                gint          *x1,
+                                gint          *x2)
 {
   gint x_offset = 0;
   GList *list;
@@ -8681,9 +8681,9 @@ gtk_tree_view_get_arrow_xrange (GtkTreeView *tree_view,
   x_offset += (expander_size - expander_render_size);
 
   if (rtl)
-    x_offset -= expander_size * _gtk_rbtree_get_depth (tree);
+    x_offset -= expander_size * gtk_tree_rbtree_get_depth (tree);
   else
-    x_offset += expander_size * _gtk_rbtree_get_depth (tree);
+    x_offset += expander_size * gtk_tree_rbtree_get_depth (tree);
 
   *x1 = x_offset;
 
@@ -8696,26 +8696,26 @@ gtk_tree_view_get_arrow_xrange (GtkTreeView *tree_view,
 }
 
 static void
-gtk_tree_view_build_tree (GtkTreeView *tree_view,
-                         GtkRBTree   *tree,
-                         GtkTreeIter *iter,
-                         gint         depth,
-                         gboolean     recurse)
+gtk_tree_view_build_tree (GtkTreeView   *tree_view,
+                         GtkTreeRBTree *tree,
+                         GtkTreeIter   *iter,
+                         gint           depth,
+                         gboolean       recurse)
 {
-  GtkRBNode *temp = NULL;
+  GtkTreeRBNode *temp = NULL;
   GtkTreePath *path = NULL;
 
   do
     {
       gtk_tree_model_ref_node (tree_view->priv->model, iter);
-      temp = _gtk_rbtree_insert_after (tree, temp, 0, FALSE);
+      temp = gtk_tree_rbtree_insert_after (tree, temp, 0, FALSE);
 
       if (tree_view->priv->fixed_height > 0)
         {
-          if (GTK_RBNODE_FLAG_SET (temp, GTK_RBNODE_INVALID))
+          if (GTK_TREE_RBNODE_FLAG_SET (temp, GTK_TREE_RBNODE_INVALID))
            {
-              _gtk_rbtree_node_set_height (tree, temp, tree_view->priv->fixed_height);
-             _gtk_rbtree_node_mark_valid (tree, temp);
+              gtk_tree_rbtree_node_set_height (tree, temp, tree_view->priv->fixed_height);
+             gtk_tree_rbtree_node_mark_valid (tree, temp);
            }
         }
 
@@ -8740,7 +8740,7 @@ gtk_tree_view_build_tree (GtkTreeView *tree_view,
              if (gtk_tree_model_iter_has_child (tree_view->priv->model, iter)
                  && !expand)
                {
-                 temp->children = _gtk_rbtree_new ();
+                 temp->children = gtk_tree_rbtree_new ();
                  temp->children->parent_tree = tree;
                  temp->children->parent_node = temp;
                  gtk_tree_view_build_tree (tree_view, temp->children, &child, depth + 1, recurse);
@@ -8750,8 +8750,8 @@ gtk_tree_view_build_tree (GtkTreeView *tree_view,
 
       if (gtk_tree_model_iter_has_child (tree_view->priv->model, iter))
        {
-         if ((temp->flags&GTK_RBNODE_IS_PARENT) != GTK_RBNODE_IS_PARENT)
-           temp->flags ^= GTK_RBNODE_IS_PARENT;
+         if ((temp->flags&GTK_TREE_RBNODE_IS_PARENT) != GTK_TREE_RBNODE_IS_PARENT)
+           temp->flags ^= GTK_TREE_RBNODE_IS_PARENT;
        }
     }
   while (gtk_tree_model_iter_next (tree_view->priv->model, iter));
@@ -8762,9 +8762,9 @@ gtk_tree_view_build_tree (GtkTreeView *tree_view,
 
 /* Make sure the node is visible vertically */
 static void
-gtk_tree_view_clamp_node_visible (GtkTreeView *tree_view,
-                                 GtkRBTree   *tree,
-                                 GtkRBNode   *node)
+gtk_tree_view_clamp_node_visible (GtkTreeView   *tree_view,
+                                 GtkTreeRBTree *tree,
+                                 GtkTreeRBNode *node)
 {
   gint node_dy, height;
   GtkTreePath *path = NULL;
@@ -8773,9 +8773,9 @@ gtk_tree_view_clamp_node_visible (GtkTreeView *tree_view,
     return;
 
   /* just return if the node is visible, avoiding a costly expose */
-  node_dy = _gtk_rbtree_node_find_offset (tree, node);
+  node_dy = gtk_tree_rbtree_node_find_offset (tree, node);
   height = gtk_tree_view_get_row_height (tree_view, node);
-  if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)
+  if (! GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)
       && node_dy >= gtk_adjustment_get_value (tree_view->priv->vadjustment)
       && node_dy + height <= (gtk_adjustment_get_value (tree_view->priv->vadjustment)
                               + gtk_adjustment_get_page_size (tree_view->priv->vadjustment)))
@@ -8853,12 +8853,12 @@ gtk_tree_view_clamp_column_visible (GtkTreeView       *tree_view,
 /* This function could be more efficient.  I'll optimize it if profiling seems
  * to imply that it is important */
 GtkTreePath *
-_gtk_tree_path_new_from_rbtree (GtkRBTree   *tree,
-                               GtkRBNode   *node)
+_gtk_tree_path_new_from_rbtree (GtkTreeRBTree *tree,
+                               GtkTreeRBNode *node)
 {
   GtkTreePath *path;
-  GtkRBTree *tmp_tree;
-  GtkRBNode *tmp_node, *last;
+  GtkTreeRBTree *tmp_tree;
+  GtkTreeRBNode *tmp_node, *last;
   gint count;
 
   path = gtk_tree_path_new ();
@@ -8872,7 +8872,7 @@ _gtk_tree_path_new_from_rbtree (GtkRBTree   *tree,
   tmp_tree = tree;
   while (tmp_tree)
     {
-      while (!_gtk_rbtree_is_nil (tmp_node))
+      while (!gtk_tree_rbtree_is_nil (tmp_node))
        {
          if (tmp_node->right == last)
            count += 1 + tmp_node->left->count;
@@ -8896,13 +8896,13 @@ _gtk_tree_path_new_from_rbtree (GtkRBTree   *tree,
  * both set to NULL.
  */
 gboolean
-_gtk_tree_view_find_node (GtkTreeView  *tree_view,
-                         GtkTreePath  *path,
-                         GtkRBTree   **tree,
-                         GtkRBNode   **node)
+_gtk_tree_view_find_node (GtkTreeView    *tree_view,
+                         GtkTreePath    *path,
+                         GtkTreeRBTree **tree,
+                         GtkTreeRBNode **node)
 {
-  GtkRBNode *tmpnode = NULL;
-  GtkRBTree *tmptree = tree_view->priv->tree;
+  GtkTreeRBNode *tmpnode = NULL;
+  GtkTreeRBTree *tmptree = tree_view->priv->tree;
   gint *indices = gtk_tree_path_get_indices (path);
   gint depth = gtk_tree_path_get_depth (path);
   gint i = 0;
@@ -8914,7 +8914,7 @@ _gtk_tree_view_find_node (GtkTreeView  *tree_view,
     return FALSE;
   do
     {
-      tmpnode = _gtk_rbtree_find_count (tmptree, indices[i] + 1);
+      tmpnode = gtk_tree_rbtree_find_count (tmptree, indices[i] + 1);
       ++i;
       if (tmpnode == NULL)
        {
@@ -9009,10 +9009,10 @@ gtk_tree_view_add_move_binding (GtkBindingSet  *binding_set,
 }
 
 static gint
-gtk_tree_view_unref_tree_helper (GtkTreeModel *model,
-                                GtkTreeIter  *iter,
-                                GtkRBTree    *tree,
-                                GtkRBNode    *node)
+gtk_tree_view_unref_tree_helper (GtkTreeModel  *model,
+                                GtkTreeIter   *iter,
+                                GtkTreeRBTree *tree,
+                                GtkTreeRBNode *node)
 {
   gint retval = FALSE;
   do
@@ -9022,11 +9022,11 @@ gtk_tree_view_unref_tree_helper (GtkTreeModel *model,
       if (node->children)
        {
          GtkTreeIter child;
-         GtkRBTree *new_tree;
-         GtkRBNode *new_node;
+         GtkTreeRBTree *new_tree;
+         GtkTreeRBNode *new_node;
 
          new_tree = node->children;
-          new_node = _gtk_rbtree_first (new_tree);
+          new_node = gtk_tree_rbtree_first (new_tree);
 
          if (!gtk_tree_model_iter_children (model, &child, iter))
            return FALSE;
@@ -9034,10 +9034,10 @@ gtk_tree_view_unref_tree_helper (GtkTreeModel *model,
          retval = gtk_tree_view_unref_tree_helper (model, &child, new_tree, new_node) | retval;
        }
 
-      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+      if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
        retval = TRUE;
       gtk_tree_model_unref_node (model, iter);
-      node = _gtk_rbtree_next (tree, node);
+      node = gtk_tree_rbtree_next (tree, node);
     }
   while (gtk_tree_model_iter_next (model, iter));
 
@@ -9045,18 +9045,18 @@ gtk_tree_view_unref_tree_helper (GtkTreeModel *model,
 }
 
 static gint
-gtk_tree_view_unref_and_check_selection_tree (GtkTreeView *tree_view,
-                                             GtkRBTree   *tree)
+gtk_tree_view_unref_and_check_selection_tree (GtkTreeView   *tree_view,
+                                             GtkTreeRBTree *tree)
 {
   GtkTreeIter iter;
   GtkTreePath *path;
-  GtkRBNode *node;
+  GtkTreeRBNode *node;
   gint retval;
 
   if (!tree)
     return FALSE;
 
-  node = _gtk_rbtree_first (tree);
+  node = gtk_tree_rbtree_first (tree);
 
   g_return_val_if_fail (node != NULL, FALSE);
   path = _gtk_tree_path_new_from_rbtree (tree, node);
@@ -9254,16 +9254,16 @@ _gtk_tree_view_set_anchor_path (GtkTreeView *tree_view,
                                        tree_view->priv->model, anchor_path);
 }
 
-GtkRBTree *
+GtkTreeRBTree *
 _gtk_tree_view_get_rbtree (GtkTreeView *tree_view)
 {
   return tree_view->priv->tree;
 }
 
 gboolean
-_gtk_tree_view_get_cursor_node (GtkTreeView  *tree_view,
-                                GtkRBTree   **tree,
-                                GtkRBNode   **node)
+_gtk_tree_view_get_cursor_node (GtkTreeView    *tree_view,
+                                GtkTreeRBTree **tree,
+                                GtkTreeRBNode **node)
 {
   GtkTreeViewPrivate *priv;
 
@@ -9303,10 +9303,10 @@ _gtk_tree_view_set_focus_column (GtkTreeView       *tree_view,
 /* x and y are the mouse position
  */
 static void
-gtk_tree_view_snapshot_arrow (GtkTreeView *tree_view,
-                              GtkSnapshot *snapshot,
-                              GtkRBTree   *tree,
-                              GtkRBNode   *node)
+gtk_tree_view_snapshot_arrow (GtkTreeView   *tree_view,
+                              GtkSnapshot   *snapshot,
+                              GtkTreeRBTree *tree,
+                              GtkTreeRBNode *node)
 {
   GdkRectangle area;
   GtkStateFlags state = 0;
@@ -9322,7 +9322,7 @@ gtk_tree_view_snapshot_arrow (GtkTreeView *tree_view,
   context = gtk_widget_get_style_context (widget);
   rtl = (_gtk_widget_get_direction (widget) == GTK_TEXT_DIR_RTL);
 
-  if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT))
+  if (! GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT))
     return;
 
   gtk_tree_view_get_arrow_xrange (tree_view, tree, &x_offset, &x2);
@@ -9332,7 +9332,7 @@ gtk_tree_view_snapshot_arrow (GtkTreeView *tree_view,
   area.width = x2 - x_offset;
   area.height = gtk_tree_view_get_cell_area_height (tree_view, node);
 
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_SELECTED))
+  if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_SELECTED))
     flags |= GTK_CELL_RENDERER_SELECTED;
 
   if (node == tree_view->priv->prelight_node &&
@@ -9457,8 +9457,8 @@ gtk_tree_view_move_cursor_up_down (GtkTreeView *tree_view,
                                   gint         count)
 {
   gint selection_count;
-  GtkRBTree *new_cursor_tree = NULL;
-  GtkRBNode *new_cursor_node = NULL;
+  GtkTreeRBTree *new_cursor_tree = NULL;
+  GtkTreeRBNode *new_cursor_node = NULL;
   GtkTreePath *cursor_path = NULL;
   gboolean grab_focus = TRUE;
   gboolean selectable;
@@ -9488,7 +9488,7 @@ gtk_tree_view_move_cursor_up_down (GtkTreeView *tree_view,
       gtk_tree_view_column_cell_set_cell_data (tree_view->priv->focus_column,
                                               tree_view->priv->model,
                                                &iter,
-                                               GTK_RBNODE_FLAG_SET (tree_view->priv->cursor_node, 
GTK_RBNODE_IS_PARENT),
+                                               GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->cursor_node, 
GTK_TREE_RBNODE_IS_PARENT),
                                               tree_view->priv->cursor_node->children ? TRUE : FALSE);
 
       /* Save the last cell that had focus, if we hit the end of the view we'll give
@@ -9517,10 +9517,10 @@ gtk_tree_view_move_cursor_up_down (GtkTreeView *tree_view,
   else
     {
       if (count == -1)
-       _gtk_rbtree_prev_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
+       gtk_tree_rbtree_prev_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
                               &new_cursor_tree, &new_cursor_node);
       else
-       _gtk_rbtree_next_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
+       gtk_tree_rbtree_next_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
                               &new_cursor_tree, &new_cursor_node);
     }
 
@@ -9547,14 +9547,14 @@ gtk_tree_view_move_cursor_up_down (GtkTreeView *tree_view,
       new_cursor_node == NULL)
     {
       if (count == -1)
-        _gtk_rbtree_next_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
+        gtk_tree_rbtree_next_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
                               &new_cursor_tree, &new_cursor_node);
       else
-        _gtk_rbtree_prev_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
+        gtk_tree_rbtree_prev_full (tree_view->priv->cursor_tree, tree_view->priv->cursor_node,
                               &new_cursor_tree, &new_cursor_node);
 
       if (new_cursor_node == NULL
-         && !GTK_RBNODE_FLAG_SET (tree_view->priv->cursor_node, GTK_RBNODE_IS_SELECTED))
+         && !GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->cursor_node, GTK_TREE_RBNODE_IS_SELECTED))
         {
           new_cursor_node = tree_view->priv->cursor_node;
           new_cursor_tree = tree_view->priv->cursor_tree;
@@ -9618,10 +9618,10 @@ gtk_tree_view_move_cursor_page_up_down (GtkTreeView *tree_view,
 {
   GtkTreePath *old_cursor_path = NULL;
   GtkTreePath *cursor_path = NULL;
-  GtkRBTree *start_cursor_tree = NULL;
-  GtkRBNode *start_cursor_node = NULL;
-  GtkRBTree *cursor_tree;
-  GtkRBNode *cursor_node;
+  GtkTreeRBTree *start_cursor_tree = NULL;
+  GtkTreeRBNode *start_cursor_node = NULL;
+  GtkTreeRBTree *cursor_tree;
+  GtkTreeRBNode *cursor_node;
   gint y;
   gint window_y;
 
@@ -9634,7 +9634,7 @@ gtk_tree_view_move_cursor_page_up_down (GtkTreeView *tree_view,
   old_cursor_path = _gtk_tree_path_new_from_rbtree (tree_view->priv->cursor_tree,
                                                     tree_view->priv->cursor_node);
 
-  y = _gtk_rbtree_node_find_offset (tree_view->priv->cursor_tree, tree_view->priv->cursor_node);
+  y = gtk_tree_rbtree_node_find_offset (tree_view->priv->cursor_tree, tree_view->priv->cursor_node);
   window_y = RBTREE_Y_TO_TREE_WINDOW_Y (tree_view, y);
   y += tree_view->priv->cursor_offset;
   y += count * (int)gtk_adjustment_get_page_increment (tree_view->priv->vadjustment);
@@ -9644,7 +9644,7 @@ gtk_tree_view_move_cursor_page_up_down (GtkTreeView *tree_view,
     y = gtk_tree_view_get_height (tree_view) - 1;
 
   tree_view->priv->cursor_offset =
-    _gtk_rbtree_find_offset (tree_view->priv->tree, y,
+    gtk_tree_rbtree_find_offset (tree_view->priv->tree, y,
                             &cursor_tree, &cursor_node);
 
   if (cursor_tree == NULL)
@@ -9657,7 +9657,7 @@ gtk_tree_view_move_cursor_page_up_down (GtkTreeView *tree_view,
   if (tree_view->priv->cursor_offset
       > gtk_tree_view_get_row_height (tree_view, cursor_node))
     {
-      _gtk_rbtree_next_full (cursor_tree, cursor_node,
+      gtk_tree_rbtree_next_full (cursor_tree, cursor_node,
                             &cursor_tree, &cursor_node);
       tree_view->priv->cursor_offset -= gtk_tree_view_get_row_height (tree_view, cursor_node);
     }
@@ -9689,7 +9689,7 @@ gtk_tree_view_move_cursor_page_up_down (GtkTreeView *tree_view,
     goto cleanup;
 
   /* update y */
-  y = _gtk_rbtree_node_find_offset (cursor_tree, cursor_node);
+  y = gtk_tree_rbtree_node_find_offset (cursor_tree, cursor_node);
 
   gtk_tree_view_real_set_cursor (tree_view, cursor_path, CLEAR_AND_SELECT);
 
@@ -9767,7 +9767,7 @@ gtk_tree_view_move_cursor_left_right (GtkTreeView *tree_view,
       gtk_tree_view_column_cell_set_cell_data (column,
                                               tree_view->priv->model,
                                               &iter,
-                                              GTK_RBNODE_FLAG_SET (tree_view->priv->cursor_node, 
GTK_RBNODE_IS_PARENT),
+                                              GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->cursor_node, 
GTK_TREE_RBNODE_IS_PARENT),
                                               tree_view->priv->cursor_node->children ? TRUE : FALSE);
 
       cell_area = gtk_cell_layout_get_area (GTK_CELL_LAYOUT (column));
@@ -9808,8 +9808,8 @@ static void
 gtk_tree_view_move_cursor_start_end (GtkTreeView *tree_view,
                                     gint         count)
 {
-  GtkRBTree *cursor_tree;
-  GtkRBNode *cursor_node;
+  GtkTreeRBTree *cursor_tree;
+  GtkTreeRBNode *cursor_node;
   GtkTreePath *path;
   GtkTreePath *old_path;
 
@@ -9824,7 +9824,7 @@ gtk_tree_view_move_cursor_start_end (GtkTreeView *tree_view,
 
   if (count == -1)
     {
-      cursor_node = _gtk_rbtree_first (cursor_tree);
+      cursor_node = gtk_tree_rbtree_first (cursor_tree);
 
       /* Now go forward to find the first focusable row. */
       path = _gtk_tree_path_new_from_rbtree (cursor_tree, cursor_node);
@@ -9837,7 +9837,7 @@ gtk_tree_view_move_cursor_start_end (GtkTreeView *tree_view,
 
       do
        {
-         while (cursor_node && !_gtk_rbtree_is_nil (cursor_node->right))
+         while (cursor_node && !gtk_tree_rbtree_is_nil (cursor_node->right))
            cursor_node = cursor_node->right;
          if (cursor_node->children == NULL)
            break;
@@ -9903,10 +9903,10 @@ static gboolean
 gtk_tree_view_real_select_cursor_row (GtkTreeView *tree_view,
                                      gboolean     start_editing)
 {
-  GtkRBTree *new_tree = NULL;
-  GtkRBNode *new_node = NULL;
-  GtkRBTree *cursor_tree = NULL;
-  GtkRBNode *cursor_node = NULL;
+  GtkTreeRBTree *new_tree = NULL;
+  GtkTreeRBNode *new_node = NULL;
+  GtkTreeRBTree *cursor_tree = NULL;
+  GtkTreeRBNode *cursor_node = NULL;
   GtkTreePath *cursor_path = NULL;
   GtkTreeSelectMode mode = 0;
 
@@ -9976,8 +9976,8 @@ gtk_tree_view_real_select_cursor_row (GtkTreeView *tree_view,
 static gboolean
 gtk_tree_view_real_toggle_cursor_row (GtkTreeView *tree_view)
 {
-  GtkRBTree *new_tree = NULL;
-  GtkRBNode *new_node = NULL;
+  GtkTreeRBTree *new_tree = NULL;
+  GtkTreeRBNode *new_node = NULL;
   GtkTreePath *cursor_path = NULL;
 
   if (!gtk_widget_has_focus (GTK_WIDGET (tree_view)))
@@ -10034,7 +10034,7 @@ gtk_tree_view_real_expand_collapse_cursor_row (GtkTreeView *tree_view,
                                                 tree_view->priv->cursor_node);
 
   /* Don't handle the event if we aren't an expander */
-  if (!GTK_RBNODE_FLAG_SET (tree_view->priv->cursor_node, GTK_RBNODE_IS_PARENT))
+  if (!GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->cursor_node, GTK_TREE_RBNODE_IS_PARENT))
     return FALSE;
 
   if (!logical
@@ -10554,7 +10554,7 @@ gtk_tree_view_set_model (GtkTreeView  *tree_view,
       path = gtk_tree_path_new_first ();
       if (gtk_tree_model_get_iter (tree_view->priv->model, &iter, path))
        {
-         tree_view->priv->tree = _gtk_rbtree_new ();
+         tree_view->priv->tree = gtk_tree_rbtree_new ();
          gtk_tree_view_build_tree (tree_view, tree_view->priv->tree, &iter, 1, FALSE);
           _gtk_tree_view_accessible_add (tree_view, tree_view->priv->tree, NULL);
        }
@@ -11379,7 +11379,7 @@ gtk_tree_view_scroll_to_cell (GtkTreeView       *tree_view,
   if (!gtk_widget_get_visible (GTK_WIDGET (tree_view)) ||
       !gtk_widget_get_realized (GTK_WIDGET (tree_view)) ||
       _gtk_widget_get_alloc_needed (GTK_WIDGET (tree_view)) ||
-      GTK_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_RBNODE_DESCENDANTS_INVALID))
+      GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID))
     {
       if (tree_view->priv->scroll_to_path)
        gtk_tree_row_reference_free (tree_view->priv->scroll_to_path);
@@ -11466,13 +11466,13 @@ gtk_tree_view_row_activated (GtkTreeView       *tree_view,
 
 
 static void
-gtk_tree_view_expand_all_emission_helper (GtkRBTree *tree,
-                                          GtkRBNode *node,
-                                          gpointer   data)
+gtk_tree_view_expand_all_emission_helper (GtkTreeRBTree *tree,
+                                          GtkTreeRBNode *node,
+                                          gpointer       data)
 {
   GtkTreeView *tree_view = data;
 
-  if ((node->flags & GTK_RBNODE_IS_PARENT) == GTK_RBNODE_IS_PARENT &&
+  if ((node->flags & GTK_TREE_RBNODE_IS_PARENT) == GTK_TREE_RBNODE_IS_PARENT &&
       node->children)
     {
       GtkTreePath *path;
@@ -11487,7 +11487,7 @@ gtk_tree_view_expand_all_emission_helper (GtkRBTree *tree,
     }
 
   if (node->children)
-    _gtk_rbtree_traverse (node->children,
+    gtk_tree_rbtree_traverse (node->children,
                           node->children->root,
                           G_PRE_ORDER,
                           gtk_tree_view_expand_all_emission_helper,
@@ -11504,8 +11504,8 @@ void
 gtk_tree_view_expand_all (GtkTreeView *tree_view)
 {
   GtkTreePath *path;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   g_return_if_fail (GTK_IS_TREE_VIEW (tree_view));
 
@@ -11518,7 +11518,7 @@ gtk_tree_view_expand_all (GtkTreeView *tree_view)
   while (node)
     {
       gtk_tree_view_real_expand_row (tree_view, path, tree, node, TRUE, FALSE);
-      node = _gtk_rbtree_next (tree, node);
+      node = gtk_tree_rbtree_next (tree, node);
       gtk_tree_path_next (path);
   }
 
@@ -11534,8 +11534,8 @@ gtk_tree_view_expand_all (GtkTreeView *tree_view)
 void
 gtk_tree_view_collapse_all (GtkTreeView *tree_view)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GtkTreePath *path;
   gint *indices;
 
@@ -11549,14 +11549,14 @@ gtk_tree_view_collapse_all (GtkTreeView *tree_view)
   indices = gtk_tree_path_get_indices (path);
 
   tree = tree_view->priv->tree;
-  node = _gtk_rbtree_first (tree);
+  node = gtk_tree_rbtree_first (tree);
 
   while (node)
     {
       if (node->children)
        gtk_tree_view_real_collapse_row (tree_view, path, tree, node, FALSE);
       indices[0]++;
-      node = _gtk_rbtree_next (tree, node);
+      node = gtk_tree_rbtree_next (tree, node);
     }
 
   gtk_tree_path_free (path);
@@ -11603,12 +11603,12 @@ gtk_tree_view_expand_to_path (GtkTreeView *tree_view,
 
 
 static gboolean
-gtk_tree_view_real_expand_row (GtkTreeView *tree_view,
-                              GtkTreePath *path,
-                              GtkRBTree   *tree,
-                              GtkRBNode   *node,
-                              gboolean     open_all,
-                              gboolean     animate)
+gtk_tree_view_real_expand_row (GtkTreeView   *tree_view,
+                              GtkTreePath   *path,
+                              GtkTreeRBTree *tree,
+                              GtkTreeRBNode *node,
+                              gboolean       open_all,
+                              gboolean       animate)
 {
   GtkTreeIter iter;
   GtkTreeIter temp;
@@ -11622,7 +11622,7 @@ gtk_tree_view_real_expand_row (GtkTreeView *tree_view,
   if (node->children && !open_all)
     return FALSE;
 
-  if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT))
+  if (! GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT))
     return FALSE;
 
   gtk_tree_model_get_iter (tree_view->priv->model, &iter, path);
@@ -11637,7 +11637,7 @@ gtk_tree_view_real_expand_row (GtkTreeView *tree_view,
 
       gtk_tree_path_append_index (tmp_path, 0);
       tree = node->children;
-      node = _gtk_rbtree_first (tree);
+      node = gtk_tree_rbtree_first (tree);
       /* try to expand the children */
       do
         {
@@ -11648,7 +11648,7 @@ gtk_tree_view_real_expand_row (GtkTreeView *tree_view,
            retval = TRUE;
 
          gtk_tree_path_next (tmp_path);
-        node = _gtk_rbtree_next (tree, node);
+        node = gtk_tree_rbtree_next (tree, node);
        }
       while (node != NULL);
 
@@ -11665,7 +11665,7 @@ gtk_tree_view_real_expand_row (GtkTreeView *tree_view,
   if (expand)
     return FALSE;
 
-  node->children = _gtk_rbtree_new ();
+  node->children = gtk_tree_rbtree_new ();
   node->children->parent_tree = tree;
   node->children->parent_node = node;
 
@@ -11687,7 +11687,7 @@ gtk_tree_view_real_expand_row (GtkTreeView *tree_view,
   g_signal_emit (tree_view, tree_view_signals[ROW_EXPANDED], 0, &iter, path);
   if (open_all && node->children)
     {
-      _gtk_rbtree_traverse (node->children,
+      gtk_tree_rbtree_traverse (node->children,
                             node->children->root,
                             G_PRE_ORDER,
                             gtk_tree_view_expand_all_emission_helper,
@@ -11712,8 +11712,8 @@ gtk_tree_view_expand_row (GtkTreeView *tree_view,
                          GtkTreePath *path,
                          gboolean     open_all)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   g_return_val_if_fail (GTK_IS_TREE_VIEW (tree_view), FALSE);
   g_return_val_if_fail (tree_view->priv->model != NULL, FALSE);
@@ -11732,11 +11732,11 @@ gtk_tree_view_expand_row (GtkTreeView *tree_view,
 }
 
 static gboolean
-gtk_tree_view_real_collapse_row (GtkTreeView *tree_view,
-                                GtkTreePath *path,
-                                GtkRBTree   *tree,
-                                GtkRBNode   *node,
-                                gboolean     animate)
+gtk_tree_view_real_collapse_row (GtkTreeView   *tree_view,
+                                GtkTreePath   *path,
+                                GtkTreeRBTree *tree,
+                                GtkTreeRBNode *node,
+                                gboolean       animate)
 {
   GtkTreeIter iter;
   GtkTreeIter children;
@@ -11763,8 +11763,8 @@ gtk_tree_view_real_collapse_row (GtkTreeView *tree_view,
 
   if (tree_view->priv->prelight_tree)
     {
-      GtkRBTree *parent_tree;
-      GtkRBNode *parent_node;
+      GtkTreeRBTree *parent_tree;
+      GtkTreeRBNode *parent_node;
 
       parent_tree = tree_view->priv->prelight_tree->parent_tree;
       parent_node = tree_view->priv->prelight_tree->parent_node;
@@ -11795,7 +11795,7 @@ gtk_tree_view_real_collapse_row (GtkTreeView *tree_view,
   if (tree_view->priv->cursor_node)
     {
       cursor_changed = (node->children == tree_view->priv->cursor_tree)
-                       || _gtk_rbtree_contains (node->children, tree_view->priv->cursor_tree);
+                       || gtk_tree_rbtree_contains (node->children, tree_view->priv->cursor_tree);
     }
   else
     cursor_changed = FALSE;
@@ -11821,7 +11821,7 @@ gtk_tree_view_real_collapse_row (GtkTreeView *tree_view,
                                           tree, node,
                                           GTK_CELL_RENDERER_EXPANDED);
 
-  _gtk_rbtree_remove (node->children);
+  gtk_tree_rbtree_remove (node->children);
 
   if (cursor_changed)
     gtk_tree_view_real_set_cursor (tree_view, path, CLEAR_AND_SELECT | CURSOR_INVALID);
@@ -11856,8 +11856,8 @@ gboolean
 gtk_tree_view_collapse_row (GtkTreeView *tree_view,
                            GtkTreePath *path)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   g_return_val_if_fail (GTK_IS_TREE_VIEW (tree_view), FALSE);
   g_return_val_if_fail (tree_view->priv->tree != NULL, FALSE);
@@ -11877,17 +11877,17 @@ gtk_tree_view_collapse_row (GtkTreeView *tree_view,
 
 static void
 gtk_tree_view_map_expanded_rows_helper (GtkTreeView            *tree_view,
-                                       GtkRBTree              *tree,
+                                       GtkTreeRBTree          *tree,
                                        GtkTreePath            *path,
                                        GtkTreeViewMappingFunc  func,
                                        gpointer                user_data)
 {
-  GtkRBNode *node;
+  GtkTreeRBNode *node;
 
   if (tree == NULL || tree->root == NULL)
     return;
 
-  node = _gtk_rbtree_first (tree);
+  node = gtk_tree_rbtree_first (tree);
 
   while (node)
     {
@@ -11899,7 +11899,7 @@ gtk_tree_view_map_expanded_rows_helper (GtkTreeView            *tree_view,
          gtk_tree_path_up (path);
        }
       gtk_tree_path_next (path);
-      node = _gtk_rbtree_next (tree, node);
+      node = gtk_tree_rbtree_next (tree, node);
     }
 }
 
@@ -11943,8 +11943,8 @@ gboolean
 gtk_tree_view_row_expanded (GtkTreeView *tree_view,
                            GtkTreePath *path)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
   g_return_val_if_fail (GTK_IS_TREE_VIEW (tree_view), FALSE);
   g_return_val_if_fail (path != NULL, FALSE);
@@ -12067,8 +12067,8 @@ gtk_tree_view_real_set_cursor (GtkTreeView     *tree_view,
 
   if (tree_view->priv->cursor_node != NULL)
     {
-      GtkRBTree *new_tree = NULL;
-      GtkRBNode *new_node = NULL;
+      GtkTreeRBTree *new_tree = NULL;
+      GtkTreeRBNode *new_node = NULL;
 
       if ((flags & CLEAR_AND_SELECT) && !tree_view->priv->modify_selection_pressed)
         {
@@ -12293,8 +12293,8 @@ gtk_tree_view_get_path_at_pos (GtkTreeView        *tree_view,
                                gint               *cell_x,
                                gint               *cell_y)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gint y_offset;
 
   g_return_val_if_fail (tree_view != NULL, FALSE);
@@ -12370,7 +12370,7 @@ gtk_tree_view_get_path_at_pos (GtkTreeView        *tree_view,
        }
     }
 
-  y_offset = _gtk_rbtree_find_offset (tree_view->priv->tree,
+  y_offset = gtk_tree_rbtree_find_offset (tree_view->priv->tree,
                                      TREE_WINDOW_Y_TO_RBTREE_Y (tree_view, y),
                                      &tree, &node);
 
@@ -12388,8 +12388,8 @@ gtk_tree_view_get_path_at_pos (GtkTreeView        *tree_view,
 
 
 static inline gint
-gtk_tree_view_get_cell_area_height (GtkTreeView *tree_view,
-                                    GtkRBNode   *node)
+gtk_tree_view_get_cell_area_height (GtkTreeView   *tree_view,
+                                    GtkTreeRBNode *node)
 {
   int expander_size = gtk_tree_view_get_expander_size (tree_view);
   int height;
@@ -12410,9 +12410,9 @@ gtk_tree_view_get_cell_area_height (GtkTreeView *tree_view,
 }
 
 static inline gint
-gtk_tree_view_get_cell_area_y_offset (GtkTreeView *tree_view,
-                                      GtkRBTree   *tree,
-                                      GtkRBNode   *node)
+gtk_tree_view_get_cell_area_y_offset (GtkTreeView   *tree_view,
+                                      GtkTreeRBTree *tree,
+                                      GtkTreeRBNode *node)
 {
   int offset;
 
@@ -12444,8 +12444,8 @@ gtk_tree_view_get_cell_area (GtkTreeView        *tree_view,
                              GtkTreeViewColumn  *column,
                              GdkRectangle       *rect)
 {
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
 
   g_return_if_fail (GTK_IS_TREE_VIEW (tree_view));
   g_return_if_fail (column == NULL || GTK_IS_TREE_VIEW_COLUMN (column));
@@ -12512,8 +12512,8 @@ gtk_tree_view_get_cell_area (GtkTreeView        *tree_view,
 }
 
 static inline gint
-gtk_tree_view_get_row_height (GtkTreeView *tree_view,
-                              GtkRBNode   *node)
+gtk_tree_view_get_row_height (GtkTreeView   *tree_view,
+                              GtkTreeRBNode *node)
 {
   int expander_size = gtk_tree_view_get_expander_size (tree_view);
   int height;
@@ -12526,7 +12526,7 @@ gtk_tree_view_get_row_height (GtkTreeView *tree_view,
    * Non-regular nodes (e.g. separators) can have a height set smaller
    * than expander_size and should not be overruled here.
    */
-  height = GTK_RBNODE_GET_HEIGHT (node);
+  height = GTK_TREE_RBNODE_GET_HEIGHT (node);
   if (height <= 0)
     height = expander_size;
 
@@ -12534,13 +12534,13 @@ gtk_tree_view_get_row_height (GtkTreeView *tree_view,
 }
 
 static inline gint
-gtk_tree_view_get_row_y_offset (GtkTreeView *tree_view,
-                                GtkRBTree   *tree,
-                                GtkRBNode   *node)
+gtk_tree_view_get_row_y_offset (GtkTreeView   *tree_view,
+                                GtkTreeRBTree *tree,
+                                GtkTreeRBNode *node)
 {
   int offset;
 
-  offset = _gtk_rbtree_node_find_offset (tree, node);
+  offset = gtk_tree_rbtree_node_find_offset (tree, node);
 
   return RBTREE_Y_TO_TREE_WINDOW_Y (tree_view, offset);
 }
@@ -12569,8 +12569,8 @@ gtk_tree_view_get_background_area (GtkTreeView        *tree_view,
                                    GtkTreeViewColumn  *column,
                                    GdkRectangle       *rect)
 {
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
 
   g_return_if_fail (GTK_IS_TREE_VIEW (tree_view));
   g_return_if_fail (column == NULL || GTK_IS_TREE_VIEW_COLUMN (column));
@@ -12817,8 +12817,8 @@ gtk_tree_view_get_visible_range (GtkTreeView  *tree_view,
                                  GtkTreePath **start_path,
                                  GtkTreePath **end_path)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gboolean retval;
   
   g_return_val_if_fail (GTK_IS_TREE_VIEW (tree_view), FALSE);
@@ -12830,7 +12830,7 @@ gtk_tree_view_get_visible_range (GtkTreeView  *tree_view,
 
   if (start_path)
     {
-      _gtk_rbtree_find_offset (tree_view->priv->tree,
+      gtk_tree_rbtree_find_offset (tree_view->priv->tree,
                                TREE_WINDOW_Y_TO_RBTREE_Y (tree_view, 0),
                                &tree, &node);
       if (node)
@@ -12848,7 +12848,7 @@ gtk_tree_view_get_visible_range (GtkTreeView  *tree_view,
       else
         y = TREE_WINDOW_Y_TO_RBTREE_Y (tree_view, gtk_adjustment_get_page_size 
(tree_view->priv->vadjustment)) - 1;
 
-      _gtk_rbtree_find_offset (tree_view->priv->tree, y, &tree, &node);
+      gtk_tree_rbtree_find_offset (tree_view->priv->tree, y, &tree, &node);
       if (node)
         *end_path = _gtk_tree_path_new_from_rbtree (tree, node);
       else
@@ -12902,8 +12902,8 @@ gtk_tree_view_is_blank_at_pos (GtkTreeView       *tree_view,
                                gint               *cell_x,
                                gint               *cell_y)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GtkTreeIter iter;
   GtkTreePath *real_path;
   GtkTreeViewColumn *real_column;
@@ -12946,7 +12946,7 @@ gtk_tree_view_is_blank_at_pos (GtkTreeView       *tree_view,
   gtk_tree_view_column_cell_set_cell_data (real_column,
                                            tree_view->priv->model,
                                            &iter,
-                                           GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
+                                           GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT),
                                            node->children ? TRUE : FALSE);
 
   gtk_tree_view_get_background_area (tree_view, real_path, real_column,
@@ -13335,9 +13335,9 @@ GdkPaintable *
 gtk_tree_view_create_row_drag_icon (GtkTreeView  *tree_view,
                                     GtkTreePath  *path)
 {
-  GtkTreeIter   iter;
-  GtkRBTree    *tree;
-  GtkRBNode    *node;
+  GtkTreeIter iter;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   GtkStyleContext *context;
   gint cell_offset;
   GList *list;
@@ -13406,7 +13406,7 @@ gtk_tree_view_create_row_drag_icon (GtkTreeView  *tree_view,
         continue;
 
       gtk_tree_view_column_cell_set_cell_data (column, tree_view->priv->model, &iter,
-                                              GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_IS_PARENT),
+                                              GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_IS_PARENT),
                                               node->children?TRUE:FALSE);
 
       background_area.x = cell_offset;
@@ -13865,7 +13865,7 @@ gtk_tree_view_search_activate (GtkEntry    *entry,
   /* If we have a row selected and it's the cursor row, we activate
    * the row XXX */
   if (tree_view->priv->cursor_node &&
-      GTK_RBNODE_FLAG_SET (tree_view->priv->cursor_node, GTK_RBNODE_IS_SELECTED))
+      GTK_TREE_RBNODE_FLAG_SET (tree_view->priv->cursor_node, GTK_TREE_RBNODE_IS_SELECTED))
     {
       path = _gtk_tree_path_new_from_rbtree (tree_view->priv->cursor_tree,
                                              tree_view->priv->cursor_node);
@@ -14147,8 +14147,8 @@ gtk_tree_view_search_iter (GtkTreeModel     *model,
                           gint             *count,
                           gint              n)
 {
-  GtkRBTree *tree = NULL;
-  GtkRBNode *node = NULL;
+  GtkTreeRBTree *tree = NULL;
+  GtkTreeRBNode *node = NULL;
   GtkTreePath *path;
 
   GtkTreeView *tree_view = gtk_tree_selection_get_tree_view (selection);
@@ -14181,7 +14181,7 @@ gtk_tree_view_search_iter (GtkTreeModel     *model,
          GtkTreeIter tmp;
 
          tree = node->children;
-          node = _gtk_rbtree_first (tree);
+          node = gtk_tree_rbtree_first (tree);
 
          tmp = *iter;
          has_child = gtk_tree_model_iter_children (model, iter, &tmp);
@@ -14196,7 +14196,7 @@ gtk_tree_view_search_iter (GtkTreeModel     *model,
 
          do
            {
-             node = _gtk_rbtree_next (tree, node);
+             node = gtk_tree_rbtree_next (tree, node);
 
              if (node)
                {
@@ -14322,8 +14322,8 @@ gtk_tree_view_start_editing (GtkTreeView *tree_view,
   GtkTreeViewColumn *focus_column;
   guint flags = 0; /* can be 0, as the flags are primarily for rendering */
   gint retval = FALSE;
-  GtkRBTree *cursor_tree;
-  GtkRBNode *cursor_node;
+  GtkTreeRBTree *cursor_tree;
+  GtkTreeRBNode *cursor_node;
 
   g_assert (tree_view->priv->focus_column);
   focus_column = tree_view->priv->focus_column;
@@ -14342,7 +14342,7 @@ gtk_tree_view_start_editing (GtkTreeView *tree_view,
   gtk_tree_view_column_cell_set_cell_data (focus_column,
                                            tree_view->priv->model,
                                            &iter,
-                                           GTK_RBNODE_FLAG_SET (cursor_node, GTK_RBNODE_IS_PARENT),
+                                           GTK_TREE_RBNODE_FLAG_SET (cursor_node, GTK_TREE_RBNODE_IS_PARENT),
                                            cursor_node->children ? TRUE : FALSE);
   gtk_tree_view_get_cell_area (tree_view,
                                cursor_path,
@@ -14592,7 +14592,7 @@ gtk_tree_view_set_row_separator_func (GtkTreeView                 *tree_view,
   tree_view->priv->row_separator_destroy = destroy;
 
   /* Have the tree recalculate heights */
-  _gtk_rbtree_mark_invalid (tree_view->priv->tree);
+  gtk_tree_rbtree_mark_invalid (tree_view->priv->tree);
   gtk_widget_queue_resize (GTK_WIDGET (tree_view));
 }
 
diff --git a/gtk/meson.build b/gtk/meson.build
index cc021d7fea..e2eb7af3a5 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -307,7 +307,7 @@ gtk_public_sources = files([
   'gtkradiomenuitem.c',
   'gtkradiotoolbutton.c',
   'gtkrange.c',
-  'gtkrbtree.c',
+  'gtktreerbtree.c',
   'gtkrecentmanager.c',
   'gtkrender.c',
   'gtkrenderbackground.c',
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index d86e035eff..69dd63df7d 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -39,7 +39,7 @@ tests = [
   ['objects-finalize'],
   ['papersize'],
   ['propertylookuplistmodel', ['../../gtk/gtkpropertylookuplistmodel.c'], ['-DGTK_COMPILATION', 
'-UG_ENABLE_DEBUG']],
-  ['rbtree', ['../../gtk/gtkrbtree.c'], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']],
+  ['rbtree', ['../../gtk/gtktreerbtree.c'], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']],
   ['recentmanager'],
   ['regression-tests'],
   ['scrolledwindow'],
diff --git a/testsuite/gtk/rbtree.c b/testsuite/gtk/rbtree.c
index 513c6abb67..c29eb1fbd8 100644
--- a/testsuite/gtk/rbtree.c
+++ b/testsuite/gtk/rbtree.c
@@ -1,4 +1,4 @@
-/* GtkRBTree tests.
+/* GtkTreeRBTree tests.
  *
  * Copyright (C) 2011, Red Hat, Inc.
  * Authors: Benjamin Otte <otte gnome org>
@@ -19,12 +19,12 @@
 
 #include <locale.h>
 
-#include "../../gtk/gtkrbtreeprivate.h"
+#include "../../gtk/gtktreerbtreeprivate.h"
 
-/* _gtk_rbtree_test */
+/* gtk_tree_rbtree_test */
 
 static guint
-get_total_count (GtkRBNode *node)
+get_total_count (GtkTreeRBNode *node)
 {
   guint child_total = 0;
 
@@ -38,18 +38,18 @@ get_total_count (GtkRBNode *node)
 }
 
 static guint
-count_total (GtkRBTree *tree,
-             GtkRBNode *node)
+count_total (GtkTreeRBTree *tree,
+             GtkTreeRBNode *node)
 {
   guint res;
-  
-  if (_gtk_rbtree_is_nil (node))
+
+  if (gtk_tree_rbtree_is_nil (node))
     return 0;
-  
+
   res =
     count_total (tree, node->left) +
     count_total (tree, node->right) +
-    (guint)1 +
+    (guint) 1 +
     (node->children ? count_total (node->children, node->children->root) : 0);
 
   if (res != node->total_count)
@@ -57,16 +57,16 @@ count_total (GtkRBTree *tree,
 
   if (get_total_count (node) != node->total_count)
     g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
-  
+
   return res;
 }
 
 static gint
-_count_nodes (GtkRBTree *tree,
-              GtkRBNode *node)
+_count_nodes (GtkTreeRBTree *tree,
+              GtkTreeRBNode *node)
 {
   gint res;
-  if (_gtk_rbtree_is_nil (node))
+  if (gtk_tree_rbtree_is_nil (node))
     return 0;
 
   g_assert (node->left);
@@ -81,95 +81,94 @@ _count_nodes (GtkRBTree *tree,
 }
 
 static void
-_gtk_rbtree_test_height (GtkRBTree *tree,
-                         GtkRBNode *node)
+gtk_tree_rbtree_test_height (GtkTreeRBTree *tree,
+                             GtkTreeRBNode *node)
 {
   gint computed_offset = 0;
 
   /* This whole test is sort of a useless truism. */
-  
-  if (!_gtk_rbtree_is_nil (node->left))
+
+  if (!gtk_tree_rbtree_is_nil (node->left))
     computed_offset += node->left->offset;
 
-  if (!_gtk_rbtree_is_nil (node->right))
+  if (!gtk_tree_rbtree_is_nil (node->right))
     computed_offset += node->right->offset;
 
-  if (node->children && !_gtk_rbtree_is_nil (node->children->root))
+  if (node->children && !gtk_tree_rbtree_is_nil (node->children->root))
     computed_offset += node->children->root->offset;
 
-  if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
+  if (GTK_TREE_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
     g_error ("node has broken offset");
 
-  if (!_gtk_rbtree_is_nil (node->left))
-    _gtk_rbtree_test_height (tree, node->left);
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    gtk_tree_rbtree_test_height (tree, node->left);
 
-  if (!_gtk_rbtree_is_nil (node->right))
-    _gtk_rbtree_test_height (tree, node->right);
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    gtk_tree_rbtree_test_height (tree, node->right);
 
-  if (node->children && !_gtk_rbtree_is_nil (node->children->root))
-    _gtk_rbtree_test_height (node->children, node->children->root);
+  if (node->children && !gtk_tree_rbtree_is_nil (node->children->root))
+    gtk_tree_rbtree_test_height (node->children, node->children->root);
 }
 
 static void
-_gtk_rbtree_test_dirty (GtkRBTree *tree,
-                       GtkRBNode *node,
-                        gint      expected_dirtyness)
+gtk_tree_rbtree_test_dirty (GtkTreeRBTree *tree,
+                            GtkTreeRBNode *node,
+                            gint           expected_dirtyness)
 {
-
   if (expected_dirtyness)
     {
-      g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
-               GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-               GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
-               GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
-               (node->children && GTK_RBNODE_FLAG_SET (node->children->root, 
GTK_RBNODE_DESCENDANTS_INVALID)));
+      g_assert (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) ||
+                GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
+                GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
+                GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
+                (node->children && GTK_TREE_RBNODE_FLAG_SET (node->children->root, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID)));
     }
   else
     {
-      g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
-               ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
-      if (!_gtk_rbtree_is_nil (node->left))
-       g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
-      if (!_gtk_rbtree_is_nil (node->right))
-       g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
+      g_assert (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) &&
+                !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID));
+      if (!gtk_tree_rbtree_is_nil (node->left))
+        g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+      if (!gtk_tree_rbtree_is_nil (node->right))
+        g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
       if (node->children != NULL)
-       g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
+        g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
     }
 
-  if (!_gtk_rbtree_is_nil (node->left))
-    _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, 
GTK_RBNODE_DESCENDANTS_INVALID));
-  if (!_gtk_rbtree_is_nil (node->right))
-    _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, 
GTK_RBNODE_DESCENDANTS_INVALID));
-  if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root))
-    _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, 
GTK_RBNODE_DESCENDANTS_INVALID));
+  if (!gtk_tree_rbtree_is_nil (node->left))
+    gtk_tree_rbtree_test_dirty (tree, node->left, GTK_TREE_RBNODE_FLAG_SET (node->left, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+  if (!gtk_tree_rbtree_is_nil (node->right))
+    gtk_tree_rbtree_test_dirty (tree, node->right, GTK_TREE_RBNODE_FLAG_SET (node->right, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID));
+  if (node->children != NULL && !gtk_tree_rbtree_is_nil (node->children->root))
+    gtk_tree_rbtree_test_dirty (node->children, node->children->root, GTK_TREE_RBNODE_FLAG_SET 
(node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
 }
 
-static void _gtk_rbtree_test_structure (GtkRBTree *tree);
+static void gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree);
 
 static guint
-_gtk_rbtree_test_structure_helper (GtkRBTree *tree,
-                                  GtkRBNode *node)
+gtk_tree_rbtree_test_structure_helper (GtkTreeRBTree *tree,
+                                       GtkTreeRBNode *node)
 {
   guint left_blacks, right_blacks;
 
-  g_assert (!_gtk_rbtree_is_nil (node));
+  g_assert (!gtk_tree_rbtree_is_nil (node));
 
   g_assert (node->left != NULL);
   g_assert (node->right != NULL);
   g_assert (node->parent != NULL);
 
-  if (!_gtk_rbtree_is_nil (node->left))
+  if (!gtk_tree_rbtree_is_nil (node->left))
     {
       g_assert (node->left->parent == node);
-      left_blacks = _gtk_rbtree_test_structure_helper (tree, node->left);
+      left_blacks = gtk_tree_rbtree_test_structure_helper (tree, node->left);
     }
   else
     left_blacks = 0;
 
-  if (!_gtk_rbtree_is_nil (node->right))
+  if (!gtk_tree_rbtree_is_nil (node->right))
     {
       g_assert (node->right->parent == node);
-      right_blacks = _gtk_rbtree_test_structure_helper (tree, node->right);
+      right_blacks = gtk_tree_rbtree_test_structure_helper (tree, node->right);
     }
   else
     right_blacks = 0;
@@ -179,29 +178,29 @@ _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
       g_assert (node->children->parent_tree == tree);
       g_assert (node->children->parent_node == node);
 
-      _gtk_rbtree_test_structure (node->children);
+      gtk_tree_rbtree_test_structure (node->children);
     }
 
   g_assert (left_blacks == right_blacks);
 
-  return left_blacks + (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK ? 1 : 0);
+  return left_blacks + (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK ? 1 : 0);
 }
 
 static void
-_gtk_rbtree_test_structure (GtkRBTree *tree)
+gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree)
 {
   g_assert (tree->root);
-  if (_gtk_rbtree_is_nil (tree->root))
+  if (gtk_tree_rbtree_is_nil (tree->root))
     return;
 
-  g_assert (_gtk_rbtree_is_nil (tree->root->parent));
-  _gtk_rbtree_test_structure_helper (tree, tree->root);
+  g_assert (gtk_tree_rbtree_is_nil (tree->root->parent));
+  gtk_tree_rbtree_test_structure_helper (tree, tree->root);
 }
 
 static void
-_gtk_rbtree_test (GtkRBTree *tree)
+gtk_tree_rbtree_test (GtkTreeRBTree *tree)
 {
-  GtkRBTree *tmp_tree;
+  GtkTreeRBTree *tmp_tree;
 
   if (tree == NULL)
     return;
@@ -210,64 +209,64 @@ _gtk_rbtree_test (GtkRBTree *tree)
   tmp_tree = tree;
   while (tmp_tree->parent_tree)
     tmp_tree = tmp_tree->parent_tree;
-  
-  if (_gtk_rbtree_is_nil (tmp_tree->root))
+
+  if (gtk_tree_rbtree_is_nil (tmp_tree->root))
     return;
 
-  _gtk_rbtree_test_structure (tmp_tree);
+  gtk_tree_rbtree_test_structure (tmp_tree);
 
   g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
-            _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
-      
-  _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
-  _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, 
GTK_RBNODE_DESCENDANTS_INVALID));
+             _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
+
+  gtk_tree_rbtree_test_height (tmp_tree, tmp_tree->root);
+  gtk_tree_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_TREE_RBNODE_FLAG_SET (tmp_tree->root, 
GTK_TREE_RBNODE_DESCENDANTS_INVALID));
   g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
 }
 
 /* gtk_rbtree_print() - unused, for debugging only */
 
 static void
-gtk_rbtree_print_node (GtkRBTree *tree,
-                       GtkRBNode *node,
-                       gint       depth)
+gtk_rbtree_print_node (GtkTreeRBTree *tree,
+                       GtkTreeRBNode *node,
+                       gint           depth)
 {
   gint i;
   for (i = 0; i < depth; i++)
     g_print ("\t");
 
   g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
-          node,
-          (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
-          node->offset,
-          node->total_count,
-          (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
-          (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
-          (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
+           node,
+           (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK) ? "BLACK" : " RED ",
+           node->offset,
+           node->total_count,
+           (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ? 1 : 0,
+           (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) ? 1 : 0,
+           (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)) ? 1 : 0);
   if (node->children != NULL)
     {
       g_print ("Looking at child.\n");
       gtk_rbtree_print_node (node->children, node->children->root, depth + 1);
       g_print ("Done looking at child.\n");
     }
-  if (!_gtk_rbtree_is_nil (node->left))
+  if (!gtk_tree_rbtree_is_nil (node->left))
     {
-      gtk_rbtree_print_node (tree, node->left, depth+1);
+      gtk_rbtree_print_node (tree, node->left, depth + 1);
     }
-  if (!_gtk_rbtree_is_nil (node->right))
+  if (!gtk_tree_rbtree_is_nil (node->right))
     {
-      gtk_rbtree_print_node (tree, node->right, depth+1);
+      gtk_rbtree_print_node (tree, node->right, depth + 1);
     }
 }
 
 /* not static so the debugger finds it. */
-void gtk_rbtree_print (GtkRBTree *tree);
+void gtk_rbtree_print (GtkTreeRBTree *tree);
 
 void
-gtk_rbtree_print (GtkRBTree *tree)
+gtk_rbtree_print (GtkTreeRBTree *tree)
 {
   g_return_if_fail (tree != NULL);
 
-  if (_gtk_rbtree_is_nil (tree->root))
+  if (gtk_tree_rbtree_is_nil (tree->root))
     g_print ("Empty tree...\n");
   else
     gtk_rbtree_print_node (tree, tree->root, 0);
@@ -276,13 +275,13 @@ gtk_rbtree_print (GtkRBTree *tree)
 /* actual tests */
 
 static guint
-append_elements (GtkRBTree *tree,
-                 guint      depth,
-                 guint      elements_per_depth,
-                 gboolean   check,
-                 guint      height)
+append_elements (GtkTreeRBTree *tree,
+                 guint          depth,
+                 guint          elements_per_depth,
+                 gboolean       check,
+                 guint          height)
 {
-  GtkRBNode *node;
+  GtkTreeRBNode *node;
   guint i;
 
   g_assert (depth > 0);
@@ -292,33 +291,33 @@ append_elements (GtkRBTree *tree,
 
   for (i = 0; i < elements_per_depth; i++)
     {
-      node = _gtk_rbtree_insert_after (tree, node, ++height, TRUE);
+      node = gtk_tree_rbtree_insert_after (tree, node, ++height, TRUE);
       if (depth)
         {
-          node->children = _gtk_rbtree_new ();
+          node->children = gtk_tree_rbtree_new ();
           node->children->parent_tree = tree;
           node->children->parent_node = node;
           height = append_elements (node->children, depth, elements_per_depth, check, height);
         }
       if (check)
-        _gtk_rbtree_test (tree);
+        gtk_tree_rbtree_test (tree);
     }
 
   return height;
 }
 
-static GtkRBTree *
-create_rbtree (guint depth,
-               guint elements_per_depth,
+static GtkTreeRBTree *
+create_rbtree (guint    depth,
+               guint    elements_per_depth,
                gboolean check)
 {
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
-  tree = _gtk_rbtree_new ();
+  tree = gtk_tree_rbtree_new ();
 
   append_elements (tree, depth, elements_per_depth, check, 0);
 
-  _gtk_rbtree_test (tree);
+  gtk_tree_rbtree_test (tree);
 
   return tree;
 }
@@ -326,106 +325,106 @@ create_rbtree (guint depth,
 static void
 test_create (void)
 {
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
   tree = create_rbtree (5, 5, TRUE);
 
-  _gtk_rbtree_free (tree);
+  gtk_tree_rbtree_free (tree);
 }
 
 static void
 test_insert_after (void)
 {
   guint i;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
-  tree = _gtk_rbtree_new ();
+  tree = gtk_tree_rbtree_new ();
   node = NULL;
 
   for (i = 1; i <= 100; i++)
     {
-      node = _gtk_rbtree_insert_after (tree, node, i, TRUE);
-      _gtk_rbtree_test (tree);
+      node = gtk_tree_rbtree_insert_after (tree, node, i, TRUE);
+      gtk_tree_rbtree_test (tree);
       g_assert (tree->root->count == i);
       g_assert (tree->root->total_count == i);
       g_assert (tree->root->offset == i * (i + 1) / 2);
     }
 
-  _gtk_rbtree_free (tree);
+  gtk_tree_rbtree_free (tree);
 }
 
 static void
 test_insert_before (void)
 {
   guint i;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
 
-  tree = _gtk_rbtree_new ();
+  tree = gtk_tree_rbtree_new ();
   node = NULL;
 
   for (i = 1; i <= 100; i++)
     {
-      node = _gtk_rbtree_insert_before (tree, node, i, TRUE);
-      _gtk_rbtree_test (tree);
+      node = gtk_tree_rbtree_insert_before (tree, node, i, TRUE);
+      gtk_tree_rbtree_test (tree);
       g_assert (tree->root->count == i);
       g_assert (tree->root->total_count == i);
       g_assert (tree->root->offset == i * (i + 1) / 2);
     }
 
-  _gtk_rbtree_free (tree);
+  gtk_tree_rbtree_free (tree);
 }
 
 static void
 test_remove_node (void)
 {
-  GtkRBTree *tree;
+  GtkTreeRBTree *tree;
 
   tree = create_rbtree (3, 16, g_test_thorough ());
 
   while (tree->root->count > 1)
     {
-      GtkRBTree *find_tree;
-      GtkRBNode *find_node;
+      GtkTreeRBTree *find_tree;
+      GtkTreeRBNode *find_node;
       guint i;
-      
+
       i = g_test_rand_int_range (0, tree->root->total_count);
-      if (!_gtk_rbtree_find_index (tree, i, &find_tree, &find_node))
+      if (!gtk_tree_rbtree_find_index (tree, i, &find_tree, &find_node))
         {
           /* We search an available index, so we mustn't fail. */
           g_assert_not_reached ();
         }
-      
-      _gtk_rbtree_test (find_tree);
+
+      gtk_tree_rbtree_test (find_tree);
 
       if (find_tree->root->count == 1)
         {
-          _gtk_rbtree_remove (find_tree);
+          gtk_tree_rbtree_remove (find_tree);
         }
       else
-        _gtk_rbtree_remove_node (find_tree, find_node);
-      _gtk_rbtree_test (tree);
+        gtk_tree_rbtree_remove_node (find_tree, find_node);
+      gtk_tree_rbtree_test (tree);
     }
 
-  _gtk_rbtree_free (tree);
+  gtk_tree_rbtree_free (tree);
 }
 
 static void
 test_remove_root (void)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
+
+  tree = gtk_tree_rbtree_new ();
 
-  tree = _gtk_rbtree_new ();
-  
-  node = _gtk_rbtree_insert_after (tree, NULL, 1, TRUE);
-  _gtk_rbtree_insert_after (tree, node, 2, TRUE);
-  _gtk_rbtree_insert_before (tree, node, 3, TRUE);
+  node = gtk_tree_rbtree_insert_after (tree, NULL, 1, TRUE);
+  gtk_tree_rbtree_insert_after (tree, node, 2, TRUE);
+  gtk_tree_rbtree_insert_before (tree, node, 3, TRUE);
 
-  _gtk_rbtree_remove_node (tree, node);
+  gtk_tree_rbtree_remove_node (tree, node);
 
-  _gtk_rbtree_free (tree);
+  gtk_tree_rbtree_free (tree);
 }
 
 static gint *
@@ -446,29 +445,29 @@ fisher_yates_shuffle (guint n_items)
   return list;
 }
 
-static GtkRBTree *
-create_unsorted_tree (gint  *order,
-                      guint  n)
+static GtkTreeRBTree *
+create_unsorted_tree (gint *order,
+                      guint n)
 {
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   guint i;
 
-  tree = _gtk_rbtree_new ();
+  tree = gtk_tree_rbtree_new ();
   node = NULL;
 
   for (i = 0; i < n; i++)
     {
-      node = _gtk_rbtree_insert_after (tree, node, 0, TRUE);
+      node = gtk_tree_rbtree_insert_after (tree, node, 0, TRUE);
     }
 
   for (i = 0; i < n; i++)
     {
-      node = _gtk_rbtree_find_count (tree, order[i] + 1);
-      _gtk_rbtree_node_set_height (tree, node, i);
+      node = gtk_tree_rbtree_find_count (tree, order[i] + 1);
+      gtk_tree_rbtree_node_set_height (tree, node, i);
     }
 
-  _gtk_rbtree_test (tree);
+  gtk_tree_rbtree_test (tree);
 
   return tree;
 }
@@ -477,8 +476,8 @@ static void
 test_reorder (void)
 {
   guint n = g_test_perf () ? 1000000 : 100;
-  GtkRBTree *tree;
-  GtkRBNode *node;
+  GtkTreeRBTree *tree;
+  GtkTreeRBNode *node;
   gint *reorder;
   guint i;
   double elapsed;
@@ -488,29 +487,30 @@ test_reorder (void)
 
   g_test_timer_start ();
 
-  _gtk_rbtree_reorder (tree, reorder, n);
+  gtk_tree_rbtree_reorder (tree, reorder, n);
 
   elapsed = g_test_timer_elapsed ();
   if (g_test_perf ())
     g_test_minimized_result (elapsed, "reordering rbtree with %u items: %gsec", n, elapsed);
 
-  _gtk_rbtree_test (tree);
+  gtk_tree_rbtree_test (tree);
 
-  for (node = _gtk_rbtree_first (tree), i = 0;
+  for (node = gtk_tree_rbtree_first (tree), i = 0;
        node != NULL;
-       node = _gtk_rbtree_next (tree, node), i++)
+       node = gtk_tree_rbtree_next (tree, node), i++)
     {
-      g_assert (GTK_RBNODE_GET_HEIGHT (node) == i);
+      g_assert (GTK_TREE_RBNODE_GET_HEIGHT (node) == i);
     }
   g_assert (i == n);
 
-  _gtk_rbtree_free (tree);
+  gtk_tree_rbtree_free (tree);
 
   g_free (reorder);
 }
 
 int
-main (int argc, char *argv[])
+main (int   argc,
+      char *argv[])
 {
   g_test_init (&argc, &argv, NULL);
   setlocale (LC_ALL, "C");


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]