diff options
author | Ben Cheng <bccheng@google.com> | 2012-10-01 10:30:31 -0700 |
---|---|---|
committer | Ben Cheng <bccheng@google.com> | 2012-10-01 10:30:31 -0700 |
commit | 82bcbebce43f0227f506d75a5b764b6847041bae (patch) | |
tree | fe9f8597b48a430c4daeb5123e3e8eb28e6f9da9 /gcc-4.7/include/fibheap.h | |
parent | 3c052de3bb16ac53b6b6ed659ec7557eb84c7590 (diff) | |
download | toolchain_gcc-82bcbebce43f0227f506d75a5b764b6847041bae.tar.gz toolchain_gcc-82bcbebce43f0227f506d75a5b764b6847041bae.tar.bz2 toolchain_gcc-82bcbebce43f0227f506d75a5b764b6847041bae.zip |
Initial check-in of gcc 4.7.2.
Change-Id: I4a2f5a921c21741a0e18bda986d77e5f1bef0365
Diffstat (limited to 'gcc-4.7/include/fibheap.h')
-rw-r--r-- | gcc-4.7/include/fibheap.h | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/gcc-4.7/include/fibheap.h b/gcc-4.7/include/fibheap.h new file mode 100644 index 000000000..a3d09dd9d --- /dev/null +++ b/gcc-4.7/include/fibheap.h @@ -0,0 +1,95 @@ +/* A Fibonacci heap datatype. + Copyright 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2009 + 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, 51 Franklin Street - Fifth Floor, +Boston, MA 02110-1301, 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" + +#ifdef __cplusplus +extern "C" { +#endif + +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; +#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4) + __extension__ unsigned long int degree : 31; + __extension__ unsigned long int mark : 1; +#else + unsigned int degree : 31; + unsigned int mark : 1; +#endif +} *fibnode_t; + +extern fibheap_t fibheap_new (void); +extern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *); +extern int fibheap_empty (fibheap_t); +extern fibheapkey_t fibheap_min_key (fibheap_t); +extern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t, + fibheapkey_t); +extern void *fibheap_replace_key_data (fibheap_t, fibnode_t, + fibheapkey_t, void *); +extern void *fibheap_extract_min (fibheap_t); +extern void *fibheap_min (fibheap_t); +extern void *fibheap_replace_data (fibheap_t, fibnode_t, void *); +extern void *fibheap_delete_node (fibheap_t, fibnode_t); +extern void fibheap_delete (fibheap_t); +extern fibheap_t fibheap_union (fibheap_t, fibheap_t); + +#ifdef __cplusplus +} +#endif + +#endif /* _FIBHEAP_H_ */ |