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