[gtk/wip/matthiasc/rbtree: 1/2] Rename GtkRBTree to GtkTreeRBTree
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/matthiasc/rbtree: 1/2] Rename GtkRBTree to GtkTreeRBTree
- Date: Mon, 7 Jan 2019 04:40:52 +0000 (UTC)
commit 10aefb5c799d00ab81ad9283902c359f7a8012e2
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 | 128 +--
gtk/a11y/gtktreeviewaccessibleprivate.h | 20 +-
gtk/gtkrbtree.c | 1738 -------------------------------
gtk/gtkrbtreeprivate.h | 172 ---
gtk/gtktreeprivate.h | 22 +-
gtk/gtktreerbtree.c | 1738 +++++++++++++++++++++++++++++++
gtk/gtktreerbtreeprivate.h | 172 +++
gtk/gtktreeselection.c | 132 +--
gtk/gtktreeview.c | 726 ++++++-------
gtk/meson.build | 2 +-
testsuite/gtk/meson.build | 2 +-
testsuite/gtk/rbtree.c | 258 ++---
12 files changed, 2555 insertions(+), 2555 deletions(-)
---
diff --git a/gtk/a11y/gtktreeviewaccessible.c b/gtk/a11y/gtktreeviewaccessible.c
index 37339ceb14..df427d9a14 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,8 +58,8 @@ 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,
@@ -67,8 +67,8 @@ static gint get_column_number (GtkTreeView
static gboolean get_rbtree_column_from_index (GtkTreeView *tree_view,
gint index,
- GtkRBTree **tree,
- GtkRBNode **node,
+ GtkTreeRBTree **tree,
+ GtkTreeRBNode **node,
GtkTreeViewColumn **column);
static GtkTreeViewAccessibleCellInfo* find_cell_info (GtkTreeViewAccessible *view,
@@ -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;
@@ -415,8 +415,8 @@ create_cell_accessible (GtkTreeView *treeview,
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)),
+ 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),
+ 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),
+ 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);
@@ -1217,10 +1217,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))
@@ -1230,7 +1230,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)
@@ -1241,8 +1241,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)
@@ -1334,8 +1334,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.
@@ -1378,9 +1378,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)
@@ -1413,7 +1413,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);
}
@@ -1517,7 +1517,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);
@@ -1526,8 +1526,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)
{
@@ -1581,8 +1581,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);
@@ -1598,7 +1598,7 @@ 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),
+ if (!_gtk_tree_rbtree_find_index (_gtk_tree_view_get_rbtree (tree_view),
index / n_columns,
tree,
node))
@@ -1652,8 +1652,8 @@ get_header_from_column (GtkTreeViewColumn *tv_col)
void
_gtk_tree_view_accessible_add (GtkTreeView *treeview,
- GtkRBTree *tree,
- GtkRBNode *node)
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node)
{
GtkTreeViewAccessible *accessible;
guint row, n_rows, n_cols, i;
@@ -1664,12 +1664,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);
}
@@ -1688,8 +1688,8 @@ _gtk_tree_view_accessible_add (GtkTreeView *treeview,
void
_gtk_tree_view_accessible_remove (GtkTreeView *treeview,
- GtkRBTree *tree,
- GtkRBNode *node)
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node)
{
GtkTreeViewAccessibleCellInfo *cell_info;
GHashTableIter iter;
@@ -1704,12 +1704,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;
@@ -1731,7 +1731,7 @@ _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);
}
}
@@ -1739,8 +1739,8 @@ _gtk_tree_view_accessible_remove (GtkTreeView *treeview,
void
_gtk_tree_view_accessible_changed (GtkTreeView *treeview,
- GtkRBTree *tree,
- GtkRBNode *node)
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node)
{
GtkTreeViewAccessible *accessible;
guint i;
@@ -1955,8 +1955,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,8 +1994,8 @@ _gtk_tree_view_accessible_update_focus_column (GtkTreeView *treeview,
void
_gtk_tree_view_accessible_add_state (GtkTreeView *treeview,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
GtkCellRendererState state)
{
GtkTreeViewAccessible *accessible;
@@ -2059,8 +2059,8 @@ _gtk_tree_view_accessible_add_state (GtkTreeView *treeview,
void
_gtk_tree_view_accessible_remove_state (GtkTreeView *treeview,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
GtkCellRendererState state)
{
GtkTreeViewAccessible *accessible;
diff --git a/gtk/a11y/gtktreeviewaccessibleprivate.h b/gtk/a11y/gtktreeviewaccessibleprivate.h
index 3c91009bac..7f79cd41c4 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..3468586066 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..a92a13a4c6
--- /dev/null
+++ b/gtk/gtktreerbtree.c
@@ -0,0 +1,1738 @@
+/* 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..6ae75ef5c6
--- /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>K_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..b53bda08fc 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,19 +638,19 @@ gtk_tree_selection_get_selected_rows (GtkTreeSelection *selection,
}
static void
-gtk_tree_selection_count_selected_rows_helper (GtkRBTree *tree,
- GtkRBNode *node,
+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,
+ _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);
@@ -690,7 +690,7 @@ gtk_tree_selection_count_selected_rows (GtkTreeSelection *selection)
return 0;
}
- _gtk_rbtree_traverse (tree, tree->root,
+ _gtk_tree_rbtree_traverse (tree, tree->root,
G_PRE_ORDER,
gtk_tree_selection_count_selected_rows_helper,
&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;
@@ -860,8 +860,8 @@ gtk_tree_selection_select_path (GtkTreeSelection *selection,
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,7 +1127,7 @@ gtk_tree_selection_real_select_all (GtkTreeSelection *selection)
tuple->selection = selection;
tuple->dirty = FALSE;
- _gtk_rbtree_traverse (tree, tree->root,
+ _gtk_tree_rbtree_traverse (tree, tree->root,
G_PRE_ORDER,
select_all_helper,
tuple);
@@ -1169,19 +1169,19 @@ gtk_tree_selection_select_all (GtkTreeSelection *selection)
}
static void
-unselect_all_helper (GtkRBTree *tree,
- GtkRBNode *node,
+unselect_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,
unselect_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, 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,14 +1227,14 @@ 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,
+ _gtk_tree_rbtree_traverse (tree, tree->root,
G_PRE_ORDER,
unselect_all_helper,
tuple);
@@ -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,7 +1422,7 @@ gtk_tree_selection_unselect_range (GtkTreeSelection *selection,
gboolean
_gtk_tree_selection_row_is_selectable (GtkTreeSelection *selection,
- GtkRBNode *node,
+ GtkTreeRBNode *node,
GtkTreePath *path)
{
GtkTreeSelectionPrivate *priv = selection->priv;
@@ -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,8 +1466,8 @@ _gtk_tree_selection_row_is_selectable (GtkTreeSelection *selection,
*/
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)
@@ -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,8 +1598,8 @@ _gtk_tree_selection_emit_changed (GtkTreeSelection *selection)
static gint
gtk_tree_selection_real_select_node (GtkTreeSelection *selection,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
gboolean select)
{
GtkTreeSelectionPrivate *priv = selection->priv;
@@ -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..84f708c9a7 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 */
@@ -689,8 +689,8 @@ static void gtk_tree_view_rows_reordered (GtkTreeModel *mode
/* Incremental reflow */
static gboolean validate_row (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
GtkTreeIter *iter,
GtkTreePath *path);
static void validate_visible_area (GtkTreeView *tree_view);
@@ -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,
@@ -775,16 +775,16 @@ static void update_prelight (GtkTreeView
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);
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node);
static inline gint gtk_tree_view_get_cell_area_height (GtkTreeView *tree_view,
- GtkRBNode *node);
+ GtkTreeRBNode *node);
static inline gint gtk_tree_view_get_row_y_offset (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node);
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node);
static inline gint gtk_tree_view_get_row_height (GtkTreeView *tree_view,
- GtkRBNode *node);
+ 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;
@@ -3328,8 +3328,8 @@ gtk_tree_view_multipress_gesture_released (GtkGestureMultiPress *gesture,
static gboolean
coords_are_over_arrow (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
/* these are in bin window coords */
gint x,
gint y)
@@ -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);
@@ -3392,8 +3392,8 @@ remove_auto_expand_timeout (GtkTreeView *tree_view)
static void
do_prelight (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
/* these are in bin_window coords */
gint x,
gint y)
@@ -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));
@@ -3477,8 +3477,8 @@ do_prelight (GtkTreeView *tree_view,
static void
prelight_or_select (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
/* these are in bin_window coords */
gint x,
gint y)
@@ -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)
@@ -3750,10 +3750,10 @@ 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,
+ GtkTreeRBTree *start_tree,
+ GtkTreeRBNode *start_node,
+ GtkTreeRBTree *end_tree,
+ GtkTreeRBNode *end_node,
gboolean select,
gboolean skip_start,
gboolean skip_end)
@@ -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;
@@ -5474,13 +5474,13 @@ gtk_tree_view_key_controller_focus_out (GtkEventControllerKey *key,
static gboolean
node_is_visible (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node)
+ 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) &&
@@ -5521,8 +5521,8 @@ get_separator_height (GtkTreeView *tree_view)
*/
static gboolean
validate_row (GtkTreeView *tree_view,
- GtkRBTree *tree,
- GtkRBNode *node,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
GtkTreeIter *iter,
GtkTreePath *path)
{
@@ -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))
@@ -7859,11 +7859,11 @@ static gboolean
search_first_focusable_path (GtkTreeView *tree_view,
GtkTreePath **path,
gboolean search_forward,
- GtkRBTree **new_tree,
- GtkRBNode **new_node)
+ 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,
+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)
@@ -8643,7 +8643,7 @@ gtk_tree_view_get_background_xrange (GtkTreeView *tree_view,
static void
gtk_tree_view_get_arrow_xrange (GtkTreeView *tree_view,
- GtkRBTree *tree,
+ GtkTreeRBTree *tree,
gint *x1,
gint *x2)
{
@@ -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;
@@ -8697,25 +8697,25 @@ gtk_tree_view_get_arrow_xrange (GtkTreeView *tree_view,
static void
gtk_tree_view_build_tree (GtkTreeView *tree_view,
- GtkRBTree *tree,
+ 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>K_RBNODE_IS_PARENT) != GTK_RBNODE_IS_PARENT)
- temp->flags ^= GTK_RBNODE_IS_PARENT;
+ if ((temp->flags>K_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));
@@ -8763,8 +8763,8 @@ 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)
+ 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;
@@ -8898,11 +8898,11 @@ _gtk_tree_path_new_from_rbtree (GtkRBTree *tree,
gboolean
_gtk_tree_view_find_node (GtkTreeView *tree_view,
GtkTreePath *path,
- GtkRBTree **tree,
- GtkRBNode **node)
+ 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)
{
@@ -9011,8 +9011,8 @@ 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)
+ 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));
@@ -9046,17 +9046,17 @@ gtk_tree_view_unref_tree_helper (GtkTreeModel *model,
static gint
gtk_tree_view_unref_and_check_selection_tree (GtkTreeView *tree_view,
- GtkRBTree *tree)
+ 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,7 +9254,7 @@ _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;
@@ -9262,8 +9262,8 @@ _gtk_tree_view_get_rbtree (GtkTreeView *tree_view)
gboolean
_gtk_tree_view_get_cursor_node (GtkTreeView *tree_view,
- GtkRBTree **tree,
- GtkRBNode **node)
+ GtkTreeRBTree **tree,
+ GtkTreeRBNode **node)
{
GtkTreeViewPrivate *priv;
@@ -9305,8 +9305,8 @@ _gtk_tree_view_set_focus_column (GtkTreeView *tree_view,
static void
gtk_tree_view_snapshot_arrow (GtkTreeView *tree_view,
GtkSnapshot *snapshot,
- GtkRBTree *tree,
- GtkRBNode *node)
+ 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,
+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);
@@ -11605,8 +11605,8 @@ 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,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
gboolean open_all,
gboolean animate)
{
@@ -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);
@@ -11734,8 +11734,8 @@ 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,
+ GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
gboolean animate)
{
GtkTreeIter iter;
@@ -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);
@@ -12389,7 +12389,7 @@ 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)
+ GtkTreeRBNode *node)
{
int expander_size = gtk_tree_view_get_expander_size (tree_view);
int height;
@@ -12411,8 +12411,8 @@ 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)
+ 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));
@@ -12513,7 +12513,7 @@ gtk_tree_view_get_cell_area (GtkTreeView *tree_view,
static inline gint
gtk_tree_view_get_row_height (GtkTreeView *tree_view,
- GtkRBNode *node)
+ 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;
@@ -12535,12 +12535,12 @@ 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)
+ 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,
@@ -13336,8 +13336,8 @@ gtk_tree_view_create_row_drag_icon (GtkTreeView *tree_view,
GtkTreePath *path)
{
GtkTreeIter iter;
- GtkRBTree *tree;
- GtkRBNode *node;
+ 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 e4f8451d9d..6cd29aacda 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -314,7 +314,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 7f4161857e..8c3d5b7b3c 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -41,7 +41,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..3c6bc15f88 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,12 +38,12 @@ 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 =
@@ -62,11 +62,11 @@ count_total (GtkRBTree *tree,
}
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,95 @@ _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,
+_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 +179,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;
@@ -211,24 +211,24 @@ _gtk_rbtree_test (GtkRBTree *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));
+ _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,
+gtk_rbtree_print_node (GtkTreeRBTree *tree,
+ GtkTreeRBNode *node,
gint depth)
{
gint i;
@@ -237,37 +237,37 @@ gtk_rbtree_print_node (GtkRBTree *tree,
g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
node,
- (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
+ (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_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);
+ (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);
}
- if (!_gtk_rbtree_is_nil (node->right))
+ if (!_gtk_tree_rbtree_is_nil (node->right))
{
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 +276,13 @@ gtk_rbtree_print (GtkRBTree *tree)
/* actual tests */
static guint
-append_elements (GtkRBTree *tree,
+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 +292,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 *
+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 +326,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_rbtree_new ();
+ tree = _gtk_tree_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 +446,29 @@ fisher_yates_shuffle (guint n_items)
return list;
}
-static GtkRBTree *
+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 +477,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,23 +488,23 @@ 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);
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
