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