32 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
33 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
41 namespace __gnu_parallel
56 template<
typename T,
typename Comparator>
71 unsigned int ik, k, offset;
110 for (
unsigned int i = ik - 1; i < k; ++i)
120 { ::operator
delete(
losers); }
133 unsigned int pos = k + source;
138 for (
unsigned int i = 0; i < (2 * k); ++i)
139 new(&(
losers[i].key)) T(key);
164 template<
bool stable,
typename T,
typename Comparator>
173 LoserTree(
unsigned int _k, Comparator _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].sup
189 || (!losers[left].sup
190 && !comp(losers[right].key, losers[left].key)))
193 losers[root] = losers[
right];
199 losers[root] = losers[
left];
206 { losers[0] = losers[init_winner(1)]; }
217 #if _GLIBCXX_ASSERTIONS
219 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
222 int source = losers[0].source;
223 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
226 if ((sup && (!losers[pos].sup || losers[pos].source < source))
227 || (!sup && !losers[pos].sup
228 && ((comp(losers[pos].key, key))
229 || (!comp(key, losers[pos].key)
230 && losers[pos].source < source))))
233 std::swap(losers[pos].sup, sup);
234 std::swap(losers[pos].source, source);
235 std::swap(losers[pos].key, key);
240 losers[0].source = source;
250 template<
typename T,
typename Comparator>
255 using Base::_M_log_k;
258 using Base::first_insert;
261 LoserTree(
unsigned int _k, Comparator _comp)
262 : Base::LoserTreeBase(_k, _comp)
281 unsigned int left = init_winner (2 * root);
282 unsigned int right = init_winner (2 * root + 1);
283 if (losers[right].sup ||
285 && !comp(losers[right].key, losers[left].key)))
288 losers[root] = losers[
right];
294 losers[root] = losers[
left];
302 { losers[0] = losers[init_winner(1)]; }
314 #if _GLIBCXX_ASSERTIONS
316 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
319 int source = losers[0].source;
320 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
323 if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
326 std::swap(losers[pos].sup, sup);
327 std::swap(losers[pos].source, source);
328 std::swap(losers[pos].key, key);
333 losers[0].source = source;
342 template<
typename T,
typename Comparator>
354 unsigned int ik, k, offset;
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].sup =
true;
373 { ::operator
delete[](losers); }
376 {
return losers[0].source; }
378 void insert_start(
const T& key,
int source,
bool sup)
380 unsigned int pos = k + source;
382 losers[pos].sup = sup;
383 losers[pos].source = source;
384 losers[pos].keyp = &key;
393 template<
bool stable,
typename T,
typename Comparator>
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].sup
417 || (!losers[left].sup && !comp(*losers[right].keyp,
418 *losers[left].keyp)))
421 losers[root] = losers[
right];
427 losers[root] = losers[
left];
434 { losers[0] = losers[init_winner(1)]; }
436 void delete_min_insert(
const T& key,
bool sup)
438 #if _GLIBCXX_ASSERTIONS
440 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
443 const T* keyp = &key;
444 int source = losers[0].source;
445 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
448 if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
449 (!sup && !losers[pos].sup &&
450 ((comp(*losers[pos].keyp, *keyp)) ||
451 (!comp(*keyp, *losers[pos].keyp)
452 && losers[pos].source < source))))
455 std::swap(losers[pos].sup, sup);
456 std::swap(losers[pos].source, source);
457 std::swap(losers[pos].keyp, keyp);
462 losers[0].source = source;
463 losers[0].keyp = keyp;
472 template<
typename T,
typename Comparator>
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].sup
497 || (!losers[left].sup
498 && !comp(*losers[right].keyp, *losers[left].keyp)))
501 losers[root] = losers[
right];
507 losers[root] = losers[
left];
514 { losers[0] = losers[init_winner(1)]; }
516 void delete_min_insert(
const T& key,
bool sup)
518 #if _GLIBCXX_ASSERTIONS
520 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
523 const T* keyp = &key;
524 int source = losers[0].source;
525 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
528 if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
531 std::swap(losers[pos].sup, sup);
532 std::swap(losers[pos].source, source);
533 std::swap(losers[pos].keyp, keyp);
538 losers[0].source = source;
539 losers[0].keyp = keyp;
553 template<
typename T,
typename Comparator>
563 unsigned int ik, k, offset;
576 k = 1 << (
__log2(ik - 1) + 1);
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].key = _sentinel;
584 losers[i].source = -1;
589 { ::operator
delete(losers); }
594 #if _GLIBCXX_ASSERTIONS
596 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
598 return losers[0].source;
602 insert_start(
const T& key,
int source,
bool)
604 unsigned int pos = k + source;
606 new(&(losers[pos].key)) T(key);
607 losers[pos].source = source;
616 template<
bool stable,
typename T,
typename Comparator>
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].key, losers[left].key))
643 losers[root] = losers[
right];
649 losers[root] = losers[
left];
658 losers[0] = losers[init_winner(1)];
660 #if _GLIBCXX_ASSERTIONS
662 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
668 delete_min_insert(T key,
bool)
670 #if _GLIBCXX_ASSERTIONS
672 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
675 int source = losers[0].source;
676 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
679 if (comp(losers[pos].key, key)
680 || (!comp(key, losers[pos].key) && losers[pos].source < source))
683 std::swap(losers[pos].source, source);
684 std::swap(losers[pos].key, key);
688 losers[0].source = source;
698 template<
typename T,
typename Comparator>
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
726 if (losers[left].source == -1)
727 _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
730 if (!comp(losers[right].key, losers[left].key))
733 losers[root] = losers[
right];
739 losers[root] = losers[
left];
748 losers[0] = losers[init_winner(1)];
750 #if _GLIBCXX_ASSERTIONS
752 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
758 delete_min_insert(T key,
bool)
760 #if _GLIBCXX_ASSERTIONS
762 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
765 int source = losers[0].source;
766 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
769 if (comp(losers[pos].key, key))
772 std::swap(losers[pos].source, source);
773 std::swap(losers[pos].key, key);
777 losers[0].source = source;
788 template<
typename T,
typename Comparator>
798 unsigned int ik, k, offset;
812 k = 1 << (
__log2(ik - 1) + 1);
815 losers =
new Loser[2 * k];
817 for (
unsigned int i = k + ik - 1; i < (2 * k); ++i)
819 losers[i].keyp = &_sentinel;
820 losers[i].source = -1;
830 #if _GLIBCXX_ASSERTIONS
832 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
834 return losers[0].source;
838 insert_start(
const T& key,
int source,
bool)
840 unsigned int pos = k + source;
842 losers[pos].keyp = &key;
843 losers[pos].source = source;
852 template<
bool stable,
typename T,
typename Comparator>
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].keyp, *losers[left].keyp))
880 losers[root] = losers[
right];
886 losers[root] = losers[
left];
895 losers[0] = losers[init_winner(1)];
897 #if _GLIBCXX_ASSERTIONS
899 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
904 delete_min_insert(
const T& key,
bool sup)
906 #if _GLIBCXX_ASSERTIONS
908 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
911 const T* keyp = &key;
912 int source = losers[0].source;
913 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
916 if (comp(*losers[pos].keyp, *keyp)
917 || (!comp(*keyp, *losers[pos].keyp) && losers[pos].source < source))
920 std::swap(losers[pos].source, source);
921 std::swap(losers[pos].keyp, keyp);
925 losers[0].source = source;
926 losers[0].keyp = keyp;
935 template<
typename T,
typename Comparator>
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
963 if (losers[left].source == -1)
964 _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
967 if (!comp(*losers[right].keyp, *losers[left].keyp))
970 losers[root] = losers[
right];
976 losers[root] = losers[
left];
985 losers[0] = losers[init_winner(1)];
987 #if _GLIBCXX_ASSERTIONS
989 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
994 delete_min_insert(
const T& key,
bool sup)
996 #if _GLIBCXX_ASSERTIONS
998 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
1001 const T* keyp = &key;
1002 int source = losers[0].source;
1003 for (
unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
1006 if (comp(*(losers[pos].keyp), *keyp))
1009 std::swap(losers[pos].source, source);
1010 std::swap(losers[pos].keyp, keyp);
1014 losers[0].source = source;
1015 losers[0].keyp = keyp;
Stable unguarded LoserTree variant storing pointers.
Base class of Loser Tree implementation using pointers.
Loser * losers
LoserTree elements.
void delete_min_insert(T key, bool sup)
Stable implementation of unguarded LoserTree.
void delete_min_insert(T key, bool sup)
Delete the smallest element and insert a new element from the previously smallest element's sequence...
Defines on whether to include algorithm variants.
Internal representation of LoserTree elements.
Comparator comp
Comparator to use.
bool first_insert
State flag that determines whether the LoserTree is empty.
ios_base & right(ios_base &__base)
Calls base.setf(ios_base::right, ios_base::adjustfield).
Guarded loser/tournament tree.
Unguarded loser tree, keeping only pointers to the elements in the tree structure.
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library...
Base class for unguarded LoserTree implementation.
ios_base & left(ios_base &__base)
Calls base.setf(ios_base::left, ios_base::adjustfield).
Stable LoserTree implementation.
unsigned int init_winner(unsigned int root)
int source
index of the source sequence.
T key
key of the element in the LoserTree.
LoserTreeBase(unsigned int _k, Comparator _comp)
The constructor.
~LoserTreeBase()
The destructor.
void insert_start(const T &key, int source, bool sup)
Initializes the sequence "source" with the element "key".
Stable LoserTree variant.
bool sup
flag, true iff this is a "maximum" sentinel.
Size __log2(Size n)
Calculates the rounded-down logarithm of n for base 2.
Internal representation of a LoserTree element.
One of the comparison functors.