LCOV - code coverage report
Current view: top level - gcc - fibonacci_heap.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 129 133 97.0 %
Date: 2020-03-28 11:57:23 Functions: 9 9 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Fibonacci heap for GNU compiler.
       2                 :            :    Copyright (C) 2016-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Martin Liska <mliska@suse.cz>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "alloc-pool.h"
      25                 :            : #include "fibonacci_heap.h"
      26                 :            : #include "selftest.h"
      27                 :            : 
      28                 :            : #if CHECKING_P
      29                 :            : 
      30                 :            : namespace selftest {
      31                 :            : 
      32                 :            : /* Selftests.  */
      33                 :            : 
      34                 :            : /* Verify that operations with empty heap work.  */
      35                 :            : 
      36                 :            : typedef fibonacci_node <int, int> int_heap_node_t;
      37                 :            : typedef fibonacci_heap <int, int> int_heap_t;
      38                 :            : 
      39                 :            : static void
      40                 :          2 : test_empty_heap ()
      41                 :            : {
      42                 :          2 :   pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
      43                 :          2 :   int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);
      44                 :            : 
      45                 :          2 :   ASSERT_TRUE (h1->empty ());
      46                 :          2 :   ASSERT_EQ (0, h1->nodes ());
      47                 :          2 :   ASSERT_EQ (NULL, h1->min ());
      48                 :            : 
      49                 :          2 :   int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);
      50                 :            : 
      51                 :          2 :   int_heap_t *r = h1->union_with (h2);
      52                 :          2 :   ASSERT_TRUE (r->empty ());
      53                 :          2 :   ASSERT_EQ (0, r->nodes ());
      54                 :          2 :   ASSERT_EQ (NULL, r->min ());
      55                 :            : 
      56                 :          2 :   delete r;
      57                 :          2 : }
      58                 :            : 
      59                 :            : #define TEST_HEAP_N 100
      60                 :            : #define TEST_CALCULATE_VALUE(i)  ((3 * i) + 10000)
      61                 :            : 
      62                 :            : /* Verify heap basic operations.  */
      63                 :            : 
      64                 :            : static void
      65                 :          2 : test_basic_heap_operations ()
      66                 :            : {
      67                 :          2 :   int values[TEST_HEAP_N];
      68                 :          2 :   int_heap_t *h1 = new int_heap_t (INT_MIN);
      69                 :            : 
      70                 :        202 :   for (unsigned i = 0; i < TEST_HEAP_N; i++)
      71                 :            :     {
      72                 :        200 :       values[i] = TEST_CALCULATE_VALUE (i);
      73                 :        200 :       ASSERT_EQ (i, h1->nodes ());
      74                 :        200 :       h1->insert (i, &values[i]);
      75                 :        200 :       ASSERT_EQ (0, h1->min_key ());
      76                 :        400 :       ASSERT_EQ (values[0], *h1->min ());
      77                 :            :     }
      78                 :            : 
      79                 :        202 :   for (unsigned i = 0; i < TEST_HEAP_N; i++)
      80                 :            :     {
      81                 :        200 :       ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
      82                 :        200 :       ASSERT_EQ ((int)i, h1->min_key ());
      83                 :        400 :       ASSERT_EQ (values[i], *h1->min ());
      84                 :            : 
      85                 :        200 :       h1->extract_min ();
      86                 :            :     }
      87                 :            : 
      88                 :          2 :   ASSERT_TRUE (h1->empty ());
      89                 :            : 
      90                 :          2 :   delete h1;
      91                 :          2 : }
      92                 :            : 
      93                 :            : /* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
      94                 :            :    of each key is equal to 3 * key + 10000.  BUFFER is used as a storage
      95                 :            :    of values and NODES points to inserted nodes.  */
      96                 :            : 
      97                 :            : static int_heap_t *
      98                 :          2 : build_simple_heap (int *buffer, int_heap_node_t **nodes)
      99                 :            : {
     100                 :          2 :   int_heap_t *h = new int_heap_t (INT_MIN);
     101                 :            : 
     102                 :        202 :   for (unsigned i = 0; i < TEST_HEAP_N; i++)
     103                 :            :     {
     104                 :        200 :       buffer[i] = TEST_CALCULATE_VALUE (i);
     105                 :        200 :       nodes[i] = h->insert (i, &buffer[i]);
     106                 :            :     }
     107                 :            : 
     108                 :          2 :   return h;
     109                 :            : }
     110                 :            : 
     111                 :            : /* Verify that fibonacci_heap::replace_key works.  */
     112                 :            : 
     113                 :            : static void
     114                 :          2 : test_replace_key ()
     115                 :            : {
     116                 :          2 :   int values[TEST_HEAP_N];
     117                 :          2 :   int_heap_node_t *nodes[TEST_HEAP_N];
     118                 :            : 
     119                 :          2 :   int_heap_t *heap = build_simple_heap (values, nodes);
     120                 :            : 
     121                 :          2 :   int N = 10;
     122                 :         22 :   for (unsigned i = 0; i < (unsigned)N; i++)
     123                 :         20 :     heap->replace_key (nodes[i], 100 * 1000 + i);
     124                 :            : 
     125                 :          2 :   ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
     126                 :          2 :   ASSERT_EQ (N, heap->min_key ());
     127                 :          4 :   ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
     128                 :            : 
     129                 :        200 :   for (int i = 0; i < TEST_HEAP_N - 1; i++)
     130                 :        198 :     heap->extract_min ();
     131                 :            : 
     132                 :          2 :   ASSERT_EQ (1, heap->nodes ());
     133                 :          2 :   ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
     134                 :            : 
     135                 :          2 :   delete heap;
     136                 :          2 : }
     137                 :            : 
     138                 :            : /* Verify that heap can handle duplicate keys.  */
     139                 :            : 
     140                 :            : static void
     141                 :          2 : test_duplicate_keys ()
     142                 :            : {
     143                 :          2 :   int values[3 * TEST_HEAP_N];
     144                 :          2 :   int_heap_t *heap = new int_heap_t (INT_MIN);
     145                 :            : 
     146                 :        602 :   for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
     147                 :            :     {
     148                 :        600 :       values[i] = TEST_CALCULATE_VALUE (i);
     149                 :        600 :       heap->insert (i / 3, &values[i]);
     150                 :            :     }
     151                 :            : 
     152                 :          2 :   ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
     153                 :          2 :   ASSERT_EQ (0, heap->min_key ());
     154                 :          4 :   ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
     155                 :            : 
     156                 :         20 :   for (unsigned i = 0; i < 9; i++)
     157                 :         18 :     heap->extract_min ();
     158                 :            : 
     159                 :          8 :   for (unsigned i = 0; i < 3; i++)
     160                 :            :     {
     161                 :          6 :       ASSERT_EQ (3, heap->min_key ());
     162                 :          6 :       heap->extract_min ();
     163                 :            :     }
     164                 :            : 
     165                 :          2 :   delete heap;
     166                 :          2 : }
     167                 :            : 
     168                 :            : /* Verify that heap can handle union.  */
     169                 :            : 
     170                 :            : static void
     171                 :          2 : test_union ()
     172                 :            : {
     173                 :          2 :   int value = 777;
     174                 :          2 :   pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
     175                 :            : 
     176                 :          2 :   int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
     177                 :        402 :   for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
     178                 :        400 :     heap1->insert (i, &value);
     179                 :            : 
     180                 :          2 :   int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
     181                 :        202 :   for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
     182                 :        200 :     heap2->insert (i, &value);
     183                 :            : 
     184                 :          2 :   int_heap_t *union_heap = heap1->union_with (heap2);
     185                 :            : 
     186                 :        602 :   for (int i = 0; i < 3 * TEST_HEAP_N; i++)
     187                 :            :     {
     188                 :        600 :       ASSERT_EQ (i, union_heap->min_key ());
     189                 :        600 :       union_heap->extract_min ();
     190                 :            :     }
     191                 :            : 
     192                 :          2 :   delete union_heap;
     193                 :          2 : }
     194                 :            : 
     195                 :            : /* Verify that heap can handle union with a heap having exactly the same
     196                 :            :    keys.  */
     197                 :            : 
     198                 :            : static void
     199                 :          2 : test_union_of_equal_heaps ()
     200                 :            : {
     201                 :          2 :   int value = 777;
     202                 :          2 :   pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
     203                 :            : 
     204                 :          2 :   int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
     205                 :        202 :   for (unsigned i = 0; i < TEST_HEAP_N; i++)
     206                 :        200 :     heap1->insert (i, &value);
     207                 :            : 
     208                 :          2 :   int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
     209                 :        202 :   for (unsigned i = 0; i < TEST_HEAP_N; i++)
     210                 :        200 :     heap2->insert (i, &value);
     211                 :            : 
     212                 :          2 :   int_heap_t *union_heap = heap1->union_with (heap2);
     213                 :            : 
     214                 :        202 :   for (int i = 0; i < TEST_HEAP_N; i++)
     215                 :        600 :     for (int j = 0; j < 2; j++)
     216                 :            :     {
     217                 :        400 :       ASSERT_EQ (i, union_heap->min_key ());
     218                 :        400 :       union_heap->extract_min ();
     219                 :            :     }
     220                 :            : 
     221                 :          2 :   delete union_heap;
     222                 :          2 : }
     223                 :            : 
     224                 :            : /* Dummy struct for testing.  */
     225                 :            : 
     226                 :            : class heap_key
     227                 :            : {
     228                 :            : public:
     229                 :         10 :   heap_key (int k): key (k)
     230                 :            :   {
     231                 :            :   }
     232                 :            : 
     233                 :            :   int key;
     234                 :            : 
     235                 :         10 :   bool operator< (const heap_key &other) const
     236                 :            :   {
     237                 :         10 :     return key > other.key;
     238                 :            :   }
     239                 :            : 
     240                 :          0 :   bool operator== (const heap_key &other) const
     241                 :            :   {
     242                 :          0 :     return key == other.key;
     243                 :            :   }
     244                 :            : 
     245                 :          0 :   bool operator> (const heap_key &other) const
     246                 :            :   {
     247                 :          0 :     return !(*this == other || *this < other);
     248                 :            :   }
     249                 :            : };
     250                 :            : 
     251                 :            : typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
     252                 :            : 
     253                 :            : /* Verify that heap can handle a struct as key type.  */
     254                 :            : 
     255                 :            : static void
     256                 :          2 : test_struct_key ()
     257                 :            : {
     258                 :          2 :   int value = 123456;
     259                 :          2 :   class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
     260                 :            : 
     261                 :          2 :   heap->insert (heap_key (1), &value);
     262                 :          2 :   heap->insert (heap_key (10), &value);
     263                 :          2 :   heap->insert (heap_key (100), &value);
     264                 :          2 :   heap->insert (heap_key (1000), &value);
     265                 :            : 
     266                 :          2 :   ASSERT_EQ (1000, heap->min_key ().key);
     267                 :          2 :   ASSERT_EQ (4, heap->nodes ());
     268                 :          2 :   heap->extract_min ();
     269                 :          2 :   heap->extract_min ();
     270                 :          2 :   ASSERT_EQ (10, heap->min_key ().key);
     271                 :          2 :   heap->extract_min ();
     272                 :          4 :   ASSERT_EQ (&value, heap->min ());
     273                 :          2 :   heap->extract_min ();
     274                 :          2 :   ASSERT_TRUE (heap->empty ());
     275                 :            : 
     276                 :          2 :   delete heap;
     277                 :          2 : }
     278                 :            : 
     279                 :            : /* Run all of the selftests within this file.  */
     280                 :            : 
     281                 :            : void
     282                 :          2 : fibonacci_heap_c_tests ()
     283                 :            : {
     284                 :          2 :   test_empty_heap ();
     285                 :          2 :   test_basic_heap_operations ();
     286                 :          2 :   test_replace_key ();
     287                 :          2 :   test_duplicate_keys ();
     288                 :          2 :   test_union ();
     289                 :          2 :   test_union_of_equal_heaps ();
     290                 :          2 :   test_struct_key ();
     291                 :          2 : }
     292                 :            : 
     293                 :            : } // namespace selftest
     294                 :            : 
     295                 :            : #endif /* #if CHECKING_P */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.