contrib/gcc-4.4/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
  42 namespace __gnu_parallel
  43 {
  44   /**
  45    *  @brief Precalculate advances for Knuth-Morris-Pratt algorithm.
  46    *  @param elements Begin iterator of sequence to search for.
  47    *  @param length Length of sequence to search for.
  48    *  @param advances Returned offsets.
  49    */
  50 template<typename RandomAccessIterator, typename _DifferenceTp>
  51   void
  52   calc_borders(RandomAccessIterator elements, _DifferenceTp length,
  53               _DifferenceTp* off)
  54   {
  55     typedef _DifferenceTp difference_type;
  56
  57     off[0] = -1;
  58     if (length > 1)
  59       off[1] = 0;
  60     difference_type k = 0;
  61     for (difference_type j = 2; j <= length; j++)
  62       {
  63         while ((k >= 0) && !(elements[k] == elements[j-1]))
  64           k = off[k];
  65         off[j] = ++k;
  66       }
  67   }
  68
  69   // Generic parallel find algorithm (requires random access iterator).
  70
  71   /** @brief Parallel std::search.
  72    *  @param begin1 Begin iterator of first sequence.
  73    *  @param end1 End iterator of first sequence.
  74    *  @param begin2 Begin iterator of second sequence.
  75    *  @param end2 End iterator of second sequence.
  76    *  @param pred Find predicate.
  77    *  @return Place of finding in first sequences. */
  78 template<typename _RandomAccessIterator1,
  79          typename _RandomAccessIterator2,
  80          typename Pred>
  81   _RandomAccessIterator1
  82   search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1,
  83                   _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2,
  84                   Pred pred)
  85   {
  86     typedef std::iterator_traits<_RandomAccessIterator1> traits_type;
  87     typedef typename traits_type::difference_type difference_type;
  88
  89     _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2));
  90
  91     difference_type pattern_length = end2 - begin2;
  92
  93     // Pattern too short.
  94     if(pattern_length <= 0)
  95       return end1;
  96
  97     // Last point to start search.
  98     difference_type input_length = (end1 - begin1) - pattern_length;
  99
 100     // Where is first occurrence of pattern? defaults to end.
 101     difference_type result = (end1 - begin1);
 102     difference_type *splitters;
 103
 104     // Pattern too long.
 105     if (input_length < 0)
 106       return end1;
 107
 108     omp_lock_t result_lock;
 109     omp_init_lock(&result_lock);
 110
 111     thread_index_t num_threads =
 112         std::max<difference_type>(1,
 113             std::min<difference_type>(input_length, get_max_threads()));
 114
 115     difference_type advances[pattern_length];
 116     calc_borders(begin2, pattern_length, advances);
 117
 118 #   pragma omp parallel num_threads(num_threads)
 119       {
 120 #       pragma omp single
 121           {
 122             num_threads = omp_get_num_threads();
 123             splitters = new difference_type[num_threads + 1];
 124             equally_split(input_length, num_threads, splitters);
 125           }
 126
 127         thread_index_t iam = omp_get_thread_num();
 128
 129         difference_type start = splitters[iam], stop = splitters[iam + 1];
 130
 131         difference_type 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 =
 159                 (advances[pos_in_pattern] < 0) ? 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 */