1116743Ssam/* A Fibonacci heap datatype. 2186904Ssam Copyright (C) 1998-2020 Free Software Foundation, Inc. 3116743Ssam Contributed by Daniel Berlin (dan@cgsoftware.com). 4116743Ssam 5116743SsamThis file is part of GNU CC. 6116743Ssam 7116743SsamGNU CC is free software; you can redistribute it and/or modify it 8116743Ssamunder the terms of the GNU General Public License as published by 9116743Ssamthe Free Software Foundation; either version 2, or (at your option) 10116743Ssamany later version. 11116743Ssam 12116743SsamGNU CC is distributed in the hope that it will be useful, but 13116743SsamWITHOUT ANY WARRANTY; without even the implied warranty of 14116743SsamMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15116743SsamGeneral Public License for more details. 16116743Ssam 17116743SsamYou should have received a copy of the GNU General Public License 18116743Ssamalong with GNU CC; see the file COPYING. If not, write to 19116743Ssamthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20116743SsamBoston, MA 02110-1301, USA. */ 21116743Ssam 22116743Ssam#ifdef HAVE_CONFIG_H 23116743Ssam#include "config.h" 24116743Ssam#endif 25116743Ssam#ifdef HAVE_LIMITS_H 26116743Ssam#include <limits.h> 27116743Ssam#endif 28116743Ssam#ifdef HAVE_STDLIB_H 29116743Ssam#include <stdlib.h> 30116743Ssam#endif 31116743Ssam#ifdef HAVE_STRING_H 32116743Ssam#include <string.h> 33116743Ssam#endif 34116743Ssam#include "libiberty.h" 35116743Ssam#include "fibheap.h" 36116743Ssam 37116743Ssam 38227327Sadrian#define FIBHEAPKEY_MIN LONG_MIN 39227327Sadrian 40227327Sadrianstatic void fibheap_ins_root (fibheap_t, fibnode_t); 41227327Sadrianstatic void fibheap_rem_root (fibheap_t, fibnode_t); 42227327Sadrianstatic void fibheap_consolidate (fibheap_t); 43227327Sadrianstatic void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 44227327Sadrianstatic void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 45227327Sadrianstatic void fibheap_cascading_cut (fibheap_t, fibnode_t); 46233989Sadrianstatic fibnode_t fibheap_extr_min_node (fibheap_t); 47227327Sadrianstatic int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 48227327Sadrianstatic int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 49234090Sadrianstatic fibnode_t fibnode_new (void); 50234090Sadrianstatic void fibnode_insert_after (fibnode_t, fibnode_t); 51234090Sadrian#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 52234090Sadrianstatic fibnode_t fibnode_remove (fibnode_t); 53116743Ssam 54116743Ssam 55116743Ssam/* Create a new fibonacci heap. */ 56116743Ssamfibheap_t 57155492Ssamfibheap_new (void) 58138570Ssam{ 59116743Ssam return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 60116743Ssam} 61116743Ssam 62138570Ssam/* Create a new fibonacci heap node. */ 63116743Ssamstatic fibnode_t 64138570Ssamfibnode_new (void) 65116743Ssam{ 66116743Ssam fibnode_t node; 67116743Ssam 68116743Ssam node = (fibnode_t) xcalloc (1, sizeof *node); 69116743Ssam node->left = node; 70116743Ssam node->right = node; 71116743Ssam 72116743Ssam return node; 73116743Ssam} 74116743Ssam 75116743Ssamstatic inline int 76116743Ssamfibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 77116743Ssam{ 78116743Ssam if (a->key < b->key) 79116743Ssam return -1; 80116743Ssam if (a->key > b->key) 81116743Ssam return 1; 82116743Ssam return 0; 83116743Ssam} 84116743Ssam 85127779Ssamstatic inline int 86127779Ssamfibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 87170530Ssam{ 88170530Ssam struct fibnode a; 89116743Ssam 90116743Ssam a.key = key; 91116743Ssam a.data = data; 92116743Ssam 93116743Ssam return fibheap_compare (heap, &a, b); 94116743Ssam} 95138570Ssam 96116743Ssam/* Insert DATA, with priority KEY, into HEAP. */ 97218689Sadrianfibnode_t 98119147Ssamfibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 99127779Ssam{ 100138570Ssam fibnode_t node; 101138570Ssam 102119147Ssam /* Create the new node. */ 103138570Ssam node = fibnode_new (); 104138570Ssam 105161187Ssam /* Set the node's data. */ 106138570Ssam node->data = data; 107116743Ssam node->key = key; 108116743Ssam 109116743Ssam /* Insert it into the root list. */ 110116743Ssam fibheap_ins_root (heap, node); 111116743Ssam 112116743Ssam /* If their was no minimum, or this key is less than the min, 113116743Ssam it's the new min. */ 114138570Ssam if (heap->min == NULL || node->key < heap->min->key) 115138570Ssam heap->min = node; 116138570Ssam 117138570Ssam heap->nodes++; 118159894Ssam 119159894Ssam return node; 120160992Ssam} 121170530Ssam 122170530Ssam/* Return the data of the minimum node (if we know it). */ 123170530Ssamvoid * 124170530Ssamfibheap_min (fibheap_t heap) 125170530Ssam{ 126170530Ssam /* If there is no min, we can't easily return it. */ 127186904Ssam if (heap->min == NULL) 128186904Ssam return NULL; 129186904Ssam return heap->min->data; 130186904Ssam} 131186904Ssam 132186904Ssam/* Return the key of the minimum node (if we know it). */ 133188195Ssamfibheapkey_t 134188195Ssamfibheap_min_key (fibheap_t heap) 135188555Ssam{ 136211299Sadrian /* If there is no min, we can't easily return it. */ 137217684Sadrian if (heap->min == NULL) 138218378Sadrian return 0; 139221965Sadrian return heap->min->key; 140221965Sadrian} 141221965Sadrian 142221965Sadrian/* Union HEAPA and HEAPB into a new heap. */ 143221965Sadrianfibheap_t 144218689Sadrianfibheap_union (fibheap_t heapa, fibheap_t heapb) 145218924Sadrian{ 146221965Sadrian fibnode_t a_root, b_root, temp; 147220772Sadrian 148220782Sadrian /* If one of the heaps is empty, the union is just the other heap. */ 149221965Sadrian if ((a_root = heapa->root) == NULL) 150221965Sadrian { 151221965Sadrian free (heapa); 152226798Sadrian return heapb; 153226798Sadrian } 154226798Sadrian if ((b_root = heapb->root) == NULL) 155226798Sadrian { 156227868Sadrian free (heapb); 157226798Sadrian return heapa; 158226798Sadrian } 159226798Sadrian 160226798Sadrian /* Merge them to the next nodes on the opposite chain. */ 161227868Sadrian a_root->left->right = b_root; 162227868Sadrian b_root->left->right = a_root; 163232764Sadrian temp = a_root->left; 164232764Sadrian a_root->left = b_root->left; 165116743Ssam b_root->left = temp; 166116743Ssam heapa->nodes += heapb->nodes; 167116743Ssam 168188557Ssam /* And set the new minimum, if it's changed. */ 169236833Sadrian if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 170116743Ssam heapa->min = heapb->min; 171123044Ssam 172138570Ssam free (heapb); 173138570Ssam return heapa; 174138570Ssam} 175138570Ssam 176138570Ssam/* Extract the data of the minimum node from HEAP. */ 177138570Ssamvoid * 178138570Ssamfibheap_extract_min (fibheap_t heap) 179138570Ssam{ 180138570Ssam fibnode_t z; 181138570Ssam void *ret = NULL; 182123044Ssam 183123044Ssam /* If we don't have a min set, it means we have no nodes. */ 184123044Ssam if (heap->min != NULL) 185224245Sadrian { 186123044Ssam /* Otherwise, extract the min node, free the node, and return the 187119783Ssam node's data. */ 188119783Ssam z = fibheap_extr_min_node (heap); 189119783Ssam ret = z->data; 190237522Sadrian free (z); 191154140Ssam } 192119783Ssam 193119783Ssam return ret; 194123928Ssam} 195154140Ssam 196154140Ssam/* Replace both the KEY and the DATA associated with NODE. */ 197170530Ssamvoid * 198119783Ssamfibheap_replace_key_data (fibheap_t heap, fibnode_t node, 199119783Ssam fibheapkey_t key, void *data) 200237522Sadrian{ 201237522Sadrian void *odata; 202237522Sadrian fibheapkey_t okey; 203237522Sadrian fibnode_t y; 204237522Sadrian 205237522Sadrian /* If we wanted to, we could actually do a real increase by redeleting and 206237522Sadrian inserting. However, this would require O (log n) time. So just bail out 207237522Sadrian for now. */ 208237522Sadrian if (fibheap_comp_data (heap, key, data, node) > 0) 209237522Sadrian return NULL; 210237522Sadrian 211237522Sadrian odata = node->data; 212237522Sadrian okey = node->key; 213237522Sadrian node->data = data; 214237522Sadrian node->key = key; 215237522Sadrian y = node->parent; 216237522Sadrian 217237522Sadrian /* Short-circuit if the key is the same, as we then don't have to 218237522Sadrian do anything. Except if we're trying to force the new node to 219237522Sadrian be the new minimum for delete. */ 220237522Sadrian if (okey == key && okey != FIBHEAPKEY_MIN) 221237522Sadrian return odata; 222237522Sadrian 223237522Sadrian /* These two compares are specifically <= 0 to make sure that in the case 224237522Sadrian of equality, a node we replaced the data on, becomes the new min. This 225237522Sadrian is needed so that delete's call to extractmin gets the right node. */ 226237522Sadrian if (y != NULL && fibheap_compare (heap, node, y) <= 0) 227237522Sadrian { 228237522Sadrian fibheap_cut (heap, node, y); 229237522Sadrian fibheap_cascading_cut (heap, y); 230237522Sadrian } 231237522Sadrian 232237522Sadrian if (fibheap_compare (heap, node, heap->min) <= 0) 233237522Sadrian heap->min = node; 234237522Sadrian 235237522Sadrian return odata; 236237522Sadrian} 237237522Sadrian 238237522Sadrian/* Replace the DATA associated with NODE. */ 239237522Sadrianvoid * 240237522Sadrianfibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 241237522Sadrian{ 242237522Sadrian return fibheap_replace_key_data (heap, node, node->key, data); 243237522Sadrian} 244237522Sadrian 245237522Sadrian/* Replace the KEY associated with NODE. */ 246237522Sadrianfibheapkey_t 247237522Sadrianfibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 248237522Sadrian{ 249237522Sadrian int okey = node->key; 250237522Sadrian fibheap_replace_key_data (heap, node, key, node->data); 251237522Sadrian return okey; 252237522Sadrian} 253237522Sadrian 254237522Sadrian/* Delete NODE from HEAP. */ 255237522Sadrianvoid * 256119783Ssamfibheap_delete_node (fibheap_t heap, fibnode_t node) 257119783Ssam{ 258237522Sadrian void *ret = node->data; 259237522Sadrian 260237522Sadrian /* To perform delete, we just make it the min key, and extract. */ 261237522Sadrian fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 262237522Sadrian if (node != heap->min) 263237522Sadrian { 264237522Sadrian fprintf (stderr, "Can't force minimum on fibheap.\n"); 265237522Sadrian abort (); 266237522Sadrian } 267237522Sadrian fibheap_extract_min (heap); 268237522Sadrian 269237522Sadrian return ret; 270237522Sadrian} 271237522Sadrian 272237522Sadrian/* Delete HEAP. */ 273237522Sadrianvoid 274154140Ssamfibheap_delete (fibheap_t heap) 275154140Ssam{ 276119783Ssam while (heap->min != NULL) 277170530Ssam free (fibheap_extr_min_node (heap)); 278170530Ssam 279170530Ssam free (heap); 280170530Ssam} 281170530Ssam 282119783Ssam/* Determine if HEAP is empty. */ 283170530Ssamint 284170530Ssamfibheap_empty (fibheap_t heap) 285237522Sadrian{ 286237522Sadrian return heap->nodes == 0; 287237522Sadrian} 288237522Sadrian 289237522Sadrian/* Extract the minimum node of the heap. */ 290237522Sadrianstatic fibnode_t 291237522Sadrianfibheap_extr_min_node (fibheap_t heap) 292237522Sadrian{ 293237522Sadrian fibnode_t ret = heap->min; 294237522Sadrian fibnode_t x, y, orig; 295237522Sadrian 296237522Sadrian /* Attach the child list of the minimum node to the root list of the heap. 297237522Sadrian If there is no child list, we don't do squat. */ 298237522Sadrian for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 299237522Sadrian { 300237522Sadrian if (orig == NULL) 301237522Sadrian orig = x; 302237522Sadrian y = x->right; 303237522Sadrian x->parent = NULL; 304237522Sadrian fibheap_ins_root (heap, x); 305170530Ssam } 306119783Ssam 307119783Ssam /* Remove the old root. */ 308154140Ssam fibheap_rem_root (heap, ret); 309119783Ssam heap->nodes--; 310119783Ssam 311123928Ssam /* If we are left with no nodes, then the min is NULL. */ 312123928Ssam if (heap->nodes == 0) 313170530Ssam heap->min = NULL; 314119783Ssam else 315119783Ssam { 316119783Ssam /* Otherwise, consolidate to find new minimum, as well as do the reorg 317119783Ssam work that needs to be done. */ 318154140Ssam heap->min = ret->right; 319154140Ssam fibheap_consolidate (heap); 320119783Ssam } 321123928Ssam 322123928Ssam return ret; 323170530Ssam} 324170530Ssam 325170530Ssam/* Insert NODE into the root list of HEAP. */ 326170530Ssamstatic void 327170530Ssamfibheap_ins_root (fibheap_t heap, fibnode_t node) 328119783Ssam{ 329224245Sadrian /* If the heap is currently empty, the new node becomes the singleton 330224245Sadrian circular root list. */ 331224245Sadrian if (heap->root == NULL) 332224245Sadrian { 333224245Sadrian heap->root = node; 334224245Sadrian node->left = node; 335224245Sadrian node->right = node; 336224245Sadrian return; 337224245Sadrian } 338224245Sadrian 339224245Sadrian /* Otherwise, insert it in the circular root list between the root 340224245Sadrian and it's right node. */ 341224245Sadrian fibnode_insert_after (heap->root, node); 342224245Sadrian} 343224245Sadrian 344224245Sadrian/* Remove NODE from the rootlist of HEAP. */ 345224245Sadrianstatic void 346224245Sadrianfibheap_rem_root (fibheap_t heap, fibnode_t node) 347224245Sadrian{ 348224245Sadrian if (node->left == node) 349224245Sadrian heap->root = NULL; 350224245Sadrian else 351224245Sadrian heap->root = fibnode_remove (node); 352224245Sadrian} 353224245Sadrian 354224245Sadrian/* Consolidate the heap. */ 355224245Sadrianstatic void 356224245Sadrianfibheap_consolidate (fibheap_t heap) 357224245Sadrian{ 358224245Sadrian fibnode_t a[1 + 8 * sizeof (long)]; 359116743Ssam 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. */ 402static void 403fibheap_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. */ 416static void 417fibheap_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 426static void 427fibheap_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 446static void 447fibnode_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 465static fibnode_t 466fibnode_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