1 | /* Fibonacci heap for GNU compiler. |
2 | Copyright (C) 2016-2023 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 (heapb: 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 (key: i, data: &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 (key: i, data: &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 (buffer: values, nodes); |
120 | |
121 | int N = 10; |
122 | for (unsigned i = 0; i < (unsigned)N; i++) |
123 | heap->replace_key (node: nodes[i], key: 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 (key: i / 3, data: &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 (key: i, data: &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 (key: i, data: &value); |
183 | |
184 | int_heap_t *union_heap = heap1->union_with (heapb: 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 (key: i, data: &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 (key: i, data: &value); |
211 | |
212 | int_heap_t *union_heap = heap1->union_with (heapb: 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 (key: heap_key (1), data: &value); |
262 | heap->insert (key: heap_key (10), data: &value); |
263 | heap->insert (key: heap_key (100), data: &value); |
264 | heap->insert (key: heap_key (1000), data: &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_cc_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 | |