annotate gcc/fibonacci_heap.c @ 111:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
111
kono
parents:
diff changeset
1 /* Fibonacci heap for GNU compiler.
kono
parents:
diff changeset
2 Copyright (C) 2016-2017 Free Software Foundation, Inc.
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"
kono
parents:
diff changeset
24 #include "fibonacci_heap.h"
kono
parents:
diff changeset
25 #include "selftest.h"
kono
parents:
diff changeset
26
kono
parents:
diff changeset
27 #if CHECKING_P
kono
parents:
diff changeset
28
kono
parents:
diff changeset
29 namespace selftest {
kono
parents:
diff changeset
30
kono
parents:
diff changeset
31 /* Selftests. */
kono
parents:
diff changeset
32
kono
parents:
diff changeset
33 /* Verify that operations with empty heap work. */
kono
parents:
diff changeset
34
kono
parents:
diff changeset
35 typedef fibonacci_node <int, int> int_heap_node_t;
kono
parents:
diff changeset
36 typedef fibonacci_heap <int, int> int_heap_t;
kono
parents:
diff changeset
37
kono
parents:
diff changeset
38 static void
kono
parents:
diff changeset
39 test_empty_heap ()
kono
parents:
diff changeset
40 {
kono
parents:
diff changeset
41 int_heap_t *h1 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
42
kono
parents:
diff changeset
43 ASSERT_TRUE (h1->empty ());
kono
parents:
diff changeset
44 ASSERT_EQ (0, h1->nodes ());
kono
parents:
diff changeset
45 ASSERT_EQ (NULL, h1->min ());
kono
parents:
diff changeset
46
kono
parents:
diff changeset
47 int_heap_t *h2 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
48
kono
parents:
diff changeset
49 int_heap_t *r = h1->union_with (h2);
kono
parents:
diff changeset
50 ASSERT_TRUE (r->empty ());
kono
parents:
diff changeset
51 ASSERT_EQ (0, r->nodes ());
kono
parents:
diff changeset
52 ASSERT_EQ (NULL, r->min ());
kono
parents:
diff changeset
53
kono
parents:
diff changeset
54 delete r;
kono
parents:
diff changeset
55 }
kono
parents:
diff changeset
56
kono
parents:
diff changeset
57 #define TEST_HEAP_N 100
kono
parents:
diff changeset
58 #define TEST_CALCULATE_VALUE(i) ((3 * i) + 10000)
kono
parents:
diff changeset
59
kono
parents:
diff changeset
60 /* Verify heap basic operations. */
kono
parents:
diff changeset
61
kono
parents:
diff changeset
62 static void
kono
parents:
diff changeset
63 test_basic_heap_operations ()
kono
parents:
diff changeset
64 {
kono
parents:
diff changeset
65 int values[TEST_HEAP_N];
kono
parents:
diff changeset
66 int_heap_t *h1 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
67
kono
parents:
diff changeset
68 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
69 {
kono
parents:
diff changeset
70 values[i] = TEST_CALCULATE_VALUE (i);
kono
parents:
diff changeset
71 ASSERT_EQ (i, h1->nodes ());
kono
parents:
diff changeset
72 h1->insert (i, &values[i]);
kono
parents:
diff changeset
73 ASSERT_EQ (0, h1->min_key ());
kono
parents:
diff changeset
74 ASSERT_EQ (values[0], *h1->min ());
kono
parents:
diff changeset
75 }
kono
parents:
diff changeset
76
kono
parents:
diff changeset
77 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
78 {
kono
parents:
diff changeset
79 ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
kono
parents:
diff changeset
80 ASSERT_EQ ((int)i, h1->min_key ());
kono
parents:
diff changeset
81 ASSERT_EQ (values[i], *h1->min ());
kono
parents:
diff changeset
82
kono
parents:
diff changeset
83 h1->extract_min ();
kono
parents:
diff changeset
84 }
kono
parents:
diff changeset
85
kono
parents:
diff changeset
86 ASSERT_TRUE (h1->empty ());
kono
parents:
diff changeset
87
kono
parents:
diff changeset
88 delete h1;
kono
parents:
diff changeset
89 }
kono
parents:
diff changeset
90
kono
parents:
diff changeset
91 /* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
kono
parents:
diff changeset
92 of each key is equal to 3 * key + 10000. BUFFER is used as a storage
kono
parents:
diff changeset
93 of values and NODES points to inserted nodes. */
kono
parents:
diff changeset
94
kono
parents:
diff changeset
95 static int_heap_t *
kono
parents:
diff changeset
96 build_simple_heap (int *buffer, int_heap_node_t **nodes)
kono
parents:
diff changeset
97 {
kono
parents:
diff changeset
98 int_heap_t *h = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
99
kono
parents:
diff changeset
100 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
101 {
kono
parents:
diff changeset
102 buffer[i] = TEST_CALCULATE_VALUE (i);
kono
parents:
diff changeset
103 nodes[i] = h->insert (i, &buffer[i]);
kono
parents:
diff changeset
104 }
kono
parents:
diff changeset
105
kono
parents:
diff changeset
106 return h;
kono
parents:
diff changeset
107 }
kono
parents:
diff changeset
108
kono
parents:
diff changeset
109 /* Verify that fibonacci_heap::replace_key works. */
kono
parents:
diff changeset
110
kono
parents:
diff changeset
111 static void
kono
parents:
diff changeset
112 test_replace_key ()
kono
parents:
diff changeset
113 {
kono
parents:
diff changeset
114 int values[TEST_HEAP_N];
kono
parents:
diff changeset
115 int_heap_node_t *nodes[TEST_HEAP_N];
kono
parents:
diff changeset
116
kono
parents:
diff changeset
117 int_heap_t *heap = build_simple_heap (values, nodes);
kono
parents:
diff changeset
118
kono
parents:
diff changeset
119 int N = 10;
kono
parents:
diff changeset
120 for (unsigned i = 0; i < (unsigned)N; i++)
kono
parents:
diff changeset
121 heap->replace_key (nodes[i], 100 * 1000 + i);
kono
parents:
diff changeset
122
kono
parents:
diff changeset
123 ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
kono
parents:
diff changeset
124 ASSERT_EQ (N, heap->min_key ());
kono
parents:
diff changeset
125 ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
kono
parents:
diff changeset
126
kono
parents:
diff changeset
127 for (int i = 0; i < TEST_HEAP_N - 1; i++)
kono
parents:
diff changeset
128 heap->extract_min ();
kono
parents:
diff changeset
129
kono
parents:
diff changeset
130 ASSERT_EQ (1, heap->nodes ());
kono
parents:
diff changeset
131 ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
kono
parents:
diff changeset
132
kono
parents:
diff changeset
133 delete heap;
kono
parents:
diff changeset
134 }
kono
parents:
diff changeset
135
kono
parents:
diff changeset
136 /* Verify that heap can handle duplicate keys. */
kono
parents:
diff changeset
137
kono
parents:
diff changeset
138 static void
kono
parents:
diff changeset
139 test_duplicate_keys ()
kono
parents:
diff changeset
140 {
kono
parents:
diff changeset
141 int values[3 * TEST_HEAP_N];
kono
parents:
diff changeset
142 int_heap_t *heap = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
143
kono
parents:
diff changeset
144 for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
145 {
kono
parents:
diff changeset
146 values[i] = TEST_CALCULATE_VALUE (i);
kono
parents:
diff changeset
147 heap->insert (i / 3, &values[i]);
kono
parents:
diff changeset
148 }
kono
parents:
diff changeset
149
kono
parents:
diff changeset
150 ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
kono
parents:
diff changeset
151 ASSERT_EQ (0, heap->min_key ());
kono
parents:
diff changeset
152 ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
kono
parents:
diff changeset
153
kono
parents:
diff changeset
154 for (unsigned i = 0; i < 9; i++)
kono
parents:
diff changeset
155 heap->extract_min ();
kono
parents:
diff changeset
156
kono
parents:
diff changeset
157 for (unsigned i = 0; i < 3; i++)
kono
parents:
diff changeset
158 {
kono
parents:
diff changeset
159 ASSERT_EQ (3, heap->min_key ());
kono
parents:
diff changeset
160 heap->extract_min ();
kono
parents:
diff changeset
161 }
kono
parents:
diff changeset
162
kono
parents:
diff changeset
163 delete heap;
kono
parents:
diff changeset
164 }
kono
parents:
diff changeset
165
kono
parents:
diff changeset
166 /* Verify that heap can handle union. */
kono
parents:
diff changeset
167
kono
parents:
diff changeset
168 static void
kono
parents:
diff changeset
169 test_union ()
kono
parents:
diff changeset
170 {
kono
parents:
diff changeset
171 int value = 777;
kono
parents:
diff changeset
172
kono
parents:
diff changeset
173 int_heap_t *heap1 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
174 for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
175 heap1->insert (i, &value);
kono
parents:
diff changeset
176
kono
parents:
diff changeset
177 int_heap_t *heap2 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
178 for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
179 heap2->insert (i, &value);
kono
parents:
diff changeset
180
kono
parents:
diff changeset
181 int_heap_t *union_heap = heap1->union_with (heap2);
kono
parents:
diff changeset
182
kono
parents:
diff changeset
183 for (int i = 0; i < 3 * TEST_HEAP_N; i++)
kono
parents:
diff changeset
184 {
kono
parents:
diff changeset
185 ASSERT_EQ (i, union_heap->min_key ());
kono
parents:
diff changeset
186 union_heap->extract_min ();
kono
parents:
diff changeset
187 }
kono
parents:
diff changeset
188
kono
parents:
diff changeset
189 delete union_heap;
kono
parents:
diff changeset
190 }
kono
parents:
diff changeset
191
kono
parents:
diff changeset
192 /* Verify that heap can handle union with a heap having exactly the same
kono
parents:
diff changeset
193 keys. */
kono
parents:
diff changeset
194
kono
parents:
diff changeset
195 static void
kono
parents:
diff changeset
196 test_union_of_equal_heaps ()
kono
parents:
diff changeset
197 {
kono
parents:
diff changeset
198 int value = 777;
kono
parents:
diff changeset
199
kono
parents:
diff changeset
200 int_heap_t *heap1 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
201 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
202 heap1->insert (i, &value);
kono
parents:
diff changeset
203
kono
parents:
diff changeset
204 int_heap_t *heap2 = new int_heap_t (INT_MIN);
kono
parents:
diff changeset
205 for (unsigned i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
206 heap2->insert (i, &value);
kono
parents:
diff changeset
207
kono
parents:
diff changeset
208 int_heap_t *union_heap = heap1->union_with (heap2);
kono
parents:
diff changeset
209
kono
parents:
diff changeset
210 for (int i = 0; i < TEST_HEAP_N; i++)
kono
parents:
diff changeset
211 for (int j = 0; j < 2; j++)
kono
parents:
diff changeset
212 {
kono
parents:
diff changeset
213 ASSERT_EQ (i, union_heap->min_key ());
kono
parents:
diff changeset
214 union_heap->extract_min ();
kono
parents:
diff changeset
215 }
kono
parents:
diff changeset
216
kono
parents:
diff changeset
217 delete union_heap;
kono
parents:
diff changeset
218 }
kono
parents:
diff changeset
219
kono
parents:
diff changeset
220 /* Dummy struct for testing. */
kono
parents:
diff changeset
221
kono
parents:
diff changeset
222 struct heap_key
kono
parents:
diff changeset
223 {
kono
parents:
diff changeset
224 heap_key (int k): key (k)
kono
parents:
diff changeset
225 {
kono
parents:
diff changeset
226 }
kono
parents:
diff changeset
227
kono
parents:
diff changeset
228 int key;
kono
parents:
diff changeset
229
kono
parents:
diff changeset
230 bool operator< (const heap_key &other) const
kono
parents:
diff changeset
231 {
kono
parents:
diff changeset
232 return key > other.key;
kono
parents:
diff changeset
233 }
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 !(*this == other || *this < other);
kono
parents:
diff changeset
243 }
kono
parents:
diff changeset
244 };
kono
parents:
diff changeset
245
kono
parents:
diff changeset
246 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
kono
parents:
diff changeset
247
kono
parents:
diff changeset
248 /* Verify that heap can handle a struct as key type. */
kono
parents:
diff changeset
249
kono
parents:
diff changeset
250 static void
kono
parents:
diff changeset
251 test_struct_key ()
kono
parents:
diff changeset
252 {
kono
parents:
diff changeset
253 int value = 123456;
kono
parents:
diff changeset
254 class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
kono
parents:
diff changeset
255
kono
parents:
diff changeset
256 heap->insert (heap_key (1), &value);
kono
parents:
diff changeset
257 heap->insert (heap_key (10), &value);
kono
parents:
diff changeset
258 heap->insert (heap_key (100), &value);
kono
parents:
diff changeset
259 heap->insert (heap_key (1000), &value);
kono
parents:
diff changeset
260
kono
parents:
diff changeset
261 ASSERT_EQ (1000, heap->min_key ().key);
kono
parents:
diff changeset
262 ASSERT_EQ (4, heap->nodes ());
kono
parents:
diff changeset
263 heap->extract_min ();
kono
parents:
diff changeset
264 heap->extract_min ();
kono
parents:
diff changeset
265 ASSERT_EQ (10, heap->min_key ().key);
kono
parents:
diff changeset
266 heap->extract_min ();
kono
parents:
diff changeset
267 ASSERT_EQ (&value, heap->min ());
kono
parents:
diff changeset
268 heap->extract_min ();
kono
parents:
diff changeset
269 ASSERT_TRUE (heap->empty ());
kono
parents:
diff changeset
270
kono
parents:
diff changeset
271 delete heap;
kono
parents:
diff changeset
272 }
kono
parents:
diff changeset
273
kono
parents:
diff changeset
274 /* Run all of the selftests within this file. */
kono
parents:
diff changeset
275
kono
parents:
diff changeset
276 void
kono
parents:
diff changeset
277 fibonacci_heap_c_tests ()
kono
parents:
diff changeset
278 {
kono
parents:
diff changeset
279 test_empty_heap ();
kono
parents:
diff changeset
280 test_basic_heap_operations ();
kono
parents:
diff changeset
281 test_replace_key ();
kono
parents:
diff changeset
282 test_duplicate_keys ();
kono
parents:
diff changeset
283 test_union ();
kono
parents:
diff changeset
284 test_union_of_equal_heaps ();
kono
parents:
diff changeset
285 test_struct_key ();
kono
parents:
diff changeset
286 }
kono
parents:
diff changeset
287
kono
parents:
diff changeset
288 } // namespace selftest
kono
parents:
diff changeset
289
kono
parents:
diff changeset
290 #endif /* #if CHECKING_P */