The C and C++ Include Header Files

/usr/include/c++/11/parallel/losertree.h


$ cat -n /usr/include/c++/11/parallel/losertree.h

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2007-2021 Free Software Foundation, Inc.
     4	//
     5	// This file is part of the GNU ISO C++ Library.  This library is free
     6	// software; you can redistribute it and/or modify it under the terms
     7	// of the GNU General Public License as published by the Free Software
     8	// Foundation; either version 3, or (at your option) any later
     9	// version.
    10	
    11	// This library is distributed in the hope that it will be useful, but
    12	// WITHOUT ANY WARRANTY; without even the implied warranty of
    13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    14	// General Public License for more details.
    15	
    16	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	/** @file parallel/losertree.h
    26	*  @brief Many generic loser tree variants.
    27	*  This file is a GNU parallel extension to the Standard C++ Library.
    28	*/
    29	
    30	// Written by Johannes Singler.
    31	
    32	#ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
    33	#define _GLIBCXX_PARALLEL_LOSERTREE_H 1
    34	
    35	#include <bits/stl_algobase.h>
    36	#include <bits/stl_function.h>
    37	#include <parallel/features.h>
    38	#include <parallel/base.h>
    39	
    40	namespace __gnu_parallel
    41	{
    42	  /**
    43	   * @brief Guarded loser/tournament tree.
    44	   *
    45	   * The smallest element is at the top.
    46	   *
    47	   * Guarding is done explicitly through one flag _M_sup per element,
    48	   * inf is not needed due to a better initialization routine.  This
    49	   * is a well-performing variant.
    50	   *
    51	   * @param _Tp the element type
    52	   * @param _Compare the comparator to use, defaults to std::less<_Tp>
    53	   */
    54	  template<typename _Tp, typename _Compare>
    55	    class _LoserTreeBase
    56	    {
    57	    protected:
    58	      /** @brief Internal representation of a _LoserTree element. */
    59	      struct _Loser
    60	      {
    61		/** @brief flag, true iff this is a "maximum" __sentinel. */
    62		bool _M_sup;
    63		/** @brief __index of the __source __sequence. */
    64		int _M_source;
    65		/** @brief _M_key of the element in the _LoserTree. */
    66		_Tp _M_key;
    67	      };
    68	
    69	      unsigned int _M_ik, _M_k, _M_offset;
    70	
    71	      /** log_2{_M_k} */
    72	      unsigned int _M_log_k;
    73	
    74	      /** @brief _LoserTree __elements. */
    75	      _Loser* _M_losers;
    76	
    77	      /** @brief _Compare to use. */
    78	      _Compare _M_comp;
    79	
    80	      /**
    81	       * @brief State flag that determines whether the _LoserTree is empty.
    82	       *
    83	       * Only used for building the _LoserTree.
    84	       */
    85	      bool _M_first_insert;
    86	
    87	    public:
    88	      /**
    89	       * @brief The constructor.
    90	       *
    91	       * @param __k The number of sequences to merge.
    92	       * @param __comp The comparator to use.
    93	       */
    94	      _LoserTreeBase(unsigned int __k, _Compare __comp)
    95	      : _M_comp(__comp)
    96	      {
    97		_M_ik = __k;
    98	
    99		// Compute log_2{_M_k} for the _Loser Tree
   100		_M_log_k = __rd_log2(_M_ik - 1) + 1;
   101	
   102		// Next greater power of 2.
   103		_M_k = 1 << _M_log_k;
   104		_M_offset = _M_k;
   105	
   106		// Avoid default-constructing _M_losers[]._M_key
   107		_M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
   108								* sizeof(_Loser)));
   109		for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
   110		  _M_losers[__i + _M_k]._M_sup = true;
   111	
   112		_M_first_insert = true;
   113	      }
   114	
   115	      /**
   116	       * @brief The destructor.
   117	       */
   118	      ~_LoserTreeBase()
   119	      {
   120		for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
   121		  _M_losers[__i].~_Loser();
   122		::operator delete(_M_losers);
   123	      }
   124	
   125	      /**
   126	       * @brief Initializes the sequence "_M_source" with the element "__key".
   127	       *
   128	       * @param __key the element to insert
   129	       * @param __source __index of the __source __sequence
   130	       * @param __sup flag that determines whether the value to insert is an
   131	       *   explicit __supremum.
   132	       */
   133	      void
   134	      __insert_start(const _Tp& __key, int __source, bool __sup)
   135	      {
   136		unsigned int __pos = _M_k + __source;
   137	
   138		if (_M_first_insert)
   139		  {
   140		    // Construct all keys, so we can easily destruct them.
   141		    for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
   142		      ::new(&(_M_losers[__i]._M_key)) _Tp(__key);
   143		    _M_first_insert = false;
   144		  }
   145		else
   146		  _M_losers[__pos]._M_key = __key;
   147	
   148		_M_losers[__pos]._M_sup = __sup;
   149		_M_losers[__pos]._M_source = __source;
   150	      }
   151	
   152	      /**
   153	       * @return the index of the sequence with the smallest element.
   154	       */
   155	      int __get_min_source()
   156	      { return _M_losers[0]._M_source; }
   157	    };
   158	
   159	    /**
   160	     * @brief Stable _LoserTree variant.
   161	     *
   162	     * Provides the stable implementations of insert_start, __init_winner,
   163	     * __init and __delete_min_insert.
   164	     *
   165	     * Unstable variant is done using partial specialisation below.
   166	     */
   167	  template<bool __stable/* default == true */, typename _Tp,
   168		   typename _Compare>
   169	    class _LoserTree
   170	    : public _LoserTreeBase<_Tp, _Compare>
   171	    {
   172	      typedef _LoserTreeBase<_Tp, _Compare> _Base;
   173	      using _Base::_M_k;
   174	      using _Base::_M_comp;
   175	      using _Base::_M_losers;
   176	      using _Base::_M_first_insert;
   177	
   178	    public:
   179	      _LoserTree(unsigned int __k, _Compare __comp)
   180	      : _Base::_LoserTreeBase(__k, __comp)
   181	      { }
   182	
   183	      unsigned int
   184	      __init_winner(unsigned int __root)
   185	      {
   186		if (__root >= _M_k)
   187		  return __root;
   188		else
   189		  {
   190		    unsigned int __left = __init_winner(2 * __root);
   191		    unsigned int __right = __init_winner(2 * __root + 1);
   192		    if (_M_losers[__right]._M_sup
   193			|| (!_M_losers[__left]._M_sup
   194			    && !_M_comp(_M_losers[__right]._M_key,
   195					_M_losers[__left]._M_key)))
   196		      {
   197			// Left one is less or equal.
   198			_M_losers[__root] = _M_losers[__right];
   199			return __left;
   200		      }
   201		    else
   202		      {
   203			// Right one is less.
   204			_M_losers[__root] = _M_losers[__left];
   205			return __right;
   206		      }
   207		  }
   208	      }
   209	
   210	      void __init()
   211	      { _M_losers[0] = _M_losers[__init_winner(1)]; }
   212	
   213	      /**
   214	       * @brief Delete the smallest element and insert a new element from
   215	       *   the previously smallest element's sequence.
   216	       *
   217	       * This implementation is stable.
   218	       */
   219	      // Do not pass a const reference since __key will be used as
   220	      // local variable.
   221	      void
   222	      __delete_min_insert(_Tp __key, bool __sup)
   223	      {
   224	        using std::swap;
   225	#if _GLIBCXX_PARALLEL_ASSERTIONS
   226		// no dummy sequence can ever be at the top!
   227		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   228	#endif
   229	
   230		int __source = _M_losers[0]._M_source;
   231		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   232		     __pos /= 2)
   233		  {
   234		    // The smaller one gets promoted, ties are broken by _M_source.
   235		    if ((__sup && (!_M_losers[__pos]._M_sup
   236				   || _M_losers[__pos]._M_source < __source))
   237			|| (!__sup && !_M_losers[__pos]._M_sup
   238			    && ((_M_comp(_M_losers[__pos]._M_key, __key))
   239				|| (!_M_comp(__key, _M_losers[__pos]._M_key)
   240				    && _M_losers[__pos]._M_source < __source))))
   241		      {
   242			// The other one is smaller.
   243			std::swap(_M_losers[__pos]._M_sup, __sup);
   244			std::swap(_M_losers[__pos]._M_source, __source);
   245			swap(_M_losers[__pos]._M_key, __key);
   246		      }
   247		  }
   248	
   249		_M_losers[0]._M_sup = __sup;
   250		_M_losers[0]._M_source = __source;
   251		_M_losers[0]._M_key = __key;
   252	      }
   253	    };
   254	
   255	    /**
   256	     * @brief Unstable _LoserTree variant.
   257	     *
   258	     * Stability (non-stable here) is selected with partial specialization.
   259	     */
   260	  template<typename _Tp, typename _Compare>
   261	    class _LoserTree</* __stable == */false, _Tp, _Compare>
   262	    : public _LoserTreeBase<_Tp, _Compare>
   263	    {
   264	      typedef _LoserTreeBase<_Tp, _Compare> _Base;
   265	      using _Base::_M_log_k;
   266	      using _Base::_M_k;
   267	      using _Base::_M_comp;
   268	      using _Base::_M_losers;
   269	      using _Base::_M_first_insert;
   270	
   271	    public:
   272	      _LoserTree(unsigned int __k, _Compare __comp)
   273	      : _Base::_LoserTreeBase(__k, __comp)
   274	      { }
   275	
   276	      /**
   277	       * Computes the winner of the competition at position "__root".
   278	       *
   279	       * Called recursively (starting at 0) to build the initial tree.
   280	       *
   281	       * @param __root __index of the "game" to start.
   282	       */
   283	      unsigned int
   284	      __init_winner(unsigned int __root)
   285	      {
   286		if (__root >= _M_k)
   287		  return __root;
   288		else
   289		  {
   290		    unsigned int __left = __init_winner(2 * __root);
   291		    unsigned int __right = __init_winner(2 * __root + 1);
   292		    if (_M_losers[__right]._M_sup
   293			|| (!_M_losers[__left]._M_sup
   294			    && !_M_comp(_M_losers[__right]._M_key,
   295					_M_losers[__left]._M_key)))
   296		      {
   297			// Left one is less or equal.
   298			_M_losers[__root] = _M_losers[__right];
   299			return __left;
   300		      }
   301		    else
   302		      {
   303			// Right one is less.
   304			_M_losers[__root] = _M_losers[__left];
   305			return __right;
   306		      }
   307		  }
   308	      }
   309	
   310	      void
   311	      __init()
   312	      { _M_losers[0] = _M_losers[__init_winner(1)]; }
   313	
   314	      /**
   315	       * Delete the _M_key smallest element and insert the element __key
   316	       * instead.
   317	       *
   318	       * @param __key the _M_key to insert
   319	       * @param __sup true iff __key is an explicitly marked supremum
   320	       */
   321	      // Do not pass a const reference since __key will be used as local
   322	      // variable.
   323	      void
   324	      __delete_min_insert(_Tp __key, bool __sup)
   325	      {
   326	        using std::swap;
   327	#if _GLIBCXX_PARALLEL_ASSERTIONS
   328		// no dummy sequence can ever be at the top!
   329		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   330	#endif
   331	
   332		int __source = _M_losers[0]._M_source;
   333		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   334		     __pos /= 2)
   335		  {
   336		    // The smaller one gets promoted.
   337		    if (__sup || (!_M_losers[__pos]._M_sup
   338				  && _M_comp(_M_losers[__pos]._M_key, __key)))
   339		      {
   340			// The other one is smaller.
   341			std::swap(_M_losers[__pos]._M_sup, __sup);
   342			std::swap(_M_losers[__pos]._M_source, __source);
   343			swap(_M_losers[__pos]._M_key, __key);
   344		      }
   345		  }
   346	
   347		_M_losers[0]._M_sup = __sup;
   348		_M_losers[0]._M_source = __source;
   349		_M_losers[0]._M_key = __key;
   350	      }
   351	    };
   352	
   353	  /**
   354	   * @brief Base class of _Loser Tree implementation using pointers.
   355	   */
   356	  template<typename _Tp, typename _Compare>
   357	    class _LoserTreePointerBase
   358	    {
   359	    protected:
   360	      /** @brief Internal representation of _LoserTree __elements. */
   361	      struct _Loser
   362	      {
   363		bool _M_sup;
   364		int _M_source;
   365		const _Tp* _M_keyp;
   366	      };
   367	
   368	      unsigned int _M_ik, _M_k, _M_offset;
   369	      _Loser* _M_losers;
   370	      _Compare _M_comp;
   371	
   372	    public:
   373	      _LoserTreePointerBase(unsigned int __k,
   374				    _Compare __comp = std::less<_Tp>())
   375	      : _M_comp(__comp)
   376	      {
   377		_M_ik = __k;
   378	
   379		// Next greater power of 2.
   380		_M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
   381		_M_offset = _M_k;
   382		_M_losers = new _Loser[_M_k * 2];
   383		for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
   384		  _M_losers[__i + _M_k]._M_sup = true;
   385	      }
   386	
   387	      ~_LoserTreePointerBase()
   388	      { delete[] _M_losers; }
   389	
   390	      int __get_min_source()
   391	      { return _M_losers[0]._M_source; }
   392	
   393	      void __insert_start(const _Tp& __key, int __source, bool __sup)
   394	      {
   395		unsigned int __pos = _M_k + __source;
   396	
   397		_M_losers[__pos]._M_sup = __sup;
   398		_M_losers[__pos]._M_source = __source;
   399		_M_losers[__pos]._M_keyp = &__key;
   400	      }
   401	    };
   402	
   403	  /**
   404	   * @brief Stable _LoserTree implementation.
   405	   *
   406	   * The unstable variant is implemented using partial instantiation below.
   407	   */
   408	  template<bool __stable/* default == true */, typename _Tp, typename _Compare>
   409	    class _LoserTreePointer
   410	    : public _LoserTreePointerBase<_Tp, _Compare>
   411	    {
   412	      typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
   413	      using _Base::_M_k;
   414	      using _Base::_M_comp;
   415	      using _Base::_M_losers;
   416	
   417	    public:
   418	      _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
   419	      : _Base::_LoserTreePointerBase(__k, __comp)
   420	      { }
   421	
   422	      unsigned int
   423	      __init_winner(unsigned int __root)
   424	      {
   425		if (__root >= _M_k)
   426		  return __root;
   427		else
   428		  {
   429		    unsigned int __left = __init_winner(2 * __root);
   430		    unsigned int __right = __init_winner(2 * __root + 1);
   431		    if (_M_losers[__right]._M_sup
   432			|| (!_M_losers[__left]._M_sup
   433			    && !_M_comp(*_M_losers[__right]._M_keyp,
   434					*_M_losers[__left]._M_keyp)))
   435		      {
   436			// Left one is less or equal.
   437			_M_losers[__root] = _M_losers[__right];
   438			return __left;
   439		      }
   440		    else
   441		      {
   442			// Right one is less.
   443			_M_losers[__root] = _M_losers[__left];
   444			return __right;
   445		      }
   446		  }
   447	      }
   448	
   449	      void __init()
   450	      { _M_losers[0] = _M_losers[__init_winner(1)]; }
   451	
   452	      void __delete_min_insert(const _Tp& __key, bool __sup)
   453	      {
   454	#if _GLIBCXX_PARALLEL_ASSERTIONS
   455		// no dummy sequence can ever be at the top!
   456		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   457	#endif
   458	
   459		const _Tp* __keyp = &__key;
   460		int __source = _M_losers[0]._M_source;
   461		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   462		     __pos /= 2)
   463		  {
   464		    // The smaller one gets promoted, ties are broken by __source.
   465		    if ((__sup && (!_M_losers[__pos]._M_sup
   466				   || _M_losers[__pos]._M_source < __source))
   467			|| (!__sup && !_M_losers[__pos]._M_sup &&
   468			    ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
   469			     || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
   470				 && _M_losers[__pos]._M_source < __source))))
   471		      {
   472			// The other one is smaller.
   473			std::swap(_M_losers[__pos]._M_sup, __sup);
   474			std::swap(_M_losers[__pos]._M_source, __source);
   475			std::swap(_M_losers[__pos]._M_keyp, __keyp);
   476		      }
   477		  }
   478	
   479		_M_losers[0]._M_sup = __sup;
   480		_M_losers[0]._M_source = __source;
   481		_M_losers[0]._M_keyp = __keyp;
   482	      }
   483	    };
   484	
   485	  /**
   486	   * @brief Unstable _LoserTree implementation.
   487	   *
   488	   * The stable variant is above.
   489	   */
   490	  template<typename _Tp, typename _Compare>
   491	    class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
   492	    : public _LoserTreePointerBase<_Tp, _Compare>
   493	    {
   494	      typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
   495	      using _Base::_M_k;
   496	      using _Base::_M_comp;
   497	      using _Base::_M_losers;
   498	
   499	    public:
   500	      _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
   501	      : _Base::_LoserTreePointerBase(__k, __comp)
   502	      { }
   503	
   504	      unsigned int
   505	      __init_winner(unsigned int __root)
   506	      {
   507		if (__root >= _M_k)
   508		  return __root;
   509		else
   510		  {
   511		    unsigned int __left = __init_winner(2 * __root);
   512		    unsigned int __right = __init_winner(2 * __root + 1);
   513		    if (_M_losers[__right]._M_sup
   514	        	|| (!_M_losers[__left]._M_sup
   515			    && !_M_comp(*_M_losers[__right]._M_keyp,
   516					*_M_losers[__left]._M_keyp)))
   517		      {
   518			// Left one is less or equal.
   519			_M_losers[__root] = _M_losers[__right];
   520			return __left;
   521		      }
   522		    else
   523		      {
   524			// Right one is less.
   525			_M_losers[__root] = _M_losers[__left];
   526			return __right;
   527		      }
   528		  }
   529	      }
   530	
   531	      void __init()
   532	      { _M_losers[0] = _M_losers[__init_winner(1)]; }
   533	
   534	      void __delete_min_insert(const _Tp& __key, bool __sup)
   535	      {
   536	#if _GLIBCXX_PARALLEL_ASSERTIONS
   537		// no dummy sequence can ever be at the top!
   538		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   539	#endif
   540	
   541		const _Tp* __keyp = &__key;
   542		int __source = _M_losers[0]._M_source;
   543		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   544		     __pos /= 2)
   545		  {
   546		    // The smaller one gets promoted.
   547		    if (__sup || (!_M_losers[__pos]._M_sup
   548				  && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
   549		      {
   550			// The other one is smaller.
   551			std::swap(_M_losers[__pos]._M_sup, __sup);
   552			std::swap(_M_losers[__pos]._M_source, __source);
   553			std::swap(_M_losers[__pos]._M_keyp, __keyp);
   554		      }
   555		  }
   556	
   557		_M_losers[0]._M_sup = __sup;
   558		_M_losers[0]._M_source = __source;
   559		_M_losers[0]._M_keyp = __keyp;
   560	      }
   561	    };
   562	
   563	  /** @brief Base class for unguarded _LoserTree implementation.
   564	   * 
   565	   * The whole element is copied into the tree structure.
   566	   *
   567	   * No guarding is done, therefore not a single input sequence must
   568	   * run empty.  Unused __sequence heads are marked with a sentinel which
   569	   * is > all elements that are to be merged.
   570	   *
   571	   * This is a very fast variant.
   572	   */
   573	  template<typename _Tp, typename _Compare>
   574	    class _LoserTreeUnguardedBase
   575	    {
   576	    protected:
   577	      struct _Loser
   578	      {
   579		int _M_source;
   580		_Tp _M_key;
   581	      };
   582	
   583	      unsigned int _M_ik, _M_k, _M_offset;
   584	      _Loser* _M_losers;
   585	      _Compare _M_comp;
   586	
   587	    public:
   588	      _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel,
   589				      _Compare __comp = std::less<_Tp>())
   590	      : _M_comp(__comp)
   591	      {
   592		_M_ik = __k;
   593	
   594		// Next greater power of 2.
   595		_M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
   596		_M_offset = _M_k;
   597		// Avoid default-constructing _M_losers[]._M_key
   598		_M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
   599								* sizeof(_Loser)));
   600	
   601	        for (unsigned int __i = 0; __i < _M_k; ++__i)
   602	          {
   603		    ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
   604		    _M_losers[__i]._M_source = -1;
   605		  }
   606	        for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
   607	          {
   608		    ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
   609		    _M_losers[__i]._M_source = -1;
   610		  }
   611	      }
   612	
   613	      ~_LoserTreeUnguardedBase()
   614	      {
   615		for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
   616		  _M_losers[__i].~_Loser();
   617		::operator delete(_M_losers);
   618	      }
   619	
   620	      int
   621	      __get_min_source()
   622	      {
   623	#if _GLIBCXX_PARALLEL_ASSERTIONS
   624		// no dummy sequence can ever be at the top!
   625		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   626	#endif
   627		return _M_losers[0]._M_source;
   628	      }
   629	
   630	      void
   631	      __insert_start(const _Tp& __key, int __source, bool)
   632	      {
   633		unsigned int __pos = _M_k + __source;
   634	
   635		::new(&(_M_losers[__pos]._M_key)) _Tp(__key);
   636		_M_losers[__pos]._M_source = __source;
   637	      }
   638	    };
   639	
   640	  /**
   641	   * @brief Stable implementation of unguarded _LoserTree.
   642	   *
   643	   * Unstable variant is selected below with partial specialization.
   644	   */
   645	  template<bool __stable/* default == true */, typename _Tp, typename _Compare>
   646	    class _LoserTreeUnguarded
   647	    : public _LoserTreeUnguardedBase<_Tp, _Compare>
   648	    {
   649	      typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
   650	      using _Base::_M_k;
   651	      using _Base::_M_comp;
   652	      using _Base::_M_losers;
   653	
   654	  public:
   655	      _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
   656				  _Compare __comp = std::less<_Tp>())
   657	      : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
   658	      { }
   659	
   660	      unsigned int
   661	      __init_winner(unsigned int __root)
   662	      {
   663		if (__root >= _M_k)
   664		  return __root;
   665		else
   666		  {
   667		    unsigned int __left = __init_winner(2 * __root);
   668		    unsigned int __right = __init_winner(2 * __root + 1);
   669		    if (!_M_comp(_M_losers[__right]._M_key,
   670				 _M_losers[__left]._M_key))
   671		      {
   672			// Left one is less or equal.
   673			_M_losers[__root] = _M_losers[__right];
   674			return __left;
   675		      }
   676		    else
   677		      {
   678			// Right one is less.
   679			_M_losers[__root] = _M_losers[__left];
   680			return __right;
   681		      }
   682		  }
   683	      }
   684	
   685	      void
   686	      __init()
   687	      {
   688		_M_losers[0] = _M_losers[__init_winner(1)];
   689	
   690	#if _GLIBCXX_PARALLEL_ASSERTIONS
   691		// no dummy sequence can ever be at the top at the beginning
   692		// (0 sequences!)
   693		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   694	#endif
   695	      }
   696	
   697	      // Do not pass a const reference since __key will be used as
   698	      // local variable.
   699	      void
   700	      __delete_min_insert(_Tp __key, bool)
   701	      {
   702	        using std::swap;
   703	#if _GLIBCXX_PARALLEL_ASSERTIONS
   704		// no dummy sequence can ever be at the top!
   705		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   706	#endif
   707	
   708		int __source = _M_losers[0]._M_source;
   709		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   710		     __pos /= 2)
   711		  {
   712		    // The smaller one gets promoted, ties are broken by _M_source.
   713		    if (_M_comp(_M_losers[__pos]._M_key, __key)
   714	        	|| (!_M_comp(__key, _M_losers[__pos]._M_key)
   715	                    && _M_losers[__pos]._M_source < __source))
   716		      {
   717			// The other one is smaller.
   718			std::swap(_M_losers[__pos]._M_source, __source);
   719			swap(_M_losers[__pos]._M_key, __key);
   720		      }
   721		  }
   722	
   723		_M_losers[0]._M_source = __source;
   724		_M_losers[0]._M_key = __key;
   725	      }
   726	    };
   727	
   728	  /**
   729	   * @brief Non-Stable implementation of unguarded _LoserTree.
   730	   *
   731	   * Stable implementation is above.
   732	   */
   733	  template<typename _Tp, typename _Compare>
   734	    class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare>
   735	    : public _LoserTreeUnguardedBase<_Tp, _Compare>
   736	    {
   737	      typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
   738	      using _Base::_M_k;
   739	      using _Base::_M_comp;
   740	      using _Base::_M_losers;
   741	
   742	    public:
   743	      _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
   744				  _Compare __comp = std::less<_Tp>())
   745	      : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
   746	      { }
   747	
   748	      unsigned int
   749	      __init_winner(unsigned int __root)
   750	      {
   751		if (__root >= _M_k)
   752		  return __root;
   753		else
   754		  {
   755		    unsigned int __left = __init_winner(2 * __root);
   756		    unsigned int __right = __init_winner(2 * __root + 1);
   757	
   758	#if _GLIBCXX_PARALLEL_ASSERTIONS
   759		    // If __left one is sentinel then __right one must be, too.
   760		    if (_M_losers[__left]._M_source == -1)
   761		      _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
   762	#endif
   763	
   764		    if (!_M_comp(_M_losers[__right]._M_key,
   765				 _M_losers[__left]._M_key))
   766		      {
   767			// Left one is less or equal.
   768			_M_losers[__root] = _M_losers[__right];
   769			return __left;
   770		      }
   771		    else
   772		      {
   773			// Right one is less.
   774			_M_losers[__root] = _M_losers[__left];
   775			return __right;
   776		      }
   777		  }
   778	      }
   779	
   780	      void
   781	      __init()
   782	      {
   783		_M_losers[0] = _M_losers[__init_winner(1)];
   784	
   785	#if _GLIBCXX_PARALLEL_ASSERTIONS
   786		// no dummy sequence can ever be at the top at the beginning
   787		// (0 sequences!)
   788		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   789	#endif
   790	      }
   791	
   792	      // Do not pass a const reference since __key will be used as
   793	      // local variable.
   794	      void
   795	      __delete_min_insert(_Tp __key, bool)
   796	      {
   797	        using std::swap;
   798	#if _GLIBCXX_PARALLEL_ASSERTIONS
   799		// no dummy sequence can ever be at the top!
   800		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   801	#endif
   802	
   803		int __source = _M_losers[0]._M_source;
   804		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   805		     __pos /= 2)
   806		  {
   807		    // The smaller one gets promoted.
   808		    if (_M_comp(_M_losers[__pos]._M_key, __key))
   809		      {
   810			// The other one is smaller.
   811			std::swap(_M_losers[__pos]._M_source, __source);
   812			swap(_M_losers[__pos]._M_key, __key);
   813		      }
   814		  }
   815	
   816		_M_losers[0]._M_source = __source;
   817		_M_losers[0]._M_key = __key;
   818	      }
   819	    };
   820	
   821	  /** @brief Unguarded loser tree, keeping only pointers to the
   822	  * elements in the tree structure.
   823	  *
   824	  *  No guarding is done, therefore not a single input sequence must
   825	  *  run empty.  This is a very fast variant.
   826	  */
   827	  template<typename _Tp, typename _Compare>
   828	    class _LoserTreePointerUnguardedBase
   829	    {
   830	    protected:
   831	      struct _Loser
   832	      {
   833		int _M_source;
   834		const _Tp* _M_keyp;
   835	      };
   836	
   837	      unsigned int _M_ik, _M_k, _M_offset;
   838	      _Loser* _M_losers;
   839	      _Compare _M_comp;
   840	
   841	    public:
   842	
   843	      _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
   844					     _Compare __comp = std::less<_Tp>())
   845	      : _M_comp(__comp)
   846	      {
   847		_M_ik = __k;
   848	
   849		// Next greater power of 2.
   850		_M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
   851		_M_offset = _M_k;
   852		// Avoid default-constructing _M_losers[]._M_key
   853		_M_losers = new _Loser[2 * _M_k];
   854	
   855		for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
   856		  {
   857		    _M_losers[__i]._M_keyp = &__sentinel;
   858		    _M_losers[__i]._M_source = -1;
   859		  }
   860	      }
   861	
   862	      ~_LoserTreePointerUnguardedBase()
   863	      { delete[] _M_losers; }
   864	
   865	      int
   866	      __get_min_source()
   867	      {
   868	#if _GLIBCXX_PARALLEL_ASSERTIONS
   869		// no dummy sequence can ever be at the top!
   870		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   871	#endif
   872		return _M_losers[0]._M_source;
   873	      }
   874	
   875	      void
   876	      __insert_start(const _Tp& __key, int __source, bool)
   877	      {
   878		unsigned int __pos = _M_k + __source;
   879	
   880		_M_losers[__pos]._M_keyp = &__key;
   881		_M_losers[__pos]._M_source = __source;
   882	      }
   883	    };
   884	
   885	  /**
   886	   * @brief Stable unguarded _LoserTree variant storing pointers.
   887	   *
   888	   * Unstable variant is implemented below using partial specialization.
   889	   */
   890	  template<bool __stable/* default == true */, typename _Tp, typename _Compare>
   891	    class _LoserTreePointerUnguarded
   892	    : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
   893	    {
   894	      typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
   895	      using _Base::_M_k;
   896	      using _Base::_M_comp;
   897	      using _Base::_M_losers;
   898	
   899	    public:
   900	      _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
   901					 _Compare __comp = std::less<_Tp>())
   902	      : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
   903	      { }
   904	
   905	      unsigned int
   906	      __init_winner(unsigned int __root)
   907	      {
   908		if (__root >= _M_k)
   909		  return __root;
   910		else
   911		  {
   912		    unsigned int __left = __init_winner(2 * __root);
   913		    unsigned int __right = __init_winner(2 * __root + 1);
   914		    if (!_M_comp(*_M_losers[__right]._M_keyp,
   915				 *_M_losers[__left]._M_keyp))
   916		      {
   917			// Left one is less or equal.
   918			_M_losers[__root] = _M_losers[__right];
   919			return __left;
   920		      }
   921		    else
   922		      {
   923			// Right one is less.
   924			_M_losers[__root] = _M_losers[__left];
   925			return __right;
   926		      }
   927		  }
   928	      }
   929	
   930	      void
   931	      __init()
   932	      {
   933		_M_losers[0] = _M_losers[__init_winner(1)];
   934	
   935	#if _GLIBCXX_PARALLEL_ASSERTIONS
   936		// no dummy sequence can ever be at the top at the beginning
   937		// (0 sequences!)
   938		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   939	#endif
   940	      }
   941	
   942	      void
   943	      __delete_min_insert(const _Tp& __key, bool __sup)
   944	      {
   945	#if _GLIBCXX_PARALLEL_ASSERTIONS
   946		// no dummy sequence can ever be at the top!
   947		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
   948	#endif
   949	
   950		const _Tp* __keyp = &__key;
   951		int __source = _M_losers[0]._M_source;
   952		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
   953		     __pos /= 2)
   954		  {
   955		    // The smaller one gets promoted, ties are broken by _M_source.
   956		    if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
   957			|| (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
   958			    && _M_losers[__pos]._M_source < __source))
   959		      {
   960			// The other one is smaller.
   961			std::swap(_M_losers[__pos]._M_source, __source);
   962			std::swap(_M_losers[__pos]._M_keyp, __keyp);
   963		      }
   964		  }
   965	
   966		_M_losers[0]._M_source = __source;
   967		_M_losers[0]._M_keyp = __keyp;
   968	      }
   969	    };
   970	
   971	  /**
   972	   * @brief Unstable unguarded _LoserTree variant storing pointers.
   973	   *
   974	   * Stable variant is above.
   975	   */
   976	  template<typename _Tp, typename _Compare>
   977	    class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
   978	    : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
   979	    {
   980	      typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
   981	      using _Base::_M_k;
   982	      using _Base::_M_comp;
   983	      using _Base::_M_losers;
   984	
   985	  public:
   986	      _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
   987					 _Compare __comp = std::less<_Tp>())
   988	      : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
   989	      { }
   990	
   991	      unsigned int
   992	      __init_winner(unsigned int __root)
   993	      {
   994		if (__root >= _M_k)
   995		  return __root;
   996		else
   997		  {
   998		    unsigned int __left = __init_winner(2 * __root);
   999		    unsigned int __right = __init_winner(2 * __root + 1);
  1000	
  1001	#if _GLIBCXX_PARALLEL_ASSERTIONS
  1002		    // If __left one is sentinel then __right one must be, too.
  1003		    if (_M_losers[__left]._M_source == -1)
  1004		      _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
  1005	#endif
  1006	
  1007		    if (!_M_comp(*_M_losers[__right]._M_keyp,
  1008				 *_M_losers[__left]._M_keyp))
  1009		      {
  1010			// Left one is less or equal.
  1011			_M_losers[__root] = _M_losers[__right];
  1012			return __left;
  1013		      }
  1014		    else
  1015		      {
  1016			// Right one is less.
  1017			_M_losers[__root] = _M_losers[__left];
  1018			return __right;
  1019		      }
  1020		  }
  1021	      }
  1022	
  1023	      void
  1024	      __init()
  1025	      {
  1026		_M_losers[0] = _M_losers[__init_winner(1)];
  1027	
  1028	#if _GLIBCXX_PARALLEL_ASSERTIONS
  1029		// no dummy sequence can ever be at the top at the beginning
  1030		// (0 sequences!)
  1031		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
  1032	#endif
  1033	      }
  1034	
  1035	      void
  1036	      __delete_min_insert(const _Tp& __key, bool __sup)
  1037	      {
  1038	#if _GLIBCXX_PARALLEL_ASSERTIONS
  1039		// no dummy sequence can ever be at the top!
  1040		_GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
  1041	#endif
  1042	
  1043		const _Tp* __keyp = &__key;
  1044		int __source = _M_losers[0]._M_source;
  1045		for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
  1046		     __pos /= 2)
  1047		  {
  1048		    // The smaller one gets promoted.
  1049		    if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
  1050		      {
  1051			// The other one is smaller.
  1052			std::swap(_M_losers[__pos]._M_source, __source);
  1053			std::swap(_M_losers[__pos]._M_keyp, __keyp);
  1054		      }
  1055		  }
  1056	
  1057		_M_losers[0]._M_source = __source;
  1058		_M_losers[0]._M_keyp = __keyp;
  1059	      }
  1060	    };
  1061	} // namespace __gnu_parallel
  1062	
  1063	#endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */