summaryrefslogtreecommitdiff
path: root/gcc/fibonacci_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc/fibonacci_heap.c')
-rw-r--r--gcc/fibonacci_heap.c290
1 files changed, 290 insertions, 0 deletions
diff --git a/gcc/fibonacci_heap.c b/gcc/fibonacci_heap.c
new file mode 100644
index 0000000000..6f8dda2fd4
--- /dev/null
+++ b/gcc/fibonacci_heap.c
@@ -0,0 +1,290 @@
+/* Fibonacci heap for GNU compiler.
+ Copyright (C) 2016-2017 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 */
View Lorry Controller Status