1 // -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file parallel/algobase.h 26 * @brief Parallel STL function calls corresponding to the 27 * stl_algobase.h header. The functions defined here mainly do case 28 * switches and call the actual parallelized versions in other files. 29 * Inlining policy: Functions that basically only contain one 30 * function call, are declared inline. 31 * This file is a GNU parallel extension to the Standard C++ Library. 32 */ 33 34 // Written by Johannes Singler and Felix Putze. 35 36 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H 37 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1 38 39 #include <bits/stl_algobase.h> 40 #include <parallel/base.h> 41 #include <parallel/tags.h> 42 #include <parallel/settings.h> 43 #include <parallel/find.h> 44 #include <parallel/find_selectors.h> 45 46 namespace std 47 { 48 namespace __parallel 49 { 50 // NB: equal and lexicographical_compare require mismatch. 51 52 // Sequential fallback 53 template<typename _IIter1, typename _IIter2> 54 inline pair<_IIter1, _IIter2> 55 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 56 __gnu_parallel::sequential_tag) 57 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2); } 58 59 // Sequential fallback 60 template<typename _IIter1, typename _IIter2, typename _Predicate> 61 inline pair<_IIter1, _IIter2> 62 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 63 _Predicate __pred, __gnu_parallel::sequential_tag) 64 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); } 65 66 // Sequential fallback for input iterator case 67 template<typename _IIter1, typename _IIter2, 68 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 69 inline pair<_IIter1, _IIter2> 70 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 71 _Predicate __pred, _IteratorTag1, _IteratorTag2) 72 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); } 73 74 // Parallel mismatch for random access iterators 75 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 76 pair<_RAIter1, _RAIter2> 77 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 78 _RAIter2 __begin2, _Predicate __pred, 79 random_access_iterator_tag, random_access_iterator_tag) 80 { 81 if (_GLIBCXX_PARALLEL_CONDITION(true)) 82 { 83 _RAIter1 __res = 84 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 85 __gnu_parallel:: 86 __mismatch_selector()).first; 87 return make_pair(__res , __begin2 + (__res - __begin1)); 88 } 89 else 90 return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); 91 } 92 93 // Public interface 94 template<typename _IIter1, typename _IIter2> 95 inline pair<_IIter1, _IIter2> 96 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 97 { 98 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 99 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 100 typedef typename _Iterator1Traits::value_type _ValueType1; 101 typedef typename _Iterator2Traits::value_type _ValueType2; 102 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 103 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 104 105 typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo; 106 107 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), 108 _IteratorCategory1(), _IteratorCategory2()); 109 } 110 111 // Public interface 112 template<typename _IIter1, typename _IIter2, typename _Predicate> 113 inline pair<_IIter1, _IIter2> 114 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 115 _Predicate __pred) 116 { 117 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 118 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 119 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 120 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 121 122 return __mismatch_switch(__begin1, __end1, __begin2, __pred, 123 _IteratorCategory1(), _IteratorCategory2()); 124 } 125 126 // Sequential fallback 127 template<typename _IIter1, typename _IIter2> 128 inline bool 129 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 130 __gnu_parallel::sequential_tag) 131 { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2); } 132 133 // Sequential fallback 134 template<typename _IIter1, typename _IIter2, typename _Predicate> 135 inline bool 136 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 137 _Predicate __pred, __gnu_parallel::sequential_tag) 138 { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2, __pred); } 139 140 // Public interface 141 template<typename _IIter1, typename _IIter2> 142 inline bool 143 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 144 { 145 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first 146 == __end1; 147 } 148 149 // Public interface 150 template<typename _IIter1, typename _IIter2, typename _Predicate> 151 inline bool 152 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 153 _Predicate __pred) 154 { 155 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first 156 == __end1; 157 } 158 159 // Sequential fallback 160 template<typename _IIter1, typename _IIter2> 161 inline bool 162 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 163 _IIter2 __begin2, _IIter2 __end2, 164 __gnu_parallel::sequential_tag) 165 { return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1, 166 __begin2, __end2); } 167 168 // Sequential fallback 169 template<typename _IIter1, typename _IIter2, typename _Predicate> 170 inline bool 171 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 172 _IIter2 __begin2, _IIter2 __end2, 173 _Predicate __pred, __gnu_parallel::sequential_tag) 174 { return _GLIBCXX_STD_P::lexicographical_compare( 175 __begin1, __end1, __begin2, __end2, __pred); } 176 177 // Sequential fallback for input iterator case 178 template<typename _IIter1, typename _IIter2, 179 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 180 inline bool 181 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1, 182 _IIter2 __begin2, _IIter2 __end2, 183 _Predicate __pred, 184 _IteratorTag1, _IteratorTag2) 185 { return _GLIBCXX_STD_P::lexicographical_compare( 186 __begin1, __end1, __begin2, __end2, __pred); } 187 188 // Parallel lexicographical_compare for random access iterators 189 // Limitation: Both valuetypes must be the same 190 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 191 bool 192 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1, 193 _RAIter2 __begin2, _RAIter2 __end2, 194 _Predicate __pred, 195 random_access_iterator_tag, 196 random_access_iterator_tag) 197 { 198 if (_GLIBCXX_PARALLEL_CONDITION(true)) 199 { 200 typedef iterator_traits<_RAIter1> _TraitsType1; 201 typedef typename _TraitsType1::value_type _ValueType1; 202 203 typedef iterator_traits<_RAIter2> _TraitsType2; 204 typedef typename _TraitsType2::value_type _ValueType2; 205 206 typedef __gnu_parallel:: 207 _EqualFromLess<_ValueType1, _ValueType2, _Predicate> 208 _EqualFromLessCompare; 209 210 // Longer sequence in first place. 211 if ((__end1 - __begin1) < (__end2 - __begin2)) 212 { 213 typedef pair<_RAIter1, _RAIter2> _SpotType; 214 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 215 _EqualFromLessCompare(__pred), 216 random_access_iterator_tag(), 217 random_access_iterator_tag()); 218 219 return (__mm.first == __end1) 220 || bool(__pred(*__mm.first, *__mm.second)); 221 } 222 else 223 { 224 typedef pair<_RAIter2, _RAIter1> _SpotType; 225 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 226 _EqualFromLessCompare(__pred), 227 random_access_iterator_tag(), 228 random_access_iterator_tag()); 229 230 return (__mm.first != __end2) 231 && bool(__pred(*__mm.second, *__mm.first)); 232 } 233 } 234 else 235 return _GLIBCXX_STD_P::lexicographical_compare( 236 __begin1, __end1, __begin2, __end2, __pred); 237 } 238 239 // Public interface 240 template<typename _IIter1, typename _IIter2> 241 inline bool 242 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 243 _IIter2 __begin2, _IIter2 __end2) 244 { 245 typedef iterator_traits<_IIter1> _TraitsType1; 246 typedef typename _TraitsType1::value_type _ValueType1; 247 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 248 249 typedef iterator_traits<_IIter2> _TraitsType2; 250 typedef typename _TraitsType2::value_type _ValueType2; 251 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 252 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType; 253 254 return __lexicographical_compare_switch( 255 __begin1, __end1, __begin2, __end2, _LessType(), 256 _IteratorCategory1(), _IteratorCategory2()); 257 } 258 259 // Public interface 260 template<typename _IIter1, typename _IIter2, typename _Predicate> 261 inline bool 262 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 263 _IIter2 __begin2, _IIter2 __end2, 264 _Predicate __pred) 265 { 266 typedef iterator_traits<_IIter1> _TraitsType1; 267 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 268 269 typedef iterator_traits<_IIter2> _TraitsType2; 270 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 271 272 return __lexicographical_compare_switch( 273 __begin1, __end1, __begin2, __end2, __pred, 274 _IteratorCategory1(), _IteratorCategory2()); 275 } 276 } // end namespace 277 } // end namespace 278 279 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ 280