JezK
Edit File: metaprogramming.h
/* 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