Add selftests for fibonacci_heap

	* 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.

From-SVN: r238509

6 files changed, 331 insertions, 9 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2d767c8..c6a3d6b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,15 @@
 2016-07-20  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.
+
+2016-07-20  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.
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 ();