| /* Stable vector. |
| * |
| * Copyright 2008 Joaquin M Lopez Munoz. |
| * Distributed under the Boost Software License, Version 1.0. |
| * (See accompanying file LICENSE_1_0.txt or copy at |
| * http://www.boost.org/LICENSE_1_0.txt) |
| */ |
| |
| #ifndef STABLE_VECTOR_HPP_3A7EB5C0_55BF_11DD_AE16_0800200C9A66 |
| #define STABLE_VECTOR_HPP_3A7EB5C0_55BF_11DD_AE16_0800200C9A66 |
| |
| #include <algorithm> |
| #include <stdexcept> |
| #include <boost/mpl/bool.hpp> |
| #include <boost/mpl/not.hpp> |
| #include <boost/noncopyable.hpp> |
| #include <boost/type_traits/is_integral.hpp> |
| #include <boost/interprocess/containers/container/detail/version_type.hpp> |
| #include <boost/interprocess/containers/container/detail/multiallocation_chain.hpp> |
| #include <boost/interprocess/containers/container/detail/utilities.hpp> |
| #include <boost/interprocess/containers/container/detail/algorithms.hpp> |
| #include <boost/pointer_to_other.hpp> |
| #include <boost/get_pointer.hpp> |
| |
| #define STABLE_VECTOR_USE_CONTAINERS_VECTOR |
| |
| #if defined (STABLE_VECTOR_USE_CONTAINERS_VECTOR) |
| #include <boost/interprocess/containers/container/vector.hpp> |
| #else |
| #include <vector> |
| #endif //STABLE_VECTOR_USE_CONTAINERS_VECTOR |
| |
| //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING |
| |
| #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) |
| #include <boost/assert.hpp> |
| #endif |
| |
| #ifdef BOOST_INTERPROCESS_DOXYGEN_INVOKED |
| namespace boost { |
| namespace interprocess { |
| #else |
| namespace boost { |
| namespace interprocess_container { |
| #endif |
| |
| /// @cond |
| |
| namespace stable_vector_detail{ |
| |
| template<class SmartPtr> |
| struct smart_ptr_type |
| { |
| typedef typename SmartPtr::value_type value_type; |
| typedef value_type *pointer; |
| static pointer get (const SmartPtr &smartptr) |
| { return smartptr.get();} |
| }; |
| |
| template<class T> |
| struct smart_ptr_type<T*> |
| { |
| typedef T value_type; |
| typedef value_type *pointer; |
| static pointer get (pointer ptr) |
| { return ptr;} |
| }; |
| |
| template<class Ptr> |
| inline typename smart_ptr_type<Ptr>::pointer get_pointer(const Ptr &ptr) |
| { return smart_ptr_type<Ptr>::get(ptr); } |
| |
| template <class C> |
| class clear_on_destroy |
| { |
| public: |
| clear_on_destroy(C &c) |
| : c_(c), do_clear_(true) |
| {} |
| |
| void release() |
| { do_clear_ = false; } |
| |
| ~clear_on_destroy() |
| { |
| if(do_clear_){ |
| c_.clear(); |
| c_.clear_pool(); |
| } |
| } |
| |
| private: |
| clear_on_destroy(const clear_on_destroy &); |
| clear_on_destroy &operator=(const clear_on_destroy &); |
| C &c_; |
| bool do_clear_; |
| }; |
| |
| template <class T, class Difference = std::ptrdiff_t> |
| class constant_iterator |
| : public std::iterator |
| <std::random_access_iterator_tag, T, Difference, const T*, const T &> |
| { |
| typedef constant_iterator<T, Difference> this_type; |
| |
| public: |
| explicit constant_iterator(const T &ref, Difference range_size) |
| : m_ptr(&ref), m_num(range_size){} |
| |
| //Constructors |
| constant_iterator() |
| : m_ptr(0), m_num(0){} |
| |
| constant_iterator& operator++() |
| { increment(); return *this; } |
| |
| constant_iterator operator++(int) |
| { |
| constant_iterator result (*this); |
| increment(); |
| return result; |
| } |
| |
| friend bool operator== (const constant_iterator& i, const constant_iterator& i2) |
| { return i.equal(i2); } |
| |
| friend bool operator!= (const constant_iterator& i, const constant_iterator& i2) |
| { return !(i == i2); } |
| |
| friend bool operator< (const constant_iterator& i, const constant_iterator& i2) |
| { return i.less(i2); } |
| |
| friend bool operator> (const constant_iterator& i, const constant_iterator& i2) |
| { return i2 < i; } |
| |
| friend bool operator<= (const constant_iterator& i, const constant_iterator& i2) |
| { return !(i > i2); } |
| |
| friend bool operator>= (const constant_iterator& i, const constant_iterator& i2) |
| { return !(i < i2); } |
| |
| friend Difference operator- (const constant_iterator& i, const constant_iterator& i2) |
| { return i2.distance_to(i); } |
| |
| //Arithmetic |
| constant_iterator& operator+=(Difference off) |
| { this->advance(off); return *this; } |
| |
| constant_iterator operator+(Difference off) const |
| { |
| constant_iterator other(*this); |
| other.advance(off); |
| return other; |
| } |
| |
| friend constant_iterator operator+(Difference off, const constant_iterator& right) |
| { return right + off; } |
| |
| constant_iterator& operator-=(Difference off) |
| { this->advance(-off); return *this; } |
| |
| constant_iterator operator-(Difference off) const |
| { return *this + (-off); } |
| |
| const T& operator*() const |
| { return dereference(); } |
| |
| const T* operator->() const |
| { return &(dereference()); } |
| |
| private: |
| const T * m_ptr; |
| Difference m_num; |
| |
| void increment() |
| { --m_num; } |
| |
| void decrement() |
| { ++m_num; } |
| |
| bool equal(const this_type &other) const |
| { return m_num == other.m_num; } |
| |
| bool less(const this_type &other) const |
| { return other.m_num < m_num; } |
| |
| const T & dereference() const |
| { return *m_ptr; } |
| |
| void advance(Difference n) |
| { m_num -= n; } |
| |
| Difference distance_to(const this_type &other)const |
| { return m_num - other.m_num; } |
| }; |
| |
| template<class VoidPtr> |
| struct node_type_base |
| {/* |
| node_type_base(VoidPtr p) |
| : up(p) |
| {}*/ |
| node_type_base() |
| {} |
| void set_pointer(VoidPtr p) |
| { up = p; } |
| |
| VoidPtr up; |
| }; |
| |
| template<typename VoidPointer, typename T> |
| struct node_type |
| : public node_type_base<VoidPointer> |
| { |
| #ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| node_type() |
| : value() |
| {} |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| node_type(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| : value(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)) \ |
| {} \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #else //#ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| node_type() |
| : value() |
| {} |
| |
| template<class ...Args> |
| node_type(Args &&...args) |
| : value(boost::interprocess::forward<Args>(args)...) |
| {} |
| #endif//#ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| void set_pointer(VoidPointer p) |
| { node_type_base<VoidPointer>::set_pointer(p); } |
| |
| T value; |
| }; |
| |
| template<typename T, typename Value, typename Pointer> |
| class iterator |
| : public std::iterator< std::random_access_iterator_tag |
| , const typename std::iterator_traits<Pointer>::value_type |
| , typename std::iterator_traits<Pointer>::difference_type |
| , Pointer |
| , Value &> |
| { |
| |
| typedef typename boost::pointer_to_other |
| <Pointer, void>::type void_ptr; |
| typedef node_type<void_ptr, T> node_type_t; |
| typedef typename boost::pointer_to_other |
| <void_ptr, node_type_t>::type node_type_ptr_t; |
| typedef typename boost::pointer_to_other |
| <void_ptr, void_ptr>::type void_ptr_ptr; |
| |
| friend class iterator<T, const T, typename boost::pointer_to_other<Pointer, T>::type>; |
| |
| public: |
| typedef std::random_access_iterator_tag iterator_category; |
| typedef Value value_type; |
| typedef typename std::iterator_traits |
| <Pointer>::difference_type difference_type; |
| typedef Pointer pointer; |
| typedef Value & reference; |
| |
| iterator() |
| {} |
| |
| explicit iterator(node_type_ptr_t pn) |
| : pn(pn) |
| {} |
| |
| iterator(const iterator<T, T, typename boost::pointer_to_other<Pointer, T>::type >& x) |
| : pn(x.pn) |
| {} |
| |
| private: |
| static node_type_ptr_t node_ptr_cast(void_ptr p) |
| { |
| using boost::get_pointer; |
| return node_type_ptr_t(static_cast<node_type_t*>(stable_vector_detail::get_pointer(p))); |
| } |
| |
| static void_ptr_ptr void_ptr_ptr_cast(void_ptr p) |
| { |
| using boost::get_pointer; |
| return void_ptr_ptr(static_cast<void_ptr*>(stable_vector_detail::get_pointer(p))); |
| } |
| |
| Value& dereference() const |
| { return pn->value; } |
| bool equal(const iterator& x) const |
| { return pn==x.pn; } |
| void increment() |
| { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+1)); } |
| void decrement() |
| { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)-1)); } |
| void advance(std::ptrdiff_t n) |
| { pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+n)); } |
| std::ptrdiff_t distance_to(const iterator& x)const |
| { return void_ptr_ptr_cast(x.pn->up) - void_ptr_ptr_cast(pn->up); } |
| |
| public: |
| //Pointer like operators |
| reference operator*() const { return this->dereference(); } |
| pointer operator->() const { return pointer(&this->dereference()); } |
| |
| //Increment / Decrement |
| iterator& operator++() |
| { this->increment(); return *this; } |
| |
| iterator operator++(int) |
| { iterator tmp(*this); ++*this; return iterator(tmp); } |
| |
| iterator& operator--() |
| { this->decrement(); return *this; } |
| |
| iterator operator--(int) |
| { iterator tmp(*this); --*this; return iterator(tmp); } |
| |
| reference operator[](difference_type off) const |
| { |
| iterator tmp(*this); |
| tmp += off; |
| return *tmp; |
| } |
| |
| iterator& operator+=(difference_type off) |
| { |
| pn = node_ptr_cast(*(void_ptr_ptr_cast(pn->up)+off)); |
| return *this; |
| } |
| |
| iterator operator+(difference_type off) const |
| { |
| iterator tmp(*this); |
| tmp += off; |
| return tmp; |
| } |
| |
| friend iterator operator+(difference_type off, const iterator& right) |
| { |
| iterator tmp(right); |
| tmp += off; |
| return tmp; |
| } |
| |
| iterator& operator-=(difference_type off) |
| { *this += -off; return *this; } |
| |
| iterator operator-(difference_type off) const |
| { |
| iterator tmp(*this); |
| tmp -= off; |
| return tmp; |
| } |
| |
| difference_type operator-(const iterator& right) const |
| { |
| void_ptr_ptr p1 = void_ptr_ptr_cast(this->pn->up); |
| void_ptr_ptr p2 = void_ptr_ptr_cast(right.pn->up); |
| return p1 - p2; |
| } |
| |
| //Comparison operators |
| bool operator== (const iterator& r) const |
| { return pn == r.pn; } |
| |
| bool operator!= (const iterator& r) const |
| { return pn != r.pn; } |
| |
| bool operator< (const iterator& r) const |
| { return void_ptr_ptr_cast(pn->up) < void_ptr_ptr_cast(r.pn->up); } |
| |
| bool operator<= (const iterator& r) const |
| { return void_ptr_ptr_cast(pn->up) <= void_ptr_ptr_cast(r.pn->up); } |
| |
| bool operator> (const iterator& r) const |
| { return void_ptr_ptr_cast(pn->up) > void_ptr_ptr_cast(r.pn->up); } |
| |
| bool operator>= (const iterator& r) const |
| { return void_ptr_ptr_cast(pn->up) >= void_ptr_ptr_cast(r.pn->up); } |
| |
| node_type_ptr_t pn; |
| }; |
| |
| /* |
| class node_access |
| { |
| public: |
| template<typename T, typename Value, typename VoidPointer> |
| static typename iterator<T, Value, VoidPointer>::node_type_t* get(const iterator<T,Value,VoidPointer>& it) |
| { |
| return stable_vector_detail::get_pointer(it.pn); |
| } |
| }; |
| */ |
| |
| template<class Allocator, unsigned int Version> |
| struct select_multiallocation_chain |
| { |
| typedef typename Allocator::multiallocation_chain type; |
| }; |
| |
| template<class Allocator> |
| struct select_multiallocation_chain<Allocator, 1> |
| { |
| typedef typename Allocator::template |
| rebind<void>::other::pointer void_ptr; |
| typedef containers_detail::basic_multiallocation_cached_slist<void_ptr> multialloc_cached; |
| typedef containers_detail::basic_multiallocation_cached_counted_slist |
| <multialloc_cached> multialloc_cached_counted; |
| typedef boost::interprocess_container::containers_detail::transform_multiallocation_chain |
| <multialloc_cached_counted, typename Allocator::value_type> type; |
| }; |
| |
| } //namespace stable_vector_detail |
| |
| #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) |
| |
| #define STABLE_VECTOR_CHECK_INVARIANT \ |
| invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \ |
| BOOST_JOIN(check_invariant_,__LINE__).touch(); |
| #else |
| |
| #define STABLE_VECTOR_CHECK_INVARIANT |
| |
| #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) |
| |
| /// @endcond |
| |
| template<typename T,typename Allocator=std::allocator<T> > |
| class stable_vector |
| { |
| typedef typename Allocator::template |
| rebind<void>::other::pointer void_ptr; |
| typedef typename Allocator::template |
| rebind<void_ptr>::other::pointer void_ptr_ptr; |
| typedef stable_vector_detail::node_type |
| <void_ptr, T> node_type_t; |
| typedef typename Allocator::template |
| rebind<node_type_t>::other::pointer node_type_ptr_t; |
| typedef stable_vector_detail::node_type_base |
| <void_ptr> node_type_base_t; |
| typedef typename Allocator::template |
| rebind<node_type_base_t>::other::pointer node_type_base_ptr_t; |
| typedef |
| #if defined (STABLE_VECTOR_USE_CONTAINERS_VECTOR) |
| ::boost::interprocess_container:: |
| #else |
| ::std:: |
| #endif //STABLE_VECTOR_USE_CONTAINERS_VECTOR |
| vector<void_ptr, |
| typename Allocator:: |
| template rebind<void_ptr>::other |
| > impl_type; |
| typedef typename impl_type::iterator impl_iterator; |
| typedef typename impl_type::const_iterator const_impl_iterator; |
| |
| typedef ::boost::interprocess_container::containers_detail:: |
| integral_constant<unsigned, 1> allocator_v1; |
| typedef ::boost::interprocess_container::containers_detail:: |
| integral_constant<unsigned, 2> allocator_v2; |
| typedef ::boost::interprocess_container::containers_detail::integral_constant |
| <unsigned, boost::interprocess_container::containers_detail:: |
| version<Allocator>::value> alloc_version; |
| typedef typename Allocator:: |
| template rebind<node_type_t>::other node_allocator_type; |
| |
| node_type_ptr_t allocate_one() |
| { return this->allocate_one(alloc_version()); } |
| |
| node_type_ptr_t allocate_one(allocator_v1) |
| { return get_al().allocate(1); } |
| |
| node_type_ptr_t allocate_one(allocator_v2) |
| { return get_al().allocate_one(); } |
| |
| void deallocate_one(node_type_ptr_t p) |
| { return this->deallocate_one(p, alloc_version()); } |
| |
| void deallocate_one(node_type_ptr_t p, allocator_v1) |
| { get_al().deallocate(p, 1); } |
| |
| void deallocate_one(node_type_ptr_t p, allocator_v2) |
| { get_al().deallocate_one(p); } |
| |
| friend class stable_vector_detail::clear_on_destroy<stable_vector>; |
| |
| public: |
| // types: |
| |
| typedef typename Allocator::reference reference; |
| typedef typename Allocator::const_reference const_reference; |
| typedef typename Allocator::pointer pointer; |
| typedef typename Allocator::const_pointer const_pointer; |
| typedef stable_vector_detail::iterator |
| <T,T, pointer> iterator; |
| typedef stable_vector_detail::iterator |
| <T,const T, const_pointer> const_iterator; |
| typedef typename impl_type::size_type size_type; |
| typedef typename iterator::difference_type difference_type; |
| typedef T value_type; |
| typedef Allocator allocator_type; |
| typedef std::reverse_iterator<iterator> reverse_iterator; |
| typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| |
| private: |
| static const size_type ExtraPointers = 3; |
| typedef typename stable_vector_detail:: |
| select_multiallocation_chain |
| < node_allocator_type |
| , alloc_version::value |
| >::type multiallocation_chain; |
| |
| public: |
| BOOST_INTERPROCESS_ENABLE_MOVE_EMULATION(stable_vector) |
| |
| // construct/copy/destroy: |
| explicit stable_vector(const Allocator& al=Allocator()) |
| : internal_data(al),impl(al) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| } |
| |
| explicit stable_vector(size_type n) |
| : internal_data(Allocator()),impl(Allocator()) |
| { |
| stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); |
| this->resize(n); |
| STABLE_VECTOR_CHECK_INVARIANT; |
| cod.release(); |
| } |
| |
| stable_vector(size_type n,const T& t=T(),const Allocator& al=Allocator()) |
| : internal_data(al),impl(al) |
| { |
| stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); |
| this->insert(this->cbegin(), n, t); |
| STABLE_VECTOR_CHECK_INVARIANT; |
| cod.release(); |
| } |
| |
| template <class InputIterator> |
| stable_vector(InputIterator first,InputIterator last,const Allocator& al=Allocator()) |
| : internal_data(al),impl(al) |
| { |
| stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); |
| this->insert(this->cbegin(), first, last); |
| STABLE_VECTOR_CHECK_INVARIANT; |
| cod.release(); |
| } |
| |
| stable_vector(const stable_vector& x) |
| : internal_data(x.get_al()),impl(x.get_al()) |
| { |
| stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); |
| this->insert(this->cbegin(), x.begin(), x.end()); |
| STABLE_VECTOR_CHECK_INVARIANT; |
| cod.release(); |
| } |
| |
| stable_vector(BOOST_INTERPROCESS_RV_REF(stable_vector) x) |
| : internal_data(x.get_al()),impl(x.get_al()) |
| { this->swap(x); } |
| |
| ~stable_vector() |
| { |
| this->clear(); |
| clear_pool(); |
| } |
| |
| stable_vector& operator=(const stable_vector &x) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| if (this != &x) { |
| this->assign(x.begin(), x.end()); |
| } |
| return *this; |
| } |
| |
| stable_vector& operator=(BOOST_INTERPROCESS_RV_REF(stable_vector) x) |
| { |
| if (&x != this){ |
| this->swap(x); |
| x.clear(); |
| } |
| return *this; |
| } |
| |
| template<typename InputIterator> |
| void assign(InputIterator first,InputIterator last) |
| { |
| assign_dispatch(first, last, boost::is_integral<InputIterator>()); |
| } |
| |
| void assign(size_type n,const T& t) |
| { |
| typedef stable_vector_detail::constant_iterator<value_type, difference_type> cvalue_iterator; |
| return assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); |
| } |
| |
| allocator_type get_allocator()const {return get_al();} |
| |
| // iterators: |
| |
| iterator begin() |
| { return (impl.empty()) ? end(): iterator(node_ptr_cast(impl.front())) ; } |
| |
| const_iterator begin()const |
| { return (impl.empty()) ? cend() : const_iterator(node_ptr_cast(impl.front())) ; } |
| |
| iterator end() {return iterator(get_end_node());} |
| const_iterator end()const {return const_iterator(get_end_node());} |
| |
| reverse_iterator rbegin() {return reverse_iterator(this->end());} |
| const_reverse_iterator rbegin()const {return const_reverse_iterator(this->end());} |
| reverse_iterator rend() {return reverse_iterator(this->begin());} |
| const_reverse_iterator rend()const {return const_reverse_iterator(this->begin());} |
| |
| const_iterator cbegin()const {return this->begin();} |
| const_iterator cend()const {return this->end();} |
| const_reverse_iterator crbegin()const{return this->rbegin();} |
| const_reverse_iterator crend()const {return this->rend();} |
| |
| // capacity: |
| size_type size() const |
| { return impl.empty() ? 0 : (impl.size() - ExtraPointers); } |
| |
| size_type max_size() const |
| { return impl.max_size() - ExtraPointers; } |
| |
| size_type capacity() const |
| { |
| if(!impl.capacity()){ |
| return 0; |
| } |
| else{ |
| const size_type num_nodes = this->impl.size() + this->internal_data.pool_size; |
| const size_type num_buck = this->impl.capacity(); |
| return (num_nodes < num_buck) ? num_nodes : num_buck; |
| } |
| } |
| |
| bool empty() const |
| { return impl.empty() || impl.size() == ExtraPointers; } |
| |
| void resize(size_type n, const T& t) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| if(n > size()) |
| this->insert(this->cend(), n - this->size(), t); |
| else if(n < this->size()) |
| this->erase(this->cbegin() + n, this->cend()); |
| } |
| |
| void resize(size_type n) |
| { |
| typedef default_construct_iterator<value_type, difference_type> default_iterator; |
| STABLE_VECTOR_CHECK_INVARIANT; |
| if(n > size()) |
| this->insert(this->cend(), default_iterator(n - this->size()), default_iterator()); |
| else if(n < this->size()) |
| this->erase(this->cbegin() + n, this->cend()); |
| } |
| |
| void reserve(size_type n) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| if(n > this->max_size()) |
| throw std::bad_alloc(); |
| |
| size_type size = this->size(); |
| size_type old_capacity = this->capacity(); |
| if(n > old_capacity){ |
| this->initialize_end_node(n); |
| const void * old_ptr = &impl[0]; |
| impl.reserve(n + ExtraPointers); |
| bool realloced = &impl[0] != old_ptr; |
| //Fix the pointers for the newly allocated buffer |
| if(realloced){ |
| this->align_nodes(impl.begin(), impl.begin()+size+1); |
| } |
| //Now fill pool if data is not enough |
| if((n - size) > this->internal_data.pool_size){ |
| this->add_to_pool((n - size) - this->internal_data.pool_size); |
| } |
| } |
| } |
| |
| void clear_pool(allocator_v1) |
| { |
| if(!impl.empty() && impl.back()){ |
| void_ptr &p1 = *(impl.end()-2); |
| void_ptr &p2 = impl.back(); |
| |
| multiallocation_chain holder(p1, p2, this->internal_data.pool_size); |
| while(!holder.empty()){ |
| node_type_ptr_t n = holder.front(); |
| holder.pop_front(); |
| this->deallocate_one(n); |
| } |
| p1 = p2 = 0; |
| this->internal_data.pool_size = 0; |
| } |
| } |
| |
| void clear_pool(allocator_v2) |
| { |
| |
| if(!impl.empty() && impl.back()){ |
| void_ptr &p1 = *(impl.end()-2); |
| void_ptr &p2 = impl.back(); |
| multiallocation_chain holder(p1, p2, this->internal_data.pool_size); |
| get_al().deallocate_individual(boost::interprocess::move(holder)); |
| p1 = p2 = 0; |
| this->internal_data.pool_size = 0; |
| } |
| } |
| |
| void clear_pool() |
| { |
| this->clear_pool(alloc_version()); |
| } |
| |
| void add_to_pool(size_type n) |
| { |
| this->add_to_pool(n, alloc_version()); |
| } |
| |
| void add_to_pool(size_type n, allocator_v1) |
| { |
| size_type remaining = n; |
| while(remaining--){ |
| this->put_in_pool(this->allocate_one()); |
| } |
| } |
| |
| void add_to_pool(size_type n, allocator_v2) |
| { |
| void_ptr &p1 = *(impl.end()-2); |
| void_ptr &p2 = impl.back(); |
| multiallocation_chain holder(p1, p2, this->internal_data.pool_size); |
| BOOST_STATIC_ASSERT((boost::interprocess::is_movable<multiallocation_chain>::value == true)); |
| multiallocation_chain m (get_al().allocate_individual(n)); |
| holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n); |
| this->internal_data.pool_size += n; |
| std::pair<void_ptr, void_ptr> data(holder.extract_data()); |
| p1 = data.first; |
| p2 = data.second; |
| } |
| |
| void put_in_pool(node_type_ptr_t p) |
| { |
| void_ptr &p1 = *(impl.end()-2); |
| void_ptr &p2 = impl.back(); |
| multiallocation_chain holder(p1, p2, internal_data.pool_size); |
| holder.push_front(p); |
| ++this->internal_data.pool_size; |
| std::pair<void_ptr, void_ptr> ret(holder.extract_data()); |
| p1 = ret.first; |
| p2 = ret.second; |
| } |
| |
| node_type_ptr_t get_from_pool() |
| { |
| if(!impl.back()){ |
| return node_type_ptr_t(0); |
| } |
| else{ |
| void_ptr &p1 = *(impl.end()-2); |
| void_ptr &p2 = impl.back(); |
| multiallocation_chain holder(p1, p2, internal_data.pool_size); |
| node_type_ptr_t ret = holder.front(); |
| holder.pop_front(); |
| std::pair<void_ptr, void_ptr> data(holder.extract_data()); |
| p1 = data.first; |
| p2 = data.second; |
| --this->internal_data.pool_size; |
| return ret; |
| } |
| } |
| |
| // element access: |
| |
| reference operator[](size_type n){return value(impl[n]);} |
| const_reference operator[](size_type n)const{return value(impl[n]);} |
| |
| const_reference at(size_type n)const |
| { |
| if(n>=size()) |
| throw std::out_of_range("invalid subscript at stable_vector::at"); |
| return operator[](n); |
| } |
| |
| reference at(size_type n) |
| { |
| if(n>=size()) |
| throw std::out_of_range("invalid subscript at stable_vector::at"); |
| return operator[](n); |
| } |
| |
| reference front() |
| { return value(impl.front()); } |
| |
| const_reference front()const |
| { return value(impl.front()); } |
| |
| reference back() |
| { return value(*(&impl.back() - ExtraPointers)); } |
| |
| const_reference back()const |
| { return value(*(&impl.back() - ExtraPointers)); } |
| |
| // modifiers: |
| |
| void push_back(const T& t) |
| { this->insert(end(), t); } |
| |
| void push_back(BOOST_INTERPROCESS_RV_REF(T) t) |
| { this->insert(end(), boost::interprocess::move(t)); } |
| |
| void pop_back() |
| { this->erase(this->end()-1); } |
| |
| iterator insert(const_iterator position, const T& t) |
| { |
| typedef stable_vector_detail::constant_iterator<value_type, difference_type> cvalue_iterator; |
| return this->insert_iter(position, cvalue_iterator(t, 1), cvalue_iterator(), std::forward_iterator_tag()); |
| } |
| |
| iterator insert(const_iterator position, BOOST_INTERPROCESS_RV_REF(T) x) |
| { |
| typedef repeat_iterator<T, difference_type> repeat_it; |
| typedef boost::interprocess::move_iterator<repeat_it> repeat_move_it; |
| //Just call more general insert(pos, size, value) and return iterator |
| size_type pos_n = position - cbegin(); |
| this->insert(position |
| ,repeat_move_it(repeat_it(x, 1)) |
| ,repeat_move_it(repeat_it())); |
| return iterator(this->begin() + pos_n); |
| } |
| |
| void insert(const_iterator position, size_type n, const T& t) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| this->insert_not_iter(position, n, t); |
| } |
| |
| template <class InputIterator> |
| void insert(const_iterator position,InputIterator first, InputIterator last) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| this->insert_iter(position,first,last, |
| boost::mpl::not_<boost::is_integral<InputIterator> >()); |
| } |
| |
| #ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| //! <b>Effects</b>: Inserts an object of type T constructed with |
| //! std::forward<Args>(args)... in the end of the vector. |
| //! |
| //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. |
| //! |
| //! <b>Complexity</b>: Amortized constant time. |
| template<class ...Args> |
| void emplace_back(Args &&...args) |
| { |
| typedef emplace_functor<node_type_t, Args...> EmplaceFunctor; |
| typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; |
| EmplaceFunctor ef(boost::interprocess::forward<Args>(args)...); |
| this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); |
| } |
| |
| //! <b>Requires</b>: position must be a valid iterator of *this. |
| //! |
| //! <b>Effects</b>: Inserts an object of type T constructed with |
| //! std::forward<Args>(args)... before position |
| //! |
| //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. |
| //! |
| //! <b>Complexity</b>: If position is end(), amortized constant time |
| //! Linear time otherwise. |
| template<class ...Args> |
| iterator emplace(const_iterator position, Args && ...args) |
| { |
| //Just call more general insert(pos, size, value) and return iterator |
| size_type pos_n = position - cbegin(); |
| typedef emplace_functor<node_type_t, Args...> EmplaceFunctor; |
| typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; |
| EmplaceFunctor ef(boost::interprocess::forward<Args>(args)...); |
| this->insert(position, EmplaceIterator(ef), EmplaceIterator()); |
| return iterator(this->begin() + pos_n); |
| } |
| |
| #else |
| |
| void emplace_back() |
| { |
| typedef emplace_functor<node_type_t> EmplaceFunctor; |
| typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; |
| EmplaceFunctor ef; |
| this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); |
| } |
| |
| iterator emplace(const_iterator position) |
| { |
| typedef emplace_functor<node_type_t> EmplaceFunctor; |
| typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; |
| EmplaceFunctor ef; |
| size_type pos_n = position - this->cbegin(); |
| this->insert(position, EmplaceIterator(ef), EmplaceIterator()); |
| return iterator(this->begin() + pos_n); |
| } |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ |
| <node_type_t, BOOST_PP_ENUM_PARAMS(n, P)> EmplaceFunctor; \ |
| typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; \ |
| EmplaceFunctor ef(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); \ |
| } \ |
| \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| iterator emplace(const_iterator pos, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ |
| <node_type_t, BOOST_PP_ENUM_PARAMS(n, P)> EmplaceFunctor; \ |
| typedef emplace_iterator<node_type_t, EmplaceFunctor> EmplaceIterator; \ |
| EmplaceFunctor ef(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| size_type pos_n = pos - this->cbegin(); \ |
| this->insert(pos, EmplaceIterator(ef), EmplaceIterator()); \ |
| return iterator(this->begin() + pos_n); \ |
| } \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| iterator erase(const_iterator position) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| difference_type d=position-this->cbegin(); |
| impl_iterator it=impl.begin()+d; |
| this->delete_node(*it); |
| impl.erase(it); |
| this->align_nodes(impl.begin()+d,get_last_align()); |
| return this->begin()+d; |
| } |
| |
| iterator erase(const_iterator first, const_iterator last) |
| { return priv_erase(first, last, alloc_version()); } |
| |
| void swap(stable_vector & x) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| this->swap_impl(*this,x); |
| } |
| |
| void clear() |
| { this->erase(this->cbegin(),this->cend()); } |
| |
| /// @cond |
| private: |
| |
| void insert_iter_prolog(size_type n, difference_type d) |
| { |
| initialize_end_node(n); |
| const void* old_ptr = &impl[0]; |
| //size_type old_capacity = capacity(); |
| //size_type old_size = size(); |
| impl.insert(impl.begin()+d, n, 0); |
| bool realloced = &impl[0] != old_ptr; |
| //Fix the pointers for the newly allocated buffer |
| if(realloced){ |
| align_nodes(impl.begin(), impl.begin()+d); |
| } |
| } |
| |
| template<typename InputIterator> |
| void assign_dispatch(InputIterator first, InputIterator last, boost::mpl::false_) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| iterator first1 = this->begin(); |
| iterator last1 = this->end(); |
| for ( ; first1 != last1 && first != last; ++first1, ++first) |
| *first1 = *first; |
| if (first == last){ |
| this->erase(first1, last1); |
| } |
| else{ |
| this->insert(last1, first, last); |
| } |
| } |
| |
| template<typename Integer> |
| void assign_dispatch(Integer n, Integer t, boost::mpl::true_) |
| { |
| typedef stable_vector_detail::constant_iterator<value_type, difference_type> cvalue_iterator; |
| this->assign_dispatch(cvalue_iterator(t, n), cvalue_iterator(), boost::mpl::false_()); |
| } |
| |
| iterator priv_erase(const_iterator first, const_iterator last, allocator_v1) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| difference_type d1 = first - this->cbegin(), d2 = last - this->cbegin(); |
| if(d1 != d2){ |
| impl_iterator it1(impl.begin() + d1), it2(impl.begin() + d2); |
| for(impl_iterator it = it1; it != it2; ++it) |
| this->delete_node(*it); |
| impl.erase(it1, it2); |
| this->align_nodes(impl.begin() + d1, get_last_align()); |
| } |
| return iterator(this->begin() + d1); |
| } |
| |
| impl_iterator get_last_align() |
| { |
| return impl.end() - (ExtraPointers - 1); |
| } |
| |
| const_impl_iterator get_last_align() const |
| { |
| return impl.cend() - (ExtraPointers - 1); |
| } |
| |
| template<class AllocatorVersion> |
| iterator priv_erase(const_iterator first, const_iterator last, AllocatorVersion, |
| typename boost::interprocess_container::containers_detail::enable_if_c |
| <boost::interprocess_container::containers_detail::is_same<AllocatorVersion, allocator_v2> |
| ::value>::type * = 0) |
| { |
| STABLE_VECTOR_CHECK_INVARIANT; |
| return priv_erase(first, last, allocator_v1()); |
| } |
| |
| static node_type_ptr_t node_ptr_cast(void_ptr p) |
| { |
| using boost::get_pointer; |
| return node_type_ptr_t(static_cast<node_type_t*>(stable_vector_detail::get_pointer(p))); |
| } |
| |
| static node_type_base_ptr_t node_base_ptr_cast(void_ptr p) |
| { |
| using boost::get_pointer; |
| return node_type_base_ptr_t(static_cast<node_type_base_t*>(stable_vector_detail::get_pointer(p))); |
| } |
| |
| static value_type& value(void_ptr p) |
| { |
| return node_ptr_cast(p)->value; |
| } |
| |
| void initialize_end_node(size_type impl_capacity = 0) |
| { |
| if(impl.empty()){ |
| impl.reserve(impl_capacity + ExtraPointers); |
| impl.resize (ExtraPointers, void_ptr(0)); |
| impl[0] = &this->internal_data.end_node; |
| this->internal_data.end_node.up = &impl[0]; |
| } |
| } |
| |
| void readjust_end_node() |
| { |
| if(!this->impl.empty()){ |
| void_ptr &end_node_ref = *(this->get_last_align()-1); |
| end_node_ref = this->get_end_node(); |
| this->internal_data.end_node.up = &end_node_ref; |
| } |
| else{ |
| this->internal_data.end_node.up = void_ptr(&this->internal_data.end_node.up); |
| } |
| } |
| |
| node_type_ptr_t get_end_node() const |
| { |
| const node_type_base_t* cp = &this->internal_data.end_node; |
| node_type_base_t* p = const_cast<node_type_base_t*>(cp); |
| return node_ptr_cast(p); |
| } |
| |
| template<class Iter> |
| void_ptr new_node(void_ptr up, Iter it) |
| { |
| node_type_ptr_t p = this->allocate_one(); |
| try{ |
| boost::interprocess_container::construct_in_place(&*p, it); |
| p->set_pointer(up); |
| } |
| catch(...){ |
| this->deallocate_one(p); |
| throw; |
| } |
| return p; |
| } |
| |
| void delete_node(void_ptr p) |
| { |
| node_type_ptr_t n(node_ptr_cast(p)); |
| n->~node_type_t(); |
| this->put_in_pool(n); |
| } |
| |
| static void align_nodes(impl_iterator first,impl_iterator last) |
| { |
| while(first!=last){ |
| node_ptr_cast(*first)->up = void_ptr(&*first); |
| ++first; |
| } |
| } |
| |
| void insert_not_iter(const_iterator position, size_type n, const T& t) |
| { |
| typedef stable_vector_detail::constant_iterator<value_type, difference_type> cvalue_iterator; |
| this->insert_iter(position, cvalue_iterator(t, n), cvalue_iterator(), std::forward_iterator_tag()); |
| } |
| |
| template <class InputIterator> |
| void insert_iter(const_iterator position,InputIterator first,InputIterator last, boost::mpl::true_) |
| { |
| typedef typename std::iterator_traits<InputIterator>::iterator_category category; |
| this->insert_iter(position, first, last, category()); |
| } |
| |
| template <class InputIterator> |
| void insert_iter(const_iterator position,InputIterator first,InputIterator last,std::input_iterator_tag) |
| { |
| for(; first!=last; ++first){ |
| this->insert(position, *first); |
| } |
| } |
| |
| template <class InputIterator> |
| iterator insert_iter(const_iterator position, InputIterator first, InputIterator last, std::forward_iterator_tag) |
| { |
| size_type n = (size_type)std::distance(first,last); |
| difference_type d = position-this->cbegin(); |
| if(n){ |
| this->insert_iter_prolog(n, d); |
| const impl_iterator it(impl.begin() + d); |
| this->insert_iter_fwd(it, first, last, n); |
| //Fix the pointers for the newly allocated buffer |
| this->align_nodes(it + n, get_last_align()); |
| } |
| return this->begin() + d; |
| } |
| |
| template <class FwdIterator> |
| void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v1) |
| { |
| size_type i=0; |
| try{ |
| while(first!=last){ |
| *(it + i) = this->new_node(void_ptr((void*)(&*(it + i))), first); |
| ++first; |
| ++i; |
| } |
| } |
| catch(...){ |
| impl.erase(it + i, it + n); |
| this->align_nodes(it + i, get_last_align()); |
| throw; |
| } |
| } |
| |
| template <class FwdIterator> |
| void insert_iter_fwd_alloc(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n, allocator_v2) |
| { |
| multiallocation_chain mem(get_al().allocate_individual(n)); |
| |
| size_type i = 0; |
| node_type_ptr_t p = 0; |
| try{ |
| while(first != last){ |
| p = mem.front(); |
| mem.pop_front(); |
| //This can throw |
| boost::interprocess_container::construct_in_place(&*p, first); |
| p->set_pointer(void_ptr((void*)(&*(it + i)))); |
| ++first; |
| *(it + i) = p; |
| ++i; |
| } |
| } |
| catch(...){ |
| get_al().deallocate_one(p); |
| get_al().deallocate_many(boost::interprocess::move(mem)); |
| impl.erase(it+i, it+n); |
| this->align_nodes(it+i,get_last_align()); |
| throw; |
| } |
| } |
| |
| template <class FwdIterator> |
| void insert_iter_fwd(const impl_iterator it, FwdIterator first, FwdIterator last, difference_type n) |
| { |
| size_type i = 0; |
| node_type_ptr_t p = 0; |
| try{ |
| while(first != last){ |
| p = get_from_pool(); |
| if(!p){ |
| insert_iter_fwd_alloc(it+i, first, last, n-i, alloc_version()); |
| break; |
| } |
| //This can throw |
| boost::interprocess_container::construct_in_place(&*p, first); |
| p->set_pointer(void_ptr(&*(it+i))); |
| ++first; |
| *(it+i)=p; |
| ++i; |
| } |
| } |
| catch(...){ |
| put_in_pool(p); |
| impl.erase(it+i,it+n); |
| this->align_nodes(it+i,get_last_align()); |
| throw; |
| } |
| } |
| |
| template <class InputIterator> |
| void insert_iter(const_iterator position,InputIterator first,InputIterator last, boost::mpl::false_) |
| { |
| this->insert_not_iter(position,first,last); |
| } |
| |
| static void swap_impl(stable_vector& x,stable_vector& y) |
| { |
| using std::swap; |
| swap(x.get_al(),y.get_al()); |
| swap(x.impl,y.impl); |
| swap(x.internal_data.pool_size, y.internal_data.pool_size); |
| x.readjust_end_node(); |
| y.readjust_end_node(); |
| } |
| |
| #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) |
| bool invariant()const |
| { |
| if(impl.empty()) |
| return !capacity() && !size(); |
| if(get_end_node() != *(impl.end() - ExtraPointers)){ |
| return false; |
| } |
| for(const_impl_iterator it=impl.begin(),it_end=get_last_align();it!=it_end;++it){ |
| if(node_ptr_cast(*it)->up != &*it) |
| return false; |
| } |
| size_type n = capacity()-size(); |
| const void_ptr &pool_head = impl.back(); |
| size_type num_pool = 0; |
| node_type_ptr_t p = node_ptr_cast(pool_head); |
| while(p){ |
| ++num_pool; |
| p = p->up; |
| } |
| return n >= num_pool; |
| } |
| |
| class invariant_checker:private boost::noncopyable |
| { |
| const stable_vector* p; |
| public: |
| invariant_checker(const stable_vector& v):p(&v){} |
| ~invariant_checker(){BOOST_ASSERT(p->invariant());} |
| void touch(){} |
| }; |
| #endif |
| |
| struct ebo_holder |
| : node_allocator_type |
| { |
| ebo_holder(const allocator_type &a) |
| : node_allocator_type(a), pool_size(0), end_node() |
| { |
| end_node.set_pointer(void_ptr(&end_node.up)); |
| } |
| size_type pool_size; |
| node_type_base_t end_node; |
| } internal_data; |
| |
| node_allocator_type &get_al() { return internal_data; } |
| const node_allocator_type &get_al() const { return internal_data; } |
| |
| impl_type impl; |
| /// @endcond |
| }; |
| |
| template <typename T,typename Allocator> |
| bool operator==(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) |
| { |
| return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); |
| } |
| |
| template <typename T,typename Allocator> |
| bool operator< (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) |
| { |
| return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); |
| } |
| |
| template <typename T,typename Allocator> |
| bool operator!=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) |
| { |
| return !(x==y); |
| } |
| |
| template <typename T,typename Allocator> |
| bool operator> (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) |
| { |
| return y<x; |
| } |
| |
| template <typename T,typename Allocator> |
| bool operator>=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) |
| { |
| return !(x<y); |
| } |
| |
| template <typename T,typename Allocator> |
| bool operator<=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y) |
| { |
| return !(x>y); |
| } |
| |
| // specialized algorithms: |
| |
| template <typename T, typename Allocator> |
| void swap(stable_vector<T,Allocator>& x,stable_vector<T,Allocator>& y) |
| { |
| x.swap(y); |
| } |
| |
| /// @cond |
| |
| #undef STABLE_VECTOR_CHECK_INVARIANT |
| |
| /// @endcond |
| |
| }} |
| |
| #endif |