1 /* reducer_opxor.h -*- C++ -*-
4 * Copyright (C) 2009-2013, Intel Corporation
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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
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.
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.
37 /** @file reducer_opxor.h
39 * @brief Defines classes for doing parallel bitwise or reductions.
41 * @ingroup ReducersXor
46 #ifndef REDUCER_OPXOR_H_INCLUDED
47 #define REDUCER_OPXOR_H_INCLUDED
49 #include <cilk/reducer.h>
51 /** @defgroup ReducersXor Bitwise Xor Reducers
53 * Bitwise and reducers allow the computation of the bitwise and of a set of
58 * You should be familiar with @ref pagereducers "Cilk reducers", described in
59 * file `reducers.md`, and particularly with @ref reducers_using, before trying
60 * to use the information in this file.
62 * @section redopxor_usage Usage Example
64 * cilk::reducer< cilk::op_xor<unsigned> > r;
65 * cilk_for (int i = 0; i != N; ++i) {
71 * @section redopxor_monoid The Monoid
73 * @subsection redopxor_monoid_values Value Set
75 * The value set of a bitwise xor reducer is the set of values of `Type`, which
76 * is expected to be a builtin integer type which has a representation as a
77 * sequence of bits (or something like it, such as `bool` or `std::bitset`).
79 * @subsection redopxor_monoid_operator Operator
81 * The operator of a bitwise xor reducer is the bitwise xor operator, defined
82 * by the “`^`” binary operator on `Type`.
84 * @subsection redopxor_monoid_identity Identity
86 * The identity value of the reducer is the value whose representation
87 * contains all 0-bits. This is expected to be the value of the default
88 * constructor `Type()`.
90 * @section redopxor_operations Operations
92 * @subsection redopxor_constructors Constructors
94 * reducer() // identity
95 * reducer(const Type& value)
96 * reducer(move_in(Type& variable))
98 * @subsection redopxor_get_set Set and Get
100 * r.set_value(const Type& value)
101 * const Type& = r.get_value() const
102 * r.move_in(Type& variable)
103 * r.move_out(Type& variable)
105 * @subsection redopxor_initial Initial Values
107 * If a bitwise xor reducer is constructed without an explicit initial value,
108 * then its initial value will be its identity value, as long as `Type`
109 * satisfies the requirements of @ref redopxor_types.
111 * @subsection redopxor_view_ops View Operations
115 * *r = *r ^ a1 ^ a2 … ^ an
117 * @section redopxor_types Type and Operator Requirements
119 * `Type` must be `Copy Constructible`, `Default Constructible`, and
122 * The operator “`^=`” must be defined on `Type`, with `x ^= a` having the
123 * same meaning as `x = x ^ a`.
125 * The expression `Type()` must be a valid expression which yields the
126 * identity value (the value of `Type` whose representation consists of all
129 * @section redopxor_in_c Bitwise Xor Reducers in C
131 * The @ref CILK_C_REDUCER_OPXOR and @ref CILK_C_REDUCER_OPXOR_TYPE macros can
132 * be used to do bitwise xor reductions in C. For example:
134 * CILK_C_REDUCER_OPXOR(r, uint, 0);
135 * CILK_C_REGISTER_REDUCER(r);
136 * cilk_for(int i = 0; i != n; ++i) {
137 * REDUCER_VIEW(r) ^= a[i];
139 * CILK_C_UNREGISTER_REDUCER(r);
140 * printf("The bitwise XOR of the elements of a is %x\n", REDUCER_VIEW(r));
142 * See @ref reducers_c_predefined.
149 /** The bitwise xor reducer view class.
151 * This is the view class for reducers created with
152 * `cilk::reducer< cilk::op_xor<Type> >`. It holds the accumulator variable
153 * for the reduction, and allows only `xor` operations to be performed on it.
155 * @note The reducer “dereference” operation (`reducer::operator *()`)
156 * yields a reference to the view. Thus, for example, the view class’s
157 * `^=` operation would be used in an expression like `*r ^= a`, where
158 * `r` is an opmod reducer variable.
160 * @tparam Type The type of the contained accumulator variable. This will
161 * be the value type of a monoid_with_view that is
162 * instantiated with this view.
167 * @ingroup ReducersXor
169 template <typename Type
>
170 class op_xor_view
: public scalar_view
<Type
>
172 typedef scalar_view
<Type
> base
;
175 /** Class to represent the right-hand side of `*reducer = *reducer ^ value`.
177 * The only assignment operator for the op_xor_view class takes an
178 * rhs_proxy as its operand. This results in the syntactic restriction
179 * that the only expressions that can be assigned to an op_xor_view are
180 * ones which generate an rhs_proxy — that is, expressions of the form
181 * `op_xor_view ^ value ... ^ value`.
184 * The lhs and rhs views in such an assignment must be the same;
185 * otherwise, the behavior will be undefined. (I.e., `v1 = v1 ^ x` is
186 * legal; `v1 = v2 ^ x` is illegal.) This condition will be checked with
187 * a runtime assertion when compiled in debug mode.
192 friend class op_xor_view
;
194 const op_xor_view
* m_view
;
197 // Constructor is invoked only from op_xor_view::operator^().
199 rhs_proxy(const op_xor_view
* view
, const Type
& value
) : m_view(view
), m_value(value
) {}
201 rhs_proxy
& operator=(const rhs_proxy
&); // Disable assignment operator
202 rhs_proxy(); // Disable default constructor
205 /** Bitwise xor with an additional rhs value. If `v` is an op_xor_view
206 * and `a1` is a value, then the expression `v ^ a1` invokes the
207 * view’s `operator^()` to create an rhs_proxy for `(v, a1)`; then
208 * `v ^ a1 ^ a2` invokes the rhs_proxy’s `operator^()` to create a new
209 * rhs_proxy for `(v, a1^a2)`. This allows the right-hand side of an
210 * assignment to be not just `view ^ value`, but
211 ( `view ^ value ^ value ... ^ value`. The effect is that
213 * v = v ^ a1 ^ a2 ... ^ an;
217 * v = v ^ (a1 ^ a2 ... ^ an);
219 rhs_proxy
& operator^(const Type
& x
) { m_value
^= x
; return *this; }
223 /** Default/identity constructor. This constructor initializes the
224 * contained value to `Type()`.
226 op_xor_view() : base() {}
228 /** Construct with a specified initial value.
230 explicit op_xor_view(const Type
& v
) : base(v
) {}
232 /** Reduction operation.
234 * This function is invoked by the @ref op_xor monoid to combine the views
235 * of two strands when the right strand merges with the left one. It
236 * “xors” the value contained in the left-strand view by the value
237 * contained in the right-strand view, and leaves the value in the
238 * right-strand view undefined.
240 * @param right A pointer to the right-strand view. (`this` points to
241 * the left-strand view.)
243 * @note Used only by the @ref op_xor monoid to implement the monoid
246 void reduce(op_xor_view
* right
) { this->m_value
^= right
->m_value
; }
248 /** @name Accumulator variable updates.
250 * These functions support the various syntaxes for “xoring” the
251 * accumulator variable contained in the view with some value.
255 /** Xor the accumulator variable with @a x.
257 op_xor_view
& operator^=(const Type
& x
) { this->m_value
^= x
; return *this; }
259 /** Create an object representing `*this ^ x`.
263 rhs_proxy
operator^(const Type
& x
) const { return rhs_proxy(this, x
); }
265 /** Assign the result of a `view ^ value` expression to the view. Note that
266 * this is the only assignment operator for this class.
270 op_xor_view
& operator=(const rhs_proxy
& rhs
) {
271 __CILKRTS_ASSERT(this == rhs
.m_view
);
272 this->m_value
^= rhs
.m_value
;
279 /** Monoid class for bitwise xor reductions. Instantiate the cilk::reducer
280 * template class with an op_xor monoid to create a bitwise xor reducer
281 * class. For example, to compute the bitwise xor of a set of `unsigned long`
284 * cilk::reducer< cilk::op_xor<unsigned long> > r;
286 * @tparam Type The reducer value type.
287 * @tparam Align If `false` (the default), reducers instantiated on this
288 * monoid will be naturally aligned (the Cilk library 1.0
289 * behavior). If `true`, reducers instantiated on this monoid
290 * will be cache-aligned for binary compatibility with
291 * reducers in Cilk library version 0.9.
296 * @ingroup ReducersXor
298 template <typename Type
, bool Align
= false>
299 struct op_xor
: public monoid_with_view
<op_xor_view
<Type
>, Align
> {};
301 /** Deprecated bitwise xor reducer class.
303 * reducer_opxor is the same as @ref reducer<@ref op_xor>, except that
304 * reducer_opxor is a proxy for the contained view, so that accumulator
305 * variable update operations can be applied directly to the reducer. For
306 * example, a value is xored with a `reducer<%op_xor>` with `*r ^= a`, but a
307 * value can be xored with a `%reducer_opxor` with `r ^= a`.
309 * @deprecated Users are strongly encouraged to use `reducer<monoid>`
310 * reducers rather than the old wrappers like reducer_opand.
311 * The `reducer<monoid>` reducers show the reducer/monoid/view
312 * architecture more clearly, are more consistent in their
313 * implementation, and present a simpler model for new
314 * user-implemented reducers.
316 * @note Implicit conversions are provided between `%reducer_opxor`
317 * and `reducer<%op_xor>`. This allows incremental code
318 * conversion: old code that used `%reducer_opxor` can pass a
319 * `%reducer_opxor` to a converted function that now expects a
320 * pointer or reference to a `reducer<%op_xor>`, and vice
323 * @tparam Type The value type of the reducer.
329 * @ingroup ReducersXor
331 template <typename Type
>
332 class reducer_opxor
: public reducer
< op_xor
<Type
, true> >
334 typedef reducer
< op_xor
<Type
, true> > base
;
338 /// The view type for the reducer.
339 typedef typename
base::view_type view_type
;
341 /// The view’s rhs proxy type.
342 typedef typename
view_type::rhs_proxy rhs_proxy
;
344 /// The view type for the reducer.
345 typedef view_type View
;
347 /// The monoid type for the reducer.
348 typedef typename
base::monoid_type Monoid
;
350 /** @name Constructors
354 /** Default (identity) constructor.
356 * Constructs the wrapper with the default initial value of `Type()`.
360 /** Value constructor.
362 * Constructs the wrapper with a specified initial value.
364 explicit reducer_opxor(const Type
& initial_value
) : base(initial_value
) {}
368 /** @name Forwarded functions
369 * @details Functions that update the contained accumulator variable are
370 * simply forwarded to the contained @ref op_and_view. */
373 /// @copydoc op_xor_view::operator^=(const Type&)
374 reducer_opxor
& operator^=(const Type
& x
)
376 view() ^= x
; return *this;
379 // The legacy definition of reducer_opxor::operator^() has different
380 // behavior and a different return type than this definition. The legacy
381 // version is defined as a member function, so this new version is defined
382 // as a free function to give it a different signature, so that they won’t
383 // end up sharing a single object file entry.
385 /// @copydoc op_xor_view::operator^(const Type&) const
386 friend rhs_proxy
operator^(const reducer_opxor
& r
, const Type
& x
)
391 /// @copydoc op_and_view::operator=(const rhs_proxy&)
392 reducer_opxor
& operator=(const rhs_proxy
& temp
)
394 view() = temp
; return *this;
398 /** @name Dereference
399 * @details Dereferencing a wrapper is a no-op. It simply returns the
400 * wrapper. Combined with the rule that the wrapper forwards view
401 * operations to its contained view, this means that view operations can
402 * be written the same way on reducers and wrappers, which is convenient
403 * for incrementally converting old code using wrappers to use reducers
406 * reducer< op_and<int> > r;
407 * *r &= a; // *r returns the view
408 * // operator &= is a view member function
410 * reducer_opand<int> w;
411 * *w &= a; // *w returns the wrapper
412 * // operator &= is a wrapper member function that
413 * // calls the corresponding view function
416 reducer_opxor
& operator*() { return *this; }
417 reducer_opxor
const& operator*() const { return *this; }
419 reducer_opxor
* operator->() { return this; }
420 reducer_opxor
const* operator->() const { return this; }
424 * @details In Cilk library 0.9, reducers were always cache-aligned. In
425 * library 1.0, reducer cache alignment is optional. By default, reducers
426 * are unaligned (i.e., just naturally aligned), but legacy wrappers
427 * inherit from cache-aligned reducers for binary compatibility.
429 * This means that a wrapper will automatically be upcast to its aligned
430 * reducer base class. The following conversion operators provide
431 * pseudo-upcasts to the corresponding unaligned reducer class.
434 operator reducer
< op_xor
<Type
, false> >& ()
436 return *reinterpret_cast< reducer
< op_xor
<Type
, false> >* >(this);
438 operator const reducer
< op_xor
<Type
, false> >& () const
440 return *reinterpret_cast< const reducer
< op_xor
<Type
, false> >* >(this);
447 /** Metafunction specialization for reducer conversion.
449 * This specialization of the @ref legacy_reducer_downcast template class
450 * defined in reducer.h causes the `reducer< op_xor<Type> >` class to have an
451 * `operator reducer_opxor<Type>& ()` conversion operator that statically
452 * downcasts the `reducer<op_xor>` to the corresponding `reducer_opxor` type.
453 * (The reverse conversion, from `reducer_opxor` to `reducer<op_xor>`, is just
454 * an upcast, which is provided for free by the language.)
456 * @ingroup ReducersXor
458 template <typename Type
, bool Align
>
459 struct legacy_reducer_downcast
<reducer
<op_xor
<Type
, Align
> > >
461 typedef reducer_opxor
<Type
> type
;
467 #endif /* __cplusplus */
470 /** @ingroup ReducersXor
474 /** @name C language reducer macros
476 * These macros are used to declare and work with op_xor reducers in C code.
478 * @see @ref page_reducers_in_c
482 __CILKRTS_BEGIN_EXTERN_C
484 /** Opxor reducer type name.
486 * This macro expands into the identifier which is the name of the op_xor
487 * reducer type for a specified numeric type.
489 * @param tn The @ref reducers_c_type_names "numeric type name" specifying
490 * the type of the reducer.
492 * @see @ref reducers_c_predefined
495 #define CILK_C_REDUCER_OPXOR_TYPE(tn) \
496 __CILKRTS_MKIDENT(cilk_c_reducer_opxor_,tn)
498 /** Declare an op_xor reducer object.
500 * This macro expands into a declaration of an op_xor reducer object for a
501 * specified numeric type. For example:
503 * CILK_C_REDUCER_OPXOR(my_reducer, ulong, 0);
505 * @param obj The variable name to be used for the declared reducer object.
506 * @param tn The @ref reducers_c_type_names "numeric type name" specifying
507 * the type of the reducer.
508 * @param v The initial value for the reducer. (A value which can be
509 * assigned to the numeric type represented by @a tn.)
511 * @see @ref reducers_c_predefined
514 #define CILK_C_REDUCER_OPXOR(obj,tn,v) \
515 CILK_C_REDUCER_OPXOR_TYPE(tn) obj = \
516 CILK_C_INIT_REDUCER(_Typeof(obj.value), \
517 __CILKRTS_MKIDENT(cilk_c_reducer_opxor_reduce_,tn), \
518 __CILKRTS_MKIDENT(cilk_c_reducer_opxor_identity_,tn), \
519 __cilkrts_hyperobject_noop_destroy, v)
523 /** Declare the op_xor reducer functions for a numeric type.
525 * This macro expands into external function declarations for functions which
526 * implement the reducer functionality for the op_xor reducer type for a
527 * specified numeric type.
529 * @param t The value type of the reducer.
530 * @param tn The value “type name” identifier, used to construct the reducer
531 * type name, function names, etc.
533 #define CILK_C_REDUCER_OPXOR_DECLARATION(t,tn) \
534 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_OPXOR_TYPE(tn); \
535 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_opxor,tn,l,r); \
536 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_opxor,tn);
538 /** Define the op_xor reducer functions for a numeric type.
540 * This macro expands into function definitions for functions which implement
541 * the reducer functionality for the op_xor reducer type for a specified
544 * @param t The value type of the reducer.
545 * @param tn The value “type name” identifier, used to construct the reducer
546 * type name, function names, etc.
548 #define CILK_C_REDUCER_OPXOR_DEFINITION(t,tn) \
549 typedef CILK_C_DECLARE_REDUCER(t) CILK_C_REDUCER_OPXOR_TYPE(tn); \
550 __CILKRTS_DECLARE_REDUCER_REDUCE(cilk_c_reducer_opxor,tn,l,r) \
551 { *(t*)l ^= *(t*)r; } \
552 __CILKRTS_DECLARE_REDUCER_IDENTITY(cilk_c_reducer_opxor,tn) \
556 /** @def CILK_C_REDUCER_OPXOR_INSTANCE
557 * @brief Declare or define implementation functions for a reducer type.
559 * In the runtime source file c_reducers.c, the macro `CILK_C_DEFINE_REDUCERS`
560 * will be defined, and this macro will generate reducer implementation
561 * functions. Everywhere else, `CILK_C_DEFINE_REDUCERS` will be undefined, and
562 * this macro will expand into external declarations for the functions.
564 #ifdef CILK_C_DEFINE_REDUCERS
565 # define CILK_C_REDUCER_OPXOR_INSTANCE(t,tn) \
566 CILK_C_REDUCER_OPXOR_DEFINITION(t,tn)
568 # define CILK_C_REDUCER_OPXOR_INSTANCE(t,tn) \
569 CILK_C_REDUCER_OPXOR_DECLARATION(t,tn)
573 /* Declare or define an instance of the reducer type and its functions for each
576 CILK_C_REDUCER_OPXOR_INSTANCE(char, char)
577 CILK_C_REDUCER_OPXOR_INSTANCE(unsigned char, uchar
)
578 CILK_C_REDUCER_OPXOR_INSTANCE(signed char, schar
)
579 CILK_C_REDUCER_OPXOR_INSTANCE(wchar_t, wchar_t)
580 CILK_C_REDUCER_OPXOR_INSTANCE(short, short)
581 CILK_C_REDUCER_OPXOR_INSTANCE(unsigned short, ushort
)
582 CILK_C_REDUCER_OPXOR_INSTANCE(int, int)
583 CILK_C_REDUCER_OPXOR_INSTANCE(unsigned int, uint
)
584 CILK_C_REDUCER_OPXOR_INSTANCE(unsigned int, unsigned) /* alternate name */
585 CILK_C_REDUCER_OPXOR_INSTANCE(long, long)
586 CILK_C_REDUCER_OPXOR_INSTANCE(unsigned long, ulong
)
587 CILK_C_REDUCER_OPXOR_INSTANCE(long long, longlong
)
588 CILK_C_REDUCER_OPXOR_INSTANCE(unsigned long long, ulonglong
)
592 __CILKRTS_END_EXTERN_C
598 #endif /* REDUCER_OPXOR_H_INCLUDED */