Index/impl / array.ipp

impl/array.ipp

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