| /* metaprogramming.h -*- C++ -*- |
| * |
| * @copyright |
| * Copyright (C) 2012-2013, Intel Corporation |
| * All rights reserved. |
| * |
| * @copyright |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * * Neither the name of Intel Corporation nor the names of its |
| * contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * @copyright |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, |
| * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS |
| * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED |
| * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY |
| * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| * POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /** @file metaprogramming.h |
| * |
| * @brief Defines metaprogramming utility classes used in the Cilk library. |
| * |
| * @ingroup common |
| */ |
| |
| #ifndef METAPROGRAMMING_H_INCLUDED |
| #define METAPROGRAMMING_H_INCLUDED |
| |
| #ifdef __cplusplus |
| |
| #include <functional> |
| #include <new> |
| #include <cstdlib> |
| #ifdef _WIN32 |
| #include <malloc.h> |
| #endif |
| #include <algorithm> |
| |
| namespace cilk { |
| |
| namespace internal { |
| |
| /** Test if a class is empty. |
| * |
| * If @a Class is an empty (and therefore necessarily stateless) class, then |
| * the “empty base-class optimization” guarantees that |
| * `sizeof(check_for_empty_class<Class>) == sizeof(char)`. Conversely, if |
| * `sizeof(check_for_empty_class<Class>) > sizeof(char)`, then @a Class is not |
| * empty, and we must discriminate distinct instances of @a Class. |
| * |
| * Typical usage: |
| * |
| * // General definition of A<B> for non-empty B: |
| * template <typename B, bool BIsEmpty = class_is_empty<B>::value> > |
| * class A { ... }; |
| * |
| * // Specialized definition of A<B> for empty B: |
| * template <typename B> |
| * class A<B, true> { ... }; |
| * |
| * @tparam Class The class to be tested for emptiness. |
| * |
| * @result The `value` member will be `true` if @a Class is empty, |
| * `false` otherwise. |
| * |
| * @ingroup common |
| */ |
| template <class Class> |
| class class_is_empty { |
| class check_for_empty_class : public Class |
| { |
| char m_data; |
| public: |
| // Declared but not defined |
| check_for_empty_class(); |
| check_for_empty_class(const check_for_empty_class&); |
| check_for_empty_class& operator=(const check_for_empty_class&); |
| ~check_for_empty_class(); |
| }; |
| public: |
| |
| /** Constant is true if and only if @a Class is empty. |
| */ |
| static const bool value = (sizeof(check_for_empty_class) == sizeof(char)); |
| }; |
| |
| |
| /** Get the alignment of a type. |
| * |
| * For example: |
| * |
| * align_of<double>::value == 8 |
| * |
| * @tparam Tp The type whose alignment is to be computed. |
| * |
| * @result The `value` member of an instantiation of this class template |
| * will hold the integral alignment requirement of @a Tp. |
| * |
| * @pre @a Tp shall be a complete type. |
| * |
| * @ingroup common |
| */ |
| template <typename Tp> |
| struct align_of |
| { |
| private: |
| struct imp { |
| char m_padding; |
| Tp m_val; |
| |
| // The following declarations exist to suppress compiler-generated |
| // definitions, in case @a Tp does not have a public default |
| // constructor, copy constructor, or destructor. |
| imp(const imp&); // Declared but not defined |
| ~imp(); // Declared but not defined |
| }; |
| |
| public: |
| /// The integral alignment requirement of @a Tp. |
| static const std::size_t value = (sizeof(imp) - sizeof(Tp)); |
| }; |
| |
| |
| /** A class containing raw bytes with a specified alignment and size. |
| * |
| * An object of type `aligned_storage<S, A>` will have alignment `A` and |
| * size at least `S`. Its contents will be uninitialized bytes. |
| * |
| * @tparam Size The required minimum size of the resulting class. |
| * @tparam Alignment The required alignment of the resulting class. |
| * |
| * @pre @a Alignment shall be a power of 2 no greater then 64. |
| * |
| * @note This is implemented using the `CILK_ALIGNAS` macro, which uses |
| * the non-standard, implementation-specific features |
| * `__declspec(align(N))` on Windows, and |
| * `__attribute__((__aligned__(N)))` on Unix. The `gcc` implementation |
| * of `__attribute__((__aligned__(N)))` requires a numeric literal `N` |
| * (_not_ an arbitrary compile-time constant expression). Therefore, |
| * this class is implemented using specialization on the required |
| * alignment. |
| * |
| * @note The template class is specialized only for the supported |
| * alignments. An attempt to instantiate it for an unsupported |
| * alignment will result in a compilation error. |
| */ |
| template <std::size_t Size, std::size_t Alignment> |
| struct aligned_storage; |
| |
| template<std::size_t Size> class aligned_storage<Size, 1> |
| { CILK_ALIGNAS( 1) char m_bytes[Size]; }; |
| template<std::size_t Size> class aligned_storage<Size, 2> |
| { CILK_ALIGNAS( 2) char m_bytes[Size]; }; |
| template<std::size_t Size> class aligned_storage<Size, 4> |
| { CILK_ALIGNAS( 4) char m_bytes[Size]; }; |
| template<std::size_t Size> class aligned_storage<Size, 8> |
| { CILK_ALIGNAS( 8) char m_bytes[Size]; }; |
| template<std::size_t Size> class aligned_storage<Size, 16> |
| { CILK_ALIGNAS(16) char m_bytes[Size]; }; |
| template<std::size_t Size> class aligned_storage<Size, 32> |
| { CILK_ALIGNAS(32) char m_bytes[Size]; }; |
| template<std::size_t Size> class aligned_storage<Size, 64> |
| { CILK_ALIGNAS(64) char m_bytes[Size]; }; |
| |
| |
| /** A buffer of uninitialized bytes with the same size and alignment as a |
| * specified type. |
| * |
| * The class `storage_for_object<Type>` will have the same size and alignment |
| * properties as `Type`, but it will contain only raw (uninitialized) bytes. |
| * This allows the definition of a data member which can contain a `Type` |
| * object which is initialized explicitly under program control, rather |
| * than implicitly as part of the initialization of the containing class. |
| * For example: |
| * |
| * class C { |
| * storage_for_object<MemberClass> _member; |
| * public: |
| * C() ... // Does NOT initialize _member |
| * void initialize(args) |
| * { new (_member.pointer()) MemberClass(args); } |
| * const MemberClass& member() const { return _member.object(); } |
| * MemberClass& member() { return _member.object(); } |
| * |
| * @tparam Type The type whose size and alignment are to be reflected |
| * by this class. |
| */ |
| template <typename Type> |
| class storage_for_object : |
| aligned_storage< sizeof(Type), align_of<Type>::value > |
| { |
| public: |
| /// Return a typed reference to the buffer. |
| const Type& object() const { return *reinterpret_cast<Type*>(this); } |
| Type& object() { return *reinterpret_cast<Type*>(this); } |
| }; |
| |
| |
| /** Get the functor class corresponding to a binary function type. |
| * |
| * The `binary_functor` template class class can be instantiated with a binary |
| * functor class or with a real binary function, and will yield an equivalent |
| * binary functor class class in either case. |
| * |
| * @tparam F A binary functor class, a binary function type, or a pointer to |
| * binary function type. |
| * |
| * @result `binary_functor<F>::%type` will be the same as @a F if @a F is |
| * a class. It will be a `std::pointer_to_binary_function` wrapper |
| * if @a F is a binary function or binary function pointer type. |
| * (It will _not_ necessarily be an `Adaptable Binary Function` |
| * class, since @a F might be a non-adaptable binary functor |
| * class.) |
| * |
| * @ingroup common |
| */ |
| template <typename F> |
| struct binary_functor { |
| /// The binary functor class equivalent to @a F. |
| typedef F type; |
| }; |
| |
| /// @copydoc binary_functor |
| /// Specialization for binary function. |
| template <typename R, typename A, typename B> |
| struct binary_functor<R(A,B)> { |
| /// The binary functor class equivalent to @a F. |
| typedef std::pointer_to_binary_function<A, B, R> type; |
| }; |
| |
| /// @copydoc binary_functor |
| /// Specialization for pointer to binary function. |
| template <typename R, typename A, typename B> |
| struct binary_functor<R(*)(A,B)> { |
| /// The binary functor class equivalent to @a F. |
| typedef std::pointer_to_binary_function<A, B, R> type; |
| }; |
| |
| |
| /** Indirect binary function class with specified types. |
| * |
| * `typed_indirect_binary_function<F>` is an `Adaptable Binary Function` class |
| * based on an existing binary functor class or binary function type @a F. If |
| * @a F is a stateless class, then this class will be empty, and its |
| * `operator()` will invoke @a F’s `operator()`. Otherwise, an object of this |
| * class will hold a pointer to an object of type @a F, and will refer its |
| * `operator()` calls to the pointed-to @a F object. |
| * |
| * That is, suppose that we have the declarations: |
| * |
| * F *p; |
| * typed_indirect_binary_function<F, int, int, bool> ibf(p); |
| * |
| * Then: |
| * |
| * - `ibf(x, y) == (*p)(x, y)`. |
| * - `ibf(x, y)` will not do a pointer dereference if `F` is an empty class. |
| * |
| * @note Just to repeat: if `F` is an empty class, then |
| * `typed_indirect_binary_function\<F\>' is also an empty class. |
| * This is critical for its use in the @ref min_max::view_base |
| * "min/max reducer view classes", where it allows the view to |
| * call a comparison functor in the monoid without actually |
| * having to allocate a pointer in the view class when the |
| * comparison class is empty. |
| * |
| * @note If you have an `Adaptable Binary Function` class or a binary |
| * function type, then you can use the |
| * @ref indirect_binary_function class, which derives the |
| * argument and result types parameter type instead of requiring |
| * you to specify them as template arguments. |
| * |
| * @tparam F A binary functor class, a binary function type, or a pointer to |
| * binary function type. |
| * @param A1 The first argument type. |
| * @param A2 The second argument type. |
| * @param R The result type. |
| * |
| * @see min_max::comparator_base |
| * @see indirect_binary_function |
| * |
| * @ingroup common |
| */ |
| template < typename F |
| , typename A1 |
| , typename A2 |
| , typename R |
| , typename Functor = typename binary_functor<F>::type |
| , bool FunctorIsEmpty = class_is_empty<Functor>::value |
| > |
| class typed_indirect_binary_function : std::binary_function<A1, A2, R> |
| { |
| const F* f; |
| public: |
| /// Constructor captures a pointer to the wrapped function. |
| typed_indirect_binary_function(const F* f) : f(f) {} |
| |
| /// Return the comparator pointer, or `NULL` if the comparator is stateless. |
| const F* pointer() const { return f; } |
| |
| /// Apply the pointed-to functor to the arguments. |
| R operator()(const A1& a1, const A2& a2) const { return (*f)(a1, a2); } |
| }; |
| |
| |
| /// @copydoc typed_indirect_binary_function |
| /// Specialization for an empty functor class. (This is only possible if @a F |
| /// itself is an empty class. If @a F is a function or pointer-to-function |
| /// type, then the functor will contain a pointer.) |
| template <typename F, typename A1, typename A2, typename R, typename Functor> |
| class typed_indirect_binary_function<F, A1, A2, R, Functor, true> : |
| std::binary_function<A1, A2, R> |
| { |
| public: |
| /// Return `NULL` for the comparator pointer of a stateless comparator. |
| const F* pointer() const { return 0; } |
| |
| /// Constructor discards the pointer to a stateless functor class. |
| typed_indirect_binary_function(const F* f) {} |
| |
| /// Create an instance of the stateless functor class and apply it to the arguments. |
| R operator()(const A1& a1, const A2& a2) const { return F()(a1, a2); } |
| }; |
| |
| |
| /** Indirect binary function class with inferred types. |
| * |
| * This is identical to @ref typed_indirect_binary_function, except that it |
| * derives the binary function argument and result types from the parameter |
| * type @a F instead of taking them as additional template parameters. If @a F |
| * is a class type, then it must be an `Adaptable Binary Function`. |
| * |
| * @see typed_indirect_binary_function |
| * |
| * @ingroup common |
| */ |
| template <typename F, typename Functor = typename binary_functor<F>::type> |
| class indirect_binary_function : |
| typed_indirect_binary_function< F |
| , typename Functor::first_argument_type |
| , typename Functor::second_argument_type |
| , typename Functor::result_type |
| > |
| { |
| typedef typed_indirect_binary_function< F |
| , typename Functor::first_argument_type |
| , typename Functor::second_argument_type |
| , typename Functor::result_type |
| > |
| base; |
| public: |
| indirect_binary_function(const F* f) : base(f) {} ///< Constructor |
| }; |
| |
| |
| /** Choose a type based on a boolean constant. |
| * |
| * This metafunction is identical to C++11’s condition metafunction. |
| * It needs to be here until we can reasonably assume that users will be |
| * compiling with C++11. |
| * |
| * @tparam Cond A boolean constant. |
| * @tparam IfTrue A type. |
| * @tparam IfFalse A type. |
| * @result The `type` member will be a typedef of @a IfTrue if @a Cond |
| * is true, and a typedef of @a IfFalse if @a Cond is false. |
| * |
| * @ingroup common |
| */ |
| template <bool Cond, typename IfTrue, typename IfFalse> |
| struct condition |
| { |
| typedef IfTrue type; ///< The type selected by the condition. |
| }; |
| |
| /// @copydoc condition |
| /// Specialization for @a Cond == `false`. |
| template <typename IfTrue, typename IfFalse> |
| struct condition<false, IfTrue, IfFalse> |
| { |
| typedef IfFalse type; ///< The type selected by the condition. |
| }; |
| |
| |
| /** @def __CILKRTS_STATIC_ASSERT |
| * |
| * @brief Compile-time assertion. |
| * |
| * Causes a compilation error if a compile-time constant expression is false. |
| * |
| * @par Usage example. |
| * This assertion is used in reducer_min_max.h to avoid defining |
| * legacy reducer classes that would not be binary-compatible with the |
| * same classes compiled with earlier versions of the reducer library. |
| * |
| * __CILKRTS_STATIC_ASSERT( |
| * internal::class_is_empty< internal::binary_functor<Compare> >::value, |
| * "cilk::reducer_max<Value, Compare> only works with an empty Compare class"); |
| * |
| * @note In a C++11 compiler, this is just the language predefined |
| * `static_assert` macro. |
| * |
| * @note In a non-C++11 compiler, the @a Msg string is not directly included |
| * in the compiler error message, but it may appear if the compiler |
| * prints the source line that the error occurred on. |
| * |
| * @param Cond The expression to test. |
| * @param Msg A string explaining the failure. |
| * |
| * @ingroup common |
| */ |
| #if defined(__INTEL_CXX11_MODE__) || defined(__GXX_EXPERIMENTAL_CXX0X__) |
| # define __CILKRTS_STATIC_ASSERT(Cond, Msg) static_assert(Cond, Msg) |
| #else |
| # define __CILKRTS_STATIC_ASSERT(Cond, Msg) \ |
| typedef int __CILKRTS_STATIC_ASSERT_DUMMY_TYPE \ |
| [::cilk::internal::static_assert_failure<(Cond)>::Success] |
| |
| /// @cond internal |
| template <bool> struct static_assert_failure { }; |
| template <> struct static_assert_failure<true> { enum { Success = 1 }; }; |
| |
| # define __CILKRTS_STATIC_ASSERT_DUMMY_TYPE \ |
| __CILKRTS_STATIC_ASSERT_DUMMY_TYPE1(__cilkrts_static_assert_, __LINE__) |
| # define __CILKRTS_STATIC_ASSERT_DUMMY_TYPE1(a, b) \ |
| __CILKRTS_STATIC_ASSERT_DUMMY_TYPE2(a, b) |
| # define __CILKRTS_STATIC_ASSERT_DUMMY_TYPE2(a, b) a ## b |
| /// @endcond |
| |
| #endif |
| |
| /// @cond internal |
| |
| /** @name Aligned heap management. |
| */ |
| //@{ |
| |
| /** Implementation-specific aligned memory allocation function. |
| * |
| * @param size The minimum number of bytes to allocate. |
| * @param alignment The required alignment (must be a power of 2). |
| * @return The address of a block of memory of at least @a size |
| * bytes. The address will be a multiple of @a alignment. |
| * `NULL` if the allocation fails. |
| * |
| * @see deallocate_aligned() |
| */ |
| inline void* allocate_aligned(std::size_t size, std::size_t alignment) |
| { |
| #ifdef _WIN32 |
| return _aligned_malloc(size, alignment); |
| #else |
| #if defined(__ANDROID__) |
| return memalign(std::max(alignment, sizeof(void*)), size); |
| #else |
| void* ptr; |
| return (posix_memalign(&ptr, std::max(alignment, sizeof(void*)), size) == 0) ? ptr : 0; |
| #endif |
| #endif |
| } |
| |
| /** Implementation-specific aligned memory deallocation function. |
| * |
| * @param ptr A pointer which was returned by a call to alloc_aligned(). |
| */ |
| inline void deallocate_aligned(void* ptr) |
| { |
| #ifdef _WIN32 |
| _aligned_free(ptr); |
| #else |
| std::free(ptr); |
| #endif |
| } |
| |
| /** Class to allocate and guard an aligned pointer. |
| * |
| * A new_aligned_pointer object allocates aligned heap-allocated memory when |
| * it is created, and automatically deallocates it when it is destroyed |
| * unless its `ok()` function is called. |
| * |
| * @tparam T The type of the object to allocate on the heap. The allocated |
| * will have the size and alignment of an object of type T. |
| */ |
| template <typename T> |
| class new_aligned_pointer { |
| void* m_ptr; |
| public: |
| /// Constructor allocates the pointer. |
| new_aligned_pointer() : |
| m_ptr(allocate_aligned(sizeof(T), internal::align_of<T>::value)) {} |
| /// Destructor deallocates the pointer. |
| ~new_aligned_pointer() { if (m_ptr) deallocate_aligned(m_ptr); } |
| /// Get the pointer. |
| operator void*() { return m_ptr; } |
| /// Return the pointer and release the guard. |
| T* ok() { |
| T* ptr = static_cast<T*>(m_ptr); |
| m_ptr = 0; |
| return ptr; |
| } |
| }; |
| |
| //@} |
| |
| /// @endcond |
| |
| } // namespace internal |
| |
| //@{ |
| |
| /** Allocate an aligned data structure on the heap. |
| * |
| * `cilk::aligned_new<T>([args])` is equivalent to `new T([args])`, except |
| * that it guarantees that the returned pointer will be at least as aligned |
| * as the alignment requirements of type `T`. |
| * |
| * @ingroup common |
| */ |
| template <typename T> |
| T* aligned_new() |
| { |
| internal::new_aligned_pointer<T> ptr; |
| new (ptr) T(); |
| return ptr.ok(); |
| } |
| |
| template <typename T, typename T1> |
| T* aligned_new(const T1& x1) |
| { |
| internal::new_aligned_pointer<T> ptr; |
| new (ptr) T(x1); |
| return ptr.ok(); |
| } |
| |
| template <typename T, typename T1, typename T2> |
| T* aligned_new(const T1& x1, const T2& x2) |
| { |
| internal::new_aligned_pointer<T> ptr; |
| new (ptr) T(x1, x2); |
| return ptr.ok(); |
| } |
| |
| template <typename T, typename T1, typename T2, typename T3> |
| T* aligned_new(const T1& x1, const T2& x2, const T3& x3) |
| { |
| internal::new_aligned_pointer<T> ptr; |
| new (ptr) T(x1, x2, x3); |
| return ptr.ok(); |
| } |
| |
| template <typename T, typename T1, typename T2, typename T3, typename T4> |
| T* aligned_new(const T1& x1, const T2& x2, const T3& x3, const T4& x4) |
| { |
| internal::new_aligned_pointer<T> ptr; |
| new (ptr) T(x1, x2, x3, x4); |
| return ptr.ok(); |
| } |
| |
| template <typename T, typename T1, typename T2, typename T3, typename T4, typename T5> |
| T* aligned_new(const T1& x1, const T2& x2, const T3& x3, const T4& x4, const T5& x5) |
| { |
| internal::new_aligned_pointer<T> ptr; |
| new (ptr) T(x1, x2, x3, x4, x5); |
| return ptr.ok(); |
| } |
| |
| //@} |
| |
| |
| /** Deallocate an aligned data structure on the heap. |
| * |
| * `cilk::aligned_delete(ptr)` is equivalent to `delete ptr`, except that it |
| * operates on a pointer that was allocated by aligned_new(). |
| * |
| * @ingroup common |
| */ |
| template <typename T> |
| void aligned_delete(const T* ptr) |
| { |
| ptr->~T(); |
| internal::deallocate_aligned((void*)ptr); |
| } |
| |
| } // namespace cilk |
| |
| #endif // __cplusplus |
| |
| #endif // METAPROGRAMMING_H_INCLUDED |
