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 InputIterator1, typename InputIterator2> 54 inline pair<InputIterator1, InputIterator2> 55 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 56 __gnu_parallel::sequential_tag) 57 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); } 58 59 // Sequential fallback 60 template<typename InputIterator1, typename InputIterator2, 61 typename Predicate> 62 inline pair<InputIterator1, InputIterator2> 63 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 64 Predicate pred, __gnu_parallel::sequential_tag) 65 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } 66 67 // Sequential fallback for input iterator case 68 template<typename InputIterator1, typename InputIterator2, 69 typename Predicate, typename IteratorTag1, typename IteratorTag2> 70 inline pair<InputIterator1, InputIterator2> 71 mismatch_switch(InputIterator1 begin1, InputIterator1 end1, 72 InputIterator2 begin2, Predicate pred, IteratorTag1, 73 IteratorTag2) 74 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } 75 76 // Parallel mismatch for random access iterators 77 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 78 typename Predicate> 79 pair<RandomAccessIterator1, RandomAccessIterator2> 80 mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, 81 RandomAccessIterator2 begin2, Predicate pred, 82 random_access_iterator_tag, random_access_iterator_tag) 83 { 84 if (_GLIBCXX_PARALLEL_CONDITION(true)) 85 { 86 RandomAccessIterator1 res = 87 __gnu_parallel::find_template(begin1, end1, begin2, pred, 88 __gnu_parallel:: 89 mismatch_selector()).first; 90 return make_pair(res , begin2 + (res - begin1)); 91 } 92 else 93 return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); 94 } 95 96 // Public interface 97 template<typename InputIterator1, typename InputIterator2> 98 inline pair<InputIterator1, InputIterator2> 99 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) 100 { 101 typedef std::iterator_traits<InputIterator1> iterator1_traits; 102 typedef std::iterator_traits<InputIterator2> iterator2_traits; 103 typedef typename iterator1_traits::value_type value1_type; 104 typedef typename iterator2_traits::value_type value2_type; 105 typedef typename iterator1_traits::iterator_category iterator1_category; 106 typedef typename iterator2_traits::iterator_category iterator2_category; 107 108 typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type; 109 110 return mismatch_switch(begin1, end1, begin2, equal_to_type(), 111 iterator1_category(), iterator2_category()); 112 } 113 114 // Public interface 115 template<typename InputIterator1, typename InputIterator2, 116 typename Predicate> 117 inline pair<InputIterator1, InputIterator2> 118 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 119 Predicate pred) 120 { 121 typedef std::iterator_traits<InputIterator1> iterator1_traits; 122 typedef std::iterator_traits<InputIterator2> iterator2_traits; 123 typedef typename iterator1_traits::iterator_category iterator1_category; 124 typedef typename iterator2_traits::iterator_category iterator2_category; 125 126 return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), 127 iterator2_category()); 128 } 129 130 // Sequential fallback 131 template<typename InputIterator1, typename InputIterator2> 132 inline bool 133 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 134 __gnu_parallel::sequential_tag) 135 { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); } 136 137 // Sequential fallback 138 template<typename InputIterator1, typename InputIterator2, 139 typename Predicate> 140 inline bool 141 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 142 Predicate pred, __gnu_parallel::sequential_tag) 143 { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); } 144 145 // Public interface 146 template<typename InputIterator1, typename InputIterator2> 147 inline bool 148 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) 149 { return mismatch(begin1, end1, begin2).first == end1; } 150 151 // Public interface 152 template<typename InputIterator1, typename InputIterator2, 153 typename Predicate> 154 inline bool 155 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 156 Predicate pred) 157 { return mismatch(begin1, end1, begin2, pred).first == end1; } 158 159 // Sequential fallback 160 template<typename InputIterator1, typename InputIterator2> 161 inline bool 162 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 163 InputIterator2 begin2, InputIterator2 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 InputIterator1, typename InputIterator2, 170 typename Predicate> 171 inline bool 172 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 173 InputIterator2 begin2, InputIterator2 end2, 174 Predicate pred, __gnu_parallel::sequential_tag) 175 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 176 begin2, end2, pred); } 177 178 // Sequential fallback for input iterator case 179 template<typename InputIterator1, typename InputIterator2, 180 typename Predicate, typename IteratorTag1, typename IteratorTag2> 181 inline bool 182 lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, 183 InputIterator2 begin2, InputIterator2 end2, 184 Predicate pred, IteratorTag1, IteratorTag2) 185 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 186 begin2, end2, pred); } 187 188 // Parallel lexicographical_compare for random access iterators 189 // Limitation: Both valuetypes must be the same 190 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 191 typename Predicate> 192 bool 193 lexicographical_compare_switch(RandomAccessIterator1 begin1, 194 RandomAccessIterator1 end1, 195 RandomAccessIterator2 begin2, 196 RandomAccessIterator2 end2, Predicate pred, 197 random_access_iterator_tag, 198 random_access_iterator_tag) 199 { 200 if (_GLIBCXX_PARALLEL_CONDITION(true)) 201 { 202 typedef iterator_traits<RandomAccessIterator1> traits1_type; 203 typedef typename traits1_type::value_type value1_type; 204 205 typedef iterator_traits<RandomAccessIterator2> traits2_type; 206 typedef typename traits2_type::value_type value2_type; 207 208 typedef __gnu_parallel::equal_from_less<Predicate, value1_type, 209 value2_type> equal_type; 210 211 // Longer sequence in first place. 212 if ((end1 - begin1) < (end2 - begin2)) 213 { 214 typedef pair<RandomAccessIterator1, RandomAccessIterator2> 215 pair_type; 216 pair_type mm = mismatch_switch(begin1, end1, begin2, 217 equal_type(pred), 218 random_access_iterator_tag(), 219 random_access_iterator_tag()); 220 221 return (mm.first == end1) || bool(pred(*mm.first, *mm.second)); 222 } 223 else 224 { 225 typedef pair<RandomAccessIterator2, RandomAccessIterator1> 226 pair_type; 227 pair_type mm = mismatch_switch(begin2, end2, begin1, 228 equal_type(pred), 229 random_access_iterator_tag(), 230 random_access_iterator_tag()); 231 232 return (mm.first != end2) && bool(pred(*mm.second, *mm.first)); 233 } 234 } 235 else 236 return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 237 begin2, end2, pred); 238 } 239 240 // Public interface 241 template<typename InputIterator1, typename InputIterator2> 242 inline bool 243 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 244 InputIterator2 begin2, InputIterator2 end2) 245 { 246 typedef iterator_traits<InputIterator1> traits1_type; 247 typedef typename traits1_type::value_type value1_type; 248 typedef typename traits1_type::iterator_category iterator1_category; 249 250 typedef iterator_traits<InputIterator2> traits2_type; 251 typedef typename traits2_type::value_type value2_type; 252 typedef typename traits2_type::iterator_category iterator2_category; 253 typedef __gnu_parallel::less<value1_type, value2_type> less_type; 254 255 return lexicographical_compare_switch(begin1, end1, begin2, end2, 256 less_type(), iterator1_category(), 257 iterator2_category()); 258 } 259 260 // Public interface 261 template<typename InputIterator1, typename InputIterator2, 262 typename Predicate> 263 inline bool 264 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 265 InputIterator2 begin2, InputIterator2 end2, 266 Predicate pred) 267 { 268 typedef iterator_traits<InputIterator1> traits1_type; 269 typedef typename traits1_type::iterator_category iterator1_category; 270 271 typedef iterator_traits<InputIterator2> traits2_type; 272 typedef typename traits2_type::iterator_category iterator2_category; 273 274 return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, 275 iterator1_category(), 276 iterator2_category()); 277 } 278 } // end namespace 279 } // end namespace 280 281 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ 282
