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/container_hash/hash.hpp>
14 : #include <boost/json/array.hpp>
15 : #include <boost/json/pilfer.hpp>
16 : #include <boost/json/detail/except.hpp>
17 : #include <cstdlib>
18 : #include <limits>
19 : #include <new>
20 : #include <utility>
21 :
22 : namespace boost {
23 : namespace json {
24 :
25 : //----------------------------------------------------------
26 :
27 : constexpr array::table::table() = default;
28 :
29 : // empty arrays point here
30 : BOOST_JSON_REQUIRE_CONST_INIT
31 : array::table array::empty_;
32 :
33 : auto
34 HIT 2578 : array::
35 : table::
36 : allocate(
37 : std::size_t capacity,
38 : storage_ptr const& sp) ->
39 : table*
40 : {
41 2578 : BOOST_ASSERT(capacity > 0);
42 2578 : if(capacity > array::max_size())
43 : {
44 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
45 2 : detail::throw_system_error( error::array_too_large, &loc );
46 : }
47 : auto p = reinterpret_cast<
48 2576 : table*>(sp->allocate(
49 : sizeof(table) +
50 2576 : capacity * sizeof(value),
51 : alignof(value)));
52 2437 : p->capacity = static_cast<
53 : std::uint32_t>(capacity);
54 2437 : return p;
55 : }
56 :
57 : void
58 4503 : array::
59 : table::
60 : deallocate(
61 : table* p,
62 : storage_ptr const& sp)
63 : {
64 4503 : if(p->capacity == 0)
65 2070 : return;
66 2433 : sp->deallocate(p,
67 : sizeof(table) +
68 2433 : p->capacity * sizeof(value),
69 : alignof(value));
70 : }
71 :
72 : //----------------------------------------------------------
73 :
74 37 : array::
75 : revert_insert::
76 : revert_insert(
77 : const_iterator pos,
78 : std::size_t n,
79 37 : array& arr)
80 37 : : arr_(&arr)
81 37 : , i_(pos - arr_->data())
82 37 : , n_(n)
83 : {
84 37 : BOOST_ASSERT(
85 : pos >= arr_->begin() &&
86 : pos <= arr_->end());
87 74 : if( n_ <= arr_->capacity() -
88 37 : arr_->size())
89 : {
90 : // fast path
91 2 : p = arr_->data() + i_;
92 2 : if(n_ == 0)
93 1 : return;
94 1 : relocate(
95 1 : p + n_,
96 : p,
97 1 : arr_->size() - i_);
98 1 : arr_->t_->size = static_cast<
99 : std::uint32_t>(
100 1 : arr_->t_->size + n_);
101 1 : return;
102 : }
103 35 : if(n_ > max_size() - arr_->size())
104 : {
105 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
106 1 : detail::throw_system_error( error::array_too_large, &loc );
107 : }
108 34 : auto t = table::allocate(
109 34 : arr_->growth(arr_->size() + n_),
110 34 : arr_->sp_);
111 24 : t->size = static_cast<std::uint32_t>(
112 24 : arr_->size() + n_);
113 24 : p = &(*t)[0] + i_;
114 24 : relocate(
115 24 : &(*t)[0],
116 24 : arr_->data(),
117 24 : i_);
118 24 : relocate(
119 24 : &(*t)[i_ + n_],
120 24 : arr_->data() + i_,
121 24 : arr_->size() - i_);
122 24 : t = detail::exchange(arr_->t_, t);
123 24 : table::deallocate(t, arr_->sp_);
124 : }
125 :
126 26 : array::
127 : revert_insert::
128 8 : ~revert_insert()
129 : {
130 26 : if(! arr_)
131 18 : return;
132 8 : BOOST_ASSERT(n_ != 0);
133 : auto const pos =
134 8 : arr_->data() + i_;
135 8 : arr_->destroy(pos, p);
136 8 : arr_->t_->size = static_cast<
137 : std::uint32_t>(
138 8 : arr_->t_->size - n_);
139 8 : relocate(
140 : pos,
141 8 : pos + n_,
142 8 : arr_->size() - i_);
143 26 : }
144 :
145 : //----------------------------------------------------------
146 :
147 : void
148 25 : array::
149 : destroy(
150 : value* first, value* last) noexcept
151 : {
152 25 : if(sp_.is_not_shared_and_deallocate_is_trivial())
153 1 : return;
154 50 : while(last-- != first)
155 26 : last->~value();
156 : }
157 :
158 : void
159 3732 : array::
160 : destroy() noexcept
161 : {
162 3732 : if(sp_.is_not_shared_and_deallocate_is_trivial())
163 5 : return;
164 3727 : auto last = end();
165 3727 : auto const first = begin();
166 20974 : while(last-- != first)
167 17247 : last->~value();
168 3727 : table::deallocate(t_, sp_);
169 : }
170 :
171 : //----------------------------------------------------------
172 : //
173 : // Special Members
174 : //
175 : //----------------------------------------------------------
176 :
177 2120 : array::
178 2120 : array(detail::unchecked_array&& ua)
179 2120 : : sp_(ua.storage())
180 : {
181 : BOOST_STATIC_ASSERT(
182 : 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 3668 : array::
196 : ~array() noexcept
197 : {
198 3668 : destroy();
199 3668 : }
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 274 : array::
283 : array(
284 : array&& other,
285 274 : storage_ptr sp)
286 274 : : sp_(std::move(sp))
287 : {
288 274 : if(*sp_ == *other.sp_)
289 : {
290 : // same resource
291 502 : t_ = detail::exchange(
292 251 : other.t_, &empty_);
293 255 : 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 244 : array::
319 : array(
320 : std::initializer_list<
321 : value_ref> init,
322 244 : storage_ptr sp)
323 244 : : sp_(std::move(sp))
324 : {
325 244 : if(init.size() == 0)
326 : {
327 5 : t_ = &empty_;
328 5 : return;
329 : }
330 239 : t_ = table::allocate(
331 239 : init.size(), sp_);
332 212 : t_->size = 0;
333 212 : revert_construct r(*this);
334 212 : value_ref::write_array(
335 212 : data(), init, sp_);
336 197 : t_->size = static_cast<
337 197 : std::uint32_t>(init.size());
338 197 : r.commit();
339 254 : }
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 814 : array::
664 : growth(
665 : std::size_t new_size) const
666 : {
667 814 : 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 813 : std::size_t const old = capacity();
673 813 : if(old > max_size() - old / 2)
674 1 : return new_size;
675 812 : std::size_t const g =
676 812 : old + old / 2; // 1.5x
677 812 : if(g < new_size)
678 732 : return new_size;
679 80 : return g;
680 : }
681 :
682 : // precondition: new_capacity > capacity()
683 : void
684 702 : array::
685 : reserve_impl(
686 : std::size_t new_capacity)
687 : {
688 702 : BOOST_ASSERT(
689 : new_capacity > t_->capacity);
690 701 : auto t = table::allocate(
691 702 : growth(new_capacity), sp_);
692 681 : relocate(
693 681 : &(*t)[0],
694 681 : &(*t_)[0],
695 681 : t_->size);
696 681 : t->size = t_->size;
697 681 : t = detail::exchange(t_, t);
698 681 : table::deallocate(t, sp_);
699 681 : }
700 :
701 : // precondition: pv is not aliased
702 : value&
703 7686 : array::
704 : push_back(
705 : pilfered<value> pv)
706 : {
707 7686 : auto const n = t_->size;
708 7686 : if(n < t_->capacity)
709 : {
710 : // fast path
711 : auto& v = *::new(
712 7619 : &(*t_)[n]) value(pv);
713 7619 : ++t_->size;
714 7619 : 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 88 : array::
784 : equal(
785 : array const& other) const noexcept
786 : {
787 88 : if(size() != other.size())
788 2 : return false;
789 3284 : for(std::size_t i = 0; i < size(); ++i)
790 3204 : if((*this)[i] != other[i])
791 6 : return false;
792 80 : 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
|
