1// -*- C++ -*- 2 3// Copyright (C) 2007-2013 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/algorithmfwd.h> 42#include <parallel/find.h> 43#include <parallel/find_selectors.h> 44 45namespace std _GLIBCXX_VISIBILITY(default) 46{ 47namespace __parallel 48{ 49 // NB: equal and lexicographical_compare require mismatch. 50 51 // Sequential fallback 52 template<typename _IIter1, typename _IIter2> 53 inline pair<_IIter1, _IIter2> 54 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 55 __gnu_parallel::sequential_tag) 56 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); } 57 58 // Sequential fallback 59 template<typename _IIter1, typename _IIter2, typename _Predicate> 60 inline pair<_IIter1, _IIter2> 61 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 62 _Predicate __pred, __gnu_parallel::sequential_tag) 63 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 64 65 // Sequential fallback for input iterator case 66 template<typename _IIter1, typename _IIter2, 67 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 68 inline pair<_IIter1, _IIter2> 69 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 70 _Predicate __pred, _IteratorTag1, _IteratorTag2) 71 { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); } 72 73 // Parallel mismatch for random access iterators 74 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 75 pair<_RAIter1, _RAIter2> 76 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1, 77 _RAIter2 __begin2, _Predicate __pred, 78 random_access_iterator_tag, random_access_iterator_tag) 79 { 80 if (_GLIBCXX_PARALLEL_CONDITION(true)) 81 { 82 _RAIter1 __res = 83 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred, 84 __gnu_parallel:: 85 __mismatch_selector()).first; 86 return make_pair(__res , __begin2 + (__res - __begin1)); 87 } 88 else 89 return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); 90 } 91 92 // Public interface 93 template<typename _IIter1, typename _IIter2> 94 inline pair<_IIter1, _IIter2> 95 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 96 { 97 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 98 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 99 typedef typename _Iterator1Traits::value_type _ValueType1; 100 typedef typename _Iterator2Traits::value_type _ValueType2; 101 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 102 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 103 104 typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo; 105 106 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(), 107 _IteratorCategory1(), _IteratorCategory2()); 108 } 109 110 // Public interface 111 template<typename _IIter1, typename _IIter2, typename _Predicate> 112 inline pair<_IIter1, _IIter2> 113 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 114 _Predicate __pred) 115 { 116 typedef std::iterator_traits<_IIter1> _Iterator1Traits; 117 typedef std::iterator_traits<_IIter2> _Iterator2Traits; 118 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; 119 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; 120 121 return __mismatch_switch(__begin1, __end1, __begin2, __pred, 122 _IteratorCategory1(), _IteratorCategory2()); 123 } 124 125 // Sequential fallback 126 template<typename _IIter1, typename _IIter2> 127 inline bool 128 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 129 __gnu_parallel::sequential_tag) 130 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); } 131 132 // Sequential fallback 133 template<typename _IIter1, typename _IIter2, typename _Predicate> 134 inline bool 135 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 136 _Predicate __pred, __gnu_parallel::sequential_tag) 137 { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); } 138 139 // Public interface 140 template<typename _IIter1, typename _IIter2> 141 inline bool 142 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2) 143 { 144 return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first 145 == __end1; 146 } 147 148 // Public interface 149 template<typename _IIter1, typename _IIter2, typename _Predicate> 150 inline bool 151 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 152 _Predicate __pred) 153 { 154 return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first 155 == __end1; 156 } 157 158 // Sequential fallback 159 template<typename _IIter1, typename _IIter2> 160 inline bool 161 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 162 _IIter2 __begin2, _IIter2 __end2, 163 __gnu_parallel::sequential_tag) 164 { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1, 165 __begin2, __end2); } 166 167 // Sequential fallback 168 template<typename _IIter1, typename _IIter2, typename _Predicate> 169 inline bool 170 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 171 _IIter2 __begin2, _IIter2 __end2, 172 _Predicate __pred, __gnu_parallel::sequential_tag) 173 { return _GLIBCXX_STD_A::lexicographical_compare( 174 __begin1, __end1, __begin2, __end2, __pred); } 175 176 // Sequential fallback for input iterator case 177 template<typename _IIter1, typename _IIter2, 178 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2> 179 inline bool 180 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1, 181 _IIter2 __begin2, _IIter2 __end2, 182 _Predicate __pred, 183 _IteratorTag1, _IteratorTag2) 184 { return _GLIBCXX_STD_A::lexicographical_compare( 185 __begin1, __end1, __begin2, __end2, __pred); } 186 187 // Parallel lexicographical_compare for random access iterators 188 // Limitation: Both valuetypes must be the same 189 template<typename _RAIter1, typename _RAIter2, typename _Predicate> 190 bool 191 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1, 192 _RAIter2 __begin2, _RAIter2 __end2, 193 _Predicate __pred, 194 random_access_iterator_tag, 195 random_access_iterator_tag) 196 { 197 if (_GLIBCXX_PARALLEL_CONDITION(true)) 198 { 199 typedef iterator_traits<_RAIter1> _TraitsType1; 200 typedef typename _TraitsType1::value_type _ValueType1; 201 202 typedef iterator_traits<_RAIter2> _TraitsType2; 203 typedef typename _TraitsType2::value_type _ValueType2; 204 205 typedef __gnu_parallel:: 206 _EqualFromLess<_ValueType1, _ValueType2, _Predicate> 207 _EqualFromLessCompare; 208 209 // Longer sequence in first place. 210 if ((__end1 - __begin1) < (__end2 - __begin2)) 211 { 212 typedef pair<_RAIter1, _RAIter2> _SpotType; 213 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2, 214 _EqualFromLessCompare(__pred), 215 random_access_iterator_tag(), 216 random_access_iterator_tag()); 217 218 return (__mm.first == __end1) 219 || bool(__pred(*__mm.first, *__mm.second)); 220 } 221 else 222 { 223 typedef pair<_RAIter2, _RAIter1> _SpotType; 224 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1, 225 _EqualFromLessCompare(__pred), 226 random_access_iterator_tag(), 227 random_access_iterator_tag()); 228 229 return (__mm.first != __end2) 230 && bool(__pred(*__mm.second, *__mm.first)); 231 } 232 } 233 else 234 return _GLIBCXX_STD_A::lexicographical_compare( 235 __begin1, __end1, __begin2, __end2, __pred); 236 } 237 238 // Public interface 239 template<typename _IIter1, typename _IIter2> 240 inline bool 241 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 242 _IIter2 __begin2, _IIter2 __end2) 243 { 244 typedef iterator_traits<_IIter1> _TraitsType1; 245 typedef typename _TraitsType1::value_type _ValueType1; 246 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 247 248 typedef iterator_traits<_IIter2> _TraitsType2; 249 typedef typename _TraitsType2::value_type _ValueType2; 250 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 251 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType; 252 253 return __lexicographical_compare_switch( 254 __begin1, __end1, __begin2, __end2, _LessType(), 255 _IteratorCategory1(), _IteratorCategory2()); 256 } 257 258 // Public interface 259 template<typename _IIter1, typename _IIter2, typename _Predicate> 260 inline bool 261 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1, 262 _IIter2 __begin2, _IIter2 __end2, 263 _Predicate __pred) 264 { 265 typedef iterator_traits<_IIter1> _TraitsType1; 266 typedef typename _TraitsType1::iterator_category _IteratorCategory1; 267 268 typedef iterator_traits<_IIter2> _TraitsType2; 269 typedef typename _TraitsType2::iterator_category _IteratorCategory2; 270 271 return __lexicographical_compare_switch( 272 __begin1, __end1, __begin2, __end2, __pred, 273 _IteratorCategory1(), _IteratorCategory2()); 274 } 275} // end namespace 276} // end namespace 277 278#endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ 279