#include <fibonacci_heap.h>

Inheritance diagram for fibonacci_heap< K, V >:

[legend]

Collaboration diagram for fibonacci_heap< K, V >:

[legend]

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 >

Detailed Description

template<class K, class V>
class fibonacci_heap< 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.

Member Typedef Documentation

◆ fibonacci_node_t

template<class K, class V>

typedef fibonacci_node<K,V> fibonacci_heap< K, V >::fibonacci_node_t

private

Constructor & Destructor Documentation

◆ fibonacci_heap()

template<class K, class V>

fibonacci_heap< K, V >::fibonacci_heap	(	K	global_min_key,
		pool_allocator *	allocator = NULL )

inline

Referenced by union_with().

◆ ~fibonacci_heap()

template<class K, class V>

fibonacci_heap< K, V >::~fibonacci_heap ( )

inline

Member Function Documentation

◆ cascading_cut()

template<class K, class V>

void fibonacci_heap< K, V >::cascading_cut ( fibonacci_node_t * y )

private

Process cut of node Y and do it recursivelly.

References cut(), NULL, and y.

Referenced by replace_key_data().

◆ consolidate()

template<class K, class V>

void fibonacci_heap< K, V >::consolidate ( )

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().

◆ cut()

template<class K, class V>

void fibonacci_heap< K, V >::cut	(	fibonacci_node_t *	node,
		fibonacci_node_t *	parent )

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().

◆ decrease_key()

template<class K, class V>

K fibonacci_heap< K, V >::decrease_key	(	fibonacci_node_t *	node,
		K	key )

inline

Referenced by update_edge_key().

◆ delete_node()

template<class K, class V>

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().

◆ empty()

template<class K, class V>

bool fibonacci_heap< K, V >::empty ( ) const

inline

Referenced by inline_small_functions(), recursive_inlining(), tail_duplicate(), and vt_find_locations().

◆ extract_min()

template<class K, class V>

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().

◆ extract_minimum_node()

template<class K, class V>

fibonacci_node< K, V > * fibonacci_heap< K, V >::extract_minimum_node ( )

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().

◆ insert() [1/2]

template<class K, class V>

fibonacci_node< K, V > * fibonacci_heap< K, V >::insert	(	fibonacci_node_t *	node,
		K	key,
		V *	data )

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.

◆ insert() [2/2]

template<class K, class V>

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().

◆ insert_node()

template<class K, class V>

fibonacci_node< K, V > * fibonacci_heap< K, V >::insert_node ( fibonacci_node_t * node )

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.

Referenced by insert(), and insert().

◆ insert_root()

template<class K, class V>

void fibonacci_heap< K, V >::insert_root ( fibonacci_node_t * node )

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().

◆ min()

template<class K, class V>

V * fibonacci_heap< K, V >::min ( ) const

inline

Referenced by inline_small_functions().

◆ min_key()

template<class K, class V>

K fibonacci_heap< K, V >::min_key ( ) const

inline

Referenced by inline_small_functions().

◆ nodes()

template<class K, class V>

size_t fibonacci_heap< K, V >::nodes ( ) const

inline

Referenced by vt_find_locations().

◆ remove_root()

template<class K, class V>

void fibonacci_heap< K, V >::remove_root ( fibonacci_node_t * node )

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().

◆ replace_data()

template<class K, class V>

V * fibonacci_heap< K, V >::replace_data	(	fibonacci_node_t *	node,
		V *	data )

inline

◆ replace_key()

template<class K, class V>

K fibonacci_heap< K, V >::replace_key	(	fibonacci_node_t *	node,
		K	key )

inline

Referenced by fibonacci_heap< long, basic_block_def >::decrease_key(), and delete_node().

◆ replace_key_data()

template<class K, class V>

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().

◆ union_with()

template<class K, class V>

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.

Friends And Related Symbol Documentation

◆ fibonacci_node< K, V >

template<class K, class V>

friend class fibonacci_node< K, V >

friend

Field Documentation

◆ m_allocator

template<class K, class V>

pool_allocator* fibonacci_heap< K, V >::m_allocator

private

Referenced by extract_min(), insert(), and union_with().

◆ m_global_min_key

template<class K, class V>

K fibonacci_heap< K, V >::m_global_min_key

private

Referenced by delete_node(), and replace_key_data().

◆ m_min

template<class K, class V>

fibonacci_node_t* fibonacci_heap< K, V >::m_min

private

Referenced by consolidate(), delete_node(), extract_min(), extract_minimum_node(), insert_node(), replace_key_data(), and union_with().

◆ m_nodes

template<class K, class V>

size_t fibonacci_heap< K, V >::m_nodes

private

Referenced by extract_minimum_node(), insert_node(), and union_with().

◆ m_own_allocator

template<class K, class V>

bool fibonacci_heap< K, V >::m_own_allocator

private

◆ m_root

template<class K, class V>

fibonacci_node_t* fibonacci_heap< K, V >::m_root

private

Referenced by consolidate(), insert_root(), remove_root(), and union_with().

The documentation for this class was generated from the following file:

fibonacci_heap.h

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ fibonacci_node_t

Constructor & Destructor Documentation

◆ fibonacci_heap()

◆ ~fibonacci_heap()

Member Function Documentation

◆ cascading_cut()

◆ consolidate()

◆ cut()

◆ decrease_key()

◆ delete_node()

◆ empty()

◆ extract_min()

◆ extract_minimum_node()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_node()

◆ insert_root()

◆ min()

◆ min_key()

◆ nodes()

◆ remove_root()

◆ replace_data()

◆ replace_key()

◆ replace_key_data()

◆ union_with()

Friends And Related Symbol Documentation

◆ fibonacci_node< K, V >

Field Documentation

◆ m_allocator

◆ m_global_min_key

◆ m_min

◆ m_nodes

◆ m_own_allocator

◆ m_root