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 19218822Sdimthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20218822SdimBoston, MA 02110-1301, 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 40218822Sdimstatic void fibheap_ins_root (fibheap_t, fibnode_t); 41218822Sdimstatic void fibheap_rem_root (fibheap_t, fibnode_t); 42218822Sdimstatic void fibheap_consolidate (fibheap_t); 43218822Sdimstatic void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 44218822Sdimstatic void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 45218822Sdimstatic void fibheap_cascading_cut (fibheap_t, fibnode_t); 46218822Sdimstatic fibnode_t fibheap_extr_min_node (fibheap_t); 47218822Sdimstatic int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 48218822Sdimstatic int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 49218822Sdimstatic fibnode_t fibnode_new (void); 50218822Sdimstatic void fibnode_insert_after (fibnode_t, fibnode_t); 5189857Sobrien#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 52218822Sdimstatic fibnode_t fibnode_remove (fibnode_t); 5389857Sobrien 5489857Sobrien 5589857Sobrien/* Create a new fibonacci heap. */ 5689857Sobrienfibheap_t 57218822Sdimfibheap_new (void) 5889857Sobrien{ 5989857Sobrien return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 6089857Sobrien} 6189857Sobrien 6289857Sobrien/* Create a new fibonacci heap node. */ 6389857Sobrienstatic fibnode_t 64218822Sdimfibnode_new (void) 6589857Sobrien{ 6689857Sobrien fibnode_t node; 6789857Sobrien 68130561Sobrien node = (fibnode_t) xcalloc (1, sizeof *node); 6989857Sobrien node->left = node; 7089857Sobrien node->right = node; 7189857Sobrien 7289857Sobrien return node; 7389857Sobrien} 7489857Sobrien 7589857Sobrienstatic inline int 76218822Sdimfibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 7789857Sobrien{ 7889857Sobrien if (a->key < b->key) 7989857Sobrien return -1; 8089857Sobrien if (a->key > b->key) 8189857Sobrien return 1; 8289857Sobrien return 0; 8389857Sobrien} 8489857Sobrien 8589857Sobrienstatic inline int 86218822Sdimfibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 8789857Sobrien{ 8889857Sobrien struct fibnode a; 8989857Sobrien 9089857Sobrien a.key = key; 9189857Sobrien a.data = data; 9289857Sobrien 9389857Sobrien return fibheap_compare (heap, &a, b); 9489857Sobrien} 9589857Sobrien 9689857Sobrien/* Insert DATA, with priority KEY, into HEAP. */ 9789857Sobrienfibnode_t 98218822Sdimfibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 9989857Sobrien{ 10089857Sobrien fibnode_t node; 10189857Sobrien 10289857Sobrien /* Create the new node. */ 10389857Sobrien node = fibnode_new (); 10489857Sobrien 10589857Sobrien /* Set the node's data. */ 10689857Sobrien node->data = data; 10789857Sobrien node->key = key; 10889857Sobrien 10989857Sobrien /* Insert it into the root list. */ 11089857Sobrien fibheap_ins_root (heap, node); 11189857Sobrien 11289857Sobrien /* If their was no minimum, or this key is less than the min, 11389857Sobrien it's the new min. */ 11489857Sobrien if (heap->min == NULL || node->key < heap->min->key) 11589857Sobrien heap->min = node; 11689857Sobrien 11789857Sobrien heap->nodes++; 11889857Sobrien 11989857Sobrien return node; 12089857Sobrien} 12189857Sobrien 12289857Sobrien/* Return the data of the minimum node (if we know it). */ 12389857Sobrienvoid * 124218822Sdimfibheap_min (fibheap_t heap) 12589857Sobrien{ 12689857Sobrien /* If there is no min, we can't easily return it. */ 12789857Sobrien if (heap->min == NULL) 12889857Sobrien return NULL; 12989857Sobrien return heap->min->data; 13089857Sobrien} 13189857Sobrien 13289857Sobrien/* Return the key of the minimum node (if we know it). */ 13389857Sobrienfibheapkey_t 134218822Sdimfibheap_min_key (fibheap_t heap) 13589857Sobrien{ 13689857Sobrien /* If there is no min, we can't easily return it. */ 13789857Sobrien if (heap->min == NULL) 13889857Sobrien return 0; 13989857Sobrien return heap->min->key; 14089857Sobrien} 14189857Sobrien 14289857Sobrien/* Union HEAPA and HEAPB into a new heap. */ 14389857Sobrienfibheap_t 144218822Sdimfibheap_union (fibheap_t heapa, fibheap_t heapb) 14589857Sobrien{ 14689857Sobrien fibnode_t a_root, b_root, temp; 14789857Sobrien 14889857Sobrien /* If one of the heaps is empty, the union is just the other heap. */ 14989857Sobrien if ((a_root = heapa->root) == NULL) 15089857Sobrien { 15189857Sobrien free (heapa); 15289857Sobrien return heapb; 15389857Sobrien } 15489857Sobrien if ((b_root = heapb->root) == NULL) 15589857Sobrien { 15689857Sobrien free (heapb); 15789857Sobrien return heapa; 15889857Sobrien } 15989857Sobrien 16089857Sobrien /* Merge them to the next nodes on the opposite chain. */ 16189857Sobrien a_root->left->right = b_root; 16289857Sobrien b_root->left->right = a_root; 16389857Sobrien temp = a_root->left; 16489857Sobrien a_root->left = b_root->left; 16589857Sobrien b_root->left = temp; 16689857Sobrien heapa->nodes += heapb->nodes; 16789857Sobrien 16889857Sobrien /* And set the new minimum, if it's changed. */ 16989857Sobrien if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 17089857Sobrien heapa->min = heapb->min; 17189857Sobrien 17289857Sobrien free (heapb); 17389857Sobrien return heapa; 17489857Sobrien} 17589857Sobrien 17689857Sobrien/* Extract the data of the minimum node from HEAP. */ 17789857Sobrienvoid * 178218822Sdimfibheap_extract_min (fibheap_t heap) 17989857Sobrien{ 18089857Sobrien fibnode_t z; 18189857Sobrien void *ret = NULL; 18289857Sobrien 18389857Sobrien /* If we don't have a min set, it means we have no nodes. */ 18489857Sobrien if (heap->min != NULL) 18589857Sobrien { 18689857Sobrien /* Otherwise, extract the min node, free the node, and return the 18789857Sobrien node's data. */ 18889857Sobrien z = fibheap_extr_min_node (heap); 18989857Sobrien ret = z->data; 19089857Sobrien free (z); 19189857Sobrien } 19289857Sobrien 19389857Sobrien return ret; 19489857Sobrien} 19589857Sobrien 19689857Sobrien/* Replace both the KEY and the DATA associated with NODE. */ 19789857Sobrienvoid * 198218822Sdimfibheap_replace_key_data (fibheap_t heap, fibnode_t node, 199218822Sdim fibheapkey_t key, void *data) 20089857Sobrien{ 20189857Sobrien void *odata; 202130561Sobrien fibheapkey_t okey; 20389857Sobrien fibnode_t y; 20489857Sobrien 20589857Sobrien /* If we wanted to, we could actually do a real increase by redeleting and 20689857Sobrien inserting. However, this would require O (log n) time. So just bail out 20789857Sobrien for now. */ 20889857Sobrien if (fibheap_comp_data (heap, key, data, node) > 0) 20989857Sobrien return NULL; 21089857Sobrien 21189857Sobrien odata = node->data; 21289857Sobrien okey = node->key; 21389857Sobrien node->data = data; 21489857Sobrien node->key = key; 21589857Sobrien y = node->parent; 21689857Sobrien 21789857Sobrien if (okey == key) 21889857Sobrien return odata; 21989857Sobrien 22089857Sobrien /* These two compares are specifically <= 0 to make sure that in the case 22189857Sobrien of equality, a node we replaced the data on, becomes the new min. This 22289857Sobrien is needed so that delete's call to extractmin gets the right node. */ 22389857Sobrien if (y != NULL && fibheap_compare (heap, node, y) <= 0) 22489857Sobrien { 22589857Sobrien fibheap_cut (heap, node, y); 22689857Sobrien fibheap_cascading_cut (heap, y); 22789857Sobrien } 22889857Sobrien 22989857Sobrien if (fibheap_compare (heap, node, heap->min) <= 0) 23089857Sobrien heap->min = node; 23189857Sobrien 23289857Sobrien return odata; 23389857Sobrien} 23489857Sobrien 23589857Sobrien/* Replace the DATA associated with NODE. */ 23689857Sobrienvoid * 237218822Sdimfibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 23889857Sobrien{ 23989857Sobrien return fibheap_replace_key_data (heap, node, node->key, data); 24089857Sobrien} 24189857Sobrien 24289857Sobrien/* Replace the KEY associated with NODE. */ 24389857Sobrienfibheapkey_t 244218822Sdimfibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 24589857Sobrien{ 24689857Sobrien int okey = node->key; 24789857Sobrien fibheap_replace_key_data (heap, node, key, node->data); 24889857Sobrien return okey; 24989857Sobrien} 25089857Sobrien 25189857Sobrien/* Delete NODE from HEAP. */ 25289857Sobrienvoid * 253218822Sdimfibheap_delete_node (fibheap_t heap, fibnode_t node) 25489857Sobrien{ 25589857Sobrien void *ret = node->data; 25689857Sobrien 25789857Sobrien /* To perform delete, we just make it the min key, and extract. */ 25889857Sobrien fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 25989857Sobrien fibheap_extract_min (heap); 26089857Sobrien 26189857Sobrien return ret; 26289857Sobrien} 26389857Sobrien 26489857Sobrien/* Delete HEAP. */ 26589857Sobrienvoid 266218822Sdimfibheap_delete (fibheap_t heap) 26789857Sobrien{ 26889857Sobrien while (heap->min != NULL) 26989857Sobrien free (fibheap_extr_min_node (heap)); 27089857Sobrien 27189857Sobrien free (heap); 27289857Sobrien} 27389857Sobrien 27489857Sobrien/* Determine if HEAP is empty. */ 27589857Sobrienint 276218822Sdimfibheap_empty (fibheap_t heap) 27789857Sobrien{ 27889857Sobrien return heap->nodes == 0; 27989857Sobrien} 28089857Sobrien 28189857Sobrien/* Extract the minimum node of the heap. */ 28289857Sobrienstatic fibnode_t 283218822Sdimfibheap_extr_min_node (fibheap_t heap) 28489857Sobrien{ 28589857Sobrien fibnode_t ret = heap->min; 28689857Sobrien fibnode_t x, y, orig; 28789857Sobrien 28889857Sobrien /* Attach the child list of the minimum node to the root list of the heap. 28989857Sobrien If there is no child list, we don't do squat. */ 29089857Sobrien for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 29189857Sobrien { 29289857Sobrien if (orig == NULL) 29389857Sobrien orig = x; 29489857Sobrien y = x->right; 29589857Sobrien x->parent = NULL; 29689857Sobrien fibheap_ins_root (heap, x); 29789857Sobrien } 29889857Sobrien 29989857Sobrien /* Remove the old root. */ 30089857Sobrien fibheap_rem_root (heap, ret); 30189857Sobrien heap->nodes--; 30289857Sobrien 30389857Sobrien /* If we are left with no nodes, then the min is NULL. */ 30489857Sobrien if (heap->nodes == 0) 30589857Sobrien heap->min = NULL; 30689857Sobrien else 30789857Sobrien { 30889857Sobrien /* Otherwise, consolidate to find new minimum, as well as do the reorg 30989857Sobrien work that needs to be done. */ 31089857Sobrien heap->min = ret->right; 31189857Sobrien fibheap_consolidate (heap); 31289857Sobrien } 31389857Sobrien 31489857Sobrien return ret; 31589857Sobrien} 31689857Sobrien 31789857Sobrien/* Insert NODE into the root list of HEAP. */ 31889857Sobrienstatic void 319218822Sdimfibheap_ins_root (fibheap_t heap, fibnode_t node) 32089857Sobrien{ 32189857Sobrien /* If the heap is currently empty, the new node becomes the singleton 32289857Sobrien circular root list. */ 32389857Sobrien if (heap->root == NULL) 32489857Sobrien { 32589857Sobrien heap->root = node; 32689857Sobrien node->left = node; 32789857Sobrien node->right = node; 32889857Sobrien return; 32989857Sobrien } 33089857Sobrien 33189857Sobrien /* Otherwise, insert it in the circular root list between the root 33289857Sobrien and it's right node. */ 33389857Sobrien fibnode_insert_after (heap->root, node); 33489857Sobrien} 33589857Sobrien 33689857Sobrien/* Remove NODE from the rootlist of HEAP. */ 33789857Sobrienstatic void 338218822Sdimfibheap_rem_root (fibheap_t heap, fibnode_t node) 33989857Sobrien{ 34089857Sobrien if (node->left == node) 34189857Sobrien heap->root = NULL; 34289857Sobrien else 34389857Sobrien heap->root = fibnode_remove (node); 34489857Sobrien} 34589857Sobrien 34689857Sobrien/* Consolidate the heap. */ 34789857Sobrienstatic void 348218822Sdimfibheap_consolidate (fibheap_t heap) 34989857Sobrien{ 35089857Sobrien fibnode_t a[1 + 8 * sizeof (long)]; 35189857Sobrien fibnode_t w; 35289857Sobrien fibnode_t y; 35389857Sobrien fibnode_t x; 35489857Sobrien int i; 35589857Sobrien int d; 35689857Sobrien int D; 35789857Sobrien 35889857Sobrien D = 1 + 8 * sizeof (long); 35989857Sobrien 36089857Sobrien memset (a, 0, sizeof (fibnode_t) * D); 36189857Sobrien 36289857Sobrien while ((w = heap->root) != NULL) 36389857Sobrien { 36489857Sobrien x = w; 36589857Sobrien fibheap_rem_root (heap, w); 36689857Sobrien d = x->degree; 36789857Sobrien while (a[d] != NULL) 36889857Sobrien { 36989857Sobrien y = a[d]; 37089857Sobrien if (fibheap_compare (heap, x, y) > 0) 37189857Sobrien { 37289857Sobrien fibnode_t temp; 37389857Sobrien temp = x; 37489857Sobrien x = y; 37589857Sobrien y = temp; 37689857Sobrien } 37789857Sobrien fibheap_link (heap, y, x); 37889857Sobrien a[d] = NULL; 37989857Sobrien d++; 38089857Sobrien } 38189857Sobrien a[d] = x; 38289857Sobrien } 38389857Sobrien heap->min = NULL; 38489857Sobrien for (i = 0; i < D; i++) 38589857Sobrien if (a[i] != NULL) 38689857Sobrien { 38789857Sobrien fibheap_ins_root (heap, a[i]); 38889857Sobrien if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 38989857Sobrien heap->min = a[i]; 39089857Sobrien } 39189857Sobrien} 39289857Sobrien 39389857Sobrien/* Make NODE a child of PARENT. */ 39489857Sobrienstatic void 395218822Sdimfibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, 396218822Sdim fibnode_t node, fibnode_t parent) 39789857Sobrien{ 39889857Sobrien if (parent->child == NULL) 39989857Sobrien parent->child = node; 40089857Sobrien else 40189857Sobrien fibnode_insert_before (parent->child, node); 40289857Sobrien node->parent = parent; 40389857Sobrien parent->degree++; 40489857Sobrien node->mark = 0; 40589857Sobrien} 40689857Sobrien 40789857Sobrien/* Remove NODE from PARENT's child list. */ 40889857Sobrienstatic void 409218822Sdimfibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) 41089857Sobrien{ 41189857Sobrien fibnode_remove (node); 41289857Sobrien parent->degree--; 41389857Sobrien fibheap_ins_root (heap, node); 41489857Sobrien node->parent = NULL; 41589857Sobrien node->mark = 0; 41689857Sobrien} 41789857Sobrien 41889857Sobrienstatic void 419218822Sdimfibheap_cascading_cut (fibheap_t heap, fibnode_t y) 42089857Sobrien{ 42189857Sobrien fibnode_t z; 42289857Sobrien 42389857Sobrien while ((z = y->parent) != NULL) 42489857Sobrien { 42589857Sobrien if (y->mark == 0) 42689857Sobrien { 42789857Sobrien y->mark = 1; 42889857Sobrien return; 42989857Sobrien } 43089857Sobrien else 43189857Sobrien { 43289857Sobrien fibheap_cut (heap, y, z); 43389857Sobrien y = z; 43489857Sobrien } 43589857Sobrien } 43689857Sobrien} 43789857Sobrien 43889857Sobrienstatic void 439218822Sdimfibnode_insert_after (fibnode_t a, fibnode_t b) 44089857Sobrien{ 44189857Sobrien if (a == a->right) 44289857Sobrien { 44389857Sobrien a->right = b; 44489857Sobrien a->left = b; 44589857Sobrien b->right = a; 44689857Sobrien b->left = a; 44789857Sobrien } 44889857Sobrien else 44989857Sobrien { 45089857Sobrien b->right = a->right; 45189857Sobrien a->right->left = b; 45289857Sobrien a->right = b; 45389857Sobrien b->left = a; 45489857Sobrien } 45589857Sobrien} 45689857Sobrien 45789857Sobrienstatic fibnode_t 458218822Sdimfibnode_remove (fibnode_t node) 45989857Sobrien{ 46089857Sobrien fibnode_t ret; 46189857Sobrien 46289857Sobrien if (node == node->left) 46389857Sobrien ret = NULL; 46489857Sobrien else 46589857Sobrien ret = node->left; 46689857Sobrien 46789857Sobrien if (node->parent != NULL && node->parent->child == node) 46889857Sobrien node->parent->child = ret; 46989857Sobrien 47089857Sobrien node->right->left = node->left; 47189857Sobrien node->left->right = node->right; 47289857Sobrien 47389857Sobrien node->parent = NULL; 47489857Sobrien node->left = node; 47589857Sobrien node->right = node; 47689857Sobrien 47789857Sobrien return ret; 47889857Sobrien} 479