diff options
| -rw-r--r-- | include/ChangeLog | 4 | ||||
| -rw-r--r-- | include/fibheap.h | 80 | ||||
| -rw-r--r-- | libiberty/ChangeLog | 8 | ||||
| -rw-r--r-- | libiberty/Makefile.in | 5 | ||||
| -rw-r--r-- | libiberty/fibheap.c | 552 |
5 files changed, 647 insertions, 2 deletions
diff --git a/include/ChangeLog b/include/ChangeLog index e76756b..b2b0f14 100644 --- a/include/ChangeLog +++ b/include/ChangeLog @@ -1,3 +1,7 @@ +2001-08-20 Daniel Berlin <dan@cgsoftware.com> + + * fibheap.h: New file. Fibonacci heap. + 2001-08-20 Andrew Cagney <ac131313@redhat.com> * floatformat.h (floatformat_arm_ext): Document as deprecated. diff --git a/include/fibheap.h b/include/fibheap.h new file mode 100644 index 0000000..16db65e --- /dev/null +++ b/include/fibheap.h @@ -0,0 +1,80 @@ +/* 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, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +/* Fibonacci heaps are somewhat complex, but, there's an + article in DDJ on them that explains them pretty well: + + http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms + + Introduction to algorithms by Corman and Rivest also goes over + them. + + The original paper that introduced them is "Fibonacci heaps and their + uses in improved network optimization algorithms" by Tarjan and + Fredman (JACM 34(3), July 1987). + + Amortized and real worst case time for operations: + + ExtractMin: O(lg n) amortized. O(n) worst case. + DecreaseKey: O(1) amortized. O(lg n) worst case. + Insert: O(2) amortized. O(1) actual. + Union: O(1) amortized. O(1) actual. + + +*/ + +#ifndef _FIBHEAP_H_ +#define _FIBHEAP_H_ + +#include <ansidecl.h> + +typedef struct fibheap +{ + size_t nodes; + struct fibnode *min; + struct fibnode *root; +} *fibheap_t; +typedef long fibheapkey_t; +typedef struct fibnode +{ + struct fibnode *parent; + struct fibnode *child; + struct fibnode *left; + struct fibnode *right; + unsigned int degree : sizeof(size_t) * CHAR_BIT - 2; + unsigned int mark:1; + fibheapkey_t key; + void *data; +} *fibnode_t; + +extern fibheap_t fibheap_new PARAMS ((void)); +extern fibnode_t fibheap_insert PARAMS ((fibheap_t, fibheapkey_t, void *)); +extern int fibheap_empty PARAMS ((fibheap_t)); +extern fibheapkey_t fibheap_min_key PARAMS ((fibheap_t)); +extern fibheapkey_t fibheap_replace_key PARAMS ((fibheap_t, fibnode_t, fibheapkey_t)); +extern void *fibheap_replace_key_data PARAMS ((fibheap_t, fibnode_t, fibheapkey_t, void *)); +extern void *fibheap_extract_min PARAMS ((fibheap_t)); +extern void *fibheap_min PARAMS ((fibheap_t)); +extern void *fibheap_replace_data PARAMS ((fibheap_t, fibnode_t, void *)); +extern void *fibheap_delete_node PARAMS ((fibheap_t, fibnode_t)); +extern void fibheap_delete PARAMS ((fibheap_t)); +extern fibheap_t fibheap_union PARAMS ((fibheap_t, fibheap_t)); +#endif /* _FIBHEAP_H_ */ diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index 0b3dd67..d910b7f 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,11 @@ +2001-08-20 Daniel Berlin <dan@cgsoftware.com> + + * fibheap.c: New file. Fibonacci heap. + + * Makefile.in (CFILES): Add fibheap.c. + (REQUIRED_OFILES): Add fibheap.o. + (fibheap.o): Add dependencies for fibheap.o. + 2001-08-20 Andrew Cagney <ac131313@redhat.com> * floatformat.c (floatformat_m88110_ext): Remove #ifdef diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in index 226f7d1..41ea945 100644 --- a/libiberty/Makefile.in +++ b/libiberty/Makefile.in @@ -133,7 +133,7 @@ CFILES = asprintf.c alloca.c argv.c atexit.c basename.c bcmp.c bcopy.c \ strncasecmp.c strchr.c strdup.c strerror.c strncmp.c strrchr.c \ strsignal.c strstr.c strtod.c strtol.c strtoul.c tmpnam.c vasprintf.c \ vfork.c vfprintf.c vprintf.c vsprintf.c waitpid.c xatexit.c xexit.c \ - xmalloc.c xmemdup.c xstrdup.c xstrerror.c ternary.c + xmalloc.c xmemdup.c xstrdup.c xstrerror.c ternary.c fibheap.c # These are always included in the library. REQUIRED_OFILES = argv.o alloca.o choose-temp.o concat.o cplus-dem.o \ @@ -142,7 +142,7 @@ REQUIRED_OFILES = argv.o alloca.o choose-temp.o concat.o cplus-dem.o \ md5.o make-temp-file.o objalloc.o \ obstack.o partition.o pexecute.o regex.o safe-ctype.o sort.o spaces.o \ splay-tree.o strerror.o strsignal.o xatexit.o xexit.o xmalloc.o \ - xmemdup.o xstrdup.o xstrerror.o ternary.o + xmemdup.o xstrdup.o xstrerror.o ternary.o fibheap.o $(TARGETLIB): $(REQUIRED_OFILES) $(EXTRA_OFILES) $(LIBOBJS) -rm -f $(TARGETLIB) @@ -265,6 +265,7 @@ cplus-dem.o: config.h $(INCDIR)/demangle.h cp-demangle.o: config.h $(INCDIR)/dyn-string.h $(INCDIR)/demangle.h dyn-string.o: config.h $(INCDIR)/dyn-string.h fdmatch.o: $(INCDIR)/libiberty.h +fibheap.o: $(INCDIR)/libiberty.h $(INCDIR)/fibheap.h fnmatch.o: config.h $(INCDIR)/fnmatch.h getcwd.o: config.h getopt.o: config.h $(INCDIR)/getopt.h diff --git a/libiberty/fibheap.c b/libiberty/fibheap.c new file mode 100644 index 0000000..3c8b347 --- /dev/null +++ b/libiberty/fibheap.c @@ -0,0 +1,552 @@ + +/* 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, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +/* Fibonacci heaps */ +#include <limits.h> +#include <stdlib.h> +#include "libiberty.h" +#include "fibheap.h" + + +static void fibheap_init PARAMS ((fibheap_t)); +static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t)); +static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t)); +static void fibheap_consolidate PARAMS ((fibheap_t)); +static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t)); +static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t)); +static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t)); +static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t)); +static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t)); +static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, fibnode_t)); +static fibnode_t fibnode_new PARAMS ((void)); +static void fibnode_init PARAMS ((fibnode_t)); +static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t)); +#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) +static fibnode_t fibnode_remove PARAMS ((fibnode_t)); + +/* Create a new fibonacci heap. */ +fibheap_t +fibheap_new () +{ + fibheap_t result; + + if ((result = xmalloc (sizeof (*result))) == NULL) + return NULL; + + fibheap_init (result); + + return result; +} + +/* Initialize the passed in fibonacci heap. */ +static void +fibheap_init (heap) + fibheap_t heap; +{ + heap->nodes = 0; + heap->min = NULL; + heap->root = NULL; +} + +/* Insert DATA, with priority KEY, into HEAP. */ +fibnode_t +fibheap_insert (heap, key, data) + fibheap_t heap; + fibheapkey_t key; + void *data; +{ + fibnode_t node; + /* Create the new node, if we fail, return NULL. */ + if ((node = fibnode_new ()) == NULL) + return NULL; + /* 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 (heap) + 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 (heap) + 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 (heapa, heapb) + fibheap_t heapa; + fibheap_t heapb; +{ + fibnode_t temp; + + /* If one of the heaps is empty, the union is just the other heap. */ + if (heapa->root == NULL || heapb->root == NULL) + { + if (heapa->root == NULL) + { + free (heapa); + return heapb; + } + else + { + free (heapb); + return heapa; + } + } + /* Merge them to the next nodes on the opposite chain. */ + heapa->root->left->right = heapb->root; + heapb->root->left->right = heapa->root; + temp = heapa->root->left; + heapa->root->left = heapb->root->left; + heapb->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 (heap) + fibheap_t heap; +{ + fibnode_t z; + void *ret; + + 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 the DATA associated with NODE. */ +void * +fibheap_replace_data (heap, node, 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 (heap, node, key) + fibheap_t heap; + fibnode_t node; + fibheapkey_t key; +{ + int ret; + + ret = node->key; + (void) fibheap_replace_key_data (heap, node, key, node->data); + + return ret; +} + +/* Replace both the KEY and the DATA associated with NODE. */ +void * +fibheap_replace_key_data (heap, node, key, data) + fibheap_t heap; + fibnode_t node; + fibheapkey_t key; + void *data; +{ + void *odata; + int 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; +} + +/* Delete NODE from HEAP. */ +void * +fibheap_delete_node (heap, node) + fibheap_t heap; + fibnode_t node; +{ + void *k; + /* To perform delete, we just make it the min key, and extract. */ + k = node->data; + fibheap_replace_key (heap, node, LONG_MIN); + fibheap_extract_min (heap); + + return k; +} + +/* Delete HEAP. */ +void +fibheap_delete (heap) + fibheap_t heap; +{ + while (heap->min != NULL) + free (fibheap_extr_min_node (heap)); + + free (heap); +} + +/* Determine if HEAP is empty. */ +int +fibheap_empty (heap) + fibheap_t heap; +{ + return heap->nodes == 0; +} + + +/* Extract the minimum node of the heap. */ +static fibnode_t +fibheap_extr_min_node (heap) + fibheap_t heap; +{ + fibnode_t ret; + fibnode_t x, y, orig; + + ret = heap->min; + + orig = NULL; + /* 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; x != orig && x != NULL;) + { + if (orig == NULL) + orig = x; + y = x->right; + x->parent = NULL; + fibheap_ins_root (heap, x); + x = y; + } + /* 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 (heap, node) + 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 (heap, node) + 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 (heap) + 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 (heap, node, parent) + 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 (heap, node, parent) + 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 (heap, y) + 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 fibnode_t +fibnode_new () +{ + fibnode_t e; + + if ((e = xmalloc (sizeof *e)) == NULL) + return NULL; + + fibnode_init (e); + + return e; +} + +static void +fibnode_init (node) + fibnode_t node; +{ + node->degree = 0; + node->mark = 0; + node->parent = NULL; + node->child = NULL; + node->left = node; + node->right = node; + node->data = NULL; +} + +static void +fibnode_insert_after (a, b) + 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 (node) + 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; +} + +static int +fibheap_compare (heap, a, b) + 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 int +fibheap_comp_data (heap, key, data, b) + 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); +} |