33 #ifndef _GLIBCXX_PARALLEL_SEARCH_H
34 #define _GLIBCXX_PARALLEL_SEARCH_H 1
42 namespace __gnu_parallel
50 template<
typename RandomAccessIterator,
typename _DifferenceTp>
55 typedef _DifferenceTp difference_type;
60 difference_type k = 0;
61 for (difference_type j = 2; j <= length; j++)
63 while ((k >= 0) && !(elements[k] == elements[j-1]))
78 template<
typename _RandomAccessIterator1,
79 typename _RandomAccessIterator2,
81 _RandomAccessIterator1
83 _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2,
87 typedef typename traits_type::difference_type difference_type;
91 difference_type pattern_length = end2 - begin2;
94 if(pattern_length <= 0)
98 difference_type input_length = (end1 - begin1) - pattern_length;
101 difference_type result = (end1 - begin1);
102 difference_type *splitters;
105 if (input_length < 0)
108 omp_lock_t result_lock;
109 omp_init_lock(&result_lock);
112 std::max<difference_type>(1,
113 std::min<difference_type>(input_length, get_max_threads()));
115 difference_type advances[pattern_length];
118 # pragma omp parallel num_threads(num_threads)
122 num_threads = omp_get_num_threads();
123 splitters =
new difference_type[num_threads + 1];
129 difference_type start = splitters[iam], stop = splitters[iam + 1];
131 difference_type pos_in_pattern = 0;
132 bool found_pattern =
false;
134 while (start <= stop && !found_pattern)
137 #pragma omp flush(result)
141 while (pred(begin1[start + pos_in_pattern],
142 begin2[pos_in_pattern]))
145 if (pos_in_pattern == pattern_length)
148 omp_set_lock(&result_lock);
150 omp_unset_lock(&result_lock);
152 found_pattern =
true;
157 start += (pos_in_pattern - advances[pos_in_pattern]);
159 (advances[pos_in_pattern] < 0) ? 0 : advances[pos_in_pattern];
163 omp_destroy_lock(&result_lock);
168 return (begin1 + result);