libstdc++
|
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 */