fibheap.c revision 218822
11897Swollman/* A Fibonacci heap datatype. 21897Swollman Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 31897Swollman Contributed by Daniel Berlin (dan@cgsoftware.com). 41897Swollman 51897SwollmanThis file is part of GNU CC. 61897Swollman 71897SwollmanGNU CC is free software; you can redistribute it and/or modify it 8100441Scharnierunder the terms of the GNU General Public License as published by 91897Swollmanthe Free Software Foundation; either version 2, or (at your option) 101897Swollmanany later version. 111897Swollman 12100441ScharnierGNU CC is distributed in the hope that it will be useful, but 131897SwollmanWITHOUT ANY WARRANTY; without even the implied warranty of 141897SwollmanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 151897SwollmanGeneral Public License for more details. 16100441Scharnier 171897SwollmanYou should have received a copy of the GNU General Public License 181897Swollmanalong with GNU CC; see the file COPYING. If not, write to 191897Swollmanthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20100441ScharnierBoston, MA 02110-1301, USA. */ 211897Swollman 221897Swollman#ifdef HAVE_CONFIG_H 231897Swollman#include "config.h" 24100441Scharnier#endif 251897Swollman#ifdef HAVE_LIMITS_H 261897Swollman#include <limits.h> 271897Swollman#endif 281897Swollman#ifdef HAVE_STDLIB_H 2912798Swpaul#include <stdlib.h> 30100441Scharnier#endif 311897Swollman#ifdef HAVE_STRING_H 32146833Sstefanf#include <string.h> 3312798Swpaul#endif 341897Swollman#include "libiberty.h" 3579880Skris#include "fibheap.h" 361897Swollman 37100441Scharnier 38100441Scharnier#define FIBHEAPKEY_MIN LONG_MIN 39100441Scharnier 401897Swollmanstatic void fibheap_ins_root (fibheap_t, fibnode_t); 411897Swollmanstatic void fibheap_rem_root (fibheap_t, fibnode_t); 4212798Swpaulstatic void fibheap_consolidate (fibheap_t); 431897Swollmanstatic void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 441897Swollmanstatic void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 4512798Swpaulstatic void fibheap_cascading_cut (fibheap_t, fibnode_t); 461897Swollmanstatic fibnode_t fibheap_extr_min_node (fibheap_t); 47149682Sstefanfstatic int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 481897Swollmanstatic int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 491897Swollmanstatic fibnode_t fibnode_new (void); 5099979Salfredstatic void fibnode_insert_after (fibnode_t, fibnode_t); 5199979Salfred#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 521897Swollmanstatic fibnode_t fibnode_remove (fibnode_t); 531897Swollman 541897Swollman 551897Swollman/* Create a new fibonacci heap. */ 561897Swollmanfibheap_t 5712798Swpaulfibheap_new (void) 581897Swollman{ 5912798Swpaul return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 6012798Swpaul} 6192921Simp 6292921Simp/* Create a new fibonacci heap node. */ 6392921Simpstatic fibnode_t 6492921Simpfibnode_new (void) 6592921Simp{ 6692921Simp fibnode_t node; 6792921Simp 6892921Simp node = (fibnode_t) xcalloc (1, sizeof *node); 6992921Simp node->left = node; 7092921Simp node->right = node; 7192921Simp 7292921Simp return node; 7392921Simp} 7492921Simp 7592921Simpstatic inline int 7612798Swpaulfibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 7712798Swpaul{ 7817142Sjkh if (a->key < b->key) 7912798Swpaul return -1; 8012798Swpaul if (a->key > b->key) 8112798Swpaul return 1; 8212798Swpaul return 0; 83149709Sstefanf} 84149709Sstefanf 8512798Swpaulstatic inline int 8612798Swpaulfibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 8712798Swpaul{ 8812798Swpaul struct fibnode a; 8912798Swpaul 9012798Swpaul a.key = key; 9112798Swpaul a.data = data; 9212798Swpaul 9312798Swpaul return fibheap_compare (heap, &a, b); 9412798Swpaul} 9512798Swpaul 9612798Swpaul/* Insert DATA, with priority KEY, into HEAP. */ 971897Swollmanfibnode_t 988874Srgrimesfibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 991897Swollman{ 1001897Swollman fibnode_t node; 10112798Swpaul 10212798Swpaul /* Create the new node. */ 10312798Swpaul node = fibnode_new (); 10412798Swpaul 1051897Swollman /* Set the node's data. */ 10612798Swpaul node->data = data; 10712798Swpaul node->key = key; 10812798Swpaul 10912798Swpaul /* Insert it into the root list. */ 11012798Swpaul fibheap_ins_root (heap, node); 11199979Salfred 11212798Swpaul /* If their was no minimum, or this key is less than the min, 11312798Swpaul it's the new min. */ 11412798Swpaul if (heap->min == NULL || node->key < heap->min->key) 11512798Swpaul heap->min = node; 1161897Swollman 11712798Swpaul heap->nodes++; 11812798Swpaul 11912798Swpaul return node; 12012798Swpaul} 12112798Swpaul 12212798Swpaul/* Return the data of the minimum node (if we know it). */ 12312798Swpaulvoid * 12412798Swpaulfibheap_min (fibheap_t heap) 12512798Swpaul{ 12612798Swpaul /* If there is no min, we can't easily return it. */ 12712798Swpaul if (heap->min == NULL) 12812798Swpaul return NULL; 12912798Swpaul return heap->min->data; 13012798Swpaul} 1311897Swollman 13212798Swpaul/* Return the key of the minimum node (if we know it). */ 1331897Swollmanfibheapkey_t 13412798Swpaulfibheap_min_key (fibheap_t heap) 13512798Swpaul{ 1361897Swollman /* If there is no min, we can't easily return it. */ 13712798Swpaul if (heap->min == NULL) 13812798Swpaul return 0; 13912798Swpaul return heap->min->key; 14012798Swpaul} 14112798Swpaul 14212798Swpaul/* Union HEAPA and HEAPB into a new heap. */ 14399979Salfredfibheap_t 14499979Salfredfibheap_union (fibheap_t heapa, fibheap_t heapb) 1451897Swollman{ 146109363Smbr fibnode_t a_root, b_root, temp; 147109363Smbr 148109363Smbr /* If one of the heaps is empty, the union is just the other heap. */ 149109363Smbr if ((a_root = heapa->root) == NULL) 150109363Smbr { 15112798Swpaul free (heapa); 15212798Swpaul return heapb; 15312798Swpaul } 15412798Swpaul if ((b_root = heapb->root) == NULL) 15512798Swpaul { 15612798Swpaul free (heapb); 15712798Swpaul return heapa; 15812798Swpaul } 15912798Swpaul 16012798Swpaul /* Merge them to the next nodes on the opposite chain. */ 16112798Swpaul a_root->left->right = b_root; 16212798Swpaul b_root->left->right = a_root; 16312798Swpaul temp = a_root->left; 16499979Salfred a_root->left = b_root->left; 16599979Salfred b_root->left = temp; 16699979Salfred heapa->nodes += heapb->nodes; 16799979Salfred 16899979Salfred /* And set the new minimum, if it's changed. */ 16999979Salfred if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 17099979Salfred heapa->min = heapb->min; 17112798Swpaul 17212798Swpaul free (heapb); 17312798Swpaul return heapa; 17499979Salfred} 17599979Salfred 17699979Salfred/* Extract the data of the minimum node from HEAP. */ 17799979Salfredvoid * 17899979Salfredfibheap_extract_min (fibheap_t heap) 179100441Scharnier{ 18099979Salfred fibnode_t z; 18112798Swpaul void *ret = NULL; 18212798Swpaul 18312798Swpaul /* If we don't have a min set, it means we have no nodes. */ 18412798Swpaul if (heap->min != NULL) 18512798Swpaul { 18612798Swpaul /* Otherwise, extract the min node, free the node, and return the 18712798Swpaul node's data. */ 18812798Swpaul z = fibheap_extr_min_node (heap); 18912798Swpaul ret = z->data; 19012798Swpaul free (z); 19112798Swpaul } 19212798Swpaul 19312798Swpaul return ret; 19412798Swpaul} 19512798Swpaul 19612798Swpaul/* Replace both the KEY and the DATA associated with NODE. */ 19712798Swpaulvoid * 19812798Swpaulfibheap_replace_key_data (fibheap_t heap, fibnode_t node, 19912798Swpaul fibheapkey_t key, void *data) 20012798Swpaul{ 20112798Swpaul void *odata; 20212798Swpaul fibheapkey_t okey; 20312798Swpaul fibnode_t y; 20412798Swpaul 20512798Swpaul /* If we wanted to, we could actually do a real increase by redeleting and 20612798Swpaul inserting. However, this would require O (log n) time. So just bail out 20712798Swpaul for now. */ 2081897Swollman if (fibheap_comp_data (heap, key, data, node) > 0) 20912798Swpaul return NULL; 21012798Swpaul 21112798Swpaul odata = node->data; 21212798Swpaul okey = node->key; 21312798Swpaul node->data = data; 21412798Swpaul node->key = key; 21512798Swpaul y = node->parent; 216109363Smbr 217109363Smbr if (okey == key) 218109363Smbr return odata; 219109363Smbr 220109363Smbr /* These two compares are specifically <= 0 to make sure that in the case 221109363Smbr of equality, a node we replaced the data on, becomes the new min. This 222109363Smbr is needed so that delete's call to extractmin gets the right node. */ 223109363Smbr if (y != NULL && fibheap_compare (heap, node, y) <= 0) 224109363Smbr { 22512798Swpaul fibheap_cut (heap, node, y); 22612798Swpaul fibheap_cascading_cut (heap, y); 22712798Swpaul } 22812798Swpaul 22912798Swpaul if (fibheap_compare (heap, node, heap->min) <= 0) 23012798Swpaul heap->min = node; 2311897Swollman 2321897Swollman return odata; 2331897Swollman} 2341897Swollman 2351897Swollman/* Replace the DATA associated with NODE. */ 2361897Swollmanvoid * 23712798Swpaulfibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 23812798Swpaul{ 23912798Swpaul return fibheap_replace_key_data (heap, node, node->key, data); 24012798Swpaul} 24112798Swpaul 24212798Swpaul/* Replace the KEY associated with NODE. */ 24312798Swpaulfibheapkey_t 24412798Swpaulfibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 24512798Swpaul{ 24612798Swpaul int okey = node->key; 24712798Swpaul fibheap_replace_key_data (heap, node, key, node->data); 24812798Swpaul return okey; 24912798Swpaul} 25012798Swpaul 2511897Swollman/* Delete NODE from HEAP. */ 2521897Swollmanvoid * 25312798Swpaulfibheap_delete_node (fibheap_t heap, fibnode_t node) 2541897Swollman{ 2551897Swollman void *ret = node->data; 2561897Swollman 25712798Swpaul /* To perform delete, we just make it the min key, and extract. */ 2581897Swollman fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 2591897Swollman fibheap_extract_min (heap); 26012798Swpaul 2611897Swollman return ret; 2621897Swollman} 2631897Swollman 2641897Swollman/* Delete HEAP. */ 2651897Swollmanvoid 2661897Swollmanfibheap_delete (fibheap_t heap) 2671897Swollman{ 2681897Swollman while (heap->min != NULL) 2691897Swollman free (fibheap_extr_min_node (heap)); 2701897Swollman 2711897Swollman free (heap); 272109363Smbr} 273109363Smbr 274109363Smbr/* Determine if HEAP is empty. */ 275109363Smbrint 2761897Swollmanfibheap_empty (fibheap_t heap) 27712798Swpaul{ 2781897Swollman return heap->nodes == 0; 27912798Swpaul} 2801897Swollman 28112798Swpaul/* Extract the minimum node of the heap. */ 28212798Swpaulstatic fibnode_t 28312798Swpaulfibheap_extr_min_node (fibheap_t heap) 28412798Swpaul{ 2851897Swollman fibnode_t ret = heap->min; 2861897Swollman fibnode_t x, y, orig; 2871897Swollman 2881897Swollman /* Attach the child list of the minimum node to the root list of the heap. 2891897Swollman If there is no child list, we don't do squat. */ 2901897Swollman for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 2911897Swollman { 2928874Srgrimes if (orig == NULL) 2931897Swollman orig = x; 2941897Swollman y = x->right; 2951897Swollman x->parent = NULL; 2961897Swollman fibheap_ins_root (heap, x); 29712798Swpaul } 29812798Swpaul 29912798Swpaul /* Remove the old root. */ 30012798Swpaul fibheap_rem_root (heap, ret); 30112798Swpaul heap->nodes--; 30212798Swpaul 30312798Swpaul /* If we are left with no nodes, then the min is NULL. */ 30412798Swpaul if (heap->nodes == 0) 30512798Swpaul heap->min = NULL; 30612798Swpaul else 307149709Sstefanf { 30812798Swpaul /* Otherwise, consolidate to find new minimum, as well as do the reorg 30912798Swpaul work that needs to be done. */ 31012798Swpaul heap->min = ret->right; 31112798Swpaul fibheap_consolidate (heap); 31212798Swpaul } 3131897Swollman 31412798Swpaul return ret; 31512798Swpaul} 3161897Swollman 31712798Swpaul/* Insert NODE into the root list of HEAP. */ 3181897Swollmanstatic void 3191897Swollmanfibheap_ins_root (fibheap_t heap, fibnode_t node) 3201897Swollman{ 3211897Swollman /* If the heap is currently empty, the new node becomes the singleton 3221897Swollman circular root list. */ 3231897Swollman if (heap->root == NULL) 3241897Swollman { 3251897Swollman heap->root = node; 3261897Swollman node->left = node; 3271897Swollman node->right = node; 32812798Swpaul return; 3291897Swollman } 3301897Swollman 3311897Swollman /* Otherwise, insert it in the circular root list between the root 33212798Swpaul and it's right node. */ 33312798Swpaul fibnode_insert_after (heap->root, node); 33412798Swpaul} 33512798Swpaul 33612798Swpaul/* Remove NODE from the rootlist of HEAP. */ 33712798Swpaulstatic void 33812798Swpaulfibheap_rem_root (fibheap_t heap, fibnode_t node) 33912798Swpaul{ 3401897Swollman if (node->left == node) 3411897Swollman heap->root = NULL; 3421897Swollman else 34312798Swpaul heap->root = fibnode_remove (node); 34412798Swpaul} 3451897Swollman 3461897Swollman/* Consolidate the heap. */ 34712798Swpaulstatic void 34812798Swpaulfibheap_consolidate (fibheap_t heap) 34912798Swpaul{ 35012798Swpaul fibnode_t a[1 + 8 * sizeof (long)]; 35112798Swpaul fibnode_t w; 35212798Swpaul fibnode_t y; 35317142Sjkh fibnode_t x; 35412798Swpaul int i; 35512798Swpaul int d; 35612798Swpaul int D; 35712798Swpaul 35812798Swpaul D = 1 + 8 * sizeof (long); 35912798Swpaul 3601897Swollman memset (a, 0, sizeof (fibnode_t) * D); 36112798Swpaul 36212798Swpaul while ((w = heap->root) != NULL) 36312798Swpaul { 36412798Swpaul x = w; 36512798Swpaul fibheap_rem_root (heap, w); 36612798Swpaul d = x->degree; 36712798Swpaul while (a[d] != NULL) 36812798Swpaul { 36912798Swpaul y = a[d]; 37012798Swpaul if (fibheap_compare (heap, x, y) > 0) 371149709Sstefanf { 372149709Sstefanf fibnode_t temp; 373149709Sstefanf temp = x; 374149709Sstefanf x = y; 375149709Sstefanf y = temp; 376149709Sstefanf } 377149709Sstefanf fibheap_link (heap, y, x); 378149709Sstefanf a[d] = NULL; 379149709Sstefanf d++; 380149709Sstefanf } 38112798Swpaul a[d] = x; 38212798Swpaul } 38312798Swpaul heap->min = NULL; 384149709Sstefanf for (i = 0; i < D; i++) 385149709Sstefanf if (a[i] != NULL) 386149709Sstefanf { 38712798Swpaul fibheap_ins_root (heap, a[i]); 38812798Swpaul if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 38912798Swpaul heap->min = a[i]; 390149709Sstefanf } 39112798Swpaul} 39212798Swpaul 39312798Swpaul/* Make NODE a child of PARENT. */ 39412798Swpaulstatic void 39512798Swpaulfibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, 39612798Swpaul fibnode_t node, fibnode_t parent) 39712798Swpaul{ 39812798Swpaul if (parent->child == NULL) 39912798Swpaul parent->child = node; 40012798Swpaul else 40112798Swpaul fibnode_insert_before (parent->child, node); 40212798Swpaul node->parent = parent; 40312798Swpaul parent->degree++; 40412798Swpaul node->mark = 0; 40512798Swpaul} 40612798Swpaul 40712798Swpaul/* Remove NODE from PARENT's child list. */ 40817142Sjkhstatic void 4091897Swollmanfibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) 4101897Swollman{ 4111897Swollman fibnode_remove (node); 4121897Swollman parent->degree--; 4131897Swollman fibheap_ins_root (heap, node); 4141897Swollman node->parent = NULL; 4151897Swollman node->mark = 0; 4161897Swollman} 4171897Swollman 4181897Swollmanstatic void 4191897Swollmanfibheap_cascading_cut (fibheap_t heap, fibnode_t y) 4201897Swollman{ 4211897Swollman fibnode_t z; 4221897Swollman 4231897Swollman while ((z = y->parent) != NULL) 42412798Swpaul { 425149709Sstefanf if (y->mark == 0) 426149710Sstefanf { 4271897Swollman y->mark = 1; 4281897Swollman return; 4291897Swollman } 4301897Swollman else 4311897Swollman { 43212798Swpaul fibheap_cut (heap, y, z); 43312798Swpaul y = z; 43412798Swpaul } 43512798Swpaul } 43612798Swpaul} 43712798Swpaul 43812798Swpaulstatic void 43912798Swpaulfibnode_insert_after (fibnode_t a, fibnode_t b) 44012798Swpaul{ 44112798Swpaul if (a == a->right) 44212798Swpaul { 44312798Swpaul a->right = b; 44412798Swpaul a->left = b; 44512798Swpaul b->right = a; 44612798Swpaul b->left = a; 44712798Swpaul } 44812798Swpaul else 44912798Swpaul { 4501897Swollman b->right = a->right; 4511897Swollman a->right->left = b; 4521897Swollman a->right = b; 4531897Swollman b->left = a; 4541897Swollman } 4551897Swollman} 45612798Swpaul 45712798Swpaulstatic fibnode_t 45812798Swpaulfibnode_remove (fibnode_t node) 45912798Swpaul{ 46012798Swpaul fibnode_t ret; 46112798Swpaul 46212798Swpaul if (node == node->left) 46312798Swpaul ret = NULL; 46412798Swpaul else 46512798Swpaul ret = node->left; 46612798Swpaul 46712798Swpaul if (node->parent != NULL && node->parent->child == node) 468100441Scharnier node->parent->child = ret; 46912798Swpaul 47012798Swpaul node->right->left = node->left; 471149709Sstefanf node->left->right = node->right; 472149709Sstefanf 47312798Swpaul node->parent = NULL; 474149709Sstefanf node->left = node; 475149709Sstefanf node->right = node; 476149709Sstefanf 477149709Sstefanf return ret; 478149709Sstefanf} 479149709Sstefanf