losertree.h

Go to the documentation of this file.

// -*- C++ -*-

// Copyright (C) 2007-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

// Written by Johannes Singler.

#ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
#define _GLIBCXX_PARALLEL_LOSERTREE_H 1

#include <bits/stl_algobase.h>
#include <bits/stl_function.h>
#include <parallel/features.h>
#include <parallel/base.h>

namespace __gnu_parallel
{
  template<typename _Tp, typename _Compare>
    class _LoserTreeBase
    {
    protected:
      struct _Loser
      {
    bool _M_sup;
    int _M_source;
    _Tp _M_key;
      };

      unsigned int _M_ik, _M_k, _M_offset;

      unsigned int _M_log_k;

      _Loser* _M_losers;

      _Compare _M_comp;

      bool _M_first_insert;

    public:
      _LoserTreeBase(unsigned int __k, _Compare __comp)
      : _M_comp(__comp)
      {
    _M_ik = __k;

    // Compute log_2{_M_k} for the _Loser Tree
    _M_log_k = __rd_log2(_M_ik - 1) + 1;

    // Next greater power of 2.
    _M_k = 1 << _M_log_k;
    _M_offset = _M_k;

    // Avoid default-constructing _M_losers[]._M_key
    _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
                            * sizeof(_Loser)));
    for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
      _M_losers[__i + _M_k]._M_sup = true;

    _M_first_insert = true;
      }

      ~_LoserTreeBase()
      {
    for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
      _M_losers[__i].~_Loser();
    ::operator delete(_M_losers);
      }

      void
      __insert_start(const _Tp& __key, int __source, bool __sup)
      {
    unsigned int __pos = _M_k + __source;

    if (_M_first_insert)
      {
        // Construct all keys, so we can easily destruct them.
        for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
          ::new(&(_M_losers[__i]._M_key)) _Tp(__key);
        _M_first_insert = false;
      }
    else
      _M_losers[__pos]._M_key = __key;

    _M_losers[__pos]._M_sup = __sup;
    _M_losers[__pos]._M_source = __source;
      }

      int __get_min_source()
      { return _M_losers[0]._M_source; }
    };

  template<bool __stable/* default == true */, typename _Tp,
       typename _Compare>
    class _LoserTree
    : public _LoserTreeBase<_Tp, _Compare>
    {
      typedef _LoserTreeBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;
      using _Base::_M_first_insert;

    public:
      _LoserTree(unsigned int __k, _Compare __comp)
      : _Base::_LoserTreeBase(__k, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    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_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;
          }
      }
      }

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

      // Do not pass a const reference since __key will be used as
      // local variable.
      void
      __delete_min_insert(_Tp __key, bool __sup)
      {
        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 ((__sup && (!_M_losers[__pos]._M_sup
               || _M_losers[__pos]._M_source < __source))
        || (!__sup && !_M_losers[__pos]._M_sup
            && ((_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_sup, __sup);
        std::swap(_M_losers[__pos]._M_source, __source);
        swap(_M_losers[__pos]._M_key, __key);
          }
      }

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

  template<typename _Tp, typename _Compare>
    class _LoserTree</* __stable == */false, _Tp, _Compare>
    : public _LoserTreeBase<_Tp, _Compare>
    {
      typedef _LoserTreeBase<_Tp, _Compare> _Base;
      using _Base::_M_log_k;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;
      using _Base::_M_first_insert;

    public:
      _LoserTree(unsigned int __k, _Compare __comp)
      : _Base::_LoserTreeBase(__k, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    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_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;
          }
      }
      }

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

      // Do not pass a const reference since __key will be used as local
      // variable.
      void
      __delete_min_insert(_Tp __key, bool __sup)
      {
        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.
        if (__sup || (!_M_losers[__pos]._M_sup
              && _M_comp(_M_losers[__pos]._M_key, __key)))
          {
        // The other one is smaller.
        std::swap(_M_losers[__pos]._M_sup, __sup);
        std::swap(_M_losers[__pos]._M_source, __source);
        swap(_M_losers[__pos]._M_key, __key);
          }
      }

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

  template<typename _Tp, typename _Compare>
    class _LoserTreePointerBase
    {
    protected:
      struct _Loser
      {
    bool _M_sup;
    int _M_source;
    const _Tp* _M_keyp;
      };

      unsigned int _M_ik, _M_k, _M_offset;
      _Loser* _M_losers;
      _Compare _M_comp;

    public:
      _LoserTreePointerBase(unsigned int __k,
                _Compare __comp = std::less<_Tp>())
      : _M_comp(__comp)
      {
    _M_ik = __k;

    // Next greater power of 2.
    _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
    _M_offset = _M_k;
    _M_losers = new _Loser[_M_k * 2];
    for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
      _M_losers[__i + _M_k]._M_sup = true;
      }

      ~_LoserTreePointerBase()
      { delete[] _M_losers; }

      int __get_min_source()
      { return _M_losers[0]._M_source; }

      void __insert_start(const _Tp& __key, int __source, bool __sup)
      {
    unsigned int __pos = _M_k + __source;

    _M_losers[__pos]._M_sup = __sup;
    _M_losers[__pos]._M_source = __source;
    _M_losers[__pos]._M_keyp = &__key;
      }
    };

  template<bool __stable/* default == true */, typename _Tp, typename _Compare>
    class _LoserTreePointer
    : public _LoserTreePointerBase<_Tp, _Compare>
    {
      typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;

    public:
      _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
      : _Base::_LoserTreePointerBase(__k, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    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;
          }
      }
      }

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

      void __delete_min_insert(const _Tp& __key, bool __sup)
      {
#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<typename _Tp, typename _Compare>
    class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
    : public _LoserTreePointerBase<_Tp, _Compare>
    {
      typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;

    public:
      _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
      : _Base::_LoserTreePointerBase(__k, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    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;
          }
      }
      }

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

      void __delete_min_insert(const _Tp& __key, bool __sup)
      {
#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.
        if (__sup || (!_M_losers[__pos]._M_sup
              && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
          {
        // 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<typename _Tp, typename _Compare>
    class _LoserTreeUnguardedBase
    {
    protected:
      struct _Loser
      {
    int _M_source;
    _Tp _M_key;
      };

      unsigned int _M_ik, _M_k, _M_offset;
      _Loser* _M_losers;
      _Compare _M_comp;

    public:
      _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel,
                  _Compare __comp = std::less<_Tp>())
      : _M_comp(__comp)
      {
    _M_ik = __k;

    // Next greater power of 2.
    _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
    _M_offset = _M_k;
    // Avoid default-constructing _M_losers[]._M_key
    _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
                            * sizeof(_Loser)));

        for (unsigned int __i = 0; __i < _M_k; ++__i)
          {
        ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
        _M_losers[__i]._M_source = -1;
      }
        for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
          {
        ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
        _M_losers[__i]._M_source = -1;
      }
      }

      ~_LoserTreeUnguardedBase()
      {
    for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
      _M_losers[__i].~_Loser();
    ::operator delete(_M_losers);
      }

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

      void
      __insert_start(const _Tp& __key, int __source, bool)
      {
    unsigned int __pos = _M_k + __source;

    ::new(&(_M_losers[__pos]._M_key)) _Tp(__key);
    _M_losers[__pos]._M_source = __source;
      }
    };

  template<bool __stable/* default == true */, typename _Tp, typename _Compare>
    class _LoserTreeUnguarded
    : public _LoserTreeUnguardedBase<_Tp, _Compare>
    {
      typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;

  public:
      _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
              _Compare __comp = std::less<_Tp>())
      : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    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;
          }
      }
      }

      void
      __init()
      {
    _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
      }

      // Do not pass a const reference since __key will be used as
      // local variable.
      void
      __delete_min_insert(_Tp __key, bool)
      {
        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<typename _Tp, typename _Compare>
    class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare>
    : public _LoserTreeUnguardedBase<_Tp, _Compare>
    {
      typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;

    public:
      _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
              _Compare __comp = std::less<_Tp>())
      : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    if (__root >= _M_k)
      return __root;
    else
      {
        unsigned int __left = __init_winner(2 * __root);
        unsigned int __right = __init_winner(2 * __root + 1);

#if _GLIBCXX_ASSERTIONS
        // If __left one is sentinel then __right one must be, too.
        if (_M_losers[__left]._M_source == -1)
          _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
#endif

        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;
          }
      }
      }

      void
      __init()
      {
    _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
      }

      // Do not pass a const reference since __key will be used as
      // local variable.
      void
      __delete_min_insert(_Tp __key, bool)
      {
        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.
        if (_M_comp(_M_losers[__pos]._M_key, __key))
          {
        // 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<typename _Tp, typename _Compare>
    class _LoserTreePointerUnguardedBase
    {
    protected:
      struct _Loser
      {
    int _M_source;
    const _Tp* _M_keyp;
      };

      unsigned int _M_ik, _M_k, _M_offset;
      _Loser* _M_losers;
      _Compare _M_comp;

    public:

      _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
                     _Compare __comp = std::less<_Tp>())
      : _M_comp(__comp)
      {
    _M_ik = __k;

    // Next greater power of 2.
    _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
    _M_offset = _M_k;
    // Avoid default-constructing _M_losers[]._M_key
    _M_losers = new _Loser[2 * _M_k];

    for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
      {
        _M_losers[__i]._M_keyp = &__sentinel;
        _M_losers[__i]._M_source = -1;
      }
      }

      ~_LoserTreePointerUnguardedBase()
      { delete[] _M_losers; }

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

      void
      __insert_start(const _Tp& __key, int __source, bool)
      {
    unsigned int __pos = _M_k + __source;

    _M_losers[__pos]._M_keyp = &__key;
    _M_losers[__pos]._M_source = __source;
      }
    };

  template<bool __stable/* default == true */, typename _Tp, typename _Compare>
    class _LoserTreePointerUnguarded
    : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
    {
      typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;

    public:
      _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
                 _Compare __comp = std::less<_Tp>())
      : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    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;
          }
      }
      }

      void
      __init()
      {
    _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
      }

      void
      __delete_min_insert(const _Tp& __key, bool __sup)
      {
#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<typename _Tp, typename _Compare>
    class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
    : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
    {
      typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
      using _Base::_M_k;
      using _Base::_M_comp;
      using _Base::_M_losers;

  public:
      _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
                 _Compare __comp = std::less<_Tp>())
      : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
      { }

      unsigned int
      __init_winner(unsigned int __root)
      {
    if (__root >= _M_k)
      return __root;
    else
      {
        unsigned int __left = __init_winner(2 * __root);
        unsigned int __right = __init_winner(2 * __root + 1);

#if _GLIBCXX_ASSERTIONS
        // If __left one is sentinel then __right one must be, too.
        if (_M_losers[__left]._M_source == -1)
          _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
#endif

        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;
          }
      }
      }

      void
      __init()
      {
    _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
      }

      void
      __delete_min_insert(const _Tp& __key, bool __sup)
      {
#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.
        if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
          {
        // 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;
      }
    };
} // namespace __gnu_parallel

#endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */