contrib/gcc-5.0/libstdc++-v3/include/parallel/partition.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2015 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/partition.h
  26  *  @brief Parallel implementation of std::partition(),
  27  *  std::nth_element(), and std::partial_sort().
  28  *  This file is a GNU parallel extension to the Standard C++ Library.
  29  */
  30
  31 // Written by Johannes Singler and Felix Putze.
  32
  33 #ifndef _GLIBCXX_PARALLEL_PARTITION_H
  34 #define _GLIBCXX_PARALLEL_PARTITION_H 1
  35
  36 #include <parallel/basic_iterator.h>
  37 #include <parallel/sort.h>
  38 #include <parallel/random_number.h>
  39 #include <bits/stl_algo.h>
  40 #include <parallel/parallel.h>
  41
  42 /** @brief Decide whether to declare certain variables volatile. */
  43 #define _GLIBCXX_VOLATILE volatile
  44
  45 namespace __gnu_parallel
  46 {
  47   /** @brief Parallel implementation of std::partition.
  48     *  @param __begin Begin iterator of input sequence to split.
  49     *  @param __end End iterator of input sequence to split.
  50     *  @param __pred Partition predicate, possibly including some kind
  51     *         of pivot.
  52     *  @param __num_threads Maximum number of threads to use for this task.
  53     *  @return Number of elements not fulfilling the predicate. */
  54   template<typename _RAIter, typename _Predicate>
  55     typename std::iterator_traits<_RAIter>::difference_type
  56     __parallel_partition(_RAIter __begin, _RAIter __end,
  57                          _Predicate __pred, _ThreadIndex __num_threads)
  58     {
  59       typedef std::iterator_traits<_RAIter> _TraitsType;
  60       typedef typename _TraitsType::value_type _ValueType;
  61       typedef typename _TraitsType::difference_type _DifferenceType;
  62
  63       _DifferenceType __n = __end - __begin;
  64
  65       _GLIBCXX_CALL(__n)
  66
  67       const _Settings& __s = _Settings::get();
  68
  69       // shared
  70       _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1,
  71                                         __dist = __n,
  72                                         __leftover_left, __leftover_right,
  73                                         __leftnew, __rightnew;
  74
  75       // just 0 or 1, but int to allow atomic operations
  76       int* __reserved_left = 0, * __reserved_right = 0;
  77
  78       _DifferenceType __chunk_size = __s.partition_chunk_size;
  79
  80       //at least two chunks per thread
  81       if (__dist >= 2 * __num_threads * __chunk_size)
  82 #       pragma omp parallel num_threads(__num_threads)
  83         {
  84 #         pragma omp single
  85           {
  86             __num_threads = omp_get_num_threads();
  87             __reserved_left = new int[__num_threads];
  88             __reserved_right = new int[__num_threads];
  89
  90             if (__s.partition_chunk_share > 0.0)
  91               __chunk_size = std::max<_DifferenceType>
  92                 (__s.partition_chunk_size, (double)__n
  93                  * __s.partition_chunk_share / (double)__num_threads);
  94             else
  95               __chunk_size = __s.partition_chunk_size;
  96           }
  97
  98           while (__dist >= 2 * __num_threads * __chunk_size)
  99             {
 100 #             pragma omp single
 101               {
 102                 _DifferenceType __num_chunks = __dist / __chunk_size;
 103
 104                 for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
 105                   {
 106                     __reserved_left [__r] = 0; // false
 107                     __reserved_right[__r] = 0; // false
 108                   }
 109                 __leftover_left = 0;
 110                 __leftover_right = 0;
 111               } //implicit barrier
 112
 113               // Private.
 114               _DifferenceType __thread_left, __thread_left_border,
 115                               __thread_right, __thread_right_border;
 116
 117               __thread_left = __left + 1;
 118               // Just to satisfy the condition below.
 119               __thread_left_border = __thread_left - 1;
 120
 121               __thread_right = __n - 1;
 122              // Just to satisfy the condition below.
 123               __thread_right_border = __thread_right + 1;
 124
 125               bool __iam_finished = false;
 126               while (!__iam_finished)
 127                 {
 128                   if (__thread_left > __thread_left_border)
 129                     {
 130                       _DifferenceType __former_dist =
 131                               __fetch_and_add(&__dist, -__chunk_size);
 132                       if (__former_dist < __chunk_size)
 133                         {
 134                           __fetch_and_add(&__dist, __chunk_size);
 135                           __iam_finished = true;
 136                           break;
 137                         }
 138                       else
 139                         {
 140                           __thread_left =
 141                                   __fetch_and_add(&__left, __chunk_size);
 142                           __thread_left_border =
 143                                   __thread_left + (__chunk_size - 1);
 144                         }
 145                     }
 146
 147                   if (__thread_right < __thread_right_border)
 148                     {
 149                       _DifferenceType __former_dist =
 150                               __fetch_and_add(&__dist, -__chunk_size);
 151                       if (__former_dist < __chunk_size)
 152                         {
 153                           __fetch_and_add(&__dist, __chunk_size);
 154                           __iam_finished = true;
 155                           break;
 156                         }
 157                       else
 158                         {
 159                           __thread_right =
 160                                   __fetch_and_add(&__right, -__chunk_size);
 161                           __thread_right_border =
 162                                   __thread_right - (__chunk_size - 1);
 163                         }
 164                     }
 165
 166                   // Swap as usual.
 167                   while (__thread_left < __thread_right)
 168                     {
 169                       while (__pred(__begin[__thread_left])
 170                              && __thread_left <= __thread_left_border)
 171                         ++__thread_left;
 172                       while (!__pred(__begin[__thread_right])
 173                              && __thread_right >= __thread_right_border)
 174                         --__thread_right;
 175
 176                       if (__thread_left > __thread_left_border
 177                           || __thread_right < __thread_right_border)
 178                         // Fetch new chunk(__s).
 179                         break;
 180
 181                       std::iter_swap(__begin + __thread_left,
 182                              __begin + __thread_right);
 183                       ++__thread_left;
 184                       --__thread_right;
 185                     }
 186                 }
 187
 188               // Now swap the leftover chunks to the right places.
 189               if (__thread_left <= __thread_left_border)
 190 #               pragma omp atomic
 191                 ++__leftover_left;
 192               if (__thread_right >= __thread_right_border)
 193 #               pragma omp atomic
 194                 ++__leftover_right;
 195
 196 #             pragma omp barrier
 197
 198               _DifferenceType
 199                     __leftold = __left,
 200                     __leftnew = __left - __leftover_left * __chunk_size,
 201                     __rightold = __right,
 202                     __rightnew = __right + __leftover_right * __chunk_size;
 203
 204               // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
 205               if (__thread_left <= __thread_left_border
 206                   && __thread_left_border >= __leftnew)
 207                 {
 208                   // Chunk already in place, reserve spot.
 209                 __reserved_left[(__left - (__thread_left_border + 1))
 210                                 / __chunk_size] = 1;
 211                 }
 212
 213               // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
 214               if (__thread_right >= __thread_right_border
 215                   && __thread_right_border <= __rightnew)
 216                 {
 217                   // Chunk already in place, reserve spot.
 218                   __reserved_right[((__thread_right_border - 1) - __right)
 219                                    / __chunk_size] = 1;
 220                 }
 221
 222 #             pragma omp barrier
 223
 224               if (__thread_left <= __thread_left_border
 225                   && __thread_left_border < __leftnew)
 226                 {
 227                   // Find spot and swap.
 228                   _DifferenceType __swapstart = -1;
 229                   for (int __r = 0; __r < __leftover_left; ++__r)
 230                     if (__reserved_left[__r] == 0
 231                         && __compare_and_swap(&(__reserved_left[__r]), 0, 1))
 232                       {
 233                         __swapstart = __leftold - (__r + 1) * __chunk_size;
 234                         break;
 235                       }
 236
 237 #if _GLIBCXX_ASSERTIONS
 238                   _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
 239 #endif
 240
 241                   std::swap_ranges(__begin + __thread_left_border
 242                                    - (__chunk_size - 1),
 243                                    __begin + __thread_left_border + 1,
 244                                    __begin + __swapstart);
 245                 }
 246
 247               if (__thread_right >= __thread_right_border
 248                   && __thread_right_border > __rightnew)
 249                 {
 250                   // Find spot and swap
 251                   _DifferenceType __swapstart = -1;
 252                   for (int __r = 0; __r < __leftover_right; ++__r)
 253                     if (__reserved_right[__r] == 0
 254                         && __compare_and_swap(&(__reserved_right[__r]), 0, 1))
 255                       {
 256                         __swapstart = __rightold + __r * __chunk_size + 1;
 257                         break;
 258                       }
 259
 260 #if _GLIBCXX_ASSERTIONS
 261                   _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
 262 #endif
 263
 264                   std::swap_ranges(__begin + __thread_right_border,
 265                                    __begin + __thread_right_border
 266                                    + __chunk_size, __begin + __swapstart);
 267               }
 268 #if _GLIBCXX_ASSERTIONS
 269 #             pragma omp barrier
 270
 271 #             pragma omp single
 272               {
 273                 for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
 274                   _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);
 275                 for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
 276                   _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);
 277               }
 278 #endif
 279
 280               __left = __leftnew;
 281               __right = __rightnew;
 282               __dist = __right - __left + 1;
 283             }
 284
 285 #           pragma omp flush(__left, __right)
 286         } // end "recursion" //parallel
 287
 288         _DifferenceType __final_left = __left, __final_right = __right;
 289
 290         while (__final_left < __final_right)
 291           {
 292             // Go right until key is geq than pivot.
 293             while (__pred(__begin[__final_left])
 294                    && __final_left < __final_right)
 295               ++__final_left;
 296
 297             // Go left until key is less than pivot.
 298             while (!__pred(__begin[__final_right])
 299                    && __final_left < __final_right)
 300               --__final_right;
 301
 302             if (__final_left == __final_right)
 303               break;
 304             std::iter_swap(__begin + __final_left, __begin + __final_right);
 305             ++__final_left;
 306             --__final_right;
 307           }
 308
 309         // All elements on the left side are < piv, all elements on the
 310         // right are >= piv
 311         delete[] __reserved_left;
 312         delete[] __reserved_right;
 313
 314         // Element "between" __final_left and __final_right might not have
 315         // been regarded yet
 316         if (__final_left < __n && !__pred(__begin[__final_left]))
 317           // Really swapped.
 318           return __final_left;
 319         else
 320           return __final_left + 1;
 321     }
 322
 323   /**
 324     *  @brief Parallel implementation of std::nth_element().
 325     *  @param __begin Begin iterator of input sequence.
 326     *  @param __nth _Iterator of element that must be in position afterwards.
 327     *  @param __end End iterator of input sequence.
 328     *  @param __comp Comparator.
 329     */
 330   template<typename _RAIter, typename _Compare>
 331     void
 332     __parallel_nth_element(_RAIter __begin, _RAIter __nth,
 333                            _RAIter __end, _Compare __comp)
 334     {
 335       typedef std::iterator_traits<_RAIter> _TraitsType;
 336       typedef typename _TraitsType::value_type _ValueType;
 337       typedef typename _TraitsType::difference_type _DifferenceType;
 338
 339       _GLIBCXX_CALL(__end - __begin)
 340
 341       _RAIter __split;
 342       _RandomNumber __rng;
 343
 344       const _Settings& __s = _Settings::get();
 345       _DifferenceType __minimum_length = std::max<_DifferenceType>(2,
 346         std::max(__s.nth_element_minimal_n, __s.partition_minimal_n));
 347
 348       // Break if input range to small.
 349       while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)
 350         {
 351           _DifferenceType __n = __end - __begin;
 352
 353           _RAIter __pivot_pos = __begin + __rng(__n);
 354
 355           // Swap __pivot_pos value to end.
 356           if (__pivot_pos != (__end - 1))
 357             std::iter_swap(__pivot_pos, __end - 1);
 358           __pivot_pos = __end - 1;
 359
 360           // _Compare must have first_value_type, second_value_type,
 361           // result_type
 362           // _Compare ==
 363           // __gnu_parallel::_Lexicographic<S, int,
 364           //                                __gnu_parallel::_Less<S, S> >
 365           // __pivot_pos == std::pair<S, int>*
 366           __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
 367             __pred(__comp, *__pivot_pos);
 368
 369           // Divide, leave pivot unchanged in last place.
 370           _RAIter __split_pos1, __split_pos2;
 371           __split_pos1 = __begin + __parallel_partition(__begin, __end - 1,
 372                                                         __pred,
 373                                                         __get_max_threads());
 374
 375           // Left side: < __pivot_pos; __right side: >= __pivot_pos
 376
 377           // Swap pivot back to middle.
 378           if (__split_pos1 != __pivot_pos)
 379             std::iter_swap(__split_pos1, __pivot_pos);
 380           __pivot_pos = __split_pos1;
 381
 382           // In case all elements are equal, __split_pos1 == 0
 383           if ((__split_pos1 + 1 - __begin) < (__n >> 7)
 384               || (__end - __split_pos1) < (__n >> 7))
 385             {
 386               // Very unequal split, one part smaller than one 128th
 387               // elements not strictly larger than the pivot.
 388               __gnu_parallel::__unary_negate<__gnu_parallel::
 389                 __binder1st<_Compare, _ValueType,
 390                             _ValueType, bool>, _ValueType>
 391                 __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,
 392                        _ValueType, bool>(__comp, *__pivot_pos));
 393
 394               // Find other end of pivot-equal range.
 395               __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,
 396                                                          __end, __pred);
 397             }
 398           else
 399             // Only skip the pivot.
 400             __split_pos2 = __split_pos1 + 1;
 401
 402           // Compare iterators.
 403           if (__split_pos2 <= __nth)
 404             __begin = __split_pos2;
 405           else if (__nth < __split_pos1)
 406             __end = __split_pos1;
 407           else
 408             break;
 409         }
 410
 411       // Only at most _Settings::partition_minimal_n __elements __left.
 412       __gnu_sequential::nth_element(__begin, __nth, __end, __comp);
 413     }
 414
 415   /** @brief Parallel implementation of std::partial_sort().
 416   *  @param __begin Begin iterator of input sequence.
 417   *  @param __middle Sort until this position.
 418   *  @param __end End iterator of input sequence.
 419   *  @param __comp Comparator. */
 420   template<typename _RAIter, typename _Compare>
 421     void
 422     __parallel_partial_sort(_RAIter __begin,
 423                             _RAIter __middle,
 424                             _RAIter __end, _Compare __comp)
 425     {
 426       __parallel_nth_element(__begin, __middle, __end, __comp);
 427       std::sort(__begin, __middle, __comp);
 428     }
 429
 430 } //namespace __gnu_parallel
 431
 432 #undef _GLIBCXX_VOLATILE
 433
 434 #endif /* _GLIBCXX_PARALLEL_PARTITION_H */