annotate gcc/fibonacci_heap.c @ 145:1830386684a0

gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
111
kono
parents:
diff changeset
1 /* Fibonacci heap for GNU compiler.
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
2 Copyright (C) 2016-2020 Free Software Foundation, Inc.
111
kono
parents:
diff changeset
3 Contributed by Martin Liska <mliska@suse.cz>
kono
parents:
diff changeset
4
kono
parents:
diff changeset
5 This file is part of GCC.
kono
parents:
diff changeset
6
kono
parents:
diff changeset
7 GCC is free software; you can redistribute it and/or modify it under
kono
parents:
diff changeset
8 the terms of the GNU General Public License as published by the Free
kono
parents:
diff changeset
9 Software Foundation; either version 3, or (at your option) any later
kono
parents:
diff changeset
10 version.
kono
parents:
diff changeset
11
kono
parents:
diff changeset
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
kono
parents:
diff changeset
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
kono
parents:
diff changeset
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
kono
parents:
diff changeset
15 for more details.
kono
parents:
diff changeset
16
kono
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
kono
parents:
diff changeset
18 along with GCC; see the file COPYING3. If not see
kono
parents:
diff changeset
19 <http://www.gnu.org/licenses/>. */
kono
parents:
diff changeset
20
kono
parents:
diff changeset
21 #include "config.h"
kono
parents:
diff changeset
22 #include "system.h"
kono
parents:
diff changeset
23 #include "coretypes.h"
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
24 #include "alloc-pool.h"
111
kono
parents:
diff changeset
25 #include "fibonacci_heap.h"
kono
parents:
diff changeset
26 #include "selftest.h"
kono
parents:
diff changeset
27
kono
parents:
diff changeset
28 #if CHECKING_P
kono
parents:
diff changeset
29
kono
parents:
diff changeset
30 namespace selftest {
kono
parents:
diff changeset
31
kono
parents:
diff changeset
32 /* Selftests. */
kono
parents:
diff changeset
33
kono
parents:
diff changeset
34 /* Verify that operations with empty heap work. */
kono
parents:
diff changeset
35
kono
parents:
diff changeset
36 typedef fibonacci_node <int, int> int_heap_node_t;
kono
parents:
diff changeset
37 typedef fibonacci_heap <int, int> int_heap_t;
kono
parents:
diff changeset
38
kono
parents:
diff changeset
39 static void
kono
parents:
diff changeset
40 test_empty_heap ()
kono
parents:
diff changeset
41 {
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
42 pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
43 int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);
111
kono
parents:
diff changeset
44
kono
parents:
diff changeset
45 ASSERT_TRUE (h1->empty ());
kono
parents:
diff changeset
46 ASSERT_EQ (0, h1->nodes ());
kono
parents:
diff changeset
47 ASSERT_EQ (NULL, h1->min ());
kono
parents:
diff changeset
48
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
49 int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);
111
kono
parents:
diff changeset
50
kono
parents:
diff changeset
51 int_heap_t *r = h1->union_with (h2);
kono
parents:
diff changeset
52 ASSERT_TRUE (r->empty ());
kono
parents:
diff changeset
53 ASSERT_EQ (0, r->nodes ());
kono
parents:
diff changeset
54 ASSERT_EQ (NULL, r->min ());
kono
parents:
diff changeset
55
kono
parents:
diff changeset
56 delete r;
kono
parents:
diff changeset
57 }
kono
parents:
diff changeset
58
kono
parents:
diff changeset
59 #define TEST_HEAP_N 100
kono
parents:
diff changeset
60 #define TEST_CALCULATE_VALUE(i) ((3 * i) + 10000)
kono
parents:
diff changeset
61
kono
parents:
diff changeset
62 /* Verify heap basic operations. */
kono
parents:
diff changeset
63
kono
parents:
diff changeset
64 static void
kono
parents:
diff changeset
65 test_basic_heap_operations ()
kono
parents:
diff changeset
66 {
kono
parents:
diff changeset
67 int values[TEST_HEAP_N];
kono
parents:
diff changeset
68 int_heap_t *h1 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
69
kono
parents:
diff changeset
70 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
71 {
kono
parents:
diff changeset
72 values[i] = TEST_CALCULATE_VALUE (i);
kono
parents:
diff changeset
73 ASSERT_EQ (i, h1->nodes ());
kono
parents:
diff changeset
74 h1->insert (i, &values[i]);
kono
parents:
diff changeset
75 ASSERT_EQ (0, h1->min_key ());
kono
parents:
diff changeset
76 ASSERT_EQ (values[0], *h1->min ());
kono
parents:
diff changeset
77 }
kono
parents:
diff changeset
78
kono
parents:
diff changeset
79 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
80 {
kono
parents:
diff changeset
81 ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
kono
parents:
diff changeset
82 ASSERT_EQ ((int)i, h1->min_key ());
kono
parents:
diff changeset
83 ASSERT_EQ (values[i], *h1->min ());
kono
parents:
diff changeset
84
kono
parents:
diff changeset
85 h1->extract_min ();
kono
parents:
diff changeset
86 }
kono
parents:
diff changeset
87
kono
parents:
diff changeset
88 ASSERT_TRUE (h1->empty ());
kono
parents:
diff changeset
89
kono
parents:
diff changeset
90 delete h1;
kono
parents:
diff changeset
91 }
kono
parents:
diff changeset
92
kono
parents:
diff changeset
93 /* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
kono
parents:
diff changeset
94 of each key is equal to 3 * key + 10000. BUFFER is used as a storage
kono
parents:
diff changeset
95 of values and NODES points to inserted nodes. */
kono
parents:
diff changeset
96
kono
parents:
diff changeset
97 static int_heap_t *
kono
parents:
diff changeset
98 build_simple_heap (int *buffer, int_heap_node_t **nodes)
kono
parents:
diff changeset
99 {
kono
parents:
diff changeset
100 int_heap_t *h = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
101
kono
parents:
diff changeset
102 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
103 {
kono
parents:
diff changeset
104 buffer[i] = TEST_CALCULATE_VALUE (i);
kono
parents:
diff changeset
105 nodes[i] = h->insert (i, &buffer[i]);
kono
parents:
diff changeset
106 }
kono
parents:
diff changeset
107
kono
parents:
diff changeset
108 return h;
kono
parents:
diff changeset
109 }
kono
parents:
diff changeset
110
kono
parents:
diff changeset
111 /* Verify that fibonacci_heap::replace_key works. */
kono
parents:
diff changeset
112
kono
parents:
diff changeset
113 static void
kono
parents:
diff changeset
114 test_replace_key ()
kono
parents:
diff changeset
115 {
kono
parents:
diff changeset
116 int values[TEST_HEAP_N];
kono
parents:
diff changeset
117 int_heap_node_t *nodes[TEST_HEAP_N];
kono
parents:
diff changeset
118
kono
parents:
diff changeset
119 int_heap_t *heap = build_simple_heap (values, nodes);
kono
parents:
diff changeset
120
kono
parents:
diff changeset
121 int N = 10;
kono
parents:
diff changeset
122 for (unsigned i = 0; i < (unsigned)N; i++)
kono
parents:
diff changeset
123 heap->replace_key (nodes[i], 100 * 1000 + i);
kono
parents:
diff changeset
124
kono
parents:
diff changeset
125 ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
kono
parents:
diff changeset
126 ASSERT_EQ (N, heap->min_key ());
kono
parents:
diff changeset
127 ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
kono
parents:
diff changeset
128
kono
parents:
diff changeset
129 for (int i = 0; i < TEST_HEAP_N - 1; i++)
kono
parents:
diff changeset
130 heap->extract_min ();
kono
parents:
diff changeset
131
kono
parents:
diff changeset
132 ASSERT_EQ (1, heap->nodes ());
kono
parents:
diff changeset
133 ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
kono
parents:
diff changeset
134
kono
parents:
diff changeset
135 delete heap;
kono
parents:
diff changeset
136 }
kono
parents:
diff changeset
137
kono
parents:
diff changeset
138 /* Verify that heap can handle duplicate keys. */
kono
parents:
diff changeset
139
kono
parents:
diff changeset
140 static void
kono
parents:
diff changeset
141 test_duplicate_keys ()
kono
parents:
diff changeset
142 {
kono
parents:
diff changeset
143 int values[3 * TEST_HEAP_N];
kono
parents:
diff changeset
144 int_heap_t *heap = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
145
kono
parents:
diff changeset
146 for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
147 {
kono
parents:
diff changeset
148 values[i] = TEST_CALCULATE_VALUE (i);
kono
parents:
diff changeset
149 heap->insert (i / 3, &values[i]);
kono
parents:
diff changeset
150 }
kono
parents:
diff changeset
151
kono
parents:
diff changeset
152 ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
kono
parents:
diff changeset
153 ASSERT_EQ (0, heap->min_key ());
kono
parents:
diff changeset
154 ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
kono
parents:
diff changeset
155
kono
parents:
diff changeset
156 for (unsigned i = 0; i < 9; i++)
kono
parents:
diff changeset
157 heap->extract_min ();
kono
parents:
diff changeset
158
kono
parents:
diff changeset
159 for (unsigned i = 0; i < 3; i++)
kono
parents:
diff changeset
160 {
kono
parents:
diff changeset
161 ASSERT_EQ (3, heap->min_key ());
kono
parents:
diff changeset
162 heap->extract_min ();
kono
parents:
diff changeset
163 }
kono
parents:
diff changeset
164
kono
parents:
diff changeset
165 delete heap;
kono
parents:
diff changeset
166 }
kono
parents:
diff changeset
167
kono
parents:
diff changeset
168 /* Verify that heap can handle union. */
kono
parents:
diff changeset
169
kono
parents:
diff changeset
170 static void
kono
parents:
diff changeset
171 test_union ()
kono
parents:
diff changeset
172 {
kono
parents:
diff changeset
173 int value = 777;
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
174 pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
111
kono
parents:
diff changeset
175
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
176 int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
111
kono
parents:
diff changeset
177 for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
178 heap1->insert (i, &value);
kono
parents:
diff changeset
179
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
180 int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
111
kono
parents:
diff changeset
181 for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
182 heap2->insert (i, &value);
kono
parents:
diff changeset
183
kono
parents:
diff changeset
184 int_heap_t *union_heap = heap1->union_with (heap2);
kono
parents:
diff changeset
185
kono
parents:
diff changeset
186 for (int i = 0; i < 3 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
187 {
kono
parents:
diff changeset
188 ASSERT_EQ (i, union_heap->min_key ());
kono
parents:
diff changeset
189 union_heap->extract_min ();
kono
parents:
diff changeset
190 }
kono
parents:
diff changeset
191
kono
parents:
diff changeset
192 delete union_heap;
kono
parents:
diff changeset
193 }
kono
parents:
diff changeset
194
kono
parents:
diff changeset
195 /* Verify that heap can handle union with a heap having exactly the same
kono
parents:
diff changeset
196 keys. */
kono
parents:
diff changeset
197
kono
parents:
diff changeset
198 static void
kono
parents:
diff changeset
199 test_union_of_equal_heaps ()
kono
parents:
diff changeset
200 {
kono
parents:
diff changeset
201 int value = 777;
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
202 pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
111
kono
parents:
diff changeset
203
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
204 int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
111
kono
parents:
diff changeset
205 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
206 heap1->insert (i, &value);
kono
parents:
diff changeset
207
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
208 int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
111
kono
parents:
diff changeset
209 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
210 heap2->insert (i, &value);
kono
parents:
diff changeset
211
kono
parents:
diff changeset
212 int_heap_t *union_heap = heap1->union_with (heap2);
kono
parents:
diff changeset
213
kono
parents:
diff changeset
214 for (int i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
215 for (int j = 0; j < 2; j++)
kono
parents:
diff changeset
216 {
kono
parents:
diff changeset
217 ASSERT_EQ (i, union_heap->min_key ());
kono
parents:
diff changeset
218 union_heap->extract_min ();
kono
parents:
diff changeset
219 }
kono
parents:
diff changeset
220
kono
parents:
diff changeset
221 delete union_heap;
kono
parents:
diff changeset
222 }
kono
parents:
diff changeset
223
kono
parents:
diff changeset
224 /* Dummy struct for testing. */
kono
parents:
diff changeset
225
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
226 class heap_key
111
kono
parents:
diff changeset
227 {
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
228 public:
111
kono
parents:
diff changeset
229 heap_key (int k): key (k)
kono
parents:
diff changeset
230 {
kono
parents:
diff changeset
231 }
kono
parents:
diff changeset
232
kono
parents:
diff changeset
233 int key;
kono
parents:
diff changeset
234
kono
parents:
diff changeset
235 bool operator< (const heap_key &other) const
kono
parents:
diff changeset
236 {
kono
parents:
diff changeset
237 return key > other.key;
kono
parents:
diff changeset
238 }
kono
parents:
diff changeset
239
kono
parents:
diff changeset
240 bool operator== (const heap_key &other) const
kono
parents:
diff changeset
241 {
kono
parents:
diff changeset
242 return key == other.key;
kono
parents:
diff changeset
243 }
kono
parents:
diff changeset
244
kono
parents:
diff changeset
245 bool operator> (const heap_key &other) const
kono
parents:
diff changeset
246 {
kono
parents:
diff changeset
247 return !(*this == other || *this < other);
kono
parents:
diff changeset
248 }
kono
parents:
diff changeset
249 };
kono
parents:
diff changeset
250
kono
parents:
diff changeset
251 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
kono
parents:
diff changeset
252
kono
parents:
diff changeset
253 /* Verify that heap can handle a struct as key type. */
kono
parents:
diff changeset
254
kono
parents:
diff changeset
255 static void
kono
parents:
diff changeset
256 test_struct_key ()
kono
parents:
diff changeset
257 {
kono
parents:
diff changeset
258 int value = 123456;
kono
parents:
diff changeset
259 class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
kono
parents:
diff changeset
260
kono
parents:
diff changeset
261 heap->insert (heap_key (1), &value);
kono
parents:
diff changeset
262 heap->insert (heap_key (10), &value);
kono
parents:
diff changeset
263 heap->insert (heap_key (100), &value);
kono
parents:
diff changeset
264 heap->insert (heap_key (1000), &value);
kono
parents:
diff changeset
265
kono
parents:
diff changeset
266 ASSERT_EQ (1000, heap->min_key ().key);
kono
parents:
diff changeset
267 ASSERT_EQ (4, heap->nodes ());
kono
parents:
diff changeset
268 heap->extract_min ();
kono
parents:
diff changeset
269 heap->extract_min ();
kono
parents:
diff changeset
270 ASSERT_EQ (10, heap->min_key ().key);
kono
parents:
diff changeset
271 heap->extract_min ();
kono
parents:
diff changeset
272 ASSERT_EQ (&value, heap->min ());
kono
parents:
diff changeset
273 heap->extract_min ();
kono
parents:
diff changeset
274 ASSERT_TRUE (heap->empty ());
kono
parents:
diff changeset
275
kono
parents:
diff changeset
276 delete heap;
kono
parents:
diff changeset
277 }
kono
parents:
diff changeset
278
kono
parents:
diff changeset
279 /* Run all of the selftests within this file. */
kono
parents:
diff changeset
280
kono
parents:
diff changeset
281 void
kono
parents:
diff changeset
282 fibonacci_heap_c_tests ()
kono
parents:
diff changeset
283 {
kono
parents:
diff changeset
284 test_empty_heap ();
kono
parents:
diff changeset
285 test_basic_heap_operations ();
kono
parents:
diff changeset
286 test_replace_key ();
kono
parents:
diff changeset
287 test_duplicate_keys ();
kono
parents:
diff changeset
288 test_union ();
kono
parents:
diff changeset
289 test_union_of_equal_heaps ();
kono
parents:
diff changeset
290 test_struct_key ();
kono
parents:
diff changeset
291 }
kono
parents:
diff changeset
292
kono
parents:
diff changeset
293 } // namespace selftest
kono
parents:
diff changeset
294
kono
parents:
diff changeset
295 #endif /* #if CHECKING_P */