fibheap.c revision 89857
189857Sobrien/* A Fibonacci heap datatype. 289857Sobrien Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 389857Sobrien Contributed by Daniel Berlin (dan@cgsoftware.com). 489857Sobrien 589857SobrienThis file is part of GNU CC. 689857Sobrien 789857SobrienGNU CC is free software; you can redistribute it and/or modify it 889857Sobrienunder the terms of the GNU General Public License as published by 989857Sobrienthe Free Software Foundation; either version 2, or (at your option) 1089857Sobrienany later version. 1189857Sobrien 1289857SobrienGNU CC is distributed in the hope that it will be useful, but 1389857SobrienWITHOUT ANY WARRANTY; without even the implied warranty of 1489857SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1589857SobrienGeneral Public License for more details. 1689857Sobrien 1789857SobrienYou should have received a copy of the GNU General Public License 1889857Sobrienalong with GNU CC; see the file COPYING. If not, write to 1989857Sobrienthe Free Software Foundation, 59 Temple Place - Suite 330, 2089857SobrienBoston, MA 02111-1307, USA. */ 2189857Sobrien 2289857Sobrien#ifdef HAVE_CONFIG_H 2389857Sobrien#include "config.h" 2489857Sobrien#endif 2589857Sobrien#ifdef HAVE_LIMITS_H 2689857Sobrien#include <limits.h> 2789857Sobrien#endif 2889857Sobrien#ifdef HAVE_STDLIB_H 2989857Sobrien#include <stdlib.h> 3089857Sobrien#endif 3189857Sobrien#ifdef HAVE_STRING_H 3289857Sobrien#include <string.h> 3389857Sobrien#endif 3489857Sobrien#include "libiberty.h" 3589857Sobrien#include "fibheap.h" 3689857Sobrien 3789857Sobrien 3889857Sobrien#define FIBHEAPKEY_MIN LONG_MIN 3989857Sobrien 4089857Sobrienstatic void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t)); 4189857Sobrienstatic void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t)); 4289857Sobrienstatic void fibheap_consolidate PARAMS ((fibheap_t)); 4389857Sobrienstatic void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t)); 4489857Sobrienstatic void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t)); 4589857Sobrienstatic void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t)); 4689857Sobrienstatic fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t)); 4789857Sobrienstatic int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t)); 4889857Sobrienstatic int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, 4989857Sobrien fibnode_t)); 5089857Sobrienstatic fibnode_t fibnode_new PARAMS ((void)); 5189857Sobrienstatic void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t)); 5289857Sobrien#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 5389857Sobrienstatic fibnode_t fibnode_remove PARAMS ((fibnode_t)); 5489857Sobrien 5589857Sobrien 5689857Sobrien/* Create a new fibonacci heap. */ 5789857Sobrienfibheap_t 5889857Sobrienfibheap_new () 5989857Sobrien{ 6089857Sobrien return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 6189857Sobrien} 6289857Sobrien 6389857Sobrien/* Create a new fibonacci heap node. */ 6489857Sobrienstatic fibnode_t 6589857Sobrienfibnode_new () 6689857Sobrien{ 6789857Sobrien fibnode_t node; 6889857Sobrien 6989857Sobrien node = xcalloc (1, sizeof *node); 7089857Sobrien node->left = node; 7189857Sobrien node->right = node; 7289857Sobrien 7389857Sobrien return node; 7489857Sobrien} 7589857Sobrien 7689857Sobrienstatic inline int 7789857Sobrienfibheap_compare (heap, a, b) 7889857Sobrien fibheap_t heap ATTRIBUTE_UNUSED; 7989857Sobrien fibnode_t a; 8089857Sobrien fibnode_t b; 8189857Sobrien{ 8289857Sobrien if (a->key < b->key) 8389857Sobrien return -1; 8489857Sobrien if (a->key > b->key) 8589857Sobrien return 1; 8689857Sobrien return 0; 8789857Sobrien} 8889857Sobrien 8989857Sobrienstatic inline int 9089857Sobrienfibheap_comp_data (heap, key, data, b) 9189857Sobrien fibheap_t heap; 9289857Sobrien fibheapkey_t key; 9389857Sobrien void *data; 9489857Sobrien fibnode_t b; 9589857Sobrien{ 9689857Sobrien struct fibnode a; 9789857Sobrien 9889857Sobrien a.key = key; 9989857Sobrien a.data = data; 10089857Sobrien 10189857Sobrien return fibheap_compare (heap, &a, b); 10289857Sobrien} 10389857Sobrien 10489857Sobrien/* Insert DATA, with priority KEY, into HEAP. */ 10589857Sobrienfibnode_t 10689857Sobrienfibheap_insert (heap, key, data) 10789857Sobrien fibheap_t heap; 10889857Sobrien fibheapkey_t key; 10989857Sobrien void *data; 11089857Sobrien{ 11189857Sobrien fibnode_t node; 11289857Sobrien 11389857Sobrien /* Create the new node. */ 11489857Sobrien node = fibnode_new (); 11589857Sobrien 11689857Sobrien /* Set the node's data. */ 11789857Sobrien node->data = data; 11889857Sobrien node->key = key; 11989857Sobrien 12089857Sobrien /* Insert it into the root list. */ 12189857Sobrien fibheap_ins_root (heap, node); 12289857Sobrien 12389857Sobrien /* If their was no minimum, or this key is less than the min, 12489857Sobrien it's the new min. */ 12589857Sobrien if (heap->min == NULL || node->key < heap->min->key) 12689857Sobrien heap->min = node; 12789857Sobrien 12889857Sobrien heap->nodes++; 12989857Sobrien 13089857Sobrien return node; 13189857Sobrien} 13289857Sobrien 13389857Sobrien/* Return the data of the minimum node (if we know it). */ 13489857Sobrienvoid * 13589857Sobrienfibheap_min (heap) 13689857Sobrien fibheap_t heap; 13789857Sobrien{ 13889857Sobrien /* If there is no min, we can't easily return it. */ 13989857Sobrien if (heap->min == NULL) 14089857Sobrien return NULL; 14189857Sobrien return heap->min->data; 14289857Sobrien} 14389857Sobrien 14489857Sobrien/* Return the key of the minimum node (if we know it). */ 14589857Sobrienfibheapkey_t 14689857Sobrienfibheap_min_key (heap) 14789857Sobrien fibheap_t heap; 14889857Sobrien{ 14989857Sobrien /* If there is no min, we can't easily return it. */ 15089857Sobrien if (heap->min == NULL) 15189857Sobrien return 0; 15289857Sobrien return heap->min->key; 15389857Sobrien} 15489857Sobrien 15589857Sobrien/* Union HEAPA and HEAPB into a new heap. */ 15689857Sobrienfibheap_t 15789857Sobrienfibheap_union (heapa, heapb) 15889857Sobrien fibheap_t heapa; 15989857Sobrien fibheap_t heapb; 16089857Sobrien{ 16189857Sobrien fibnode_t a_root, b_root, temp; 16289857Sobrien 16389857Sobrien /* If one of the heaps is empty, the union is just the other heap. */ 16489857Sobrien if ((a_root = heapa->root) == NULL) 16589857Sobrien { 16689857Sobrien free (heapa); 16789857Sobrien return heapb; 16889857Sobrien } 16989857Sobrien if ((b_root = heapb->root) == NULL) 17089857Sobrien { 17189857Sobrien free (heapb); 17289857Sobrien return heapa; 17389857Sobrien } 17489857Sobrien 17589857Sobrien /* Merge them to the next nodes on the opposite chain. */ 17689857Sobrien a_root->left->right = b_root; 17789857Sobrien b_root->left->right = a_root; 17889857Sobrien temp = a_root->left; 17989857Sobrien a_root->left = b_root->left; 18089857Sobrien b_root->left = temp; 18189857Sobrien heapa->nodes += heapb->nodes; 18289857Sobrien 18389857Sobrien /* And set the new minimum, if it's changed. */ 18489857Sobrien if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 18589857Sobrien heapa->min = heapb->min; 18689857Sobrien 18789857Sobrien free (heapb); 18889857Sobrien return heapa; 18989857Sobrien} 19089857Sobrien 19189857Sobrien/* Extract the data of the minimum node from HEAP. */ 19289857Sobrienvoid * 19389857Sobrienfibheap_extract_min (heap) 19489857Sobrien fibheap_t heap; 19589857Sobrien{ 19689857Sobrien fibnode_t z; 19789857Sobrien void *ret = NULL; 19889857Sobrien 19989857Sobrien /* If we don't have a min set, it means we have no nodes. */ 20089857Sobrien if (heap->min != NULL) 20189857Sobrien { 20289857Sobrien /* Otherwise, extract the min node, free the node, and return the 20389857Sobrien node's data. */ 20489857Sobrien z = fibheap_extr_min_node (heap); 20589857Sobrien ret = z->data; 20689857Sobrien free (z); 20789857Sobrien } 20889857Sobrien 20989857Sobrien return ret; 21089857Sobrien} 21189857Sobrien 21289857Sobrien/* Replace both the KEY and the DATA associated with NODE. */ 21389857Sobrienvoid * 21489857Sobrienfibheap_replace_key_data (heap, node, key, data) 21589857Sobrien fibheap_t heap; 21689857Sobrien fibnode_t node; 21789857Sobrien fibheapkey_t key; 21889857Sobrien void *data; 21989857Sobrien{ 22089857Sobrien void *odata; 22189857Sobrien int okey; 22289857Sobrien fibnode_t y; 22389857Sobrien 22489857Sobrien /* If we wanted to, we could actually do a real increase by redeleting and 22589857Sobrien inserting. However, this would require O (log n) time. So just bail out 22689857Sobrien for now. */ 22789857Sobrien if (fibheap_comp_data (heap, key, data, node) > 0) 22889857Sobrien return NULL; 22989857Sobrien 23089857Sobrien odata = node->data; 23189857Sobrien okey = node->key; 23289857Sobrien node->data = data; 23389857Sobrien node->key = key; 23489857Sobrien y = node->parent; 23589857Sobrien 23689857Sobrien if (okey == key) 23789857Sobrien return odata; 23889857Sobrien 23989857Sobrien /* These two compares are specifically <= 0 to make sure that in the case 24089857Sobrien of equality, a node we replaced the data on, becomes the new min. This 24189857Sobrien is needed so that delete's call to extractmin gets the right node. */ 24289857Sobrien if (y != NULL && fibheap_compare (heap, node, y) <= 0) 24389857Sobrien { 24489857Sobrien fibheap_cut (heap, node, y); 24589857Sobrien fibheap_cascading_cut (heap, y); 24689857Sobrien } 24789857Sobrien 24889857Sobrien if (fibheap_compare (heap, node, heap->min) <= 0) 24989857Sobrien heap->min = node; 25089857Sobrien 25189857Sobrien return odata; 25289857Sobrien} 25389857Sobrien 25489857Sobrien/* Replace the DATA associated with NODE. */ 25589857Sobrienvoid * 25689857Sobrienfibheap_replace_data (heap, node, data) 25789857Sobrien fibheap_t heap; 25889857Sobrien fibnode_t node; 25989857Sobrien void *data; 26089857Sobrien{ 26189857Sobrien return fibheap_replace_key_data (heap, node, node->key, data); 26289857Sobrien} 26389857Sobrien 26489857Sobrien/* Replace the KEY associated with NODE. */ 26589857Sobrienfibheapkey_t 26689857Sobrienfibheap_replace_key (heap, node, key) 26789857Sobrien fibheap_t heap; 26889857Sobrien fibnode_t node; 26989857Sobrien fibheapkey_t key; 27089857Sobrien{ 27189857Sobrien int okey = node->key; 27289857Sobrien fibheap_replace_key_data (heap, node, key, node->data); 27389857Sobrien return okey; 27489857Sobrien} 27589857Sobrien 27689857Sobrien/* Delete NODE from HEAP. */ 27789857Sobrienvoid * 27889857Sobrienfibheap_delete_node (heap, node) 27989857Sobrien fibheap_t heap; 28089857Sobrien fibnode_t node; 28189857Sobrien{ 28289857Sobrien void *ret = node->data; 28389857Sobrien 28489857Sobrien /* To perform delete, we just make it the min key, and extract. */ 28589857Sobrien fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 28689857Sobrien fibheap_extract_min (heap); 28789857Sobrien 28889857Sobrien return ret; 28989857Sobrien} 29089857Sobrien 29189857Sobrien/* Delete HEAP. */ 29289857Sobrienvoid 29389857Sobrienfibheap_delete (heap) 29489857Sobrien fibheap_t heap; 29589857Sobrien{ 29689857Sobrien while (heap->min != NULL) 29789857Sobrien free (fibheap_extr_min_node (heap)); 29889857Sobrien 29989857Sobrien free (heap); 30089857Sobrien} 30189857Sobrien 30289857Sobrien/* Determine if HEAP is empty. */ 30389857Sobrienint 30489857Sobrienfibheap_empty (heap) 30589857Sobrien fibheap_t heap; 30689857Sobrien{ 30789857Sobrien return heap->nodes == 0; 30889857Sobrien} 30989857Sobrien 31089857Sobrien/* Extract the minimum node of the heap. */ 31189857Sobrienstatic fibnode_t 31289857Sobrienfibheap_extr_min_node (heap) 31389857Sobrien fibheap_t heap; 31489857Sobrien{ 31589857Sobrien fibnode_t ret = heap->min; 31689857Sobrien fibnode_t x, y, orig; 31789857Sobrien 31889857Sobrien /* Attach the child list of the minimum node to the root list of the heap. 31989857Sobrien If there is no child list, we don't do squat. */ 32089857Sobrien for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 32189857Sobrien { 32289857Sobrien if (orig == NULL) 32389857Sobrien orig = x; 32489857Sobrien y = x->right; 32589857Sobrien x->parent = NULL; 32689857Sobrien fibheap_ins_root (heap, x); 32789857Sobrien } 32889857Sobrien 32989857Sobrien /* Remove the old root. */ 33089857Sobrien fibheap_rem_root (heap, ret); 33189857Sobrien heap->nodes--; 33289857Sobrien 33389857Sobrien /* If we are left with no nodes, then the min is NULL. */ 33489857Sobrien if (heap->nodes == 0) 33589857Sobrien heap->min = NULL; 33689857Sobrien else 33789857Sobrien { 33889857Sobrien /* Otherwise, consolidate to find new minimum, as well as do the reorg 33989857Sobrien work that needs to be done. */ 34089857Sobrien heap->min = ret->right; 34189857Sobrien fibheap_consolidate (heap); 34289857Sobrien } 34389857Sobrien 34489857Sobrien return ret; 34589857Sobrien} 34689857Sobrien 34789857Sobrien/* Insert NODE into the root list of HEAP. */ 34889857Sobrienstatic void 34989857Sobrienfibheap_ins_root (heap, node) 35089857Sobrien fibheap_t heap; 35189857Sobrien fibnode_t node; 35289857Sobrien{ 35389857Sobrien /* If the heap is currently empty, the new node becomes the singleton 35489857Sobrien circular root list. */ 35589857Sobrien if (heap->root == NULL) 35689857Sobrien { 35789857Sobrien heap->root = node; 35889857Sobrien node->left = node; 35989857Sobrien node->right = node; 36089857Sobrien return; 36189857Sobrien } 36289857Sobrien 36389857Sobrien /* Otherwise, insert it in the circular root list between the root 36489857Sobrien and it's right node. */ 36589857Sobrien fibnode_insert_after (heap->root, node); 36689857Sobrien} 36789857Sobrien 36889857Sobrien/* Remove NODE from the rootlist of HEAP. */ 36989857Sobrienstatic void 37089857Sobrienfibheap_rem_root (heap, node) 37189857Sobrien fibheap_t heap; 37289857Sobrien fibnode_t node; 37389857Sobrien{ 37489857Sobrien if (node->left == node) 37589857Sobrien heap->root = NULL; 37689857Sobrien else 37789857Sobrien heap->root = fibnode_remove (node); 37889857Sobrien} 37989857Sobrien 38089857Sobrien/* Consolidate the heap. */ 38189857Sobrienstatic void 38289857Sobrienfibheap_consolidate (heap) 38389857Sobrien fibheap_t heap; 38489857Sobrien{ 38589857Sobrien fibnode_t a[1 + 8 * sizeof (long)]; 38689857Sobrien fibnode_t w; 38789857Sobrien fibnode_t y; 38889857Sobrien fibnode_t x; 38989857Sobrien int i; 39089857Sobrien int d; 39189857Sobrien int D; 39289857Sobrien 39389857Sobrien D = 1 + 8 * sizeof (long); 39489857Sobrien 39589857Sobrien memset (a, 0, sizeof (fibnode_t) * D); 39689857Sobrien 39789857Sobrien while ((w = heap->root) != NULL) 39889857Sobrien { 39989857Sobrien x = w; 40089857Sobrien fibheap_rem_root (heap, w); 40189857Sobrien d = x->degree; 40289857Sobrien while (a[d] != NULL) 40389857Sobrien { 40489857Sobrien y = a[d]; 40589857Sobrien if (fibheap_compare (heap, x, y) > 0) 40689857Sobrien { 40789857Sobrien fibnode_t temp; 40889857Sobrien temp = x; 40989857Sobrien x = y; 41089857Sobrien y = temp; 41189857Sobrien } 41289857Sobrien fibheap_link (heap, y, x); 41389857Sobrien a[d] = NULL; 41489857Sobrien d++; 41589857Sobrien } 41689857Sobrien a[d] = x; 41789857Sobrien } 41889857Sobrien heap->min = NULL; 41989857Sobrien for (i = 0; i < D; i++) 42089857Sobrien if (a[i] != NULL) 42189857Sobrien { 42289857Sobrien fibheap_ins_root (heap, a[i]); 42389857Sobrien if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 42489857Sobrien heap->min = a[i]; 42589857Sobrien } 42689857Sobrien} 42789857Sobrien 42889857Sobrien/* Make NODE a child of PARENT. */ 42989857Sobrienstatic void 43089857Sobrienfibheap_link (heap, node, parent) 43189857Sobrien fibheap_t heap ATTRIBUTE_UNUSED; 43289857Sobrien fibnode_t node; 43389857Sobrien fibnode_t parent; 43489857Sobrien{ 43589857Sobrien if (parent->child == NULL) 43689857Sobrien parent->child = node; 43789857Sobrien else 43889857Sobrien fibnode_insert_before (parent->child, node); 43989857Sobrien node->parent = parent; 44089857Sobrien parent->degree++; 44189857Sobrien node->mark = 0; 44289857Sobrien} 44389857Sobrien 44489857Sobrien/* Remove NODE from PARENT's child list. */ 44589857Sobrienstatic void 44689857Sobrienfibheap_cut (heap, node, parent) 44789857Sobrien fibheap_t heap; 44889857Sobrien fibnode_t node; 44989857Sobrien fibnode_t parent; 45089857Sobrien{ 45189857Sobrien fibnode_remove (node); 45289857Sobrien parent->degree--; 45389857Sobrien fibheap_ins_root (heap, node); 45489857Sobrien node->parent = NULL; 45589857Sobrien node->mark = 0; 45689857Sobrien} 45789857Sobrien 45889857Sobrienstatic void 45989857Sobrienfibheap_cascading_cut (heap, y) 46089857Sobrien fibheap_t heap; 46189857Sobrien fibnode_t y; 46289857Sobrien{ 46389857Sobrien fibnode_t z; 46489857Sobrien 46589857Sobrien while ((z = y->parent) != NULL) 46689857Sobrien { 46789857Sobrien if (y->mark == 0) 46889857Sobrien { 46989857Sobrien y->mark = 1; 47089857Sobrien return; 47189857Sobrien } 47289857Sobrien else 47389857Sobrien { 47489857Sobrien fibheap_cut (heap, y, z); 47589857Sobrien y = z; 47689857Sobrien } 47789857Sobrien } 47889857Sobrien} 47989857Sobrien 48089857Sobrienstatic void 48189857Sobrienfibnode_insert_after (a, b) 48289857Sobrien fibnode_t a; 48389857Sobrien fibnode_t b; 48489857Sobrien{ 48589857Sobrien if (a == a->right) 48689857Sobrien { 48789857Sobrien a->right = b; 48889857Sobrien a->left = b; 48989857Sobrien b->right = a; 49089857Sobrien b->left = a; 49189857Sobrien } 49289857Sobrien else 49389857Sobrien { 49489857Sobrien b->right = a->right; 49589857Sobrien a->right->left = b; 49689857Sobrien a->right = b; 49789857Sobrien b->left = a; 49889857Sobrien } 49989857Sobrien} 50089857Sobrien 50189857Sobrienstatic fibnode_t 50289857Sobrienfibnode_remove (node) 50389857Sobrien fibnode_t node; 50489857Sobrien{ 50589857Sobrien fibnode_t ret; 50689857Sobrien 50789857Sobrien if (node == node->left) 50889857Sobrien ret = NULL; 50989857Sobrien else 51089857Sobrien ret = node->left; 51189857Sobrien 51289857Sobrien if (node->parent != NULL && node->parent->child == node) 51389857Sobrien node->parent->child = ret; 51489857Sobrien 51589857Sobrien node->right->left = node->left; 51689857Sobrien node->left->right = node->right; 51789857Sobrien 51889857Sobrien node->parent = NULL; 51989857Sobrien node->left = node; 52089857Sobrien node->right = node; 52189857Sobrien 52289857Sobrien return ret; 52389857Sobrien} 524