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> {
};
} // namespace PndFTSArrayInternal

#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