1 /* A Fibonacci heap datatype. 2 Copyright (C) 1998-2018 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin (dan@cgsoftware.com). 4 5 This file is part of GNU CC. 6 7 GNU CC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2, or (at your option) 10 any later version. 11 12 GNU CC is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GNU CC; see the file COPYING. If not, write to 19 the Free Software Foundation, 51 Franklin Street - Fifth Floor, 20 Boston, MA 02110-1301, USA. */ 21 22 #ifdef HAVE_CONFIG_H 23 #include "config.h" 24 #endif 25 #ifdef HAVE_LIMITS_H 26 #include <limits.h> 27 #endif 28 #ifdef HAVE_STDLIB_H 29 #include <stdlib.h> 30 #endif 31 #ifdef HAVE_STRING_H 32 #include <string.h> 33 #endif 34 #include "libiberty.h" 35 #include "fibheap.h" 36 37 38 #define FIBHEAPKEY_MIN LONG_MIN 39 40 static void fibheap_ins_root (fibheap_t, fibnode_t); 41 static void fibheap_rem_root (fibheap_t, fibnode_t); 42 static void fibheap_consolidate (fibheap_t); 43 static void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 44 static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 45 static void fibheap_cascading_cut (fibheap_t, fibnode_t); 46 static fibnode_t fibheap_extr_min_node (fibheap_t); 47 static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 48 static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 49 static fibnode_t fibnode_new (void); 50 static void fibnode_insert_after (fibnode_t, fibnode_t); 51 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 52 static fibnode_t fibnode_remove (fibnode_t); 53 54 55 /* Create a new fibonacci heap. */ 56 fibheap_t 57 fibheap_new (void) 58 { 59 return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 60 } 61 62 /* Create a new fibonacci heap node. */ 63 static fibnode_t 64 fibnode_new (void) 65 { 66 fibnode_t node; 67 68 node = (fibnode_t) xcalloc (1, sizeof *node); 69 node->left = node; 70 node->right = node; 71 72 return node; 73 } 74 75 static inline int 76 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 77 { 78 if (a->key < b->key) 79 return -1; 80 if (a->key > b->key) 81 return 1; 82 return 0; 83 } 84 85 static inline int 86 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 87 { 88 struct fibnode a; 89 90 a.key = key; 91 a.data = data; 92 93 return fibheap_compare (heap, &a, b); 94 } 95 96 /* Insert DATA, with priority KEY, into HEAP. */ 97 fibnode_t 98 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 99 { 100 fibnode_t node; 101 102 /* Create the new node. */ 103 node = fibnode_new (); 104 105 /* Set the node's data. */ 106 node->data = data; 107 node->key = key; 108 109 /* Insert it into the root list. */ 110 fibheap_ins_root (heap, node); 111 112 /* If their was no minimum, or this key is less than the min, 113 it's the new min. */ 114 if (heap->min == NULL || node->key < heap->min->key) 115 heap->min = node; 116 117 heap->nodes++; 118 119 return node; 120 } 121 122 /* Return the data of the minimum node (if we know it). */ 123 void * 124 fibheap_min (fibheap_t heap) 125 { 126 /* If there is no min, we can't easily return it. */ 127 if (heap->min == NULL) 128 return NULL; 129 return heap->min->data; 130 } 131 132 /* Return the key of the minimum node (if we know it). */ 133 fibheapkey_t 134 fibheap_min_key (fibheap_t heap) 135 { 136 /* If there is no min, we can't easily return it. */ 137 if (heap->min == NULL) 138 return 0; 139 return heap->min->key; 140 } 141 142 /* Union HEAPA and HEAPB into a new heap. */ 143 fibheap_t 144 fibheap_union (fibheap_t heapa, fibheap_t heapb) 145 { 146 fibnode_t a_root, b_root, temp; 147 148 /* If one of the heaps is empty, the union is just the other heap. */ 149 if ((a_root = heapa->root) == NULL) 150 { 151 free (heapa); 152 return heapb; 153 } 154 if ((b_root = heapb->root) == NULL) 155 { 156 free (heapb); 157 return heapa; 158 } 159 160 /* Merge them to the next nodes on the opposite chain. */ 161 a_root->left->right = b_root; 162 b_root->left->right = a_root; 163 temp = a_root->left; 164 a_root->left = b_root->left; 165 b_root->left = temp; 166 heapa->nodes += heapb->nodes; 167 168 /* And set the new minimum, if it's changed. */ 169 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 170 heapa->min = heapb->min; 171 172 free (heapb); 173 return heapa; 174 } 175 176 /* Extract the data of the minimum node from HEAP. */ 177 void * 178 fibheap_extract_min (fibheap_t heap) 179 { 180 fibnode_t z; 181 void *ret = NULL; 182 183 /* If we don't have a min set, it means we have no nodes. */ 184 if (heap->min != NULL) 185 { 186 /* Otherwise, extract the min node, free the node, and return the 187 node's data. */ 188 z = fibheap_extr_min_node (heap); 189 ret = z->data; 190 free (z); 191 } 192 193 return ret; 194 } 195 196 /* Replace both the KEY and the DATA associated with NODE. */ 197 void * 198 fibheap_replace_key_data (fibheap_t heap, fibnode_t node, 199 fibheapkey_t key, void *data) 200 { 201 void *odata; 202 fibheapkey_t okey; 203 fibnode_t y; 204 205 /* If we wanted to, we could actually do a real increase by redeleting and 206 inserting. However, this would require O (log n) time. So just bail out 207 for now. */ 208 if (fibheap_comp_data (heap, key, data, node) > 0) 209 return NULL; 210 211 odata = node->data; 212 okey = node->key; 213 node->data = data; 214 node->key = key; 215 y = node->parent; 216 217 /* Short-circuit if the key is the same, as we then don't have to 218 do anything. Except if we're trying to force the new node to 219 be the new minimum for delete. */ 220 if (okey == key && okey != FIBHEAPKEY_MIN) 221 return odata; 222 223 /* These two compares are specifically <= 0 to make sure that in the case 224 of equality, a node we replaced the data on, becomes the new min. This 225 is needed so that delete's call to extractmin gets the right node. */ 226 if (y != NULL && fibheap_compare (heap, node, y) <= 0) 227 { 228 fibheap_cut (heap, node, y); 229 fibheap_cascading_cut (heap, y); 230 } 231 232 if (fibheap_compare (heap, node, heap->min) <= 0) 233 heap->min = node; 234 235 return odata; 236 } 237 238 /* Replace the DATA associated with NODE. */ 239 void * 240 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 241 { 242 return fibheap_replace_key_data (heap, node, node->key, data); 243 } 244 245 /* Replace the KEY associated with NODE. */ 246 fibheapkey_t 247 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 248 { 249 int okey = node->key; 250 fibheap_replace_key_data (heap, node, key, node->data); 251 return okey; 252 } 253 254 /* Delete NODE from HEAP. */ 255 void * 256 fibheap_delete_node (fibheap_t heap, fibnode_t node) 257 { 258 void *ret = node->data; 259 260 /* To perform delete, we just make it the min key, and extract. */ 261 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 262 if (node != heap->min) 263 { 264 fprintf (stderr, "Can't force minimum on fibheap.\n"); 265 abort (); 266 } 267 fibheap_extract_min (heap); 268 269 return ret; 270 } 271 272 /* Delete HEAP. */ 273 void 274 fibheap_delete (fibheap_t heap) 275 { 276 while (heap->min != NULL) 277 free (fibheap_extr_min_node (heap)); 278 279 free (heap); 280 } 281 282 /* Determine if HEAP is empty. */ 283 int 284 fibheap_empty (fibheap_t heap) 285 { 286 return heap->nodes == 0; 287 } 288 289 /* Extract the minimum node of the heap. */ 290 static fibnode_t 291 fibheap_extr_min_node (fibheap_t heap) 292 { 293 fibnode_t ret = heap->min; 294 fibnode_t x, y, orig; 295 296 /* Attach the child list of the minimum node to the root list of the heap. 297 If there is no child list, we don't do squat. */ 298 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 299 { 300 if (orig == NULL) 301 orig = x; 302 y = x->right; 303 x->parent = NULL; 304 fibheap_ins_root (heap, x); 305 } 306 307 /* Remove the old root. */ 308 fibheap_rem_root (heap, ret); 309 heap->nodes--; 310 311 /* If we are left with no nodes, then the min is NULL. */ 312 if (heap->nodes == 0) 313 heap->min = NULL; 314 else 315 { 316 /* Otherwise, consolidate to find new minimum, as well as do the reorg 317 work that needs to be done. */ 318 heap->min = ret->right; 319 fibheap_consolidate (heap); 320 } 321 322 return ret; 323 } 324 325 /* Insert NODE into the root list of HEAP. */ 326 static void 327 fibheap_ins_root (fibheap_t heap, fibnode_t node) 328 { 329 /* If the heap is currently empty, the new node becomes the singleton 330 circular root list. */ 331 if (heap->root == NULL) 332 { 333 heap->root = node; 334 node->left = node; 335 node->right = node; 336 return; 337 } 338 339 /* Otherwise, insert it in the circular root list between the root 340 and it's right node. */ 341 fibnode_insert_after (heap->root, node); 342 } 343 344 /* Remove NODE from the rootlist of HEAP. */ 345 static void 346 fibheap_rem_root (fibheap_t heap, fibnode_t node) 347 { 348 if (node->left == node) 349 heap->root = NULL; 350 else 351 heap->root = fibnode_remove (node); 352 } 353 354 /* Consolidate the heap. */ 355 static void 356 fibheap_consolidate (fibheap_t heap) 357 { 358 fibnode_t a[1 + 8 * sizeof (long)]; 359 fibnode_t w; 360 fibnode_t y; 361 fibnode_t x; 362 int i; 363 int d; 364 int D; 365 366 D = 1 + 8 * sizeof (long); 367 368 memset (a, 0, sizeof (fibnode_t) * D); 369 370 while ((w = heap->root) != NULL) 371 { 372 x = w; 373 fibheap_rem_root (heap, w); 374 d = x->degree; 375 while (a[d] != NULL) 376 { 377 y = a[d]; 378 if (fibheap_compare (heap, x, y) > 0) 379 { 380 fibnode_t temp; 381 temp = x; 382 x = y; 383 y = temp; 384 } 385 fibheap_link (heap, y, x); 386 a[d] = NULL; 387 d++; 388 } 389 a[d] = x; 390 } 391 heap->min = NULL; 392 for (i = 0; i < D; i++) 393 if (a[i] != NULL) 394 { 395 fibheap_ins_root (heap, a[i]); 396 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 397 heap->min = a[i]; 398 } 399 } 400 401 /* Make NODE a child of PARENT. */ 402 static void 403 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, 404 fibnode_t node, fibnode_t parent) 405 { 406 if (parent->child == NULL) 407 parent->child = node; 408 else 409 fibnode_insert_before (parent->child, node); 410 node->parent = parent; 411 parent->degree++; 412 node->mark = 0; 413 } 414 415 /* Remove NODE from PARENT's child list. */ 416 static void 417 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) 418 { 419 fibnode_remove (node); 420 parent->degree--; 421 fibheap_ins_root (heap, node); 422 node->parent = NULL; 423 node->mark = 0; 424 } 425 426 static void 427 fibheap_cascading_cut (fibheap_t heap, fibnode_t y) 428 { 429 fibnode_t z; 430 431 while ((z = y->parent) != NULL) 432 { 433 if (y->mark == 0) 434 { 435 y->mark = 1; 436 return; 437 } 438 else 439 { 440 fibheap_cut (heap, y, z); 441 y = z; 442 } 443 } 444 } 445 446 static void 447 fibnode_insert_after (fibnode_t a, fibnode_t b) 448 { 449 if (a == a->right) 450 { 451 a->right = b; 452 a->left = b; 453 b->right = a; 454 b->left = a; 455 } 456 else 457 { 458 b->right = a->right; 459 a->right->left = b; 460 a->right = b; 461 b->left = a; 462 } 463 } 464 465 static fibnode_t 466 fibnode_remove (fibnode_t node) 467 { 468 fibnode_t ret; 469 470 if (node == node->left) 471 ret = NULL; 472 else 473 ret = node->left; 474 475 if (node->parent != NULL && node->parent->child == node) 476 node->parent->child = ret; 477 478 node->right->left = node->left; 479 node->left->right = node->right; 480 481 node->parent = NULL; 482 node->left = node; 483 node->right = node; 484 485 return ret; 486 } 487