1/* Copyright 2016-2020 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_SPLIT_SEGMENT_HPP
10#define BOOST_POLY_COLLECTION_DETAIL_SPLIT_SEGMENT_HPP
11
12#if defined(_MSC_VER)
13#pragma once
14#endif
15
16#include <boost/poly_collection/detail/segment_backend.hpp>
17#include <boost/poly_collection/detail/value_holder.hpp>
18#include <iterator>
19#include <memory>
20#include <new>
21#include <utility>
22#include <vector>
23
24namespace boost{
25
26namespace poly_collection{
27
28namespace detail{
29
30/* segment_backend implementation that maintains two internal vectors, one for
31 * value_type's (the index) and another for the concrete elements those refer
32 * to (the store).
33 *
34 * Requires:
35 * - [const_]base_iterator is constructible from value_type*.
36 * - value_type is copy constructible.
37 * - Model::make_value_type(x) returns a value_type created from a reference
38 * to the concrete type.
39 *
40 * Conversion from base_iterator to local_iterator<Concrete> requires accesing
41 * value_type internal info, so the end() base_iterator has to be made to point
42 * to a valid element of index, which implies size(index)=size(store)+1. This
43 * slightly complicates the memory management.
44 */
45
46template<typename Model,typename Concrete,typename Allocator>
47class split_segment:public segment_backend<Model,Allocator>
48{
49 using value_type=typename Model::value_type;
50 using store_value_type=value_holder<Concrete>;
51 using store=std::vector<
52 store_value_type,
53 typename std::allocator_traits<Allocator>::
54 template rebind_alloc<store_value_type>
55 >;
56 using store_iterator=typename store::iterator;
57 using const_store_iterator=typename store::const_iterator;
58 using index=std::vector<
59 value_type,
60 typename std::allocator_traits<Allocator>::
61 template rebind_alloc<value_type>
62 >;
63 using const_index_iterator=typename index::const_iterator;
64 using segment_backend=detail::segment_backend<Model,Allocator>;
65 using typename segment_backend::segment_backend_unique_ptr;
66 using typename segment_backend::value_pointer;
67 using typename segment_backend::const_value_pointer;
68 using typename segment_backend::base_iterator;
69 using typename segment_backend::const_base_iterator;
70 using const_iterator=
71 typename segment_backend::template const_iterator<Concrete>;
72 using typename segment_backend::base_sentinel;
73 using typename segment_backend::range;
74 using segment_allocator_type=typename std::allocator_traits<Allocator>::
75 template rebind_alloc<split_segment>;
76
77public:
78 virtual ~split_segment()=default;
79
80 static segment_backend_unique_ptr make(const segment_allocator_type& al)
81 {
82 return new_(al,al);
83 }
84
85 virtual segment_backend_unique_ptr copy()const
86 {
87 return new_(s.get_allocator(),store{s});
88 }
89
90 virtual segment_backend_unique_ptr copy(const Allocator& al)const
91 {
92 return new_(al,store{s,al});
93 }
94
95 virtual segment_backend_unique_ptr empty_copy(const Allocator& al)const
96 {
97 return new_(al,al);
98 }
99
100 virtual segment_backend_unique_ptr move(const Allocator& al)
101 {
102 return new_(al,store{std::move(s),al});
103 }
104
105 virtual bool equal(const segment_backend& x)const
106 {
107 return s==static_cast<const split_segment&>(x).s;
108 }
109
110 virtual Allocator get_allocator()const noexcept
111 {return s.get_allocator();}
112 virtual base_iterator begin()const noexcept{return nv_begin();}
113 base_iterator nv_begin()const noexcept
114 {return base_iterator{value_ptr(p: i.data())};}
115 virtual base_iterator end()const noexcept{return nv_end();}
116 base_iterator nv_end()const noexcept
117 {return base_iterator{value_ptr(p: i.data()+s.size())};}
118 virtual bool empty()const noexcept{return nv_empty();}
119 bool nv_empty()const noexcept{return s.empty();}
120 virtual std::size_t size()const noexcept{return nv_size();}
121 std::size_t nv_size()const noexcept{return s.size();}
122 virtual std::size_t max_size()const noexcept{return nv_max_size();}
123 std::size_t nv_max_size()const noexcept{return s.max_size()-1;}
124 virtual std::size_t capacity()const noexcept{return nv_capacity();}
125 std::size_t nv_capacity()const noexcept{return s.capacity();}
126
127 virtual base_sentinel reserve(std::size_t n){return nv_reserve(n);}
128
129 base_sentinel nv_reserve(std::size_t n)
130 {
131 bool rebuild=n>s.capacity();
132 i.reserve(n+1);
133 s.reserve(n);
134 if(rebuild)rebuild_index();
135 return sentinel();
136 };
137
138 virtual base_sentinel shrink_to_fit(){return nv_shrink_to_fit();}
139
140 base_sentinel nv_shrink_to_fit()
141 {
142 try{
143 auto p=s.data();
144 if(!s.empty())s.shrink_to_fit();
145 else{
146 store ss{s.get_allocator()};
147 ss.reserve(1); /* --> s.data()!=nullptr */
148 s.swap(ss);
149 }
150 if(p!=s.data()){
151 index ii{{},i.get_allocator()};
152 ii.reserve(s.capacity()+1);
153 i.swap(ii);
154 build_index();
155 }
156 }
157 catch(...){
158 rebuild_index();
159 throw;
160 }
161 return sentinel();
162 }
163
164 template<typename Iterator,typename... Args>
165 range nv_emplace(Iterator p,Args&&... args)
166 {
167 auto q=prereserve(p);
168 auto it=s.emplace(
169 iterator_from(q),
170 value_holder_emplacing_ctor,std::forward<Args>(args)...);
171 push_index_entry();
172 return range_from(it);
173 }
174
175 template<typename... Args>
176 range nv_emplace_back(Args&&... args)
177 {
178 prereserve();
179 s.emplace_back(value_holder_emplacing_ctor,std::forward<Args>(args)...);
180 push_index_entry();
181 return range_from(s.size()-1);
182 }
183
184 virtual range push_back(const_value_pointer x)
185 {return nv_push_back(const_concrete_ref(p: x));}
186
187 range nv_push_back(const Concrete& x)
188 {
189 prereserve();
190 s.emplace_back(x);
191 push_index_entry();
192 return range_from(s.size()-1);
193 }
194
195 virtual range push_back_move(value_pointer x)
196 {return nv_push_back(std::move(concrete_ref(x)));}
197
198 range nv_push_back(Concrete&& x)
199 {
200 prereserve();
201 s.emplace_back(std::move(x));
202 push_index_entry();
203 return range_from(s.size()-1);
204 }
205
206 virtual range insert(const_base_iterator p,const_value_pointer x)
207 {return nv_insert(const_iterator(p),const_concrete_ref(p: x));}
208
209 range nv_insert(const_iterator p,const Concrete& x)
210 {
211 p=prereserve(p);
212 auto it=s.emplace(iterator_from(p),x);
213 push_index_entry();
214 return range_from(it);
215 }
216
217 virtual range insert_move(const_base_iterator p,value_pointer x)
218 {return nv_insert(const_iterator(p),std::move(concrete_ref(x)));}
219
220 range nv_insert(const_iterator p,Concrete&& x)
221 {
222 p=prereserve(p);
223 auto it=s.emplace(iterator_from(p),std::move(x));
224 push_index_entry();
225 return range_from(it);
226 }
227
228 template<typename InputIterator>
229 range nv_insert(InputIterator first,InputIterator last)
230 {
231 return nv_insert(
232 const_iterator(concrete_ptr(p: s.data()+s.size())),first,last);
233 }
234
235 template<typename InputIterator>
236 range nv_insert(const_iterator p,InputIterator first,InputIterator last)
237 {
238 return insert(
239 p,first,last,
240 typename std::iterator_traits<InputIterator>::iterator_category{});
241 }
242
243 virtual range erase(const_base_iterator p)
244 {return nv_erase(const_iterator(p));}
245
246 range nv_erase(const_iterator p)
247 {
248 pop_index_entry();
249 return range_from(s.erase(iterator_from(p)));
250 }
251
252 virtual range erase(const_base_iterator first,const_base_iterator last)
253 {return nv_erase(const_iterator(first),const_iterator(last));}
254
255 range nv_erase(const_iterator first,const_iterator last)
256 {
257 std::size_t n=s.size();
258 auto it=s.erase(iterator_from(first),iterator_from(last));
259 pop_index_entry(n: n-s.size());
260 return range_from(it);
261 }
262
263 virtual range erase_till_end(const_base_iterator first)
264 {
265 std::size_t n=s.size();
266 auto it=s.erase(iterator_from(first),s.end());
267 pop_index_entry(n: n-s.size());
268 return range_from(it);
269 }
270
271 virtual range erase_from_begin(const_base_iterator last)
272 {
273 std::size_t n=s.size();
274 auto it=s.erase(s.begin(),iterator_from(last));
275 pop_index_entry(n: n-s.size());
276 return range_from(it);
277 }
278
279 base_sentinel clear()noexcept{return nv_clear();}
280
281 base_sentinel nv_clear()noexcept
282 {
283 s.clear();
284 for(std::size_t n=i.size()-1;n--;)i.pop_back();
285 return sentinel();
286 }
287
288private:
289 template<typename... Args>
290 static segment_backend_unique_ptr new_(
291 segment_allocator_type al,Args&&... args)
292 {
293 auto p=std::allocator_traits<segment_allocator_type>::allocate(al,1);
294 try{
295 ::new ((void*)p) split_segment{std::forward<Args>(args)...};
296 }
297 catch(...){
298 std::allocator_traits<segment_allocator_type>::deallocate(al,p,1);
299 throw;
300 }
301 return {p,&delete_};
302 }
303
304 static void delete_(segment_backend* p)
305 {
306 auto q=static_cast<split_segment*>(p);
307 auto al=segment_allocator_type{q->s.get_allocator()};
308 q->~split_segment();
309 std::allocator_traits<segment_allocator_type>::deallocate(al,q,1);
310 }
311
312 split_segment(const Allocator& al):
313 s{typename store::allocator_type{al}},
314 i{{},typename index::allocator_type{al}}
315 {
316 s.reserve(1); /* --> s.data()!=nullptr */
317 build_index();
318 }
319
320 split_segment(store&& s_):
321 s{std::move(s_)},i{{},typename index::allocator_type{s.get_allocator()}}
322 {
323 s.reserve(1); /* --> s.data()!=nullptr */
324 build_index();
325 }
326
327 void prereserve()
328 {
329 if(s.size()==s.capacity())expand();
330 }
331
332 const_base_iterator prereserve(const_base_iterator p)
333 {
334 if(s.size()==s.capacity()){
335 auto n=p-i.data();
336 expand();
337 return const_base_iterator{i.data()+n};
338 }
339 else return p;
340 }
341
342 const_iterator prereserve(const_iterator p)
343 {
344 if(s.size()==s.capacity()){
345 auto n=p-const_concrete_ptr(p: s.data());
346 expand();
347 return const_concrete_ptr(p: s.data())+n;
348 }
349 else return p;
350 }
351
352 const_iterator prereserve(const_iterator p,std::size_t m)
353 {
354 if(s.size()+m>s.capacity()){
355 auto n=p-const_concrete_ptr(p: s.data());
356 expand(m);
357 return const_concrete_ptr(p: s.data())+n;
358 }
359 else return p;
360 }
361
362 void expand()
363 {
364 std::size_t c=
365 s.size()<=1||(s.max_size()-1-s.size())/2<s.size()?
366 s.size()+1:
367 s.size()+s.size()/2;
368 i.reserve(c+1);
369 s.reserve(c);
370 rebuild_index();
371 }
372
373 void expand(std::size_t m)
374 {
375 i.reserve(s.size()+m+1);
376 s.reserve(s.size()+m);
377 rebuild_index();
378 }
379
380 void build_index(std::size_t start=0)
381 {
382 for(std::size_t n=start,m=s.size();n<=m;++n){
383 i.push_back(Model::make_value_type(concrete_ref(s.data()[n])));
384 };
385 }
386
387 void rebuild_index()
388 {
389 i.clear();
390 build_index();
391 }
392
393 void push_index_entry()
394 {
395 build_index(start: s.size());
396 }
397
398 void pop_index_entry(std::size_t n=1)
399 {
400 while(n--)i.pop_back();
401 }
402
403 static Concrete& concrete_ref(value_pointer p)noexcept
404 {
405 return *static_cast<Concrete*>(p);
406 }
407
408 static Concrete& concrete_ref(store_value_type& r)noexcept
409 {
410 return *concrete_ptr(p: &r);
411 }
412
413 static const Concrete& const_concrete_ref(const_value_pointer p)noexcept
414 {
415 return *static_cast<const Concrete*>(p);
416 }
417
418 static Concrete* concrete_ptr(store_value_type* p)noexcept
419 {
420 return reinterpret_cast<Concrete*>(
421 static_cast<value_holder_base<Concrete>*>(p));
422 }
423
424 static const Concrete* const_concrete_ptr(const store_value_type* p)noexcept
425 {
426 return concrete_ptr(p: const_cast<store_value_type*>(p));
427 }
428
429 static value_type* value_ptr(const value_type* p)noexcept
430 {
431 return const_cast<value_type*>(p);
432 }
433
434 /* It would have sufficed if iterator_from returned const_store_iterator
435 * except for the fact that some old versions of libstdc++ claiming to be
436 * C++11 compliant do not however provide std::vector modifier ops taking
437 * const_iterator's.
438 */
439
440 store_iterator iterator_from(const_base_iterator p)
441 {
442 return s.begin()+(p-i.data());
443 }
444
445 store_iterator iterator_from(const_iterator p)
446 {
447 return s.begin()+(p-const_concrete_ptr(p: s.data()));
448 }
449
450 base_sentinel sentinel()const noexcept
451 {
452 return base_iterator{value_ptr(p: i.data()+s.size())};
453 }
454
455 range range_from(const_store_iterator it)const
456 {
457 return {base_iterator{value_ptr(p: i.data()+(it-s.begin()))},sentinel()};
458 }
459
460 range range_from(std::size_t n)const
461 {
462 return {base_iterator{value_ptr(p: i.data()+n)},sentinel()};
463 }
464
465 template<typename InputIterator>
466 range insert(
467 const_iterator p,InputIterator first,InputIterator last,
468 std::input_iterator_tag)
469 {
470 std::size_t n=0;
471 for(;first!=last;++first,++n,++p){
472 p=prereserve(p);
473 s.emplace(iterator_from(p),*first);
474 push_index_entry();
475 }
476 return range_from(iterator_from(p-n));
477 }
478
479 template<typename InputIterator>
480 range insert(
481 const_iterator p,InputIterator first,InputIterator last,
482 std::forward_iterator_tag)
483 {
484 auto n=s.size();
485 auto m=static_cast<std::size_t>(std::distance(first,last));
486 if(m){
487 p=prereserve(p,m);
488 try{
489 s.insert(iterator_from(p),first,last);
490 }
491 catch(...){
492 build_index(start: n+1);
493 throw;
494 }
495 build_index(start: n+1);
496 }
497 return range_from(iterator_from(p));
498 }
499
500 store s;
501 index i;
502};
503
504} /* namespace poly_collection::detail */
505
506} /* namespace poly_collection */
507
508} /* namespace boost */
509
510#endif
511

source code of boost/libs/poly_collection/include/boost/poly_collection/detail/split_segment.hpp