libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 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 00047 { 00048 namespace __parallel 00049 { 00050 // NB: equal and lexicographical_compare require mismatch. 00051 00052 // Sequential fallback 00053 template<typename InputIterator1, typename InputIterator2> 00054 inline pair<InputIterator1, InputIterator2> 00055 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 00056 __gnu_parallel::sequential_tag) 00057 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2); } 00058 00059 // Sequential fallback 00060 template<typename InputIterator1, typename InputIterator2, 00061 typename Predicate> 00062 inline pair<InputIterator1, InputIterator2> 00063 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 00064 Predicate pred, __gnu_parallel::sequential_tag) 00065 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } 00066 00067 // Sequential fallback for input iterator case 00068 template<typename InputIterator1, typename InputIterator2, 00069 typename Predicate, typename IteratorTag1, typename IteratorTag2> 00070 inline pair<InputIterator1, InputIterator2> 00071 mismatch_switch(InputIterator1 begin1, InputIterator1 end1, 00072 InputIterator2 begin2, Predicate pred, IteratorTag1, 00073 IteratorTag2) 00074 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); } 00075 00076 // Parallel mismatch for random access iterators 00077 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00078 typename Predicate> 00079 pair<RandomAccessIterator1, RandomAccessIterator2> 00080 mismatch_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, 00081 RandomAccessIterator2 begin2, Predicate pred, 00082 random_access_iterator_tag, random_access_iterator_tag) 00083 { 00084 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00085 { 00086 RandomAccessIterator1 res = 00087 __gnu_parallel::find_template(begin1, end1, begin2, pred, 00088 __gnu_parallel:: 00089 mismatch_selector()).first; 00090 return make_pair(res , begin2 + (res - begin1)); 00091 } 00092 else 00093 return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred); 00094 } 00095 00096 // Public interface 00097 template<typename InputIterator1, typename InputIterator2> 00098 inline pair<InputIterator1, InputIterator2> 00099 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) 00100 { 00101 typedef std::iterator_traits<InputIterator1> iterator1_traits; 00102 typedef std::iterator_traits<InputIterator2> iterator2_traits; 00103 typedef typename iterator1_traits::value_type value1_type; 00104 typedef typename iterator2_traits::value_type value2_type; 00105 typedef typename iterator1_traits::iterator_category iterator1_category; 00106 typedef typename iterator2_traits::iterator_category iterator2_category; 00107 00108 typedef __gnu_parallel::equal_to<value1_type, value2_type> equal_to_type; 00109 00110 return mismatch_switch(begin1, end1, begin2, equal_to_type(), 00111 iterator1_category(), iterator2_category()); 00112 } 00113 00114 // Public interface 00115 template<typename InputIterator1, typename InputIterator2, 00116 typename Predicate> 00117 inline pair<InputIterator1, InputIterator2> 00118 mismatch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 00119 Predicate pred) 00120 { 00121 typedef std::iterator_traits<InputIterator1> iterator1_traits; 00122 typedef std::iterator_traits<InputIterator2> iterator2_traits; 00123 typedef typename iterator1_traits::iterator_category iterator1_category; 00124 typedef typename iterator2_traits::iterator_category iterator2_category; 00125 00126 return mismatch_switch(begin1, end1, begin2, pred, iterator1_category(), 00127 iterator2_category()); 00128 } 00129 00130 // Sequential fallback 00131 template<typename InputIterator1, typename InputIterator2> 00132 inline bool 00133 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 00134 __gnu_parallel::sequential_tag) 00135 { return _GLIBCXX_STD_P::equal(begin1, end1, begin2); } 00136 00137 // Sequential fallback 00138 template<typename InputIterator1, typename InputIterator2, 00139 typename Predicate> 00140 inline bool 00141 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 00142 Predicate pred, __gnu_parallel::sequential_tag) 00143 { return _GLIBCXX_STD_P::equal(begin1, end1, begin2, pred); } 00144 00145 // Public interface 00146 template<typename InputIterator1, typename InputIterator2> 00147 inline bool 00148 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) 00149 { return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2).first == end1; } 00150 00151 // Public interface 00152 template<typename InputIterator1, typename InputIterator2, 00153 typename Predicate> 00154 inline bool 00155 equal(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 00156 Predicate pred) 00157 { 00158 return _GLIBCXX_STD_P::mismatch(begin1, end1, begin2, pred).first 00159 == end1; 00160 } 00161 00162 // Sequential fallback 00163 template<typename InputIterator1, typename InputIterator2> 00164 inline bool 00165 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 00166 InputIterator2 begin2, InputIterator2 end2, 00167 __gnu_parallel::sequential_tag) 00168 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 00169 begin2, end2); } 00170 00171 // Sequential fallback 00172 template<typename InputIterator1, typename InputIterator2, 00173 typename Predicate> 00174 inline bool 00175 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 00176 InputIterator2 begin2, InputIterator2 end2, 00177 Predicate pred, __gnu_parallel::sequential_tag) 00178 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 00179 begin2, end2, pred); } 00180 00181 // Sequential fallback for input iterator case 00182 template<typename InputIterator1, typename InputIterator2, 00183 typename Predicate, typename IteratorTag1, typename IteratorTag2> 00184 inline bool 00185 lexicographical_compare_switch(InputIterator1 begin1, InputIterator1 end1, 00186 InputIterator2 begin2, InputIterator2 end2, 00187 Predicate pred, IteratorTag1, IteratorTag2) 00188 { return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 00189 begin2, end2, pred); } 00190 00191 // Parallel lexicographical_compare for random access iterators 00192 // Limitation: Both valuetypes must be the same 00193 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00194 typename Predicate> 00195 bool 00196 lexicographical_compare_switch(RandomAccessIterator1 begin1, 00197 RandomAccessIterator1 end1, 00198 RandomAccessIterator2 begin2, 00199 RandomAccessIterator2 end2, Predicate pred, 00200 random_access_iterator_tag, 00201 random_access_iterator_tag) 00202 { 00203 if (_GLIBCXX_PARALLEL_CONDITION(true)) 00204 { 00205 typedef iterator_traits<RandomAccessIterator1> traits1_type; 00206 typedef typename traits1_type::value_type value1_type; 00207 00208 typedef iterator_traits<RandomAccessIterator2> traits2_type; 00209 typedef typename traits2_type::value_type value2_type; 00210 00211 typedef __gnu_parallel::equal_from_less<Predicate, value1_type, 00212 value2_type> equal_type; 00213 00214 // Longer sequence in first place. 00215 if ((end1 - begin1) < (end2 - begin2)) 00216 { 00217 typedef pair<RandomAccessIterator1, RandomAccessIterator2> 00218 pair_type; 00219 pair_type mm = mismatch_switch(begin1, end1, begin2, 00220 equal_type(pred), 00221 random_access_iterator_tag(), 00222 random_access_iterator_tag()); 00223 00224 return (mm.first == end1) || bool(pred(*mm.first, *mm.second)); 00225 } 00226 else 00227 { 00228 typedef pair<RandomAccessIterator2, RandomAccessIterator1> 00229 pair_type; 00230 pair_type mm = mismatch_switch(begin2, end2, begin1, 00231 equal_type(pred), 00232 random_access_iterator_tag(), 00233 random_access_iterator_tag()); 00234 00235 return (mm.first != end2) && bool(pred(*mm.second, *mm.first)); 00236 } 00237 } 00238 else 00239 return _GLIBCXX_STD_P::lexicographical_compare(begin1, end1, 00240 begin2, end2, pred); 00241 } 00242 00243 // Public interface 00244 template<typename InputIterator1, typename InputIterator2> 00245 inline bool 00246 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 00247 InputIterator2 begin2, InputIterator2 end2) 00248 { 00249 typedef iterator_traits<InputIterator1> traits1_type; 00250 typedef typename traits1_type::value_type value1_type; 00251 typedef typename traits1_type::iterator_category iterator1_category; 00252 00253 typedef iterator_traits<InputIterator2> traits2_type; 00254 typedef typename traits2_type::value_type value2_type; 00255 typedef typename traits2_type::iterator_category iterator2_category; 00256 typedef __gnu_parallel::less<value1_type, value2_type> less_type; 00257 00258 return lexicographical_compare_switch(begin1, end1, begin2, end2, 00259 less_type(), iterator1_category(), 00260 iterator2_category()); 00261 } 00262 00263 // Public interface 00264 template<typename InputIterator1, typename InputIterator2, 00265 typename Predicate> 00266 inline bool 00267 lexicographical_compare(InputIterator1 begin1, InputIterator1 end1, 00268 InputIterator2 begin2, InputIterator2 end2, 00269 Predicate pred) 00270 { 00271 typedef iterator_traits<InputIterator1> traits1_type; 00272 typedef typename traits1_type::iterator_category iterator1_category; 00273 00274 typedef iterator_traits<InputIterator2> traits2_type; 00275 typedef typename traits2_type::iterator_category iterator2_category; 00276 00277 return lexicographical_compare_switch(begin1, end1, begin2, end2, pred, 00278 iterator1_category(), 00279 iterator2_category()); 00280 } 00281 } // end namespace 00282 } // end namespace 00283 00284 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */