TLA Line data Source code
1 : //
2 : // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.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/json
8 : //
9 :
10 : #ifndef BOOST_JSON_IMPL_ARRAY_IPP
11 : #define BOOST_JSON_IMPL_ARRAY_IPP
12 :
13 : #include <boost/core/detail/static_assert.hpp>
14 : #include <boost/container_hash/hash.hpp>
15 : #include <boost/json/array.hpp>
16 : #include <boost/json/pilfer.hpp>
17 : #include <boost/json/detail/except.hpp>
18 : #include <cstdlib>
19 : #include <limits>
20 : #include <new>
21 : #include <utility>
22 :
23 : namespace boost {
24 : namespace json {
25 :
26 : //----------------------------------------------------------
27 :
28 : constexpr array::table::table() = default;
29 :
30 : // empty arrays point here
31 : BOOST_JSON_REQUIRE_CONST_INIT
32 : array::table array::empty_;
33 :
34 : auto
35 HIT 2553 : array::
36 : table::
37 : allocate(
38 : std::size_t capacity,
39 : storage_ptr const& sp) ->
40 : table*
41 : {
42 2553 : BOOST_ASSERT(capacity > 0);
43 2553 : if(capacity > array::max_size())
44 : {
45 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
46 2 : detail::throw_system_error( error::array_too_large, &loc );
47 : }
48 : auto p = reinterpret_cast<
49 2551 : table*>(sp->allocate(
50 : sizeof(table) +
51 2551 : capacity * sizeof(value),
52 : alignof(value)));
53 2412 : p->capacity = static_cast<
54 : std::uint32_t>(capacity);
55 2412 : return p;
56 : }
57 :
58 : void
59 4442 : array::
60 : table::
61 : deallocate(
62 : table* p,
63 : storage_ptr const& sp)
64 : {
65 4442 : if(p->capacity == 0)
66 2034 : return;
67 2408 : sp->deallocate(p,
68 : sizeof(table) +
69 2408 : p->capacity * sizeof(value),
70 : alignof(value));
71 : }
72 :
73 : //----------------------------------------------------------
74 :
75 37 : array::
76 : revert_insert::
77 : revert_insert(
78 : const_iterator pos,
79 : std::size_t n,
80 37 : array& arr)
81 37 : : arr_(&arr)
82 37 : , i_(pos - arr_->data())
83 37 : , n_(n)
84 : {
85 37 : BOOST_ASSERT(
86 : pos >= arr_->begin() &&
87 : pos <= arr_->end());
88 74 : if( n_ <= arr_->capacity() -
89 37 : arr_->size())
90 : {
91 : // fast path
92 2 : p = arr_->data() + i_;
93 2 : if(n_ == 0)
94 1 : return;
95 1 : relocate(
96 1 : p + n_,
97 : p,
98 1 : arr_->size() - i_);
99 1 : arr_->t_->size = static_cast<
100 : std::uint32_t>(
101 1 : arr_->t_->size + n_);
102 1 : return;
103 : }
104 35 : if(n_ > max_size() - arr_->size())
105 : {
106 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
107 1 : detail::throw_system_error( error::array_too_large, &loc );
108 : }
109 34 : auto t = table::allocate(
110 34 : arr_->growth(arr_->size() + n_),
111 34 : arr_->sp_);
112 24 : t->size = static_cast<std::uint32_t>(
113 24 : arr_->size() + n_);
114 24 : p = &(*t)[0] + i_;
115 24 : relocate(
116 24 : &(*t)[0],
117 24 : arr_->data(),
118 24 : i_);
119 24 : relocate(
120 24 : &(*t)[i_ + n_],
121 24 : arr_->data() + i_,
122 24 : arr_->size() - i_);
123 24 : t = detail::exchange(arr_->t_, t);
124 24 : table::deallocate(t, arr_->sp_);
125 : }
126 :
127 26 : array::
128 : revert_insert::
129 8 : ~revert_insert()
130 : {
131 26 : if(! arr_)
132 18 : return;
133 8 : BOOST_ASSERT(n_ != 0);
134 : auto const pos =
135 8 : arr_->data() + i_;
136 8 : arr_->destroy(pos, p);
137 8 : arr_->t_->size = static_cast<
138 : std::uint32_t>(
139 8 : arr_->t_->size - n_);
140 8 : relocate(
141 : pos,
142 8 : pos + n_,
143 8 : arr_->size() - i_);
144 26 : }
145 :
146 : //----------------------------------------------------------
147 :
148 : void
149 25 : array::
150 : destroy(
151 : value* first, value* last) noexcept
152 : {
153 25 : if(sp_.is_not_shared_and_deallocate_is_trivial())
154 1 : return;
155 50 : while(last-- != first)
156 26 : last->~value();
157 : }
158 :
159 : void
160 3699 : array::
161 : destroy() noexcept
162 : {
163 3699 : if(sp_.is_not_shared_and_deallocate_is_trivial())
164 5 : return;
165 3694 : auto last = end();
166 3694 : auto const first = begin();
167 20870 : while(last-- != first)
168 17176 : last->~value();
169 3694 : table::deallocate(t_, sp_);
170 : }
171 :
172 : //----------------------------------------------------------
173 : //
174 : // Special Members
175 : //
176 : //----------------------------------------------------------
177 :
178 2120 : array::
179 2120 : array(detail::unchecked_array&& ua)
180 2120 : : sp_(ua.storage())
181 : {
182 : BOOST_CORE_STATIC_ASSERT( alignof(table) == alignof(value) );
183 2120 : if(ua.size() == 0)
184 : {
185 819 : t_ = &empty_;
186 819 : return;
187 : }
188 1301 : t_= table::allocate(
189 1301 : ua.size(), sp_);
190 1263 : t_->size = static_cast<
191 1263 : std::uint32_t>(ua.size());
192 1263 : ua.relocate(data());
193 38 : }
194 :
195 3635 : array::
196 : ~array() noexcept
197 : {
198 3635 : destroy();
199 3635 : }
200 :
201 35 : array::
202 : array(
203 : std::size_t count,
204 : value const& v,
205 35 : storage_ptr sp)
206 35 : : sp_(std::move(sp))
207 : {
208 35 : if(count == 0)
209 : {
210 1 : t_ = &empty_;
211 1 : return;
212 : }
213 63 : t_= table::allocate(
214 34 : count, sp_);
215 29 : t_->size = 0;
216 29 : revert_construct r(*this);
217 98 : while(count--)
218 : {
219 101 : ::new(end()) value(v, sp_);
220 69 : ++t_->size;
221 : }
222 13 : r.commit();
223 50 : }
224 :
225 16 : array::
226 : array(
227 : std::size_t count,
228 16 : storage_ptr sp)
229 16 : : sp_(std::move(sp))
230 : {
231 16 : if(count == 0)
232 : {
233 1 : t_ = &empty_;
234 1 : return;
235 : }
236 26 : t_ = table::allocate(
237 15 : count, sp_);
238 11 : t_->size = static_cast<
239 : std::uint32_t>(count);
240 11 : auto p = data();
241 : do
242 : {
243 34 : ::new(p++) value(sp_);
244 : }
245 34 : while(--count);
246 4 : }
247 :
248 8 : array::
249 8 : array(array const& other)
250 8 : : array(other, other.sp_)
251 : {
252 8 : }
253 :
254 153 : array::
255 : array(
256 : array const& other,
257 153 : storage_ptr sp)
258 153 : : sp_(std::move(sp))
259 : {
260 153 : if(other.empty())
261 : {
262 14 : t_ = &empty_;
263 14 : return;
264 : }
265 139 : t_ = table::allocate(
266 139 : other.size(), sp_);
267 120 : t_->size = 0;
268 120 : revert_construct r(*this);
269 120 : auto src = other.data();
270 120 : auto dest = data();
271 120 : auto const n = other.size();
272 : do
273 : {
274 13 : ::new(dest++) value(
275 2412 : *src++, sp_);
276 2373 : ++t_->size;
277 : }
278 2373 : while(t_->size < n);
279 107 : r.commit();
280 152 : }
281 :
282 265 : array::
283 : array(
284 : array&& other,
285 265 : storage_ptr sp)
286 265 : : sp_(std::move(sp))
287 : {
288 265 : if(*sp_ == *other.sp_)
289 : {
290 : // same resource
291 484 : t_ = detail::exchange(
292 242 : other.t_, &empty_);
293 246 : return;
294 : }
295 23 : else if(other.empty())
296 : {
297 4 : t_ = &empty_;
298 4 : return;
299 : }
300 : // copy
301 19 : t_ = table::allocate(
302 19 : other.size(), sp_);
303 14 : t_->size = 0;
304 14 : revert_construct r(*this);
305 14 : auto src = other.data();
306 14 : auto dest = data();
307 14 : auto const n = other.size();
308 : do
309 : {
310 6 : ::new(dest++) value(
311 48 : *src++, sp_);
312 30 : ++t_->size;
313 : }
314 30 : while(t_->size < n);
315 8 : r.commit();
316 25 : }
317 :
318 247 : array::
319 : array(
320 : std::initializer_list<
321 : value_ref> init,
322 247 : storage_ptr sp)
323 247 : : sp_(std::move(sp))
324 : {
325 247 : if(init.size() == 0)
326 : {
327 5 : t_ = &empty_;
328 5 : return;
329 : }
330 242 : t_ = table::allocate(
331 242 : init.size(), sp_);
332 215 : t_->size = 0;
333 215 : revert_construct r(*this);
334 215 : value_ref::write_array(
335 215 : data(), init, sp_);
336 200 : t_->size = static_cast<
337 200 : std::uint32_t>(init.size());
338 200 : r.commit();
339 257 : }
340 :
341 : //----------------------------------------------------------
342 :
343 : array&
344 16 : array::
345 : operator=(array const& other)
346 : {
347 32 : array(other,
348 12 : storage()).swap(*this);
349 12 : return *this;
350 : }
351 :
352 : array&
353 7 : array::
354 : operator=(array&& other)
355 : {
356 14 : array(std::move(other),
357 5 : storage()).swap(*this);
358 5 : return *this;
359 : }
360 :
361 : array&
362 9 : array::
363 : operator=(
364 : std::initializer_list<value_ref> init)
365 : {
366 18 : array(init,
367 5 : storage()).swap(*this);
368 5 : return *this;
369 : }
370 :
371 : //----------------------------------------------------------
372 : //
373 : // Element access
374 : //
375 : //----------------------------------------------------------
376 :
377 : system::result<value&>
378 12 : array::try_at(std::size_t pos) noexcept
379 : {
380 12 : if(pos >= t_->size)
381 : {
382 8 : system::error_code ec;
383 8 : BOOST_JSON_FAIL(ec, error::out_of_range);
384 8 : return ec;
385 : }
386 4 : return (*t_)[pos];
387 : }
388 :
389 : system::result<value const&>
390 106 : array::try_at(std::size_t pos) const noexcept
391 : {
392 106 : if(pos >= t_->size)
393 : {
394 12 : system::error_code ec;
395 12 : BOOST_JSON_FAIL(ec, error::out_of_range);
396 12 : return ec;
397 : }
398 94 : return (*t_)[pos];
399 : }
400 :
401 : value const&
402 100 : array::
403 : array::at(std::size_t pos, source_location const& loc) const&
404 : {
405 100 : return try_at(pos).value(loc);
406 : }
407 :
408 : //----------------------------------------------------------
409 : //
410 : // Capacity
411 : //
412 : //----------------------------------------------------------
413 :
414 : void
415 6 : array::
416 : shrink_to_fit() noexcept
417 : {
418 6 : if(capacity() <= size())
419 2 : return;
420 4 : if(size() == 0)
421 : {
422 1 : table::deallocate(t_, sp_);
423 1 : t_ = &empty_;
424 1 : return;
425 : }
426 :
427 : #ifndef BOOST_NO_EXCEPTIONS
428 : try
429 : {
430 : #endif
431 3 : auto t = table::allocate(
432 3 : size(), sp_);
433 4 : relocate(
434 2 : &(*t)[0],
435 : data(),
436 : size());
437 2 : t->size = static_cast<
438 2 : std::uint32_t>(size());
439 2 : t = detail::exchange(
440 2 : t_, t);
441 2 : table::deallocate(t, sp_);
442 : #ifndef BOOST_NO_EXCEPTIONS
443 : }
444 1 : catch(...)
445 : {
446 : // eat the exception
447 1 : return;
448 1 : }
449 : #endif
450 : }
451 :
452 : //----------------------------------------------------------
453 : //
454 : // Modifiers
455 : //
456 : //----------------------------------------------------------
457 :
458 : void
459 4 : array::
460 : clear() noexcept
461 : {
462 4 : if(size() == 0)
463 1 : return;
464 3 : destroy(
465 : begin(), end());
466 3 : t_->size = 0;
467 : }
468 :
469 : auto
470 3 : array::
471 : insert(
472 : const_iterator pos,
473 : value const& v) ->
474 : iterator
475 : {
476 3 : return emplace(pos, v);
477 : }
478 :
479 : auto
480 3 : array::
481 : insert(
482 : const_iterator pos,
483 : value&& v) ->
484 : iterator
485 : {
486 3 : return emplace(pos, std::move(v));
487 : }
488 :
489 : auto
490 10 : array::
491 : insert(
492 : const_iterator pos,
493 : std::size_t count,
494 : value const& v) ->
495 : iterator
496 : {
497 : revert_insert r(
498 10 : pos, count, *this);
499 17 : while(count--)
500 : {
501 16 : ::new(r.p) value(v, sp_);
502 10 : ++r.p;
503 : }
504 8 : return r.commit();
505 7 : }
506 :
507 : auto
508 3 : array::
509 : insert(
510 : const_iterator pos,
511 : std::initializer_list<
512 : value_ref> init) ->
513 : iterator
514 : {
515 : revert_insert r(
516 3 : pos, init.size(), *this);
517 2 : value_ref::write_array(
518 2 : r.p, init, sp_);
519 2 : return r.commit();
520 2 : }
521 :
522 : auto
523 7 : array::
524 : erase(
525 : const_iterator pos) noexcept ->
526 : iterator
527 : {
528 7 : BOOST_ASSERT(
529 : pos >= begin() &&
530 : pos <= end());
531 7 : return erase(pos, pos + 1);
532 : }
533 :
534 : auto
535 8 : array::
536 : erase(
537 : const_iterator first,
538 : const_iterator last) noexcept ->
539 : iterator
540 : {
541 8 : BOOST_ASSERT(
542 : first >= begin() &&
543 : last >= first &&
544 : last <= end());
545 8 : std::size_t const n =
546 8 : last - first;
547 8 : auto const p = &(*t_)[0] +
548 8 : (first - &(*t_)[0]);
549 8 : destroy(p, p + n);
550 8 : relocate(p, p + n,
551 8 : t_->size - (last -
552 8 : &(*t_)[0]));
553 8 : t_->size = static_cast<
554 8 : std::uint32_t>(t_->size - n);
555 8 : return p;
556 : }
557 :
558 : void
559 4 : array::
560 : push_back(value const& v)
561 : {
562 4 : emplace_back(v);
563 2 : }
564 :
565 : void
566 9 : array::
567 : push_back(value&& v)
568 : {
569 9 : emplace_back(std::move(v));
570 7 : }
571 :
572 : void
573 3 : array::
574 : pop_back() noexcept
575 : {
576 3 : auto const p = &back();
577 3 : destroy(p, p + 1);
578 3 : --t_->size;
579 3 : }
580 :
581 : void
582 15 : array::
583 : resize(std::size_t count)
584 : {
585 15 : if(count <= t_->size)
586 : {
587 : // shrink
588 4 : destroy(
589 2 : &(*t_)[0] + count,
590 2 : &(*t_)[0] + t_->size);
591 2 : t_->size = static_cast<
592 : std::uint32_t>(count);
593 2 : return;
594 : }
595 :
596 13 : reserve(count);
597 12 : auto p = &(*t_)[t_->size];
598 12 : auto const end = &(*t_)[count];
599 32 : while(p != end)
600 20 : ::new(p++) value(sp_);
601 12 : t_->size = static_cast<
602 : std::uint32_t>(count);
603 : }
604 :
605 : void
606 7 : array::
607 : resize(
608 : std::size_t count,
609 : value const& v)
610 : {
611 7 : if(count <= size())
612 : {
613 : // shrink
614 2 : destroy(
615 1 : data() + count,
616 1 : data() + size());
617 1 : t_->size = static_cast<
618 : std::uint32_t>(count);
619 1 : return;
620 : }
621 6 : count -= size();
622 : revert_insert r(
623 6 : end(), count, *this);
624 9 : while(count--)
625 : {
626 12 : ::new(r.p) value(v, sp_);
627 4 : ++r.p;
628 : }
629 1 : r.commit();
630 5 : }
631 :
632 : void
633 28 : array::
634 : swap(array& other)
635 : {
636 28 : if(*sp_ == *other.sp_)
637 : {
638 48 : t_ = detail::exchange(
639 24 : other.t_, t_);
640 24 : return;
641 : }
642 : array temp1(
643 4 : std::move(*this),
644 9 : other.storage());
645 : array temp2(
646 3 : std::move(other),
647 7 : this->storage());
648 2 : this->~array();
649 6 : ::new(this) array(
650 2 : pilfer(temp2));
651 2 : other.~array();
652 6 : ::new(&other) array(
653 2 : pilfer(temp1));
654 3 : }
655 :
656 : //----------------------------------------------------------
657 : //
658 : // Private
659 : //
660 : //----------------------------------------------------------
661 :
662 : std::size_t
663 786 : array::
664 : growth(
665 : std::size_t new_size) const
666 : {
667 786 : if(new_size > max_size())
668 : {
669 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
670 1 : detail::throw_system_error( error::array_too_large, &loc );
671 : }
672 785 : std::size_t const old = capacity();
673 785 : if(old > max_size() - old / 2)
674 1 : return new_size;
675 784 : std::size_t const g =
676 784 : old + old / 2; // 1.5x
677 784 : if(g < new_size)
678 704 : return new_size;
679 80 : return g;
680 : }
681 :
682 : // precondition: new_capacity > capacity()
683 : void
684 674 : array::
685 : reserve_impl(
686 : std::size_t new_capacity)
687 : {
688 674 : BOOST_ASSERT(
689 : new_capacity > t_->capacity);
690 673 : auto t = table::allocate(
691 674 : growth(new_capacity), sp_);
692 653 : relocate(
693 653 : &(*t)[0],
694 653 : &(*t_)[0],
695 653 : t_->size);
696 653 : t->size = t_->size;
697 653 : t = detail::exchange(t_, t);
698 653 : table::deallocate(t, sp_);
699 653 : }
700 :
701 : // precondition: pv is not aliased
702 : value&
703 7604 : array::
704 : push_back(
705 : pilfered<value> pv)
706 : {
707 7604 : auto const n = t_->size;
708 7604 : if(n < t_->capacity)
709 : {
710 : // fast path
711 : auto& v = *::new(
712 7537 : &(*t_)[n]) value(pv);
713 7537 : ++t_->size;
714 7537 : return v;
715 : }
716 : auto const t =
717 67 : detail::exchange(t_,
718 : table::allocate(
719 67 : growth(n + 1),
720 67 : sp_));
721 : auto& v = *::new(
722 62 : &(*t_)[n]) value(pv);
723 62 : relocate(
724 62 : &(*t_)[0],
725 62 : &(*t)[0],
726 : n);
727 62 : t_->size = n + 1;
728 62 : table::deallocate(t, sp_);
729 62 : return v;
730 : }
731 :
732 : // precondition: pv is not aliased
733 : auto
734 12 : array::
735 : insert(
736 : const_iterator pos,
737 : pilfered<value> pv) ->
738 : iterator
739 : {
740 12 : BOOST_ASSERT(
741 : pos >= begin() &&
742 : pos <= end());
743 12 : std::size_t const n =
744 12 : t_->size;
745 : std::size_t const i =
746 12 : pos - &(*t_)[0];
747 12 : if(n < t_->capacity)
748 : {
749 : // fast path
750 : auto const p =
751 1 : &(*t_)[i];
752 1 : relocate(
753 : p + 1,
754 : p,
755 : n - i);
756 1 : ::new(p) value(pv);
757 1 : ++t_->size;
758 1 : return p;
759 : }
760 : auto t =
761 11 : table::allocate(
762 11 : growth(n + 1), sp_);
763 6 : auto const p = &(*t)[i];
764 6 : ::new(p) value(pv);
765 6 : relocate(
766 6 : &(*t)[0],
767 6 : &(*t_)[0],
768 : i);
769 6 : relocate(
770 : p + 1,
771 6 : &(*t_)[i],
772 : n - i);
773 6 : t->size = static_cast<
774 6 : std::uint32_t>(size() + 1);
775 6 : t = detail::exchange(t_, t);
776 6 : table::deallocate(t, sp_);
777 6 : return p;
778 : }
779 :
780 : //----------------------------------------------------------
781 :
782 : bool
783 79 : array::
784 : equal(
785 : array const& other) const noexcept
786 : {
787 79 : if(size() != other.size())
788 2 : return false;
789 3250 : for(std::size_t i = 0; i < size(); ++i)
790 3179 : if((*this)[i] != other[i])
791 6 : return false;
792 71 : return true;
793 : }
794 :
795 : } // namespace json
796 : } // namespace boost
797 :
798 : //----------------------------------------------------------
799 : //
800 : // std::hash specialization
801 : //
802 : //----------------------------------------------------------
803 :
804 : std::size_t
805 12 : std::hash<::boost::json::array>::operator()(
806 : ::boost::json::array const& ja) const noexcept
807 : {
808 12 : return ::boost::hash< ::boost::json::array >()( ja );
809 : }
810 :
811 : //----------------------------------------------------------
812 :
813 : #endif
|
