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/algobase.h 00026 * @brief Parallel STL function calls corresponding to the 00027 * stl_algobase.h header. The functions defined here mainly do case 00028 * switches and call the actual parallelized versions in other files. 00029 * Inlining policy: Functions that basically only contain one 00030 * function call, are declared inline. 00031 * This file is a GNU parallel extension to the Standard C++ Library. 00032 */ 00033 00034 // Written by Johannes Singler and Felix Putze. 00035 00036 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H 00037 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1 00038 00039 #include <bits/stl_algobase.h> 00040 #include <parallel/base.h> 00041 #include <parallel/algorithmfwd.h> 00042 #include <parallel/find.h> 00043 #include <parallel/find_selectors.h> 00044 00045 namespace std _GLIBCXX_VISIBILITY(default) 00046 { 00047 namespace __parallel 00048 { 00049 // NB: equal and lexicographical_compare require mismatch. 00050 00051 // Sequential fallback 00052 template<typename _IIter1, typename _IIter2> 00053 inline pair<_IIter1, _IIter2> 00054 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00055 __gnu_parallel::sequential_tag) 00056 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); } 00057 00058 // Sequential fallback 00059 template<typename _IIter1, typename _IIter2, typename _Predicate> 00060 inline pair<_IIter1, _IIter2> 00061 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00062 _Predicate __pred, __gnu_parallel::sequential_tag) 00063 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 00064 00065 // Sequential fallback for input iterator case 00066 template<typename _IIter1, typename _IIter2, 00067 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00068 inline pair<_IIter1, _IIter2> 00069 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00070 _Predicate __pred, _IteratorTag1, _IteratorTag2) 00071 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 00072 00073 // Parallel mismatch for random access iterators 00074 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 00075 pair<_RAIter1, _RAIter2> 00076 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 00077 _RAIter2 __begin2, _Predicate __pred, 00078 random_access_iterator_tag, random_access_iterator_tag) 00079 { 00080 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00081 { 00082 _RAIter1 __res = 00083 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 00084 __gnu_parallel:: 00085 __mismatch_selector()).first; 00086 return make_pair(__res , __begin2 + (__res - __begin1)); 00087 } 00088 else 00089 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); 00090 } 00091 00092 // Public interface 00093 template<typename _IIter1, typename _IIter2> 00094 inline pair<_IIter1, _IIter2> 00095 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 00096 { 00097 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 00098 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 00099 typedef typename _Iterator1Traits::value_type _ValueType1; 00100 typedef typename _Iterator2Traits::value_type _ValueType2; 00101 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 00102 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 00103 00104 typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo; 00105 00106 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), 00107 _IteratorCategory1(), _IteratorCategory2()); 00108 } 00109 00110 // Public interface 00111 template<typename _IIter1, typename _IIter2, typename _Predicate> 00112 inline pair<_IIter1, _IIter2> 00113 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00114 _Predicate __pred) 00115 { 00116 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 00117 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 00118 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 00119 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 00120 00121 return __mismatch_switch(__begin1, __end1, __begin2, __pred, 00122 _IteratorCategory1(), _IteratorCategory2()); 00123 } 00124 00125 // Sequential fallback 00126 template<typename _IIter1, typename _IIter2> 00127 inline bool 00128 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00129 __gnu_parallel::sequential_tag) 00130 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); } 00131 00132 // Sequential fallback 00133 template<typename _IIter1, typename _IIter2, typename _Predicate> 00134 inline bool 00135 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00136 _Predicate __pred, __gnu_parallel::sequential_tag) 00137 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); } 00138 00139 // Public interface 00140 template<typename _IIter1, typename _IIter2> 00141 inline bool 00142 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 00143 { 00144 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first 00145 == __end1; 00146 } 00147 00148 // Public interface 00149 template<typename _IIter1, typename _IIter2, typename _Predicate> 00150 inline bool 00151 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 00152 _Predicate __pred) 00153 { 00154 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first 00155 == __end1; 00156 } 00157 00158 // Sequential fallback 00159 template<typename _IIter1, typename _IIter2> 00160 inline bool 00161 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00162 _IIter2 __begin2, _IIter2 __end2, 00163 __gnu_parallel::sequential_tag) 00164 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 00165 __begin2, __end2); } 00166 00167 // Sequential fallback 00168 template<typename _IIter1, typename _IIter2, typename _Predicate> 00169 inline bool 00170 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00171 _IIter2 __begin2, _IIter2 __end2, 00172 _Predicate __pred, __gnu_parallel::sequential_tag) 00173 { return _GLIBCXX_STD_A::lexicographical_compare( 00174 __begin1, __end1, __begin2, __end2, __pred); } 00175 00176 // Sequential fallback for input iterator case 00177 template<typename _IIter1, typename _IIter2, 00178 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 00179 inline bool 00180 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1, 00181 _IIter2 __begin2, _IIter2 __end2, 00182 _Predicate __pred, 00183 _IteratorTag1, _IteratorTag2) 00184 { return _GLIBCXX_STD_A::lexicographical_compare( 00185 __begin1, __end1, __begin2, __end2, __pred); } 00186 00187 // Parallel lexicographical_compare for random access iterators 00188 // Limitation: Both valuetypes must be the same 00189 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 00190 bool 00191 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1, 00192 _RAIter2 __begin2, _RAIter2 __end2, 00193 _Predicate __pred, 00194 random_access_iterator_tag, 00195 random_access_iterator_tag) 00196 { 00197 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00198 { 00199 typedef iterator_traits<_RAIter1> _TraitsType1; 00200 typedef typename _TraitsType1::value_type _ValueType1; 00201 00202 typedef iterator_traits<_RAIter2> _TraitsType2; 00203 typedef typename _TraitsType2::value_type _ValueType2; 00204 00205 typedef __gnu_parallel:: 00206 _EqualFromLess<_ValueType1, _ValueType2, _Predicate> 00207 _EqualFromLessCompare; 00208 00209 // Longer sequence in first place. 00210 if ((__end1 - __begin1) < (__end2 - __begin2)) 00211 { 00212 typedef pair<_RAIter1, _RAIter2> _SpotType; 00213 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 00214 _EqualFromLessCompare(__pred), 00215 random_access_iterator_tag(), 00216 random_access_iterator_tag()); 00217 00218 return (__mm.first == __end1) 00219 || bool(__pred(*__mm.first, *__mm.second)); 00220 } 00221 else 00222 { 00223 typedef pair<_RAIter2, _RAIter1> _SpotType; 00224 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 00225 _EqualFromLessCompare(__pred), 00226 random_access_iterator_tag(), 00227 random_access_iterator_tag()); 00228 00229 return (__mm.first != __end2) 00230 && bool(__pred(*__mm.second, *__mm.first)); 00231 } 00232 } 00233 else 00234 return _GLIBCXX_STD_A::lexicographical_compare( 00235 __begin1, __end1, __begin2, __end2, __pred); 00236 } 00237 00238 // Public interface 00239 template<typename _IIter1, typename _IIter2> 00240 inline bool 00241 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00242 _IIter2 __begin2, _IIter2 __end2) 00243 { 00244 typedef iterator_traits<_IIter1> _TraitsType1; 00245 typedef typename _TraitsType1::value_type _ValueType1; 00246 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00247 00248 typedef iterator_traits<_IIter2> _TraitsType2; 00249 typedef typename _TraitsType2::value_type _ValueType2; 00250 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00251 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType; 00252 00253 return __lexicographical_compare_switch( 00254 __begin1, __end1, __begin2, __end2, _LessType(), 00255 _IteratorCategory1(), _IteratorCategory2()); 00256 } 00257 00258 // Public interface 00259 template<typename _IIter1, typename _IIter2, typename _Predicate> 00260 inline bool 00261 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 00262 _IIter2 __begin2, _IIter2 __end2, 00263 _Predicate __pred) 00264 { 00265 typedef iterator_traits<_IIter1> _TraitsType1; 00266 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 00267 00268 typedef iterator_traits<_IIter2> _TraitsType2; 00269 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 00270 00271 return __lexicographical_compare_switch( 00272 __begin1, __end1, __begin2, __end2, __pred, 00273 _IteratorCategory1(), _IteratorCategory2()); 00274 } 00275 } // end namespace 00276 } // end namespace 00277 00278 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */