l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/parallel/losertree.h

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