tests: Remove unused argument from treeview-scrolling test

[~andy/gtk] / gtk / tests / rbtree.c

diff --git a/gtk/tests/rbtree.c b/gtk/tests/rbtree.c
index d2441925ef32f2a05817978d4074fd760c242aa8..88e9c80ca607c2fdb5e6354c360992354a39787e 100644 (file)
--- a/gtk/tests/rbtree.c
+++ b/gtk/tests/rbtree.c
@@ -45,7 +45,7 @@ count_total (GtkRBTree *tree,
 {
   guint res;
   
-  if (node == tree->nil)
+  if (_gtk_rbtree_is_nil (node))
     return 0;
   
   res =
@@ -68,7 +68,7 @@ _count_nodes (GtkRBTree *tree,
               GtkRBNode *node)
 {
   gint res;
-  if (node == tree->nil)
+  if (_gtk_rbtree_is_nil (node))
     return 0;
 
   g_assert (node->left);
@@ -90,25 +90,25 @@ _gtk_rbtree_test_height (GtkRBTree *tree,
 
   /* This whole test is sort of a useless truism. */
   
-  if (node->left != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->left))
     computed_offset += node->left->offset;
 
-  if (node->right != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->right))
     computed_offset += node->right->offset;
 
-  if (node->children && node->children->root != node->children->nil)
+  if (node->children && !_gtk_rbtree_is_nil (node->children->root))
     computed_offset += node->children->root->offset;
 
   if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
     g_error ("node has broken offset\n");
 
-  if (node->left != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->left))
     _gtk_rbtree_test_height (tree, node->left);
 
-  if (node->right != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->right))
     _gtk_rbtree_test_height (tree, node->right);
 
-  if (node->children && node->children->root != node->children->nil)
+  if (node->children && !_gtk_rbtree_is_nil (node->children->root))
     _gtk_rbtree_test_height (node->children, node->children->root);
 }
 
@@ -122,27 +122,27 @@ _gtk_rbtree_test_dirty (GtkRBTree *tree,
     {
       g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
                GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
-               (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
-               (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_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)));
     }
   else
     {
       g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
                ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
-      if (node->left != tree->nil)
+      if (!_gtk_rbtree_is_nil (node->left))
        g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
-      if (node->right != tree->nil)
+      if (!_gtk_rbtree_is_nil (node->right))
        g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
       if (node->children != NULL)
        g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
     }
 
-  if (node->left != tree->nil)
+  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 (node->right != tree->nil)
+  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 && node->children->root != node->children->nil)
+  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));
 }
 
@@ -154,13 +154,13 @@ _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
 {
   guint left_blacks, right_blacks;
 
-  g_assert (node != tree->nil);
+  g_assert (!_gtk_rbtree_is_nil (node));
 
   g_assert (node->left != NULL);
   g_assert (node->right != NULL);
   g_assert (node->parent != NULL);
 
-  if (node->left != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->left))
     {
       g_assert (node->left->parent == node);
       left_blacks = _gtk_rbtree_test_structure_helper (tree, node->left);
@@ -168,7 +168,7 @@ _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
   else
     left_blacks = 0;
 
-  if (node->right != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->right))
     {
       g_assert (node->right->parent == node);
       right_blacks = _gtk_rbtree_test_structure_helper (tree, node->right);
@@ -193,10 +193,10 @@ static void
 _gtk_rbtree_test_structure (GtkRBTree *tree)
 {
   g_assert (tree->root);
-  if (tree->root == tree->nil)
+  if (_gtk_rbtree_is_nil (tree->root))
     return;
 
-  g_assert (tree->root->parent == tree->nil);
+  g_assert (_gtk_rbtree_is_nil (tree->root->parent));
   _gtk_rbtree_test_structure_helper (tree, tree->root);
 }
 
@@ -213,9 +213,7 @@ _gtk_rbtree_test (GtkRBTree *tree)
   while (tmp_tree->parent_tree)
     tmp_tree = tmp_tree->parent_tree;
   
-  g_assert (tmp_tree->nil != NULL);
-
-  if (tmp_tree->root == tmp_tree->nil)
+  if (_gtk_rbtree_is_nil (tmp_tree->root))
     return;
 
   _gtk_rbtree_test_structure (tmp_tree);
@@ -253,11 +251,11 @@ gtk_rbtree_print_node (GtkRBTree *tree,
       gtk_rbtree_print_node (node->children, node->children->root, depth + 1);
       g_print ("Done looking at child.\n");
     }
-  if (node->left != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->left))
     {
       gtk_rbtree_print_node (tree, node->left, depth+1);
     }
-  if (node->right != tree->nil)
+  if (!_gtk_rbtree_is_nil (node->right))
     {
       gtk_rbtree_print_node (tree, node->right, depth+1);
     }
@@ -271,7 +269,7 @@ gtk_rbtree_print (GtkRBTree *tree)
 {
   g_return_if_fail (tree != NULL);
 
-  if (tree->root == tree->nil)
+  if (_gtk_rbtree_is_nil (tree->root))
     g_print ("Empty tree...\n");
   else
     gtk_rbtree_print_node (tree, tree->root, 0);
@@ -283,6 +281,7 @@ static guint
 append_elements (GtkRBTree *tree,
                  guint      depth,
                  guint      elements_per_depth,
+                 gboolean   check,
                  guint      height)
 {
   GtkRBNode *node;
@@ -301,9 +300,10 @@ append_elements (GtkRBTree *tree,
           node->children = _gtk_rbtree_new ();
           node->children->parent_tree = tree;
           node->children->parent_node = node;
-          height = append_elements (node->children, depth, elements_per_depth, height);
+          height = append_elements (node->children, depth, elements_per_depth, check, height);
         }
-      _gtk_rbtree_test (tree);
+      if (check)
+        _gtk_rbtree_test (tree);
     }
 
   return height;
@@ -311,13 +311,16 @@ append_elements (GtkRBTree *tree,
 
 static GtkRBTree *
 create_rbtree (guint depth,
-               guint elements_per_depth)
+               guint elements_per_depth,
+               gboolean check)
 {
   GtkRBTree *tree;
 
   tree = _gtk_rbtree_new ();
 
-  append_elements (tree, depth, elements_per_depth, 0);
+  append_elements (tree, depth, elements_per_depth, check, 0);
+
+  _gtk_rbtree_test (tree);
 
   return tree;
 }
@@ -327,7 +330,7 @@ test_create (void)
 {
   GtkRBTree *tree;
 
-  tree = create_rbtree (5, 5);
+  tree = create_rbtree (5, 5, TRUE);
 
   _gtk_rbtree_free (tree);
 }
@@ -381,7 +384,7 @@ test_remove_node (void)
 {
   GtkRBTree *tree;
 
-  tree = create_rbtree (3, 16);
+  tree = create_rbtree (3, 16, g_test_thorough ());
 
   while (tree->root->count > 1)
     {
@@ -427,6 +430,85 @@ test_remove_root (void)
   _gtk_rbtree_free (tree);
 }
 
+static gint *
+fisher_yates_shuffle (guint n_items)
+{
+  gint *list;
+  guint i, j;
+
+  list = g_new (gint, n_items);
+
+  for (i = 0; i < n_items; i++)
+    {
+      j = g_random_int_range (0, i + 1);
+      list[i] = list[j];
+      list[j] = i;
+    }
+
+  return list;
+}
+
+static GtkRBTree *
+create_unsorted_tree (gint  *order,
+                      guint  n)
+{
+  GtkRBTree *tree;
+  GtkRBNode *node;
+  guint i;
+
+  tree = _gtk_rbtree_new ();
+  node = NULL;
+
+  for (i = 0; i < n; i++)
+    {
+      node = _gtk_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);
+    }
+
+  _gtk_rbtree_test (tree);
+
+  return tree;
+}
+
+static void
+test_reorder (void)
+{
+  guint n = g_test_perf () ? 1000000 : 100;
+  GtkRBTree *tree;
+  GtkRBNode *node;
+  gint *reorder;
+  guint i;
+  double elapsed;
+
+  reorder = fisher_yates_shuffle (n);
+  tree = create_unsorted_tree (reorder, n);
+
+  g_test_timer_start ();
+
+  _gtk_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);
+
+  for (node = _gtk_rbtree_first (tree), i = 0;
+       node != NULL;
+       node = _gtk_rbtree_next (tree, node), i++)
+    {
+      g_assert (GTK_RBNODE_GET_HEIGHT (node) == i);
+    }
+  g_assert (i == n);
+
+  _gtk_rbtree_free (tree);
+}
+
 int
 main (int argc, char *argv[])
 {
@@ -438,8 +520,8 @@ main (int argc, char *argv[])
   g_test_add_func ("/rbtree/insert_after", test_insert_after);
   g_test_add_func ("/rbtree/insert_before", test_insert_before);
   g_test_add_func ("/rbtree/remove_node", test_remove_node);
-
   g_test_add_func ("/rbtree/remove_root", test_remove_root);
+  g_test_add_func ("/rbtree/reorder", test_reorder);
 
   return g_test_run ();
 }