core/impl/flat_buffer.hpp

0001 //
0002 // Copyright (c) 2016-2019 Vinnie Falco (vinnie dot falco at gmail dot com)
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // Official repository: https://github.com/boostorg/beast
0008 //
0009
0010 #ifndef BOOST_BEAST_IMPL_FLAT_BUFFER_HPP
0011 #define BOOST_BEAST_IMPL_FLAT_BUFFER_HPP
0012
0013 #include <boost/core/exchange.hpp>
0014 #include <boost/assert.hpp>
0015 #include <boost/throw_exception.hpp>
0016 #include <memory>
0017 #include <stdexcept>
0018
0019 namespace boost {
0020 namespace beast {
0021
0022 /*  Layout:
0023
0024       begin_     in_          out_        last_      end_
0025         |<------->|<---------->|<---------->|<------->|
0026                   |  readable  |  writable  |
0027 */
0028
0029 template<class Allocator>
0030 basic_flat_buffer<Allocator>::
0031 ~basic_flat_buffer()
0032 {
0033     if(! begin_)
0034         return;
0035     alloc_traits::deallocate(
0036         this->get(), begin_, capacity());
0037 }
0038
0039 template<class Allocator>
0040 basic_flat_buffer<Allocator>::
0041 basic_flat_buffer() noexcept(default_nothrow)
0042     : begin_(nullptr)
0043     , in_(nullptr)
0044     , out_(nullptr)
0045     , last_(nullptr)
0046     , end_(nullptr)
0047     , max_(alloc_traits::max_size(
0048         this->get()))
0049 {
0050 }
0051
0052 template<class Allocator>
0053 basic_flat_buffer<Allocator>::
0054 basic_flat_buffer(
0055     std::size_t limit) noexcept(default_nothrow)
0056     : begin_(nullptr)
0057     , in_(nullptr)
0058     , out_(nullptr)
0059     , last_(nullptr)
0060     , end_(nullptr)
0061     , max_(limit)
0062 {
0063 }
0064
0065 template<class Allocator>
0066 basic_flat_buffer<Allocator>::
0067 basic_flat_buffer(Allocator const& alloc) noexcept
0068     : boost::empty_value<base_alloc_type>(
0069         boost::empty_init_t{}, alloc)
0070     , begin_(nullptr)
0071     , in_(nullptr)
0072     , out_(nullptr)
0073     , last_(nullptr)
0074     , end_(nullptr)
0075     , max_(alloc_traits::max_size(
0076         this->get()))
0077 {
0078 }
0079
0080 template<class Allocator>
0081 basic_flat_buffer<Allocator>::
0082 basic_flat_buffer(
0083     std::size_t limit,
0084     Allocator const& alloc) noexcept
0085     : boost::empty_value<base_alloc_type>(
0086         boost::empty_init_t{}, alloc)
0087     , begin_(nullptr)
0088     , in_(nullptr)
0089     , out_(nullptr)
0090     , last_(nullptr)
0091     , end_(nullptr)
0092     , max_(limit)
0093 {
0094 }
0095
0096 template<class Allocator>
0097 basic_flat_buffer<Allocator>::
0098 basic_flat_buffer(basic_flat_buffer&& other) noexcept
0099     : boost::empty_value<base_alloc_type>(
0100         boost::empty_init_t{}, std::move(other.get()))
0101     , begin_(boost::exchange(other.begin_, nullptr))
0102     , in_(boost::exchange(other.in_, nullptr))
0103     , out_(boost::exchange(other.out_, nullptr))
0104     , last_(boost::exchange(other.last_, nullptr))
0105     , end_(boost::exchange(other.end_, nullptr))
0106     , max_(other.max_)
0107 {
0108 }
0109
0110 template<class Allocator>
0111 basic_flat_buffer<Allocator>::
0112 basic_flat_buffer(
0113     basic_flat_buffer&& other,
0114     Allocator const& alloc)
0115     : boost::empty_value<base_alloc_type>(
0116         boost::empty_init_t{}, alloc)
0117 {
0118     if(this->get() != other.get())
0119     {
0120         begin_ = nullptr;
0121         in_ = nullptr;
0122         out_ = nullptr;
0123         last_ = nullptr;
0124         end_ = nullptr;
0125         max_ = other.max_;
0126         copy_from(other);
0127         return;
0128     }
0129
0130     begin_ = other.begin_;
0131     in_ = other.in_;
0132     out_ = other.out_;
0133     last_ = other.out_; // invalidate
0134     end_ = other.end_;
0135     max_ = other.max_;
0136     BOOST_ASSERT(
0137         alloc_traits::max_size(this->get()) ==
0138         alloc_traits::max_size(other.get()));
0139     other.begin_ = nullptr;
0140     other.in_ = nullptr;
0141     other.out_ = nullptr;
0142     other.last_ = nullptr;
0143     other.end_ = nullptr;
0144 }
0145
0146 template<class Allocator>
0147 basic_flat_buffer<Allocator>::
0148 basic_flat_buffer(basic_flat_buffer const& other)
0149     : boost::empty_value<base_alloc_type>(boost::empty_init_t{},
0150         alloc_traits::select_on_container_copy_construction(
0151             other.get()))
0152     , begin_(nullptr)
0153     , in_(nullptr)
0154     , out_(nullptr)
0155     , last_(nullptr)
0156     , end_(nullptr)
0157     , max_(other.max_)
0158 {
0159     copy_from(other);
0160 }
0161
0162 template<class Allocator>
0163 basic_flat_buffer<Allocator>::
0164 basic_flat_buffer(
0165     basic_flat_buffer const& other,
0166     Allocator const& alloc)
0167     : boost::empty_value<base_alloc_type>(
0168         boost::empty_init_t{}, alloc)
0169     , begin_(nullptr)
0170     , in_(nullptr)
0171     , out_(nullptr)
0172     , last_(nullptr)
0173     , end_(nullptr)
0174     , max_(other.max_)
0175 {
0176     copy_from(other);
0177 }
0178
0179 template<class Allocator>
0180 template<class OtherAlloc>
0181 basic_flat_buffer<Allocator>::
0182 basic_flat_buffer(
0183     basic_flat_buffer<OtherAlloc> const& other)
0184         noexcept(default_nothrow)
0185     : begin_(nullptr)
0186     , in_(nullptr)
0187     , out_(nullptr)
0188     , last_(nullptr)
0189     , end_(nullptr)
0190     , max_(other.max_)
0191 {
0192     copy_from(other);
0193 }
0194
0195 template<class Allocator>
0196 template<class OtherAlloc>
0197 basic_flat_buffer<Allocator>::
0198 basic_flat_buffer(
0199     basic_flat_buffer<OtherAlloc> const& other,
0200     Allocator const& alloc)
0201     : boost::empty_value<base_alloc_type>(
0202         boost::empty_init_t{}, alloc)
0203     , begin_(nullptr)
0204     , in_(nullptr)
0205     , out_(nullptr)
0206     , last_(nullptr)
0207     , end_(nullptr)
0208     , max_(other.max_)
0209 {
0210     copy_from(other);
0211 }
0212
0213 template<class Allocator>
0214 auto
0215 basic_flat_buffer<Allocator>::
0216 operator=(basic_flat_buffer&& other) noexcept ->
0217     basic_flat_buffer&
0218 {
0219     if(this == &other)
0220         return *this;
0221     move_assign(other, pocma{});
0222     return *this;
0223 }
0224
0225 template<class Allocator>
0226 auto
0227 basic_flat_buffer<Allocator>::
0228 operator=(basic_flat_buffer const& other) ->
0229     basic_flat_buffer&
0230 {
0231     if(this == &other)
0232         return *this;
0233     copy_assign(other, pocca{});
0234     return *this;
0235 }
0236
0237 template<class Allocator>
0238 template<class OtherAlloc>
0239 auto
0240 basic_flat_buffer<Allocator>::
0241 operator=(
0242     basic_flat_buffer<OtherAlloc> const& other) ->
0243     basic_flat_buffer&
0244 {
0245     copy_from(other);
0246     return *this;
0247 }
0248
0249 template<class Allocator>
0250 void
0251 basic_flat_buffer<Allocator>::
0252 reserve(std::size_t n)
0253 {
0254     if(max_ < n)
0255         max_ = n;
0256     if(n > capacity())
0257         prepare(n - size());
0258 }
0259
0260 template<class Allocator>
0261 void
0262 basic_flat_buffer<Allocator>::
0263 shrink_to_fit() noexcept
0264 {
0265     auto const len = size();
0266
0267     if(len == capacity())
0268         return;
0269
0270     char* p;
0271     if(len > 0)
0272     {
0273         BOOST_ASSERT(begin_);
0274         BOOST_ASSERT(in_);
0275 #ifndef BOOST_NO_EXCEPTIONS
0276         try
0277         {
0278 #endif
0279             p = alloc(len);
0280 #ifndef BOOST_NO_EXCEPTIONS
0281         }
0282         catch(std::exception const&)
0283         {
0284             // request could not be fulfilled,
0285             // squelch the exception
0286             return;
0287         }
0288 #endif
0289         std::memcpy(p, in_, len);
0290     }
0291     else
0292     {
0293         p = nullptr;
0294     }
0295     alloc_traits::deallocate(
0296         this->get(), begin_, this->capacity());
0297     begin_ = p;
0298     in_ = begin_;
0299     out_ = begin_ + len;
0300     last_ = out_;
0301     end_ = out_;
0302 }
0303
0304 template<class Allocator>
0305 void
0306 basic_flat_buffer<Allocator>::
0307 clear() noexcept
0308 {
0309     in_ = begin_;
0310     out_ = begin_;
0311     last_ = begin_;
0312 }
0313
0314 //------------------------------------------------------------------------------
0315
0316 template<class Allocator>
0317 auto
0318 basic_flat_buffer<Allocator>::
0319 prepare(std::size_t n) ->
0320     mutable_buffers_type
0321 {
0322     auto const len = size();
0323     if(len > max_ || n > (max_ - len))
0324         BOOST_THROW_EXCEPTION(std::length_error{
0325             "basic_flat_buffer too long"});
0326     if(n <= dist(out_, end_))
0327     {
0328         // existing capacity is sufficient
0329         last_ = out_ + n;
0330         return{out_, n};
0331     }
0332     if(n <= capacity() - len)
0333     {
0334         // after a memmove,
0335         // existing capacity is sufficient
0336         if(len > 0)
0337         {
0338             BOOST_ASSERT(begin_);
0339             BOOST_ASSERT(in_);
0340             std::memmove(begin_, in_, len);
0341         }
0342         in_ = begin_;
0343         out_ = in_ + len;
0344         last_ = out_ + n;
0345         return {out_, n};
0346     }
0347     // allocate a new buffer
0348     auto const new_size = (std::min<std::size_t>)(
0349         max_,
0350         (std::max<std::size_t>)(2 * len, len + n));
0351     auto const p = alloc(new_size);
0352     if(begin_)
0353     {
0354         BOOST_ASSERT(p);
0355         BOOST_ASSERT(in_);
0356         std::memcpy(p, in_, len);
0357         alloc_traits::deallocate(
0358             this->get(), begin_, capacity());
0359     }
0360     begin_ = p;
0361     in_ = begin_;
0362     out_ = in_ + len;
0363     last_ = out_ + n;
0364     end_ = begin_ + new_size;
0365     return {out_, n};
0366 }
0367
0368 template<class Allocator>
0369 void
0370 basic_flat_buffer<Allocator>::
0371 consume(std::size_t n) noexcept
0372 {
0373     if(n >= dist(in_, out_))
0374     {
0375         in_ = begin_;
0376         out_ = begin_;
0377         return;
0378     }
0379     in_ += n;
0380 }
0381
0382 //------------------------------------------------------------------------------
0383
0384 template<class Allocator>
0385 template<class OtherAlloc>
0386 void
0387 basic_flat_buffer<Allocator>::
0388 copy_from(
0389     basic_flat_buffer<OtherAlloc> const& other)
0390 {
0391     std::size_t const n = other.size();
0392     if(n == 0 || n > capacity())
0393     {
0394         if(begin_ != nullptr)
0395         {
0396             alloc_traits::deallocate(
0397                 this->get(), begin_,
0398                 this->capacity());
0399             begin_ = nullptr;
0400             in_ = nullptr;
0401             out_ = nullptr;
0402             last_ = nullptr;
0403             end_ = nullptr;
0404         }
0405         if(n == 0)
0406             return;
0407         begin_ = alloc(n);
0408         in_ = begin_;
0409         out_ = begin_ + n;
0410         last_ = begin_ + n;
0411         end_ = begin_ + n;
0412     }
0413     in_ = begin_;
0414     out_ = begin_ + n;
0415     last_ = begin_ + n;
0416     if(begin_)
0417     {
0418         BOOST_ASSERT(other.begin_);
0419         std::memcpy(begin_, other.in_, n);
0420     }
0421 }
0422
0423 template<class Allocator>
0424 void
0425 basic_flat_buffer<Allocator>::
0426 move_assign(basic_flat_buffer& other, std::true_type)
0427 {
0428     clear();
0429     shrink_to_fit();
0430     this->get() = std::move(other.get());
0431     begin_ = other.begin_;
0432     in_ = other.in_;
0433     out_ = other.out_;
0434     last_ = out_;
0435     end_ = other.end_;
0436     max_ = other.max_;
0437     other.begin_ = nullptr;
0438     other.in_ = nullptr;
0439     other.out_ = nullptr;
0440     other.last_ = nullptr;
0441     other.end_ = nullptr;
0442 }
0443
0444 template<class Allocator>
0445 void
0446 basic_flat_buffer<Allocator>::
0447 move_assign(basic_flat_buffer& other, std::false_type)
0448 {
0449     if(this->get() != other.get())
0450     {
0451         copy_from(other);
0452     }
0453     else
0454     {
0455         move_assign(other, std::true_type{});
0456     }
0457 }
0458
0459 template<class Allocator>
0460 void
0461 basic_flat_buffer<Allocator>::
0462 copy_assign(basic_flat_buffer const& other, std::true_type)
0463 {
0464     max_ = other.max_;
0465     this->get() = other.get();
0466     copy_from(other);
0467 }
0468
0469 template<class Allocator>
0470 void
0471 basic_flat_buffer<Allocator>::
0472 copy_assign(basic_flat_buffer const& other, std::false_type)
0473 {
0474     clear();
0475     shrink_to_fit();
0476     max_ = other.max_;
0477     copy_from(other);
0478 }
0479
0480 template<class Allocator>
0481 void
0482 basic_flat_buffer<Allocator>::
0483 swap(basic_flat_buffer& other)
0484 {
0485     swap(other, typename
0486         alloc_traits::propagate_on_container_swap{});
0487 }
0488
0489 template<class Allocator>
0490 void
0491 basic_flat_buffer<Allocator>::
0492 swap(basic_flat_buffer& other, std::true_type)
0493 {
0494     using std::swap;
0495     swap(this->get(), other.get());
0496     swap(max_, other.max_);
0497     swap(begin_, other.begin_);
0498     swap(in_, other.in_);
0499     swap(out_, other.out_);
0500     last_ = this->out_;
0501     other.last_ = other.out_;
0502     swap(end_, other.end_);
0503 }
0504
0505 template<class Allocator>
0506 void
0507 basic_flat_buffer<Allocator>::
0508 swap(basic_flat_buffer& other, std::false_type)
0509 {
0510     BOOST_ASSERT(this->get() == other.get());
0511     using std::swap;
0512     swap(max_, other.max_);
0513     swap(begin_, other.begin_);
0514     swap(in_, other.in_);
0515     swap(out_, other.out_);
0516     last_ = this->out_;
0517     other.last_ = other.out_;
0518     swap(end_, other.end_);
0519 }
0520
0521 template<class Allocator>
0522 void
0523 swap(
0524     basic_flat_buffer<Allocator>& lhs,
0525     basic_flat_buffer<Allocator>& rhs)
0526 {
0527     lhs.swap(rhs);
0528 }
0529
0530 template<class Allocator>
0531 char*
0532 basic_flat_buffer<Allocator>::
0533 alloc(std::size_t n)
0534 {
0535     if(n > alloc_traits::max_size(this->get()))
0536         BOOST_THROW_EXCEPTION(std::length_error(
0537             "A basic_flat_buffer exceeded the allocator's maximum size"));
0538     return alloc_traits::allocate(this->get(), n);
0539 }
0540
0541 } // beast
0542 } // boost
0543
0544 #endif