Classes¶

struct Loser
Internal representation of a LoserTree element.

Public Member Functions¶

int get_min_source ()
void insert_start (const T &key, int source, bool sup)
LoserTreeBase (unsigned int _k, Comparator _comp)
~LoserTreeBase ()

Protected Attributes¶

unsigned int _M_log_k
Comparator comp
bool first_insert
unsigned int ik
unsigned int k
Loser * losers
unsigned int offset

template<typename T, typename Comparator> class __gnu_parallel::LoserTreeBase< T, Comparator >¶

Guarded loser/tournament tree.

The smallest element is at the top.

Guarding is done explicitly through one flag sup per element, inf is not needed due to a better initialization routine. This is a well-performing variant.

Parameters:

Definition at line 57 of file losertree.h.

template<typename T , typename Comparator > __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase (unsigned int _k, Comparator _comp) [inline]¶

The constructor. Parameters:

Definition at line 96 of file losertree.h.

References __gnu_parallel::__log2(), __gnu_parallel::LoserTreeBase< T, Comparator >::_M_log_k, __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert, and __gnu_parallel::LoserTreeBase< T, Comparator >::losers.

template<typename T , typename Comparator > __gnu_parallel::LoserTreeBase< T, Comparator >::~LoserTreeBase () [inline]¶

The destructor.

Definition at line 119 of file losertree.h.

References __gnu_parallel::LoserTreeBase< T, Comparator >::losers.

template<typename T , typename Comparator > int __gnu_parallel::LoserTreeBase< T, Comparator >::get_min_source () [inline] Returns:¶

Definition at line 152 of file losertree.h.

References __gnu_parallel::LoserTreeBase< T, Comparator >::losers, and __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::source.

template<typename T , typename Comparator > void __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start (const T & key, int source, bool sup) [inline]¶

Initializes the sequence 'source' with the element 'key'. Parameters:

Definition at line 131 of file losertree.h.

References __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert, __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::key, __gnu_parallel::LoserTreeBase< T, Comparator >::losers, __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::source, and __gnu_parallel::LoserTreeBase< T, Comparator >::Loser::sup.

template<typename T , typename Comparator > unsigned int __gnu_parallel::LoserTreeBase< T, Comparator >::_M_log_k [protected] log_2{k}¶

Definition at line 74 of file losertree.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase().

template<typename T , typename Comparator > Comparator __gnu_parallel::LoserTreeBase< T, Comparator >::comp [protected]¶

Comparator to use.

Definition at line 80 of file losertree.h.

template<typename T , typename Comparator > bool __gnu_parallel::LoserTreeBase< T, Comparator >::first_insert [protected]¶

State flag that determines whether the LoserTree is empty. Only used for building the LoserTree.

Definition at line 87 of file losertree.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start(), and __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase().

template<typename T , typename Comparator > Loser* __gnu_parallel::LoserTreeBase< T, Comparator >::losers [protected]¶

LoserTree elements.

Definition at line 77 of file losertree.h.

Referenced by __gnu_parallel::LoserTreeBase< T, Comparator >::get_min_source(), __gnu_parallel::LoserTreeBase< T, Comparator >::insert_start(), __gnu_parallel::LoserTreeBase< T, Comparator >::LoserTreeBase(), and __gnu_parallel::LoserTreeBase< T, Comparator >::~LoserTreeBase().