vector.hpp

Go to the documentation of this file.

/*
Copyright (c) 2014-2016, Scott Zuyderduyn
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.
2. 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.

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 OWNER 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.

The views and conclusions contained in the software and documentation are those
of the authors and should not be interpreted as representing official policies,
either expressed or implied, of the FreeBSD Project.
*/

//----------------------------------------------------------------------------
// vector.hpp
//
// An STL-like structure that resides in video memory.
//
// Author: Scott D. Zuyderduyn, Ph.D. (scott.zuyderduyn@utoronto.ca)
//----------------------------------------------------------------------------

#pragma once
#ifndef ECUDA_VECTOR_HPP
#define ECUDA_VECTOR_HPP

#include <cstddef>
#include <iterator>
#include <limits>
#include <vector>

#ifdef ECUDA_CPP11_AVAILABLE
#include <initializer_list>
#include <memory>
#include <utility>
#endif

#include "global.hpp"
#include "algorithm.hpp"
#include "allocators.hpp"
#include "memory.hpp"
#include "type_traits.hpp"

#include "model/device_contiguous_sequence.hpp"

namespace ecuda {

namespace impl {

template<typename T,class Alloc> class vector_kernel_argument; // forward declaration

} // namespace impl

template< typename T, class Alloc=device_allocator<T>, class P=shared_ptr<T> >
class vector : private model::device_contiguous_sequence< T, P > {

private:
    typedef model::device_contiguous_sequence< T, P > base_type;

public:
    typedef typename base_type::value_type      value_type;      
    typedef Alloc                               allocator_type;  
    typedef typename base_type::size_type       size_type;       
    typedef typename base_type::difference_type difference_type; 
    #ifdef ECUDA_CPP11_AVAILABLE
    typedef typename base_type::reference                        reference;       
    typedef typename base_type::const_reference                  const_reference; 
    typedef typename std::allocator_traits<Alloc>::pointer       pointer;         
    typedef typename std::allocator_traits<Alloc>::const_pointer const_pointer;   
    #else
    typedef typename Alloc::reference       reference;       
    typedef typename Alloc::const_reference const_reference; 
    typedef typename Alloc::pointer         pointer;         
    typedef typename Alloc::const_pointer   const_pointer;   
    #endif

    typedef typename base_type::iterator               iterator;               
    typedef typename base_type::const_iterator         const_iterator;         
    typedef typename base_type::reverse_iterator       reverse_iterator;       
    typedef typename base_type::const_reverse_iterator const_reverse_iterator; 

    typedef       impl::vector_kernel_argument<T,Alloc> kernel_argument;       
    typedef const impl::vector_kernel_argument<T,Alloc> const_kernel_argument; 

private:
    size_type n; 
    allocator_type allocator;

    template<typename U,class Alloc2,class Q> friend class vector;

protected:
    template<class Q>
    __HOST__ __DEVICE__ vector( const vector<T,Alloc,Q>& src, ecuda::true_type ) : base_type(unmanaged_cast(src.get_pointer())), n(src.n), allocator(src.allocator) {}

    template<class Q>
    __HOST__ __DEVICE__ vector& shallow_assign( const vector<T,Alloc,Q>& other )
    {
        base_type::get_pointer() = unmanaged_cast(other.get_pointer());
        n = other.n;
        allocator = other.allocator;
        return *this;
    }


private:
    __HOST__ void growMemory( size_type minimum );

    __HOST__ void init( size_type len, const value_type& value, ecuda::true_type )
    {
        growMemory( len );
        n = len;
        if( len ) ecuda::fill( begin(), end(), value );
    }

    template<class Iterator>
    __HOST__ inline void init( Iterator first, Iterator last, ecuda::false_type )
    {
        const size_type len = ::ecuda::distance(first,last);
        growMemory( len );
        ecuda::copy( first, last, begin() );
        n = len;
    }

public:
    __HOST__ explicit vector( const allocator_type& allocator = allocator_type() ) : base_type(), n(0), allocator(allocator) {}

    __HOST__ explicit vector( size_type n, const value_type& value, const allocator_type& allocator = allocator_type() ) : base_type( shared_ptr<T>( allocator.allocate(n) ), n ), n(n), allocator(allocator)
    {
        init( n, value, ecuda::true_type() );
    }

    __HOST__ explicit vector( size_type n ) : base_type( shared_ptr<T>( Alloc().allocate(n) ) ), n(n)
    {
        init( n, value_type(), ecuda::true_type() );
    }

    template<class Iterator>
    __HOST__ vector( Iterator first, Iterator last, const allocator_type& allocator = allocator_type() ) : base_type(), n(0), allocator(allocator)
    {
        typedef typename ecuda::is_integral<Iterator>::type _Integral;
        init( first, last, _Integral() );
    }

    __HOST__ vector( const vector& src ) :
        base_type(),
        n(src.n),
        allocator(src.get_allocator())
        //std::allocator_traits<allocator_type>::select_on_container_copy_construction(src.get_allocator())
    {
        if( size() != src.size() ) resize( src.size() );
        ecuda::copy( src.begin(), src.end(), begin() );
    }

    __HOST__ vector& operator=( const vector& src )
    {
        if( size() != src.size() ) resize( src.size() );
        allocator = src.allocator;
        ecuda::copy( src.begin(), src.end(), begin() );
        return *this;
    }

    #ifdef ECUDA_CPP11_AVAILABLE
    __HOST__ __DEVICE__ vector( vector&& src ) : base_type(src), n(std::move(src.n)), allocator(std::move(src.allocator)) {}

    __HOST__ __DEVICE__ vector( vector&& src, const allocator_type& allocator ) : base_type(src), n(std::move(src.n)), allocator(allocator) {}

    __HOST__ vector( std::initializer_list<value_type> il, const allocator_type& allocator = allocator_type() ) : base_type(shared_ptr<T>(allocator.allocate(il.size()))), n(il.size()), allocator(allocator)
    {
        ecuda::copy( il.begin(), il.end(), begin() );
    }

    __HOST__ vector& operator=( vector&& src )
    {
        base_type::operator=(std::move(src));
        n = std::move(src.n);
        return *this;
    }
    #endif

    __HOST__ __DEVICE__ inline iterator begin() __NOEXCEPT__ { return base_type::begin(); }

    __HOST__ __DEVICE__ inline iterator end() __NOEXCEPT__ { return base_type::begin()+size(); }

    __HOST__ __DEVICE__ inline const_iterator begin() const __NOEXCEPT__ { return base_type::begin(); }

    __HOST__ __DEVICE__ inline const_iterator end() const __NOEXCEPT__ { return base_type::begin()+size(); }

    __HOST__ __DEVICE__ inline reverse_iterator rbegin() __NOEXCEPT__ { return reverse_iterator(end()); }

    __HOST__ __DEVICE__ inline reverse_iterator rend() __NOEXCEPT__ { return reverse_iterator(begin()); }

    __HOST__ __DEVICE__ inline const_reverse_iterator rbegin() const __NOEXCEPT__ { return const_reverse_iterator(end()); }

    __HOST__ __DEVICE__ inline const_reverse_iterator rend() const __NOEXCEPT__ { return const_reverse_iterator(begin()); }

    #ifdef ECUDA_CPP11_AVAILABLE
    __HOST__ __DEVICE__ inline const_iterator         cbegin() const __NOEXCEPT__ { return base_type::cbegin();         }
    __HOST__ __DEVICE__ inline const_iterator         cend() const   __NOEXCEPT__ { return base_type::cbegin()+size();  }
    __HOST__ __DEVICE__ inline const_reverse_iterator crbegin()      __NOEXCEPT__ { return base_type::crbegin();        }
    __HOST__ __DEVICE__ inline const_reverse_iterator crend()        __NOEXCEPT__ { return base_type::crbegin()+size(); }
    #endif

    __HOST__ __DEVICE__ inline size_type size() const __NOEXCEPT__ { return n; }

    __HOST__ __DEVICE__ __CONSTEXPR__ inline size_type max_size() const __NOEXCEPT__ { return std::numeric_limits<size_type>::max(); }

    __HOST__ void resize( size_type newSize, const value_type& value = value_type() )
    {
        if( size() == newSize ) return;
        if( size() > newSize ) { n = newSize; return; }
        growMemory( newSize ); // make sure enough device memory is allocated
        std::vector< value_type, host_allocator<value_type> > v( newSize-n, value );
        ecuda::copy( v.begin(), v.end(), begin() );
        n = newSize;
    }

    __HOST__ __DEVICE__ inline size_type capacity() const __NOEXCEPT__ { return base_type::size(); }

    __HOST__ __DEVICE__ inline bool empty() const __NOEXCEPT__ { return !n; }

    __HOST__ inline void reserve( size_type newCapacity ) { growMemory(newCapacity); }

    __DEVICE__ inline reference at( size_type index )
    {
        if( !(index < size()) ) {
            #ifndef __CUDACC__
            throw std::out_of_range( EXCEPTION_MSG("ecuda::vector::at() index parameter is out of range") );
            #else
            // this strategy is taken from:
            // http://stackoverflow.com/questions/12521721/crashing-a-kernel-gracefully
            ecuda::threadfence();
            //__threadfence();
            asm("trap;");
            #endif
        }
        return base_type::operator[](index);
    }

    __DEVICE__ inline const_reference at( size_type index ) const
    {
        if( !(index < size()) ) {
            #ifndef __CUDACC__
            throw std::out_of_range( EXCEPTION_MSG("ecuda::vector::at() index parameter is out of range") );
            #else
            // this strategy is taken from:
            // http://stackoverflow.com/questions/12521721/crashing-a-kernel-gracefully
            ecuda::threadfence();
            //__threadfence();
            asm("trap;");
            #endif
        }
        return base_type::operator[](index);
    }

    __DEVICE__ inline reference operator[]( const size_type index ) { return base_type::operator[](index); }

    __DEVICE__ inline const_reference operator[]( const size_type index ) const { return base_type::operator[](index); }

    __DEVICE__ inline reference operator()( const size_type index ) { return base_type::operator[](index); }

    __DEVICE__ inline const_reference operator()( const size_type index ) const { return base_type::operator[](index); }

    __DEVICE__ inline reference front() { return operator[](0); }

    __DEVICE__ inline reference back() { return operator[]( size()-1 ); }

    __DEVICE__ inline const_reference front() const { return operator[](0); }

    __DEVICE__ inline const_reference back() const { return operator[]( size()-1 ); }

    __HOST__ __DEVICE__ inline pointer data() __NOEXCEPT__ { return base_type::get_pointer(); }

    __HOST__ __DEVICE__ inline const_pointer data() const __NOEXCEPT__ { return base_type::get_pointer(); }

    __HOST__ void assign( size_type newSize, const value_type& value = value_type() )
    {
        growMemory(newSize); // make sure enough device memory is allocated
        ecuda::fill( begin(), end(), value );
        n = newSize;
    }

    template<class Iterator>
    __HOST__ void assign( Iterator first, Iterator last )
    {
        typename std::iterator_traits<Iterator>::difference_type len = ::ecuda::distance(first,last);
        growMemory( len ); // make sure enough device memory is allocated
        ecuda::copy( first, last, begin() );
        n = len;
    }

    #ifdef ECUDA_CPP11_AVAILABLE
    __HOST__ inline void assign( std::initializer_list<value_type> il )
    {
        assign( il.begin(), il.end() );
        //host_array_proxy<const value_type> proxy( il.begin(), il.size() );
        //assign( proxy.begin(), proxy.end() );
    }
    #endif

    __HOST__ void push_back( const value_type& value )
    {
        growMemory(n+1);
        ecuda::copy( &value, (&value)+1, begin()+n );
        ++n;
    }

    __HOST__ __DEVICE__ inline void pop_back() { /*if( n )*/ --n; } // NOTE: if called from device the host instance doesn't change

    __HOST__ iterator insert( const_iterator position, const value_type& value )
    {
        std::vector< value_type, host_allocator<value_type> > v( ::ecuda::distance(position,end())+1 ); // allocate staging memory
        v.front() = value; // put new element at front of staging
        ::ecuda::copy( position, end(), v.begin()+1 ); // copy trailing elements to staging
        const size_type index = ::ecuda::distance(begin(),position); // get index of insert position
        growMemory(size()+1); // make sure enough device memory is allocated
        // reacquire iterator just in case new memory was allocated
        const_iterator newPosition = begin()+index;
        ::ecuda::copy( v.begin(), v.end(), newPosition );
        ++n;
        return newPosition;
    }

    __HOST__ iterator insert( const_iterator position, const size_type count, const value_type& value )
    {
        std::vector< value_type, host_allocator<value_type> > v( ::ecuda::distance(position,end())+count, value ); // allocate staging memory
        ::ecuda::copy( position, end(), v.begin()+count ); // copy trailing elements to staging
        const size_type index = ::ecuda::distance(begin(),position); // get index of insert position
        growMemory(size()+count); // make sure enough device memory is allocated
        // require iterator just in case new memory was allocated
        const_iterator newPosition = begin()+index;
        ::ecuda::copy( v.begin(), v.end(), newPosition );
        n += count;
        return newPosition;
    }

    template<class InputIterator>
    __HOST__ void insert( const_iterator position, InputIterator first, InputIterator last )
    {
        const std::vector< value_type, host_allocator<value_type> > v( first, last ); // allocate staging memory and put new content there
        const size_type len = v.size(); // number of new elements
        v.resize( v.size()+::ecuda::distance(position,end()) ); // make room for trailing elements
        ::ecuda::copy( position, end(), v.begin()+len ); // copy trailing elements to staging
        const size_type index = ::ecuda::distance(begin(),position); // get index of insert position
        growMemory(size()+len); // make sure enough device memory is allocated
        // require iterator just in case new memory was allocated
        const_iterator newPosition = begin()+index;
        ::ecuda::copy( v.begin(), v.end(), newPosition );
        n += len;
    }

    #ifdef ECUDA_CPP11_AVAILABLE
    __HOST__ inline void insert( const_iterator position, std::initializer_list<value_type> il )
    {
        return insert( position, il.begin(), il.end() );
    }
    #endif

    __HOST__ iterator erase( const_iterator position )
    {
        vector<value_type> v( position+1, end() ); // copy trailing elements to another device vector
        ecuda::copy( v.begin(), v.end(), position ); // overwrite erase position
        --n;
        return begin()+ecuda::distance(begin(),position);
    }

    __HOST__ iterator erase( const_iterator first, const_iterator last )
    {
        vector<value_type> v( last, end() ); // copy trailing elements to another device vector
        ecuda::copy( v.begin(), v.end(), first ); // overwrite erased elements
        n -= ecuda::distance(first,last);
        return begin()+ecuda::distance(begin(),first);
    }

    __HOST__ __DEVICE__ void swap( vector& other )
    {
        base_type::swap( other );
        ecuda::swap( n, other.n );
    }

    __HOST__ __DEVICE__ inline void clear() { n = 0; }

    __HOST__ inline allocator_type get_allocator() const { return allocator; }

    __HOST__ void shrink_to_fit()
    {
        if( size() == capacity() ) return;
        vector v( n );
        ecuda::copy( begin(), end(), v.begin() );
        swap( v );
    }

    __HOST__ __DEVICE__ bool operator==( const vector& other ) const
    {
        if( size() != other.size() ) return false;
        #ifdef __CUDA_ARCH__
        const_iterator iter1 = begin();
        const_iterator iter2 = other.begin();
        for( ; iter1 != end(); ++iter1, ++iter2 ) if( !( *iter1 == *iter2 ) ) return false;
        return true;
        #else
        return ecuda::equal( begin(), end(), other.begin(), other.end() );
        #endif
    }

    __HOST__ __DEVICE__ inline bool operator!=( const vector& other ) const { return !operator==(other); }

    __HOST__ __DEVICE__ inline bool operator<( const vector& other ) const
    {
        #ifdef __CUDA_ARCH__
        return ecuda::lexicographical_compare( begin(), end(), other.begin(), other.end() );
        #else
        std::vector< value_type, host_allocator<value_type> > v1( size() ), v2( size() );
        ecuda::copy( begin(), end(), v1.begin() );
        ecuda::copy( other.begin(), other.end(), v2.begin() );
        return std::lexicographical_compare( v1.begin(), v1.end(), v2.begin(), v2.end() );
        #endif
    }

    __HOST__ __DEVICE__ inline bool operator>( const vector& other ) const
    {
        #ifdef __CUDA_ARCH__
        return ecuda::lexicographical_compare( other.begin(), other.end(), begin(), end() );
        #else
        std::vector< value_type, host_allocator<value_type> > v1( size() ), v2( size() );
        ecuda::copy( begin(), end(), v1.begin() );
        ecuda::copy( other.begin(), other.end(), v2.begin() );
        return std::lexicographical_compare( v2.begin(), v2.end(), v1.begin(), v1.end() );
        #endif
    }

    __HOST__ __DEVICE__ inline bool operator<=( const vector& other ) const { return !operator>(other); }

    __HOST__ __DEVICE__ inline bool operator>=( const vector& other ) const { return !operator<(other); }

};

template<typename T,class Alloc,class P>
__HOST__ void vector<T,Alloc,P>::growMemory( size_type minimum )
{
    if( base_type::size() >= minimum ) return; // no growth neccessary
    size_type m2 = base_type::size();
    if( !m2 ) m2 = 1; // in case no memory is currently allocated
    while( m2 < minimum ) m2 <<= 1;
    // allocate larger chunk
    shared_ptr<value_type> newMemory( get_allocator().allocate( m2 ) );
    model::device_contiguous_sequence< value_type, shared_ptr<value_type> > newSequence( newMemory, m2 );
    ecuda::copy( begin(), end(), newSequence.begin() );
    base_type::swap( newSequence );
}

namespace impl {

template<typename T,class Alloc>
class vector_kernel_argument : public vector<T,Alloc,typename ecuda::add_pointer<T>::type>
{

private:
    typedef vector<T,Alloc,typename ecuda::add_pointer<T>::type> base_type;

public:
    template<class P>
    __HOST__ vector_kernel_argument( const vector<T,Alloc,P>& src ) : base_type( src, ecuda::true_type() ) {}
    __HOST__ __DEVICE__ vector_kernel_argument( const vector_kernel_argument& src ) : base_type( src, ecuda::true_type() ) {}
    template<class P>
    __HOST__ vector_kernel_argument& operator=( const vector<T,Alloc,P>& src )
    {
        vector<T,Alloc>::shallow_assign( src );
        return *this;
    }

    #ifdef ECUDA_CPP11_AVAILABLE
    vector_kernel_argument( vector_kernel_argument&& src ) : base_type(std::move(src)) {}

    vector_kernel_argument& operator=( vector_kernel_argument&& src )
    {
        base_type::operator=(std::move(src));
        return *this;
    }
    #endif

};

} // namespace impl

} // namespace ecuda

#endif