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