impl/object.hpp

91.3% Lines (428/469) 97.2% List of functions (69/71)

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

f(x) Functions (71)

Function Calls Lines Branches 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_OBJECT_HPP
11		#define BOOST_JSON_IMPL_OBJECT_HPP
12
13		#include <boost/core/detail/static_assert.hpp>
14		#include <boost/json/value.hpp>
15		#include <iterator>
16		#include <cmath>
17		#include <type_traits>
18		#include <utility>
19
20		namespace boost {
21		namespace json {
22
23		namespace detail {
24
25		// Objects with size less than or equal
26		// to this number will use a linear search
27		// instead of the more expensive hash function.
28		static
29		constexpr
30		std::size_t
31		small_object_size_ = 18;
32
33		BOOST_CORE_STATIC_ASSERT(
34		small_object_size_ < BOOST_JSON_MAX_STRUCTURED_SIZE);
35
36		} // detail
37
38		//----------------------------------------------------------
39
40		struct alignas(key_value_pair)
41		object::table
42		{
43		std::uint32_t size = 0;
44		std::uint32_t capacity = 0;
45		std::uintptr_t salt = 0;
46
47		#if defined(_MSC_VER) && BOOST_JSON_ARCH == 32
48		// VFALCO If we make key_value_pair smaller,
49		// then we might want to revisit this
50		// padding.
51		BOOST_CORE_STATIC_ASSERT( sizeof(key_value_pair) == 32 );
52		char pad[4] = {}; // silence warnings
53		#endif
54
55		constexpr table();
56
57		// returns true if we use a linear
58		// search instead of the hash table.
59	122186x	bool is_small() const noexcept
60		{
61	122186x	return capacity <=
62	122186x	detail::small_object_size_;
63		}
64
65		key_value_pair&
66	293734x	operator[](
67		std::size_t pos) noexcept
68		{
69		return reinterpret_cast<
70		key_value_pair*>(
71	293734x	this + 1)[pos];
72		}
73
74		// VFALCO This is exported for tests
75		BOOST_JSON_DECL
76		std::size_t
77		digest(string_view key) const noexcept;
78
79		inline
80		index_t&
81		bucket(std::size_t hash) noexcept;
82
83		inline
84		index_t&
85		bucket(string_view key) noexcept;
86
87		inline
88		void
89		clear() noexcept;
90
91		static
92		inline
93		table*
94		allocate(
95		std::size_t capacity,
96		std::uintptr_t salt,
97		storage_ptr const& sp);
98
99		static
100		void
101	36352x	deallocate(
102		table* p,
103		storage_ptr const& sp) noexcept
104		{
105	36352x	if(p->capacity == 0)
106	983x	return;
107	35369x	if(! p->is_small())
108	388x	sp->deallocate(p,
109	388x	sizeof(table) + p->capacity * (
110		sizeof(key_value_pair) +
111		sizeof(index_t)));
112		else
113	34981x	sp->deallocate(p,
114	34981x	sizeof(table) + p->capacity *
115		sizeof(key_value_pair));
116		}
117		};
118
119		//----------------------------------------------------------
120
121		class object::revert_construct
122		{
123		object* obj_;
124
125		BOOST_JSON_DECL
126		void
127		destroy() noexcept;
128
129		public:
130		explicit
131	705x	revert_construct(
132		object& obj) noexcept
133	705x	: obj_(&obj)
134		{
135	705x	}
136
137	705x	~revert_construct()
138	374x	{
139	705x	if(! obj_)
140	331x	return;
141	374x	destroy();
142	705x	}
143
144		void
145	331x	commit() noexcept
146		{
147	331x	obj_ = nullptr;
148	331x	}
149		};
150
151		//----------------------------------------------------------
152
153		class object::revert_insert
154		{
155		object* obj_;
156		table* t_ = nullptr;
157		std::size_t size_;
158
159		BOOST_JSON_DECL
160		void
161		destroy() noexcept;
162
163		public:
164		explicit
165	503x	revert_insert(
166		object& obj,
167		std::size_t capacity)
168	503x	: obj_(&obj)
169	503x	, size_(obj_->size())
170		{
171	503x	if( capacity > obj_->capacity() )
172	138x	t_ = obj_->reserve_impl(capacity);
173	494x	}
174
175	494x	~revert_insert()
176	230x	{
177	494x	if(! obj_)
178	264x	return;
179
180	230x	destroy();
181	230x	if( t_ )
182		{
183	117x	table::deallocate( obj_->t_, obj_->sp_ );
184	117x	obj_->t_ = t_;
185		}
186		else
187		{
188	113x	obj_->t_->size = static_cast<index_t>(size_);
189		}
190	494x	}
191
192		void
193	264x	commit() noexcept
194		{
195	264x	BOOST_ASSERT(obj_);
196	264x	if( t_ )
197	12x	table::deallocate( t_, obj_->sp_ );
198	264x	obj_ = nullptr;
199	264x	}
200		};
201
202		//----------------------------------------------------------
203		//
204		// Iterators
205		//
206		//----------------------------------------------------------
207
208		auto
209	70788x	object::
210		begin() noexcept ->
211		iterator
212		{
213	70788x	return &(*t_)[0];
214		}
215
216		auto
217	53205x	object::
218		begin() const noexcept ->
219		const_iterator
220		{
221	53205x	return &(*t_)[0];
222		}
223
224		auto
225	3x	object::
226		cbegin() const noexcept ->
227		const_iterator
228		{
229	3x	return &(*t_)[0];
230		}
231
232		auto
233	46093x	object::
234		end() noexcept ->
235		iterator
236		{
237	46093x	return &(*t_)[t_->size];
238		}
239
240		auto
241	27786x	object::
242		end() const noexcept ->
243		const_iterator
244		{
245	27786x	return &(*t_)[t_->size];
246		}
247
248		auto
249	3x	object::
250		cend() const noexcept ->
251		const_iterator
252		{
253	3x	return &(*t_)[t_->size];
254		}
255
256		auto
257	2x	object::
258		rbegin() noexcept ->
259		reverse_iterator
260		{
261	2x	return reverse_iterator(end());
262		}
263
264		auto
265	2x	object::
266		rbegin() const noexcept ->
267		const_reverse_iterator
268		{
269	2x	return const_reverse_iterator(end());
270		}
271
272		auto
273	2x	object::
274		crbegin() const noexcept ->
275		const_reverse_iterator
276		{
277	2x	return const_reverse_iterator(end());
278		}
279
280		auto
281	2x	object::
282		rend() noexcept ->
283		reverse_iterator
284		{
285	2x	return reverse_iterator(begin());
286		}
287
288		auto
289	2x	object::
290		rend() const noexcept ->
291		const_reverse_iterator
292		{
293	2x	return const_reverse_iterator(begin());
294		}
295
296		auto
297	2x	object::
298		crend() const noexcept ->
299		const_reverse_iterator
300		{
301	2x	return const_reverse_iterator(begin());
302		}
303
304		//----------------------------------------------------------
305		//
306		// Capacity
307		//
308		//----------------------------------------------------------
309
310		bool
311	10473x	object::
312		empty() const noexcept
313		{
314	10473x	return t_->size == 0;
315		}
316
317		auto
318	44249x	object::
319		size() const noexcept ->
320		std::size_t
321		{
322	44249x	return t_->size;
323		}
324
325		constexpr
326		std::size_t
327	73125x	object::
328		max_size() noexcept
329		{
330		// max_size depends on the address model
331		using min = std::integral_constant<std::size_t,
332		(std::size_t(-1) - sizeof(table)) /
333		(sizeof(key_value_pair) + sizeof(index_t))>;
334		return min::value < BOOST_JSON_MAX_STRUCTURED_SIZE ?
335	73125x	min::value : BOOST_JSON_MAX_STRUCTURED_SIZE;
336		}
337
338		auto
339	18848x	object::
340		capacity() const noexcept ->
341		std::size_t
342		{
343	18848x	return t_->capacity;
344		}
345
346		void
347	4742x	object::
348		reserve(std::size_t new_capacity)
349		{
350	4742x	if( new_capacity <= capacity() )
351	3224x	return;
352	1518x	table* const old_table = reserve_impl(new_capacity);
353	1453x	table::deallocate( old_table, sp_ );
354		}
355
356		//----------------------------------------------------------
357		//
358		// Lookup
359		//
360		//----------------------------------------------------------
361
362		value&
363	42x	object::
364		at(string_view key, source_location const& loc) &
365		{
366	42x	auto const& self = *this;
367	42x	return const_cast< value& >( self.at(key, loc) );
368		}
369
370		value&&
371	5x	object::
372		at(string_view key, source_location const& loc) &&
373		{
374	5x	return std::move( at(key, loc) );
375		}
376
377		//----------------------------------------------------------
378
379		template<class P, class>
380		auto
381	3127x	object::
382		insert(P&& p) ->
383		std::pair<iterator, bool>
384		{
385	3422x	key_value_pair v(
386	3127x	std::forward<P>(p), sp_);
387	5791x	return emplace_impl( v.key(), pilfer(v) );
388	2979x	}
389
390		template<class M>
391		auto
392	17x	object::
393		insert_or_assign(
394		string_view key, M&& m) ->
395		std::pair<iterator, bool>
396		{
397	17x	std::pair<iterator, bool> result = emplace_impl(
398		key, key, static_cast<M&&>(m) );
399	10x	if( !result.second )
400		{
401	8x	value(static_cast<M>(m), sp_).swap(
402	3x	result.first->value());
403		}
404	9x	return result;
405		}
406
407		template<class Arg>
408		auto
409	995x	object::
410		emplace(
411		string_view key,
412		Arg&& arg) ->
413		std::pair<iterator, bool>
414		{
415	995x	return emplace_impl( key, key, static_cast<Arg&&>(arg) );
416		}
417
418		//----------------------------------------------------------
419		//
420		// (private)
421		//
422		//----------------------------------------------------------
423
424		template<class InputIt>
425		void
426	78x	object::
427		construct(
428		InputIt first,
429		InputIt last,
430		std::size_t min_capacity,
431		std::input_iterator_tag)
432		{
433	78x	reserve(min_capacity);
434	76x	revert_construct r(*this);
435	753x	while(first != last)
436		{
437	750x	insert(*first);
438	677x	++first;
439		}
440	3x	r.commit();
441	76x	}
442
443		template<class InputIt>
444		void
445	82x	object::
446		construct(
447		InputIt first,
448		InputIt last,
449		std::size_t min_capacity,
450		std::forward_iterator_tag)
451		{
452	82x	auto n = static_cast<
453	82x	std::size_t>(std::distance(
454		first, last));
455	82x	if( n < min_capacity)
456	76x	n = min_capacity;
457	82x	reserve(n);
458	79x	revert_construct r(*this);
459	771x	while(first != last)
460		{
461	764x	insert(*first);
462	692x	++first;
463		}
464	7x	r.commit();
465	79x	}
466
467		template<class InputIt>
468		void
469	94x	object::
470		insert(
471		InputIt first,
472		InputIt last,
473		std::input_iterator_tag)
474		{
475		// Since input iterators cannot be rewound,
476		// we keep inserted elements on an exception.
477		//
478	871x	while(first != last)
479		{
480	867x	insert(*first);
481	777x	++first;
482		}
483	4x	}
484
485		template<class InputIt>
486		void
487	80x	object::
488		insert(
489		InputIt first,
490		InputIt last,
491		std::forward_iterator_tag)
492		{
493	80x	auto const n =
494		static_cast<std::size_t>(
495	80x	std::distance(first, last));
496	80x	auto const n0 = size();
497	80x	if(n > max_size() - n0)
498		{
499		BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
500	1x	detail::throw_system_error( error::object_too_large, &loc );
501		}
502	79x	revert_insert r( *this, n0 + n );
503	738x	while(first != last)
504		{
505	734x	insert(*first);
506	661x	++first;
507		}
508	4x	r.commit();
509	77x	}
510
511		template< class... Args >
512		std::pair<object::iterator, bool>
513	3991x	object::
514		emplace_impl( string_view key, Args&& ... args )
515		{
516	3991x	std::pair<iterator, std::size_t> search_result(nullptr, 0);
517	3991x	if( !empty() )
518		{
519	3462x	search_result = detail::find_in_object(*this, key);
520	3462x	if( search_result.first )
521	30x	return { search_result.first, false };
522		}
523
524		// we create the new value before reserving, in case it is a reference to
525		// a subobject of the current object
526	4253x	key_value_pair kv( static_cast<Args&&>(args)..., sp_ );
527		// the key might get deallocated too
528	3808x	key = kv.key();
529
530	3808x	std::size_t const old_capacity = capacity();
531	3808x	reserve(size() + 1);
532	4294x	if( (empty() && capacity() > detail::small_object_size_)
533	4294x	\|\| (capacity() != old_capacity) )
534	724x	search_result.second = detail::digest(
535	724x	key.begin(), key.end(), t_->salt);
536
537	3781x	BOOST_ASSERT(
538		t_->is_small() \|\|
539		(search_result.second ==
540		detail::digest(key.begin(), key.end(), t_->salt)) );
541
542	3781x	return { insert_impl(pilfer(kv), search_result.second), true };
543	3808x	}
544
545		//----------------------------------------------------------
546
547		namespace detail {
548
549	34879x	unchecked_object::
550	1086x	~unchecked_object()
551		{
552	34879x	if(! data_)
553	33791x	return;
554	1088x	if(sp_.is_not_shared_and_deallocate_is_trivial())
555	2x	return;
556	1086x	value* p = data_;
557	1146x	while(size_--)
558		{
559	60x	p[0].~value();
560	60x	p[1].~value();
561	60x	p += 2;
562		}
563	34879x	}
564
565		} // detail
566
567		} // namespace json
568		} // namespace boost
569
570		#endif
571