111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2007-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file parallel/find.h 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Parallel implementation base for std::find(), std::equal() 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * and related functions. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This file is a GNU parallel extension to the Standard C++ Library. 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Written by Felix Putze and Johannes Singler. 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_PARALLEL_FIND_H 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_PARALLEL_FIND_H 1 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <bits/stl_algobase.h> 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/features.h> 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/parallel.h> 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/compatibility.h> 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/equally_split.h> 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_parallel 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Parallel std::find, switch for different algorithms. 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. Must have same 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * length as first sequence. 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Place of finding in both sequences. 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _RAIter2, 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred, 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Selector> 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<_RAIter1, _RAIter2> 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __find_template(_RAIter1 __begin1, _RAIter1 __end1, 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred, _Selector __selector) 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch (_Settings::get().find_algorithm) 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case GROWING_BLOCKS: 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __find_template(__begin1, __end1, __begin2, __pred, 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __selector, growing_blocks_tag()); 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case CONSTANT_SIZE_BLOCKS: 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __find_template(__begin1, __end1, __begin2, __pred, 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __selector, constant_size_blocks_tag()); 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case EQUAL_SPLIT: 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __find_template(__begin1, __end1, __begin2, __pred, 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __selector, equal_split_tag()); 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert default: 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT(false); 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(__begin1, __begin2); 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if _GLIBCXX_FIND_EQUAL_SPLIT 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Parallel std::find, equal splitting variant. 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. Second __sequence 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * must have same length as first sequence. 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Place of finding in both sequences. 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _RAIter2, 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred, 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Selector> 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __find_template(_RAIter1 __begin1, _RAIter1 __end1, 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred, 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Selector __selector, equal_split_tag) 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_CALL(__end1 - __begin1) 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::iterator_traits<_RAIter1> _TraitsType; 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _TraitsType::difference_type _DifferenceType; 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _TraitsType::value_type _ValueType; 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __length = __end1 - __begin1; 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __result = __length; 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType* __borders; 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_lock_t __result_lock; 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_init_lock(&__result_lock); 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ThreadIndex __num_threads = __get_max_threads(); 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp parallel num_threads(__num_threads) 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp single 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __num_threads = omp_get_num_threads(); 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __borders = new _DifferenceType[__num_threads + 1]; 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __equally_split(__length, __num_threads, __borders); 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } //single 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ThreadIndex __iam = omp_get_thread_num(); 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __start = __borders[__iam], 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __stop = __borders[__iam + 1]; 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __i1 = __begin1 + __start; 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __i2 = __begin2 + __start; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_DifferenceType __pos = __start; __pos < __stop; ++__pos) 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp flush(__result) 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Result has been set to something lower. 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result < __pos) 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__selector(__i1, __i2, __pred)) 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_set_lock(&__result_lock); 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__pos < __result) 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __pos; 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_unset_lock(&__result_lock); 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__i1; 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__i2; 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } //parallel 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_destroy_lock(&__result_lock); 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert delete[] __borders; 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::pair<_RAIter1, _RAIter2>(__begin1 + __result, 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 + __result); 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if _GLIBCXX_FIND_GROWING_BLOCKS 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Parallel std::find, growing block size variant. 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. Second __sequence 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * must have same length as first sequence. 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Place of finding in both sequences. 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @see __gnu_parallel::_Settings::find_sequential_search_size 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @see __gnu_parallel::_Settings::find_scale_factor 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * There are two main differences between the growing blocks and 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * the constant-size blocks variants. 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1. For GB, the block size grows; for CSB, the block size is fixed. 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 2. For GB, the blocks are allocated dynamically; 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * for CSB, the blocks are allocated in a predetermined manner, 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * namely spacial round-robin. 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _RAIter2, 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred, 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Selector> 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __find_template(_RAIter1 __begin1, _RAIter1 __end1, 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred, _Selector __selector, 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert growing_blocks_tag) 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_CALL(__end1 - __begin1) 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::iterator_traits<_RAIter1> _TraitsType; 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _TraitsType::difference_type _DifferenceType; 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _TraitsType::value_type _ValueType; 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Settings& __s = _Settings::get(); 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __length = __end1 - __begin1; 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __sequential_search_size = std::min<_DifferenceType> 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__length, __s.find_sequential_search_size); 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Try it sequentially first. 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __find_seq_result = __selector._M_sequential_algorithm 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__begin1, __begin1 + __sequential_search_size, 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2, __pred); 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__find_seq_result.first != (__begin1 + __sequential_search_size)) 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __find_seq_result; 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Index of beginning of next free block (after sequential find). 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __next_block_start = __sequential_search_size; 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __result = __length; 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_lock_t __result_lock; 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_init_lock(&__result_lock); 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const float __scale_factor = __s.find_scale_factor; 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ThreadIndex __num_threads = __get_max_threads(); 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp parallel shared(__result) num_threads(__num_threads) 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp single 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __num_threads = omp_get_num_threads(); 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Not within first __k elements -> start parallel. 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ThreadIndex __iam = omp_get_thread_num(); 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __block_size = 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::max<_DifferenceType>(1, __scale_factor * __next_block_start); 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __start = __fetch_and_add<_DifferenceType> 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (&__next_block_start, __block_size); 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Get new block, update pointer to next block. 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __stop = 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::min<_DifferenceType>(__length, __start + __block_size); 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> __local_result; 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__start < __length) 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp flush(__result) 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Get new value of result. 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result < __start) 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // No chance to find first element. 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __local_result = __selector._M_sequential_algorithm 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__begin1 + __start, __begin1 + __stop, 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 + __start, __pred); 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__local_result.first != (__begin1 + __stop)) 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_set_lock(&__result_lock); 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if ((__local_result.first - __begin1) < __result) 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __local_result.first - __begin1; 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Result cannot be in future blocks, stop algorithm. 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __fetch_and_add<_DifferenceType>(&__next_block_start, 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __length); 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_unset_lock(&__result_lock); 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __block_size = 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::max<_DifferenceType>(1, __scale_factor * __next_block_start); 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Get new block, update pointer to next block. 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __start = __fetch_and_add<_DifferenceType>(&__next_block_start, 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __block_size); 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __stop = 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::min<_DifferenceType>(__length, __start + __block_size); 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } //parallel 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_destroy_lock(&__result_lock); 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Return iterator on found element. 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2>(__begin1 + __result, 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 + __result); 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if _GLIBCXX_FIND_CONSTANT_SIZE_BLOCKS 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Parallel std::find, constant block size variant. 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. Second __sequence 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * must have same length as first sequence. 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __selector _Functionality (e. g. std::find_if(), std::equal(),...) 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Place of finding in both sequences. 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @see __gnu_parallel::_Settings::find_sequential_search_size 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @see __gnu_parallel::_Settings::find_block_size 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * There are two main differences between the growing blocks and the 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * constant-size blocks variants. 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1. For GB, the block size grows; for CSB, the block size is fixed. 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 2. For GB, the blocks are allocated dynamically; for CSB, the 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * blocks are allocated in a predetermined manner, namely spacial 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * round-robin. 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _RAIter2, 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred, 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Selector> 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __find_template(_RAIter1 __begin1, _RAIter1 __end1, 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred, _Selector __selector, 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert constant_size_blocks_tag) 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_CALL(__end1 - __begin1) 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::iterator_traits<_RAIter1> _TraitsType; 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _TraitsType::difference_type _DifferenceType; 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _TraitsType::value_type _ValueType; 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _Settings& __s = _Settings::get(); 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __length = __end1 - __begin1; 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __sequential_search_size = std::min<_DifferenceType> 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__length, __s.find_sequential_search_size); 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Try it sequentially first. 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __find_seq_result = __selector._M_sequential_algorithm 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__begin1, __begin1 + __sequential_search_size, __begin2, __pred); 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__find_seq_result.first != (__begin1 + __sequential_search_size)) 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __find_seq_result; 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __result = __length; 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_lock_t __result_lock; 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_init_lock(&__result_lock); 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Not within first __sequential_search_size elements -> start parallel. 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ThreadIndex __num_threads = __get_max_threads(); 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp parallel shared(__result) num_threads(__num_threads) 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp single 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __num_threads = omp_get_num_threads(); 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ThreadIndex __iam = omp_get_thread_num(); 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __block_size = __s.find_initial_block_size; 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // First element of thread's current iteration. 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __iteration_start = __sequential_search_size; 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Where to work (initialization). 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __start = __iteration_start + __iam * __block_size; 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceType __stop = std::min<_DifferenceType>(__length, 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __start 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert + __block_size); 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> __local_result; 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__start < __length) 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Get new value of result. 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# pragma omp flush(__result) 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // No chance to find first element. 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result < __start) 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __local_result = __selector._M_sequential_algorithm 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__begin1 + __start, __begin1 + __stop, 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 + __start, __pred); 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__local_result.first != (__begin1 + __stop)) 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_set_lock(&__result_lock); 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if ((__local_result.first - __begin1) < __result) 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __local_result.first - __begin1; 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_unset_lock(&__result_lock); 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Will not find better value in its interval. 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __iteration_start += __num_threads * __block_size; 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Where to work. 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __start = __iteration_start + __iam * __block_size; 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __stop = std::min<_DifferenceType>(__length, 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __start + __block_size); 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } //parallel 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_destroy_lock(&__result_lock); 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Return iterator on found element. 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::pair<_RAIter1, _RAIter2>(__begin1 + __result, 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 + __result); 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // end namespace 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _GLIBCXX_PARALLEL_FIND_H */ 406