Mercurial > hg > CbC > CbC_gcc

comparison gcc/fibonacci_heap.c @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* Fibonacci heap for GNU compiler. 1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 2016-2018 Free Software Foundation, Inc. 2 Copyright (C) 2016-2020 Free Software Foundation, Inc.
3 Contributed by Martin Liska <mliska@suse.cz> 3 Contributed by Martin Liska <mliska@suse.cz>
4 4
5 This file is part of GCC. 5 This file is part of GCC.
6 6
7 GCC is free software; you can redistribute it and/or modify it under 7 GCC is free software; you can redistribute it and/or modify it under
19 <http://www.gnu.org/licenses/>. */ 19 <http://www.gnu.org/licenses/>. */
20 20
21 #include "config.h" 21 #include "config.h"
22 #include "system.h" 22 #include "system.h"
23 #include "coretypes.h" 23 #include "coretypes.h"
24 #include "alloc-pool.h"
24 #include "fibonacci_heap.h" 25 #include "fibonacci_heap.h"
25 #include "selftest.h" 26 #include "selftest.h"
26 27
27 #if CHECKING_P 28 #if CHECKING_P
28 29
36 typedef fibonacci_heap <int, int> int_heap_t; 37 typedef fibonacci_heap <int, int> int_heap_t;
37 38
38 static void 39 static void
39 test_empty_heap () 40 test_empty_heap ()
40 { 41 {
41 int_heap_t *h1 = new int_heap_t (INT_MIN); 42 pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
43 int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);
42 44
43 ASSERT_TRUE (h1->empty ()); 45 ASSERT_TRUE (h1->empty ());
44 ASSERT_EQ (0, h1->nodes ()); 46 ASSERT_EQ (0, h1->nodes ());
45 ASSERT_EQ (NULL, h1->min ()); 47 ASSERT_EQ (NULL, h1->min ());
46 48
47 int_heap_t *h2 = new int_heap_t (INT_MIN); 49 int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);
48 50
49 int_heap_t *r = h1->union_with (h2); 51 int_heap_t *r = h1->union_with (h2);
50 ASSERT_TRUE (r->empty ()); 52 ASSERT_TRUE (r->empty ());
51 ASSERT_EQ (0, r->nodes ()); 53 ASSERT_EQ (0, r->nodes ());
52 ASSERT_EQ (NULL, r->min ()); 54 ASSERT_EQ (NULL, r->min ());
167 169
168 static void 170 static void
169 test_union () 171 test_union ()
170 { 172 {
171 int value = 777; 173 int value = 777;
172 174 pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
173 int_heap_t *heap1 = new int_heap_t (INT_MIN); 175
176 int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
174 for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++) 177 for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
175 heap1->insert (i, &value); 178 heap1->insert (i, &value);
176 179
177 int_heap_t *heap2 = new int_heap_t (INT_MIN); 180 int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
178 for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++) 181 for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
179 heap2->insert (i, &value); 182 heap2->insert (i, &value);
180 183
181 int_heap_t *union_heap = heap1->union_with (heap2); 184 int_heap_t *union_heap = heap1->union_with (heap2);
182 185
194 197
195 static void 198 static void
196 test_union_of_equal_heaps () 199 test_union_of_equal_heaps ()
197 { 200 {
198 int value = 777; 201 int value = 777;
199 202 pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
200 int_heap_t *heap1 = new int_heap_t (INT_MIN); 203
204 int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
201 for (unsigned i = 0; i < TEST_HEAP_N; i++) 205 for (unsigned i = 0; i < TEST_HEAP_N; i++)
202 heap1->insert (i, &value); 206 heap1->insert (i, &value);
203 207
204 int_heap_t *heap2 = new int_heap_t (INT_MIN); 208 int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
205 for (unsigned i = 0; i < TEST_HEAP_N; i++) 209 for (unsigned i = 0; i < TEST_HEAP_N; i++)
206 heap2->insert (i, &value); 210 heap2->insert (i, &value);
207 211
208 int_heap_t *union_heap = heap1->union_with (heap2); 212 int_heap_t *union_heap = heap1->union_with (heap2);
209 213
217 delete union_heap; 221 delete union_heap;
218 } 222 }
219 223
220 /* Dummy struct for testing. */ 224 /* Dummy struct for testing. */
221 225
222 struct heap_key 226 class heap_key
223 { 227 {
228 public:
224 heap_key (int k): key (k) 229 heap_key (int k): key (k)
225 { 230 {
226 } 231 }
227 232
228 int key; 233 int key;