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 2587 : array::
36 : table::
37 : allocate(
38 : std::size_t capacity,
39 : storage_ptr const& sp) ->
40 : table*
41 : {
42 2587 : BOOST_ASSERT(capacity > 0);
43 2587 : 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 2585 : table*>(sp->allocate(
50 : sizeof(table) +
51 2585 : capacity * sizeof(value),
52 : alignof(value)));
53 2440 : p->capacity = static_cast<
54 : std::uint32_t>(capacity);
55 2440 : return p;
56 : }
57 :
58 : void
59 4478 : array::
60 : table::
61 : deallocate(
62 : table* p,
63 : storage_ptr const& sp)
64 : {
65 4478 : if(p->capacity == 0)
66 2042 : return;
67 2436 : sp->deallocate(p,
68 : sizeof(table) +
69 2436 : p->capacity * sizeof(value),
70 : alignof(value));
71 : }
72 :
73 : //----------------------------------------------------------
74 :
75 41 : array::
76 : revert_insert::
77 : revert_insert(
78 : const_iterator pos,
79 : std::size_t n,
80 41 : array& arr)
81 41 : : arr_(&arr)
82 41 : , i_(pos - arr_->data())
83 41 : , n_(n)
84 : {
85 41 : BOOST_ASSERT(
86 : pos >= arr_->begin() &&
87 : pos <= arr_->end());
88 82 : if( n_ <= arr_->capacity() -
89 41 : 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 39 : 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 38 : auto t = table::allocate(
110 38 : arr_->growth(arr_->size() + n_),
111 38 : arr_->sp_);
112 26 : t->size = static_cast<std::uint32_t>(
113 26 : arr_->size() + n_);
114 26 : p = &(*t)[0] + i_;
115 26 : relocate(
116 26 : &(*t)[0],
117 26 : arr_->data(),
118 26 : i_);
119 26 : relocate(
120 26 : &(*t)[i_ + n_],
121 26 : arr_->data() + i_,
122 26 : arr_->size() - i_);
123 26 : t = detail::exchange(arr_->t_, t);
124 26 : table::deallocate(t, arr_->sp_);
125 : }
126 :
127 28 : array::
128 : revert_insert::
129 8 : ~revert_insert()
130 : {
131 28 : if(! arr_)
132 20 : 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 28 : }
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 3728 : array::
161 : destroy() noexcept
162 : {
163 3728 : if(sp_.is_not_shared_and_deallocate_is_trivial())
164 5 : return;
165 3723 : auto last = end();
166 3723 : auto const first = begin();
167 20993 : while(last-- != first)
168 17270 : last->~value();
169 3723 : 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 3663 : array::
196 : ~array() noexcept
197 : {
198 3663 : destroy();
199 3663 : }
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 248 : array::
319 : array(
320 : std::initializer_list<
321 : value_ref> init,
322 248 : storage_ptr sp)
323 248 : : sp_(std::move(sp))
324 : {
325 248 : if(init.size() == 0)
326 : {
327 5 : t_ = &empty_;
328 5 : return;
329 : }
330 243 : t_ = table::allocate(
331 243 : init.size(), sp_);
332 216 : t_->size = 0;
333 216 : revert_construct r(*this);
334 216 : value_ref::write_array(
335 216 : data(), init, sp_);
336 201 : t_->size = static_cast<
337 201 : std::uint32_t>(init.size());
338 201 : r.commit();
339 258 : }
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 3 : array::
513 : insert(
514 : const_iterator pos,
515 : std::initializer_list<
516 : value_ref> init) ->
517 : iterator
518 : {
519 : revert_insert r(
520 3 : pos, init.size(), *this);
521 2 : value_ref::write_array(
522 2 : r.p, init, sp_);
523 2 : return r.commit();
524 2 : }
525 :
526 : auto
527 7 : array::
528 : erase(
529 : const_iterator pos) noexcept ->
530 : iterator
531 : {
532 7 : BOOST_ASSERT(
533 : pos >= begin() &&
534 : pos <= end());
535 7 : return erase(pos, pos + 1);
536 : }
537 :
538 : auto
539 8 : array::
540 : erase(
541 : const_iterator first,
542 : const_iterator last) noexcept ->
543 : iterator
544 : {
545 8 : BOOST_ASSERT(
546 : first >= begin() &&
547 : last >= first &&
548 : last <= end());
549 8 : std::size_t const n =
550 8 : last - first;
551 8 : auto const p = &(*t_)[0] +
552 8 : (first - &(*t_)[0]);
553 8 : destroy(p, p + n);
554 8 : relocate(p, p + n,
555 8 : t_->size - (last -
556 8 : &(*t_)[0]));
557 8 : t_->size = static_cast<
558 8 : std::uint32_t>(t_->size - n);
559 8 : return p;
560 : }
561 :
562 : void
563 4 : array::
564 : push_back(value const& v)
565 : {
566 4 : emplace_back(v);
567 2 : }
568 :
569 : void
570 9 : array::
571 : push_back(value&& v)
572 : {
573 9 : emplace_back(std::move(v));
574 7 : }
575 :
576 : void
577 3 : array::
578 : pop_back() noexcept
579 : {
580 3 : auto const p = &back();
581 3 : destroy(p, p + 1);
582 3 : --t_->size;
583 3 : }
584 :
585 : void
586 15 : array::
587 : resize(std::size_t count)
588 : {
589 15 : if(count <= t_->size)
590 : {
591 : // shrink
592 4 : destroy(
593 2 : &(*t_)[0] + count,
594 2 : &(*t_)[0] + t_->size);
595 2 : t_->size = static_cast<
596 : std::uint32_t>(count);
597 2 : return;
598 : }
599 :
600 13 : reserve(count);
601 12 : auto p = &(*t_)[t_->size];
602 12 : auto const end = &(*t_)[count];
603 32 : while(p != end)
604 20 : ::new(p++) value(sp_);
605 12 : t_->size = static_cast<
606 : std::uint32_t>(count);
607 : }
608 :
609 : void
610 11 : array::
611 : resize(
612 : std::size_t count,
613 : value const& v)
614 : {
615 11 : if(count <= size())
616 : {
617 : // shrink
618 2 : destroy(
619 1 : data() + count,
620 1 : data() + size());
621 1 : t_->size = static_cast<
622 : std::uint32_t>(count);
623 1 : return;
624 : }
625 10 : count -= size();
626 : // v may refer to an element of this array, whose
627 : // storage revert_insert can relocate and free, so
628 : // copy it before inserting
629 12 : value const tmp(v, sp_);
630 : revert_insert r(
631 8 : end(), count, *this);
632 18 : while(count--)
633 : {
634 20 : ::new(r.p) value(tmp, sp_);
635 12 : ++r.p;
636 : }
637 2 : r.commit();
638 12 : }
639 :
640 : void
641 28 : array::
642 : swap(array& other)
643 : {
644 28 : if(*sp_ == *other.sp_)
645 : {
646 48 : t_ = detail::exchange(
647 24 : other.t_, t_);
648 24 : return;
649 : }
650 : array temp1(
651 4 : std::move(*this),
652 9 : other.storage());
653 : array temp2(
654 3 : std::move(other),
655 7 : this->storage());
656 2 : this->~array();
657 6 : ::new(this) array(
658 2 : pilfer(temp2));
659 2 : other.~array();
660 6 : ::new(&other) array(
661 2 : pilfer(temp1));
662 3 : }
663 :
664 : //----------------------------------------------------------
665 : //
666 : // Private
667 : //
668 : //----------------------------------------------------------
669 :
670 : std::size_t
671 797 : array::
672 : growth(
673 : std::size_t new_size) const
674 : {
675 797 : if(new_size > max_size())
676 : {
677 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
678 1 : detail::throw_system_error( error::array_too_large, &loc );
679 : }
680 796 : std::size_t const old = capacity();
681 796 : if(old > max_size() - old / 2)
682 1 : return new_size;
683 795 : std::size_t const g =
684 795 : old + old / 2; // 1.5x
685 795 : if(g < new_size)
686 715 : return new_size;
687 80 : return g;
688 : }
689 :
690 : // precondition: new_capacity > capacity()
691 : void
692 681 : array::
693 : reserve_impl(
694 : std::size_t new_capacity)
695 : {
696 681 : BOOST_ASSERT(
697 : new_capacity > t_->capacity);
698 680 : auto t = table::allocate(
699 681 : growth(new_capacity), sp_);
700 658 : relocate(
701 658 : &(*t)[0],
702 658 : &(*t_)[0],
703 658 : t_->size);
704 658 : t->size = t_->size;
705 658 : t = detail::exchange(t_, t);
706 658 : table::deallocate(t, sp_);
707 658 : }
708 :
709 : // precondition: pv is not aliased
710 : value&
711 7623 : array::
712 : push_back(
713 : pilfered<value> pv)
714 : {
715 7623 : auto const n = t_->size;
716 7623 : if(n < t_->capacity)
717 : {
718 : // fast path
719 : auto& v = *::new(
720 7556 : &(*t_)[n]) value(pv);
721 7556 : ++t_->size;
722 7556 : return v;
723 : }
724 : auto const t =
725 67 : detail::exchange(t_,
726 : table::allocate(
727 67 : growth(n + 1),
728 67 : sp_));
729 : auto& v = *::new(
730 62 : &(*t_)[n]) value(pv);
731 62 : relocate(
732 62 : &(*t_)[0],
733 62 : &(*t)[0],
734 : n);
735 62 : t_->size = n + 1;
736 62 : table::deallocate(t, sp_);
737 62 : return v;
738 : }
739 :
740 : // precondition: pv is not aliased
741 : auto
742 12 : array::
743 : insert(
744 : const_iterator pos,
745 : pilfered<value> pv) ->
746 : iterator
747 : {
748 12 : BOOST_ASSERT(
749 : pos >= begin() &&
750 : pos <= end());
751 12 : std::size_t const n =
752 12 : t_->size;
753 : std::size_t const i =
754 12 : pos - &(*t_)[0];
755 12 : if(n < t_->capacity)
756 : {
757 : // fast path
758 : auto const p =
759 1 : &(*t_)[i];
760 1 : relocate(
761 : p + 1,
762 : p,
763 : n - i);
764 1 : ::new(p) value(pv);
765 1 : ++t_->size;
766 1 : return p;
767 : }
768 : auto t =
769 11 : table::allocate(
770 11 : growth(n + 1), sp_);
771 6 : auto const p = &(*t)[i];
772 6 : ::new(p) value(pv);
773 6 : relocate(
774 6 : &(*t)[0],
775 6 : &(*t_)[0],
776 : i);
777 6 : relocate(
778 : p + 1,
779 6 : &(*t_)[i],
780 : n - i);
781 6 : t->size = static_cast<
782 6 : std::uint32_t>(size() + 1);
783 6 : t = detail::exchange(t_, t);
784 6 : table::deallocate(t, sp_);
785 6 : return p;
786 : }
787 :
788 : //----------------------------------------------------------
789 :
790 : bool
791 79 : array::
792 : equal(
793 : array const& other) const noexcept
794 : {
795 79 : if(size() != other.size())
796 2 : return false;
797 3250 : for(std::size_t i = 0; i < size(); ++i)
798 3179 : if((*this)[i] != other[i])
799 6 : return false;
800 71 : return true;
801 : }
802 :
803 : } // namespace json
804 : } // namespace boost
805 :
806 : //----------------------------------------------------------
807 : //
808 : // std::hash specialization
809 : //
810 : //----------------------------------------------------------
811 :
812 : std::size_t
813 12 : std::hash<::boost::json::array>::operator()(
814 : ::boost::json::array const& ja) const noexcept
815 : {
816 12 : return ::boost::hash< ::boost::json::array >()( ja );
817 : }
818 :
819 : //----------------------------------------------------------
820 :
821 : #endif
|
