diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/search.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/search.h | 194 |
1 files changed, 96 insertions, 98 deletions
diff --git a/libstdc++-v3/include/parallel/search.h b/libstdc++-v3/include/parallel/search.h index 1fc8ceaa5c8..9709925618d 100644 --- a/libstdc++-v3/include/parallel/search.h +++ b/libstdc++-v3/include/parallel/search.h @@ -38,7 +38,6 @@ #include <parallel/parallel.h> #include <parallel/equally_split.h> - namespace __gnu_parallel { /** @@ -47,24 +46,24 @@ namespace __gnu_parallel * @param __length Length of sequence to search for. * @param __advances Returned __offsets. */ -template<typename _RAIter, typename _DifferenceTp> - void - __calc_borders(_RAIter __elements, _DifferenceTp __length, - _DifferenceTp* __off) - { - typedef _DifferenceTp _DifferenceType; - - __off[0] = -1; - if (__length > 1) - __off[1] = 0; - _DifferenceType __k = 0; - for (_DifferenceType __j = 2; __j <= __length; __j++) - { - while ((__k >= 0) && !(__elements[__k] == __elements[__j-1])) - __k = __off[__k]; - __off[__j] = ++__k; - } - } + template<typename _RAIter, typename _DifferenceTp> + void + __calc_borders(_RAIter __elements, _DifferenceTp __length, + _DifferenceTp* __off) + { + typedef _DifferenceTp _DifferenceType; + + __off[0] = -1; + if (__length > 1) + __off[1] = 0; + _DifferenceType __k = 0; + for (_DifferenceType __j = 2; __j <= __length; __j++) + { + while ((__k >= 0) && !(__elements[__k] == __elements[__j-1])) + __k = __off[__k]; + __off[__j] = ++__k; + } + } // Generic parallel find algorithm (requires random access iterator). @@ -75,100 +74,99 @@ template<typename _RAIter, typename _DifferenceTp> * @param __end2 End iterator of second sequence. * @param __pred Find predicate. * @return Place of finding in first sequences. */ -template<typename __RAIter1, - typename __RAIter2, - typename _Pred> - __RAIter1 - __search_template(__RAIter1 __begin1, __RAIter1 __end1, - __RAIter2 __begin2, __RAIter2 __end2, - _Pred __pred) - { - typedef std::iterator_traits<__RAIter1> _TraitsType; - typedef typename _TraitsType::difference_type _DifferenceType; + template<typename __RAIter1, + typename __RAIter2, + typename _Pred> + __RAIter1 + __search_template(__RAIter1 __begin1, __RAIter1 __end1, + __RAIter2 __begin2, __RAIter2 __end2, + _Pred __pred) + { + typedef std::iterator_traits<__RAIter1> _TraitsType; + typedef typename _TraitsType::difference_type _DifferenceType; - _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2)); + _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2)); - _DifferenceType __pattern_length = __end2 - __begin2; + _DifferenceType __pattern_length = __end2 - __begin2; - // Pattern too short. - if(__pattern_length <= 0) - return __end1; + // Pattern too short. + if(__pattern_length <= 0) + return __end1; - // Last point to start search. - _DifferenceType __input_length = (__end1 - __begin1) - __pattern_length; + // Last point to start search. + _DifferenceType __input_length = (__end1 - __begin1) - __pattern_length; - // Where is first occurrence of pattern? defaults to end. - _DifferenceType __result = (__end1 - __begin1); - _DifferenceType *__splitters; + // Where is first occurrence of pattern? defaults to end. + _DifferenceType __result = (__end1 - __begin1); + _DifferenceType *__splitters; - // Pattern too long. - if (__input_length < 0) - return __end1; + // Pattern too long. + if (__input_length < 0) + return __end1; - omp_lock_t __result_lock; - omp_init_lock(&__result_lock); + omp_lock_t __result_lock; + omp_init_lock(&__result_lock); - _ThreadIndex __num_threads = - std::max<_DifferenceType>(1, - std::min<_DifferenceType>(__input_length, __get_max_threads())); + _ThreadIndex __num_threads = std::max<_DifferenceType> + (1, std::min<_DifferenceType>(__input_length, + __get_max_threads())); - _DifferenceType __advances[__pattern_length]; - __calc_borders(__begin2, __pattern_length, __advances); + _DifferenceType __advances[__pattern_length]; + __calc_borders(__begin2, __pattern_length, __advances); -# pragma omp parallel num_threads(__num_threads) +# pragma omp parallel num_threads(__num_threads) { # pragma omp single - { - __num_threads = omp_get_num_threads(); - __splitters = new _DifferenceType[__num_threads + 1]; - equally_split(__input_length, __num_threads, __splitters); - } - - _ThreadIndex __iam = omp_get_thread_num(); - - _DifferenceType __start = __splitters[__iam], - __stop = __splitters[__iam + 1]; - - _DifferenceType __pos_in_pattern = 0; - bool __found_pattern = false; - - while (__start <= __stop && !__found_pattern) - { - // Get new value of result. - #pragma omp flush(__result) - // No chance for this thread to find first occurrence. - if (__result < __start) - break; - while (__pred(__begin1[__start + __pos_in_pattern], - __begin2[__pos_in_pattern])) - { - ++__pos_in_pattern; - if (__pos_in_pattern == __pattern_length) - { - // Found new candidate for result. - omp_set_lock(&__result_lock); - __result = std::min(__result, __start); - omp_unset_lock(&__result_lock); - - __found_pattern = true; - break; - } - } - // Make safe jump. - __start += (__pos_in_pattern - __advances[__pos_in_pattern]); - __pos_in_pattern = - (__advances[__pos_in_pattern] < 0) ? - 0 : __advances[__pos_in_pattern]; - } + { + __num_threads = omp_get_num_threads(); + __splitters = new _DifferenceType[__num_threads + 1]; + equally_split(__input_length, __num_threads, __splitters); + } + + _ThreadIndex __iam = omp_get_thread_num(); + + _DifferenceType __start = __splitters[__iam], + __stop = __splitters[__iam + 1]; + + _DifferenceType __pos_in_pattern = 0; + bool __found_pattern = false; + + while (__start <= __stop && !__found_pattern) + { + // Get new value of result. +#pragma omp flush(__result) + // No chance for this thread to find first occurrence. + if (__result < __start) + break; + while (__pred(__begin1[__start + __pos_in_pattern], + __begin2[__pos_in_pattern])) + { + ++__pos_in_pattern; + if (__pos_in_pattern == __pattern_length) + { + // Found new candidate for result. + omp_set_lock(&__result_lock); + __result = std::min(__result, __start); + omp_unset_lock(&__result_lock); + + __found_pattern = true; + break; + } + } + // Make safe jump. + __start += (__pos_in_pattern - __advances[__pos_in_pattern]); + __pos_in_pattern = (__advances[__pos_in_pattern] < 0 + ? 0 : __advances[__pos_in_pattern]); + } } //parallel - omp_destroy_lock(&__result_lock); - - delete[] __splitters; + omp_destroy_lock(&__result_lock); - // Return iterator on found element. - return (__begin1 + __result); - } + delete[] __splitters; + + // Return iterator on found element. + return (__begin1 + __result); + } } // end namespace #endif /* _GLIBCXX_PARALLEL_SEARCH_H */ |