search.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/search.h
00026  *  @brief Parallel implementation base for std::search() and
00027  *  std::search_n().
00028  *  This file is a GNU parallel extension to the Standard C++ Library.
00029  */
00030 
00031 // Written by Felix Putze.
00032 
00033 #ifndef _GLIBCXX_PARALLEL_SEARCH_H
00034 #define _GLIBCXX_PARALLEL_SEARCH_H 1
00035 
00036 #include <bits/stl_algobase.h>
00037 
00038 #include <parallel/parallel.h>
00039 #include <parallel/equally_split.h>
00040 
00041 
00042 namespace __gnu_parallel
00043 {
00044   /**
00045    *  @brief Precalculate advances for Knuth-Morris-Pratt algorithm.
00046    *  @param elements Begin iterator of sequence to search for.
00047    *  @param length Length of sequence to search for.
00048    *  @param advances Returned offsets. 
00049    */
00050 template<typename RandomAccessIterator, typename _DifferenceTp>
00051   void
00052   calc_borders(RandomAccessIterator elements, _DifferenceTp length, 
00053               _DifferenceTp* off)
00054   {
00055     typedef _DifferenceTp difference_type;
00056 
00057     off[0] = -1;
00058     if (length > 1)
00059       off[1] = 0;
00060     difference_type k = 0;
00061     for (difference_type j = 2; j <= length; j++)
00062       {
00063         while ((k >= 0) && !(elements[k] == elements[j-1]))
00064           k = off[k];
00065         off[j] = ++k;
00066       }
00067   }
00068 
00069   // Generic parallel find algorithm (requires random access iterator).
00070 
00071   /** @brief Parallel std::search.
00072    *  @param begin1 Begin iterator of first sequence.
00073    *  @param end1 End iterator of first sequence.
00074    *  @param begin2 Begin iterator of second sequence.
00075    *  @param end2 End iterator of second sequence.
00076    *  @param pred Find predicate.
00077    *  @return Place of finding in first sequences. */
00078 template<typename _RandomAccessIterator1,
00079      typename _RandomAccessIterator2,
00080      typename Pred>
00081   _RandomAccessIterator1
00082   search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1,
00083                   _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2,
00084                   Pred pred)
00085   {
00086     typedef std::iterator_traits<_RandomAccessIterator1> traits_type;
00087     typedef typename traits_type::difference_type difference_type;
00088 
00089     _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2));
00090 
00091     difference_type pattern_length = end2 - begin2;
00092 
00093     // Pattern too short.
00094     if(pattern_length <= 0)
00095       return end1;
00096 
00097     // Last point to start search.
00098     difference_type input_length = (end1 - begin1) - pattern_length;
00099 
00100     // Where is first occurrence of pattern? defaults to end.
00101     difference_type result = (end1 - begin1);
00102     difference_type *splitters;
00103 
00104     // Pattern too long.
00105     if (input_length < 0)
00106       return end1;
00107 
00108     omp_lock_t result_lock;
00109     omp_init_lock(&result_lock);
00110 
00111     thread_index_t num_threads =
00112         std::max<difference_type>(1,
00113             std::min<difference_type>(input_length, get_max_threads()));
00114 
00115     difference_type advances[pattern_length];
00116     calc_borders(begin2, pattern_length, advances);
00117 
00118 #   pragma omp parallel num_threads(num_threads)
00119       {
00120 #       pragma omp single
00121           {
00122             num_threads = omp_get_num_threads();
00123             splitters = new difference_type[num_threads + 1];
00124             equally_split(input_length, num_threads, splitters);
00125           }
00126 
00127         thread_index_t iam = omp_get_thread_num();
00128 
00129         difference_type start = splitters[iam], stop = splitters[iam + 1];
00130 
00131         difference_type pos_in_pattern = 0;
00132         bool found_pattern = false;
00133 
00134         while (start <= stop && !found_pattern)
00135           {
00136             // Get new value of result.
00137             #pragma omp flush(result)
00138             // No chance for this thread to find first occurrence.
00139             if (result < start)
00140               break;
00141             while (pred(begin1[start + pos_in_pattern],
00142                          begin2[pos_in_pattern]))
00143               {
00144                 ++pos_in_pattern;
00145                 if (pos_in_pattern == pattern_length)
00146                   {
00147                     // Found new candidate for result.
00148                             omp_set_lock(&result_lock);
00149                     result = std::min(result, start);
00150                             omp_unset_lock(&result_lock);
00151 
00152                     found_pattern = true;
00153                     break;
00154                   }
00155               }
00156             // Make safe jump.
00157             start += (pos_in_pattern - advances[pos_in_pattern]);
00158             pos_in_pattern =
00159                 (advances[pos_in_pattern] < 0) ? 0 : advances[pos_in_pattern];
00160           }
00161       } //parallel
00162 
00163     omp_destroy_lock(&result_lock);
00164 
00165     delete[] splitters;
00166 
00167     // Return iterator on found element.
00168     return (begin1 + result);
00169   }
00170 } // end namespace
00171 
00172 #endif /* _GLIBCXX_PARALLEL_SEARCH_H */

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1