Line data Source code
1 : /* Fibonacci heap for GNU compiler.
2 : Copyright (C) 2016-2026 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 */
|
