libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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/find.h 00026 * @brief Parallel implementation base for std::find(), std::equal() 00027 * and related functions. 00028 * This file is a GNU parallel extension to the Standard C++ Library. 00029 */ 00030 00031 // Written by Felix Putze and Johannes Singler. 00032 00033 #ifndef _GLIBCXX_PARALLEL_FIND_H 00034 #define _GLIBCXX_PARALLEL_FIND_H 1 00035 00036 #include <bits/stl_algobase.h> 00037 00038 #include <parallel/features.h> 00039 #include <parallel/parallel.h> 00040 #include <parallel/compatibility.h> 00041 #include <parallel/equally_split.h> 00042 00043 namespace __gnu_parallel 00044 { 00045 /** 00046 * @brief Parallel std::find, switch for different algorithms. 00047 * @param __begin1 Begin iterator of first sequence. 00048 * @param __end1 End iterator of first sequence. 00049 * @param __begin2 Begin iterator of second sequence. Must have same 00050 * length as first sequence. 00051 * @param __pred Find predicate. 00052 * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 00053 * @return Place of finding in both sequences. 00054 */ 00055 template<typename _RAIter1, 00056 typename _RAIter2, 00057 typename _Pred, 00058 typename _Selector> 00059 inline std::pair<_RAIter1, _RAIter2> 00060 __find_template(_RAIter1 __begin1, _RAIter1 __end1, 00061 _RAIter2 __begin2, _Pred __pred, _Selector __selector) 00062 { 00063 switch (_Settings::get().find_algorithm) 00064 { 00065 case GROWING_BLOCKS: 00066 return __find_template(__begin1, __end1, __begin2, __pred, 00067 __selector, growing_blocks_tag()); 00068 case CONSTANT_SIZE_BLOCKS: 00069 return __find_template(__begin1, __end1, __begin2, __pred, 00070 __selector, constant_size_blocks_tag()); 00071 case EQUAL_SPLIT: 00072 return __find_template(__begin1, __end1, __begin2, __pred, 00073 __selector, equal_split_tag()); 00074 default: 00075 _GLIBCXX_PARALLEL_ASSERT(false); 00076 return std::make_pair(__begin1, __begin2); 00077 } 00078 } 00079 00080 #if _GLIBCXX_FIND_EQUAL_SPLIT 00081 00082 /** 00083 * @brief Parallel std::find, equal splitting variant. 00084 * @param __begin1 Begin iterator of first sequence. 00085 * @param __end1 End iterator of first sequence. 00086 * @param __begin2 Begin iterator of second sequence. Second __sequence 00087 * must have same length as first sequence. 00088 * @param __pred Find predicate. 00089 * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 00090 * @return Place of finding in both sequences. 00091 */ 00092 template<typename _RAIter1, 00093 typename _RAIter2, 00094 typename _Pred, 00095 typename _Selector> 00096 std::pair<_RAIter1, _RAIter2> 00097 __find_template(_RAIter1 __begin1, _RAIter1 __end1, 00098 _RAIter2 __begin2, _Pred __pred, 00099 _Selector __selector, equal_split_tag) 00100 { 00101 _GLIBCXX_CALL(__end1 - __begin1) 00102 00103 typedef std::iterator_traits<_RAIter1> _TraitsType; 00104 typedef typename _TraitsType::difference_type _DifferenceType; 00105 typedef typename _TraitsType::value_type _ValueType; 00106 00107 _DifferenceType __length = __end1 - __begin1; 00108 _DifferenceType __result = __length; 00109 _DifferenceType* __borders; 00110 00111 omp_lock_t __result_lock; 00112 omp_init_lock(&__result_lock); 00113 00114 _ThreadIndex __num_threads = __get_max_threads(); 00115 # pragma omp parallel num_threads(__num_threads) 00116 { 00117 # pragma omp single 00118 { 00119 __num_threads = omp_get_num_threads(); 00120 __borders = new _DifferenceType[__num_threads + 1]; 00121 __equally_split(__length, __num_threads, __borders); 00122 } //single 00123 00124 _ThreadIndex __iam = omp_get_thread_num(); 00125 _DifferenceType __start = __borders[__iam], 00126 __stop = __borders[__iam + 1]; 00127 00128 _RAIter1 __i1 = __begin1 + __start; 00129 _RAIter2 __i2 = __begin2 + __start; 00130 for (_DifferenceType __pos = __start; __pos < __stop; ++__pos) 00131 { 00132 # pragma omp flush(__result) 00133 // Result has been set to something lower. 00134 if (__result < __pos) 00135 break; 00136 00137 if (__selector(__i1, __i2, __pred)) 00138 { 00139 omp_set_lock(&__result_lock); 00140 if (__pos < __result) 00141 __result = __pos; 00142 omp_unset_lock(&__result_lock); 00143 break; 00144 } 00145 ++__i1; 00146 ++__i2; 00147 } 00148 } //parallel 00149 00150 omp_destroy_lock(&__result_lock); 00151 delete[] __borders; 00152 00153 return std::pair<_RAIter1, _RAIter2>(__begin1 + __result, 00154 __begin2 + __result); 00155 } 00156 00157 #endif 00158 00159 #if _GLIBCXX_FIND_GROWING_BLOCKS 00160 00161 /** 00162 * @brief Parallel std::find, growing block size variant. 00163 * @param __begin1 Begin iterator of first sequence. 00164 * @param __end1 End iterator of first sequence. 00165 * @param __begin2 Begin iterator of second sequence. Second __sequence 00166 * must have same length as first sequence. 00167 * @param __pred Find predicate. 00168 * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 00169 * @return Place of finding in both sequences. 00170 * @see __gnu_parallel::_Settings::find_sequential_search_size 00171 * @see __gnu_parallel::_Settings::find_scale_factor 00172 * 00173 * There are two main differences between the growing blocks and 00174 * the constant-size blocks variants. 00175 * 1. For GB, the block size grows; for CSB, the block size is fixed. 00176 * 2. For GB, the blocks are allocated dynamically; 00177 * for CSB, the blocks are allocated in a predetermined manner, 00178 * namely spacial round-robin. 00179 */ 00180 template<typename _RAIter1, 00181 typename _RAIter2, 00182 typename _Pred, 00183 typename _Selector> 00184 std::pair<_RAIter1, _RAIter2> 00185 __find_template(_RAIter1 __begin1, _RAIter1 __end1, 00186 _RAIter2 __begin2, _Pred __pred, _Selector __selector, 00187 growing_blocks_tag) 00188 { 00189 _GLIBCXX_CALL(__end1 - __begin1) 00190 00191 typedef std::iterator_traits<_RAIter1> _TraitsType; 00192 typedef typename _TraitsType::difference_type _DifferenceType; 00193 typedef typename _TraitsType::value_type _ValueType; 00194 00195 const _Settings& __s = _Settings::get(); 00196 00197 _DifferenceType __length = __end1 - __begin1; 00198 00199 _DifferenceType 00200 __sequential_search_size = std::min<_DifferenceType> 00201 (__length, __s.find_sequential_search_size); 00202 00203 // Try it sequentially first. 00204 std::pair<_RAIter1, _RAIter2> 00205 __find_seq_result = __selector._M_sequential_algorithm 00206 (__begin1, __begin1 + __sequential_search_size, 00207 __begin2, __pred); 00208 00209 if (__find_seq_result.first != (__begin1 + __sequential_search_size)) 00210 return __find_seq_result; 00211 00212 // Index of beginning of next free block (after sequential find). 00213 _DifferenceType __next_block_start = __sequential_search_size; 00214 _DifferenceType __result = __length; 00215 00216 omp_lock_t __result_lock; 00217 omp_init_lock(&__result_lock); 00218 00219 const float __scale_factor = __s.find_scale_factor; 00220 00221 _ThreadIndex __num_threads = __get_max_threads(); 00222 # pragma omp parallel shared(__result) num_threads(__num_threads) 00223 { 00224 # pragma omp single 00225 __num_threads = omp_get_num_threads(); 00226 00227 // Not within first __k elements -> start parallel. 00228 _ThreadIndex __iam = omp_get_thread_num(); 00229 00230 _DifferenceType __block_size = 00231 std::max<_DifferenceType>(1, __scale_factor * __next_block_start); 00232 _DifferenceType __start = __fetch_and_add<_DifferenceType> 00233 (&__next_block_start, __block_size); 00234 00235 // Get new block, update pointer to next block. 00236 _DifferenceType __stop = 00237 std::min<_DifferenceType>(__length, __start + __block_size); 00238 00239 std::pair<_RAIter1, _RAIter2> __local_result; 00240 00241 while (__start < __length) 00242 { 00243 # pragma omp flush(__result) 00244 // Get new value of result. 00245 if (__result < __start) 00246 { 00247 // No chance to find first element. 00248 break; 00249 } 00250 00251 __local_result = __selector._M_sequential_algorithm 00252 (__begin1 + __start, __begin1 + __stop, 00253 __begin2 + __start, __pred); 00254 00255 if (__local_result.first != (__begin1 + __stop)) 00256 { 00257 omp_set_lock(&__result_lock); 00258 if ((__local_result.first - __begin1) < __result) 00259 { 00260 __result = __local_result.first - __begin1; 00261 00262 // Result cannot be in future blocks, stop algorithm. 00263 __fetch_and_add<_DifferenceType>(&__next_block_start, 00264 __length); 00265 } 00266 omp_unset_lock(&__result_lock); 00267 } 00268 00269 _DifferenceType __block_size = 00270 std::max<_DifferenceType>(1, __scale_factor * __next_block_start); 00271 00272 // Get new block, update pointer to next block. 00273 __start = __fetch_and_add<_DifferenceType>(&__next_block_start, 00274 __block_size); 00275 __stop = 00276 std::min<_DifferenceType>(__length, __start + __block_size); 00277 } 00278 } //parallel 00279 00280 omp_destroy_lock(&__result_lock); 00281 00282 // Return iterator on found element. 00283 return 00284 std::pair<_RAIter1, _RAIter2>(__begin1 + __result, 00285 __begin2 + __result); 00286 } 00287 00288 #endif 00289 00290 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS 00291 00292 /** 00293 * @brief Parallel std::find, constant block size variant. 00294 * @param __begin1 Begin iterator of first sequence. 00295 * @param __end1 End iterator of first sequence. 00296 * @param __begin2 Begin iterator of second sequence. Second __sequence 00297 * must have same length as first sequence. 00298 * @param __pred Find predicate. 00299 * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 00300 * @return Place of finding in both sequences. 00301 * @see __gnu_parallel::_Settings::find_sequential_search_size 00302 * @see __gnu_parallel::_Settings::find_block_size 00303 * There are two main differences between the growing blocks and the 00304 * constant-size blocks variants. 00305 * 1. For GB, the block size grows; for CSB, the block size is fixed. 00306 * 2. For GB, the blocks are allocated dynamically; for CSB, the 00307 * blocks are allocated in a predetermined manner, namely spacial 00308 * round-robin. 00309 */ 00310 template<typename _RAIter1, 00311 typename _RAIter2, 00312 typename _Pred, 00313 typename _Selector> 00314 std::pair<_RAIter1, _RAIter2> 00315 __find_template(_RAIter1 __begin1, _RAIter1 __end1, 00316 _RAIter2 __begin2, _Pred __pred, _Selector __selector, 00317 constant_size_blocks_tag) 00318 { 00319 _GLIBCXX_CALL(__end1 - __begin1) 00320 typedef std::iterator_traits<_RAIter1> _TraitsType; 00321 typedef typename _TraitsType::difference_type _DifferenceType; 00322 typedef typename _TraitsType::value_type _ValueType; 00323 00324 const _Settings& __s = _Settings::get(); 00325 00326 _DifferenceType __length = __end1 - __begin1; 00327 00328 _DifferenceType __sequential_search_size = std::min<_DifferenceType> 00329 (__length, __s.find_sequential_search_size); 00330 00331 // Try it sequentially first. 00332 std::pair<_RAIter1, _RAIter2> 00333 __find_seq_result = __selector._M_sequential_algorithm 00334 (__begin1, __begin1 + __sequential_search_size, __begin2, __pred); 00335 00336 if (__find_seq_result.first != (__begin1 + __sequential_search_size)) 00337 return __find_seq_result; 00338 00339 _DifferenceType __result = __length; 00340 omp_lock_t __result_lock; 00341 omp_init_lock(&__result_lock); 00342 00343 // Not within first __sequential_search_size elements -> start parallel. 00344 00345 _ThreadIndex __num_threads = __get_max_threads(); 00346 # pragma omp parallel shared(__result) num_threads(__num_threads) 00347 { 00348 # pragma omp single 00349 __num_threads = omp_get_num_threads(); 00350 00351 _ThreadIndex __iam = omp_get_thread_num(); 00352 _DifferenceType __block_size = __s.find_initial_block_size; 00353 00354 // First element of thread's current iteration. 00355 _DifferenceType __iteration_start = __sequential_search_size; 00356 00357 // Where to work (initialization). 00358 _DifferenceType __start = __iteration_start + __iam * __block_size; 00359 _DifferenceType __stop = std::min<_DifferenceType>(__length, 00360 __start 00361 + __block_size); 00362 00363 std::pair<_RAIter1, _RAIter2> __local_result; 00364 00365 while (__start < __length) 00366 { 00367 // Get new value of result. 00368 # pragma omp flush(__result) 00369 // No chance to find first element. 00370 if (__result < __start) 00371 break; 00372 00373 __local_result = __selector._M_sequential_algorithm 00374 (__begin1 + __start, __begin1 + __stop, 00375 __begin2 + __start, __pred); 00376 00377 if (__local_result.first != (__begin1 + __stop)) 00378 { 00379 omp_set_lock(&__result_lock); 00380 if ((__local_result.first - __begin1) < __result) 00381 __result = __local_result.first - __begin1; 00382 omp_unset_lock(&__result_lock); 00383 // Will not find better value in its interval. 00384 break; 00385 } 00386 00387 __iteration_start += __num_threads * __block_size; 00388 00389 // Where to work. 00390 __start = __iteration_start + __iam * __block_size; 00391 __stop = std::min<_DifferenceType>(__length, 00392 __start + __block_size); 00393 } 00394 } //parallel 00395 00396 omp_destroy_lock(&__result_lock); 00397 00398 // Return iterator on found element. 00399 return std::pair<_RAIter1, _RAIter2>(__begin1 + __result, 00400 __begin2 + __result); 00401 } 00402 #endif 00403 } // end namespace 00404 00405 #endif /* _GLIBCXX_PARALLEL_FIND_H */