1 /* reducer_min_max.h -*- C++ -*-
3 * Copyright (C) 2009-2016, Intel Corporation
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
16 * * Neither the name of Intel Corporation nor the names of its
17 * contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
27 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
30 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
33 * *********************************************************************
35 * PLEASE NOTE: This file is a downstream copy of a file mainitained in
36 * a repository at cilkplus.org. Changes made to this file that are not
37 * submitted through the contribution process detailed at
38 * http://www.cilkplus.org/submit-cilk-contribution will be lost the next
39 * time that a new version is released. Changes only submitted to the
40 * GNU compiler collection or posted to the git repository at
41 * https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are
44 * We welcome your contributions to this open source project. Thank you
45 * for your assistance in helping us improve Cilk Plus.
48 /** @file reducer_min_max.h
50 * @brief Defines classes for doing parallel minimum and maximum reductions.
52 * @ingroup ReducersMinMax
57 #ifndef REDUCER_MIN_MAX_H_INCLUDED
58 #define REDUCER_MIN_MAX_H_INCLUDED
60 #include <cilk/reducer.h>
67 /** @defgroup ReducersMinMax Minimum and Maximum Reducers
69 * Minimum and maximum reducers allow the computation of the minimum or
70 * maximum of a set of values in parallel.
74 * You should be familiar with @ref pagereducers "Intel(R) Cilk(TM) Plus reducers",
75 * described in file `reducers.md`, and particularly with @ref reducers_using,
76 * before trying to use the information in this file.
78 * @section redminmax_usage Usage Examples
80 * cilk::reducer< cilk::op_max<int> > rm;
81 * cilk_for (int i = 0; i < ARRAY_SIZE; ++i)
83 * rm->calc_max(a[i]); // or *rm = cilk::max_of(*max, a[i])
85 * std::cout << "maximum value is " << rm.get_value() << std::endl;
89 * cilk::reducer< cilk::op_min_index<int, double> > rmi;
90 * cilk_for (int i = 0; i < ARRAY_SIZE; ++i)
92 * rmi->calc_min(i, a[i]) // or *rmi = cilk::min_of(*rmi, i, a[i]);
94 * std::cout << "minimum value a[" << rmi.get_value().first << "] = "
95 * << rmi.get_value().second << std::endl;
97 * @section redminmax_monoid The Monoid
99 * @subsection redminmax_monoid_values Value Set
101 * The value set of a minimum or maximum reducer is the set of values of
102 * `Type`, augmented with a "special identity value" which is not a value of
103 * `Type`, but which is defined to be greater than (less than) any value of
106 * @subsection redminmax_monoid_operator Operator
108 * By default, the operator of a minimum reducer is defined as
110 * x MIN y == (x < y) ? x : y
112 * Thus, `a1 MIN a2 MIN … an` is the first `ai` which is not greater than any
115 * The operator of a maximum reducer is defined as
117 * x MAX y == (x > y) ? x : y
119 * Thus, `a1 MAX a2 MAX … an` is the first `ai` which is not less than any
122 * @subsection redminmax_monoid_comparators Comparators
124 * Min/max reducers are not limited to finding the minimum or maximum value
125 * determined by the `<` or `>` operator. In fact, all min/max reducers use a
126 * _comparator_, which is either a function or an object of a function class
127 * that defines a [strict weak ordering]
128 * (http://en.wikipedia.org/wiki/Strict_weak_ordering#Strict_weak_orderings)
129 * on a set of values. (This is exactly the same as the requirement for the
130 * comparison predicate for STL associative containers and sorting
133 * Just as with STL algorithms and containers, the comparator type parameter
134 * for min/max reducers is optional. If it is omitted, it defaults to
135 * `std::less`, which gives the behavior described in the previous section.
136 * Using non-default comparators (anything other than `std::less`) with
137 * min/max reducers is just like using them with STL containers and
140 * Taking comparator objects into account, the reduction operation `MIN` for a
141 * minimum reducer is defined as
143 * x MIN y == compare(x, y) ? x : y
145 * where `compare()` is the reducer's comparator. Similarly, the reduction
146 * operation MAX for a maximum reducer is defined as
148 * x MAX y == compare(y, x) ? x : y
150 * (If `compare(x, y) == x < y`, then `compare(y, x) == x > y`.)
152 * @subsection redminmax_monoid_identity Identity
154 * The identity value of a min/max reducer is its monoid's
155 * ["special identity value"](#redminmax_monoid_values), which is not a value
156 * of the reducer's data type. (See @ref redminmax_initial.)
158 * @section redminmax_index Value and Index Reducers
160 * Min/max reducers come in two families. The _value_ reducers, with the
161 * `op_min` and `op_max` monoids, simply find the smallest or largest value
162 * from a set of values. The _index_ reducers, with the `op_min_index` and
163 * `op_max_index` monoids, also record an index value associated with the
164 * first occurrence of the smallest or largest value.
166 * In the `%op_min_index` usage example [above](#redminmax_usage), the values
167 * are taken from an array, and the index of a value is the index of the array
168 * element it comes from. More generally, though, an index can be any sort of
169 * key which identifies a particular value in a collection of values. For
170 * example, if the values were taken from the nodes of a tree, then the
171 * "index" of a value might be a pointer to the node containing that value.
173 * A min/max index reducer is essentially the same as a min/max value reducer
174 * whose value type is an (index, value) pair, and whose comparator ignores
175 * the index part of the pair. (index, value) pairs are represented by
176 * `std::pair<Index, Type>` objects. This has the consequence that wherever
177 * the interface of a min/max value reducer has a `Type`, the interface of a
178 * min/max index reducer has a `std::pair<Index, Type>`. (There are
179 * convenience variants of the `reducer(Type)` constructor and the
180 * `calc_min()`, `calc_max()`, `%min_of()`, and `%max_of()` functions that
181 * take an index argument and a value argument instead of a single index/value
184 * @section redminmax_operations Operations
186 * @subsection redminmax_constructors Constructors
188 * @subsubsection redminmax_constructors_value Min/Max Value Reducers
190 * reducer() // identity
191 * reducer(const Compare& compare) // identity
192 * reducer(const Type& value)
193 * reducer(move_in(Type& variable))
194 * reducer(const Type& value, const Compare& compare)
195 * reducer(move_in(Type& variable), const Compare& compare)
197 * @subsubsection redminmax_constructors_index Min/Max Index Reducers
199 * reducer() // identity
200 * reducer(const Compare& compare) // identity
201 * reducer(const std::pair<Index, Type>& pair)
202 * reducer(const Index& index, const Type& value)
203 * reducer(move_in(std::pair<Index, Type>& variable))
204 * reducer(const std::pair<Index, Type>& pair, const Compare& compare)
205 * reducer(const Index& index, const Type& value, const Compare& compare)
206 * reducer(move_in(std::pair<Index, Type>& variable), const Compare& compare)
208 * See the explanation of the following two constructors in
209 * @ref redminmax_index_vector.
211 * reducer(const Index& index)
212 * reducer(const Index& index, const Compare& compare)
214 * @subsection redminmax_get_set Set and Get
216 * r.set_value(const Type& value)
217 * Type = r.get_value() const
218 * r.move_in(Type& variable)
219 * r.move_out(Type& variable)
221 * Note that for an index reducer, the `Type` in these operations is actually a
222 * `std::pair<Index, Type>`. (See @ref redminmax_index.) There is _not_ a
223 * `set_value(value, index)` operation.
225 * @subsection redminmax_initial Initial Values and is_set()
227 * The initial value of the leftmost view of a default-initialized min/max
228 * reducer, or of a non-leftmost view (created for a stolen parallel strand)
229 * is the special identity value, which is not a value of the reducer's value
232 * A view will have a real (non-identity) value if:
234 * - it is the leftmost view of a reducer that was constructed with an
236 * - it was assigned a value with a call to `reducer.set_value()` or
237 * `reducer.move_in()`, or
238 * - it has been updated with a call to `reducer->calc_min()` or
239 * `reducer->calc_max()`, or
240 * - it has been updated with an assignment `*reducer = min_of(*reducer, x)`
241 * or `*reducer = max_of(*reducer, x)`.
243 * Calling `get_value()` or `move_out()` on a reducer whose view has the
244 * special identity value will yield an undefined result. The `is_set()`
245 * function can be used to test whether a view has the special identity value
246 * or a real value. If a reducer's current view has the special identity
247 * value, then `reducer()->is_set()` will return `false` (and
248 * `reducer.get_value()` will return an undefined value); if the view has a
249 * real value, them `reducer->is_set()` will return `true` and
250 * `reducer.get_value()` will return the value.
252 * @subsubsection redminmax_index_vector Special Issues with Min/Max Index Reducers
254 * The index portion of the computed index/value pair will be wrong in the
255 * following special case:
257 * - The reducer's value type is a simple numeric type.
258 * - The reducer uses the default comparator (`std::less<Type>`).
259 * - The reducer is updated at least once with a call to `calc_min()` or
260 * `calc_max()` or an assignment with `min_of()` or `max_of()`.
261 * - The value in _every_ update to the reducer is the maximum value of the
262 * value type (for a min_index reducer) or the minimum value of the value
263 * type (for a max_index reducer).
265 * In this case, `reducer.get_value().first` should be the index argument from
266 * the first reducer update, but it will actually be the default value of the
267 * `Index` type. Now, in the common case where the index type is an integer
268 * type and the reducer is finding the smallest or largest element in an
269 * array, the default value of the index type will be zero, which is the
270 * index of the first element in the array, so everything will work out:
272 * unsigned a[3] = {0, 0, 0};
273 * reducer< op_max_index<int, unsigned> > r;
274 * for (int i = 0; i < 3; ++i) r->calc_max(i, a[i]);
275 * // r.get_value() = (0, 0)
277 * However, it doesn't always work out so well:
279 * typedef std::map<std::string, unsigned> my_map;
284 * reducer< op_max_index<std::string, unsigned> > r;
285 * for (typename my_map::iterator i = a.begin(); i != a.end(); ++i)
286 * r.calc_max(i->first, i->second);
287 * // r.get_value() = ("", 0), should be ("first", 0)
289 * If you know that no data value is associated with the default index value,
290 * then you can treat the default index value as a flag meaning "use the index
291 * of the first data value." But suppose that you don't know whether there is
292 * an element in the map with index `""`. Then you won't know what to do when
293 * `r.get_value().first == ""`.
295 * As a workaround for this conundrum, you can specify an alternative
296 * "default" index value. Either provide an index argument, _but not a
297 * value argument_, to the reducer constructor:
299 * reducer< op_max_index<std::string, unsigned> >
300 * r(a.empty() ? std::string() : a.begin()->first);
302 * or specify the default index with the view `set_default_index()` function:
304 * reducer< op_max_index<std::string, unsigned> > r;
305 * if (!a.empty()) r->set_default_index(a.begin()->first);
307 * Note that setting a default index, unlike setting an initial value, does
308 * not mark the view as having a non-identity value:
310 * reducer< op_min_index<int, int> > r;
311 * r->set_default_index(-1);
312 * // r->is_set() = false
313 * // r.get_value() is undefined
315 * @subsection redminmax_view_ops View Operations
317 * The basic reduction operation is `x = x MIN a` for a minimum reducer, or
318 * `x = x MAX a` for a maximum reducer. The basic syntax for these operations
319 * uses the `calc_min()` and `calc_max()` member functions of the view class.
320 * An assignment syntax is also provided, using the `%cilk::min_of()` and
321 * `%cilk::max_of()` global functions:
323 * Class | Modifier | Assignment
324 * ---------------|---------------------|-----------
325 * `op_min` | `r->calc_min(x)` | `*r = min_of(*r, x)` or `*r = min_of(x, *r)`
326 * `op_max` | `r->calc_max(x)` | `*r = max_of(*r, x)` or `*r = max_of(x, *r)`
327 * `op_min_index` | `r->calc_min(i, x)` | `*r = min_of(*r, i, x)` or `*r = min_of(i, x, *r)`
328 * `op_max_index` | `r->calc_max(i, x)` | `*r = max_of(*r, i, x)` or `*r = max_of(i, x, *r)`
330 * Wherever an "`i`, `x`" argument pair is shown in the table above, a single
331 * pair argument may be passed instead. For example:
335 * std::pair<Index, Type> ind_val(index, value);
336 * // The following statements are all equivalent.
337 * r->calc_min(index, value);
338 * r->calc_min(ind_val);
339 * *r = min_of(*r, index, value);
340 * *r = min_of(*r, ind_val);
342 * The `calc_min()` and `calc_max()` member functions return a reference to
343 * the view, so they can be chained:
345 * r->calc_max(x).calc_max(y).calc_max(z);
347 * In a `%min_of()` or `%max_of()` assignment, the view on the left-hand side
348 * of the assignment must be the same as the view argument in the call.
349 * Otherwise, the behavior is undefined (but an assertion error will occur if
350 * the code is compiled with debugging enabled).
352 * *r = max_of(*r, x); // OK
353 * *r1 = max_of(*r2, y); // ERROR
355 * `%min_of()` and `%max_of()` calls can be nested:
357 * *r = max_of(max_of(max_of(*r, x), y), z);
358 * *r = min_of(i, a[i], min_of(j, a[j], min_of(k, a[k], *r)));
360 * @section redminmax_compatibility Binary Compatibility Issues
362 * Most Intel Cilk Plus library reducers provide binary compatibility between
363 * `reducer_KIND` reducers compiled with Intel Cilk Plus library version 0.9
364 * (distributed with Intel® C++ Composer XE version 13.0 and earlier) and the
365 * ame reducers compiled with Intel Cilk Plus library version 1.0 and later.
367 * Because of implementation changes that were needed to allow vectorization
368 * of loops containing min/max reducers, this binary compatibility is _not_
369 * generally available for min/max reducers, either between Intel Cilk Plus library
370 * versions 0.9 and 1.0, or between versions 1.0 and 1.1. (Code compiled with
371 * different versions can be linked together safely, but min/max reducers in
372 * different library versions are in different namespaces, so reducer objects
373 * cannot be shared between them.)
375 * If this is an inconvenience, the simplest solution is just to recompile any
376 * existing code you may have that uses min/max reducers. If that is
377 * impossible, you can define the `CILK_LIBRARY_0_9_REDUCER_MINMAX` macro (on
378 * the compiler command line, or in your source code before including
379 * `reducer_min_max.h`) when compiling with the new library. This will cause
380 * it to generate numeric reducers that will be link-time and run-time
381 * compatible with the 0.9 library.
383 * @subsection redminmax_compatibility_stateful Non-empty Comparators
385 * The representation of min/max reducers with non-empty comparator objects or
386 * with comparator functions is so different in between the 0.9 and 1.1
387 * libraries that there is no way to make them binary compatible, even when
388 * compiling with `CILK_LIBRARY_0_9_REDUCER_MINMAX`. Therefore, the
389 * `reducer_{min|max}[_index]` wrapper classes have been coded in the 1.0 and
390 * later library so that they will not even compile when instantiated with a
391 * non-empty comparator class.
393 * This is not a problem when using an empty comparator class, such as the
394 * default `std::less`.
396 * @section redminmax_types Type Requirements
398 * `Type` and `Index` must be `Copy Constructible`, `Default Constructible`,
401 * `Compare` must be `Copy Constructible` if the reducer is constructed with a
402 * `compare` argument, and `Default Constructible` otherwise.
404 * The `Compare` function must induce a strict weak ordering on the elements
407 * @section redminmax_in_c Minimum and Maximum Reducers in C
409 * These macros can be used to do minimum and maximum reductions in C:
411 * Declaration | Type | Operation
412 * -----------------------------|-----------------------------------|----------
413 * @ref CILK_C_REDUCER_MIN |@ref CILK_C_REDUCER_MIN_TYPE |@ref CILK_C_REDUCER_MIN_CALC
414 * @ref CILK_C_REDUCER_MAX |@ref CILK_C_REDUCER_MAX_TYPE |@ref CILK_C_REDUCER_MAX_CALC
415 * @ref CILK_C_REDUCER_MIN_INDEX |@ref CILK_C_REDUCER_MIN_INDEX_TYPE |@ref CILK_C_REDUCER_MIN_INDEX_CALC
416 * @ref CILK_C_REDUCER_MAX_INDEX |@ref CILK_C_REDUCER_MAX_INDEX_TYPE |@ref CILK_C_REDUCER_MAX_INDEX_CALC
420 * CILK_C_REDUCER_MIN(r, int, INT_MAX);
421 * CILK_C_REGISTER_REDUCER(r);
422 * cilk_for(int i = 0; i != n; ++i) {
423 * CILK_C_REDUCER_MIN_CALC(r, a[i]);
425 * CILK_C_UNREGISTER_REDUCER(r);
426 * printf("The smallest value in a is %d\n", REDUCER_VIEW(r));
429 * CILK_C_REDUCER_MAX_INDEX(r, uint, 0);
430 * CILK_C_REGISTER_REDUCER(r);
431 * cilk_for(int i = 0; i != n; ++i) {
432 * CILK_C_REDUCER_MAX_INDEX_CALC(r, i, a[i]);
434 * CILK_C_UNREGISTER_REDUCER(r);
435 * printf("The largest value in a is %u at %d\n",
436 * REDUCER_VIEW (r).value, REDUCER_VIEW(r).index);
438 * See @ref reducers_c_predefined.
443 /** @defgroup ReducersMinMaxBinComp Binary compatibility
445 * If the macro `CILK_LIBRARY_0_9_REDUCER_MINMAX` is defined, then we generate
446 * reducer code and data structures which are binary-compatible with code that
447 * was compiled with the old min/max wrapper definitions, so we want the
448 * mangled names of the legacy min/max reducer wrapper classes to be the
449 * same as the names produced by the old definitions.
451 * Conversely, if the macro is not defined, then we generate binary-
452 * incompatible code, so we want different mangled names, to make sure that
453 * the linker does not allow new and old compiled legacy wrappers to be passed
454 * to one another. (Global variables are a different, and probably insoluble,
457 * Similarly, min/max classes compiled with and without
458 * CILK_LIBRARY_0_9_REDUCER_MINMAX are binary-incompatible, and must get
459 * different mangled names.
461 * The trick is, when compiling in normal (non-compatibility) mode, wrap
462 * everything in an extra namespace, and then `use` it into the top-level cilk
465 * * Classes and functions compiled in normal mode will be in
466 * different namespaces from the same classes and functions compiled in
467 * compatibility mode.
468 * * The legacy wrapper classes and functions will be in the same namespace
469 * as the same classes and functions compiled with the 0.9 library if and
470 * only if they are compiled in compatibility mode.
472 * @ingroup ReducersMinMax
475 #ifndef CILK_LIBRARY_0_9_REDUCER_MINMAX
476 /** Namespace to wrap min/max reducer definitions when not compiling in "binary
477 * compatibility" mode.
479 * By default, all of the min/max reducer definitions are defined in this
480 * namespace and then imported into namespace ::cilk, so that they do not
481 * clash with the legacy definitions with the same names. However, if the
482 * macro `CILK_LIBRARY_0_9_REDUCER_MINMAX` is defined, then the min/max
483 * definitions go directly into namespace ::cilk, so that, for example,
484 * cilk::reducer_max defined with the 1.0 library is equivalent (to the
485 * linker) to cilk::reducer_max defined with the 0.9 library.
487 * @ingroup ReducersMinMaxBinComp
488 * @ingroup ReducersMinMax
490 namespace cilk_lib_1_1
{
493 /** Namespace containing internal implementation classes and functions for
496 * @ingroup ReducersMinMax
498 namespace min_max_internal
{
500 using ::cilk::internal::binary_functor
;
501 using ::cilk::internal::typed_indirect_binary_function
;
502 using ::cilk::internal::class_is_empty
;
504 /** @defgroup ReducersMinMaxIsSet The "is_set optimization"
506 * The obvious definition of the identity value for a max or min reducer is as
507 * the smallest (or largest) value of the value type. However, for an
508 * arbitrary comparator and/or an arbitrary value type, the largest / smallest
509 * value may not be known. It may not even be defined - what is the largest
512 * Therefore, min/max reducers represent their value internally as a pair
513 * `(value, is_set)`. When `is_set` is true, the pair represents the known
514 * value `value`; when `is_set` is false, the pair represents the identity
517 * This is an effective solution, but the most common use of min/max reducers
518 * is probably with numeric types and the default definition of minimum or
519 * maximum (using `std::less`), in which case there are well-defined, knowable
520 * smallest and largest values. Testing `is_set` for every comparison is then
521 * unnecessary and wasteful.
523 * The "is_set optimization" just means generating code that doesn't use
524 * `is_set` when it isn't needed. It is implemented using two metaprogramming
527 * - do_is_set_optimization tests whether the optimization is applicable.
528 * - identity_value gets the appropriate identity value for a type.
530 * The is_set optimization is the reason that min/max reducers compiled with
531 * Intel Cilk Plus library 1.0 are binary-incompatible with the same reducers
532 * compiled with library 0.9, and therefore the optimization is suppressed when
534 * ReducersMinMaxBinComp "binary compatibility mode".
536 * @ingroup ReducersMinMax
539 /** Tests whether the ReducersMinMaxIsSet "is_set optimization" is
542 * The @ref do_is_set_optimization class is used to test whether the is_set
543 * optimization should be applied for a particular reducer. It is instantiated
544 * with a value type and a comparator, and defines a boolean constant,
545 * `value`. Then `%do_is_set_optimization<Type, Comp>::%value` can be used as
546 * a boolean template parameter to control the specialization of another
549 * In ReducersMinMaxBinComp "binary compatibility mode" (i.e., when the
550 * `CILK_LIBRARY_0_9_REDUCER_MINMAX` macro is defined), `value` will always
553 * @tparam Type The value type for the reducer.
554 * @tparam Compare The comparator type for the reducer.
556 * @result The `value` data member will be `true` if @a Type is a numeric
557 * type, @a Compare is `std::less<Type>`, and
558 * `CILK_LIBRARY_0_9_REDUCER_MINMAX` is not defined.
560 * @see ReducersMinMaxIsSet
561 * @see @ref view_content
563 * @ingroup ReducersMinMaxIsSet
565 template < typename Type
,
567 struct do_is_set_optimization
569 /// `True` if the is_set optimization should be applied to min/max reducers
570 /// with this value type and comparator; `false` otherwise.
571 static const bool value
= false;
574 #ifndef CILK_LIBRARY_0_9_REDUCER_MINMAX
576 template <typename Type
>
577 struct do_is_set_optimization
<Type
, std::less
<Type
> >
579 /// True in the special case where optimization is possible.
580 static const bool value
= std::numeric_limits
<Type
>::is_specialized
;
586 /** Gets the identity value when using the ReducersMinMaxIsSet
587 * "is_set optimization".
589 * This class defines a function which assigns the appropriate identity value
590 * to a variable when the is_set optimization is applicable.
592 * @tparam Type The value type for the reducer.
593 * @tparam Compare The comparator type for the reducer.
594 * @tparam ForMax `true` to get the identity value for a max reducer (i.e.,
595 * the smallest value of @a Type), `false` to get the identity
596 * value for a min reducer (i.e., the largest value of
599 * @result If @a Type and @a Compare qualify for the is_set optimization, the
600 * `set_identity()' function will set its argument variable to the
601 * smallest or largest value of @a Type, depending on @a ForMax.
602 * Otherwise, `set_identity()` will be a no-op.
604 * @see ReducersMinMaxIsSet
606 * @ingroup ReducersMinMaxIsSet
607 * @see @ref view_content
609 template < typename Type
,
612 bool = std::numeric_limits
<Type
>::is_specialized
,
613 bool = std::numeric_limits
<Type
>::has_infinity
>
614 struct identity_value
{
615 /// Assign the identity value to the reference parameter.
616 static void set_identity(Type
&) {}
620 template <typename Type
>
621 struct identity_value
<Type
, std::less
<Type
>, true, true, true> {
622 /// Floating max identity is negative infinity.
623 static void set_identity(Type
& id
)
624 { id
= -std::numeric_limits
<Type
>::infinity(); }
627 template <typename Type
>
628 struct identity_value
<Type
, std::less
<Type
>, true, true, false> {
629 /// Integer max identity is minimum value of type.
630 static void set_identity(Type
& id
)
631 { id
= std::numeric_limits
<Type
>::min(); }
634 template <typename Type
>
635 struct identity_value
<Type
, std::less
<Type
>, false, true, true> {
636 /// Floating min identity is positive infinity.
637 static void set_identity(Type
& id
)
638 { id
= std::numeric_limits
<Type
>::infinity(); }
641 template <typename Type
>
642 struct identity_value
<Type
, std::less
<Type
>, false, true, false> {
643 /// Integer min identity is maximum value of type.
644 static void set_identity(Type
& id
)
645 { id
= std::numeric_limits
<Type
>::max(); }
651 /** Adapter class to reverse the arguments of a predicate.
656 * max(x, y) == (x < y) ? y : x
657 * min(x, y) == (y < x) ? y : x == (x > y) ? y : x
659 * More generally, if `c` is a predicate defining a `Strict Weak Ordering`,
660 * and `c*(x, y) == c(y, x)`, then
662 * max(x, y, c) == c(x, y) ? y : x
663 * min(x, y, c) == c(y, x) ? y : x == c*(x, y) ? y : x == max(x, y, c*)
665 * For any predicate `C` with argument type `T`, the template class
666 * `%reverse_predicate<C, T>` defines a predicate which is identical to `C`,
667 * except that its arguments are reversed. Thus, for example, we could
668 * implement `%op_min_view<Type, Compare>` as
669 * `%op_max_view<Type, %reverse_predicate<Compare, Type> >`.
670 * (Actually, op_min_view and op_max_view are both implemented as subclasses
671 * of a common base class, view_base.)
673 * @note If `C` is an empty functor class, then `reverse_predicate(C)` will
674 * also be an empty functor class.
676 * @tparam Predicate The predicate whose arguments are to be reversed.
677 * @tparam Argument @a Predicate's argument type.
679 * @ingroup ReducersMinMax
681 template <typename Predicate
,
682 typename Argument
= typename
Predicate::first_argument_type
>
683 class reverse_predicate
: private binary_functor
<Predicate
>::type
{
684 typedef typename binary_functor
<Predicate
>::type base
;
686 /// Default constructor
687 reverse_predicate() : base() {}
688 /// Constructor with predicate object
689 reverse_predicate(const Predicate
& p
) : base(p
) {}
690 /// The reversed predicate operation
691 bool operator()(const Argument
& x
, const Argument
& y
) const
692 { return base::operator()(y
, x
); }
696 /** Class to represent the comparator for a min/max view class.
698 * This class is intended to accomplish two objectives in the implementation
701 * 1. To minimize data bloat, when we have a reducer with a non-stateless
702 * comparator, we want to keep a single instance of the comparator object
703 * in the monoid, and just call it from the views.
704 * 2. In ReducersMinMaxBinComp "binary compatibility mode", views for
705 * reducers with a stateless comparator must have the same content as in
706 * Intel Cilk Plus library 0.9 - that is, they must contain only `value` and
707 * `is_set` data members.
709 * To achieve the first objective, we use the
710 * @ref internal::typed_indirect_binary_function class defined in
711 * metaprogramming.h to wrap a pointer to the actual comparator. If no
712 * pointer is needed because the actual comparator is stateless, the
713 * `typed_indirect_binary_function` class will be empty, too.
715 * To achieve the second objective, we make the
716 * `typed_indirect_binary_function` class a base class of the view rather than
717 * a data member, so the "empty base class" rule will ensure no that no
718 * additional space is allocated in the view unless it is needed.
720 * We could simply use typed_indirect_binary_function as the base class of the
721 * view, but this would mean writing comparisons as `(*this)(x, y)`, which is
722 * just weird. So, instead, we comparator_base as a subclass of
723 * typed_indirect_binary_function which provides function `compare()`
724 * as a synonym for `operator()`.
726 * @tparam Type The value type of the comparator class.
727 * @tparam Compare A predicate class.
729 * @see internal::typed_indirect_binary_function
731 * @ingroup ReducersMinMax
733 template <typename Type
, typename Compare
>
734 class comparator_base
: private typed_indirect_binary_function
<Compare
, Type
, Type
, bool>
736 typedef typed_indirect_binary_function
<Compare
, Type
, Type
, bool> base
;
738 comparator_base(const Compare
* f
) : base(f
) {} ///< Constructor.
740 /// Comparison function.
741 bool compare(const Type
& a
, const Type
& b
) const
743 return base::operator()(a
, b
);
746 /// Get the comparator pointer.
747 const Compare
* compare_pointer() const { return base::pointer(); }
751 /** @defgroup ReducersMinMaxViewContent Content classes for min/max views
753 * @ingroup ReducersMinMax
755 * Minimum and maximum reducer view classes inherit from a "view content"
756 * class. The content class defines the actual data members for the view,
757 * and provides typedefs and member functions for accessing the data members
758 * as needed to support the view functionality.
760 * There are two content classes, which encapsulate the differences between
761 * simple min/max reducers and min/max with index reducers:
764 * - index_view_content
766 * @note An obvious, and arguably simpler, encapsulation strategy would be
767 * to just let the `Type` of a min/max view be an (index, value) pair
768 * structure for min_index and max_index reducers. Then all views
769 * would just have a `Type` data member and an `is_set` data member,
770 * and the comparator for min_index and max_index views could be
771 * customized to consider only the value component of the (index,
772 * value) `Type` pair. Unfortunately, this would break binary
773 * compatibility with reducer_max_index and reducer_min_index in
774 * Intel Cilk Plus library 0.9, because the memory layout of an
775 * (index, value) pair followed by a `bool` is different from the
776 * memory layout of an index data member followed by a value data
777 * member followed by a `bool` data member. The content class is
778 * designed to exactly replicate the layout of the views in library 0.9
781 * A content class `C`, and its objects `c`, must define the following:
783 * Definition | Meaning
784 * ------------------------------------|--------
785 * `C::value_type` | A typedef for `Type` of the view. (A `std::pair<Index, Type>` for min_index and max_index views).
786 * `C::comp_value_type` | A typedef for the type of value compared by the view's `compare()` function.
787 * `C()` | Constructs the content with the identity value.
788 * `C(const value_type&)` | Constructs the content with a specified value.
789 * `c.is_set()` | Returns true if the content has a known value.
790 * `c.value()` | Returns the content's value.
791 * `c.set_value(const value_type&)` | Sets the content's value. (The value becomes known.)
792 * `c.comp_value()` | Returns a const reference to the value or component of the value that is to be compared by the view's comparator.
793 * `C::comp_value(const value_type&)` | Returns a const reference to a value or component of a value that is to be compared by the view's comparator.
798 /** Content class for op_min_view and op_max_view.
800 * @tparam Type The value type of the op_min_view or op_max_view.
801 * @tparam Compare The comparator class specified for the op_min_view or
802 * op_max_view. (_Not_ the derived comparator class actually
803 * used by the view_base. For example, the view_content of an
804 * `op_min_view<int>` will have `Compare = std::less<int>`,
805 * but its comparator_base will have
806 * `Compare = reverse_predicate< std::less<int> >`.)
807 * @tparam ForMax `true` if this is the content class for an op_max_view,
808 * `false` if it is for an op_min_view.
810 * @note The general implementation of view_content uses an `is_set` data
811 * member. There is also a specialization which implements the
812 * ReducersMinMaxIsSet "is_set optimization". View classes that
813 * inherit from view_content do not need to know anything about the
814 * difference, though; the details are abstracted away in the
815 * view_content interface.
817 * @see ReducersMinMaxViewContent
819 * @ingroup ReducersMinMaxViewContent
820 * @ingroup ReducersMinMax
822 template < typename Type
825 , bool = do_is_set_optimization
<Type
, Compare
>::value
834 /// The value type of the view.
835 typedef Type value_type
;
837 /// The type compared by the view's `compare()` function (which is the same
838 /// as the value type for view_content).
839 typedef Type comp_value_type
;
841 /// Construct with the identity value.
842 view_content() : m_value(), m_is_set(false) {}
844 /// Construct with a defined value.
845 view_content(const value_type
& value
) : m_value(value
), m_is_set(true) {}
848 value_type
value() const { return m_value
; }
851 void set_value(const value_type
& value
)
856 /// Sets the is_set flag.
862 /// Sets the index part of the value (which is meaningless for non-index
863 ///reducers, but required for view_base).
864 void set_default_index(const value_type
&) {}
866 /// Gets the comparison value (which, for view_content, is the same as the
868 const comp_value_type
& comp_value() const { return m_value
; }
870 /// Given an arbitrary value, gets the corresponding comparison value
871 /// (which, for view_content, is the same as the value).
872 static const comp_value_type
& comp_value(const value_type
& value
)
877 /// Gets a const reference to value part of the value (which is the same as
878 /// the value for view_content).
879 const Type
& get_reference() const { return m_value
; }
881 /// Gets a const reference to the index part of the value (which is
882 /// meaningless for non-index reducers, but required for view_base.
883 const Type
& get_index_reference() const { return m_value
; }
885 /// Tests if the value is defined.
886 bool is_set() const { return m_is_set
; }
888 /// Tests if the view has a comparable value.
889 bool has_value() const { return is_set(); }
894 /* This is the specialization of the view_content class for cases where
895 * the is_set optimization is applicable).
897 template < typename Type
901 class view_content
<Type
, Compare
, ForMax
, true> :
902 public view_content
<Type
, Compare
, ForMax
, false>
904 typedef view_content
<Type
, Compare
, ForMax
, false> base
;
905 typedef identity_value
<Type
, Compare
, ForMax
> Identity
;
908 typedef typename
base::value_type value_type
;;
909 typedef typename
base::comp_value_type comp_value_type
;;
911 view_content() : base() { Identity::set_identity(this->m_value
); }
913 view_content(const value_type
& value
) : base(value
) {}
915 bool has_value() const { return true; }
921 /** Content class for op_min_index_view and op_max_index_view.
923 * @tparam Index The index type of the op_min_index_view or
925 * @tparam Type The value type of the op_min_view or op_max_view. (_Not_
926 * the value type of the view, which will be
927 * `std::pair<Index, Type>`.)
928 * @tparam Compare The comparator class specified for the op_min_index_view or
929 * op_max_index_view. (_Not_ the derived comparator class
930 * actually used by the view_base. For example, the
931 * index_view_content of an `op_min_index_view<int>` will have
932 * `Compare = std::less<int>`, but its comparator_base will
933 * have `Compare = reverse_predicate< std::less<int> >`.)
934 * @tparam ForMax `true` if this is the content class for an
935 * op_max_index_view, `false` if it is for an
938 * @see ReducersMinMaxViewContent
940 * @ingroup ReducersMinMaxViewContent
941 * @ingroup ReducersMinMax
943 template < typename Index
947 , bool = do_is_set_optimization
<Type
, Compare
>::value
949 class index_view_content
{
957 /// The value type of the view (which is an <index, value> pair for
958 /// index_view_content).
959 typedef std::pair
<Index
, Type
> value_type
;
961 /// The type compared by the view's `compare()` function (which is the data
962 /// value type for index_view_content).
963 typedef Type comp_value_type
;
965 /// Construct with the identity value.
966 index_view_content() : m_index(), m_value(), m_is_set(false) {}
968 /// Construct with an index/value pair.
969 index_view_content(const value_type
& value
) :
970 m_index(value
.first
), m_value(value
.second
), m_is_set(true) {}
972 /// Construct with an index and a value.
973 index_view_content(const Index
& index
, const Type
& value
) :
974 m_index(index
), m_value(value
), m_is_set(true) {}
976 /// Construct with just an index.
977 index_view_content(const Index
& index
) :
978 m_index(index
), m_value(), m_is_set(false) {}
981 value_type
value() const { return value_type(m_index
, m_value
); }
984 void set_value(const value_type
& value
)
986 m_index
= value
.first
;
987 m_value
= value
.second
;
990 /// Sets the is_set flag.
996 /// Sets the (initial) index, without marking the view as set.
997 void set_default_index(const Index
& index
)
1002 /// Gets the comparison value (which, for index_view_content, is the value
1003 /// component of the index/value pair).
1004 const comp_value_type
& comp_value() const { return m_value
; }
1006 /// Given an arbitrary value (i.e., index/value pair), gets the
1007 /// corresponding comparison value (which, for index_view_content, is the
1008 /// value component of the index/value pair).
1009 static const comp_value_type
& comp_value(const value_type
& value
)
1010 { return value
.second
; }
1012 /// Gets a const reference to the value part of the value.
1013 const Type
& get_reference() const { return m_value
; }
1015 /// Gets a const reference to the index part of the value.
1016 const Index
& get_index_reference() const { return m_index
; }
1018 /// Tests if the value is defined.
1019 bool is_set() const { return m_is_set
; }
1021 /// Tests if the view has a comparable value.
1022 bool has_value() const { return is_set(); }
1028 /* This is the specialization of the index_view_content class for cases where
1029 * the is_set optimization is applicable).
1031 template < typename Index
1036 class index_view_content
<Index
, Type
, Compare
, ForMax
, true> :
1037 public index_view_content
<Index
, Type
, Compare
, ForMax
, false>
1039 typedef index_view_content
<Index
, Type
, Compare
, ForMax
, false> base
;
1040 typedef identity_value
<Type
, Compare
, ForMax
> Identity
;
1042 typedef typename
base::value_type value_type
;;
1043 typedef typename
base::comp_value_type comp_value_type
;;
1045 index_view_content() : base() { Identity::set_identity(this->m_value
); }
1047 index_view_content(const value_type
& value
) : base(value
) {}
1049 index_view_content(const Index
& index
, const Type
& value
) :
1050 base(index
, value
) {}
1052 index_view_content(const Index
& index
) : base() {
1053 Identity::set_identity(this->m_value
);
1054 this->m_index
= index
;
1057 /// Test if the view has a comparable value.
1058 bool has_value() const { return true; }
1064 template <typename View
> class rhs_proxy
;
1066 /** Creates an rhs_proxy.
1068 template <typename View
>
1069 inline rhs_proxy
<View
>
1070 make_proxy(const typename
View::value_type
& value
, const View
& view
);
1072 template <typename Content
, typename Less
, typename Compare
> class view_base
;
1075 /** Class to represent the right-hand side of
1076 * `*reducer = {min|max}_of(*reducer, value)`.
1078 * The only assignment operator for a min/max view class takes a rhs_proxy as
1079 * its operand. This results in the syntactic restriction that the only
1080 * expressions that can be assigned to a min/max view are ones which generate
1081 * an rhs_proxy - that is, expressions of the form `max_of(view, value)` and
1082 * `min_of(view, value)`.
1085 * The lhs and rhs views in such an assignment must be the same; otherwise,
1086 * the behavior will be undefined. (I.e., `*r1 = min_of(*r1, x)` is legal;
1087 * `*r1 = min_of(*r2, x)` is illegal.) This condition will be checked with a
1088 * runtime assertion when compiled in debug mode.
1090 * @tparam View The view class (op_{min|max}[_index]_view) that this proxy
1095 * @ingroup ReducersMinMax
1097 template <typename View
>
1099 typedef typename
View::less_type less_type
;
1100 typedef typename
View::compare_type compare_type
;
1101 typedef typename
View::value_type value_type
;
1102 typedef typename
View::content_type content_type
;
1103 typedef typename
content_type::comp_value_type comp_value_type
;
1105 friend class view_base
<content_type
, less_type
, compare_type
>;
1106 friend rhs_proxy make_proxy
<View
>(
1107 const typename
View::value_type
& value
,
1110 typed_indirect_binary_function
<
1111 compare_type
, comp_value_type
, comp_value_type
, bool>
1116 rhs_proxy
& operator=(const rhs_proxy
&); // Disable assignment operator
1117 rhs_proxy(); // Disable default constructor
1119 // Constructor (called from view_base::make_proxy).
1120 rhs_proxy(const View
* view
,
1121 const value_type
& value
,
1122 const compare_type
* compare
) :
1123 m_view(view
), m_value(value
), m_comp(compare
) {}
1125 // Checks matching view, then return value (called from view_base::assign).
1126 value_type
value(const typename
View::base
* view
) const
1128 __CILKRTS_ASSERT(view
== m_view
);
1134 /** Supports max_of(max_of(view, value), value) and the like.
1136 rhs_proxy
calc(const value_type
& x
) const
1140 m_comp( content_type::comp_value(m_value
),
1141 content_type::comp_value(x
)
1148 template <typename View
>
1149 inline rhs_proxy
<View
>
1150 make_proxy(const typename
View::value_type
& value
, const View
& view
)
1152 return rhs_proxy
<View
>(&view
, value
, view
.compare_pointer());
1157 /** Base class for min and max view classes.
1159 * This class accumulates the minimum or maximum of a set of values which have
1160 * occurred as arguments to the `calc()` function, as determined by a
1161 * comparator. The accumulated value will be the first `calc()` argument value
1162 * `x` such that `compare(x, y)` is false for every `calc()` argument value
1165 * If the comparator is `std::less`, then the accumulated value is the first
1166 * argument value which is not less than any other argument value, i.e., the
1167 * maximum. Similarly, if the comparator is `reverse_predicate<std::less>`,
1168 * which is equivalent to `std::greater`, then the accumulated value is the
1169 * first argument value which is not greater than any other argument value,
1170 * i.e., the minimum.
1172 * @note This class provides the definitions that are required for a class
1173 * that will be used as the parameter of a
1174 * min_max_internal::monoid_base specialization.
1176 * @tparam Content A content class that provides the value types and data
1177 * members for the view.
1178 * @tparam Less A "less than" binary predicate that defines the min or
1180 * @tparam Compare A binary predicate to be used to compare the values.
1181 * (The same as @a Less for max reducers; its reversal for
1184 * @see ReducersMinMaxViewContent
1187 * @see op_max_index_view
1188 * @see op_min_index_view
1191 * @ingroup ReducersMinMax
1193 template <typename Content
, typename Less
, typename Compare
>
1195 // comparator_base comes first to ensure that it will get empty base class
1197 private comparator_base
<typename
Content::comp_value_type
, Compare
>,
1200 typedef comparator_base
<typename
Content::comp_value_type
, Compare
> base
;
1201 using base::compare
;
1202 using Content::value
;
1203 using Content::set_value
;
1204 using Content::has_value
;
1205 using Content::set_is_set
;
1206 using Content::comp_value
;
1207 typedef Content content_type
;
1209 template <typename View
> friend class rhs_proxy
;
1210 template <typename View
>
1211 friend rhs_proxy
<View
> make_proxy(const typename
View::value_type
& value
, const View
& view
);
1215 /** @name Monoid support.
1219 /** Value type. Required by @ref monoid_with_view.
1221 typedef typename
Content::value_type value_type
;
1223 /** The type of the comparator specified by the user, that defines the
1224 * ordering on @a Type. Required by min_max::monoid_base.
1226 typedef Less less_type
;
1228 /** The type of the comparator actually used by the view. Required by
1229 * min_max::monoid_base. (This is the same as the @ref less_type for a
1230 * max reducer, or `reverse_predicate<less_type>` for a min reducer.)
1232 typedef Compare compare_type
;
1234 /** Reduces two views. Required by @ref monoid_with_view.
1236 void reduce(view_base
* other
)
1238 if ( other
->is_set() &&
1239 ( !this->is_set() ||
1240 compare(this->comp_value(), other
->comp_value()) ) )
1242 this->set_value(other
->value());
1249 /** Default constructor. Initializes to identity value.
1251 explicit view_base(const compare_type
* compare
) :
1252 base(compare
), Content() {}
1254 /** Value constructor.
1256 template <typename T1
>
1257 view_base(const T1
& x1
, const compare_type
* compare
) :
1258 base(compare
), Content(x1
) {}
1260 /** Value constructor.
1262 template <typename T1
, typename T2
>
1263 view_base(const T1
& x1
, const T2
& x2
, const compare_type
* compare
) :
1264 base(compare
), Content(x1
, x2
) {}
1267 /** Move-in constructor.
1269 explicit view_base(move_in_wrapper
<value_type
> w
, const compare_type
* compare
) :
1270 base(compare
), Content(w
.value()) {}
1272 /** @name Reducer support.
1276 void view_move_in(value_type
& v
)
1277 { set_value(v
); set_is_set();}
1278 void view_move_out(value_type
& v
)
1280 void view_set_value(const value_type
& v
)
1281 { set_value(v
); set_is_set(); }
1282 value_type
view_get_value() const
1284 // view_get_reference() NOT SUPPORTED
1288 /** Sets the contained index data member, without marking the view as set.
1289 * (Meaningless for non-index reducers.)
1291 using Content::set_default_index
;
1293 /** Is the value defined?
1295 using Content::is_set
;
1297 /** Reference to contained value data member.
1298 * @deprecated For legacy reducers only.
1300 using Content::get_reference
;
1302 /** Reference to contained index data member.
1303 * (Meaningless for non-index reducers.)
1304 * @deprecated For legacy reducers only.
1306 using Content::get_index_reference
;
1310 /** Updates the min/max value.
1312 void calc(const value_type
& x
)
1314 if (!has_value() || compare(comp_value(), comp_value(x
))) set_value(x
);
1318 /** Assigns the result of a `{min|max}_of(view, value)` expression to the
1323 template <typename View
>
1324 void assign(const rhs_proxy
<View
>& rhs
)
1326 calc(rhs
.value(this));
1332 /** Base class for min and max monoid classes.
1334 * The unique characteristic of minimum and maximum reducers is that they
1335 * incorporate a comparator functor that defines what "minimum" or "maximum"
1336 * means. The monoid for a reducer contains the comparator that will be used
1337 * for the reduction. If the comparator is a function or a class with state,
1338 * then each view will have a pointer to the comparator.
1340 * This means that the `construct()` functions first construct the monoid
1341 * (possibly with an explicit comparator argument), and then construct the
1342 * view with a pointer to the monoid's comparator.
1344 * @tparam View The view class.
1345 * @tparam Align If true, reducers instantiated on this monoid will be
1346 * aligned. By default, library reducers (unlike legacy
1347 * library reducer _wrappers_) are unaligned.
1351 * @ingroup ReducersMinMax
1353 template <typename View
, bool Align
= false>
1354 class monoid_base
: public monoid_with_view
<View
, Align
>
1356 typedef typename
View::compare_type compare_type
;
1357 typedef typename
View::less_type less_type
;
1359 const compare_type m_compare
;
1361 const compare_type
* compare_pointer() const { return &m_compare
; }
1365 /** Default constructor uses default comparator.
1367 monoid_base() : m_compare() {}
1371 * @param compare The comparator to use.
1373 monoid_base(const compare_type
& compare
) : m_compare(compare
) {}
1375 /** Creates an identity view.
1377 * List view identity constructors take the list allocator as an argument.
1379 * @param v The address of the uninitialized memory in which the view
1380 * will be constructed.
1382 void identity(View
*v
) const { ::new((void*) v
) View(compare_pointer()); }
1384 /** @name construct functions
1386 * Min/max monoid `construct()` functions optionally take one or two value
1387 * arguments, a @ref move_in argument, and/or a comparator argument.
1391 template <typename Monoid
>
1392 static void construct(Monoid
* monoid
, View
* view
)
1394 provisional_guard
<Monoid
> mg( new((void*) monoid
) Monoid
);
1395 mg
.confirm_if( new((void*) view
) View(monoid
->compare_pointer()) );
1398 template <typename Monoid
, typename T1
>
1399 static void construct(Monoid
* monoid
, View
* view
, const T1
& x1
)
1401 provisional_guard
<Monoid
> mg( new((void*) monoid
) Monoid
);
1402 mg
.confirm_if( new((void*) view
) View(x1
, monoid
->compare_pointer()) );
1405 template <typename Monoid
, typename T1
, typename T2
>
1406 static void construct(Monoid
* monoid
, View
* view
,
1407 const T1
& x1
, const T2
& x2
)
1409 provisional_guard
<Monoid
> mg( new((void*) monoid
) Monoid
);
1410 mg
.confirm_if( new((void*) view
) View(x1
, x2
,
1411 monoid
->compare_pointer()) );
1414 template <typename Monoid
>
1415 static void construct(Monoid
* monoid
, View
* view
, const less_type
& compare
)
1417 provisional_guard
<Monoid
> mg( new((void*) monoid
) Monoid(compare
) );
1418 mg
.confirm_if( new((void*) view
) View(monoid
->compare_pointer()) );
1421 template <typename Monoid
, typename T1
>
1422 static void construct(Monoid
* monoid
, View
* view
, const T1
& x1
,
1423 const less_type
& compare
)
1425 provisional_guard
<Monoid
> mg( new((void*) monoid
) Monoid(compare
) );
1426 mg
.confirm_if( new((void*) view
) View(x1
, monoid
->compare_pointer()) );
1429 template <typename Monoid
, typename T1
, typename T2
>
1430 static void construct(Monoid
* monoid
, View
* view
,
1431 const T1
& x1
, const T2
& x2
, const less_type
& compare
)
1433 provisional_guard
<Monoid
> mg( new((void*) monoid
) Monoid(compare
) );
1434 mg
.confirm_if( new((void*) view
) View(x1
, x2
,
1435 monoid
->compare_pointer()) );
1441 } //namespace min_max_internal
1444 /** @defgroup ReducersMinMaxMaxValue Maximum reducers (value only)
1446 * These reducers will find the largest value from a set of values.
1448 * @ingroup ReducersMinMax
1452 /** The maximum reducer view class.
1454 * This is the view class for reducers created with
1455 * `cilk::reducer< cilk::op_max<Type, Compare> >`. It accumulates the maximum,
1456 * as determined by a comparator, of a set of values which have occurred as
1457 * arguments to the `calc_max()` function. The accumulated value will be the
1458 * first argument `x` such that `compare(x, y)` is false for every argument
1461 * If the comparator is `std::less`, then the accumulated value is the first
1462 * argument value which is not less than any other argument value, i.e., the
1465 * @note The reducer "dereference" operation (`reducer::operator *()`)
1466 * yields a reference to the view. Thus, for example, the view class's
1467 * `calc_max()` function would be used in an expression like
1468 * `r->calc_max(a)` where `r` is an op_max reducer variable.
1470 * @tparam Type The type of the values compared by the reducer. This will
1471 * be the value type of a monoid_with_view that is
1472 * instantiated with this view.
1473 * @tparam Compare A `Strict Weak Ordering` whose argument type is @a Type. It
1474 * defines the "less than" relation used to compute the
1477 * @see ReducersMinMax
1480 template <typename Type
, typename Compare
>
1481 class op_max_view
: public min_max_internal::view_base
<
1482 min_max_internal::view_content
<Type
, Compare
, true>,
1486 typedef min_max_internal::view_base
<
1487 min_max_internal::view_content
<Type
, Compare
, true>,
1492 friend class min_max_internal::rhs_proxy
<op_max_view
>;
1496 /** @name Constructors.
1498 * All op_max_view constructors simply pass their arguments on to the
1499 * @ref view_base base class.
1503 template <typename T1
>
1504 op_max_view(const T1
& x1
) : base(x1
) {}
1506 template <typename T1
, typename T2
>
1507 op_max_view(const T1
& x1
, const T2
& x2
) : base(x1
, x2
) {}
1511 /** @name View modifier operations.
1515 /** Maximizes with a value.
1517 * If @a x is greater than the current value of the view (as defined by
1518 * the reducer's comparator), or if the view was created without an
1519 * initial value and its value has never been updated (with `calc_max()`
1520 * or `= max_of()`), then the value of the view is set to @a x.
1522 * @param x The value to maximize the view's value with.
1524 * @return A reference to the view. (Allows chaining
1525 * `view.comp_max(a).comp_max(b)…`.)
1527 op_max_view
& calc_max(const Type
& x
) { calc(x
); return *this; }
1529 /** Assigns the result of a `max_of(view, value)` expression to the view.
1531 * @param rhs An rhs_proxy value created by a `max_of(view, value)`
1534 * @return A reference to the view.
1536 * @see min_max_internal::view_base::rhs_proxy
1538 op_max_view
& operator=(const min_max_internal::rhs_proxy
<op_max_view
>& rhs
)
1539 { assign(rhs
); return *this; }
1545 /** Computes the maximum of the value in an op_max_view and another value.
1547 * The result of this computation can only be assigned back to the original
1548 * view or used in another max_of() call. For example,
1550 * *reducer = max_of(*reducer, x);
1551 * *reducer = max_of(x, *reducer);
1553 * @see min_max_internal::rhs_proxy
1555 template <typename Type
, typename Compare
>
1556 inline min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >
1557 max_of(const op_max_view
<Type
, Compare
>& view
, const Type
& value
)
1559 return min_max_internal::make_proxy(value
, view
);
1562 /// @copydoc max_of(const op_max_view<Type, Compare>&, const Type&)
1563 template <typename Type
, typename Compare
>
1564 inline min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >
1565 max_of(const Type
& value
, const op_max_view
<Type
, Compare
>& view
)
1567 return min_max_internal::make_proxy(value
, view
);
1570 /** Computes nested maximum.
1572 * Compute the maximum of the result of a max_of() call and another value.
1574 * The result of this computation can only be assigned back to the original
1575 * view or wrapper, or used in another max_of() call. For example,
1577 * *reducer = max_of(x, max_of(y, *reducer));
1578 * wrapper = max_of(max_of(wrapper, x), y);
1580 * @see min_max_internal::rhs_proxy
1582 template <typename Type
, typename Compare
>
1583 inline min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >
1584 max_of(const min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >& proxy
,
1587 return proxy
.calc(value
);
1590 /// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_view<Type, Compare> >&, const Type&)
1591 template <typename Type
, typename Compare
>
1592 inline min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >
1593 max_of(const Type
& value
,
1594 const min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >& proxy
)
1596 return proxy
.calc(value
);
1600 /** Monoid class for maximum reductions. Instantiate the cilk::reducer template
1601 * class with an op_max monoid to create a maximum reducer class. For example,
1602 * to compute the maximum of a set of `int` values:
1604 * cilk::reducer< cilk::op_max<int> > r;
1606 * @see ReducersMinMax
1609 template <typename Type
, typename Compare
=std::less
<Type
>, bool Align
= false>
1611 public min_max_internal::monoid_base
<op_max_view
<Type
, Compare
>, Align
>
1613 typedef min_max_internal::monoid_base
<op_max_view
<Type
, Compare
>, Align
>
1616 /// Construct with default comparator.
1618 /// Construct with specified comparator.
1619 op_max(const Compare
& compare
) : base(compare
) {}
1625 /** @defgroup ReducersMinMaxMinValue Minimum reducers (value only)
1627 * These reducers will find the smallest value from a set of values.
1629 * @ingroup ReducersMinMax
1633 /** The minimum reducer view class.
1635 * This is the view class for reducers created with
1636 * `cilk::reducer< cilk::op_min<Type, Compare> >`. It accumulates the minimum,
1637 * as determined by a comparator, of a set of values which have occurred as
1638 * arguments to the `calc_min()` function. The accumulated value will be the
1639 * first argument `x` such that `compare(y, x)` is false for every argument
1642 * If the comparator is `std::less`, then the accumulated value is the first
1643 * argument value which no other argument value is less than, i.e., the
1646 * @note The reducer "dereference" operation (`reducer::operator *()`)
1647 * yields a reference to the view. Thus, for example, the view class's
1648 * `calc_min()` function would be used in an expression like
1649 * `r->calc_min(a)` where `r` is an op_min reducer variable.
1651 * @tparam Type The type of the values compared by the reducer. This will
1652 * be the value type of a monoid_with_view that is
1653 * instantiated with this view.
1654 * @tparam Compare A `Strict Weak Ordering` whose argument type is @a Type. It
1655 * defines the "less than" relation used to compute the
1658 * @see ReducersMinMax
1661 template <typename Type
, typename Compare
>
1662 class op_min_view
: public min_max_internal::view_base
<
1663 min_max_internal::view_content
<Type
, Compare
, false>,
1665 min_max_internal::reverse_predicate
<Compare
, Type
> >
1667 typedef min_max_internal::view_base
<
1668 min_max_internal::view_content
<Type
, Compare
, false>,
1670 min_max_internal::reverse_predicate
<Compare
, Type
> > base
;
1673 friend class min_max_internal::rhs_proxy
<op_min_view
>;
1676 /** @name Constructors.
1678 * All op_min_view constructors simply pass their arguments on to the
1679 * @ref view_base base class.
1683 template <typename T1
>
1684 op_min_view(const T1
& x1
) : base(x1
) {}
1686 template <typename T1
, typename T2
>
1687 op_min_view(const T1
& x1
, const T2
& x2
) : base(x1
, x2
) {}
1691 /** @name View modifier operations.
1695 /** Minimizes with a value.
1697 * If @a x is less than the current value of the view (as defined by the
1698 * reducer's comparator), or if the view was created without an initial
1699 * value and its value has never been updated (with `calc_min()` or
1700 * `= min_of()`), then the value of the view is set to @a x.
1702 * @param x The value to minimize the view's value with.
1704 * @return A reference to the view. (Allows chaining
1705 * `view.comp_min(a).comp_min(b)…`.)
1707 op_min_view
& calc_min(const Type
& x
) { calc(x
); return *this; }
1709 /** Assigns the result of a `min_of(view, value)` expression to the view.
1711 * @param rhs An rhs_proxy value created by a `min_of(view, value)`
1714 * @return A reference to the view.
1716 * @see min_max_internal::view_base::rhs_proxy
1718 op_min_view
& operator=(const min_max_internal::rhs_proxy
<op_min_view
>& rhs
)
1719 { assign(rhs
); return *this; }
1723 /** Computes the minimum of the value in a view and another value.
1725 * The result of this computation can only be assigned back to the original
1726 * view or used in another min_of() call. For example,
1728 * *reducer = min_of(*reducer, x);
1729 * *reducer = min_of(x, *reducer);
1731 * @see min_max_internal::view_base::rhs_proxy
1733 template <typename Type
, typename Compare
>
1734 inline min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >
1735 min_of(const op_min_view
<Type
, Compare
>& view
, const Type
& value
)
1737 return min_max_internal::make_proxy(value
, view
);
1740 /// @copydoc min_of(const op_min_view<Type, Compare>&, const Type&)
1741 template <typename Type
, typename Compare
>
1742 inline min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >
1743 min_of(const Type
& value
, const op_min_view
<Type
, Compare
>& view
)
1745 return min_max_internal::make_proxy(value
, view
);
1748 /** Computes nested minimum.
1750 * Compute the minimum of the result of a min_of() call and another value.
1752 * The result of this computation can only be assigned back to the original
1753 * view or wrapper, or used in another min_of() call. For example,
1755 * *reducer = min_of(x, min_of(y, *reducer));
1756 * wrapper = min_of(min_of(wrapper, x), y);
1758 * @see min_max_internal::rhs_proxy
1760 template <typename Type
, typename Compare
>
1761 inline min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >
1762 min_of(const min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >& proxy
,
1765 return proxy
.calc(value
);
1768 /// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_view<Type, Compare> >&, const Type&)
1769 template <typename Type
, typename Compare
>
1770 inline min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >
1771 min_of(const Type
& value
,
1772 const min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >& proxy
)
1774 return proxy
.calc(value
);
1778 /** Monoid class for minimum reductions. Instantiate the cilk::reducer template
1779 * class with an op_min monoid to create a minimum reducer class. For example,
1780 * to compute the minimum of a set of `int` values:
1782 * cilk::reducer< cilk::op_min<int> > r;
1784 * @see ReducersMinMax
1787 template <typename Type
, typename Compare
=std::less
<Type
>, bool Align
= false>
1788 class op_min
: public min_max_internal::monoid_base
<op_min_view
<Type
, Compare
>, Align
> {
1789 typedef min_max_internal::monoid_base
<op_min_view
<Type
, Compare
>, Align
> base
;
1791 /// Construct with default comparator.
1793 /// Construct with specified comparator.
1794 op_min(const Compare
& compare
) : base(compare
) {}
1800 /** @defgroup ReducersMinMaxMaxIndex Maximum reducers (value and index)
1802 * These reducers will find the largest value from a set of values, and its
1805 * @ingroup ReducersMinMax
1809 /** The maximum index reducer view class.
1811 * This is the view class for reducers created with
1812 * `cilk::reducer< cilk::op_max_index<Index, Type, Compare> >`. It accumulates
1813 * the maximum, as determined by a comparator, of a set of values which have
1814 * occurred as arguments to the `calc_max()` function, and records the index
1815 * of the maximum value. The accumulated value will be the first argument `x`
1816 * such that `compare(x, y)` is false for every argument `y`.
1818 * If the comparator is `std::less`, then the accumulated value is the first
1819 * argument value which is not less than any other argument value, i.e., the
1822 * @note The reducer "dereference" operation (`reducer::operator *()`)
1823 * yields a reference to the view. Thus, for example, the view class's
1824 * `calc_max()` function would be used in an expression like
1825 * `r->calc_max(i, a)`where `r` is an op_max_index reducer
1828 * @note The word "index" suggests an integer index into an array, but there
1829 * is no restriction on the index type or how it should be used. In
1830 * general, it may be convenient to use it for any kind of key that
1831 * can be used to locate the maximum value in the collection that it
1832 * came from - for example:
1833 * - An index into an array.
1834 * - A key into an STL map.
1835 * - An iterator into any STL container.
1837 * @note A max_index reducer is essentially a max reducer whose value type
1838 * is a `std::pair<Index, Type>`. This fact is camouflaged in the view
1839 * `calc_max` function, the global `max_of` functions, and the reducer
1840 * value constructor, which can all take an index argument and a value
1841 * argument as an alternative to a single `std::pair` argument.
1842 * However, the reducer `set_value()`, `get_value()`, `move_in()`, and
1843 * `move_out()` functions work only with pairs, not with individual
1844 * value and/or index arguments.
1846 * @tparam Index The type of the indices associated with the values.
1847 * @tparam Type The type of the values compared by the reducer. This will
1848 * be the value type of a monoid_with_view that is
1849 * instantiated with this view.
1850 * @tparam Compare Used to compare the values. It must be a binary predicate.
1851 * If it is omitted, then the view computes the conventional
1852 * arithmetic maximum.
1854 * @see ReducersMinMax
1857 template <typename Index
, typename Type
, typename Compare
>
1858 class op_max_index_view
: public min_max_internal::view_base
<
1859 min_max_internal::index_view_content
<Index
, Type
, Compare
, true>,
1863 typedef min_max_internal::view_base
<
1864 min_max_internal::index_view_content
<Index
, Type
, Compare
, true>,
1869 typedef std::pair
<Index
, Type
> pair_type
;
1870 friend class min_max_internal::rhs_proxy
<op_max_index_view
>;
1873 /** @name Constructors.
1875 * All op_max_index_view constructors simply pass their arguments on to the
1876 * @ref view_base base class, except for the `(index, value [, compare])`
1877 * constructors, which create a `std::pair` containing the index and value.
1881 op_max_index_view() : base() {}
1883 template <typename T1
>
1884 op_max_index_view(const T1
& x1
) : base(x1
) {}
1886 template <typename T1
, typename T2
>
1887 op_max_index_view(const T1
& x1
, const T2
& x2
) : base(x1
, x2
) {}
1889 template <typename T1
, typename T2
, typename T3
>
1890 op_max_index_view(const T1
& x1
, const T2
& x2
, const T3
& x3
) : base(x1
, x2
, x3
) {}
1892 op_max_index_view(const Index
& i
, const Type
& v
) : base(pair_type(i
, v
)) {}
1894 op_max_index_view(const Index
& i
, const Type
& v
, const typename
base::compare_type
* c
) :
1895 base(pair_type(i
, v
), c
) {}
1899 /** Maximizes with a value and index.
1901 * If @a x is greater than the current value of the view (as defined by
1902 * the reducer's comparator), or if the view was created without an
1903 * initial value and its value has never been updated (with `calc_max()`
1904 * or `= max_of()`), then the value of the view is set to @a x, and the
1905 * index is set to @a i..
1907 * @param i The index of the value @a x.
1908 * @param x The value to maximize the view's value with.
1910 * @return A reference to the view. (Allows
1911 * `view.comp_max(i, a).comp_max(j, b)…`.)
1913 op_max_index_view
& calc_max(const Index
& i
, const Type
& x
)
1914 { calc(pair_type(i
, x
)); return *this; }
1916 /** Maximizes with an index/value pair.
1918 * If @a pair.second is greater than the current value of the view (as
1919 * defined by the reducer's comparator), or if the view was created
1920 * without an initial value and its value has never been updated (with
1921 * `calc_max()` or `= max_of()`), then the value of the view is set to
1922 * @a pair.second, and the index is set to @a pair.first.
1924 * @param pair A pair containing a value to maximize the view's value
1925 * with and its associated index.
1927 * @return A reference to the view. (Allows
1928 * `view.comp_max(p1).comp_max(p2)…`.)
1930 op_max_index_view
& calc_max(const pair_type
& pair
)
1931 { calc(pair
); return *this; }
1933 /** Assigns the result of a `max_of(view, index, value)` expression to the
1936 * @param rhs An rhs_proxy value created by a `max_of(view, index, value)`
1939 * @return A reference to the view.
1941 * @see min_max_internal::view_base::rhs_proxy
1943 op_max_index_view
& operator=(const min_max_internal::rhs_proxy
<op_max_index_view
>& rhs
)
1944 { assign(rhs
); return *this; }
1948 /** Computes the maximum of the value in a view and another value.
1950 * The result of this computation can only be assigned back to the original
1951 * view or used in another max_of() call. For example,
1953 * *reducer = max_of(*reducer, i, x);
1954 * *reducer = max_of(i, x, *reducer);
1956 * @see min_max_internal::rhs_proxy
1958 template <typename Index
, typename Type
, typename Compare
>
1959 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
1960 max_of(const op_max_index_view
<Index
, Type
, Compare
>& view
,
1961 const Index
& index
, const Type
& value
)
1963 return min_max_internal::make_proxy(std::pair
<Index
, Type
>(index
, value
), view
);
1966 /// @copydoc max_of(const op_max_index_view<Index, Type, Compare>&, const Index&, const Type&)
1967 template <typename Index
, typename Type
, typename Compare
>
1968 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
1969 max_of(const Index
& index
, const Type
& value
,
1970 const op_max_index_view
<Index
, Type
, Compare
>& view
)
1972 return min_max_internal::make_proxy(std::pair
<Index
, Type
>(index
, value
), view
);
1975 /// @copydoc max_of(const op_max_index_view<Index, Type, Compare>&, const Index&, const Type&)
1976 template <typename Index
, typename Type
, typename Compare
>
1977 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
1978 max_of(const op_max_index_view
<Index
, Type
, Compare
>& view
,
1979 const std::pair
<Index
, Type
>& pair
)
1981 return min_max_internal::make_proxy(pair
, view
);
1984 /// @copydoc max_of(const op_max_index_view<Index, Type, Compare>&, const Index&, const Type&)
1985 template <typename Index
, typename Type
, typename Compare
>
1986 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
1987 max_of(const std::pair
<Index
, Type
>& pair
,
1988 const op_max_index_view
<Index
, Type
, Compare
>& view
)
1990 return min_max_internal::make_proxy(pair
, view
);
1993 /** Computes the nested maximum between the value in a view and other values.
1995 * Compute the maximum of the result of a max_of() call and another value.
1997 * The result of this computation can only be assigned back to the original
1998 * view or used in another max_of() call. For example,
2000 * *reducer = max_of(x, max_of(y, *reducer));
2001 * *reducer = max_of(max_of(*reducer, x), y);
2003 * @see min_max_internal::rhs_proxy
2005 template <typename Index
, typename Type
, typename Compare
>
2006 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
2007 max_of(const min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >& proxy
,
2008 const Index
& index
, const Type
& value
)
2010 return proxy
.calc(std::pair
<Index
, Type
>(index
, value
));
2013 /// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >&, const Index&, const Type&)
2014 template <typename Index
, typename Type
, typename Compare
>
2015 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
2016 max_of(const Index
& index
, const Type
& value
,
2017 const min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >& proxy
)
2019 return proxy
.calc(std::pair
<Index
, Type
>(index
, value
));
2022 /// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >&, const Index&, const Type&)
2023 template <typename Index
, typename Type
, typename Compare
>
2024 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
2025 max_of(const min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >& proxy
,
2026 const std::pair
<Index
, Type
>& pair
)
2028 return proxy
.calc(pair
);
2031 /// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >&, const Index&, const Type&)
2032 template <typename Index
, typename Type
, typename Compare
>
2033 inline min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >
2034 max_of(const std::pair
<Index
, Type
>& pair
,
2035 const min_max_internal::rhs_proxy
< op_max_index_view
<Index
, Type
, Compare
> >& proxy
)
2037 return proxy
.calc(pair
);
2041 /** Monoid class for maximum reductions with index. Instantiate the
2042 * cilk::reducer template class with an op_max_index monoid to create a
2043 * max_index reducer class. For example, to compute the maximum of an array of
2044 * `double` values and the array index of the max value:
2046 * cilk::reducer< cilk::op_max_index<unsigned, double> > r;
2048 * @see ReducersMinMax
2049 * @see op_max_index_view
2051 template < typename Index
2053 , typename Compare
=std::less
<Type
>
2054 , bool Align
= false
2056 class op_max_index
: public min_max_internal::monoid_base
<op_max_index_view
<Index
, Type
, Compare
>, Align
>
2058 typedef min_max_internal::monoid_base
<
2059 op_max_index_view
<Index
, Type
, Compare
>, Align
> base
;
2061 /// Construct with default comparator.
2063 /// Construct with specified comparator.
2064 op_max_index(const Compare
& compare
) : base(compare
) {}
2071 /** @defgroup ReducersMinMaxMinIndex Minimum reducers (value and index)
2073 * These reducers will find the smallest value from a set of values, and its
2076 * @ingroup ReducersMinMax
2080 /** The minimum index reducer view class.
2082 * This is the view class for reducers created with
2083 * `cilk::reducer<cilk::op_min_index<Index, Type, Compare> >`. It accumulates
2084 * the minimum, as determined by a comparator, of a set of values which have
2085 * occurred as arguments to the `calc_min()` function, and records the index
2086 * of the minimum value. The accumulated value will be the first argument `x`
2087 * such that `compare(y, x)` is false for every argument `y`.
2089 * If the comparator is `std::less`, then the accumulated value is the first
2090 * argument value which no other argument value is less than, i.e., the
2093 * @note The reducer "dereference" operation (`reducer::operator *()`)
2094 * yields a reference to the view. Thus, for example, the view class's
2095 * `calc_min()` function would be
2096 * used in an expression like `r->calc_min(i, a)`where `r` is an
2097 * op_min_index reducer variable.
2099 * @note The word "index" suggests an integer index into an array, but there
2100 * is no restriction on the index type or how it should be used. In
2101 * general, it may be convenient to use it for any kind of key that
2102 * can be used to locate the minimum value in the collection that it
2103 * came from - for example:
2104 * - An index into an array.
2105 * - A key into an STL map.
2106 * - An iterator into any STL container.
2108 * @note A min_index reducer is essentially a min reducer whose value type
2109 * is a `std::pair<Index, Type>`. This fact is camouflaged in the view
2110 * `calc_min` function, the global `min_of` functions, and the reducer
2111 * value constructor, which can all take an index argument and a value
2112 * argument as an alternative to a single `std::pair` argument.
2113 * However, the reducer `set_value()`, `get_value()`, `move_in()`, and
2114 * `move_out()` functions work only with pairs, not with individual
2115 * value and/or index arguments.
2117 * @tparam Index The type of the indices associated with the values.
2118 * @tparam Type The type of the values compared by the reducer. This will
2119 * be the value type of a monoid_with_view that is
2120 * instantiated with this view.
2121 * @tparam Compare Used to compare the values. It must be a binary predicate.
2122 * If it is omitted, then the view computes the conventional
2123 * arithmetic minimum.
2125 * @see ReducersMinMax
2128 template <typename Index
, typename Type
, typename Compare
>
2129 class op_min_index_view
: public min_max_internal::view_base
<
2130 min_max_internal::index_view_content
<Index
, Type
, Compare
, false>,
2132 min_max_internal::reverse_predicate
<Compare
, Type
> >
2134 typedef min_max_internal::view_base
<
2135 min_max_internal::index_view_content
<Index
, Type
, Compare
, false>,
2137 min_max_internal::reverse_predicate
<Compare
, Type
> > base
;
2140 typedef std::pair
<Index
, Type
> pair_type
;
2141 friend class min_max_internal::rhs_proxy
<op_min_index_view
>;
2144 /** @name Constructors.
2146 * All op_min_index_view constructors simply pass their arguments on to the
2147 * @ref view_base base class, except for the `(index, value [, compare])`
2148 * constructors, which create a `std::pair` containing the index and value.
2152 op_min_index_view() : base() {}
2154 template <typename T1
>
2155 op_min_index_view(const T1
& x1
) : base(x1
) {}
2157 template <typename T1
, typename T2
>
2158 op_min_index_view(const T1
& x1
, const T2
& x2
) : base(x1
, x2
) {}
2160 template <typename T1
, typename T2
, typename T3
>
2161 op_min_index_view(const T1
& x1
, const T2
& x2
, const T3
& x3
) : base(x1
, x2
, x3
) {}
2163 op_min_index_view(const Index
& i
, const Type
& v
) : base(pair_type(i
, v
)) {}
2165 op_min_index_view(const Index
& i
, const Type
& v
, const typename
base::compare_type
* c
) :
2166 base(pair_type(i
, v
), c
) {}
2170 /** Minimizes with a value and index.
2172 * If @a x is greater than the current value of the view (as defined by
2173 * the reducer's comparator), or if the view was created without an
2174 * initial value and its value has never been updated (with `calc_min()`
2175 * or `= min_of()`), then the value of the view is set to @a x, and the
2176 * index is set to @a i..
2178 * @param i The index of the value @a x.
2179 * @param x The value to minimize the view's value with.
2181 * @return A reference to the view. (Allows
2182 * `view.comp_min(i, a).comp_min(j, b)…`.)
2184 op_min_index_view
& calc_min(const Index
& i
, const Type
& x
)
2185 { calc(pair_type(i
, x
)); return *this; }
2187 /** Maximizes with an index/value pair.
2189 * If @a pair.second is less than the current value of the view (as
2190 * defined by the reducer's comparator), or if the view was created
2191 * without an initial value and its value has never been updated (with
2192 * `calc_min()` or `= min_of()`), then the value of the view is set to
2193 * @a pair.second, and the index is set to @a pair.first.
2195 * @param pair A pair containing a value to minimize the view's value
2196 * with and its associated index.
2198 * @return A reference to the view. (Allows
2199 * `view.comp_min(p1).comp_min(p2)…`.)
2201 op_min_index_view
& calc_min(const pair_type
& pair
)
2202 { calc(pair
); return *this; }
2204 /** Assigns the result of a `min_of(view, index, value)` expression to the
2207 * @param rhs An rhs_proxy value created by a `min_of(view, index, value)`
2210 * @return A reference to the view.
2212 * @see min_max_internal::view_base::rhs_proxy
2214 op_min_index_view
& operator=(const min_max_internal::rhs_proxy
<op_min_index_view
>& rhs
)
2215 { assign(rhs
); return *this; }
2219 /** Computes the minimum of the value in a view and another value.
2221 * The result of this computation can only be assigned back to the original
2222 * view or used in another min_of() call. For example,
2224 * *reducer = min_of(*reducer, i, x);
2225 * *reducer = min_of(i, x, *reducer);
2227 * @see min_max_internal::min_min_view_base::rhs_proxy
2229 template <typename Index
, typename Type
, typename Compare
>
2230 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2231 min_of(const op_min_index_view
<Index
, Type
, Compare
>& view
,
2232 const Index
& index
, const Type
& value
)
2234 return min_max_internal::make_proxy(std::pair
<Index
, Type
>(index
, value
), view
);
2237 /// @copydoc min_of(const op_min_index_view<Index, Type, Compare>&, const Index&, const Type&)
2238 template <typename Index
, typename Type
, typename Compare
>
2239 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2240 min_of(const Index
& index
, const Type
& value
,
2241 const op_min_index_view
<Index
, Type
, Compare
>& view
)
2243 return min_max_internal::make_proxy(std::pair
<Index
, Type
>(index
, value
), view
);
2246 /// @copydoc min_of(const op_min_index_view<Index, Type, Compare>&, const Index&, const Type&)
2247 template <typename Index
, typename Type
, typename Compare
>
2248 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2249 min_of(const op_min_index_view
<Index
, Type
, Compare
>& view
,
2250 const std::pair
<Index
, Type
>& pair
)
2252 return min_max_internal::make_proxy(pair
, view
);
2255 /// @copydoc min_of(const op_min_index_view<Index, Type, Compare>&, const Index&, const Type&)
2256 template <typename Index
, typename Type
, typename Compare
>
2257 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2258 min_of(const std::pair
<Index
, Type
>& pair
,
2259 const op_min_index_view
<Index
, Type
, Compare
>& view
)
2261 return min_max_internal::make_proxy(pair
, view
);
2264 /** Computes nested minimum between the value in a view and other values.
2266 * Compute the minimum of the result of a min_of() call and another value.
2268 * The result of this computation can only be assigned back to the original
2269 * view or used in another min_of() call. For example,
2271 * *reducer = min_of(x, min_of(y, *reducer));
2272 * *reducer = min_of(min_of(*reducer, x), y);
2274 * @see min_max_internal::min_min_view_base::rhs_proxy
2276 template <typename Index
, typename Type
, typename Compare
>
2277 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2278 min_of(const min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >& proxy
,
2279 const Index
& index
, const Type
& value
)
2281 return proxy
.calc(std::pair
<Index
, Type
>(index
, value
));
2284 /// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >&, const Index&, const Type&)
2285 template <typename Index
, typename Type
, typename Compare
>
2286 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2287 min_of(const Index
& index
, const Type
& value
,
2288 const min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >& proxy
)
2290 return proxy
.calc(std::pair
<Index
, Type
>(index
, value
));
2293 /// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >&, const Index&, const Type&)
2294 template <typename Index
, typename Type
, typename Compare
>
2295 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2296 min_of(const min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >& proxy
,
2297 const std::pair
<Index
, Type
>& pair
)
2299 return proxy
.calc(pair
);
2302 /// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >&, const Index&, const Type&)
2303 template <typename Index
, typename Type
, typename Compare
>
2304 inline min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >
2305 min_of(const std::pair
<Index
, Type
>& pair
,
2306 const min_max_internal::rhs_proxy
< op_min_index_view
<Index
, Type
, Compare
> >& proxy
)
2308 return proxy
.calc(pair
);
2312 /** Monoid class for minimum reductions with index. Instantiate the
2313 * cilk::reducer template class with an op_min_index monoid to create a
2314 * min_index reducer class. For example, to compute the minimum of an array of
2315 * `double` values and the array index of the min value:
2317 * cilk::reducer< cilk::op_min_index<unsigned, double> > r;
2319 * @see ReducersMinMax
2320 * @see op_min_index_view
2322 template < typename Index
2324 , typename Compare
=std::less
<Type
>
2325 , bool Align
= false
2327 class op_min_index
: public min_max_internal::monoid_base
<op_min_index_view
<Index
, Type
, Compare
>, Align
>
2329 typedef min_max_internal::monoid_base
<
2330 op_min_index_view
<Index
, Type
, Compare
>, Align
> base
;
2332 /// Construct with default comparator.
2334 /// Construct with specified comparator.
2335 op_min_index(const Compare
& compare
) : base(compare
) {}
2341 /** Deprecated maximum reducer wrapper class.
2343 * reducer_max is the same as @ref reducer<@ref op_max>, except that
2344 * reducer_max is a proxy for the contained view, so that accumulator
2345 * variable update operations can be applied directly to the reducer. For
2346 * example, a value is maximized with a `reducer<%op_max>` with
2347 * `r->calc_max(a)`, but a value can be maximized with a `%reducer_max` with
2351 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
2352 * reducers rather than the old wrappers like reducer_max.
2353 * The `reducer<monoid>` reducers show the reducer/monoid/view
2354 * architecture more clearly, are more consistent in their
2355 * implementation, and present a simpler model for new
2356 * user-implemented reducers.
2358 * @note Implicit conversions are provided between `%reducer_max`
2359 * and `reducer<%op_max>`. This allows incremental code
2360 * conversion: old code that used `%reducer_max` can pass a
2361 * `%reducer_max` to a converted function that now expects a
2362 * pointer or reference to a `reducer<%op_max>`, and vice
2363 * versa. **But see @ref redminmax_compatibility.**
2365 * @tparam Type The value type of the reducer.
2366 * @tparam Compare The "less than" comparator type for the reducer.
2371 * @see ReducersMinMax
2372 * @ingroup ReducersMinMaxMaxValue
2374 template <typename Type
, typename Compare
=std::less
<Type
> >
2375 class reducer_max
: public reducer
< op_max
<Type
, Compare
, true> >
2377 __CILKRTS_STATIC_ASSERT(
2378 ::cilk::internal::class_is_empty
<
2379 typename ::cilk::internal::binary_functor
<Compare
>::type
>::value
,
2380 "cilk::reducer_max<Type, Compare> only works with "
2381 "an empty Compare class");
2382 typedef reducer
< op_max
<Type
, Compare
, true> > base
;
2385 /// Type of data in a reducer_max.
2386 typedef Type basic_value_type
;
2388 /// The view type for the reducer.
2389 typedef typename
base::view_type view_type
;
2391 /// The view type for the reducer.
2392 typedef typename
base::view_type View
;
2394 /// The monoid type for the reducer.
2395 typedef typename
base::monoid_type monoid_type
;
2397 /// The monoid type for the reducer.
2398 typedef typename
base::monoid_type Monoid
;
2400 /// The view's rhs proxy type.
2401 typedef min_max_internal::rhs_proxy
<View
> rhs_proxy
;
2405 /** @name Constructors
2409 /// Constructs the wrapper in its identity state (either `!is_set()`, or
2410 /// `value() == identity value`).
2411 reducer_max() : base() {}
2413 /// Constructs the wrapper with a specified initial value.
2414 explicit reducer_max(const Type
& initial_value
) : base(initial_value
) {}
2416 /// Constructs the wrapper in its identity state with a specified
2418 explicit reducer_max(const Compare
& comp
) : base(comp
) {}
2420 /// Constructs the wrapper with a specified initial value and a specified
2422 reducer_max(const Type
& initial_value
, const Compare
& comp
)
2423 : base(initial_value
, comp
) {}
2427 /** @name Forwarded functions
2428 * @details Functions that update the contained accumulator variable are
2429 * simply forwarded to the contained @ref op_max_view. */
2432 /// @copydoc cilk_lib_1_1::min_max_internal::view_content::is_set() const
2433 bool is_set() const { return view().is_set(); }
2435 /// @copydoc op_max_view::calc_max(const Type&)
2436 reducer_max
& calc_max(const Type
& x
)
2437 { view().calc_max(x
); return *this; }
2439 /// @copydoc op_max_view::operator=(const min_max_internal::rhs_proxy<op_max_view>&)
2440 reducer_max
& operator=(const rhs_proxy
& rhs
)
2441 { view() = rhs
; return *this; }
2445 /** Allows read-only access to the value within the current view.
2447 * @returns A const reference to the value within the current view.
2449 const Type
& get_reference() const { return view().get_reference(); }
2451 /// @name Dereference
2452 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
2453 * Combined with the rule that a wrapper forwards view operations to the
2454 * view, this means that view operations can be written the same way on
2455 * reducers and wrappers, which is convenient for incrementally
2456 * converting code using wrappers to code using reducers. That is:
2458 * reducer< op_max<int> > r;
2459 * r->calc_max(a); // *r returns the view
2460 * // calc_max is a view member function
2462 * reducer_max<int> w;
2463 * w->calc_max(a); // *w returns the wrapper
2464 * // calc_max is a wrapper member function that
2465 * // calls the corresponding view function
2468 reducer_max
& operator*() { return *this; }
2469 reducer_max
const& operator*() const { return *this; }
2471 reducer_max
* operator->() { return this; }
2472 reducer_max
const* operator->() const { return this; }
2476 * @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
2477 * In library 1.0, reducer cache alignment is optional. By default,
2478 * reducers are unaligned (i.e., just naturally aligned), but legacy
2479 * wrappers inherit from cache-aligned reducers for binary compatibility.
2481 * This means that a wrapper will automatically be upcast to its aligned
2482 * reducer base class. The following conversion operators provide
2483 * pseudo-upcasts to the corresponding unaligned reducer class.
2486 operator reducer
< op_max
<Type
, Compare
, false> >& ()
2488 return *reinterpret_cast< reducer
< op_max
<Type
, Compare
, false> >* >(this);
2491 operator const reducer
< op_max
<Type
, Compare
, false> >& () const
2493 return *reinterpret_cast< const reducer
< op_max
<Type
, Compare
, false> >* >(this);
2500 // The legacy definition of max_of(reducer_max, value) has different
2501 // behavior and a different return type than this definition. We add an
2502 // unused third argument to this version of the function to give it a different
2503 // signature, so that they won't end up sharing a single object file entry.
2504 struct max_of_1_0_t
{};
2505 const max_of_1_0_t max_of_1_0
= {};
2508 /** Computes the maximum of the value in a reducer_max and another value.
2510 * @deprecated Because reducer_max is deprecated.
2512 * The result of this computation can only be assigned back to the original
2513 * reducer or used in another max_of() call. For example,
2515 * reducer = max_of(reducer, x);
2516 * reducer = max_of(x, reducer);
2518 * @see min_max_internal::rhs_proxy
2520 * @ingroup ReducersMinMaxMaxValue
2522 template <typename Type
, typename Compare
>
2523 inline min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >
2524 max_of(const reducer_max
<Type
, Compare
>& r
, const Type
& value
,
2525 const max_of_1_0_t
& = max_of_1_0
)
2527 return min_max_internal::make_proxy(value
, r
.view());
2530 /// @copydoc max_of(const reducer_max<Type, Compare>&, const Type&, const max_of_1_0_t&)
2531 /// @ingroup ReducersMinMaxMaxValue
2532 template <typename Type
, typename Compare
>
2533 inline min_max_internal::rhs_proxy
< op_max_view
<Type
, Compare
> >
2534 max_of(const Type
& value
, const reducer_max
<Type
, Compare
>& r
,
2535 const max_of_1_0_t
& = max_of_1_0
)
2537 return min_max_internal::make_proxy(value
, r
.view());
2541 /** Deprecated minimum reducer wrapper class.
2543 * reducer_min is the same as @ref reducer<@ref op_min>, except that
2544 * reducer_min is a proxy for the contained view, so that accumulator
2545 * variable update operations can be applied directly to the reducer. For
2546 * example, a value is minimized with a `reducer<%op_min>` with
2547 * `r->calc_min(a)`, but a value can be minimized with a `%reducer_min` with
2551 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
2552 * reducers rather than the old wrappers like reducer_min.
2553 * The `reducer<monoid>` reducers show the reducer/monoid/view
2554 * architecture more clearly, are more consistent in their
2555 * implementation, and present a simpler model for new
2556 * user-implemented reducers.
2558 * @note Implicit conversions are provided between `%reducer_min`
2559 * and `reducer<%op_min>`. This allows incremental code
2560 * conversion: old code that used `%reducer_min` can pass a
2561 * `%reducer_min` to a converted function that now expects a
2562 * pointer or reference to a `reducer<%op_min>`, and vice
2563 * versa. **But see @ref redminmax_compatibility.**
2565 * @tparam Type The value type of the reducer.
2566 * @tparam Compare The "less than" comparator type for the reducer.
2571 * @see ReducersMinMax
2572 * @ingroup ReducersMinMaxMinValue
2574 template <typename Type
, typename Compare
=std::less
<Type
> >
2575 class reducer_min
: public reducer
< op_min
<Type
, Compare
, true> >
2577 __CILKRTS_STATIC_ASSERT(
2578 ::cilk::internal::class_is_empty
<
2579 typename ::cilk::internal::binary_functor
<Compare
>::type
>::value
,
2580 "cilk::reducer_min<Type, Compare> only works with "
2581 "an empty Compare class");
2582 typedef reducer
< op_min
<Type
, Compare
, true> > base
;
2585 /// Type of data in a reducer_min.
2586 typedef Type basic_value_type
;
2588 /// The view type for the reducer.
2589 typedef typename
base::view_type view_type
;
2591 /// The view type for the reducer.
2592 typedef typename
base::view_type View
;
2594 /// The monoid type for the reducer.
2595 typedef typename
base::monoid_type monoid_type
;
2597 /// The monoid type for the reducer.
2598 typedef typename
base::monoid_type Monoid
;
2600 /// The view's rhs proxy type.
2601 typedef min_max_internal::rhs_proxy
<View
> rhs_proxy
;
2605 /** @name Constructors
2609 /// Constructs the wrapper in its identity state (either `!is_set()`, or
2610 /// `value() == identity value`).
2611 reducer_min() : base() {}
2613 /// Constructs the wrapper with a specified initial value.
2614 explicit reducer_min(const Type
& initial_value
) : base(initial_value
) {}
2616 /// Constructs the wrapper in its identity state with a specified
2618 explicit reducer_min(const Compare
& comp
) : base(comp
) {}
2620 /// Constructs the wrapper with a specified initial value and a specified
2622 reducer_min(const Type
& initial_value
, const Compare
& comp
)
2623 : base(initial_value
, comp
) {}
2627 /** @name Forwarded functions
2628 * @details Functions that update the contained accumulator variable are
2629 * simply forwarded to the contained @ref op_min_view. */
2632 /// @copydoc cilk_lib_1_1::min_max_internal::view_content::is_set() const
2633 bool is_set() const { return view().is_set(); }
2635 /// @copydoc op_min_view::calc_min(const Type&)
2636 reducer_min
& calc_min(const Type
& x
)
2637 { view().calc_min(x
); return *this; }
2639 /// @copydoc op_min_view::operator=(const min_max_internal::rhs_proxy<op_min_view>&)
2640 reducer_min
& operator=(const rhs_proxy
& rhs
)
2641 { view() = rhs
; return *this; }
2645 /** Allows read-only access to the value within the current view.
2647 * @returns A const reference to the value within the current view.
2649 const Type
& get_reference() const { return view().get_reference(); }
2651 /// @name Dereference
2652 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
2653 * Combined with the rule that a wrapper forwards view operations to the
2654 * view, this means that view operations can be written the same way on
2655 * reducers and wrappers, which is convenient for incrementally
2656 * converting code using wrappers to code using reducers. That is:
2658 * reducer< op_min<int> > r;
2659 * r->calc_min(a); // *r returns the view
2660 * // calc_min is a view member function
2662 * reducer_min<int> w;
2663 * w->calc_min(a); // *w returns the wrapper
2664 * // calc_min is a wrapper member function that
2665 * // calls the corresponding view function
2668 reducer_min
& operator*() { return *this; }
2669 reducer_min
const& operator*() const { return *this; }
2671 reducer_min
* operator->() { return this; }
2672 reducer_min
const* operator->() const { return this; }
2676 * @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
2677 * In library 1.0, reducer cache alignment is optional. By default,
2678 * reducers are unaligned (i.e., just naturally aligned), but legacy
2679 * wrappers inherit from cache-aligned reducers for binary compatibility.
2681 * This means that a wrapper will automatically be upcast to its aligned
2682 * reducer base class. The following conversion operators provide
2683 * pseudo-upcasts to the corresponding unaligned reducer class.
2686 operator reducer
< op_min
<Type
, Compare
, false> >& ()
2688 return *reinterpret_cast< reducer
< op_min
<Type
, Compare
, false> >* >(this);
2691 operator const reducer
< op_min
<Type
, Compare
, false> >& () const
2693 return *reinterpret_cast< const reducer
< op_min
<Type
, Compare
, false> >* >(this);
2699 /** Computes the minimum of a reducer and a value.
2701 * @deprecated Because reducer_min is deprecated.
2704 // The legacy definition of min_of(reducer_min, value) has different
2705 // behavior and a different return type than this definition. We add an
2706 // unused third argument to this version of the function to give it a different
2707 // signature, so that they won't end up sharing a single object file entry.
2708 struct min_of_1_0_t
{};
2709 const min_of_1_0_t min_of_1_0
= {};
2711 template <typename Type
, typename Compare
>
2712 inline min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >
2713 min_of(const reducer_min
<Type
, Compare
>& r
, const Type
& value
,
2714 const min_of_1_0_t
& = min_of_1_0
)
2716 return min_max_internal::make_proxy(value
, r
.view());
2719 template <typename Type
, typename Compare
>
2720 inline min_max_internal::rhs_proxy
< op_min_view
<Type
, Compare
> >
2721 min_of(const Type
& value
, const reducer_min
<Type
, Compare
>& r
,
2722 const min_of_1_0_t
& = min_of_1_0
)
2724 return min_max_internal::make_proxy(value
, r
.view());
2729 /** Deprecated maximum with index reducer wrapper class.
2731 * reducer_max_index is the same as @ref reducer<@ref op_max_index>, except
2732 * that reducer_max_index is a proxy for the contained view, so that
2733 * accumulator variable update operations can be applied directly to the
2734 * reducer. For example, a value is maximized with a `reducer<%op_max_index>`
2735 * with `r->calc_max(i, a)`, but a value can be maximized with a
2736 * `%reducer_max` with `r.calc_max(i, aa)`.
2739 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
2740 * reducers rather than the old wrappers like reducer_max.
2741 * The `reducer<monoid>` reducers show the reducer/monoid/view
2742 * architecture more clearly, are more consistent in their
2743 * implementation, and present a simpler model for new
2744 * user-implemented reducers.
2746 * @note Implicit conversions are provided between `%reducer_max_index`
2747 * and `reducer<%op_max_index>`. This allows incremental code
2748 * conversion: old code that used `%reducer_max_index` can pass a
2749 * `%reducer_max_index` to a converted function that now expects a
2750 * pointer or reference to a `reducer<%op_max_index>`, and vice
2751 * versa. **But see @ref redminmax_compatibility.**
2753 * @tparam Index The index type of the reducer.
2754 * @tparam Type The value type of the reducer.
2755 * @tparam Compare The "less than" comparator type for the reducer.
2758 * @see op_max_index_view
2760 * @see ReducersMinMax
2761 * @ingroup ReducersMinMaxMaxIndex
2763 template < typename Index
2765 , typename Compare
= std::less
<Type
>
2767 class reducer_max_index
:
2768 public reducer
< op_max_index
<Index
, Type
, Compare
, true> >
2770 __CILKRTS_STATIC_ASSERT(
2771 ::cilk::internal::class_is_empty
<
2772 typename ::cilk::internal::binary_functor
<Compare
>::type
>::value
,
2773 "cilk::reducer_max_index<Type, Compare> only works with "
2774 "an empty Compare class");
2775 typedef reducer
< op_max_index
<Index
, Type
, Compare
, true> > base
;
2778 /// Type of data in a reducer_max_index.
2779 typedef Type basic_value_type
;
2781 /// The view type for the reducer.
2782 typedef typename
base::view_type view_type
;
2784 /// The view type for the reducer.
2785 typedef typename
base::view_type View
;
2787 /// The monoid type for the reducer.
2788 typedef typename
base::monoid_type monoid_type
;
2790 /// The monoid type for the reducer.
2791 typedef typename
base::monoid_type Monoid
;
2793 /// The view's rhs proxy type.
2794 typedef min_max_internal::rhs_proxy
<View
> rhs_proxy
;
2798 /** @name Constructors
2802 /// Constructs the wrapper in its identity state (`!is_set()`).
2803 reducer_max_index() : base() {}
2805 /// Construct with a specified initial index and value.
2806 reducer_max_index(const Index
& initial_index
,
2807 const Type
& initial_value
)
2808 : base(initial_index
, initial_value
) {}
2810 /// Constructs the wrapper with a specified comparator.
2811 explicit reducer_max_index(const Compare
& comp
) : base(comp
) {}
2813 /// Constructs the wrapper with a specified initial index, value,
2815 reducer_max_index(const Index
& initial_index
,
2816 const Type
& initial_value
,
2817 const Compare
& comp
)
2818 : base(initial_index
, initial_value
, comp
) {}
2826 /// Sets the index and value of this object.
2827 void set_value(const Index
& index
, const Type
& value
)
2828 { base::set_value(std::make_pair(index
, value
)); }
2830 /// Returns the maximum value.
2831 const Type
& get_value() const
2832 { return view().get_reference(); }
2834 /// Returns the maximum index.
2835 const Index
& get_index() const
2836 { return view().get_index_reference(); }
2838 /// Returns a const reference to value data member in the view.
2839 const Type
& get_reference() const
2840 { return view().get_reference(); }
2842 /// Returns a const reference to index data member in the view.
2843 const Index
& get_index_reference() const
2844 { return view().get_index_reference(); }
2848 /** @name Forwarded functions
2849 * @details Functions that update the contained accumulator variable are
2850 * simply forwarded to the contained @ref op_max_view. */
2853 /// @copydoc cilk_lib_1_1::min_max_internal::view_content::is_set() const
2854 bool is_set() const { return view().is_set(); }
2856 /// @copydoc op_max_index_view::calc_max(const Index&, const Type&)
2857 reducer_max_index
& calc_max(const Index
& i
, const Type
& x
)
2858 { view().calc_max(i
, x
); return *this; }
2860 /// @copydoc op_max_view::operator=(const min_max_internal::rhs_proxy<op_max_view>&)
2861 reducer_max_index
& operator=(const rhs_proxy
& rhs
)
2862 { view() = rhs
; return *this; }
2866 /// @name Dereference
2867 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
2868 * Combined with the rule that a wrapper forwards view operations to the
2869 * view, this means that view operations can be written the same way on
2870 * reducers and wrappers, which is convenient for incrementally
2871 * converting code using wrappers to code using reducers. That is:
2873 * reducer< op_max_index<int, int> > r;
2874 * r->calc_max(i, a); // *r returns the view
2875 * // calc_max is a view member function
2877 * reducer_max_index<int, int> w;
2878 * w->calc_max(i, a); // *w returns the wrapper
2879 * // calc_max is a wrapper member function that
2880 * // calls the corresponding view function
2883 reducer_max_index
& operator*() { return *this; }
2884 reducer_max_index
const& operator*() const { return *this; }
2886 reducer_max_index
* operator->() { return this; }
2887 reducer_max_index
const* operator->() const { return this; }
2891 * @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
2892 * In library 1.0, reducer cache alignment is optional. By default,
2893 * reducers are unaligned (i.e., just naturally aligned), but legacy
2894 * wrappers inherit from cache-aligned reducers for binary compatibility.
2896 * This means that a wrapper will automatically be upcast to its aligned
2897 * reducer base class. The following conversion operators provide
2898 * pseudo-upcasts to the corresponding unaligned reducer class.
2901 operator reducer
< op_max_index
<Index
, Type
, Compare
, false> >& ()
2903 return *reinterpret_cast< reducer
< op_max_index
<Index
, Type
, Compare
, false> >* >(this);
2906 operator const reducer
< op_max_index
<Index
, Type
, Compare
, false> >& () const
2908 return *reinterpret_cast< const reducer
< op_max_index
<Index
, Type
, Compare
, false> >* >(this);
2915 /** Deprecated minimum with index reducer wrapper class.
2917 * reducer_min_index is the same as @ref reducer<@ref op_min_index>, except
2918 * that reducer_min_index is a proxy for the contained view, so that
2919 * accumulator variable update operations can be applied directly to the
2920 * reducer. For example, a value is minimized with a `reducer<%op_min_index>`
2921 * with `r->calc_min(i, a)`, but a value can be minimized with a
2922 * `%reducer_min` with `r.calc_min(i, aa)`.
2925 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
2926 * reducers rather than the old wrappers like reducer_min.
2927 * The `reducer<monoid>` reducers show the reducer/monoid/view
2928 * architecture more clearly, are more consistent in their
2929 * implementation, and present a simpler model for new
2930 * user-implemented reducers.
2932 * @note Implicit conversions are provided between `%reducer_min_index`
2933 * and `reducer<%op_min_index>`. This allows incremental code
2934 * conversion: old code that used `%reducer_min_index` can pass a
2935 * `%reducer_min_index` to a converted function that now expects a
2936 * pointer or reference to a `reducer<%op_min_index>`, and vice
2937 * versa. **But see @ref redminmax_compatibility.**
2939 * @tparam Index The index type of the reducer.
2940 * @tparam Type The value type of the reducer.
2941 * @tparam Compare The "less than" comparator type for the reducer.
2944 * @see op_min_index_view
2946 * @see ReducersMinMax
2947 * @ingroup ReducersMinMaxMinIndex
2949 template < typename Index
2951 , typename Compare
= std::less
<Type
>
2953 class reducer_min_index
:
2954 public reducer
< op_min_index
<Index
, Type
, Compare
, true> >
2956 __CILKRTS_STATIC_ASSERT(
2957 ::cilk::internal::class_is_empty
<
2958 typename ::cilk::internal::binary_functor
<Compare
>::type
>::value
,
2959 "cilk::reducer_min_index<Type, Compare> only works with "
2960 "an empty Compare class");
2961 typedef reducer
< op_min_index
<Index
, Type
, Compare
, true> > base
;
2964 /// Type of data in a reducer_min_index.
2965 typedef Type basic_value_type
;
2967 /// The view type for the reducer.
2968 typedef typename
base::view_type view_type
;
2970 /// The view type for the reducer.
2971 typedef typename
base::view_type View
;
2973 /// The monoid type for the reducer.
2974 typedef typename
base::monoid_type monoid_type
;
2976 /// The monoid type for the reducer.
2977 typedef typename
base::monoid_type Monoid
;
2979 /// The view's rhs proxy type.
2980 typedef min_max_internal::rhs_proxy
<View
> rhs_proxy
;
2984 /** @name Constructors
2988 /// Constructs the wrapper in its identity state (`!is_set()`).
2989 reducer_min_index() : base() {}
2991 /// Construct with a specified initial index and value.
2992 reducer_min_index(const Index
& initial_index
,
2993 const Type
& initial_value
)
2994 : base(initial_index
, initial_value
) {}
2996 /// Constructs the wrapper with a specified comparator.
2997 explicit reducer_min_index(const Compare
& comp
) : base(comp
) {}
2999 /// Constructs the wrapper with a specified initial index, value,
3001 reducer_min_index(const Index
& initial_index
,
3002 const Type
& initial_value
,
3003 const Compare
& comp
)
3004 : base(initial_index
, initial_value
, comp
) {}
3012 /// Sets the index and value of this object.
3013 void set_value(const Index
& index
, const Type
& value
)
3014 { base::set_value(std::make_pair(index
, value
)); }
3016 /// Returns the minimum value.
3017 const Type
& get_value() const
3018 { return view().get_reference(); }
3020 /// Returns the minimum index.
3021 const Index
& get_index() const
3022 { return view().get_index_reference(); }
3024 /// Returns a const reference to value data member in the view.
3025 const Type
& get_reference() const
3026 { return view().get_reference(); }
3028 /// Returns a const reference to index data member in the view.
3029 const Index
& get_index_reference() const
3030 { return view().get_index_reference(); }
3034 /** @name Forwarded functions
3035 * @details Functions that update the contained accumulator variable are
3036 * simply forwarded to the contained @ref op_min_view. */
3039 /// @copydoc cilk_lib_1_1::min_max_internal::view_content::is_set() const
3040 bool is_set() const { return view().is_set(); }
3042 /// @copydoc op_min_index_view::calc_min(const Index&, const Type&)
3043 reducer_min_index
& calc_min(const Index
& i
, const Type
& x
)
3044 { view().calc_min(i
, x
); return *this; }
3046 /// @copydoc op_min_view::operator=(const min_max_internal::rhs_proxy<op_min_view>&)
3047 reducer_min_index
& operator=(const rhs_proxy
& rhs
)
3048 { view() = rhs
; return *this; }
3052 /// @name Dereference
3053 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
3054 * Combined with the rule that a wrapper forwards view operations to the
3055 * view, this means that view operations can be written the same way on
3056 * reducers and wrappers, which is convenient for incrementally
3057 * converting code using wrappers to code using reducers. That is:
3059 * reducer< op_min_index<int, int> > r;
3060 * r->calc_min(i, a); // *r returns the view
3061 * // calc_min is a view member function
3063 * reducer_min_index<int, int> w;
3064 * w->calc_min(i, a); // *w returns the wrapper
3065 * // calc_min is a wrapper member function that
3066 * // calls the corresponding view function
3069 reducer_min_index
& operator*() { return *this; }
3070 reducer_min_index
const& operator*() const { return *this; }
3072 reducer_min_index
* operator->() { return this; }
3073 reducer_min_index
const* operator->() const { return this; }
3077 * @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
3078 * In library 1.0, reducer cache alignment is optional. By default,
3079 * reducers are unaligned (i.e., just naturally aligned), but legacy
3080 * wrappers inherit from cache-aligned reducers for binary compatibility.
3082 * This means that a wrapper will automatically be upcast to its aligned
3083 * reducer base class. The following conversion operators provide
3084 * pseudo-upcasts to the corresponding unaligned reducer class.
3087 operator reducer
< op_min_index
<Index
, Type
, Compare
, false> >& ()
3089 return *reinterpret_cast< reducer
< op_min_index
<Index
, Type
, Compare
, false> >* >(this);
3092 operator const reducer
< op_min_index
<Index
, Type
, Compare
, false> >& () const
3094 return *reinterpret_cast< const reducer
< op_min_index
<Index
, Type
, Compare
, false> >* >(this);
3101 #ifndef CILK_LIBRARY_0_9_REDUCER_MINMAX
3102 } // namespace cilk_lib_1_1
3103 using namespace cilk_lib_1_1
;
3108 /** Metafunction specialization for reducer conversion.
3110 * These specializations of the @ref legacy_reducer_downcast template class
3111 * defined in reducer.h causes each `reducer< op_xxxx<Type> >` classes to have
3112 * an `operator reducer_xxxx<Type>& ()` conversion operator that statically
3113 * downcasts the `reducer<op_xxxx>` to the corresponding `reducer_xxxx` type.
3114 * (The reverse conversion, from `reducer_xxxx` to `reducer<op_xxxx>`, is just
3115 * an upcast, which is provided for free by the language.)
3117 template <typename Type
, typename Compare
, bool Align
>
3118 struct legacy_reducer_downcast
< reducer
< op_max
<Type
, Compare
, Align
> > >
3120 typedef reducer_max
<Type
> type
;
3123 template <typename Type
, typename Compare
, bool Align
>
3124 struct legacy_reducer_downcast
< reducer
< op_min
<Type
, Compare
, Align
> > >
3126 typedef reducer_min
<Type
> type
;
3129 template <typename Index
, typename Type
, typename Compare
, bool Align
>
3130 struct legacy_reducer_downcast
< reducer
< op_max_index
<Index
, Type
, Compare
, Align
> > >
3132 typedef reducer_max_index
<Index
, Type
> type
;
3135 template <typename Index
, typename Type
, typename Compare
, bool Align
>
3136 struct legacy_reducer_downcast
< reducer
< op_min_index
<Index
, Type
, Compare
, Align
> > >
3138 typedef reducer_min_index
<Index
, Type
> type
;
3144 #endif // __cplusplus
3147 /** @name C language reducer macros
3149 * These macros are used to declare and work with numeric minimum and maximum reducers in C
3152 * @see @ref page_reducers_in_c
3157 #ifdef CILK_C_DEFINE_REDUCERS
3159 /* Integer min/max constants */
3162 /* Wchar_t min/max constants */
3163 #if defined(_MSC_VER) || defined(__ANDROID__)
3166 # include <stdint.h>
3169 /* Floating-point min/max constants */
3172 static const unsigned int __huge_valf
[] = {0x7f800000};
3173 # define HUGE_VALF (*((const float *)__huge_valf))
3177 static const unsigned int __huge_vall
[] = {0, 0, 0x00007f80, 0};
3178 # define HUGE_VALL (*((const long double *)__huge_vall))
3183 /** Declares max reducer type name.
3185 * This macro expands into the identifier which is the name of the max reducer
3186 * type for a specified numeric type.
3188 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3191 * @see @ref reducers_c_predefined
3193 #define CILK_C_REDUCER_MAX_TYPE(tn) \
3194 __CILKRTS_MKIDENT(cilk_c_reducer_max_,tn)
3196 /** Declares a max reducer object.
3198 * This macro expands into a declaration of a max reducer object for a specified numeric
3199 * type. For example:
3201 * CILK_C_REDUCER_MAX(my_reducer, double, -DBL_MAX);
3203 * @param obj The variable name to be used for the declared reducer object.
3204 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3206 * @param v The initial value for the reducer. (A value which can be assigned to the
3207 * numeric type represented by @a tn.)
3209 * @see @ref reducers_c_predefined
3211 #define CILK_C_REDUCER_MAX(obj,tn,v) \
3212 CILK_C_REDUCER_MAX_TYPE(tn) obj = \
3213 CILK_C_INIT_REDUCER(_Typeof(obj.value), \
3214 __CILKRTS_MKIDENT(cilk_c_reducer_max_reduce_,tn), \
3215 __CILKRTS_MKIDENT(cilk_c_reducer_max_identity_,tn), \
3216 __cilkrts_hyperobject_noop_destroy, v)
3218 /** Maximizes with a value.
3220 * `CILK_C_REDUCER_MAX_CALC(reducer, v)` sets the current view of the
3221 * reducer to the max of its previous value and a specified new value.
3222 * This is equivalent to
3224 * REDUCER_VIEW(reducer) = max(REDUCER_VIEW(reducer), v)
3226 * @param reducer The reducer whose contained value is to be updated.
3227 * @param v The value that it is to be maximized with.
3229 #define CILK_C_REDUCER_MAX_CALC(reducer, v) do { \
3230 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \
3231 _Typeof(v) __value = (v); \
3232 if (*view < __value) { \
3238 /** Declares the max reducer functions for a numeric type.
3240 * This macro expands into external function declarations for functions which implement
3241 * the reducer functionality for the max reducer type for a specified numeric type.
3243 * @param t The value type of the reducer.
3244 * @param tn The value "type name" identifier, used to construct the reducer type name,
3245 * function names, etc.
3247 #define CILK_C_REDUCER_MAX_DECLARATION(t,tn,id) \
3248 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MAX_TYPE(tn); \
3249 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max,tn,l,r); \
3250 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max,tn);
3252 /** Defines the max reducer functions for a numeric type.
3254 * This macro expands into function definitions for functions which implement the
3255 * reducer functionality for the max reducer type for a specified numeric type.
3257 * @param t The value type of the reducer.
3258 * @param tn The value "type name" identifier, used to construct the reducer type name,
3259 * function names, etc.
3261 #define CILK_C_REDUCER_MAX_DEFINITION(t,tn,id) \
3262 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MAX_TYPE(tn); \
3263 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max,tn,l,r) \
3264 { if (*(t*)l < *(t*)r) *(t*)l = *(t*)r; } \
3265 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max,tn) \
3269 /** @def CILK_C_REDUCER_MAX_INSTANCE
3270 * @brief Declare or define implementation functions for a reducer type.
3272 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and
3273 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS`
3274 * will be undefined, and this macro will expand into external declarations for the functions.
3276 #ifdef CILK_C_DEFINE_REDUCERS
3277 # define CILK_C_REDUCER_MAX_INSTANCE(t,tn,id) \
3278 CILK_C_REDUCER_MAX_DEFINITION(t,tn,id)
3280 # define CILK_C_REDUCER_MAX_INSTANCE(t,tn,id) \
3281 CILK_C_REDUCER_MAX_DECLARATION(t,tn,id)
3285 /* Declare or define an instance of the reducer type and its functions for each
3288 __CILKRTS_BEGIN_EXTERN_C
3289 CILK_C_REDUCER_MAX_INSTANCE(char, char, CHAR_MIN
)
3290 CILK_C_REDUCER_MAX_INSTANCE(unsigned char, uchar
, 0)
3291 CILK_C_REDUCER_MAX_INSTANCE(signed char, schar
, SCHAR_MIN
)
3292 CILK_C_REDUCER_MAX_INSTANCE(wchar_t, wchar_t, WCHAR_MIN
)
3293 CILK_C_REDUCER_MAX_INSTANCE(short, short, SHRT_MIN
)
3294 CILK_C_REDUCER_MAX_INSTANCE(unsigned short, ushort
, 0)
3295 CILK_C_REDUCER_MAX_INSTANCE(int, int, INT_MIN
)
3296 CILK_C_REDUCER_MAX_INSTANCE(unsigned int, uint
, 0)
3297 CILK_C_REDUCER_MAX_INSTANCE(unsigned int, unsigned, 0) // alternate name
3298 CILK_C_REDUCER_MAX_INSTANCE(long, long, LONG_MIN
)
3299 CILK_C_REDUCER_MAX_INSTANCE(unsigned long, ulong
, 0)
3300 CILK_C_REDUCER_MAX_INSTANCE(long long, longlong
, LLONG_MIN
)
3301 CILK_C_REDUCER_MAX_INSTANCE(unsigned long long, ulonglong
, 0)
3302 CILK_C_REDUCER_MAX_INSTANCE(float, float, -HUGE_VALF
)
3303 CILK_C_REDUCER_MAX_INSTANCE(double, double, -HUGE_VAL
)
3304 CILK_C_REDUCER_MAX_INSTANCE(long double, longdouble
, -HUGE_VALL
)
3305 __CILKRTS_END_EXTERN_C
3309 /** Max_index reducer type name.
3311 * This macro expands into the identifier which is the name of the max_index reducer
3312 * type for a specified numeric type.
3314 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3317 * @see @ref reducers_c_predefined
3319 #define CILK_C_REDUCER_MAX_INDEX_TYPE(tn) \
3320 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_,tn)
3322 /** Declares an op_max_index reducer object.
3324 * This macro expands into a declaration of a max_index reducer object for a specified
3325 * numeric type. For example:
3327 * CILK_C_REDUCER_MAX_INDEX(my_reducer, double, -DBL_MAX_INDEX);
3329 * @param obj The variable name to be used for the declared reducer object.
3330 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3332 * @param v The initial value for the reducer. (A value which can be assigned to the
3333 * numeric type represented by @a tn.)
3335 * @see @ref reducers_c_predefined
3337 #define CILK_C_REDUCER_MAX_INDEX(obj,tn,v) \
3338 CILK_C_REDUCER_MAX_INDEX_TYPE(tn) obj = \
3339 CILK_C_INIT_REDUCER(_Typeof(obj.value), \
3340 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_reduce_,tn), \
3341 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_identity_,tn), \
3342 __cilkrts_hyperobject_noop_destroy, {0, v})
3344 /** Maximizes with a value.
3346 * `CILK_C_REDUCER_MAX_INDEX_CALC(reducer, i, v)` sets the current view of the
3347 * reducer to the max of its previous value and a specified new value.
3348 * This is equivalent to
3350 * REDUCER_VIEW(reducer) = max_index(REDUCER_VIEW(reducer), v)
3352 * If the value of the reducer is changed to @a v, then the index of the reducer is
3355 * @param reducer The reducer whose contained value and index are to be updated.
3356 * @param i The index associated with the new value.
3357 * @param v The value that it is to be maximized with.
3359 #define CILK_C_REDUCER_MAX_INDEX_CALC(reducer, i, v) do { \
3360 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \
3361 _Typeof(v) __value = (v); \
3362 if (view->value < __value) { \
3363 view->index = (i); \
3364 view->value = __value; \
3369 /** Declares the max_index view type.
3371 * The view of a max_index reducer is a structure containing both the
3372 * maximum value for the reducer and the index that was associated with
3373 * that value in the sequence of input values.
3375 #define CILK_C_REDUCER_MAX_INDEX_VIEW(t,tn) \
3377 __STDNS ptrdiff_t index; \
3379 } __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn)
3381 /** Declares the max_index reducer functions for a numeric type.
3383 * This macro expands into external function declarations for functions which implement
3384 * the reducer functionality for the max_index reducer type for a specified numeric type.
3386 * @param t The value type of the reducer.
3387 * @param tn The value "type name" identifier, used to construct the reducer type name,
3388 * function names, etc.
3390 #define CILK_C_REDUCER_MAX_INDEX_DECLARATION(t,tn,id) \
3391 CILK_C_REDUCER_MAX_INDEX_VIEW(t,tn); \
3392 typedef CILK_C_DECLARE_REDUCER( \
3393 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn)) \
3394 CILK_C_REDUCER_MAX_INDEX_TYPE(tn); \
3395 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max_index,tn,l,r); \
3396 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max_index,tn);
3398 /** Defines the max_index reducer functions for a numeric type.
3400 * This macro expands into function definitions for functions which implement the
3401 * reducer functionality for the max_index reducer type for a specified numeric type.
3403 * @param t The value type of the reducer.
3404 * @param tn The value "type name" identifier, used to construct the reducer type name,
3405 * function names, etc.
3407 #define CILK_C_REDUCER_MAX_INDEX_DEFINITION(t,tn,id) \
3408 CILK_C_REDUCER_MAX_INDEX_VIEW(t,tn); \
3409 typedef CILK_C_DECLARE_REDUCER( \
3410 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn)) \
3411 CILK_C_REDUCER_MAX_INDEX_TYPE(tn); \
3412 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max_index,tn,l,r) \
3413 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn) view_t; \
3414 if (((view_t*)l)->value < ((view_t*)r)->value) \
3415 *(view_t*)l = *(view_t*)r; } \
3416 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max_index,tn) \
3417 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn) view_t; \
3418 ((view_t*)v)->index = 0; ((view_t*)v)->value = id; }
3421 /** @def CILK_C_REDUCER_MAX_INDEX_INSTANCE
3422 * @brief Declare or define implementation functions for a reducer type.
3424 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and
3425 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS`
3426 * will be undefined, and this macro will expand into external declarations for the functions.
3428 #ifdef CILK_C_DEFINE_REDUCERS
3429 # define CILK_C_REDUCER_MAX_INDEX_INSTANCE(t,tn,id) \
3430 CILK_C_REDUCER_MAX_INDEX_DEFINITION(t,tn,id)
3432 # define CILK_C_REDUCER_MAX_INDEX_INSTANCE(t,tn,id) \
3433 CILK_C_REDUCER_MAX_INDEX_DECLARATION(t,tn,id)
3437 /* Declares or defines an instance of the reducer type and its functions for each
3440 __CILKRTS_BEGIN_EXTERN_C
3441 CILK_C_REDUCER_MAX_INDEX_INSTANCE(char, char, CHAR_MIN
)
3442 CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned char, uchar
, 0)
3443 CILK_C_REDUCER_MAX_INDEX_INSTANCE(signed char, schar
, SCHAR_MIN
)
3444 CILK_C_REDUCER_MAX_INDEX_INSTANCE(wchar_t, wchar_t, WCHAR_MIN
)
3445 CILK_C_REDUCER_MAX_INDEX_INSTANCE(short, short, SHRT_MIN
)
3446 CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned short, ushort
, 0)
3447 CILK_C_REDUCER_MAX_INDEX_INSTANCE(int, int, INT_MIN
)
3448 CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned int, uint
, 0)
3449 CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned int, unsigned, 0) // alternate name
3450 CILK_C_REDUCER_MAX_INDEX_INSTANCE(long, long, LONG_MIN
)
3451 CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned long, ulong
, 0)
3452 CILK_C_REDUCER_MAX_INDEX_INSTANCE(long long, longlong
, LLONG_MIN
)
3453 CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned long long, ulonglong
, 0)
3454 CILK_C_REDUCER_MAX_INDEX_INSTANCE(float, float, -HUGE_VALF
)
3455 CILK_C_REDUCER_MAX_INDEX_INSTANCE(double, double, -HUGE_VAL
)
3456 CILK_C_REDUCER_MAX_INDEX_INSTANCE(long double, longdouble
, -HUGE_VALL
)
3457 __CILKRTS_END_EXTERN_C
3461 /** Declares min reducer type name.
3463 * This macro expands into the identifier which is the name of the min reducer
3464 * type for a specified numeric type.
3466 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3469 * @see @ref reducers_c_predefined
3471 #define CILK_C_REDUCER_MIN_TYPE(tn) \
3472 __CILKRTS_MKIDENT(cilk_c_reducer_min_,tn)
3474 /** Declares a min reducer object.
3476 * This macro expands into a declaration of a min reducer object for a specified numeric
3477 * type. For example:
3479 * CILK_C_REDUCER_MIN(my_reducer, double, DBL_MAX);
3481 * @param obj The variable name to be used for the declared reducer object.
3482 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3484 * @param v The initial value for the reducer. (A value which can be assigned to the
3485 * numeric type represented by @a tn.)
3487 * @see @ref reducers_c_predefined
3489 #define CILK_C_REDUCER_MIN(obj,tn,v) \
3490 CILK_C_REDUCER_MIN_TYPE(tn) obj = \
3491 CILK_C_INIT_REDUCER(_Typeof(obj.value), \
3492 __CILKRTS_MKIDENT(cilk_c_reducer_min_reduce_,tn), \
3493 __CILKRTS_MKIDENT(cilk_c_reducer_min_identity_,tn), \
3494 __cilkrts_hyperobject_noop_destroy, v)
3496 /** Minimizes with a value.
3498 * `CILK_C_REDUCER_MIN_CALC(reducer, v)` sets the current view of the
3499 * reducer to the min of its previous value and a specified new value.
3500 * This is equivalent to
3502 * REDUCER_VIEW(reducer) = min(REDUCER_VIEW(reducer), v)
3504 * @param reducer The reducer whose contained value is to be updated.
3505 * @param v The value that it is to be minimized with.
3507 #define CILK_C_REDUCER_MIN_CALC(reducer, v) do { \
3508 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \
3509 _Typeof(v) __value = (v); \
3510 if (*view > __value) { \
3516 /** Declares the min reducer functions for a numeric type.
3518 * This macro expands into external function declarations for functions which implement
3519 * the reducer functionality for the min reducer type for a specified numeric type.
3521 * @param t The value type of the reducer.
3522 * @param tn The value "type name" identifier, used to construct the reducer type name,
3523 * function names, etc.
3525 #define CILK_C_REDUCER_MIN_DECLARATION(t,tn,id) \
3526 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MIN_TYPE(tn); \
3527 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min,tn,l,r); \
3528 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min,tn);
3530 /** Defines the min reducer functions for a numeric type.
3532 * This macro expands into function definitions for functions which implement the
3533 * reducer functionality for the min reducer type for a specified numeric type.
3535 * @param t The value type of the reducer.
3536 * @param tn The value "type name" identifier, used to construct the reducer type name,
3537 * function names, etc.
3539 #define CILK_C_REDUCER_MIN_DEFINITION(t,tn,id) \
3540 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MIN_TYPE(tn); \
3541 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min,tn,l,r) \
3542 { if (*(t*)l > *(t*)r) *(t*)l = *(t*)r; } \
3543 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min,tn) \
3547 /** @def CILK_C_REDUCER_MIN_INSTANCE
3548 * @brief Declare or define implementation functions for a reducer type.
3550 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and
3551 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS`
3552 * will be undefined, and this macro will expand into external declarations for the functions.
3554 #ifdef CILK_C_DEFINE_REDUCERS
3555 # define CILK_C_REDUCER_MIN_INSTANCE(t,tn,id) \
3556 CILK_C_REDUCER_MIN_DEFINITION(t,tn,id)
3558 # define CILK_C_REDUCER_MIN_INSTANCE(t,tn,id) \
3559 CILK_C_REDUCER_MIN_DECLARATION(t,tn,id)
3563 /* Declares or defines an instance of the reducer type and its functions for each
3566 __CILKRTS_BEGIN_EXTERN_C
3567 CILK_C_REDUCER_MIN_INSTANCE(char, char, CHAR_MAX
)
3568 CILK_C_REDUCER_MIN_INSTANCE(unsigned char, uchar
, CHAR_MAX
)
3569 CILK_C_REDUCER_MIN_INSTANCE(signed char, schar
, SCHAR_MAX
)
3570 CILK_C_REDUCER_MIN_INSTANCE(wchar_t, wchar_t, WCHAR_MAX
)
3571 CILK_C_REDUCER_MIN_INSTANCE(short, short, SHRT_MAX
)
3572 CILK_C_REDUCER_MIN_INSTANCE(unsigned short, ushort
, USHRT_MAX
)
3573 CILK_C_REDUCER_MIN_INSTANCE(int, int, INT_MAX
)
3574 CILK_C_REDUCER_MIN_INSTANCE(unsigned int, uint
, UINT_MAX
)
3575 CILK_C_REDUCER_MIN_INSTANCE(unsigned int, unsigned, UINT_MAX
) // alternate name
3576 CILK_C_REDUCER_MIN_INSTANCE(long, long, LONG_MAX
)
3577 CILK_C_REDUCER_MIN_INSTANCE(unsigned long, ulong
, ULONG_MAX
)
3578 CILK_C_REDUCER_MIN_INSTANCE(long long, longlong
, LLONG_MAX
)
3579 CILK_C_REDUCER_MIN_INSTANCE(unsigned long long, ulonglong
, ULLONG_MAX
)
3580 CILK_C_REDUCER_MIN_INSTANCE(float, float, HUGE_VALF
)
3581 CILK_C_REDUCER_MIN_INSTANCE(double, double, HUGE_VAL
)
3582 CILK_C_REDUCER_MIN_INSTANCE(long double, longdouble
, HUGE_VALL
)
3583 __CILKRTS_END_EXTERN_C
3587 /** Declares `min_index` reducer type name.
3589 * This macro expands into the identifier which is the name of the min_index reducer
3590 * type for a specified numeric type.
3592 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3595 * @see @ref reducers_c_predefined
3597 #define CILK_C_REDUCER_MIN_INDEX_TYPE(tn) \
3598 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_,tn)
3600 /** Declares an op_min_index reducer object.
3602 * This macro expands into a declaration of a min_index reducer object for a specified
3603 * numeric type. For example:
3605 * CILK_C_REDUCER_MIN_INDEX(my_reducer, double, -DBL_MIN_INDEX);
3607 * @param obj The variable name to be used for the declared reducer object.
3608 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the
3610 * @param v The initial value for the reducer. (A value which can be assigned to the
3611 * numeric type represented by @a tn.)
3613 * @see @ref reducers_c_predefined
3615 #define CILK_C_REDUCER_MIN_INDEX(obj,tn,v) \
3616 CILK_C_REDUCER_MIN_INDEX_TYPE(tn) obj = \
3617 CILK_C_INIT_REDUCER(_Typeof(obj.value), \
3618 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_reduce_,tn), \
3619 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_identity_,tn), \
3620 __cilkrts_hyperobject_noop_destroy, {0, v})
3622 /** Minimizes with a value.
3624 * `CILK_C_REDUCER_MIN_INDEX_CALC(reducer, i, v)` sets the current view of the
3625 * reducer to the min of its previous value and a specified new value.
3626 * This is equivalent to
3628 * REDUCER_VIEW(reducer) = min_index(REDUCER_VIEW(reducer), v)
3630 * If the value of the reducer is changed to @a v, then the index of the reducer is
3633 * @param reducer The reducer whose contained value and index are to be updated.
3634 * @param i The index associated with the new value.
3635 * @param v The value that it is to be minimized with.
3637 #define CILK_C_REDUCER_MIN_INDEX_CALC(reducer, i, v) do { \
3638 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \
3639 _Typeof(v) __value = (v); \
3640 if (view->value > __value) { \
3641 view->index = (i); \
3642 view->value = __value; \
3647 /** Declares the min_index view type.
3649 * The view of a min_index reducer is a structure containing both the
3650 * minimum value for the reducer and the index that was associated with
3651 * that value in the sequence of input values.
3653 #define CILK_C_REDUCER_MIN_INDEX_VIEW(t,tn) \
3655 __STDNS ptrdiff_t index; \
3657 } __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn)
3659 /** Declares the min_index reducer functions for a numeric type.
3661 * This macro expands into external function declarations for functions which implement
3662 * the reducer functionality for the min_index reducer type for a specified numeric type.
3664 * @param t The value type of the reducer.
3665 * @param tn The value "type name" identifier, used to construct the reducer type name,
3666 * function names, etc.
3668 #define CILK_C_REDUCER_MIN_INDEX_DECLARATION(t,tn,id) \
3669 CILK_C_REDUCER_MIN_INDEX_VIEW(t,tn); \
3670 typedef CILK_C_DECLARE_REDUCER( \
3671 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn)) \
3672 CILK_C_REDUCER_MIN_INDEX_TYPE(tn); \
3673 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min_index,tn,l,r); \
3674 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min_index,tn);
3676 /** Defines the min_index reducer functions for a numeric type.
3678 * This macro expands into function definitions for functions which implement the
3679 * reducer functionality for the min_index reducer type for a specified numeric type.
3681 * @param t The value type of the reducer.
3682 * @param tn The value "type name" identifier, used to construct the reducer type name,
3683 * function names, etc.
3685 #define CILK_C_REDUCER_MIN_INDEX_DEFINITION(t,tn,id) \
3686 CILK_C_REDUCER_MIN_INDEX_VIEW(t,tn); \
3687 typedef CILK_C_DECLARE_REDUCER( \
3688 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn)) \
3689 CILK_C_REDUCER_MIN_INDEX_TYPE(tn); \
3690 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min_index,tn,l,r) \
3691 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn) view_t; \
3692 if (((view_t*)l)->value > ((view_t*)r)->value) \
3693 *(view_t*)l = *(view_t*)r; } \
3694 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min_index,tn) \
3695 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn) view_t; \
3696 ((view_t*)v)->index = 0; ((view_t*)v)->value = id; }
3699 /** @def CILK_C_REDUCER_MIN_INDEX_INSTANCE
3700 * @brief Declares or defines implementation functions for a reducer type.
3702 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and
3703 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS`
3704 * will be undefined, and this macro will expand into external declarations for the functions.
3706 #ifdef CILK_C_DEFINE_REDUCERS
3707 # define CILK_C_REDUCER_MIN_INDEX_INSTANCE(t,tn,id) \
3708 CILK_C_REDUCER_MIN_INDEX_DEFINITION(t,tn,id)
3710 # define CILK_C_REDUCER_MIN_INDEX_INSTANCE(t,tn,id) \
3711 CILK_C_REDUCER_MIN_INDEX_DECLARATION(t,tn,id)
3715 /* Declares or defines an instance of the reducer type and its functions for each
3718 __CILKRTS_BEGIN_EXTERN_C
3719 CILK_C_REDUCER_MIN_INDEX_INSTANCE(char, char, CHAR_MAX
)
3720 CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned char, uchar
, CHAR_MAX
)
3721 CILK_C_REDUCER_MIN_INDEX_INSTANCE(signed char, schar
, SCHAR_MAX
)
3722 CILK_C_REDUCER_MIN_INDEX_INSTANCE(wchar_t, wchar_t, WCHAR_MAX
)
3723 CILK_C_REDUCER_MIN_INDEX_INSTANCE(short, short, SHRT_MAX
)
3724 CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned short, ushort
, USHRT_MAX
)
3725 CILK_C_REDUCER_MIN_INDEX_INSTANCE(int, int, INT_MAX
)
3726 CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned int, uint
, UINT_MAX
)
3727 CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned int, unsigned, UINT_MAX
) // alternate name
3728 CILK_C_REDUCER_MIN_INDEX_INSTANCE(long, long, LONG_MAX
)
3729 CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned long, ulong
, ULONG_MAX
)
3730 CILK_C_REDUCER_MIN_INDEX_INSTANCE(long long, longlong
, LLONG_MAX
)
3731 CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned long long, ulonglong
, ULLONG_MAX
)
3732 CILK_C_REDUCER_MIN_INDEX_INSTANCE(float, float, HUGE_VALF
)
3733 CILK_C_REDUCER_MIN_INDEX_INSTANCE(double, double, HUGE_VAL
)
3734 CILK_C_REDUCER_MIN_INDEX_INSTANCE(long double, longdouble
, HUGE_VALL
)
3735 __CILKRTS_END_EXTERN_C
3741 #endif // defined REDUCER_MIN_MAX_H_INCLUDED