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