]> git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/ptr_container/include/boost/ptr_container/detail/reversible_ptr_container.hpp
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / ptr_container / include / boost / ptr_container / detail / reversible_ptr_container.hpp
1 //
2 // Boost.Pointer Container
3 //
4 // Copyright Thorsten Ottosen 2003-2005. Use, modification and
5 // distribution is subject to the Boost Software License, Version
6 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // For more information, see http://www.boost.org/libs/ptr_container/
10 //
11
12
13 #ifndef BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP
14 #define BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP
15
16 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
17 # pragma once
18 #endif
19
20 #include <boost/ptr_container/detail/throw_exception.hpp>
21 #include <boost/ptr_container/detail/scoped_deleter.hpp>
22 #include <boost/ptr_container/detail/static_move_ptr.hpp>
23 #include <boost/ptr_container/exception.hpp>
24 #include <boost/ptr_container/clone_allocator.hpp>
25 #include <boost/ptr_container/nullable.hpp>
26
27 #ifdef BOOST_NO_SFINAE
28 #else
29 #include <boost/range/functions.hpp>
30 #endif
31
32 #include <boost/config.hpp>
33 #include <boost/iterator/reverse_iterator.hpp>
34 #include <boost/range/iterator.hpp>
35 #include <boost/utility/enable_if.hpp>
36 #include <boost/type_traits/is_pointer.hpp>
37 #include <boost/type_traits/is_integral.hpp>
38 #include <typeinfo>
39 #include <memory>
40
41 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
42 #pragma warning(push)
43 #pragma warning(disable:4127)
44 #endif
45
46 namespace boost
47 {
48
49 namespace ptr_container_detail
50 {
51 template< class CloneAllocator >
52 struct clone_deleter
53 {
54 template< class T >
55 void operator()( const T* p ) const
56 {
57 CloneAllocator::deallocate_clone( p );
58 }
59 };
60
61 template< class T >
62 struct is_pointer_or_integral
63 {
64 BOOST_STATIC_CONSTANT(bool, value = is_pointer<T>::value || is_integral<T>::value );
65 };
66
67 struct is_pointer_or_integral_tag {};
68 struct is_range_tag {};
69 struct sequence_tag {};
70 struct fixed_length_sequence_tag : sequence_tag {};
71 struct associative_container_tag {};
72 struct ordered_associative_container_tag : associative_container_tag {};
73 struct unordered_associative_container_tag : associative_container_tag {};
74
75
76
77 template
78 <
79 class Config,
80 class CloneAllocator
81 >
82 class reversible_ptr_container
83 {
84 private:
85 BOOST_STATIC_CONSTANT( bool, allow_null = Config::allow_null );
86
87 typedef BOOST_DEDUCED_TYPENAME Config::value_type Ty_;
88
89 template< bool allow_null_values >
90 struct null_clone_allocator
91 {
92 template< class Iter >
93 static Ty_* allocate_clone_from_iterator( Iter i )
94 {
95 return allocate_clone( Config::get_const_pointer( i ) );
96 }
97
98 static Ty_* allocate_clone( const Ty_* x )
99 {
100 if( allow_null_values )
101 {
102 if( x == 0 )
103 return 0;
104 }
105 else
106 {
107 BOOST_ASSERT( x != 0 && "Cannot insert clone of null!" );
108 }
109
110 Ty_* res = CloneAllocator::allocate_clone( *x );
111 BOOST_ASSERT( typeid(*res) == typeid(*x) &&
112 "CloneAllocator::allocate_clone() does not clone the "
113 "object properly. Check that new_clone() is implemented"
114 " correctly" );
115 return res;
116 }
117
118 static void deallocate_clone( const Ty_* x )
119 {
120 if( allow_null_values )
121 {
122 if( x == 0 )
123 return;
124 }
125
126 CloneAllocator::deallocate_clone( x );
127 }
128 };
129
130 typedef BOOST_DEDUCED_TYPENAME Config::void_container_type Cont;
131 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
132 typedef null_clone_allocator<reversible_ptr_container::allow_null>
133 null_cloner_type;
134 #else
135 typedef null_clone_allocator<allow_null> null_cloner_type;
136 #endif
137 typedef clone_deleter<null_cloner_type> Deleter;
138
139 Cont c_;
140
141 public:
142 Cont& base() { return c_; }
143 protected: // having this public could break encapsulation
144 const Cont& base() const { return c_; }
145
146 public: // typedefs
147 typedef Ty_* value_type;
148 typedef Ty_* pointer;
149 typedef Ty_& reference;
150 typedef const Ty_& const_reference;
151
152 typedef BOOST_DEDUCED_TYPENAME Config::iterator
153 iterator;
154 typedef BOOST_DEDUCED_TYPENAME Config::const_iterator
155 const_iterator;
156 typedef boost::reverse_iterator< iterator >
157 reverse_iterator;
158 typedef boost::reverse_iterator< const_iterator >
159 const_reverse_iterator;
160 typedef BOOST_DEDUCED_TYPENAME Cont::difference_type
161 difference_type;
162 typedef BOOST_DEDUCED_TYPENAME Cont::size_type
163 size_type;
164 typedef BOOST_DEDUCED_TYPENAME Config::allocator_type
165 allocator_type;
166 typedef CloneAllocator clone_allocator_type;
167 typedef ptr_container_detail::static_move_ptr<Ty_,Deleter>
168 auto_type;
169
170 protected:
171
172 typedef ptr_container_detail::scoped_deleter<Ty_,null_cloner_type>
173 scoped_deleter;
174 typedef BOOST_DEDUCED_TYPENAME Cont::iterator
175 ptr_iterator;
176 typedef BOOST_DEDUCED_TYPENAME Cont::const_iterator
177 ptr_const_iterator;
178 private:
179
180 template< class InputIterator >
181 void copy( InputIterator first, InputIterator last )
182 {
183 std::copy( first, last, begin() );
184 }
185
186 void copy( const reversible_ptr_container& r )
187 {
188 copy( r.begin(), r.end() );
189 }
190
191 void copy_clones_and_release( scoped_deleter& sd ) // nothrow
192 {
193 BOOST_ASSERT( size_type( std::distance( sd.begin(), sd.end() ) ) == c_.size() );
194 std::copy( sd.begin(), sd.end(), c_.begin() );
195 sd.release();
196 }
197
198 template< class ForwardIterator >
199 void clone_assign( ForwardIterator first,
200 ForwardIterator last ) // strong
201 {
202 BOOST_ASSERT( first != last );
203 scoped_deleter sd( first, last ); // strong
204 copy_clones_and_release( sd ); // nothrow
205 }
206
207 template< class ForwardIterator >
208 void clone_back_insert( ForwardIterator first,
209 ForwardIterator last )
210 {
211 BOOST_ASSERT( first != last );
212 scoped_deleter sd( first, last );
213 insert_clones_and_release( sd, end() );
214 }
215
216 void remove_all()
217 {
218 remove( begin(), end() );
219 }
220
221 protected:
222
223 void insert_clones_and_release( scoped_deleter& sd,
224 iterator where ) // strong
225 {
226 //
227 // 'c_.insert' always provides the strong guarantee for T* elements
228 // since a copy constructor of a pointer cannot throw
229 //
230 c_.insert( where.base(),
231 sd.begin(), sd.end() );
232 sd.release();
233 }
234
235 void insert_clones_and_release( scoped_deleter& sd ) // strong
236 {
237 c_.insert( sd.begin(), sd.end() );
238 sd.release();
239 }
240
241 template< class U >
242 void remove( U* ptr )
243 {
244 null_policy_deallocate_clone( ptr );
245 }
246
247 template< class I >
248 void remove( I i )
249 {
250 null_policy_deallocate_clone( Config::get_const_pointer(i) );
251 }
252
253 template< class I >
254 void remove( I first, I last )
255 {
256 for( ; first != last; ++first )
257 remove( first );
258 }
259
260 static void enforce_null_policy( const Ty_* x, const char* msg )
261 {
262 if( !allow_null )
263 {
264 BOOST_PTR_CONTAINER_THROW_EXCEPTION( 0 == x && "null not allowed",
265 bad_pointer, msg );
266 }
267 }
268
269 static Ty_* null_policy_allocate_clone( const Ty_* x )
270 {
271 return null_cloner_type::allocate_clone( x );
272 }
273
274 static void null_policy_deallocate_clone( const Ty_* x )
275 {
276 null_cloner_type::deallocate_clone( x );
277 }
278
279 private:
280 template< class ForwardIterator >
281 ForwardIterator advance( ForwardIterator begin, size_type n )
282 {
283 ForwardIterator iter = begin;
284 std::advance( iter, n );
285 return iter;
286 }
287
288 template< class I >
289 void constructor_impl( I first, I last, std::input_iterator_tag ) // basic
290 {
291 while( first != last )
292 {
293 insert( end(), null_cloner_type::allocate_clone_from_iterator(first) );
294 ++first;
295 }
296 }
297
298 template< class I >
299 void constructor_impl( I first, I last, std::forward_iterator_tag ) // strong
300 {
301 if( first == last )
302 return;
303 clone_back_insert( first, last );
304 }
305
306 template< class I >
307 void associative_constructor_impl( I first, I last ) // strong
308 {
309 if( first == last )
310 return;
311
312 scoped_deleter sd( first, last );
313 insert_clones_and_release( sd );
314 }
315
316 public: // foundation! should be protected!
317 reversible_ptr_container()
318 { }
319
320 template< class SizeType >
321 reversible_ptr_container( SizeType n, unordered_associative_container_tag )
322 : c_( n )
323 { }
324
325 template< class SizeType >
326 reversible_ptr_container( SizeType n, fixed_length_sequence_tag )
327 : c_( n )
328 { }
329
330 template< class SizeType >
331 reversible_ptr_container( SizeType n, const allocator_type& a,
332 fixed_length_sequence_tag )
333 : c_( n, a )
334 { }
335
336 explicit reversible_ptr_container( const allocator_type& a )
337 : c_( a )
338 { }
339
340 template< class PtrContainer >
341 explicit reversible_ptr_container( std::auto_ptr<PtrContainer> clone )
342 {
343 swap( *clone );
344 }
345
346 reversible_ptr_container( const reversible_ptr_container& r )
347 {
348 constructor_impl( r.begin(), r.end(), std::forward_iterator_tag() );
349 }
350
351 template< class C, class V >
352 reversible_ptr_container( const reversible_ptr_container<C,V>& r )
353 {
354 constructor_impl( r.begin(), r.end(), std::forward_iterator_tag() );
355 }
356
357 template< class PtrContainer >
358 reversible_ptr_container& operator=( std::auto_ptr<PtrContainer> clone ) // nothrow
359 {
360 swap( *clone );
361 return *this;
362 }
363
364 reversible_ptr_container& operator=( reversible_ptr_container r ) // strong
365 {
366 swap( r );
367 return *this;
368 }
369
370 // overhead: null-initilization of container pointer (very cheap compared to cloning)
371 // overhead: 1 heap allocation (very cheap compared to cloning)
372 template< class InputIterator >
373 reversible_ptr_container( InputIterator first,
374 InputIterator last,
375 const allocator_type& a = allocator_type() ) // basic, strong
376 : c_( a )
377 {
378 constructor_impl( first, last,
379 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
380 #else
381 BOOST_DEDUCED_TYPENAME
382 #endif
383 iterator_category<InputIterator>::type() );
384 }
385
386 template< class Compare >
387 reversible_ptr_container( const Compare& comp,
388 const allocator_type& a )
389 : c_( comp, a ) {}
390
391 template< class ForwardIterator >
392 reversible_ptr_container( ForwardIterator first,
393 ForwardIterator last,
394 fixed_length_sequence_tag )
395 : c_( std::distance(first,last) )
396 {
397 constructor_impl( first, last,
398 std::forward_iterator_tag() );
399 }
400
401 template< class SizeType, class InputIterator >
402 reversible_ptr_container( SizeType n,
403 InputIterator first,
404 InputIterator last,
405 fixed_length_sequence_tag )
406 : c_( n )
407 {
408 constructor_impl( first, last,
409 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
410 #else
411 BOOST_DEDUCED_TYPENAME
412 #endif
413 iterator_category<InputIterator>::type() );
414 }
415
416 template< class Compare >
417 reversible_ptr_container( const Compare& comp,
418 const allocator_type& a,
419 associative_container_tag )
420 : c_( comp, a )
421 { }
422
423 template< class InputIterator >
424 reversible_ptr_container( InputIterator first,
425 InputIterator last,
426 associative_container_tag )
427 {
428 associative_constructor_impl( first, last );
429 }
430
431 template< class InputIterator, class Compare >
432 reversible_ptr_container( InputIterator first,
433 InputIterator last,
434 const Compare& comp,
435 const allocator_type& a,
436 associative_container_tag )
437 : c_( comp, a )
438 {
439 associative_constructor_impl( first, last );
440 }
441
442 explicit reversible_ptr_container( size_type n )
443 : c_( n ) {}
444
445 template< class Hash, class Pred >
446 reversible_ptr_container( const Hash& h,
447 const Pred& pred,
448 const allocator_type& a )
449 : c_( h, pred, a ) {}
450
451 template< class InputIterator, class Hash, class Pred >
452 reversible_ptr_container( InputIterator first,
453 InputIterator last,
454 const Hash& h,
455 const Pred& pred,
456 const allocator_type& a )
457 : c_( h, pred, a )
458 {
459 associative_constructor_impl( first, last );
460 }
461
462 public:
463 ~reversible_ptr_container()
464 {
465 remove_all();
466 }
467
468 public:
469
470 allocator_type get_allocator() const
471 {
472 return c_.get_allocator();
473 }
474
475 public: // container requirements
476 iterator begin()
477 { return iterator( c_.begin() ); }
478 const_iterator begin() const
479 { return const_iterator( c_.begin() ); }
480 iterator end()
481 { return iterator( c_.end() ); }
482 const_iterator end() const
483 { return const_iterator( c_.end() ); }
484
485 reverse_iterator rbegin()
486 { return reverse_iterator( this->end() ); }
487 const_reverse_iterator rbegin() const
488 { return const_reverse_iterator( this->end() ); }
489 reverse_iterator rend()
490 { return reverse_iterator( this->begin() ); }
491 const_reverse_iterator rend() const
492 { return const_reverse_iterator( this->begin() ); }
493
494 const_iterator cbegin() const
495 { return const_iterator( c_.begin() ); }
496 const_iterator cend() const
497 { return const_iterator( c_.end() ); }
498
499 const_reverse_iterator crbegin() const
500 { return const_reverse_iterator( this->end() ); }
501 const_reverse_iterator crend() const
502 { return const_reverse_iterator( this->begin() ); }
503
504 void swap( reversible_ptr_container& r ) // nothrow
505 {
506 c_.swap( r.c_ );
507 }
508
509 size_type size() const // nothrow
510 {
511 return c_.size();
512 }
513
514 size_type max_size() const // nothrow
515 {
516 return c_.max_size();
517 }
518
519 bool empty() const // nothrow
520 {
521 return c_.empty();
522 }
523
524 public: // optional container requirements
525
526 bool operator==( const reversible_ptr_container& r ) const // nothrow
527 {
528 if( size() != r.size() )
529 return false;
530 else
531 return std::equal( begin(), end(), r.begin() );
532 }
533
534 bool operator!=( const reversible_ptr_container& r ) const // nothrow
535 {
536 return !(*this == r);
537 }
538
539 bool operator<( const reversible_ptr_container& r ) const // nothrow
540 {
541 return std::lexicographical_compare( begin(), end(), r.begin(), r.end() );
542 }
543
544 bool operator<=( const reversible_ptr_container& r ) const // nothrow
545 {
546 return !(r < *this);
547 }
548
549 bool operator>( const reversible_ptr_container& r ) const // nothrow
550 {
551 return r < *this;
552 }
553
554 bool operator>=( const reversible_ptr_container& r ) const // nothrow
555 {
556 return !(*this < r);
557 }
558
559 public: // modifiers
560
561 iterator insert( iterator before, Ty_* x )
562 {
563 enforce_null_policy( x, "Null pointer in 'insert()'" );
564
565 auto_type ptr( x ); // nothrow
566 iterator res( c_.insert( before.base(), x ) ); // strong, commit
567 ptr.release(); // nothrow
568 return res;
569 }
570
571 template< class U >
572 iterator insert( iterator before, std::auto_ptr<U> x )
573 {
574 return insert( before, x.release() );
575 }
576
577 iterator erase( iterator x ) // nothrow
578 {
579 BOOST_ASSERT( !empty() );
580 BOOST_ASSERT( x != end() );
581
582 remove( x );
583 return iterator( c_.erase( x.base() ) );
584 }
585
586 iterator erase( iterator first, iterator last ) // nothrow
587 {
588 remove( first, last );
589 return iterator( c_.erase( first.base(),
590 last.base() ) );
591 }
592
593 template< class Range >
594 iterator erase( const Range& r )
595 {
596 return erase( boost::begin(r), boost::end(r) );
597 }
598
599 void clear()
600 {
601 remove_all();
602 c_.clear();
603 }
604
605 public: // access interface
606
607 auto_type release( iterator where )
608 {
609 BOOST_ASSERT( where != end() );
610
611 BOOST_PTR_CONTAINER_THROW_EXCEPTION( empty(), bad_ptr_container_operation,
612 "'release()' on empty container" );
613
614 auto_type ptr( Config::get_pointer( where ) ); // nothrow
615 c_.erase( where.base() ); // nothrow
616 return boost::ptr_container_detail::move( ptr );
617 }
618
619 auto_type replace( iterator where, Ty_* x ) // strong
620 {
621 BOOST_ASSERT( where != end() );
622
623 enforce_null_policy( x, "Null pointer in 'replace()'" );
624
625 auto_type ptr( x );
626
627 BOOST_PTR_CONTAINER_THROW_EXCEPTION( empty(), bad_ptr_container_operation,
628 "'replace()' on empty container" );
629
630 auto_type old( Config::get_pointer( where ) ); // nothrow
631 const_cast<void*&>(*where.base()) = ptr.release();
632 return boost::ptr_container_detail::move( old );
633 }
634
635 template< class U >
636 auto_type replace( iterator where, std::auto_ptr<U> x )
637 {
638 return replace( where, x.release() );
639 }
640
641 auto_type replace( size_type idx, Ty_* x ) // strong
642 {
643 enforce_null_policy( x, "Null pointer in 'replace()'" );
644
645 auto_type ptr( x );
646
647 BOOST_PTR_CONTAINER_THROW_EXCEPTION( idx >= size(), bad_index,
648 "'replace()' out of bounds" );
649
650 auto_type old( static_cast<Ty_*>( c_[idx] ) ); // nothrow
651 c_[idx] = ptr.release(); // nothrow, commit
652 return boost::ptr_container_detail::move( old );
653 }
654
655 template< class U >
656 auto_type replace( size_type idx, std::auto_ptr<U> x )
657 {
658 return replace( idx, x.release() );
659 }
660
661 }; // 'reversible_ptr_container'
662
663
664 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
665 #define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \
666 typename base_type::auto_type \
667 release( typename base_type::iterator i ) \
668 { \
669 return boost::ptr_container_detail::move(base_type::release(i)); \
670 }
671 #else
672 #define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \
673 using base_type::release;
674 #endif
675
676 //
677 // two-phase lookup of template functions
678 // is buggy on most compilers, so we use a macro instead
679 //
680 #define BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type ) \
681 explicit PC( std::auto_ptr<this_type> r ) \
682 : base_type ( r ) { } \
683 \
684 PC& operator=( std::auto_ptr<this_type> r ) \
685 { \
686 base_type::operator=( r ); \
687 return *this; \
688 } \
689 \
690 std::auto_ptr<this_type> release() \
691 { \
692 std::auto_ptr<this_type> ptr( new this_type );\
693 this->swap( *ptr ); \
694 return ptr; \
695 } \
696 BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \
697 \
698 std::auto_ptr<this_type> clone() const \
699 { \
700 return std::auto_ptr<this_type>( new this_type( this->begin(), this->end() ) ); \
701 }
702
703 #define BOOST_PTR_CONTAINER_DEFINE_COPY_CONSTRUCTORS( PC, base_type ) \
704 \
705 template< class U > \
706 PC( const PC<U>& r ) : base_type( r ) { } \
707 \
708 PC& operator=( PC r ) \
709 { \
710 this->swap( r ); \
711 return *this; \
712 } \
713
714
715 #define BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type ) \
716 typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator; \
717 typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type; \
718 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference const_reference; \
719 typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type allocator_type; \
720 PC() {} \
721 explicit PC( const allocator_type& a ) : base_type(a) {} \
722 template< class InputIterator > \
723 PC( InputIterator first, InputIterator last ) : base_type( first, last ) {} \
724 template< class InputIterator > \
725 PC( InputIterator first, InputIterator last, \
726 const allocator_type& a ) : base_type( first, last, a ) {}
727
728 #define BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type ) \
729 BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type ) \
730 BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type )
731
732 #define BOOST_PTR_CONTAINER_DEFINE_SEQEUENCE_MEMBERS( PC, base_type, this_type ) \
733 BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type ) \
734 BOOST_PTR_CONTAINER_DEFINE_COPY_CONSTRUCTORS( PC, base_type )
735
736 } // namespace 'ptr_container_detail'
737
738 //
739 // @remark: expose movability of internal move-pointer
740 //
741 namespace ptr_container
742 {
743 using ptr_container_detail::move;
744 }
745
746 } // namespace 'boost'
747
748 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
749 #pragma warning(pop)
750 #endif
751
752 #endif