libstdc++-v3/include/parallel/search.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/search.h
  26  *  @brief Parallel implementation base for std::search() and
  27  *  std::search_n().
  28  *  This file is a GNU parallel extension to the Standard C++ Library.
  29  */
  30
  31 // Written by Felix Putze.
  32
  33 #ifndef _GLIBCXX_PARALLEL_SEARCH_H
  34 #define _GLIBCXX_PARALLEL_SEARCH_H 1
  35
  36 #include <bits/stl_algobase.h>
  37
  38 #include <parallel/parallel.h>
  39 #include <parallel/equally_split.h>
  40
  41 namespace __gnu_parallel
  42 {
  43   /**
  44    *  @brief Precalculate __advances for Knuth-Morris-Pratt algorithm.
  45    *  @param __elements Begin iterator of sequence to search for.
  46    *  @param __length Length of sequence to search for.
  47    *  @param __advances Returned __offsets.
  48    */
  49   template<typename _RAIter, typename _DifferenceTp>
  50     void
  51     __calc_borders(_RAIter __elements, _DifferenceTp __length,
  52                    _DifferenceTp* __off)
  53     {
  54       typedef _DifferenceTp _DifferenceType;
  55
  56       __off[0] = -1;
  57       if (__length > 1)
  58         __off[1] = 0;
  59       _DifferenceType __k = 0;
  60       for (_DifferenceType __j = 2; __j <= __length; __j++)
  61         {
  62           while ((__k >= 0) && !(__elements[__k] == __elements[__j-1]))
  63             __k = __off[__k];
  64           __off[__j] = ++__k;
  65         }
  66     }
  67
  68   // Generic parallel find algorithm (requires random access iterator).
  69
  70   /** @brief Parallel std::search.
  71    *  @param __begin1 Begin iterator of first sequence.
  72    *  @param __end1 End iterator of first sequence.
  73    *  @param __begin2 Begin iterator of second sequence.
  74    *  @param __end2 End iterator of second sequence.
  75    *  @param __pred Find predicate.
  76    *  @return Place of finding in first sequences. */
  77   template<typename __RAIter1,
  78            typename __RAIter2,
  79            typename _Pred>
  80     __RAIter1
  81     __search_template(__RAIter1 __begin1, __RAIter1 __end1,
  82                       __RAIter2 __begin2, __RAIter2 __end2,
  83                       _Pred __pred)
  84     {
  85       typedef std::iterator_traits<__RAIter1> _TraitsType;
  86       typedef typename _TraitsType::difference_type _DifferenceType;
  87
  88       _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2));
  89
  90       _DifferenceType __pattern_length = __end2 - __begin2;
  91
  92       // Pattern too short.
  93       if(__pattern_length <= 0)
  94         return __end1;
  95
  96       // Last point to start search.
  97       _DifferenceType __input_length = (__end1 - __begin1) - __pattern_length;
  98
  99       // Where is first occurrence of pattern? defaults to end.
 100       _DifferenceType __result = (__end1 - __begin1);
 101       _DifferenceType *__splitters;
 102
 103       // Pattern too long.
 104       if (__input_length < 0)
 105         return __end1;
 106
 107       omp_lock_t __result_lock;
 108       omp_init_lock(&__result_lock);
 109
 110       _ThreadIndex __num_threads = std::max<_DifferenceType>
 111         (1, std::min<_DifferenceType>(__input_length,
 112                                       __get_max_threads()));
 113
 114       _DifferenceType __advances[__pattern_length];
 115       __calc_borders(__begin2, __pattern_length, __advances);
 116
 117 #     pragma omp parallel num_threads(__num_threads)
 118       {
 119 #       pragma omp single
 120         {
 121           __num_threads = omp_get_num_threads();
 122           __splitters = new _DifferenceType[__num_threads + 1];
 123           equally_split(__input_length, __num_threads, __splitters);
 124         }
 125
 126         _ThreadIndex __iam = omp_get_thread_num();
 127
 128         _DifferenceType __start = __splitters[__iam],
 129                          __stop = __splitters[__iam + 1];
 130
 131         _DifferenceType __pos_in_pattern = 0;
 132         bool __found_pattern = false;
 133
 134         while (__start <= __stop && !__found_pattern)
 135           {
 136             // Get new value of result.
 137 #pragma omp flush(__result)
 138             // No chance for this thread to find first occurrence.
 139             if (__result < __start)
 140               break;
 141             while (__pred(__begin1[__start + __pos_in_pattern],
 142                           __begin2[__pos_in_pattern]))
 143               {
 144                 ++__pos_in_pattern;
 145                 if (__pos_in_pattern == __pattern_length)
 146                   {
 147                     // Found new candidate for result.
 148                     omp_set_lock(&__result_lock);
 149                     __result = std::min(__result, __start);
 150                     omp_unset_lock(&__result_lock);
 151
 152                     __found_pattern = true;
 153                     break;
 154                   }
 155               }
 156             // Make safe jump.
 157             __start += (__pos_in_pattern - __advances[__pos_in_pattern]);
 158             __pos_in_pattern = (__advances[__pos_in_pattern] < 0
 159                                 ? 0 : __advances[__pos_in_pattern]);
 160           }
 161       } //parallel
 162
 163       omp_destroy_lock(&__result_lock);
 164
 165       delete[] __splitters;
 166
 167       // Return iterator on found element.
 168       return (__begin1 + __result);
 169     }
 170 } // end namespace
 171
 172 #endif /* _GLIBCXX_PARALLEL_SEARCH_H */