1 /* Fibonacci heap for GNU compiler. 2 Copyright (C) 2016-2018 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 "fibonacci_heap.h" 25 #include "selftest.h" 26 27 #if CHECKING_P 28 29 namespace selftest { 30 31 /* Selftests. */ 32 33 /* Verify that operations with empty heap work. */ 34 35 typedef fibonacci_node <int, int> int_heap_node_t; 36 typedef fibonacci_heap <int, int> int_heap_t; 37 38 static void 39 test_empty_heap () 40 { 41 int_heap_t *h1 = new int_heap_t (INT_MIN); 42 43 ASSERT_TRUE (h1->empty ()); 44 ASSERT_EQ (0, h1->nodes ()); 45 ASSERT_EQ (NULL, h1->min ()); 46 47 int_heap_t *h2 = new int_heap_t (INT_MIN); 48 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 ()); 53 54 delete r; 55 } 56 57 #define TEST_HEAP_N 100 58 #define TEST_CALCULATE_VALUE(i) ((3 * i) + 10000) 59 60 /* Verify heap basic operations. */ 61 62 static void 63 test_basic_heap_operations () 64 { 65 int values[TEST_HEAP_N]; 66 int_heap_t *h1 = new int_heap_t (INT_MIN); 67 68 for (unsigned i = 0; i < TEST_HEAP_N; i++) 69 { 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 ()); 75 } 76 77 for (unsigned i = 0; i < TEST_HEAP_N; i++) 78 { 79 ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ()); 80 ASSERT_EQ ((int)i, h1->min_key ()); 81 ASSERT_EQ (values[i], *h1->min ()); 82 83 h1->extract_min (); 84 } 85 86 ASSERT_TRUE (h1->empty ()); 87 88 delete h1; 89 } 90 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. */ 94 95 static int_heap_t * 96 build_simple_heap (int *buffer, int_heap_node_t **nodes) 97 { 98 int_heap_t *h = new int_heap_t (INT_MIN); 99 100 for (unsigned i = 0; i < TEST_HEAP_N; i++) 101 { 102 buffer[i] = TEST_CALCULATE_VALUE (i); 103 nodes[i] = h->insert (i, &buffer[i]); 104 } 105 106 return h; 107 } 108 109 /* Verify that fibonacci_heap::replace_key works. */ 110 111 static void 112 test_replace_key () 113 { 114 int values[TEST_HEAP_N]; 115 int_heap_node_t *nodes[TEST_HEAP_N]; 116 117 int_heap_t *heap = build_simple_heap (values, nodes); 118 119 int N = 10; 120 for (unsigned i = 0; i < (unsigned)N; i++) 121 heap->replace_key (nodes[i], 100 * 1000 + i); 122 123 ASSERT_EQ (TEST_HEAP_N, heap->nodes ()); 124 ASSERT_EQ (N, heap->min_key ()); 125 ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ()); 126 127 for (int i = 0; i < TEST_HEAP_N - 1; i++) 128 heap->extract_min (); 129 130 ASSERT_EQ (1, heap->nodes ()); 131 ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ()); 132 133 delete heap; 134 } 135 136 /* Verify that heap can handle duplicate keys. */ 137 138 static void 139 test_duplicate_keys () 140 { 141 int values[3 * TEST_HEAP_N]; 142 int_heap_t *heap = new int_heap_t (INT_MIN); 143 144 for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++) 145 { 146 values[i] = TEST_CALCULATE_VALUE (i); 147 heap->insert (i / 3, &values[i]); 148 } 149 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 ()); 153 154 for (unsigned i = 0; i < 9; i++) 155 heap->extract_min (); 156 157 for (unsigned i = 0; i < 3; i++) 158 { 159 ASSERT_EQ (3, heap->min_key ()); 160 heap->extract_min (); 161 } 162 163 delete heap; 164 } 165 166 /* Verify that heap can handle union. */ 167 168 static void 169 test_union () 170 { 171 int value = 777; 172 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); 176 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); 180 181 int_heap_t *union_heap = heap1->union_with (heap2); 182 183 for (int i = 0; i < 3 * TEST_HEAP_N; i++) 184 { 185 ASSERT_EQ (i, union_heap->min_key ()); 186 union_heap->extract_min (); 187 } 188 189 delete union_heap; 190 } 191 192 /* Verify that heap can handle union with a heap having exactly the same 193 keys. */ 194 195 static void 196 test_union_of_equal_heaps () 197 { 198 int value = 777; 199 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); 203 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); 207 208 int_heap_t *union_heap = heap1->union_with (heap2); 209 210 for (int i = 0; i < TEST_HEAP_N; i++) 211 for (int j = 0; j < 2; j++) 212 { 213 ASSERT_EQ (i, union_heap->min_key ()); 214 union_heap->extract_min (); 215 } 216 217 delete union_heap; 218 } 219 220 /* Dummy struct for testing. */ 221 222 struct heap_key 223 { 224 heap_key (int k): key (k) 225 { 226 } 227 228 int key; 229 230 bool operator< (const heap_key &other) const 231 { 232 return key > other.key; 233 } 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 !(*this == other || *this < other); 243 } 244 }; 245 246 typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t; 247 248 /* Verify that heap can handle a struct as key type. */ 249 250 static void 251 test_struct_key () 252 { 253 int value = 123456; 254 class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN); 255 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); 260 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 ()); 270 271 delete heap; 272 } 273 274 /* Run all of the selftests within this file. */ 275 276 void 277 fibonacci_heap_c_tests () 278 { 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 (); 286 } 287 288 } // namespace selftest 289 290 #endif /* #if CHECKING_P */ 291