impl/array.ipp

100.0% Lines (392/392) 100.0% List of functions (40/40)

[ ] prev/next file

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