libstdc++
losertree.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/losertree.h
00026 *  @brief Many generic loser tree variants.
00027 *  This file is a GNU parallel extension to the Standard C++ Library.
00028 */
00029 
00030 // Written by Johannes Singler.
00031 
00032 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
00033 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
00034 
00035 #include <bits/stl_algobase.h>
00036 #include <bits/stl_function.h>
00037 #include <parallel/features.h>
00038 #include <parallel/base.h>
00039 
00040 namespace __gnu_parallel
00041 {
00042   /**
00043    * @brief Guarded loser/tournament tree.
00044    *
00045    * The smallest element is at the top.
00046    *
00047    * Guarding is done explicitly through one flag _M_sup per element,
00048    * inf is not needed due to a better initialization routine.  This
00049    * is a well-performing variant.
00050    *
00051    * @param _Tp the element type
00052    * @param _Compare the comparator to use, defaults to std::less<_Tp>
00053    */
00054   template<typename _Tp, typename _Compare>
00055     class _LoserTreeBase
00056     {
00057     protected:
00058       /** @brief Internal representation of a _LoserTree element. */
00059       struct _Loser
00060       {
00061     /** @brief flag, true iff this is a "maximum" __sentinel. */
00062     bool _M_sup;
00063     /** @brief __index of the __source __sequence. */
00064     int _M_source;
00065     /** @brief _M_key of the element in the _LoserTree. */
00066     _Tp _M_key;
00067       };
00068 
00069       unsigned int _M_ik, _M_k, _M_offset;
00070 
00071       /** log_2{_M_k} */
00072       unsigned int _M_log_k;
00073 
00074       /** @brief _LoserTree __elements. */
00075       _Loser* _M_losers;
00076 
00077       /** @brief _Compare to use. */
00078       _Compare _M_comp;
00079 
00080       /**
00081        * @brief State flag that determines whether the _LoserTree is empty.
00082        *
00083        * Only used for building the _LoserTree.
00084        */
00085       bool _M_first_insert;
00086 
00087     public:
00088       /**
00089        * @brief The constructor.
00090        *
00091        * @param __k The number of sequences to merge.
00092        * @param __comp The comparator to use.
00093        */
00094       _LoserTreeBase(unsigned int __k, _Compare __comp)
00095       : _M_comp(__comp)
00096       {
00097     _M_ik = __k;
00098 
00099     // Compute log_2{_M_k} for the _Loser Tree
00100     _M_log_k = __rd_log2(_M_ik - 1) + 1;
00101 
00102     // Next greater power of 2.
00103     _M_k = 1 << _M_log_k;
00104     _M_offset = _M_k;
00105 
00106     // Avoid default-constructing _M_losers[]._M_key
00107     _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
00108                             * sizeof(_Loser)));
00109     for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
00110       _M_losers[__i + _M_k]._M_sup = true;
00111 
00112     _M_first_insert = true;
00113       }
00114 
00115       /**
00116        * @brief The destructor.
00117        */
00118       ~_LoserTreeBase()
00119       { ::operator delete(_M_losers); }
00120 
00121       /**
00122        * @brief Initializes the sequence "_M_source" with the element "__key".
00123        *
00124        * @param __key the element to insert
00125        * @param __source __index of the __source __sequence
00126        * @param __sup flag that determines whether the value to insert is an
00127        *   explicit __supremum.
00128        */
00129       void
00130       __insert_start(const _Tp& __key, int __source, bool __sup)
00131       {
00132     unsigned int __pos = _M_k + __source;
00133 
00134     if(_M_first_insert)
00135       {
00136         // Construct all keys, so we can easily deconstruct them.
00137         for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
00138           new(&(_M_losers[__i]._M_key)) _Tp(__key);
00139         _M_first_insert = false;
00140       }
00141     else
00142       new(&(_M_losers[__pos]._M_key)) _Tp(__key);
00143 
00144     _M_losers[__pos]._M_sup = __sup;
00145     _M_losers[__pos]._M_source = __source;
00146       }
00147 
00148       /**
00149        * @return the index of the sequence with the smallest element.
00150        */
00151       int __get_min_source()
00152       { return _M_losers[0]._M_source; }
00153     };
00154 
00155     /**
00156      * @brief Stable _LoserTree variant.
00157      *
00158      * Provides the stable implementations of insert_start, __init_winner,
00159      * __init and __delete_min_insert.
00160      *
00161      * Unstable variant is done using partial specialisation below.
00162      */
00163   template<bool __stable/* default == true */, typename _Tp,
00164        typename _Compare>
00165     class _LoserTree
00166     : public _LoserTreeBase<_Tp, _Compare>
00167     {
00168       typedef _LoserTreeBase<_Tp, _Compare> _Base;
00169       using _Base::_M_k;
00170       using _Base::_M_losers;
00171       using _Base::_M_first_insert;
00172 
00173     public:
00174       _LoserTree(unsigned int __k, _Compare __comp)
00175       : _Base::_LoserTreeBase(__k, __comp)
00176       { }
00177 
00178       unsigned int
00179       __init_winner(unsigned int __root)
00180       {
00181     if (__root >= _M_k)
00182       return __root;
00183     else
00184       {
00185         unsigned int __left = __init_winner(2 * __root);
00186         unsigned int __right = __init_winner(2 * __root + 1);
00187         if (_M_losers[__right]._M_sup
00188         || (!_M_losers[__left]._M_sup
00189             && !_M_comp(_M_losers[__right]._M_key,
00190                 _M_losers[__left]._M_key)))
00191           {
00192         // Left one is less or equal.
00193         _M_losers[__root] = _M_losers[__right];
00194         return __left;
00195           }
00196         else
00197           {
00198         // Right one is less.
00199         _M_losers[__root] = _M_losers[__left];
00200         return __right;
00201           }
00202       }
00203       }
00204 
00205       void __init()
00206       { _M_losers[0] = _M_losers[__init_winner(1)]; }
00207 
00208       /**
00209        * @brief Delete the smallest element and insert a new element from
00210        *   the previously smallest element's sequence.
00211        *
00212        * This implementation is stable.
00213        */
00214       // Do not pass a const reference since __key will be used as
00215       // local variable.
00216       void
00217       __delete_min_insert(_Tp __key, bool __sup)
00218       {
00219         using std::swap;
00220 #if _GLIBCXX_ASSERTIONS
00221     // no dummy sequence can ever be at the top!
00222     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00223 #endif
00224 
00225     int __source = _M_losers[0]._M_source;
00226     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00227          __pos /= 2)
00228       {
00229         // The smaller one gets promoted, ties are broken by _M_source.
00230         if ((__sup && (!_M_losers[__pos]._M_sup
00231                || _M_losers[__pos]._M_source < __source))
00232         || (!__sup && !_M_losers[__pos]._M_sup
00233             && ((_M_comp(_M_losers[__pos]._M_key, __key))
00234             || (!_M_comp(__key, _M_losers[__pos]._M_key)
00235                 && _M_losers[__pos]._M_source < __source))))
00236           {
00237         // The other one is smaller.
00238         std::swap(_M_losers[__pos]._M_sup, __sup);
00239         std::swap(_M_losers[__pos]._M_source, __source);
00240         swap(_M_losers[__pos]._M_key, __key);
00241           }
00242       }
00243 
00244     _M_losers[0]._M_sup = __sup;
00245     _M_losers[0]._M_source = __source;
00246     _M_losers[0]._M_key = __key;
00247       }
00248     };
00249 
00250     /**
00251      * @brief Unstable _LoserTree variant.
00252      *
00253      * Stability (non-stable here) is selected with partial specialization.
00254      */
00255   template<typename _Tp, typename _Compare>
00256     class _LoserTree</* __stable == */false, _Tp, _Compare>
00257     : public _LoserTreeBase<_Tp, _Compare>
00258     {
00259       typedef _LoserTreeBase<_Tp, _Compare> _Base;
00260       using _Base::_M_log_k;
00261       using _Base::_M_k;
00262       using _Base::_M_losers;
00263       using _Base::_M_first_insert;
00264 
00265     public:
00266       _LoserTree(unsigned int __k, _Compare __comp)
00267       : _Base::_LoserTreeBase(__k, __comp)
00268       { }
00269 
00270       /**
00271        * Computes the winner of the competition at position "__root".
00272        *
00273        * Called recursively (starting at 0) to build the initial tree.
00274        *
00275        * @param __root __index of the "game" to start.
00276        */
00277       unsigned int
00278       __init_winner(unsigned int __root)
00279       {
00280     if (__root >= _M_k)
00281       return __root;
00282     else
00283       {
00284         unsigned int __left = __init_winner(2 * __root);
00285         unsigned int __right = __init_winner(2 * __root + 1);
00286         if (_M_losers[__right]._M_sup
00287         || (!_M_losers[__left]._M_sup
00288             && !_M_comp(_M_losers[__right]._M_key,
00289                 _M_losers[__left]._M_key)))
00290           {
00291         // Left one is less or equal.
00292         _M_losers[__root] = _M_losers[__right];
00293         return __left;
00294           }
00295         else
00296           {
00297         // Right one is less.
00298         _M_losers[__root] = _M_losers[__left];
00299         return __right;
00300           }
00301       }
00302       }
00303 
00304       void
00305       __init()
00306       { _M_losers[0] = _M_losers[__init_winner(1)]; }
00307 
00308       /**
00309        * Delete the _M_key smallest element and insert the element __key
00310        * instead.
00311        *
00312        * @param __key the _M_key to insert
00313        * @param __sup true iff __key is an explicitly marked supremum
00314        */
00315       // Do not pass a const reference since __key will be used as local
00316       // variable.
00317       void
00318       __delete_min_insert(_Tp __key, bool __sup)
00319       {
00320         using std::swap;
00321 #if _GLIBCXX_ASSERTIONS
00322     // no dummy sequence can ever be at the top!
00323     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00324 #endif
00325 
00326     int __source = _M_losers[0]._M_source;
00327     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00328          __pos /= 2)
00329       {
00330         // The smaller one gets promoted.
00331         if (__sup || (!_M_losers[__pos]._M_sup
00332               && _M_comp(_M_losers[__pos]._M_key, __key)))
00333           {
00334         // The other one is smaller.
00335         std::swap(_M_losers[__pos]._M_sup, __sup);
00336         std::swap(_M_losers[__pos]._M_source, __source);
00337         swap(_M_losers[__pos]._M_key, __key);
00338           }
00339       }
00340 
00341     _M_losers[0]._M_sup = __sup;
00342     _M_losers[0]._M_source = __source;
00343     _M_losers[0]._M_key = __key;
00344       }
00345     };
00346 
00347   /**
00348    * @brief Base class of _Loser Tree implementation using pointers.
00349    */
00350   template<typename _Tp, typename _Compare>
00351     class _LoserTreePointerBase
00352     {
00353     protected:
00354       /** @brief Internal representation of _LoserTree __elements. */
00355       struct _Loser
00356       {
00357     bool _M_sup;
00358     int _M_source;
00359     const _Tp* _M_keyp;
00360       };
00361 
00362       unsigned int _M_ik, _M_k, _M_offset;
00363       _Loser* _M_losers;
00364       _Compare _M_comp;
00365 
00366     public:
00367       _LoserTreePointerBase(unsigned int __k,
00368                 _Compare __comp = std::less<_Tp>())
00369       : _M_comp(__comp)
00370       {
00371     _M_ik = __k;
00372 
00373     // Next greater power of 2.
00374     _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00375     _M_offset = _M_k;
00376     _M_losers = new _Loser[_M_k * 2];
00377     for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
00378       _M_losers[__i + _M_k]._M_sup = true;
00379       }
00380 
00381       ~_LoserTreePointerBase()
00382       { ::operator delete[](_M_losers); }
00383 
00384       int __get_min_source()
00385       { return _M_losers[0]._M_source; }
00386 
00387       void __insert_start(const _Tp& __key, int __source, bool __sup)
00388       {
00389     unsigned int __pos = _M_k + __source;
00390 
00391     _M_losers[__pos]._M_sup = __sup;
00392     _M_losers[__pos]._M_source = __source;
00393     _M_losers[__pos]._M_keyp = &__key;
00394       }
00395     };
00396 
00397   /**
00398    * @brief Stable _LoserTree implementation.
00399    *
00400    * The unstable variant is implemented using partial instantiation below.
00401    */
00402   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
00403     class _LoserTreePointer
00404     : public _LoserTreePointerBase<_Tp, _Compare>
00405     {
00406       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
00407       using _Base::_M_k;
00408       using _Base::_M_losers;
00409 
00410     public:
00411       _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
00412       : _Base::_LoserTreePointerBase(__k, __comp)
00413       { }
00414 
00415       unsigned int
00416       __init_winner(unsigned int __root)
00417       {
00418     if (__root >= _M_k)
00419       return __root;
00420     else
00421       {
00422         unsigned int __left = __init_winner(2 * __root);
00423         unsigned int __right = __init_winner(2 * __root + 1);
00424         if (_M_losers[__right]._M_sup
00425         || (!_M_losers[__left]._M_sup
00426             && !_M_comp(*_M_losers[__right]._M_keyp,
00427                 *_M_losers[__left]._M_keyp)))
00428           {
00429         // Left one is less or equal.
00430         _M_losers[__root] = _M_losers[__right];
00431         return __left;
00432           }
00433         else
00434           {
00435         // Right one is less.
00436         _M_losers[__root] = _M_losers[__left];
00437         return __right;
00438           }
00439       }
00440       }
00441 
00442       void __init()
00443       { _M_losers[0] = _M_losers[__init_winner(1)]; }
00444 
00445       void __delete_min_insert(const _Tp& __key, bool __sup)
00446       {
00447 #if _GLIBCXX_ASSERTIONS
00448     // no dummy sequence can ever be at the top!
00449     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00450 #endif
00451 
00452     const _Tp* __keyp = &__key;
00453     int __source = _M_losers[0]._M_source;
00454     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00455          __pos /= 2)
00456       {
00457         // The smaller one gets promoted, ties are broken by __source.
00458         if ((__sup && (!_M_losers[__pos]._M_sup
00459                || _M_losers[__pos]._M_source < __source))
00460         || (!__sup && !_M_losers[__pos]._M_sup &&
00461             ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
00462              || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
00463              && _M_losers[__pos]._M_source < __source))))
00464           {
00465         // The other one is smaller.
00466         std::swap(_M_losers[__pos]._M_sup, __sup);
00467         std::swap(_M_losers[__pos]._M_source, __source);
00468         std::swap(_M_losers[__pos]._M_keyp, __keyp);
00469           }
00470       }
00471 
00472     _M_losers[0]._M_sup = __sup;
00473     _M_losers[0]._M_source = __source;
00474     _M_losers[0]._M_keyp = __keyp;
00475       }
00476     };
00477 
00478   /**
00479    * @brief Unstable _LoserTree implementation.
00480    *
00481    * The stable variant is above.
00482    */
00483   template<typename _Tp, typename _Compare>
00484     class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
00485     : public _LoserTreePointerBase<_Tp, _Compare>
00486     {
00487       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
00488       using _Base::_M_k;
00489       using _Base::_M_losers;
00490 
00491     public:
00492       _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
00493       : _Base::_LoserTreePointerBase(__k, __comp)
00494       { }
00495 
00496       unsigned int
00497       __init_winner(unsigned int __root)
00498       {
00499     if (__root >= _M_k)
00500       return __root;
00501     else
00502       {
00503         unsigned int __left = __init_winner(2 * __root);
00504         unsigned int __right = __init_winner(2 * __root + 1);
00505         if (_M_losers[__right]._M_sup
00506             || (!_M_losers[__left]._M_sup
00507             && !_M_comp(*_M_losers[__right]._M_keyp,
00508                 *_M_losers[__left]._M_keyp)))
00509           {
00510         // Left one is less or equal.
00511         _M_losers[__root] = _M_losers[__right];
00512         return __left;
00513           }
00514         else
00515           {
00516         // Right one is less.
00517         _M_losers[__root] = _M_losers[__left];
00518         return __right;
00519           }
00520       }
00521       }
00522 
00523       void __init()
00524       { _M_losers[0] = _M_losers[__init_winner(1)]; }
00525 
00526       void __delete_min_insert(const _Tp& __key, bool __sup)
00527       {
00528 #if _GLIBCXX_ASSERTIONS
00529     // no dummy sequence can ever be at the top!
00530     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00531 #endif
00532 
00533     const _Tp* __keyp = &__key;
00534     int __source = _M_losers[0]._M_source;
00535     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00536          __pos /= 2)
00537       {
00538         // The smaller one gets promoted.
00539         if (__sup || (!_M_losers[__pos]._M_sup
00540               && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
00541           {
00542         // The other one is smaller.
00543         std::swap(_M_losers[__pos]._M_sup, __sup);
00544         std::swap(_M_losers[__pos]._M_source, __source);
00545         std::swap(_M_losers[__pos]._M_keyp, __keyp);
00546           }
00547       }
00548 
00549     _M_losers[0]._M_sup = __sup;
00550     _M_losers[0]._M_source = __source;
00551     _M_losers[0]._M_keyp = __keyp;
00552       }
00553     };
00554 
00555   /** @brief Base class for unguarded _LoserTree implementation.
00556    * 
00557    * The whole element is copied into the tree structure.
00558    *
00559    * No guarding is done, therefore not a single input sequence must
00560    * run empty.  Unused __sequence heads are marked with a sentinel which
00561    * is &gt; all elements that are to be merged.
00562    *
00563    * This is a very fast variant.
00564    */
00565   template<typename _Tp, typename _Compare>
00566     class _LoserTreeUnguardedBase
00567     {
00568     protected:
00569       struct _Loser
00570       {
00571     int _M_source;
00572     _Tp _M_key;
00573       };
00574 
00575       unsigned int _M_ik, _M_k, _M_offset;
00576       _Loser* _M_losers;
00577       _Compare _M_comp;
00578 
00579     public:
00580       _LoserTreeUnguardedBase(unsigned int __k, const _Tp __sentinel,
00581                   _Compare __comp = std::less<_Tp>())
00582       : _M_comp(__comp)
00583       {
00584     _M_ik = __k;
00585 
00586     // Next greater power of 2.
00587     _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00588     _M_offset = _M_k;
00589     // Avoid default-constructing _M_losers[]._M_key
00590     _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
00591                             * sizeof(_Loser)));
00592 
00593     for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
00594       {
00595         _M_losers[__i]._M_key = __sentinel;
00596         _M_losers[__i]._M_source = -1;
00597       }
00598       }
00599 
00600       ~_LoserTreeUnguardedBase()
00601       { ::operator delete(_M_losers); }
00602 
00603       int
00604       __get_min_source()
00605       {
00606 #if _GLIBCXX_ASSERTIONS
00607     // no dummy sequence can ever be at the top!
00608     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00609 #endif
00610     return _M_losers[0]._M_source;
00611       }
00612 
00613       void
00614       __insert_start(const _Tp& __key, int __source, bool)
00615       {
00616     unsigned int __pos = _M_k + __source;
00617 
00618     new(&(_M_losers[__pos]._M_key)) _Tp(__key);
00619     _M_losers[__pos]._M_source = __source;
00620       }
00621     };
00622 
00623   /**
00624    * @brief Stable implementation of unguarded _LoserTree.
00625    *
00626    * Unstable variant is selected below with partial specialization.
00627    */
00628   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
00629     class _LoserTreeUnguarded
00630     : public _LoserTreeUnguardedBase<_Tp, _Compare>
00631     {
00632       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
00633       using _Base::_M_k;
00634       using _Base::_M_losers;
00635 
00636   public:
00637       _LoserTreeUnguarded(unsigned int __k, const _Tp __sentinel,
00638               _Compare __comp = std::less<_Tp>())
00639       : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
00640       { }
00641 
00642       unsigned int
00643       __init_winner(unsigned int __root)
00644       {
00645     if (__root >= _M_k)
00646       return __root;
00647     else
00648       {
00649         unsigned int __left = __init_winner(2 * __root);
00650         unsigned int __right = __init_winner(2 * __root + 1);
00651         if (!_M_comp(_M_losers[__right]._M_key,
00652              _M_losers[__left]._M_key))
00653           {
00654         // Left one is less or equal.
00655         _M_losers[__root] = _M_losers[__right];
00656         return __left;
00657           }
00658         else
00659           {
00660         // Right one is less.
00661         _M_losers[__root] = _M_losers[__left];
00662         return __right;
00663           }
00664       }
00665       }
00666 
00667       void
00668       __init()
00669       {
00670     _M_losers[0] = _M_losers[__init_winner(1)];
00671 
00672 #if _GLIBCXX_ASSERTIONS
00673     // no dummy sequence can ever be at the top at the beginning
00674     // (0 sequences!)
00675     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00676 #endif
00677       }
00678 
00679       // Do not pass a const reference since __key will be used as
00680       // local variable.
00681       void
00682       __delete_min_insert(_Tp __key, bool)
00683       {
00684         using std::swap;
00685 #if _GLIBCXX_ASSERTIONS
00686     // no dummy sequence can ever be at the top!
00687     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00688 #endif
00689 
00690     int __source = _M_losers[0]._M_source;
00691     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00692          __pos /= 2)
00693       {
00694         // The smaller one gets promoted, ties are broken by _M_source.
00695         if (_M_comp(_M_losers[__pos]._M_key, __key)
00696             || (!_M_comp(__key, _M_losers[__pos]._M_key)
00697                     && _M_losers[__pos]._M_source < __source))
00698           {
00699         // The other one is smaller.
00700         std::swap(_M_losers[__pos]._M_source, __source);
00701         swap(_M_losers[__pos]._M_key, __key);
00702           }
00703       }
00704 
00705     _M_losers[0]._M_source = __source;
00706     _M_losers[0]._M_key = __key;
00707       }
00708     };
00709 
00710   /**
00711    * @brief Non-Stable implementation of unguarded _LoserTree.
00712    *
00713    * Stable implementation is above.
00714    */
00715   template<typename _Tp, typename _Compare>
00716     class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare>
00717     : public _LoserTreeUnguardedBase<_Tp, _Compare>
00718     {
00719       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
00720       using _Base::_M_k;
00721       using _Base::_M_losers;
00722 
00723     public:
00724       _LoserTreeUnguarded(unsigned int __k, const _Tp __sentinel,
00725               _Compare __comp = std::less<_Tp>())
00726       : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
00727       { }
00728 
00729       unsigned int
00730       __init_winner(unsigned int __root)
00731       {
00732     if (__root >= _M_k)
00733       return __root;
00734     else
00735       {
00736         unsigned int __left = __init_winner(2 * __root);
00737         unsigned int __right = __init_winner(2 * __root + 1);
00738 
00739 #if _GLIBCXX_ASSERTIONS
00740         // If __left one is sentinel then __right one must be, too.
00741         if (_M_losers[__left]._M_source == -1)
00742           _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
00743 #endif
00744 
00745         if (!_M_comp(_M_losers[__right]._M_key,
00746              _M_losers[__left]._M_key))
00747           {
00748         // Left one is less or equal.
00749         _M_losers[__root] = _M_losers[__right];
00750         return __left;
00751           }
00752         else
00753           {
00754         // Right one is less.
00755         _M_losers[__root] = _M_losers[__left];
00756         return __right;
00757           }
00758       }
00759       }
00760 
00761       void
00762       __init()
00763       {
00764     _M_losers[0] = _M_losers[__init_winner(1)];
00765 
00766 #if _GLIBCXX_ASSERTIONS
00767     // no dummy sequence can ever be at the top at the beginning
00768     // (0 sequences!)
00769     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00770 #endif
00771       }
00772 
00773       // Do not pass a const reference since __key will be used as
00774       // local variable.
00775       void
00776       __delete_min_insert(_Tp __key, bool)
00777       {
00778         using std::swap;
00779 #if _GLIBCXX_ASSERTIONS
00780     // no dummy sequence can ever be at the top!
00781     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00782 #endif
00783 
00784     int __source = _M_losers[0]._M_source;
00785     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00786          __pos /= 2)
00787       {
00788         // The smaller one gets promoted.
00789         if (_M_comp(_M_losers[__pos]._M_key, __key))
00790           {
00791         // The other one is smaller.
00792         std::swap(_M_losers[__pos]._M_source, __source);
00793         swap(_M_losers[__pos]._M_key, __key);
00794           }
00795       }
00796 
00797     _M_losers[0]._M_source = __source;
00798     _M_losers[0]._M_key = __key;
00799       }
00800     };
00801 
00802   /** @brief Unguarded loser tree, keeping only pointers to the
00803   * elements in the tree structure.
00804   *
00805   *  No guarding is done, therefore not a single input sequence must
00806   *  run empty.  This is a very fast variant.
00807   */
00808   template<typename _Tp, typename _Compare>
00809     class _LoserTreePointerUnguardedBase
00810     {
00811     protected:
00812       struct _Loser
00813       {
00814     int _M_source;
00815     const _Tp* _M_keyp;
00816       };
00817 
00818       unsigned int _M_ik, _M_k, _M_offset;
00819       _Loser* _M_losers;
00820       _Compare _M_comp;
00821 
00822     public:
00823 
00824       _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
00825                      _Compare __comp = std::less<_Tp>())
00826       : _M_comp(__comp)
00827       {
00828     _M_ik = __k;
00829 
00830     // Next greater power of 2.
00831     _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00832     _M_offset = _M_k;
00833     // Avoid default-constructing _M_losers[]._M_key
00834     _M_losers = new _Loser[2 * _M_k];
00835 
00836     for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
00837       {
00838         _M_losers[__i]._M_keyp = &__sentinel;
00839         _M_losers[__i]._M_source = -1;
00840       }
00841       }
00842 
00843       ~_LoserTreePointerUnguardedBase()
00844       { delete[] _M_losers; }
00845 
00846       int
00847       __get_min_source()
00848       {
00849 #if _GLIBCXX_ASSERTIONS
00850     // no dummy sequence can ever be at the top!
00851     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00852 #endif
00853     return _M_losers[0]._M_source;
00854       }
00855 
00856       void
00857       __insert_start(const _Tp& __key, int __source, bool)
00858       {
00859     unsigned int __pos = _M_k + __source;
00860 
00861     _M_losers[__pos]._M_keyp = &__key;
00862     _M_losers[__pos]._M_source = __source;
00863       }
00864     };
00865 
00866   /**
00867    * @brief Stable unguarded _LoserTree variant storing pointers.
00868    *
00869    * Unstable variant is implemented below using partial specialization.
00870    */
00871   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
00872     class _LoserTreePointerUnguarded
00873     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
00874     {
00875       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
00876       using _Base::_M_k;
00877       using _Base::_M_losers;
00878 
00879     public:
00880       _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
00881                  _Compare __comp = std::less<_Tp>())
00882       : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
00883       { }
00884 
00885       unsigned int
00886       __init_winner(unsigned int __root)
00887       {
00888     if (__root >= _M_k)
00889       return __root;
00890     else
00891       {
00892         unsigned int __left = __init_winner(2 * __root);
00893         unsigned int __right = __init_winner(2 * __root + 1);
00894         if (!_M_comp(*_M_losers[__right]._M_keyp,
00895              *_M_losers[__left]._M_keyp))
00896           {
00897         // Left one is less or equal.
00898         _M_losers[__root] = _M_losers[__right];
00899         return __left;
00900           }
00901         else
00902           {
00903         // Right one is less.
00904         _M_losers[__root] = _M_losers[__left];
00905         return __right;
00906           }
00907       }
00908       }
00909 
00910       void
00911       __init()
00912       {
00913     _M_losers[0] = _M_losers[__init_winner(1)];
00914 
00915 #if _GLIBCXX_ASSERTIONS
00916     // no dummy sequence can ever be at the top at the beginning
00917     // (0 sequences!)
00918     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00919 #endif
00920       }
00921 
00922       void
00923       __delete_min_insert(const _Tp& __key, bool __sup)
00924       {
00925 #if _GLIBCXX_ASSERTIONS
00926     // no dummy sequence can ever be at the top!
00927     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00928 #endif
00929 
00930     const _Tp* __keyp = &__key;
00931     int __source = _M_losers[0]._M_source;
00932     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00933          __pos /= 2)
00934       {
00935         // The smaller one gets promoted, ties are broken by _M_source.
00936         if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
00937         || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
00938             && _M_losers[__pos]._M_source < __source))
00939           {
00940         // The other one is smaller.
00941         std::swap(_M_losers[__pos]._M_source, __source);
00942         std::swap(_M_losers[__pos]._M_keyp, __keyp);
00943           }
00944       }
00945 
00946     _M_losers[0]._M_source = __source;
00947     _M_losers[0]._M_keyp = __keyp;
00948       }
00949     };
00950 
00951   /**
00952    * @brief Unstable unguarded _LoserTree variant storing pointers.
00953    *
00954    * Stable variant is above.
00955    */
00956   template<typename _Tp, typename _Compare>
00957     class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
00958     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
00959     {
00960       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
00961       using _Base::_M_k;
00962       using _Base::_M_losers;
00963 
00964   public:
00965       _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
00966                  _Compare __comp = std::less<_Tp>())
00967       : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
00968       { }
00969 
00970       unsigned int
00971       __init_winner(unsigned int __root)
00972       {
00973     if (__root >= _M_k)
00974       return __root;
00975     else
00976       {
00977         unsigned int __left = __init_winner(2 * __root);
00978         unsigned int __right = __init_winner(2 * __root + 1);
00979 
00980 #if _GLIBCXX_ASSERTIONS
00981         // If __left one is sentinel then __right one must be, too.
00982         if (_M_losers[__left]._M_source == -1)
00983           _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
00984 #endif
00985 
00986         if (!_M_comp(*_M_losers[__right]._M_keyp,
00987              *_M_losers[__left]._M_keyp))
00988           {
00989         // Left one is less or equal.
00990         _M_losers[__root] = _M_losers[__right];
00991         return __left;
00992           }
00993         else
00994           {
00995         // Right one is less.
00996         _M_losers[__root] = _M_losers[__left];
00997         return __right;
00998           }
00999       }
01000       }
01001 
01002       void
01003       __init()
01004       {
01005     _M_losers[0] = _M_losers[__init_winner(1)];
01006 
01007 #if _GLIBCXX_ASSERTIONS
01008     // no dummy sequence can ever be at the top at the beginning
01009     // (0 sequences!)
01010     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
01011 #endif
01012       }
01013 
01014       void
01015       __delete_min_insert(const _Tp& __key, bool __sup)
01016       {
01017 #if _GLIBCXX_ASSERTIONS
01018     // no dummy sequence can ever be at the top!
01019     _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
01020 #endif
01021 
01022     const _Tp* __keyp = &__key;
01023     int __source = _M_losers[0]._M_source;
01024     for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
01025          __pos /= 2)
01026       {
01027         // The smaller one gets promoted.
01028         if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
01029           {
01030         // The other one is smaller.
01031         std::swap(_M_losers[__pos]._M_source, __source);
01032         std::swap(_M_losers[__pos]._M_keyp, __keyp);
01033           }
01034       }
01035 
01036     _M_losers[0]._M_source = __source;
01037     _M_losers[0]._M_keyp = __keyp;
01038       }
01039     };
01040 } // namespace __gnu_parallel
01041 
01042 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */