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