3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file parallel/losertree.h
26 * @brief Many generic loser tree variants.
27 * This file is a GNU parallel extension to the Standard C++ Library.
30 // Written by Johannes Singler.
32 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
33 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
37 #include <bits/stl_algobase.h>
38 #include <parallel/features.h>
39 #include <parallel/base.h>
41 namespace __gnu_parallel
45 * @brief Guarded loser/tournament tree.
47 * The smallest element is at the top.
49 * Guarding is done explicitly through one flag _M_sup per element,
50 * inf is not needed due to a better initialization routine. This
51 * is a well-performing variant.
53 * @param _Tp the element _Self
54 * @param _Compare the comparator to use, defaults to std::less<_Tp>
56 template<typename _Tp
, typename _Compare
>
60 /** @brief Internal representation of a LoserTree element. */
63 /** @brief flag, true iff this is a "maximum" __sentinel. */
65 /** @brief __index of the _M_source __sequence. */
67 /** @brief _M_key of the element in the LoserTree. */
71 unsigned int __ik
, __k
, __offset
;
74 unsigned int _M_log_k
;
76 /** @brief LoserTree __elements. */
79 /** @brief _Compare to use. */
83 * @brief State flag that determines whether the LoserTree is empty.
85 * Only used for building the LoserTree.
91 * @brief The constructor.
93 * @param _k The number of sequences to merge.
94 * @param _comp The comparator to use.
96 LoserTreeBase(unsigned int _k
, _Compare _comp
)
101 // Compute log_2{__k} for the _Loser Tree
102 _M_log_k
= __log2(__ik
- 1) + 1;
104 // Next greater power of 2.
108 // Avoid default-constructing __losers[]._M_key
109 __losers
= static_cast<_Loser
*>(::operator new(2 * __k
* sizeof(_Loser
)));
110 for (unsigned int __i
= __ik
- 1; __i
< __k
; ++__i
)
111 __losers
[__i
+ __k
]._M_sup
= true;
113 __first_insert
= true;
117 * @brief The destructor.
120 { ::operator delete(__losers
); }
123 * @brief Initializes the sequence "_M_source" with the element "_M_key".
125 * @param _M_key the element to insert
126 * @param _M_source __index of the _M_source __sequence
127 * @param _M_sup flag that determines whether the value to insert is an
128 * explicit __supremum.
131 __insert_start(const _Tp
& _M_key
, int _M_source
, bool _M_sup
)
133 unsigned int __pos
= __k
+ _M_source
;
137 // Construct all keys, so we can easily deconstruct them.
138 for (unsigned int __i
= 0; __i
< (2 * __k
); ++__i
)
139 new(&(__losers
[__i
]._M_key
)) _Tp(_M_key
);
140 __first_insert
= false;
143 new(&(__losers
[__pos
]._M_key
)) _Tp(_M_key
);
145 __losers
[__pos
]._M_sup
= _M_sup
;
146 __losers
[__pos
]._M_source
= _M_source
;
150 * @return the index of the sequence with the smallest element.
152 int __get_min_source()
153 { return __losers
[0]._M_source
; }
157 * @brief Stable LoserTree variant.
159 * Provides the stable implementations of insert_start, __init_winner,
160 * __init and __delete_min_insert.
162 * Unstable variant is done using partial specialisation below.
164 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
165 class LoserTree
: public LoserTreeBase
<_Tp
, _Compare
>
167 typedef LoserTreeBase
<_Tp
, _Compare
> Base
;
169 using Base::__losers
;
170 using Base::__first_insert
;
173 LoserTree(unsigned int _k
, _Compare _comp
)
174 : Base::LoserTreeBase(_k
, _comp
)
178 __init_winner(unsigned int __root
)
186 unsigned int __left
= __init_winner (2 * __root
);
187 unsigned int __right
= __init_winner (2 * __root
+ 1);
188 if (__losers
[__right
]._M_sup
189 || (!__losers
[__left
]._M_sup
190 && !__comp(__losers
[__right
]._M_key
, __losers
[__left
]._M_key
)))
192 // Left one is less or equal.
193 __losers
[__root
] = __losers
[__right
];
198 // Right one is less.
199 __losers
[__root
] = __losers
[__left
];
206 { __losers
[0] = __losers
[__init_winner(1)]; }
209 * @brief Delete the smallest element and insert a new element from
210 * the previously smallest element's sequence.
212 * This implementation is stable.
214 // Do not pass a const reference since _M_key will be used as local variable.
215 void __delete_min_insert(_Tp _M_key
, bool _M_sup
)
217 #if _GLIBCXX_ASSERTIONS
218 // no dummy sequence can ever be at the top!
219 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
222 int _M_source
= __losers
[0]._M_source
;
223 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
225 // The smaller one gets promoted, ties are broken by _M_source.
226 if ((_M_sup
&& (!__losers
[__pos
]._M_sup
|| __losers
[__pos
]._M_source
< _M_source
))
227 || (!_M_sup
&& !__losers
[__pos
]._M_sup
228 && ((__comp(__losers
[__pos
]._M_key
, _M_key
))
229 || (!__comp(_M_key
, __losers
[__pos
]._M_key
)
230 && __losers
[__pos
]._M_source
< _M_source
))))
232 // The other one is smaller.
233 std::swap(__losers
[__pos
]._M_sup
, _M_sup
);
234 std::swap(__losers
[__pos
]._M_source
, _M_source
);
235 std::swap(__losers
[__pos
]._M_key
, _M_key
);
239 __losers
[0]._M_sup
= _M_sup
;
240 __losers
[0]._M_source
= _M_source
;
241 __losers
[0]._M_key
= _M_key
;
246 * @brief Unstable LoserTree variant.
248 * Stability (non-stable here) is selected with partial specialization.
250 template<typename _Tp
, typename _Compare
>
251 class LoserTree
</* __stable == */false, _Tp
, _Compare
> :
252 public LoserTreeBase
<_Tp
, _Compare
>
254 typedef LoserTreeBase
<_Tp
, _Compare
> Base
;
255 using Base::_M_log_k
;
257 using Base::__losers
;
258 using Base::__first_insert
;
261 LoserTree(unsigned int _k
, _Compare _comp
)
262 : Base::LoserTreeBase(_k
, _comp
)
266 * Computes the winner of the competition at __position "__root".
268 * Called recursively (starting at 0) to build the initial tree.
270 * @param __root __index of the "game" to start.
273 __init_winner (unsigned int __root
)
281 unsigned int __left
= __init_winner (2 * __root
);
282 unsigned int __right
= __init_winner (2 * __root
+ 1);
283 if (__losers
[__right
]._M_sup
||
284 (!__losers
[__left
]._M_sup
285 && !__comp(__losers
[__right
]._M_key
, __losers
[__left
]._M_key
)))
287 // Left one is less or equal.
288 __losers
[__root
] = __losers
[__right
];
293 // Right one is less.
294 __losers
[__root
] = __losers
[__left
];
302 { __losers
[0] = __losers
[__init_winner(1)]; }
305 * Delete the _M_key smallest element and insert the element _M_key instead.
307 * @param _M_key the _M_key to insert
308 * @param _M_sup true iff _M_key is an explicitly marked supremum
310 // Do not pass a const reference since _M_key will be used as local variable.
312 __delete_min_insert(_Tp _M_key
, bool _M_sup
)
314 #if _GLIBCXX_ASSERTIONS
315 // no dummy sequence can ever be at the top!
316 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
319 int _M_source
= __losers
[0]._M_source
;
320 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
322 // The smaller one gets promoted.
323 if (_M_sup
|| (!__losers
[__pos
]._M_sup
&& __comp(__losers
[__pos
]._M_key
, _M_key
)))
325 // The other one is smaller.
326 std::swap(__losers
[__pos
]._M_sup
, _M_sup
);
327 std::swap(__losers
[__pos
]._M_source
, _M_source
);
328 std::swap(__losers
[__pos
]._M_key
, _M_key
);
332 __losers
[0]._M_sup
= _M_sup
;
333 __losers
[0]._M_source
= _M_source
;
334 __losers
[0]._M_key
= _M_key
;
340 * @brief Base class of _Loser Tree implementation using pointers.
342 template<typename _Tp
, typename _Compare
>
343 class _LoserTreePointerBase
346 /** @brief Internal representation of LoserTree __elements. */
354 unsigned int __ik
, __k
, __offset
;
359 _LoserTreePointerBase(unsigned int _k
, _Compare _comp
= std::less
<_Tp
>())
364 // Next greater power of 2.
365 __k
= 1 << (__log2(__ik
- 1) + 1);
367 __losers
= new _Loser
[__k
* 2];
368 for (unsigned int __i
= __ik
- 1; __i
< __k
; __i
++)
369 __losers
[__i
+ __k
]._M_sup
= true;
372 ~_LoserTreePointerBase()
373 { ::operator delete[](__losers
); }
375 int __get_min_source()
376 { return __losers
[0]._M_source
; }
378 void __insert_start(const _Tp
& _M_key
, int _M_source
, bool _M_sup
)
380 unsigned int __pos
= __k
+ _M_source
;
382 __losers
[__pos
]._M_sup
= _M_sup
;
383 __losers
[__pos
]._M_source
= _M_source
;
384 __losers
[__pos
]._M_keyp
= &_M_key
;
389 * @brief Stable LoserTree implementation.
391 * The unstable variant is implemented using partial instantiation below.
393 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
394 class _LoserTreePointer
: public _LoserTreePointerBase
<_Tp
, _Compare
>
396 typedef _LoserTreePointerBase
<_Tp
, _Compare
> Base
;
398 using Base::__losers
;
401 _LoserTreePointer(unsigned int _k
, _Compare _comp
= std::less
<_Tp
>())
402 : Base::_LoserTreePointerBase(_k
, _comp
)
406 __init_winner(unsigned int __root
)
414 unsigned int __left
= __init_winner (2 * __root
);
415 unsigned int __right
= __init_winner (2 * __root
+ 1);
416 if (__losers
[__right
]._M_sup
417 || (!__losers
[__left
]._M_sup
&& !__comp(*__losers
[__right
]._M_keyp
,
418 *__losers
[__left
]._M_keyp
)))
420 // Left one is less or equal.
421 __losers
[__root
] = __losers
[__right
];
426 // Right one is less.
427 __losers
[__root
] = __losers
[__left
];
434 { __losers
[0] = __losers
[__init_winner(1)]; }
436 void __delete_min_insert(const _Tp
& _M_key
, bool _M_sup
)
438 #if _GLIBCXX_ASSERTIONS
439 // no dummy sequence can ever be at the top!
440 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
443 const _Tp
* _M_keyp
= &_M_key
;
444 int _M_source
= __losers
[0]._M_source
;
445 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
447 // The smaller one gets promoted, ties are broken by _M_source.
448 if ((_M_sup
&& (!__losers
[__pos
]._M_sup
|| __losers
[__pos
]._M_source
< _M_source
)) ||
449 (!_M_sup
&& !__losers
[__pos
]._M_sup
&&
450 ((__comp(*__losers
[__pos
]._M_keyp
, *_M_keyp
)) ||
451 (!__comp(*_M_keyp
, *__losers
[__pos
]._M_keyp
)
452 && __losers
[__pos
]._M_source
< _M_source
))))
454 // The other one is smaller.
455 std::swap(__losers
[__pos
]._M_sup
, _M_sup
);
456 std::swap(__losers
[__pos
]._M_source
, _M_source
);
457 std::swap(__losers
[__pos
]._M_keyp
, _M_keyp
);
461 __losers
[0]._M_sup
= _M_sup
;
462 __losers
[0]._M_source
= _M_source
;
463 __losers
[0]._M_keyp
= _M_keyp
;
468 * @brief Unstable LoserTree implementation.
470 * The stable variant is above.
472 template<typename _Tp
, typename _Compare
>
473 class _LoserTreePointer
</* __stable == */false, _Tp
, _Compare
> :
474 public _LoserTreePointerBase
<_Tp
, _Compare
>
476 typedef _LoserTreePointerBase
<_Tp
, _Compare
> Base
;
478 using Base::__losers
;
481 _LoserTreePointer(unsigned int _k
, _Compare _comp
= std::less
<_Tp
>())
482 : Base::_LoserTreePointerBase(_k
, _comp
)
486 __init_winner(unsigned int __root
)
494 unsigned int __left
= __init_winner (2 * __root
);
495 unsigned int __right
= __init_winner (2 * __root
+ 1);
496 if (__losers
[__right
]._M_sup
497 || (!__losers
[__left
]._M_sup
498 && !__comp(*__losers
[__right
]._M_keyp
, *__losers
[__left
]._M_keyp
)))
500 // Left one is less or equal.
501 __losers
[__root
] = __losers
[__right
];
506 // Right one is less.
507 __losers
[__root
] = __losers
[__left
];
514 { __losers
[0] = __losers
[__init_winner(1)]; }
516 void __delete_min_insert(const _Tp
& _M_key
, bool _M_sup
)
518 #if _GLIBCXX_ASSERTIONS
519 // no dummy sequence can ever be at the top!
520 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
523 const _Tp
* _M_keyp
= &_M_key
;
524 int _M_source
= __losers
[0]._M_source
;
525 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
527 // The smaller one gets promoted.
528 if (_M_sup
|| (!__losers
[__pos
]._M_sup
&& __comp(*__losers
[__pos
]._M_keyp
, *_M_keyp
)))
530 // The other one is smaller.
531 std::swap(__losers
[__pos
]._M_sup
, _M_sup
);
532 std::swap(__losers
[__pos
]._M_source
, _M_source
);
533 std::swap(__losers
[__pos
]._M_keyp
, _M_keyp
);
537 __losers
[0]._M_sup
= _M_sup
;
538 __losers
[0]._M_source
= _M_source
;
539 __losers
[0]._M_keyp
= _M_keyp
;
543 /** @brief Base class for unguarded LoserTree implementation.
545 * The whole element is copied into the tree structure.
547 * No guarding is done, therefore not a single input sequence must
548 * run empty. Unused __sequence heads are marked with a sentinel which
549 * is > all elements that are to be merged.
551 * This is a very fast variant.
553 template<typename _Tp
, typename _Compare
>
554 class _LoserTreeUnguardedBase
563 unsigned int __ik
, __k
, __offset
;
569 _LoserTreeUnguardedBase(unsigned int _k
, const _Tp _sentinel
,
570 _Compare _comp
= std::less
<_Tp
>())
575 // Next greater power of 2.
576 __k
= 1 << (__log2(__ik
- 1) + 1);
578 // Avoid default-constructing __losers[]._M_key
579 __losers
= static_cast<_Loser
*>(::operator new(2 * __k
* sizeof(_Loser
)));
581 for (unsigned int __i
= __k
+ __ik
- 1; __i
< (2 * __k
); ++__i
)
583 __losers
[__i
]._M_key
= _sentinel
;
584 __losers
[__i
]._M_source
= -1;
588 inline ~_LoserTreeUnguardedBase()
589 { ::operator delete(__losers
); }
594 #if _GLIBCXX_ASSERTIONS
595 // no dummy sequence can ever be at the top!
596 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
598 return __losers
[0]._M_source
;
602 __insert_start(const _Tp
& _M_key
, int _M_source
, bool)
604 unsigned int __pos
= __k
+ _M_source
;
606 new(&(__losers
[__pos
]._M_key
)) _Tp(_M_key
);
607 __losers
[__pos
]._M_source
= _M_source
;
612 * @brief Stable implementation of unguarded LoserTree.
614 * Unstable variant is selected below with partial specialization.
616 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
617 class _LoserTreeUnguarded
: public _LoserTreeUnguardedBase
<_Tp
, _Compare
>
619 typedef _LoserTreeUnguardedBase
<_Tp
, _Compare
> Base
;
621 using Base::__losers
;
624 _LoserTreeUnguarded(unsigned int _k
, const _Tp _sentinel
,
625 _Compare _comp
= std::less
<_Tp
>())
626 : Base::_LoserTreeUnguardedBase(_k
, _sentinel
, _comp
)
630 __init_winner(unsigned int __root
)
638 unsigned int __left
= __init_winner (2 * __root
);
639 unsigned int __right
= __init_winner (2 * __root
+ 1);
640 if (!__comp(__losers
[__right
]._M_key
, __losers
[__left
]._M_key
))
642 // Left one is less or equal.
643 __losers
[__root
] = __losers
[__right
];
648 // Right one is less.
649 __losers
[__root
] = __losers
[__left
];
658 __losers
[0] = __losers
[__init_winner(1)];
660 #if _GLIBCXX_ASSERTIONS
661 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
662 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
666 // Do not pass a const reference since _M_key will be used as local variable.
668 __delete_min_insert(_Tp _M_key
, bool)
670 #if _GLIBCXX_ASSERTIONS
671 // no dummy sequence can ever be at the top!
672 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
675 int _M_source
= __losers
[0]._M_source
;
676 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
678 // The smaller one gets promoted, ties are broken by _M_source.
679 if (__comp(__losers
[__pos
]._M_key
, _M_key
)
680 || (!__comp(_M_key
, __losers
[__pos
]._M_key
) && __losers
[__pos
]._M_source
< _M_source
))
682 // The other one is smaller.
683 std::swap(__losers
[__pos
]._M_source
, _M_source
);
684 std::swap(__losers
[__pos
]._M_key
, _M_key
);
688 __losers
[0]._M_source
= _M_source
;
689 __losers
[0]._M_key
= _M_key
;
694 * @brief Non-Stable implementation of unguarded LoserTree.
696 * Stable implementation is above.
698 template<typename _Tp
, typename _Compare
>
699 class _LoserTreeUnguarded
</* __stable == */false, _Tp
, _Compare
> :
700 public _LoserTreeUnguardedBase
<_Tp
, _Compare
>
702 typedef _LoserTreeUnguardedBase
<_Tp
, _Compare
> Base
;
704 using Base::__losers
;
707 _LoserTreeUnguarded(unsigned int _k
, const _Tp _sentinel
,
708 _Compare _comp
= std::less
<_Tp
>())
709 : Base::_LoserTreeUnguardedBase(_k
, _sentinel
, _comp
)
713 __init_winner (unsigned int __root
)
721 unsigned int __left
= __init_winner (2 * __root
);
722 unsigned int __right
= __init_winner (2 * __root
+ 1);
724 #if _GLIBCXX_ASSERTIONS
725 // If __left one is sentinel then __right one must be, too.
726 if (__losers
[__left
]._M_source
== -1)
727 _GLIBCXX_PARALLEL_ASSERT(__losers
[__right
]._M_source
== -1);
730 if (!__comp(__losers
[__right
]._M_key
, __losers
[__left
]._M_key
))
732 // Left one is less or equal.
733 __losers
[__root
] = __losers
[__right
];
738 // Right one is less.
739 __losers
[__root
] = __losers
[__left
];
748 __losers
[0] = __losers
[__init_winner(1)];
750 #if _GLIBCXX_ASSERTIONS
751 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
752 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
756 // Do not pass a const reference since _M_key will be used as local variable.
758 __delete_min_insert(_Tp _M_key
, bool)
760 #if _GLIBCXX_ASSERTIONS
761 // no dummy sequence can ever be at the top!
762 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
765 int _M_source
= __losers
[0]._M_source
;
766 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
768 // The smaller one gets promoted.
769 if (__comp(__losers
[__pos
]._M_key
, _M_key
))
771 // The other one is smaller.
772 std::swap(__losers
[__pos
]._M_source
, _M_source
);
773 std::swap(__losers
[__pos
]._M_key
, _M_key
);
777 __losers
[0]._M_source
= _M_source
;
778 __losers
[0]._M_key
= _M_key
;
782 /** @brief Unguarded loser tree, keeping only pointers to the
783 * __elements in the tree structure.
785 * No guarding is done, therefore not a single input sequence must
786 * run empty. This is a very fast variant.
788 template<typename _Tp
, typename _Compare
>
789 class LoserTreePointerUnguardedBase
798 unsigned int __ik
, __k
, __offset
;
805 LoserTreePointerUnguardedBase(unsigned int _k
, const _Tp
& _sentinel
,
806 _Compare _comp
= std::less
<_Tp
>())
811 // Next greater power of 2.
812 __k
= 1 << (__log2(__ik
- 1) + 1);
814 // Avoid default-constructing __losers[]._M_key
815 __losers
= new _Loser
[2 * __k
];
817 for (unsigned int __i
= __k
+ __ik
- 1; __i
< (2 * __k
); ++__i
)
819 __losers
[__i
]._M_keyp
= &_sentinel
;
820 __losers
[__i
]._M_source
= -1;
824 inline ~LoserTreePointerUnguardedBase()
825 { delete[] __losers
; }
830 #if _GLIBCXX_ASSERTIONS
831 // no dummy sequence can ever be at the top!
832 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
834 return __losers
[0]._M_source
;
838 __insert_start(const _Tp
& _M_key
, int _M_source
, bool)
840 unsigned int __pos
= __k
+ _M_source
;
842 __losers
[__pos
]._M_keyp
= &_M_key
;
843 __losers
[__pos
]._M_source
= _M_source
;
848 * @brief Stable unguarded LoserTree variant storing pointers.
850 * Unstable variant is implemented below using partial specialization.
852 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
853 class LoserTreePointerUnguarded
:
854 public LoserTreePointerUnguardedBase
<_Tp
, _Compare
>
856 typedef LoserTreePointerUnguardedBase
<_Tp
, _Compare
> Base
;
858 using Base::__losers
;
861 LoserTreePointerUnguarded(unsigned int _k
, const _Tp
& _sentinel
,
862 _Compare _comp
= std::less
<_Tp
>())
863 : Base::LoserTreePointerUnguardedBase(_k
, _sentinel
, _comp
)
867 __init_winner(unsigned int __root
)
875 unsigned int __left
= __init_winner (2 * __root
);
876 unsigned int __right
= __init_winner (2 * __root
+ 1);
877 if (!__comp(*__losers
[__right
]._M_keyp
, *__losers
[__left
]._M_keyp
))
879 // Left one is less or equal.
880 __losers
[__root
] = __losers
[__right
];
885 // Right one is less.
886 __losers
[__root
] = __losers
[__left
];
895 __losers
[0] = __losers
[__init_winner(1)];
897 #if _GLIBCXX_ASSERTIONS
898 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
899 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
904 __delete_min_insert(const _Tp
& _M_key
, bool _M_sup
)
906 #if _GLIBCXX_ASSERTIONS
907 // no dummy sequence can ever be at the top!
908 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
911 const _Tp
* _M_keyp
= &_M_key
;
912 int _M_source
= __losers
[0]._M_source
;
913 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
915 // The smaller one gets promoted, ties are broken by _M_source.
916 if (__comp(*__losers
[__pos
]._M_keyp
, *_M_keyp
)
917 || (!__comp(*_M_keyp
, *__losers
[__pos
]._M_keyp
) && __losers
[__pos
]._M_source
< _M_source
))
919 // The other one is smaller.
920 std::swap(__losers
[__pos
]._M_source
, _M_source
);
921 std::swap(__losers
[__pos
]._M_keyp
, _M_keyp
);
925 __losers
[0]._M_source
= _M_source
;
926 __losers
[0]._M_keyp
= _M_keyp
;
931 * @brief Unstable unguarded LoserTree variant storing pointers.
933 * Stable variant is above.
935 template<typename _Tp
, typename _Compare
>
936 class LoserTreePointerUnguarded
</* __stable == */false, _Tp
, _Compare
> :
937 public LoserTreePointerUnguardedBase
<_Tp
, _Compare
>
939 typedef LoserTreePointerUnguardedBase
<_Tp
, _Compare
> Base
;
941 using Base::__losers
;
944 LoserTreePointerUnguarded(unsigned int _k
, const _Tp
& _sentinel
,
945 _Compare _comp
= std::less
<_Tp
>())
946 : Base::LoserTreePointerUnguardedBase(_k
, _sentinel
, _comp
)
950 __init_winner(unsigned int __root
)
958 unsigned int __left
= __init_winner (2 * __root
);
959 unsigned int __right
= __init_winner (2 * __root
+ 1);
961 #if _GLIBCXX_ASSERTIONS
962 // If __left one is sentinel then __right one must be, too.
963 if (__losers
[__left
]._M_source
== -1)
964 _GLIBCXX_PARALLEL_ASSERT(__losers
[__right
]._M_source
== -1);
967 if (!__comp(*__losers
[__right
]._M_keyp
, *__losers
[__left
]._M_keyp
))
969 // Left one is less or equal.
970 __losers
[__root
] = __losers
[__right
];
975 // Right one is less.
976 __losers
[__root
] = __losers
[__left
];
985 __losers
[0] = __losers
[__init_winner(1)];
987 #if _GLIBCXX_ASSERTIONS
988 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
989 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
994 __delete_min_insert(const _Tp
& _M_key
, bool _M_sup
)
996 #if _GLIBCXX_ASSERTIONS
997 // no dummy sequence can ever be at the top!
998 _GLIBCXX_PARALLEL_ASSERT(__losers
[0]._M_source
!= -1);
1001 const _Tp
* _M_keyp
= &_M_key
;
1002 int _M_source
= __losers
[0]._M_source
;
1003 for (unsigned int __pos
= (__k
+ _M_source
) / 2; __pos
> 0; __pos
/= 2)
1005 // The smaller one gets promoted.
1006 if (__comp(*(__losers
[__pos
]._M_keyp
), *_M_keyp
))
1008 // The other one is smaller.
1009 std::swap(__losers
[__pos
]._M_source
, _M_source
);
1010 std::swap(__losers
[__pos
]._M_keyp
, _M_keyp
);
1014 __losers
[0]._M_source
= _M_source
;
1015 __losers
[0]._M_keyp
= _M_keyp
;
1019 } // namespace __gnu_parallel
1021 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */