simple_vector.h

/*****************************************************/
/* lean Containers              (c) Tobias Zirr 2011 */
/*****************************************************/

#ifndef LEAN_CONTAINERS_SIMPLE_VECTOR
#define LEAN_CONTAINERS_SIMPLE_VECTOR

#include "../lean.h"
#include "../meta/type_traits.h"
#include <memory>
#include <stdexcept>

namespace lean 
{
namespace containers
{

namespace simple_vector_policies
{
    template <bool RawMove = false, bool NoDestruct = false, bool NoConstruct = false>
    struct policy
    {
        static const bool raw_move = RawMove;
        static const bool no_destruct = NoDestruct;
        static const bool no_construct = NoConstruct;
    };

    typedef policy<> nonpod;
    typedef policy<true> semipod;
    typedef policy<true, true> inipod;
    typedef policy<true, true, true> pod;
}

template < class Element, class Policy = simple_vector_policies::nonpod, class Allocator = std::allocator<Element> >
class simple_vector
{
private:
    typedef typename Allocator::template rebind<Element>::other allocator_type_;
    allocator_type_ m_allocator;

    Element *m_elements;
    Element *m_elementsEnd;
    Element *m_capacityEnd;

    typedef typename allocator_type_::size_type size_type_;
    static const size_type_ s_maxSize = static_cast<size_type_>(-1); // WORKAROUND: premature evaluation / sizeof(Element);
    static const size_type_ s_minSize = (16 < s_maxSize) ? 16 : s_maxSize;

    // Make sure size_type is unsigned
    LEAN_STATIC_ASSERT(is_unsigned<size_type_>::value);

    LEAN_INLINE void default_construct(Element *dest)
    {
        if (!Policy::no_construct)
            m_allocator.construct(dest, Element());
    }
    void default_construct(Element *dest, Element *destEnd)
    {
        if (!Policy::no_construct)
        {
            Element *destr = dest;

            try
            {
                for (; dest != destEnd; ++dest)
                    default_construct(dest);
            }
            catch(...)
            {
                destruct(destr, dest);
                throw;
            }
        }
    }
    LEAN_INLINE void copy_construct(Element *dest, const Element &source)
    {
        m_allocator.construct(dest, source);
    }
    template <class Iterator>
    void copy_construct(Iterator source, Iterator sourceEnd, Element *dest)
    {
        Element *destr = dest;

        try
        {
            for (; source != sourceEnd; ++dest, ++source)
                copy_construct(dest, *source);
        }
        catch(...)
        {
            destruct(destr, dest);
            throw;
        }
    }
    LEAN_INLINE void move_construct(Element *dest, Element &source)
    {
#ifndef LEAN0X_NO_RVALUE_REFERENCES
        m_allocator.construct(dest, std::move(source));
#else
        copy_construct(dest, source);
#endif
    }
    void move_construct(Element *source, Element *sourceEnd, Element *dest)
    {
        Element *destr = dest;

        try
        {
            for (; source != sourceEnd; ++dest, ++source)
                move_construct(dest, *source);
        }
        catch(...)
        {
            destruct(destr, dest);
            throw;
        }
    }
    LEAN_INLINE void move(Element *dest, Element &source)
    {
#ifndef LEAN0X_NO_RVALUE_REFERENCES
        *dest = std::move(source);
#else
        *dest = source;
#endif
    }
    void move(Element *source, Element *sourceEnd, Element *dest)
    {
        for (; source != sourceEnd; ++dest, ++source)
            move(dest, *source);
    }

    LEAN_INLINE void destruct(Element *destr)
    {
        if (!Policy::no_destruct)
            m_allocator.destroy(destr);
    }
    void destruct(Element *destr, Element *destrEnd)
    {
        if (!Policy::no_destruct)
            for (; destr != destrEnd; ++destr)
                destruct(destr);
    }

    void reallocate(size_type_ newCapacity)
    {
        Element *newElements = m_allocator.allocate(newCapacity);

        if (!empty())
            try
            {
                if (Policy::raw_move)
                    memcpy(newElements, m_elements, size() * sizeof(Element));
                else
                    move_construct(m_elements, m_elementsEnd, newElements);
            }
            catch(...)
            {
                m_allocator.deallocate(newElements, newCapacity);
                throw;
            }

        Element *oldElements = m_elements;
        Element *oldElementsEnd = m_elementsEnd;
        size_type_ oldCapacity = capacity();
        
        // Mind the order, size() based on member variables!
        m_elementsEnd = newElements + size();
        m_capacityEnd = newElements + newCapacity;
        m_elements = newElements;

        if (oldElements)
        {
            // Do nothing on exception, resources leaking anyways!
            if (!Policy::raw_move)
                destruct(oldElements, oldElementsEnd);
            m_allocator.deallocate(oldElements, oldCapacity);
        }
    }

    LEAN_INLINE void free()
    {
        if (m_elements)
        {
            // Do nothing on exception, resources leaking anyways!
            destruct(m_elements, m_elementsEnd);
            m_allocator.deallocate(m_elements, capacity());
        }
    }

    LEAN_INLINE void growTo(size_type_ newCount, bool checkLength = true)
    {
        // Mind overflow
        if (checkLength)
            check_length(newCount);

        reallocate(next_capacity_hint(newCount));
    }
    LEAN_INLINE void grow(size_type_ count)
    {
        size_type_ oldSize = size();

        // Mind overflow
        if (count > s_maxSize || s_maxSize - count < oldSize)
            length_exceeded();

        growTo(oldSize + count, false);
    }
    LEAN_INLINE Element& grow_and_relocate(Element &value)
    {
        size_type_ index = lean::addressof(value) - m_elements;
        grow(1);
        
        // Index is unsigned, make use of wrap-around
        return (index < size())
            ? m_elements[index]
            : value;
    }

    LEAN_NOINLINE void growToHL(size_type_ newCount)
    {
        growTo(newCount);
    }
    LEAN_NOINLINE void growHL(size_type_ count)
    {
        grow(count);
    }
    LEAN_NOINLINE void grow_and_pushHL(const Element &value)
    {
        copy_construct(m_elementsEnd, grow_and_relocate(const_cast<Element&>(value)));
        ++m_elementsEnd;
    }
    LEAN_NOINLINE void grow_and_pushHL(Element &&value)
    {
        move_construct(m_elementsEnd, grow_and_relocate(value));
        ++m_elementsEnd;
    }

    LEAN_NOINLINE static void out_of_range()
    {
        throw std::out_of_range("simple_vector<T> out of range");
    }
    LEAN_INLINE void check_pos(size_type_ pos) const
    {
        if (pos >= size())
            out_of_range();
    }
    LEAN_NOINLINE static void length_exceeded()
    {
        throw std::length_error("simple_vector<T> too long");
    }
    LEAN_INLINE static void check_length(size_type_ count)
    {
        if (count > s_maxSize)
            length_exceeded();
    }

public:
    typedef Policy construction_policy;

    typedef allocator_type_ allocator_type;
    typedef size_type_ size_type;
    typedef typename allocator_type::difference_type difference_type;

    typedef typename allocator_type::pointer pointer;
    typedef typename allocator_type::const_pointer const_pointer;
    typedef typename allocator_type::reference reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef typename allocator_type::value_type value_type;

    typedef pointer iterator;
    typedef const_pointer const_iterator;

    simple_vector()
        : m_elements(nullptr),
        m_elementsEnd(nullptr),
        m_capacityEnd(nullptr) { }
    explicit simple_vector(allocator_type allocator)
        : m_allocator(allocator),
        m_elements(nullptr),
        m_elementsEnd(nullptr),
        m_capacityEnd(nullptr) { }
    simple_vector(const simple_vector &right)
        : m_allocator(right.m_allocator),
        m_elements(nullptr),
        m_elementsEnd(nullptr),
        m_capacityEnd(nullptr)
    {
        assign_disj(right.begin(), right.end());
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    simple_vector(simple_vector &&right)
        : m_allocator(std::move(right.m_allocator)),
        m_elements(std::move(right.m_elements)),
        m_elementsEnd(std::move(right.m_elementsEnd)),
        m_capacityEnd(std::move(right.m_capacityEnd))
    {
        right.m_elements = nullptr;
        right.m_elementsEnd = nullptr;
        right.m_capacityEnd = nullptr;
    }
#endif

    ~simple_vector()
    {
        free();
    }

    simple_vector& operator =(const simple_vector &right)
    {
        if (&right != this)
            assign_disj(right.begin(), right.end());
        return *this;
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    simple_vector& operator =(simple_vector &&right)
    {
        if (&right != this)
        {
            free();

            m_elements = std::move(right.m_elements);
            m_elementsEnd = std::move(right.m_elementsEnd);
            m_capacityEnd = std::move(right.m_capacityEnd);

            right.m_elements = nullptr;
            right.m_elementsEnd = nullptr;
            right.m_capacityEnd = nullptr;

            m_allocator = std::move(right.m_allocator);
        }
        return *this;
    }
#endif

    template <class Iterator>
    void assign(Iterator source, Iterator sourceEnd)
    {
        LEAN_ASSERT(source <= sourceEnd);

        Element *sourceElements = const_cast<Element*>( lean::addressof(*source) );

        // Index is unsigned, make use of wrap-around
        if (static_cast<size_type>(sourceElements - m_elements) < size())
        {
            Element *sourceElementsEnd = const_cast<Element*>( lean::addressof(*sourceEnd) );
            LEAN_ASSERT(sourceElementsEnd <= m_elementsEnd);

            // Move (always back to front)
            LEAN_ASSERT(m_elements <= sourceElements);
            move(sourceElements, sourceElementsEnd, m_elements);

            Element *oldElementsEnd = m_elementsEnd;
            m_elementsEnd = m_elements + (sourceElementsEnd - sourceElements);
            destruct(m_elementsEnd, oldElementsEnd);
        }
        else
            assign_disj(source, sourceEnd);
    }
    template <class Iterator>
    void assign_disj(Iterator source, Iterator sourceEnd)
    {
        // Clear before reallocation to prevent full-range moves
        clear();

        size_type count = sourceEnd - source;

        if (count > capacity())
            growToHL(count);

        copy_construct(source, sourceEnd, m_elements);
        m_elementsEnd = m_elements + count;
    }

    LEAN_INLINE reference push_back()
    {
        if (m_elementsEnd == m_capacityEnd)
            growHL(1);

        default_construct(m_elementsEnd);
        return *(m_elementsEnd++);
    }
    LEAN_INLINE void push_back(const value_type &value)
    {
        if (m_elementsEnd == m_capacityEnd)
            grow_and_pushHL(value);
        else
        {
            copy_construct(m_elementsEnd, value);
            ++m_elementsEnd;
        }
    }
#ifndef LEAN0X_NO_RVALUE_REFERENCES

    LEAN_INLINE void push_back(value_type &&value)
    {
        if (m_elementsEnd == m_capacityEnd)
            grow_and_pushHL(std::move(value));
        else
        {
            move_construct(m_elementsEnd, value);
            ++m_elementsEnd;
        }
    }
#endif

    LEAN_INLINE void pop_back()
    {
        LEAN_ASSERT(!empty());

        destruct(m_elementsEnd--);
    }

    LEAN_INLINE void clear()
    {
        Element *oldElementsEnd = m_elementsEnd;
        m_elementsEnd = m_elements;
        destruct(m_elements, oldElementsEnd);
    }

    LEAN_INLINE void reserve(size_type newCapacity)
    {
        // Mind overflow
        check_length(newCapacity);

        if (newCapacity > capacity())
            reallocate(newCapacity);
    }
    void resize(size_type newCount)
    {
        // Mind overflow
        check_length(newCount);

        if (newCount > size())
        {
            if (newCount > capacity())
                growToHL(newCount);
            
            Element *newElementsEnd = m_elements + newCount;
            default_construct(m_elementsEnd, newElementsEnd);
            m_elementsEnd = newElementsEnd;
        }
        else
        {
            Element *oldElementsEnd = m_elementsEnd;
            m_elementsEnd = m_elements + newCount;
            destruct(m_elementsEnd, oldElementsEnd);
        }
    }
    
    LEAN_INLINE reference at(size_type pos) { check_pos(pos); return m_elements[pos]; };
    LEAN_INLINE const_reference at(size_type pos) const { check_pos(pos); return m_elements[pos]; };
    LEAN_INLINE reference front(void) { LEAN_ASSERT(!empty()); return *m_elements; };
    LEAN_INLINE const_reference front(void) const { LEAN_ASSERT(!empty()); return *m_elements; };
    LEAN_INLINE reference back(void) { LEAN_ASSERT(!empty()); return m_elementsEnd[-1]; };
    LEAN_INLINE const_reference back(void) const { LEAN_ASSERT(!empty()); return m_elementsEnd[-1]; };

    LEAN_INLINE reference operator [](size_type pos) { return m_elements[pos]; };
    LEAN_INLINE const_reference operator [](size_type pos) const { return m_elements[pos]; };

    LEAN_INLINE iterator begin(void) { return m_elements; };
    LEAN_INLINE const_iterator begin(void) const { return m_elements; };
    LEAN_INLINE iterator end(void) { return m_elementsEnd; };
    LEAN_INLINE const_iterator end(void) const { return m_elementsEnd; };

    LEAN_INLINE allocator_type get_allocator() const { return m_allocator; };

    LEAN_INLINE bool empty(void) const { return (m_elements == m_elementsEnd); };
    LEAN_INLINE size_type size(void) const { return m_elementsEnd - m_elements; };
    LEAN_INLINE size_type capacity(void) const { return m_capacityEnd - m_elements; };

    size_type next_capacity_hint(size_type count) const
    {
        size_type capacity = this->capacity();
        LEAN_ASSERT(capacity <= s_maxSize);
        size_type capacityDelta = capacity / 2;

        // Try to increase capacity by 1.5 (mind overflow)
        capacity = (s_maxSize - capacityDelta < capacity)
            ? s_maxSize
            : capacity + capacityDelta;

        if (capacity < count)
            capacity = count;

        if (capacity < s_minSize)
            capacity = s_minSize;
        
        return capacity;
    }

    LEAN_INLINE size_type max_size() const
    {
        return s_maxSize;
    }

    LEAN_INLINE void swap(simple_vector &right) throw()
    {
        using std::swap;

        swap(m_allocator, right.m_allocator);
        swap(m_elements, right.m_elements);
        swap(m_elementsEnd, right.m_elementsEnd);
        swap(m_capacityEnd, right.m_capacityEnd);
    }
};

template <class Element, class Policy, class Allocator>
LEAN_INLINE void swap(simple_vector<Element, Policy, Allocator> &left, simple_vector<Element, Policy, Allocator> &right)
{
    left.swap(right);
}

} // namespace

namespace simple_vector_policies = containers::simple_vector_policies;
using containers::simple_vector;

} // namespace

#endif