2008-05-06 Johannes Singler <singler@ira.uka.de>

        * 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

3 files changed, 133 insertions, 78 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index ff9ac66..b5201c5 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,16 @@
+2008-05-06  Johannes Singler  <singler@ira.uka.de>
+
+        * 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  <bkoz@redhat.com>
 
 	* 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 cae15c0..3736b90 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<Loser*>(::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<T>())
-    : 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<T>())
     : 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</* stable == */false, T, Comparator> :
   using Base::losers;
 
 public:
-  LoserTreePointerUnguarded(unsigned int _k, const T _sentinel,
+  LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
       Comparator _comp = std::less<T>())
     : 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 0505722..37e99cd 100644
--- a/libstdc++-v3/include/parallel/multiway_merge.h
+++ b/libstdc++-v3/include/parallel/multiway_merge.h
@@ -615,15 +615,19 @@ template<typename LT,
  * @return End iterator of output sequence.
  */
 template<typename LT,
-	 typename RandomAccessIteratorIterator,
-	 typename RandomAccessIterator3,
-	 typename _DifferenceTp, typename Comparator>
+    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<typename std::iterator_traits<
+      RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+        sentinel,
+    Comparator comp,
+    _DifferenceTp length)
   {
     _GLIBCXX_CALL(length)
     typedef _DifferenceTp difference_type;
@@ -636,10 +640,6 @@ template<typename LT,
 
     int k = seqs_end - seqs_begin;
 
-    // Determine the sentinel.  The sentinel is largest/last element of the
-    // sequences with the smallest largest/last element.
-    value_type sentinel = *(seqs_begin[min_seq].second - 1);
-
     LT lt(k, sentinel, comp);
 
     for (int t = 0; t < k; ++t)
@@ -674,9 +674,6 @@ template<typename LT,
         *(target++) = *(seqs_begin[source].first++);
 
 #if _GLIBCXX_ASSERTIONS
-        _GLIBCXX_PARALLEL_ASSERT(
-            (seqs_begin[source].first != seqs_begin[source].second)
-            || (i >= 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<typename std::iterator_traits<
+      RandomAccessIteratorIterator>::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
         <UnguardedLoserTree>
-      (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<typename std::iterator_traits<
+        RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+          sentinel,
       Comparator comp, _DifferenceTp length)
   {
     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
@@ -917,7 +921,7 @@ struct multiway_merge_k_variant_sentinel_switch
             loser_tree_traits<value_type>::use_pointer
           , LoserTreePointerUnguarded<stable, value_type, Comparator>
           , LoserTreeUnguarded<stable, value_type, Comparator>
-        >::__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<typename std::iterator_traits<
+        RandomAccessIteratorIterator>::value_type::first_type>::value_type&
+          sentinel,
       Comparator comp, _DifferenceTp length)
   {
     typedef typename std::iterator_traits<RandomAccessIteratorIterator>
@@ -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<typename std::iterator_traits<
+      RandomAccessIteratorIterator>::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<stable, sentinels>(
-              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
       </* stable = */ false, /* sentinels = */ false>
         (seqs_begin, seqs_end, target, comp,
         multiway_merge_sampling_splitting</* stable = */ false,
-          RandomAccessIteratorPairIterator, Comparator, _DifferenceTp>,
+          typename std::iterator_traits<RandomAccessIteratorPairIterator>
+            ::value_type*, Comparator, _DifferenceTp>,
         static_cast<difference_type>(length));
   else
     return sequential_multiway_merge
       </* stable = */false, /* sentinels = */ false>(
         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
     </* stable = */ false, /* sentinels = */ false>
-      (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</* stable = */ false,
-            RandomAccessIteratorPairIterator, Comparator, _DifferenceTp>,
+            typename std::iterator_traits<RandomAccessIteratorPairIterator>
+              ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge
                       </* stable = */ false, /* sentinels = */ false>(
           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</* stable = */ true,
-          RandomAccessIteratorPairIterator, Comparator, _DifferenceTp>,
+            typename std::iterator_traits<RandomAccessIteratorPairIterator>
+              ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge
         </* stable = */ true, /* sentinels = */ false>(
           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
       </* stable = */ true, /* sentinels = */ false>
-        (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
-            </* stable = */ true, RandomAccessIteratorPairIterator,
-             Comparator, _DifferenceTp>,
+            </* stable = */ true,
+              typename std::iterator_traits<RandomAccessIteratorPairIterator>
+                ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge</* stable = */ true,
         /* sentinels = */ false>(
           seqs_begin, seqs_end,
-          target, comp, length);
+          target, *(seqs_begin->second), comp, length);
 }
 
 /**
@@ -1798,14 +1814,15 @@ multiway_merge_sentinels(RandomAccessIteratorPairIterator seqs_begin
         </* stable = */ false, /* sentinels = */ true>
           (seqs_begin, seqs_end, target, comp,
           multiway_merge_sampling_splitting
-            </* stable = */ false, RandomAccessIteratorPairIterator,
-             Comparator, _DifferenceTp>,
+            </* stable = */ false,
+              typename std::iterator_traits<RandomAccessIteratorPairIterator>
+                ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge
         </* stable = */false, /* sentinels = */ true>(
           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
       </* stable = */ false, /* sentinels = */ true>
-        (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
-            </* stable = */ false, RandomAccessIteratorPairIterator,
-              Comparator, _DifferenceTp>,
+            </* stable = */ false,
+              typename std::iterator_traits<RandomAccessIteratorPairIterator>
+                ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge
         </* stable = */ false, /* sentinels = */ true>(
           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
-            </* stable = */ true, RandomAccessIteratorPairIterator,
-            Comparator, _DifferenceTp>,
+            </* stable = */ true,
+              typename std::iterator_traits<RandomAccessIteratorPairIterator>
+                ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge
         </* stable = */ true, /* sentinels = */ true>(
           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
       </* stable = */ true, /* sentinels = */ true>
-        (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
-            </* stable = */ true, RandomAccessIteratorPairIterator,
-            Comparator, _DifferenceTp>,
+            </* stable = */ true,
+              typename std::iterator_traits<RandomAccessIteratorPairIterator>
+                ::value_type*, Comparator, _DifferenceTp>,
           static_cast<difference_type>(length));
     else
       return sequential_multiway_merge
         </* stable = */ true, /* sentinels = */ true>(
           seqs_begin, seqs_end,
-          target, comp, length);
+          target, *(seqs_begin->second), comp, length);
 }
 
 }; // namespace __gnu_parallel