From ba1a7a0f859c5c3e2998a89a0b9f78198f328a94 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Wed, 20 Jul 2016 09:01:48 +0200 Subject: 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 --- gcc/fibonacci_heap.c | 290 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 290 insertions(+) create mode 100644 gcc/fibonacci_heap.c (limited to 'gcc/fibonacci_heap.c') 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 + +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 +. */ + +#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_heap_node_t; +typedef fibonacci_heap 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 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 */ -- cgit v1.1