libstdc++
search.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 */