#include <fibonacci_heap.h>
Public Member Functions | |
fibonacci_heap (K global_min_key, pool_allocator *allocator=NULL) | |
~fibonacci_heap () | |
fibonacci_node_t * | insert (K key, V *data) |
bool | empty () const |
size_t | nodes () const |
K | min_key () const |
K | replace_key (fibonacci_node_t *node, K key) |
K | decrease_key (fibonacci_node_t *node, K key) |
V * | replace_key_data (fibonacci_node_t *node, K key, V *data) |
V * | extract_min (bool release=true) |
V * | min () const |
V * | replace_data (fibonacci_node_t *node, V *data) |
V * | delete_node (fibonacci_node_t *node, bool release=true) |
fibonacci_heap * | union_with (fibonacci_heap *heapb) |
Private Types | |
typedef fibonacci_node< K, V > | fibonacci_node_t |
Private Member Functions | |
fibonacci_node_t * | insert (fibonacci_node_t *node, K key, V *data) |
fibonacci_node_t * | insert_node (fibonacci_node_t *node) |
void | insert_root (fibonacci_node_t *node) |
void | cut (fibonacci_node_t *node, fibonacci_node_t *parent) |
void | cascading_cut (fibonacci_node_t *y) |
fibonacci_node_t * | extract_minimum_node () |
void | remove_root (fibonacci_node_t *node) |
void | consolidate () |
Private Attributes | |
size_t | m_nodes |
fibonacci_node_t * | m_min |
fibonacci_node_t * | m_root |
K | m_global_min_key |
pool_allocator * | m_allocator |
bool | m_own_allocator |
Friends | |
class | fibonacci_node< K, V > |
Fibonacci heap for GNU compiler. Copyright (C) 1998-2025 Free Software Foundation, Inc. Contributed by Daniel Berlin (dan@cgsoftware.com). Re-implemented in C++ by Martin Liska <mliska@suse.cz> 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 3, 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 COPYING3. If not see <http://www.gnu.org/licenses/>.
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(1) amortized. Union: O(1) amortized.
Forward definition.
Fibonacci heap class.
|
private |
|
inline |
Referenced by union_with().
|
inline |
|
private |
Process cut of node Y and do it recursivelly.
References cut(), NULL, and y.
Referenced by replace_key_data().
|
private |
Consolidate heap.
References a, fibonacci_node< K, V >::compare(), gcc_checking_assert, i, insert_root(), fibonacci_node< K, V >::m_degree, m_min, m_root, NULL, remove_root(), and y.
Referenced by extract_minimum_node().
|
private |
Remove NODE from PARENT's child list.
References insert_root(), fibonacci_node< K, V >::m_degree, fibonacci_node< K, V >::m_mark, fibonacci_node< K, V >::m_parent, NULL, and fibonacci_node< K, V >::remove().
Referenced by cascading_cut(), and replace_key_data().
|
inline |
Referenced by update_edge_key().
V * fibonacci_heap< K, V >::delete_node | ( | fibonacci_node_t * | node, |
bool | release = true ) |
Delete NODE in the heap, if RELEASE is specified memory is released.
References abort, extract_min(), fibonacci_node< K, V >::m_data, m_global_min_key, m_min, and replace_key().
Referenced by replace_key_data(), tail_duplicate(), update_callee_keys(), and update_caller_keys().
|
inline |
Referenced by inline_small_functions(), recursive_inlining(), tail_duplicate(), and vt_find_locations().
V * fibonacci_heap< K, V >::extract_min | ( | bool | release = true | ) |
Extract minimum node in the heap. Delete fibonacci node if RELEASE is true.
References extract_minimum_node(), m_allocator, fibonacci_node< K, V >::m_data, m_min, and NULL.
Referenced by delete_node(), inline_small_functions(), recursive_inlining(), and tail_duplicate().
|
private |
Extract minimum node from the heap.
References consolidate(), insert_root(), fibonacci_node< K, V >::m_child, m_min, m_nodes, fibonacci_node< K, V >::m_parent, fibonacci_node< K, V >::m_right, NULL, remove_root(), and y.
Referenced by extract_min(), and fibonacci_heap< long, basic_block_def >::~fibonacci_heap().
|
private |
Insert new NODE given by DATA associated with the key.
References insert_node(), fibonacci_node< K, V >::m_data, and fibonacci_node< K, V >::m_key.
fibonacci_node< K, V > * fibonacci_heap< K, V >::insert | ( | K | key, |
V * | data ) |
Insert new node given by KEY and DATA associated with the key.
References insert_node(), and m_allocator.
Referenced by add_new_edges_to_heap(), find_traces(), find_traces_1_round(), inline_small_functions(), lookup_recursive_calls(), tail_duplicate(), update_edge_key(), and vt_find_locations().
|
private |
Insert new NODE that has already filled key and value.
References insert_root(), fibonacci_node< K, V >::m_key, m_min, m_nodes, and NULL.
|
private |
Insert it into the root list.
References fibonacci_node< K, V >::m_left, fibonacci_node< K, V >::m_right, m_root, and NULL.
Referenced by consolidate(), cut(), extract_minimum_node(), and insert_node().
|
inline |
Referenced by inline_small_functions().
|
inline |
Referenced by inline_small_functions().
|
inline |
Referenced by vt_find_locations().
|
private |
Remove root NODE from the heap.
References fibonacci_node< K, V >::m_left, m_root, NULL, and fibonacci_node< K, V >::remove().
Referenced by consolidate(), and extract_minimum_node().
|
inline |
|
inline |
Referenced by fibonacci_heap< long, basic_block_def >::decrease_key(), and delete_node().
V * fibonacci_heap< K, V >::replace_key_data | ( | fibonacci_node_t * | node, |
K | key, | ||
V * | data ) |
For given NODE, set new KEY and DATA value.
References cascading_cut(), fibonacci_node< K, V >::compare(), fibonacci_node< K, V >::compare_data(), cut(), delete_node(), insert(), fibonacci_node< K, V >::m_data, m_global_min_key, fibonacci_node< K, V >::m_key, m_min, fibonacci_node< K, V >::m_parent, NULL, odata, and y.
Referenced by fibonacci_heap< long, basic_block_def >::replace_data(), and fibonacci_heap< long, basic_block_def >::replace_key().
fibonacci_heap< K, V > * fibonacci_heap< K, V >::union_with | ( | fibonacci_heap< K, V > * | heapb | ) |
Union the heap with HEAPB. One of the heaps is going to be deleted.
References fibonacci_node< K, V >::compare(), fibonacci_heap(), gcc_checking_assert, m_allocator, fibonacci_node< K, V >::m_left, m_min, m_nodes, fibonacci_node< K, V >::m_right, m_root, and NULL.
|
friend |
|
private |
Referenced by extract_min(), insert(), and union_with().
|
private |
Referenced by delete_node(), and replace_key_data().
|
private |
Referenced by consolidate(), delete_node(), extract_min(), extract_minimum_node(), insert_node(), replace_key_data(), and union_with().
|
private |
Referenced by extract_minimum_node(), insert_node(), and union_with().
|
private |
|
private |
Referenced by consolidate(), insert_root(), remove_root(), and union_with().