losertree.h

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

Generated on Fri Jan 23 20:12:14 2009 for libstdc++ by  doxygen 1.5.6