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_FLAT_BUFFER_HPP
11 #define BOOST_BEAST_IMPL_FLAT_BUFFER_HPP
12
13 #include <boost/core/exchange.hpp>
14 #include <boost/assert.hpp>
15 #include <boost/throw_exception.hpp>
16 #include <memory>
17 #include <stdexcept>
18
19 namespace boost {
20 namespace beast {
21
22 /* Layout:
23
24 begin_ in_ out_ last_ end_
25 |<------->|<---------->|<---------->|<------->|
26 | readable | writable |
27 */
28
29 template<class Allocator>
30 basic_flat_buffer<Allocator>::
~basic_flat_buffer()31 ~basic_flat_buffer()
32 {
33 if(! begin_)
34 return;
35 alloc_traits::deallocate(
36 this->get(), begin_, capacity());
37 }
38
39 template<class Allocator>
40 basic_flat_buffer<Allocator>::
basic_flat_buffer()41 basic_flat_buffer() noexcept(default_nothrow)
42 : begin_(nullptr)
43 , in_(nullptr)
44 , out_(nullptr)
45 , last_(nullptr)
46 , end_(nullptr)
47 , max_(alloc_traits::max_size(
48 this->get()))
49 {
50 }
51
52 template<class Allocator>
53 basic_flat_buffer<Allocator>::
basic_flat_buffer(std::size_t limit)54 basic_flat_buffer(
55 std::size_t limit) noexcept(default_nothrow)
56 : begin_(nullptr)
57 , in_(nullptr)
58 , out_(nullptr)
59 , last_(nullptr)
60 , end_(nullptr)
61 , max_(limit)
62 {
63 }
64
65 template<class Allocator>
66 basic_flat_buffer<Allocator>::
basic_flat_buffer(Allocator const & alloc)67 basic_flat_buffer(Allocator const& alloc) noexcept
68 : boost::empty_value<base_alloc_type>(
69 boost::empty_init_t{}, alloc)
70 , begin_(nullptr)
71 , in_(nullptr)
72 , out_(nullptr)
73 , last_(nullptr)
74 , end_(nullptr)
75 , max_(alloc_traits::max_size(
76 this->get()))
77 {
78 }
79
80 template<class Allocator>
81 basic_flat_buffer<Allocator>::
basic_flat_buffer(std::size_t limit,Allocator const & alloc)82 basic_flat_buffer(
83 std::size_t limit,
84 Allocator const& alloc) noexcept
85 : boost::empty_value<base_alloc_type>(
86 boost::empty_init_t{}, alloc)
87 , begin_(nullptr)
88 , in_(nullptr)
89 , out_(nullptr)
90 , last_(nullptr)
91 , end_(nullptr)
92 , max_(limit)
93 {
94 }
95
96 template<class Allocator>
97 basic_flat_buffer<Allocator>::
basic_flat_buffer(basic_flat_buffer && other)98 basic_flat_buffer(basic_flat_buffer&& other) noexcept
99 : boost::empty_value<base_alloc_type>(
100 boost::empty_init_t{}, std::move(other.get()))
101 , begin_(boost::exchange(other.begin_, nullptr))
102 , in_(boost::exchange(other.in_, nullptr))
103 , out_(boost::exchange(other.out_, nullptr))
104 , last_(boost::exchange(other.last_, nullptr))
105 , end_(boost::exchange(other.end_, nullptr))
106 , max_(other.max_)
107 {
108 }
109
110 template<class Allocator>
111 basic_flat_buffer<Allocator>::
basic_flat_buffer(basic_flat_buffer && other,Allocator const & alloc)112 basic_flat_buffer(
113 basic_flat_buffer&& other,
114 Allocator const& alloc)
115 : boost::empty_value<base_alloc_type>(
116 boost::empty_init_t{}, alloc)
117 {
118 if(this->get() != other.get())
119 {
120 begin_ = nullptr;
121 in_ = nullptr;
122 out_ = nullptr;
123 last_ = nullptr;
124 end_ = nullptr;
125 max_ = other.max_;
126 copy_from(other);
127 return;
128 }
129
130 begin_ = other.begin_;
131 in_ = other.in_;
132 out_ = other.out_;
133 last_ = other.out_; // invalidate
134 end_ = other.end_;
135 max_ = other.max_;
136 BOOST_ASSERT(
137 alloc_traits::max_size(this->get()) ==
138 alloc_traits::max_size(other.get()));
139 other.begin_ = nullptr;
140 other.in_ = nullptr;
141 other.out_ = nullptr;
142 other.last_ = nullptr;
143 other.end_ = nullptr;
144 }
145
146 template<class Allocator>
147 basic_flat_buffer<Allocator>::
basic_flat_buffer(basic_flat_buffer const & other)148 basic_flat_buffer(basic_flat_buffer const& other)
149 : boost::empty_value<base_alloc_type>(boost::empty_init_t{},
150 alloc_traits::select_on_container_copy_construction(
151 other.get()))
152 , begin_(nullptr)
153 , in_(nullptr)
154 , out_(nullptr)
155 , last_(nullptr)
156 , end_(nullptr)
157 , max_(other.max_)
158 {
159 copy_from(other);
160 }
161
162 template<class Allocator>
163 basic_flat_buffer<Allocator>::
basic_flat_buffer(basic_flat_buffer const & other,Allocator const & alloc)164 basic_flat_buffer(
165 basic_flat_buffer const& other,
166 Allocator const& alloc)
167 : boost::empty_value<base_alloc_type>(
168 boost::empty_init_t{}, alloc)
169 , begin_(nullptr)
170 , in_(nullptr)
171 , out_(nullptr)
172 , last_(nullptr)
173 , end_(nullptr)
174 , max_(other.max_)
175 {
176 copy_from(other);
177 }
178
179 template<class Allocator>
180 template<class OtherAlloc>
181 basic_flat_buffer<Allocator>::
basic_flat_buffer(basic_flat_buffer<OtherAlloc> const & other)182 basic_flat_buffer(
183 basic_flat_buffer<OtherAlloc> const& other)
184 noexcept(default_nothrow)
185 : begin_(nullptr)
186 , in_(nullptr)
187 , out_(nullptr)
188 , last_(nullptr)
189 , end_(nullptr)
190 , max_(other.max_)
191 {
192 copy_from(other);
193 }
194
195 template<class Allocator>
196 template<class OtherAlloc>
197 basic_flat_buffer<Allocator>::
basic_flat_buffer(basic_flat_buffer<OtherAlloc> const & other,Allocator const & alloc)198 basic_flat_buffer(
199 basic_flat_buffer<OtherAlloc> const& other,
200 Allocator const& alloc)
201 : boost::empty_value<base_alloc_type>(
202 boost::empty_init_t{}, alloc)
203 , begin_(nullptr)
204 , in_(nullptr)
205 , out_(nullptr)
206 , last_(nullptr)
207 , end_(nullptr)
208 , max_(other.max_)
209 {
210 copy_from(other);
211 }
212
213 template<class Allocator>
214 auto
215 basic_flat_buffer<Allocator>::
operator =(basic_flat_buffer && other)216 operator=(basic_flat_buffer&& other) noexcept ->
217 basic_flat_buffer&
218 {
219 if(this == &other)
220 return *this;
221 move_assign(other, pocma{});
222 return *this;
223 }
224
225 template<class Allocator>
226 auto
227 basic_flat_buffer<Allocator>::
operator =(basic_flat_buffer const & other)228 operator=(basic_flat_buffer const& other) ->
229 basic_flat_buffer&
230 {
231 if(this == &other)
232 return *this;
233 copy_assign(other, pocca{});
234 return *this;
235 }
236
237 template<class Allocator>
238 template<class OtherAlloc>
239 auto
240 basic_flat_buffer<Allocator>::
operator =(basic_flat_buffer<OtherAlloc> const & other)241 operator=(
242 basic_flat_buffer<OtherAlloc> const& other) ->
243 basic_flat_buffer&
244 {
245 copy_from(other);
246 return *this;
247 }
248
249 template<class Allocator>
250 void
251 basic_flat_buffer<Allocator>::
reserve(std::size_t n)252 reserve(std::size_t n)
253 {
254 if(max_ < n)
255 max_ = n;
256 if(n > capacity())
257 prepare(n - size());
258 }
259
260 template<class Allocator>
261 void
262 basic_flat_buffer<Allocator>::
shrink_to_fit()263 shrink_to_fit() noexcept
264 {
265 auto const len = size();
266
267 if(len == capacity())
268 return;
269
270 char* p;
271 if(len > 0)
272 {
273 BOOST_ASSERT(begin_);
274 BOOST_ASSERT(in_);
275 #ifndef BOOST_NO_EXCEPTIONS
276 try
277 {
278 #endif
279 p = alloc(len);
280 #ifndef BOOST_NO_EXCEPTIONS
281 }
282 catch(std::exception const&)
283 {
284 // request could not be fulfilled,
285 // squelch the exception
286 return;
287 }
288 #endif
289 std::memcpy(p, in_, len);
290 }
291 else
292 {
293 p = nullptr;
294 }
295 alloc_traits::deallocate(
296 this->get(), begin_, this->capacity());
297 begin_ = p;
298 in_ = begin_;
299 out_ = begin_ + len;
300 last_ = out_;
301 end_ = out_;
302 }
303
304 template<class Allocator>
305 void
306 basic_flat_buffer<Allocator>::
clear()307 clear() noexcept
308 {
309 in_ = begin_;
310 out_ = begin_;
311 last_ = begin_;
312 }
313
314 //------------------------------------------------------------------------------
315
316 template<class Allocator>
317 auto
318 basic_flat_buffer<Allocator>::
prepare(std::size_t n)319 prepare(std::size_t n) ->
320 mutable_buffers_type
321 {
322 auto const len = size();
323 if(len > max_ || n > (max_ - len))
324 BOOST_THROW_EXCEPTION(std::length_error{
325 "basic_flat_buffer too long"});
326 if(n <= dist(out_, end_))
327 {
328 // existing capacity is sufficient
329 last_ = out_ + n;
330 return{out_, n};
331 }
332 if(n <= capacity() - len)
333 {
334 // after a memmove,
335 // existing capacity is sufficient
336 if(len > 0)
337 {
338 BOOST_ASSERT(begin_);
339 BOOST_ASSERT(in_);
340 std::memmove(begin_, in_, len);
341 }
342 in_ = begin_;
343 out_ = in_ + len;
344 last_ = out_ + n;
345 return {out_, n};
346 }
347 // allocate a new buffer
348 auto const new_size = (std::min<std::size_t>)(
349 max_,
350 (std::max<std::size_t>)(2 * len, len + n));
351 auto const p = alloc(new_size);
352 if(begin_)
353 {
354 BOOST_ASSERT(p);
355 BOOST_ASSERT(in_);
356 std::memcpy(p, in_, len);
357 alloc_traits::deallocate(
358 this->get(), begin_, capacity());
359 }
360 begin_ = p;
361 in_ = begin_;
362 out_ = in_ + len;
363 last_ = out_ + n;
364 end_ = begin_ + new_size;
365 return {out_, n};
366 }
367
368 template<class Allocator>
369 void
370 basic_flat_buffer<Allocator>::
consume(std::size_t n)371 consume(std::size_t n) noexcept
372 {
373 if(n >= dist(in_, out_))
374 {
375 in_ = begin_;
376 out_ = begin_;
377 return;
378 }
379 in_ += n;
380 }
381
382 //------------------------------------------------------------------------------
383
384 template<class Allocator>
385 template<class OtherAlloc>
386 void
387 basic_flat_buffer<Allocator>::
copy_from(basic_flat_buffer<OtherAlloc> const & other)388 copy_from(
389 basic_flat_buffer<OtherAlloc> const& other)
390 {
391 std::size_t const n = other.size();
392 if(n == 0 || n > capacity())
393 {
394 if(begin_ != nullptr)
395 {
396 alloc_traits::deallocate(
397 this->get(), begin_,
398 this->capacity());
399 begin_ = nullptr;
400 in_ = nullptr;
401 out_ = nullptr;
402 last_ = nullptr;
403 end_ = nullptr;
404 }
405 if(n == 0)
406 return;
407 begin_ = alloc(n);
408 in_ = begin_;
409 out_ = begin_ + n;
410 last_ = begin_ + n;
411 end_ = begin_ + n;
412 }
413 in_ = begin_;
414 out_ = begin_ + n;
415 last_ = begin_ + n;
416 if(begin_)
417 {
418 BOOST_ASSERT(other.begin_);
419 std::memcpy(begin_, other.in_, n);
420 }
421 }
422
423 template<class Allocator>
424 void
425 basic_flat_buffer<Allocator>::
move_assign(basic_flat_buffer & other,std::true_type)426 move_assign(basic_flat_buffer& other, std::true_type)
427 {
428 clear();
429 shrink_to_fit();
430 this->get() = std::move(other.get());
431 begin_ = other.begin_;
432 in_ = other.in_;
433 out_ = other.out_;
434 last_ = out_;
435 end_ = other.end_;
436 max_ = other.max_;
437 other.begin_ = nullptr;
438 other.in_ = nullptr;
439 other.out_ = nullptr;
440 other.last_ = nullptr;
441 other.end_ = nullptr;
442 }
443
444 template<class Allocator>
445 void
446 basic_flat_buffer<Allocator>::
move_assign(basic_flat_buffer & other,std::false_type)447 move_assign(basic_flat_buffer& other, std::false_type)
448 {
449 if(this->get() != other.get())
450 {
451 copy_from(other);
452 }
453 else
454 {
455 move_assign(other, std::true_type{});
456 }
457 }
458
459 template<class Allocator>
460 void
461 basic_flat_buffer<Allocator>::
copy_assign(basic_flat_buffer const & other,std::true_type)462 copy_assign(basic_flat_buffer const& other, std::true_type)
463 {
464 max_ = other.max_;
465 this->get() = other.get();
466 copy_from(other);
467 }
468
469 template<class Allocator>
470 void
471 basic_flat_buffer<Allocator>::
copy_assign(basic_flat_buffer const & other,std::false_type)472 copy_assign(basic_flat_buffer const& other, std::false_type)
473 {
474 clear();
475 shrink_to_fit();
476 max_ = other.max_;
477 copy_from(other);
478 }
479
480 template<class Allocator>
481 void
482 basic_flat_buffer<Allocator>::
swap(basic_flat_buffer & other)483 swap(basic_flat_buffer& other)
484 {
485 swap(other, typename
486 alloc_traits::propagate_on_container_swap{});
487 }
488
489 template<class Allocator>
490 void
491 basic_flat_buffer<Allocator>::
swap(basic_flat_buffer & other,std::true_type)492 swap(basic_flat_buffer& other, std::true_type)
493 {
494 using std::swap;
495 swap(this->get(), other.get());
496 swap(max_, other.max_);
497 swap(begin_, other.begin_);
498 swap(in_, other.in_);
499 swap(out_, other.out_);
500 last_ = this->out_;
501 other.last_ = other.out_;
502 swap(end_, other.end_);
503 }
504
505 template<class Allocator>
506 void
507 basic_flat_buffer<Allocator>::
swap(basic_flat_buffer & other,std::false_type)508 swap(basic_flat_buffer& other, std::false_type)
509 {
510 BOOST_ASSERT(this->get() == other.get());
511 using std::swap;
512 swap(max_, other.max_);
513 swap(begin_, other.begin_);
514 swap(in_, other.in_);
515 swap(out_, other.out_);
516 last_ = this->out_;
517 other.last_ = other.out_;
518 swap(end_, other.end_);
519 }
520
521 template<class Allocator>
522 void
swap(basic_flat_buffer<Allocator> & lhs,basic_flat_buffer<Allocator> & rhs)523 swap(
524 basic_flat_buffer<Allocator>& lhs,
525 basic_flat_buffer<Allocator>& rhs)
526 {
527 lhs.swap(rhs);
528 }
529
530 template<class Allocator>
531 char*
532 basic_flat_buffer<Allocator>::
alloc(std::size_t n)533 alloc(std::size_t n)
534 {
535 if(n > alloc_traits::max_size(this->get()))
536 BOOST_THROW_EXCEPTION(std::length_error(
537 "A basic_flat_buffer exceeded the allocator's maximum size"));
538 return alloc_traits::allocate(this->get(), n);
539 }
540
541 } // beast
542 } // boost
543
544 #endif
545