sharedVector.h

/* sharedVector.h */
/*
 * Copyright information and license terms for this software can be
 * found in the file LICENSE that is included with the distribution
 */
#ifndef SHAREDVECTOR_H
#define SHAREDVECTOR_H

#include <ostream>
#include <algorithm>
#include <stdexcept>
#include <iterator>

#if __cplusplus>=201103L
#  include <initializer_list>
#endif

#include <cassert>

#include "pv/sharedPtr.h"
#include "pv/pvIntrospect.h"
#include "pv/typeCast.h"
#include "pv/templateMeta.h"

namespace epics { namespace pvData {

template<typename E, class Enable = void> class shared_vector;

template<typename TO, typename FROM>
static FORCE_INLINE
shared_vector<TO>
const_shared_vector_cast(shared_vector<FROM>& src);

namespace detail {
    template<typename E>
    struct default_array_deleter {void operator()(E a){delete[] a;}};

    // How values should be passed as arguments to shared_vector methods
    // really should use boost::call_traits
    template<typename T> struct call_with { typedef T type; };
    template<typename T> struct call_with<std::tr1::shared_ptr<T> >
    { typedef const std::tr1::shared_ptr<T>& type; };
    template<> struct call_with<std::string> { typedef const std::string& type; };

    struct _shared_vector_freeze_tag {};
    struct _shared_vector_thaw_tag {};
    struct _shared_vector_cast_tag {};

    /* All the parts of shared_vector which
     * don't need special handling for E=void
     */
    template<typename E>
    class shared_vector_base
    {
        // allow specialization for all E to be friends
        template<typename E1> friend class shared_vector_base;
    protected:
        // NOTE: Do no use m_data, since VxWorks has a 'm_data' macro defined
        std::tr1::shared_ptr<E> m_sdata;
        size_t m_offset;
        size_t m_count;
        size_t m_total;

        /* invariants
         *  m_count <= m_total (enforced)
         *  m_offset + m_total <= (size_t)-1 (checked w/ assert())
         */

    public:
#if __cplusplus>=201103L
        constexpr shared_vector_base() noexcept
            :m_sdata(), m_offset(0), m_count(0), m_total(0)
        {}
#else
        shared_vector_base()
            :m_sdata(), m_offset(0), m_count(0), m_total(0)
        {}
#endif

    protected:
        // helper for constructors
        // Ensure that offset and size are zero when we are constructed with NULL
        void _null_input()
        {
            if(!m_sdata) {
                m_offset = m_total = m_count = 0;
            } else {
                // ensure we won't have integer overflows later
                assert( m_offset <= ((size_t)-1) - m_total);
            }
        }
    public:

        template<typename A>
        shared_vector_base(A* v, size_t o, size_t c)
            :m_sdata(v, detail::default_array_deleter<A*>())
            ,m_offset(o), m_count(c), m_total(c)
        {_null_input();}

        shared_vector_base(const std::tr1::shared_ptr<E>& d, size_t o, size_t c)
            :m_sdata(d), m_offset(o), m_count(c), m_total(c)
        {_null_input();}


        template<typename A, typename B>
        shared_vector_base(A d, B b, size_t o, size_t c)
            :m_sdata(d,b), m_offset(o), m_count(c), m_total(c)
        {_null_input();}

        shared_vector_base(const shared_vector_base& O)
            :m_sdata(O.m_sdata), m_offset(O.m_offset)
            ,m_count(O.m_count), m_total(O.m_total)
        {}

#if __cplusplus >= 201103L
        shared_vector_base(shared_vector_base &&O)
            :m_sdata(std::move(O.m_sdata))
            ,m_offset(O.m_offset)
            ,m_count(O.m_count)
            ,m_total(O.m_total)
        {
            O.clear();
        }
#endif

    protected:
        typedef typename meta::strip_const<E>::type _E_non_const;
    public:
        shared_vector_base(shared_vector_base<_E_non_const>& O,
                           _shared_vector_freeze_tag)
            :m_sdata()
            ,m_offset(O.m_offset)
            ,m_count(O.m_count)
            ,m_total(O.m_total)
        {
            if(!O.unique())
                throw std::runtime_error("Can't freeze non-unique vector");
#if __cplusplus >= 201103L
            m_sdata = std::move(O.m_sdata);
#else
            m_sdata = O.m_sdata;
#endif
            O.clear();
        }

        shared_vector_base(shared_vector<const E>& O,
                           _shared_vector_thaw_tag)
            :m_sdata()
            ,m_offset(O.m_offset)
            ,m_count(O.m_count)
            ,m_total(O.m_total)
        {
            O.make_unique();
#if __cplusplus >= 201103L
            m_sdata = std::move(std::tr1::const_pointer_cast<E>(O.m_sdata));
#else
            m_sdata = std::tr1::const_pointer_cast<E>(O.m_sdata);
#endif
            O.clear();
        }

        shared_vector_base& operator=(const shared_vector_base& o)
        {
            if(&o!=this) {
                m_sdata=o.m_sdata;
                m_offset=o.m_offset;
                m_count=o.m_count;
                m_total=o.m_total;
            }
            return *this;
        }

#if __cplusplus >= 201103L
        shared_vector_base& operator=(shared_vector_base&& o)
        {
            if(&o!=this) {
                m_sdata=std::move(o.m_sdata);
                m_offset=o.m_offset;
                m_count=o.m_count;
                m_total=o.m_total;
                o.clear();
            }
            return *this;
        }
#endif

        void swap(shared_vector_base& o) {
            if(&o!=this) {
                m_sdata.swap(o.m_sdata);
                std::swap(m_count, o.m_count);
                std::swap(m_offset, o.m_offset);
                std::swap(m_total, o.m_total);
            }
        }

        void clear() {
            m_sdata.reset();
            m_offset = m_total = m_count = 0;
        }

        bool unique() const {return !m_sdata || m_sdata.use_count()<=1;}


        size_t size() const{return m_count;}
        bool empty() const{return !m_count;}


        void slice(size_t offset, size_t length=(size_t)-1)
        {
            if(offset>m_count)
                offset = m_count; // will slice down to zero length

            const size_t max_count = m_count - offset;

            m_offset += offset;

            m_total -= offset;

            if(length > max_count)
                length = max_count;
            m_count = length;
        }

        // Access to members.
        const std::tr1::shared_ptr<E>& dataPtr() const { return m_sdata; }
        size_t dataOffset() const { return m_offset; }
        size_t dataCount() const { return m_count; }
        size_t dataTotal() const { return m_total; }
    };
}

template<typename E, class Enable>
class shared_vector : public detail::shared_vector_base<E>
{
    typedef detail::shared_vector_base<E> base_t;
    typedef typename detail::call_with<E>::type param_type;
    typedef typename meta::strip_const<E>::type _E_non_const;
public:
    typedef E value_type;
    typedef E& reference;
    typedef typename meta::decorate_const<E>::type& const_reference;
    typedef E* pointer;
    typedef typename meta::decorate_const<E>::type* const_pointer;
    typedef E* iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef typename meta::decorate_const<E>::type* const_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;

    typedef E element_type;
    typedef std::tr1::shared_ptr<E> shared_pointer_type;

    // allow specialization for all E to be friends
    template<typename E1, class Enable1> friend class shared_vector;

#if __cplusplus>=201103L
    constexpr shared_vector() noexcept :base_t() {}
#else
    shared_vector() :base_t() {}
#endif

#if __cplusplus>=201103L
    template<typename A>
    shared_vector(std::initializer_list<A> L)
        :base_t(new _E_non_const[L.size()], 0, L.size())
    {
        _E_non_const *raw = const_cast<_E_non_const*>(data());
        std::copy(L.begin(), L.end(), raw);
    }
#endif

    explicit shared_vector(size_t c)
        :base_t(new _E_non_const[c], 0, c)
    {}

    shared_vector(size_t c, param_type e)
        :base_t(new _E_non_const[c], 0, c)
    {
        std::fill_n((_E_non_const*)this->m_sdata.get(), this->m_count, e);
    }

    template<typename A>
    shared_vector(A v, size_t o, size_t c) :base_t(v,o,c) {}

    template<typename E1>
    shared_vector(const std::tr1::shared_ptr<E1>& d, size_t o, size_t c)
        :base_t(d,o,c) {}

    template<typename A, typename B>
    shared_vector(A d, B b, size_t o, size_t c)
        :base_t(d,b,o,c) {}

    shared_vector(const shared_vector& o) :base_t(o) {}

#if __cplusplus>=201103L
    shared_vector(shared_vector&& o) :base_t(std::move(o)) {}
#endif

    template<typename FROM>
    shared_vector(const shared_vector<FROM> &src,
                  detail::_shared_vector_cast_tag)
        :base_t(std::tr1::static_pointer_cast<E>(src.dataPtr()),
                src.dataOffset()/sizeof(E),
                src.dataCount()/sizeof(E))
    {}


    shared_vector(shared_vector<typename base_t::_E_non_const>& O,
                  detail::_shared_vector_freeze_tag t)
        :base_t(O,t)
    {}

    shared_vector(shared_vector<const E>& O,
                  detail::_shared_vector_thaw_tag t)
        :base_t(O,t)
    {}

    inline shared_vector& operator=(const shared_vector& o)
    {
        this->base_t::operator=(o);
        return *this;
    }

#if __cplusplus>=201103L
    inline shared_vector& operator=(shared_vector&& o)
    {
        this->base_t::operator=(std::move(o));
        return *this;
    }
#endif

    size_t max_size() const{return ((size_t)-1)/sizeof(E);}

    size_t capacity() const { return this->m_total; }

    void reserve(size_t i) {
        if(this->unique() && i<=this->m_total)
            return;
        size_t new_count = this->m_count;
        if(new_count > i)
            new_count = i;
        _E_non_const* temp=new _E_non_const[i];
        try{
            std::copy(begin(), begin()+new_count, temp);
        }catch(...){
            delete[] temp;
            throw;
        }
        this->m_sdata.reset(temp, detail::default_array_deleter<E*>());
        this->m_offset = 0;
        this->m_count = new_count;
        this->m_total = i;
    }

    void resize(size_t i) {
        if(i==this->m_count) {
            make_unique();
            return;
        }
        if(this->m_sdata && this->m_sdata.use_count()==1) {
            // we have data and exclusive ownership of it
            if(i<=this->m_total) {
                // We have room to grow (or shrink)!
                this->m_count = i;
                return;
            }
        }
        // must re-allocate :(
        size_t new_total = this->m_total;
        if(new_total < i)
            new_total = i;
        _E_non_const* temp=new _E_non_const[new_total];
        try{
            size_t n = this->size();
            if(n > i)
                n = i;
            // Copy as much as possible from old,
            // remaining elements are uninitialized.
            std::copy(begin(),
                      begin()+n,
                      temp);
        }catch(...){
            delete[] temp;
            throw;
        }
        this->m_sdata.reset(temp, detail::default_array_deleter<pointer>());
        this->m_offset= 0;
        this->m_count = i;
        this->m_total = new_total;
    }

    void resize(size_t i, param_type v) {
        size_t oldsize=this->size();
        resize(i);
        if(this->size()>oldsize) {
            std::fill(begin()+oldsize, end(), v);
        }
    }

    void make_unique() {
        if(this->unique())
            return;
        // at this point we know that !!m_sdata, so get()!=NULL
        _E_non_const *d = new _E_non_const[this->m_total];
        try {
            std::copy(this->m_sdata.get()+this->m_offset,
                      this->m_sdata.get()+this->m_offset+this->m_count,
                      d);
        }catch(...){
            delete[] d;
            throw;
        }
        this->m_sdata.reset(d, detail::default_array_deleter<E*>());
        this->m_offset=0;
    }

private:
    /* Hack alert.
     * For reasons of simplicity and efficiency, we want to use raw pointers for iteration.
     * However, shared_ptr::get() isn't defined when !m_sdata, although practically it gives NULL.
     * Unfortunately, many of the MSVC (<= VS 2013) STL methods assert() that iterators are never NULL.
     * So we fudge here by abusing 'this' so that our iterators are always !NULL.
     */
    inline E* base_ptr() const {
#if defined(_MSC_VER) && _MSC_VER<=1800
        return this->m_count ? this->m_sdata.get() : (E*)(this-1);
#else
        return this->m_sdata.get();
#endif
    }
public:
    // STL iterators

    iterator begin() const{return this->base_ptr()+this->m_offset;}
    const_iterator cbegin() const{return begin();}

    iterator end() const{return this->base_ptr()+this->m_offset+this->m_count;}
    const_iterator cend() const{return end();}

    reverse_iterator rbegin() const{return reverse_iterator(end());}
    const_reverse_iterator crbegin() const{return rbegin();}

    reverse_iterator rend() const{return reverse_iterator(begin());}
    const_reverse_iterator crend() const{return rend();}

    reference front() const{return (*this)[0];}
    reference back() const{return (*this)[this->m_count-1];}

    // Modifications

private:
    void _push_resize() {
        if(this->m_count==this->m_total || !this->unique()) {
            size_t next;
            if(this->m_total<1024) {
                // round m_total+1 up to the next power of 2
                next = this->m_total;
                next |= next >> 1;
                next |= next >> 2;
                next |= next >> 4;
                next |= next >> 8;
                next++;
            } else {
                // pad m_total up to the next multiple of 1024
                next = this->m_total+1024;
                next &= ~0x3ff;
            }
            assert(next > this->m_total);
            reserve(next);
        }
        resize(this->size()+1);
    }

public:

    void push_back(param_type v)
    {
        _push_resize();
        back() = v;
    }

    void pop_back()
    {
        this->slice(0, this->size()-1);
    }

    // data access

    pointer data() const{return this->m_sdata.get()+this->m_offset;}

    reference operator[](size_t i) const {return this->m_sdata.get()[this->m_offset+i];}

    reference at(size_t i) const
    {
        if(i>this->m_count)
            throw std::out_of_range("Index out of bounds");
        return (*this)[i];
    }

};

template<typename E>
class shared_vector<E, typename meta::is_void<E>::type >
    : public detail::shared_vector_base<E>
{
    typedef detail::shared_vector_base<E> base_t;
    ScalarType m_vtype;

    // allow specialization for all E to be friends
    template<typename E1, class Enable1> friend class shared_vector;
public:
    typedef E value_type;
    typedef E* pointer;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;

    typedef std::tr1::shared_ptr<E> shared_pointer_type;

#if __cplusplus>=201103L
    constexpr shared_vector() noexcept :base_t(), m_vtype((ScalarType)-1) {}
#else
    shared_vector() :base_t(), m_vtype((ScalarType)-1) {}
#endif

    shared_vector(pointer v, size_t o, size_t c)
        :base_t(v,o,c), m_vtype((ScalarType)-1) {}

    template<typename B>
    shared_vector(pointer d, B b, size_t o, size_t c)
        :base_t(d,b,o,c), m_vtype((ScalarType)-1) {}

    template<typename E1>
    shared_vector(const std::tr1::shared_ptr<E1>& d, size_t o, size_t c)
        :base_t(d,o,c), m_vtype((ScalarType)-1) {}

    shared_vector(const shared_vector& o)
        :base_t(o), m_vtype(o.m_vtype) {}

#if __cplusplus>=201103L
    shared_vector(shared_vector&& o)
        :base_t(std::move(o)), m_vtype(o.m_vtype) {}
#endif

    template<typename FROM>
    shared_vector(const shared_vector<FROM> &src,
                  detail::_shared_vector_cast_tag)
        :base_t(std::tr1::static_pointer_cast<E>(src.dataPtr()),
                src.dataOffset()*sizeof(FROM),
                src.dataCount()*sizeof(FROM))
        ,m_vtype((ScalarType)ScalarTypeID<FROM>::value)
    {}

    shared_vector(shared_vector<void>& O,
                  detail::_shared_vector_freeze_tag t)
        :base_t(O,t), m_vtype(O.m_vtype)
    {}

    shared_vector(shared_vector<const void>& O,
                  detail::_shared_vector_thaw_tag t)
        :base_t(O,t), m_vtype(O.m_vtype)
    {}

    shared_vector& operator=(const shared_vector& o)
    {
        if(&o!=this) {
            this->base_t::operator=(o);
            m_vtype = o.m_vtype;
        }
        return *this;
    }

#if __cplusplus>=201103L
    shared_vector& operator=(shared_vector&& o)
    {
        if(&o!=this) {
            this->base_t::operator=(std::move(o));
            m_vtype = o.m_vtype;
        }
        return *this;
    }
#endif

    void swap(shared_vector& o) {
        base_t::swap(o);
        std::swap(m_vtype, o.m_vtype);
    }

    size_t max_size() const{return (size_t)-1;}

    pointer data() const{
        return (pointer)(((char*)this->m_sdata.get())+this->m_offset);
    }

    shared_vector& set_original_type(ScalarType t) { m_vtype=t; return *this; }
    ScalarType original_type() const {return m_vtype;}
};

namespace detail {
    template<typename TO, typename FROM, class Enable = void>
    struct static_shared_vector_caster { /* no default */ };
    // from void to non-void with same const-ness
    template<typename TO, typename FROM>
    struct static_shared_vector_caster<TO, FROM,
                                       typename meta::_and<meta::_and<meta::is_not_void<TO>, meta::is_void<FROM> >,
                                                           meta::same_const<TO,FROM> >::type> {
        static inline shared_vector<TO> op(const shared_vector<FROM>& src) {
            return shared_vector<TO>(src, detail::_shared_vector_cast_tag());
        }
    };
    // from non-void to void with same const-ness
    template<typename TO, typename FROM>
    struct static_shared_vector_caster<TO, FROM,
                                       typename meta::_and<meta::_and<meta::is_void<TO>, meta::is_not_void<FROM> >,
                                                           meta::same_const<TO,FROM> >::type> {
        static FORCE_INLINE shared_vector<TO> op(const shared_vector<FROM>& src) {
            return shared_vector<TO>(src, detail::_shared_vector_cast_tag());
        }
    };

    // cast to same type, no-op
    template<typename TOFRO>
    struct static_shared_vector_caster<TOFRO,TOFRO,void> {
        static FORCE_INLINE const shared_vector<TOFRO>& op(const shared_vector<TOFRO>& src) {
            return src;
        }
    };
} // namespace detail

template<typename TO, typename FROM>
static FORCE_INLINE
shared_vector<TO>
static_shared_vector_cast(const shared_vector<FROM>& src)
{
    return detail::static_shared_vector_caster<TO,FROM>::op(src);
}

namespace detail {

    // Default to type conversion using castUnsafe (C++ type casting) on each element
    template<typename TO, typename FROM, class Enable = void>
    struct shared_vector_converter {
        static inline shared_vector<TO> op(const shared_vector<FROM>& src)
        {
            shared_vector<TO> ret(src.size());
            std::transform(src.begin(), src.end(), ret.begin(), castUnsafe<TO,FROM>);
            return ret;
        }
    };

    // copy reference when types are the same (excluding const qualifiers)
    template<typename TO, typename FROM>
    struct shared_vector_converter<TO,FROM, typename meta::same_root<TO,FROM>::type > {
        static FORCE_INLINE shared_vector<TO> op(const shared_vector<FROM>& src) {
            return src;
        }
    };

    // "convert" to 'void' or 'const void from non-void
    // is an alias for shared_vector_cast<void>()
    template<typename TO, typename FROM>
    struct shared_vector_converter<TO,FROM,
            typename meta::_and<meta::is_void<TO>, meta::is_not_void<FROM> >::type
            >
    {
        static FORCE_INLINE shared_vector<TO> op(const shared_vector<FROM>& src) {
            return shared_vector<TO>(src, detail::_shared_vector_cast_tag());
        }
    };

    // convert from void uses original type or throws an exception.
    template<typename TO, typename FROM>
    struct shared_vector_converter<TO,FROM,
            typename meta::_and<meta::is_not_void<TO>, meta::is_void<FROM> >::type
            >
    {
        static shared_vector<TO> op(const shared_vector<FROM>& src) {
            typedef typename meta::strip_const<TO>::type to_t;
            ScalarType stype = src.original_type(),
                       dtype = (ScalarType)ScalarTypeID<TO>::value;
            if(src.empty()) {
                return shared_vector<TO>();

            } else if(stype==dtype) {
                // no convert needed
                return shared_vector<TO>(src, detail::_shared_vector_cast_tag());

            } else {
                // alloc and convert
                shared_vector<to_t> ret(src.size()/ScalarTypeFunc::elementSize(stype));
                castUnsafeV(ret.size(),
                            dtype,
                            static_cast<void*>(ret.data()),
                            stype,
                            static_cast<const void*>(src.data()));
                return const_shared_vector_cast<TO>(ret);
            }
        }
    };
}

template<typename TO, typename FROM>
static FORCE_INLINE
shared_vector<TO>
shared_vector_convert(const shared_vector<FROM>& src)
{
    return detail::shared_vector_converter<TO,FROM>::op(src);
}

template<typename SRC>
static FORCE_INLINE
shared_vector<typename meta::decorate_const<typename SRC::value_type>::type>
freeze(SRC& src)
{
    typedef typename meta::decorate_const<typename SRC::value_type>::type const_value;
    return shared_vector<const_value>(src, detail::_shared_vector_freeze_tag());
}

template<typename SRC>
static FORCE_INLINE
shared_vector<typename meta::strip_const<typename SRC::value_type>::type>
thaw(SRC& src)
{
    typedef typename meta::strip_const<typename SRC::value_type>::type value;
    return shared_vector<value>(src, detail::_shared_vector_thaw_tag());
}

namespace detail {
    template<typename TO, typename FROM, class Enable = void>
    struct const_caster {};

    template<typename TYPE>
    struct const_caster<TYPE,const TYPE> {
        static FORCE_INLINE shared_vector<TYPE> op(shared_vector<const TYPE>& src)
        {
            return thaw(src);
        }
    };

    template<typename TYPE>
    struct const_caster<const TYPE,TYPE> {
        static FORCE_INLINE shared_vector<const TYPE> op(shared_vector<TYPE>& src)
        {
            return freeze(src);
        }
    };

    template<typename TYPE>
    struct const_caster<TYPE,TYPE> {
        static FORCE_INLINE shared_vector<TYPE> op(shared_vector<TYPE>& src)
        {
            shared_vector<TYPE> ret(src);
            src.clear();
            return ret;
        }
    };
}

template<typename TO, typename FROM>
static FORCE_INLINE
shared_vector<TO>
const_shared_vector_cast(shared_vector<FROM>& src)
{
    return detail::const_caster<TO,FROM>::op(src);
}


namespace ScalarTypeFunc {
    epicsShareFunc shared_vector<void> allocArray(ScalarType id, size_t len);

    template<ScalarType ID>
    inline
    shared_vector<typename ScalarTypeTraits<ID>::type>
    allocArray(size_t len)
    {
        shared_vector<void> raw(allocArray(ID, len));
        return static_shared_vector_cast<typename ScalarTypeTraits<ID>::type>(raw);
    }
}

}} // namespace epics::pvData

// Global operators for shared_vector

template<typename A, typename B>
bool operator==(const epics::pvData::shared_vector<A>& a,
                const epics::pvData::shared_vector<B>& b)
{
    if(a.size() != b.size())
        return false;
    if(a.dataOffset()==b.dataOffset() && a.dataPtr().get()==b.dataPtr().get())
        return true;
    return std::equal(a.begin(), a.end(), b.begin());
}

template<typename A, typename B>
bool operator!=(const epics::pvData::shared_vector<A>& a,
                const epics::pvData::shared_vector<B>& b)
{
    return !(a==b);
}

template<typename E>
std::ostream& operator<<(std::ostream& strm, const epics::pvData::shared_vector<E>& arr)
{
    strm<<'{'<<arr.size()<<"}[";
    for(size_t i=0; i<arr.size(); i++) {
        if(i>10) {
            strm<<"...";
            break;
        }
        strm<<arr[i];
        if(i+1<arr.size())
            strm<<", ";
    }
    strm<<']';
    return strm;
}


#endif // SHAREDVECTOR_H