]>
Commit | Line | Data |
---|---|---|
ba1a7a0f | 1 | /* Fibonacci heap for GNU compiler. |
a945c346 | 2 | Copyright (C) 2016-2024 Free Software Foundation, Inc. |
ba1a7a0f ML |
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" | |
516fd7ce | 24 | #include "alloc-pool.h" |
ba1a7a0f ML |
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 | { | |
516fd7ce JH |
42 | pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t)); |
43 | int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator); | |
ba1a7a0f ML |
44 | |
45 | ASSERT_TRUE (h1->empty ()); | |
46 | ASSERT_EQ (0, h1->nodes ()); | |
47 | ASSERT_EQ (NULL, h1->min ()); | |
48 | ||
516fd7ce | 49 | int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator); |
ba1a7a0f ML |
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; | |
516fd7ce | 174 | pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t)); |
ba1a7a0f | 175 | |
516fd7ce | 176 | int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator); |
ba1a7a0f ML |
177 | for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++) |
178 | heap1->insert (i, &value); | |
179 | ||
516fd7ce | 180 | int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator); |
ba1a7a0f ML |
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; | |
516fd7ce | 202 | pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t)); |
ba1a7a0f | 203 | |
516fd7ce | 204 | int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator); |
ba1a7a0f ML |
205 | for (unsigned i = 0; i < TEST_HEAP_N; i++) |
206 | heap1->insert (i, &value); | |
207 | ||
516fd7ce | 208 | int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator); |
ba1a7a0f ML |
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 | ||
6c1dae73 | 226 | class heap_key |
ba1a7a0f | 227 | { |
6c1dae73 | 228 | public: |
ba1a7a0f ML |
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 | |
d5148d4f | 282 | fibonacci_heap_cc_tests () |
ba1a7a0f ML |
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 */ |