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