diff options
Diffstat (limited to 'gcc-4.9/libcilkrts/include/cilk/metaprogramming.h')
| -rw-r--r-- | gcc-4.9/libcilkrts/include/cilk/metaprogramming.h | 606 |
1 files changed, 606 insertions, 0 deletions
diff --git a/gcc-4.9/libcilkrts/include/cilk/metaprogramming.h b/gcc-4.9/libcilkrts/include/cilk/metaprogramming.h new file mode 100644 index 000000000..5f6f29df8 --- /dev/null +++ b/gcc-4.9/libcilkrts/include/cilk/metaprogramming.h @@ -0,0 +1,606 @@ +/* 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) || 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 |