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

Stable _LoserTree implementation. More...

#include <parallel/losertree.h>

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

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

Private Types
typedef _LoserTreePointerBase < _Tp, _Compare >	_Base

Additional Inherited Members
Protected Attributes inherited from __gnu_parallel::_LoserTreePointerBase< _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::_LoserTreePointer< __stable, _Tp, _Compare >

Stable _LoserTree implementation.

The unstable variant is implemented using partial instantiation below.

Member Typedef Documentation

template<bool __stable, typename _Tp , typename _Compare >

typedef _LoserTreePointerBase<_Tp, _Compare> __gnu_parallel::_LoserTreePointer< __stable, _Tp, _Compare >::_Base

private

Constructor & Destructor Documentation

template<bool __stable, typename _Tp , typename _Compare >

__gnu_parallel::_LoserTreePointer< __stable, _Tp, _Compare >::_LoserTreePointer ( unsigned int  __k, _Compare  __comp = std::less<_Tp>()  )

inline

      : _Base::_LoserTreePointerBase(__k, __comp)
      { }

Member Function Documentation

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTreePointer< __stable, _Tp, _Compare >::__delete_min_insert ( const _Tp &  __key, bool  __sup  )

inline

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

    const _Tp* __keyp = &__key;
    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 __source.
        if ((__sup && (!_M_losers[__pos]._M_sup
               || _M_losers[__pos]._M_source < __source))
        || (!__sup && !_M_losers[__pos]._M_sup &&
            ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
             || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
             && _M_losers[__pos]._M_source < __source))))
          {
        // The other one is smaller.
        std::swap(_M_losers[__pos]._M_sup, __sup);
        std::swap(_M_losers[__pos]._M_source, __source);
        std::swap(_M_losers[__pos]._M_keyp, __keyp);
          }
      }

    _M_losers[0]._M_sup = __sup;
    _M_losers[0]._M_source = __source;
    _M_losers[0]._M_keyp = __keyp;
      }

template<bool __stable, typename _Tp , typename _Compare >

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

inline

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

template<bool __stable, typename _Tp , typename _Compare >

unsigned int __gnu_parallel::_LoserTreePointer< __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_losers[__right]._M_sup
        || (!_M_losers[__left]._M_sup
            && !_M_comp(*_M_losers[__right]._M_keyp,
                *_M_losers[__left]._M_keyp)))
          {
        // 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