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