diff options
author | cvs2svn <> | 2002-02-09 22:54:17 +0000 |
---|---|---|
committer | cvs2svn <> | 2002-02-09 22:54:17 +0000 |
commit | 34124a07180b9c8c7479517436c49292cfd12dcd (patch) | |
tree | 75b8ab96fbc6007f3c2f5289a74119190b1c246c /include/fibheap.h | |
parent | 53c570dbbc783190848fb72380c42664c4a5e808 (diff) | |
download | cygnal-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.h | 81 |
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_ */ |