// | |
// Boost.Pointer Container | |
// | |
// Copyright Thorsten Ottosen 2003-2005. Use, modification and | |
// distribution is subject to 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) | |
// | |
// For more information, see http://www.boost.org/libs/ptr_container/ | |
// | |
#ifndef BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP | |
#define BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP | |
#if defined(_MSC_VER) && (_MSC_VER >= 1200) | |
# pragma once | |
#endif | |
#include <boost/ptr_container/detail/throw_exception.hpp> | |
#include <boost/ptr_container/detail/scoped_deleter.hpp> | |
#include <boost/ptr_container/detail/static_move_ptr.hpp> | |
#include <boost/ptr_container/exception.hpp> | |
#include <boost/ptr_container/clone_allocator.hpp> | |
#include <boost/ptr_container/nullable.hpp> | |
#ifdef BOOST_NO_SFINAE | |
#else | |
#include <boost/range/functions.hpp> | |
#endif | |
#include <boost/config.hpp> | |
#include <boost/iterator/reverse_iterator.hpp> | |
#include <boost/range/iterator.hpp> | |
#include <boost/utility/enable_if.hpp> | |
#include <boost/type_traits/is_pointer.hpp> | |
#include <boost/type_traits/is_integral.hpp> | |
#include <typeinfo> | |
#include <memory> | |
#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) | |
#pragma warning(push) | |
#pragma warning(disable:4127) | |
#endif | |
namespace boost | |
{ | |
namespace ptr_container_detail | |
{ | |
template< class CloneAllocator > | |
struct clone_deleter | |
{ | |
template< class T > | |
void operator()( const T* p ) const | |
{ | |
CloneAllocator::deallocate_clone( p ); | |
} | |
}; | |
template< class T > | |
struct is_pointer_or_integral | |
{ | |
BOOST_STATIC_CONSTANT(bool, value = is_pointer<T>::value || is_integral<T>::value ); | |
}; | |
struct is_pointer_or_integral_tag {}; | |
struct is_range_tag {}; | |
struct sequence_tag {}; | |
struct fixed_length_sequence_tag : sequence_tag {}; | |
struct associative_container_tag {}; | |
struct ordered_associative_container_tag : associative_container_tag {}; | |
struct unordered_associative_container_tag : associative_container_tag {}; | |
template | |
< | |
class Config, | |
class CloneAllocator | |
> | |
class reversible_ptr_container | |
{ | |
private: | |
BOOST_STATIC_CONSTANT( bool, allow_null = Config::allow_null ); | |
typedef BOOST_DEDUCED_TYPENAME Config::value_type Ty_; | |
template< bool allow_null_values > | |
struct null_clone_allocator | |
{ | |
template< class Iter > | |
static Ty_* allocate_clone_from_iterator( Iter i ) | |
{ | |
return allocate_clone( Config::get_const_pointer( i ) ); | |
} | |
static Ty_* allocate_clone( const Ty_* x ) | |
{ | |
if( allow_null_values ) | |
{ | |
if( x == 0 ) | |
return 0; | |
} | |
else | |
{ | |
BOOST_ASSERT( x != 0 && "Cannot insert clone of null!" ); | |
} | |
Ty_* res = CloneAllocator::allocate_clone( *x ); | |
BOOST_ASSERT( typeid(*res) == typeid(*x) && | |
"CloneAllocator::allocate_clone() does not clone the " | |
"object properly. Check that new_clone() is implemented" | |
" correctly" ); | |
return res; | |
} | |
static void deallocate_clone( const Ty_* x ) | |
{ | |
if( allow_null_values ) | |
{ | |
if( x == 0 ) | |
return; | |
} | |
CloneAllocator::deallocate_clone( x ); | |
} | |
}; | |
typedef BOOST_DEDUCED_TYPENAME Config::void_container_type Cont; | |
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) | |
typedef null_clone_allocator<reversible_ptr_container::allow_null> | |
null_cloner_type; | |
#else | |
typedef null_clone_allocator<allow_null> null_cloner_type; | |
#endif | |
typedef clone_deleter<null_cloner_type> Deleter; | |
Cont c_; | |
public: | |
Cont& base() { return c_; } | |
protected: // having this public could break encapsulation | |
const Cont& base() const { return c_; } | |
public: // typedefs | |
typedef Ty_* value_type; | |
typedef Ty_* pointer; | |
typedef Ty_& reference; | |
typedef const Ty_& const_reference; | |
typedef BOOST_DEDUCED_TYPENAME Config::iterator | |
iterator; | |
typedef BOOST_DEDUCED_TYPENAME Config::const_iterator | |
const_iterator; | |
typedef boost::reverse_iterator< iterator > | |
reverse_iterator; | |
typedef boost::reverse_iterator< const_iterator > | |
const_reverse_iterator; | |
typedef BOOST_DEDUCED_TYPENAME Cont::difference_type | |
difference_type; | |
typedef BOOST_DEDUCED_TYPENAME Cont::size_type | |
size_type; | |
typedef BOOST_DEDUCED_TYPENAME Config::allocator_type | |
allocator_type; | |
typedef CloneAllocator clone_allocator_type; | |
typedef ptr_container_detail::static_move_ptr<Ty_,Deleter> | |
auto_type; | |
protected: | |
typedef ptr_container_detail::scoped_deleter<Ty_,null_cloner_type> | |
scoped_deleter; | |
typedef BOOST_DEDUCED_TYPENAME Cont::iterator | |
ptr_iterator; | |
typedef BOOST_DEDUCED_TYPENAME Cont::const_iterator | |
ptr_const_iterator; | |
private: | |
template< class InputIterator > | |
void copy( InputIterator first, InputIterator last ) | |
{ | |
std::copy( first, last, begin() ); | |
} | |
void copy( const reversible_ptr_container& r ) | |
{ | |
copy( r.begin(), r.end() ); | |
} | |
void copy_clones_and_release( scoped_deleter& sd ) // nothrow | |
{ | |
BOOST_ASSERT( size_type( std::distance( sd.begin(), sd.end() ) ) == c_.size() ); | |
std::copy( sd.begin(), sd.end(), c_.begin() ); | |
sd.release(); | |
} | |
template< class ForwardIterator > | |
void clone_assign( ForwardIterator first, | |
ForwardIterator last ) // strong | |
{ | |
BOOST_ASSERT( first != last ); | |
scoped_deleter sd( first, last ); // strong | |
copy_clones_and_release( sd ); // nothrow | |
} | |
template< class ForwardIterator > | |
void clone_back_insert( ForwardIterator first, | |
ForwardIterator last ) | |
{ | |
BOOST_ASSERT( first != last ); | |
scoped_deleter sd( first, last ); | |
insert_clones_and_release( sd, end() ); | |
} | |
void remove_all() | |
{ | |
remove( begin(), end() ); | |
} | |
protected: | |
void insert_clones_and_release( scoped_deleter& sd, | |
iterator where ) // strong | |
{ | |
// | |
// 'c_.insert' always provides the strong guarantee for T* elements | |
// since a copy constructor of a pointer cannot throw | |
// | |
c_.insert( where.base(), | |
sd.begin(), sd.end() ); | |
sd.release(); | |
} | |
void insert_clones_and_release( scoped_deleter& sd ) // strong | |
{ | |
c_.insert( sd.begin(), sd.end() ); | |
sd.release(); | |
} | |
template< class U > | |
void remove( U* ptr ) | |
{ | |
null_policy_deallocate_clone( ptr ); | |
} | |
template< class I > | |
void remove( I i ) | |
{ | |
null_policy_deallocate_clone( Config::get_const_pointer(i) ); | |
} | |
template< class I > | |
void remove( I first, I last ) | |
{ | |
for( ; first != last; ++first ) | |
remove( first ); | |
} | |
static void enforce_null_policy( const Ty_* x, const char* msg ) | |
{ | |
if( !allow_null ) | |
{ | |
BOOST_PTR_CONTAINER_THROW_EXCEPTION( 0 == x && "null not allowed", | |
bad_pointer, msg ); | |
} | |
} | |
static Ty_* null_policy_allocate_clone( const Ty_* x ) | |
{ | |
return null_cloner_type::allocate_clone( x ); | |
} | |
static void null_policy_deallocate_clone( const Ty_* x ) | |
{ | |
null_cloner_type::deallocate_clone( x ); | |
} | |
private: | |
template< class ForwardIterator > | |
ForwardIterator advance( ForwardIterator begin, size_type n ) | |
{ | |
ForwardIterator iter = begin; | |
std::advance( iter, n ); | |
return iter; | |
} | |
template< class I > | |
void constructor_impl( I first, I last, std::input_iterator_tag ) // basic | |
{ | |
while( first != last ) | |
{ | |
insert( end(), null_cloner_type::allocate_clone_from_iterator(first) ); | |
++first; | |
} | |
} | |
template< class I > | |
void constructor_impl( I first, I last, std::forward_iterator_tag ) // strong | |
{ | |
if( first == last ) | |
return; | |
clone_back_insert( first, last ); | |
} | |
template< class I > | |
void associative_constructor_impl( I first, I last ) // strong | |
{ | |
if( first == last ) | |
return; | |
scoped_deleter sd( first, last ); | |
insert_clones_and_release( sd ); | |
} | |
public: // foundation! should be protected! | |
reversible_ptr_container() | |
{ } | |
template< class SizeType > | |
reversible_ptr_container( SizeType n, unordered_associative_container_tag ) | |
: c_( n ) | |
{ } | |
template< class SizeType > | |
reversible_ptr_container( SizeType n, fixed_length_sequence_tag ) | |
: c_( n ) | |
{ } | |
template< class SizeType > | |
reversible_ptr_container( SizeType n, const allocator_type& a, | |
fixed_length_sequence_tag ) | |
: c_( n, a ) | |
{ } | |
explicit reversible_ptr_container( const allocator_type& a ) | |
: c_( a ) | |
{ } | |
template< class PtrContainer > | |
explicit reversible_ptr_container( std::auto_ptr<PtrContainer> clone ) | |
{ | |
swap( *clone ); | |
} | |
reversible_ptr_container( const reversible_ptr_container& r ) | |
{ | |
constructor_impl( r.begin(), r.end(), std::forward_iterator_tag() ); | |
} | |
template< class C, class V > | |
reversible_ptr_container( const reversible_ptr_container<C,V>& r ) | |
{ | |
constructor_impl( r.begin(), r.end(), std::forward_iterator_tag() ); | |
} | |
template< class PtrContainer > | |
reversible_ptr_container& operator=( std::auto_ptr<PtrContainer> clone ) // nothrow | |
{ | |
swap( *clone ); | |
return *this; | |
} | |
reversible_ptr_container& operator=( reversible_ptr_container r ) // strong | |
{ | |
swap( r ); | |
return *this; | |
} | |
// overhead: null-initilization of container pointer (very cheap compared to cloning) | |
// overhead: 1 heap allocation (very cheap compared to cloning) | |
template< class InputIterator > | |
reversible_ptr_container( InputIterator first, | |
InputIterator last, | |
const allocator_type& a = allocator_type() ) // basic, strong | |
: c_( a ) | |
{ | |
constructor_impl( first, last, | |
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) | |
#else | |
BOOST_DEDUCED_TYPENAME | |
#endif | |
iterator_category<InputIterator>::type() ); | |
} | |
template< class Compare > | |
reversible_ptr_container( const Compare& comp, | |
const allocator_type& a ) | |
: c_( comp, a ) {} | |
template< class ForwardIterator > | |
reversible_ptr_container( ForwardIterator first, | |
ForwardIterator last, | |
fixed_length_sequence_tag ) | |
: c_( std::distance(first,last) ) | |
{ | |
constructor_impl( first, last, | |
std::forward_iterator_tag() ); | |
} | |
template< class SizeType, class InputIterator > | |
reversible_ptr_container( SizeType n, | |
InputIterator first, | |
InputIterator last, | |
fixed_length_sequence_tag ) | |
: c_( n ) | |
{ | |
constructor_impl( first, last, | |
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) | |
#else | |
BOOST_DEDUCED_TYPENAME | |
#endif | |
iterator_category<InputIterator>::type() ); | |
} | |
template< class Compare > | |
reversible_ptr_container( const Compare& comp, | |
const allocator_type& a, | |
associative_container_tag ) | |
: c_( comp, a ) | |
{ } | |
template< class InputIterator > | |
reversible_ptr_container( InputIterator first, | |
InputIterator last, | |
associative_container_tag ) | |
{ | |
associative_constructor_impl( first, last ); | |
} | |
template< class InputIterator, class Compare > | |
reversible_ptr_container( InputIterator first, | |
InputIterator last, | |
const Compare& comp, | |
const allocator_type& a, | |
associative_container_tag ) | |
: c_( comp, a ) | |
{ | |
associative_constructor_impl( first, last ); | |
} | |
explicit reversible_ptr_container( size_type n ) | |
: c_( n ) {} | |
template< class Hash, class Pred > | |
reversible_ptr_container( const Hash& h, | |
const Pred& pred, | |
const allocator_type& a ) | |
: c_( h, pred, a ) {} | |
template< class InputIterator, class Hash, class Pred > | |
reversible_ptr_container( InputIterator first, | |
InputIterator last, | |
const Hash& h, | |
const Pred& pred, | |
const allocator_type& a ) | |
: c_( h, pred, a ) | |
{ | |
associative_constructor_impl( first, last ); | |
} | |
public: | |
~reversible_ptr_container() | |
{ | |
remove_all(); | |
} | |
public: | |
allocator_type get_allocator() const | |
{ | |
return c_.get_allocator(); | |
} | |
public: // container requirements | |
iterator begin() | |
{ return iterator( c_.begin() ); } | |
const_iterator begin() const | |
{ return const_iterator( c_.begin() ); } | |
iterator end() | |
{ return iterator( c_.end() ); } | |
const_iterator end() const | |
{ return const_iterator( c_.end() ); } | |
reverse_iterator rbegin() | |
{ return reverse_iterator( this->end() ); } | |
const_reverse_iterator rbegin() const | |
{ return const_reverse_iterator( this->end() ); } | |
reverse_iterator rend() | |
{ return reverse_iterator( this->begin() ); } | |
const_reverse_iterator rend() const | |
{ return const_reverse_iterator( this->begin() ); } | |
const_iterator cbegin() const | |
{ return const_iterator( c_.begin() ); } | |
const_iterator cend() const | |
{ return const_iterator( c_.end() ); } | |
const_reverse_iterator crbegin() const | |
{ return const_reverse_iterator( this->end() ); } | |
const_reverse_iterator crend() const | |
{ return const_reverse_iterator( this->begin() ); } | |
void swap( reversible_ptr_container& r ) // nothrow | |
{ | |
c_.swap( r.c_ ); | |
} | |
size_type size() const // nothrow | |
{ | |
return c_.size(); | |
} | |
size_type max_size() const // nothrow | |
{ | |
return c_.max_size(); | |
} | |
bool empty() const // nothrow | |
{ | |
return c_.empty(); | |
} | |
public: // optional container requirements | |
bool operator==( const reversible_ptr_container& r ) const // nothrow | |
{ | |
if( size() != r.size() ) | |
return false; | |
else | |
return std::equal( begin(), end(), r.begin() ); | |
} | |
bool operator!=( const reversible_ptr_container& r ) const // nothrow | |
{ | |
return !(*this == r); | |
} | |
bool operator<( const reversible_ptr_container& r ) const // nothrow | |
{ | |
return std::lexicographical_compare( begin(), end(), r.begin(), r.end() ); | |
} | |
bool operator<=( const reversible_ptr_container& r ) const // nothrow | |
{ | |
return !(r < *this); | |
} | |
bool operator>( const reversible_ptr_container& r ) const // nothrow | |
{ | |
return r < *this; | |
} | |
bool operator>=( const reversible_ptr_container& r ) const // nothrow | |
{ | |
return !(*this < r); | |
} | |
public: // modifiers | |
iterator insert( iterator before, Ty_* x ) | |
{ | |
enforce_null_policy( x, "Null pointer in 'insert()'" ); | |
auto_type ptr( x ); // nothrow | |
iterator res( c_.insert( before.base(), x ) ); // strong, commit | |
ptr.release(); // nothrow | |
return res; | |
} | |
template< class U > | |
iterator insert( iterator before, std::auto_ptr<U> x ) | |
{ | |
return insert( before, x.release() ); | |
} | |
iterator erase( iterator x ) // nothrow | |
{ | |
BOOST_ASSERT( !empty() ); | |
BOOST_ASSERT( x != end() ); | |
remove( x ); | |
return iterator( c_.erase( x.base() ) ); | |
} | |
iterator erase( iterator first, iterator last ) // nothrow | |
{ | |
remove( first, last ); | |
return iterator( c_.erase( first.base(), | |
last.base() ) ); | |
} | |
template< class Range > | |
iterator erase( const Range& r ) | |
{ | |
return erase( boost::begin(r), boost::end(r) ); | |
} | |
void clear() | |
{ | |
remove_all(); | |
c_.clear(); | |
} | |
public: // access interface | |
auto_type release( iterator where ) | |
{ | |
BOOST_ASSERT( where != end() ); | |
BOOST_PTR_CONTAINER_THROW_EXCEPTION( empty(), bad_ptr_container_operation, | |
"'release()' on empty container" ); | |
auto_type ptr( Config::get_pointer( where ) ); // nothrow | |
c_.erase( where.base() ); // nothrow | |
return boost::ptr_container_detail::move( ptr ); | |
} | |
auto_type replace( iterator where, Ty_* x ) // strong | |
{ | |
BOOST_ASSERT( where != end() ); | |
enforce_null_policy( x, "Null pointer in 'replace()'" ); | |
auto_type ptr( x ); | |
BOOST_PTR_CONTAINER_THROW_EXCEPTION( empty(), bad_ptr_container_operation, | |
"'replace()' on empty container" ); | |
auto_type old( Config::get_pointer( where ) ); // nothrow | |
const_cast<void*&>(*where.base()) = ptr.release(); | |
return boost::ptr_container_detail::move( old ); | |
} | |
template< class U > | |
auto_type replace( iterator where, std::auto_ptr<U> x ) | |
{ | |
return replace( where, x.release() ); | |
} | |
auto_type replace( size_type idx, Ty_* x ) // strong | |
{ | |
enforce_null_policy( x, "Null pointer in 'replace()'" ); | |
auto_type ptr( x ); | |
BOOST_PTR_CONTAINER_THROW_EXCEPTION( idx >= size(), bad_index, | |
"'replace()' out of bounds" ); | |
auto_type old( static_cast<Ty_*>( c_[idx] ) ); // nothrow | |
c_[idx] = ptr.release(); // nothrow, commit | |
return boost::ptr_container_detail::move( old ); | |
} | |
template< class U > | |
auto_type replace( size_type idx, std::auto_ptr<U> x ) | |
{ | |
return replace( idx, x.release() ); | |
} | |
}; // 'reversible_ptr_container' | |
#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) | |
#define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \ | |
typename base_type::auto_type \ | |
release( typename base_type::iterator i ) \ | |
{ \ | |
return boost::ptr_container_detail::move(base_type::release(i)); \ | |
} | |
#else | |
#define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \ | |
using base_type::release; | |
#endif | |
// | |
// two-phase lookup of template functions | |
// is buggy on most compilers, so we use a macro instead | |
// | |
#define BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type ) \ | |
explicit PC( std::auto_ptr<this_type> r ) \ | |
: base_type ( r ) { } \ | |
\ | |
PC& operator=( std::auto_ptr<this_type> r ) \ | |
{ \ | |
base_type::operator=( r ); \ | |
return *this; \ | |
} \ | |
\ | |
std::auto_ptr<this_type> release() \ | |
{ \ | |
std::auto_ptr<this_type> ptr( new this_type );\ | |
this->swap( *ptr ); \ | |
return ptr; \ | |
} \ | |
BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \ | |
\ | |
std::auto_ptr<this_type> clone() const \ | |
{ \ | |
return std::auto_ptr<this_type>( new this_type( this->begin(), this->end() ) ); \ | |
} | |
#define BOOST_PTR_CONTAINER_DEFINE_COPY_CONSTRUCTORS( PC, base_type ) \ | |
\ | |
template< class U > \ | |
PC( const PC<U>& r ) : base_type( r ) { } \ | |
\ | |
PC& operator=( PC r ) \ | |
{ \ | |
this->swap( r ); \ | |
return *this; \ | |
} \ | |
#define BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type ) \ | |
typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator; \ | |
typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type; \ | |
typedef BOOST_DEDUCED_TYPENAME base_type::const_reference const_reference; \ | |
typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type allocator_type; \ | |
PC() {} \ | |
explicit PC( const allocator_type& a ) : base_type(a) {} \ | |
template< class InputIterator > \ | |
PC( InputIterator first, InputIterator last ) : base_type( first, last ) {} \ | |
template< class InputIterator > \ | |
PC( InputIterator first, InputIterator last, \ | |
const allocator_type& a ) : base_type( first, last, a ) {} | |
#define BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type ) \ | |
BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type ) \ | |
BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type ) | |
#define BOOST_PTR_CONTAINER_DEFINE_SEQEUENCE_MEMBERS( PC, base_type, this_type ) \ | |
BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type ) \ | |
BOOST_PTR_CONTAINER_DEFINE_COPY_CONSTRUCTORS( PC, base_type ) | |
} // namespace 'ptr_container_detail' | |
// | |
// @remark: expose movability of internal move-pointer | |
// | |
namespace ptr_container | |
{ | |
using ptr_container_detail::move; | |
} | |
} // namespace 'boost' | |
#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) | |
#pragma warning(pop) | |
#endif | |
#endif |