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

Stable unguarded _LoserTree variant storing pointers. More...

#include <parallel/losertree.h>

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

Public Member Functions
	_LoserTreePointerUnguarded (unsigned int __k, const _Tp &__sentinel, _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::_LoserTreePointerUnguardedBase< _Tp, _Compare >
	_LoserTreePointerUnguardedBase (unsigned int __k, const _Tp &__sentinel, _Compare __comp=std::less< _Tp >())
	~_LoserTreePointerUnguardedBase ()
int	__get_min_source ()
void	__insert_start (const _Tp &__key, int __source, bool)

Private Types
typedef _LoserTreePointerUnguardedBase < _Tp, _Compare >	_Base

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

Stable unguarded _LoserTree variant storing pointers.

Unstable variant is implemented below using partial specialization.

Member Typedef Documentation

template<bool __stable, typename _Tp , typename _Compare >

typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> __gnu_parallel::_LoserTreePointerUnguarded< __stable, _Tp, _Compare >::_Base

private

Constructor & Destructor Documentation

template<bool __stable, typename _Tp , typename _Compare >

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

inline

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

Member Function Documentation

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTreePointerUnguarded< __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 _M_source.
        if (_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_source, __source);
        std::swap(_M_losers[__pos]._M_keyp, __keyp);
          }
      }

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

template<bool __stable, typename _Tp , typename _Compare >

void __gnu_parallel::_LoserTreePointerUnguarded< __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::_LoserTreePointerUnguarded< __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_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