summaryrefslogtreecommitdiffstats
path: root/include/fibheap.h
diff options
context:
space:
mode:
authorcvs2svn <>2002-02-09 22:54:17 +0000
committercvs2svn <>2002-02-09 22:54:17 +0000
commit34124a07180b9c8c7479517436c49292cfd12dcd (patch)
tree75b8ab96fbc6007f3c2f5289a74119190b1c246c /include/fibheap.h
parent53c570dbbc783190848fb72380c42664c4a5e808 (diff)
downloadcygnal-34124a07180b9c8c7479517436c49292cfd12dcd.tar.gz
cygnal-34124a07180b9c8c7479517436c49292cfd12dcd.tar.bz2
cygnal-34124a07180b9c8c7479517436c49292cfd12dcd.zip
This commit was manufactured by cvs2svn to create branch 'binutils-binutils-2_12-branchpoint
2_12-branch'. Sprout from gdb_5_1-2001-07-29-branch 2001-07-26 14:20:06 UTC cvs2svn 'This commit was manufactured by cvs2svn to create branch' Cherrypick from master 2002-02-09 22:54:16 UTC Richard Henderson <rth@redhat.com> ' * alpha.h (R_ALPHA_BRSGP): New.': COPYING.NEWLIB ChangeLog MAINTAINERS Makefile.in config.guess config.sub configure configure.in etc/ChangeLog etc/Makefile.in gettext.m4 include/ChangeLog include/ansidecl.h include/aout/ChangeLog include/aout/aout64.h include/aout/hp300hpux.h include/bfdlink.h include/coff/ChangeLog include/coff/arm.h include/coff/external.h include/coff/internal.h include/coff/m88k.h include/coff/or32.h include/coff/ti.h include/coff/tic54x.h include/coff/xcoff.h include/demangle.h include/dis-asm.h include/dyn-string.h include/elf/ChangeLog include/elf/alpha.h include/elf/arm.h include/elf/common.h include/elf/dwarf2.h include/elf/external.h include/elf/h8.h include/elf/ia64.h include/elf/internal.h include/elf/mips.h include/elf/mmix.h include/elf/or32.h include/elf/ppc.h include/elf/sh.h include/elf/xstormy16.h include/fibheap.h include/filenames.h include/floatformat.h include/hashtab.h include/libiberty.h include/nlm/ChangeLog include/nlm/common.h include/objalloc.h include/opcode/ChangeLog include/opcode/alpha.h include/opcode/arc.h include/opcode/avr.h include/opcode/cgen.h include/opcode/d10v.h include/opcode/d30v.h include/opcode/h8300.h include/opcode/hppa.h include/opcode/i386.h include/opcode/mips.h include/opcode/mmix.h include/opcode/or32.h include/opcode/ppc.h include/opcode/tic54x.h include/opcode/v850.h include/partition.h include/safe-ctype.h include/sort.h include/splay-tree.h include/xregex.h libtool.m4 ltcf-c.sh ltcf-cxx.sh ltcf-gcj.sh ltconfig ltmain.sh symlink-tree
Diffstat (limited to 'include/fibheap.h')
-rw-r--r--include/fibheap.h81
1 files changed, 81 insertions, 0 deletions
diff --git a/include/fibheap.h b/include/fibheap.h
new file mode 100644
index 000000000..d109e4ad1
--- /dev/null
+++ b/include/fibheap.h
@@ -0,0 +1,81 @@
+/* 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 GCC.
+
+GCC 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.
+
+GCC 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 GCC; 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 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 long fibheapkey_t;
+
+typedef struct fibheap
+{
+ size_t nodes;
+ struct fibnode *min;
+ struct fibnode *root;
+} *fibheap_t;
+
+typedef struct fibnode
+{
+ struct fibnode *parent;
+ struct fibnode *child;
+ struct fibnode *left;
+ struct fibnode *right;
+ fibheapkey_t key;
+ void *data;
+ unsigned int degree : 31;
+ unsigned int mark : 1;
+} *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_ */