// -*- C++ -*-
-// Copyright (C) 2007, 2008 Free Software Foundation, Inc.
+// Copyright (C) 2007-2023 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
-// Foundation; either version 2, or (at your option) any later
+// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
-// You should have received a copy of the GNU General Public License
-// along with this library; see the file COPYING. If not, write to
-// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
-// MA 02111-1307, USA.
-
-// As a special exception, you may use this file as part of a free
-// software library without restriction. Specifically, if other files
-// instantiate templates or use macros or inline functions from this
-// file, or you compile this file and link it with other files to
-// produce an executable, this file does not by itself cause the
-// resulting executable to be covered by the GNU General Public
-// License. This exception does not however invalidate any other
-// reasons why the executable file might be covered by the GNU General
-// Public License.
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
/** @file parallel/search.h
* @brief Parallel implementation base for std::search() and
#include <parallel/parallel.h>
#include <parallel/equally_split.h>
-
namespace __gnu_parallel
{
/**
- * @brief Precalculate advances for Knuth-Morris-Pratt algorithm.
- * @param elements Begin iterator of sequence to search for.
- * @param length Length of sequence to search for.
- * @param advances Returned offsets.
+ * @brief Precalculate __advances for Knuth-Morris-Pratt algorithm.
+ * @param __elements Begin iterator of sequence to search for.
+ * @param __length Length of sequence to search for.
+ * @param __off Returned __offsets.
*/
-template<typename RandomAccessIterator, typename _DifferenceTp>
- void
- calc_borders(RandomAccessIterator elements, _DifferenceTp length,
- _DifferenceTp* off)
- {
- typedef _DifferenceTp difference_type;
-
- off[0] = -1;
- if (length > 1)
- off[1] = 0;
- difference_type k = 0;
- for (difference_type 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).
/** @brief Parallel std::search.
- * @param begin1 Begin iterator of first sequence.
- * @param end1 End iterator of first sequence.
- * @param begin2 Begin iterator of second sequence.
- * @param end2 End iterator of second sequence.
- * @param pred Find predicate.
+ * @param __begin1 Begin iterator of first sequence.
+ * @param __end1 End iterator of first sequence.
+ * @param __begin2 Begin iterator of second sequence.
+ * @param __end2 End iterator of second sequence.
+ * @param __pred Find predicate.
* @return Place of finding in first sequences. */
-template<typename _RandomAccessIterator1,
- typename _RandomAccessIterator2,
- typename Pred>
- _RandomAccessIterator1
- search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1,
- _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2,
- Pred pred)
- {
- typedef std::iterator_traits<_RandomAccessIterator1> traits_type;
- typedef typename traits_type::difference_type difference_type;
+ 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));
- difference_type 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.
- difference_type 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.
- difference_type result = (end1 - begin1);
- difference_type *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);
- thread_index_t num_threads =
- std::max<difference_type>(1,
- std::min<difference_type>(input_length, get_max_threads()));
+ _ThreadIndex __num_threads = std::max<_DifferenceType>
+ (1, std::min<_DifferenceType>(__input_length,
+ __get_max_threads()));
- difference_type 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 difference_type[num_threads + 1];
- equally_split(input_length, num_threads, splitters);
- }
-
- thread_index_t iam = omp_get_thread_num();
-
- difference_type start = splitters[iam], stop = splitters[iam + 1];
-
- difference_type 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 */
projects / thirdparty / gcc.git / blobdiff