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