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
test_empty_heap()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
test_basic_heap_operations()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 *
build_simple_heap(int * buffer,int_heap_node_t ** nodes)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
test_replace_key()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
test_duplicate_keys()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
test_union()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
test_union_of_equal_heaps()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 struct heap_key
223 {
heap_keyheap_key224 heap_key (int k): key (k)
225 {
226 }
227
228 int key;
229
230 bool operator< (const heap_key &other) const
231 {
232 return key > other.key;
233 }
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 !(*this == other || *this < other);
243 }
244 };
245
246 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
247
248 /* Verify that heap can handle a struct as key type. */
249
250 static void
test_struct_key()251 test_struct_key ()
252 {
253 int value = 123456;
254 class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
255
256 heap->insert (heap_key (1), &value);
257 heap->insert (heap_key (10), &value);
258 heap->insert (heap_key (100), &value);
259 heap->insert (heap_key (1000), &value);
260
261 ASSERT_EQ (1000, heap->min_key ().key);
262 ASSERT_EQ (4, heap->nodes ());
263 heap->extract_min ();
264 heap->extract_min ();
265 ASSERT_EQ (10, heap->min_key ().key);
266 heap->extract_min ();
267 ASSERT_EQ (&value, heap->min ());
268 heap->extract_min ();
269 ASSERT_TRUE (heap->empty ());
270
271 delete heap;
272 }
273
274 /* Run all of the selftests within this file. */
275
276 void
fibonacci_heap_c_tests()277 fibonacci_heap_c_tests ()
278 {
279 test_empty_heap ();
280 test_basic_heap_operations ();
281 test_replace_key ();
282 test_duplicate_keys ();
283 test_union ();
284 test_union_of_equal_heaps ();
285 test_struct_key ();
286 }
287
288 } // namespace selftest
289
290 #endif /* #if CHECKING_P */
291