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_IPP
11 : #define BOOST_JSON_IMPL_OBJECT_IPP
12 :
13 : #include <boost/core/detail/static_assert.hpp>
14 : #include <boost/container_hash/hash.hpp>
15 : #include <boost/json/object.hpp>
16 : #include <boost/json/detail/digest.hpp>
17 : #include <boost/json/detail/except.hpp>
18 : #include <algorithm>
19 : #include <cmath>
20 : #include <cstdlib>
21 : #include <cstring>
22 : #include <new>
23 : #include <stdexcept>
24 : #include <type_traits>
25 :
26 : namespace boost {
27 : namespace json {
28 : namespace detail {
29 :
30 : template<class CharRange>
31 : std::pair<key_value_pair*, std::size_t>
32 HIT 42858 : find_in_object(
33 : object const& obj,
34 : CharRange key) noexcept
35 : {
36 42858 : BOOST_ASSERT(obj.t_->capacity > 0);
37 42858 : if(obj.t_->is_small())
38 : {
39 41004 : auto it = &(*obj.t_)[0];
40 : auto const last =
41 41004 : &(*obj.t_)[obj.t_->size];
42 75339 : for(;it != last; ++it)
43 35062 : if( key == it->key() )
44 727 : return { it, 0 };
45 40277 : return { nullptr, 0 };
46 : }
47 : std::pair<
48 : key_value_pair*,
49 1854 : std::size_t> result;
50 1854 : BOOST_ASSERT(obj.t_->salt != 0);
51 1854 : result.second = detail::digest(key.begin(), key.end(), obj.t_->salt);
52 1854 : auto i = obj.t_->bucket(
53 : result.second);
54 2628 : while(i != object::null_index_)
55 : {
56 1113 : auto& v = (*obj.t_)[i];
57 1113 : if( key == v.key() )
58 : {
59 339 : result.first = &v;
60 339 : return result;
61 : }
62 774 : i = access::next(v);
63 : }
64 1515 : result.first = nullptr;
65 1515 : return result;
66 : }
67 :
68 :
69 : template
70 : std::pair<key_value_pair*, std::size_t>
71 : find_in_object<string_view>(
72 : object const& obj,
73 : string_view key) noexcept;
74 :
75 : } // namespace detail
76 :
77 : //----------------------------------------------------------
78 :
79 : constexpr object::table::table() = default;
80 :
81 : // empty objects point here
82 : BOOST_JSON_REQUIRE_CONST_INIT
83 : object::table object::empty_;
84 :
85 : std::size_t
86 7624 : object::table::
87 : digest(string_view key) const noexcept
88 : {
89 7624 : BOOST_ASSERT(salt != 0);
90 7624 : return detail::digest(
91 15248 : key.begin(), key.end(), salt);
92 : }
93 :
94 : auto
95 11042 : object::table::
96 : bucket(std::size_t hash) noexcept ->
97 : index_t&
98 : {
99 : return reinterpret_cast<
100 11042 : index_t*>(&(*this)[capacity])[
101 11042 : hash % capacity];
102 : }
103 :
104 : auto
105 7598 : object::table::
106 : bucket(string_view key) noexcept ->
107 : index_t&
108 : {
109 7598 : return bucket(digest(key));
110 : }
111 :
112 : void
113 393 : object::table::
114 : clear() noexcept
115 : {
116 393 : BOOST_ASSERT(! is_small());
117 : // initialize buckets
118 786 : std::memset(
119 : reinterpret_cast<index_t*>(
120 393 : &(*this)[capacity]),
121 : 0xff, // null_index_
122 393 : capacity * sizeof(index_t));
123 393 : }
124 :
125 : object::table*
126 35482 : object::table::
127 : allocate(
128 : std::size_t capacity,
129 : std::uintptr_t salt,
130 : storage_ptr const& sp)
131 : {
132 : BOOST_CORE_STATIC_ASSERT(
133 : alignof(key_value_pair) >= alignof(index_t));
134 35482 : BOOST_ASSERT(capacity > 0);
135 35482 : BOOST_ASSERT(capacity <= max_size());
136 : table* p;
137 35482 : if(capacity <= detail::small_object_size_)
138 : {
139 : p = reinterpret_cast<
140 35078 : table*>(sp->allocate(
141 35078 : sizeof(table) + capacity *
142 : sizeof(key_value_pair)));
143 34987 : p->capacity = static_cast<
144 : std::uint32_t>(capacity);
145 : }
146 : else
147 : {
148 : p = reinterpret_cast<
149 404 : table*>(sp->allocate(
150 404 : sizeof(table) + capacity * (
151 : sizeof(key_value_pair) +
152 : sizeof(index_t))));
153 389 : p->capacity = static_cast<
154 : std::uint32_t>(capacity);
155 389 : p->clear();
156 : }
157 35376 : if(salt)
158 : {
159 489 : p->salt = salt;
160 : }
161 : else
162 : {
163 : // VFALCO This would be better if it
164 : // was random, but maybe this
165 : // is good enough.
166 34887 : p->salt = reinterpret_cast<
167 : std::uintptr_t>(p);
168 : }
169 35376 : return p;
170 : }
171 :
172 : //----------------------------------------------------------
173 :
174 : void
175 374 : object::
176 : revert_construct::
177 : destroy() noexcept
178 : {
179 374 : obj_->destroy();
180 374 : }
181 :
182 : //----------------------------------------------------------
183 :
184 : void
185 231 : object::
186 : revert_insert::
187 : destroy() noexcept
188 : {
189 : // when no reallocation happened, insert_impl linked each rolled-back
190 : // element into a bucket of the live table; unlink them while their keys
191 : // are still valid, otherwise a bucket head is left pointing at a slot
192 : // that is about to be destroyed
193 231 : if( !t_ && !obj_->t_->is_small() )
194 : {
195 58 : key_value_pair* const first = &(*obj_->t_)[size_];
196 58 : key_value_pair* last = obj_->end();
197 574 : while( last != first )
198 : {
199 516 : --last;
200 516 : obj_->remove( obj_->t_->bucket( last->key() ), *last );
201 : }
202 : }
203 231 : if(! obj_->sp_.is_not_shared_and_deallocate_is_trivial())
204 230 : obj_->destroy(
205 230 : &(*obj_->t_)[size_],
206 230 : obj_->end());
207 231 : }
208 :
209 : //----------------------------------------------------------
210 : //
211 : // Construction
212 : //
213 : //----------------------------------------------------------
214 :
215 34880 : object::
216 34880 : object(detail::unchecked_object&& uo)
217 34880 : : sp_(uo.storage())
218 : {
219 34880 : if(uo.size() == 0)
220 : {
221 1049 : t_ = &empty_;
222 1049 : return;
223 : }
224 : // should already be checked
225 33831 : BOOST_ASSERT(
226 : uo.size() <= max_size());
227 33831 : t_ = table::allocate(
228 33831 : uo.size(), 0, sp_);
229 :
230 : // insert all elements, keeping
231 : // the last of any duplicate keys.
232 33792 : auto dest = begin();
233 33792 : auto src = uo.release();
234 33792 : auto const end = src + 2 * uo.size();
235 33792 : if(t_->is_small())
236 : {
237 33759 : t_->size = 0;
238 70269 : while(src != end)
239 : {
240 36510 : access::construct_key_value_pair(
241 36510 : dest, pilfer(src[0]), pilfer(src[1]));
242 36510 : src += 2;
243 36510 : auto result = detail::find_in_object(*this, dest->key());
244 36510 : if(! result.first)
245 : {
246 36500 : ++dest;
247 36500 : ++t_->size;
248 36500 : continue;
249 : }
250 : // handle duplicate
251 10 : auto& v = *result.first;
252 : // don't bother to check if
253 : // storage deallocate is trivial
254 10 : v.~key_value_pair();
255 : // trivial relocate
256 10 : std::memcpy(
257 : static_cast<void*>(&v),
258 : dest, sizeof(v));
259 : }
260 33759 : return;
261 : }
262 1674 : while(src != end)
263 : {
264 1641 : access::construct_key_value_pair(
265 1641 : dest, pilfer(src[0]), pilfer(src[1]));
266 1641 : src += 2;
267 1641 : auto& head = t_->bucket(dest->key());
268 1641 : auto i = head;
269 : for(;;)
270 : {
271 2497 : if(i == null_index_)
272 : {
273 : // end of bucket
274 1640 : access::next(
275 1640 : *dest) = head;
276 1640 : head = static_cast<index_t>(
277 1640 : dest - begin());
278 1640 : ++dest;
279 1640 : break;
280 : }
281 857 : auto& v = (*t_)[i];
282 857 : if(v.key() != dest->key())
283 : {
284 856 : i = access::next(v);
285 856 : continue;
286 : }
287 :
288 : // handle duplicate
289 1 : access::next(*dest) =
290 1 : access::next(v);
291 : // don't bother to check if
292 : // storage deallocate is trivial
293 1 : v.~key_value_pair();
294 : // trivial relocate
295 1 : std::memcpy(
296 : static_cast<void*>(&v),
297 : dest, sizeof(v));
298 1 : break;
299 856 : }
300 : }
301 33 : t_->size = static_cast<
302 33 : index_t>(dest - begin());
303 39 : }
304 :
305 35950 : object::
306 34398 : ~object() noexcept
307 : {
308 35950 : if(sp_.is_not_shared_and_deallocate_is_trivial())
309 6 : return;
310 35944 : if(t_->capacity == 0)
311 1546 : return;
312 34398 : destroy();
313 35950 : }
314 :
315 7 : object::
316 : object(
317 : std::size_t min_capacity,
318 7 : storage_ptr sp)
319 7 : : sp_(std::move(sp))
320 7 : , t_(&empty_)
321 : {
322 7 : reserve(min_capacity);
323 7 : }
324 :
325 71 : object::
326 71 : object(object&& other) noexcept
327 71 : : sp_(other.sp_)
328 142 : , t_(detail::exchange(
329 71 : other.t_, &empty_))
330 : {
331 71 : }
332 :
333 184 : object::
334 : object(
335 : object&& other,
336 184 : storage_ptr sp)
337 184 : : sp_(std::move(sp))
338 : {
339 184 : if(*sp_ == *other.sp_)
340 : {
341 192 : t_ = detail::exchange(
342 96 : other.t_, &empty_);
343 96 : return;
344 : }
345 :
346 88 : t_ = &empty_;
347 151 : object(other, sp_).swap(*this);
348 63 : }
349 :
350 197 : object::
351 : object(
352 : object const& other,
353 197 : storage_ptr sp)
354 197 : : sp_(std::move(sp))
355 197 : , t_(&empty_)
356 : {
357 197 : reserve(other.size());
358 185 : revert_construct r(*this);
359 185 : if(t_->is_small())
360 : {
361 712 : for(auto const& v : other)
362 : {
363 724 : ::new(end())
364 800 : key_value_pair(v, sp_);
365 572 : ++t_->size;
366 : }
367 64 : r.commit();
368 64 : return;
369 : }
370 2485 : for(auto const& v : other)
371 : {
372 : // skip duplicate checking
373 : auto& head =
374 2480 : t_->bucket(v.key());
375 2480 : auto pv = ::new(end())
376 2520 : key_value_pair(v, sp_);
377 2440 : access::next(*pv) = head;
378 2440 : head = t_->size;
379 2440 : ++t_->size;
380 : }
381 5 : r.commit();
382 313 : }
383 :
384 382 : object::
385 : object(
386 : std::initializer_list<std::pair<
387 : string_view, value_ref>> init,
388 : std::size_t min_capacity,
389 382 : storage_ptr sp)
390 382 : : sp_(std::move(sp))
391 382 : , t_(&empty_)
392 : {
393 382 : if( min_capacity < init.size())
394 336 : min_capacity = init.size();
395 382 : reserve(min_capacity);
396 366 : revert_construct r(*this);
397 366 : insert(init);
398 253 : r.commit();
399 495 : }
400 :
401 : //----------------------------------------------------------
402 : //
403 : // Assignment
404 : //
405 : //----------------------------------------------------------
406 :
407 : object&
408 22 : object::
409 : operator=(object const& other)
410 : {
411 39 : object tmp(other, sp_);
412 5 : this->~object();
413 5 : ::new(this) object(pilfer(tmp));
414 5 : return *this;
415 5 : }
416 :
417 : object&
418 7 : object::
419 : operator=(object&& other)
420 : {
421 11 : object tmp(std::move(other), sp_);
422 3 : this->~object();
423 3 : ::new(this) object(pilfer(tmp));
424 3 : return *this;
425 3 : }
426 :
427 : object&
428 7 : object::
429 : operator=(
430 : std::initializer_list<std::pair<
431 : string_view, value_ref>> init)
432 : {
433 11 : object tmp(init, sp_);
434 3 : this->~object();
435 3 : ::new(this) object(pilfer(tmp));
436 3 : return *this;
437 3 : }
438 :
439 : //----------------------------------------------------------
440 : //
441 : // Lookup
442 : //
443 : //----------------------------------------------------------
444 :
445 : system::result<value&>
446 4 : object::
447 : try_at(string_view key) noexcept
448 : {
449 4 : auto it = find(key);
450 4 : if( it != end() )
451 2 : return it->value();
452 :
453 2 : system::error_code ec;
454 2 : BOOST_JSON_FAIL(ec, error::out_of_range);
455 2 : return ec;
456 : }
457 :
458 : system::result<value const&>
459 109 : object::
460 : try_at(string_view key) const noexcept
461 : {
462 109 : auto it = find(key);
463 109 : if( it != end() )
464 103 : return it->value();
465 :
466 6 : system::error_code ec;
467 6 : BOOST_JSON_FAIL(ec, error::out_of_range);
468 6 : return ec;
469 : }
470 :
471 : value const&
472 105 : object::
473 : at(string_view key, source_location const& loc) const&
474 : {
475 105 : return try_at(key).value(loc);
476 : }
477 :
478 : //----------------------------------------------------------
479 : //
480 : // Modifiers
481 : //
482 : //----------------------------------------------------------
483 :
484 : void
485 7 : object::
486 : clear() noexcept
487 : {
488 7 : if(empty())
489 2 : return;
490 5 : if(! sp_.is_not_shared_and_deallocate_is_trivial())
491 5 : destroy(begin(), end());
492 5 : if(! t_->is_small())
493 4 : t_->clear();
494 5 : t_->size = 0;
495 : }
496 :
497 : void
498 426 : object::
499 : insert(
500 : std::initializer_list<std::pair<
501 : string_view, value_ref>> init)
502 : {
503 426 : auto const n0 = size();
504 426 : if(init.size() > max_size() - n0)
505 : {
506 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
507 1 : detail::throw_system_error( error::object_too_large, &loc );
508 : }
509 425 : revert_insert r( *this, n0 + init.size() );
510 418 : if(t_->is_small())
511 : {
512 2035 : for(auto& iv : init)
513 : {
514 : auto result =
515 1834 : detail::find_in_object(*this, iv.first);
516 1834 : if(result.first)
517 : {
518 : // ignore duplicate
519 4 : continue;
520 : }
521 1907 : ::new(end()) key_value_pair(
522 : iv.first,
523 2058 : iv.second.make_value(sp_));
524 1753 : ++t_->size;
525 : }
526 201 : r.commit();
527 201 : return;
528 : }
529 1999 : for(auto& iv : init)
530 : {
531 1939 : auto& head = t_->bucket(iv.first);
532 1939 : auto i = head;
533 : for(;;)
534 : {
535 2582 : if(i == null_index_)
536 : {
537 : // VFALCO value_ref should construct
538 : // a key_value_pair using placement
539 1937 : auto& v = *::new(end())
540 : key_value_pair(
541 : iv.first,
542 2097 : iv.second.make_value(sp_));
543 1857 : access::next(v) = head;
544 1857 : head = static_cast<index_t>(
545 1857 : t_->size);
546 1857 : ++t_->size;
547 1857 : break;
548 : }
549 645 : auto& v = (*t_)[i];
550 645 : if(v.key() == iv.first)
551 : {
552 : // ignore duplicate
553 2 : break;
554 : }
555 643 : i = access::next(v);
556 643 : }
557 : }
558 60 : r.commit();
559 418 : }
560 :
561 : auto
562 6 : object::
563 : erase(const_iterator pos) noexcept ->
564 : iterator
565 : {
566 6 : return do_erase(pos,
567 2 : [this](iterator p) {
568 : // the casts silence warnings
569 2 : std::memcpy(
570 : static_cast<void*>(p),
571 2 : static_cast<void const*>(end()),
572 : sizeof(*p));
573 2 : },
574 3 : [this](iterator p) {
575 3 : reindex_relocate(end(), p);
576 6 : });
577 : }
578 :
579 : auto
580 5 : object::
581 : erase(string_view key) noexcept ->
582 : std::size_t
583 : {
584 5 : auto it = find(key);
585 5 : if(it == end())
586 1 : return 0;
587 4 : erase(it);
588 4 : return 1;
589 : }
590 :
591 : auto
592 3 : object::
593 : stable_erase(const_iterator pos) noexcept ->
594 : iterator
595 : {
596 3 : return do_erase(pos,
597 2 : [this](iterator p) {
598 : // the casts silence warnings
599 2 : std::memmove(
600 : static_cast<void*>(p),
601 2 : static_cast<void const*>(p + 1),
602 2 : sizeof(*p) * (end() - p));
603 2 : },
604 1 : [this](iterator p) {
605 10 : for (; p != end(); ++p)
606 : {
607 9 : reindex_relocate(p + 1, p);
608 : }
609 3 : });
610 : }
611 :
612 : auto
613 2 : object::
614 : stable_erase(string_view key) noexcept ->
615 : std::size_t
616 : {
617 2 : auto it = find(key);
618 2 : if(it == end())
619 1 : return 0;
620 1 : stable_erase(it);
621 1 : return 1;
622 : }
623 :
624 : void
625 36 : object::
626 : swap(object& other)
627 : {
628 36 : if(*sp_ == *other.sp_)
629 : {
630 52 : t_ = detail::exchange(
631 26 : other.t_, t_);
632 26 : return;
633 : }
634 : object temp1(
635 10 : std::move(*this),
636 24 : other.storage());
637 : object temp2(
638 6 : std::move(other),
639 16 : this->storage());
640 2 : other.~object();
641 2 : ::new(&other) object(pilfer(temp1));
642 2 : this->~object();
643 2 : ::new(this) object(pilfer(temp2));
644 6 : }
645 :
646 : //----------------------------------------------------------
647 : //
648 : // Lookup
649 : //
650 : //----------------------------------------------------------
651 :
652 : auto
653 147 : object::
654 : operator[](string_view key) ->
655 : value&
656 : {
657 : auto const result =
658 147 : emplace(key, nullptr);
659 294 : return result.first->value();
660 : }
661 :
662 : auto
663 8 : object::
664 : count(string_view key) const noexcept ->
665 : std::size_t
666 : {
667 8 : if(find(key) == end())
668 3 : return 0;
669 5 : return 1;
670 : }
671 :
672 : auto
673 31 : object::
674 : find(string_view key) noexcept ->
675 : iterator
676 : {
677 31 : if(empty())
678 1 : return end();
679 : auto const p =
680 30 : detail::find_in_object(*this, key).first;
681 30 : if(p)
682 21 : return p;
683 9 : return end();
684 : }
685 :
686 : auto
687 880 : object::
688 : find(string_view key) const noexcept ->
689 : const_iterator
690 : {
691 880 : if(empty())
692 1 : return end();
693 : auto const p =
694 879 : detail::find_in_object(*this, key).first;
695 879 : if(p)
696 867 : return p;
697 12 : return end();
698 : }
699 :
700 : bool
701 3 : object::
702 : contains(
703 : string_view key) const noexcept
704 : {
705 3 : if(empty())
706 1 : return false;
707 2 : return detail::find_in_object(*this, key).first
708 2 : != nullptr;
709 : }
710 :
711 : value const*
712 3 : object::
713 : if_contains(
714 : string_view key) const noexcept
715 : {
716 3 : auto const it = find(key);
717 3 : if(it != end())
718 2 : return &it->value();
719 1 : return nullptr;
720 : }
721 :
722 : value*
723 5 : object::
724 : if_contains(
725 : string_view key) noexcept
726 : {
727 5 : auto const it = find(key);
728 5 : if(it != end())
729 4 : return &it->value();
730 1 : return nullptr;
731 : }
732 :
733 : //----------------------------------------------------------
734 : //
735 : // (private)
736 : //
737 : //----------------------------------------------------------
738 :
739 : key_value_pair*
740 3784 : object::
741 : insert_impl(
742 : pilfered<key_value_pair> p,
743 : std::size_t hash)
744 : {
745 3784 : BOOST_ASSERT(
746 : capacity() > size());
747 3784 : if(t_->is_small())
748 : {
749 2194 : auto const pv = ::new(end())
750 2194 : key_value_pair(p);
751 2194 : ++t_->size;
752 2194 : return pv;
753 : }
754 : auto& head =
755 1590 : t_->bucket(hash);
756 1590 : auto const pv = ::new(end())
757 1590 : key_value_pair(p);
758 1590 : access::next(*pv) = head;
759 1590 : head = t_->size;
760 1590 : ++t_->size;
761 1590 : return pv;
762 : }
763 :
764 : // allocate new table, copy elements there, and rehash them
765 : object::table*
766 1658 : object::
767 : reserve_impl(std::size_t new_capacity)
768 : {
769 1658 : BOOST_ASSERT(
770 : new_capacity > t_->capacity);
771 1651 : auto t = table::allocate(
772 : growth(new_capacity),
773 1658 : t_->salt, sp_);
774 1584 : if(! empty())
775 488 : std::memcpy(
776 : static_cast<
777 488 : void*>(&(*t)[0]),
778 488 : begin(),
779 488 : size() * sizeof(
780 : key_value_pair));
781 1584 : t->size = t_->size;
782 1584 : std::swap(t_, t);
783 :
784 1584 : if(! t_->is_small())
785 : {
786 : // rebuild hash table,
787 : // without dup checks
788 356 : auto p = end();
789 356 : index_t i = t_->size;
790 1361 : while(i-- > 0)
791 : {
792 1005 : --p;
793 : auto& head =
794 1005 : t_->bucket(p->key());
795 1005 : access::next(*p) = head;
796 1005 : head = i;
797 : }
798 : }
799 :
800 1584 : return t;
801 : }
802 :
803 : bool
804 75 : object::
805 : equal(object const& other) const noexcept
806 : {
807 75 : if(size() != other.size())
808 5 : return false;
809 70 : auto const end_ = other.end();
810 825 : for(auto e : *this)
811 : {
812 757 : auto it = other.find(e.key());
813 757 : if(it == end_)
814 1 : return false;
815 756 : if(it->value() != e.value())
816 1 : return false;
817 757 : }
818 68 : return true;
819 : }
820 :
821 : std::size_t
822 1658 : object::
823 : growth(
824 : std::size_t new_size) const
825 : {
826 1658 : if(new_size > max_size())
827 : {
828 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
829 7 : detail::throw_system_error( error::object_too_large, &loc );
830 : }
831 1651 : std::size_t const old = capacity();
832 1651 : if(old > max_size() - old / 2)
833 2 : return new_size;
834 1649 : std::size_t const g =
835 1649 : old + old / 2; // 1.5x
836 1649 : if(g < new_size)
837 1247 : return new_size;
838 402 : return g;
839 : }
840 :
841 : void
842 533 : object::
843 : remove(
844 : index_t& head,
845 : key_value_pair& v) noexcept
846 : {
847 533 : BOOST_ASSERT(! t_->is_small());
848 : auto const i = static_cast<
849 533 : index_t>(&v - begin());
850 533 : if(head == i)
851 : {
852 529 : head = access::next(v);
853 529 : return;
854 : }
855 : auto* pn =
856 4 : &access::next((*t_)[head]);
857 5 : while(*pn != i)
858 1 : pn = &access::next((*t_)[*pn]);
859 4 : *pn = access::next(v);
860 : }
861 :
862 : void
863 34772 : object::
864 : destroy() noexcept
865 : {
866 34772 : BOOST_ASSERT(t_->capacity > 0);
867 34772 : BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
868 34772 : destroy(begin(), end());
869 34772 : table::deallocate(t_, sp_);
870 34772 : }
871 :
872 : void
873 35007 : object::
874 : destroy(
875 : key_value_pair* first,
876 : key_value_pair* last) noexcept
877 : {
878 35007 : BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
879 83519 : while(last != first)
880 48512 : (--last)->~key_value_pair();
881 35007 : }
882 :
883 : template<class FS, class FB>
884 : auto
885 9 : object::
886 : do_erase(
887 : const_iterator pos,
888 : FS small_reloc,
889 : FB big_reloc) noexcept
890 : -> iterator
891 : {
892 9 : auto p = begin() + (pos - begin());
893 9 : if(t_->is_small())
894 : {
895 4 : p->~value_type();
896 4 : --t_->size;
897 4 : if(p != end())
898 : {
899 4 : small_reloc(p);
900 : }
901 4 : return p;
902 : }
903 5 : remove(t_->bucket(p->key()), *p);
904 5 : p->~value_type();
905 5 : --t_->size;
906 5 : if(p != end())
907 : {
908 4 : big_reloc(p);
909 : }
910 5 : return p;
911 : }
912 :
913 : void
914 12 : object::
915 : reindex_relocate(
916 : key_value_pair* src,
917 : key_value_pair* dst) noexcept
918 : {
919 12 : BOOST_ASSERT(! t_->is_small());
920 12 : auto& head = t_->bucket(src->key());
921 12 : remove(head, *src);
922 : // the casts silence warnings
923 12 : std::memcpy(
924 : static_cast<void*>(dst),
925 : static_cast<void const*>(src),
926 : sizeof(*dst));
927 12 : access::next(*dst) = head;
928 12 : head = static_cast<
929 12 : index_t>(dst - begin());
930 12 : }
931 :
932 : } // namespace json
933 : } // namespace boost
934 :
935 : //----------------------------------------------------------
936 : //
937 : // std::hash specialization
938 : //
939 : //----------------------------------------------------------
940 :
941 : std::size_t
942 8 : std::hash<::boost::json::object>::operator()(
943 : ::boost::json::object const& jo) const noexcept
944 : {
945 8 : return ::boost::hash< ::boost::json::object >()( jo );
946 : }
947 :
948 : //----------------------------------------------------------
949 :
950 :
951 : #endif
|
