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