gcc/fibonacci_heap.c

   1 /* Fibonacci heap for GNU compiler.
   2    Copyright (C) 2016-2019 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 "fibonacci_heap.h"
  25 #include "selftest.h"
  26
  27 #if CHECKING_P
  28
  29 namespace selftest {
  30
  31 /* Selftests.  */
  32
  33 /* Verify that operations with empty heap work.  */
  34
  35 typedef fibonacci_node <int, int> int_heap_node_t;
  36 typedef fibonacci_heap <int, int> int_heap_t;
  37
  38 static void
  39 test_empty_heap ()
  40 {
  41   int_heap_t *h1 = new int_heap_t (INT_MIN);
  42
  43   ASSERT_TRUE (h1->empty ());
  44   ASSERT_EQ (0, h1->nodes ());
  45   ASSERT_EQ (NULL, h1->min ());
  46
  47   int_heap_t *h2 = new int_heap_t (INT_MIN);
  48
  49   int_heap_t *r = h1->union_with (h2);
  50   ASSERT_TRUE (r->empty ());
  51   ASSERT_EQ (0, r->nodes ());
  52   ASSERT_EQ (NULL, r->min ());
  53
  54   delete r;
  55 }
  56
  57 #define TEST_HEAP_N 100
  58 #define TEST_CALCULATE_VALUE(i)  ((3 * i) + 10000)
  59
  60 /* Verify heap basic operations.  */
  61
  62 static void
  63 test_basic_heap_operations ()
  64 {
  65   int values[TEST_HEAP_N];
  66   int_heap_t *h1 = new int_heap_t (INT_MIN);
  67
  68   for (unsigned i = 0; i < TEST_HEAP_N; i++)
  69     {
  70       values[i] = TEST_CALCULATE_VALUE (i);
  71       ASSERT_EQ (i, h1->nodes ());
  72       h1->insert (i, &values[i]);
  73       ASSERT_EQ (0, h1->min_key ());
  74       ASSERT_EQ (values[0], *h1->min ());
  75     }
  76
  77   for (unsigned i = 0; i < TEST_HEAP_N; i++)
  78     {
  79       ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
  80       ASSERT_EQ ((int)i, h1->min_key ());
  81       ASSERT_EQ (values[i], *h1->min ());
  82
  83       h1->extract_min ();
  84     }
  85
  86   ASSERT_TRUE (h1->empty ());
  87
  88   delete h1;
  89 }
  90
  91 /* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
  92    of each key is equal to 3 * key + 10000.  BUFFER is used as a storage
  93    of values and NODES points to inserted nodes.  */
  94
  95 static int_heap_t *
  96 build_simple_heap (int *buffer, int_heap_node_t **nodes)
  97 {
  98   int_heap_t *h = new int_heap_t (INT_MIN);
  99
 100   for (unsigned i = 0; i < TEST_HEAP_N; i++)
 101     {
 102       buffer[i] = TEST_CALCULATE_VALUE (i);
 103       nodes[i] = h->insert (i, &buffer[i]);
 104     }
 105
 106   return h;
 107 }
 108
 109 /* Verify that fibonacci_heap::replace_key works.  */
 110
 111 static void
 112 test_replace_key ()
 113 {
 114   int values[TEST_HEAP_N];
 115   int_heap_node_t *nodes[TEST_HEAP_N];
 116
 117   int_heap_t *heap = build_simple_heap (values, nodes);
 118
 119   int N = 10;
 120   for (unsigned i = 0; i < (unsigned)N; i++)
 121     heap->replace_key (nodes[i], 100 * 1000 + i);
 122
 123   ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
 124   ASSERT_EQ (N, heap->min_key ());
 125   ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
 126
 127   for (int i = 0; i < TEST_HEAP_N - 1; i++)
 128     heap->extract_min ();
 129
 130   ASSERT_EQ (1, heap->nodes ());
 131   ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
 132
 133   delete heap;
 134 }
 135
 136 /* Verify that heap can handle duplicate keys.  */
 137
 138 static void
 139 test_duplicate_keys ()
 140 {
 141   int values[3 * TEST_HEAP_N];
 142   int_heap_t *heap = new int_heap_t (INT_MIN);
 143
 144   for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
 145     {
 146       values[i] = TEST_CALCULATE_VALUE (i);
 147       heap->insert (i / 3, &values[i]);
 148     }
 149
 150   ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
 151   ASSERT_EQ (0, heap->min_key ());
 152   ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
 153
 154   for (unsigned i = 0; i < 9; i++)
 155     heap->extract_min ();
 156
 157   for (unsigned i = 0; i < 3; i++)
 158     {
 159       ASSERT_EQ (3, heap->min_key ());
 160       heap->extract_min ();
 161     }
 162
 163   delete heap;
 164 }
 165
 166 /* Verify that heap can handle union.  */
 167
 168 static void
 169 test_union ()
 170 {
 171   int value = 777;
 172
 173   int_heap_t *heap1 = new int_heap_t (INT_MIN);
 174   for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
 175     heap1->insert (i, &value);
 176
 177   int_heap_t *heap2 = new int_heap_t (INT_MIN);
 178   for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
 179     heap2->insert (i, &value);
 180
 181   int_heap_t *union_heap = heap1->union_with (heap2);
 182
 183   for (int i = 0; i < 3 * TEST_HEAP_N; i++)
 184     {
 185       ASSERT_EQ (i, union_heap->min_key ());
 186       union_heap->extract_min ();
 187     }
 188
 189   delete union_heap;
 190 }
 191
 192 /* Verify that heap can handle union with a heap having exactly the same
 193    keys.  */
 194
 195 static void
 196 test_union_of_equal_heaps ()
 197 {
 198   int value = 777;
 199
 200   int_heap_t *heap1 = new int_heap_t (INT_MIN);
 201   for (unsigned i = 0; i < TEST_HEAP_N; i++)
 202     heap1->insert (i, &value);
 203
 204   int_heap_t *heap2 = new int_heap_t (INT_MIN);
 205   for (unsigned i = 0; i < TEST_HEAP_N; i++)
 206     heap2->insert (i, &value);
 207
 208   int_heap_t *union_heap = heap1->union_with (heap2);
 209
 210   for (int i = 0; i < TEST_HEAP_N; i++)
 211     for (int j = 0; j < 2; j++)
 212     {
 213       ASSERT_EQ (i, union_heap->min_key ());
 214       union_heap->extract_min ();
 215     }
 216
 217   delete union_heap;
 218 }
 219
 220 /* Dummy struct for testing.  */
 221
 222 class heap_key
 223 {
 224 public:
 225   heap_key (int k): key (k)
 226   {
 227   }
 228
 229   int key;
 230
 231   bool operator< (const heap_key &other) const
 232   {
 233     return key > other.key;
 234   }
 235
 236   bool operator== (const heap_key &other) const
 237   {
 238     return key == other.key;
 239   }
 240
 241   bool operator> (const heap_key &other) const
 242   {
 243     return !(*this == other || *this < other);
 244   }
 245 };
 246
 247 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
 248
 249 /* Verify that heap can handle a struct as key type.  */
 250
 251 static void
 252 test_struct_key ()
 253 {
 254   int value = 123456;
 255   class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
 256
 257   heap->insert (heap_key (1), &value);
 258   heap->insert (heap_key (10), &value);
 259   heap->insert (heap_key (100), &value);
 260   heap->insert (heap_key (1000), &value);
 261
 262   ASSERT_EQ (1000, heap->min_key ().key);
 263   ASSERT_EQ (4, heap->nodes ());
 264   heap->extract_min ();
 265   heap->extract_min ();
 266   ASSERT_EQ (10, heap->min_key ().key);
 267   heap->extract_min ();
 268   ASSERT_EQ (&value, heap->min ());
 269   heap->extract_min ();
 270   ASSERT_TRUE (heap->empty ());
 271
 272   delete heap;
 273 }
 274
 275 /* Run all of the selftests within this file.  */
 276
 277 void
 278 fibonacci_heap_c_tests ()
 279 {
 280   test_empty_heap ();
 281   test_basic_heap_operations ();
 282   test_replace_key ();
 283   test_duplicate_keys ();
 284   test_union ();
 285   test_union_of_equal_heaps ();
 286   test_struct_key ();
 287 }
 288
 289 } // namespace selftest
 290
 291 #endif /* #if CHECKING_P */