ceph/src/boost/boost/signals2/detail/auto_buffer.hpp

   1 // Copyright Thorsten Ottosen, 2009.
   2 // Distributed under the Boost Software License, Version 1.0. (See
   3 // accompanying file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #ifndef BOOST_SIGNALS2_DETAIL_AUTO_BUFFER_HPP_25_02_2009
   7 #define BOOST_SIGNALS2_DETAIL_AUTO_BUFFER_HPP_25_02_2009
   8
   9 #include <boost/detail/workaround.hpp>
  10
  11 #if defined(_MSC_VER)
  12 # pragma once
  13 #endif
  14
  15 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
  16 #pragma warning(push)
  17 #pragma warning(disable:4996)
  18 #endif
  19
  20 #include <boost/assert.hpp>
  21 #include <boost/iterator/reverse_iterator.hpp>
  22 #include <boost/iterator/iterator_traits.hpp>
  23 #include <boost/mpl/if.hpp>
  24 #include <boost/multi_index/detail/scope_guard.hpp>
  25 #include <boost/swap.hpp>
  26 #include <boost/type_traits/aligned_storage.hpp>
  27 #include <boost/type_traits/alignment_of.hpp>
  28 #include <boost/type_traits/has_nothrow_copy.hpp>
  29 #include <boost/type_traits/has_nothrow_assign.hpp>
  30 #include <boost/type_traits/has_trivial_assign.hpp>
  31 #include <boost/type_traits/has_trivial_constructor.hpp>
  32 #include <boost/type_traits/has_trivial_destructor.hpp>
  33 #include <algorithm>
  34 #include <cstring>
  35 #include <iterator>
  36 #include <memory>
  37 #include <stdexcept>
  38
  39 namespace boost
  40 {
  41 namespace signals2
  42 {
  43 namespace detail
  44 {
  45     //
  46     // Policies for creating the stack buffer.
  47     //
  48     template< unsigned N >
  49     struct store_n_objects
  50     {
  51         BOOST_STATIC_CONSTANT( unsigned, value = N );
  52     };
  53
  54     template< unsigned N >
  55     struct store_n_bytes
  56     {
  57         BOOST_STATIC_CONSTANT( unsigned, value = N );
  58     };
  59
  60     namespace auto_buffer_detail
  61     {
  62         template< class Policy, class T >
  63         struct compute_buffer_size
  64         {
  65             BOOST_STATIC_CONSTANT( unsigned, value = Policy::value * sizeof(T) );
  66         };
  67
  68         template< unsigned N, class T >
  69         struct compute_buffer_size< store_n_bytes<N>, T >
  70         {
  71             BOOST_STATIC_CONSTANT( unsigned, value = N );
  72         };
  73
  74         template< class Policy, class T >
  75         struct compute_buffer_objects
  76         {
  77             BOOST_STATIC_CONSTANT( unsigned, value = Policy::value );
  78         };
  79
  80         template< unsigned N, class T >
  81         struct compute_buffer_objects< store_n_bytes<N>, T >
  82         {
  83             BOOST_STATIC_CONSTANT( unsigned, value = N / sizeof(T) );
  84         };
  85     }
  86
  87     struct default_grow_policy
  88     {
  89         template< class SizeType >
  90         static SizeType new_capacity( SizeType capacity )
  91         {
  92             //
  93             // @remark: we grow the capacity quite agressively.
  94             //          this is justified since we aim to minimize
  95             //          heap-allocations, and because we mostly use
  96             //          the buffer locally.
  97             return capacity * 4u;
  98         }
  99
 100         template< class SizeType >
 101         static bool should_shrink( SizeType, SizeType )
 102         {
 103             //
 104             // @remark: when defining a new grow policy, one might
 105             //          choose that if the waated space is less
 106             //          than a certain percentage, then it is of
 107             //          little use to shrink.
 108             //
 109             return true;
 110         }
 111     };
 112
 113     template< class T,
 114               class StackBufferPolicy = store_n_objects<256>,
 115               class GrowPolicy        = default_grow_policy,
 116               class Allocator         = std::allocator<T> >
 117     class auto_buffer;
 118
 119
 120
 121     template
 122     <
 123         class T,
 124         class StackBufferPolicy,
 125         class GrowPolicy,
 126         class Allocator
 127     >
 128     class auto_buffer : Allocator
 129     {
 130     private:
 131         enum { N = auto_buffer_detail::
 132                    compute_buffer_objects<StackBufferPolicy,T>::value };
 133
 134         BOOST_STATIC_CONSTANT( bool, is_stack_buffer_empty = N == 0u );
 135
 136         typedef auto_buffer<T, store_n_objects<0>, GrowPolicy, Allocator>
 137                                                          local_buffer;
 138
 139     public:
 140         typedef Allocator                                allocator_type;
 141         typedef T                                        value_type;
 142         typedef typename Allocator::size_type            size_type;
 143         typedef typename Allocator::difference_type      difference_type;
 144         typedef T*                                       pointer;
 145         typedef typename Allocator::pointer              allocator_pointer;
 146         typedef const T*                                 const_pointer;
 147         typedef T&                                       reference;
 148         typedef const T&                                 const_reference;
 149         typedef pointer                                  iterator;
 150         typedef const_pointer                            const_iterator;
 151         typedef boost::reverse_iterator<iterator>        reverse_iterator;
 152         typedef boost::reverse_iterator<const_iterator>  const_reverse_iterator;
 153         typedef typename boost::mpl::if_c< boost::has_trivial_assign<T>::value
 154                                            && sizeof(T) <= sizeof(long double),
 155                                           const value_type,
 156                                           const_reference >::type
 157                                                       optimized_const_reference;
 158     private:
 159
 160         pointer allocate( size_type capacity_arg )
 161         {
 162             if( capacity_arg > N )
 163                 return &*get_allocator().allocate( capacity_arg );
 164             else
 165                 return static_cast<T*>( members_.address() );
 166         }
 167
 168         void deallocate( pointer where, size_type capacity_arg )
 169         {
 170             if( capacity_arg <= N )
 171                 return;
 172             get_allocator().deallocate( allocator_pointer(where), capacity_arg );
 173         }
 174
 175         template< class I >
 176         static void copy_impl( I begin, I end, pointer where, std::random_access_iterator_tag )
 177         {
 178             copy_rai( begin, end, where, boost::has_trivial_assign<T>() );
 179         }
 180
 181         static void copy_rai( const T* begin, const T* end,
 182                               pointer where, const boost::true_type& )
 183         {
 184             std::memcpy( where, begin, sizeof(T) * std::distance(begin,end) );
 185         }
 186
 187         template< class I, bool b >
 188         static void copy_rai( I begin, I end,
 189                               pointer where, const boost::integral_constant<bool, b>& )
 190         {
 191             std::uninitialized_copy( begin, end, where );
 192         }
 193
 194         template< class I >
 195         static void copy_impl( I begin, I end, pointer where, std::bidirectional_iterator_tag )
 196         {
 197             std::uninitialized_copy( begin, end, where );
 198         }
 199
 200         template< class I >
 201         static void copy_impl( I begin, I end, pointer where )
 202         {
 203             copy_impl( begin, end, where,
 204                        typename std::iterator_traits<I>::iterator_category() );
 205         }
 206
 207         template< class I, class I2 >
 208         static void assign_impl( I begin, I end, I2 where )
 209         {
 210             assign_impl( begin, end, where, boost::has_trivial_assign<T>() );
 211         }
 212
 213         template< class I, class I2 >
 214         static void assign_impl( I begin, I end, I2 where, const boost::true_type& )
 215         {
 216             std::memcpy( where, begin, sizeof(T) * std::distance(begin,end) );
 217         }
 218
 219         template< class I, class I2 >
 220         static void assign_impl( I begin, I end, I2 where, const boost::false_type& )
 221         {
 222             for( ; begin != end; ++begin, ++where )
 223                 *where = *begin;
 224         }
 225
 226         void unchecked_push_back_n( size_type n, const boost::true_type& )
 227         {
 228             std::uninitialized_fill( end(), end() + n, T() );
 229             size_ += n;
 230         }
 231
 232         void unchecked_push_back_n( size_type n, const boost::false_type& )
 233         {
 234             for( size_type i = 0u; i < n; ++i )
 235                 unchecked_push_back();
 236         }
 237
 238         void auto_buffer_destroy( pointer where, const boost::false_type& )
 239         {
 240             (*where).~T();
 241         }
 242
 243         void auto_buffer_destroy( pointer, const boost::true_type& )
 244         { }
 245
 246         void auto_buffer_destroy( pointer where )
 247         {
 248             auto_buffer_destroy( where, boost::has_trivial_destructor<T>() );
 249         }
 250
 251         void auto_buffer_destroy()
 252         {
 253             BOOST_ASSERT( is_valid() );
 254             if( buffer_ ) // do we need this check? Yes, but only
 255                 // for N = 0u + local instances in one_sided_swap()
 256                 auto_buffer_destroy( boost::has_trivial_destructor<T>() );
 257         }
 258
 259         void destroy_back_n( size_type n, const boost::false_type& )
 260         {
 261             BOOST_ASSERT( n > 0 );
 262             pointer buffer  = buffer_ + size_ - 1u;
 263             pointer new_end = buffer - n;
 264             for( ; buffer > new_end; --buffer )
 265                 auto_buffer_destroy( buffer );
 266         }
 267
 268         void destroy_back_n( size_type, const boost::true_type& )
 269         { }
 270
 271         void destroy_back_n( size_type n )
 272         {
 273             destroy_back_n( n, boost::has_trivial_destructor<T>() );
 274         }
 275
 276         void auto_buffer_destroy( const boost::false_type& x )
 277         {
 278             if( size_ )
 279                 destroy_back_n( size_, x );
 280             deallocate( buffer_, members_.capacity_ );
 281         }
 282
 283         void auto_buffer_destroy( const boost::true_type& )
 284         {
 285             deallocate( buffer_, members_.capacity_ );
 286         }
 287
 288         pointer move_to_new_buffer( size_type new_capacity, const boost::false_type& )
 289         {
 290             pointer new_buffer = allocate( new_capacity ); // strong
 291             boost::multi_index::detail::scope_guard guard =
 292                 boost::multi_index::detail::make_obj_guard( *this,
 293                                                             &auto_buffer::deallocate,
 294                                                             new_buffer,
 295                                                             new_capacity );
 296             copy_impl( begin(), end(), new_buffer ); // strong
 297             guard.dismiss();                         // nothrow
 298             return new_buffer;
 299         }
 300
 301         pointer move_to_new_buffer( size_type new_capacity, const boost::true_type& )
 302         {
 303             pointer new_buffer = allocate( new_capacity ); // strong
 304             copy_impl( begin(), end(), new_buffer );       // nothrow
 305             return new_buffer;
 306         }
 307
 308         void reserve_impl( size_type new_capacity )
 309         {
 310             pointer new_buffer = move_to_new_buffer( new_capacity,
 311                                                  boost::has_nothrow_copy<T>() );
 312             auto_buffer_destroy();
 313             buffer_   = new_buffer;
 314             members_.capacity_ = new_capacity;
 315             BOOST_ASSERT( size_ <= members_.capacity_ );
 316         }
 317
 318         size_type new_capacity_impl( size_type n )
 319         {
 320             BOOST_ASSERT( n > members_.capacity_ );
 321             size_type new_capacity = GrowPolicy::new_capacity( members_.capacity_ );
 322             // @todo: consider to check for allocator.max_size()
 323             return (std::max)(new_capacity,n);
 324         }
 325
 326         static void swap_helper( auto_buffer& l, auto_buffer& r,
 327                                  const boost::true_type& )
 328         {
 329             BOOST_ASSERT( l.is_on_stack() && r.is_on_stack() );
 330
 331             auto_buffer temp( l.begin(), l.end() );
 332             assign_impl( r.begin(), r.end(), l.begin() );
 333             assign_impl( temp.begin(), temp.end(), r.begin() );
 334             boost::swap( l.size_, r.size_ );
 335             boost::swap( l.members_.capacity_, r.members_.capacity_ );
 336         }
 337
 338         static void swap_helper( auto_buffer& l, auto_buffer& r,
 339                                  const boost::false_type& )
 340         {
 341             BOOST_ASSERT( l.is_on_stack() && r.is_on_stack() );
 342             size_type min_size    = (std::min)(l.size_,r.size_);
 343             size_type max_size    = (std::max)(l.size_,r.size_);
 344             size_type diff        = max_size - min_size;
 345             auto_buffer* smallest = l.size_ == min_size ? &l : &r;
 346             auto_buffer* largest  = smallest == &l ? &r : &l;
 347
 348             // @remark: the implementation below is not as fast
 349             //          as it could be if we assumed T had a default
 350             //          constructor.
 351
 352             size_type i = 0u;
 353             for(  ; i < min_size; ++i )
 354                 boost::swap( (*smallest)[i], (*largest)[i] );
 355
 356             for( ; i < max_size; ++i )
 357                 smallest->unchecked_push_back( (*largest)[i] );
 358
 359             largest->pop_back_n( diff );
 360             boost::swap( l.members_.capacity_, r.members_.capacity_ );
 361         }
 362
 363         void one_sided_swap( auto_buffer& temp ) // nothrow
 364         {
 365             BOOST_ASSERT( !temp.is_on_stack() );
 366             auto_buffer_destroy();
 367             // @remark: must be nothrow
 368             get_allocator()    = temp.get_allocator();
 369             members_.capacity_ = temp.members_.capacity_;
 370             buffer_            = temp.buffer_;
 371             BOOST_ASSERT( temp.size_ >= size_ + 1u );
 372             size_              = temp.size_;
 373             temp.buffer_       = 0;
 374             BOOST_ASSERT( temp.is_valid() );
 375         }
 376
 377         template< class I >
 378         void insert_impl( const_iterator before, I begin_arg, I end_arg,
 379                           std::input_iterator_tag )
 380         {
 381             for( ; begin_arg != end_arg; ++begin_arg )
 382             {
 383                 before = insert( before, *begin_arg );
 384                 ++before;
 385             }
 386         }
 387
 388         void grow_back( size_type n, const boost::true_type& )
 389         {
 390             BOOST_ASSERT( size_ + n <= members_.capacity_ );
 391             size_ += n;
 392         }
 393
 394         void grow_back( size_type n, const boost::false_type& )
 395         {
 396             unchecked_push_back_n(n);
 397         }
 398
 399         void grow_back( size_type n )
 400         {
 401             grow_back( n, boost::has_trivial_constructor<T>() );
 402         }
 403
 404         void grow_back_one( const boost::true_type& )
 405         {
 406             BOOST_ASSERT( size_ + 1 <= members_.capacity_ );
 407             size_ += 1;
 408         }
 409
 410         void grow_back_one( const boost::false_type& )
 411         {
 412             unchecked_push_back();
 413         }
 414
 415         void grow_back_one()
 416         {
 417             grow_back_one( boost::has_trivial_constructor<T>() );
 418         }
 419
 420         template< class I >
 421         void insert_impl( const_iterator before, I begin_arg, I end_arg,
 422                           std::forward_iterator_tag )
 423         {
 424             difference_type n = std::distance(begin_arg, end_arg);
 425
 426             if( size_ + n <= members_.capacity_ )
 427             {
 428                 bool is_back_insertion = before == cend();
 429                 if( !is_back_insertion )
 430                 {
 431                     grow_back( n );
 432                     iterator where = const_cast<T*>(before);
 433                     std::copy( before, cend() - n, where + n );
 434                     assign_impl( begin_arg, end_arg, where );
 435                 }
 436                 else
 437                 {
 438                     unchecked_push_back( begin_arg, end_arg );
 439                 }
 440                 BOOST_ASSERT( is_valid() );
 441                 return;
 442             }
 443
 444             auto_buffer temp( new_capacity_impl( size_ + n ) );
 445             temp.unchecked_push_back( cbegin(), before );
 446             temp.unchecked_push_back( begin_arg, end_arg );
 447             temp.unchecked_push_back( before, cend() );
 448             one_sided_swap( temp );
 449             BOOST_ASSERT( is_valid() );
 450         }
 451
 452     public:
 453         bool is_valid() const // invariant
 454         {
 455             // @remark: allowed for N==0 and when
 456             //          using a locally instance
 457             //          in insert()/one_sided_swap()
 458             if( buffer_ == 0 )
 459                 return true;
 460
 461             if( members_.capacity_ < N )
 462                 return false;
 463
 464             if( !is_on_stack() && members_.capacity_ <= N )
 465                 return false;
 466
 467             if( buffer_ == members_.address() )
 468                 if( members_.capacity_ > N )
 469                     return false;
 470
 471             if( size_ > members_.capacity_ )
 472                 return false;
 473
 474             return true;
 475         }
 476
 477         auto_buffer()
 478             : members_( N ),
 479               buffer_( static_cast<T*>(members_.address()) ),
 480               size_( 0u )
 481         {
 482             BOOST_ASSERT( is_valid() );
 483         }
 484
 485         auto_buffer( const auto_buffer& r )
 486             : members_( (std::max)(r.size_,size_type(N)) ),
 487               buffer_( allocate( members_.capacity_ ) ),
 488               size_( 0 )
 489         {
 490             copy_impl( r.begin(), r.end(), buffer_ );
 491             size_ = r.size_;
 492             BOOST_ASSERT( is_valid() );
 493         }
 494
 495         auto_buffer& operator=( const auto_buffer& r ) // basic
 496         {
 497             if( this == &r )
 498                 return *this;
 499
 500             difference_type diff = size_ - r.size_;
 501             if( diff >= 0 )
 502             {
 503                 pop_back_n( static_cast<size_type>(diff) );
 504                 assign_impl( r.begin(), r.end(), begin() );
 505             }
 506             else
 507             {
 508                 if( members_.capacity_ >= r.size() )
 509                 {
 510                     unchecked_push_back_n( static_cast<size_type>(-diff) );
 511                     assign_impl( r.begin(), r.end(), begin() );
 512                 }
 513                 else
 514                 {
 515                     // @remark: we release memory as early as possible
 516                     //          since we only give the basic guarantee
 517                     auto_buffer_destroy();
 518                     buffer_ = 0;
 519                     pointer new_buffer = allocate( r.size() );
 520                     boost::multi_index::detail::scope_guard guard =
 521                         boost::multi_index::detail::make_obj_guard( *this,
 522                                                                     &auto_buffer::deallocate,
 523                                                                     new_buffer,
 524                                                                     r.size() );
 525                     copy_impl( r.begin(), r.end(), new_buffer );
 526                     guard.dismiss();
 527                     buffer_            = new_buffer;
 528                     members_.capacity_ = r.size();
 529                     size_              = members_.capacity_;
 530                 }
 531             }
 532
 533             BOOST_ASSERT( size() == r.size() );
 534             BOOST_ASSERT( is_valid() );
 535             return *this;
 536         }
 537
 538         explicit auto_buffer( size_type capacity_arg )
 539             : members_( (std::max)(capacity_arg, size_type(N)) ),
 540               buffer_( allocate(members_.capacity_) ),
 541               size_( 0 )
 542         {
 543             BOOST_ASSERT( is_valid() );
 544         }
 545
 546         auto_buffer( size_type size_arg, optimized_const_reference init_value )
 547             : members_( (std::max)(size_arg, size_type(N)) ),
 548               buffer_( allocate(members_.capacity_) ),
 549               size_( 0 )
 550         {
 551             std::uninitialized_fill( buffer_, buffer_ + size_arg, init_value );
 552             size_ = size_arg;
 553             BOOST_ASSERT( is_valid() );
 554         }
 555
 556         auto_buffer( size_type capacity_arg, const allocator_type& a )
 557             : allocator_type( a ),
 558               members_( (std::max)(capacity_arg, size_type(N)) ),
 559               buffer_( allocate(members_.capacity_) ),
 560               size_( 0 )
 561         {
 562             BOOST_ASSERT( is_valid() );
 563         }
 564
 565         auto_buffer( size_type size_arg, optimized_const_reference init_value,
 566                      const allocator_type& a )
 567             : allocator_type( a ),
 568               members_( (std::max)(size_arg, size_type(N)) ),
 569               buffer_( allocate(members_.capacity_) ),
 570               size_( 0 )
 571         {
 572             std::uninitialized_fill( buffer_, buffer_ + size_arg, init_value );
 573             size_ = size_arg;
 574             BOOST_ASSERT( is_valid() );
 575         }
 576
 577         template< class ForwardIterator >
 578         auto_buffer( ForwardIterator begin_arg, ForwardIterator end_arg )
 579             :
 580               members_( std::distance(begin_arg, end_arg) ),
 581               buffer_( allocate(members_.capacity_) ),
 582               size_( 0 )
 583         {
 584             copy_impl( begin_arg, end_arg, buffer_ );
 585             size_ = members_.capacity_;
 586             if( members_.capacity_ < N )
 587                 members_.capacity_ = N;
 588             BOOST_ASSERT( is_valid() );
 589         }
 590
 591         template< class ForwardIterator >
 592         auto_buffer( ForwardIterator begin_arg, ForwardIterator end_arg,
 593                      const allocator_type& a )
 594             : allocator_type( a ),
 595               members_( std::distance(begin_arg, end_arg) ),
 596               buffer_( allocate(members_.capacity_) ),
 597               size_( 0 )
 598         {
 599             copy_impl( begin_arg, end_arg, buffer_ );
 600             size_ = members_.capacity_;
 601             if( members_.capacity_ < N )
 602                 members_.capacity_ = N;
 603             BOOST_ASSERT( is_valid() );
 604         }
 605
 606         ~auto_buffer()
 607         {
 608             auto_buffer_destroy();
 609         }
 610
 611     public:
 612         bool empty() const
 613         {
 614             return size_ == 0;
 615         }
 616
 617         bool full() const
 618         {
 619             return size_ == members_.capacity_;
 620         }
 621
 622         bool is_on_stack() const
 623         {
 624             return members_.capacity_ <= N;
 625         }
 626
 627         size_type size() const
 628         {
 629             return size_;
 630         }
 631
 632         size_type capacity() const
 633         {
 634             return members_.capacity_;
 635         }
 636
 637     public:
 638         pointer data()
 639         {
 640             return buffer_;
 641         }
 642
 643         const_pointer data() const
 644         {
 645             return buffer_;
 646         }
 647
 648         allocator_type& get_allocator()
 649         {
 650             return static_cast<allocator_type&>(*this);
 651         }
 652
 653         const allocator_type& get_allocator() const
 654         {
 655             return static_cast<const allocator_type&>(*this);
 656         }
 657
 658     public:
 659         iterator begin()
 660         {
 661             return buffer_;
 662         }
 663
 664         const_iterator begin() const
 665         {
 666             return buffer_;
 667         }
 668
 669         iterator end()
 670         {
 671             return buffer_ + size_;
 672         }
 673
 674         const_iterator end() const
 675         {
 676             return buffer_ + size_;
 677         }
 678
 679         reverse_iterator rbegin()
 680         {
 681             return reverse_iterator(end());
 682         }
 683
 684         const_reverse_iterator rbegin() const
 685         {
 686             return const_reverse_iterator(end());
 687         }
 688
 689         reverse_iterator rend()
 690         {
 691             return reverse_iterator(begin());
 692         }
 693
 694         const_reverse_iterator rend() const
 695         {
 696             return const_reverse_iterator(begin());
 697         }
 698
 699         const_iterator cbegin() const
 700         {
 701             return const_cast<const auto_buffer*>(this)->begin();
 702         }
 703
 704         const_iterator cend() const
 705         {
 706             return const_cast<const auto_buffer*>(this)->end();
 707         }
 708
 709         const_reverse_iterator crbegin() const
 710         {
 711             return const_cast<const auto_buffer*>(this)->rbegin();
 712         }
 713
 714         const_reverse_iterator crend() const
 715         {
 716             return const_cast<const auto_buffer*>(this)->rend();
 717         }
 718
 719     public:
 720         reference front()
 721         {
 722             return buffer_[0];
 723         }
 724
 725         optimized_const_reference front() const
 726         {
 727             return buffer_[0];
 728         }
 729
 730         reference back()
 731         {
 732             return buffer_[size_-1];
 733         }
 734
 735         optimized_const_reference back() const
 736         {
 737             return buffer_[size_-1];
 738         }
 739
 740         reference operator[]( size_type n )
 741         {
 742             BOOST_ASSERT( n < size_ );
 743             return buffer_[n];
 744         }
 745
 746         optimized_const_reference operator[]( size_type n ) const
 747         {
 748             BOOST_ASSERT( n < size_ );
 749             return buffer_[n];
 750         }
 751
 752         void unchecked_push_back()
 753         {
 754             BOOST_ASSERT( !full() );
 755             new (buffer_ + size_) T;
 756             ++size_;
 757         }
 758
 759         void unchecked_push_back_n( size_type n )
 760         {
 761             BOOST_ASSERT( size_ + n <= members_.capacity_ );
 762             unchecked_push_back_n( n, boost::has_trivial_assign<T>() );
 763         }
 764
 765         void unchecked_push_back( optimized_const_reference x ) // non-growing
 766         {
 767             BOOST_ASSERT( !full() );
 768             new (buffer_ + size_) T( x );
 769             ++size_;
 770         }
 771
 772         template< class ForwardIterator >
 773         void unchecked_push_back( ForwardIterator begin_arg,
 774                                   ForwardIterator end_arg ) // non-growing
 775         {
 776             BOOST_ASSERT( size_ + std::distance(begin_arg, end_arg) <= members_.capacity_ );
 777             copy_impl( begin_arg, end_arg, buffer_ + size_ );
 778             size_ += std::distance(begin_arg, end_arg);
 779         }
 780
 781         void reserve_precisely( size_type n )
 782         {
 783             BOOST_ASSERT( members_.capacity_  >= N );
 784
 785             if( n <= members_.capacity_ )
 786                 return;
 787             reserve_impl( n );
 788             BOOST_ASSERT( members_.capacity_ == n );
 789         }
 790
 791         void reserve( size_type n ) // strong
 792         {
 793             BOOST_ASSERT( members_.capacity_  >= N );
 794
 795             if( n <= members_.capacity_ )
 796                 return;
 797
 798             reserve_impl( new_capacity_impl( n ) );
 799             BOOST_ASSERT( members_.capacity_ >= n );
 800         }
 801
 802         void push_back()
 803         {
 804             if( size_ != members_.capacity_ )
 805             {
 806                 unchecked_push_back();
 807             }
 808             else
 809             {
 810                 reserve( size_ + 1u );
 811                 unchecked_push_back();
 812             }
 813         }
 814
 815         void push_back( optimized_const_reference x )
 816         {
 817             if( size_ != members_.capacity_ )
 818             {
 819                 unchecked_push_back( x );
 820             }
 821             else
 822             {
 823                reserve( size_ + 1u );
 824                unchecked_push_back( x );
 825             }
 826         }
 827
 828         template< class ForwardIterator >
 829         void push_back( ForwardIterator begin_arg, ForwardIterator end_arg )
 830         {
 831             difference_type diff = std::distance(begin_arg, end_arg);
 832             if( size_ + diff > members_.capacity_ )
 833                 reserve( size_ + diff );
 834             unchecked_push_back( begin_arg, end_arg );
 835         }
 836
 837         iterator insert( const_iterator before, optimized_const_reference x ) // basic
 838         {
 839             // @todo: consider if we want to support x in 'this'
 840             if( size_ < members_.capacity_ )
 841             {
 842                 bool is_back_insertion = before == cend();
 843                 iterator where = const_cast<T*>(before);
 844
 845                 if( !is_back_insertion )
 846                 {
 847                     grow_back_one();
 848                     std::copy( before, cend() - 1u, where + 1u );
 849                     *where = x;
 850                     BOOST_ASSERT( is_valid() );
 851                  }
 852                 else
 853                 {
 854                     unchecked_push_back( x );
 855                 }
 856                 return where;
 857             }
 858
 859             auto_buffer temp( new_capacity_impl( size_ + 1u ) );
 860             temp.unchecked_push_back( cbegin(), before );
 861             iterator result = temp.end();
 862             temp.unchecked_push_back( x );
 863             temp.unchecked_push_back( before, cend() );
 864             one_sided_swap( temp );
 865             BOOST_ASSERT( is_valid() );
 866             return result;
 867         }
 868
 869         void insert( const_iterator before, size_type n,
 870                      optimized_const_reference x )
 871         {
 872             // @todo: see problems above
 873             if( size_ + n <= members_.capacity_ )
 874             {
 875                 grow_back( n );
 876                 iterator where = const_cast<T*>(before);
 877                 std::copy( before, cend() - n, where + n );
 878                 std::fill( where, where + n, x );
 879                 BOOST_ASSERT( is_valid() );
 880                 return;
 881             }
 882
 883             auto_buffer temp( new_capacity_impl( size_ + n ) );
 884             temp.unchecked_push_back( cbegin(), before );
 885             std::uninitialized_fill_n( temp.end(), n, x );
 886             temp.size_ += n;
 887             temp.unchecked_push_back( before, cend() );
 888             one_sided_swap( temp );
 889             BOOST_ASSERT( is_valid() );
 890         }
 891
 892         template< class ForwardIterator >
 893         void insert( const_iterator before,
 894                      ForwardIterator begin_arg, ForwardIterator end_arg ) // basic
 895         {
 896             typedef typename std::iterator_traits<ForwardIterator>
 897                 ::iterator_category category;
 898             insert_impl( before, begin_arg, end_arg, category() );
 899         }
 900
 901         void pop_back()
 902         {
 903             BOOST_ASSERT( !empty() );
 904             auto_buffer_destroy( buffer_ + size_ - 1, boost::has_trivial_destructor<T>() );
 905             --size_;
 906         }
 907
 908         void pop_back_n( size_type n )
 909         {
 910             BOOST_ASSERT( n <= size_ );
 911             if( n )
 912             {
 913                 destroy_back_n( n );
 914                 size_ -= n;
 915             }
 916         }
 917
 918         void clear()
 919         {
 920             pop_back_n( size_ );
 921         }
 922
 923         iterator erase( const_iterator where )
 924         {
 925             BOOST_ASSERT( !empty() );
 926             BOOST_ASSERT( cbegin() <= where );
 927             BOOST_ASSERT( cend() > where );
 928
 929             unsigned elements = cend() - where - 1u;
 930
 931             if( elements > 0u )
 932             {
 933                 const_iterator start = where + 1u;
 934                 std::copy( start, start + elements,
 935                            const_cast<T*>(where) );
 936             }
 937             pop_back();
 938             BOOST_ASSERT( !full() );
 939             iterator result = const_cast<T*>( where );
 940             BOOST_ASSERT( result <= end() );
 941             return result;
 942         }
 943
 944         iterator erase( const_iterator from, const_iterator to )
 945         {
 946             BOOST_ASSERT( !(std::distance(from,to)>0) ||
 947                           !empty() );
 948             BOOST_ASSERT( cbegin() <= from );
 949             BOOST_ASSERT( cend() >= to );
 950
 951             unsigned elements = std::distance(to,cend());
 952
 953             if( elements > 0u )
 954             {
 955                 BOOST_ASSERT( elements > 0u );
 956                 std::copy( to, to + elements,
 957                            const_cast<T*>(from) );
 958             }
 959             pop_back_n( std::distance(from,to) );
 960             BOOST_ASSERT( !full() );
 961             iterator result = const_cast<T*>( from );
 962             BOOST_ASSERT( result <= end() );
 963             return result;
 964         }
 965
 966         void shrink_to_fit()
 967         {
 968             if( is_on_stack() || !GrowPolicy::should_shrink(size_,members_.capacity_) )
 969                 return;
 970
 971             reserve_impl( size_ );
 972             members_.capacity_ = (std::max)(size_type(N),members_.capacity_);
 973             BOOST_ASSERT( is_on_stack() || size_ == members_.capacity_ );
 974             BOOST_ASSERT( !is_on_stack() || size_ <= members_.capacity_ );
 975         }
 976
 977         pointer uninitialized_grow( size_type n ) // strong
 978         {
 979             if( size_ + n > members_.capacity_ )
 980                 reserve( size_ + n );
 981
 982             pointer res = end();
 983             size_ += n;
 984             return res;
 985         }
 986
 987         void uninitialized_shrink( size_type n ) // nothrow
 988         {
 989             // @remark: test for wrap-around
 990             BOOST_ASSERT( size_ - n <= members_.capacity_ );
 991             size_ -= n;
 992         }
 993
 994         void uninitialized_resize( size_type n )
 995         {
 996             if( n > size() )
 997                 uninitialized_grow( n - size() );
 998             else if( n < size() )
 999                 uninitialized_shrink( size() - n );
1000
1001            BOOST_ASSERT( size() == n );
1002         }
1003
1004         // nothrow  - if both buffer are on the heap, or
1005         //          - if one buffer is on the heap and one has
1006         //            'has_allocated_buffer() == false', or
1007         //          - if copy-construction cannot throw
1008         // basic    - otherwise (better guarantee impossible)
1009         // requirement: the allocator must be no-throw-swappable
1010         void swap( auto_buffer& r )
1011         {
1012             bool on_stack      = is_on_stack();
1013             bool r_on_stack    = r.is_on_stack();
1014             bool both_on_heap  = !on_stack && !r_on_stack;
1015             if( both_on_heap )
1016             {
1017                 boost::swap( get_allocator(), r.get_allocator() );
1018                 boost::swap( members_.capacity_, r.members_.capacity_ );
1019                 boost::swap( buffer_, r.buffer_ );
1020                 boost::swap( size_, r.size_ );
1021                 BOOST_ASSERT( is_valid() );
1022                 BOOST_ASSERT( r.is_valid() );
1023                 return;
1024             }
1025
1026             BOOST_ASSERT( on_stack || r_on_stack );
1027             bool exactly_one_on_stack = (on_stack && !r_on_stack) ||
1028                                         (!on_stack && r_on_stack);
1029
1030             //
1031             // Remark: we now know that we can copy into
1032             //         the unused stack buffer.
1033             //
1034             if( exactly_one_on_stack )
1035             {
1036                 auto_buffer* one_on_stack = on_stack ? this : &r;
1037                 auto_buffer* other        = on_stack ? &r : this;
1038                 pointer new_buffer = static_cast<T*>(other->members_.address());
1039                 copy_impl( one_on_stack->begin(), one_on_stack->end(),
1040                            new_buffer );                            // strong
1041                 one_on_stack->auto_buffer_destroy();                       // nothrow
1042                 boost::swap( get_allocator(), r.get_allocator() );  // assume nothrow
1043                 boost::swap( members_.capacity_, r.members_.capacity_ );
1044                 boost::swap( size_, r.size_ );
1045                 one_on_stack->buffer_ = other->buffer_;
1046                 other->buffer_        = new_buffer;
1047                 BOOST_ASSERT( other->is_on_stack() );
1048                 BOOST_ASSERT( !one_on_stack->is_on_stack() );
1049                 BOOST_ASSERT( is_valid() );
1050                 BOOST_ASSERT( r.is_valid() );
1051                 return;
1052             }
1053
1054             BOOST_ASSERT( on_stack && r_on_stack );
1055             swap_helper( *this, r, boost::has_trivial_assign<T>() );
1056             BOOST_ASSERT( is_valid() );
1057             BOOST_ASSERT( r.is_valid() );
1058         }
1059
1060     private:
1061         typedef boost::aligned_storage< N * sizeof(T),
1062                                         boost::alignment_of<T>::value >
1063                                storage;
1064
1065         struct members_type : storage /* to enable EBO */
1066         {
1067             size_type capacity_;
1068
1069             members_type( size_type capacity )
1070                : capacity_(capacity)
1071             { }
1072
1073             void* address() const
1074             { return const_cast<storage&>(static_cast<const storage&>(*this)).address(); }
1075         };
1076
1077         members_type members_;
1078         pointer      buffer_;
1079         size_type    size_;
1080
1081     };
1082
1083     template< class T, class SBP, class GP, class A >
1084     inline void swap( auto_buffer<T,SBP,GP,A>& l, auto_buffer<T,SBP,GP,A>& r )
1085     {
1086         l.swap( r );
1087     }
1088
1089     template< class T, class SBP, class GP, class A >
1090     inline bool operator==( const auto_buffer<T,SBP,GP,A>& l,
1091                             const auto_buffer<T,SBP,GP,A>& r )
1092     {
1093         if( l.size() != r.size() )
1094             return false;
1095         return std::equal( l.begin(), l.end(), r.begin() );
1096     }
1097
1098     template< class T, class SBP, class GP, class A >
1099     inline bool operator!=( const auto_buffer<T,SBP,GP,A>& l,
1100                             const auto_buffer<T,SBP,GP,A>& r )
1101     {
1102         return !(l == r);
1103     }
1104
1105     template< class T, class SBP, class GP, class A >
1106     inline bool operator<( const auto_buffer<T,SBP,GP,A>& l,
1107                            const auto_buffer<T,SBP,GP,A>& r )
1108     {
1109         return std::lexicographical_compare( l.begin(), l.end(),
1110                                              r.begin(), r.end() );
1111     }
1112
1113     template< class T, class SBP, class GP, class A >
1114     inline bool operator>( const auto_buffer<T,SBP,GP,A>& l,
1115                            const auto_buffer<T,SBP,GP,A>& r )
1116     {
1117         return (r < l);
1118     }
1119
1120     template< class T, class SBP, class GP, class A >
1121     inline bool operator<=( const auto_buffer<T,SBP,GP,A>& l,
1122                             const auto_buffer<T,SBP,GP,A>& r )
1123     {
1124         return !(l > r);
1125     }
1126
1127     template< class T, class SBP, class GP, class A >
1128     inline bool operator>=( const auto_buffer<T,SBP,GP,A>& l,
1129                             const auto_buffer<T,SBP,GP,A>& r )
1130     {
1131         return !(l < r);
1132     }
1133
1134 } // namespace detail
1135 } // namespace signals2
1136 }
1137
1138 #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)
1139 #pragma warning(pop)
1140 #endif
1141
1142 #endif