[PATCH 1/2] Add sreal to selftests

[PATCH 1/2] Add sreal to selftests

[marxin]

gcc/ChangeLog:

2016-07-12  Martin Liska  <mliska@suse.cz>

	* selftest-run-tests.c (selftest::run_tests): New function.
	* selftest.h (sreal_c_tests): Declare.
	* sreal.c (sreal_verify_basics): New function.
	(verify_aritmetics): Likewise.
	(sreal_verify_arithmetics): Likewise.
	(verify_shifting): Likewise.
	(sreal_verify_shifting): Likewise.
	(void sreal_c_tests): Likewise.

gcc/testsuite/ChangeLog:

2016-07-12  Martin Liska  <mliska@suse.cz>

	* gcc.dg/plugin/plugin.exp: Remove sreal test.
	* gcc.dg/plugin/sreal-test-1.c: Remove.
	* gcc.dg/plugin/sreal_plugin.c: Remove.
---
 gcc/selftest-run-tests.c                   |   1 +
 gcc/selftest.h                             |   1 +
 gcc/sreal.c                                | 112 +++++++++++++++++++
 gcc/testsuite/gcc.dg/plugin/plugin.exp     |   1 -
 gcc/testsuite/gcc.dg/plugin/sreal-test-1.c |   8 --
 gcc/testsuite/gcc.dg/plugin/sreal_plugin.c | 170 -----------------------------
 6 files changed, 114 insertions(+), 179 deletions(-)
 delete mode 100644 gcc/testsuite/gcc.dg/plugin/sreal-test-1.c
 delete mode 100644 gcc/testsuite/gcc.dg/plugin/sreal_plugin.c

diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index bddf0b2..bb004cc 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -49,6 +49,7 @@ selftest::run_tests ()
   pretty_print_c_tests ();
   wide_int_cc_tests ();
   ggc_tests_c_tests ();
+  sreal_c_tests ();
 
   /* Mid-level data structures.  */
   input_c_tests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index 967e76b..c805386 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -86,6 +86,7 @@ extern void pretty_print_c_tests ();
 extern void rtl_tests_c_tests ();
 extern void spellcheck_c_tests ();
 extern void spellcheck_tree_c_tests ();
+extern void sreal_c_tests ();
 extern void tree_c_tests ();
 extern void tree_cfg_c_tests ();
 extern void vec_c_tests ();
diff --git a/gcc/sreal.c b/gcc/sreal.c
index a7c9c12..9c43b4e 100644
--- a/gcc/sreal.c
+++ b/gcc/sreal.c
@@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.  If not see
 #include <math.h>
 #include "coretypes.h"
 #include "sreal.h"
+#include "selftest.h"
 
 /* Print the content of struct sreal.  */
 
@@ -233,3 +234,114 @@ sreal::operator/ (const sreal &other) const
   r.normalize ();
   return r;
 }
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Selftests for sreals.  */
+
+/* Verify basic sreal operations.  */
+
+static void
+sreal_verify_basics (void)
+{
+  sreal minimum = INT_MIN;
+  sreal maximum = INT_MAX;
+
+  sreal seven = 7;
+  sreal minus_two = -2;
+  sreal minus_nine = -9;
+
+  ASSERT_EQ (INT_MIN, minimum.to_int ());
+  ASSERT_EQ (INT_MAX, maximum.to_int ());
+
+  ASSERT_FALSE (minus_two < minus_two);
+  ASSERT_FALSE (seven < seven);
+  ASSERT_TRUE (seven > minus_two);
+  ASSERT_TRUE (minus_two < seven);
+  ASSERT_TRUE (minus_two != seven);
+  ASSERT_EQ (minus_two, -2);
+  ASSERT_EQ (seven, 7);
+  ASSERT_EQ ((seven << 10) >> 10, 7);
+  ASSERT_EQ (seven + minus_nine, -2);
+}
+
+/* Helper function that performs basic arithmetics and comparison
+   of given arguments A and B.  */
+
+static void
+verify_aritmetics (int64_t a, int64_t b)
+{
+  ASSERT_EQ (a, -(-(sreal (a))).to_int ());
+  ASSERT_EQ (a < b, sreal (a) < sreal (b));
+  ASSERT_EQ (a <= b, sreal (a) <= sreal (b));
+  ASSERT_EQ (a == b, sreal (a) == sreal (b));
+  ASSERT_EQ (a != b, sreal (a) != sreal (b));
+  ASSERT_EQ (a > b, sreal (a) > sreal (b));
+  ASSERT_EQ (a >= b, sreal (a) >= sreal (b));
+  ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_int ());
+  ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_int ());
+  ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_int ());
+  ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_int ());
+}
+
+/* Verify arithmetics for interesting numbers.  */
+
+static void
+sreal_verify_arithmetics (void)
+{
+  int values[] = {-14123413, -7777, -17, -10, -2, 0, 17, 139, 1234123};
+  unsigned c = sizeof (values) / sizeof (int);
+
+  for (unsigned i = 0; i < c; i++)
+    for (unsigned j = 0; j < c; j++)
+      {
+	int a = values[i];
+	int b = values[j];
+
+	verify_aritmetics (a, b);
+      }
+}
+
+/* Helper function that performs various shifting test of a given
+   argument A.  */
+
+static void
+verify_shifting (int64_t a)
+{
+  sreal v = a;
+
+  for (unsigned i = 0; i < 16; i++)
+    ASSERT_EQ (a << i, (v << i).to_int());
+
+  a = a << 16;
+  v = v << 16;
+
+  for (unsigned i = 0; i < 16; i++)
+    ASSERT_EQ (a >> i, (v >> i).to_int());
+}
+
+/* Verify shifting for interesting numbers.  */
+
+static void
+sreal_verify_shifting (void)
+{
+  int values[] = {0, 17, 32, 139, 1024, 55555, 1234123};
+  unsigned c = sizeof (values) / sizeof (int);
+
+  for (unsigned i = 0; i < c; i++)
+    verify_shifting (values[i]);
+}
+
+/* Run all of the selftests within this file.  */
+
+void sreal_c_tests ()
+{
+  sreal_verify_basics ();
+  sreal_verify_arithmetics ();
+  sreal_verify_shifting ();
+}
+
+} // namespace selftest
+#endif /* CHECKING_P */
diff --git a/gcc/testsuite/gcc.dg/plugin/plugin.exp b/gcc/testsuite/gcc.dg/plugin/plugin.exp
index f039c8d..faebb75 100644
--- a/gcc/testsuite/gcc.dg/plugin/plugin.exp
+++ b/gcc/testsuite/gcc.dg/plugin/plugin.exp
@@ -59,7 +59,6 @@ set plugin_test_list [list \
     { selfassign.c self-assign-test-1.c self-assign-test-2.c } \
     { ggcplug.c ggcplug-test-1.c } \
     { one_time_plugin.c one_time-test-1.c } \
-    { sreal_plugin.c sreal-test-1.c } \
     { start_unit_plugin.c start_unit-test-1.c } \
     { finish_unit_plugin.c finish_unit-test-1.c } \
     { wide-int_plugin.c wide-int-test-1.c } \
diff --git a/gcc/testsuite/gcc.dg/plugin/sreal-test-1.c b/gcc/testsuite/gcc.dg/plugin/sreal-test-1.c
deleted file mode 100644
index 1bce2cc..0000000
--- a/gcc/testsuite/gcc.dg/plugin/sreal-test-1.c
+++ /dev/null
@@ -1,8 +0,0 @@
-/* Test that pass is inserted and invoked once. */
-/* { dg-do compile } */
-/* { dg-options "-O" } */
-
-int main (int argc, char **argv)
-{
-  return 0;
-}
diff --git a/gcc/testsuite/gcc.dg/plugin/sreal_plugin.c b/gcc/testsuite/gcc.dg/plugin/sreal_plugin.c
deleted file mode 100644
index f113816..0000000
--- a/gcc/testsuite/gcc.dg/plugin/sreal_plugin.c
+++ /dev/null
@@ -1,170 +0,0 @@
-/* Plugin that process internal tests for sreal.  */
-#include "config.h"
-#include "gcc-plugin.h"
-#include "system.h"
-#include "coretypes.h"
-#include "tree.h"
-#include "tm.h"
-#include "toplev.h"
-#include "hash-table.h"
-#include "vec.h"
-#include "ggc.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-fold.h"
-#include "tree-eh.h"
-#include "gimple-expr.h"
-#include "is-a.h"
-#include "gimple.h"
-#include "tree-pass.h"
-#include "intl.h"
-#include "context.h"
-#include "sreal.h"
-
-int plugin_is_GPL_compatible;
-
-namespace {
-
-static void assert (bool c)
-{
-  if (!c)
-    abort ();
-}
-
-const pass_data pass_data_sreal_pass =
-{
-  GIMPLE_PASS, /* type */
-  "sreal", /* name */
-  OPTGROUP_NONE, /* optinfo_flags */
-  TV_NONE, /* tv_id */
-  PROP_gimple_any, /* properties_required */
-  0, /* properties_provided */
-  0, /* properties_destroyed */
-  0, /* todo_flags_start */
-  0, /* todo_flags_finish */
-};
-
-class sreal_pass : public gimple_opt_pass
-{
-public:
-  sreal_pass(gcc::context *ctxt)
-    : gimple_opt_pass(pass_data_sreal_pass, ctxt)
-  {}
-
-  /* opt_pass methods: */
-  virtual bool gate (function *);
-  virtual unsigned int execute (function *);
-
-private:
-  void check_sreal ();
-
-  static void verify_aritmetics (int a, int b);
-  static void verify_shifting (int a);
-}; // class one_pass
-
-} // anon namespace
-
-void
-sreal_pass::verify_aritmetics (int a, int b)
-{
-  assert (a == -(-(sreal (a))).to_int ());
-  assert ((a < b) == (sreal (a) < sreal (b)));
-  assert ((a <= b) == (sreal (a) <= sreal (b)));
-  assert ((a == b) == (sreal (a) == sreal (b)));
-  assert ((a != b) == (sreal (a) != sreal (b)));
-  assert ((a > b) == (sreal (a) > sreal (b)));
-  assert ((a >= b) == (sreal (a) >= sreal (b)));
-  assert ((a + b) == (sreal (a) + sreal (b)).to_int ());
-  assert ((a - b) == (sreal (a) - sreal (b)).to_int ());
-  assert ((b + a) == (sreal (b) + sreal (a)).to_int ());
-  assert ((b - a) == (sreal (b) - sreal (a)).to_int ());
-}
-
-void
-sreal_pass::verify_shifting (int a)
-{
-  sreal v = a;
-
-  for (unsigned i = 0; i < 16; i++)
-    assert ((a << i) == (v << i).to_int());
-
-  a = a << 16;
-  v = v << 16;
-
-  for (unsigned i = 0; i < 16; i++)
-    assert ((a >> i) == (v >> i).to_int());
-}
-
-void
-sreal_pass::check_sreal ()
-{
-  sreal minimum = INT_MIN;
-  sreal maximum = INT_MAX;
-  sreal seven = 7;
-  sreal minus_two = -2;
-  sreal minus_nine = -9;
-
-  assert (minimum.to_int () == INT_MIN);
-  assert (maximum.to_int () == INT_MAX);
-
-  assert (!(minus_two < minus_two));
-  assert (!(seven < seven));
-  assert (seven > minus_two);
-  assert (minus_two < seven);
-  assert (minus_two != seven);
-  assert (minus_two == minus_two);
-  assert (seven == seven);
-
-  assert (seven == ((seven << 10) >> 10));
-
-  assert ((seven + minus_two) == 5);
-  assert ((seven + minus_nine) == -2);
-
-  for (int a = -100; a < 100; a++)
-    for (int b = -100; b < 100; b++)
-      {
-        verify_aritmetics (a, b);
-        verify_aritmetics (INT_MIN + 100, b);
-        verify_aritmetics (INT_MAX - 100, b);
-      }
-
-  srand (123456);
-
-  for (int i = 0; i < 1000 * 1000; i++)
-    {
-      verify_aritmetics (rand () % 10, rand () % 1000000);
-      verify_aritmetics (rand () % 100, rand () % 10000);
-    }
-
-  for (int a = -100; a < 100; a++)
-    verify_shifting (a);
-}
-
-bool sreal_pass::gate (function *)
-{
-  return true;
-}
-
-unsigned int
-sreal_pass::execute (function *)
-{
-  check_sreal ();
-
-  return 0;
-}
-
-int plugin_init (struct plugin_name_args *plugin_info,
-                 struct plugin_gcc_version *version)
-{
-  struct register_pass_info p;
-
-  p.pass = new sreal_pass (g);
-  p.reference_pass_name = "cfg";
-  p.ref_pass_instance_number = 1;
-  p.pos_op = PASS_POS_INSERT_AFTER;
-
-  register_callback ("sreal", PLUGIN_PASS_MANAGER_SETUP, NULL, &p);
-
-  return 0;
-}
-- 
2.8.4

[PATCH 0/2] New selftests: sreal and fibonacci_heap

[marxin]

Hello.

Following small patch set adds selftests for sreal and fibonacci_heap.
I basically transformed the existing tests (for sreal) which were implemented
as a GCC plugin.

Current implementation of the fibonacci heap corrupts memory in
union_with and another usability change was applied to insert_node function.

Patches survive regression tests and bootstrap on x86_64-linux-gnu
and ppc64le-linux-gnu. Apart from that, aarch64 compiler can be built
w/ --disable-bootstrap.

Ready for trunk?
Martin

marxin (2):
  Add sreal to selftests
  Add selftests for fibonacci_heap

 gcc/Makefile.in                            |   1 +
 gcc/fibonacci_heap.c                       | 290 +++++++++++++++++++++++++++++
 gcc/fibonacci_heap.h                       |  37 +++-
 gcc/selftest-run-tests.c                   |   2 +
 gcc/selftest.h                             |   2 +
 gcc/sreal.c                                | 112 +++++++++++
 gcc/testsuite/gcc.dg/plugin/plugin.exp     |   1 -
 gcc/testsuite/gcc.dg/plugin/sreal-test-1.c |   8 -
 gcc/testsuite/gcc.dg/plugin/sreal_plugin.c | 170 -----------------
 9 files changed, 435 insertions(+), 188 deletions(-)
 create mode 100644 gcc/fibonacci_heap.c
 delete mode 100644 gcc/testsuite/gcc.dg/plugin/sreal-test-1.c
 delete mode 100644 gcc/testsuite/gcc.dg/plugin/sreal_plugin.c

-- 
2.8.4

[PATCH 2/2] Add selftests for fibonacci_heap

[marxin]

gcc/ChangeLog:

2016-07-13  Martin Liska  <mliska@suse.cz>

	* Makefile.in: Include fibonacci_heap.c
	* fibonacci_heap.c: New file.
	* fibonacci_heap.h (fibonacci_heap::insert): Use insert_node.
	(fibonacci_heap::union_with): Fix deletion of the second heap.
	* selftest-run-tests.c (selftest::run_tests): Incroporate
	fibonacci heap tests.
	* selftest.h: Declare fibonacci_heap_c_tests.
---
 gcc/Makefile.in          |   1 +
 gcc/fibonacci_heap.c     | 290 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/fibonacci_heap.h     |  37 ++++--
 gcc/selftest-run-tests.c |   1 +
 gcc/selftest.h           |   1 +
 5 files changed, 321 insertions(+), 9 deletions(-)
 create mode 100644 gcc/fibonacci_heap.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 0786fa3..bfa467c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1259,6 +1259,7 @@ OBJS = \
 	explow.o \
 	expmed.o \
 	expr.o \
+	fibonacci_heap.o \
 	final.o \
 	fixed-value.o \
 	fold-const.o \
diff --git a/gcc/fibonacci_heap.c b/gcc/fibonacci_heap.c
new file mode 100644
index 0000000..db58417
--- /dev/null
+++ b/gcc/fibonacci_heap.c
@@ -0,0 +1,290 @@
+/* Fibonacci heap for GNU compiler.
+   Copyright (C) 2016 Free Software Foundation, Inc.
+   Contributed by Martin Liska <mliska@suse.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC 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 General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "fibonacci_heap.h"
+#include "selftest.h"
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Selftests.  */
+
+/* Verify that operations with empty heap work.  */
+
+typedef fibonacci_node <int, int> int_heap_node_t;
+typedef fibonacci_heap <int, int> int_heap_t;
+
+static void
+test_empty_heap ()
+{
+  int_heap_t *h1 = new int_heap_t (INT_MIN);
+
+  ASSERT_TRUE (h1->empty ());
+  ASSERT_EQ (0, h1->nodes ());
+  ASSERT_EQ (NULL, h1->min ());
+
+  int_heap_t *h2 = new int_heap_t (INT_MIN);
+
+  int_heap_t *r = h1->union_with (h2);
+  ASSERT_TRUE (r->empty ());
+  ASSERT_EQ (0, r->nodes ());
+  ASSERT_EQ (NULL, r->min ());
+
+  delete r;
+}
+
+#define TEST_HEAP_N 100
+#define TEST_CALCULATE_VALUE(i)  ((3 * i) + 10000)
+
+/* Verify heap basic operations.  */
+
+static void
+test_basic_heap_operations ()
+{
+  int values[TEST_HEAP_N];
+  int_heap_t *h1 = new int_heap_t (INT_MIN);
+
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    {
+      values[i] = TEST_CALCULATE_VALUE (i);
+      ASSERT_EQ (i, h1->nodes ());
+      h1->insert (i, &values[i]);
+      ASSERT_EQ (0, h1->min_key ());
+      ASSERT_EQ (values[0], *h1->min ());
+    }
+
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    {
+      ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
+      ASSERT_EQ ((int)i, h1->min_key ());
+      ASSERT_EQ (values[i], *h1->min ());
+
+      h1->extract_min ();
+    }
+
+  ASSERT_TRUE (h1->empty ());
+
+  delete h1;
+}
+
+/* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
+   of each key is equal to 3 * key + 10000.  BUFFER is used as a storage
+   of values and NODES points to inserted nodes.  */
+
+static int_heap_t *
+build_simple_heap (int *buffer, int_heap_node_t **nodes)
+{
+  int_heap_t *h = new int_heap_t (INT_MIN);
+
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    {
+      buffer[i] = TEST_CALCULATE_VALUE (i);
+      nodes[i] = h->insert (i, &buffer[i]);
+    }
+
+  return h;
+}
+
+/* Verify that fibonacci_heap::replace_key works.  */
+
+static void
+test_replace_key ()
+{
+  int values[TEST_HEAP_N];
+  int_heap_node_t *nodes[TEST_HEAP_N];
+
+  int_heap_t *heap = build_simple_heap (values, nodes);
+
+  int N = 10;
+  for (unsigned i = 0; i < (unsigned)N; i++)
+    heap->replace_key (nodes[i], 100 * 1000 + i);
+
+  ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
+  ASSERT_EQ (N, heap->min_key ());
+  ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
+
+  for (int i = 0; i < TEST_HEAP_N - 1; i++)
+    heap->extract_min ();
+
+  ASSERT_EQ (1, heap->nodes ());
+  ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
+
+  delete heap;
+}
+
+/* Verify that heap can handle duplicite keys.  */
+
+static void
+test_duplicite_keys ()
+{
+  int values[3 * TEST_HEAP_N];
+  int_heap_t *heap = new int_heap_t (INT_MIN);
+
+  for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
+    {
+      values[i] = TEST_CALCULATE_VALUE (i);
+      heap->insert (i / 3, &values[i]);
+    }
+
+  ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
+  ASSERT_EQ (0, heap->min_key ());
+  ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
+
+  for (unsigned i = 0; i < 9; i++)
+    heap->extract_min ();
+
+  for (unsigned i = 0; i < 3; i++)
+    {
+      ASSERT_EQ (3, heap->min_key ());
+      heap->extract_min ();
+    }
+
+  delete heap;
+}
+
+/* Verify that heap can handle union.  */
+
+static void
+test_union ()
+{
+  int value = 777;
+
+  int_heap_t *heap1 = new int_heap_t (INT_MIN);
+  for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
+    heap1->insert (i, &value);
+
+  int_heap_t *heap2 = new int_heap_t (INT_MIN);
+  for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
+    heap2->insert (i, &value);
+
+  int_heap_t *union_heap = heap1->union_with (heap2);
+
+  for (int i = 0; i < 3 * TEST_HEAP_N; i++)
+    {
+      ASSERT_EQ (i, union_heap->min_key ());
+      union_heap->extract_min ();
+    }
+
+  delete union_heap;
+}
+
+/* Verify that heap can handle union with a heap having exactly the same
+   keys.  */
+
+static void
+test_union_of_equal_heaps ()
+{
+  int value = 777;
+
+  int_heap_t *heap1 = new int_heap_t (INT_MIN);
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    heap1->insert (i, &value);
+
+  int_heap_t *heap2 = new int_heap_t (INT_MIN);
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    heap2->insert (i, &value);
+
+  int_heap_t *union_heap = heap1->union_with (heap2);
+
+  for (int i = 0; i < TEST_HEAP_N; i++)
+    for (int j = 0; j < 2; j++)
+    {
+      ASSERT_EQ (i, union_heap->min_key ());
+      union_heap->extract_min ();
+    }
+
+  delete union_heap;
+}
+
+/* Dummy struct for testing.  */
+
+struct heap_key
+{
+  heap_key (int k): key (k)
+  {
+  }
+
+  int key;
+
+  bool operator< (const heap_key &other) const
+  {
+    return key > other.key;
+  }
+
+  bool operator== (const heap_key &other) const
+  {
+    return key == other.key;
+  }
+
+  bool operator> (const heap_key &other) const
+  {
+    return !(*this == other || *this < other);
+  }
+};
+
+typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
+
+/* Verify that heap can handle a struct as key type.  */
+
+static void
+test_struct_key ()
+{
+  int value = 123456;
+  class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
+
+  heap->insert (heap_key (1), &value);
+  heap->insert (heap_key (10), &value);
+  heap->insert (heap_key (100), &value);
+  heap->insert (heap_key (1000), &value);
+
+  ASSERT_EQ (1000, heap->min_key ().key);
+  ASSERT_EQ (4, heap->nodes ());
+  heap->extract_min ();
+  heap->extract_min ();
+  ASSERT_EQ (10, heap->min_key ().key);
+  heap->extract_min ();
+  ASSERT_EQ (&value, heap->min ());
+  heap->extract_min ();
+  ASSERT_TRUE (heap->empty ());
+
+  delete heap;
+}
+
+/* Run all of the selftests within this file.  */
+
+void
+fibonacci_heap_c_tests ()
+{
+  test_empty_heap ();
+  test_basic_heap_operations ();
+  test_replace_key ();
+  test_duplicite_keys ();
+  test_union ();
+  test_union_of_equal_heaps ();
+  test_struct_key ();
+}
+
+} // namespace selftest
+
+#endif /* #if CHECKING_P */
diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
index c6c2a45..602d5ee 100644
--- a/gcc/fibonacci_heap.h
+++ b/gcc/fibonacci_heap.h
@@ -1,4 +1,4 @@
-/* Vector API for GNU compiler.
+/* Fibonacci heap for GNU compiler.
    Copyright (C) 1998-2016 Free Software Foundation, Inc.
    Contributed by Daniel Berlin (dan@cgsoftware.com).
    Re-implemented in C++ by Martin Liska <mliska@suse.cz>
@@ -61,8 +61,8 @@ public:
   }
 
   /* Constructor for a node with given KEY.  */
-  fibonacci_node (K key): m_parent (NULL), m_child (NULL), m_left (this),
-    m_right (this), m_key (key),
+  fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
+    m_left (this), m_right (this), m_key (key), m_data (data),
     m_degree (0), m_mark (0)
   {
   }
@@ -230,6 +230,9 @@ private:
   /* Insert new NODE given by KEY and DATA associated with the key.  */
   fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
 
+  /* Insert new NODE that has alredy filled key and value.  */
+  fibonacci_node_t *insert_node (fibonacci_node_t *node);
+
   /* Insert it into the root list.  */
   void insert_root (fibonacci_node_t *node);
 
@@ -330,12 +333,12 @@ fibonacci_node<K,V>*
 fibonacci_heap<K,V>::insert (K key, V *data)
 {
   /* Create the new node.  */
-  fibonacci_node<K,V> *node = new fibonacci_node_t ();
+  fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
 
-  return insert (node, key, data);
+  return insert_node (node);
 }
 
-/* Insert new NODE given by KEY and DATA associated with the key.  */
+/* Insert new NODE given by DATA associated with the key.  */
 
 template<class K, class V>
 fibonacci_node<K,V>*
@@ -345,6 +348,15 @@ fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
   node->m_data = data;
   node->m_key = key;
 
+  return insert_node (node);
+}
+
+/* Insert new NODE that has alredy filled key and value.  */
+
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
+{
   /* Insert it into the root list.  */
   insert_root (node);
 
@@ -359,6 +371,7 @@ fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
 }
 
 /* For given NODE, set new KEY and DATA value.  */
+
 template<class K, class V>
 V*
 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
@@ -406,7 +419,9 @@ fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
   return odata;
 }
 
-/* Extract minimum node in the heap.  */
+/* Extract minimum node in the heap.  Delete fibonacci node if RELEASE
+   is true.  */
+
 template<class K, class V>
 V*
 fibonacci_heap<K,V>::extract_min (bool release)
@@ -449,7 +464,7 @@ fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
   return ret;
 }
 
-/* Union the heap with HEAPB.  */
+/* Union the heap with HEAPB.  One of the heaps is going to be deleted.  */
 
 template<class K, class V>
 fibonacci_heap<K,V>*
@@ -478,10 +493,13 @@ fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
   heapa->m_nodes += heapb->m_nodes;
 
   /* And set the new minimum, if it's changed.  */
-  if (heapb->min->compare (heapa->min) < 0)
+  if (heapb->m_min->compare (heapa->m_min) < 0)
     heapa->m_min = heapb->m_min;
 
+  /* Set m_min to NULL to not to delete live fibonacci nodes.  */
+  heapb->m_min = NULL;
   delete (heapb);
+
   return heapa;
 }
 
@@ -544,6 +562,7 @@ fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
 }
 
 /* Extract minimum node from the heap.  */
+
 template<class K, class V>
 fibonacci_node<K,V>*
 fibonacci_heap<K,V>::extract_minimum_node ()
diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index bb004cc..85e101d 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -50,6 +50,7 @@ selftest::run_tests ()
   wide_int_cc_tests ();
   ggc_tests_c_tests ();
   sreal_c_tests ();
+  fibonacci_heap_c_tests ();
 
   /* Mid-level data structures.  */
   input_c_tests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index c805386..0bee476 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -76,6 +76,7 @@ extern void diagnostic_c_tests ();
 extern void diagnostic_show_locus_c_tests ();
 extern void et_forest_c_tests ();
 extern void fold_const_c_tests ();
+extern void fibonacci_heap_c_tests ();
 extern void function_tests_c_tests ();
 extern void gimple_c_tests ();
 extern void ggc_tests_c_tests ();
-- 
2.8.4

Re: [PATCH 2/2] Add selftests for fibonacci_heap

[David Malcolm]

On Tue, 2016-07-12 at 15:17 +0200, marxin wrote:

Thanks for writing selftests!

FWIW, some spelling nits below (I'm not a reviewer, and not familiar
with our fibonacci heap implementation).

> gcc/ChangeLog:
> 
> 2016-07-13  Martin Liska  <mliska@suse.cz>
> 
> 	* Makefile.in: Include fibonacci_heap.c
> 	* fibonacci_heap.c: New file.
> 	* fibonacci_heap.h (fibonacci_heap::insert): Use insert_node.
> 	(fibonacci_heap::union_with): Fix deletion of the second heap.
> 	* selftest-run-tests.c (selftest::run_tests): Incroporate

Spelling nit: "Incroporate" -> "Incorporate".

> 	fibonacci heap tests.
> 	* selftest.h: Declare fibonacci_heap_c_tests.


diff --git a/gcc/fibonacci_heap.c b/gcc/fibonacci_heap.c
> new file mode 100644
> index 0000000..db58417
> --- /dev/null
> +++ b/gcc/fibonacci_heap.c

[...]


> +/* Verify that heap can handle duplicite keys.  */

Spelling nit:
  "duplicite" -> "duplicate"

> +
> +static void
> +test_duplicite_keys ()

and here ^^^^^^^^

> diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
> index c6c2a45..602d5ee 100644
> --- a/gcc/fibonacci_heap.h
> +++ b/gcc/fibonacci_heap.h

[...]

> @@ -230,6 +230,9 @@ private:
>    /* Insert new NODE given by KEY and DATA associated with the key. 
>  */
>    fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
>  
> +  /* Insert new NODE that has alredy filled key and value.  */

Spelling nit: "alredy" -> "already".

> @@ -345,6 +348,15 @@ fibonacci_heap<K,V>::insert (fibonacci_node_t
> +/* Insert new NODE that has alredy filled key and value.  */
> 

Likewise: "alredy" -> "already".

Re: [PATCH 2/2] Add selftests for fibonacci_heap

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 65 bytes --]

Thank you for the nits, sending second version of the patch.

M.

[-- Attachment #2: 0002-Add-selftests-for-fibonacci_heap-v2.patch --]
[-- Type: text/x-patch, Size: 12603 bytes --]

From be12e60d4a2731cf4f1f68516e08f5bdb6c1ef77 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Tue, 12 Jul 2016 15:17:24 +0200
Subject: [PATCH 2/2] Add selftests for fibonacci_heap

gcc/ChangeLog:

2016-07-13  Martin Liska  <mliska@suse.cz>

	* Makefile.in: Include fibonacci_heap.c
	* fibonacci_heap.c: New file.
	* fibonacci_heap.h (fibonacci_heap::insert): Use insert_node.
	(fibonacci_heap::union_with): Fix deletion of the second heap.
	* selftest-run-tests.c (selftest::run_tests): Incorporate
	fibonacci heap tests.
	* selftest.h: Declare fibonacci_heap_c_tests.
---
 gcc/Makefile.in          |   1 +
 gcc/fibonacci_heap.c     | 290 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/fibonacci_heap.h     |  37 ++++--
 gcc/selftest-run-tests.c |   1 +
 gcc/selftest.h           |   1 +
 5 files changed, 321 insertions(+), 9 deletions(-)
 create mode 100644 gcc/fibonacci_heap.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 0786fa3..bfa467c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1259,6 +1259,7 @@ OBJS = \
 	explow.o \
 	expmed.o \
 	expr.o \
+	fibonacci_heap.o \
 	final.o \
 	fixed-value.o \
 	fold-const.o \
diff --git a/gcc/fibonacci_heap.c b/gcc/fibonacci_heap.c
new file mode 100644
index 0000000..afc8581
--- /dev/null
+++ b/gcc/fibonacci_heap.c
@@ -0,0 +1,290 @@
+/* Fibonacci heap for GNU compiler.
+   Copyright (C) 2016 Free Software Foundation, Inc.
+   Contributed by Martin Liska <mliska@suse.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC 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 General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "fibonacci_heap.h"
+#include "selftest.h"
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Selftests.  */
+
+/* Verify that operations with empty heap work.  */
+
+typedef fibonacci_node <int, int> int_heap_node_t;
+typedef fibonacci_heap <int, int> int_heap_t;
+
+static void
+test_empty_heap ()
+{
+  int_heap_t *h1 = new int_heap_t (INT_MIN);
+
+  ASSERT_TRUE (h1->empty ());
+  ASSERT_EQ (0, h1->nodes ());
+  ASSERT_EQ (NULL, h1->min ());
+
+  int_heap_t *h2 = new int_heap_t (INT_MIN);
+
+  int_heap_t *r = h1->union_with (h2);
+  ASSERT_TRUE (r->empty ());
+  ASSERT_EQ (0, r->nodes ());
+  ASSERT_EQ (NULL, r->min ());
+
+  delete r;
+}
+
+#define TEST_HEAP_N 100
+#define TEST_CALCULATE_VALUE(i)  ((3 * i) + 10000)
+
+/* Verify heap basic operations.  */
+
+static void
+test_basic_heap_operations ()
+{
+  int values[TEST_HEAP_N];
+  int_heap_t *h1 = new int_heap_t (INT_MIN);
+
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    {
+      values[i] = TEST_CALCULATE_VALUE (i);
+      ASSERT_EQ (i, h1->nodes ());
+      h1->insert (i, &values[i]);
+      ASSERT_EQ (0, h1->min_key ());
+      ASSERT_EQ (values[0], *h1->min ());
+    }
+
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    {
+      ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
+      ASSERT_EQ ((int)i, h1->min_key ());
+      ASSERT_EQ (values[i], *h1->min ());
+
+      h1->extract_min ();
+    }
+
+  ASSERT_TRUE (h1->empty ());
+
+  delete h1;
+}
+
+/* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
+   of each key is equal to 3 * key + 10000.  BUFFER is used as a storage
+   of values and NODES points to inserted nodes.  */
+
+static int_heap_t *
+build_simple_heap (int *buffer, int_heap_node_t **nodes)
+{
+  int_heap_t *h = new int_heap_t (INT_MIN);
+
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    {
+      buffer[i] = TEST_CALCULATE_VALUE (i);
+      nodes[i] = h->insert (i, &buffer[i]);
+    }
+
+  return h;
+}
+
+/* Verify that fibonacci_heap::replace_key works.  */
+
+static void
+test_replace_key ()
+{
+  int values[TEST_HEAP_N];
+  int_heap_node_t *nodes[TEST_HEAP_N];
+
+  int_heap_t *heap = build_simple_heap (values, nodes);
+
+  int N = 10;
+  for (unsigned i = 0; i < (unsigned)N; i++)
+    heap->replace_key (nodes[i], 100 * 1000 + i);
+
+  ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
+  ASSERT_EQ (N, heap->min_key ());
+  ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
+
+  for (int i = 0; i < TEST_HEAP_N - 1; i++)
+    heap->extract_min ();
+
+  ASSERT_EQ (1, heap->nodes ());
+  ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
+
+  delete heap;
+}
+
+/* Verify that heap can handle duplicate keys.  */
+
+static void
+test_duplicate_keys ()
+{
+  int values[3 * TEST_HEAP_N];
+  int_heap_t *heap = new int_heap_t (INT_MIN);
+
+  for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
+    {
+      values[i] = TEST_CALCULATE_VALUE (i);
+      heap->insert (i / 3, &values[i]);
+    }
+
+  ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
+  ASSERT_EQ (0, heap->min_key ());
+  ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
+
+  for (unsigned i = 0; i < 9; i++)
+    heap->extract_min ();
+
+  for (unsigned i = 0; i < 3; i++)
+    {
+      ASSERT_EQ (3, heap->min_key ());
+      heap->extract_min ();
+    }
+
+  delete heap;
+}
+
+/* Verify that heap can handle union.  */
+
+static void
+test_union ()
+{
+  int value = 777;
+
+  int_heap_t *heap1 = new int_heap_t (INT_MIN);
+  for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
+    heap1->insert (i, &value);
+
+  int_heap_t *heap2 = new int_heap_t (INT_MIN);
+  for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
+    heap2->insert (i, &value);
+
+  int_heap_t *union_heap = heap1->union_with (heap2);
+
+  for (int i = 0; i < 3 * TEST_HEAP_N; i++)
+    {
+      ASSERT_EQ (i, union_heap->min_key ());
+      union_heap->extract_min ();
+    }
+
+  delete union_heap;
+}
+
+/* Verify that heap can handle union with a heap having exactly the same
+   keys.  */
+
+static void
+test_union_of_equal_heaps ()
+{
+  int value = 777;
+
+  int_heap_t *heap1 = new int_heap_t (INT_MIN);
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    heap1->insert (i, &value);
+
+  int_heap_t *heap2 = new int_heap_t (INT_MIN);
+  for (unsigned i = 0; i < TEST_HEAP_N; i++)
+    heap2->insert (i, &value);
+
+  int_heap_t *union_heap = heap1->union_with (heap2);
+
+  for (int i = 0; i < TEST_HEAP_N; i++)
+    for (int j = 0; j < 2; j++)
+    {
+      ASSERT_EQ (i, union_heap->min_key ());
+      union_heap->extract_min ();
+    }
+
+  delete union_heap;
+}
+
+/* Dummy struct for testing.  */
+
+struct heap_key
+{
+  heap_key (int k): key (k)
+  {
+  }
+
+  int key;
+
+  bool operator< (const heap_key &other) const
+  {
+    return key > other.key;
+  }
+
+  bool operator== (const heap_key &other) const
+  {
+    return key == other.key;
+  }
+
+  bool operator> (const heap_key &other) const
+  {
+    return !(*this == other || *this < other);
+  }
+};
+
+typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
+
+/* Verify that heap can handle a struct as key type.  */
+
+static void
+test_struct_key ()
+{
+  int value = 123456;
+  class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
+
+  heap->insert (heap_key (1), &value);
+  heap->insert (heap_key (10), &value);
+  heap->insert (heap_key (100), &value);
+  heap->insert (heap_key (1000), &value);
+
+  ASSERT_EQ (1000, heap->min_key ().key);
+  ASSERT_EQ (4, heap->nodes ());
+  heap->extract_min ();
+  heap->extract_min ();
+  ASSERT_EQ (10, heap->min_key ().key);
+  heap->extract_min ();
+  ASSERT_EQ (&value, heap->min ());
+  heap->extract_min ();
+  ASSERT_TRUE (heap->empty ());
+
+  delete heap;
+}
+
+/* Run all of the selftests within this file.  */
+
+void
+fibonacci_heap_c_tests ()
+{
+  test_empty_heap ();
+  test_basic_heap_operations ();
+  test_replace_key ();
+  test_duplicate_keys ();
+  test_union ();
+  test_union_of_equal_heaps ();
+  test_struct_key ();
+}
+
+} // namespace selftest
+
+#endif /* #if CHECKING_P */
diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
index c6c2a45..1345027 100644
--- a/gcc/fibonacci_heap.h
+++ b/gcc/fibonacci_heap.h
@@ -1,4 +1,4 @@
-/* Vector API for GNU compiler.
+/* Fibonacci heap for GNU compiler.
    Copyright (C) 1998-2016 Free Software Foundation, Inc.
    Contributed by Daniel Berlin (dan@cgsoftware.com).
    Re-implemented in C++ by Martin Liska <mliska@suse.cz>
@@ -61,8 +61,8 @@ public:
   }
 
   /* Constructor for a node with given KEY.  */
-  fibonacci_node (K key): m_parent (NULL), m_child (NULL), m_left (this),
-    m_right (this), m_key (key),
+  fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
+    m_left (this), m_right (this), m_key (key), m_data (data),
     m_degree (0), m_mark (0)
   {
   }
@@ -230,6 +230,9 @@ private:
   /* Insert new NODE given by KEY and DATA associated with the key.  */
   fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
 
+  /* Insert new NODE that has already filled key and value.  */
+  fibonacci_node_t *insert_node (fibonacci_node_t *node);
+
   /* Insert it into the root list.  */
   void insert_root (fibonacci_node_t *node);
 
@@ -330,12 +333,12 @@ fibonacci_node<K,V>*
 fibonacci_heap<K,V>::insert (K key, V *data)
 {
   /* Create the new node.  */
-  fibonacci_node<K,V> *node = new fibonacci_node_t ();
+  fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
 
-  return insert (node, key, data);
+  return insert_node (node);
 }
 
-/* Insert new NODE given by KEY and DATA associated with the key.  */
+/* Insert new NODE given by DATA associated with the key.  */
 
 template<class K, class V>
 fibonacci_node<K,V>*
@@ -345,6 +348,15 @@ fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
   node->m_data = data;
   node->m_key = key;
 
+  return insert_node (node);
+}
+
+/* Insert new NODE that has already filled key and value.  */
+
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
+{
   /* Insert it into the root list.  */
   insert_root (node);
 
@@ -359,6 +371,7 @@ fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
 }
 
 /* For given NODE, set new KEY and DATA value.  */
+
 template<class K, class V>
 V*
 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
@@ -406,7 +419,9 @@ fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
   return odata;
 }
 
-/* Extract minimum node in the heap.  */
+/* Extract minimum node in the heap.  Delete fibonacci node if RELEASE
+   is true.  */
+
 template<class K, class V>
 V*
 fibonacci_heap<K,V>::extract_min (bool release)
@@ -449,7 +464,7 @@ fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
   return ret;
 }
 
-/* Union the heap with HEAPB.  */
+/* Union the heap with HEAPB.  One of the heaps is going to be deleted.  */
 
 template<class K, class V>
 fibonacci_heap<K,V>*
@@ -478,10 +493,13 @@ fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
   heapa->m_nodes += heapb->m_nodes;
 
   /* And set the new minimum, if it's changed.  */
-  if (heapb->min->compare (heapa->min) < 0)
+  if (heapb->m_min->compare (heapa->m_min) < 0)
     heapa->m_min = heapb->m_min;
 
+  /* Set m_min to NULL to not to delete live fibonacci nodes.  */
+  heapb->m_min = NULL;
   delete (heapb);
+
   return heapa;
 }
 
@@ -544,6 +562,7 @@ fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
 }
 
 /* Extract minimum node from the heap.  */
+
 template<class K, class V>
 fibonacci_node<K,V>*
 fibonacci_heap<K,V>::extract_minimum_node ()
diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index bb004cc..85e101d 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -50,6 +50,7 @@ selftest::run_tests ()
   wide_int_cc_tests ();
   ggc_tests_c_tests ();
   sreal_c_tests ();
+  fibonacci_heap_c_tests ();
 
   /* Mid-level data structures.  */
   input_c_tests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index c805386..0bee476 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -76,6 +76,7 @@ extern void diagnostic_c_tests ();
 extern void diagnostic_show_locus_c_tests ();
 extern void et_forest_c_tests ();
 extern void fold_const_c_tests ();
+extern void fibonacci_heap_c_tests ();
 extern void function_tests_c_tests ();
 extern void gimple_c_tests ();
 extern void ggc_tests_c_tests ();
-- 
2.9.0

Re: [PATCH 2/2] Add selftests for fibonacci_heap

[Jeff Law]

On 07/19/2016 08:31 AM, Martin Liška wrote:
> Thank you for the nits, sending second version of the patch.
>
> M.
>
>
> 0002-Add-selftests-for-fibonacci_heap-v2.patch
>
>
> From be12e60d4a2731cf4f1f68516e08f5bdb6c1ef77 Mon Sep 17 00:00:00 2001
> From: marxin <mliska@suse.cz>
> Date: Tue, 12 Jul 2016 15:17:24 +0200
> Subject: [PATCH 2/2] Add selftests for fibonacci_heap
>
> gcc/ChangeLog:
>
> 2016-07-13  Martin Liska  <mliska@suse.cz>
>
> 	* Makefile.in: Include fibonacci_heap.c
> 	* fibonacci_heap.c: New file.
> 	* fibonacci_heap.h (fibonacci_heap::insert): Use insert_node.
> 	(fibonacci_heap::union_with): Fix deletion of the second heap.
> 	* selftest-run-tests.c (selftest::run_tests): Incorporate
> 	fibonacci heap tests.
> 	* selftest.h: Declare fibonacci_heap_c_tests.
OK.
jeff

Re: [PATCH 1/2] Add sreal to selftests

[Jeff Law]

On 07/11/2016 08:34 AM, marxin wrote:
> gcc/ChangeLog:
>
> 2016-07-12  Martin Liska  <mliska@suse.cz>
>
> 	* selftest-run-tests.c (selftest::run_tests): New function.
> 	* selftest.h (sreal_c_tests): Declare.
> 	* sreal.c (sreal_verify_basics): New function.
> 	(verify_aritmetics): Likewise.
> 	(sreal_verify_arithmetics): Likewise.
> 	(verify_shifting): Likewise.
> 	(sreal_verify_shifting): Likewise.
> 	(void sreal_c_tests): Likewise.
>
> gcc/testsuite/ChangeLog:
>
> 2016-07-12  Martin Liska  <mliska@suse.cz>
>
> 	* gcc.dg/plugin/plugin.exp: Remove sreal test.
> 	* gcc.dg/plugin/sreal-test-1.c: Remove.
> 	* gcc.dg/plugin/sreal_plugin.c: Remove.
> ---
>  gcc/selftest-run-tests.c                   |   1 +
>  gcc/selftest.h                             |   1 +
>  gcc/sreal.c                                | 112 +++++++++++++++++++
>  gcc/testsuite/gcc.dg/plugin/plugin.exp     |   1 -
>  gcc/testsuite/gcc.dg/plugin/sreal-test-1.c |   8 --
>  gcc/testsuite/gcc.dg/plugin/sreal_plugin.c | 170 -----------------------------
>  6 files changed, 114 insertions(+), 179 deletions(-)
>  delete mode 100644 gcc/testsuite/gcc.dg/plugin/sreal-test-1.c
>  delete mode 100644 gcc/testsuite/gcc.dg/plugin/sreal_plugin.c
>
> diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
> index bddf0b2..bb004cc 100644
> --- a/gcc/selftest-run-tests.c
> +++ b/gcc/selftest-run-tests.c
> @@ -49,6 +49,7 @@ selftest::run_tests ()
>    pretty_print_c_tests ();
>    wide_int_cc_tests ();
>    ggc_tests_c_tests ();
> +  sreal_c_tests ();
>
>    /* Mid-level data structures.  */
>    input_c_tests ();
> diff --git a/gcc/selftest.h b/gcc/selftest.h
> index 967e76b..c805386 100644
> --- a/gcc/selftest.h
> +++ b/gcc/selftest.h
> @@ -86,6 +86,7 @@ extern void pretty_print_c_tests ();
>  extern void rtl_tests_c_tests ();
>  extern void spellcheck_c_tests ();
>  extern void spellcheck_tree_c_tests ();
> +extern void sreal_c_tests ();
>  extern void tree_c_tests ();
>  extern void tree_cfg_c_tests ();
>  extern void vec_c_tests ();
> diff --git a/gcc/sreal.c b/gcc/sreal.c
> index a7c9c12..9c43b4e 100644
> --- a/gcc/sreal.c
> +++ b/gcc/sreal.c
> @@ -52,6 +52,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include <math.h>
>  #include "coretypes.h"
>  #include "sreal.h"
> +#include "selftest.h"
>
>  /* Print the content of struct sreal.  */
>
> @@ -233,3 +234,114 @@ sreal::operator/ (const sreal &other) const
>    r.normalize ();
>    return r;
>  }
> +
> +#if CHECKING_P
> +
> +namespace selftest {
> +
> +/* Selftests for sreals.  */
> +
> +/* Verify basic sreal operations.  */
> +
> +static void
> +sreal_verify_basics (void)
> +{
> +  sreal minimum = INT_MIN;
> +  sreal maximum = INT_MAX;
> +
> +  sreal seven = 7;
> +  sreal minus_two = -2;
> +  sreal minus_nine = -9;
> +
> +  ASSERT_EQ (INT_MIN, minimum.to_int ());
> +  ASSERT_EQ (INT_MAX, maximum.to_int ());
> +
> +  ASSERT_FALSE (minus_two < minus_two);
> +  ASSERT_FALSE (seven < seven);
> +  ASSERT_TRUE (seven > minus_two);
> +  ASSERT_TRUE (minus_two < seven);
> +  ASSERT_TRUE (minus_two != seven);
> +  ASSERT_EQ (minus_two, -2);
> +  ASSERT_EQ (seven, 7);
> +  ASSERT_EQ ((seven << 10) >> 10, 7);
> +  ASSERT_EQ (seven + minus_nine, -2);
> +}
> +
> +/* Helper function that performs basic arithmetics and comparison
> +   of given arguments A and B.  */
> +
> +static void
> +verify_aritmetics (int64_t a, int64_t b)
arithmetics rather than aritmetics?


OK with that change.

jeff