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/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 RandomAccessIterator1, 00056 typename RandomAccessIterator2, 00057 typename Pred, 00058 typename Selector> 00059 inline std::pair<RandomAccessIterator1, RandomAccessIterator2> 00060 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, 00061 RandomAccessIterator2 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, selector, 00067 growing_blocks_tag()); 00068 case CONSTANT_SIZE_BLOCKS: 00069 return find_template(begin1, end1, begin2, pred, selector, 00070 constant_size_blocks_tag()); 00071 case EQUAL_SPLIT: 00072 return find_template(begin1, end1, begin2, pred, selector, 00073 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 RandomAccessIterator1, 00093 typename RandomAccessIterator2, 00094 typename Pred, 00095 typename Selector> 00096 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00097 find_template(RandomAccessIterator1 begin1, 00098 RandomAccessIterator1 end1, 00099 RandomAccessIterator2 begin2, 00100 Pred pred, 00101 Selector selector, 00102 equal_split_tag) 00103 { 00104 _GLIBCXX_CALL(end1 - begin1) 00105 00106 typedef std::iterator_traits<RandomAccessIterator1> traits_type; 00107 typedef typename traits_type::difference_type difference_type; 00108 typedef typename traits_type::value_type value_type; 00109 00110 difference_type length = end1 - begin1; 00111 difference_type result = length; 00112 difference_type* borders; 00113 00114 omp_lock_t result_lock; 00115 omp_init_lock(&result_lock); 00116 00117 thread_index_t num_threads = get_max_threads(); 00118 # pragma omp parallel num_threads(num_threads) 00119 { 00120 # pragma omp single 00121 { 00122 num_threads = omp_get_num_threads(); 00123 borders = new difference_type[num_threads + 1]; 00124 equally_split(length, num_threads, borders); 00125 } //single 00126 00127 thread_index_t iam = omp_get_thread_num(); 00128 difference_type start = borders[iam], stop = borders[iam + 1]; 00129 00130 RandomAccessIterator1 i1 = begin1 + start; 00131 RandomAccessIterator2 i2 = begin2 + start; 00132 for (difference_type pos = start; pos < stop; ++pos) 00133 { 00134 #pragma omp flush(result) 00135 // Result has been set to something lower. 00136 if (result < pos) 00137 break; 00138 00139 if (selector(i1, i2, pred)) 00140 { 00141 omp_set_lock(&result_lock); 00142 if (pos < result) 00143 result = pos; 00144 omp_unset_lock(&result_lock); 00145 break; 00146 } 00147 ++i1; 00148 ++i2; 00149 } 00150 } //parallel 00151 00152 omp_destroy_lock(&result_lock); 00153 delete[] borders; 00154 00155 return 00156 std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result, 00157 begin2 + result); 00158 } 00159 00160 #endif 00161 00162 #if _GLIBCXX_FIND_GROWING_BLOCKS 00163 00164 /** 00165 * @brief Parallel std::find, growing block size variant. 00166 * @param begin1 Begin iterator of first sequence. 00167 * @param end1 End iterator of first sequence. 00168 * @param begin2 Begin iterator of second sequence. Second sequence 00169 * must have same length as first sequence. 00170 * @param pred Find predicate. 00171 * @param selector Functionality (e. g. std::find_if (), std::equal(),...) 00172 * @return Place of finding in both sequences. 00173 * @see __gnu_parallel::_Settings::find_sequential_search_size 00174 * @see __gnu_parallel::_Settings::find_initial_block_size 00175 * @see __gnu_parallel::_Settings::find_maximum_block_size 00176 * @see __gnu_parallel::_Settings::find_increasing_factor 00177 * 00178 * There are two main differences between the growing blocks and 00179 * the constant-size blocks variants. 00180 * 1. For GB, the block size grows; for CSB, the block size is fixed. 00181 00182 * 2. For GB, the blocks are allocated dynamically; 00183 * for CSB, the blocks are allocated in a predetermined manner, 00184 * namely spacial round-robin. 00185 */ 00186 template<typename RandomAccessIterator1, 00187 typename RandomAccessIterator2, 00188 typename Pred, 00189 typename Selector> 00190 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00191 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, 00192 RandomAccessIterator2 begin2, Pred pred, Selector selector, 00193 growing_blocks_tag) 00194 { 00195 _GLIBCXX_CALL(end1 - begin1) 00196 00197 typedef std::iterator_traits<RandomAccessIterator1> traits_type; 00198 typedef typename traits_type::difference_type difference_type; 00199 typedef typename traits_type::value_type value_type; 00200 00201 const _Settings& __s = _Settings::get(); 00202 00203 difference_type length = end1 - begin1; 00204 00205 difference_type sequential_search_size = 00206 std::min<difference_type>(length, __s.find_sequential_search_size); 00207 00208 // Try it sequentially first. 00209 std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result = 00210 selector.sequential_algorithm( 00211 begin1, begin1 + sequential_search_size, begin2, pred); 00212 00213 if (find_seq_result.first != (begin1 + sequential_search_size)) 00214 return find_seq_result; 00215 00216 // Index of beginning of next free block (after sequential find). 00217 difference_type next_block_start = sequential_search_size; 00218 difference_type result = length; 00219 00220 omp_lock_t result_lock; 00221 omp_init_lock(&result_lock); 00222 00223 thread_index_t num_threads = get_max_threads(); 00224 # pragma omp parallel shared(result) num_threads(num_threads) 00225 { 00226 # pragma omp single 00227 num_threads = omp_get_num_threads(); 00228 00229 // Not within first k elements -> start parallel. 00230 thread_index_t iam = omp_get_thread_num(); 00231 00232 difference_type block_size = __s.find_initial_block_size; 00233 difference_type start = 00234 fetch_and_add<difference_type>(&next_block_start, block_size); 00235 00236 // Get new block, update pointer to next block. 00237 difference_type stop = 00238 std::min<difference_type>(length, start + block_size); 00239 00240 std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result; 00241 00242 while (start < length) 00243 { 00244 # pragma omp flush(result) 00245 // Get new value of result. 00246 if (result < start) 00247 { 00248 // No chance to find first element. 00249 break; 00250 } 00251 00252 local_result = selector.sequential_algorithm( 00253 begin1 + start, begin1 + stop, begin2 + start, pred); 00254 if (local_result.first != (begin1 + stop)) 00255 { 00256 omp_set_lock(&result_lock); 00257 if ((local_result.first - begin1) < result) 00258 { 00259 result = local_result.first - begin1; 00260 00261 // Result cannot be in future blocks, stop algorithm. 00262 fetch_and_add<difference_type>(&next_block_start, length); 00263 } 00264 omp_unset_lock(&result_lock); 00265 } 00266 00267 block_size = 00268 std::min<difference_type>(block_size * __s.find_increasing_factor, 00269 __s.find_maximum_block_size); 00270 00271 // Get new block, update pointer to next block. 00272 start = 00273 fetch_and_add<difference_type>(&next_block_start, block_size); 00274 stop = ((length < (start + block_size)) 00275 ? length : (start + block_size)); 00276 } 00277 } //parallel 00278 00279 omp_destroy_lock(&result_lock); 00280 00281 // Return iterator on found element. 00282 return 00283 std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result, 00284 begin2 + result); 00285 } 00286 00287 #endif 00288 00289 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS 00290 00291 /** 00292 * @brief Parallel std::find, constant block size variant. 00293 * @param begin1 Begin iterator of first sequence. 00294 * @param end1 End iterator of first sequence. 00295 * @param begin2 Begin iterator of second sequence. Second sequence 00296 * must have same length as first sequence. 00297 * @param pred Find predicate. 00298 * @param selector Functionality (e. g. std::find_if (), std::equal(),...) 00299 * @return Place of finding in both sequences. 00300 * @see __gnu_parallel::_Settings::find_sequential_search_size 00301 * @see __gnu_parallel::_Settings::find_block_size 00302 * There are two main differences between the growing blocks and the 00303 * constant-size blocks variants. 00304 * 1. For GB, the block size grows; for CSB, the block size is fixed. 00305 * 2. For GB, the blocks are allocated dynamically; for CSB, the 00306 * blocks are allocated in a predetermined manner, namely spacial 00307 * round-robin. 00308 */ 00309 template<typename RandomAccessIterator1, 00310 typename RandomAccessIterator2, 00311 typename Pred, 00312 typename Selector> 00313 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00314 find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, 00315 RandomAccessIterator2 begin2, Pred pred, Selector selector, 00316 constant_size_blocks_tag) 00317 { 00318 _GLIBCXX_CALL(end1 - begin1) 00319 typedef std::iterator_traits<RandomAccessIterator1> traits_type; 00320 typedef typename traits_type::difference_type difference_type; 00321 typedef typename traits_type::value_type value_type; 00322 00323 const _Settings& __s = _Settings::get(); 00324 00325 difference_type length = end1 - begin1; 00326 00327 difference_type sequential_search_size = std::min<difference_type>( 00328 length, __s.find_sequential_search_size); 00329 00330 // Try it sequentially first. 00331 std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result = 00332 selector.sequential_algorithm(begin1, begin1 + sequential_search_size, 00333 begin2, pred); 00334 00335 if (find_seq_result.first != (begin1 + sequential_search_size)) 00336 return find_seq_result; 00337 00338 difference_type result = length; 00339 omp_lock_t result_lock; 00340 omp_init_lock(&result_lock); 00341 00342 // Not within first sequential_search_size elements -> start parallel. 00343 00344 thread_index_t num_threads = get_max_threads(); 00345 # pragma omp parallel shared(result) num_threads(num_threads) 00346 { 00347 # pragma omp single 00348 num_threads = omp_get_num_threads(); 00349 00350 thread_index_t iam = omp_get_thread_num(); 00351 difference_type block_size = __s.find_initial_block_size; 00352 00353 // First element of thread's current iteration. 00354 difference_type iteration_start = sequential_search_size; 00355 00356 // Where to work (initialization). 00357 difference_type start = iteration_start + iam * block_size; 00358 difference_type stop = 00359 std::min<difference_type>(length, start + block_size); 00360 00361 std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result; 00362 00363 while (start < length) 00364 { 00365 // Get new value of result. 00366 # pragma omp flush(result) 00367 // No chance to find first element. 00368 if (result < start) 00369 break; 00370 local_result = selector.sequential_algorithm( 00371 begin1 + start, begin1 + stop, 00372 begin2 + start, pred); 00373 if (local_result.first != (begin1 + stop)) 00374 { 00375 omp_set_lock(&result_lock); 00376 if ((local_result.first - begin1) < result) 00377 result = local_result.first - begin1; 00378 omp_unset_lock(&result_lock); 00379 // Will not find better value in its interval. 00380 break; 00381 } 00382 00383 iteration_start += num_threads * block_size; 00384 00385 // Where to work. 00386 start = iteration_start + iam * block_size; 00387 stop = std::min<difference_type>(length, start + block_size); 00388 } 00389 } //parallel 00390 00391 omp_destroy_lock(&result_lock); 00392 00393 // Return iterator on found element. 00394 return 00395 std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result, 00396 begin2 + result); 00397 } 00398 #endif 00399 } // end namespace 00400 00401 #endif /* _GLIBCXX_PARALLEL_FIND_H */