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