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