1/* reducer_min_max.h -*- C++ -*- 2 * 3 * @copyright 4 * Copyright (C) 2009-2013, Intel Corporation 5 * All rights reserved. 6 * 7 * @copyright 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * * Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * * Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the 17 * distribution. 18 * * Neither the name of Intel Corporation nor the names of its 19 * contributors may be used to endorse or promote products derived 20 * from this software without specific prior written permission. 21 * 22 * @copyright 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 30 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY 33 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 * POSSIBILITY OF SUCH DAMAGE. 35 */ 36 37/** @file reducer_min_max.h 38 * 39 * @brief Defines classes for doing parallel minimum and maximum reductions. 40 * 41 * @ingroup ReducersMinMax 42 * 43 * @see ReducersMinMax 44 */ 45 46#ifndef REDUCER_MIN_MAX_H_INCLUDED 47#define REDUCER_MIN_MAX_H_INCLUDED 48 49#include <cilk/reducer.h> 50 51#ifdef __cplusplus 52 53#include <algorithm> 54#include <limits> 55 56/** @defgroup ReducersMinMax Minimum and Maximum Reducers 57 * 58 * Minimum and maximum reducers allow the computation of the minimum or 59 * maximum of a set of values in parallel. 60 * 61 * @ingroup Reducers 62 * 63 * You should be familiar with @ref pagereducers "Cilk reducers", described in 64 * file `reducers.md`, and particularly with @ref reducers_using, before trying 65 * to use the information in this file. 66 * 67 * @section redminmax_usage Usage Examples 68 * 69 * cilk::reducer< cilk::op_max<int> > rm; 70 * cilk_for (int i = 0; i < ARRAY_SIZE; ++i) 71 * { 72 * rm->calc_max(a[i]); // or *rm = cilk::max_of(*max, a[i]) 73 * } 74 * std::cout << "maximum value is " << rm.get_value() << std::endl; 75 * 76 * and 77 * 78 * cilk::reducer< cilk::op_min_index<int, double> > rmi; 79 * cilk_for (int i = 0; i < ARRAY_SIZE; ++i) 80 * { 81 * rmi->calc_min(i, a[i]) // or *rmi = cilk::min_of(*rmi, i, a[i]); 82 * } 83 * std::cout << "minimum value a[" << rmi.get_value().first << "] = " 84 * << rmi.get_value().second << std::endl; 85 * 86 * @section redminmax_monoid The Monoid 87 * 88 * @subsection redminmax_monoid_values Value Set 89 * 90 * The value set of a minimum or maximum reducer is the set of values of 91 * `Type`, possibly augmented with a special identity value which is greater 92 * than (less than) any value of `Type`. 93 * 94 * @subsection redminmax_monoid_operator Operator 95 * 96 * In the most common case, the operator of a minimum reducer is defined as 97 * 98 * x MIN y == (x < y) ? x : y 99 * 100 * Thus, `a1 MIN a2 MIN ��� an` is the first `ai` which is not greater than any 101 * other `ai`. 102 * 103 * The operator of a maximum reducer is defined as 104 * 105 * x MAX y == (x > y) ? x : y 106 * 107 * Thus, `a1 MAX a2 MAX ��� an` is the first `ai` which is not less than any 108 * other `ai`. 109 * 110 * @subsection redminmax_monoid_comparators Comparators 111 * 112 * Min/max reducers are not limited to finding the minimum or maximum value 113 * determined by the `<` or `>` operator. In fact, all min/max reducers use a 114 * _comparator_, which is either a function or an object of a function class 115 * that defines a [strict weak ordering] 116 * (http://en.wikipedia.org/wiki/Strict_weak_ordering#Strict_weak_orderings) 117 * on a set of values. (This is exactly the same as the requirement for the 118 * comparison predicate for STL associative containers and sorting 119 * algorithms.) 120 * 121 * Just as with STL algorithms and containers, the comparator type parameter 122 * for min/max reducers is optional. If it is omitted, it defaults to 123 * `std::less`, which gives the behavior described in the previous section. 124 * Using non-default comparators (anything other than `std::less`) with 125 * min/max reducers is just like using them with STL containers and 126 * algorithms. 127 * 128 * Taking comparator objects into account, the reduction operation `MIN` for a 129 * minimum reducer is defined as 130 * 131 * x MIN y == compare(x, y) ? x : y 132 * 133 * where `compare()` is the reducer���s comparator. Similarly, the reduction 134 * operation MAX for a maximum reducer is defined as 135 * 136 * x MAX y == compare(y, x) ? x : y 137 * 138 * (If `compare(x, y) == x < y`, then `compare(y, x) == x > y`.) 139 * 140 * @subsection redminmax_monoid_identity Identity 141 * 142 * The identity value of the reducer is the value which is greater than (less 143 * than) any other value in the value set of the reducer. This is the 144 * [���special identity value���](#redminmax_monoid_values) if the reducer has 145 * one, or the largest (smallest) value in the value set otherwise. 146 * 147 * @section redminmax_index Value and Index Reducers 148 * 149 * Min/max reducers come in two families. The _value_ reducers, using `op_min` 150 * and `op_max` monoids, simply find the smallest or largest value from a set 151 * of values. The _index_ reducers, using `op_min_index` and `op_max_index` 152 * monoids, also record an index value associated with the first occurrence of 153 * the smallest or largest value. 154 * 155 * In the `%op_min_index` usage example [above](#redminmax_usage), the values 156 * are taken from an array, and the index of a value is the index of the array 157 * element it comes from. More generally, though, an index can be any sort of 158 * key which identifies a particular value in a collection of values. For 159 * example, if the values were taken from the nodes of a tree, then the 160 * ���index��� of a value might be a pointer to the node containing that value. 161 * 162 * A min/max index reducer is essentially the same as a min/max value reducer 163 * whose value type is an (index, value) pair, and whose comparator ignores 164 * the index part of the pair. (index, value) pairs are represented by 165 * `std::pair<Index, Type>` objects. This has the consequence that wherever 166 * the interface of a min/max value reducer has a `Type`, the interface of the 167 * corresponding min/max index reducer has a `std::pair<Index, Type>`. (There 168 * are convenience variants of the `reducer(Type)` constructor and the 169 * `calc_min()`, `calc_max()`, `%min_of()`, and `%max_of()` functions that 170 * take an index argument and a value argument instead of an index/value 171 * pair.) 172 * 173 * @section redminmax_operations Operations 174 * 175 * @subsection redminmax_constructors Constructors 176 * 177 * @subsubsection redminmax_constructors_value Min/Max Value Reducers 178 * 179 * reducer() // identity 180 * reducer(const Compare& compare) // identity 181 * reducer(const Type& value) 182 * reducer(move_in(Type& variable)) 183 * reducer(const Type& value, const Compare& compare) 184 * reducer(move_in(Type& variable), const Compare& compare) 185 * 186 * @subsubsection redminmax_constructors_index Min/Max Index Reducers 187 * 188 * reducer() // identity 189 * reducer(const Compare& compare) // identity 190 * reducer(const std::pair<Index, Type>& pair) 191 * reducer(const Index& index, const Type& value) 192 * reducer(move_in(std::pair<Index, Type>& variable)) 193 * reducer(const std::pair<Index, Type>& pair, const Compare& compare) 194 * reducer(const Index& index, const Type& value, const Compare& compare) 195 * reducer(move_in(std::pair<Index, Type>& variable), const Compare& compare) 196 * 197 * @subsection redminmax_get_set Set and Get 198 * 199 * r.set_value(const Type& value) 200 * Type = r.get_value() const 201 * r.move_in(Type& variable) 202 * r.move_out(Type& variable) 203 * 204 * Note that for an index reducer, the `Type` in these operations is actually a 205 * `std::pair<Index, Type>`. (See @ref redminmax_index.) There is _not_ a 206 * `set_value(value, index)` operation. 207 * 208 * @subsection redminmax_initial Initial Values and is_set() 209 * 210 * A minimum or maximum reducer without a specified initial value, before any 211 * MIN or MAX operation has been performed on it, represents the [identity 212 * value](#redminmax_monoid_identity) of its monoid. For value reducers with a 213 * numeric type and default comparator (`std::less`), this will be a well 214 * defined value. For example, 215 * 216 * reducer< op_max<unsigned> > r1; 217 * // r1.get_value() == 0 218 * 219 * reducer< op_min<float> > r2; 220 * // r2.get_value() == std::numeric_limits<float>::infinity 221 * 222 * In other cases, though (index reducers, non-numeric types, or non-default 223 * comparators), the actual identity value for the monoid may be unknown, or 224 * it may not even be a value of the reducer���s type. For example, there is no 225 * ���largest string��� to serve as the initial value for a 226 * `reducer< op_min<std::string> >`. In these cases, the result of calling 227 * `get_value()` is undefined. 228 * 229 * To avoid calling `get_value()` when its result is undefined, you can call 230 * the view���s `is_set()` function, which will return true if the reducer 231 * has a well-defined value ��� either because a MIN or MAX operation has been 232 * performed, or because it had a well-defined initial value: 233 * 234 * reducer< op_max<unsigned> > r1; 235 * // r1->is_set() == true 236 * // r1.get_value() == 0 237 * 238 * reducer< op_min<std::string> > r2; 239 * // r2->is_set() == false 240 * // r2.get_value() is undefined 241 * r2->calc_min("xyzzy"); 242 * // r2->is_set() == true 243 * // r2.get_value() == "xyzzy" 244 * 245 * > Note: For an index reducer without a specified initial value, the 246 * > initial value of the index is the default value of the `Index` type. 247 * 248 * @subsection redminmax_view_ops View Operations 249 * 250 * The basic reduction operation is `x = x MIN a` for a minimum reducer, or 251 * `x = x MAX a` for a maximum reducer. The basic syntax for these operations 252 * uses the `calc_min()` and `calc_max()` member functions of the view class. 253 * An assignment syntax is also provided, using the %cilk::min_of() and 254 * %cilk::max_of() global functions: 255 * 256 * Class | Modifier | Assignment 257 * ---------------|---------------------|----------- 258 * `op_min` | `r->calc_min(x)` | `*r = min_of(*r, x)` or `*r = min_of(x, *r)` 259 * `op_max` | `r->calc_max(x)` | `*r = max_of(*r, x)` or `*r = max_of(x, *r)` 260 * `op_min_index` | `r->calc_min(i, x)` | `*r = min_of(*r, i, x)` or `*r = min_of(i, x, *r)` 261 * `op_max_index` | `r->calc_max(i, x)` | `*r = max_of(*r, i, x)` or `*r = max_of(i, x, *r)` 262 * 263 * Wherever an ���`i`, `x`��� argument pair is shown in the table above, a single 264 * pair argument may be passed instead. For example: 265 * 266 * Index index; 267 * Type value; 268 * std::pair<Index, Type> ind_val(index, value); 269 * // The following statements are all equivalent. 270 * r->calc_min(index, value); 271 * r->calc_min(ind_val); 272 * *r = min_of(*r, index, value); 273 * *r = min_of(*r, ind_val); 274 * 275 * The `calc_min()` and `calc_max()` member functions return a reference to 276 * the view, so they can be chained: 277 * 278 * r->calc_max(x).calc_max(y).calc_max(z); 279 * 280 * In a `%min_of()` or `%max_of()` assignment, the view on the left-hand side 281 * of the assignment must be the same as the view argument in the call. 282 * Otherwise, the behavior is undefined (but an assertion error will occur if 283 * the code is compiled with debugging enabled). 284 * 285 * *r = max_of(*r, x); // OK 286 * *r1 = max_of(*r2, y); // ERROR 287 * 288 * `%min_of()` and `%max_of()` calls can be nested: 289 * 290 * *r = max_of(max_of(max_of(*r, x), y), z); 291 * *r = min_of(i, a[i], min_of(j, a[j], min_of(k, a[k], *r))); 292 * 293 * @section redminmax_compatibility Compatibility Issues 294 * 295 * Most Cilk library reducers provide 296 * * Binary compatibility between `reducer_KIND` reducers compiled with Cilk 297 * library version 0.9 (distributed with Intel�� C++ Composer XE version 298 * 13.0 and earlier) and the same reducers compiled with Cilk library 299 * version 1.0 and later. 300 * * Transparent casting between references to `reducer<op_KIND>` and 301 * `reducer_KIND`. 302 * 303 * This compatibility is not available in all cases for min/max reducers. 304 * There are two areas of incompatibility. 305 * 306 * @subsection redminmax_compatibility_stateful Non-empty Comparators 307 * 308 * There is no way to provide binary compatibility between the 0.9 and 1.0 309 * definitions of min/max reducers that use a non-empty comparator class or a 310 * comparator function. (Empty comparator classes like `std::less` are not a 311 * problem.) 312 * 313 * To avoid run-time surprises, the legacy `reducer_{min|max}[_index]` classes 314 * have been coded in the 1.0 library so that they will not even compile when 315 * instantiated with a non-empty comparator class. 316 * 317 * @subsection redminmax_compatibility_optimized Numeric Optimization 318 * 319 * Min/max reducers with a numeric value type and the default comparator can 320 * be implemented slightly more efficiently than other min/max reducers. 321 * However, the optimization is incompatible with the 0.9 library 322 * implementation of min/max reducers. 323 * 324 * The default min/max reducers implementation in the 1.0 library uses this 325 * numeric optimization. Code using legacy reducers compiled with the 1.0 326 * library can be safely used in the same program as code compiled with the 327 * 0.9 library, but classes compiled with the different Cilk libraries will be 328 * defined in different namespaces. 329 * 330 * The simplest solution is just to recompile the code that was compiled with 331 * the older version of Cilk. However, if this is impossible, you can define 332 * the `CILK_LIBRARY_0_9_REDUCER_MINMAX` macro (on the compiler command line, 333 * or in your source code before including `reducer_min_max.h`) when compiling 334 * with the new library. This will cause it to generate numeric reducers that 335 * will be less efficient, but will be fully compatible with previously 336 * compiled code. (Note that this macro has no effect on [the non-empty 337 * comparator incompatibility] (redminmax_compatibility_stateful).) 338 * 339 * @section redminmax_types Type Requirements 340 * 341 * `Type` and `Index` must be `Copy Constructible`, `Default Constructible`, 342 * and `Assignable`. 343 * 344 * `Compare` must be `Copy Constructible` if the reducer is constructed with a 345 * `compare` argument, and `Default Constructible` otherwise. 346 * 347 * The `Compare` function must induce a strict weak ordering on the elements 348 * of `Type`. 349 * 350 * @section redminmax_in_c Minimum and Maximum Reducers in C 351 * 352 * These macros can be used to do minimum and maximum reductions in C: 353 * 354 * Declaration | Type | Operation 355 * -----------------------------|-----------------------------------|---------- 356 * @ref CILK_C_REDUCER_MIN |@ref CILK_C_REDUCER_MIN_TYPE |@ref CILK_C_REDUCER_MIN_CALC 357 * @ref CILK_C_REDUCER_MAX |@ref CILK_C_REDUCER_MAX_TYPE |@ref CILK_C_REDUCER_MAX_CALC 358 * @ref CILK_C_REDUCER_MIN_INDEX |@ref CILK_C_REDUCER_MIN_INDEX_TYPE |@ref CILK_C_REDUCER_MIN_INDEX_CALC 359 * @ref CILK_C_REDUCER_MAX_INDEX |@ref CILK_C_REDUCER_MAX_INDEX_TYPE |@ref CILK_C_REDUCER_MAX_INDEX_CALC 360 * 361 * For example: 362 * 363 * CILK_C_REDUCER_MIN(r, int, INT_MAX); 364 * CILK_C_REGISTER_REDUCER(r); 365 * cilk_for(int i = 0; i != n; ++i) { 366 * CILK_C_REDUCER_MIN_CALC(r, a[i]); 367 * } 368 * CILK_C_UNREGISTER_REDUCER(r); 369 * printf("The smallest value in a is %d\n", REDUCER_VIEW(r)); 370 * 371 * 372 * CILK_C_REDUCER_MAX_INDEX(r, uint, 0); 373 * CILK_C_REGISTER_REDUCER(r); 374 * cilk_for(int i = 0; i != n; ++i) { 375 * CILK_C_REDUCER_MAX_INDEX_CALC(r, i, a[i]); 376 * } 377 * CILK_C_UNREGISTER_REDUCER(r); 378 * printf("The largest value in a is %u at %d\n", 379 * REDUCER_VIEW (r).value, REDUCER_VIEW(r).index); 380 * 381 * See @ref reducers_c_predefined. 382 */ 383 384namespace cilk { 385 386/** @defgroup ReducersMinMaxBinComp Binary compatibility 387 * 388 * If the macro CILK_LIBRARY_0_9_REDUCER_MINMAX is defined, then we generate 389 * reducer code and data structures which are binary-compatible with code that 390 * was compiled with the old min/max wrapper definitions, so we want the 391 * mangled names of the legacy min/max reducer wrapper classes to be the 392 * same as the names produced by the old definitions. 393 * 394 * Conversely, if the macro is not defined, then we generate binary- 395 * incompatible code, so we want different mangled names, to make sure that 396 * the linker does not allow new and old compiled legacy wrappers to be passed 397 * to one another. (Global variables are a different, and probably insoluble, 398 * problem.) 399 * 400 * Similarly, min/max classes compiled with and without 401 * CILK_LIBRARY_0_9_REDUCER_MINMAX are binary-incompatible, and must get 402 * different mangled names. 403 * 404 * The trick is, when compiling in normal (non-compatibility) mode, wrap 405 * everything in an extra namespace, and then `use` it into the top-level cilk 406 * namespace. Then 407 * 408 * * Classes and functions compiled in normal mode will be in 409 * different namespaces from the same classes and functions compiled in 410 * compatibility mode. 411 * * The legacy wrapper classes and functions will be in the same namespace 412 * as the same classes and functions compiled with the0.9 library if and 413 * only if the are compiled in compatibility mode. 414 * 415 * @ingroup ReducersMinMax 416 */ 417 418#ifndef CILK_LIBRARY_0_9_REDUCER_MINMAX 419/** Namespace to wrap min/max reducer definitions when not compiling in ���binary 420 * compatibility��� mode. 421 * 422 * By default, all of the min/max reducer definitions are defined in this 423 * namespace and then imported into namespace ::cilk, so that they do not 424 * clash with the legacy definitions with the same names. However, if the 425 * macro `CILK_LIBRARY_0_9_REDUCER_MINMAX` is defined, then the min/max 426 * definitions go directly into namespace ::cilk, so that, for example, 427 * cilk::reducer_max defined with the 1.0 library is equivalent (to the 428 * linker) to cilk::reducer_max defined with the 0.9 library. 429 * 430 * @ingroup ReducersMinMaxBinComp 431 * @ingroup ReducersMinMax 432 */ 433namespace cilk_lib_1_0 { 434#endif 435 436/** Namespace containing internal implementation classes and functions for 437 * min/max reducers. 438 * 439 * @ingroup ReducersMinMax 440 */ 441namespace min_max_internal { 442 443using ::cilk::internal::binary_functor; 444using ::cilk::internal::typed_indirect_binary_function; 445using ::cilk::internal::class_is_empty; 446 447/** @defgroup ReducersMinMaxIsSet The ���is_set optimization��� 448 * 449 * The obvious definition of the identity value for a max or min reducer is as 450 * the smallest (or largest) value of the value type. However, for an 451 * arbitrary comparator and/or an arbitrary value type, the largest / smallest 452 * value may not be known. It may not even be defined ��� what is the largest 453 * string? 454 * 455 * Therefore, min/max reducers represent their value internally as a pair 456 * `(value, is_set)`. When `is_set` is true, the pair represents the known 457 * value `value`; when `is_set` is false, the pair represents the identity 458 * value. 459 * 460 * This is an effective solution, but the most common use of min/max reducers 461 * is probably with numeric types and the default definition of minimum or 462 * maximum (using `std::less`), in which case there are well-defined, knowable 463 * smallest and largest values. Testing `is_set` for every comparison is then 464 * unnecessary and wasteful. 465 * 466 * The ���is_set optimization��� just means generating code that doesn���t use 467 * `is_set` when it isn���t needed. It is implemented using two metaprogramming 468 * classes: 469 * 470 * - do_is_set_optimization tests whether the optimization is applicable. 471 * - identity_value gets the appropriate identity value for a type. 472 * 473 * The is_set optimization is the reason that min/max reducers compiled with 474 * Cilk library 1.0 are binary-incompatible with the same reducers compiled 475 * with library 0.9, and therefore the optimization is suppressed when 476 * compiling in 477 * ReducersMinMaxBinComp "binary compatibility mode". 478 * 479 * @ingroup ReducersMinMax 480 */ 481 482/** Test whether the ReducersMinMaxIsSet "is_set optimization" is 483 * applicable. 484 * 485 * The @ref do_is_set_optimization class is used to test whether the is_set 486 * optimization should be applied for a particular reducer. It is instantiated 487 * with a value type and a comparator, and defines a boolean constant, 488 * `value`. Then `%do_is_set_optimization<Type, Comp>::%value` can be used as 489 * a boolean template parameter to control the specialization of another 490 * class. 491 * 492 * In ReducersMinMaxBinComp "binary compatibility mode", when the 493 * `CILK_LIBRARY_0_9_REDUCER_MINMAX` macro is defined, `value` will always 494 * be false. 495 * 496 * @tparam Type The value type for the reducer. 497 * @tparam Compare The comparator type for the reducer. 498 * 499 * @result The `value` data member will be `true` if @a Type is a numeric 500 * type, @a Compare is `std::less<Type>`, and 501 * `CILK_LIBRARY_0_9_REDUCER_MINMAX` is not defined. 502 * 503 * @see ReducersMinMaxIsSet 504 * @see @ref view_content 505 * 506 * @ingroup ReducersMinMaxIsSet 507 */ 508template < typename Type, 509 typename Compare > 510struct do_is_set_optimization 511{ 512 /// `True` if the is_set optimization should be applied to min/max reducers 513 /// with this value type and comparator; `false` otherwise. 514 static const bool value = false; 515}; 516 517#ifndef CILK_LIBRARY_0_9_REDUCER_MINMAX 518/// @cond 519template <typename Type> 520struct do_is_set_optimization<Type, std::less<Type> > 521{ 522 /// True in the special case where optimization is possible. 523 static const bool value = std::numeric_limits<Type>::is_specialized; 524}; 525/// @endcond 526#endif 527 528 529/** Get the identity value when using the ReducersMinMaxIsSet 530 * "is_set optimization". 531 * 532 * This class defines a function which assigns the appropriate identity value 533 * to a variable when the is_set optimization is applicable. 534 * 535 * @tparam Type The value type for the reducer. 536 * @tparam Compare The comparator type for the reducer. 537 * @tparam ForMax `true` to get the identity value for a max reducer (i.e., 538 * the smallest value of @a Type), `false` to get the identity 539 * value for a min reducer (i.e., the largest value of 540 * @a Type). 541 * 542 * @result If @a Type and @a Compare qualify for the is_set optimization, the 543 * `set_identity()' function will set its argument variable to the 544 * smallest or largest value of @a Type, depending on @a ForMax. 545 * Otherwise, `set_identity()` will be a no-op. 546 * 547 * @see ReducersMinMaxIsSet 548 * 549 * @ingroup ReducersMinMaxIsSet 550 * @see @ref view_content 551 */ 552template < typename Type, 553 typename Compare, 554 bool ForMax, 555 bool = std::numeric_limits<Type>::is_specialized, 556 bool = std::numeric_limits<Type>::has_infinity > 557struct identity_value { 558 /// Assign the identity value to the reference parameter. 559 static void set_identity(Type&) {} 560}; 561 562/// @cond 563template <typename Type> 564struct identity_value<Type, std::less<Type>, true, true, true> { 565 /// Floating max identity is negative infinity. 566 static void set_identity(Type& id) 567 { id = -std::numeric_limits<Type>::infinity(); } 568}; 569 570template <typename Type> 571struct identity_value<Type, std::less<Type>, true, true, false> { 572 /// Integer max identity is minimum value of type. 573 static void set_identity(Type& id) 574 { id = std::numeric_limits<Type>::min(); } 575}; 576 577template <typename Type> 578struct identity_value<Type, std::less<Type>, false, true, true> { 579 /// Floating min identity is positive infinity. 580 static void set_identity(Type& id) 581 { id = std::numeric_limits<Type>::infinity(); } 582}; 583 584template <typename Type> 585struct identity_value<Type, std::less<Type>, false, true, false> { 586 /// Integer min identity is maximum value of type. 587 static void set_identity(Type& id) 588 { id = std::numeric_limits<Type>::max(); } 589}; 590 591/// @endcond 592 593 594/** Adapter class to reverse the arguments of a predicate. 595 * 596 * Observe that: 597 * 598 * (x < y) == (y > x) 599 * max(x, y) == (x < y) ? y : x 600 * min(x, y) == (y < x) ? y : x == (x > y) ? y : x 601 * 602 * More generally, if `c` is a predicate defining a `Strict Weak Ordering`, 603 * and `c*(x, y) == c(y, x)`, then 604 * 605 * max(x, y, c) == c(x, y) ? y : x 606 * min(x, y, c) == c(y, x) ? y : x == c*(x, y) ? y : x == max(x, y, c*) 607 * 608 * For any predicate `C` with argument type `T`, the template class 609 * `%reverse_predicate<C, T>` defines a predicate which is identical to `C`, 610 * except that its arguments are reversed. Thus, for example, we could 611 * implement `%op_min_view<Type, Compare>` as 612 * `%op_max_view<Type, %reverse_predicate<Compare, Type> >`. 613 * (Actually, op_min_view and op_max_view are both implemented as subclasses 614 * of a common base class, view_base.) 615 * 616 * @note If `C` is an empty functor class, then `reverse_predicate(C)` will 617 * also be an empty functor class. 618 * 619 * @tparam Predicate The predicate whose arguments are to be reversed. 620 * @tparam Argument @a Predicate���s argument type. 621 * 622 * @ingroup ReducersMinMax 623 */ 624template <typename Predicate, 625 typename Argument = typename Predicate::first_argument_type> 626class reverse_predicate : private binary_functor<Predicate>::type { 627 typedef typename binary_functor<Predicate>::type base; 628public: 629 /// Default constructor 630 reverse_predicate() : base() {} 631 /// Constructor with predicate object 632 reverse_predicate(const Predicate& p) : base(p) {} 633 /// The reversed predicate operation 634 bool operator()(const Argument& x, const Argument& y) const 635 { return base::operator()(y, x); } 636}; 637 638 639/** Class to represent the comparator for a min/max view class. 640 * 641 * This class is intended to accomplish two objectives in the implementation 642 * of min/max views. 643 * 644 * 1. To minimize data bloat, when we have a reducer with a non-stateless 645 * comparator, we want to keep a single instance of the comparator object 646 * in the monoid, and just call it from the views. 647 * 2. In ReducersMinMaxBinComp "binary compatibility mode", views for 648 * reducers with a stateless comparator must have the same content as in 649 * Cilk library 0.9 ��� that is, they must contain only `value` and 650 * `is_set` data members. 651 * 652 * To achieve the first objective, we use the 653 * @ref internal::typed_indirect_binary_function class defined in 654 * metaprogramming.h to wrap a pointer to the actual comparator. If no 655 * pointer is needed because the actual comparator is stateless, the 656 * `typed_indirect_binary_function` class will be empty, too. 657 * 658 * To achieve the second objective, we make the 659 * `typed_indirect_binary_function` class a base class of the view rather than 660 * a data member, so the ���empty base class��� rule will ensure no that no 661 * additional space is allocated in the view unless it is needed. 662 * 663 * We could simply use typed_indirect_binary_function as the base class of the 664 * view, but this would mean writing comparisons as `(*this)(x, y)`, which is 665 * just weird. So, instead, we comparator_base as a subclass of 666 * typed_indirect_binary_function which provides function `compare()` 667 * as a synonym for `operator()`. 668 * 669 * @tparam Type The value type of the comparator class. 670 * @tparam Compare A predicate class. 671 * 672 * @see internal::typed_indirect_binary_function 673 * 674 * @ingroup ReducersMinMax 675 */ 676template <typename Type, typename Compare> 677class comparator_base : private typed_indirect_binary_function<Compare, Type, Type, bool> 678{ 679 typedef typed_indirect_binary_function<Compare, Type, Type, bool> base; 680protected: 681 comparator_base(const Compare* f) : base(f) {} ///< Constructor. 682 683 /// Comparison function. 684 bool compare(const Type& a, const Type& b) const 685 { 686 return base::operator()(a, b); 687 } 688 689 /// Get the comparator pointer. 690 const Compare* compare_pointer() const { return base::pointer(); } 691}; 692 693 694/** @defgroup ReducersMinMaxViewContent Content classes for min/max views 695 * 696 * @ingroup ReducersMinMax 697 * 698 * Minimum and maximum reducer view classes inherit from a ���view content��� 699 * class. The content class defines the actual data members for the view, 700 * and provides typedefs and member functions for accessing the data members 701 * as needed to support the view functionality. 702 * 703 * There are two content classes, which encapsulate the differences between 704 * simple min/max reducers and min/max with index reducers: 705 * 706 * - view_content 707 * - index_view_content 708 * 709 * @note An obvious, and arguably simpler, encapsulation strategy would be 710 * to just let the `Type` of a min/max view be an (index, value) pair 711 * structure for min_index and max_index reducers. Then all views 712 * would just have a `Type` data member and an `is_set` data member, 713 * and the comparator for min_index and max_index views could be 714 * customized to consider only the value component of the (index, 715 * value) `Type` pair. Unfortunately, this would break binary 716 * compatibility with reducer_max_index and reducer_min_index in 717 * Cilk library 0.9, because the memory layout of an (index, value) 718 * pair followed by a `bool` is different from the memory layout of an 719 * index data member followed by a value data member followed by a 720 * `bool` data member. The content class is designed to exactly 721 * replicate the layout of the views in library 0.9 reducers. 722 * 723 * A content class `C`, and its objects `c`, must define the following: 724 * 725 * Definition | Meaning 726 * ------------------------------------|-------- 727 * `C::value_type` | A typedef for `Type` of the view. (A `std::pair<Index, Type>` for min_index and max_index views). 728 * `C::comp_value_type` | A typedef for the type of value compared by the view���s `compare()` function. 729 * `C()` | Constructs the content with the identity value. 730 * `C(const value_type&)` | Constructs the content with a specified value. 731 * `c.is_set()` | Returns true if the content has a known value. 732 * `c.value()` | Returns the content���s value. 733 * `c.set_value(const value_type&)` | Sets the content���s value. (The value becomes known.) 734 * `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. 735 * `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. 736 * 737 * @see view_base 738 */ 739 740/** Content class for op_min_view and op_max_view. 741 * 742 * @tparam Type The value type of the op_min_view or op_max_view. 743 * @tparam Compare The comparator class specified for the op_min_view or 744 * op_max_view. (_Not_ the derived comparator class actually 745 * used by the view_base. For example, the view_content of an 746 * `op_min_view<int>` will have `Compare = std::less<int>`, 747 * but its comparator_base will have 748 * `Compare = reverse_predicate< std::less<int> >`.) 749 * @tparam ForMax `true` if this is the content class for an op_max_view, 750 * `false` if it is for an op_min_view. 751 * 752 * @note The general implementation of view_content uses an `is_set` data 753 * member. There is also a specialization which implements the 754 * ReducersMinMaxIsSet "is_set optimization". View classes that 755 * inherit from view_content do not need to know anything about the 756 * difference, though; the details are abstracted away in the 757 * view_content interface. 758 * 759 * @see ReducersMinMaxViewContent 760 * 761 * @ingroup ReducersMinMaxViewContent 762 * @ingroup ReducersMinMax 763 */ 764template < typename Type 765 , typename Compare 766 , bool ForMax 767 , bool = do_is_set_optimization<Type, Compare>::value 768 > 769class view_content { 770 Type m_value; 771 bool m_is_set; 772public: 773 /// The value type of the view. 774 typedef Type value_type; 775 776 /// The type compared by the view���s `compare()` function (which is the same 777 /// as the value type for view_content). 778 typedef Type comp_value_type; 779 780 /// Construct with the identity value. 781 view_content() : m_value(), m_is_set(false) {} 782 783 /// Construct with a defined value. 784 view_content(const value_type& value) : m_value(value), m_is_set(true) {} 785 786 /// Get the value. 787 value_type value() const { return m_value; } 788 789 /// Set the value. 790 void set_value(const value_type& value) 791 { 792 m_value = value; 793 m_is_set = true; 794 } 795 796 /// Get the comparison value (which is the same as the value for 797 /// view_content). 798 const comp_value_type& comp_value() const { return m_value; } 799 800 /// Given an arbitrary value, get the corresponding comparison value (which 801 /// is the same as the value for view_content). 802 static const comp_value_type& comp_value(const value_type& value) 803 { 804 return value; 805 } 806 807 /// Get a const reference to value part of the value (which is the same as 808 /// the value for view_content). 809 const Type& get_reference() const { return m_value; } 810 811 /// Get a const reference to the index part of the value (which is 812 /// meaningless for non-index reducers, but required for view_base. 813 const Type& get_index_reference() const { return m_value; } 814 815 /// Test if the value is defined. 816 bool is_set() const { return m_is_set; } 817}; 818 819/// @cond 820 821/* This is the specialization of the view_content class for cases where 822 * `AssumeIsSet` is true (i.e., where the is_set optimization is applicable). 823 */ 824template < typename Type 825 , typename Compare 826 , bool ForMax 827 > 828class view_content<Type, Compare, ForMax, true> { 829 typedef identity_value<Type, Compare, ForMax> Identity; 830 Type m_value; 831public: 832 typedef Type value_type; 833 typedef Type comp_value_type; 834 835 /// Construct with identity value. 836 view_content() { Identity::set_identity(m_value); } 837 838 view_content(const value_type& value) : m_value(value) {} 839 840 value_type value() const { return m_value; } 841 842 void set_value(const value_type& value) 843 { 844 m_value = value; 845 } 846 847 const comp_value_type& comp_value() const { return m_value; } 848 849 static const comp_value_type& comp_value(const value_type& value) 850 { 851 return value; 852 } 853 854 const Type& get_reference() const { return m_value; } 855 856 const Type& get_index_reference() const { return m_value; } 857 858 /// Test if the value is defined. 859 bool is_set() const { return true; } 860}; 861 862/// @endcond 863 864 865/** Content class for op_min_index_view and op_max_index_view. 866 * 867 * @tparam Index The index type of the op_min_index_view or 868 op_max_index_view. 869 * @tparam Type The value type of the op_min_view or op_max_view. (_Not_ 870 * the value type of the view, which will be 871 * `std::pair<Index, Type>`.) 872 * @tparam Compare The comparator class specified for the op_min_index_view or 873 * op_max_index_view. (_Not_ the derived comparator class 874 * actually used by the view_base. For example, the 875 * index_view_content of an `op_min_index_view<int>` will have 876 * `Compare = std::less<int>`, but its comparator_base will 877 * have `Compare = reverse_predicate< std::less<int> >`.) 878 * @tparam ForMax `true` if this is the content class for an 879 * op_max_index_view, `false` if it is for an 880 * op_min_index_view. 881 * 882 * @see ReducersMinMaxViewContent 883 * 884 * @ingroup ReducersMinMaxViewContent 885 * @ingroup ReducersMinMax 886 */ 887template < typename Index 888 , typename Type 889 , typename Compare 890 , bool ForMax 891 > 892class index_view_content { 893 typedef identity_value<Type, Compare, ForMax> Identity; 894 895 Index m_index; 896 Type m_value; 897 bool m_is_set; 898public: 899 /// The value type of the view (which is an <index, value> pair for 900 /// index_view_content). 901 typedef std::pair<Index, Type> value_type; 902 903 /// The type compared by the view���s `compare()` function (which is the data 904 /// value type for index_view_content). 905 typedef Type comp_value_type; 906 907 /// Construct with the identity value. 908 index_view_content() : m_index(), m_value(), m_is_set(false) {} 909 910 /// Construct with an index/value pair. 911 index_view_content(const value_type& value) : 912 m_index(value.first), m_value(value.second), m_is_set(true) {} 913 914 /// Construct with an index and a value. 915 index_view_content(const Index& index, const Type& value) : 916 m_index(index), m_value(value), m_is_set(true) {} 917 918 /// Construct with just an index. 919 index_view_content(const Index& index) : 920 m_index(index), m_value(), m_is_set(false) {} 921 922 /// Get the value. 923 value_type value() const { return value_type(m_index, m_value); } 924 925 /// Set value. 926 void set_value(const value_type& value) 927 { 928 m_index = value.first; 929 m_value = value.second; 930 m_is_set = true; 931 } 932 933 /// Get the comparison value (which is the value component of the 934 /// index/value pair for index_view_content). 935 const comp_value_type& comp_value() const { return m_value; } 936 937 /// Given an arbitrary value (i.e., index/value pair), get the 938 /// corresponding comparison value (which is the value component of the 939 /// index/value pair for index_view_content). 940 static const comp_value_type& comp_value(const value_type& value) 941 { return value.second; } 942 943 /// Get a const reference to value part of the value. 944 const Type& get_reference() const { return m_value; } 945 946 /// Get a const reference to the index part of the value. 947 const Index& get_index_reference() const { return m_index; } 948 949 /// Test if the value is defined. 950 bool is_set() const { return m_is_set; } 951}; 952 953 954template <typename View> class rhs_proxy; 955 956/** Create an rhs_proxy. 957 */ 958template <typename View> 959inline rhs_proxy<View> 960make_proxy(const typename View::value_type& value, const View& view); 961 962template <typename Content, typename Less, typename Compare> class view_base; 963 964 965/** Class to represent the right-hand side of 966 * `*reducer = {min|max}_of(*reducer, value)`. 967 * 968 * The only assignment operator for a min/max view class takes a rhs_proxy as 969 * its operand. This results in the syntactic restriction that the only 970 * expressions that can be assigned to a min/max view are ones which generate 971 * an rhs_proxy ��� that is, expressions of the form `max_of(view, value)` and 972 * `min_of(view, value)`. 973 * 974 * @warning 975 * The lhs and rhs views in such an assignment must be the same; otherwise, 976 * the behavior will be undefined. (I.e., `*r1 = min_of(*r1, x)` is legal; 977 * `*r1 = min_of(*r2, x)` is illegal.) This condition will be checked with a 978 * runtime assertion when compiled in debug mode. 979 * 980 * @tparam View The view class (op_{min|max}[_index]_view) that this proxy 981 * was created from. 982 * 983 * @see view_base 984 * 985 * @ingroup ReducersMinMax 986 */ 987template <typename View> 988class rhs_proxy { 989 typedef typename View::less_type less_type; 990 typedef typename View::compare_type compare_type; 991 typedef typename View::value_type value_type; 992 typedef typename View::content_type content_type; 993 typedef typename content_type::comp_value_type comp_value_type; 994 995 friend class view_base<content_type, less_type, compare_type>; 996 friend rhs_proxy make_proxy<View>( 997 const typename View::value_type& value, 998 const View& view); 999 1000 typed_indirect_binary_function< 1001 compare_type, comp_value_type, comp_value_type, bool> 1002 m_comp; 1003 const View* m_view; 1004 value_type m_value; 1005 1006 rhs_proxy& operator=(const rhs_proxy&); // Disable assignment operator 1007 rhs_proxy(); // Disable default constructor 1008 1009 // Constructor (called from view_base::make_proxy). 1010 rhs_proxy(const View* view, 1011 const value_type& value, 1012 const compare_type* compare) : 1013 m_view(view), m_value(value), m_comp(compare) {} 1014 1015 // Check matching view, then return value (called from view_base::assign). 1016 value_type value(const typename View::base* view) const 1017 { 1018 __CILKRTS_ASSERT(view == m_view); 1019 return m_value; 1020 } 1021 1022public: 1023 1024 /** Support max_of(max_of(view, value), value) and the like. 1025 */ 1026 rhs_proxy calc(const value_type& x) const 1027 { 1028 return rhs_proxy( 1029 m_view, 1030 m_comp( content_type::comp_value(m_value), 1031 content_type::comp_value(x) 1032 ) ? x : m_value, 1033 m_comp.pointer()); 1034 } 1035}; 1036 1037 1038template <typename View> 1039inline rhs_proxy<View> 1040make_proxy(const typename View::value_type& value, const View& view) 1041{ 1042 return rhs_proxy<View>(&view, value, view.compare_pointer()); 1043} 1044 1045//@} 1046 1047/** Base class for min and max view classes. 1048 * 1049 * This class accumulates the minimum or maximum of a set of values which have 1050 * occurred as arguments to the `calc()` function, as determined by a 1051 * comparator. The accumulated value will be the first `calc()` argument value 1052 * `x` such that `compare(x, y)` is false for every `calc()` argument value 1053 * `y`. 1054 * 1055 * If the comparator is `std::less`, then the accumulated value is the first 1056 * argument value which is not less than any other argument value, i.e., the 1057 * maximum. Similarly, if the comparator is `reverse_predicate<std::less>`, 1058 * which is equivalent to `std::greater`, then the accumulated value is the 1059 * first argument value which is not greater than any other argument value, 1060 * i.e., the minimum. 1061 * 1062 * @note This class provides the definitions that are required for a class 1063 * that will be used as the parameter of a 1064 * min_max_internal::monoid_base specialization. 1065 * 1066 * @tparam Content A content class that provides the value types and data 1067 * members for the view. 1068 * @tparam Less A ���less than��� binary predicate that defines the min or 1069 * max function. 1070 * @tparam Compare A binary predicate to be used to compare the values. 1071 * (The same as @a Less for max reducers; its reversal for 1072 * min reducers.) 1073 * 1074 * @see ReducersMinMaxViewContent 1075 * @see op_max_view 1076 * @see op_min_view 1077 * @see op_max_index_view 1078 * @see op_min_index_view 1079 * @see monoid_base 1080 * 1081 * @ingroup ReducersMinMax 1082 */ 1083template <typename Content, typename Less, typename Compare> 1084class view_base : 1085 // comparator_base comes first to ensure that it will get empty base class 1086 // treatment 1087 private comparator_base<typename Content::comp_value_type, Compare>, 1088 private Content 1089{ 1090 typedef comparator_base<typename Content::comp_value_type, Compare> base; 1091 using base::compare; 1092 using Content::value; 1093 using Content::set_value; 1094 using Content::comp_value; 1095 typedef Content content_type; 1096 1097 template <typename View> friend class rhs_proxy; 1098 template <typename View> 1099 friend rhs_proxy<View> make_proxy(const typename View::value_type& value, const View& view); 1100 1101public: 1102 1103 /** @name Monoid support. 1104 */ 1105 //@{ 1106 1107 /** Value type. Required by @ref monoid_with_view. 1108 */ 1109 typedef typename Content::value_type value_type; 1110 1111 /** The type of the comparator specified by the user, that defines the 1112 * ordering on @a Type. Required by min_max::monoid_base. 1113 */ 1114 typedef Less less_type; 1115 1116 /** The type of the comparator actually used by the view. Required by 1117 * min_max::monoid_base. (This is the same as the @ref less_type for a 1118 * max reducer, or `reverse_predicate<less_type>` for a min reducer.) 1119 */ 1120 typedef Compare compare_type; 1121 1122 /** Reduce operation. Required by @ref monoid_with_view. 1123 */ 1124 void reduce(view_base* other) 1125 { 1126 if ( other->is_set() && 1127 ( !this->is_set() || 1128 compare(this->comp_value(), other->comp_value()) ) ) 1129 { 1130 this->set_value(other->value()); 1131 } 1132 } 1133 1134 //@} 1135 1136 /** Default constructor. Initializes to identity value. 1137 */ 1138 explicit view_base(const compare_type* compare) : 1139 base(compare), Content() {} 1140 1141 /** Value constructor. 1142 */ 1143 template <typename T1> 1144 view_base(const T1& x1, const compare_type* compare) : 1145 base(compare), Content(x1) {} 1146 1147 /** Value constructor. 1148 */ 1149 template <typename T1, typename T2> 1150 view_base(const T1& x1, const T2& x2, const compare_type* compare) : 1151 base(compare), Content(x1, x2) {} 1152 1153 1154 /** Move-in constructor. 1155 */ 1156 explicit view_base(move_in_wrapper<value_type> w, const compare_type* compare) : 1157 base(compare), Content(w.value()) {} 1158 1159 /** @name Reducer support. 1160 */ 1161 //@{ 1162 1163 void view_move_in(value_type& v) { set_value(v); } 1164 void view_move_out(value_type& v) { v = value(); } 1165 void view_set_value(const value_type& v) { set_value(v); } 1166 value_type view_get_value() const { return value(); } 1167 // view_get_reference() NOT SUPPORTED 1168 1169 //@} 1170 1171 /** Is the value defined? 1172 */ 1173 using Content::is_set; 1174 1175 /** Reference to contained value data member. 1176 * @deprecated For legacy reducers only. 1177 */ 1178 using Content::get_reference; 1179 1180 /** Reference to contained index data member. 1181 * (Meaningless for non-index reducers.) 1182 * @deprecated For legacy reducers only. 1183 */ 1184 using Content::get_index_reference; 1185 1186protected: 1187 1188 /** Update the min/max value. 1189 */ 1190 void calc(const value_type& x) 1191 { 1192 if (!is_set() || compare(comp_value(), comp_value(x))) set_value(x); 1193 } 1194 1195 /** Assign the result of a `{min|max}_of(view, value)` expression to the 1196 * view. 1197 * 1198 * @see rhs_proxy 1199 */ 1200 template <typename View> 1201 void assign(const rhs_proxy<View>& rhs) 1202 { 1203 calc(rhs.value(this)); 1204 } 1205 1206}; 1207 1208 1209/** Base class for min and max monoid classes. 1210 * 1211 * The unique characteristic of minimum and maximum reducers is that they 1212 * incorporate a comparator functor that defines what ���minimum��� or ���maximum��� 1213 * means. The monoid for a reducer contains the comparator that will be used 1214 * for the reduction. If the comparator is a function or a class with state, 1215 * then each view will have a pointer to the comparator. 1216 * 1217 * This means that the `construct()` functions first construct the monoid 1218 * (possibly with an explicit comparator argument), and then construct the 1219 * view with a pointer to the monoid���s comparator. 1220 * 1221 * @tparam View The view class. 1222 * @tparam Align If true, reducers instantiated on this monoid will be 1223 * aligned. By default, library reducers (unlike legacy 1224 * library reducer _wrappers_) are unaligned. 1225 * 1226 * @see view_base 1227 * 1228 * @ingroup ReducersMinMax 1229 */ 1230template <typename View, bool Align = false> 1231class monoid_base : public monoid_with_view<View, Align> 1232{ 1233 typedef typename View::compare_type compare_type; 1234 typedef typename View::less_type less_type; 1235 const compare_type m_compare; 1236 1237 const compare_type* compare_pointer() const { return &m_compare; } 1238 1239 using cilk::monoid_base<typename View::value_type, View>::provisional; 1240 1241public: 1242 1243 /** Default constructor uses default comparator. 1244 */ 1245 monoid_base() : m_compare() {} 1246 1247 /** Constructor. 1248 * 1249 * @param compare The comparator to use. 1250 */ 1251 monoid_base(const compare_type& compare) : m_compare(compare) {} 1252 1253 /** Create an identity view. 1254 * 1255 * List view identity constructors take the list allocator as an argument. 1256 * 1257 * @param v The address of the uninitialized memory in which the view 1258 * will be constructed. 1259 */ 1260 void identity(View *v) const { ::new((void*) v) View(compare_pointer()); } 1261 1262 /** @name construct functions 1263 * 1264 * Min/max monoid `construct()` functions optionally take one or two value 1265 * arguments, a @ref move_in argument, and/or a comparator argument. 1266 */ 1267 //@{ 1268 1269 template <typename Monoid> 1270 static void construct(Monoid* monoid, View* view) 1271 { provisional( new ((void*)monoid) Monoid() ).confirm_if( 1272 new ((void*)view) View(monoid->compare_pointer()) ); } 1273 1274 template <typename Monoid, typename T1> 1275 static void construct(Monoid* monoid, View* view, const T1& x1) 1276 { provisional( new ((void*)monoid) Monoid() ).confirm_if( 1277 new ((void*)view) View(x1, monoid->compare_pointer()) ); } 1278 1279 template <typename Monoid, typename T1, typename T2> 1280 static void construct(Monoid* monoid, View* view, const T1& x1, const T2& x2) 1281 { provisional( new ((void*)monoid) Monoid() ).confirm_if( 1282 new ((void*)view) View(x1, x2, monoid->compare_pointer()) ); } 1283 1284 template <typename Monoid> 1285 static void construct(Monoid* monoid, View* view, const less_type& compare) 1286 { provisional( new ((void*)monoid) Monoid(compare) ).confirm_if( 1287 new ((void*)view) View(monoid->compare_pointer()) ); } 1288 1289 template <typename Monoid, typename T1> 1290 static void construct(Monoid* monoid, View* view, const T1& x1, const less_type& compare) 1291 { provisional( new ((void*)monoid) Monoid(compare) ).confirm_if( 1292 new ((void*)view) View(x1, monoid->compare_pointer()) ); } 1293 1294 template <typename Monoid, typename T1, typename T2> 1295 static void construct(Monoid* monoid, View* view, const T1& x1, const T2& x2, const less_type& compare) 1296 { provisional( new ((void*)monoid) Monoid(compare) ).confirm_if( 1297 new ((void*)view) View(x1, x2, monoid->compare_pointer()) ); } 1298 1299 //@} 1300}; 1301 1302} //namespace min_max_internal 1303 1304 1305/** @defgroup ReducersMinMaxMaxValue Maximum reducers (value only) 1306 * 1307 * These reducers will find the largest value from a set of values. 1308 * 1309 * @ingroup ReducersMinMax 1310 */ 1311//@{ 1312 1313/** The maximum reducer view class. 1314 * 1315 * This is the view class for reducers created with 1316 * `cilk::reducer< cilk::op_max<Type, Compare> >`. It accumulates the maximum, 1317 * as determined by a comparator, of a set of values which have occurred as 1318 * arguments to the `calc_max()` function. The accumulated value will be the 1319 * first argument `x` such that `compare(x, y)` is false for every argument 1320 * `y`. 1321 * 1322 * If the comparator is `std::less`, then the accumulated value is the first 1323 * argument value which is not less than any other argument value, i.e., the 1324 * maximum. 1325 * 1326 * @note The reducer ���dereference��� operation (`reducer::operator *()`) 1327 * yields a reference to the view. Thus, for example, the view class���s 1328 * `calc_max()` function would be used in an expression like 1329 * `r->calc_max(a)` where `r` is an op_max reducer variable. 1330 * 1331 * @tparam Type The type of the values compared by the reducer. This will 1332 * be the value type of a monoid_with_view that is 1333 * instantiated with this view. 1334 * @tparam Compare A `Strict Weak Ordering` whose argument type is @a Type. It 1335 * defines the ���less than��� relation used to compute the 1336 * maximum. 1337 * 1338 * @see ReducersMinMax 1339 * @see op_max 1340 */ 1341template <typename Type, typename Compare> 1342class op_max_view : public min_max_internal::view_base< 1343 min_max_internal::view_content<Type, Compare, true>, 1344 Compare, 1345 Compare> 1346{ 1347 typedef min_max_internal::view_base< 1348 min_max_internal::view_content<Type, Compare, true>, 1349 Compare, 1350 Compare> base; 1351 using base::calc; 1352 using base::assign; 1353 friend class min_max_internal::rhs_proxy<op_max_view>; 1354 1355public: 1356 1357 /** @name Constructors. 1358 * 1359 * All op_max_view constructors simply pass their arguments on to the 1360 * @ref view_base base class. 1361 */ 1362 //@{ 1363 1364 op_max_view() : base() {} 1365 1366 template <typename T1> 1367 op_max_view(const T1& x1) : base(x1) {} 1368 1369 template <typename T1, typename T2> 1370 op_max_view(const T1& x1, const T2& x2) : base(x1, x2) {} 1371 1372 //@} 1373 1374 /** @name View modifier operations. 1375 */ 1376 //@{ 1377 1378 /** Maximize with a value. 1379 * 1380 * If @a x is greater than the current value of the view (as defined by 1381 * the reducer���s comparator), or if the view was created without an 1382 * initial value and its value has never been updated (with `calc_max()` 1383 * or `= max_of()`), then the value of the view is set to @a x. 1384 * 1385 * @param x The value to maximize the view���s value with. 1386 * 1387 * @return A reference to the view. (Allows chaining 1388 * `view.comp_max(a).comp_max(b)���`.) 1389 */ 1390 op_max_view& calc_max(const Type& x) { calc(x); return *this; } 1391 1392 /** Assign the result of a `max_of(view, value)` expression to the view. 1393 * 1394 * @param rhs An rhs_proxy value created by a `max_of(view, value)` 1395 * expression. 1396 * 1397 * @return A reference to the view. 1398 * 1399 * @see min_max_internal::view_base::rhs_proxy 1400 */ 1401 op_max_view& operator=(const min_max_internal::rhs_proxy<op_max_view>& rhs) 1402 { assign(rhs); return *this; } 1403 1404 //@} 1405}; 1406 1407 1408/** Compute the maximum of the value in an op_max_view and another value. 1409 * 1410 * The result of this computation can only be assigned back to the original 1411 * view or used in another max_of() call. For example, 1412 * 1413 * *reducer = max_of(*reducer, x); 1414 * *reducer = max_of(x, *reducer); 1415 * 1416 * @see min_max_internal::rhs_proxy 1417 */ 1418template <typename Type, typename Compare> 1419inline min_max_internal::rhs_proxy< op_max_view<Type, Compare> > 1420max_of(const op_max_view<Type, Compare>& view, const Type& value) 1421{ 1422 return min_max_internal::make_proxy(value, view); 1423} 1424 1425/// @copydoc max_of(const op_max_view<Type, Compare>&, const Type&) 1426template <typename Type, typename Compare> 1427inline min_max_internal::rhs_proxy< op_max_view<Type, Compare> > 1428max_of(const Type& value, const op_max_view<Type, Compare>& view) 1429{ 1430 return min_max_internal::make_proxy(value, view); 1431} 1432 1433/** Nested maximum computation. 1434 * 1435 * Compute the maximum of the result of a max_of() call and another value. 1436 * 1437 * The result of this computation can only be assigned back to the original 1438 * view or wrapper, or used in another max_of() call. For example, 1439 * 1440 * *reducer = max_of(x, max_of(y, *reducer)); 1441 * wrapper = max_of(max_of(wrapper, x), y); 1442 * 1443 * @see min_max_internal::rhs_proxy 1444 */ 1445template <typename Type, typename Compare> 1446inline min_max_internal::rhs_proxy< op_max_view<Type, Compare> > 1447max_of(const min_max_internal::rhs_proxy< op_max_view<Type, Compare> >& proxy, 1448 const Type& value) 1449{ 1450 return proxy.calc(value); 1451} 1452 1453/// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_view<Type, Compare> >&, const Type&) 1454template <typename Type, typename Compare> 1455inline min_max_internal::rhs_proxy< op_max_view<Type, Compare> > 1456max_of(const Type& value, 1457 const min_max_internal::rhs_proxy< op_max_view<Type, Compare> >& proxy) 1458{ 1459 return proxy.calc(value); 1460} 1461 1462 1463/** Monoid class for maximum reductions. Instantiate the cilk::reducer template 1464 * class with an op_max monoid to create a maximum reducer class. For example, 1465 * to compute the maximum of a set of `int` values: 1466 * 1467 * cilk::reducer< cilk::op_max<int> > r; 1468 * 1469 * @see ReducersMinMax 1470 * @see op_max_view 1471 */ 1472template <typename Type, typename Compare=std::less<Type>, bool Align = false> 1473class op_max : 1474 public min_max_internal::monoid_base<op_max_view<Type, Compare>, Align> 1475{ 1476 typedef min_max_internal::monoid_base<op_max_view<Type, Compare>, Align> 1477 base; 1478public: 1479 /// Construct with default comparator. 1480 op_max() {} 1481 /// Construct with specified comparator. 1482 op_max(const Compare& compare) : base(compare) {} 1483}; 1484 1485//@} 1486 1487 1488/** @defgroup ReducersMinMaxMinValue Minimum reducers (value only) 1489 * 1490 * These reducers will find the smallest value from a set of values. 1491 * 1492 * @ingroup ReducersMinMax 1493 */ 1494//@{ 1495 1496/** The minimum reducer view class. 1497 * 1498 * This is the view class for reducers created with 1499 * `cilk::reducer< cilk::op_min<Type, Compare> >`. It accumulates the minimum, 1500 * as determined by a comparator, of a set of values which have occurred as 1501 * arguments to the `calc_min()` function. The accumulated value will be the 1502 * first argument `x` such that `compare(y, x)` is false for every argument 1503 * `y`. 1504 * 1505 * If the comparator is `std::less`, then the accumulated value is the first 1506 * argument value which no other argument value is less than, i.e., the 1507 * minimum. 1508 * 1509 * @note The reducer ���dereference��� operation (`reducer::operator *()`) 1510 * yields a reference to the view. Thus, for example, the view class���s 1511 * `calc_min()` function would be used in an expression like 1512 * `r->calc_min(a)` where `r` is an op_min reducer variable. 1513 * 1514 * @tparam Type The type of the values compared by the reducer. This will 1515 * be the value type of a monoid_with_view that is 1516 * instantiated with this view. 1517 * @tparam Compare A `Strict Weak Ordering` whose argument type is @a Type. It 1518 * defines the ���less than��� relation used to compute the 1519 * minimum. 1520 * 1521 * @see ReducersMinMax 1522 * @see op_min 1523 */ 1524template <typename Type, typename Compare> 1525class op_min_view : public min_max_internal::view_base< 1526 min_max_internal::view_content<Type, Compare, false>, 1527 Compare, 1528 min_max_internal::reverse_predicate<Compare, Type> > 1529{ 1530 typedef min_max_internal::view_base< 1531 min_max_internal::view_content<Type, Compare, false>, 1532 Compare, 1533 min_max_internal::reverse_predicate<Compare, Type> > base; 1534 using base::calc; 1535 using base::assign; 1536 friend class min_max_internal::rhs_proxy<op_min_view>; 1537 1538public: 1539 /** @name Constructors. 1540 * 1541 * All op_min_view constructors simply pass their arguments on to the 1542 * @ref view_base base class. 1543 */ 1544 //@{ 1545 1546 op_min_view() : base() {} 1547 1548 template <typename T1> 1549 op_min_view(const T1& x1) : base(x1) {} 1550 1551 template <typename T1, typename T2> 1552 op_min_view(const T1& x1, const T2& x2) : base(x1, x2) {} 1553 1554 //@} 1555 1556 /** @name View modifier operations. 1557 */ 1558 //@{ 1559 1560 /** Minimize with a value. 1561 * 1562 * If @a x is less than the current value of the view (as defined by the 1563 * reducer���s comparator), or if the view was created without an initial 1564 * value and its value has never been updated (with `calc_min()` or 1565 * `= min_of()`), then the value of the view is set to @a x. 1566 * 1567 * @param x The value to minimize the view���s value with. 1568 * 1569 * @return A reference to the view. (Allows chaining 1570 * `view.comp_min(a).comp_min(b)���`.) 1571 */ 1572 op_min_view& calc_min(const Type& x) { calc(x); return *this; } 1573 1574 /** Assign the result of a `min_of(view, value)` expression to the view. 1575 * 1576 * @param rhs An rhs_proxy value created by a `min_of(view, value)` 1577 * expression. 1578 * 1579 * @return A reference to the view. 1580 * 1581 * @see min_max_internal::view_base::rhs_proxy 1582 */ 1583 op_min_view& operator=(const min_max_internal::rhs_proxy<op_min_view>& rhs) 1584 { assign(rhs); return *this; } 1585}; 1586 1587 1588/** Compute the minimum of the value in a view and another value. 1589 * 1590 * The result of this computation can only be assigned back to the original 1591 * view or used in another min_of() call. For example, 1592 * 1593 * *reducer = min_of(*reducer, x); 1594 * *reducer = min_of(x, *reducer); 1595 * 1596 * @see min_max_internal::view_base::rhs_proxy 1597 */ 1598template <typename Type, typename Compare> 1599inline min_max_internal::rhs_proxy< op_min_view<Type, Compare> > 1600min_of(const op_min_view<Type, Compare>& view, const Type& value) 1601{ 1602 return min_max_internal::make_proxy(value, view); 1603} 1604 1605/// @copydoc min_of(const op_min_view<Type, Compare>&, const Type&) 1606template <typename Type, typename Compare> 1607inline min_max_internal::rhs_proxy< op_min_view<Type, Compare> > 1608min_of(const Type& value, const op_min_view<Type, Compare>& view) 1609{ 1610 return min_max_internal::make_proxy(value, view); 1611} 1612 1613/** Nested minimum computation. 1614 * 1615 * Compute the minimum of the result of a min_of() call and another value. 1616 * 1617 * The result of this computation can only be assigned back to the original 1618 * view or wrapper, or used in another min_of() call. For example, 1619 * 1620 * *reducer = min_of(x, min_of(y, *reducer)); 1621 * wrapper = min_of(min_of(wrapper, x), y); 1622 * 1623 * @see min_max_internal::rhs_proxy 1624 */ 1625template <typename Type, typename Compare> 1626inline min_max_internal::rhs_proxy< op_min_view<Type, Compare> > 1627min_of(const min_max_internal::rhs_proxy< op_min_view<Type, Compare> >& proxy, 1628 const Type& value) 1629{ 1630 return proxy.calc(value); 1631} 1632 1633/// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_view<Type, Compare> >&, const Type&) 1634template <typename Type, typename Compare> 1635inline min_max_internal::rhs_proxy< op_min_view<Type, Compare> > 1636min_of(const Type& value, 1637 const min_max_internal::rhs_proxy< op_min_view<Type, Compare> >& proxy) 1638{ 1639 return proxy.calc(value); 1640} 1641 1642 1643/** Monoid class for minimum reductions. Instantiate the cilk::reducer template 1644 * class with an op_min monoid to create a minimum reducer class. For example, 1645 * to compute the minimum of a set of `int` values: 1646 * 1647 * cilk::reducer< cilk::op_min<int> > r; 1648 * 1649 * @see ReducersMinMax 1650 * @see op_min_view 1651 */ 1652template <typename Type, typename Compare=std::less<Type>, bool Align = false> 1653class op_min : public min_max_internal::monoid_base<op_min_view<Type, Compare>, Align> { 1654 typedef min_max_internal::monoid_base<op_min_view<Type, Compare>, Align> base; 1655public: 1656 /// Construct with default comparator. 1657 op_min() {} 1658 /// Construct with specified comparator. 1659 op_min(const Compare& compare) : base(compare) {} 1660}; 1661 1662//@} 1663 1664 1665/** @defgroup ReducersMinMaxMaxIndex Maximum reducers (value and index) 1666 * 1667 * These reducers will find the largest value from a set of values, and its 1668 * index in the set. 1669 * 1670 * @ingroup ReducersMinMax 1671 */ 1672//@{ 1673 1674/** The maximum index reducer view class. 1675 * 1676 * This is the view class for reducers created with 1677 * `cilk::reducer< cilk::op_max_index<Index, Type, Compare> >`. It accumulates 1678 * the maximum, as determined by a comparator, of a set of values which have 1679 * occurred as arguments to the `calc_max()` function, and records the index 1680 * of the maximum value. The accumulated value will be the first argument `x` 1681 * such that `compare(x, y)` is false for every argument `y`. 1682 * 1683 * If the comparator is `std::less`, then the accumulated value is the first 1684 * argument value which is not less than any other argument value, i.e., the 1685 * maximum. 1686 * 1687 * @note The reducer ���dereference��� operation (`reducer::operator *()`) 1688 * yields a reference to the view. Thus, for example, the view class���s 1689 * `calc_max()` function would be used in an expression like 1690 * `r->calc_max(i, a)`where `r` is an op_max_index reducer 1691 * variable. 1692 * 1693 * @note The word ���index��� suggests an integer index into an array, but there 1694 * is no restriction on the index type or how it should be used. In 1695 * general, it may be convenient to use it for any kind of key that 1696 * can be used to locate the maximum value in the collection that it 1697 * came from ��� for example: 1698 * - An index into an array. 1699 * - A key into an STL map. 1700 * - An iterator into any STL container. 1701 * 1702 * @note A max_index reducer is essentially a max reducer whose value type 1703 * is a `std::pair<Index, Type>`. This fact is camouflaged in the view 1704 * `calc_max` function, the global `max_of` functions, and the reducer 1705 * value constructor, which can all take an index argument and a value 1706 * argument as an alternative to a single `std::pair` argument. 1707 * However, the reducer `set_value()`, `get_value()`, `move_in()`, and 1708 * `move_out()` functions work only with pairs, not with individual 1709 * value and/or index arguments. 1710 * 1711 * @tparam Index The type of the indices associated with the values. 1712 * @tparam Type The type of the values compared by the reducer. This will 1713 * be the value type of a monoid_with_view that is 1714 * instantiated with this view. 1715 * @tparam Compare Used to compare the values. It must be a binary predicate. 1716 * If it is omitted, then the view computes the conventional 1717 * arithmetic maximum. 1718 * 1719 * @see ReducersMinMax 1720 * @see op_max_index 1721 */ 1722template <typename Index, typename Type, typename Compare> 1723class op_max_index_view : public min_max_internal::view_base< 1724 min_max_internal::index_view_content<Index, Type, Compare, true>, 1725 Compare, 1726 Compare> 1727{ 1728 typedef min_max_internal::view_base< 1729 min_max_internal::index_view_content<Index, Type, Compare, true>, 1730 Compare, 1731 Compare> base; 1732 using base::calc; 1733 using base::assign; 1734 typedef std::pair<Index, Type> pair_type; 1735 friend class min_max_internal::rhs_proxy<op_max_index_view>; 1736 1737public: 1738 /** @name Constructors. 1739 * 1740 * All op_max_index_view constructors simply pass their arguments on to the 1741 * @ref view_base base class, except for the `(index, value [, compare])` 1742 * constructors, which create a `std::pair` containing the index and value. 1743 */ 1744 //@{ 1745 1746 op_max_index_view() : base() {} 1747 1748 template <typename T1> 1749 op_max_index_view(const T1& x1) : base(x1) {} 1750 1751 template <typename T1, typename T2> 1752 op_max_index_view(const T1& x1, const T2& x2) : base(x1, x2) {} 1753 1754 template <typename T1, typename T2, typename T3> 1755 op_max_index_view(const T1& x1, const T2& x2, const T3& x3) : base(x1, x2, x3) {} 1756 1757 op_max_index_view(const Index& i, const Type& v) : base(pair_type(i, v)) {} 1758 1759 op_max_index_view(const Index& i, const Type& v, const typename base::compare_type* c) : 1760 base(pair_type(i, v), c) {} 1761 1762 //@} 1763 1764 /** Maximize with a value and index. 1765 * 1766 * If @a x is greater than the current value of the view (as defined by 1767 * the reducer���s comparator), or if the view was created without an 1768 * initial value and its value has never been updated (with `calc_max()` 1769 * or `= max_of()`), then the value of the view is set to @a x, and the 1770 * index is set to @a i.. 1771 * 1772 * @param i The index of the value @a x. 1773 * @param x The value to maximize the view���s value with. 1774 * 1775 * @return A reference to the view. (Allows 1776 * `view.comp_max(i, a).comp_max(j, b)���`.) 1777 */ 1778 op_max_index_view& calc_max(const Index& i, const Type& x) 1779 { calc(pair_type(i, x)); return *this; } 1780 1781 /** Maximize with an index/value pair. 1782 * 1783 * If @a pair.second is greater than the current value of the view (as 1784 * defined by the reducer���s comparator), or if the view was created 1785 * without an initial value and its value has never been updated (with 1786 * `calc_max()` or `= max_of()`), then the value of the view is set to 1787 * @a pair.second, and the index is set to @a pair.first. 1788 * 1789 * @param pair A pair containing a value to maximize the view���s value 1790 * with and its associated index. 1791 * 1792 * @return A reference to the view. (Allows 1793 * `view.comp_max(p1).comp_max(p2)���`.) 1794 */ 1795 op_max_index_view& calc_max(const pair_type& pair) 1796 { calc(pair); return *this; } 1797 1798 /** Assign the result of a `max_of(view, index, value)` expression to the 1799 * view. 1800 * 1801 * @param rhs An rhs_proxy value created by a `max_of(view, index, value)` 1802 * expression. 1803 * 1804 * @return A reference to the view. 1805 * 1806 * @see min_max_internal::view_base::rhs_proxy 1807 */ 1808 op_max_index_view& operator=(const min_max_internal::rhs_proxy<op_max_index_view>& rhs) 1809 { assign(rhs); return *this; } 1810}; 1811 1812 1813/** Compute the maximum of the value in a view and another value. 1814 * 1815 * The result of this computation can only be assigned back to the original 1816 * view or used in another max_of() call. For example, 1817 * 1818 * *reducer = max_of(*reducer, i, x); 1819 * *reducer = max_of(i, x, *reducer); 1820 * 1821 * @see min_max_internal::rhs_proxy 1822 */ 1823template <typename Index, typename Type, typename Compare> 1824inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1825max_of(const op_max_index_view<Index, Type, Compare>& view, 1826 const Index& index, const Type& value) 1827{ 1828 return min_max_internal::make_proxy(std::pair<Index, Type>(index, value), view); 1829} 1830 1831/// @copydoc max_of(const op_max_index_view<Index, Type, Compare>&, const Index&, const Type&) 1832template <typename Index, typename Type, typename Compare> 1833inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1834max_of(const Index& index, const Type& value, 1835 const op_max_index_view<Index, Type, Compare>& view) 1836{ 1837 return min_max_internal::make_proxy(std::pair<Index, Type>(index, value), view); 1838} 1839 1840/// @copydoc max_of(const op_max_index_view<Index, Type, Compare>&, const Index&, const Type&) 1841template <typename Index, typename Type, typename Compare> 1842inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1843max_of(const op_max_index_view<Index, Type, Compare>& view, 1844 const std::pair<Index, Type>& pair) 1845{ 1846 return min_max_internal::make_proxy(pair, view); 1847} 1848 1849/// @copydoc max_of(const op_max_index_view<Index, Type, Compare>&, const Index&, const Type&) 1850template <typename Index, typename Type, typename Compare> 1851inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1852max_of(const std::pair<Index, Type>& pair, 1853 const op_max_index_view<Index, Type, Compare>& view) 1854{ 1855 return min_max_internal::make_proxy(pair, view); 1856} 1857 1858/** Nested computation of the maximum of the value in a view and other values. 1859 * 1860 * Compute the maximum of the result of a max_of() call and another value. 1861 * 1862 * The result of this computation can only be assigned back to the original 1863 * view or used in another max_of() call. For example, 1864 * 1865 * *reducer = max_of(x, max_of(y, *reducer)); 1866 * *reducer = max_of(max_of(*reducer, x), y); 1867 * 1868 * @see min_max_internal::rhs_proxy 1869 */ 1870template <typename Index, typename Type, typename Compare> 1871inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1872max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >& proxy, 1873 const Index& index, const Type& value) 1874{ 1875 return proxy.calc(std::pair<Index, Type>(index, value)); 1876} 1877 1878/// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >&, const Index&, const Type&) 1879template <typename Index, typename Type, typename Compare> 1880inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1881max_of(const Index& index, const Type& value, 1882 const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >& proxy) 1883{ 1884 return proxy.calc(std::pair<Index, Type>(index, value)); 1885} 1886 1887/// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >&, const Index&, const Type&) 1888template <typename Index, typename Type, typename Compare> 1889inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1890max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >& proxy, 1891 const std::pair<Index, Type>& pair) 1892{ 1893 return proxy.calc(pair); 1894} 1895 1896/// @copydoc max_of(const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >&, const Index&, const Type&) 1897template <typename Index, typename Type, typename Compare> 1898inline min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> > 1899max_of(const std::pair<Index, Type>& pair, 1900 const min_max_internal::rhs_proxy< op_max_index_view<Index, Type, Compare> >& proxy) 1901{ 1902 return proxy.calc(pair); 1903} 1904 1905 1906/** Monoid class for maximum reductions with index. Instantiate the 1907 * cilk::reducer template class with an op_max_index monoid to create a 1908 * max_index reducer class. For example, to compute the maximum of an array of 1909 * `double` values and the array index of the max value: 1910 * 1911 * cilk::reducer< cilk::op_max_index<unsigned, double> > r; 1912 * 1913 * @see ReducersMinMax 1914 * @see op_max_index_view 1915 */ 1916template < typename Index 1917 , typename Type 1918 , typename Compare=std::less<Type> 1919 , bool Align = false 1920 > 1921class op_max_index : public min_max_internal::monoid_base<op_max_index_view<Index, Type, Compare>, Align> 1922{ 1923 typedef min_max_internal::monoid_base< 1924 op_max_index_view<Index, Type, Compare>, Align> base; 1925public: 1926 /// Construct with default comparator. 1927 op_max_index() {} 1928 /// Construct with specified comparator. 1929 op_max_index(const Compare& compare) : base(compare) {} 1930}; 1931 1932//@} 1933 1934 1935 1936/** @defgroup ReducersMinMaxMinIndex Minimum reducers (value and index) 1937 * 1938 * These reducers will find the smallest value from a set of values, and its 1939 * index in the set. 1940 * 1941 * @ingroup ReducersMinMax 1942 */ 1943//@{ 1944 1945/** The minimum index reducer view class. 1946 * 1947 * This is the view class for reducers created with 1948 * `cilk::reducer<cilk::op_min_index<Index, Type, Compare> >`. It accumulates 1949 * the minimum, as determined by a comparator, of a set of values which have 1950 * occurred as arguments to the `calc_min()` function, and records the index 1951 * of the minimum value. The accumulated value will be the first argument `x` 1952 * such that `compare(y, x)` is false for every argument `y`. 1953 * 1954 * If the comparator is `std::less`, then the accumulated value is the first 1955 * argument value which no other argument value is less than, i.e., the 1956 * minimum. 1957 * 1958 * @note The reducer ���dereference��� operation (`reducer::operator *()`) 1959 * yields a reference to the view. Thus, for example, the view class���s 1960 * `calc_min()` function would be 1961 * used in an expression like `r->calc_min(i, a)`where `r` is an 1962 * op_min_index reducer variable. 1963 * 1964 * @note The word ���index��� suggests an integer index into an array, but there 1965 * is no restriction on the index type or how it should be used. In 1966 * general, it may be convenient to use it for any kind of key that 1967 * can be used to locate the minimum value in the collection that it 1968 * came from ��� for example: 1969 * - An index into an array. 1970 * - A key into an STL map. 1971 * - An iterator into any STL container. 1972 * 1973 * @note A min_index reducer is essentially a min reducer whose value type 1974 * is a `std::pair<Index, Type>`. This fact is camouflaged in the view 1975 * `calc_min` function, the global `min_of` functions, and the reducer 1976 * value constructor, which can all take an index argument and a value 1977 * argument as an alternative to a single `std::pair` argument. 1978 * However, the reducer `set_value()`, `get_value()`, `move_in()`, and 1979 * `move_out()` functions work only with pairs, not with individual 1980 * value and/or index arguments. 1981 * 1982 * @tparam Index The type of the indices associated with the values. 1983 * @tparam Type The type of the values compared by the reducer. This will 1984 * be the value type of a monoid_with_view that is 1985 * instantiated with this view. 1986 * @tparam Compare Used to compare the values. It must be a binary predicate. 1987 * If it is omitted, then the view computes the conventional 1988 * arithmetic minimum. 1989 * 1990 * @see ReducersMinMax 1991 * @see op_min_index 1992 */ 1993template <typename Index, typename Type, typename Compare> 1994class op_min_index_view : public min_max_internal::view_base< 1995 min_max_internal::index_view_content<Index, Type, Compare, false>, 1996 Compare, 1997 min_max_internal::reverse_predicate<Compare, Type> > 1998{ 1999 typedef min_max_internal::view_base< 2000 min_max_internal::index_view_content<Index, Type, Compare, false>, 2001 Compare, 2002 min_max_internal::reverse_predicate<Compare, Type> > base; 2003 using base::calc; 2004 using base::assign; 2005 typedef std::pair<Index, Type> pair_type; 2006 friend class min_max_internal::rhs_proxy<op_min_index_view>; 2007 2008public: 2009 /** @name Constructors. 2010 * 2011 * All op_min_index_view constructors simply pass their arguments on to the 2012 * @ref view_base base class, except for the `(index, value [, compare])` 2013 * constructors, which create a `std::pair` containing the index and value. 2014 */ 2015 //@{ 2016 2017 op_min_index_view() : base() {} 2018 2019 template <typename T1> 2020 op_min_index_view(const T1& x1) : base(x1) {} 2021 2022 template <typename T1, typename T2> 2023 op_min_index_view(const T1& x1, const T2& x2) : base(x1, x2) {} 2024 2025 template <typename T1, typename T2, typename T3> 2026 op_min_index_view(const T1& x1, const T2& x2, const T3& x3) : base(x1, x2, x3) {} 2027 2028 op_min_index_view(const Index& i, const Type& v) : base(pair_type(i, v)) {} 2029 2030 op_min_index_view(const Index& i, const Type& v, const typename base::compare_type* c) : 2031 base(pair_type(i, v), c) {} 2032 2033 //@} 2034 2035 /** Minimize with a value and index. 2036 * 2037 * If @a x is greater than the current value of the view (as defined by 2038 * the reducer���s comparator), or if the view was created without an 2039 * initial value and its value has never been updated (with `calc_min()` 2040 * or `= min_of()`), then the value of the view is set to @a x, and the 2041 * index is set to @a i.. 2042 * 2043 * @param i The index of the value @a x. 2044 * @param x The value to minimize the view���s value with. 2045 * 2046 * @return A reference to the view. (Allows 2047 * `view.comp_min(i, a).comp_min(j, b)���`.) 2048 */ 2049 op_min_index_view& calc_min(const Index& i, const Type& x) 2050 { calc(pair_type(i, x)); return *this; } 2051 2052 /** Maximize with an index/value pair. 2053 * 2054 * If @a pair.second is less than the current value of the view (as 2055 * defined by the reducer���s comparator), or if the view was created 2056 * without an initial value and its value has never been updated (with 2057 * `calc_min()` or `= min_of()`), then the value of the view is set to 2058 * @a pair.second, and the index is set to @a pair.first. 2059 * 2060 * @param pair A pair containing a value to minimize the view���s value 2061 * with and its associated index. 2062 * 2063 * @return A reference to the view. (Allows 2064 * `view.comp_min(p1).comp_min(p2)���`.) 2065 */ 2066 op_min_index_view& calc_min(const pair_type& pair) 2067 { calc(pair); return *this; } 2068 2069 /** Assign the result of a `min_of(view, index, value)` expression to the 2070 * view. 2071 * 2072 * @param rhs An rhs_proxy value created by a `min_of(view, index, value)` 2073 * expression. 2074 * 2075 * @return A reference to the view. 2076 * 2077 * @see min_max_internal::view_base::rhs_proxy 2078 */ 2079 op_min_index_view& operator=(const min_max_internal::rhs_proxy<op_min_index_view>& rhs) 2080 { assign(rhs); return *this; } 2081}; 2082 2083 2084/** Compute the minimum of the value in a view and another value. 2085 * 2086 * The result of this computation can only be assigned back to the original 2087 * view or used in another min_of() call. For example, 2088 * 2089 * *reducer = min_of(*reducer, i, x); 2090 * *reducer = min_of(i, x, *reducer); 2091 * 2092 * @see min_max_internal::min_min_view_base::rhs_proxy 2093 */ 2094template <typename Index, typename Type, typename Compare> 2095inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2096min_of(const op_min_index_view<Index, Type, Compare>& view, 2097 const Index& index, const Type& value) 2098{ 2099 return min_max_internal::make_proxy(std::pair<Index, Type>(index, value), view); 2100} 2101 2102/// @copydoc min_of(const op_min_index_view<Index, Type, Compare>&, const Index&, const Type&) 2103template <typename Index, typename Type, typename Compare> 2104inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2105min_of(const Index& index, const Type& value, 2106 const op_min_index_view<Index, Type, Compare>& view) 2107{ 2108 return min_max_internal::make_proxy(std::pair<Index, Type>(index, value), view); 2109} 2110 2111/// @copydoc min_of(const op_min_index_view<Index, Type, Compare>&, const Index&, const Type&) 2112template <typename Index, typename Type, typename Compare> 2113inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2114min_of(const op_min_index_view<Index, Type, Compare>& view, 2115 const std::pair<Index, Type>& pair) 2116{ 2117 return min_max_internal::make_proxy(pair, view); 2118} 2119 2120/// @copydoc min_of(const op_min_index_view<Index, Type, Compare>&, const Index&, const Type&) 2121template <typename Index, typename Type, typename Compare> 2122inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2123min_of(const std::pair<Index, Type>& pair, 2124 const op_min_index_view<Index, Type, Compare>& view) 2125{ 2126 return min_max_internal::make_proxy(pair, view); 2127} 2128 2129/** Nested computation of the minimum of the value in a view and other values. 2130 * 2131 * Compute the minimum of the result of a min_of() call and another value. 2132 * 2133 * The result of this computation can only be assigned back to the original 2134 * view or used in another min_of() call. For example, 2135 * 2136 * *reducer = min_of(x, min_of(y, *reducer)); 2137 * *reducer = min_of(min_of(*reducer, x), y); 2138 * 2139 * @see min_max_internal::min_min_view_base::rhs_proxy 2140 */ 2141template <typename Index, typename Type, typename Compare> 2142inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2143min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >& proxy, 2144 const Index& index, const Type& value) 2145{ 2146 return proxy.calc(std::pair<Index, Type>(index, value)); 2147} 2148 2149/// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >&, const Index&, const Type&) 2150template <typename Index, typename Type, typename Compare> 2151inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2152min_of(const Index& index, const Type& value, 2153 const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >& proxy) 2154{ 2155 return proxy.calc(std::pair<Index, Type>(index, value)); 2156} 2157 2158/// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >&, const Index&, const Type&) 2159template <typename Index, typename Type, typename Compare> 2160inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2161min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >& proxy, 2162 const std::pair<Index, Type>& pair) 2163{ 2164 return proxy.calc(pair); 2165} 2166 2167/// @copydoc min_of(const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >&, const Index&, const Type&) 2168template <typename Index, typename Type, typename Compare> 2169inline min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> > 2170min_of(const std::pair<Index, Type>& pair, 2171 const min_max_internal::rhs_proxy< op_min_index_view<Index, Type, Compare> >& proxy) 2172{ 2173 return proxy.calc(pair); 2174} 2175 2176 2177/** Monoid class for minimum reductions with index. Instantiate the 2178 * cilk::reducer template class with an op_min_index monoid to create a 2179 * min_index reducer class. For example, to compute the minimum of an array of 2180 * `double` values and the array index of the min value: 2181 * 2182 * cilk::reducer< cilk::op_min_index<unsigned, double> > r; 2183 * 2184 * @see ReducersMinMax 2185 * @see op_min_index_view 2186 */ 2187template < typename Index 2188 , typename Type 2189 , typename Compare=std::less<Type> 2190 , bool Align = false 2191 > 2192class op_min_index : public min_max_internal::monoid_base<op_min_index_view<Index, Type, Compare>, Align> 2193{ 2194 typedef min_max_internal::monoid_base< 2195 op_min_index_view<Index, Type, Compare>, Align> base; 2196public: 2197 /// Construct with default comparator. 2198 op_min_index() {} 2199 /// Construct with specified comparator. 2200 op_min_index(const Compare& compare) : base(compare) {} 2201}; 2202 2203//@} 2204 2205 2206/** Deprecated maximum reducer wrapper class. 2207 * 2208 * reducer_max is the same as @ref reducer<@ref op_max>, except that 2209 * reducer_max is a proxy for the contained view, so that accumulator 2210 * variable update operations can be applied directly to the reducer. For 2211 * example, a value is maximized with a `reducer<%op_max>` with 2212 * `r->calc_max(a)`, but a value can be maximized with a `%reducer_max` with 2213 * `r.calc_max(a)`. 2214 * 2215 * 2216 * @deprecated Users are strongly encouraged to use `reducer<monoid>` 2217 * reducers rather than the old wrappers like reducer_max. 2218 * The `reducer<monoid>` reducers show the reducer/monoid/view 2219 * architecture more clearly, are more consistent in their 2220 * implementation, and present a simpler model for new 2221 * user-implemented reducers. 2222 * 2223 * @note Implicit conversions are provided between `%reducer_max` 2224 * and `reducer<%op_max>`. This allows incremental code 2225 * conversion: old code that used `%reducer_max` can pass a 2226 * `%reducer_max` to a converted function that now expects a 2227 * pointer or reference to a `reducer<%op_max>`, and vice 2228 * versa. **But see @ref redminmax_compatibility.** 2229 * 2230 * @tparam Type The value type of the reducer. 2231 * @tparam Compare The ���less than��� comparator type for the reducer. 2232 * 2233 * @see op_max 2234 * @see op_max_view 2235 * @see reducer 2236 * @see ReducersMinMax 2237 * @ingroup ReducersMinMaxMaxValue 2238 */ 2239template <typename Type, typename Compare=std::less<Type> > 2240class reducer_max : public reducer< op_max<Type, Compare, true> > 2241{ 2242 __CILKRTS_STATIC_ASSERT( 2243 ::cilk::internal::class_is_empty< 2244 typename ::cilk::internal::binary_functor<Compare>::type >::value, 2245 "cilk::reducer_max<Type, Compare> only works with " 2246 "an empty Compare class"); 2247 typedef reducer< op_max<Type, Compare, true> > base; 2248public: 2249 2250 /// Type of data in a reducer_max. 2251 typedef Type basic_value_type; 2252 2253 /// The view type for the reducer. 2254 typedef typename base::view_type view_type; 2255 2256 /// The view type for the reducer. 2257 typedef typename base::view_type View; 2258 2259 /// The monoid type for the reducer. 2260 typedef typename base::monoid_type monoid_type; 2261 2262 /// The monoid type for the reducer. 2263 typedef typename base::monoid_type Monoid; 2264 2265 /// The view���s rhs proxy type. 2266 typedef min_max_internal::rhs_proxy<View> rhs_proxy; 2267 2268 using base::view; 2269 2270 /** @name Constructors 2271 */ 2272 //@{ 2273 2274 /// Construct the wrapper in its identity state (either `!is_set()`, or 2275 /// `value() == identity value`). 2276 reducer_max() : base() {} 2277 2278 /// Construct the wrapper with a specified initial value. 2279 explicit reducer_max(const Type& initial_value) : base(initial_value) {} 2280 2281 /// Construct the wrapper in its identity state with a specified 2282 /// comparator. 2283 explicit reducer_max(const Compare& comp) : base(comp) {} 2284 2285 /// Construct the wrapper with a specified initial value and a specified 2286 /// comparator. 2287 reducer_max(const Type& initial_value, const Compare& comp) 2288 : base(initial_value, comp) {} 2289 2290 //@} 2291 2292 /** @name Forwarded functions 2293 * @details Functions that update the contained accumulator variable are 2294 * simply forwarded to the contained @ref op_max_view. */ 2295 //@{ 2296 2297 /// @copydoc cilk_lib_1_0::min_max_internal::view_content::is_set() const 2298 bool is_set() const { return view().is_set(); } 2299 2300 /// @copydoc op_max_view::calc_max(const Type&) 2301 reducer_max& calc_max(const Type& x) 2302 { view().calc_max(x); return *this; } 2303 2304 /// @copydoc op_max_view::operator=(const min_max_internal::rhs_proxy<op_max_view>&) 2305 reducer_max& operator=(const rhs_proxy& rhs) 2306 { view() = rhs; return *this; } 2307 2308 //@} 2309 2310 /** Allow read-only access to the value within the current view. 2311 * 2312 * @returns A const reference to the value within the current view. 2313 */ 2314 const Type& get_reference() const { return view().get_reference(); } 2315 2316 /// @name Dereference 2317 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper. 2318 * Combined with the rule that a wrapper forwards view operations to the 2319 * view, this means that view operations can be written the same way on 2320 * reducers and wrappers, which is convenient for incrementally 2321 * converting code using wrappers to code using reducers. That is: 2322 * 2323 * reducer< op_max<int> > r; 2324 * r->calc_max(a); // *r returns the view 2325 * // calc_max is a view member function 2326 * 2327 * reducer_max<int> w; 2328 * w->calc_max(a); // *w returns the wrapper 2329 * // calc_max is a wrapper member function that 2330 * // calls the corresponding view function 2331 */ 2332 //@{ 2333 reducer_max& operator*() { return *this; } 2334 reducer_max const& operator*() const { return *this; } 2335 2336 reducer_max* operator->() { return this; } 2337 reducer_max const* operator->() const { return this; } 2338 //@} 2339 2340 /** @name Upcast 2341 * @details In Cilk library 0.9, reducers were always cache-aligned. In 2342 * library 1.0, reducer cache alignment is optional. By default, reducers 2343 * are unaligned (i.e., just naturally aligned), but legacy wrappers 2344 * inherit from cache-aligned reducers for binary compatibility. 2345 * 2346 * This means that a wrapper will automatically be upcast to its aligned 2347 * reducer base class. The following conversion operators provide 2348 * pseudo-upcasts to the corresponding unaligned reducer class. 2349 */ 2350 //@{ 2351 operator reducer< op_max<Type, Compare, false> >& () 2352 { 2353 return *reinterpret_cast< reducer< op_max<Type, Compare, false> >* >(this); 2354 } 2355 2356 operator const reducer< op_max<Type, Compare, false> >& () const 2357 { 2358 return *reinterpret_cast< const reducer< op_max<Type, Compare, false> >* >(this); 2359 } 2360 //@} 2361}; 2362 2363 2364/// @cond internal 2365// The legacy definition of max_of(reducer_max, value) has different 2366// behavior and a different return type than this definition. We add an 2367// unused third argument to this version of the function to give it a different 2368// signature, so that they won���t end up sharing a single object file entry. 2369struct max_of_1_0_t {}; 2370const max_of_1_0_t max_of_1_0 = {}; 2371/// @endcond 2372 2373/** Compute the maximum of the value in a reducer_max and another value. 2374 * 2375 * @deprecated Because reducer_max is deprecated. 2376 * 2377 * The result of this computation can only be assigned back to the original 2378 * reducer or used in another max_of() call. For example, 2379 * 2380 * reducer = max_of(reducer, x); 2381 * reducer = max_of(x, reducer); 2382 * 2383 * @see min_max_internal::rhs_proxy 2384 * 2385 * @ingroup ReducersMinMaxMaxValue 2386 */ 2387template <typename Type, typename Compare> 2388inline min_max_internal::rhs_proxy< op_max_view<Type, Compare> > 2389max_of(const reducer_max<Type, Compare>& r, const Type& value, 2390 const max_of_1_0_t& = max_of_1_0) 2391{ 2392 return min_max_internal::make_proxy(value, r.view()); 2393} 2394 2395/// @copydoc max_of(const reducer_max<Type, Compare>&, const Type&, const max_of_1_0_t&) 2396/// @ingroup ReducersMinMaxMaxValue 2397template <typename Type, typename Compare> 2398inline min_max_internal::rhs_proxy< op_max_view<Type, Compare> > 2399max_of(const Type& value, const reducer_max<Type, Compare>& r, 2400 const max_of_1_0_t& = max_of_1_0) 2401{ 2402 return min_max_internal::make_proxy(value, r.view()); 2403} 2404 2405 2406/** Deprecated minimum reducer wrapper class. 2407 * 2408 * reducer_min is the same as @ref reducer<@ref op_min>, except that 2409 * reducer_min is a proxy for the contained view, so that accumulator 2410 * variable update operations can be applied directly to the reducer. For 2411 * example, a value is minimized with a `reducer<%op_min>` with 2412 * `r->calc_min(a)`, but a value can be minimized with a `%reducer_min` with 2413 * `r.calc_min(a)`. 2414 * 2415 * 2416 * @deprecated Users are strongly encouraged to use `reducer<monoid>` 2417 * reducers rather than the old wrappers like reducer_min. 2418 * The `reducer<monoid>` reducers show the reducer/monoid/view 2419 * architecture more clearly, are more consistent in their 2420 * implementation, and present a simpler model for new 2421 * user-implemented reducers. 2422 * 2423 * @note Implicit conversions are provided between `%reducer_min` 2424 * and `reducer<%op_min>`. This allows incremental code 2425 * conversion: old code that used `%reducer_min` can pass a 2426 * `%reducer_min` to a converted function that now expects a 2427 * pointer or reference to a `reducer<%op_min>`, and vice 2428 * versa. **But see @ref redminmax_compatibility.** 2429 * 2430 * @tparam Type The value type of the reducer. 2431 * @tparam Compare The ���less than��� comparator type for the reducer. 2432 * 2433 * @see op_min 2434 * @see op_min_view 2435 * @see reducer 2436 * @see ReducersMinMax 2437 * @ingroup ReducersMinMaxMinValue 2438 */ 2439template <typename Type, typename Compare=std::less<Type> > 2440class reducer_min : public reducer< op_min<Type, Compare, true> > 2441{ 2442 __CILKRTS_STATIC_ASSERT( 2443 ::cilk::internal::class_is_empty< 2444 typename ::cilk::internal::binary_functor<Compare>::type >::value, 2445 "cilk::reducer_min<Type, Compare> only works with " 2446 "an empty Compare class"); 2447 typedef reducer< op_min<Type, Compare, true> > base; 2448public: 2449 2450 /// Type of data in a reducer_min. 2451 typedef Type basic_value_type; 2452 2453 /// The view type for the reducer. 2454 typedef typename base::view_type view_type; 2455 2456 /// The view type for the reducer. 2457 typedef typename base::view_type View; 2458 2459 /// The monoid type for the reducer. 2460 typedef typename base::monoid_type monoid_type; 2461 2462 /// The monoid type for the reducer. 2463 typedef typename base::monoid_type Monoid; 2464 2465 /// The view���s rhs proxy type. 2466 typedef min_max_internal::rhs_proxy<View> rhs_proxy; 2467 2468 using base::view; 2469 2470 /** @name Constructors 2471 */ 2472 //@{ 2473 2474 /// Construct the wrapper in its identity state (either `!is_set()`, or 2475 /// `value() == identity value`). 2476 reducer_min() : base() {} 2477 2478 /// Construct the wrapper with a specified initial value. 2479 explicit reducer_min(const Type& initial_value) : base(initial_value) {} 2480 2481 /// Construct the wrapper in its identity state with a specified 2482 /// comparator. 2483 explicit reducer_min(const Compare& comp) : base(comp) {} 2484 2485 /// Construct the wrapper with a specified initial value and a specified 2486 /// comparator. 2487 reducer_min(const Type& initial_value, const Compare& comp) 2488 : base(initial_value, comp) {} 2489 2490 //@} 2491 2492 /** @name Forwarded functions 2493 * @details Functions that update the contained accumulator variable are 2494 * simply forwarded to the contained @ref op_min_view. */ 2495 //@{ 2496 2497 /// @copydoc cilk_lib_1_0::min_max_internal::view_content::is_set() const 2498 bool is_set() const { return view().is_set(); } 2499 2500 /// @copydoc op_min_view::calc_min(const Type&) 2501 reducer_min& calc_min(const Type& x) 2502 { view().calc_min(x); return *this; } 2503 2504 /// @copydoc op_min_view::operator=(const min_max_internal::rhs_proxy<op_min_view>&) 2505 reducer_min& operator=(const rhs_proxy& rhs) 2506 { view() = rhs; return *this; } 2507 2508 //@} 2509 2510 /** Allow read-only access to the value within the current view. 2511 * 2512 * @returns A const reference to the value within the current view. 2513 */ 2514 const Type& get_reference() const { return view().get_reference(); } 2515 2516 /// @name Dereference 2517 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper. 2518 * Combined with the rule that a wrapper forwards view operations to the 2519 * view, this means that view operations can be written the same way on 2520 * reducers and wrappers, which is convenient for incrementally 2521 * converting code using wrappers to code using reducers. That is: 2522 * 2523 * reducer< op_min<int> > r; 2524 * r->calc_min(a); // *r returns the view 2525 * // calc_min is a view member function 2526 * 2527 * reducer_min<int> w; 2528 * w->calc_min(a); // *w returns the wrapper 2529 * // calc_min is a wrapper member function that 2530 * // calls the corresponding view function 2531 */ 2532 //@{ 2533 reducer_min& operator*() { return *this; } 2534 reducer_min const& operator*() const { return *this; } 2535 2536 reducer_min* operator->() { return this; } 2537 reducer_min const* operator->() const { return this; } 2538 //@} 2539 2540 /** @name Upcast 2541 * @details In Cilk library 0.9, reducers were always cache-aligned. In 2542 * library 1.0, reducer cache alignment is optional. By default, reducers 2543 * are unaligned (i.e., just naturally aligned), but legacy wrappers 2544 * inherit from cache-aligned reducers for binary compatibility. 2545 * 2546 * This means that a wrapper will automatically be upcast to its aligned 2547 * reducer base class. The following conversion operators provide 2548 * pseudo-upcasts to the corresponding unaligned reducer class. 2549 */ 2550 //@{ 2551 operator reducer< op_min<Type, Compare, false> >& () 2552 { 2553 return *reinterpret_cast< reducer< op_min<Type, Compare, false> >* >(this); 2554 } 2555 2556 operator const reducer< op_min<Type, Compare, false> >& () const 2557 { 2558 return *reinterpret_cast< const reducer< op_min<Type, Compare, false> >* >(this); 2559 } 2560 //@} 2561}; 2562 2563 2564/** Compute the minimum of a reducer and a value. 2565 * 2566 * @deprecated Because reducer_min is deprecated. 2567 */ 2568//@{ 2569// The legacy definition of min_of(reducer_min, value) has different 2570// behavior and a different return type than this definition. We add an 2571// unused third argument to this version of the function to give it a different 2572// signature, so that they won���t end up sharing a single object file entry. 2573struct min_of_1_0_t {}; 2574const min_of_1_0_t min_of_1_0 = {}; 2575 2576template <typename Type, typename Compare> 2577inline min_max_internal::rhs_proxy< op_min_view<Type, Compare> > 2578min_of(const reducer_min<Type, Compare>& r, const Type& value, 2579 const min_of_1_0_t& = min_of_1_0) 2580{ 2581 return min_max_internal::make_proxy(value, r.view()); 2582} 2583 2584template <typename Type, typename Compare> 2585inline min_max_internal::rhs_proxy< op_min_view<Type, Compare> > 2586min_of(const Type& value, const reducer_min<Type, Compare>& r, 2587 const min_of_1_0_t& = min_of_1_0) 2588{ 2589 return min_max_internal::make_proxy(value, r.view()); 2590} 2591//@} 2592 2593 2594/** Deprecated maximum with index reducer wrapper class. 2595 * 2596 * reducer_max_index is the same as @ref reducer<@ref op_max_index>, except 2597 * that reducer_max_index is a proxy for the contained view, so that 2598 * accumulator variable update operations can be applied directly to the 2599 * reducer. For example, a value is maximized with a `reducer<%op_max_index>` 2600 * with `r->calc_max(i, a)`, but a value can be maximized with a 2601 * `%reducer_max` with `r.calc_max(i, aa)`. 2602 * 2603 * 2604 * @deprecated Users are strongly encouraged to use `reducer<monoid>` 2605 * reducers rather than the old wrappers like reducer_max. 2606 * The `reducer<monoid>` reducers show the reducer/monoid/view 2607 * architecture more clearly, are more consistent in their 2608 * implementation, and present a simpler model for new 2609 * user-implemented reducers. 2610 * 2611 * @note Implicit conversions are provided between `%reducer_max_index` 2612 * and `reducer<%op_max_index>`. This allows incremental code 2613 * conversion: old code that used `%reducer_max_index` can pass a 2614 * `%reducer_max_index` to a converted function that now expects a 2615 * pointer or reference to a `reducer<%op_max_index>`, and vice 2616 * versa. **But see @ref redminmax_compatibility.** 2617 * 2618 * @tparam Index The index type of the reducer. 2619 * @tparam Type The value type of the reducer. 2620 * @tparam Compare The ���less than��� comparator type for the reducer. 2621 * 2622 * @see op_max_index 2623 * @see op_max_index_view 2624 * @see reducer 2625 * @see ReducersMinMax 2626 * @ingroup ReducersMinMaxMaxIndex 2627 */ 2628template < typename Index 2629 , typename Type 2630 , typename Compare = std::less<Type> 2631 > 2632class reducer_max_index : 2633 public reducer< op_max_index<Index, Type, Compare, true> > 2634{ 2635 __CILKRTS_STATIC_ASSERT( 2636 ::cilk::internal::class_is_empty< 2637 typename ::cilk::internal::binary_functor<Compare>::type >::value, 2638 "cilk::reducer_max_index<Type, Compare> only works with " 2639 "an empty Compare class"); 2640 typedef reducer< op_max_index<Index, Type, Compare, true> > base; 2641public: 2642 2643 /// Type of data in a reducer_max_index. 2644 typedef Type basic_value_type; 2645 2646 /// The view type for the reducer. 2647 typedef typename base::view_type view_type; 2648 2649 /// The view type for the reducer. 2650 typedef typename base::view_type View; 2651 2652 /// The monoid type for the reducer. 2653 typedef typename base::monoid_type monoid_type; 2654 2655 /// The monoid type for the reducer. 2656 typedef typename base::monoid_type Monoid; 2657 2658 /// The view���s rhs proxy type. 2659 typedef min_max_internal::rhs_proxy<View> rhs_proxy; 2660 2661 using base::view; 2662 2663 /** @name Constructors 2664 */ 2665 //@{ 2666 2667 /// Construct the wrapper in its identity state (`!is_set()`). 2668 reducer_max_index() : base() {} 2669 2670 /// Construct with a specified initial index and value. 2671 reducer_max_index(const Index& initial_index, 2672 const Type& initial_value) 2673 : base(initial_index, initial_value) {} 2674 2675 /// Construct the wrapper with a specified comparator. 2676 explicit reducer_max_index(const Compare& comp) : base(comp) {} 2677 2678 /// Construct the wrapper with a specified initial index, value, 2679 /// and comparator. 2680 reducer_max_index(const Index& initial_index, 2681 const Type& initial_value, 2682 const Compare& comp) 2683 : base(initial_index, initial_value, comp) {} 2684 2685 //@} 2686 2687 /** @name Set / Get 2688 */ 2689 //@{ 2690 2691 /// Set the index and value of this object. 2692 void set_value(const Index& index, const Type& value) 2693 { base::set_value(std::make_pair(index, value)); } 2694 2695 /// Return the maximum value. 2696 const Type& get_value() const 2697 { return view().get_reference(); } 2698 2699 /// Return the maximum index. 2700 const Index& get_index() const 2701 { return view().get_index_reference(); } 2702 2703 /// Return a const reference to value data member in the view. 2704 const Type& get_reference() const 2705 { return view().get_reference(); } 2706 2707 /// Return a const reference to index data member in the view. 2708 const Index& get_index_reference() const 2709 { return view().get_index_reference(); } 2710 2711 //@} 2712 2713 /** @name Forwarded functions 2714 * @details Functions that update the contained accumulator variable are 2715 * simply forwarded to the contained @ref op_max_view. */ 2716 //@{ 2717 2718 /// @copydoc cilk_lib_1_0::min_max_internal::view_content::is_set() const 2719 bool is_set() const { return view().is_set(); } 2720 2721 /// @copydoc op_max_index_view::calc_max(const Index&, const Type&) 2722 reducer_max_index& calc_max(const Index& i, const Type& x) 2723 { view().calc_max(i, x); return *this; } 2724 2725 /// @copydoc op_max_view::operator=(const min_max_internal::rhs_proxy<op_max_view>&) 2726 reducer_max_index& operator=(const rhs_proxy& rhs) 2727 { view() = rhs; return *this; } 2728 2729 //@} 2730 2731 /// @name Dereference 2732 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper. 2733 * Combined with the rule that a wrapper forwards view operations to the 2734 * view, this means that view operations can be written the same way on 2735 * reducers and wrappers, which is convenient for incrementally 2736 * converting code using wrappers to code using reducers. That is: 2737 * 2738 * reducer< op_max_index<int, int> > r; 2739 * r->calc_max(i, a); // *r returns the view 2740 * // calc_max is a view member function 2741 * 2742 * reducer_max_index<int, int> w; 2743 * w->calc_max(i, a); // *w returns the wrapper 2744 * // calc_max is a wrapper member function that 2745 * // calls the corresponding view function 2746 */ 2747 //@{ 2748 reducer_max_index& operator*() { return *this; } 2749 reducer_max_index const& operator*() const { return *this; } 2750 2751 reducer_max_index* operator->() { return this; } 2752 reducer_max_index const* operator->() const { return this; } 2753 //@} 2754 2755 /** @name Upcast 2756 * @details In Cilk library 0.9, reducers were always cache-aligned. In 2757 * library 1.0, reducer cache alignment is optional. By default, reducers 2758 * are unaligned (i.e., just naturally aligned), but legacy wrappers 2759 * inherit from cache-aligned reducers for binary compatibility. 2760 * 2761 * This means that a wrapper will automatically be upcast to its aligned 2762 * reducer base class. The following conversion operators provide 2763 * pseudo-upcasts to the corresponding unaligned reducer class. 2764 */ 2765 //@{ 2766 operator reducer< op_max_index<Index, Type, Compare, false> >& () 2767 { 2768 return *reinterpret_cast< reducer< op_max_index<Index, Type, Compare, false> >* >(this); 2769 } 2770 2771 operator const reducer< op_max_index<Index, Type, Compare, false> >& () const 2772 { 2773 return *reinterpret_cast< const reducer< op_max_index<Index, Type, Compare, false> >* >(this); 2774 } 2775 //@} 2776 2777}; 2778 2779 2780/** Deprecated minimum with index reducer wrapper class. 2781 * 2782 * reducer_min_index is the same as @ref reducer<@ref op_min_index>, except 2783 * that reducer_min_index is a proxy for the contained view, so that 2784 * accumulator variable update operations can be applied directly to the 2785 * reducer. For example, a value is minimized with a `reducer<%op_min_index>` 2786 * with `r->calc_min(i, a)`, but a value can be minimized with a 2787 * `%reducer_min` with `r.calc_min(i, aa)`. 2788 * 2789 * 2790 * @deprecated Users are strongly encouraged to use `reducer<monoid>` 2791 * reducers rather than the old wrappers like reducer_min. 2792 * The `reducer<monoid>` reducers show the reducer/monoid/view 2793 * architecture more clearly, are more consistent in their 2794 * implementation, and present a simpler model for new 2795 * user-implemented reducers. 2796 * 2797 * @note Implicit conversions are provided between `%reducer_min_index` 2798 * and `reducer<%op_min_index>`. This allows incremental code 2799 * conversion: old code that used `%reducer_min_index` can pass a 2800 * `%reducer_min_index` to a converted function that now expects a 2801 * pointer or reference to a `reducer<%op_min_index>`, and vice 2802 * versa. **But see @ref redminmax_compatibility.** 2803 * 2804 * @tparam Index The index type of the reducer. 2805 * @tparam Type The value type of the reducer. 2806 * @tparam Compare The ���less than��� comparator type for the reducer. 2807 * 2808 * @see op_min_index 2809 * @see op_min_index_view 2810 * @see reducer 2811 * @see ReducersMinMax 2812 * @ingroup ReducersMinMaxMinIndex 2813 */ 2814template < typename Index 2815 , typename Type 2816 , typename Compare = std::less<Type> 2817 > 2818class reducer_min_index : 2819 public reducer< op_min_index<Index, Type, Compare, true> > 2820{ 2821 __CILKRTS_STATIC_ASSERT( 2822 ::cilk::internal::class_is_empty< 2823 typename ::cilk::internal::binary_functor<Compare>::type >::value, 2824 "cilk::reducer_min_index<Type, Compare> only works with " 2825 "an empty Compare class"); 2826 typedef reducer< op_min_index<Index, Type, Compare, true> > base; 2827public: 2828 2829 /// Type of data in a reducer_min_index. 2830 typedef Type basic_value_type; 2831 2832 /// The view type for the reducer. 2833 typedef typename base::view_type view_type; 2834 2835 /// The view type for the reducer. 2836 typedef typename base::view_type View; 2837 2838 /// The monoid type for the reducer. 2839 typedef typename base::monoid_type monoid_type; 2840 2841 /// The monoid type for the reducer. 2842 typedef typename base::monoid_type Monoid; 2843 2844 /// The view���s rhs proxy type. 2845 typedef min_max_internal::rhs_proxy<View> rhs_proxy; 2846 2847 using base::view; 2848 2849 /** @name Constructors 2850 */ 2851 //@{ 2852 2853 /// Construct the wrapper in its identity state (`!is_set()`). 2854 reducer_min_index() : base() {} 2855 2856 /// Construct with a specified initial index and value. 2857 reducer_min_index(const Index& initial_index, 2858 const Type& initial_value) 2859 : base(initial_index, initial_value) {} 2860 2861 /// Construct the wrapper with a specified comparator. 2862 explicit reducer_min_index(const Compare& comp) : base(comp) {} 2863 2864 /// Construct the wrapper with a specified initial index, value, 2865 /// and comparator. 2866 reducer_min_index(const Index& initial_index, 2867 const Type& initial_value, 2868 const Compare& comp) 2869 : base(initial_index, initial_value, comp) {} 2870 2871 //@} 2872 2873 /** @name Set / Get 2874 */ 2875 //@{ 2876 2877 /// Set the index and value of this object. 2878 void set_value(const Index& index, const Type& value) 2879 { base::set_value(std::make_pair(index, value)); } 2880 2881 /// Return the minimum value. 2882 const Type& get_value() const 2883 { return view().get_reference(); } 2884 2885 /// Return the minimum index. 2886 const Index& get_index() const 2887 { return view().get_index_reference(); } 2888 2889 /// Return a const reference to value data member in the view. 2890 const Type& get_reference() const 2891 { return view().get_reference(); } 2892 2893 /// Return a const reference to index data member in the view. 2894 const Index& get_index_reference() const 2895 { return view().get_index_reference(); } 2896 2897 //@} 2898 2899 /** @name Forwarded functions 2900 * @details Functions that update the contained accumulator variable are 2901 * simply forwarded to the contained @ref op_min_view. */ 2902 //@{ 2903 2904 /// @copydoc cilk_lib_1_0::min_max_internal::view_content::is_set() const 2905 bool is_set() const { return view().is_set(); } 2906 2907 /// @copydoc op_min_index_view::calc_min(const Index&, const Type&) 2908 reducer_min_index& calc_min(const Index& i, const Type& x) 2909 { view().calc_min(i, x); return *this; } 2910 2911 /// @copydoc op_min_view::operator=(const min_max_internal::rhs_proxy<op_min_view>&) 2912 reducer_min_index& operator=(const rhs_proxy& rhs) 2913 { view() = rhs; return *this; } 2914 2915 //@} 2916 2917 /// @name Dereference 2918 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper. 2919 * Combined with the rule that a wrapper forwards view operations to the 2920 * view, this means that view operations can be written the same way on 2921 * reducers and wrappers, which is convenient for incrementally 2922 * converting code using wrappers to code using reducers. That is: 2923 * 2924 * reducer< op_min_index<int, int> > r; 2925 * r->calc_min(i, a); // *r returns the view 2926 * // calc_min is a view member function 2927 * 2928 * reducer_min_index<int, int> w; 2929 * w->calc_min(i, a); // *w returns the wrapper 2930 * // calc_min is a wrapper member function that 2931 * // calls the corresponding view function 2932 */ 2933 //@{ 2934 reducer_min_index& operator*() { return *this; } 2935 reducer_min_index const& operator*() const { return *this; } 2936 2937 reducer_min_index* operator->() { return this; } 2938 reducer_min_index const* operator->() const { return this; } 2939 //@} 2940 2941 /** @name Upcast 2942 * @details In Cilk library 0.9, reducers were always cache-aligned. In 2943 * library 1.0, reducer cache alignment is optional. By default, reducers 2944 * are unaligned (i.e., just naturally aligned), but legacy wrappers 2945 * inherit from cache-aligned reducers for binary compatibility. 2946 * 2947 * This means that a wrapper will automatically be upcast to its aligned 2948 * reducer base class. The following conversion operators provide 2949 * pseudo-upcasts to the corresponding unaligned reducer class. 2950 */ 2951 //@{ 2952 operator reducer< op_min_index<Index, Type, Compare, false> >& () 2953 { 2954 return *reinterpret_cast< reducer< op_min_index<Index, Type, Compare, false> >* >(this); 2955 } 2956 2957 operator const reducer< op_min_index<Index, Type, Compare, false> >& () const 2958 { 2959 return *reinterpret_cast< const reducer< op_min_index<Index, Type, Compare, false> >* >(this); 2960 } 2961 //@} 2962 2963}; 2964 2965 2966#ifndef CILK_LIBRARY_0_9_REDUCER_MINMAX 2967} // namespace cilk_lib_1_0 2968using namespace cilk_lib_1_0; 2969#endif 2970 2971 2972/// @cond internal 2973/** Metafunction specialization for reducer conversion. 2974 * 2975 * These specializations of the @ref legacy_reducer_downcast template class 2976 * defined in reducer.h causes each `reducer< op_xxxx<Type> >` classes to have 2977 * an `operator reducer_xxxx<Type>& ()` conversion operator that statically 2978 * downcasts the `reducer<op_xxxx>` to the corresponding `reducer_xxxx` type. 2979 * (The reverse conversion, from `reducer_xxxx` to `reducer<op_xxxx>`, is just 2980 * an upcast, which is provided for free by the language.) 2981 */ 2982template <typename Type, typename Compare, bool Align> 2983struct legacy_reducer_downcast< reducer< op_max<Type, Compare, Align> > > 2984{ 2985 typedef reducer_max<Type> type; 2986}; 2987 2988template <typename Type, typename Compare, bool Align> 2989struct legacy_reducer_downcast< reducer< op_min<Type, Compare, Align> > > 2990{ 2991 typedef reducer_min<Type> type; 2992}; 2993 2994template <typename Index, typename Type, typename Compare, bool Align> 2995struct legacy_reducer_downcast< reducer< op_max_index<Index, Type, Compare, Align> > > 2996{ 2997 typedef reducer_max_index<Index, Type> type; 2998}; 2999 3000template <typename Index, typename Type, typename Compare, bool Align> 3001struct legacy_reducer_downcast< reducer< op_min_index<Index, Type, Compare, Align> > > 3002{ 3003 typedef reducer_min_index<Index, Type> type; 3004}; 3005/// @endcond 3006 3007} // namespace cilk 3008 3009#endif // __cplusplus 3010 3011 3012/** @name C language reducer macros 3013 * 3014 * These macros are used to declare and work with numeric minimum and maximum reducers in C 3015 * code. 3016 * 3017 * @see @ref page_reducers_in_c 3018 */ 3019 //@{ 3020 3021 3022#ifdef CILK_C_DEFINE_REDUCERS 3023 3024/* Integer min/max constants */ 3025#include <limits.h> 3026 3027/* Wchar_t min/max constants */ 3028#if defined(_MSC_VER) || defined(__ANDROID__) 3029# include <wchar.h> 3030#else 3031# include <stdint.h> 3032#endif 3033 3034/* Floating-point min/max constants */ 3035#include <math.h> 3036#ifndef HUGE_VALF 3037 static const unsigned int __huge_valf[] = {0x7f800000}; 3038# define HUGE_VALF (*((const float *)__huge_valf)) 3039#endif 3040 3041#ifndef HUGE_VALL 3042 static const unsigned int __huge_vall[] = {0, 0, 0x00007f80, 0}; 3043# define HUGE_VALL (*((const long double *)__huge_vall)) 3044#endif 3045 3046#endif 3047 3048/** Max reducer type name. 3049 * 3050 * This macro expands into the identifier which is the name of the max reducer 3051 * type for a specified numeric type. 3052 * 3053 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3054 * reducer. 3055 * 3056 * @see @ref reducers_c_predefined 3057 */ 3058#define CILK_C_REDUCER_MAX_TYPE(tn) \ 3059 __CILKRTS_MKIDENT(cilk_c_reducer_max_,tn) 3060 3061/** Declare a max reducer object. 3062 * 3063 * This macro expands into a declaration of a max reducer object for a specified numeric 3064 * type. For example: 3065 * 3066 * CILK_C_REDUCER_MAX(my_reducer, double, -DBL_MAX); 3067 * 3068 * @param obj The variable name to be used for the declared reducer object. 3069 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3070 * reducer. 3071 * @param v The initial value for the reducer. (A value which can be assigned to the 3072 * numeric type represented by @a tn.) 3073 * 3074 * @see @ref reducers_c_predefined 3075 */ 3076#define CILK_C_REDUCER_MAX(obj,tn,v) \ 3077 CILK_C_REDUCER_MAX_TYPE(tn) obj = \ 3078 CILK_C_INIT_REDUCER(_Typeof(obj.value), \ 3079 __CILKRTS_MKIDENT(cilk_c_reducer_max_reduce_,tn), \ 3080 __CILKRTS_MKIDENT(cilk_c_reducer_max_identity_,tn), \ 3081 __cilkrts_hyperobject_noop_destroy, v) 3082 3083/** Maximize with a value. 3084 * 3085 * `CILK_C_REDUCER_MAX_CALC(reducer, v)` sets the current view of the 3086 * reducer to the max of its previous value and a specified new value. 3087 * This is equivalent to 3088 * 3089 * REDUCER_VIEW(reducer) = max(REDUCER_VIEW(reducer), v) 3090 * 3091 * @param reducer The reducer whose contained value is to be updated. 3092 * @param v The value that it is to be maximized with. 3093 */ 3094#define CILK_C_REDUCER_MAX_CALC(reducer, v) do { \ 3095 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \ 3096 _Typeof(v) __value = (v); \ 3097 if (*view < __value) { \ 3098 *view = __value; \ 3099 } } while (0) 3100 3101/// @cond internal 3102 3103/** Declare the max reducer functions for a numeric type. 3104 * 3105 * This macro expands into external function declarations for functions which implement 3106 * the reducer functionality for the max reducer type for a specified numeric type. 3107 * 3108 * @param t The value type of the reducer. 3109 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3110 * function names, etc. 3111 */ 3112#define CILK_C_REDUCER_MAX_DECLARATION(t,tn,id) \ 3113 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MAX_TYPE(tn); \ 3114 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max,tn,l,r); \ 3115 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max,tn); 3116 3117/** Define the max reducer functions for a numeric type. 3118 * 3119 * This macro expands into function definitions for functions which implement the 3120 * reducer functionality for the max reducer type for a specified numeric type. 3121 * 3122 * @param t The value type of the reducer. 3123 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3124 * function names, etc. 3125 */ 3126#define CILK_C_REDUCER_MAX_DEFINITION(t,tn,id) \ 3127 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MAX_TYPE(tn); \ 3128 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max,tn,l,r) \ 3129 { if (*(t*)l < *(t*)r) *(t*)l = *(t*)r; } \ 3130 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max,tn) \ 3131 { *(t*)v = id; } 3132 3133//@{ 3134/** @def CILK_C_REDUCER_MAX_INSTANCE 3135 * @brief Declare or define implementation functions for a reducer type. 3136 * 3137 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and 3138 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS` 3139 * will be undefined, and this macro will expand into external declarations for the functions. 3140 */ 3141#ifdef CILK_C_DEFINE_REDUCERS 3142# define CILK_C_REDUCER_MAX_INSTANCE(t,tn,id) \ 3143 CILK_C_REDUCER_MAX_DEFINITION(t,tn,id) 3144#else 3145# define CILK_C_REDUCER_MAX_INSTANCE(t,tn,id) \ 3146 CILK_C_REDUCER_MAX_DECLARATION(t,tn,id) 3147#endif 3148//@} 3149 3150/* Declare or define an instance of the reducer type and its functions for each 3151 * numeric type. 3152 */ 3153__CILKRTS_BEGIN_EXTERN_C 3154CILK_C_REDUCER_MAX_INSTANCE(char, char, CHAR_MIN) 3155CILK_C_REDUCER_MAX_INSTANCE(unsigned char, uchar, 0) 3156CILK_C_REDUCER_MAX_INSTANCE(signed char, schar, SCHAR_MIN) 3157CILK_C_REDUCER_MAX_INSTANCE(wchar_t, wchar_t, WCHAR_MIN) 3158CILK_C_REDUCER_MAX_INSTANCE(short, short, SHRT_MIN) 3159CILK_C_REDUCER_MAX_INSTANCE(unsigned short, ushort, 0) 3160CILK_C_REDUCER_MAX_INSTANCE(int, int, INT_MIN) 3161CILK_C_REDUCER_MAX_INSTANCE(unsigned int, uint, 0) 3162CILK_C_REDUCER_MAX_INSTANCE(unsigned int, unsigned, 0) // alternate name 3163CILK_C_REDUCER_MAX_INSTANCE(long, long, LONG_MIN) 3164CILK_C_REDUCER_MAX_INSTANCE(unsigned long, ulong, 0) 3165CILK_C_REDUCER_MAX_INSTANCE(long long, longlong, LLONG_MIN) 3166CILK_C_REDUCER_MAX_INSTANCE(unsigned long long, ulonglong, 0) 3167CILK_C_REDUCER_MAX_INSTANCE(float, float, -HUGE_VALF) 3168CILK_C_REDUCER_MAX_INSTANCE(double, double, -HUGE_VAL) 3169CILK_C_REDUCER_MAX_INSTANCE(long double, longdouble, -HUGE_VALL) 3170__CILKRTS_END_EXTERN_C 3171 3172/// @endcond 3173 3174/** Max_index reducer type name. 3175 * 3176 * This macro expands into the identifier which is the name of the max_index reducer 3177 * type for a specified numeric type. 3178 * 3179 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3180 * reducer. 3181 * 3182 * @see @ref reducers_c_predefined 3183 */ 3184#define CILK_C_REDUCER_MAX_INDEX_TYPE(tn) \ 3185 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_,tn) 3186 3187/** Declare an op_max_index reducer object. 3188 * 3189 * This macro expands into a declaration of a max_index reducer object for a specified 3190 * numeric type. For example: 3191 * 3192 * CILK_C_REDUCER_MAX_INDEX(my_reducer, double, -DBL_MAX_INDEX); 3193 * 3194 * @param obj The variable name to be used for the declared reducer object. 3195 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3196 * reducer. 3197 * @param v The initial value for the reducer. (A value which can be assigned to the 3198 * numeric type represented by @a tn.) 3199 * 3200 * @see @ref reducers_c_predefined 3201 */ 3202#define CILK_C_REDUCER_MAX_INDEX(obj,tn,v) \ 3203 CILK_C_REDUCER_MAX_INDEX_TYPE(tn) obj = \ 3204 CILK_C_INIT_REDUCER(_Typeof(obj.value), \ 3205 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_reduce_,tn), \ 3206 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_identity_,tn), \ 3207 __cilkrts_hyperobject_noop_destroy, {0, v}) 3208 3209/** Maximize with a value. 3210 * 3211 * `CILK_C_REDUCER_MAX_INDEX_CALC(reducer, i, v)` sets the current view of the 3212 * reducer to the max of its previous value and a specified new value. 3213 * This is equivalent to 3214 * 3215 * REDUCER_VIEW(reducer) = max_index(REDUCER_VIEW(reducer), v) 3216 * 3217 * If the value of the reducer is changed to @a v, then the index of the reducer is 3218 * changed to @a i. 3219 * 3220 * @param reducer The reducer whose contained value and index are to be updated. 3221 * @param i The index associated with the new value. 3222 * @param v The value that it is to be maximized with. 3223 */ 3224#define CILK_C_REDUCER_MAX_INDEX_CALC(reducer, i, v) do { \ 3225 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \ 3226 _Typeof(v) __value = (v); \ 3227 if (view->value < __value) { \ 3228 view->index = (i); \ 3229 view->value = __value; \ 3230 } } while (0) 3231 3232/// @cond internal 3233 3234/** Declare the max_index view type. 3235 * 3236 * The view of a max_index reducer is a structure containing both the 3237 * maximum value for the reducer and the index that was associated with 3238 * that value in the sequence of input values. 3239 */ 3240#define CILK_C_REDUCER_MAX_INDEX_VIEW(t,tn) \ 3241 typedef struct { \ 3242 __STDNS ptrdiff_t index; \ 3243 t value; \ 3244 } __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn) 3245 3246/** Declare the max_index reducer functions for a numeric type. 3247 * 3248 * This macro expands into external function declarations for functions which implement 3249 * the reducer functionality for the max_index reducer type for a specified numeric type. 3250 * 3251 * @param t The value type of the reducer. 3252 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3253 * function names, etc. 3254 */ 3255#define CILK_C_REDUCER_MAX_INDEX_DECLARATION(t,tn,id) \ 3256 CILK_C_REDUCER_MAX_INDEX_VIEW(t,tn); \ 3257 typedef CILK_C_DECLARE_REDUCER( \ 3258 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn)) \ 3259 CILK_C_REDUCER_MAX_INDEX_TYPE(tn); \ 3260 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max_index,tn,l,r); \ 3261 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max_index,tn); 3262 3263/** Define the max_index reducer functions for a numeric type. 3264 * 3265 * This macro expands into function definitions for functions which implement the 3266 * reducer functionality for the max_index reducer type for a specified numeric type. 3267 * 3268 * @param t The value type of the reducer. 3269 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3270 * function names, etc. 3271 */ 3272#define CILK_C_REDUCER_MAX_INDEX_DEFINITION(t,tn,id) \ 3273 CILK_C_REDUCER_MAX_INDEX_VIEW(t,tn); \ 3274 typedef CILK_C_DECLARE_REDUCER( \ 3275 __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn)) \ 3276 CILK_C_REDUCER_MAX_INDEX_TYPE(tn); \ 3277 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_max_index,tn,l,r) \ 3278 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn) view_t; \ 3279 if (((view_t*)l)->value < ((view_t*)r)->value) \ 3280 *(view_t*)l = *(view_t*)r; } \ 3281 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_max_index,tn) \ 3282 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_max_index_view_,tn) view_t; \ 3283 ((view_t*)v)->index = 0; ((view_t*)v)->value = id; } 3284 3285//@{ 3286/** @def CILK_C_REDUCER_MAX_INDEX_INSTANCE 3287 * @brief Declare or define implementation functions for a reducer type. 3288 * 3289 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and 3290 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS` 3291 * will be undefined, and this macro will expand into external declarations for the functions. 3292 */ 3293#ifdef CILK_C_DEFINE_REDUCERS 3294# define CILK_C_REDUCER_MAX_INDEX_INSTANCE(t,tn,id) \ 3295 CILK_C_REDUCER_MAX_INDEX_DEFINITION(t,tn,id) 3296#else 3297# define CILK_C_REDUCER_MAX_INDEX_INSTANCE(t,tn,id) \ 3298 CILK_C_REDUCER_MAX_INDEX_DECLARATION(t,tn,id) 3299#endif 3300//@} 3301 3302/* Declare or define an instance of the reducer type and its functions for each 3303 * numeric type. 3304 */ 3305__CILKRTS_BEGIN_EXTERN_C 3306CILK_C_REDUCER_MAX_INDEX_INSTANCE(char, char, CHAR_MIN) 3307CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned char, uchar, 0) 3308CILK_C_REDUCER_MAX_INDEX_INSTANCE(signed char, schar, SCHAR_MIN) 3309CILK_C_REDUCER_MAX_INDEX_INSTANCE(wchar_t, wchar_t, WCHAR_MIN) 3310CILK_C_REDUCER_MAX_INDEX_INSTANCE(short, short, SHRT_MIN) 3311CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned short, ushort, 0) 3312CILK_C_REDUCER_MAX_INDEX_INSTANCE(int, int, INT_MIN) 3313CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned int, uint, 0) 3314CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned int, unsigned, 0) // alternate name 3315CILK_C_REDUCER_MAX_INDEX_INSTANCE(long, long, LONG_MIN) 3316CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned long, ulong, 0) 3317CILK_C_REDUCER_MAX_INDEX_INSTANCE(long long, longlong, LLONG_MIN) 3318CILK_C_REDUCER_MAX_INDEX_INSTANCE(unsigned long long, ulonglong, 0) 3319CILK_C_REDUCER_MAX_INDEX_INSTANCE(float, float, -HUGE_VALF) 3320CILK_C_REDUCER_MAX_INDEX_INSTANCE(double, double, -HUGE_VAL) 3321CILK_C_REDUCER_MAX_INDEX_INSTANCE(long double, longdouble, -HUGE_VALL) 3322__CILKRTS_END_EXTERN_C 3323 3324/// @endcond 3325 3326/** Min reducer type name. 3327 * 3328 * This macro expands into the identifier which is the name of the min reducer 3329 * type for a specified numeric type. 3330 * 3331 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3332 * reducer. 3333 * 3334 * @see @ref reducers_c_predefined 3335 */ 3336#define CILK_C_REDUCER_MIN_TYPE(tn) \ 3337 __CILKRTS_MKIDENT(cilk_c_reducer_min_,tn) 3338 3339/** Declare a min reducer object. 3340 * 3341 * This macro expands into a declaration of a min reducer object for a specified numeric 3342 * type. For example: 3343 * 3344 * CILK_C_REDUCER_MIN(my_reducer, double, DBL_MAX); 3345 * 3346 * @param obj The variable name to be used for the declared reducer object. 3347 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3348 * reducer. 3349 * @param v The initial value for the reducer. (A value which can be assigned to the 3350 * numeric type represented by @a tn.) 3351 * 3352 * @see @ref reducers_c_predefined 3353 */ 3354#define CILK_C_REDUCER_MIN(obj,tn,v) \ 3355 CILK_C_REDUCER_MIN_TYPE(tn) obj = \ 3356 CILK_C_INIT_REDUCER(_Typeof(obj.value), \ 3357 __CILKRTS_MKIDENT(cilk_c_reducer_min_reduce_,tn), \ 3358 __CILKRTS_MKIDENT(cilk_c_reducer_min_identity_,tn), \ 3359 __cilkrts_hyperobject_noop_destroy, v) 3360 3361/** Minimize with a value. 3362 * 3363 * `CILK_C_REDUCER_MIN_CALC(reducer, v)` sets the current view of the 3364 * reducer to the min of its previous value and a specified new value. 3365 * This is equivalent to 3366 * 3367 * REDUCER_VIEW(reducer) = min(REDUCER_VIEW(reducer), v) 3368 * 3369 * @param reducer The reducer whose contained value is to be updated. 3370 * @param v The value that it is to be minimized with. 3371 */ 3372#define CILK_C_REDUCER_MIN_CALC(reducer, v) do { \ 3373 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \ 3374 _Typeof(v) __value = (v); \ 3375 if (*view > __value) { \ 3376 *view = __value; \ 3377 } } while (0) 3378 3379/// @cond internal 3380 3381/** Declare the min reducer functions for a numeric type. 3382 * 3383 * This macro expands into external function declarations for functions which implement 3384 * the reducer functionality for the min reducer type for a specified numeric type. 3385 * 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. 3389 */ 3390#define CILK_C_REDUCER_MIN_DECLARATION(t,tn,id) \ 3391 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MIN_TYPE(tn); \ 3392 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min,tn,l,r); \ 3393 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min,tn); 3394 3395/** Define the min reducer functions for a numeric type. 3396 * 3397 * This macro expands into function definitions for functions which implement the 3398 * reducer functionality for the min reducer type for a specified numeric type. 3399 * 3400 * @param t The value type of the reducer. 3401 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3402 * function names, etc. 3403 */ 3404#define CILK_C_REDUCER_MIN_DEFINITION(t,tn,id) \ 3405 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_MIN_TYPE(tn); \ 3406 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min,tn,l,r) \ 3407 { if (*(t*)l > *(t*)r) *(t*)l = *(t*)r; } \ 3408 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min,tn) \ 3409 { *(t*)v = id; } 3410 3411//@{ 3412/** @def CILK_C_REDUCER_MIN_INSTANCE 3413 * @brief Declare or define implementation functions for a reducer type. 3414 * 3415 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and 3416 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS` 3417 * will be undefined, and this macro will expand into external declarations for the functions. 3418 */ 3419#ifdef CILK_C_DEFINE_REDUCERS 3420# define CILK_C_REDUCER_MIN_INSTANCE(t,tn,id) \ 3421 CILK_C_REDUCER_MIN_DEFINITION(t,tn,id) 3422#else 3423# define CILK_C_REDUCER_MIN_INSTANCE(t,tn,id) \ 3424 CILK_C_REDUCER_MIN_DECLARATION(t,tn,id) 3425#endif 3426//@} 3427 3428/* Declare or define an instance of the reducer type and its functions for each 3429 * numeric type. 3430 */ 3431__CILKRTS_BEGIN_EXTERN_C 3432CILK_C_REDUCER_MIN_INSTANCE(char, char, CHAR_MAX) 3433CILK_C_REDUCER_MIN_INSTANCE(unsigned char, uchar, CHAR_MAX) 3434CILK_C_REDUCER_MIN_INSTANCE(signed char, schar, SCHAR_MAX) 3435CILK_C_REDUCER_MIN_INSTANCE(wchar_t, wchar_t, WCHAR_MAX) 3436CILK_C_REDUCER_MIN_INSTANCE(short, short, SHRT_MAX) 3437CILK_C_REDUCER_MIN_INSTANCE(unsigned short, ushort, USHRT_MAX) 3438CILK_C_REDUCER_MIN_INSTANCE(int, int, INT_MAX) 3439CILK_C_REDUCER_MIN_INSTANCE(unsigned int, uint, UINT_MAX) 3440CILK_C_REDUCER_MIN_INSTANCE(unsigned int, unsigned, UINT_MAX) // alternate name 3441CILK_C_REDUCER_MIN_INSTANCE(long, long, LONG_MAX) 3442CILK_C_REDUCER_MIN_INSTANCE(unsigned long, ulong, ULONG_MAX) 3443CILK_C_REDUCER_MIN_INSTANCE(long long, longlong, LLONG_MAX) 3444CILK_C_REDUCER_MIN_INSTANCE(unsigned long long, ulonglong, ULLONG_MAX) 3445CILK_C_REDUCER_MIN_INSTANCE(float, float, HUGE_VALF) 3446CILK_C_REDUCER_MIN_INSTANCE(double, double, HUGE_VAL) 3447CILK_C_REDUCER_MIN_INSTANCE(long double, longdouble, HUGE_VALL) 3448__CILKRTS_END_EXTERN_C 3449 3450/// @endcond 3451 3452/** Min_index reducer type name. 3453 * 3454 * This macro expands into the identifier which is the name of the min_index reducer 3455 * type for a specified numeric type. 3456 * 3457 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3458 * reducer. 3459 * 3460 * @see @ref reducers_c_predefined 3461 */ 3462#define CILK_C_REDUCER_MIN_INDEX_TYPE(tn) \ 3463 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_,tn) 3464 3465/** Declare an op_min_index reducer object. 3466 * 3467 * This macro expands into a declaration of a min_index reducer object for a specified 3468 * numeric type. For example: 3469 * 3470 * CILK_C_REDUCER_MIN_INDEX(my_reducer, double, -DBL_MIN_INDEX); 3471 * 3472 * @param obj The variable name to be used for the declared reducer object. 3473 * @param tn The @ref reducers_c_type_names "numeric type name" specifying the type of the 3474 * reducer. 3475 * @param v The initial value for the reducer. (A value which can be assigned to the 3476 * numeric type represented by @a tn.) 3477 * 3478 * @see @ref reducers_c_predefined 3479 */ 3480#define CILK_C_REDUCER_MIN_INDEX(obj,tn,v) \ 3481 CILK_C_REDUCER_MIN_INDEX_TYPE(tn) obj = \ 3482 CILK_C_INIT_REDUCER(_Typeof(obj.value), \ 3483 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_reduce_,tn), \ 3484 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_identity_,tn), \ 3485 __cilkrts_hyperobject_noop_destroy, {0, v}) 3486 3487/** Minimize with a value. 3488 * 3489 * `CILK_C_REDUCER_MIN_INDEX_CALC(reducer, i, v)` sets the current view of the 3490 * reducer to the min of its previous value and a specified new value. 3491 * This is equivalent to 3492 * 3493 * REDUCER_VIEW(reducer) = min_index(REDUCER_VIEW(reducer), v) 3494 * 3495 * If the value of the reducer is changed to @a v, then the index of the reducer is 3496 * changed to @a i. 3497 * 3498 * @param reducer The reducer whose contained value and index are to be updated. 3499 * @param i The index associated with the new value. 3500 * @param v The value that it is to be minimized with. 3501 */ 3502#define CILK_C_REDUCER_MIN_INDEX_CALC(reducer, i, v) do { \ 3503 _Typeof((reducer).value)* view = &(REDUCER_VIEW(reducer)); \ 3504 _Typeof(v) __value = (v); \ 3505 if (view->value > __value) { \ 3506 view->index = (i); \ 3507 view->value = __value; \ 3508 } } while (0) 3509 3510/// @cond internal 3511 3512/** Declare the min_index view type. 3513 * 3514 * The view of a min_index reducer is a structure containing both the 3515 * minimum value for the reducer and the index that was associated with 3516 * that value in the sequence of input values. 3517 */ 3518#define CILK_C_REDUCER_MIN_INDEX_VIEW(t,tn) \ 3519 typedef struct { \ 3520 __STDNS ptrdiff_t index; \ 3521 t value; \ 3522 } __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn) 3523 3524/** Declare the min_index reducer functions for a numeric type. 3525 * 3526 * This macro expands into external function declarations for functions which implement 3527 * the reducer functionality for the min_index reducer type for a specified numeric type. 3528 * 3529 * @param t The value type of the reducer. 3530 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3531 * function names, etc. 3532 */ 3533#define CILK_C_REDUCER_MIN_INDEX_DECLARATION(t,tn,id) \ 3534 CILK_C_REDUCER_MIN_INDEX_VIEW(t,tn); \ 3535 typedef CILK_C_DECLARE_REDUCER( \ 3536 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn)) \ 3537 CILK_C_REDUCER_MIN_INDEX_TYPE(tn); \ 3538 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min_index,tn,l,r); \ 3539 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min_index,tn); 3540 3541/** Define the min_index reducer functions for a numeric type. 3542 * 3543 * This macro expands into function definitions for functions which implement the 3544 * reducer functionality for the min_index reducer type for a specified numeric type. 3545 * 3546 * @param t The value type of the reducer. 3547 * @param tn The value ���type name��� identifier, used to construct the reducer type name, 3548 * function names, etc. 3549 */ 3550#define CILK_C_REDUCER_MIN_INDEX_DEFINITION(t,tn,id) \ 3551 CILK_C_REDUCER_MIN_INDEX_VIEW(t,tn); \ 3552 typedef CILK_C_DECLARE_REDUCER( \ 3553 __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn)) \ 3554 CILK_C_REDUCER_MIN_INDEX_TYPE(tn); \ 3555 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_min_index,tn,l,r) \ 3556 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn) view_t; \ 3557 if (((view_t*)l)->value > ((view_t*)r)->value) \ 3558 *(view_t*)l = *(view_t*)r; } \ 3559 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_min_index,tn) \ 3560 { typedef __CILKRTS_MKIDENT(cilk_c_reducer_min_index_view_,tn) view_t; \ 3561 ((view_t*)v)->index = 0; ((view_t*)v)->value = id; } 3562 3563//@{ 3564/** @def CILK_C_REDUCER_MIN_INDEX_INSTANCE 3565 * @brief Declare or define implementation functions for a reducer type. 3566 * 3567 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS` will be defined, and 3568 * this macro will generate reducer implementation functions. Everywhere else, `CILK_C_DEFINE_REDUCERS` 3569 * will be undefined, and this macro will expand into external declarations for the functions. 3570 */ 3571#ifdef CILK_C_DEFINE_REDUCERS 3572# define CILK_C_REDUCER_MIN_INDEX_INSTANCE(t,tn,id) \ 3573 CILK_C_REDUCER_MIN_INDEX_DEFINITION(t,tn,id) 3574#else 3575# define CILK_C_REDUCER_MIN_INDEX_INSTANCE(t,tn,id) \ 3576 CILK_C_REDUCER_MIN_INDEX_DECLARATION(t,tn,id) 3577#endif 3578//@} 3579 3580/* Declare or define an instance of the reducer type and its functions for each 3581 * numeric type. 3582 */ 3583__CILKRTS_BEGIN_EXTERN_C 3584CILK_C_REDUCER_MIN_INDEX_INSTANCE(char, char, CHAR_MAX) 3585CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned char, uchar, CHAR_MAX) 3586CILK_C_REDUCER_MIN_INDEX_INSTANCE(signed char, schar, SCHAR_MAX) 3587CILK_C_REDUCER_MIN_INDEX_INSTANCE(wchar_t, wchar_t, WCHAR_MAX) 3588CILK_C_REDUCER_MIN_INDEX_INSTANCE(short, short, SHRT_MAX) 3589CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned short, ushort, USHRT_MAX) 3590CILK_C_REDUCER_MIN_INDEX_INSTANCE(int, int, INT_MAX) 3591CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned int, uint, UINT_MAX) 3592CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned int, unsigned, UINT_MAX) // alternate name 3593CILK_C_REDUCER_MIN_INDEX_INSTANCE(long, long, LONG_MAX) 3594CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned long, ulong, ULONG_MAX) 3595CILK_C_REDUCER_MIN_INDEX_INSTANCE(long long, longlong, LLONG_MAX) 3596CILK_C_REDUCER_MIN_INDEX_INSTANCE(unsigned long long, ulonglong, ULLONG_MAX) 3597CILK_C_REDUCER_MIN_INDEX_INSTANCE(float, float, HUGE_VALF) 3598CILK_C_REDUCER_MIN_INDEX_INSTANCE(double, double, HUGE_VAL) 3599CILK_C_REDUCER_MIN_INDEX_INSTANCE(long double, longdouble, HUGE_VALL) 3600__CILKRTS_END_EXTERN_C 3601 3602/// @endcond 3603 3604//@} 3605 3606#endif // defined REDUCER_MAX_H_INCLUDED 3607