1/* Fibonacci heap for GNU compiler.
2   Copyright (C) 2016-2020 Free Software Foundation, Inc.
3   Contributed by Martin Liska <mliska@suse.cz>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
30namespace selftest {
31
32/* Selftests.  */
33
34/* Verify that operations with empty heap work.  */
35
36typedef fibonacci_node <int, int> int_heap_node_t;
37typedef fibonacci_heap <int, int> int_heap_t;
38
39static void
40test_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
64static void
65test_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
97static int_heap_t *
98build_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
113static void
114test_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
140static void
141test_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
170static void
171test_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
198static void
199test_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
226class heap_key
227{
228public:
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
251typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
252
253/* Verify that heap can handle a struct as key type.  */
254
255static void
256test_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
281void
282fibonacci_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 */
296