gcc/fibonacci_heap.c

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