diff options
Diffstat (limited to 'boost/poly_collection/detail/split_segment.hpp')
-rw-r--r-- | boost/poly_collection/detail/split_segment.hpp | 487 |
1 files changed, 487 insertions, 0 deletions
diff --git a/boost/poly_collection/detail/split_segment.hpp b/boost/poly_collection/detail/split_segment.hpp new file mode 100644 index 0000000000..5fc9e11e20 --- /dev/null +++ b/boost/poly_collection/detail/split_segment.hpp @@ -0,0 +1,487 @@ +/* Copyright 2016-2017 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) + * + * See http://www.boost.org/libs/poly_collection for library home page. + */ + +#ifndef BOOST_POLY_COLLECTION_DETAIL_SPLIT_SEGMENT_HPP +#define BOOST_POLY_COLLECTION_DETAIL_SPLIT_SEGMENT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/newdelete_allocator.hpp> +#include <boost/poly_collection/detail/segment_backend.hpp> +#include <boost/poly_collection/detail/value_holder.hpp> +#include <iterator> +#include <memory> +#include <new> +#include <utility> +#include <vector> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* segment_backend implementation that maintains two internal vectors, one for + * value_type's (the index) and another for the concrete elements those refer + * to (the store). + * + * Requires: + * - [const_]base_iterator is constructible from value_type*. + * - value_type is copy constructible. + * - Model::make_value_type(x) returns a value_type created from a reference + * to the concrete type. + * + * Conversion from base_iterator to local_iterator<Concrete> requires accesing + * value_type internal info, so the end() base_iterator has to be made to point + * to a valid element of index, which implies size(index)=size(store)+1. This + * slightly complicates the memory management. + */ + +template<typename Model,typename Concrete,typename Allocator> +class split_segment:public segment_backend<Model> +{ + using value_type=typename Model::value_type; + using store_value_type=value_holder<Concrete>; + using store=std::vector< + store_value_type, + value_holder_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<store_value_type> + > + >; + using store_iterator=typename store::iterator; + using const_store_iterator=typename store::const_iterator; + using index=std::vector< + value_type, + newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<value_type> + > + >; + using const_index_iterator=typename index::const_iterator; + using segment_backend=detail::segment_backend<Model>; + using typename segment_backend::segment_backend_unique_ptr; + using typename segment_backend::value_pointer; + using typename segment_backend::const_value_pointer; + using typename segment_backend::base_iterator; + using typename segment_backend::const_base_iterator; + using const_iterator= + typename segment_backend::template const_iterator<Concrete>; + using typename segment_backend::base_sentinel; + using typename segment_backend::range; + using segment_allocator_type=newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<split_segment> + >; + +public: + virtual ~split_segment()=default; + + virtual segment_backend_unique_ptr copy()const + { + return new_(s.get_allocator(),store{s}); + } + + virtual segment_backend_unique_ptr empty_copy()const + { + return new_(s.get_allocator(),s.get_allocator()); + } + + virtual bool equal(const segment_backend& x)const + { + return s==static_cast<const split_segment&>(x).s; + } + + virtual base_iterator begin()const noexcept{return nv_begin();} + base_iterator nv_begin()const noexcept + {return base_iterator{value_ptr(i.data())};} + virtual base_iterator end()const noexcept{return nv_end();} + base_iterator nv_end()const noexcept + {return base_iterator{value_ptr(i.data()+s.size())};} + virtual bool empty()const noexcept{return nv_empty();} + bool nv_empty()const noexcept{return s.empty();} + virtual std::size_t size()const noexcept{return nv_size();} + std::size_t nv_size()const noexcept{return s.size();} + virtual std::size_t max_size()const noexcept{return nv_max_size();} + std::size_t nv_max_size()const noexcept{return s.max_size()-1;} + virtual std::size_t capacity()const noexcept{return nv_capacity();} + std::size_t nv_capacity()const noexcept{return s.capacity();} + + virtual base_sentinel reserve(std::size_t n){return nv_reserve(n);} + + base_sentinel nv_reserve(std::size_t n) + { + bool rebuild=n>s.capacity(); + i.reserve(n+1); + s.reserve(n); + if(rebuild)rebuild_index(); + return sentinel(); + }; + + virtual base_sentinel shrink_to_fit(){return nv_shrink_to_fit();} + + base_sentinel nv_shrink_to_fit() + { + auto p=s.data(); + s.shrink_to_fit(); + if(p!=s.data())try{ + index ii{{},i.get_allocator()}; + ii.reserve(s.capacity()+1); + i.swap(ii); + build_index(); + } + catch(...){ + rebuild_index(); + throw; + } + return sentinel(); + } + + template<typename Iterator,typename... Args> + range nv_emplace(Iterator p,Args&&... args) + { + auto q=prereserve(p); + auto it=s.emplace( + iterator_from(q), + value_holder_emplacing_ctor,std::forward<Args>(args)...); + push_index_entry(); + return range_from(it); + } + + template<typename... Args> + range nv_emplace_back(Args&&... args) + { + prereserve(); + s.emplace_back(value_holder_emplacing_ctor,std::forward<Args>(args)...); + push_index_entry(); + return range_from(s.size()-1); + } + + virtual range push_back(const_value_pointer x) + {return nv_push_back(const_concrete_ref(x));} + + range nv_push_back(const Concrete& x) + { + prereserve(); + s.emplace_back(x); + push_index_entry(); + return range_from(s.size()-1); + } + + virtual range push_back_move(value_pointer x) + {return nv_push_back(std::move(concrete_ref(x)));} + + range nv_push_back(Concrete&& x) + { + prereserve(); + s.emplace_back(std::move(x)); + push_index_entry(); + return range_from(s.size()-1); + } + + virtual range insert(const_base_iterator p,const_value_pointer x) + {return nv_insert(const_iterator(p),const_concrete_ref(x));} + + range nv_insert(const_iterator p,const Concrete& x) + { + p=prereserve(p); + auto it=s.emplace(iterator_from(p),x); + push_index_entry(); + return range_from(it); + } + + virtual range insert_move(const_base_iterator p,value_pointer x) + {return nv_insert(const_iterator(p),std::move(concrete_ref(x)));} + + range nv_insert(const_iterator p,Concrete&& x) + { + p=prereserve(p); + auto it=s.emplace(iterator_from(p),std::move(x)); + push_index_entry(); + return range_from(it); + } + + template<typename InputIterator> + range nv_insert(InputIterator first,InputIterator last) + { + return nv_insert( + const_iterator(concrete_ptr(s.data()+s.size())),first,last); + } + + template<typename InputIterator> + range nv_insert(const_iterator p,InputIterator first,InputIterator last) + { + return insert( + p,first,last, + typename std::iterator_traits<InputIterator>::iterator_category{}); + } + + virtual range erase(const_base_iterator p) + {return nv_erase(const_iterator(p));} + + range nv_erase(const_iterator p) + { + pop_index_entry(); + return range_from(s.erase(iterator_from(p))); + } + + virtual range erase(const_base_iterator first,const_base_iterator last) + {return nv_erase(const_iterator(first),const_iterator(last));} + + range nv_erase(const_iterator first,const_iterator last) + { + std::size_t n=s.size(); + auto it=s.erase(iterator_from(first),iterator_from(last)); + pop_index_entry(n-s.size()); + return range_from(it); + } + + virtual range erase_till_end(const_base_iterator first) + { + std::size_t n=s.size(); + auto it=s.erase(iterator_from(first),s.end()); + pop_index_entry(n-s.size()); + return range_from(it); + } + + virtual range erase_from_begin(const_base_iterator last) + { + std::size_t n=s.size(); + auto it=s.erase(s.begin(),iterator_from(last)); + pop_index_entry(n-s.size()); + return range_from(it); + } + + base_sentinel clear()noexcept{return nv_clear();} + + base_sentinel nv_clear()noexcept + { + s.clear(); + for(std::size_t n=i.size()-1;n--;)i.pop_back(); + return sentinel(); + } + +private: + friend Model; + + template<typename... Args> + static segment_backend_unique_ptr new_( + segment_allocator_type al,Args&&... args) + { + auto p=std::allocator_traits<segment_allocator_type>::allocate(al,1); + try{ + ::new ((void*)p) split_segment{std::forward<Args>(args)...}; + } + catch(...){ + std::allocator_traits<segment_allocator_type>::deallocate(al,p,1); + throw; + } + return {p,&delete_}; + } + + static void delete_(segment_backend* p) + { + auto q=static_cast<split_segment*>(p); + auto al=segment_allocator_type{q->s.get_allocator()}; + q->~split_segment(); + std::allocator_traits<segment_allocator_type>::deallocate(al,q,1); + } + + split_segment(const Allocator& al): + s{typename store::allocator_type{al}}, + i{{},typename index::allocator_type{al}}{build_index();} + split_segment(store&& s_): + s{std::move(s_)},i{{},typename index::allocator_type{s.get_allocator()}} + {build_index();} + + void prereserve() + { + if(s.size()==s.capacity())expand(); + } + + const_base_iterator prereserve(const_base_iterator p) + { + if(s.size()==s.capacity()){ + auto n=p-i.data(); + expand(); + return const_base_iterator{i.data()+n}; + } + else return p; + } + + const_iterator prereserve(const_iterator p) + { + if(s.size()==s.capacity()){ + auto n=p-const_concrete_ptr(s.data()); + expand(); + return const_concrete_ptr(s.data())+n; + } + else return p; + } + + const_iterator prereserve(const_iterator p,std::size_t m) + { + if(s.size()+m>s.capacity()){ + auto n=p-const_concrete_ptr(s.data()); + expand(m); + return const_concrete_ptr(s.data())+n; + } + else return p; + } + + void expand() + { + std::size_t c= + s.size()<=1||(s.max_size()-1-s.size())/2<s.size()? + s.size()+1: + s.size()+s.size()/2; + i.reserve(c+1); + s.reserve(c); + rebuild_index(); + } + + void expand(std::size_t m) + { + i.reserve(s.size()+m+1); + s.reserve(s.size()+m); + rebuild_index(); + } + + void build_index(std::size_t start=0) + { + for(std::size_t n=start,m=s.size();n<=m;++n){ + i.push_back(Model::make_value_type(concrete_ref(s.data()[n]))); + }; + } + + void rebuild_index() + { + i.clear(); + build_index(); + } + + void push_index_entry() + { + build_index(s.size()); + } + + void pop_index_entry(std::size_t n=1) + { + while(n--)i.pop_back(); + } + + static Concrete& concrete_ref(value_pointer p)noexcept + { + return *static_cast<Concrete*>(p); + } + + static Concrete& concrete_ref(store_value_type& r)noexcept + { + return *concrete_ptr(&r); + } + + static const Concrete& const_concrete_ref(const_value_pointer p)noexcept + { + return *static_cast<const Concrete*>(p); + } + + static Concrete* concrete_ptr(store_value_type* p)noexcept + { + return reinterpret_cast<Concrete*>( + static_cast<value_holder_base<Concrete>*>(p)); + } + + static const Concrete* const_concrete_ptr(const store_value_type* p)noexcept + { + return concrete_ptr(const_cast<store_value_type*>(p)); + } + + static value_type* value_ptr(const value_type* p)noexcept + { + return const_cast<value_type*>(p); + } + + /* It would have sufficed if iterator_from returned const_store_iterator + * except for the fact that some old versions of libstdc++ claiming to be + * C++11 compliant do not however provide std::vector modifier ops taking + * const_iterator's. + */ + + store_iterator iterator_from(const_base_iterator p) + { + return s.begin()+(p-i.data()); + } + + store_iterator iterator_from(const_iterator p) + { + return s.begin()+(p-const_concrete_ptr(s.data())); + } + + base_sentinel sentinel()const noexcept + { + return base_iterator{value_ptr(i.data()+s.size())}; + } + + range range_from(const_store_iterator it)const + { + return {base_iterator{value_ptr(i.data()+(it-s.begin()))},sentinel()}; + } + + range range_from(std::size_t n)const + { + return {base_iterator{value_ptr(i.data()+n)},sentinel()}; + } + + template<typename InputIterator> + range insert( + const_iterator p,InputIterator first,InputIterator last, + std::input_iterator_tag) + { + std::size_t n=0; + for(;first!=last;++first,++n,++p){ + p=prereserve(p); + s.emplace(iterator_from(p),*first); + push_index_entry(); + } + return range_from(iterator_from(p-n)); + } + + template<typename InputIterator> + range insert( + const_iterator p,InputIterator first,InputIterator last, + std::forward_iterator_tag) + { + auto n=s.size(); + auto m=static_cast<std::size_t>(std::distance(first,last)); + if(m){ + p=prereserve(p,m); + try{ + s.insert(iterator_from(p),first,last); + } + catch(...){ + build_index(n+1); + throw; + } + build_index(n+1); + } + return range_from(iterator_from(p)); + } + + store s; + index i; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif |