Detailed Description

template<class ValTp_, class Cmp_, unsigned KNKMAX>
class stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >

Loser tree from Knuth, "Sorting and Searching", Section 5.4.1.

Parameters

KNKMAX maximum arity of loser tree, has to be a power of two

Definition at line 38 of file pq_losertree.h.

Inheritance diagram for stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >:

Collaboration diagram for stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >:

Public Types
typedef Cmp_	comparator_type

typedef value_type	Element

typedef ValTp_	value_type

Public Member Functions
	loser_tree ()

	~loser_tree ()

void	init ()

void	insert_segment (Element *target, unsigned_type length)

bool	is_sentinel (const Element &a)

bool	is_space_available () const

unsigned_type	mem_cons () const

void	multi_merge (Element begin, Element end)

void	multi_merge (Element *, unsigned_type length)

bool	not_sentinel (const Element &a)

unsigned_type	size () const

void	swap (loser_tree &obj)

Private Member Functions
void	compactTree ()

void	deallocate_segment (unsigned_type slot)

void	doubleK ()

unsigned_type	initWinner (unsigned_type root)

bool	is_segment_empty (unsigned_type slot)

void	multi_merge_k (Element *target, unsigned_type length)

void	rebuildLoserTree ()

void	update_on_insert (unsigned_type node, const Element &newKey, unsigned_type newIndex, Element winnerKey, unsigned_type winnerIndex, unsigned_type *mask)

Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Private Attributes
comparator_type	cmp

Element *	current [KNKMAX]

Element *	current_end [KNKMAX]

internal_bounded_stack < unsigned_type, KNKMAX >	free_slots

unsigned_type	k

unsigned_type	logK

unsigned_type	mem_cons_

Element *	segment [KNKMAX]

unsigned_type	segment_size [KNKMAX]

Element	sentinel

unsigned_type	size_

Member Typedef Documentation

template<class ValTp_, class Cmp_, unsigned KNKMAX>

typedef Cmp_ stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::comparator_type

Definition at line 42 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

typedef value_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::Element

Definition at line 43 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

typedef ValTp_ stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::value_type

Definition at line 41 of file pq_losertree.h.

Constructor & Destructor Documentation

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::loser_tree ( )

Definition at line 208 of file pq_losertree.h.

References stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current, stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::current_end, stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::free_slots, stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::init(), stxxl::priority_queue_local::internal_bounded_stack< Tp_, max_size_ >::push(), stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::segment, and stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::sentinel.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::~loser_tree ( )

Definition at line 463 of file pq_losertree.h.

References STXXL_VERBOSE1, and STXXL_VERBOSE2.

Member Function Documentation

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::compactTree ( )

private

Definition at line 359 of file pq_losertree.h.

References STXXL_VERBOSE3.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::deallocate_segment ( unsigned_type slot )

private

Definition at line 481 of file pq_losertree.h.

References STXXL_VERBOSE2.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::doubleK ( )

private

Definition at line 328 of file pq_losertree.h.

References STXXL_VERBOSE3.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::init ( )

Definition at line 220 of file pq_losertree.h.

Referenced by stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::loser_tree().

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::initWinner ( unsigned_type root )

private

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::insert_segment	(	Element *	target,
		unsigned_type	length
	)

Definition at line 416 of file pq_losertree.h.

References STXXL_VERBOSE2.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::is_segment_empty ( unsigned_type slot )

inlineprivate

Definition at line 683 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::is_sentinel ( const Element & a )

inline

Definition at line 157 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::is_space_available ( ) const

inline

Definition at line 197 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::mem_cons ( ) const

inline

Definition at line 195 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::multi_merge	(	Element *	begin,
		Element *	end
	)

inline

Definition at line 189 of file pq_losertree.h.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::multi_merge	(	Element *	target,
		unsigned_type	length
	)

Definition at line 506 of file pq_losertree.h.

References stxxl::priority_queue_local::merge3_iterator(), stxxl::priority_queue_local::merge4_iterator(), stxxl::priority_queue_local::merge_iterator(), and STXXL_VERBOSE3.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::multi_merge_k	(	Element *	target,
		unsigned_type	length
	)

private

template<class ValTp_, class Cmp_, unsigned KNKMAX>

bool stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::not_sentinel ( const Element & a )

inline

Definition at line 161 of file pq_losertree.h.

template<class ValTp_ , class Cmp_ , unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::rebuildLoserTree ( )

private

Definition at line 233 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

unsigned_type stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::size ( ) const

inline

Definition at line 203 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::swap ( loser_tree< ValTp_, Cmp_, KNKMAX > & obj )

inline

Definition at line 171 of file pq_losertree.h.

template<class ValTp_, class Cmp_, unsigned KNKMAX>

void stxxl::priority_queue_local::loser_tree< ValTp_, Cmp_, KNKMAX >::update_on_insert	(	unsigned_type	node,
		const Element &	newKey,
		unsigned_type	newIndex,
		Element *	winnerKey,
		unsigned_type *	winnerIndex,
		unsigned_type *	mask
	)