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