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

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_ */