| /* A Fibonacci heap datatype. |
| Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. |
| Contributed by Daniel Berlin (dan@cgsoftware.com). |
| |
| This file is part of GNU CC. |
| |
| GNU CC is free software; you can redistribute it and/or modify it |
| under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GNU CC is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GNU CC; see the file COPYING. If not, write to |
| the Free Software Foundation, 51 Franklin Street - Fifth Floor, |
| Boston, MA 02110-1301, USA. */ |
| |
| #ifdef HAVE_CONFIG_H |
| #include "config.h" |
| #endif |
| #ifdef HAVE_LIMITS_H |
| #include <limits.h> |
| #endif |
| #ifdef HAVE_STDLIB_H |
| #include <stdlib.h> |
| #endif |
| #ifdef HAVE_STRING_H |
| #include <string.h> |
| #endif |
| #include "libiberty.h" |
| #include "fibheap.h" |
| |
| |
| #define FIBHEAPKEY_MIN LONG_MIN |
| |
| static void fibheap_ins_root (fibheap_t, fibnode_t); |
| static void fibheap_rem_root (fibheap_t, fibnode_t); |
| static void fibheap_consolidate (fibheap_t); |
| static void fibheap_link (fibheap_t, fibnode_t, fibnode_t); |
| static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); |
| static void fibheap_cascading_cut (fibheap_t, fibnode_t); |
| static fibnode_t fibheap_extr_min_node (fibheap_t); |
| static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); |
| static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); |
| static fibnode_t fibnode_new (void); |
| static void fibnode_insert_after (fibnode_t, fibnode_t); |
| #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) |
| static fibnode_t fibnode_remove (fibnode_t); |
| |
| |
| /* Create a new fibonacci heap. */ |
| fibheap_t |
| fibheap_new (void) |
| { |
| return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); |
| } |
| |
| /* Create a new fibonacci heap node. */ |
| static fibnode_t |
| fibnode_new (void) |
| { |
| fibnode_t node; |
| |
| node = (fibnode_t) xcalloc (1, sizeof *node); |
| node->left = node; |
| node->right = node; |
| |
| return node; |
| } |
| |
| static inline int |
| fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) |
| { |
| if (a->key < b->key) |
| return -1; |
| if (a->key > b->key) |
| return 1; |
| return 0; |
| } |
| |
| static inline int |
| fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) |
| { |
| struct fibnode a; |
| |
| a.key = key; |
| a.data = data; |
| |
| return fibheap_compare (heap, &a, b); |
| } |
| |
| /* Insert DATA, with priority KEY, into HEAP. */ |
| fibnode_t |
| fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) |
| { |
| fibnode_t node; |
| |
| /* Create the new node. */ |
| node = fibnode_new (); |
| |
| /* Set the node's data. */ |
| node->data = data; |
| node->key = key; |
| |
| /* Insert it into the root list. */ |
| fibheap_ins_root (heap, node); |
| |
| /* If their was no minimum, or this key is less than the min, |
| it's the new min. */ |
| if (heap->min == NULL || node->key < heap->min->key) |
| heap->min = node; |
| |
| heap->nodes++; |
| |
| return node; |
| } |
| |
| /* Return the data of the minimum node (if we know it). */ |
| void * |
| fibheap_min (fibheap_t heap) |
| { |
| /* If there is no min, we can't easily return it. */ |
| if (heap->min == NULL) |
| return NULL; |
| return heap->min->data; |
| } |
| |
| /* Return the key of the minimum node (if we know it). */ |
| fibheapkey_t |
| fibheap_min_key (fibheap_t heap) |
| { |
| /* If there is no min, we can't easily return it. */ |
| if (heap->min == NULL) |
| return 0; |
| return heap->min->key; |
| } |
| |
| /* Union HEAPA and HEAPB into a new heap. */ |
| fibheap_t |
| fibheap_union (fibheap_t heapa, fibheap_t heapb) |
| { |
| fibnode_t a_root, b_root, temp; |
| |
| /* If one of the heaps is empty, the union is just the other heap. */ |
| if ((a_root = heapa->root) == NULL) |
| { |
| free (heapa); |
| return heapb; |
| } |
| if ((b_root = heapb->root) == NULL) |
| { |
| free (heapb); |
| return heapa; |
| } |
| |
| /* Merge them to the next nodes on the opposite chain. */ |
| a_root->left->right = b_root; |
| b_root->left->right = a_root; |
| temp = a_root->left; |
| a_root->left = b_root->left; |
| b_root->left = temp; |
| heapa->nodes += heapb->nodes; |
| |
| /* And set the new minimum, if it's changed. */ |
| if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) |
| heapa->min = heapb->min; |
| |
| free (heapb); |
| return heapa; |
| } |
| |
| /* Extract the data of the minimum node from HEAP. */ |
| void * |
| fibheap_extract_min (fibheap_t heap) |
| { |
| fibnode_t z; |
| void *ret = NULL; |
| |
| /* If we don't have a min set, it means we have no nodes. */ |
| if (heap->min != NULL) |
| { |
| /* Otherwise, extract the min node, free the node, and return the |
| node's data. */ |
| z = fibheap_extr_min_node (heap); |
| ret = z->data; |
| free (z); |
| } |
| |
| return ret; |
| } |
| |
| /* Replace both the KEY and the DATA associated with NODE. */ |
| void * |
| fibheap_replace_key_data (fibheap_t heap, fibnode_t node, |
| fibheapkey_t key, void *data) |
| { |
| void *odata; |
| fibheapkey_t okey; |
| fibnode_t y; |
| |
| /* If we wanted to, we could actually do a real increase by redeleting and |
| inserting. However, this would require O (log n) time. So just bail out |
| for now. */ |
| if (fibheap_comp_data (heap, key, data, node) > 0) |
| return NULL; |
| |
| odata = node->data; |
| okey = node->key; |
| node->data = data; |
| node->key = key; |
| y = node->parent; |
| |
| /* Short-circuit if the key is the same, as we then don't have to |
| do anything. Except if we're trying to force the new node to |
| be the new minimum for delete. */ |
| if (okey == key && okey != FIBHEAPKEY_MIN) |
| return odata; |
| |
| /* These two compares are specifically <= 0 to make sure that in the case |
| of equality, a node we replaced the data on, becomes the new min. This |
| is needed so that delete's call to extractmin gets the right node. */ |
| if (y != NULL && fibheap_compare (heap, node, y) <= 0) |
| { |
| fibheap_cut (heap, node, y); |
| fibheap_cascading_cut (heap, y); |
| } |
| |
| if (fibheap_compare (heap, node, heap->min) <= 0) |
| heap->min = node; |
| |
| return odata; |
| } |
| |
| /* Replace the DATA associated with NODE. */ |
| void * |
| fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) |
| { |
| return fibheap_replace_key_data (heap, node, node->key, data); |
| } |
| |
| /* Replace the KEY associated with NODE. */ |
| fibheapkey_t |
| fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) |
| { |
| int okey = node->key; |
| fibheap_replace_key_data (heap, node, key, node->data); |
| return okey; |
| } |
| |
| /* Delete NODE from HEAP. */ |
| void * |
| fibheap_delete_node (fibheap_t heap, fibnode_t node) |
| { |
| void *ret = node->data; |
| |
| /* To perform delete, we just make it the min key, and extract. */ |
| fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); |
| if (node != heap->min) |
| { |
| fprintf (stderr, "Can't force minimum on fibheap.\n"); |
| abort (); |
| } |
| fibheap_extract_min (heap); |
| |
| return ret; |
| } |
| |
| /* Delete HEAP. */ |
| void |
| fibheap_delete (fibheap_t heap) |
| { |
| while (heap->min != NULL) |
| free (fibheap_extr_min_node (heap)); |
| |
| free (heap); |
| } |
| |
| /* Determine if HEAP is empty. */ |
| int |
| fibheap_empty (fibheap_t heap) |
| { |
| return heap->nodes == 0; |
| } |
| |
| /* Extract the minimum node of the heap. */ |
| static fibnode_t |
| fibheap_extr_min_node (fibheap_t heap) |
| { |
| fibnode_t ret = heap->min; |
| fibnode_t x, y, orig; |
| |
| /* Attach the child list of the minimum node to the root list of the heap. |
| If there is no child list, we don't do squat. */ |
| for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) |
| { |
| if (orig == NULL) |
| orig = x; |
| y = x->right; |
| x->parent = NULL; |
| fibheap_ins_root (heap, x); |
| } |
| |
| /* Remove the old root. */ |
| fibheap_rem_root (heap, ret); |
| heap->nodes--; |
| |
| /* If we are left with no nodes, then the min is NULL. */ |
| if (heap->nodes == 0) |
| heap->min = NULL; |
| else |
| { |
| /* Otherwise, consolidate to find new minimum, as well as do the reorg |
| work that needs to be done. */ |
| heap->min = ret->right; |
| fibheap_consolidate (heap); |
| } |
| |
| return ret; |
| } |
| |
| /* Insert NODE into the root list of HEAP. */ |
| static void |
| fibheap_ins_root (fibheap_t heap, fibnode_t node) |
| { |
| /* If the heap is currently empty, the new node becomes the singleton |
| circular root list. */ |
| if (heap->root == NULL) |
| { |
| heap->root = node; |
| node->left = node; |
| node->right = node; |
| return; |
| } |
| |
| /* Otherwise, insert it in the circular root list between the root |
| and it's right node. */ |
| fibnode_insert_after (heap->root, node); |
| } |
| |
| /* Remove NODE from the rootlist of HEAP. */ |
| static void |
| fibheap_rem_root (fibheap_t heap, fibnode_t node) |
| { |
| if (node->left == node) |
| heap->root = NULL; |
| else |
| heap->root = fibnode_remove (node); |
| } |
| |
| /* Consolidate the heap. */ |
| static void |
| fibheap_consolidate (fibheap_t heap) |
| { |
| fibnode_t a[1 + 8 * sizeof (long)]; |
| fibnode_t w; |
| fibnode_t y; |
| fibnode_t x; |
| int i; |
| int d; |
| int D; |
| |
| D = 1 + 8 * sizeof (long); |
| |
| memset (a, 0, sizeof (fibnode_t) * D); |
| |
| while ((w = heap->root) != NULL) |
| { |
| x = w; |
| fibheap_rem_root (heap, w); |
| d = x->degree; |
| while (a[d] != NULL) |
| { |
| y = a[d]; |
| if (fibheap_compare (heap, x, y) > 0) |
| { |
| fibnode_t temp; |
| temp = x; |
| x = y; |
| y = temp; |
| } |
| fibheap_link (heap, y, x); |
| a[d] = NULL; |
| d++; |
| } |
| a[d] = x; |
| } |
| heap->min = NULL; |
| for (i = 0; i < D; i++) |
| if (a[i] != NULL) |
| { |
| fibheap_ins_root (heap, a[i]); |
| if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) |
| heap->min = a[i]; |
| } |
| } |
| |
| /* Make NODE a child of PARENT. */ |
| static void |
| fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, |
| fibnode_t node, fibnode_t parent) |
| { |
| if (parent->child == NULL) |
| parent->child = node; |
| else |
| fibnode_insert_before (parent->child, node); |
| node->parent = parent; |
| parent->degree++; |
| node->mark = 0; |
| } |
| |
| /* Remove NODE from PARENT's child list. */ |
| static void |
| fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) |
| { |
| fibnode_remove (node); |
| parent->degree--; |
| fibheap_ins_root (heap, node); |
| node->parent = NULL; |
| node->mark = 0; |
| } |
| |
| static void |
| fibheap_cascading_cut (fibheap_t heap, fibnode_t y) |
| { |
| fibnode_t z; |
| |
| while ((z = y->parent) != NULL) |
| { |
| if (y->mark == 0) |
| { |
| y->mark = 1; |
| return; |
| } |
| else |
| { |
| fibheap_cut (heap, y, z); |
| y = z; |
| } |
| } |
| } |
| |
| static void |
| fibnode_insert_after (fibnode_t a, fibnode_t b) |
| { |
| if (a == a->right) |
| { |
| a->right = b; |
| a->left = b; |
| b->right = a; |
| b->left = a; |
| } |
| else |
| { |
| b->right = a->right; |
| a->right->left = b; |
| a->right = b; |
| b->left = a; |
| } |
| } |
| |
| static fibnode_t |
| fibnode_remove (fibnode_t node) |
| { |
| fibnode_t ret; |
| |
| if (node == node->left) |
| ret = NULL; |
| else |
| ret = node->left; |
| |
| if (node->parent != NULL && node->parent->child == node) |
| node->parent->child = ret; |
| |
| node->right->left = node->left; |
| node->left->right = node->right; |
| |
| node->parent = NULL; |
| node->left = node; |
| node->right = node; |
| |
| return ret; |
| } |