pod_vector.h

Go to the documentation of this file.

// 
// Copyright (c) 2006-2010, Benjamin Kaufmann
// 
// This file is part of Clasp. See http://www.cs.uni-potsdam.de/clasp/ 
// 
// Clasp is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// 
// Clasp is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with Clasp; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
//
#ifndef BK_LIB_POD_VECTOR_H_INCLUDED
#define BK_LIB_POD_VECTOR_H_INCLUDED
#include "type_manip.h"
#include <iterator>
#include <memory>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <stdexcept>
namespace bk_lib { namespace detail {
        template <class T>
        void fill(T* first, T* last, const T& x) {
                assert(first <= last);
                switch ((last - first) & 7u)
                {
                case 0:
                                while (first != last)
                                {
                                new(first++) T(x);
                case 7: new(first++) T(x);
                case 6: new(first++) T(x);
                case 5: new(first++) T(x);
                case 4: new(first++) T(x);
                case 3: new(first++) T(x);
                case 2: new(first++) T(x);
                case 1: new(first++) T(x);
                                assert(first <= last);
                                }
                }
        }
        template <class Iter, class T>
        void copy(Iter first, Iter last, std::size_t s, T* out) {
                switch (s & 7u)
                {
                case 0:
                                while (first != last)
                                {
                                new(out++) T(*first++);
                case 7: new(out++) T(*first++);
                case 6: new(out++) T(*first++);
                case 5: new(out++) T(*first++);
                case 4: new(out++) T(*first++);
                case 3: new(out++) T(*first++);
                case 2: new(out++) T(*first++);
                case 1: new(out++) T(*first++);
                                }
                }
        }
        template <class T>
        struct Fill {
                Fill(const T& val) : val_(val) {}
                void operator()(T* first, std::size_t n) const { detail::fill(first, first + n, val_); }
                const T& val_;
        private: Fill& operator=(const Fill&);
        };
        template <class Iter>
        struct Copy {
                Copy(Iter first, Iter last) : first_(first), last_(last) {}
                template <class T>
                void operator()(T* out, std::size_t n) const { detail::copy(first_, last_, n, out); }
                Iter first_;
                Iter last_;
        };
        template <class T>
        struct Memcpy {
                Memcpy(const T* first) : first_(first) {}
                void operator()(T* out, std::size_t n) const { 
                        std::memcpy(out, first_, n*sizeof(T));
                }
                const T* first_;
        };
        typedef char yes_type;
        typedef char (&no_type)[2];
        template <class T>
        struct IterType {
                static yes_type isPtr(const volatile void*);
                static no_type isPtr(...);
                static yes_type isLong(int64);
                static no_type  isLong(...);
                static T& makeT();
                enum { ptr = sizeof(isPtr(makeT())) == sizeof(yes_type) };
                enum { num = sizeof(isLong(makeT())) == sizeof(yes_type) }; 
                enum { value = ptr ? 1 : num ? 2 : 0 };
        };

} // end namespace bk_lib::detail


template <class T, class Allocator = std::allocator<T> >
class pod_vector {
public:
        // types:
        typedef          pod_vector<T,Allocator>          this_type;//not standard
        typedef          Allocator                        allocator_type;
        typedef typename Allocator::reference             reference;
        typedef typename Allocator::const_reference       const_reference;
        typedef typename Allocator::pointer               iterator;
        typedef typename Allocator::const_pointer         const_iterator;
        typedef typename Allocator::pointer               pointer;
        typedef typename Allocator::const_pointer         const_pointer;
        typedef std::reverse_iterator<iterator>           reverse_iterator;
        typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
        typedef          T                                value_type;   
        typedef typename detail::if_then_else<
                sizeof(typename Allocator::size_type)<=sizeof(unsigned int), 
                typename Allocator::size_type, 
                unsigned int>::type                           size_type;
        typedef typename detail::if_then_else<
                sizeof(typename Allocator::difference_type)<=sizeof(int), 
                typename Allocator::difference_type, 
                int>::type                                    difference_type;
        // ctors

        pod_vector() : ebo_(0, allocator_type()) { }
        

        explicit pod_vector(const allocator_type& a) : ebo_(0, a) { }


        explicit pod_vector(size_type n, const T& value = T(), const allocator_type& a = allocator_type()) 
                : ebo_(n, a) {
                detail::fill(ebo_.buf, ebo_.buf + n, value);    
                ebo_.size = n;
        }


        template <class Iter>
        pod_vector(Iter first, Iter last, const allocator_type& a = allocator_type(), typename detail::disable_if<detail::IterType<Iter>::num>::type* = 0) 
                : ebo_(0, a) {
                insert_range(end(), first, last, typename std::iterator_traits<Iter>::iterator_category());
        }
        

        pod_vector(const pod_vector& other) : ebo_(other.size(), other.get_allocator()) {
                std::memcpy(ebo_.buf, other.begin(), other.size()*sizeof(T));
                ebo_.size = other.size();
        }

        pod_vector& operator=(const pod_vector& other) {
                if (this != &other) {
                        assign(other.begin(), other.end());
                }
                return *this;
        }


        ~pod_vector() { }

        
        size_type size()     const { return ebo_.size; }
        size_type max_size() const { 
                typename allocator_type::size_type x = get_allocator().max_size();
                std::size_t                        y = size_type(-1)/sizeof(T);
                return static_cast<size_type>(std::min(std::size_t(x), y));
        }
        size_type capacity() const  { return ebo_.cap; }
        bool empty() const { return ebo_.size == 0;  }

        const_iterator begin() const { return ebo_.buf; }
        const_iterator end()   const { return ebo_.buf+ebo_.size;}
        const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
        const_reverse_iterator rend()   const { return const_reverse_iterator(begin()); }

        iterator       begin()  { return ebo_.buf; }
        iterator       end()    { return ebo_.buf+ebo_.size; }
        reverse_iterator rbegin() { return reverse_iterator(end()); }
        reverse_iterator rend()   { return reverse_iterator(begin()); }
        
        allocator_type get_allocator() const { return ebo_; }
        

        

        reference operator[](size_type n) {
                assert(n < size());
                return ebo_.buf[n];
        }
        

        const_reference operator[](size_type n) const {
                assert(n < size());
                return ebo_.buf[n];
        }
        
        const_reference at(size_type n) const {
                if (n < size()) return ebo_.buf[n];
                throw std::range_error("pod_vector::at");
        }
        reference at(size_type n) {
                if (n < size()) return ebo_.buf[n];
                throw std::range_error("pod_vector::at");
        }
        
        reference front() { assert(!empty()); return *ebo_.buf; }
        const_reference front() const { assert(!empty()); return *ebo_.buf; }
        
        reference back() { assert(!empty()); return ebo_.buf[ebo_.size-1]; }
        
        const_reference back() const { assert(!empty()); return ebo_.buf[ebo_.size-1]; }
        

        

        void clear() { ebo_.size = 0; }

        void assign(size_type n, const T& val) {
                clear();
                insert(end(), n, val);
        }
        
        template <class Iter>
        void assign(Iter first, Iter last) {
                clear();
                insert(end(), first, last);
        }
        

        iterator erase(iterator pos) {
                assert(!empty() && pos != end());
                erase(pos, pos + 1);
                return pos;
        }


        iterator erase(iterator first, iterator last) {
                if (end() - last > 0) {
                        std::memmove(first, last, (end() - last) * sizeof(T));
                }
                ebo_.size -= static_cast<size_type>(last - first);
                return first;
        }


        void resize(size_type ns, const T& val = T()) {
                if (ns > size()) {
                        ns <= capacity() ? detail::fill(end(), end()+(ns-size()), val) : append_realloc(ns-size(), val);
                }
                ebo_.size = ns;
        }


        void reserve(size_type n) {
                if (n > capacity()) {
                        T* temp = ebo_.allocate(n);
                        std::memcpy(temp, ebo_.buf, size()*sizeof(T));
                        ebo_.release();
                        ebo_.buf = temp;
                        ebo_.cap = n;
                }
        }

        void swap(pod_vector& other) {
                std::swap(ebo_.buf, other.ebo_.buf);
                std::swap(ebo_.size, other.ebo_.size);
                std::swap(ebo_.cap, other.ebo_.cap);
        }

        void push_back(const T& x) {
                if (size() < capacity()) {
                        new ((ebo_.buf+ebo_.size++)) T(x);
                }
                else {
                        append_realloc(1, x);
                }
        }
        

        void pop_back() {
                assert(!empty());
                --ebo_.size;
        }


        iterator insert(iterator pos, const T& val) {
                return insert(pos, (size_type)1, val);
        }


        iterator insert(iterator pos, size_type n, const T& val) {
                size_type off = static_cast<size_type>(pos-begin());
                insert_impl(pos, n, detail::Fill<T>(val));
                return ebo_.buf + off;
        }


        template <class Iter>
        void insert(iterator pos, Iter first, Iter last, typename detail::disable_if<detail::IterType<Iter>::num>::type* = 0) {
                insert_range(pos, first, last, typename std::iterator_traits<Iter>::iterator_category());
        }

        
        

        void resize_no_init(size_type ns) {
                reserve(ns);
                ebo_.size = ns;
        }
private:
        size_type grow_size(size_type n) {
                size_type new_cap = size() + n;
                assert(new_cap > size() && "pod_vector: max size exceeded!");
                assert(new_cap > capacity());
                if (new_cap < 4) new_cap = 1 << (new_cap+1);
                size_type x = (capacity()*3)>>1;
                if (new_cap < x) new_cap = x;
                return new_cap;
        }
        void append_realloc(size_type n, const T& x) {
                size_type new_cap = grow_size(n);
                pointer temp      = ebo_.allocate(new_cap);
                std::memcpy(temp, ebo_.buf, size()*sizeof(T));
                detail::fill(temp+size(), temp+size()+n, x);
                ebo_.release();
                ebo_.buf  = temp;
                ebo_.cap  = new_cap;
                ebo_.size+= n;
        }
        void move_right(iterator pos, size_type n) {
                assert( (pos || n == 0) && (ebo_.eos() - pos) >= (int)n);
                std::memmove(pos + n, pos, (end() - pos) * sizeof(T));
        }
        template <class It>
        void insert_range(iterator pos, It first, It last,  std::random_access_iterator_tag, 
                typename detail::disable_if<detail::same_type<pointer, It>::value == 0 && detail::same_type<const_pointer, It>::value == 0>::type* = 0) {
                assert( (first < begin() || first >= end()) && "pod_vec::insert(): Precondition violated!");
                typename allocator_type::difference_type diff = std::distance(first, last);
                assert(diff == 0 || (static_cast<size_type>(size()+diff) > size() && "pod_vector: max size exceeded!"));
                insert_impl(pos, static_cast<size_type>(diff), detail::Memcpy<T>(first));
        }
        template <class It>
        void insert_range(iterator pos, It first, It last,  std::forward_iterator_tag) {
                typename allocator_type::difference_type diff = std::distance(first, last);
                assert(diff == 0 || (static_cast<size_type>(size()+diff) > size() && "pod_vector: max size exceeded!"));
                insert_impl(pos, static_cast<size_type>(diff), detail::Copy<It>(first, last));
        }
        template <class Iter>
        void insert_range(iterator pos, Iter first, Iter last, std::input_iterator_tag) {
                pod_vector<T> temp;
                while (first != last) temp.push_back(*first++);
                insert(pos, temp.begin(), temp.end());
        }
        
        // NOTE: template parameter ST should always equal size_type
        // and is only needed to workaround an internal compiler error
        // in gcc 3.4.3
        template <class ST, class P>
        void insert_impl(iterator pos, ST n, const P& pred) {
                assert(n == 0 || (size()+n) > size() );
                if (size()+n <= capacity()) {
                        move_right(pos, n);
                        pred(pos, n);
                        ebo_.size += n;
                }
                else {
                        size_type new_cap = grow_size(n);
                        pointer temp      = ebo_.allocate(new_cap);
                        size_type prefix  = static_cast<size_type>(pos-begin());
                        // copy prefix
                        std::memcpy(temp, begin(), prefix*sizeof(T));
                        // insert new stuff
                        pred(temp+prefix, n);
                        // copy suffix
                        std::memcpy(temp+prefix+n, pos, (end()-pos)*sizeof(T));
                        ebo_.release();
                        ebo_.buf  = temp;
                        ebo_.size+= n;
                        ebo_.cap  = new_cap;
                }
        }
        struct ebo : public Allocator { // empty-base-optimization
                typedef typename this_type::size_type size_type;
                typedef typename this_type::allocator_type A;
                pointer    buf;  // pointer to array
                size_type  size; // current size (used elements)
                size_type  cap;  // max size before regrow
                ebo(size_type n, const Allocator& a) : Allocator(a), buf(0), size(0), cap(n) {
                        if (n > 0) {  buf = A::allocate(n); }
                }
                ~ebo()            { release(); }
                void release()    { if (buf) A::deallocate(buf, cap); }
                T*   eos() const  { return buf + cap; }
        }      ebo_;
};

template <class T, class A>
inline bool operator==(const pod_vector<T, A>& lhs, const pod_vector<T, A>& rhs) {
        return lhs.size() == rhs.size()
                && std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template <class T, class A>
inline bool operator!=(const pod_vector<T, A>& lhs, const pod_vector<T, A>& rhs) {
        return ! (lhs == rhs);
}

template <class T, class A>
inline bool operator<(const pod_vector<T, A>& lhs, const pod_vector<T, A>& rhs) {
        return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template <class T, class A>
inline bool operator>(const pod_vector<T, A>& lhs, const pod_vector<T, A>& rhs) {
        return rhs < lhs;
}

template <class T, class A>
inline bool operator<=(const pod_vector<T, A>& lhs, const pod_vector<T, A>& rhs) {  
        return !(rhs < lhs);
}

template <class T, class A>
inline bool operator>=(const pod_vector<T, A>& lhs, const pod_vector<T, A>& rhs) {
        return !(lhs < rhs);
}

template <class T, class A>
inline void swap(pod_vector<T, A>& lhs, pod_vector<T, A>& rhs) { 
        lhs.swap(rhs);
}

}

#endif