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
test_empty_heap()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
test_basic_heap_operations()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 *
build_simple_heap(int * buffer,int_heap_node_t ** nodes)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
test_replace_key()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
test_duplicate_keys()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
test_union()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
test_union_of_equal_heaps()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:
heap_key(int k)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
test_struct_key()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
fibonacci_heap_c_tests()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 */
296