libstdc++
search.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007-2015 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 namespace __gnu_parallel
00042 {
00043   /**
00044    *  @brief Precalculate __advances for Knuth-Morris-Pratt algorithm.
00045    *  @param __elements Begin iterator of sequence to search for.
00046    *  @param __length Length of sequence to search for.
00047    *  @param __off Returned __offsets. 
00048    */
00049   template<typename _RAIter, typename _DifferenceTp>
00050     void
00051     __calc_borders(_RAIter __elements, _DifferenceTp __length, 
00052                    _DifferenceTp* __off)
00053     {
00054       typedef _DifferenceTp _DifferenceType;
00055 
00056       __off[0] = -1;
00057       if (__length > 1)
00058         __off[1] = 0;
00059       _DifferenceType __k = 0;
00060       for (_DifferenceType __j = 2; __j <= __length; __j++)
00061         {
00062           while ((__k >= 0) && !(__elements[__k] == __elements[__j-1]))
00063             __k = __off[__k];
00064           __off[__j] = ++__k;
00065         }
00066     }
00067 
00068   // Generic parallel find algorithm (requires random access iterator).
00069 
00070   /** @brief Parallel std::search.
00071    *  @param __begin1 Begin iterator of first sequence.
00072    *  @param __end1 End iterator of first sequence.
00073    *  @param __begin2 Begin iterator of second sequence.
00074    *  @param __end2 End iterator of second sequence.
00075    *  @param __pred Find predicate.
00076    *  @return Place of finding in first sequences. */
00077   template<typename __RAIter1,
00078            typename __RAIter2,
00079            typename _Pred>
00080     __RAIter1
00081     __search_template(__RAIter1 __begin1, __RAIter1 __end1,
00082                       __RAIter2 __begin2, __RAIter2 __end2,
00083                       _Pred __pred)
00084     {
00085       typedef std::iterator_traits<__RAIter1> _TraitsType;
00086       typedef typename _TraitsType::difference_type _DifferenceType;
00087 
00088       _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2));
00089 
00090       _DifferenceType __pattern_length = __end2 - __begin2;
00091 
00092       // Pattern too short.
00093       if(__pattern_length <= 0)
00094         return __end1;
00095 
00096       // Last point to start search.
00097       _DifferenceType __input_length = (__end1 - __begin1) - __pattern_length;
00098 
00099       // Where is first occurrence of pattern? defaults to end.
00100       _DifferenceType __result = (__end1 - __begin1);
00101       _DifferenceType *__splitters;
00102 
00103       // Pattern too long.
00104       if (__input_length < 0)
00105         return __end1;
00106 
00107       omp_lock_t __result_lock;
00108       omp_init_lock(&__result_lock);
00109 
00110       _ThreadIndex __num_threads = std::max<_DifferenceType>
00111         (1, std::min<_DifferenceType>(__input_length,
00112                                       __get_max_threads()));
00113 
00114       _DifferenceType __advances[__pattern_length];
00115       __calc_borders(__begin2, __pattern_length, __advances);
00116 
00117 #     pragma omp parallel num_threads(__num_threads)
00118       {
00119 #       pragma omp single
00120         {
00121           __num_threads = omp_get_num_threads();
00122           __splitters = new _DifferenceType[__num_threads + 1];
00123           __equally_split(__input_length, __num_threads, __splitters);
00124         }
00125 
00126         _ThreadIndex __iam = omp_get_thread_num();
00127 
00128         _DifferenceType __start = __splitters[__iam],
00129                          __stop = __splitters[__iam + 1];
00130 
00131         _DifferenceType __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 = (__advances[__pos_in_pattern] < 0
00159                                 ? 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 */