vector_realloc.h

/*  -*- C++ -*-
 * vector_realloc.h
 * 
 * Copyright 2018,2020 Daniel Kondor <kondor.dani@gmail.com>
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * * 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.
 * * Neither the name of the  nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 * 
 * 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.
 * 
 * 
 */

#ifndef VECTOR_REALLOC_H
#define VECTOR_REALLOC_H

#include <limits>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <stdlib.h>
#include <string.h>


/* constexpr if support only for c++17 or newer */
#if __cplusplus >= 201703L
#define CONSTEXPR constexpr
#else
#define CONSTEXPR
#endif


namespace realloc_vector {

        template<class It>
        struct at_least_forward_iterator {
            constexpr static bool value =
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::forward_iterator_tag >::value ||
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::bidirectional_iterator_tag >::value ||
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::random_access_iterator_tag >::value
#if __cplusplus >= 202000L
                || std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::contiguous_iterator_tag >::value
#endif
                ;
        };
        template<class It>
        struct at_least_input_iterator {
            constexpr static bool value = at_least_forward_iterator<It>::value || 
                std::is_same< typename std::iterator_traits<It>::iterator_category, typename std::input_iterator_tag >::value;
        };
        


template <class T>
class vector {
    protected:
        /* This requirement is too strict; what we actually want is trivially moveable,
         * i.e. a type that can be moved with memmove(), but the copy constructor could
         * be nontrivial.
         * For such types, this assertation will need to be deleted, but this might also
         * result in undefined behavior depending on the compiler */
        static_assert(std::is_trivially_copyable<T>::value,"Element type must be trivially copyable for realloc_vector::vector!\n");
    
        T* start; 
        size_t p_size; 
        size_t p_capacity; 
        size_t max_grow; 
        static constexpr size_t p_max_capacity = std::numeric_limits<size_t>::max() / sizeof(T);
        
        bool change_size(size_t new_size) {
            T* tmp = (T*)realloc(start,new_size*sizeof(T));
            if(!tmp) return false;
            start = tmp;
            p_capacity = new_size;
            return true;
        }
        bool grow_vector(size_t minimum_size = 0) {
            if(minimum_size > p_max_capacity) return false;
            size_t grow_capacity = p_capacity;
            if(!grow_capacity) grow_capacity = 1;
            if(grow_capacity > max_grow) grow_capacity = max_grow;
            if(grow_capacity > p_max_capacity) grow_capacity = p_max_capacity;
            if(p_max_capacity - grow_capacity < p_capacity) grow_capacity = p_max_capacity - p_capacity;
            if(!grow_capacity) return false;
            size_t new_size = p_capacity + grow_capacity;
            if(new_size < minimum_size) new_size = minimum_size;
            return change_size(new_size);
        }
        
        
    public:
        /* types */
        typedef T value_type;
        typedef size_t size_type;
        typedef ssize_t difference_type;
        typedef T& reference;
        typedef const T& const_reference;
        typedef T* pointer;
        typedef const T* const_pointer; 
        
        /* Constructors */
        
        vector() noexcept : start(nullptr),p_size(0),p_capacity(0),max_grow(131072) { }
        explicit vector(size_t count, const T& value = T(), size_t max_grow_ = 131072);
        template<class It, typename std::enable_if<at_least_input_iterator<It>::value, int>::type = 0>
        vector(It first, It last, size_t max_grow_ = 131072);
        vector(const vector& v);
        vector(vector&& v);
        /* 5. assignment */
        vector& operator = (const vector& v);
        vector& operator = (vector&& v);
        /* 6. swap */
        void swap(vector& v);
        
        /* Destructor */
        ~vector() {
            /* call destructors of existing elements -- these are not allowed to throw an exception! */
            if(p_size) resize(0);
            if(start) free(start);
        }
        
        
        /* Basic access to members */
        
        size_t size() const { return p_size; }
        size_t capacity() const { return p_capacity; }
        size_t max_size() const { return p_max_capacity; }
        size_t max_capacity() const { return p_max_capacity; }
        bool empty() const { return p_size == 0; }
        size_t get_max_grow() const { return max_grow; }
        void set_max_grow(size_t max_grow_) {
            if(max_grow_ == 0) max_grow = 131072;
            else max_grow = max_grow_;
        }
        
        
        /* data access functions
         * similarly to std::vector, only at() checks bounds, all other versions
         * result in undefined behavior if an out of bounds is attempted */
        T* data() { return start; }
        const T* data() const { return start; }
        
        T& operator[](size_t i) { return start[i]; }
        const T& operator[](size_t i) const { return start[i]; }
        T& at(size_t i) { if(i < p_size) return start[i]; throw std::out_of_range("vector::at(): index out of range!\n"); }
        const T& at(size_t i) const { if(i < p_size) return start[i]; throw std::out_of_range("vector::at(): index out of range!\n"); }
        T& front() { return start[0]; }
        const T& front() const { return start[0]; }
        T& back() { return start[p_size - 1]; }
        const T& back() const { return start[p_size - 1]; }
        
        /* reserve memory */
        bool reserve_nothrow(size_t n);
        void reserve(size_t n) { if(!reserve_nothrow(n)) throw std::bad_alloc(); }
        void shrink_to_fit(size_t new_capacity = 0);
        
        /* insert /create elements at the end of the vector
         * versions that throw an exception if out of memory */
        void push_back(const T& x);
        void push_back(T&& x);
        template<class... Args> T& emplace_back(Args&&... args);
        /* versions that return false if out of memory -- note: any exceptions
         * from T's (copy / move) constructor are propagated, i.e. still can
         * throw an exception if those throw */
        bool push_back_nothrow(const T& x);
        bool push_back_nothrow(T&& x);
        template<class... Args> bool emplace_back_nothrow(Args&&... args);
        
        /* remove elements -- T's destructor should not throw exception! */
        void clear() { while(p_size) start[--p_size].~T(); }
        void pop_back() { if(p_size) start[--p_size].~T(); }
        
        bool resize_nothrow(size_t count);
        bool resize_nothrow(size_t count, const T& x);
        void resize(size_t count) { if(!resize_nothrow(count)) throw std::bad_alloc(); }
        void resize(size_t count, const T& x) { if(!resize_nothrow(count,x)) throw std::bad_alloc(); }
        
        typedef T* iterator;
        typedef const T* const_iterator;
        
    protected:
        bool insert_helper(size_t pos, size_t new_pos);
    
    public:
        iterator begin() { return iterator(start); } 
        const_iterator begin() const { return const_iterator(start); } 
        const_iterator cbegin() const { return const_iterator(start); } 
        iterator end() { return iterator(start + p_size); } 
        const_iterator end() const { return const_iterator(start + p_size); } 
        const_iterator cend() const { return const_iterator(start + p_size); } 
        
        iterator erase(const_iterator pos); 
        iterator erase(const_iterator first, const_iterator last); 
        
        /* inserts that do not throw exception when out of memory,
         * instead they return whether the insert was successful
         * the res iterator is updated to point to the inserted element
         * if the insert is successful, otherwise it is not changed */
         
        bool insert_nothrow(const_iterator pos, iterator& res, const T& x);
        bool insert_nothrow(const_iterator pos, iterator& res, T&& x);
        bool insert_nothrow(const_iterator pos, iterator& res, size_t count, const T& x);
        template<class InputIt, typename std::enable_if<at_least_input_iterator<InputIt>::value, int>::type = 0>
        bool insert_nothrow(const_iterator pos, iterator& res, InputIt first, InputIt last);

        iterator insert(const_iterator pos, const T& x) {
            iterator res;
            if(insert_nothrow(pos,res,x)) return res;
            else throw std::bad_alloc();
        }
        iterator insert(const_iterator pos, T&& x) {
            iterator res;
            if(insert_nothrow(pos,res,std::forward<T>(x))) return res;
            else throw std::bad_alloc();
        }
        iterator insert(const_iterator pos, size_t count, const T& x) {
            iterator res;
            if(insert_nothrow(pos,res,count,x)) return res;
            else throw std::bad_alloc();
        }
        template<class InputIt, typename std::enable_if<at_least_input_iterator<InputIt>::value, int>::type = 0>
        iterator insert(const_iterator pos, InputIt first, InputIt last) {
            iterator res;
            if(insert_nothrow(pos,res,first,last)) return res;
            else throw std::bad_alloc();
        }
};




/* Constructors */
template<class T>
vector<T>::vector(size_t count, const T& value, size_t max_grow_) :
        start(nullptr),p_size(0),p_capacity(0),max_grow(max_grow_) {
    reserve(count);
    if CONSTEXPR(std::is_nothrow_constructible<T>::value) {
        p_size = count;
        for(size_t i = 0; i<count; i++) new(start + i) T(value);
    }
    else for(;p_size < count; ++p_size) new(start + p_size) T(value);
}

template<class T> template<class It, typename std::enable_if< at_least_input_iterator<It>::value, int>::type >
vector<T>::vector(It first, It last, size_t max_grow_) :
        start(nullptr),p_size(0),p_capacity(0),max_grow(max_grow_) {
    for(; first != last; ++first) push_back(*first);
}

template<class T>
vector<T>::vector(const vector<T>& v) : start(nullptr), p_size(0), p_capacity(0), max_grow(v.max_grow) {
    reserve(v.size());
    memcpy(start, v.start, sizeof(T)*(v.size()));
    p_size = v.size();
}

template<class T>
void vector<T>::swap(vector<T>& v) {
    using std::swap;
    swap(start, v.start);
    swap(p_size, v.p_size);
    swap(p_capacity, v.p_capacity);
    swap(max_grow, v.max_grow);
}

template<class T>
vector<T>::vector(vector<T>&& v) : start(nullptr), p_size(0), p_capacity(0), max_grow(v.max_grow) {
    swap(v);
}

template<class T>
vector<T>& vector<T>::operator = (const vector<T>& v) {
    resize(0);
    reserve(v.size());
    memcpy(start, v.start, sizeof(T)*(v.size()));
    p_size = v.size();
    return *this;
}

template<class T>
vector<T>& vector<T>::operator = (vector<T>&& v) {
    resize(0);
    if(start) free(start);
    start = nullptr;
    swap(v);
}

template<class T>
bool vector<T>::reserve_nothrow(size_t n) {
    if(n > p_max_capacity) return false;
    if(n <= p_capacity) return true;
    return change_size(n);
}

template<class T>
void vector<T>::shrink_to_fit(size_t new_capacity) {
    if(new_capacity < p_size) new_capacity = p_size;
    if(new_capacity > p_capacity) return;
    if(!change_size(new_capacity)) throw std::bad_alloc(); /* this should not happen, shrinking memory should always succeed */
}



/* insert /create elements at the end of the vector */
template<class T>
void vector<T>::push_back(const T& x) {
    if(!push_back_nothrow(x)) throw std::bad_alloc();
}
template<class T>
void vector<T>::push_back(T&& x) {
    if(!push_back_nothrow(std::forward<T>(x))) throw std::bad_alloc();
}
template<class T> template<class... Args>
T& vector<T>::emplace_back(Args&&... args) {
    if(!emplace_back_nothrow(std::forward<Args>(args)...)) throw std::bad_alloc();
    return back();
}
template<class T>
bool vector<T>::push_back_nothrow(const T& x) {
    if(p_size == p_capacity) if(!grow_vector()) return false;
    new(start + p_size) T(x); /* copy constructor -- might still throw an exception */
    p_size++;
    return true;
}
template<class T>
bool vector<T>::push_back_nothrow(T&& x) {
    if(p_size == p_capacity) if(!grow_vector()) return false;
    new(start + p_size) T(std::forward<T>(x)); /* move constructor -- might throw an exception */
    p_size++;
    return true;
}
template<class T> template<class... Args>
bool vector<T>::emplace_back_nothrow(Args&&... args) {
    if(p_size == p_capacity) if(!grow_vector()) return false;
    new(start + p_size) T(std::forward<Args>(args)...); /* constructor -- might throw an exception */
    p_size++;
    return true;
}



template<class T>
bool vector<T>::resize_nothrow(size_t count) {
    if(count == p_size) return true;
    if(!count) { clear(); return true; }
    if(count < p_size) {
        do { pop_back(); } while(p_size > count);
        return true;
    }
    /* here count > p_size */
    if(count > p_capacity) if(!grow_vector(count)) return false;
    if CONSTEXPR(std::is_nothrow_constructible<T>::value) {
        for(size_t i = p_size; i<count; i++) new(start + i) T();
        p_size = count;
    }
    else for(; p_size < count; p_size++) new(start + p_size) T();
    return true;
}
template<class T>
bool vector<T>::resize_nothrow(size_t count, const T& x) {
    if(count == p_size) return true;
    if(!count) { clear(); return true; }
    if(count < p_size) {
        do { pop_back(); } while(p_size > count);
        return true;
    }
    /* here count > p_size */
    if(count > p_capacity) if(!grow_vector(count)) return false;
    if CONSTEXPR(std::is_nothrow_copy_constructible<T>::value) {
        for(size_t i = p_size; i<count; i++) new(start + i) T(x);
        p_size = count;
    }
    else for(; p_size < count; p_size++) new(start + p_size) T(x);
    return true;
}


template<class T>
typename vector<T>::iterator vector<T>::erase(vector<T>::const_iterator pos) {
    size_t p2 = pos - start;
    if(p2 >= p_size) throw std::out_of_range("vector::erase(): iterator out of bounds!\n");
    
    size_t remaining = (p_size - p2) - 1;
    start[p2].~T();
    if(remaining) memmove(start + p2, start + p2 + 1, remaining*sizeof(T));
    p_size--;
    return iterator(start + p2);
}
template<class T>
typename vector<T>::iterator vector<T>::erase(vector<T>::const_iterator first, vector<T>::const_iterator last) {
    ssize_t dist = last - first;
    if(!dist) return iterator(first);
    
    size_t p2 = first.data - start;
    size_t p3 = last.data - start;
    if(p2 >= p_size || p3 > p_size) throw std::out_of_range("vector::erase(): iterator out of bounds!\n");
    for(size_t i = p2; i < p3; i++) start[i].~T();
    
    size_t remaining = (p_size - p3) - 1;
    if(remaining) memmove(start + p2, start + p3, remaining*sizeof(T));
    p_size -= (p3 - p2);
    return iterator(start + p2);
}
        


/* move elements to new position from given position */
template<class T>
bool vector<T>::insert_helper(size_t pos, size_t new_pos) {
    if(new_pos > pos) {
        size_t diff = new_pos - pos;
        if(p_size > p_max_capacity - diff || !reserve_nothrow(p_size + diff)) return false;
    }
    size_t remaining = p_size - pos;
    memmove(start + new_pos, start + pos, remaining*sizeof(T));
    return true;
}



template<class T>
bool vector<T>::insert_nothrow(vector<T>::const_iterator pos, vector<T>::iterator& res, const T& x) {
    if(pos == cend()) return push_back_nothrow(x);
    size_t p2 = pos - start;
    if(!insert_helper(p2,p2+1)) return false;
    if CONSTEXPR(std::is_nothrow_copy_constructible<T>::value) new(start + p2) T(x);
    else {
        /* provide fallback if copy throws -- note: this is not possible for trivially
         * copyable types, but this vector class will work if type is trivially moveable
         * only that is a weaker criterion, but is not provided by the type_traits library */
        try { new(start + p2) T(x); }
        catch(...) {
            insert_helper(p2+1,p2);
            throw;
        }
    }
    p_size++;
    res = vector<T>::iterator(start + p2);
    return true;
}

template<class T>
bool vector<T>::insert_nothrow(vector<T>::const_iterator pos, vector<T>::iterator& res, T&& x) {
    if(pos == cend()) return push_back_nothrow(std::forward<T>(x));
    size_t p2 = pos - start;
    if(!insert_helper(p2,p2+1)) return false;
    /* note: move constructor of T should never throw an exception */
    new(start + p2) T(std::forward<T>(x));
    p_size++;
    res = vector<T>::iterator(start + p2);
    return true;
}


template<class T>
bool vector<T>::insert_nothrow(vector<T>::const_iterator pos, vector<T>::iterator& res, size_t count, const T& x) {
    size_t p2 = pos - start;
    if(pos == cend()) {
        if(!resize_nothrow(p_size + count, x)) return false;
        res = vector<T>::iterator(start + p2);
        return true;
    }
    
    if(!insert_helper(p2,p2+count)) return false;
    if CONSTEXPR(std::is_nothrow_copy_constructible<T>::value) for(size_t i = 0; i < count; i++) new(start + p2 + i) T(x);
    else {
        /* provide fallback if copy throws -- note: this is not possible for trivially
         * copyable types, but this vector class will work if type is trivially moveable
         * only that is a weaker criterion, but is not provided by the type_traits library */
        size_t i = 0;
        try {
            for(; i < count; i++) new(start + p2 + i) T(x);
        }
        catch(...) {
            /* ensure that in the case of an exception, this class
             * is left in a well-defined state */
            while(i) {
                i--;
                start[p2 + i].~T();
            }
            insert_helper(p2+count,p2);
            throw;
        }
    }
    p_size += count;
    res = vector<T>::iterator(start + p2);
    return true;
}


template<class T> template<class InputIt,
    typename std::enable_if<at_least_input_iterator<InputIt>::value, int>::type >
bool vector<T>::insert_nothrow(vector<T>::const_iterator pos, vector<T>::iterator& res, InputIt first, InputIt last) {
    size_t p2 = pos - start;
    if(first != last) {
        if CONSTEXPR(at_least_forward_iterator<InputIt>::value) {
            ssize_t dist = std::distance(first,last);
            if(dist < 0) return false;
            
            if(pos == cend()) {
                if(!reserve_nothrow(p_size + dist)) return false;
                for(; first != last; ++first) push_back(*first);
                res = vector<T>::iterator(start + p2);
                return true;
            }
            
            if(!insert_helper(p2,p2+dist)) return false;
            if CONSTEXPR(std::is_nothrow_copy_constructible<T>::value) {
                size_t p3 = p2;
                for(; first != last; ++first, p3++) new(start + p3) T(*first);
            }
            else {
                /* provide fallback if copy throws -- note: this is not possible for trivially
                 * copyable types, but this vector class will work if type is trivially moveable
                 * only that is a weaker criterion, but is not provided by the type_traits library */
                size_t p3 = p2;
                try {
                    for(; first != last; ++first, p3++) new(start + p3) T(*first);
                }
                catch(...) {
                    while(p3 > p2) {
                        p3--;
                        start[p3].~T();
                    }
                    insert_helper(p2+dist,p2);
                    throw;
                }
            }
            p_size += dist;
        }
        else {
            for(size_t p3 = p2;first != last; ++first, p3++)
                if(!insert_nothrow(vector<T>::iterator(start + p3),res,*first)) return false;
        }
    }
    res = vector<T>::iterator(start + p2);
    return true;
}



} // namespace realloc_vector

#undef CONSTEXPR

#endif