1 /* 2 * Copyright (c) 2014-2017, Siemens AG. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * 1. Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * 10 * 2. Redistributions in binary form must reproduce the above copyright notice, 11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 24 * POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #ifndef EMBB_ALGORITHMS_COUNT_H_ 28 #define EMBB_ALGORITHMS_COUNT_H_ 29 30 #include <embb/mtapi/job.h> 31 #include <embb/mtapi/execution_policy.h> 32 #include <iterator> 33 34 namespace embb { 35 namespace algorithms { 36 37 /** 38 * \defgroup CPP_ALGORITHMS_COUNT Counting 39 * Parallel count operation 40 * \ingroup CPP_ALGORITHMS 41 * \{ 42 */ 43 44 #ifdef DOXYGEN 45 46 /** 47 * Counts in parallel the number of elements in a range that are equal to 48 * the specified value. 49 * 50 * The range consists of the elements from \c first to \c last, excluding the 51 * last element. 52 * 53 * \return The number of elements that are equal to \c value 54 * \throws embb::base::ErrorException if not enough MTAPI tasks can be created 55 * to satisfy the requirements of the algorithm. 56 * \threadsafe if the elements in the range are not modified by another thread 57 * while the algorithm is executed. 58 * \note No guarantee is given on the execution order of the comparison 59 * operations.<br/> 60 * For nested algorithms, the task limit may be exceeded. In that case, 61 * increase the task limit of the MTAPI node. 62 * \see CountIf(), embb::mtapi::ExecutionPolicy 63 * \tparam RAI Random access iterator 64 * \tparam ValueType Type of \c value that is compared to the elements in the 65 * range using the \c operator==. 66 */ 67 template<typename RAI, typename ValueType> 68 typename std::iterator_traits<RAI>::difference_type Count( 69 RAI first, 70 /**< [IN] Random access iterator pointing to the first element of the range */ 71 RAI last, 72 /**< [IN] Random access iterator pointing to the last plus one element of the 73 range */ 74 const ValueType& value, 75 /**< [IN] Value that the elements in the range are compared to using 76 \c operator== */ 77 const embb::mtapi::ExecutionPolicy& policy = embb::mtapi::ExecutionPolicy(), 78 /**< [IN] embb::mtapi::ExecutionPolicy for the counting algorithm */ 79 size_t block_size = 0 80 /**< [IN] Lower bound for partitioning the range of elements into blocks that 81 are sorted in parallel. Partitioning of a block stops if its size 82 is less than or equal to \c block_size. The default value 0 means 83 that the minimum block size is determined automatically depending on 84 the number of elements in the range divided by the number of 85 available cores. */ 86 ); 87 88 /** 89 * Counts in parallel the number of elements in a range for which the comparison 90 * function returns \c true. 91 * 92 * The range consists of the elements from \c first to \c last, excluding the 93 * last element. 94 * 95 * \return The number of elements for which \c comparison returns true 96 * \throws embb::base::ErrorException if not enough MTAPI tasks can be created 97 * to satisfy the requirements of the algorithm. 98 * \threadsafe if the elements in the range are not modified by another thread 99 * while the algorithm is executed. 100 * \note No guarantee is given on the execution order of the comparison 101 * function.<br/> 102 * For nested algorithms, the task limit may be exceeded. In that case, 103 * increase the task limit of the MTAPI node. 104 * \see Count(), embb::mtapi::ExecutionPolicy 105 * \tparam RAI Random access iterator 106 * \tparam ComparisonFunction Unary predicate with argument of type 107 * <tt>std::iterator_traits<RAI>::value_type</tt> or an 108 * embb::mtapi::Job associated with an action function accepting a 109 * struct containing one member of type 110 * <tt>std::iterator_traits<RAI>::value_type</tt> as its argument 111 * buffer and a struct containing one bool member as its result buffer. 112 */ 113 template<typename RAI, typename ComparisonFunction> 114 typename std::iterator_traits<RAI>::difference_type CountIf( 115 RAI first, 116 /**< [IN] Random access iterator pointing to the first element of the range 117 RAI last, */ 118 /**< [IN] Random access iterator pointing to the last plus one element of the 119 range */ 120 ComparisonFunction comparison, 121 /**< [IN] Unary predicate used to test the elements in the range. Elements for 122 which \c comparison returns true are counted. */ 123 const embb::mtapi::ExecutionPolicy& policy = embb::mtapi::ExecutionPolicy(), 124 /**< [IN] embb::mtapi::ExecutionPolicy for the counting algorithm */ 125 size_t block_size = 0 126 /**< [IN] Lower bound for partitioning the range of elements into blocks that 127 are sorted in parallel. Partitioning of a block stops if its size 128 is less than or equal to \c block_size. The default value 0 means 129 that the minimum block size is determined automatically depending on 130 the number of elements in the range divided by the number of 131 available cores. */ 132 ); 133 134 #else // DOXYGEN 135 136 /** 137 * Overload of above described Doxygen dummy. 138 */ 139 template<typename RAI, typename ValueType> 140 typename std::iterator_traits<RAI>::difference_type Count( 141 RAI first, 142 RAI last, 143 const ValueType& value, 144 const embb::mtapi::ExecutionPolicy& policy, 145 size_t block_size 146 ); 147 148 /** 149 * Overload of above described Doxygen dummy with less arguments. 150 */ 151 template<typename RAI, typename ValueType> 152 typename std::iterator_traits<RAI>::difference_type Count( 153 RAI first, 154 RAI last, 155 const ValueType& value 156 ) { 157 return Count(first, last, value, embb::mtapi::ExecutionPolicy(), 0); 158 } 159 160 /** 161 * Overload of above described Doxygen dummy with less arguments. 162 */ 163 template<typename RAI, typename ValueType> 164 typename std::iterator_traits<RAI>::difference_type Count( 165 RAI first, 166 RAI last, 167 const ValueType& value, 168 const embb::mtapi::ExecutionPolicy& policy 169 ) { 170 return Count(first, last, value, policy, 0); 171 } 172 173 /** 174 * Overload of above described Doxygen dummy. 175 */ 176 template<typename RAI> 177 typename std::iterator_traits<RAI>::difference_type CountIf( 178 RAI first, 179 RAI last, 180 embb::mtapi::Job comparison, 181 const embb::mtapi::ExecutionPolicy& policy, 182 size_t block_size 183 ); 184 185 /** 186 * Overload of above described Doxygen dummy. 187 */ 188 template<typename RAI, typename ComparisonFunction> 189 typename std::iterator_traits<RAI>::difference_type CountIf( 190 RAI first, 191 RAI last, 192 ComparisonFunction comparison, 193 const embb::mtapi::ExecutionPolicy& policy, 194 size_t block_size 195 ); 196 197 /** 198 * Overload of above described Doxygen dummy with less arguments. 199 */ 200 template<typename RAI, typename ComparisonFunction> 201 typename std::iterator_traits<RAI>::difference_type CountIf( 202 RAI first, 203 RAI last, 204 ComparisonFunction comparison 205 ) { 206 return CountIf(first, last, comparison, embb::mtapi::ExecutionPolicy(), 0); 207 } 208 209 /** 210 * Overload of above described Doxygen dummy with less arguments. 211 */ 212 template<typename RAI, typename ComparisonFunction> 213 typename std::iterator_traits<RAI>::difference_type CountIf( 214 RAI first, 215 RAI last, 216 ComparisonFunction comparison, 217 const embb::mtapi::ExecutionPolicy& policy 218 ) { 219 return CountIf(first, last, comparison, policy, 0); 220 } 221 222 #endif // else DOXYGEN 223 224 /** 225 * \} 226 */ 227 228 } // namespace algorithms 229 } // namespace embb 230 231 #include <embb/algorithms/internal/count-inl.h> 232 233 #endif // EMBB_ALGORITHMS_COUNT_H_ 234