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