1 /* Copyright 2016-2018 Joaquin M Lopez Munoz.
2  * Distributed under the Boost Software License, Version 1.0.
3  * (See accompanying file LICENSE_1_0.txt or copy at
4  * http://www.boost.org/LICENSE_1_0.txt)
5  *
6  * See http://www.boost.org/libs/poly_collection for library home page.
7  */
8 
9 #ifndef BOOST_POLY_COLLECTION_DETAIL_SEGMENT_HPP
10 #define BOOST_POLY_COLLECTION_DETAIL_SEGMENT_HPP
11 
12 #if defined(_MSC_VER)
13 #pragma once
14 #endif
15 
16 #include <iterator>
17 #include <memory>
18 #include <type_traits>
19 #include <utility>
20 
21 namespace boost{
22 
23 namespace poly_collection{
24 
25 namespace detail{
26 
27 /* segment<Model,Allocator> encapsulates implementations of
28  * Model::segment_backend virtual interface under a value-semantics type for
29  * use by poly_collection. The techique is described by Sean Parent at slides
30  * 157-205 of
31  * https://github.com/sean-parent/sean-parent.github.com/wiki/
32  *   presentations/2013-09-11-cpp-seasoning/cpp-seasoning.pdf
33  * with one twist: when the type of the implementation can be known at compile
34  * time, a downcast is done and non-virtual member functions (named with a nv_
35  * prefix) are used: this increases the performance of some operations.
36  */
37 
38 template<typename Model,typename Allocator>
39 class segment
40 {
41 public:
42   using value_type=typename Model::value_type;
43   using allocator_type=Allocator; /* needed for uses-allocator construction */
44   using base_iterator=typename Model::base_iterator;
45   using const_base_iterator=typename Model::const_base_iterator;
46   using base_sentinel=typename Model::base_sentinel;
47   using const_base_sentinel=typename Model::const_base_sentinel;
48   template<typename T>
49   using iterator=typename Model::template iterator<T>;
50   template<typename T>
51   using const_iterator=typename Model::template const_iterator<T>;
52 
53   template<typename T>
make(const allocator_type & al)54   static segment make(const allocator_type& al)
55   {
56     return segment_backend_implementation<T>::make(al);
57   }
58 
59   /* clones the implementation of x with no elements */
60 
make_from_prototype(const segment & x,const allocator_type & al)61   static segment make_from_prototype(const segment& x,const allocator_type& al)
62   {
63     return {from_prototype{},x,al};
64   }
65 
segment(const segment & x)66   segment(const segment& x):
67     pimpl{x.impl().copy()}{set_sentinel();}
68   segment(segment&& x)=default;
segment(const segment & x,const allocator_type & al)69   segment(const segment& x,const allocator_type& al):
70     pimpl{x.impl().copy(al)}{set_sentinel();}
71 
72   /* TODO: try ptr-level move before impl().move() */
segment(segment && x,const allocator_type & al)73   segment(segment&& x,const allocator_type& al):
74     pimpl{x.impl().move(al)}{set_sentinel();}
75 
operator =(const segment & x)76   segment& operator=(const segment& x)
77   {
78     pimpl=allocator_traits::propagate_on_container_copy_assignment::value?
79       x.impl().copy():x.impl().copy(impl().get_allocator());
80     set_sentinel();
81     return *this;
82   }
83 
operator =(segment && x)84   segment& operator=(segment&& x)
85   {
86     pimpl=x.impl().move(
87       allocator_traits::propagate_on_container_move_assignment::value?
88       x.impl().get_allocator():impl().get_allocator());
89     set_sentinel();
90     return *this;
91   }
92 
operator ==(const segment & x,const segment & y)93   friend bool operator==(const segment& x,const segment& y)
94   {
95     if(typeid(*(x.pimpl))!=typeid(*(y.pimpl)))return false;
96     else return x.impl().equal(y.impl());
97   }
98 
operator !=(const segment & x,const segment & y)99   friend bool operator!=(const segment& x,const segment& y){return !(x==y);}
100 
begin() const101   base_iterator        begin()const noexcept{return impl().begin();}
102   template<typename U>
begin() const103   base_iterator        begin()const noexcept{return impl<U>().nv_begin();}
end() const104   base_iterator        end()const noexcept{return impl().end();}
105   template<typename U>
end() const106   base_iterator        end()const noexcept{return impl<U>().nv_end();}
sentinel() const107   base_sentinel        sentinel()const noexcept{return snt;}
empty() const108   bool                 empty()const noexcept{return impl().empty();}
109   template<typename U>
empty() const110   bool                 empty()const noexcept{return impl<U>().nv_empty();}
size() const111   std::size_t          size()const noexcept{return impl().size();}
112   template<typename U>
size() const113   std::size_t          size()const noexcept{return impl<U>().nv_size();}
max_size() const114   std::size_t          max_size()const noexcept{return impl().max_size();}
115   template<typename U>
max_size() const116   std::size_t          max_size()const noexcept
117                          {return impl<U>().nv_max_size();}
reserve(std::size_t n)118   void                 reserve(std::size_t n){filter(impl().reserve(n));}
119   template<typename U>
reserve(std::size_t n)120   void                 reserve(std::size_t n){filter(impl<U>().nv_reserve(n));}
capacity() const121   std::size_t          capacity()const noexcept{return impl().capacity();}
122   template<typename U>
capacity() const123   std::size_t          capacity()const noexcept
124                          {return impl<U>().nv_capacity();}
shrink_to_fit()125   void                 shrink_to_fit(){filter(impl().shrink_to_fit());}
126   template<typename U>
shrink_to_fit()127   void                 shrink_to_fit(){filter(impl<U>().nv_shrink_to_fit());}
128 
129   template<typename U,typename Iterator,typename... Args>
emplace(Iterator it,Args &&...args)130   base_iterator emplace(Iterator it,Args&&... args)
131   {
132     return filter(impl<U>().nv_emplace(it,std::forward<Args>(args)...));
133   }
134 
135   template<typename U,typename... Args>
emplace_back(Args &&...args)136   base_iterator emplace_back(Args&&... args)
137   {
138     return filter(impl<U>().nv_emplace_back(std::forward<Args>(args)...));
139   }
140 
141   template<typename T>
push_back(const T & x)142   base_iterator push_back(const T& x)
143   {
144     return filter(impl().push_back(subaddress(x)));
145   }
146 
147   template<
148     typename T,
149     typename std::enable_if<
150       !std::is_lvalue_reference<T>::value&&!std::is_const<T>::value
151     >::type* =nullptr
152   >
push_back(T && x)153   base_iterator push_back(T&& x)
154   {
155     return filter(impl().push_back_move(subaddress(x)));
156   }
157 
158   template<typename U>
push_back_terminal(U && x)159   base_iterator push_back_terminal(U&& x)
160   {
161     return filter(
162       impl<typename std::decay<U>::type>().nv_push_back(std::forward<U>(x)));
163   }
164 
165   template<typename T>
insert(const_base_iterator it,const T & x)166   base_iterator insert(const_base_iterator it,const T& x)
167   {
168     return filter(impl().insert(it,subaddress(x)));
169   }
170 
171   template<typename U,typename T>
insert(const_iterator<U> it,const T & x)172   base_iterator insert(const_iterator<U> it,const T& x)
173   {
174     return filter(
175       impl<U>().nv_insert(it,*static_cast<const U*>(subaddress(x))));
176   }
177 
178   template<
179     typename T,
180     typename std::enable_if<
181       !std::is_lvalue_reference<T>::value&&!std::is_const<T>::value
182     >::type* =nullptr
183   >
insert(const_base_iterator it,T && x)184   base_iterator insert(const_base_iterator it,T&& x)
185   {
186     return filter(impl().insert_move(it,subaddress(x)));
187   }
188 
189   template<
190     typename U,typename T,
191     typename std::enable_if<
192       !std::is_lvalue_reference<T>::value&&!std::is_const<T>::value
193     >::type* =nullptr
194   >
insert(const_iterator<U> it,T && x)195   base_iterator insert(const_iterator<U> it,T&& x)
196   {
197     return filter(
198       impl<U>().nv_insert(it,std::move(*static_cast<U*>(subaddress(x)))));
199   }
200 
201   template<typename InputIterator>
insert(InputIterator first,InputIterator last)202   base_iterator insert(InputIterator first,InputIterator last)
203   {
204     return filter(
205       impl<typename std::iterator_traits<InputIterator>::value_type>().
206         nv_insert(first,last));
207   }
208 
209   template<typename InputIterator>
insert(const_base_iterator it,InputIterator first,InputIterator last)210   base_iterator insert(
211     const_base_iterator it,InputIterator first,InputIterator last)
212   {
213     return insert(
214       const_iterator<
215         typename std::iterator_traits<InputIterator>::value_type>(it),
216       first,last);
217   }
218 
219   template<typename U,typename InputIterator>
insert(const_iterator<U> it,InputIterator first,InputIterator last)220   base_iterator insert(
221     const_iterator<U> it,InputIterator first,InputIterator last)
222   {
223     return filter(impl<U>().nv_insert(it,first,last));
224   }
225 
erase(const_base_iterator it)226   base_iterator erase(const_base_iterator it)
227   {
228     return filter(impl().erase(it));
229   }
230 
231   template<typename U>
erase(const_iterator<U> it)232   base_iterator erase(const_iterator<U> it)
233   {
234     return filter(impl<U>().nv_erase(it));
235   }
236 
erase(const_base_iterator f,const_base_iterator l)237   base_iterator erase(const_base_iterator f,const_base_iterator l)
238   {
239     return filter(impl().erase(f,l));
240   }
241 
242   template<typename U>
erase(const_iterator<U> f,const_iterator<U> l)243   base_iterator erase(const_iterator<U> f,const_iterator<U> l)
244   {
245     return filter(impl<U>().nv_erase(f,l));
246   }
247 
248   template<typename Iterator>
erase_till_end(Iterator f)249   base_iterator erase_till_end(Iterator f)
250   {
251     return filter(impl().erase_till_end(f));
252   }
253 
254   template<typename Iterator>
erase_from_begin(Iterator l)255   base_iterator erase_from_begin(Iterator l)
256   {
257     return filter(impl().erase_from_begin(l));
258   }
259 
clear()260   void                 clear()noexcept{filter(impl().clear());}
261   template<typename U>
clear()262   void                 clear()noexcept{filter(impl<U>().nv_clear());}
263 
264 private:
265   using allocator_traits=std::allocator_traits<Allocator>;
266   using segment_backend=typename Model::template segment_backend<Allocator>;
267   template<typename Concrete>
268   using segment_backend_implementation=typename Model::
269     template segment_backend_implementation<Concrete,Allocator>;
270   using segment_backend_unique_ptr=
271     typename segment_backend::segment_backend_unique_ptr;
272   using range=typename segment_backend::range;
273 
274   struct from_prototype{};
275 
segment(segment_backend_unique_ptr && pimpl)276   segment(segment_backend_unique_ptr&& pimpl):
277     pimpl{std::move(pimpl)}{set_sentinel();}
segment(from_prototype,const segment & x,const allocator_type & al)278   segment(from_prototype,const segment& x,const allocator_type& al):
279     pimpl{x.impl().empty_copy(al)}{set_sentinel();}
280 
impl()281   segment_backend&       impl()noexcept{return *pimpl;}
impl() const282   const segment_backend& impl()const noexcept{return *pimpl;}
283 
284   template<typename Concrete>
impl()285   segment_backend_implementation<Concrete>& impl()noexcept
286   {
287     return static_cast<segment_backend_implementation<Concrete>&>(impl());
288   }
289 
290   template<typename Concrete>
impl() const291   const segment_backend_implementation<Concrete>& impl()const noexcept
292   {
293     return
294       static_cast<const segment_backend_implementation<Concrete>&>(impl());
295   }
296 
297   template<typename T>
subaddress(T & x)298   static void*         subaddress(T& x){return Model::subaddress(x);}
299   template<typename T>
subaddress(const T & x)300   static const void*   subaddress(const T& x){return Model::subaddress(x);}
301 
set_sentinel()302   void          set_sentinel(){filter(impl().end());}
filter(base_sentinel x)303   void          filter(base_sentinel x){snt=x;}
filter(const range & x)304   base_iterator filter(const range& x){snt=x.second;return x.first;}
305 
306   segment_backend_unique_ptr pimpl;
307   base_sentinel              snt;
308 };
309 
310 } /* namespace poly_collection::detail */
311 
312 } /* namespace poly_collection */
313 
314 } /* namespace boost */
315 
316 #endif
317