impl/array.ipp

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