libstdc++-v3/include/parallel/search.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/search.h
  32  *  @brief Parallel implementation base for std::search() and
  33  *  std::search_n().
  34  *  This file is a GNU parallel extension to the Standard C++ Library.
  35  */
  36
  37 // Written by Felix Putze.
  38
  39 #ifndef _GLIBCXX_PARALLEL_SEARCH_H
  40 #define _GLIBCXX_PARALLEL_SEARCH_H 1
  41
  42 #include <bits/stl_algobase.h>
  43
  44 #include <parallel/parallel.h>
  45 #include <parallel/equally_split.h>
  46
  47
  48 namespace __gnu_parallel
  49 {
  50   /**
  51    *  @brief Precalculate advances for Knuth-Morris-Pratt algorithm.
  52    *  @param elements Begin iterator of sequence to search for.
  53    *  @param length Length of sequence to search for.
  54    *  @param advances Returned offsets.
  55    */
  56 template<typename RandomAccessIterator, typename _DifferenceTp>
  57   void
  58   calc_borders(RandomAccessIterator elements, _DifferenceTp length,
  59               _DifferenceTp* off)
  60   {
  61     typedef _DifferenceTp difference_type;
  62
  63     off[0] = -1;
  64     if (length > 1)
  65       off[1] = 0;
  66     difference_type k = 0;
  67     for (difference_type j = 2; j <= length; j++)
  68       {
  69         while ((k >= 0) && !(elements[k] == elements[j-1]))
  70           k = off[k];
  71         off[j] = ++k;
  72       }
  73   }
  74
  75   // Generic parallel find algorithm (requires random access iterator).
  76
  77   /** @brief Parallel std::search.
  78    *  @param begin1 Begin iterator of first sequence.
  79    *  @param end1 End iterator of first sequence.
  80    *  @param begin2 Begin iterator of second sequence.
  81    *  @param end2 End iterator of second sequence.
  82    *  @param pred Find predicate.
  83    *  @return Place of finding in first sequences. */
  84 template<typename _RandomAccessIterator1,
  85          typename _RandomAccessIterator2,
  86          typename Pred>
  87   _RandomAccessIterator1
  88   search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1,
  89                   _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2,
  90                   Pred pred)
  91   {
  92     typedef std::iterator_traits<_RandomAccessIterator1> traits_type;
  93     typedef typename traits_type::difference_type difference_type;
  94
  95     _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2));
  96
  97     difference_type pattern_length = end2 - begin2;
  98
  99     // Pattern too short.
 100     if(pattern_length <= 0)
 101       return end1;
 102
 103     // Last point to start search.
 104     difference_type input_length = (end1 - begin1) - pattern_length;
 105
 106     // Where is first occurrence of pattern? defaults to end.
 107     difference_type result = (end1 - begin1);
 108     difference_type *splitters;
 109
 110     // Pattern too long.
 111     if (input_length < 0)
 112       return end1;
 113
 114     omp_lock_t result_lock;
 115     omp_init_lock(&result_lock);
 116
 117     thread_index_t num_threads =
 118         std::max<difference_type>(1,
 119             std::min<difference_type>(input_length, get_max_threads()));
 120
 121     difference_type advances[pattern_length];
 122     calc_borders(begin2, pattern_length, advances);
 123
 124 #   pragma omp parallel num_threads(num_threads)
 125       {
 126 #       pragma omp single
 127           {
 128             num_threads = omp_get_num_threads();
 129             splitters = new difference_type[num_threads + 1];
 130             equally_split(input_length, num_threads, splitters);
 131           }
 132
 133         thread_index_t iam = omp_get_thread_num();
 134
 135         difference_type start = splitters[iam], stop = splitters[iam + 1];
 136
 137         difference_type pos_in_pattern = 0;
 138         bool found_pattern = false;
 139
 140         while (start <= stop && !found_pattern)
 141           {
 142             // Get new value of result.
 143             #pragma omp flush(result)
 144             // No chance for this thread to find first occurrence.
 145             if (result < start)
 146               break;
 147             while (pred(begin1[start + pos_in_pattern],
 148                          begin2[pos_in_pattern]))
 149               {
 150                 ++pos_in_pattern;
 151                 if (pos_in_pattern == pattern_length)
 152                   {
 153                     // Found new candidate for result.
 154                             omp_set_lock(&result_lock);
 155                     result = std::min(result, start);
 156                             omp_unset_lock(&result_lock);
 157
 158                     found_pattern = true;
 159                     break;
 160                   }
 161               }
 162             // Make safe jump.
 163             start += (pos_in_pattern - advances[pos_in_pattern]);
 164             pos_in_pattern =
 165                 (advances[pos_in_pattern] < 0) ? 0 : advances[pos_in_pattern];
 166           }
 167       } //parallel
 168
 169     omp_destroy_lock(&result_lock);
 170
 171     delete[] splitters;
 172
 173     // Return iterator on found element.
 174     return (begin1 + result);
 175   }
 176 } // end namespace
 177
 178 #endif /* _GLIBCXX_PARALLEL_SEARCH_H */