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