* tree-loop-distribution.c (struct partition): New field recording
[official-gcc.git] / gcc / fibonacci_heap.c
blob6f8dda2fd4ef96d5e565d4bf116d5b4d04ccb63e
1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 2016-2017 Free Software Foundation, Inc.
3 Contributed by Martin Liska <mliska@suse.cz>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "fibonacci_heap.h"
25 #include "selftest.h"
27 #if CHECKING_P
29 namespace selftest {
31 /* Selftests. */
33 /* Verify that operations with empty heap work. */
35 typedef fibonacci_node <int, int> int_heap_node_t;
36 typedef fibonacci_heap <int, int> int_heap_t;
38 static void
39 test_empty_heap ()
41 int_heap_t *h1 = new int_heap_t (INT_MIN);
43 ASSERT_TRUE (h1->empty ());
44 ASSERT_EQ (0, h1->nodes ());
45 ASSERT_EQ (NULL, h1->min ());
47 int_heap_t *h2 = new int_heap_t (INT_MIN);
49 int_heap_t *r = h1->union_with (h2);
50 ASSERT_TRUE (r->empty ());
51 ASSERT_EQ (0, r->nodes ());
52 ASSERT_EQ (NULL, r->min ());
54 delete r;
57 #define TEST_HEAP_N 100
58 #define TEST_CALCULATE_VALUE(i) ((3 * i) + 10000)
60 /* Verify heap basic operations. */
62 static void
63 test_basic_heap_operations ()
65 int values[TEST_HEAP_N];
66 int_heap_t *h1 = new int_heap_t (INT_MIN);
68 for (unsigned i = 0; i < TEST_HEAP_N; i++)
70 values[i] = TEST_CALCULATE_VALUE (i);
71 ASSERT_EQ (i, h1->nodes ());
72 h1->insert (i, &values[i]);
73 ASSERT_EQ (0, h1->min_key ());
74 ASSERT_EQ (values[0], *h1->min ());
77 for (unsigned i = 0; i < TEST_HEAP_N; i++)
79 ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
80 ASSERT_EQ ((int)i, h1->min_key ());
81 ASSERT_EQ (values[i], *h1->min ());
83 h1->extract_min ();
86 ASSERT_TRUE (h1->empty ());
88 delete h1;
91 /* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
92 of each key is equal to 3 * key + 10000. BUFFER is used as a storage
93 of values and NODES points to inserted nodes. */
95 static int_heap_t *
96 build_simple_heap (int *buffer, int_heap_node_t **nodes)
98 int_heap_t *h = new int_heap_t (INT_MIN);
100 for (unsigned i = 0; i < TEST_HEAP_N; i++)
102 buffer[i] = TEST_CALCULATE_VALUE (i);
103 nodes[i] = h->insert (i, &buffer[i]);
106 return h;
109 /* Verify that fibonacci_heap::replace_key works. */
111 static void
112 test_replace_key ()
114 int values[TEST_HEAP_N];
115 int_heap_node_t *nodes[TEST_HEAP_N];
117 int_heap_t *heap = build_simple_heap (values, nodes);
119 int N = 10;
120 for (unsigned i = 0; i < (unsigned)N; i++)
121 heap->replace_key (nodes[i], 100 * 1000 + i);
123 ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
124 ASSERT_EQ (N, heap->min_key ());
125 ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());
127 for (int i = 0; i < TEST_HEAP_N - 1; i++)
128 heap->extract_min ();
130 ASSERT_EQ (1, heap->nodes ());
131 ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());
133 delete heap;
136 /* Verify that heap can handle duplicate keys. */
138 static void
139 test_duplicate_keys ()
141 int values[3 * TEST_HEAP_N];
142 int_heap_t *heap = new int_heap_t (INT_MIN);
144 for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
146 values[i] = TEST_CALCULATE_VALUE (i);
147 heap->insert (i / 3, &values[i]);
150 ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
151 ASSERT_EQ (0, heap->min_key ());
152 ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());
154 for (unsigned i = 0; i < 9; i++)
155 heap->extract_min ();
157 for (unsigned i = 0; i < 3; i++)
159 ASSERT_EQ (3, heap->min_key ());
160 heap->extract_min ();
163 delete heap;
166 /* Verify that heap can handle union. */
168 static void
169 test_union ()
171 int value = 777;
173 int_heap_t *heap1 = new int_heap_t (INT_MIN);
174 for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
175 heap1->insert (i, &value);
177 int_heap_t *heap2 = new int_heap_t (INT_MIN);
178 for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
179 heap2->insert (i, &value);
181 int_heap_t *union_heap = heap1->union_with (heap2);
183 for (int i = 0; i < 3 * TEST_HEAP_N; i++)
185 ASSERT_EQ (i, union_heap->min_key ());
186 union_heap->extract_min ();
189 delete union_heap;
192 /* Verify that heap can handle union with a heap having exactly the same
193 keys. */
195 static void
196 test_union_of_equal_heaps ()
198 int value = 777;
200 int_heap_t *heap1 = new int_heap_t (INT_MIN);
201 for (unsigned i = 0; i < TEST_HEAP_N; i++)
202 heap1->insert (i, &value);
204 int_heap_t *heap2 = new int_heap_t (INT_MIN);
205 for (unsigned i = 0; i < TEST_HEAP_N; i++)
206 heap2->insert (i, &value);
208 int_heap_t *union_heap = heap1->union_with (heap2);
210 for (int i = 0; i < TEST_HEAP_N; i++)
211 for (int j = 0; j < 2; j++)
213 ASSERT_EQ (i, union_heap->min_key ());
214 union_heap->extract_min ();
217 delete union_heap;
220 /* Dummy struct for testing. */
222 struct heap_key
224 heap_key (int k): key (k)
228 int key;
230 bool operator< (const heap_key &other) const
232 return key > other.key;
235 bool operator== (const heap_key &other) const
237 return key == other.key;
240 bool operator> (const heap_key &other) const
242 return !(*this == other || *this < other);
246 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;
248 /* Verify that heap can handle a struct as key type. */
250 static void
251 test_struct_key ()
253 int value = 123456;
254 class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);
256 heap->insert (heap_key (1), &value);
257 heap->insert (heap_key (10), &value);
258 heap->insert (heap_key (100), &value);
259 heap->insert (heap_key (1000), &value);
261 ASSERT_EQ (1000, heap->min_key ().key);
262 ASSERT_EQ (4, heap->nodes ());
263 heap->extract_min ();
264 heap->extract_min ();
265 ASSERT_EQ (10, heap->min_key ().key);
266 heap->extract_min ();
267 ASSERT_EQ (&value, heap->min ());
268 heap->extract_min ();
269 ASSERT_TRUE (heap->empty ());
271 delete heap;
274 /* Run all of the selftests within this file. */
276 void
277 fibonacci_heap_c_tests ()
279 test_empty_heap ();
280 test_basic_heap_operations ();
281 test_replace_key ();
282 test_duplicate_keys ();
283 test_union ();
284 test_union_of_equal_heaps ();
285 test_struct_key ();
288 } // namespace selftest
290 #endif /* #if CHECKING_P */