libstdc++-v3/include/parallel/losertree.h

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