contrib/gcc-4.4/libstdc++-v3/include/parallel/find.h

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