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