arrayManipulation.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2021, Lawrence Livermore National Security, LLC and LvArray contributors.
 * All rights reserved.
 * See the LICENSE file for details.
 * SPDX-License-Identifier: (BSD-3-Clause)
 */

#pragma once

// Source includes
#include "limits.hpp"
#include "Macros.hpp"
#include "typeManipulation.hpp"

// System includes
#include <cstring>

#ifdef LVARRAY_BOUNDS_CHECK

#define ARRAYMANIPULATION_CHECK_BOUNDS( index ) \
  LVARRAY_ERROR_IF( !isPositive( index ) || index >= size, \
                    "Array Bounds Check Failed: index=" << index << " size()=" << size )

#define ARRAYMANIPULATION_CHECK_INSERT_BOUNDS( index ) \
  LVARRAY_ERROR_IF( !isPositive( index ) || index > size, \
                    "Array Bounds Insert Check Failed: index=" << index << " size()=" << size )

#else // LVARRAY_BOUNDS_CHECK

#define ARRAYMANIPULATION_CHECK_BOUNDS( index )

#define ARRAYMANIPULATION_CHECK_INSERT_BOUNDS( index )

#endif // LVARRAY_BOUNDS_CHECK

namespace LvArray
{

namespace arrayManipulation
{

template< typename INDEX_TYPE >
LVARRAY_HOST_DEVICE inline constexpr
typename std::enable_if< std::is_signed< INDEX_TYPE >::value, bool >::type
isPositive( INDEX_TYPE const i )
{ return i >= 0; }

template< typename INDEX_TYPE >
LVARRAY_HOST_DEVICE inline constexpr
typename std::enable_if< !std::is_signed< INDEX_TYPE >::value, bool >::type
isPositive( INDEX_TYPE )
{ return true; }

DISABLE_HD_WARNING
template< typename ITER >
inline constexpr LVARRAY_HOST_DEVICE
typename std::iterator_traits< ITER >::difference_type
iterDistance( ITER first, ITER const last, std::input_iterator_tag )
{
  typename std::iterator_traits< ITER >::difference_type n = 0;
  while( first != last )
  {
    ++first;
    ++n;
  }

  return n;
}

DISABLE_HD_WARNING
template< typename RandomAccessIterator >
inline constexpr LVARRAY_HOST_DEVICE
typename std::iterator_traits< RandomAccessIterator >::difference_type
iterDistance( RandomAccessIterator first, RandomAccessIterator last, std::random_access_iterator_tag )
{ return last - first; }

DISABLE_HD_WARNING
template< typename ITER >
inline constexpr LVARRAY_HOST_DEVICE
typename std::iterator_traits< ITER >::difference_type
iterDistance( ITER const first, ITER const last )
{ return iterDistance( first, last, typename std::iterator_traits< ITER >::iterator_category() ); }

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void destroy( T * const LVARRAY_RESTRICT ptr,
              std::ptrdiff_t const size )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );

  if( !std::is_trivially_destructible< T >::value )
  {
    for( std::ptrdiff_t i = 0; i < size; ++i )
    {
      ptr[ i ].~T();
    }
  }
}

DISABLE_HD_WARNING
template< typename ITER, typename T >
LVARRAY_HOST_DEVICE inline
void uninitializedCopy( ITER first,
                        ITER const & last,
                        T * LVARRAY_RESTRICT dst )
{
  LVARRAY_ASSERT( dst != nullptr || first == last );

  while( first != last )
  {
    new ( dst ) T( *first );
    ++dst;
    ++first;
  }
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void uninitializedMove( T * const LVARRAY_RESTRICT dst,
                        std::ptrdiff_t const size,
                        T * const LVARRAY_RESTRICT src )
{
  LVARRAY_ASSERT( dst != nullptr || size == 0 );
  LVARRAY_ASSERT( isPositive( size ) );
  LVARRAY_ASSERT( src != nullptr || size == 0 );

  for( std::ptrdiff_t i = 0; i < size; ++i )
  {
    new (dst + i) T( std::move( src[ i ] ) );
  }
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void uninitializedShiftDown( T * const LVARRAY_RESTRICT ptr,
                             std::ptrdiff_t const size,
                             std::ptrdiff_t const amount )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( isPositive( size ) );
  LVARRAY_ASSERT( isPositive( amount ) );

  if( amount == 0 )
    return;

  for( std::ptrdiff_t j = 0; j < size; ++j )
  {
    new ( ptr + j - amount ) T( std::move( ptr[ j ] ) );
    ptr[ j ].~T();
  }
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void uninitializedShiftUp( T * const LVARRAY_RESTRICT ptr,
                           std::ptrdiff_t const size,
                           std::ptrdiff_t const amount )
{
  LVARRAY_ASSERT( ptr != nullptr || size == 0 );
  LVARRAY_ASSERT( isPositive( size ) );
  LVARRAY_ASSERT( isPositive( amount ) );

  if( amount == 0 )
    return;

  for( std::ptrdiff_t j = size - 1; j >= 0; --j )
  {
    new ( ptr + amount + j ) T( std::move( ptr[ j ] ) );
    ptr[ j ].~T();
  }
}

DISABLE_HD_WARNING
template< typename T, typename ... ARGS >
LVARRAY_HOST_DEVICE inline
void resize( T * const LVARRAY_RESTRICT ptr,
             std::ptrdiff_t const size,
             std::ptrdiff_t const newSize,
             ARGS && ... args )
{
  LVARRAY_ASSERT( ptr != nullptr || (size == 0 && newSize == 0) );
  LVARRAY_ASSERT( isPositive( size ) );
  LVARRAY_ASSERT( isPositive( newSize ) );

  // Delete things between newSize and size.
  destroy( ptr + newSize, size - newSize );

  // Initialize things between size and newSize.
  if( sizeof ... ( ARGS ) == 0 && std::is_trivially_default_constructible< T >::value )
  {
    if( newSize - size > 0 )
    {
      std::size_t const sizeDiff = integerConversion< std::size_t >( newSize - size );
      std::memset( reinterpret_cast< void * >( ptr + size ), 0, ( sizeDiff ) * sizeof( T ) );
    }
  }
  else
  {
    // Use std::size_t so that when GCC optimizes this it doesn't produce sign warnings.
    for( std::size_t i = size; i < std::size_t( newSize ); ++i )
    {
      new ( ptr + i ) T( std::forward< ARGS >( args )... );
    }
  }
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void shiftUp( T * const LVARRAY_RESTRICT ptr,
              std::ptrdiff_t const size,
              std::ptrdiff_t const index,
              std::ptrdiff_t const n )
{
  LVARRAY_ASSERT( ptr != nullptr || (size == 0 && n == 0) );
  LVARRAY_ASSERT( isPositive( size ) );
  LVARRAY_ASSERT( isPositive( n ) );
  ARRAYMANIPULATION_CHECK_INSERT_BOUNDS( index );

  if( n == 0 )
    return;

  // Move the existing values up by n.
  for( std::ptrdiff_t i = size; i > index; --i )
  {
    std::ptrdiff_t const curIndex = i - 1;
    new ( ptr + curIndex + n ) T( std::move( ptr[ curIndex ] ) );
  }

  // Delete the values moved out of.
  std::ptrdiff_t const bounds = (index + n < size) ? index + n : size;
  destroy( ptr + index, bounds - index );
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void shiftDown( T * const LVARRAY_RESTRICT ptr,
                std::ptrdiff_t const size,
                std::ptrdiff_t const index,
                std::ptrdiff_t const n )
{
  ARRAYMANIPULATION_CHECK_INSERT_BOUNDS( index );
  LVARRAY_ASSERT( ptr != nullptr || (size == 0 && n == 0) );
  LVARRAY_ASSERT( isPositive( size ) );
  LVARRAY_ASSERT( isPositive( n ) );
  LVARRAY_ASSERT( index >= n );

  if( n == 0 )
    return;

  // Move the existing down by n.
  for( std::ptrdiff_t i = index; i < size; ++i )
  {
    ptr[i - n] = std::move( ptr[i] );
  }
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void erase( T * const LVARRAY_RESTRICT ptr,
            std::ptrdiff_t const size,
            std::ptrdiff_t const index,
            std::ptrdiff_t const n=1 )
{
  LVARRAY_ASSERT( isPositive( n ) );
  if( n == 0 )
    return;

  ARRAYMANIPULATION_CHECK_BOUNDS( index );
  ARRAYMANIPULATION_CHECK_BOUNDS( index + n - 1 );

  shiftDown( ptr, size, std::ptrdiff_t( index + n ), n );

  // Delete the values that were moved out of at the end of the array.
  destroy( ptr + size - n, n );
}

DISABLE_HD_WARNING
template< typename T, typename ... ARGS >
LVARRAY_HOST_DEVICE inline
void emplaceBack( T * const LVARRAY_RESTRICT ptr,
                  std::ptrdiff_t const size,
                  ARGS && ... args )
{
  LVARRAY_ASSERT( ptr != nullptr );
  LVARRAY_ASSERT( isPositive( size ) );
  new ( ptr + size ) T( std::forward< ARGS >( args ) ... );
}

DISABLE_HD_WARNING
template< typename T, typename ITER >
LVARRAY_HOST_DEVICE inline
std::ptrdiff_t append( T * const LVARRAY_RESTRICT ptr,
                       std::ptrdiff_t const size,
                       ITER first,
                       ITER const last )
{
  LVARRAY_ASSERT( ptr != nullptr || (size == 0 && first == last) );
  LVARRAY_ASSERT( isPositive( size ) );

  std::ptrdiff_t i = 0;
  while( first != last )
  {
    new( ptr + size + i ) T( *first );
    ++first;
    ++i;
  }

  return i;
}

DISABLE_HD_WARNING
template< typename T, typename ... ARGS >
LVARRAY_HOST_DEVICE inline
void emplace( T * const LVARRAY_RESTRICT ptr,
              std::ptrdiff_t const size,
              std::ptrdiff_t const index,
              ARGS && ... args )
{
  LVARRAY_ASSERT( ptr != nullptr );
  LVARRAY_ASSERT( isPositive( size ) );
  ARRAYMANIPULATION_CHECK_INSERT_BOUNDS( index );

  // Create space for the new value.
  shiftUp( ptr, size, index, std::ptrdiff_t( 1 ) );
  new ( ptr + index ) T( std::forward< ARGS >( args ) ... );
}

DISABLE_HD_WARNING
template< typename T, typename ITERATOR >
LVARRAY_HOST_DEVICE inline
void insert( T * const LVARRAY_RESTRICT ptr,
             std::ptrdiff_t const size,
             std::ptrdiff_t const index,
             ITERATOR first,
             std::ptrdiff_t const n )
{
  LVARRAY_ASSERT( ptr != nullptr );
  LVARRAY_ASSERT( isPositive( size ) );
  ARRAYMANIPULATION_CHECK_INSERT_BOUNDS( index );

  shiftUp( ptr, size, index, n );

  for( std::ptrdiff_t i = 0; i < n; ++i )
  {
    new ( ptr + index + i ) T( *first );
    ++first;
  }
}

DISABLE_HD_WARNING
template< typename T >
LVARRAY_HOST_DEVICE inline
void popBack( T * const LVARRAY_RESTRICT ptr,
              std::ptrdiff_t const size )
{
  LVARRAY_ASSERT( ptr != nullptr );
  LVARRAY_ASSERT( size > 0 );
  ptr[ size - 1 ].~T();
}

} // namespace arrayManipulation
} // namespace LvArray