find.h

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

Generated on Wed Dec 31 12:48:54 2008 for libstdc++ by  doxygen 1.5.6