ceph/src/boost/boost/beast/core/impl/multi_buffer.hpp

   1 //
   2 // Copyright (c) 2016-2019 Vinnie Falco (vinnie dot falco at gmail dot com)
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // Official repository: https://github.com/boostorg/beast
   8 //
   9
  10 #ifndef BOOST_BEAST_IMPL_MULTI_BUFFER_HPP
  11 #define BOOST_BEAST_IMPL_MULTI_BUFFER_HPP
  12
  13 #include <boost/beast/core/buffer_traits.hpp>
  14 #include <boost/config/workaround.hpp>
  15 #include <boost/core/exchange.hpp>
  16 #include <boost/assert.hpp>
  17 #include <boost/throw_exception.hpp>
  18 #include <algorithm>
  19 #include <exception>
  20 #include <sstream>
  21 #include <string>
  22 #include <type_traits>
  23 #include <utility>
  24
  25 namespace boost {
  26 namespace beast {
  27
  28 /*  These diagrams illustrate the layout and state variables.
  29
  30 1   Input and output contained entirely in one element:
  31
  32     0                           out_
  33     |<------+-----------+--------------------------------+----->|
  34           in_pos_    out_pos_                         out_end_
  35
  36
  37 2   Output contained in first and second elements:
  38
  39                  out_
  40     |<------+-----------+------>|   |<-------------------+----->|
  41           in_pos_    out_pos_                         out_end_
  42
  43
  44 3   Output contained in the second element:
  45
  46                                                   out_
  47     |<------+------------------>|   |<----+--------------+----->|
  48           in_pos_                      out_pos_       out_end_
  49
  50
  51 4   Output contained in second and third elements:
  52
  53                                  out_
  54     |<------+------->|   |<-------+------>|   |<---------+----->|
  55           in_pos_               out_pos_              out_end_
  56
  57
  58 5   Input sequence is empty:
  59
  60                  out_
  61     |<------+------------------>|   |<-------------------+----->|
  62          out_pos_                                     out_end_
  63           in_pos_
  64
  65 6   Output sequence is empty:
  66
  67                                                     out_
  68     |<------+------------------>|   |<------+------------------>|
  69           in_pos_                        out_pos_
  70                                          out_end_
  71
  72
  73 7   The end of output can point to the end of an element.
  74     But out_pos_ should never point to the end:
  75
  76                                                     out_
  77     |<------+------------------>|   |<------+------------------>|
  78           in_pos_                        out_pos_            out_end_
  79
  80
  81 8   When the input sequence entirely fills the last element and
  82     the output sequence is empty, out_ will point to the end of
  83     the list of buffers, and out_pos_ and out_end_ will be 0:
  84
  85
  86     |<------+------------------>|   out_     == list_.end()
  87           in_pos_                   out_pos_ == 0
  88                                     out_end_ == 0
  89 */
  90
  91 //------------------------------------------------------------------------------
  92
  93 #if BOOST_WORKAROUND(BOOST_MSVC, < 1910)
  94 # pragma warning (push)
  95 # pragma warning (disable: 4521) // multiple copy constructors specified
  96 # pragma warning (disable: 4522) // multiple assignment operators specified
  97 #endif
  98
  99 template<class Allocator>
 100 template<bool isMutable>
 101 class basic_multi_buffer<Allocator>::readable_bytes
 102 {
 103     basic_multi_buffer const* b_;
 104
 105     friend class basic_multi_buffer;
 106
 107     explicit
 108     readable_bytes(
 109         basic_multi_buffer const& b) noexcept
 110         : b_(&b)
 111     {
 112     }
 113
 114 public:
 115     using value_type = typename
 116         std::conditional<
 117             isMutable,
 118             net::mutable_buffer,
 119             net::const_buffer>::type;
 120
 121     class const_iterator;
 122
 123     readable_bytes() = delete;
 124 #if BOOST_WORKAROUND(BOOST_MSVC, < 1910)
 125     readable_bytes(readable_bytes const& other)
 126         : b_(other.b_)
 127     {
 128     }
 129
 130     readable_bytes& operator=(readable_bytes const& other)
 131     {
 132         b_ = other.b_;
 133         return *this;
 134     }
 135 #else
 136     readable_bytes(readable_bytes const&) = default;
 137     readable_bytes& operator=(readable_bytes const&) = default;
 138 #endif
 139
 140     template<
 141         bool isMutable_ = isMutable,
 142         class = typename std::enable_if<! isMutable_>::type>
 143     readable_bytes(
 144         readable_bytes<true> const& other) noexcept
 145         : b_(other.b_)
 146     {
 147     }
 148
 149     template<
 150         bool isMutable_ = isMutable,
 151         class = typename std::enable_if<! isMutable_>::type>
 152     readable_bytes& operator=(
 153         readable_bytes<true> const& other) noexcept
 154     {
 155         b_ = other.b_;
 156         return *this;
 157     }
 158
 159     const_iterator begin() const noexcept;
 160     const_iterator end() const noexcept;
 161
 162     std::size_t
 163     buffer_bytes() const noexcept
 164     {
 165         return b_->size();
 166     }
 167 };
 168
 169 #if BOOST_WORKAROUND(BOOST_MSVC, < 1910)
 170 # pragma warning (pop)
 171 #endif
 172
 173 //------------------------------------------------------------------------------
 174
 175 template<class Allocator>
 176 template<bool isMutable>
 177 class
 178     basic_multi_buffer<Allocator>::
 179     readable_bytes<isMutable>::
 180     const_iterator
 181 {
 182     basic_multi_buffer const* b_ = nullptr;
 183     typename list_type::const_iterator it_;
 184
 185 public:
 186     using value_type =
 187         typename readable_bytes::value_type;
 188     using pointer = value_type const*;
 189     using reference = value_type;
 190     using difference_type = std::ptrdiff_t;
 191     using iterator_category =
 192         std::bidirectional_iterator_tag;
 193
 194     const_iterator() = default;
 195     const_iterator(
 196         const_iterator const& other) = default;
 197     const_iterator& operator=(
 198         const_iterator const& other) = default;
 199
 200     const_iterator(
 201         basic_multi_buffer const& b, typename
 202         list_type::const_iterator const& it) noexcept
 203         : b_(&b)
 204         , it_(it)
 205     {
 206     }
 207
 208     bool
 209     operator==(const_iterator const& other) const noexcept
 210     {
 211         return b_ == other.b_ && it_ == other.it_;
 212     }
 213
 214     bool
 215     operator!=(const_iterator const& other) const noexcept
 216     {
 217         return !(*this == other);
 218     }
 219
 220     reference
 221     operator*() const noexcept
 222     {
 223         auto const& e = *it_;
 224         return value_type{e.data(),
 225            (b_->out_ == b_->list_.end() ||
 226                 &e != &*b_->out_) ? e.size() : b_->out_pos_} +
 227                    (&e == &*b_->list_.begin() ? b_->in_pos_ : 0);
 228     }
 229
 230     pointer
 231     operator->() const = delete;
 232
 233     const_iterator&
 234     operator++() noexcept
 235     {
 236         ++it_;
 237         return *this;
 238     }
 239
 240     const_iterator
 241     operator++(int) noexcept
 242     {
 243         auto temp = *this;
 244         ++(*this);
 245         return temp;
 246     }
 247
 248     const_iterator&
 249     operator--() noexcept
 250     {
 251         --it_;
 252         return *this;
 253     }
 254
 255     const_iterator
 256     operator--(int) noexcept
 257     {
 258         auto temp = *this;
 259         --(*this);
 260         return temp;
 261     }
 262 };
 263
 264 //------------------------------------------------------------------------------
 265
 266 template<class Allocator>
 267 class basic_multi_buffer<Allocator>::mutable_buffers_type
 268 {
 269     basic_multi_buffer const* b_;
 270
 271     friend class basic_multi_buffer;
 272
 273     explicit
 274     mutable_buffers_type(
 275         basic_multi_buffer const& b) noexcept
 276         : b_(&b)
 277     {
 278     }
 279
 280 public:
 281     using value_type = net::mutable_buffer;
 282
 283     class const_iterator;
 284
 285     mutable_buffers_type() = delete;
 286     mutable_buffers_type(mutable_buffers_type const&) = default;
 287     mutable_buffers_type& operator=(mutable_buffers_type const&) = default;
 288
 289     const_iterator begin() const noexcept;
 290     const_iterator end() const noexcept;
 291 };
 292
 293 //------------------------------------------------------------------------------
 294
 295 template<class Allocator>
 296 class basic_multi_buffer<Allocator>::mutable_buffers_type::const_iterator
 297 {
 298     basic_multi_buffer const* b_ = nullptr;
 299     typename list_type::const_iterator it_;
 300
 301 public:
 302     using value_type = typename
 303         mutable_buffers_type::value_type;
 304     using pointer = value_type const*;
 305     using reference = value_type;
 306     using difference_type = std::ptrdiff_t;
 307     using iterator_category =
 308         std::bidirectional_iterator_tag;
 309
 310     const_iterator() = default;
 311     const_iterator(const_iterator const& other) = default;
 312     const_iterator& operator=(const_iterator const& other) = default;
 313
 314     const_iterator(
 315         basic_multi_buffer const& b,
 316         typename list_type::const_iterator const& it) noexcept
 317         : b_(&b)
 318         , it_(it)
 319     {
 320     }
 321
 322     bool
 323     operator==(const_iterator const& other) const noexcept
 324     {
 325         return b_ == other.b_ && it_ == other.it_;
 326     }
 327
 328     bool
 329     operator!=(const_iterator const& other) const noexcept
 330     {
 331         return !(*this == other);
 332     }
 333
 334     reference
 335     operator*() const noexcept
 336     {
 337         auto const& e = *it_;
 338         return value_type{e.data(),
 339             &e == &*std::prev(b_->list_.end()) ?
 340                 b_->out_end_ : e.size()} +
 341                    (&e == &*b_->out_ ? b_->out_pos_ : 0);
 342     }
 343
 344     pointer
 345     operator->() const = delete;
 346
 347     const_iterator&
 348     operator++() noexcept
 349     {
 350         ++it_;
 351         return *this;
 352     }
 353
 354     const_iterator
 355     operator++(int) noexcept
 356     {
 357         auto temp = *this;
 358         ++(*this);
 359         return temp;
 360     }
 361
 362     const_iterator&
 363     operator--() noexcept
 364     {
 365         --it_;
 366         return *this;
 367     }
 368
 369     const_iterator
 370     operator--(int) noexcept
 371     {
 372         auto temp = *this;
 373         --(*this);
 374         return temp;
 375     }
 376 };
 377
 378 //------------------------------------------------------------------------------
 379
 380 template<class Allocator>
 381 template<bool isMutable>
 382 auto
 383 basic_multi_buffer<Allocator>::
 384 readable_bytes<isMutable>::
 385 begin() const noexcept ->
 386     const_iterator
 387 {
 388     return const_iterator{*b_, b_->list_.begin()};
 389 }
 390
 391 template<class Allocator>
 392 template<bool isMutable>
 393 auto
 394 basic_multi_buffer<Allocator>::
 395 readable_bytes<isMutable>::
 396 end() const noexcept ->
 397     const_iterator
 398 {
 399     return const_iterator{*b_, b_->out_ ==
 400         b_->list_.end() ? b_->list_.end() :
 401             std::next(b_->out_)};
 402 }
 403
 404 template<class Allocator>
 405 auto
 406 basic_multi_buffer<Allocator>::
 407 mutable_buffers_type::
 408 begin() const noexcept ->
 409     const_iterator
 410 {
 411     return const_iterator{*b_, b_->out_};
 412 }
 413
 414 template<class Allocator>
 415 auto
 416 basic_multi_buffer<Allocator>::
 417 mutable_buffers_type::
 418 end() const noexcept ->
 419     const_iterator
 420 {
 421     return const_iterator{*b_, b_->list_.end()};
 422 }
 423
 424 //------------------------------------------------------------------------------
 425
 426 template<class Allocator>
 427 basic_multi_buffer<Allocator>::
 428 ~basic_multi_buffer()
 429 {
 430     destroy(list_);
 431 }
 432
 433 template<class Allocator>
 434 basic_multi_buffer<Allocator>::
 435 basic_multi_buffer() noexcept(default_nothrow)
 436     : max_(alloc_traits::max_size(this->get()))
 437     , out_(list_.end())
 438 {
 439 }
 440
 441 template<class Allocator>
 442 basic_multi_buffer<Allocator>::
 443 basic_multi_buffer(
 444     std::size_t limit) noexcept(default_nothrow)
 445     : max_(limit)
 446     , out_(list_.end())
 447 {
 448 }
 449
 450 template<class Allocator>
 451 basic_multi_buffer<Allocator>::
 452 basic_multi_buffer(
 453     Allocator const& alloc) noexcept
 454     : boost::empty_value<Allocator>(
 455         boost::empty_init_t(), alloc)
 456     , max_(alloc_traits::max_size(this->get()))
 457     , out_(list_.end())
 458 {
 459 }
 460
 461 template<class Allocator>
 462 basic_multi_buffer<Allocator>::
 463 basic_multi_buffer(
 464     std::size_t limit,
 465     Allocator const& alloc) noexcept
 466     : boost::empty_value<Allocator>(
 467         boost::empty_init_t(), alloc)
 468     , max_(limit)
 469     , out_(list_.end())
 470 {
 471 }
 472
 473 template<class Allocator>
 474 basic_multi_buffer<Allocator>::
 475 basic_multi_buffer(
 476     basic_multi_buffer&& other) noexcept
 477     : boost::empty_value<Allocator>(
 478         boost::empty_init_t(), std::move(other.get()))
 479     , max_(other.max_)
 480     , in_size_(boost::exchange(other.in_size_, 0))
 481     , in_pos_(boost::exchange(other.in_pos_, 0))
 482     , out_pos_(boost::exchange(other.out_pos_, 0))
 483     , out_end_(boost::exchange(other.out_end_, 0))
 484 {
 485     auto const at_end =
 486         other.out_ == other.list_.end();
 487     list_ = std::move(other.list_);
 488     out_ = at_end ? list_.end() : other.out_;
 489     other.out_ = other.list_.end();
 490 }
 491
 492 template<class Allocator>
 493 basic_multi_buffer<Allocator>::
 494 basic_multi_buffer(
 495     basic_multi_buffer&& other,
 496     Allocator const& alloc)
 497     : boost::empty_value<Allocator>(
 498         boost::empty_init_t(), alloc)
 499     , max_(other.max_)
 500 {
 501     if(this->get() != other.get())
 502     {
 503         out_ = list_.end();
 504         copy_from(other);
 505         other.clear();
 506         other.shrink_to_fit();
 507         return;
 508     }
 509
 510     auto const at_end =
 511         other.out_ == other.list_.end();
 512     list_ = std::move(other.list_);
 513     out_ = at_end ? list_.end() : other.out_;
 514     in_size_ = other.in_size_;
 515     in_pos_ = other.in_pos_;
 516     out_pos_ = other.out_pos_;
 517     out_end_ = other.out_end_;
 518     other.in_size_ = 0;
 519     other.out_ = other.list_.end();
 520     other.in_pos_ = 0;
 521     other.out_pos_ = 0;
 522     other.out_end_ = 0;
 523 }
 524
 525 template<class Allocator>
 526 basic_multi_buffer<Allocator>::
 527 basic_multi_buffer(
 528     basic_multi_buffer const& other)
 529     : boost::empty_value<Allocator>(
 530         boost::empty_init_t(), alloc_traits::
 531             select_on_container_copy_construction(
 532                 other.get()))
 533     , max_(other.max_)
 534     , out_(list_.end())
 535 {
 536     copy_from(other);
 537 }
 538
 539 template<class Allocator>
 540 basic_multi_buffer<Allocator>::
 541 basic_multi_buffer(
 542     basic_multi_buffer const& other,
 543     Allocator const& alloc)
 544     : boost::empty_value<Allocator>(
 545         boost::empty_init_t(), alloc)
 546     , max_(other.max_)
 547     , out_(list_.end())
 548 {
 549     copy_from(other);
 550 }
 551
 552 template<class Allocator>
 553 template<class OtherAlloc>
 554 basic_multi_buffer<Allocator>::
 555 basic_multi_buffer(
 556         basic_multi_buffer<OtherAlloc> const& other)
 557     : out_(list_.end())
 558 {
 559     copy_from(other);
 560 }
 561
 562 template<class Allocator>
 563 template<class OtherAlloc>
 564 basic_multi_buffer<Allocator>::
 565 basic_multi_buffer(
 566     basic_multi_buffer<OtherAlloc> const& other,
 567         allocator_type const& alloc)
 568     : boost::empty_value<Allocator>(
 569         boost::empty_init_t(), alloc)
 570     , max_(other.max_)
 571     , out_(list_.end())
 572 {
 573     copy_from(other);
 574 }
 575
 576 template<class Allocator>
 577 auto
 578 basic_multi_buffer<Allocator>::
 579 operator=(basic_multi_buffer&& other) ->
 580     basic_multi_buffer&
 581 {
 582     if(this == &other)
 583         return *this;
 584     clear();
 585     max_ = other.max_;
 586     move_assign(other, pocma{});
 587     return *this;
 588 }
 589
 590 template<class Allocator>
 591 auto
 592 basic_multi_buffer<Allocator>::
 593 operator=(basic_multi_buffer const& other) ->
 594 basic_multi_buffer&
 595 {
 596     if(this == &other)
 597         return *this;
 598     copy_assign(other, pocca{});
 599     return *this;
 600 }
 601
 602 template<class Allocator>
 603 template<class OtherAlloc>
 604 auto
 605 basic_multi_buffer<Allocator>::
 606 operator=(
 607     basic_multi_buffer<OtherAlloc> const& other) ->
 608         basic_multi_buffer&
 609 {
 610     copy_from(other);
 611     return *this;
 612 }
 613
 614 //------------------------------------------------------------------------------
 615
 616 template<class Allocator>
 617 std::size_t
 618 basic_multi_buffer<Allocator>::
 619 capacity() const noexcept
 620 {
 621     auto pos = out_;
 622     if(pos == list_.end())
 623         return in_size_;
 624     auto n = pos->size() - out_pos_;
 625     while(++pos != list_.end())
 626         n += pos->size();
 627     return in_size_ + n;
 628 }
 629
 630 template<class Allocator>
 631 auto
 632 basic_multi_buffer<Allocator>::
 633 data() const noexcept ->
 634     const_buffers_type
 635 {
 636     return const_buffers_type(*this);
 637 }
 638
 639 template<class Allocator>
 640 auto
 641 basic_multi_buffer<Allocator>::
 642 data() noexcept ->
 643     mutable_data_type
 644 {
 645     return mutable_data_type(*this);
 646 }
 647
 648 template<class Allocator>
 649 void
 650 basic_multi_buffer<Allocator>::
 651 reserve(std::size_t n)
 652 {
 653     // VFALCO The amount needs to be adjusted for
 654     //        the sizeof(element) plus padding
 655     if(n > alloc_traits::max_size(this->get()))
 656         BOOST_THROW_EXCEPTION(std::length_error(
 657         "A basic_multi_buffer exceeded the allocator's maximum size"));
 658     std::size_t total = in_size_;
 659     if(n <= total)
 660         return;
 661     if(out_ != list_.end())
 662     {
 663         total += out_->size() - out_pos_;
 664         if(n <= total)
 665             return;
 666         for(auto it = out_;;)
 667         {
 668             if(++it == list_.end())
 669                 break;
 670             total += it->size();
 671             if(n <= total)
 672                 return;
 673         }
 674     }
 675     BOOST_ASSERT(n > total);
 676     (void)prepare(n - size());
 677 }
 678
 679 template<class Allocator>
 680 void
 681 basic_multi_buffer<Allocator>::
 682 shrink_to_fit()
 683 {
 684     // empty list
 685     if(list_.empty())
 686         return;
 687
 688     // zero readable bytes
 689     if(in_size_ == 0)
 690     {
 691         destroy(list_);
 692         list_.clear();
 693         out_ = list_.end();
 694         in_size_ = 0;
 695         in_pos_ = 0;
 696         out_pos_ = 0;
 697         out_end_ = 0;
 698     #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 699         debug_check();
 700     #endif
 701         return;
 702     }
 703
 704     // one or more unused output buffers
 705     if(out_ != list_.end())
 706     {
 707         if(out_ != list_.iterator_to(list_.back()))
 708         {
 709             // unused list
 710             list_type extra;
 711             extra.splice(
 712                 extra.end(),
 713                 list_,
 714                 std::next(out_),
 715                 list_.end());
 716             destroy(extra);
 717         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 718             debug_check();
 719         #endif
 720         }
 721
 722         // unused out_
 723         BOOST_ASSERT(out_ ==
 724             list_.iterator_to(list_.back()));
 725         if(out_pos_ == 0)
 726         {
 727             BOOST_ASSERT(out_ != list_.begin());
 728             auto& e = *out_;
 729             list_.erase(out_);
 730             out_ = list_.end();
 731             destroy(e);
 732             out_end_ = 0;
 733         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 734             debug_check();
 735         #endif
 736         }
 737     }
 738
 739     auto const replace =
 740         [&](iter pos, element& e)
 741         {
 742             auto it =
 743                 list_.insert(pos, e);
 744             auto& e0 = *pos;
 745             list_.erase(pos);
 746             destroy(e0);
 747             return it;
 748         };
 749
 750     // partial last buffer
 751     if(list_.size() > 1 && out_ != list_.end())
 752     {
 753         BOOST_ASSERT(out_ ==
 754             list_.iterator_to(list_.back()));
 755         BOOST_ASSERT(out_pos_ != 0);
 756         auto& e = alloc(out_pos_);
 757         std::memcpy(
 758             e.data(),
 759             out_->data(),
 760             out_pos_);
 761         replace(out_, e);
 762         out_ = list_.end();
 763         out_pos_ = 0;
 764         out_end_ = 0;
 765     #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 766         debug_check();
 767     #endif
 768     }
 769
 770     // partial first buffer
 771     if(in_pos_ != 0)
 772     {
 773         if(out_ != list_.begin())
 774         {
 775             auto const n =
 776                 list_.front().size() - in_pos_;
 777             auto& e = alloc(n);
 778             std::memcpy(
 779                 e.data(),
 780                 list_.front().data() + in_pos_,
 781                 n);
 782             replace(list_.begin(), e);
 783             in_pos_ = 0;
 784         }
 785         else
 786         {
 787             BOOST_ASSERT(list_.size() == 1);
 788             BOOST_ASSERT(out_pos_ > in_pos_);
 789             auto const n = out_pos_ - in_pos_;
 790             auto& e = alloc(n);
 791             std::memcpy(
 792                 e.data(),
 793                 list_.front().data() + in_pos_,
 794                 n);
 795             replace(list_.begin(), e);
 796             in_pos_ = 0;
 797             out_ = list_.end();
 798         }
 799     #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 800         debug_check();
 801     #endif
 802     }
 803 }
 804
 805 template<class Allocator>
 806 void
 807 basic_multi_buffer<Allocator>::
 808 clear() noexcept
 809 {
 810     out_ = list_.begin();
 811     in_size_ = 0;
 812     in_pos_ = 0;
 813     out_pos_ = 0;
 814     out_end_ = 0;
 815 }
 816
 817 template<class Allocator>
 818 auto
 819 basic_multi_buffer<Allocator>::
 820 prepare(size_type n) ->
 821     mutable_buffers_type
 822 {
 823     if(in_size_ > max_ || n > (max_ - in_size_))
 824         BOOST_THROW_EXCEPTION(std::length_error{
 825             "basic_multi_buffer too long"});
 826     list_type reuse;
 827     std::size_t total = in_size_;
 828     // put all empty buffers on reuse list
 829     if(out_ != list_.end())
 830     {
 831         total += out_->size() - out_pos_;
 832         if(out_ != list_.iterator_to(list_.back()))
 833         {
 834             out_end_ = out_->size();
 835             reuse.splice(reuse.end(), list_,
 836                 std::next(out_), list_.end());
 837         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 838             debug_check();
 839         #endif
 840         }
 841         auto const avail = out_->size() - out_pos_;
 842         if(n > avail)
 843         {
 844             out_end_ = out_->size();
 845             n -= avail;
 846         }
 847         else
 848         {
 849             out_end_ = out_pos_ + n;
 850             n = 0;
 851         }
 852     #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 853         debug_check();
 854     #endif
 855     }
 856     // get space from reuse buffers
 857     while(n > 0 && ! reuse.empty())
 858     {
 859         auto& e = reuse.front();
 860         reuse.erase(reuse.iterator_to(e));
 861         list_.push_back(e);
 862         total += e.size();
 863         if(n > e.size())
 864         {
 865             out_end_ = e.size();
 866             n -= e.size();
 867         }
 868         else
 869         {
 870             out_end_ = n;
 871             n = 0;
 872         }
 873     #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 874         debug_check();
 875     #endif
 876     }
 877     BOOST_ASSERT(total <= max_);
 878     if(! reuse.empty() || n > 0)
 879     {
 880         destroy(reuse);
 881         if(n > 0)
 882         {
 883             static auto const growth_factor = 2.0f;
 884             auto const size =
 885                 (std::min<std::size_t>)(
 886                     max_ - total,
 887                     (std::max<std::size_t>)({
 888                         static_cast<std::size_t>(
 889                             in_size_ * growth_factor - in_size_),
 890                         512,
 891                         n}));
 892             auto& e = alloc(size);
 893             list_.push_back(e);
 894             if(out_ == list_.end())
 895                 out_ = list_.iterator_to(e);
 896             out_end_ = n;
 897         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 898             debug_check();
 899         #endif
 900         }
 901     }
 902     return mutable_buffers_type(*this);
 903 }
 904
 905 template<class Allocator>
 906 void
 907 basic_multi_buffer<Allocator>::
 908 commit(size_type n) noexcept
 909 {
 910     if(list_.empty())
 911         return;
 912     if(out_ == list_.end())
 913         return;
 914     auto const back =
 915         list_.iterator_to(list_.back());
 916     while(out_ != back)
 917     {
 918         auto const avail =
 919             out_->size() - out_pos_;
 920         if(n < avail)
 921         {
 922             out_pos_ += n;
 923             in_size_ += n;
 924         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 925             debug_check();
 926         #endif
 927             return;
 928         }
 929         ++out_;
 930         n -= avail;
 931         out_pos_ = 0;
 932         in_size_ += avail;
 933     #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 934         debug_check();
 935     #endif
 936     }
 937
 938     n = (std::min)(n, out_end_ - out_pos_);
 939     out_pos_ += n;
 940     in_size_ += n;
 941     if(out_pos_ == out_->size())
 942     {
 943         ++out_;
 944         out_pos_ = 0;
 945         out_end_ = 0;
 946     }
 947 #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 948     debug_check();
 949 #endif
 950 }
 951
 952 template<class Allocator>
 953 void
 954 basic_multi_buffer<Allocator>::
 955 consume(size_type n) noexcept
 956 {
 957     if(list_.empty())
 958         return;
 959     for(;;)
 960     {
 961         if(list_.begin() != out_)
 962         {
 963             auto const avail =
 964                 list_.front().size() - in_pos_;
 965             if(n < avail)
 966             {
 967                 in_size_ -= n;
 968                 in_pos_ += n;
 969             #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 970                 debug_check();
 971             #endif
 972                 break;
 973             }
 974             n -= avail;
 975             in_size_ -= avail;
 976             in_pos_ = 0;
 977             auto& e = list_.front();
 978             list_.erase(list_.iterator_to(e));
 979             destroy(e);
 980         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
 981             debug_check();
 982         #endif
 983         }
 984         else
 985         {
 986             auto const avail = out_pos_ - in_pos_;
 987             if(n < avail)
 988             {
 989                 in_size_ -= n;
 990                 in_pos_ += n;
 991             }
 992             else
 993             {
 994                 in_size_ = 0;
 995                 if(out_ != list_.iterator_to(list_.back()) ||
 996                     out_pos_ != out_end_)
 997                 {
 998                     in_pos_ = out_pos_;
 999                 }
1000                 else
1001                 {
1002                     // Input and output sequences are empty, reuse buffer.
1003                     // Alternatively we could deallocate it.
1004                     in_pos_ = 0;
1005                     out_pos_ = 0;
1006                     out_end_ = 0;
1007                 }
1008             }
1009         #if BOOST_BEAST_MULTI_BUFFER_DEBUG_CHECK
1010             debug_check();
1011         #endif
1012             break;
1013         }
1014     }
1015 }
1016
1017 template<class Allocator>
1018 template<class OtherAlloc>
1019 void
1020 basic_multi_buffer<Allocator>::
1021 copy_from(basic_multi_buffer<OtherAlloc> const& other)
1022 {
1023     clear();
1024     max_ = other.max_;
1025     if(other.size() == 0)
1026         return;
1027     commit(net::buffer_copy(
1028         prepare(other.size()), other.data()));
1029 }
1030
1031 template<class Allocator>
1032 void
1033 basic_multi_buffer<Allocator>::
1034 move_assign(basic_multi_buffer& other, std::true_type) noexcept
1035 {
1036     this->get() = std::move(other.get());
1037     auto const at_end =
1038         other.out_ == other.list_.end();
1039     list_ = std::move(other.list_);
1040     out_ = at_end ? list_.end() : other.out_;
1041
1042     in_size_ = other.in_size_;
1043     in_pos_ = other.in_pos_;
1044     out_pos_ = other.out_pos_;
1045     out_end_ = other.out_end_;
1046     max_ = other.max_;
1047
1048     other.in_size_ = 0;
1049     other.out_ = other.list_.end();
1050     other.in_pos_ = 0;
1051     other.out_pos_ = 0;
1052     other.out_end_ = 0;
1053 }
1054
1055 template<class Allocator>
1056 void
1057 basic_multi_buffer<Allocator>::
1058 move_assign(basic_multi_buffer& other, std::false_type)
1059 {
1060     if(this->get() != other.get())
1061     {
1062         copy_from(other);
1063         other.clear();
1064         other.shrink_to_fit();
1065     }
1066     else
1067     {
1068         move_assign(other, std::true_type{});
1069     }
1070 }
1071
1072 template<class Allocator>
1073 void
1074 basic_multi_buffer<Allocator>::
1075 copy_assign(
1076     basic_multi_buffer const& other, std::false_type)
1077 {
1078     copy_from(other);
1079 }
1080
1081 template<class Allocator>
1082 void
1083 basic_multi_buffer<Allocator>::
1084 copy_assign(
1085     basic_multi_buffer const& other, std::true_type)
1086 {
1087     clear();
1088     this->get() = other.get();
1089     copy_from(other);
1090 }
1091
1092 template<class Allocator>
1093 void
1094 basic_multi_buffer<Allocator>::
1095 swap(basic_multi_buffer& other) noexcept
1096 {
1097     swap(other, typename
1098         alloc_traits::propagate_on_container_swap{});
1099 }
1100
1101 template<class Allocator>
1102 void
1103 basic_multi_buffer<Allocator>::
1104 swap(basic_multi_buffer& other, std::true_type) noexcept
1105 {
1106     using std::swap;
1107     auto const at_end0 =
1108         out_ == list_.end();
1109     auto const at_end1 =
1110         other.out_ == other.list_.end();
1111     swap(this->get(), other.get());
1112     swap(list_, other.list_);
1113     swap(out_, other.out_);
1114     if(at_end1)
1115         out_ = list_.end();
1116     if(at_end0)
1117         other.out_ = other.list_.end();
1118     swap(in_size_, other.in_size_);
1119     swap(in_pos_, other.in_pos_);
1120     swap(out_pos_, other.out_pos_);
1121     swap(out_end_, other.out_end_);
1122 }
1123
1124 template<class Allocator>
1125 void
1126 basic_multi_buffer<Allocator>::
1127 swap(basic_multi_buffer& other, std::false_type) noexcept
1128 {
1129     BOOST_ASSERT(this->get() == other.get());
1130     using std::swap;
1131     auto const at_end0 =
1132         out_ == list_.end();
1133     auto const at_end1 =
1134         other.out_ == other.list_.end();
1135     swap(list_, other.list_);
1136     swap(out_, other.out_);
1137     if(at_end1)
1138         out_ = list_.end();
1139     if(at_end0)
1140         other.out_ = other.list_.end();
1141     swap(in_size_, other.in_size_);
1142     swap(in_pos_, other.in_pos_);
1143     swap(out_pos_, other.out_pos_);
1144     swap(out_end_, other.out_end_);
1145 }
1146
1147 template<class Allocator>
1148 void
1149 swap(
1150     basic_multi_buffer<Allocator>& lhs,
1151     basic_multi_buffer<Allocator>& rhs) noexcept
1152 {
1153     lhs.swap(rhs);
1154 }
1155
1156 template<class Allocator>
1157 void
1158 basic_multi_buffer<Allocator>::
1159 destroy(list_type& list) noexcept
1160 {
1161     for(auto it = list.begin();
1162             it != list.end();)
1163         destroy(*it++);
1164 }
1165
1166 template<class Allocator>
1167 void
1168 basic_multi_buffer<Allocator>::
1169 destroy(const_iter it)
1170 {
1171     auto& e = list_.erase(it);
1172     destroy(e);
1173 }
1174
1175 template<class Allocator>
1176 void
1177 basic_multi_buffer<Allocator>::
1178 destroy(element& e)
1179 {
1180     auto a = rebind_type{this->get()};
1181     auto const n =
1182         (sizeof(element) + e.size() +
1183             sizeof(align_type) - 1) /
1184         sizeof(align_type);
1185     e.~element();
1186     alloc_traits::deallocate(a,
1187         reinterpret_cast<align_type*>(&e), n);
1188 }
1189
1190 template<class Allocator>
1191 auto
1192 basic_multi_buffer<Allocator>::
1193 alloc(std::size_t size) ->
1194     element&
1195 {
1196     if(size > alloc_traits::max_size(this->get()))
1197         BOOST_THROW_EXCEPTION(std::length_error(
1198         "A basic_multi_buffer exceeded the allocator's maximum size"));
1199     auto a = rebind_type{this->get()};
1200     auto const p = alloc_traits::allocate(a,
1201         (sizeof(element) + size + sizeof(align_type) - 1) /
1202             sizeof(align_type));
1203     return *(::new(p) element(size));
1204 }
1205
1206 template<class Allocator>
1207 void
1208 basic_multi_buffer<Allocator>::
1209 debug_check() const
1210 {
1211 #ifndef NDEBUG
1212     BOOST_ASSERT(buffer_bytes(data()) == in_size_);
1213     if(list_.empty())
1214     {
1215         BOOST_ASSERT(in_pos_ == 0);
1216         BOOST_ASSERT(in_size_ == 0);
1217         BOOST_ASSERT(out_pos_ == 0);
1218         BOOST_ASSERT(out_end_ == 0);
1219         BOOST_ASSERT(out_ == list_.end());
1220         return;
1221     }
1222
1223     auto const& front = list_.front();
1224
1225     BOOST_ASSERT(in_pos_ < front.size());
1226
1227     if(out_ == list_.end())
1228     {
1229         BOOST_ASSERT(out_pos_ == 0);
1230         BOOST_ASSERT(out_end_ == 0);
1231     }
1232     else
1233     {
1234         auto const& out = *out_;
1235         auto const& back = list_.back();
1236
1237         BOOST_ASSERT(out_end_ <= back.size());
1238         BOOST_ASSERT(out_pos_ <  out.size());
1239         BOOST_ASSERT(&out != &front || out_pos_ >= in_pos_);
1240         BOOST_ASSERT(&out != &front || out_pos_ - in_pos_ == in_size_);
1241         BOOST_ASSERT(&out != &back  || out_pos_ <= out_end_);
1242     }
1243 #endif
1244 }
1245
1246 } // beast
1247 } // boost
1248
1249 #endif