1169695Skan/* A Fibonacci heap datatype. 2169695Skan Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 3169695Skan Contributed by Daniel Berlin (dan@cgsoftware.com). 4169695Skan 5169695SkanThis file is part of GNU CC. 6169695Skan 7169695SkanGNU CC is free software; you can redistribute it and/or modify it 8169695Skanunder the terms of the GNU General Public License as published by 9169695Skanthe Free Software Foundation; either version 2, or (at your option) 10169695Skanany later version. 11169695Skan 12169695SkanGNU CC is distributed in the hope that it will be useful, but 13169695SkanWITHOUT ANY WARRANTY; without even the implied warranty of 14169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15169695SkanGeneral Public License for more details. 16169695Skan 17169695SkanYou should have received a copy of the GNU General Public License 18169695Skanalong with GNU CC; see the file COPYING. If not, write to 19169695Skanthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20169695SkanBoston, MA 02110-1301, USA. */ 21169695Skan 22169695Skan#ifdef HAVE_CONFIG_H 23169695Skan#include "config.h" 24169695Skan#endif 25169695Skan#ifdef HAVE_LIMITS_H 26169695Skan#include <limits.h> 27169695Skan#endif 28169695Skan#ifdef HAVE_STDLIB_H 29169695Skan#include <stdlib.h> 30169695Skan#endif 31169695Skan#ifdef HAVE_STRING_H 32169695Skan#include <string.h> 33169695Skan#endif 34169695Skan#include "libiberty.h" 35169695Skan#include "fibheap.h" 36169695Skan 37169695Skan 38169695Skan#define FIBHEAPKEY_MIN LONG_MIN 39169695Skan 40169695Skanstatic void fibheap_ins_root (fibheap_t, fibnode_t); 41169695Skanstatic void fibheap_rem_root (fibheap_t, fibnode_t); 42169695Skanstatic void fibheap_consolidate (fibheap_t); 43169695Skanstatic void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 44169695Skanstatic void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 45169695Skanstatic void fibheap_cascading_cut (fibheap_t, fibnode_t); 46169695Skanstatic fibnode_t fibheap_extr_min_node (fibheap_t); 47169695Skanstatic int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 48169695Skanstatic int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 49169695Skanstatic fibnode_t fibnode_new (void); 50169695Skanstatic void fibnode_insert_after (fibnode_t, fibnode_t); 51169695Skan#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 52169695Skanstatic fibnode_t fibnode_remove (fibnode_t); 53169695Skan 54169695Skan 55169695Skan/* Create a new fibonacci heap. */ 56169695Skanfibheap_t 57169695Skanfibheap_new (void) 58169695Skan{ 59169695Skan return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 60169695Skan} 61169695Skan 62169695Skan/* Create a new fibonacci heap node. */ 63169695Skanstatic fibnode_t 64169695Skanfibnode_new (void) 65169695Skan{ 66169695Skan fibnode_t node; 67169695Skan 68169695Skan node = (fibnode_t) xcalloc (1, sizeof *node); 69169695Skan node->left = node; 70169695Skan node->right = node; 71169695Skan 72169695Skan return node; 73169695Skan} 74169695Skan 75169695Skanstatic inline int 76169695Skanfibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 77169695Skan{ 78169695Skan if (a->key < b->key) 79169695Skan return -1; 80169695Skan if (a->key > b->key) 81169695Skan return 1; 82169695Skan return 0; 83169695Skan} 84169695Skan 85169695Skanstatic inline int 86169695Skanfibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 87169695Skan{ 88169695Skan struct fibnode a; 89169695Skan 90169695Skan a.key = key; 91169695Skan a.data = data; 92169695Skan 93169695Skan return fibheap_compare (heap, &a, b); 94169695Skan} 95169695Skan 96169695Skan/* Insert DATA, with priority KEY, into HEAP. */ 97169695Skanfibnode_t 98169695Skanfibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 99169695Skan{ 100169695Skan fibnode_t node; 101169695Skan 102169695Skan /* Create the new node. */ 103169695Skan node = fibnode_new (); 104169695Skan 105169695Skan /* Set the node's data. */ 106169695Skan node->data = data; 107169695Skan node->key = key; 108169695Skan 109169695Skan /* Insert it into the root list. */ 110169695Skan fibheap_ins_root (heap, node); 111169695Skan 112169695Skan /* If their was no minimum, or this key is less than the min, 113169695Skan it's the new min. */ 114169695Skan if (heap->min == NULL || node->key < heap->min->key) 115169695Skan heap->min = node; 116169695Skan 117169695Skan heap->nodes++; 118169695Skan 119169695Skan return node; 120169695Skan} 121169695Skan 122169695Skan/* Return the data of the minimum node (if we know it). */ 123169695Skanvoid * 124169695Skanfibheap_min (fibheap_t heap) 125169695Skan{ 126169695Skan /* If there is no min, we can't easily return it. */ 127169695Skan if (heap->min == NULL) 128169695Skan return NULL; 129169695Skan return heap->min->data; 130169695Skan} 131169695Skan 132169695Skan/* Return the key of the minimum node (if we know it). */ 133169695Skanfibheapkey_t 134169695Skanfibheap_min_key (fibheap_t heap) 135169695Skan{ 136169695Skan /* If there is no min, we can't easily return it. */ 137169695Skan if (heap->min == NULL) 138169695Skan return 0; 139169695Skan return heap->min->key; 140169695Skan} 141169695Skan 142169695Skan/* Union HEAPA and HEAPB into a new heap. */ 143169695Skanfibheap_t 144169695Skanfibheap_union (fibheap_t heapa, fibheap_t heapb) 145169695Skan{ 146169695Skan fibnode_t a_root, b_root, temp; 147169695Skan 148169695Skan /* If one of the heaps is empty, the union is just the other heap. */ 149169695Skan if ((a_root = heapa->root) == NULL) 150169695Skan { 151169695Skan free (heapa); 152169695Skan return heapb; 153169695Skan } 154169695Skan if ((b_root = heapb->root) == NULL) 155169695Skan { 156169695Skan free (heapb); 157169695Skan return heapa; 158169695Skan } 159169695Skan 160169695Skan /* Merge them to the next nodes on the opposite chain. */ 161169695Skan a_root->left->right = b_root; 162169695Skan b_root->left->right = a_root; 163169695Skan temp = a_root->left; 164169695Skan a_root->left = b_root->left; 165169695Skan b_root->left = temp; 166169695Skan heapa->nodes += heapb->nodes; 167169695Skan 168169695Skan /* And set the new minimum, if it's changed. */ 169169695Skan if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 170169695Skan heapa->min = heapb->min; 171169695Skan 172169695Skan free (heapb); 173169695Skan return heapa; 174169695Skan} 175169695Skan 176169695Skan/* Extract the data of the minimum node from HEAP. */ 177169695Skanvoid * 178169695Skanfibheap_extract_min (fibheap_t heap) 179169695Skan{ 180169695Skan fibnode_t z; 181169695Skan void *ret = NULL; 182169695Skan 183169695Skan /* If we don't have a min set, it means we have no nodes. */ 184169695Skan if (heap->min != NULL) 185169695Skan { 186169695Skan /* Otherwise, extract the min node, free the node, and return the 187169695Skan node's data. */ 188169695Skan z = fibheap_extr_min_node (heap); 189169695Skan ret = z->data; 190169695Skan free (z); 191169695Skan } 192169695Skan 193169695Skan return ret; 194169695Skan} 195169695Skan 196169695Skan/* Replace both the KEY and the DATA associated with NODE. */ 197169695Skanvoid * 198169695Skanfibheap_replace_key_data (fibheap_t heap, fibnode_t node, 199169695Skan fibheapkey_t key, void *data) 200169695Skan{ 201169695Skan void *odata; 202169695Skan fibheapkey_t okey; 203169695Skan fibnode_t y; 204169695Skan 205169695Skan /* If we wanted to, we could actually do a real increase by redeleting and 206169695Skan inserting. However, this would require O (log n) time. So just bail out 207169695Skan for now. */ 208169695Skan if (fibheap_comp_data (heap, key, data, node) > 0) 209169695Skan return NULL; 210169695Skan 211169695Skan odata = node->data; 212169695Skan okey = node->key; 213169695Skan node->data = data; 214169695Skan node->key = key; 215169695Skan y = node->parent; 216169695Skan 217169695Skan if (okey == key) 218169695Skan return odata; 219169695Skan 220169695Skan /* These two compares are specifically <= 0 to make sure that in the case 221169695Skan of equality, a node we replaced the data on, becomes the new min. This 222169695Skan is needed so that delete's call to extractmin gets the right node. */ 223169695Skan if (y != NULL && fibheap_compare (heap, node, y) <= 0) 224169695Skan { 225169695Skan fibheap_cut (heap, node, y); 226169695Skan fibheap_cascading_cut (heap, y); 227169695Skan } 228169695Skan 229169695Skan if (fibheap_compare (heap, node, heap->min) <= 0) 230169695Skan heap->min = node; 231169695Skan 232169695Skan return odata; 233169695Skan} 234169695Skan 235169695Skan/* Replace the DATA associated with NODE. */ 236169695Skanvoid * 237169695Skanfibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 238169695Skan{ 239169695Skan return fibheap_replace_key_data (heap, node, node->key, data); 240169695Skan} 241169695Skan 242169695Skan/* Replace the KEY associated with NODE. */ 243169695Skanfibheapkey_t 244169695Skanfibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 245169695Skan{ 246169695Skan int okey = node->key; 247169695Skan fibheap_replace_key_data (heap, node, key, node->data); 248169695Skan return okey; 249169695Skan} 250169695Skan 251169695Skan/* Delete NODE from HEAP. */ 252169695Skanvoid * 253169695Skanfibheap_delete_node (fibheap_t heap, fibnode_t node) 254169695Skan{ 255169695Skan void *ret = node->data; 256169695Skan 257169695Skan /* To perform delete, we just make it the min key, and extract. */ 258169695Skan fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 259169695Skan fibheap_extract_min (heap); 260169695Skan 261169695Skan return ret; 262169695Skan} 263169695Skan 264169695Skan/* Delete HEAP. */ 265169695Skanvoid 266169695Skanfibheap_delete (fibheap_t heap) 267169695Skan{ 268169695Skan while (heap->min != NULL) 269169695Skan free (fibheap_extr_min_node (heap)); 270169695Skan 271169695Skan free (heap); 272169695Skan} 273169695Skan 274169695Skan/* Determine if HEAP is empty. */ 275169695Skanint 276169695Skanfibheap_empty (fibheap_t heap) 277169695Skan{ 278169695Skan return heap->nodes == 0; 279169695Skan} 280169695Skan 281169695Skan/* Extract the minimum node of the heap. */ 282169695Skanstatic fibnode_t 283169695Skanfibheap_extr_min_node (fibheap_t heap) 284169695Skan{ 285169695Skan fibnode_t ret = heap->min; 286169695Skan fibnode_t x, y, orig; 287169695Skan 288169695Skan /* Attach the child list of the minimum node to the root list of the heap. 289169695Skan If there is no child list, we don't do squat. */ 290169695Skan for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 291169695Skan { 292169695Skan if (orig == NULL) 293169695Skan orig = x; 294169695Skan y = x->right; 295169695Skan x->parent = NULL; 296169695Skan fibheap_ins_root (heap, x); 297169695Skan } 298169695Skan 299169695Skan /* Remove the old root. */ 300169695Skan fibheap_rem_root (heap, ret); 301169695Skan heap->nodes--; 302169695Skan 303169695Skan /* If we are left with no nodes, then the min is NULL. */ 304169695Skan if (heap->nodes == 0) 305169695Skan heap->min = NULL; 306169695Skan else 307169695Skan { 308169695Skan /* Otherwise, consolidate to find new minimum, as well as do the reorg 309169695Skan work that needs to be done. */ 310169695Skan heap->min = ret->right; 311169695Skan fibheap_consolidate (heap); 312169695Skan } 313169695Skan 314169695Skan return ret; 315169695Skan} 316169695Skan 317169695Skan/* Insert NODE into the root list of HEAP. */ 318169695Skanstatic void 319169695Skanfibheap_ins_root (fibheap_t heap, fibnode_t node) 320169695Skan{ 321169695Skan /* If the heap is currently empty, the new node becomes the singleton 322169695Skan circular root list. */ 323169695Skan if (heap->root == NULL) 324169695Skan { 325169695Skan heap->root = node; 326169695Skan node->left = node; 327169695Skan node->right = node; 328169695Skan return; 329169695Skan } 330169695Skan 331169695Skan /* Otherwise, insert it in the circular root list between the root 332169695Skan and it's right node. */ 333169695Skan fibnode_insert_after (heap->root, node); 334169695Skan} 335169695Skan 336169695Skan/* Remove NODE from the rootlist of HEAP. */ 337169695Skanstatic void 338169695Skanfibheap_rem_root (fibheap_t heap, fibnode_t node) 339169695Skan{ 340169695Skan if (node->left == node) 341169695Skan heap->root = NULL; 342169695Skan else 343169695Skan heap->root = fibnode_remove (node); 344169695Skan} 345169695Skan 346169695Skan/* Consolidate the heap. */ 347169695Skanstatic void 348169695Skanfibheap_consolidate (fibheap_t heap) 349169695Skan{ 350169695Skan fibnode_t a[1 + 8 * sizeof (long)]; 351169695Skan fibnode_t w; 352169695Skan fibnode_t y; 353169695Skan fibnode_t x; 354169695Skan int i; 355169695Skan int d; 356169695Skan int D; 357169695Skan 358169695Skan D = 1 + 8 * sizeof (long); 359169695Skan 360169695Skan memset (a, 0, sizeof (fibnode_t) * D); 361169695Skan 362169695Skan while ((w = heap->root) != NULL) 363169695Skan { 364169695Skan x = w; 365169695Skan fibheap_rem_root (heap, w); 366169695Skan d = x->degree; 367169695Skan while (a[d] != NULL) 368169695Skan { 369169695Skan y = a[d]; 370169695Skan if (fibheap_compare (heap, x, y) > 0) 371169695Skan { 372169695Skan fibnode_t temp; 373169695Skan temp = x; 374169695Skan x = y; 375169695Skan y = temp; 376169695Skan } 377169695Skan fibheap_link (heap, y, x); 378169695Skan a[d] = NULL; 379169695Skan d++; 380169695Skan } 381169695Skan a[d] = x; 382169695Skan } 383169695Skan heap->min = NULL; 384169695Skan for (i = 0; i < D; i++) 385169695Skan if (a[i] != NULL) 386169695Skan { 387169695Skan fibheap_ins_root (heap, a[i]); 388169695Skan if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 389169695Skan heap->min = a[i]; 390169695Skan } 391169695Skan} 392169695Skan 393169695Skan/* Make NODE a child of PARENT. */ 394169695Skanstatic void 395169695Skanfibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, 396169695Skan fibnode_t node, fibnode_t parent) 397169695Skan{ 398169695Skan if (parent->child == NULL) 399169695Skan parent->child = node; 400169695Skan else 401169695Skan fibnode_insert_before (parent->child, node); 402169695Skan node->parent = parent; 403169695Skan parent->degree++; 404169695Skan node->mark = 0; 405169695Skan} 406169695Skan 407169695Skan/* Remove NODE from PARENT's child list. */ 408169695Skanstatic void 409169695Skanfibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) 410169695Skan{ 411169695Skan fibnode_remove (node); 412169695Skan parent->degree--; 413169695Skan fibheap_ins_root (heap, node); 414169695Skan node->parent = NULL; 415169695Skan node->mark = 0; 416169695Skan} 417169695Skan 418169695Skanstatic void 419169695Skanfibheap_cascading_cut (fibheap_t heap, fibnode_t y) 420169695Skan{ 421169695Skan fibnode_t z; 422169695Skan 423169695Skan while ((z = y->parent) != NULL) 424169695Skan { 425169695Skan if (y->mark == 0) 426169695Skan { 427169695Skan y->mark = 1; 428169695Skan return; 429169695Skan } 430169695Skan else 431169695Skan { 432169695Skan fibheap_cut (heap, y, z); 433169695Skan y = z; 434169695Skan } 435169695Skan } 436169695Skan} 437169695Skan 438169695Skanstatic void 439169695Skanfibnode_insert_after (fibnode_t a, fibnode_t b) 440169695Skan{ 441169695Skan if (a == a->right) 442169695Skan { 443169695Skan a->right = b; 444169695Skan a->left = b; 445169695Skan b->right = a; 446169695Skan b->left = a; 447169695Skan } 448169695Skan else 449169695Skan { 450169695Skan b->right = a->right; 451169695Skan a->right->left = b; 452169695Skan a->right = b; 453169695Skan b->left = a; 454169695Skan } 455169695Skan} 456169695Skan 457169695Skanstatic fibnode_t 458169695Skanfibnode_remove (fibnode_t node) 459169695Skan{ 460169695Skan fibnode_t ret; 461169695Skan 462169695Skan if (node == node->left) 463169695Skan ret = NULL; 464169695Skan else 465169695Skan ret = node->left; 466169695Skan 467169695Skan if (node->parent != NULL && node->parent->child == node) 468169695Skan node->parent->child = ret; 469169695Skan 470169695Skan node->right->left = node->left; 471169695Skan node->left->right = node->right; 472169695Skan 473169695Skan node->parent = NULL; 474169695Skan node->left = node; 475169695Skan node->right = node; 476169695Skan 477169695Skan return ret; 478169695Skan} 479