poly_collection/detail/split_segment.hpp

0001 /* Copyright 2016-2020 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/poly_collection for library home page.
0007  */
0008
0009 #ifndef BOOST_POLY_COLLECTION_DETAIL_SPLIT_SEGMENT_HPP
0010 #define BOOST_POLY_COLLECTION_DETAIL_SPLIT_SEGMENT_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/poly_collection/detail/segment_backend.hpp>
0017 #include <boost/poly_collection/detail/value_holder.hpp>
0018 #include <iterator>
0019 #include <memory>
0020 #include <new>
0021 #include <utility>
0022 #include <vector>
0023
0024 namespace boost{
0025
0026 namespace poly_collection{
0027
0028 namespace detail{
0029
0030 /* segment_backend implementation that maintains two internal vectors, one for
0031  * value_type's (the index) and another for the concrete elements those refer
0032  * to (the store).
0033  *
0034  * Requires:
0035  *   - [const_]base_iterator is constructible from value_type*.
0036  *   - value_type is copy constructible.
0037  *   - Model::make_value_type(x) returns a value_type created from a reference
0038  *     to the concrete type.
0039  *
0040  * Conversion from base_iterator to local_iterator<Concrete> requires accesing
0041  * value_type internal info, so the end() base_iterator has to be made to point
0042  * to a valid element of index, which implies size(index)=size(store)+1. This
0043  * slightly complicates the memory management.
0044  */
0045
0046 template<typename Model,typename Concrete,typename Allocator>
0047 class split_segment:public segment_backend<Model,Allocator>
0048 {
0049   using value_type=typename Model::value_type;
0050   using store_value_type=value_holder<Concrete>;
0051   using store=std::vector<
0052     store_value_type,
0053     typename std::allocator_traits<Allocator>::
0054       template rebind_alloc<store_value_type>
0055   >;
0056   using store_iterator=typename store::iterator;
0057   using const_store_iterator=typename store::const_iterator;
0058   using index=std::vector<
0059     value_type,
0060     typename std::allocator_traits<Allocator>::
0061       template rebind_alloc<value_type>
0062   >;
0063   using const_index_iterator=typename index::const_iterator;
0064   using segment_backend=detail::segment_backend<Model,Allocator>;
0065   using typename segment_backend::segment_backend_unique_ptr;
0066   using typename segment_backend::value_pointer;
0067   using typename segment_backend::const_value_pointer;
0068   using typename segment_backend::base_iterator;
0069   using typename segment_backend::const_base_iterator;
0070   using const_iterator=
0071     typename segment_backend::template const_iterator<Concrete>;
0072   using typename segment_backend::base_sentinel;
0073   using typename segment_backend::range;
0074   using segment_allocator_type=typename std::allocator_traits<Allocator>::
0075     template rebind_alloc<split_segment>;
0076
0077 public:
0078   virtual ~split_segment()=default;
0079
0080   static segment_backend_unique_ptr make(const segment_allocator_type& al)
0081   {
0082     return new_(al,al);
0083   }
0084
0085   virtual segment_backend_unique_ptr copy()const
0086   {
0087     return new_(s.get_allocator(),store{s});
0088   }
0089
0090   virtual segment_backend_unique_ptr copy(const Allocator& al)const
0091   {
0092     return new_(al,store{s,al});
0093   }
0094
0095   virtual segment_backend_unique_ptr empty_copy(const Allocator& al)const
0096   {
0097     return new_(al,al);
0098   }
0099
0100   virtual segment_backend_unique_ptr move(const Allocator& al)
0101   {
0102     return new_(al,store{std::move(s),al});
0103   }
0104
0105   virtual bool equal(const segment_backend& x)const
0106   {
0107     return s==static_cast<const split_segment&>(x).s;
0108   }
0109
0110   virtual Allocator     get_allocator()const noexcept
0111                          {return s.get_allocator();}
0112   virtual base_iterator begin()const noexcept{return nv_begin();}
0113   base_iterator         nv_begin()const noexcept
0114                          {return base_iterator{value_ptr(i.data())};}
0115   virtual base_iterator end()const noexcept{return nv_end();}
0116   base_iterator         nv_end()const noexcept
0117                          {return base_iterator{value_ptr(i.data()+s.size())};}
0118   virtual bool          empty()const noexcept{return nv_empty();}
0119   bool                  nv_empty()const noexcept{return s.empty();}
0120   virtual std::size_t   size()const noexcept{return nv_size();}
0121   std::size_t           nv_size()const noexcept{return s.size();}
0122   virtual std::size_t   max_size()const noexcept{return nv_max_size();}
0123   std::size_t           nv_max_size()const noexcept{return s.max_size()-1;}
0124   virtual std::size_t   capacity()const noexcept{return nv_capacity();}
0125   std::size_t           nv_capacity()const noexcept{return s.capacity();}
0126
0127   virtual base_sentinel reserve(std::size_t n){return nv_reserve(n);}
0128
0129   base_sentinel nv_reserve(std::size_t n)
0130   {
0131     bool rebuild=n>s.capacity();
0132     i.reserve(n+1);
0133     s.reserve(n);
0134     if(rebuild)rebuild_index();
0135     return sentinel();
0136   };
0137
0138   virtual base_sentinel shrink_to_fit(){return nv_shrink_to_fit();}
0139
0140   base_sentinel nv_shrink_to_fit()
0141   {
0142     try{
0143       auto p=s.data();
0144       if(!s.empty())s.shrink_to_fit();
0145       else{
0146         store ss{s.get_allocator()};
0147         ss.reserve(1); /* --> s.data()!=nullptr */
0148         s.swap(ss);
0149       }
0150       if(p!=s.data()){
0151         index ii{{},i.get_allocator()};
0152         ii.reserve(s.capacity()+1);
0153         i.swap(ii);
0154         build_index();
0155       }
0156     }
0157     catch(...){
0158       rebuild_index();
0159       throw;
0160     }
0161     return sentinel();
0162   }
0163
0164   template<typename Iterator,typename... Args>
0165   range nv_emplace(Iterator p,Args&&... args)
0166   {
0167     auto q=prereserve(p);
0168     auto it=s.emplace(
0169       iterator_from(q),
0170       value_holder_emplacing_ctor,std::forward<Args>(args)...);
0171     push_index_entry();
0172     return range_from(it);
0173   }
0174
0175   template<typename... Args>
0176   range nv_emplace_back(Args&&... args)
0177   {
0178     prereserve();
0179     s.emplace_back(value_holder_emplacing_ctor,std::forward<Args>(args)...);
0180     push_index_entry();
0181     return range_from(s.size()-1);
0182   }
0183
0184   virtual range push_back(const_value_pointer x)
0185   {return nv_push_back(const_concrete_ref(x));}
0186
0187   range nv_push_back(const Concrete& x)
0188   {
0189     prereserve();
0190     s.emplace_back(x);
0191     push_index_entry();
0192     return range_from(s.size()-1);
0193   }
0194
0195   virtual range push_back_move(value_pointer x)
0196   {return nv_push_back(std::move(concrete_ref(x)));}
0197
0198   range nv_push_back(Concrete&& x)
0199   {
0200     prereserve();
0201     s.emplace_back(std::move(x));
0202     push_index_entry();
0203     return range_from(s.size()-1);
0204   }
0205
0206   virtual range insert(const_base_iterator p,const_value_pointer x)
0207   {return nv_insert(const_iterator(p),const_concrete_ref(x));}
0208
0209   range nv_insert(const_iterator p,const Concrete& x)
0210   {
0211     p=prereserve(p);
0212     auto it=s.emplace(iterator_from(p),x);
0213     push_index_entry();
0214     return range_from(it);
0215   }
0216
0217   virtual range insert_move(const_base_iterator p,value_pointer x)
0218   {return nv_insert(const_iterator(p),std::move(concrete_ref(x)));}
0219
0220   range nv_insert(const_iterator p,Concrete&& x)
0221   {
0222     p=prereserve(p);
0223     auto it=s.emplace(iterator_from(p),std::move(x));
0224     push_index_entry();
0225     return range_from(it);
0226   }
0227
0228   template<typename InputIterator>
0229   range nv_insert(InputIterator first,InputIterator last)
0230   {
0231     return nv_insert(
0232       const_iterator(concrete_ptr(s.data()+s.size())),first,last);
0233   }
0234
0235   template<typename InputIterator>
0236   range nv_insert(const_iterator p,InputIterator first,InputIterator last)
0237   {
0238     return insert(
0239       p,first,last,
0240       typename std::iterator_traits<InputIterator>::iterator_category{});
0241   }
0242
0243   virtual range erase(const_base_iterator p)
0244   {return nv_erase(const_iterator(p));}
0245
0246   range nv_erase(const_iterator p)
0247   {
0248     pop_index_entry();
0249     return range_from(s.erase(iterator_from(p)));
0250   }
0251
0252   virtual range erase(const_base_iterator first,const_base_iterator last)
0253   {return nv_erase(const_iterator(first),const_iterator(last));}
0254
0255   range nv_erase(const_iterator first,const_iterator last)
0256   {
0257     std::size_t n=s.size();
0258     auto it=s.erase(iterator_from(first),iterator_from(last));
0259     pop_index_entry(n-s.size());
0260     return range_from(it);
0261   }
0262
0263   virtual range erase_till_end(const_base_iterator first)
0264   {
0265     std::size_t n=s.size();
0266     auto it=s.erase(iterator_from(first),s.end());
0267     pop_index_entry(n-s.size());
0268     return range_from(it);
0269   }
0270
0271   virtual range erase_from_begin(const_base_iterator last)
0272   {
0273     std::size_t n=s.size();
0274     auto it=s.erase(s.begin(),iterator_from(last));
0275     pop_index_entry(n-s.size());
0276     return range_from(it);
0277   }
0278
0279   base_sentinel clear()noexcept{return nv_clear();}
0280
0281   base_sentinel nv_clear()noexcept
0282   {
0283     s.clear();
0284     for(std::size_t n=i.size()-1;n--;)i.pop_back();
0285     return sentinel();
0286   }
0287
0288 private:
0289   template<typename... Args>
0290   static segment_backend_unique_ptr new_(
0291     segment_allocator_type al,Args&&... args)
0292   {
0293     auto p=std::allocator_traits<segment_allocator_type>::allocate(al,1);
0294     try{
0295       ::new ((void*)p) split_segment{std::forward<Args>(args)...};
0296     }
0297     catch(...){
0298       std::allocator_traits<segment_allocator_type>::deallocate(al,p,1);
0299       throw;
0300     }
0301     return {p,&delete_};
0302   }
0303
0304   static void delete_(segment_backend* p)
0305   {
0306     auto q=static_cast<split_segment*>(p);
0307     auto al=segment_allocator_type{q->s.get_allocator()};
0308     q->~split_segment();
0309     std::allocator_traits<segment_allocator_type>::deallocate(al,q,1);
0310   }
0311
0312   split_segment(const Allocator& al):
0313     s{typename store::allocator_type{al}},
0314     i{{},typename index::allocator_type{al}}
0315   {
0316     s.reserve(1); /* --> s.data()!=nullptr */
0317     build_index();
0318   }
0319
0320   split_segment(store&& s_):
0321     s{std::move(s_)},i{{},typename index::allocator_type{s.get_allocator()}}
0322   {
0323     s.reserve(1); /* --> s.data()!=nullptr */
0324     build_index();
0325   }
0326
0327   void prereserve()
0328   {
0329     if(s.size()==s.capacity())expand();
0330   }
0331
0332   const_base_iterator prereserve(const_base_iterator p)
0333   {
0334     if(s.size()==s.capacity()){
0335       auto n=p-i.data();
0336       expand();
0337       return const_base_iterator{i.data()+n};
0338     }
0339     else return p;
0340   }
0341
0342   const_iterator prereserve(const_iterator p)
0343   {
0344     if(s.size()==s.capacity()){
0345       auto n=p-const_concrete_ptr(s.data());
0346       expand();
0347       return const_concrete_ptr(s.data())+n;
0348     }
0349     else return p;
0350   }
0351
0352   const_iterator prereserve(const_iterator p,std::size_t m)
0353   {
0354     if(s.size()+m>s.capacity()){
0355       auto n=p-const_concrete_ptr(s.data());
0356       expand(m);
0357       return const_concrete_ptr(s.data())+n;
0358     }
0359     else return p;
0360   }
0361
0362   void expand()
0363   {
0364     std::size_t c=
0365       s.size()<=1||(s.max_size()-1-s.size())/2<s.size()?
0366         s.size()+1:
0367         s.size()+s.size()/2;
0368     i.reserve(c+1);
0369     s.reserve(c);
0370     rebuild_index();
0371   }
0372
0373   void expand(std::size_t m)
0374   {
0375     i.reserve(s.size()+m+1);
0376     s.reserve(s.size()+m);
0377     rebuild_index();
0378   }
0379
0380   void build_index(std::size_t start=0)
0381   {
0382     for(std::size_t n=start,m=s.size();n<=m;++n){
0383       i.push_back(Model::make_value_type(concrete_ref(s.data()[n])));
0384     };
0385   }
0386
0387   void rebuild_index()
0388   {
0389     i.clear();
0390     build_index();
0391   }
0392
0393   void push_index_entry()
0394   {
0395     build_index(s.size());
0396   }
0397
0398   void pop_index_entry(std::size_t n=1)
0399   {
0400     while(n--)i.pop_back();
0401   }
0402
0403   static Concrete& concrete_ref(value_pointer p)noexcept
0404   {
0405     return *static_cast<Concrete*>(p);
0406   }
0407
0408   static Concrete& concrete_ref(store_value_type& r)noexcept
0409   {
0410     return *concrete_ptr(&r);
0411   }
0412
0413   static const Concrete& const_concrete_ref(const_value_pointer p)noexcept
0414   {
0415     return *static_cast<const Concrete*>(p);
0416   }
0417
0418   static Concrete* concrete_ptr(store_value_type* p)noexcept
0419   {
0420     return reinterpret_cast<Concrete*>(
0421       static_cast<value_holder_base<Concrete>*>(p));
0422   }
0423
0424   static const Concrete* const_concrete_ptr(const store_value_type* p)noexcept
0425   {
0426     return concrete_ptr(const_cast<store_value_type*>(p));
0427   }
0428
0429   static value_type* value_ptr(const value_type* p)noexcept
0430   {
0431     return const_cast<value_type*>(p);
0432   }
0433
0434   /* It would have sufficed if iterator_from returned const_store_iterator
0435    * except for the fact that some old versions of libstdc++ claiming to be
0436    * C++11 compliant do not however provide std::vector modifier ops taking
0437    * const_iterator's.
0438    */
0439
0440   store_iterator iterator_from(const_base_iterator p)
0441   {
0442     return s.begin()+(p-i.data());
0443   }
0444
0445   store_iterator iterator_from(const_iterator p)
0446   {
0447     return s.begin()+(p-const_concrete_ptr(s.data()));
0448   }
0449
0450   base_sentinel sentinel()const noexcept
0451   {
0452     return base_iterator{value_ptr(i.data()+s.size())};
0453   }
0454
0455   range range_from(const_store_iterator it)const
0456   {
0457     return {base_iterator{value_ptr(i.data()+(it-s.begin()))},sentinel()};
0458   }
0459
0460   range range_from(std::size_t n)const
0461   {
0462     return {base_iterator{value_ptr(i.data()+n)},sentinel()};
0463   }
0464
0465   template<typename InputIterator>
0466   range insert(
0467     const_iterator p,InputIterator first,InputIterator last,
0468     std::input_iterator_tag)
0469   {
0470     std::size_t n=0;
0471     for(;first!=last;++first,++n,++p){
0472       p=prereserve(p);
0473       s.emplace(iterator_from(p),*first);
0474       push_index_entry();
0475     }
0476     return range_from(iterator_from(p-n));
0477   }
0478
0479   template<typename InputIterator>
0480   range insert(
0481     const_iterator p,InputIterator first,InputIterator last,
0482     std::forward_iterator_tag)
0483   {
0484     auto n=s.size();
0485     auto m=static_cast<std::size_t>(std::distance(first,last));
0486     if(m){
0487       p=prereserve(p,m);
0488       try{
0489         s.insert(iterator_from(p),first,last);
0490       }
0491       catch(...){
0492         build_index(n+1);
0493         throw;
0494       }
0495       build_index(n+1);
0496     }
0497     return range_from(iterator_from(p));
0498   }
0499
0500   store s;
0501   index i;
0502 };
0503
0504 } /* namespace poly_collection::detail */
0505
0506 } /* namespace poly_collection */
0507
0508 } /* namespace boost */
0509
0510 #endif