aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.2.1-5666.3/libiberty/fibheap.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.2.1-5666.3/libiberty/fibheap.c')
-rw-r--r--gcc-4.2.1-5666.3/libiberty/fibheap.c478
1 files changed, 478 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/libiberty/fibheap.c b/gcc-4.2.1-5666.3/libiberty/fibheap.c
new file mode 100644
index 000000000..c032149c0
--- /dev/null
+++ b/gcc-4.2.1-5666.3/libiberty/fibheap.c
@@ -0,0 +1,478 @@
+/* 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;
+
+ if (okey == key)
+ 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);
+ 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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-24 09:33:07 +0000