impl/array.ipp

99.7% Lines (394/0/395) 100.0% List of functions (40/0/40)

[ ] prev/next file n p prev/next uncovered line

array.ipp

f(x) Functions (40)

Function Calls Lines Blocks

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