Branch data Line data Source code
1 : : /* Fibonacci heap for GNU compiler.
2 : : Copyright (C) 2016-2025 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 : 4 : test_empty_heap ()
41 : : {
42 : 4 : pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
43 : 4 : int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);
44 : :
45 : 4 : ASSERT_TRUE (h1->empty ());
46 : 4 : ASSERT_EQ (0, h1->nodes ());
47 : 4 : ASSERT_EQ (NULL, h1->min ());
48 : :
49 : 4 : int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);
50 : :
51 : 4 : int_heap_t *r = h1->union_with (h2);
52 : 4 : ASSERT_TRUE (r->empty ());
53 : 4 : ASSERT_EQ (0, r->nodes ());
54 : 4 : ASSERT_EQ (NULL, r->min ());
55 : :
56 : 4 : delete r;
57 : 4 : }
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 : 4 : test_basic_heap_operations ()
66 : : {
67 : 4 : int values[TEST_HEAP_N];
68 : 4 : int_heap_t *h1 = new int_heap_t (INT_MIN);
69 : :
70 : 404 : for (unsigned i = 0; i < TEST_HEAP_N; i++)
71 : : {
72 : 400 : values[i] = TEST_CALCULATE_VALUE (i);
73 : 400 : ASSERT_EQ (i, h1->nodes ());
74 : 400 : h1->insert (i, &values[i]);
75 : 400 : ASSERT_EQ (0, h1->min_key ());
76 : 800 : ASSERT_EQ (values[0], *h1->min ());
77 : : }
78 : :
79 : 404 : for (unsigned i = 0; i < TEST_HEAP_N; i++)
80 : : {
81 : 400 : ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
82 : 400 : ASSERT_EQ ((int)i, h1->min_key ());
83 : 800 : ASSERT_EQ (values[i], *h1->min ());
84 : :
85 : 400 : h1->extract_min ();
86 : : }
87 : :
88 : 4 : ASSERT_TRUE (h1->empty ());
89 : :
90 : 4 : delete h1;
91 : 4 : }
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 : 4 : build_simple_heap (int *buffer, int_heap_node_t **nodes)
99 : : {
100 : 4 : int_heap_t *h = new int_heap_t (INT_MIN);
101 : :
102 : 404 : for (unsigned i = 0; i < TEST_HEAP_N; i++)
103 : : {
104 : 400 : buffer[i] = TEST_CALCULATE_VALUE (i);
105 : 400 : nodes[i] = h->insert (i, &buffer[i]);
106 : : }
107 : :
108 : 4 : return h;
109 : : }
110 : :
111 : : /* Verify that fibonacci_heap::replace_key works. */
112 : :
113 : : static void
114 : 4 : test_replace_key ()
115 : : {
116 : 4 : int values[TEST_HEAP_N];
117 : 4 : int_heap_node_t *nodes[TEST_HEAP_N];
118 : :
119 : 4 : int_heap_t *heap = build_simple_heap (values, nodes);
120 : :
121 : 4 : int N = 10;
122 : 44 : for (unsigned i = 0; i < (unsigned)N; i++)
123 : 40 : heap->replace_key (nodes[i], 100 * 1000 + i);
124 : :
125 : 4 : ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
126 : 4 : ASSERT_EQ (N, heap->min_key ());
127 : 8 : ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
128 : :
129 : 400 : for (int i = 0; i < TEST_HEAP_N - 1; i++)
130 : 396 : heap->extract_min ();
131 : :
132 : 4 : ASSERT_EQ (1, heap->nodes ());
133 : 4 : ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
134 : :
135 : 4 : delete heap;
136 : 4 : }
137 : :
138 : : /* Verify that heap can handle duplicate keys. */
139 : :
140 : : static void
141 : 4 : test_duplicate_keys ()
142 : : {
143 : 4 : int values[3 * TEST_HEAP_N];
144 : 4 : int_heap_t *heap = new int_heap_t (INT_MIN);
145 : :
146 : 1204 : for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
147 : : {
148 : 1200 : values[i] = TEST_CALCULATE_VALUE (i);
149 : 1200 : heap->insert (i / 3, &values[i]);
150 : : }
151 : :
152 : 4 : ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
153 : 4 : ASSERT_EQ (0, heap->min_key ());
154 : 8 : ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
155 : :
156 : 40 : for (unsigned i = 0; i < 9; i++)
157 : 36 : heap->extract_min ();
158 : :
159 : 16 : for (unsigned i = 0; i < 3; i++)
160 : : {
161 : 12 : ASSERT_EQ (3, heap->min_key ());
162 : 12 : heap->extract_min ();
163 : : }
164 : :
165 : 4 : delete heap;
166 : 4 : }
167 : :
168 : : /* Verify that heap can handle union. */
169 : :
170 : : static void
171 : 4 : test_union ()
172 : : {
173 : 4 : int value = 777;
174 : 4 : pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
175 : :
176 : 4 : int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
177 : 804 : for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
178 : 800 : heap1->insert (i, &value);
179 : :
180 : 4 : int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
181 : 404 : for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
182 : 400 : heap2->insert (i, &value);
183 : :
184 : 4 : int_heap_t *union_heap = heap1->union_with (heap2);
185 : :
186 : 1204 : for (int i = 0; i < 3 * TEST_HEAP_N; i++)
187 : : {
188 : 1200 : ASSERT_EQ (i, union_heap->min_key ());
189 : 1200 : union_heap->extract_min ();
190 : : }
191 : :
192 : 4 : delete union_heap;
193 : 4 : }
194 : :
195 : : /* Verify that heap can handle union with a heap having exactly the same
196 : : keys. */
197 : :
198 : : static void
199 : 4 : test_union_of_equal_heaps ()
200 : : {
201 : 4 : int value = 777;
202 : 4 : pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
203 : :
204 : 4 : int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
205 : 404 : for (unsigned i = 0; i < TEST_HEAP_N; i++)
206 : 400 : heap1->insert (i, &value);
207 : :
208 : 4 : int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
209 : 404 : for (unsigned i = 0; i < TEST_HEAP_N; i++)
210 : 400 : heap2->insert (i, &value);
211 : :
212 : 4 : int_heap_t *union_heap = heap1->union_with (heap2);
213 : :
214 : 404 : for (int i = 0; i < TEST_HEAP_N; i++)
215 : 1200 : for (int j = 0; j < 2; j++)
216 : : {
217 : 800 : ASSERT_EQ (i, union_heap->min_key ());
218 : 800 : union_heap->extract_min ();
219 : : }
220 : :
221 : 4 : delete union_heap;
222 : 4 : }
223 : :
224 : : /* Dummy struct for testing. */
225 : :
226 : : class heap_key
227 : : {
228 : : public:
229 : 20 : heap_key (int k): key (k)
230 : : {
231 : : }
232 : :
233 : : int key;
234 : :
235 : 20 : bool operator< (const heap_key &other) const
236 : : {
237 : 20 : return key > other.key;
238 : : }
239 : :
240 : : bool operator== (const heap_key &other) const
241 : : {
242 : : return key == other.key;
243 : : }
244 : :
245 : 0 : bool operator> (const heap_key &other) const
246 : : {
247 : 0 : 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 : 4 : test_struct_key ()
257 : : {
258 : 4 : int value = 123456;
259 : 4 : class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
260 : :
261 : 4 : heap->insert (heap_key (1), &value);
262 : 4 : heap->insert (heap_key (10), &value);
263 : 4 : heap->insert (heap_key (100), &value);
264 : 4 : heap->insert (heap_key (1000), &value);
265 : :
266 : 4 : ASSERT_EQ (1000, heap->min_key ().key);
267 : 4 : ASSERT_EQ (4, heap->nodes ());
268 : 4 : heap->extract_min ();
269 : 4 : heap->extract_min ();
270 : 4 : ASSERT_EQ (10, heap->min_key ().key);
271 : 4 : heap->extract_min ();
272 : 4 : ASSERT_EQ (&value, heap->min ());
273 : 4 : heap->extract_min ();
274 : 4 : ASSERT_TRUE (heap->empty ());
275 : :
276 : 4 : delete heap;
277 : 4 : }
278 : :
279 : : /* Run all of the selftests within this file. */
280 : :
281 : : void
282 : 4 : fibonacci_heap_cc_tests ()
283 : : {
284 : 4 : test_empty_heap ();
285 : 4 : test_basic_heap_operations ();
286 : 4 : test_replace_key ();
287 : 4 : test_duplicate_keys ();
288 : 4 : test_union ();
289 : 4 : test_union_of_equal_heaps ();
290 : 4 : test_struct_key ();
291 : 4 : }
292 : :
293 : : } // namespace selftest
294 : :
295 : : #endif /* #if CHECKING_P */
|
