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