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         using std::swap;
 779 #if _GLIBCXX_ASSERTIONS
 780         // no dummy sequence can ever be at the top!
 781         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 782 #endif
 783
 784         int __source = _M_losers[0]._M_source;
 785         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 786              __pos /= 2)
 787           {
 788             // The smaller one gets promoted.
 789             if (_M_comp(_M_losers[__pos]._M_key, __key))
 790               {
 791                 // The other one is smaller.
 792                 std::swap(_M_losers[__pos]._M_source, __source);
 793                 swap(_M_losers[__pos]._M_key, __key);
 794               }
 795           }
 796
 797         _M_losers[0]._M_source = __source;
 798         _M_losers[0]._M_key = __key;
 799       }
 800     };
 801
 802   /** @brief Unguarded loser tree, keeping only pointers to the
 803   * elements in the tree structure.
 804   *
 805   *  No guarding is done, therefore not a single input sequence must
 806   *  run empty.  This is a very fast variant.
 807   */
 808   template<typename _Tp, typename _Compare>
 809     class _LoserTreePointerUnguardedBase
 810     {
 811     protected:
 812       struct _Loser
 813       {
 814         int _M_source;
 815         const _Tp* _M_keyp;
 816       };
 817
 818       unsigned int _M_ik, _M_k, _M_offset;
 819       _Loser* _M_losers;
 820       _Compare _M_comp;
 821
 822     public:
 823
 824       _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
 825                                      _Compare __comp = std::less<_Tp>())
 826       : _M_comp(__comp)
 827       {
 828         _M_ik = __k;
 829
 830         // Next greater power of 2.
 831         _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
 832         _M_offset = _M_k;
 833         // Avoid default-constructing _M_losers[]._M_key
 834         _M_losers = new _Loser[2 * _M_k];
 835
 836         for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
 837           {
 838             _M_losers[__i]._M_keyp = &__sentinel;
 839             _M_losers[__i]._M_source = -1;
 840           }
 841       }
 842
 843       ~_LoserTreePointerUnguardedBase()
 844       { delete[] _M_losers; }
 845
 846       int
 847       __get_min_source()
 848       {
 849 #if _GLIBCXX_ASSERTIONS
 850         // no dummy sequence can ever be at the top!
 851         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 852 #endif
 853         return _M_losers[0]._M_source;
 854       }
 855
 856       void
 857       __insert_start(const _Tp& __key, int __source, bool)
 858       {
 859         unsigned int __pos = _M_k + __source;
 860
 861         _M_losers[__pos]._M_keyp = &__key;
 862         _M_losers[__pos]._M_source = __source;
 863       }
 864     };
 865
 866   /**
 867    * @brief Stable unguarded _LoserTree variant storing pointers.
 868    *
 869    * Unstable variant is implemented below using partial specialization.
 870    */
 871   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
 872     class _LoserTreePointerUnguarded
 873     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
 874     {
 875       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
 876       using _Base::_M_k;
 877       using _Base::_M_losers;
 878
 879     public:
 880       _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
 881                                  _Compare __comp = std::less<_Tp>())
 882       : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
 883       { }
 884
 885       unsigned int
 886       __init_winner(unsigned int __root)
 887       {
 888         if (__root >= _M_k)
 889           return __root;
 890         else
 891           {
 892             unsigned int __left = __init_winner(2 * __root);
 893             unsigned int __right = __init_winner(2 * __root + 1);
 894             if (!_M_comp(*_M_losers[__right]._M_keyp,
 895                          *_M_losers[__left]._M_keyp))
 896               {
 897                 // Left one is less or equal.
 898                 _M_losers[__root] = _M_losers[__right];
 899                 return __left;
 900               }
 901             else
 902               {
 903                 // Right one is less.
 904                 _M_losers[__root] = _M_losers[__left];
 905                 return __right;
 906               }
 907           }
 908       }
 909
 910       void
 911       __init()
 912       {
 913         _M_losers[0] = _M_losers[__init_winner(1)];
 914
 915 #if _GLIBCXX_ASSERTIONS
 916         // no dummy sequence can ever be at the top at the beginning
 917         // (0 sequences!)
 918         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 919 #endif
 920       }
 921
 922       void
 923       __delete_min_insert(const _Tp& __key, bool __sup)
 924       {
 925 #if _GLIBCXX_ASSERTIONS
 926         // no dummy sequence can ever be at the top!
 927         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 928 #endif
 929
 930         const _Tp* __keyp = &__key;
 931         int __source = _M_losers[0]._M_source;
 932         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 933              __pos /= 2)
 934           {
 935             // The smaller one gets promoted, ties are broken by _M_source.
 936             if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
 937                 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
 938                     && _M_losers[__pos]._M_source < __source))
 939               {
 940                 // The other one is smaller.
 941                 std::swap(_M_losers[__pos]._M_source, __source);
 942                 std::swap(_M_losers[__pos]._M_keyp, __keyp);
 943               }
 944           }
 945
 946         _M_losers[0]._M_source = __source;
 947         _M_losers[0]._M_keyp = __keyp;
 948       }
 949     };
 950
 951   /**
 952    * @brief Unstable unguarded _LoserTree variant storing pointers.
 953    *
 954    * Stable variant is above.
 955    */
 956   template<typename _Tp, typename _Compare>
 957     class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
 958     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
 959     {
 960       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
 961       using _Base::_M_k;
 962       using _Base::_M_losers;
 963
 964   public:
 965       _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
 966                                  _Compare __comp = std::less<_Tp>())
 967       : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
 968       { }
 969
 970       unsigned int
 971       __init_winner(unsigned int __root)
 972       {
 973         if (__root >= _M_k)
 974           return __root;
 975         else
 976           {
 977             unsigned int __left = __init_winner(2 * __root);
 978             unsigned int __right = __init_winner(2 * __root + 1);
 979
 980 #if _GLIBCXX_ASSERTIONS
 981             // If __left one is sentinel then __right one must be, too.
 982             if (_M_losers[__left]._M_source == -1)
 983               _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
 984 #endif
 985
 986             if (!_M_comp(*_M_losers[__right]._M_keyp,
 987                          *_M_losers[__left]._M_keyp))
 988               {
 989                 // Left one is less or equal.
 990                 _M_losers[__root] = _M_losers[__right];
 991                 return __left;
 992               }
 993             else
 994               {
 995                 // Right one is less.
 996                 _M_losers[__root] = _M_losers[__left];
 997                 return __right;
 998               }
 999           }
1000       }
1001
1002       void
1003       __init()
1004       {
1005         _M_losers[0] = _M_losers[__init_winner(1)];
1006
1007 #if _GLIBCXX_ASSERTIONS
1008         // no dummy sequence can ever be at the top at the beginning
1009         // (0 sequences!)
1010         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1011 #endif
1012       }
1013
1014       void
1015       __delete_min_insert(const _Tp& __key, bool __sup)
1016       {
1017 #if _GLIBCXX_ASSERTIONS
1018         // no dummy sequence can ever be at the top!
1019         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1020 #endif
1021
1022         const _Tp* __keyp = &__key;
1023         int __source = _M_losers[0]._M_source;
1024         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
1025              __pos /= 2)
1026           {
1027             // The smaller one gets promoted.
1028             if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
1029               {
1030                 // The other one is smaller.
1031                 std::swap(_M_losers[__pos]._M_source, __source);
1032                 std::swap(_M_losers[__pos]._M_keyp, __keyp);
1033               }
1034           }
1035
1036         _M_losers[0]._M_source = __source;
1037         _M_losers[0]._M_keyp = __keyp;
1038       }
1039     };
1040 } // namespace __gnu_parallel
1041
1042 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */