find.h

Go to the documentation of this file.
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 */

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1