mingw/lib/gcc/mingw32/4.3.3/include/c++/parallel/find.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/find.h
  32  *  @brief Parallel implementation base for std::find(), std::equal()
  33  *  and related functions.
  34  *  This file is a GNU parallel extension to the Standard C++ Library.
  35  */
  36
  37 // Written by Felix Putze and Johannes Singler.
  38
  39 #ifndef _GLIBCXX_PARALLEL_FIND_H
  40 #define _GLIBCXX_PARALLEL_FIND_H 1
  41
  42 #include <bits/stl_algobase.h>
  43
  44 #include <parallel/features.h>
  45 #include <parallel/parallel.h>
  46 #include <parallel/compatibility.h>
  47 #include <parallel/equally_split.h>
  48
  49 namespace __gnu_parallel
  50 {
  51 /**
  52  *  @brief Parallel std::find, switch for different algorithms.
  53  *  @param begin1 Begin iterator of first sequence.
  54  *  @param end1 End iterator of first sequence.
  55  *  @param begin2 Begin iterator of second sequence. Must have same
  56  *  length as first sequence.
  57  *  @param pred Find predicate.
  58  *  @param selector Functionality (e. g. std::find_if (), std::equal(),...)
  59  *  @return Place of finding in both sequences.
  60  */
  61 template<typename RandomAccessIterator1,
  62          typename RandomAccessIterator2,
  63          typename Pred,
  64          typename Selector>
  65   inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
  66   find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
  67                 RandomAccessIterator2 begin2, Pred pred, Selector selector)
  68   {
  69     switch (_Settings::get().find_algorithm)
  70       {
  71       case GROWING_BLOCKS:
  72         return find_template(begin1, end1, begin2, pred, selector,
  73                              growing_blocks_tag());
  74       case CONSTANT_SIZE_BLOCKS:
  75         return find_template(begin1, end1, begin2, pred, selector,
  76                              constant_size_blocks_tag());
  77       case EQUAL_SPLIT:
  78         return find_template(begin1, end1, begin2, pred, selector,
  79                              equal_split_tag());
  80       default:
  81         _GLIBCXX_PARALLEL_ASSERT(false);
  82         return std::make_pair(begin1, begin2);
  83       }
  84   }
  85
  86 #if _GLIBCXX_FIND_EQUAL_SPLIT
  87
  88 /**
  89  *  @brief Parallel std::find, equal splitting variant.
  90  *  @param begin1 Begin iterator of first sequence.
  91  *  @param end1 End iterator of first sequence.
  92  *  @param begin2 Begin iterator of second sequence. Second sequence
  93  *  must have same length as first sequence.
  94  *  @param pred Find predicate.
  95  *  @param selector Functionality (e. g. std::find_if (), std::equal(),...)
  96  *  @return Place of finding in both sequences.
  97  */
  98 template<typename RandomAccessIterator1,
  99          typename RandomAccessIterator2,
 100          typename Pred,
 101          typename Selector>
 102   std::pair<RandomAccessIterator1, RandomAccessIterator2>
 103   find_template(RandomAccessIterator1 begin1,
 104                 RandomAccessIterator1 end1,
 105                 RandomAccessIterator2 begin2,
 106                 Pred pred,
 107                 Selector selector,
 108                 equal_split_tag)
 109   {
 110     _GLIBCXX_CALL(end1 - begin1)
 111
 112     typedef std::iterator_traits<RandomAccessIterator1> traits_type;
 113     typedef typename traits_type::difference_type difference_type;
 114     typedef typename traits_type::value_type value_type;
 115
 116     difference_type length = end1 - begin1;
 117     difference_type result = length;
 118     difference_type* borders;
 119
 120     omp_lock_t result_lock;
 121     omp_init_lock(&result_lock);
 122
 123     thread_index_t num_threads = get_max_threads();
 124 #   pragma omp parallel num_threads(num_threads)
 125       {
 126 #       pragma omp single
 127           {
 128             num_threads = omp_get_num_threads();
 129             borders = new difference_type[num_threads + 1];
 130             equally_split(length, num_threads, borders);
 131           } //single
 132
 133         thread_index_t iam = omp_get_thread_num();
 134         difference_type start = borders[iam], stop = borders[iam + 1];
 135
 136         RandomAccessIterator1 i1 = begin1 + start;
 137         RandomAccessIterator2 i2 = begin2 + start;
 138         for (difference_type pos = start; pos < stop; ++pos)
 139           {
 140             #pragma omp flush(result)
 141             // Result has been set to something lower.
 142             if (result < pos)
 143               break;
 144
 145             if (selector(i1, i2, pred))
 146               {
 147                 omp_set_lock(&result_lock);
 148                 if (pos < result)
 149                   result = pos;
 150                 omp_unset_lock(&result_lock);
 151                 break;
 152               }
 153             ++i1;
 154             ++i2;
 155           }
 156       } //parallel
 157
 158     omp_destroy_lock(&result_lock);
 159     delete[] borders;
 160
 161     return
 162       std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result,
 163                                                               begin2 + result);
 164   }
 165
 166 #endif
 167
 168 #if _GLIBCXX_FIND_GROWING_BLOCKS
 169
 170 /**
 171  *  @brief Parallel std::find, growing block size variant.
 172  *  @param begin1 Begin iterator of first sequence.
 173  *  @param end1 End iterator of first sequence.
 174  *  @param begin2 Begin iterator of second sequence. Second sequence
 175  *  must have same length as first sequence.
 176  *  @param pred Find predicate.
 177  *  @param selector Functionality (e. g. std::find_if (), std::equal(),...)
 178  *  @return Place of finding in both sequences.
 179  *  @see __gnu_parallel::_Settings::find_sequential_search_size
 180  *  @see __gnu_parallel::_Settings::find_initial_block_size
 181  *  @see __gnu_parallel::_Settings::find_maximum_block_size
 182  *  @see __gnu_parallel::_Settings::find_increasing_factor
 183  *
 184  *  There are two main differences between the growing blocks and
 185  *  the constant-size blocks variants.
 186  *  1. For GB, the block size grows; for CSB, the block size is fixed.
 187
 188  *  2. For GB, the blocks are allocated dynamically;
 189  *     for CSB, the blocks are allocated in a predetermined manner,
 190  *     namely spacial round-robin.
 191  */
 192 template<typename RandomAccessIterator1,
 193          typename RandomAccessIterator2,
 194          typename Pred,
 195          typename Selector>
 196   std::pair<RandomAccessIterator1, RandomAccessIterator2>
 197   find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
 198                 RandomAccessIterator2 begin2, Pred pred, Selector selector,
 199                 growing_blocks_tag)
 200   {
 201     _GLIBCXX_CALL(end1 - begin1)
 202
 203     typedef std::iterator_traits<RandomAccessIterator1> traits_type;
 204     typedef typename traits_type::difference_type difference_type;
 205     typedef typename traits_type::value_type value_type;
 206
 207     const _Settings& __s = _Settings::get();
 208
 209     difference_type length = end1 - begin1;
 210
 211     difference_type sequential_search_size =
 212       std::min<difference_type>(length, __s.find_sequential_search_size);
 213
 214     // Try it sequentially first.
 215     std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
 216       selector.sequential_algorithm(
 217           begin1, begin1 + sequential_search_size, begin2, pred);
 218
 219     if (find_seq_result.first != (begin1 + sequential_search_size))
 220       return find_seq_result;
 221
 222     // Index of beginning of next free block (after sequential find).
 223     difference_type next_block_start = sequential_search_size;
 224     difference_type result = length;
 225
 226     omp_lock_t result_lock;
 227     omp_init_lock(&result_lock);
 228
 229     thread_index_t num_threads = get_max_threads();
 230 #   pragma omp parallel shared(result) num_threads(num_threads)
 231       {
 232 #       pragma omp single
 233           num_threads = omp_get_num_threads();
 234
 235         // Not within first k elements -> start parallel.
 236         thread_index_t iam = omp_get_thread_num();
 237
 238         difference_type block_size = __s.find_initial_block_size;
 239         difference_type start =
 240             fetch_and_add<difference_type>(&next_block_start, block_size);
 241
 242         // Get new block, update pointer to next block.
 243         difference_type stop =
 244             std::min<difference_type>(length, start + block_size);
 245
 246         std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result;
 247
 248         while (start < length)
 249           {
 250 #           pragma omp flush(result)
 251             // Get new value of result.
 252             if (result < start)
 253               {
 254                 // No chance to find first element.
 255                 break;
 256               }
 257
 258             local_result = selector.sequential_algorithm(
 259                 begin1 + start, begin1 + stop, begin2 + start, pred);
 260             if (local_result.first != (begin1 + stop))
 261               {
 262                 omp_set_lock(&result_lock);
 263                 if ((local_result.first - begin1) < result)
 264                   {
 265                     result = local_result.first - begin1;
 266
 267                     // Result cannot be in future blocks, stop algorithm.
 268                     fetch_and_add<difference_type>(&next_block_start, length);
 269                   }
 270                   omp_unset_lock(&result_lock);
 271               }
 272
 273             block_size =
 274               std::min<difference_type>(block_size * __s.find_increasing_factor,
 275                                         __s.find_maximum_block_size);
 276
 277             // Get new block, update pointer to next block.
 278             start =
 279               fetch_and_add<difference_type>(&next_block_start, block_size);
 280             stop = ((length < (start + block_size))
 281                     ? length : (start + block_size));
 282           }
 283       } //parallel
 284
 285     omp_destroy_lock(&result_lock);
 286
 287     // Return iterator on found element.
 288     return
 289       std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result,
 290                                                               begin2 + result);
 291   }
 292
 293 #endif
 294
 295 #if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS
 296
 297 /**
 298  *   @brief Parallel std::find, constant block size variant.
 299  *  @param begin1 Begin iterator of first sequence.
 300  *  @param end1 End iterator of first sequence.
 301  *  @param begin2 Begin iterator of second sequence. Second sequence
 302  *  must have same length as first sequence.
 303  *  @param pred Find predicate.
 304  *  @param selector Functionality (e. g. std::find_if (), std::equal(),...)
 305  *  @return Place of finding in both sequences.
 306  *  @see __gnu_parallel::_Settings::find_sequential_search_size
 307  *  @see __gnu_parallel::_Settings::find_block_size
 308  *  There are two main differences between the growing blocks and the
 309  *  constant-size blocks variants.
 310  *  1. For GB, the block size grows; for CSB, the block size is fixed.
 311  *  2. For GB, the blocks are allocated dynamically; for CSB, the
 312  *  blocks are allocated in a predetermined manner, namely spacial
 313  *  round-robin.
 314  */
 315 template<typename RandomAccessIterator1,
 316          typename RandomAccessIterator2,
 317          typename Pred,
 318          typename Selector>
 319   std::pair<RandomAccessIterator1, RandomAccessIterator2>
 320   find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
 321                 RandomAccessIterator2 begin2, Pred pred, Selector selector,
 322                 constant_size_blocks_tag)
 323   {
 324     _GLIBCXX_CALL(end1 - begin1)
 325     typedef std::iterator_traits<RandomAccessIterator1> traits_type;
 326     typedef typename traits_type::difference_type difference_type;
 327     typedef typename traits_type::value_type value_type;
 328
 329     const _Settings& __s = _Settings::get();
 330
 331     difference_type length = end1 - begin1;
 332
 333     difference_type sequential_search_size = std::min<difference_type>(
 334         length, __s.find_sequential_search_size);
 335
 336     // Try it sequentially first.
 337     std::pair<RandomAccessIterator1, RandomAccessIterator2> find_seq_result =
 338       selector.sequential_algorithm(begin1, begin1 + sequential_search_size,
 339                                     begin2, pred);
 340
 341     if (find_seq_result.first != (begin1 + sequential_search_size))
 342       return find_seq_result;
 343
 344     difference_type result = length;
 345     omp_lock_t result_lock;
 346     omp_init_lock(&result_lock);
 347
 348     // Not within first sequential_search_size elements -> start parallel.
 349
 350     thread_index_t num_threads = get_max_threads();
 351 #   pragma omp parallel shared(result) num_threads(num_threads)
 352       {
 353 #       pragma omp single
 354           num_threads = omp_get_num_threads();
 355
 356         thread_index_t iam = omp_get_thread_num();
 357         difference_type block_size = __s.find_initial_block_size;
 358
 359         // First element of thread's current iteration.
 360         difference_type iteration_start = sequential_search_size;
 361
 362         // Where to work (initialization).
 363         difference_type start = iteration_start + iam * block_size;
 364         difference_type stop =
 365             std::min<difference_type>(length, start + block_size);
 366
 367         std::pair<RandomAccessIterator1, RandomAccessIterator2> local_result;
 368
 369         while (start < length)
 370           {
 371             // Get new value of result.
 372 #           pragma omp flush(result)
 373             // No chance to find first element.
 374             if (result < start)
 375               break;
 376             local_result = selector.sequential_algorithm(
 377                 begin1 + start, begin1 + stop,
 378                 begin2 + start, pred);
 379             if (local_result.first != (begin1 + stop))
 380               {
 381                 omp_set_lock(&result_lock);
 382                 if ((local_result.first - begin1) < result)
 383                   result = local_result.first - begin1;
 384                 omp_unset_lock(&result_lock);
 385                 // Will not find better value in its interval.
 386                 break;
 387               }
 388
 389             iteration_start += num_threads * block_size;
 390
 391             // Where to work.
 392             start = iteration_start + iam * block_size;
 393             stop = std::min<difference_type>(length, start + block_size);
 394           }
 395       } //parallel
 396
 397     omp_destroy_lock(&result_lock);
 398
 399     // Return iterator on found element.
 400     return
 401       std::pair<RandomAccessIterator1, RandomAccessIterator2>(begin1 + result,
 402                                                               begin2 + result);
 403   }
 404 #endif
 405 } // end namespace
 406
 407 #endif