TLA Line data 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 HIT 122186 : bool is_small() const noexcept
60 : {
61 122186 : return capacity <=
62 122186 : detail::small_object_size_;
63 : }
64 :
65 : key_value_pair&
66 295661 : operator[](
67 : std::size_t pos) noexcept
68 : {
69 : return reinterpret_cast<
70 : key_value_pair*>(
71 295661 : 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 36352 : deallocate(
102 : table* p,
103 : storage_ptr const& sp) noexcept
104 : {
105 36352 : if(p->capacity == 0)
106 983 : return;
107 35369 : if(! p->is_small())
108 388 : sp->deallocate(p,
109 388 : sizeof(table) + p->capacity * (
110 : sizeof(key_value_pair) +
111 : sizeof(index_t)));
112 : else
113 34981 : sp->deallocate(p,
114 34981 : 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 705 : revert_construct(
132 : object& obj) noexcept
133 705 : : obj_(&obj)
134 : {
135 705 : }
136 :
137 705 : ~revert_construct()
138 374 : {
139 705 : if(! obj_)
140 331 : return;
141 374 : destroy();
142 705 : }
143 :
144 : void
145 331 : commit() noexcept
146 : {
147 331 : obj_ = nullptr;
148 331 : }
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 503 : revert_insert(
166 : object& obj,
167 : std::size_t capacity)
168 503 : : obj_(&obj)
169 503 : , size_(obj_->size())
170 : {
171 503 : if( capacity > obj_->capacity() )
172 138 : t_ = obj_->reserve_impl(capacity);
173 494 : }
174 :
175 494 : ~revert_insert()
176 230 : {
177 494 : if(! obj_)
178 264 : return;
179 :
180 230 : destroy();
181 230 : if( t_ )
182 : {
183 117 : table::deallocate( obj_->t_, obj_->sp_ );
184 117 : obj_->t_ = t_;
185 : }
186 : else
187 : {
188 113 : obj_->t_->size = static_cast<index_t>(size_);
189 : }
190 494 : }
191 :
192 : void
193 264 : commit() noexcept
194 : {
195 264 : BOOST_ASSERT(obj_);
196 264 : if( t_ )
197 12 : table::deallocate( t_, obj_->sp_ );
198 264 : obj_ = nullptr;
199 264 : }
200 : };
201 :
202 : //----------------------------------------------------------
203 : //
204 : // Iterators
205 : //
206 : //----------------------------------------------------------
207 :
208 : auto
209 70788 : object::
210 : begin() noexcept ->
211 : iterator
212 : {
213 70788 : return &(*t_)[0];
214 : }
215 :
216 : auto
217 53205 : object::
218 : begin() const noexcept ->
219 : const_iterator
220 : {
221 53205 : return &(*t_)[0];
222 : }
223 :
224 : auto
225 3 : object::
226 : cbegin() const noexcept ->
227 : const_iterator
228 : {
229 3 : return &(*t_)[0];
230 : }
231 :
232 : auto
233 46093 : object::
234 : end() noexcept ->
235 : iterator
236 : {
237 46093 : return &(*t_)[t_->size];
238 : }
239 :
240 : auto
241 27786 : object::
242 : end() const noexcept ->
243 : const_iterator
244 : {
245 27786 : return &(*t_)[t_->size];
246 : }
247 :
248 : auto
249 3 : object::
250 : cend() const noexcept ->
251 : const_iterator
252 : {
253 3 : return &(*t_)[t_->size];
254 : }
255 :
256 : auto
257 2 : object::
258 : rbegin() noexcept ->
259 : reverse_iterator
260 : {
261 2 : return reverse_iterator(end());
262 : }
263 :
264 : auto
265 2 : object::
266 : rbegin() const noexcept ->
267 : const_reverse_iterator
268 : {
269 2 : return const_reverse_iterator(end());
270 : }
271 :
272 : auto
273 2 : object::
274 : crbegin() const noexcept ->
275 : const_reverse_iterator
276 : {
277 2 : return const_reverse_iterator(end());
278 : }
279 :
280 : auto
281 2 : object::
282 : rend() noexcept ->
283 : reverse_iterator
284 : {
285 2 : return reverse_iterator(begin());
286 : }
287 :
288 : auto
289 2 : object::
290 : rend() const noexcept ->
291 : const_reverse_iterator
292 : {
293 2 : return const_reverse_iterator(begin());
294 : }
295 :
296 : auto
297 2 : object::
298 : crend() const noexcept ->
299 : const_reverse_iterator
300 : {
301 2 : return const_reverse_iterator(begin());
302 : }
303 :
304 : //----------------------------------------------------------
305 : //
306 : // Capacity
307 : //
308 : //----------------------------------------------------------
309 :
310 : bool
311 10473 : object::
312 : empty() const noexcept
313 : {
314 10473 : return t_->size == 0;
315 : }
316 :
317 : auto
318 44249 : object::
319 : size() const noexcept ->
320 : std::size_t
321 : {
322 44249 : return t_->size;
323 : }
324 :
325 : constexpr
326 : std::size_t
327 73125 : 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 73125 : min::value : BOOST_JSON_MAX_STRUCTURED_SIZE;
336 : }
337 :
338 : auto
339 18848 : object::
340 : capacity() const noexcept ->
341 : std::size_t
342 : {
343 18848 : return t_->capacity;
344 : }
345 :
346 : void
347 4742 : object::
348 : reserve(std::size_t new_capacity)
349 : {
350 4742 : if( new_capacity <= capacity() )
351 3224 : return;
352 1518 : table* const old_table = reserve_impl(new_capacity);
353 1453 : table::deallocate( old_table, sp_ );
354 : }
355 :
356 : //----------------------------------------------------------
357 : //
358 : // Lookup
359 : //
360 : //----------------------------------------------------------
361 :
362 : value&
363 42 : object::
364 : at(string_view key, source_location const& loc) &
365 : {
366 42 : auto const& self = *this;
367 42 : return const_cast< value& >( self.at(key, loc) );
368 : }
369 :
370 : value&&
371 5 : object::
372 : at(string_view key, source_location const& loc) &&
373 : {
374 5 : return std::move( at(key, loc) );
375 : }
376 :
377 : //----------------------------------------------------------
378 :
379 : template<class P, class>
380 : auto
381 3127 : object::
382 : insert(P&& p) ->
383 : std::pair<iterator, bool>
384 : {
385 3422 : key_value_pair v(
386 3127 : std::forward<P>(p), sp_);
387 5791 : return emplace_impl( v.key(), pilfer(v) );
388 2979 : }
389 :
390 : template<class M>
391 : auto
392 17 : object::
393 : insert_or_assign(
394 : string_view key, M&& m) ->
395 : std::pair<iterator, bool>
396 : {
397 17 : std::pair<iterator, bool> result = emplace_impl(
398 : key, key, static_cast<M&&>(m) );
399 10 : if( !result.second )
400 : {
401 8 : value(static_cast<M>(m), sp_).swap(
402 3 : result.first->value());
403 : }
404 9 : return result;
405 : }
406 :
407 : template<class Arg>
408 : auto
409 995 : object::
410 : emplace(
411 : string_view key,
412 : Arg&& arg) ->
413 : std::pair<iterator, bool>
414 : {
415 995 : 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 78 : object::
427 : construct(
428 : InputIt first,
429 : InputIt last,
430 : std::size_t min_capacity,
431 : std::input_iterator_tag)
432 : {
433 78 : reserve(min_capacity);
434 76 : revert_construct r(*this);
435 753 : while(first != last)
436 : {
437 750 : insert(*first);
438 677 : ++first;
439 : }
440 3 : r.commit();
441 76 : }
442 :
443 : template<class InputIt>
444 : void
445 82 : object::
446 : construct(
447 : InputIt first,
448 : InputIt last,
449 : std::size_t min_capacity,
450 : std::forward_iterator_tag)
451 : {
452 82 : auto n = static_cast<
453 82 : std::size_t>(std::distance(
454 : first, last));
455 82 : if( n < min_capacity)
456 76 : n = min_capacity;
457 82 : reserve(n);
458 79 : revert_construct r(*this);
459 771 : while(first != last)
460 : {
461 764 : insert(*first);
462 692 : ++first;
463 : }
464 7 : r.commit();
465 79 : }
466 :
467 : template<class InputIt>
468 : void
469 94 : 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 871 : while(first != last)
479 : {
480 867 : insert(*first);
481 777 : ++first;
482 : }
483 4 : }
484 :
485 : template<class InputIt>
486 : void
487 80 : object::
488 : insert(
489 : InputIt first,
490 : InputIt last,
491 : std::forward_iterator_tag)
492 : {
493 80 : auto const n =
494 : static_cast<std::size_t>(
495 80 : std::distance(first, last));
496 80 : auto const n0 = size();
497 80 : if(n > max_size() - n0)
498 : {
499 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
500 1 : detail::throw_system_error( error::object_too_large, &loc );
501 : }
502 79 : revert_insert r( *this, n0 + n );
503 738 : while(first != last)
504 : {
505 734 : insert(*first);
506 661 : ++first;
507 : }
508 4 : r.commit();
509 77 : }
510 :
511 : template< class... Args >
512 : std::pair<object::iterator, bool>
513 3991 : object::
514 : emplace_impl( string_view key, Args&& ... args )
515 : {
516 3991 : std::pair<iterator, std::size_t> search_result(nullptr, 0);
517 3991 : if( !empty() )
518 : {
519 3462 : search_result = detail::find_in_object(*this, key);
520 3462 : if( search_result.first )
521 30 : 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 4253 : key_value_pair kv( static_cast<Args&&>(args)..., sp_ );
527 : // the key might get deallocated too
528 3808 : key = kv.key();
529 :
530 3808 : std::size_t const old_capacity = capacity();
531 3808 : reserve(size() + 1);
532 4294 : if( (empty() && capacity() > detail::small_object_size_)
533 4294 : || (capacity() != old_capacity) )
534 724 : search_result.second = detail::digest(
535 724 : key.begin(), key.end(), t_->salt);
536 :
537 3781 : BOOST_ASSERT(
538 : t_->is_small() ||
539 : (search_result.second ==
540 : detail::digest(key.begin(), key.end(), t_->salt)) );
541 :
542 3781 : return { insert_impl(pilfer(kv), search_result.second), true };
543 3808 : }
544 :
545 : //----------------------------------------------------------
546 :
547 : namespace detail {
548 :
549 34879 : unchecked_object::
550 1086 : ~unchecked_object()
551 : {
552 34879 : if(! data_)
553 33791 : return;
554 1088 : if(sp_.is_not_shared_and_deallocate_is_trivial())
555 2 : return;
556 1086 : value* p = data_;
557 1146 : while(size_--)
558 : {
559 60 : p[0].~value();
560 60 : p[1].~value();
561 60 : p += 2;
562 : }
563 34879 : }
564 :
565 : } // detail
566 :
567 : } // namespace json
568 : } // namespace boost
569 :
570 : #endif
|
