aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
authorDJ Delorie <dj@redhat.com>2001-08-21 15:19:19 +0000
committerDJ Delorie <dj@redhat.com>2001-08-21 15:19:19 +0000
commit8e777d6aa913078f2485deacb3b4ab2a67c4c288 (patch)
tree6f73413e4314e3cb34a38b2a7b79448a20cf2059 /include
parent410f7a12904b05a10096d42b716cd50b07d9f8c5 (diff)
downloadgdb-8e777d6aa913078f2485deacb3b4ab2a67c4c288.zip
gdb-8e777d6aa913078f2485deacb3b4ab2a67c4c288.tar.gz
gdb-8e777d6aa913078f2485deacb3b4ab2a67c4c288.tar.bz2
merge from gcc
Diffstat (limited to 'include')
-rw-r--r--include/ChangeLog4
-rw-r--r--include/fibheap.h80
2 files changed, 84 insertions, 0 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_ */