__gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare > Class Template Reference

Stable implementation of unguarded _LoserTree. More...

#include <parallel/losertree.h>

Inheritance diagram for __gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >:

Public Member Functions
	_LoserTreeUnguarded (unsigned int __k, const _Tp &__sentinel, _Compare __comp=std::less< _Tp >())
unsigned int	__init_winner (unsigned int __root)
void	__init ()
void	__delete_min_insert (_Tp __key, bool)
Public Member Functions inherited from __gnu_parallel::_LoserTreeUnguardedBase< _Tp, _Compare >
	_LoserTreeUnguardedBase (unsigned int __k, const _Tp &__sentinel, _Compare __comp=std::less< _Tp >())
	~_LoserTreeUnguardedBase ()
int	__get_min_source ()
void	__insert_start (const _Tp &__key, int __source, bool)

Private Types
typedef _LoserTreeUnguardedBase< _Tp, _Compare >	_Base

Additional Inherited Members
Protected Attributes inherited from __gnu_parallel::_LoserTreeUnguardedBase< _Tp, _Compare >
unsigned int	_M_ik
unsigned int	_M_k
unsigned int	_M_offset
_Loser *	_M_losers
_Compare	_M_comp

Detailed Description

template<bool __stable, typename _Tp, typename _Compare>
class __gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >

Stable implementation of unguarded _LoserTree.

Unstable variant is selected below with partial specialization.

Member Typedef Documentation

template<bool __stable, typename _Tp , typename _Compare >

typedef _LoserTreeUnguardedBase<_Tp, _Compare> __gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >::_Base

private

Constructor & Destructor Documentation

template<bool __stable, typename _Tp , typename _Compare >

__gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >::_LoserTreeUnguarded ( unsigned int  __k, const _Tp &  __sentinel, _Compare  __comp = std::less<_Tp>()  )

inline

      : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
      { }

Member Function Documentation

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >::__delete_min_insert ( _Tp  __key, bool    )

inline

      {
        using std::swap;
#if _GLIBCXX_ASSERTIONS
    // no dummy sequence can ever be at the top!
    _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
#endif

    int __source = _M_losers[0]._M_source;
    for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
         __pos /= 2)
      {
        // The smaller one gets promoted, ties are broken by _M_source.
        if (_M_comp(_M_losers[__pos]._M_key, __key)
            || (!_M_comp(__key, _M_losers[__pos]._M_key)
                    && _M_losers[__pos]._M_source < __source))
          {
        // The other one is smaller.
        std::swap(_M_losers[__pos]._M_source, __source);
        swap(_M_losers[__pos]._M_key, __key);
          }
      }

    _M_losers[0]._M_source = __source;
    _M_losers[0]._M_key = __key;
      }

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >::__init ( )

inline

      {
    _M_losers[0] = _M_losers[__init_winner(1)];

#if _GLIBCXX_ASSERTIONS
    // no dummy sequence can ever be at the top at the beginning
    // (0 sequences!)
    _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
#endif
      }

template<bool __stable, typename _Tp , typename _Compare >

unsigned int __gnu_parallel::_LoserTreeUnguarded< __stable, _Tp, _Compare >::__init_winner ( unsigned int  __root )

inline

      {
    if (__root >= _M_k)
      return __root;
    else
      {
        unsigned int __left = __init_winner(2 * __root);
        unsigned int __right = __init_winner(2 * __root + 1);
        if (!_M_comp(_M_losers[__right]._M_key,
             _M_losers[__left]._M_key))
          {
        // Left one is less or equal.
        _M_losers[__root] = _M_losers[__right];
        return __left;
          }
        else
          {
        // Right one is less.
        _M_losers[__root] = _M_losers[__left];
        return __right;
          }
      }
      }

---

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

• GCC4/inc/parallel/losertree.h