#include <fibonacci_heap.h>

Inheritance diagram for fibonacci_heap< K, V >:

Collaboration diagram for fibonacci_heap< K, V >:

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-2024 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

References fibonacci_heap< K, V >::m_allocator, and fibonacci_heap< K, V >::m_own_allocator.

◆ ~fibonacci_heap()

template<class K , class V >

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

inline

References fibonacci_heap< K, V >::extract_minimum_node(), ggc_alloc(), fibonacci_heap< K, V >::m_allocator, fibonacci_heap< K, V >::m_min, fibonacci_heap< K, V >::m_own_allocator, NULL, and base_pool_allocator< TBlockAllocator >::remove().

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 ggc_alloc(), NULL, and y.

◆ 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, ggc_alloc(), i, fibonacci_node< K, V >::m_degree, NULL, and y.

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

◆ decrease_key()

template<class K , class V >

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

inline

References gcc_assert, ggc_alloc(), and fibonacci_heap< K, V >::replace_key().

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, ggc_alloc(), and fibonacci_node< K, V >::m_data.

Referenced by mark_bb_visited(), tail_duplicate(), update_callee_keys(), and update_caller_keys().

◆ empty()

template<class K , class V >

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

inline

References fibonacci_heap< K, V >::m_nodes.

Referenced by 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 ggc_alloc(), and NULL.

Referenced by 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 ggc_alloc(), fibonacci_node< K, V >::m_parent, fibonacci_node< K, V >::m_right, NULL, and y.

Referenced by fibonacci_heap< K, V >::~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 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.

Referenced by add_new_edges_to_heap(), find_traces(), 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 fibonacci_node< K, V >::m_key, and NULL.

◆ 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 >::insert_after(), fibonacci_node< K, V >::m_left, fibonacci_node< K, V >::m_right, and NULL.

◆ min()

template<class K , class V >

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

inline

References fibonacci_node< K, V >::m_data, fibonacci_heap< K, V >::m_min, and NULL.

◆ min_key()

template<class K , class V >

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

inline

References gcc_unreachable, fibonacci_node< K, V >::m_key, fibonacci_heap< K, V >::m_min, and NULL.

◆ nodes()

template<class K , class V >

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

inline

References fibonacci_heap< K, V >::m_nodes.

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, NULL, and fibonacci_node< K, V >::remove().

◆ replace_data()

template<class K , class V >

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

inline

References fibonacci_node< K, V >::m_key, and fibonacci_heap< K, V >::replace_key_data().

◆ replace_key()

template<class K , class V >

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

inline

References ggc_alloc(), fibonacci_node< K, V >::m_data, fibonacci_node< K, V >::m_key, and fibonacci_heap< K, V >::replace_key_data().

Referenced by fibonacci_heap< K, V >::decrease_key(), and find_traces_1_round().

◆ 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 fibonacci_node< K, V >::compare(), fibonacci_node< K, V >::compare_data(), ggc_alloc(), insert(), fibonacci_node< K, V >::m_data, fibonacci_node< K, V >::m_key, fibonacci_node< K, V >::m_parent, NULL, odata, and y.

Referenced by fibonacci_heap< K, V >::replace_data(), and fibonacci_heap< K, V >::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 gcc_checking_assert, ggc_alloc(), 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 fibonacci_heap< K, V >::fibonacci_heap(), and fibonacci_heap< K, V >::~fibonacci_heap().

◆ m_global_min_key

template<class K , class V >

K fibonacci_heap< K, V >::m_global_min_key

private

◆ m_min

template<class K , class V >

fibonacci_node_t* fibonacci_heap< K, V >::m_min

private

Referenced by fibonacci_heap< K, V >::min(), fibonacci_heap< K, V >::min_key(), and fibonacci_heap< K, V >::~fibonacci_heap().

◆ m_nodes

template<class K , class V >

size_t fibonacci_heap< K, V >::m_nodes

private

Referenced by fibonacci_heap< K, V >::empty(), and fibonacci_heap< K, V >::nodes().

◆ m_own_allocator

template<class K , class V >

bool fibonacci_heap< K, V >::m_own_allocator

private

Referenced by fibonacci_heap< K, V >::fibonacci_heap(), and fibonacci_heap< K, V >::~fibonacci_heap().

◆ m_root

template<class K , class V >

fibonacci_node_t* fibonacci_heap< K, V >::m_root

private

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