text: /*  metaprogramming.h                  -*- C++ -*-
   *
   *  Copyright (C) 2012-2015, Intel Corporation
   *  All rights reserved.
   *  
   *  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.
   *  
   *  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.
   *  
   *  *********************************************************************
   *  
   *  PLEASE NOTE: This file is a downstream copy of a file mainitained in
   *  a repository at cilkplus.org. Changes made to this file that are not
   *  submitted through the contribution process detailed at
   *  http://www.cilkplus.org/submit-cilk-contribution will be lost the next
   *  time that a new version is released. Changes only submitted to the
   *  GNU compiler collection or posted to the git repository at
   *  https://bitbucket.org/intelcilkplusruntime/itnel-cilk-runtime.git are
   *  not tracked.
   *  
   *  We welcome your contributions to this open source project. Thank you
   *  for your assistance in helping us improve Cilk Plus.
   */
  
  /** @file metaprogramming.h
   *
   *  @brief Defines metaprogramming utility classes used in the Intel(R) Cilk(TM) Plus 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 than 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>
  class aligned_storage;
  
  /// @cond
  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]; };
  /// @endcond
  
  /** 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); }
      /// Return a typed reference to the buffer.
            Type& object()       { return *reinterpret_cast<Type*>(this); }
  };
  
  
  /** Get the functor class corresponding to a binary function type.
   *
   *  The `binary_functor` template class can be instantiated with a binary
   *  functor class or with a real binary function, and will yield an equivalent
   *  binary functor 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 cilk::cilk_lib_1_1::min_max_internal::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* /* unused */) {}
  
      /// 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 cilk::internal::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(__VXWORKS__)
      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
  