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 2602 : array::
36 : table::
37 : allocate(
38 : std::size_t capacity,
39 : storage_ptr const& sp) ->
40 : table*
41 : {
42 2602 : BOOST_ASSERT(capacity > 0);
43 2602 : 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 2600 : table*>(sp->allocate(
50 : sizeof(table) +
51 2600 : capacity * sizeof(value),
52 : alignof(value)));
53 2451 : p->capacity = static_cast<
54 : std::uint32_t>(capacity);
55 2451 : return p;
56 : }
57 :
58 : void
59 4496 : array::
60 : table::
61 : deallocate(
62 : table* p,
63 : storage_ptr const& sp)
64 : {
65 4496 : if(p->capacity == 0)
66 2049 : return;
67 2447 : sp->deallocate(p,
68 : sizeof(table) +
69 2447 : p->capacity * sizeof(value),
70 : alignof(value));
71 : }
72 :
73 : //----------------------------------------------------------
74 :
75 44 : array::
76 : revert_insert::
77 : revert_insert(
78 : const_iterator pos,
79 : std::size_t n,
80 44 : array& arr)
81 44 : : arr_(&arr)
82 44 : , i_(pos - arr_->data())
83 44 : , n_(n)
84 : {
85 44 : BOOST_ASSERT(
86 : pos >= arr_->begin() &&
87 : pos <= arr_->end());
88 88 : if( n_ <= arr_->capacity() -
89 44 : 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 42 : 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 41 : auto t = table::allocate(
110 41 : arr_->growth(arr_->size() + n_),
111 41 : arr_->sp_);
112 28 : t->size = static_cast<std::uint32_t>(
113 28 : arr_->size() + n_);
114 28 : p = &(*t)[0] + i_;
115 28 : relocate(
116 28 : &(*t)[0],
117 28 : arr_->data(),
118 28 : i_);
119 28 : relocate(
120 28 : &(*t)[i_ + n_],
121 28 : arr_->data() + i_,
122 28 : arr_->size() - i_);
123 28 : t = detail::exchange(arr_->t_, t);
124 28 : table::deallocate(t, arr_->sp_);
125 : }
126 :
127 30 : array::
128 : revert_insert::
129 9 : ~revert_insert()
130 : {
131 30 : if(! arr_)
132 21 : return;
133 9 : BOOST_ASSERT(n_ != 0);
134 : auto const pos =
135 9 : arr_->data() + i_;
136 9 : arr_->destroy(pos, p);
137 9 : arr_->t_->size = static_cast<
138 : std::uint32_t>(
139 9 : arr_->t_->size - n_);
140 9 : relocate(
141 : pos,
142 9 : pos + n_,
143 9 : arr_->size() - i_);
144 30 : }
145 :
146 : //----------------------------------------------------------
147 :
148 : void
149 26 : array::
150 : destroy(
151 : value* first, value* last) noexcept
152 : {
153 26 : if(sp_.is_not_shared_and_deallocate_is_trivial())
154 1 : return;
155 54 : while(last-- != first)
156 29 : last->~value();
157 : }
158 :
159 : void
160 3741 : array::
161 : destroy() noexcept
162 : {
163 3741 : if(sp_.is_not_shared_and_deallocate_is_trivial())
164 5 : return;
165 3736 : auto last = end();
166 3736 : auto const first = begin();
167 21027 : while(last-- != first)
168 17291 : last->~value();
169 3736 : 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 3675 : array::
196 : ~array() noexcept
197 : {
198 3675 : destroy();
199 3675 : }
200 :
201 37 : array::
202 : array(
203 : std::size_t count,
204 : value const& v,
205 37 : storage_ptr sp)
206 37 : : sp_(std::move(sp))
207 : {
208 37 : if(count == 0)
209 : {
210 1 : t_ = &empty_;
211 1 : return;
212 : }
213 67 : t_= table::allocate(
214 36 : count, sp_);
215 31 : t_->size = 0;
216 31 : revert_construct r(*this);
217 106 : while(count--)
218 : {
219 107 : ::new(end()) value(v, sp_);
220 75 : ++t_->size;
221 : }
222 15 : r.commit();
223 52 : }
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 173 : array::
255 : array(
256 : array const& other,
257 173 : storage_ptr sp)
258 173 : : sp_(std::move(sp))
259 : {
260 173 : if(other.empty())
261 : {
262 14 : t_ = &empty_;
263 14 : return;
264 : }
265 159 : t_ = table::allocate(
266 159 : other.size(), sp_);
267 138 : t_->size = 0;
268 138 : revert_construct r(*this);
269 138 : auto src = other.data();
270 138 : auto dest = data();
271 138 : auto const n = other.size();
272 : do
273 : {
274 14 : ::new(dest++) value(
275 2468 : *src++, sp_);
276 2426 : ++t_->size;
277 : }
278 2426 : while(t_->size < n);
279 124 : r.commit();
280 173 : }
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 256 : array::
319 : array(
320 : std::initializer_list<
321 : value_ref> init,
322 256 : storage_ptr sp)
323 256 : : sp_(std::move(sp))
324 : {
325 256 : if(init.size() == 0)
326 : {
327 5 : t_ = &empty_;
328 5 : return;
329 : }
330 251 : t_ = table::allocate(
331 251 : init.size(), sp_);
332 222 : t_->size = 0;
333 222 : revert_construct r(*this);
334 222 : value_ref::write_array(
335 222 : data(), init, sp_);
336 206 : t_->size = static_cast<
337 206 : std::uint32_t>(init.size());
338 206 : r.commit();
339 267 : }
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 13 : array::
491 : insert(
492 : const_iterator pos,
493 : std::size_t count,
494 : value const& v) ->
495 : iterator
496 : {
497 : // v may refer to an element of this array, whose
498 : // storage revert_insert can relocate and free, so
499 : // copy it before inserting
500 14 : value const tmp(v, sp_);
501 : revert_insert r(
502 12 : pos, count, *this);
503 24 : while(count--)
504 : {
505 22 : ::new(r.p) value(tmp, sp_);
506 16 : ++r.p;
507 : }
508 10 : return r.commit();
509 15 : }
510 :
511 : auto
512 7 : array::
513 : insert(
514 : const_iterator pos,
515 : std::initializer_list<
516 : value_ref> init) ->
517 : iterator
518 : {
519 : // the initializer_list elements may reference elements of this
520 : // array, whose storage revert_insert can relocate and free, so
521 : // materialise them into a temporary before inserting
522 10 : array temp(init, sp_);
523 : revert_insert r(
524 4 : pos, temp.size(), *this);
525 2 : relocate(
526 : r.p,
527 : temp.data(),
528 : temp.size());
529 2 : temp.t_->size = 0;
530 4 : return r.commit();
531 4 : }
532 :
533 : auto
534 7 : array::
535 : erase(
536 : const_iterator pos) noexcept ->
537 : iterator
538 : {
539 7 : BOOST_ASSERT(
540 : pos >= begin() &&
541 : pos <= end());
542 7 : return erase(pos, pos + 1);
543 : }
544 :
545 : auto
546 8 : array::
547 : erase(
548 : const_iterator first,
549 : const_iterator last) noexcept ->
550 : iterator
551 : {
552 8 : BOOST_ASSERT(
553 : first >= begin() &&
554 : last >= first &&
555 : last <= end());
556 8 : std::size_t const n =
557 8 : last - first;
558 8 : auto const p = &(*t_)[0] +
559 8 : (first - &(*t_)[0]);
560 8 : destroy(p, p + n);
561 8 : relocate(p, p + n,
562 8 : t_->size - (last -
563 8 : &(*t_)[0]));
564 8 : t_->size = static_cast<
565 8 : std::uint32_t>(t_->size - n);
566 8 : return p;
567 : }
568 :
569 : void
570 4 : array::
571 : push_back(value const& v)
572 : {
573 4 : emplace_back(v);
574 2 : }
575 :
576 : void
577 9 : array::
578 : push_back(value&& v)
579 : {
580 9 : emplace_back(std::move(v));
581 7 : }
582 :
583 : void
584 3 : array::
585 : pop_back() noexcept
586 : {
587 3 : auto const p = &back();
588 3 : destroy(p, p + 1);
589 3 : --t_->size;
590 3 : }
591 :
592 : void
593 15 : array::
594 : resize(std::size_t count)
595 : {
596 15 : if(count <= t_->size)
597 : {
598 : // shrink
599 4 : destroy(
600 2 : &(*t_)[0] + count,
601 2 : &(*t_)[0] + t_->size);
602 2 : t_->size = static_cast<
603 : std::uint32_t>(count);
604 2 : return;
605 : }
606 :
607 13 : reserve(count);
608 12 : auto p = &(*t_)[t_->size];
609 12 : auto const end = &(*t_)[count];
610 32 : while(p != end)
611 20 : ::new(p++) value(sp_);
612 12 : t_->size = static_cast<
613 : std::uint32_t>(count);
614 : }
615 :
616 : void
617 11 : array::
618 : resize(
619 : std::size_t count,
620 : value const& v)
621 : {
622 11 : if(count <= size())
623 : {
624 : // shrink
625 2 : destroy(
626 1 : data() + count,
627 1 : data() + size());
628 1 : t_->size = static_cast<
629 : std::uint32_t>(count);
630 1 : return;
631 : }
632 10 : count -= size();
633 : // v may refer to an element of this array, whose
634 : // storage revert_insert can relocate and free, so
635 : // copy it before inserting
636 12 : value const tmp(v, sp_);
637 : revert_insert r(
638 8 : end(), count, *this);
639 18 : while(count--)
640 : {
641 20 : ::new(r.p) value(tmp, sp_);
642 12 : ++r.p;
643 : }
644 2 : r.commit();
645 12 : }
646 :
647 : void
648 28 : array::
649 : swap(array& other)
650 : {
651 28 : if(*sp_ == *other.sp_)
652 : {
653 48 : t_ = detail::exchange(
654 24 : other.t_, t_);
655 24 : return;
656 : }
657 : array temp1(
658 4 : std::move(*this),
659 9 : other.storage());
660 : array temp2(
661 3 : std::move(other),
662 7 : this->storage());
663 2 : this->~array();
664 6 : ::new(this) array(
665 2 : pilfer(temp2));
666 2 : other.~array();
667 6 : ::new(&other) array(
668 2 : pilfer(temp1));
669 3 : }
670 :
671 : //----------------------------------------------------------
672 : //
673 : // Private
674 : //
675 : //----------------------------------------------------------
676 :
677 : std::size_t
678 804 : array::
679 : growth(
680 : std::size_t new_size) const
681 : {
682 804 : if(new_size > max_size())
683 : {
684 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
685 1 : detail::throw_system_error( error::array_too_large, &loc );
686 : }
687 803 : std::size_t const old = capacity();
688 803 : if(old > max_size() - old / 2)
689 1 : return new_size;
690 802 : std::size_t const g =
691 802 : old + old / 2; // 1.5x
692 802 : if(g < new_size)
693 720 : return new_size;
694 82 : return g;
695 : }
696 :
697 : // precondition: new_capacity > capacity()
698 : void
699 685 : array::
700 : reserve_impl(
701 : std::size_t new_capacity)
702 : {
703 685 : BOOST_ASSERT(
704 : new_capacity > t_->capacity);
705 684 : auto t = table::allocate(
706 685 : growth(new_capacity), sp_);
707 661 : relocate(
708 661 : &(*t)[0],
709 661 : &(*t_)[0],
710 661 : t_->size);
711 661 : t->size = t_->size;
712 661 : t = detail::exchange(t_, t);
713 661 : table::deallocate(t, sp_);
714 661 : }
715 :
716 : // precondition: pv is not aliased
717 : value&
718 7635 : array::
719 : push_back(
720 : pilfered<value> pv)
721 : {
722 7635 : auto const n = t_->size;
723 7635 : if(n < t_->capacity)
724 : {
725 : // fast path
726 : auto& v = *::new(
727 7568 : &(*t_)[n]) value(pv);
728 7568 : ++t_->size;
729 7568 : return v;
730 : }
731 : auto const t =
732 67 : detail::exchange(t_,
733 : table::allocate(
734 67 : growth(n + 1),
735 67 : sp_));
736 : auto& v = *::new(
737 62 : &(*t_)[n]) value(pv);
738 62 : relocate(
739 62 : &(*t_)[0],
740 62 : &(*t)[0],
741 : n);
742 62 : t_->size = n + 1;
743 62 : table::deallocate(t, sp_);
744 62 : return v;
745 : }
746 :
747 : // precondition: pv is not aliased
748 : auto
749 12 : array::
750 : insert(
751 : const_iterator pos,
752 : pilfered<value> pv) ->
753 : iterator
754 : {
755 12 : BOOST_ASSERT(
756 : pos >= begin() &&
757 : pos <= end());
758 12 : std::size_t const n =
759 12 : t_->size;
760 : std::size_t const i =
761 12 : pos - &(*t_)[0];
762 12 : if(n < t_->capacity)
763 : {
764 : // fast path
765 : auto const p =
766 1 : &(*t_)[i];
767 1 : relocate(
768 : p + 1,
769 : p,
770 : n - i);
771 1 : ::new(p) value(pv);
772 1 : ++t_->size;
773 1 : return p;
774 : }
775 : auto t =
776 11 : table::allocate(
777 11 : growth(n + 1), sp_);
778 6 : auto const p = &(*t)[i];
779 6 : ::new(p) value(pv);
780 6 : relocate(
781 6 : &(*t)[0],
782 6 : &(*t_)[0],
783 : i);
784 6 : relocate(
785 : p + 1,
786 6 : &(*t_)[i],
787 : n - i);
788 6 : t->size = static_cast<
789 6 : std::uint32_t>(size() + 1);
790 6 : t = detail::exchange(t_, t);
791 6 : table::deallocate(t, sp_);
792 6 : return p;
793 : }
794 :
795 : //----------------------------------------------------------
796 :
797 : bool
798 79 : array::
799 : equal(
800 : array const& other) const noexcept
801 : {
802 79 : if(size() != other.size())
803 2 : return false;
804 3250 : for(std::size_t i = 0; i < size(); ++i)
805 3179 : if((*this)[i] != other[i])
806 6 : return false;
807 71 : return true;
808 : }
809 :
810 : } // namespace json
811 : } // namespace boost
812 :
813 : //----------------------------------------------------------
814 : //
815 : // std::hash specialization
816 : //
817 : //----------------------------------------------------------
818 :
819 : std::size_t
820 12 : std::hash<::boost::json::array>::operator()(
821 : ::boost::json::array const& ja) const noexcept
822 : {
823 12 : return ::boost::hash< ::boost::json::array >()( ja );
824 : }
825 :
826 : //----------------------------------------------------------
827 :
828 : #endif
|
