Chris@16: // Copyright Thorsten Ottosen, 2009.
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_SIGNALS2_DETAIL_AUTO_BUFFER_HPP_25_02_2009
Chris@16: #define BOOST_SIGNALS2_DETAIL_AUTO_BUFFER_HPP_25_02_2009
Chris@16: 
Chris@16: #include <boost/detail/workaround.hpp>
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: # pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
Chris@16: #pragma warning(push)
Chris@16: #pragma warning(disable:4996)
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/iterator/reverse_iterator.hpp>
Chris@16: #include <boost/iterator/iterator_traits.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/multi_index/detail/scope_guard.hpp>
Chris@16: #include <boost/swap.hpp>
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: #include <boost/type_traits/aligned_storage.hpp>
Chris@16: #include <boost/type_traits/alignment_of.hpp>
Chris@16: #include <boost/type_traits/has_nothrow_copy.hpp>
Chris@16: #include <boost/type_traits/has_nothrow_assign.hpp>
Chris@16: #include <boost/type_traits/has_trivial_assign.hpp>
Chris@16: #include <boost/type_traits/has_trivial_constructor.hpp>
Chris@16: #include <boost/type_traits/has_trivial_destructor.hpp>
Chris@16: #include <algorithm>
Chris@16: #include <cstring>
Chris@16: #include <iterator>
Chris@16: #include <memory>
Chris@16: #include <stdexcept>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: namespace signals2
Chris@16: {
Chris@16: namespace detail
Chris@16: {
Chris@16:     //
Chris@16:     // Policies for creating the stack buffer.
Chris@16:     //
Chris@16:     template< unsigned N >
Chris@16:     struct store_n_objects
Chris@16:     {
Chris@16:         BOOST_STATIC_CONSTANT( unsigned, value = N );
Chris@16:     };
Chris@16: 
Chris@16:     template< unsigned N >
Chris@16:     struct store_n_bytes
Chris@16:     {
Chris@16:         BOOST_STATIC_CONSTANT( unsigned, value = N );
Chris@16:     };
Chris@16: 
Chris@16:     namespace auto_buffer_detail
Chris@16:     {
Chris@16:         template< class Policy, class T >
Chris@16:         struct compute_buffer_size
Chris@16:         {
Chris@16:             BOOST_STATIC_CONSTANT( unsigned, value = Policy::value * sizeof(T) );
Chris@16:         };
Chris@16: 
Chris@16:         template< unsigned N, class T >
Chris@16:         struct compute_buffer_size< store_n_bytes<N>, T >
Chris@16:         {
Chris@16:             BOOST_STATIC_CONSTANT( unsigned, value = N );
Chris@16:         };
Chris@16: 
Chris@16:         template< class Policy, class T >
Chris@16:         struct compute_buffer_objects
Chris@16:         {
Chris@16:             BOOST_STATIC_CONSTANT( unsigned, value = Policy::value );
Chris@16:         };
Chris@16: 
Chris@16:         template< unsigned N, class T >
Chris@16:         struct compute_buffer_objects< store_n_bytes<N>, T >
Chris@16:         {
Chris@16:             BOOST_STATIC_CONSTANT( unsigned, value = N / sizeof(T) );
Chris@16:         };
Chris@16:     }
Chris@16: 
Chris@16:     struct default_grow_policy
Chris@16:     {
Chris@16:         template< class SizeType >
Chris@16:         static SizeType new_capacity( SizeType capacity )
Chris@16:         {
Chris@16:             //
Chris@16:             // @remark: we grow the capacity quite agressively.
Chris@16:             //          this is justified since we aim to minimize
Chris@16:             //          heap-allocations, and because we mostly use
Chris@16:             //          the buffer locally.
Chris@16:             return capacity * 4u;
Chris@16:         }
Chris@16: 
Chris@16:         template< class SizeType >
Chris@16:         static bool should_shrink( SizeType size, SizeType capacity )
Chris@16:         {
Chris@16:             //
Chris@16:             // @remark: when defining a new grow policy, one might
Chris@16:             //          choose that if the waated space is less
Chris@16:             //          than a certain percentage, then it is of
Chris@16:             //          little use to shrink.
Chris@16:             //
Chris@16:             return true;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template< class T,
Chris@16:               class StackBufferPolicy = store_n_objects<256>,
Chris@16:               class GrowPolicy        = default_grow_policy,
Chris@16:               class Allocator         = std::allocator<T> >
Chris@16:     class auto_buffer;
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     template
Chris@16:     <
Chris@16:         class T,
Chris@16:         class StackBufferPolicy,
Chris@16:         class GrowPolicy,
Chris@16:         class Allocator
Chris@16:     >
Chris@16:     class auto_buffer : Allocator
Chris@16:     {
Chris@16:     private:
Chris@16:         enum { N = auto_buffer_detail::
Chris@16:                    compute_buffer_objects<StackBufferPolicy,T>::value };
Chris@16: 
Chris@16:         BOOST_STATIC_CONSTANT( bool, is_stack_buffer_empty = N == 0u );
Chris@16: 
Chris@16:         typedef auto_buffer<T, store_n_objects<0>, GrowPolicy, Allocator>
Chris@16:                                                          local_buffer;
Chris@16: 
Chris@16:     public:
Chris@16:         typedef Allocator                                allocator_type;
Chris@16:         typedef T                                        value_type;
Chris@16:         typedef typename Allocator::size_type            size_type;
Chris@16:         typedef typename Allocator::difference_type      difference_type;
Chris@16:         typedef T*                                       pointer;
Chris@16:         typedef typename Allocator::pointer              allocator_pointer;
Chris@16:         typedef const T*                                 const_pointer;
Chris@16:         typedef T&                                       reference;
Chris@16:         typedef const T&                                 const_reference;
Chris@16:         typedef pointer                                  iterator;
Chris@16:         typedef const_pointer                            const_iterator;
Chris@16:         typedef boost::reverse_iterator<iterator>        reverse_iterator;
Chris@16:         typedef boost::reverse_iterator<const_iterator>  const_reverse_iterator;
Chris@16:         typedef typename boost::mpl::if_c< boost::has_trivial_assign<T>::value
Chris@16:                                            && sizeof(T) <= sizeof(long double),
Chris@16:                                           const value_type,
Chris@16:                                           const_reference >::type
Chris@16:                                                       optimized_const_reference;
Chris@16:     private:
Chris@16: 
Chris@16:         pointer allocate( size_type capacity_arg )
Chris@16:         {
Chris@16:             if( capacity_arg > N )
Chris@16:                 return &*get_allocator().allocate( capacity_arg );
Chris@16:             else
Chris@16:                 return static_cast<T*>( members_.address() );
Chris@16:         }
Chris@16: 
Chris@16:         void deallocate( pointer where, size_type capacity_arg )
Chris@16:         {
Chris@16:             if( capacity_arg <= N )
Chris@16:                 return;
Chris@16:             get_allocator().deallocate( allocator_pointer(where), capacity_arg );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I >
Chris@16:         static void copy_impl( I begin, I end, pointer where, std::random_access_iterator_tag )
Chris@16:         {
Chris@16:             copy_rai( begin, end, where, boost::has_trivial_assign<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         static void copy_rai( const T* begin, const T* end,
Chris@16:                               pointer where, const boost::true_type& )
Chris@16:         {
Chris@16:             std::memcpy( where, begin, sizeof(T) * std::distance(begin,end) );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I, bool b >
Chris@16:         static void copy_rai( I begin, I end,
Chris@16:                               pointer where, const boost::integral_constant<bool, b>& )
Chris@16:         {
Chris@16:             std::uninitialized_copy( begin, end, where );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I >
Chris@16:         static void copy_impl( I begin, I end, pointer where, std::bidirectional_iterator_tag )
Chris@16:         {
Chris@16:             std::uninitialized_copy( begin, end, where );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I >
Chris@16:         static void copy_impl( I begin, I end, pointer where )
Chris@16:         {
Chris@16:             copy_impl( begin, end, where,
Chris@16:                        typename std::iterator_traits<I>::iterator_category() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I, class I2 >
Chris@16:         static void assign_impl( I begin, I end, I2 where )
Chris@16:         {
Chris@16:             assign_impl( begin, end, where, boost::has_trivial_assign<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I, class I2 >
Chris@16:         static void assign_impl( I begin, I end, I2 where, const boost::true_type& )
Chris@16:         {
Chris@16:             std::memcpy( where, begin, sizeof(T) * std::distance(begin,end) );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I, class I2 >
Chris@16:         static void assign_impl( I begin, I end, I2 where, const boost::false_type& )
Chris@16:         {
Chris@16:             for( ; begin != end; ++begin, ++where )
Chris@16:                 *where = *begin;
Chris@16:         }
Chris@16: 
Chris@16:         void unchecked_push_back_n( size_type n, const boost::true_type& )
Chris@16:         {
Chris@16:             std::uninitialized_fill( end(), end() + n, T() );
Chris@16:             size_ += n;
Chris@16:         }
Chris@16: 
Chris@16:         void unchecked_push_back_n( size_type n, const boost::false_type& )
Chris@16:         {
Chris@16:             for( size_type i = 0u; i < n; ++i )
Chris@16:                 unchecked_push_back();
Chris@16:         }
Chris@16: 
Chris@16:         void auto_buffer_destroy( pointer where, const boost::false_type& )
Chris@16:         {
Chris@16:             (*where).~T();
Chris@16:         }
Chris@16: 
Chris@16:         void auto_buffer_destroy( pointer, const boost::true_type& )
Chris@16:         { }
Chris@16: 
Chris@16:         void auto_buffer_destroy( pointer where )
Chris@16:         {
Chris@16:             auto_buffer_destroy( where, boost::has_trivial_destructor<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         void destroy_back_n( size_type n, const boost::false_type& )
Chris@16:         {
Chris@16:             BOOST_ASSERT( n > 0 );
Chris@16:             pointer buffer  = buffer_ + size_ - 1u;
Chris@16:             pointer new_end = buffer - n;
Chris@16:             for( ; buffer > new_end; --buffer )
Chris@16:                 auto_buffer_destroy( buffer );
Chris@16:         }
Chris@16: 
Chris@16:         void destroy_back_n( size_type n, const boost::true_type& )
Chris@16:         { }
Chris@16: 
Chris@16:         void destroy_back_n( size_type n )
Chris@16:         {
Chris@16:             destroy_back_n( n, boost::has_trivial_destructor<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         void auto_buffer_destroy( const boost::false_type& x )
Chris@16:         {
Chris@16:             if( size_ )
Chris@16:                 destroy_back_n( size_, x );
Chris@16:             deallocate( buffer_, members_.capacity_ );
Chris@16:         }
Chris@16: 
Chris@16:         void auto_buffer_destroy( const boost::true_type& )
Chris@16:         {
Chris@16:             deallocate( buffer_, members_.capacity_ );
Chris@16:         }
Chris@16: 
Chris@16:         pointer move_to_new_buffer( size_type new_capacity, const boost::false_type& )
Chris@16:         {
Chris@16:             pointer new_buffer = allocate( new_capacity ); // strong
Chris@16:             boost::multi_index::detail::scope_guard guard =
Chris@16:                 boost::multi_index::detail::make_obj_guard( *this,
Chris@16:                                                             &auto_buffer::deallocate,
Chris@16:                                                             new_buffer,
Chris@16:                                                             new_capacity );
Chris@16:             copy_impl( begin(), end(), new_buffer ); // strong
Chris@16:             guard.dismiss();                         // nothrow
Chris@16:             return new_buffer;
Chris@16:         }
Chris@16: 
Chris@16:         pointer move_to_new_buffer( size_type new_capacity, const boost::true_type& )
Chris@16:         {
Chris@16:             pointer new_buffer = allocate( new_capacity ); // strong
Chris@16:             copy_impl( begin(), end(), new_buffer );       // nothrow
Chris@16:             return new_buffer;
Chris@16:         }
Chris@16: 
Chris@16:         void reserve_impl( size_type new_capacity )
Chris@16:         {
Chris@16:             pointer new_buffer = move_to_new_buffer( new_capacity,
Chris@16:                                                  boost::has_nothrow_copy<T>() );
Chris@16:             (*this).~auto_buffer();
Chris@16:             buffer_   = new_buffer;
Chris@16:             members_.capacity_ = new_capacity;
Chris@16:             BOOST_ASSERT( size_ <= members_.capacity_ );
Chris@16:         }
Chris@16: 
Chris@16:         size_type new_capacity_impl( size_type n )
Chris@16:         {
Chris@16:             BOOST_ASSERT( n > members_.capacity_ );
Chris@16:             size_type new_capacity = GrowPolicy::new_capacity( members_.capacity_ );
Chris@16:             // @todo: consider to check for allocator.max_size()
Chris@16:             return (std::max)(new_capacity,n);
Chris@16:         }
Chris@16: 
Chris@16:         static void swap_helper( auto_buffer& l, auto_buffer& r,
Chris@16:                                  const boost::true_type& )
Chris@16:         {
Chris@16:             BOOST_ASSERT( l.is_on_stack() && r.is_on_stack() );
Chris@16: 
Chris@16:             auto_buffer temp( l.begin(), l.end() );
Chris@16:             assign_impl( r.begin(), r.end(), l.begin() );
Chris@16:             assign_impl( temp.begin(), temp.end(), r.begin() );
Chris@16:             boost::swap( l.size_, r.size_ );
Chris@16:             boost::swap( l.members_.capacity_, r.members_.capacity_ );
Chris@16:         }
Chris@16: 
Chris@16:         static void swap_helper( auto_buffer& l, auto_buffer& r,
Chris@16:                                  const boost::false_type& )
Chris@16:         {
Chris@16:             BOOST_ASSERT( l.is_on_stack() && r.is_on_stack() );
Chris@16:             size_type min_size    = (std::min)(l.size_,r.size_);
Chris@16:             size_type max_size    = (std::max)(l.size_,r.size_);
Chris@16:             size_type diff        = max_size - min_size;
Chris@16:             auto_buffer* smallest = l.size_ == min_size ? &l : &r;
Chris@16:             auto_buffer* largest  = smallest == &l ? &r : &l;
Chris@16: 
Chris@16:             // @remark: the implementation below is not as fast
Chris@16:             //          as it could be if we assumed T had a default
Chris@16:             //          constructor.
Chris@16: 
Chris@16:             size_type i = 0u;
Chris@16:             for(  ; i < min_size; ++i )
Chris@16:                 boost::swap( (*smallest)[i], (*largest)[i] );
Chris@16: 
Chris@16:             for( ; i < max_size; ++i )
Chris@16:                 smallest->unchecked_push_back( (*largest)[i] );
Chris@16: 
Chris@16:             largest->pop_back_n( diff );
Chris@16:             boost::swap( l.members_.capacity_, r.members_.capacity_ );
Chris@16:         }
Chris@16: 
Chris@16:         void one_sided_swap( auto_buffer& temp ) // nothrow
Chris@16:         {
Chris@16:             BOOST_ASSERT( !temp.is_on_stack() );
Chris@16:             this->~auto_buffer();
Chris@16:             // @remark: must be nothrow
Chris@16:             get_allocator()    = temp.get_allocator();
Chris@16:             members_.capacity_ = temp.members_.capacity_;
Chris@16:             buffer_            = temp.buffer_;
Chris@16:             BOOST_ASSERT( temp.size_ >= size_ + 1u );
Chris@16:             size_              = temp.size_;
Chris@16:             temp.buffer_       = 0;
Chris@16:             BOOST_ASSERT( temp.is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I >
Chris@16:         void insert_impl( const_iterator before, I begin_arg, I end_arg,
Chris@16:                           std::input_iterator_tag )
Chris@16:         {
Chris@16:             for( ; begin_arg != end_arg; ++begin_arg )
Chris@16:             {
Chris@16:                 before = insert( before, *begin_arg );
Chris@16:                 ++before;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void grow_back( size_type n, const boost::true_type& )
Chris@16:         {
Chris@16:             BOOST_ASSERT( size_ + n <= members_.capacity_ );
Chris@16:             size_ += n;
Chris@16:         }
Chris@16: 
Chris@16:         void grow_back( size_type n, const boost::false_type& )
Chris@16:         {
Chris@16:             unchecked_push_back_n(n);
Chris@16:         }
Chris@16: 
Chris@16:         void grow_back( size_type n )
Chris@16:         {
Chris@16:             grow_back( n, boost::has_trivial_constructor<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         void grow_back_one( const boost::true_type& )
Chris@16:         {
Chris@16:             BOOST_ASSERT( size_ + 1 <= members_.capacity_ );
Chris@16:             size_ += 1;
Chris@16:         }
Chris@16: 
Chris@16:         void grow_back_one( const boost::false_type& )
Chris@16:         {
Chris@16:             unchecked_push_back();
Chris@16:         }
Chris@16: 
Chris@16:         void grow_back_one()
Chris@16:         {
Chris@16:             grow_back_one( boost::has_trivial_constructor<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class I >
Chris@16:         void insert_impl( const_iterator before, I begin_arg, I end_arg,
Chris@16:                           std::forward_iterator_tag )
Chris@16:         {
Chris@16:             difference_type n = std::distance(begin_arg, end_arg);
Chris@16: 
Chris@16:             if( size_ + n <= members_.capacity_ )
Chris@16:             {
Chris@16:                 bool is_back_insertion = before == cend();
Chris@16:                 if( !is_back_insertion )
Chris@16:                 {
Chris@16:                     grow_back( n );
Chris@16:                     iterator where = const_cast<T*>(before);
Chris@16:                     std::copy( before, cend() - n, where + n );
Chris@16:                     assign_impl( begin_arg, end_arg, where );
Chris@16:                 }
Chris@16:                 else
Chris@16:                 {
Chris@16:                     unchecked_push_back( begin_arg, end_arg );
Chris@16:                 }
Chris@16:                 BOOST_ASSERT( is_valid() );
Chris@16:                 return;
Chris@16:             }
Chris@16: 
Chris@16:             auto_buffer temp( new_capacity_impl( size_ + n ) );
Chris@16:             temp.unchecked_push_back( cbegin(), before );
Chris@16:             temp.unchecked_push_back( begin_arg, end_arg );
Chris@16:             temp.unchecked_push_back( before, cend() );
Chris@16:             one_sided_swap( temp );
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         bool is_valid() const // invariant
Chris@16:         {
Chris@16:             // @remark: allowed for N==0 and when
Chris@16:             //          using a locally instance
Chris@16:             //          in insert()/one_sided_swap()
Chris@16:             if( buffer_ == 0 )
Chris@16:                 return true;
Chris@16: 
Chris@16:             if( members_.capacity_ < N )
Chris@16:                 return false;
Chris@16: 
Chris@16:             if( !is_on_stack() && members_.capacity_ <= N )
Chris@16:                 return false;
Chris@16: 
Chris@16:             if( buffer_ == members_.address() )
Chris@16:                 if( members_.capacity_ > N )
Chris@16:                     return false;
Chris@16: 
Chris@16:             if( size_ > members_.capacity_ )
Chris@16:                 return false;
Chris@16: 
Chris@16:             return true;
Chris@16:         }
Chris@16: 
Chris@16:         auto_buffer()
Chris@16:             : members_( N ),
Chris@16:               buffer_( static_cast<T*>(members_.address()) ),
Chris@16:               size_( 0u )
Chris@16:         {
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         auto_buffer( const auto_buffer& r )
Chris@16:             : members_( (std::max)(r.size_,size_type(N)) ),
Chris@16:               buffer_( allocate( members_.capacity_ ) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             copy_impl( r.begin(), r.end(), buffer_ );
Chris@16:             size_ = r.size_;
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         auto_buffer& operator=( const auto_buffer& r ) // basic
Chris@16:         {
Chris@16:             if( this == &r )
Chris@16:                 return *this;
Chris@16: 
Chris@16:             difference_type diff = size_ - r.size_;
Chris@16:             if( diff >= 0 )
Chris@16:             {
Chris@16:                 pop_back_n( static_cast<size_type>(diff) );
Chris@16:                 assign_impl( r.begin(), r.end(), begin() );
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16:                 if( members_.capacity_ >= r.size() )
Chris@16:                 {
Chris@16:                     unchecked_push_back_n( static_cast<size_type>(-diff) );
Chris@16:                     assign_impl( r.begin(), r.end(), begin() );
Chris@16:                 }
Chris@16:                 else
Chris@16:                 {
Chris@16:                     // @remark: we release memory as early as possible
Chris@16:                     //          since we only give the basic guarantee
Chris@16:                     (*this).~auto_buffer();
Chris@16:                     buffer_ = 0;
Chris@16:                     pointer new_buffer = allocate( r.size() );
Chris@16:                     boost::multi_index::detail::scope_guard guard =
Chris@16:                         boost::multi_index::detail::make_obj_guard( *this,
Chris@16:                                                                     &auto_buffer::deallocate,
Chris@16:                                                                     new_buffer,
Chris@16:                                                                     r.size() );
Chris@16:                     copy_impl( r.begin(), r.end(), new_buffer );
Chris@16:                     guard.dismiss();
Chris@16:                     buffer_            = new_buffer;
Chris@16:                     members_.capacity_ = r.size();
Chris@16:                     size_              = members_.capacity_;
Chris@16:                 }
Chris@16:             }
Chris@16: 
Chris@16:             BOOST_ASSERT( size() == r.size() );
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         explicit auto_buffer( size_type capacity_arg )
Chris@16:             : members_( (std::max)(capacity_arg, size_type(N)) ),
Chris@16:               buffer_( allocate(members_.capacity_) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         auto_buffer( size_type size_arg, optimized_const_reference init_value )
Chris@16:             : members_( (std::max)(size_arg, size_type(N)) ),
Chris@16:               buffer_( allocate(members_.capacity_) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             std::uninitialized_fill( buffer_, buffer_ + size_arg, init_value );
Chris@16:             size_ = size_arg;
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         auto_buffer( size_type capacity_arg, const allocator_type& a )
Chris@16:             : allocator_type( a ),
Chris@16:               members_( (std::max)(capacity_arg, size_type(N)) ),
Chris@16:               buffer_( allocate(members_.capacity_) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         auto_buffer( size_type size_arg, optimized_const_reference init_value,
Chris@16:                      const allocator_type& a )
Chris@16:             : allocator_type( a ),
Chris@16:               members_( (std::max)(size_arg, size_type(N)) ),
Chris@16:               buffer_( allocate(members_.capacity_) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             std::uninitialized_fill( buffer_, buffer_ + size_arg, init_value );
Chris@16:             size_ = size_arg;
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class ForwardIterator >
Chris@16:         auto_buffer( ForwardIterator begin_arg, ForwardIterator end_arg )
Chris@16:             :
Chris@16:               members_( std::distance(begin_arg, end_arg) ),
Chris@16:               buffer_( allocate(members_.capacity_) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             copy_impl( begin_arg, end_arg, buffer_ );
Chris@16:             size_ = members_.capacity_;
Chris@16:             if( members_.capacity_ < N )
Chris@16:                 members_.capacity_ = N;
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class ForwardIterator >
Chris@16:         auto_buffer( ForwardIterator begin_arg, ForwardIterator end_arg,
Chris@16:                      const allocator_type& a )
Chris@16:             : allocator_type( a ),
Chris@16:               members_( std::distance(begin_arg, end_arg) ),
Chris@16:               buffer_( allocate(members_.capacity_) ),
Chris@16:               size_( 0 )
Chris@16:         {
Chris@16:             copy_impl( begin_arg, end_arg, buffer_ );
Chris@16:             size_ = members_.capacity_;
Chris@16:             if( members_.capacity_ < N )
Chris@16:                 members_.capacity_ = N;
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         ~auto_buffer()
Chris@16:         {
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:             if( buffer_ ) // do we need this check? Yes, but only
Chris@16:                 // for N = 0u + local instances in one_sided_swap()
Chris@16:                 auto_buffer_destroy( boost::has_trivial_destructor<T>() );
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         bool empty() const
Chris@16:         {
Chris@16:             return size_ == 0;
Chris@16:         }
Chris@16: 
Chris@16:         bool full() const
Chris@16:         {
Chris@16:             return size_ == members_.capacity_;
Chris@16:         }
Chris@16: 
Chris@16:         bool is_on_stack() const
Chris@16:         {
Chris@16:             return members_.capacity_ <= N;
Chris@16:         }
Chris@16: 
Chris@16:         size_type size() const
Chris@16:         {
Chris@16:             return size_;
Chris@16:         }
Chris@16: 
Chris@16:         size_type capacity() const
Chris@16:         {
Chris@16:             return members_.capacity_;
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         pointer data()
Chris@16:         {
Chris@16:             return buffer_;
Chris@16:         }
Chris@16: 
Chris@16:         const_pointer data() const
Chris@16:         {
Chris@16:             return buffer_;
Chris@16:         }
Chris@16: 
Chris@16:         allocator_type& get_allocator()
Chris@16:         {
Chris@16:             return static_cast<allocator_type&>(*this);
Chris@16:         }
Chris@16: 
Chris@16:         const allocator_type& get_allocator() const
Chris@16:         {
Chris@16:             return static_cast<const allocator_type&>(*this);
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         iterator begin()
Chris@16:         {
Chris@16:             return buffer_;
Chris@16:         }
Chris@16: 
Chris@16:         const_iterator begin() const
Chris@16:         {
Chris@16:             return buffer_;
Chris@16:         }
Chris@16: 
Chris@16:         iterator end()
Chris@16:         {
Chris@16:             return buffer_ + size_;
Chris@16:         }
Chris@16: 
Chris@16:         const_iterator end() const
Chris@16:         {
Chris@16:             return buffer_ + size_;
Chris@16:         }
Chris@16: 
Chris@16:         reverse_iterator rbegin()
Chris@16:         {
Chris@16:             return reverse_iterator(end());
Chris@16:         }
Chris@16: 
Chris@16:         const_reverse_iterator rbegin() const
Chris@16:         {
Chris@16:             return const_reverse_iterator(end());
Chris@16:         }
Chris@16: 
Chris@16:         reverse_iterator rend()
Chris@16:         {
Chris@16:             return reverse_iterator(begin());
Chris@16:         }
Chris@16: 
Chris@16:         const_reverse_iterator rend() const
Chris@16:         {
Chris@16:             return const_reverse_iterator(begin());
Chris@16:         }
Chris@16: 
Chris@16:         const_iterator cbegin() const
Chris@16:         {
Chris@16:             return const_cast<const auto_buffer*>(this)->begin();
Chris@16:         }
Chris@16: 
Chris@16:         const_iterator cend() const
Chris@16:         {
Chris@16:             return const_cast<const auto_buffer*>(this)->end();
Chris@16:         }
Chris@16: 
Chris@16:         const_reverse_iterator crbegin() const
Chris@16:         {
Chris@16:             return const_cast<const auto_buffer*>(this)->rbegin();
Chris@16:         }
Chris@16: 
Chris@16:         const_reverse_iterator crend() const
Chris@16:         {
Chris@16:             return const_cast<const auto_buffer*>(this)->rend();
Chris@16:         }
Chris@16: 
Chris@16:     public:
Chris@16:         reference front()
Chris@16:         {
Chris@16:             return buffer_[0];
Chris@16:         }
Chris@16: 
Chris@16:         optimized_const_reference front() const
Chris@16:         {
Chris@16:             return buffer_[0];
Chris@16:         }
Chris@16: 
Chris@16:         reference back()
Chris@16:         {
Chris@16:             return buffer_[size_-1];
Chris@16:         }
Chris@16: 
Chris@16:         optimized_const_reference back() const
Chris@16:         {
Chris@16:             return buffer_[size_-1];
Chris@16:         }
Chris@16: 
Chris@16:         reference operator[]( size_type n )
Chris@16:         {
Chris@16:             BOOST_ASSERT( n < size_ );
Chris@16:             return buffer_[n];
Chris@16:         }
Chris@16: 
Chris@16:         optimized_const_reference operator[]( size_type n ) const
Chris@16:         {
Chris@16:             BOOST_ASSERT( n < size_ );
Chris@16:             return buffer_[n];
Chris@16:         }
Chris@16: 
Chris@16:         void unchecked_push_back()
Chris@16:         {
Chris@16:             BOOST_ASSERT( !full() );
Chris@16:             new (buffer_ + size_) T;
Chris@16:             ++size_;
Chris@16:         }
Chris@16: 
Chris@16:         void unchecked_push_back_n( size_type n )
Chris@16:         {
Chris@16:             BOOST_ASSERT( size_ + n <= members_.capacity_ );
Chris@16:             unchecked_push_back_n( n, boost::has_trivial_assign<T>() );
Chris@16:         }
Chris@16: 
Chris@16:         void unchecked_push_back( optimized_const_reference x ) // non-growing
Chris@16:         {
Chris@16:             BOOST_ASSERT( !full() );
Chris@16:             new (buffer_ + size_) T( x );
Chris@16:             ++size_;
Chris@16:         }
Chris@16: 
Chris@16:         template< class ForwardIterator >
Chris@16:         void unchecked_push_back( ForwardIterator begin_arg,
Chris@16:                                   ForwardIterator end_arg ) // non-growing
Chris@16:         {
Chris@16:             BOOST_ASSERT( size_ + std::distance(begin_arg, end_arg) <= members_.capacity_ );
Chris@16:             copy_impl( begin_arg, end_arg, buffer_ + size_ );
Chris@16:             size_ += std::distance(begin_arg, end_arg);
Chris@16:         }
Chris@16: 
Chris@16:         void reserve_precisely( size_type n )
Chris@16:         {
Chris@16:             BOOST_ASSERT( members_.capacity_  >= N );
Chris@16: 
Chris@16:             if( n <= members_.capacity_ )
Chris@16:                 return;
Chris@16:             reserve_impl( n );
Chris@16:             BOOST_ASSERT( members_.capacity_ == n );
Chris@16:         }
Chris@16: 
Chris@16:         void reserve( size_type n ) // strong
Chris@16:         {
Chris@16:             BOOST_ASSERT( members_.capacity_  >= N );
Chris@16: 
Chris@16:             if( n <= members_.capacity_ )
Chris@16:                 return;
Chris@16: 
Chris@16:             reserve_impl( new_capacity_impl( n ) );
Chris@16:             BOOST_ASSERT( members_.capacity_ >= n );
Chris@16:         }
Chris@16: 
Chris@16:         void push_back()
Chris@16:         {
Chris@16:             if( size_ != members_.capacity_ )
Chris@16:             {
Chris@16:                 unchecked_push_back();
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16:                 reserve( size_ + 1u );
Chris@16:                 unchecked_push_back();
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void push_back( optimized_const_reference x )
Chris@16:         {
Chris@16:             if( size_ != members_.capacity_ )
Chris@16:             {
Chris@16:                 unchecked_push_back( x );
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16:                reserve( size_ + 1u );
Chris@16:                unchecked_push_back( x );
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         template< class ForwardIterator >
Chris@16:         void push_back( ForwardIterator begin_arg, ForwardIterator end_arg )
Chris@16:         {
Chris@16:             difference_type diff = std::distance(begin_arg, end_arg);
Chris@16:             if( size_ + diff > members_.capacity_ )
Chris@16:                 reserve( size_ + diff );
Chris@16:             unchecked_push_back( begin_arg, end_arg );
Chris@16:         }
Chris@16: 
Chris@16:         iterator insert( const_iterator before, optimized_const_reference x ) // basic
Chris@16:         {
Chris@16:             // @todo: consider if we want to support x in 'this'
Chris@16:             if( size_ < members_.capacity_ )
Chris@16:             {
Chris@16:                 bool is_back_insertion = before == cend();
Chris@16:                 iterator where = const_cast<T*>(before);
Chris@16: 
Chris@16:                 if( !is_back_insertion )
Chris@16:                 {
Chris@16:                     grow_back_one();
Chris@16:                     std::copy( before, cend() - 1u, where + 1u );
Chris@16:                     *where = x;
Chris@16:                     BOOST_ASSERT( is_valid() );
Chris@16:                  }
Chris@16:                 else
Chris@16:                 {
Chris@16:                     unchecked_push_back( x );
Chris@16:                 }
Chris@16:                 return where;
Chris@16:             }
Chris@16: 
Chris@16:             auto_buffer temp( new_capacity_impl( size_ + 1u ) );
Chris@16:             temp.unchecked_push_back( cbegin(), before );
Chris@16:             iterator result = temp.end();
Chris@16:             temp.unchecked_push_back( x );
Chris@16:             temp.unchecked_push_back( before, cend() );
Chris@16:             one_sided_swap( temp );
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:             return result;
Chris@16:         }
Chris@16: 
Chris@16:         void insert( const_iterator before, size_type n,
Chris@16:                      optimized_const_reference x )
Chris@16:         {
Chris@16:             // @todo: see problems above
Chris@16:             if( size_ + n <= members_.capacity_ )
Chris@16:             {
Chris@16:                 grow_back( n );
Chris@16:                 iterator where = const_cast<T*>(before);
Chris@16:                 std::copy( before, cend() - n, where + n );
Chris@16:                 std::fill( where, where + n, x );
Chris@16:                 BOOST_ASSERT( is_valid() );
Chris@16:                 return;
Chris@16:             }
Chris@16: 
Chris@16:             auto_buffer temp( new_capacity_impl( size_ + n ) );
Chris@16:             temp.unchecked_push_back( cbegin(), before );
Chris@16:             std::uninitialized_fill_n( temp.end(), n, x );
Chris@16:             temp.size_ += n;
Chris@16:             temp.unchecked_push_back( before, cend() );
Chris@16:             one_sided_swap( temp );
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:         template< class ForwardIterator >
Chris@16:         void insert( const_iterator before,
Chris@16:                      ForwardIterator begin_arg, ForwardIterator end_arg ) // basic
Chris@16:         {
Chris@16:             typedef typename std::iterator_traits<ForwardIterator>
Chris@16:                 ::iterator_category category;
Chris@16:             insert_impl( before, begin_arg, end_arg, category() );
Chris@16:         }
Chris@16: 
Chris@16:         void pop_back()
Chris@16:         {
Chris@16:             BOOST_ASSERT( !empty() );
Chris@16:             auto_buffer_destroy( buffer_ + size_ - 1, boost::has_trivial_destructor<T>() );
Chris@16:             --size_;
Chris@16:         }
Chris@16: 
Chris@16:         void pop_back_n( size_type n )
Chris@16:         {
Chris@16:             BOOST_ASSERT( n <= size_ );
Chris@16:             if( n )
Chris@16:             {
Chris@16:                 destroy_back_n( n );
Chris@16:                 size_ -= n;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void clear()
Chris@16:         {
Chris@16:             pop_back_n( size_ );
Chris@16:         }
Chris@16: 
Chris@16:         iterator erase( const_iterator where )
Chris@16:         {
Chris@16:             BOOST_ASSERT( !empty() );
Chris@16:             BOOST_ASSERT( cbegin() <= where );
Chris@16:             BOOST_ASSERT( cend() > where );
Chris@16: 
Chris@16:             unsigned elements = cend() - where - 1u;
Chris@16: 
Chris@16:             if( elements > 0u )
Chris@16:             {
Chris@16:                 const_iterator start = where + 1u;
Chris@16:                 std::copy( start, start + elements,
Chris@16:                            const_cast<T*>(where) );
Chris@16:             }
Chris@16:             pop_back();
Chris@16:             BOOST_ASSERT( !full() );
Chris@16:             iterator result = const_cast<T*>( where );
Chris@16:             BOOST_ASSERT( result <= end() );
Chris@16:             return result;
Chris@16:         }
Chris@16: 
Chris@16:         iterator erase( const_iterator from, const_iterator to )
Chris@16:         {
Chris@16:             BOOST_ASSERT( !(std::distance(from,to)>0) ||
Chris@16:                           !empty() );
Chris@16:             BOOST_ASSERT( cbegin() <= from );
Chris@16:             BOOST_ASSERT( cend() >= to );
Chris@16: 
Chris@16:             unsigned elements = std::distance(to,cend());
Chris@16: 
Chris@16:             if( elements > 0u )
Chris@16:             {
Chris@16:                 BOOST_ASSERT( elements > 0u );
Chris@16:                 std::copy( to, to + elements,
Chris@16:                            const_cast<T*>(from) );
Chris@16:             }
Chris@16:             pop_back_n( std::distance(from,to) );
Chris@16:             BOOST_ASSERT( !full() );
Chris@16:             iterator result = const_cast<T*>( from );
Chris@16:             BOOST_ASSERT( result <= end() );
Chris@16:             return result;
Chris@16:         }
Chris@16: 
Chris@16:         void shrink_to_fit()
Chris@16:         {
Chris@16:             if( is_on_stack() || !GrowPolicy::should_shrink(size_,members_.capacity_) )
Chris@16:                 return;
Chris@16: 
Chris@16:             reserve_impl( size_ );
Chris@16:             members_.capacity_ = (std::max)(size_type(N),members_.capacity_);
Chris@16:             BOOST_ASSERT( is_on_stack() || size_ == members_.capacity_ );
Chris@16:             BOOST_ASSERT( !is_on_stack() || size_ <= members_.capacity_ );
Chris@16:         }
Chris@16: 
Chris@16:         pointer uninitialized_grow( size_type n ) // strong
Chris@16:         {
Chris@16:             if( size_ + n <= members_.capacity_ )
Chris@16:                 reserve( size_ + n );
Chris@16: 
Chris@16:             pointer res = end();
Chris@16:             size_ += n;
Chris@16:             return res;
Chris@16:         }
Chris@16: 
Chris@16:         void uninitialized_shrink( size_type n ) // nothrow
Chris@16:         {
Chris@16:             // @remark: test for wrap-around
Chris@16:             BOOST_ASSERT( size_ - n <= members_.capacity_ );
Chris@16:             size_ -= n;
Chris@16:         }
Chris@16: 
Chris@16:         void uninitialized_resize( size_type n )
Chris@16:         {
Chris@16:             if( n > size() )
Chris@16:                 uninitialized_grow( n - size() );
Chris@16:             else if( n < size() )
Chris@16:                 uninitialized_shrink( size() - n );
Chris@16: 
Chris@16:            BOOST_ASSERT( size() == n );
Chris@16:         }
Chris@16: 
Chris@16:         // nothrow  - if both buffer are on the heap, or
Chris@16:         //          - if one buffer is on the heap and one has
Chris@16:         //            'has_allocated_buffer() == false', or
Chris@16:         //          - if copy-construction cannot throw
Chris@16:         // basic    - otherwise (better guarantee impossible)
Chris@16:         // requirement: the allocator must be no-throw-swappable
Chris@16:         void swap( auto_buffer& r )
Chris@16:         {
Chris@16:             bool on_stack      = is_on_stack();
Chris@16:             bool r_on_stack    = r.is_on_stack();
Chris@16:             bool both_on_heap  = !on_stack && !r_on_stack;
Chris@16:             if( both_on_heap )
Chris@16:             {
Chris@16:                 boost::swap( get_allocator(), r.get_allocator() );
Chris@16:                 boost::swap( members_.capacity_, r.members_.capacity_ );
Chris@16:                 boost::swap( buffer_, r.buffer_ );
Chris@16:                 boost::swap( size_, r.size_ );
Chris@16:                 BOOST_ASSERT( is_valid() );
Chris@16:                 BOOST_ASSERT( r.is_valid() );
Chris@16:                 return;
Chris@16:             }
Chris@16: 
Chris@16:             BOOST_ASSERT( on_stack || r_on_stack );
Chris@16:             bool exactly_one_on_stack = (on_stack && !r_on_stack) ||
Chris@16:                                         (!on_stack && r_on_stack);
Chris@16: 
Chris@16:             //
Chris@16:             // Remark: we now know that we can copy into
Chris@16:             //         the unused stack buffer.
Chris@16:             //
Chris@16:             if( exactly_one_on_stack )
Chris@16:             {
Chris@16:                 auto_buffer* one_on_stack = on_stack ? this : &r;
Chris@16:                 auto_buffer* other        = on_stack ? &r : this;
Chris@16:                 pointer new_buffer = static_cast<T*>(other->members_.address());
Chris@16:                 copy_impl( one_on_stack->begin(), one_on_stack->end(),
Chris@16:                            new_buffer );                            // strong
Chris@16:                 one_on_stack->~auto_buffer();                       // nothrow
Chris@16:                 boost::swap( get_allocator(), r.get_allocator() );  // assume nothrow
Chris@16:                 boost::swap( members_.capacity_, r.members_.capacity_ );
Chris@16:                 boost::swap( size_, r.size_ );
Chris@16:                 one_on_stack->buffer_ = other->buffer_;
Chris@16:                 other->buffer_        = new_buffer;
Chris@16:                 BOOST_ASSERT( other->is_on_stack() );
Chris@16:                 BOOST_ASSERT( !one_on_stack->is_on_stack() );
Chris@16:                 BOOST_ASSERT( is_valid() );
Chris@16:                 BOOST_ASSERT( r.is_valid() );
Chris@16:                 return;
Chris@16:             }
Chris@16: 
Chris@16:             BOOST_ASSERT( on_stack && r_on_stack );
Chris@16:             swap_helper( *this, r, boost::has_trivial_assign<T>() );
Chris@16:             BOOST_ASSERT( is_valid() );
Chris@16:             BOOST_ASSERT( r.is_valid() );
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         typedef boost::aligned_storage< N * sizeof(T),
Chris@16:                                         boost::alignment_of<T>::value >
Chris@16:                                storage;
Chris@16: 
Chris@16:         struct members_type : storage /* to enable EBO */
Chris@16:         {
Chris@16:             size_type capacity_;
Chris@16: 
Chris@16:             members_type( size_type capacity )
Chris@16:                : capacity_(capacity)
Chris@16:             { }
Chris@16: 
Chris@16:             void* address() const
Chris@16:             { return const_cast<storage&>(static_cast<const storage&>(*this)).address(); }
Chris@16:         };
Chris@16: 
Chris@16:         members_type members_;
Chris@16:         pointer      buffer_;
Chris@16:         size_type    size_;
Chris@16: 
Chris@16:     };
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline void swap( auto_buffer<T,SBP,GP,A>& l, auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         l.swap( r );
Chris@16:     }
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline bool operator==( const auto_buffer<T,SBP,GP,A>& l,
Chris@16:                             const auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         if( l.size() != r.size() )
Chris@16:             return false;
Chris@16:         return std::equal( l.begin(), l.end(), r.begin() );
Chris@16:     }
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline bool operator!=( const auto_buffer<T,SBP,GP,A>& l,
Chris@16:                             const auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         return !(l == r);
Chris@16:     }
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline bool operator<( const auto_buffer<T,SBP,GP,A>& l,
Chris@16:                            const auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         return std::lexicographical_compare( l.begin(), l.end(),
Chris@16:                                              r.begin(), r.end() );
Chris@16:     }
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline bool operator>( const auto_buffer<T,SBP,GP,A>& l,
Chris@16:                            const auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         return (r < l);
Chris@16:     }
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline bool operator<=( const auto_buffer<T,SBP,GP,A>& l,
Chris@16:                             const auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         return !(r > l);
Chris@16:     }
Chris@16: 
Chris@16:     template< class T, class SBP, class GP, class A >
Chris@16:     inline bool operator>=( const auto_buffer<T,SBP,GP,A>& l,
Chris@16:                             const auto_buffer<T,SBP,GP,A>& r )
Chris@16:     {
Chris@16:         return !(l < r);
Chris@16:     }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: } // namespace signals2
Chris@16: }
Chris@16: 
Chris@16: #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: #endif