search.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
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
00046
00047
00048
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
00070
00071
00072
00073
00074
00075
00076
00077
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
00094 if(pattern_length <= 0)
00095 return end1;
00096
00097
00098 difference_type input_length = (end1 - begin1) - pattern_length;
00099
00100
00101 difference_type result = (end1 - begin1);
00102 difference_type *splitters;
00103
00104
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
00137 #pragma omp flush(result)
00138
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
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
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 }
00162
00163 omp_destroy_lock(&result_lock);
00164
00165 delete[] splitters;
00166
00167
00168 return (begin1 + result);
00169 }
00170 }
00171
00172 #endif