tests: Remove unused variables

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

diff --git a/gtk/tests/rbtree.c b/gtk/tests/rbtree.c
index dfcc73234f1be399f180676e5c21ee97811ca53e..84b752b8fba8e181ca32a80f44bef27aab01a7a0 100644 (file)
--- a/gtk/tests/rbtree.c
+++ b/gtk/tests/rbtree.c
@@ -14,9 +14,7 @@
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
  */
 
 #include <locale.h>
@@ -122,8 +120,8 @@ _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) ||
-               (!_gtk_rbtree_is_nil (node->left) && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
-               (!_gtk_rbtree_is_nil (node->right) && 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
@@ -281,6 +279,7 @@ static guint
 append_elements (GtkRBTree *tree,
                  guint      depth,
                  guint      elements_per_depth,
+                 gboolean   check,
                  guint      height)
 {
   GtkRBNode *node;
@@ -299,9 +298,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;
@@ -309,13 +309,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;
 }
@@ -325,7 +328,7 @@ test_create (void)
 {
   GtkRBTree *tree;
 
-  tree = create_rbtree (5, 5);
+  tree = create_rbtree (5, 5, TRUE);
 
   _gtk_rbtree_free (tree);
 }
@@ -379,7 +382,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)
     {
@@ -425,6 +428,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[])
 {
@@ -436,8 +518,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 ();
 }