PndFTSArray.h

Go to the documentation of this file.

/****************************************************************************
 * This file is property of and copyright by the ALICE HLT Project          *
 * ALICE Experiment at CERN, All rights reserved.                           *
 *                                                                          *
 * Copyright (C) 2009 Matthias Kretz <kretz@kde.org>                        *
 *               for The ALICE HLT Project.                                 *
 *                                                                          *
 * Permission to use, copy, modify and distribute this software and its     *
 * documentation strictly for non-commercial purposes is hereby granted     *
 * without fee, provided that the above copyright notice appears in all     *
 * copies and that both the copyright notice and this permission notice     *
 * appear in the supporting documentation. The authors make no claims       *
 * about the suitability of this software for any purpose. It is            *
 * provided "as is" without express or implied warranty.                    *
 ***************************************************************************/

#ifndef PNDFTSARRAY_H
#define PNDFTSARRAY_H

#ifndef assert
#include <assert.h>
#endif

#if (defined(__MMX__) || defined(__SSE__))

#if defined(__GNUC__)

#if __GNUC__ > 3
#define USE_MM_MALLOC
#endif // if __GNUC__ > 3

#else // if defined(__GNUC__)  // not gcc, assume it can use _mm_malloc since it supports MMX/SSE

#define USE_MM_MALLOC

#endif // if defined(__GNUC__)
#endif // if (defined(__MMX__) || defined(__SSE__))

#ifdef USE_MM_MALLOC
#include <mm_malloc.h>
#else
#include <cstdlib>
#endif
#include <cstring>

enum {
  PndFTSFullyCacheLineAligned = -1
};

namespace PndFTSArrayInternal
{
  template<bool> class STATIC_ASSERT_FAILURE;
  template<> class STATIC_ASSERT_FAILURE<true> {};
}

#define PNDFTSARRAY_STATIC_ASSERT_CONCAT_HELPER(a, b) a##b
#define PNDFTSARRAY_STATIC_ASSERT_CONCAT(a, b) PNDFTSARRAY_STATIC_ASSERT_CONCAT_HELPER(a, b)
#define PNDFTSARRAY_STATIC_ASSERT_NC(cond, msg) \
  typedef PndFTSArrayInternal::STATIC_ASSERT_FAILURE<cond> PNDFTSARRAY_STATIC_ASSERT_CONCAT(_STATIC_ASSERTION_FAILED_##msg, __LINE__); \
  PNDFTSARRAY_STATIC_ASSERT_CONCAT(_STATIC_ASSERTION_FAILED_##msg, __LINE__) Error_##msg
#define PNDFTSARRAY_STATIC_ASSERT(cond, msg) PNDFTSARRAY_STATIC_ASSERT_NC(cond, msg); (void) Error_##msg

template<typename T, int Dim> class PndFTSArray;

namespace PndFTSInternal
{
  template<unsigned int Size> struct Padding { char fPadding[Size]; };
  template<> struct Padding<0> {};
  template<typename T> struct CacheLineSizeHelperData { T fData; };
  template<typename T> struct CacheLineSizeHelperEnums {
      enum {
        CacheLineSize = 64,
        MaskedSize = sizeof( T ) & ( CacheLineSize - 1 ),
        RequiredSize = MaskedSize == 0 ? sizeof( T ) : sizeof( T ) + CacheLineSize - MaskedSize,
        PaddingSize = RequiredSize - sizeof( T )
      };
  };
  template<typename T> class CacheLineSizeHelper : private CacheLineSizeHelperData<T>, private Padding<CacheLineSizeHelperEnums<T>::PaddingSize>
  {
    public:
      operator T &() { return CacheLineSizeHelperData<T>::fData; }
      operator const T &() const { return CacheLineSizeHelperData<T>::fData; }
      //const T &operator=( const T &rhs ) { CacheLineSizeHelperData<T>::fData = rhs; }

    private:
  };
  template<typename T, int alignment> struct TypeForAlignmentHelper { typedef T Type; };
  template<typename T> struct TypeForAlignmentHelper<T, PndFTSFullyCacheLineAligned> { typedef CacheLineSizeHelper<T> Type; };

  // XXX
  // The ArrayBoundsCheck and Allocator classes implement a virtual destructor only in order to
  // silence the -Weffc++ warning. It really is not required for these classes to have a virtual
  // dtor since polymorphism is not used (PndFTSResizableArray and PndFTSFixedArray are allocated on
  // the stack only). The virtual dtor only adds an unnecessary vtable to the code.
#ifndef ENABLE_ARRAY_BOUNDS_CHECKING

  class ArrayBoundsCheck
  {
    protected:
      virtual inline ~ArrayBoundsCheck() {}
      inline bool IsInBounds( int ) const { return true; }
      inline void SetBounds( int, int ) {}
      inline void MoveBounds( int ) {}
      inline void ReinterpretCast( const ArrayBoundsCheck &, int, int ) {}
  };
#define BOUNDS_CHECK(x, y)
#else

  class ArrayBoundsCheck
  {
    protected:
      virtual inline ~ArrayBoundsCheck() {}
      inline bool IsInBounds( int x ) const;
      inline void SetBounds( int start, int end ) { fStart = start; fEnd = end; }
      inline void MoveBounds( int d ) { fStart += d; fEnd += d; }

      inline void ReinterpretCast( const ArrayBoundsCheck &other, int sizeofOld, int sizeofNew ) {
        fStart = other.fStart * sizeofNew / sizeofOld;
        fEnd = other.fEnd * sizeofNew / sizeofOld;
      }

    private:
      int fStart;
      int fEnd;
  };
#define BOUNDS_CHECK(x, y) if (PndFTSInternal::ArrayBoundsCheck::IsInBounds(x)) {} else return y
#endif
  template<typename T, int alignment> class Allocator
  {
    public:
#ifdef USE_MM_MALLOC
      static inline T *Alloc( int s ) { T *p = reinterpret_cast<T *>( _mm_malloc( s * sizeof( T ), alignment ) ); return new( p ) T[s]; }
      static inline void Free( T *const p, int size ) {
        for ( int i = 0; i < size; ++i ) {
          p[i].~T();
        }
        _mm_free( p );
      }
#else
      static inline T *Alloc( int s ) { T *p; posix_memalign( &p, alignment, s * sizeof( T ) ); return new( p ) T[s]; }
      static inline void Free( T *const p, int size ) {
        for ( int i = 0; i < size; ++i ) {
          p[i].~T();
        }
        std::free( p );
      }
#endif
  };
  template<typename T> class Allocator<T, PndFTSFullyCacheLineAligned>
  {
    public:
      typedef CacheLineSizeHelper<T> T2;
#ifdef USE_MM_MALLOC
      static inline T2 *Alloc( int s ) { T2 *p = reinterpret_cast<T2 *>( _mm_malloc( s * sizeof( T2 ), 128 ) ); return new( p ) T2[s]; }
      static inline void Free( T2 *const p, int size ) {
        for ( int i = 0; i < size; ++i ) {
          p[i].~T2();
        }
        _mm_free( p );
      }
#else
      static inline T2 *Alloc( int s ) { T2 *p; posix_memalign( &p, 128, s * sizeof( T2 ) ); return new( p ) T2[s]; }
      static inline void Free( T2 *const p, int size ) {
        for ( int i = 0; i < size; ++i ) {
          p[i].~T2();
        }
        std::free( p );
      }
#endif
  };
  template<typename T> class Allocator<T, 0>
  {
    public:
#ifdef USE_MM_MALLOC
      static inline T *Alloc( int s ) { T *p = reinterpret_cast<T *>( _mm_malloc( s * sizeof( T ), 128 ) ); return new( p ) T[s]; }
      static inline void Free( T *const p, int size ) {
        for ( int i = 0; i < size; ++i ) {
          p[i].~T();
        }
        _mm_free( p );
      }
#else
      static inline T *Alloc( int s ) { T *p; posix_memalign( &p, 128, s * sizeof( T ) ); return new( p ) T[s]; }
      static inline void Free( T *const p, int size ) {
        for ( int i = 0; i < size; ++i ) {
          p[i].~T();
        }
        std::free( p );
      }
#endif

//     public:
//       static inline T *Alloc( int s ) { return new T[s]; }
//       static inline void Free( const T *const p, int ) { delete[] p; }
  };

  template<typename T> struct ReturnTypeHelper { typedef T Type; };
  template<typename T> struct ReturnTypeHelper<CacheLineSizeHelper<T> > { typedef T Type; };
  template<typename T, int Dim> class ArrayBase;

  template<typename T>
  class ArrayBase<T, 1> : public ArrayBoundsCheck
  {
      friend class ArrayBase<T, 2>;
    public:
      ArrayBase() : fData( 0 ) {} // XXX really shouldn't be done. But -Weffc++ wants it so
      ArrayBase( const ArrayBase &rhs ) : ArrayBoundsCheck( rhs ), fData( rhs.fData ), fSize( rhs.fSize ) {} // XXX
      ArrayBase &operator=( const ArrayBase &rhs ) { ArrayBoundsCheck::operator=( rhs ); fData = rhs.fData; fSize = rhs.fSize; return *this; } // XXX
      typedef typename ReturnTypeHelper<T>::Type R;
      inline R &operator[]( int x ) { BOUNDS_CHECK( x, fData[0] ); return fData[x]; }
      inline const R &operator[]( int x ) const { BOUNDS_CHECK( x, fData[0] ); return fData[x]; }

    protected:
      T *fData;
      int fSize;
      inline void SetSize( int x, int, int ) { fSize = x; }
  };

  template<typename T>
  class ArrayBase<T, 2> : public ArrayBoundsCheck
  {
      friend class ArrayBase<T, 3>;
    public:
      ArrayBase() : fData( 0 ), fSize( 0 ), fStride( 0 ) {} // XXX really shouldn't be done. But -Weffc++ wants it so
      ArrayBase( const ArrayBase &rhs ) : ArrayBoundsCheck( rhs ), fData( rhs.fData ), fSize( rhs.fSize ), fStride( rhs.fStride ) {} // XXX
      ArrayBase &operator=( const ArrayBase &rhs ) { ArrayBoundsCheck::operator=( rhs ); fData = rhs.fData; fSize = rhs.fSize; fStride = rhs.fStride; return *this; } // XXX
      typedef typename ReturnTypeHelper<T>::Type R;
      inline R &operator()( int x, int y ) { BOUNDS_CHECK( x * fStride + y, fData[0] ); return fData[x * fStride + y]; }
      inline const R &operator()( int x, int y ) const { BOUNDS_CHECK( x * fStride + y, fData[0] ); return fData[x * fStride + y]; }
      inline PndFTSArray<T, 1> operator[]( int x );
      inline const PndFTSArray<T, 1> operator[]( int x ) const;

    protected:
      T *fData;
      int fSize;
      int fStride;
      inline void SetSize( int x, int y, int ) { fStride = y; fSize = x * y; }
  };

  template<typename T>
  class ArrayBase<T, 3> : public ArrayBoundsCheck
  {
    public:
      ArrayBase() : fData( 0 ), fSize( 0 ), fStrideX( 0 ), fStrideY( 0 ) {} // XXX really shouldn't be done. But -Weffc++ wants it so
      ArrayBase( const ArrayBase &rhs ) : ArrayBoundsCheck( rhs ), fData( rhs.fData ), fSize( rhs.fSize ), fStrideX( rhs.fStrideX ), fStrideY( rhs.fStrideY ) {} // XXX
      ArrayBase &operator=( const ArrayBase &rhs ) { ArrayBoundsCheck::operator=( rhs ); fData = rhs.fData; fSize = rhs.fSize; fStrideX = rhs.fStrideX; fStrideY = rhs.fStrideY; return *this; } // XXX
      typedef typename ReturnTypeHelper<T>::Type R;
      inline R &operator()( int x, int y, int z );
      inline const R &operator()( int x, int y, int z ) const;
      inline PndFTSArray<T, 2> operator[]( int x );
      inline const PndFTSArray<T, 2> operator[]( int x ) const;

    protected:
      T *fData;
      int fSize;
      int fStrideX;
      int fStrideY;
      inline void SetSize( int x, int y, int z ) { fStrideX = y * z; fStrideY = z; fSize = fStrideX * x; }
  };

  template<typename T, unsigned int Size, int _alignment> class AlignedData
  {
    public:
      T *ConstructAlignedData() {
        const int offset = reinterpret_cast<unsigned long>( &fUnalignedArray[0] ) & ( Alignment - 1 );
        void *mem = &fUnalignedArray[0] + ( Alignment - offset );
        return new( mem ) T[Size];
      }
      ~AlignedData() {
        const int offset = reinterpret_cast<unsigned long>( &fUnalignedArray[0] ) & ( Alignment - 1 );
        T *mem = reinterpret_cast<T *>( &fUnalignedArray[0] + ( Alignment - offset ) );
        for ( unsigned int i = 0; i < Size; ++i ) {
          mem[i].~T();
        }
      }
    private:
      enum {
        Alignment = _alignment == PndFTSFullyCacheLineAligned ? 128 : _alignment,
        PaddedSize = Size * sizeof( T ) + Alignment
      };
      PNDFTSARRAY_STATIC_ASSERT_NC( ( Alignment & ( Alignment - 1 ) ) == 0, alignment_needs_to_be_a_multiple_of_2 );

      char fUnalignedArray[PaddedSize];
  };
  template<typename T, unsigned int Size> class AlignedData<T, Size, 0>
  {
    public:
      T *ConstructAlignedData() { return &fArray[0]; }
    private:
      T fArray[Size];
  };
} // namespace PndFTSInternal

template < typename T, int Dim = 1 >
class PndFTSArray : public PndFTSInternal::ArrayBase<T, Dim>
{
  public:
    typedef PndFTSInternal::ArrayBase<T, Dim> Parent;

    inline int Size() const { return Parent::fSize; }

    inline operator bool() const { return Parent::fData != 0; }
    inline bool IsValid() const { return Parent::fData != 0; }

    inline T &operator*() { BOUNDS_CHECK( 0, Parent::fData[0] ); return *Parent::fData; }
    inline const T &operator*() const { BOUNDS_CHECK( 0, Parent::fData[0] ); return *Parent::fData; }

    inline T *Data() { return Parent::fData; }
    inline const T *Data() const { return Parent::fData; }

    inline PndFTSArray operator+( int x ) const;
    inline PndFTSArray operator-( int x ) const;

    template<typename Other> inline PndFTSArray<Other, Dim> ReinterpretCast() const {
      PndFTSArray<Other, Dim> r;
      r.fData = reinterpret_cast<Other *>( Parent::fData );
      r.ReinterpretCast( *this, sizeof( T ), sizeof( Other ) );
    }
};

template < typename T, int Dim = 1, int alignment = 0 >
class PndFTSResizableArray : public PndFTSArray<typename PndFTSInternal::TypeForAlignmentHelper<T, alignment>::Type, Dim>
{
  public:
    typedef typename PndFTSInternal::TypeForAlignmentHelper<T, alignment>::Type T2;
    typedef PndFTSInternal::ArrayBase<T2, Dim> Parent;
    inline PndFTSResizableArray();
    inline PndFTSResizableArray( int x );
    inline PndFTSResizableArray( int x, int y );
    inline PndFTSResizableArray( int x, int y, int z );

    inline ~PndFTSResizableArray() { PndFTSInternal::Allocator<T, alignment>::Free( Parent::fData, Parent::fSize ); }

    inline void Resize( int x );
    inline void Resize( int x, int y );
    inline void Resize( int x, int y, int z );

  private:
    // disable allocation on the heap
    void *operator new( size_t );

    // disable copy
    PndFTSResizableArray( const PndFTSResizableArray & );
    PndFTSResizableArray &operator=( const PndFTSResizableArray & );
};

template<unsigned int x, unsigned int y = 0, unsigned int z = 0> class PndFTSArraySize
{
  public:
    enum {
      Size = y == 0 ? x : ( z == 0 ? x * y : x * y * z ),
      Dim = y == 0 ? 1 : ( z == 0 ? 2 : 3 ),
      X = x, Y = y, Z = z
    };
};

template<typename T, typename Size, int alignment = 0>
class PndFTSFixedArray : public PndFTSArray<typename PndFTSInternal::TypeForAlignmentHelper<T, alignment>::Type, Size::Dim>
{
  public:
    typedef typename PndFTSInternal::TypeForAlignmentHelper<T, alignment>::Type T2;
    typedef PndFTSInternal::ArrayBase<T2, Size::Dim> Parent;
    inline PndFTSFixedArray() {
      fData = fFixedArray.ConstructAlignedData();
      Parent::SetBounds( 0, Size::Size - 1 );
      SetSize( Size::X, Size::Y, Size::Z );
    }
    PndFTSFixedArray( const PndFTSFixedArray &rhs ) {
      fData = fFixedArray.ConstructAlignedData();
      Parent::SetBounds( 0, Size::Size - 1 );
      SetSize( Size::X, Size::Y, Size::Z );
      std::memcpy( fData, rhs.fData, Size::Size * sizeof( T ) );
    }

  private:
    PndFTSInternal::AlignedData<typename PndFTSInternal::TypeForAlignmentHelper<T, alignment>::Type, Size::Size, alignment> fFixedArray;

    // disable allocation on the heap
    void *operator new( size_t );

    using Parent::fData;

    // disable copy
    PndFTSFixedArray &operator=( const PndFTSFixedArray & );
};








namespace PndFTSInternal
{
#ifdef ENABLE_ARRAY_BOUNDS_CHECKING
  inline bool ArrayBoundsCheck::IsInBounds( int x ) const
  {
    assert( x >= fStart );
    assert( x <= fEnd );
    return ( x >= fStart && x <= fEnd );
  }
#endif

  template<typename T>
  inline PndFTSArray<T, 1> ArrayBase<T, 2>::operator[]( int x )
  {
    x *= fStride;
    //typedef PndFTSArray<T, 1> AT1;
    //BOUNDS_CHECK( x, AT1() );
    PndFTSArray<T, 1> a;
    a.fData = &fData[x];
    a.ArrayBoundsCheck::operator=( *this );
    a.MoveBounds( -x );
    return a;
  }

  template<typename T>
  inline const PndFTSArray<T, 1> ArrayBase<T, 2>::operator[]( int x ) const
  {
    x *= fStride;
    //typedef PndFTSArray<T, 1> AT1;
    //BOUNDS_CHECK( x, AT1() );
    PndFTSArray<T, 1> a;
    a.fData = &fData[x];
    a.ArrayBoundsCheck::operator=( *this );
    a.MoveBounds( -x );
    return a;
  }

  template<typename T>
  inline typename PndFTSInternal::ArrayBase<T, 3>::R &ArrayBase<T, 3>::operator()( int x, int y, int z )
  {
    BOUNDS_CHECK( x * fStrideX + y + fStrideY + z, fData[0] );
    return fData[x * fStrideX + y + fStrideY + z];
  }
  template<typename T>
  inline const typename PndFTSInternal::ArrayBase<T, 3>::R &ArrayBase<T, 3>::operator()( int x, int y, int z ) const
  {
    BOUNDS_CHECK( x * fStrideX + y + fStrideY + z, fData[0] );
    return fData[x * fStrideX + y + fStrideY + z];
  }
  template<typename T>
  inline PndFTSArray<T, 2> ArrayBase<T, 3>::operator[]( int x )
  {
    x *= fStrideX;
    //typedef PndFTSArray<T, 2> AT2;
    //BOUNDS_CHECK( x, AT2() );
    PndFTSArray<T, 2> a;
    a.fData = &fData[x];
    a.fStride = fStrideY;
    a.ArrayBoundsCheck::operator=( *this );
    a.MoveBounds( -x );
    return a;
  }
  template<typename T>
  inline const PndFTSArray<T, 2> ArrayBase<T, 3>::operator[]( int x ) const
  {
    x *= fStrideX;
    //typedef PndFTSArray<T, 2> AT2;
    //BOUNDS_CHECK( x, AT2() );
    PndFTSArray<T, 2> a;
    a.fData = &fData[x];
    a.fStride = fStrideY;
    a.ArrayBoundsCheck::operator=( *this );
    a.MoveBounds( -x );
    return a;
  }
} // namespace PndFTSInternal


template<typename T, int Dim>
inline PndFTSArray<T, Dim> PndFTSArray<T, Dim>::operator+( int x ) const
{
  PndFTSArray<T, Dim> r( *this );
  r.fData += x;
  r.MoveBounds( -x );
  return r;
}
template<typename T, int Dim>
inline PndFTSArray<T, Dim> PndFTSArray<T, Dim>::operator-( int x ) const
{
  PndFTSArray<T, Dim> r( *this );
  r.fData -= x;
  r.MoveBounds( x );
  return r;
}

template<typename T, int Dim, int alignment>
inline PndFTSResizableArray<T, Dim, alignment>::PndFTSResizableArray()
{
  Parent::fData = 0;
  Parent::SetSize( 0, 0, 0 );
  Parent::SetBounds( 0, -1 );
}
template<typename T, int Dim, int alignment>
inline PndFTSResizableArray<T, Dim, alignment>::PndFTSResizableArray( int x )
{
  PNDFTSARRAY_STATIC_ASSERT( Dim == 1, PndFTSResizableArray1_used_with_incorrect_dimension );
  Parent::fData = PndFTSInternal::Allocator<T, alignment>::Alloc( x );
  Parent::SetSize( x, 0, 0 );
  Parent::SetBounds( 0, x - 1 );
}
template<typename T, int Dim, int alignment>
inline PndFTSResizableArray<T, Dim, alignment>::PndFTSResizableArray( int x, int y )
{
  PNDFTSARRAY_STATIC_ASSERT( Dim == 2, PndFTSResizableArray2_used_with_incorrect_dimension );
  Parent::fData = PndFTSInternal::Allocator<T, alignment>::Alloc( x * y );
  Parent::SetSize( x, y, 0 );
  Parent::SetBounds( 0, x * y - 1 );
}
template<typename T, int Dim, int alignment>
inline PndFTSResizableArray<T, Dim, alignment>::PndFTSResizableArray( int x, int y, int z )
{
  PNDFTSARRAY_STATIC_ASSERT( Dim == 3, PndFTSResizableArray3_used_with_incorrect_dimension );
  Parent::fData = PndFTSInternal::Allocator<T, alignment>::Alloc( x * y * z );
  Parent::SetSize( x, y, z );
  Parent::SetBounds( 0, x * y * z - 1 );
}
// #include <iostream>
template<typename T, int Dim, int alignment>
inline void PndFTSResizableArray<T, Dim, alignment>::Resize( int x )
{
  PNDFTSARRAY_STATIC_ASSERT( Dim == 1, PndFTSResizableArray1_resize_used_with_incorrect_dimension );
  PndFTSInternal::Allocator<T, alignment>::Free( Parent::fData, Parent::fSize );
  Parent::fData = ( x == 0 ) ? 0 : PndFTSInternal::Allocator<T, alignment>::Alloc( x );
  Parent::SetSize( x, 0, 0 );
  Parent::SetBounds( 0, x - 1 );
}
template<typename T, int Dim, int alignment>
inline void PndFTSResizableArray<T, Dim, alignment>::Resize( int x, int y )
{
  PNDFTSARRAY_STATIC_ASSERT( Dim == 2, PndFTSResizableArray2_resize_used_with_incorrect_dimension );
  PndFTSInternal::Allocator<T, alignment>::Free( Parent::fData, Parent::fSize );
  Parent::fData = ( x == 0 ) ? 0 : PndFTSInternal::Allocator<T, alignment>::Alloc( x * y );
  Parent::SetSize( x, y, 0 );
  Parent::SetBounds( 0, x * y - 1 );
}
template<typename T, int Dim, int alignment>
inline void PndFTSResizableArray<T, Dim, alignment>::Resize( int x, int y, int z )
{
  PNDFTSARRAY_STATIC_ASSERT( Dim == 3, PndFTSResizableArray3_resize_used_with_incorrect_dimension );
  PndFTSInternal::Allocator<T, alignment>::Free( Parent::fData, Parent::fSize );
  Parent::fData = ( x == 0 ) ? 0 : PndFTSInternal::Allocator<T, alignment>::Alloc( x * y * z );
  Parent::SetSize( x, y, z );
  Parent::SetBounds( 0, x * y * z - 1 );
}

#undef BOUNDS_CHECK

#endif // PNDFTSARRAY_H