From 3234d6b0b0fe03b40710cd2ea7a6bcbbf7c0d7d9 Mon Sep 17 00:00:00 2001 From: Johannes Singler Date: Tue, 6 May 2008 08:55:57 +0000 Subject: [PATCH] 2008-05-06 Johannes Singler * include/parallel/multiway_merge.h: (multiway_merge_*_unguarded): Pass sentinel directly, to allow correct determination. (multiway_merge_loser_tree_unguarded): Remove over-cautious assertion. (calls to multiway_merge_*_splitting): Parametrize with type that is correct in all cases. * include/parallel/losertree.h: (delete_min_insert (in many classes)): Correct and standardize assertions. From-SVN: r134977 --- libstdc++-v3/ChangeLog | 13 ++ libstdc++-v3/include/parallel/losertree.h | 70 ++++++---- .../include/parallel/multiway_merge.h | 128 ++++++++++-------- 3 files changed, 133 insertions(+), 78 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index ff9ac66e394..b5201c5b332 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,16 @@ +2008-05-06 Johannes Singler + + * include/parallel/multiway_merge.h: + (multiway_merge_*_unguarded): + Pass sentinel directly, to allow correct determination. + (multiway_merge_loser_tree_unguarded): + Remove over-cautious assertion. + (calls to multiway_merge_*_splitting): + Parametrize with type that is correct in all cases. + * include/parallel/losertree.h: + (delete_min_insert (in many classes)): + Correct and standardize assertions. + 2008-05-05 Benjamin Kosnik * testsuite/util/testsuite_visualization.h: Move contents into... diff --git a/libstdc++-v3/include/parallel/losertree.h b/libstdc++-v3/include/parallel/losertree.h index cae15c0826e..3736b908557 100644 --- a/libstdc++-v3/include/parallel/losertree.h +++ b/libstdc++-v3/include/parallel/losertree.h @@ -220,6 +220,11 @@ public: // Do not pass a const reference since key will be used as local variable. void delete_min_insert(T key, bool sup) { +#if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); +#endif + int source = losers[0].source; for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) { @@ -313,8 +318,8 @@ public: delete_min_insert(T key, bool sup) { #if _GLIBCXX_ASSERTIONS - // loser trees are only used for at least 2 sequences - _GLIBCXX_PARALLEL_ASSERT(_M_log_k > 1); + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif int source = losers[0].source; @@ -436,6 +441,11 @@ public: void delete_min_insert(const T& key, bool sup) { +#if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); +#endif + const T* keyp = &key; int source = losers[0].source; for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) @@ -511,6 +521,11 @@ public: void delete_min_insert(const T& key, bool sup) { +#if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); +#endif + const T* keyp = &key; int source = losers[0].source; for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) @@ -569,7 +584,7 @@ public: // Avoid default-constructing losers[].key losers = static_cast(::operator new(2 * k * sizeof(Loser))); - for (unsigned int i = /*k + ik - 1*/0; i < (2 * k); ++i) + for (unsigned int i = k + ik - 1; i < (2 * k); ++i) { losers[i].key = _sentinel; losers[i].source = -1; @@ -582,8 +597,8 @@ public: inline int get_min_source() { - // no dummy sequence can ever be at the top! #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif return losers[0].source; @@ -648,8 +663,8 @@ public: { losers[0] = losers[init_winner(1)]; - // no dummy sequence can ever be at the top at the beginning (0 sequences!) #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top at the beginning (0 sequences!) _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif } @@ -658,13 +673,12 @@ public: inline void delete_min_insert(T key, bool) { - // No dummy sequence can ever be at the top and be retrieved! #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif int source = losers[0].source; - printf("%d\n", source); for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) { // The smaller one gets promoted, ties are broken by source. @@ -739,8 +753,8 @@ public: { losers[0] = losers[init_winner(1)]; - // no dummy sequence can ever be at the top at the beginning (0 sequences!) #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top at the beginning (0 sequences!) _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif } @@ -749,7 +763,11 @@ public: inline void delete_min_insert(T key, bool) { - printf("wrong\n"); +#if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); +#endif + int source = losers[0].source; for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) { @@ -785,15 +803,14 @@ protected: unsigned int ik, k, offset; Loser* losers; - const T sentinel; Comparator comp; public: inline - LoserTreePointerUnguardedBase(unsigned int _k, const T _sentinel, + LoserTreePointerUnguardedBase(unsigned int _k, const T& _sentinel, Comparator _comp = std::less()) - : sentinel(_sentinel), comp(_comp) + : comp(_comp) { ik = _k; @@ -803,9 +820,9 @@ public: // Avoid default-constructing losers[].key losers = new Loser[2 * k]; - for (unsigned int i = /*k + ik - 1*/0; i < (2 * k); ++i) + for (unsigned int i = k + ik - 1; i < (2 * k); ++i) { - losers[i].keyp = &sentinel; + losers[i].keyp = &_sentinel; losers[i].source = -1; } } @@ -816,8 +833,8 @@ public: inline int get_min_source() { - // no dummy sequence can ever be at the top! #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif return losers[0].source; @@ -847,7 +864,7 @@ class LoserTreePointerUnguarded : using Base::losers; public: - LoserTreePointerUnguarded(unsigned int _k, const T _sentinel, + LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel, Comparator _comp = std::less()) : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp) {} @@ -883,8 +900,8 @@ public: { losers[0] = losers[init_winner(1)]; - // no dummy sequence can ever be at the top at the beginning (0 sequences!) #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top at the beginning (0 sequences!) _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif } @@ -892,6 +909,11 @@ public: inline void delete_min_insert(const T& key, bool sup) { +#if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); +#endif + const T* keyp = &key; int source = losers[0].source; for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) @@ -908,11 +930,6 @@ public: losers[0].source = source; losers[0].keyp = keyp; - - // no dummy sequence can ever be at the top! -#if _GLIBCXX_ASSERTIONS - _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); -#endif } }; @@ -930,7 +947,7 @@ class LoserTreePointerUnguarded : using Base::losers; public: - LoserTreePointerUnguarded(unsigned int _k, const T _sentinel, + LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel, Comparator _comp = std::less()) : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp) {} @@ -973,8 +990,8 @@ public: { losers[0] = losers[init_winner(1)]; - // no dummy sequence can ever be at the top at the beginning (0 sequences!) #if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top at the beginning (0 sequences!) _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); #endif } @@ -982,6 +999,11 @@ public: inline void delete_min_insert(const T& key, bool sup) { +#if _GLIBCXX_ASSERTIONS + // no dummy sequence can ever be at the top! + _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1); +#endif + const T* keyp = &key; int source = losers[0].source; for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2) diff --git a/libstdc++-v3/include/parallel/multiway_merge.h b/libstdc++-v3/include/parallel/multiway_merge.h index 0505722c8a4..37e99cdeb6a 100644 --- a/libstdc++-v3/include/parallel/multiway_merge.h +++ b/libstdc++-v3/include/parallel/multiway_merge.h @@ -615,15 +615,19 @@ template + typename RandomAccessIteratorIterator, + typename RandomAccessIterator3, + typename _DifferenceTp, typename Comparator> RandomAccessIterator3 - multiway_merge_loser_tree_unguarded(RandomAccessIteratorIterator seqs_begin, - RandomAccessIteratorIterator seqs_end, - RandomAccessIterator3 target, - int min_seq, Comparator comp, - _DifferenceTp length) + multiway_merge_loser_tree_unguarded( + RandomAccessIteratorIterator seqs_begin, + RandomAccessIteratorIterator seqs_end, + RandomAccessIterator3 target, + const typename std::iterator_traits::value_type::first_type>::value_type& + sentinel, + Comparator comp, + _DifferenceTp length) { _GLIBCXX_CALL(length) typedef _DifferenceTp difference_type; @@ -636,10 +640,6 @@ template= length - 1)); ++i; #endif // Replace from same source. @@ -712,11 +709,15 @@ template< typename _DifferenceTp, typename Comparator> RandomAccessIterator3 - multiway_merge_loser_tree_sentinel(RandomAccessIteratorIterator seqs_begin, - RandomAccessIteratorIterator seqs_end, - RandomAccessIterator3 target, - Comparator comp, - _DifferenceTp length) + multiway_merge_loser_tree_sentinel( + RandomAccessIteratorIterator seqs_begin, + RandomAccessIteratorIterator seqs_end, + RandomAccessIterator3 target, + const typename std::iterator_traits::value_type::first_type>::value_type& + sentinel, + Comparator comp, + _DifferenceTp length) { _GLIBCXX_CALL(length) @@ -739,7 +740,7 @@ template< target_end = multiway_merge_loser_tree_unguarded - (seqs_begin, seqs_end, target, 0, comp, length); + (seqs_begin, seqs_end, target, sentinel, comp, length); #if _GLIBCXX_ASSERTIONS _GLIBCXX_PARALLEL_ASSERT(target_end == target + length); @@ -904,6 +905,9 @@ struct multiway_merge_k_variant_sentinel_switch RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, + const typename std::iterator_traits::value_type::first_type>::value_type& + sentinel, Comparator comp, _DifferenceTp length) { typedef typename std::iterator_traits @@ -917,7 +921,7 @@ struct multiway_merge_k_variant_sentinel_switch loser_tree_traits::use_pointer , LoserTreePointerUnguarded , LoserTreeUnguarded - >::__type>(seqs_begin, seqs_end, target, comp, length); + >::__type>(seqs_begin, seqs_end, target, sentinel, comp, length); } }; @@ -938,6 +942,9 @@ struct multiway_merge_k_variant_sentinel_switch RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, + const typename std::iterator_traits::value_type::first_type>::value_type& + sentinel, Comparator comp, _DifferenceTp length) { typedef typename std::iterator_traits @@ -976,10 +983,14 @@ template< typename _DifferenceTp, typename Comparator> RandomAccessIterator3 - sequential_multiway_merge(RandomAccessIteratorIterator seqs_begin, - RandomAccessIteratorIterator seqs_end, - RandomAccessIterator3 target, - Comparator comp, _DifferenceTp length) + sequential_multiway_merge( + RandomAccessIteratorIterator seqs_begin, + RandomAccessIteratorIterator seqs_end, + RandomAccessIterator3 target, + const typename std::iterator_traits::value_type::first_type>::value_type& + sentinel, + Comparator comp, _DifferenceTp length) { _GLIBCXX_CALL(length) @@ -1049,7 +1060,8 @@ template< , RandomAccessIteratorIterator , RandomAccessIterator3 , _DifferenceTp - , Comparator>()(seqs_begin, seqs_end, target, comp, length); + , Comparator>() + (seqs_begin, seqs_end, target, sentinel, comp, length); break; } #if _GLIBCXX_ASSERTIONS @@ -1376,8 +1388,8 @@ template< if(length > target_position) sequential_multiway_merge( - chunks, chunks + k, target + target_position, comp, - length - target_position); + chunks, chunks + k, target + target_position, + *(seqs_begin->second), comp, length - target_position); delete[] chunks; } // parallel @@ -1501,13 +1513,14 @@ multiway_merge(RandomAccessIteratorPairIterator seqs_begin (seqs_begin, seqs_end, target, comp, multiway_merge_sampling_splitting, + typename std::iterator_traits + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } // public interface @@ -1533,7 +1546,7 @@ multiway_merge(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); } //public interface @@ -1570,13 +1583,14 @@ multiway_merge(RandomAccessIteratorPairIterator seqs_begin seqs_begin, seqs_end, target, comp, multiway_merge_exact_splitting, + typename std::iterator_traits + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } // public interface @@ -1612,13 +1626,14 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin seqs_begin, seqs_end, target, comp, multiway_merge_sampling_splitting, + typename std::iterator_traits + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } // public interface @@ -1644,7 +1659,7 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); } // public interface @@ -1681,14 +1696,15 @@ stable_multiway_merge(RandomAccessIteratorPairIterator seqs_begin seqs_begin, seqs_end, target, comp, multiway_merge_exact_splitting - , + + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } /** @@ -1798,14 +1814,15 @@ multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin (seqs_begin, seqs_end, target, comp, multiway_merge_sampling_splitting - , + + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } //public interface @@ -1831,7 +1848,7 @@ multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); } // public interface @@ -1868,14 +1885,15 @@ multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin seqs_begin, seqs_end, target, comp, multiway_merge_exact_splitting - , + + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } // public interface @@ -1911,14 +1929,15 @@ stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin seqs_begin, seqs_end, target, comp, multiway_merge_sampling_splitting - , + + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } // public interface @@ -1944,7 +1963,7 @@ stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin // Execute multiway merge *sequentially*. return sequential_multiway_merge - (seqs_begin, seqs_end, target, comp, length); + (seqs_begin, seqs_end, target, *(seqs_begin->second), comp, length); } // public interface @@ -1981,14 +2000,15 @@ stable_multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin seqs_begin, seqs_end, target, comp, multiway_merge_exact_splitting - , + + ::value_type*, Comparator, _DifferenceTp>, static_cast(length)); else return sequential_multiway_merge ( seqs_begin, seqs_end, - target, comp, length); + target, *(seqs_begin->second), comp, length); } }; // namespace __gnu_parallel -- 2.30.2