1 /* reducer_list.h -*- C++ -*-
3 * Copyright (C) 2009-2016, Intel Corporation
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
16 * * Neither the name of Intel Corporation nor the names of its
17 * contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
27 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
30 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
33 * *********************************************************************
35 * PLEASE NOTE: This file is a downstream copy of a file mainitained in
36 * a repository at cilkplus.org. Changes made to this file that are not
37 * submitted through the contribution process detailed at
38 * http://www.cilkplus.org/submit-cilk-contribution will be lost the next
39 * time that a new version is released. Changes only submitted to the
40 * GNU compiler collection or posted to the git repository at
41 * https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are
44 * We welcome your contributions to this open source project. Thank you
45 * for your assistance in helping us improve Cilk Plus.
48 /** @file reducer_list.h
50 * @brief Defines classes for parallel list creation by appending or
51 * prepending reducers.
53 * @ingroup ReducersList
58 #ifndef REDUCER_LIST_H_INCLUDED
59 #define REDUCER_LIST_H_INCLUDED
61 #include <cilk/reducer.h>
64 /** @defgroup ReducersList List Reducers
66 * List-append and list-prepend reducers create standard lists by
67 * concatenating a set of lists or values in parallel.
71 * You should be familiar with @ref pagereducers "Intel(R) Cilk(TM) Plus reducers"
72 * (from file `reducers.md`) and particularly with @ref reducers_using, before
73 * trying to use the information in this file.
75 * @section redlist_usage Usage Example
77 * // Create a list containing the labels of the nodes of a tree in
78 * // "inorder" (left subtree, root, right subtree).
80 * struct Tree { Tree* left; Tree* right; string label; ... };
83 * cilk::reducer< cilk::op_list_append<string> > xr(cilk::move_in(x));
84 * collect_labels(tree, xr);
87 * void collect_labels(Tree* node,
88 * cilk::reducer< cilk::op_list_append<string> >& xr)
91 * cilk_spawn collect_labels(node->left, xr);
92 * xr->push_back(node->label);
93 * collect_labels(node->right, xr);
98 * @section redlist_monoid The Monoid
100 * @subsection redlist_monoid_values Value Set
102 * The __value set__ of a list reducer is the set of values of the class
103 * `std::list<Type, Allocator>`, which we refer to as the reducer's _list
106 * @subsection redlist_monoid_operator Operator
108 * The operator of a list-append reducer is defined as
110 * x CAT y == (every element of x, followed by every element of y)
112 * The operator of a list-prepend reducer is defined as
114 * x RCAT y == (every element of y, followed by every element of x)
116 * @subsection redlist_monoid_identity Identity
118 * The identity value of a list reducer is the empty list, which is the value
119 * of the expression `std::list<Type, Allocator>([allocator])`.
121 * @section redlist_operations Operations
123 * In the operation descriptions below, the type name `List` refers to the
124 * reducer's string type, `std::list<Type, Allocator>`.
126 * @subsection redlist_constructors Constructors
128 * Any argument list which is valid for a `std::list` constructor is valid for
129 * a list reducer constructor. The usual move-in constructor is also provided:
131 * reducer(move_in(List& variable))
133 * A list reducer with no constructor arguments, or with only an allocator
134 * argument, will initially contain the identity value, an empty list.
136 * @subsection redlist_get_set Set and Get
138 * r.set_value(const List& value)
139 * const List& = r.get_value() const
140 * r.move_in(List& variable)
141 * r.move_out(List& variable)
143 * @subsection redlist_view_ops View Operations
145 * The view of a list-append reducer provides the following member functions:
147 * void push_back(const Type& element)
148 * void insert_back(List::size_type n, const Type& element)
149 * template <typename Iter> void insert_back(Iter first, Iter last)
150 * void splice_back(List& x)
151 * void splice_back(List& x, List::iterator i)
152 * void splice_back(List& x, List::iterator first, List::iterator last)
154 * The view of a list-prepend reducer provides the following member functions:
156 * void push_front(const Type& element)
157 * void insert_front(List::size_type n, const Type& element)
158 * template <typename Iter> void insert_front(Iter first, Iter last)
159 * void splice_front(List& x)
160 * void splice_front(List& x, List::iterator i)
161 * void splice_front(List& x, List::iterator first, List::iterator last)
163 * The `push_back` and `push_front` functions are the same as the
164 * corresponding `std::list` functions. The `insert_back`, `splice_back`,
165 * `insert_front`, and `splice_front` functions are the same as the
166 * `std::list` `insert` and `splice` functions, with the first parameter
167 * fixed to the end or beginning of the list, respectively.
169 * @section redlist_performance Performance Considerations
171 * An efficient reducer requires that combining the values of two views (using
172 * the view `reduce()` function) be a constant-time operations. Two lists can
173 * be merged in constant time using the `splice()` function if they have the
174 * same allocator. Therefore, the lists for new views are created (by the view
175 * identity constructor) using the same allocator as the list that was created
176 * when the reducer was constructed.
178 * The performance of adding elements to a list reducer depends on the view
179 * operations that are used:
181 * * The `push` functions add a single element to the list, and therefore
182 * take constant time.
183 * * An `insert` function that inserts _N_ elements adds each of them
184 * individually, and therefore takes _O(N)_ time.
185 * * A `splice` function that inserts _N_ elements just adjusts a couple of
186 * pointers, and therefore takes constant time, _if the splice is from a
187 * list with the same allocator as the reducer_. Otherwise, it is
188 * equivalent to an `insert`, and takes _O(N)_ time.
190 * This means that for best performance, if you will be adding elements to a
191 * list reducer in batches, you should `splice` them from a list having the
192 * same allocator as the reducer.
194 * The reducer `move_in` and `move_out` functions do a constant-time `swap` if
195 * the variable has the same allocator as the reducer, and a linear-time copy
198 * Note that the allocator of a list reducer is determined when the reducer is
199 * constructed. The following two examples may have very different behavior:
201 * list<Element, Allocator> a_list;
203 * reducer< list_append<Element, Allocator> reducer1(move_in(a_list));
204 * ... parallel computation ...
205 * reducer1.move_out(a_list);
207 * reducer< list_append<Element, Allocator> reducer2;
208 * reducer2.move_in(a_list);
209 * ... parallel computation ...
210 * reducer2.move_out(a_list);
212 * * `reducer1` will be constructed with the same allocator as `a_list`,
213 * because the list was specified in the constructor. The `move_in`
214 * and `move_out` can therefore be done with a `swap` in constant time.
215 * * `reducer2` will be constructed with a _default_ allocator,
216 * "`Allocator()`", which may or may not be the same as the allocator of
217 * `a_list`. Therefore, the `move_in` and `move_out` may have to be done
218 * with a copy in _O(N)_ time.
220 * (All instances of an allocator type with no internal state (like
221 * `std::allocator`) are "the same". You only need to worry about the "same
222 * allocator" issue when you create list reducers with custom allocator types.)
224 * @section redlist_types Type and Operator Requirements
226 * `std::list<Type, Allocator>` must be a valid type.
234 /** @ingroup ReducersList */
237 /** Base class for list-append and prepend view classes.
239 * @note This class provides the definitions that are required for a class
240 * that will be used as the parameter of a @ref list_monoid_base
243 * @tparam Type The list element type (not the list type).
244 * @tparam Allocator The list's allocator class.
247 * @see list_monoid_base
249 template <typename Type
, typename Allocator
>
253 /// The type of the contained list.
254 typedef std::list
<Type
, Allocator
> list_type
;
256 /// The list accumulator variable.
261 /** @name Monoid support.
265 /// Required by @ref monoid_with_view
266 typedef list_type value_type
;
268 /// Required by @ref list_monoid_base
269 Allocator
get_allocator() const
271 return m_value
.get_allocator();
277 /** @name Constructors.
281 /// Standard list constructor.
282 explicit list_view_base(const Allocator
& a
= Allocator()) : m_value(a
) {}
283 explicit list_view_base(
284 typename
list_type::size_type n
,
285 const Type
& value
= Type(),
286 const Allocator
& a
= Allocator() ) : m_value(n
, value
, a
) {}
287 template <typename Iter
>
288 list_view_base(Iter first
, Iter last
, const Allocator
& a
= Allocator()) :
289 m_value(first
, last
, a
) {}
290 list_view_base(const list_type
& list
) : m_value(list
) {}
292 /// Move-in constructor.
293 explicit list_view_base(move_in_wrapper
<value_type
> w
)
294 : m_value(w
.value().get_allocator())
296 m_value
.swap(w
.value());
301 /** @name Reducer support.
305 /// Required by reducer::move_in()
306 void view_move_in(value_type
& v
)
308 if (m_value
.get_allocator() == v
.get_allocator())
309 // Equal allocators. Do a (fast) swap.
312 // Unequal allocators. Do a (slow) copy.
317 /// Required by reducer::move_out()
318 void view_move_out(value_type
& v
)
320 if (m_value
.get_allocator() == v
.get_allocator())
321 // Equal allocators. Do a (fast) swap.
324 // Unequal allocators. Do a (slow) copy.
329 /// Required by reducer::set_value()
330 void view_set_value(const value_type
& v
) { m_value
= v
; }
332 /// Required by reducer::get_value()
333 value_type
const& view_get_value() const { return m_value
; }
335 /// Type returned by view_get_value.
336 typedef value_type
const& return_type_for_get_value
;
338 // Required by legacy wrapper get_reference()
339 value_type
& view_get_reference() { return m_value
; }
340 value_type
const& view_get_reference() const { return m_value
; }
346 /** Base class for list-append and prepend monoid classes.
348 * The key to efficient reducers is that the `identity` operation, which
349 * creates a new per-strand view, and the `reduce` operation, which combines
350 * two per-strand views, must be constant-time operations. Two lists can be
351 * concatenated in constant time only if they have the same allocator.
352 * Therefore, all the per-strand list accumulator variables must be created
353 * with the same allocator as the leftmost view list.
355 * This means that a list reduction monoid must have a copy of the allocator
356 * of the leftmost view's list, so that it can use it in the `identity`
357 * operation. This, in turn, requires that list reduction monoids have a
358 * specialized `construct()` function, which constructs the leftmost view
359 * before the monoid, and then passes the leftmost view's allocator to the
360 * monoid constructor.
362 * @tparam View The list-append or prepend view class.
363 * @tparam Align If `false` (the default), reducers instantiated on this
364 * monoid will be naturally aligned (the Intel Cilk Plus library 1.0
365 * behavior). If `true`, reducers instantiated on this monoid
366 * will be cache-aligned for binary compatibility with
367 * reducers in Intel Cilk Plus library version 0.9.
370 * @see list_view_base
372 template <typename View
, bool Align
>
373 class list_monoid_base
: public monoid_with_view
<View
, Align
>
375 typedef typename
View::value_type list_type
;
376 typedef typename
list_type::allocator_type allocator_type
;
377 typedef provisional_guard
<View
> view_guard
;
379 allocator_type m_allocator
;
385 * There is no default constructor for list monoids, because the allocator
386 * must always be specified.
388 * @param allocator The list allocator to be used when
389 * identity-constructing new views.
391 list_monoid_base(const allocator_type
& allocator
= allocator_type()) :
392 m_allocator(allocator
) {}
394 /** Creates an identity view.
396 * List view identity constructors take the list allocator as an argument.
398 * @param v The address of the uninitialized memory in which the view
399 * will be constructed.
401 void identity(View
*v
) const { ::new((void*) v
) View(m_allocator
); }
403 /** @name construct functions
405 * All `construct()` functions first construct the leftmost view, using
406 * the optional @a x1, @a x2, and @a x3 arguments that were passed in from
407 * the reducer constructor. They then call the view's `get_allocator()`
408 * function to get the list allocator from its contained list, and pass it
409 * to the monoid constructor.
413 template <typename Monoid
>
414 static void construct(Monoid
* monoid
, View
* view
)
416 view_guard
vg( new((void*) view
) View() );
417 vg
.confirm_if( new((void*) monoid
) Monoid(view
->get_allocator()) );
420 template <typename Monoid
, typename T1
>
421 static void construct(Monoid
* monoid
, View
* view
, const T1
& x1
)
423 view_guard
vg( new((void*) view
) View(x1
) );
424 vg
.confirm_if( new((void*) monoid
) Monoid(view
->get_allocator()) );
427 template <typename Monoid
, typename T1
, typename T2
>
428 static void construct(Monoid
* monoid
, View
* view
,
429 const T1
& x1
, const T2
& x2
)
431 view_guard
vg( new((void*) view
) View(x1
, x2
) );
432 vg
.confirm_if( new((void*) monoid
) Monoid(view
->get_allocator()) );
435 template <typename Monoid
, typename T1
, typename T2
, typename T3
>
436 static void construct(Monoid
* monoid
, View
* view
,
437 const T1
& x1
, const T2
& x2
, const T3
& x3
)
439 view_guard
vg( new((void*) view
) View(x1
, x2
, x3
) );
440 vg
.confirm_if( new((void*) monoid
) Monoid(view
->get_allocator()) );
448 } // namespace internal
451 /** @ingroup ReducersList */
454 /** The list-append reducer view class.
456 * This is the view class for reducers created with
457 * `cilk::reducer< cilk::op_list_append<Type, Allocator> >`. It holds the
458 * accumulator variable for the reduction, and allows only append operations
459 * to be performed on it.
461 * @note The reducer "dereference" operation (`reducer::operator *()`)
462 * yields a reference to the view. Thus, for example, the view class's
463 * `push_back` operation would be used in an expression like
464 * `r->push_back(a)`, where `r` is a list-append reducer variable.
466 * @tparam Type The list element type (not the list type).
467 * @tparam Allocator The list allocator type.
470 * @see op_list_append
472 template <class Type
,
473 class Allocator
= typename
std::list
<Type
>::allocator_type
>
474 class op_list_append_view
: public internal::list_view_base
<Type
, Allocator
>
476 typedef internal::list_view_base
<Type
, Allocator
> base
;
477 typedef std::list
<Type
, Allocator
> list_type
;
478 typedef typename
list_type::iterator iterator
;
480 iterator
end() { return this->m_value
.end(); }
484 /** @name Constructors.
486 * All op_list_append_view constructors simply pass their arguments on to
487 * the @ref internal::list_view_base base class constructor.
489 * @ref internal::list_view_base supports all the std::list constructor
490 * forms, as well as the reducer move_in constructor form.
494 op_list_append_view() : base() {}
496 template <typename T1
>
497 op_list_append_view(const T1
& x1
) : base(x1
) {}
499 template <typename T1
, typename T2
>
500 op_list_append_view(const T1
& x1
, const T2
& x2
) : base(x1
, x2
) {}
502 template <typename T1
, typename T2
, typename T3
>
503 op_list_append_view(const T1
& x1
, const T2
& x2
, const T3
& x3
) :
508 /** @name View modifier operations.
512 /** Adds an element at the end of the list.
514 * This is equivalent to `list.push_back(element)`
516 void push_back(const Type
& element
)
517 { this->m_value
.push_back(element
); }
519 /** Inserts elements at the end of the list.
521 * This is equivalent to `list.insert(list.end(), n, element)`
523 void insert_back(typename
list_type::size_type n
, const Type
& element
)
524 { this->m_value
.insert(end(), n
, element
); }
526 /** Inserts elements at the end of the list.
528 * This is equivalent to `list.insert(list.end(), first, last)`
530 template <typename Iter
>
531 void insert_back(Iter first
, Iter last
)
532 { this->m_value
.insert(end(), first
, last
); }
534 /** Splices elements at the end of the list.
536 * This is equivalent to `list.splice(list.end(), x)`
538 void splice_back(list_type
& x
) {
539 if (x
.get_allocator() == this->m_value
.get_allocator())
540 this->m_value
.splice(end(), x
);
542 insert_back(x
.begin(), x
.end());
547 /** Splices elements at the end of the list.
549 * This is equivalent to `list.splice(list.end(), x, i)`
551 void splice_back(list_type
& x
, iterator i
) {
552 if (x
.get_allocator() == this->m_value
.get_allocator())
553 this->m_value
.splice(end(), x
, i
);
560 /** Splices elements at the end of the list.
562 * This is equivalent to `list.splice(list.end(), x, first, last)`
564 void splice_back(list_type
& x
, iterator first
, iterator last
) {
565 if (x
.get_allocator() == this->m_value
.get_allocator())
566 this->m_value
.splice(end(), x
, first
, last
);
568 insert_back(first
, last
);
569 x
.erase(first
, last
);
575 /** Reduces the views of two strands.
577 * This function is invoked by the @ref op_list_append monoid to combine
578 * the views of two strands when the right strand merges with the left
579 * one. It appends the value contained in the right-strand view to the
580 * value contained in the left-strand view, and leaves the value in the
581 * right-strand view undefined.
583 * @param right A pointer to the right-strand view. (`this` points to
584 * the left-strand view.)
586 * @note Used only by the @ref op_list_append monoid to implement the
587 * monoid reduce operation.
589 void reduce(op_list_append_view
* right
)
592 this->m_value
.get_allocator() == right
->m_value
.get_allocator());
593 this->m_value
.splice(end(), right
->m_value
);
598 /** The list-prepend reducer view class.
600 * This is the view class for reducers created with
601 * `cilk::reducer< cilk::op_list_prepend<Type, Allocator> >`. It holds the
602 * accumulator variable for the reduction, and allows only prepend operations
603 * to be performed on it.
605 * @note The reducer "dereference" operation (`reducer::operator *()`)
606 * yields a reference to the view. Thus, for example, the view class's
607 * `push_front` operation would be used in an expression like
608 * `r->push_front(a)`, where `r` is a list-prepend reducer variable.
610 * @tparam Type The list element type (not the list type).
611 * @tparam Allocator The list allocator type.
614 * @see op_list_prepend
616 template <class Type
,
617 class Allocator
= typename
std::list
<Type
>::allocator_type
>
618 class op_list_prepend_view
: public internal::list_view_base
<Type
, Allocator
>
620 typedef internal::list_view_base
<Type
, Allocator
> base
;
621 typedef std::list
<Type
, Allocator
> list_type
;
622 typedef typename
list_type::iterator iterator
;
624 iterator
begin() { return this->m_value
.begin(); }
628 /** @name Constructors.
630 * All op_list_prepend_view constructors simply pass their arguments on to
631 * the @ref internal::list_view_base base class constructor.
633 * @ref internal::list_view_base supports all the std::list constructor
634 * forms, as well as the reducer move_in constructor form.
639 op_list_prepend_view() : base() {}
641 template <typename T1
>
642 op_list_prepend_view(const T1
& x1
) : base(x1
) {}
644 template <typename T1
, typename T2
>
645 op_list_prepend_view(const T1
& x1
, const T2
& x2
) : base(x1
, x2
) {}
647 template <typename T1
, typename T2
, typename T3
>
648 op_list_prepend_view(const T1
& x1
, const T2
& x2
, const T3
& x3
) :
653 /** @name View modifier operations.
657 /** Adds an element at the beginning of the list.
659 * This is equivalent to `list.push_front(element)`
661 void push_front(const Type
& element
)
662 { this->m_value
.push_front(element
); }
664 /** Inserts elements at the beginning of the list.
666 * This is equivalent to `list.insert(list.begin(), n, element)`
668 void insert_front(typename
list_type::size_type n
, const Type
& element
)
669 { this->m_value
.insert(begin(), n
, element
); }
671 /** Inserts elements at the beginning of the list.
673 * This is equivalent to `list.insert(list.begin(), first, last)`
675 template <typename Iter
>
676 void insert_front(Iter first
, Iter last
)
677 { this->m_value
.insert(begin(), first
, last
); }
679 /** Splices elements at the beginning of the list.
681 * This is equivalent to `list.splice(list.begin(), x)`
683 void splice_front(list_type
& x
) {
684 if (x
.get_allocator() == this->m_value
.get_allocator())
685 this->m_value
.splice(begin(), x
);
687 insert_front(x
.begin(), x
.begin());
692 /** Splices elements at the beginning of the list.
694 * This is equivalent to `list.splice(list.begin(), x, i)`
696 void splice_front(list_type
& x
, iterator i
) {
697 if (x
.get_allocator() == this->m_value
.get_allocator())
698 this->m_value
.splice(begin(), x
, i
);
705 /** Splices elements at the beginning of the list.
707 * This is equivalent to `list.splice(list.begin(), x, first, last)`
709 void splice_front(list_type
& x
, iterator first
, iterator last
) {
710 if (x
.get_allocator() == this->m_value
.get_allocator())
711 this->m_value
.splice(begin(), x
, first
, last
);
713 insert_front(first
, last
);
714 x
.erase(first
, last
);
720 /** Reduces the views of two strands.
722 * This function is invoked by the @ref op_list_prepend monoid to combine
723 * the views of two strands when the right strand merges with the left
724 * one. It prepends the value contained in the right-strand view to the
725 * value contained in the left-strand view, and leaves the value in the
726 * right-strand view undefined.
728 * @param right A pointer to the right-strand view. (`this` points to
729 * the left-strand view.)
731 * @note Used only by the @ref op_list_prepend monoid to implement the
732 * monoid reduce operation.
734 /** Reduce operation.
736 * Required by @ref monoid_base.
738 void reduce(op_list_prepend_view
* right
)
741 this->m_value
.get_allocator() == right
->m_value
.get_allocator());
742 this->m_value
.splice(begin(), right
->m_value
);
748 /** Monoid class for list-append reductions. Instantiate the cilk::reducer
749 * template class with a op_list_append monoid to create a list-append reducer
750 * class. For example, to create a list of strings:
752 * cilk::reducer< cilk::op_list_append<std::string> > r;
754 * @tparam Type The list element type (not the list type).
755 * @tparam Alloc The list allocator type.
756 * @tparam Align If `false` (the default), reducers instantiated on this
757 * monoid will be naturally aligned (the Intel Cilk Plus library 1.0
758 * behavior). If `true`, reducers instantiated on this monoid
759 * will be cache-aligned for binary compatibility with
760 * reducers in Intel Cilk Plus library version 0.9.
763 * @see op_list_append_view
765 template <typename Type
,
766 typename Allocator
= typename
std::list
<Type
>::allocator_type
,
768 struct op_list_append
:
769 public internal::list_monoid_base
<op_list_append_view
<Type
, Allocator
>, Align
>
771 /// Construct with default allocator.
773 /// Construct with specified allocator.
774 op_list_append(const Allocator
& alloc
) :
775 internal::list_monoid_base
<op_list_append_view
<Type
, Allocator
>, Align
>(alloc
) {}
778 /** Monoid class for list-prepend reductions. Instantiate the cilk::reducer
779 * template class with a op_list_prepend monoid to create a list-prepend
780 * reducer class. For example, to create a list of strings:
782 * cilk::reducer< cilk::op_list_prepend<std::string> > r;
784 * @tparam Type The list element type (not the list type).
785 * @tparam Alloc The list allocator type.
786 * @tparam Align If `false` (the default), reducers instantiated on this
787 * monoid will be naturally aligned (the Intel Cilk Plus library 1.0
788 * behavior). If `true`, reducers instantiated on this monoid
789 * will be cache-aligned for binary compatibility with
790 * reducers in Intel Cilk Plus library version 0.9.
793 * @see op_list_prepend_view
795 template <typename Type
,
796 typename Allocator
= typename
std::list
<Type
>::allocator_type
,
798 struct op_list_prepend
:
799 public internal::list_monoid_base
<op_list_prepend_view
<Type
, Allocator
>, Align
>
801 /// Construct with default allocator.
803 /// Construct with specified allocator.
804 op_list_prepend(const Allocator
& alloc
) :
805 internal::list_monoid_base
<op_list_prepend_view
<Type
, Allocator
>, Align
>(alloc
) {}
809 /** Deprecated list-append reducer wrapper class.
811 * reducer_list_append is the same as
812 * @ref reducer<@ref op_list_append>, except that reducer_list_append is a
813 * proxy for the contained view, so that accumulator variable update
814 * operations can be applied directly to the reducer. For example, an element
815 * is appended to a `reducer<%op_list_append>` with `r->push_back(a)`, but an
816 * element can be appended to a `%reducer_list_append` with `r.push_back(a)`.
818 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
819 * reducers rather than the old wrappers like reducer_list_append.
820 * The `reducer<monoid>` reducers show the reducer/monoid/view
821 * architecture more clearly, are more consistent in their
822 * implementation, and present a simpler model for new
823 * user-implemented reducers.
825 * @note Implicit conversions are provided between `%reducer_list_append`
826 * and `reducer<%op_list_append>`. This allows incremental code
827 * conversion: old code that used `%reducer_list_append` can pass a
828 * `%reducer_list_append` to a converted function that now expects a
829 * pointer or reference to a `reducer<%op_list_append>`, and vice
832 * @tparam Type The value type of the list.
833 * @tparam Allocator The allocator type of the list.
835 * @see op_list_append
839 template <class Type
, class Allocator
= std::allocator
<Type
> >
840 class reducer_list_append
:
841 public reducer
<op_list_append
<Type
, Allocator
, true> >
843 typedef reducer
<op_list_append
<Type
, Allocator
, true> > base
;
847 /// The reducer's list type.
848 typedef typename
base::value_type list_type
;
850 /// The list's element type.
851 typedef Type list_value_type
;
853 /// The reducer's primitive component type.
854 typedef Type basic_value_type
;
857 typedef typename
base::monoid_type Monoid
;
859 /** @name Constructors
863 /** Constructs a reducer with an empty list.
865 reducer_list_append() {}
867 /** Constructs a reducer with a specified initial list value.
869 reducer_list_append(const std::list
<Type
, Allocator
> &initial_value
) :
870 base(initial_value
) {}
875 /** @name Forwarded functions
876 * @details Functions that update the contained accumulator variable are
877 * simply forwarded to the contained @ref op_and_view. */
880 /// @copydoc op_list_append_view::push_back(const Type&)
881 void push_back(const Type
& element
) { view().push_back(element
); }
885 /** Allows mutable access to the list within the current view.
887 * @warning If this method is called before the parallel calculation is
888 * complete, the list returned by this method will be a partial
891 * @returns A mutable reference to the list within the current view.
893 list_type
&get_reference() { return view().view_get_reference(); }
895 /** Allows read-only access to the list within the current view.
897 * @warning If this method is called before the parallel calculation is
898 * complete, the list returned by this method will be a partial
901 * @returns A const reference to the list within the current view.
903 list_type
const &get_reference() const { return view().view_get_reference(); }
905 /// @name Dereference
907 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
908 * Combined with the rule that a wrapper forwards view operations to the
909 * view, this means that view operations can be written the same way on
910 * reducers and wrappers, which is convenient for incrementally
911 * converting code using wrappers to code using reducers. That is:
913 * reducer< op_list_append<int> > r;
914 * r->push_back(a); // *r returns the view
915 * // push_back is a view member function
917 * reducer_list_append<int> w;
918 * w->push_back(a); // *w returns the wrapper
919 * // push_back is a wrapper member function that
920 * // calls the corresponding view function
923 reducer_list_append
& operator*() { return *this; }
924 reducer_list_append
const& operator*() const { return *this; }
926 reducer_list_append
* operator->() { return this; }
927 reducer_list_append
const* operator->() const { return this; }
931 * @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
932 * In library 1.0, reducer cache alignment is optional. By default,
933 * reducers are unaligned (i.e., just naturally aligned), but legacy
934 * wrappers inherit from cache-aligned reducers for binary compatibility.
936 * This means that a wrapper will automatically be upcast to its aligned
937 * reducer base class. The following conversion operators provide
938 * pseudo-upcasts to the corresponding unaligned reducer class.
941 operator reducer
< op_list_append
<Type
, Allocator
, false> >& ()
943 return *reinterpret_cast<
944 reducer
< op_list_append
<Type
, Allocator
, false> >*
947 operator const reducer
< op_list_append
<Type
, Allocator
, false> >& () const
949 return *reinterpret_cast<
950 const reducer
< op_list_append
<Type
, Allocator
, false> >*
958 /** Deprecated list-prepend reducer wrapper class.
960 * reducer_list_prepend is the same as
961 * @ref reducer<@ref op_list_prepend>, except that reducer_list_prepend is a
962 * proxy for the contained view, so that accumulator variable update operations
963 * can be applied directly to the reducer. For example, an element is prepended
964 * to a `reducer<op_list_prepend>` with `r->push_back(a)`, but an element is
965 * prepended to a `reducer_list_prepend` with `r.push_back(a)`.
967 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
968 * reducers rather than the old wrappers like reducer_list_prepend.
969 * The `reducer<monoid>` reducers show the reducer/monoid/view
970 * architecture more clearly, are more consistent in their
971 * implementation, and present a simpler model for new
972 * user-implemented reducers.
974 * @note Implicit conversions are provided between `%reducer_list_prepend`
975 * and `reducer<%op_list_prepend>`. This allows incremental code
976 * conversion: old code that used `%reducer_list_prepend` can pass a
977 * `%reducer_list_prepend` to a converted function that now expects a
978 * pointer or reference to a `reducer<%op_list_prepend>`, and vice
981 * @tparam Type The value type of the list.
982 * @tparam Allocator The allocator type of the list.
984 * @see op_list_prepend
988 template <class Type
, class Allocator
= std::allocator
<Type
> >
989 class reducer_list_prepend
:
990 public reducer
<op_list_prepend
<Type
, Allocator
, true> >
992 typedef reducer
<op_list_prepend
<Type
, Allocator
, true> > base
;
996 /** The reducer's list type.
998 typedef typename
base::value_type list_type
;
1000 /** The list's element type.
1002 typedef Type list_value_type
;
1004 /** The reducer's primitive component type.
1006 typedef Type basic_value_type
;
1008 /** The monoid type.
1010 typedef typename
base::monoid_type Monoid
;
1012 /** @name Constructors
1016 /** Constructs a reducer with an empty list.
1018 reducer_list_prepend() {}
1020 /** Constructs a reducer with a specified initial list value.
1022 reducer_list_prepend(const std::list
<Type
, Allocator
> &initial_value
) :
1023 base(initial_value
) {}
1027 /** @name Forwarded functions
1028 * @details Functions that update the contained accumulator variable are
1029 * simply forwarded to the contained @ref op_and_view.
1033 /// @copydoc op_list_prepend_view::push_front(const Type&)
1034 void push_front(const Type
& element
) { view().push_front(element
); }
1038 /** Allows mutable access to the list within the current view.
1040 * @warning If this method is called before the parallel calculation is
1041 * complete, the list returned by this method will be a partial
1044 * @returns A mutable reference to the list within the current view.
1046 list_type
&get_reference() { return view().view_get_reference(); }
1048 /** Allows read-only access to the list within the current view.
1050 * @warning If this method is called before the parallel calculation is
1051 * complete, the list returned by this method will be a partial
1054 * @returns A const reference to the list within the current view.
1056 list_type
const &get_reference() const { return view().view_get_reference(); }
1058 /// @name Dereference
1059 /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
1060 * Combined with the rule that a wrapper forwards view operations to the
1061 * view, this means that view operations can be written the same way on
1062 * reducers and wrappers, which is convenient for incrementally
1063 * converting code using wrappers to code using reducers. That is:
1065 * reducer< op_list_prepend<int> > r;
1066 * r->push_front(a); // *r returns the view
1067 * // push_front is a view member function
1069 * reducer_list_prepend<int> w;
1070 * w->push_front(a); // *w returns the wrapper
1071 * // push_front is a wrapper member function that
1072 * // calls the corresponding view function
1075 reducer_list_prepend
& operator*() { return *this; }
1076 reducer_list_prepend
const& operator*() const { return *this; }
1078 reducer_list_prepend
* operator->() { return this; }
1079 reducer_list_prepend
const* operator->() const { return this; }
1083 * @details In Intel Cilk Plus library 0.9, reducers were always cache-aligned.
1084 * In library 1.0, reducer cache alignment is optional. By default,
1085 * reducers are unaligned (i.e., just naturally aligned), but legacy
1086 * wrappers inherit from cache-aligned reducers for binary compatibility.
1088 * This means that a wrapper will automatically be upcast to its aligned
1089 * reducer base class. The following conversion operators provide
1090 * pseudo-upcasts to the corresponding unaligned reducer class.
1093 operator reducer
< op_list_prepend
<Type
, Allocator
, false> >& ()
1095 return *reinterpret_cast<
1096 reducer
< op_list_prepend
<Type
, Allocator
, false> >*
1099 operator const reducer
< op_list_prepend
<Type
, Allocator
, false> >& () const
1101 return *reinterpret_cast<
1102 const reducer
< op_list_prepend
<Type
, Allocator
, false> >*
1111 /** Metafunction specialization for reducer conversion.
1113 * This specialization of the @ref legacy_reducer_downcast template class
1114 * defined in reducer.h causes the `reducer< op_list_append<Type, Allocator> >`
1115 * class to have an `operator reducer_list_append<Type, Allocator>& ()`
1116 * conversion operator that statically downcasts the `reducer<op_list_append>`
1117 * to the corresponding `reducer_list_append` type. (The reverse conversion,
1118 * from `reducer_list_append` to `reducer<op_list_append>`, is just an upcast,
1119 * which is provided for free by the language.)
1121 template <class Type
, class Allocator
, bool Align
>
1122 struct legacy_reducer_downcast
<reducer
<op_list_append
<Type
, Allocator
, Align
> > >
1124 typedef reducer_list_append
<Type
, Allocator
> type
;
1127 /** Metafunction specialization for reducer conversion.
1129 * This specialization of the @ref legacy_reducer_downcast template class
1130 * defined in reducer.h causes the
1131 * `reducer< op_list_prepend<Type, Allocator> >` class to have an
1132 * `operator reducer_list_prepend<Type, Allocator>& ()` conversion operator
1133 * that statically downcasts the `reducer<op_list_prepend>` to the
1134 * corresponding `reducer_list_prepend` type. (The reverse conversion, from
1135 * `reducer_list_prepend` to `reducer<op_list_prepend>`, is just an upcast,
1136 * which is provided for free by the language.)
1138 template <class Type
, class Allocator
, bool Align
>
1139 struct legacy_reducer_downcast
<reducer
<op_list_prepend
<Type
, Allocator
, Align
> > >
1141 typedef reducer_list_prepend
<Type
, Allocator
> type
;
1148 } // Close namespace cilk
1150 #endif // REDUCER_LIST_H_INCLUDED