1 /* Fibonacci heap for GNU compiler. 2 Copyright (C) 2016-2020 Free Software Foundation, Inc. 3 Contributed by Martin Liska <mliska@suse.cz> 4 5 This file is part of GCC. 6 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. 11 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. 16 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/>. */ 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 30 namespace selftest { 31 32 /* Selftests. */ 33 34 /* Verify that operations with empty heap work. */ 35 36 typedef fibonacci_node <int, int> int_heap_node_t; 37 typedef fibonacci_heap <int, int> int_heap_t; 38 39 static void 40 test_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 64 static void 65 test_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 97 static int_heap_t * 98 build_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 113 static void 114 test_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 140 static void 141 test_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 170 static void 171 test_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 198 static void 199 test_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 226 class heap_key 227 { 228 public: 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 251 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t; 252 253 /* Verify that heap can handle a struct as key type. */ 254 255 static void 256 test_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 281 void 282 fibonacci_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