json/impl/object.ipp

0001 //
0002 // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // Official repository: https://github.com/boostorg/json
0008 //
0009
0010 #ifndef BOOST_JSON_IMPL_OBJECT_IPP
0011 #define BOOST_JSON_IMPL_OBJECT_IPP
0012
0013 #include <boost/container_hash/hash.hpp>
0014 #include <boost/json/object.hpp>
0015 #include <boost/json/detail/digest.hpp>
0016 #include <boost/json/detail/except.hpp>
0017 #include <algorithm>
0018 #include <cmath>
0019 #include <cstdlib>
0020 #include <cstring>
0021 #include <new>
0022 #include <stdexcept>
0023 #include <type_traits>
0024
0025 namespace boost {
0026 namespace json {
0027 namespace detail {
0028
0029 template<class CharRange>
0030 std::pair<key_value_pair*, std::size_t>
0031 find_in_object(
0032     object const& obj,
0033     CharRange key) noexcept
0034 {
0035     BOOST_ASSERT(obj.t_->capacity > 0);
0036     if(obj.t_->is_small())
0037     {
0038         auto it = &(*obj.t_)[0];
0039         auto const last =
0040             &(*obj.t_)[obj.t_->size];
0041         for(;it != last; ++it)
0042             if( key == it->key() )
0043                 return { it, 0 };
0044         return { nullptr, 0 };
0045     }
0046     std::pair<
0047         key_value_pair*,
0048         std::size_t> result;
0049     BOOST_ASSERT(obj.t_->salt != 0);
0050     result.second = detail::digest(key.begin(), key.end(), obj.t_->salt);
0051     auto i = obj.t_->bucket(
0052         result.second);
0053     while(i != object::null_index_)
0054     {
0055         auto& v = (*obj.t_)[i];
0056         if( key == v.key() )
0057         {
0058             result.first = &v;
0059             return result;
0060         }
0061         i = access::next(v);
0062     }
0063     result.first = nullptr;
0064     return result;
0065 }
0066
0067
0068 template
0069 std::pair<key_value_pair*, std::size_t>
0070 find_in_object<string_view>(
0071     object const& obj,
0072     string_view key) noexcept;
0073
0074 } // namespace detail
0075
0076 //----------------------------------------------------------
0077
0078 constexpr object::table::table() = default;
0079
0080 // empty objects point here
0081 BOOST_JSON_REQUIRE_CONST_INIT
0082 object::table object::empty_;
0083
0084 std::size_t
0085 object::table::
0086 digest(string_view key) const noexcept
0087 {
0088     BOOST_ASSERT(salt != 0);
0089     return detail::digest(
0090         key.begin(), key.end(), salt);
0091 }
0092
0093 auto
0094 object::table::
0095 bucket(std::size_t hash) noexcept ->
0096     index_t&
0097 {
0098     return reinterpret_cast<
0099         index_t*>(&(*this)[capacity])[
0100             hash % capacity];
0101 }
0102
0103 auto
0104 object::table::
0105 bucket(string_view key) noexcept ->
0106     index_t&
0107 {
0108     return bucket(digest(key));
0109 }
0110
0111 void
0112 object::table::
0113 clear() noexcept
0114 {
0115     BOOST_ASSERT(! is_small());
0116     // initialize buckets
0117     std::memset(
0118         reinterpret_cast<index_t*>(
0119             &(*this)[capacity]),
0120         0xff, // null_index_
0121         capacity * sizeof(index_t));
0122 }
0123
0124 object::table*
0125 object::table::
0126 allocate(
0127     std::size_t capacity,
0128     std::uintptr_t salt,
0129     storage_ptr const& sp)
0130 {
0131     BOOST_STATIC_ASSERT(
0132         alignof(key_value_pair) >=
0133         alignof(index_t));
0134     BOOST_ASSERT(capacity > 0);
0135     BOOST_ASSERT(capacity <= max_size());
0136     table* p;
0137     if(capacity <= detail::small_object_size_)
0138     {
0139         p = reinterpret_cast<
0140             table*>(sp->allocate(
0141                 sizeof(table) + capacity *
0142                     sizeof(key_value_pair)));
0143         p->capacity = static_cast<
0144             std::uint32_t>(capacity);
0145     }
0146     else
0147     {
0148         p = reinterpret_cast<
0149             table*>(sp->allocate(
0150                 sizeof(table) + capacity * (
0151                     sizeof(key_value_pair) +
0152                     sizeof(index_t))));
0153         p->capacity = static_cast<
0154             std::uint32_t>(capacity);
0155         p->clear();
0156     }
0157     if(salt)
0158     {
0159         p->salt = salt;
0160     }
0161     else
0162     {
0163         // VFALCO This would be better if it
0164         //        was random, but maybe this
0165         //        is good enough.
0166         p->salt = reinterpret_cast<
0167             std::uintptr_t>(p);
0168     }
0169     return p;
0170 }
0171
0172 //----------------------------------------------------------
0173
0174 void
0175 object::
0176 revert_construct::
0177 destroy() noexcept
0178 {
0179     obj_->destroy();
0180 }
0181
0182 //----------------------------------------------------------
0183
0184 void
0185 object::
0186 revert_insert::
0187 destroy() noexcept
0188 {
0189     obj_->destroy(
0190         &(*obj_->t_)[size_],
0191         obj_->end());
0192 }
0193
0194 //----------------------------------------------------------
0195 //
0196 // Construction
0197 //
0198 //----------------------------------------------------------
0199
0200 object::
0201 object(detail::unchecked_object&& uo)
0202     : sp_(uo.storage())
0203 {
0204     if(uo.size() == 0)
0205     {
0206         t_ = &empty_;
0207         return;
0208     }
0209     // should already be checked
0210     BOOST_ASSERT(
0211         uo.size() <= max_size());
0212     t_ = table::allocate(
0213         uo.size(), 0, sp_);
0214
0215     // insert all elements, keeping
0216     // the last of any duplicate keys.
0217     auto dest = begin();
0218     auto src = uo.release();
0219     auto const end = src + 2 * uo.size();
0220     if(t_->is_small())
0221     {
0222         t_->size = 0;
0223         while(src != end)
0224         {
0225             access::construct_key_value_pair(
0226                 dest, pilfer(src[0]), pilfer(src[1]));
0227             src += 2;
0228             auto result = detail::find_in_object(*this, dest->key());
0229             if(! result.first)
0230             {
0231                 ++dest;
0232                 ++t_->size;
0233                 continue;
0234             }
0235             // handle duplicate
0236             auto& v = *result.first;
0237             // don't bother to check if
0238             // storage deallocate is trivial
0239             v.~key_value_pair();
0240             // trivial relocate
0241             std::memcpy(
0242                 static_cast<void*>(&v),
0243                     dest, sizeof(v));
0244         }
0245         return;
0246     }
0247     while(src != end)
0248     {
0249         access::construct_key_value_pair(
0250             dest, pilfer(src[0]), pilfer(src[1]));
0251         src += 2;
0252         auto& head = t_->bucket(dest->key());
0253         auto i = head;
0254         for(;;)
0255         {
0256             if(i == null_index_)
0257             {
0258                 // end of bucket
0259                 access::next(
0260                     *dest) = head;
0261                 head = static_cast<index_t>(
0262                     dest - begin());
0263                 ++dest;
0264                 break;
0265             }
0266             auto& v = (*t_)[i];
0267             if(v.key() != dest->key())
0268             {
0269                 i = access::next(v);
0270                 continue;
0271             }
0272
0273             // handle duplicate
0274             access::next(*dest) =
0275                 access::next(v);
0276             // don't bother to check if
0277             // storage deallocate is trivial
0278             v.~key_value_pair();
0279             // trivial relocate
0280             std::memcpy(
0281                 static_cast<void*>(&v),
0282                     dest, sizeof(v));
0283             break;
0284         }
0285     }
0286     t_->size = static_cast<
0287         index_t>(dest - begin());
0288 }
0289
0290 object::
0291 ~object() noexcept
0292 {
0293     if(sp_.is_not_shared_and_deallocate_is_trivial())
0294         return;
0295     if(t_->capacity == 0)
0296         return;
0297     destroy();
0298 }
0299
0300 object::
0301 object(
0302     std::size_t min_capacity,
0303     storage_ptr sp)
0304     : sp_(std::move(sp))
0305     , t_(&empty_)
0306 {
0307     reserve(min_capacity);
0308 }
0309
0310 object::
0311 object(object&& other) noexcept
0312     : sp_(other.sp_)
0313     , t_(detail::exchange(
0314         other.t_, &empty_))
0315 {
0316 }
0317
0318 object::
0319 object(
0320     object&& other,
0321     storage_ptr sp)
0322     : sp_(std::move(sp))
0323 {
0324     if(*sp_ == *other.sp_)
0325     {
0326         t_ = detail::exchange(
0327             other.t_, &empty_);
0328         return;
0329     }
0330
0331     t_ = &empty_;
0332     object(other, sp_).swap(*this);
0333 }
0334
0335 object::
0336 object(
0337     object const& other,
0338     storage_ptr sp)
0339     : sp_(std::move(sp))
0340     , t_(&empty_)
0341 {
0342     reserve(other.size());
0343     revert_construct r(*this);
0344     if(t_->is_small())
0345     {
0346         for(auto const& v : other)
0347         {
0348             ::new(end())
0349                 key_value_pair(v, sp_);
0350             ++t_->size;
0351         }
0352         r.commit();
0353         return;
0354     }
0355     for(auto const& v : other)
0356     {
0357         // skip duplicate checking
0358         auto& head =
0359             t_->bucket(v.key());
0360         auto pv = ::new(end())
0361             key_value_pair(v, sp_);
0362         access::next(*pv) = head;
0363         head = t_->size;
0364         ++t_->size;
0365     }
0366     r.commit();
0367 }
0368
0369 object::
0370 object(
0371     std::initializer_list<std::pair<
0372         string_view, value_ref>> init,
0373     std::size_t min_capacity,
0374     storage_ptr sp)
0375     : sp_(std::move(sp))
0376     , t_(&empty_)
0377 {
0378     if( min_capacity < init.size())
0379         min_capacity = init.size();
0380     reserve(min_capacity);
0381     revert_construct r(*this);
0382     insert(init);
0383     r.commit();
0384 }
0385
0386 //----------------------------------------------------------
0387 //
0388 // Assignment
0389 //
0390 //----------------------------------------------------------
0391
0392 object&
0393 object::
0394 operator=(object const& other)
0395 {
0396     object tmp(other, sp_);
0397     this->~object();
0398     ::new(this) object(pilfer(tmp));
0399     return *this;
0400 }
0401
0402 object&
0403 object::
0404 operator=(object&& other)
0405 {
0406     object tmp(std::move(other), sp_);
0407     this->~object();
0408     ::new(this) object(pilfer(tmp));
0409     return *this;
0410 }
0411
0412 object&
0413 object::
0414 operator=(
0415     std::initializer_list<std::pair<
0416         string_view, value_ref>> init)
0417 {
0418     object tmp(init, sp_);
0419     this->~object();
0420     ::new(this) object(pilfer(tmp));
0421     return *this;
0422 }
0423
0424 //----------------------------------------------------------
0425 //
0426 // Lookup
0427 //
0428 //----------------------------------------------------------
0429
0430 system::result<value&>
0431 object::
0432 try_at(string_view key) noexcept
0433 {
0434     auto it = find(key);
0435     if( it != end() )
0436         return it->value();
0437
0438     system::error_code ec;
0439     BOOST_JSON_FAIL(ec, error::out_of_range);
0440     return ec;
0441 }
0442
0443 system::result<value const&>
0444 object::
0445 try_at(string_view key) const noexcept
0446 {
0447     auto it = find(key);
0448     if( it != end() )
0449         return it->value();
0450
0451     system::error_code ec;
0452     BOOST_JSON_FAIL(ec, error::out_of_range);
0453     return ec;
0454 }
0455
0456 value const&
0457 object::
0458 at(string_view key, source_location const& loc) const&
0459 {
0460     return try_at(key).value(loc);
0461 }
0462
0463 //----------------------------------------------------------
0464 //
0465 // Modifiers
0466 //
0467 //----------------------------------------------------------
0468
0469 void
0470 object::
0471 clear() noexcept
0472 {
0473     if(empty())
0474         return;
0475     if(! sp_.is_not_shared_and_deallocate_is_trivial())
0476         destroy(begin(), end());
0477     if(! t_->is_small())
0478         t_->clear();
0479     t_->size = 0;
0480 }
0481
0482 void
0483 object::
0484 insert(
0485     std::initializer_list<std::pair<
0486         string_view, value_ref>> init)
0487 {
0488     auto const n0 = size();
0489     if(init.size() > max_size() - n0)
0490     {
0491         BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
0492         detail::throw_system_error( error::object_too_large, &loc );
0493     }
0494     revert_insert r( *this, n0 + init.size() );
0495     if(t_->is_small())
0496     {
0497         for(auto& iv : init)
0498         {
0499             auto result =
0500                 detail::find_in_object(*this, iv.first);
0501             if(result.first)
0502             {
0503                 // ignore duplicate
0504                 continue;
0505             }
0506             ::new(end()) key_value_pair(
0507                 iv.first,
0508                 iv.second.make_value(sp_));
0509             ++t_->size;
0510         }
0511         r.commit();
0512         return;
0513     }
0514     for(auto& iv : init)
0515     {
0516         auto& head = t_->bucket(iv.first);
0517         auto i = head;
0518         for(;;)
0519         {
0520             if(i == null_index_)
0521             {
0522                 // VFALCO value_ref should construct
0523                 // a key_value_pair using placement
0524                 auto& v = *::new(end())
0525                     key_value_pair(
0526                         iv.first,
0527                         iv.second.make_value(sp_));
0528                 access::next(v) = head;
0529                 head = static_cast<index_t>(
0530                     t_->size);
0531                 ++t_->size;
0532                 break;
0533             }
0534             auto& v = (*t_)[i];
0535             if(v.key() == iv.first)
0536             {
0537                 // ignore duplicate
0538                 break;
0539             }
0540             i = access::next(v);
0541         }
0542     }
0543     r.commit();
0544 }
0545
0546 auto
0547 object::
0548 erase(const_iterator pos) noexcept ->
0549     iterator
0550 {
0551     return do_erase(pos,
0552         [this](iterator p) {
0553             // the casts silence warnings
0554             std::memcpy(
0555                 static_cast<void*>(p),
0556                 static_cast<void const*>(end()),
0557                 sizeof(*p));
0558         },
0559         [this](iterator p) {
0560             reindex_relocate(end(), p);
0561         });
0562 }
0563
0564 auto
0565 object::
0566 erase(string_view key) noexcept ->
0567     std::size_t
0568 {
0569     auto it = find(key);
0570     if(it == end())
0571         return 0;
0572     erase(it);
0573     return 1;
0574 }
0575
0576 auto
0577 object::
0578 stable_erase(const_iterator pos) noexcept ->
0579     iterator
0580 {
0581     return do_erase(pos,
0582         [this](iterator p) {
0583             // the casts silence warnings
0584             std::memmove(
0585                 static_cast<void*>(p),
0586                 static_cast<void const*>(p + 1),
0587                 sizeof(*p) * (end() - p));
0588         },
0589         [this](iterator p) {
0590             for (; p != end(); ++p)
0591             {
0592                 reindex_relocate(p + 1, p);
0593             }
0594         });
0595 }
0596
0597 auto
0598 object::
0599 stable_erase(string_view key) noexcept ->
0600     std::size_t
0601 {
0602     auto it = find(key);
0603     if(it == end())
0604         return 0;
0605     stable_erase(it);
0606     return 1;
0607 }
0608
0609 void
0610 object::
0611 swap(object& other)
0612 {
0613     if(*sp_ == *other.sp_)
0614     {
0615         t_ = detail::exchange(
0616             other.t_, t_);
0617         return;
0618     }
0619     object temp1(
0620         std::move(*this),
0621         other.storage());
0622     object temp2(
0623         std::move(other),
0624         this->storage());
0625     other.~object();
0626     ::new(&other) object(pilfer(temp1));
0627     this->~object();
0628     ::new(this) object(pilfer(temp2));
0629 }
0630
0631 //----------------------------------------------------------
0632 //
0633 // Lookup
0634 //
0635 //----------------------------------------------------------
0636
0637 auto
0638 object::
0639 operator[](string_view key) ->
0640     value&
0641 {
0642     auto const result =
0643         emplace(key, nullptr);
0644     return result.first->value();
0645 }
0646
0647 auto
0648 object::
0649 count(string_view key) const noexcept ->
0650     std::size_t
0651 {
0652     if(find(key) == end())
0653         return 0;
0654     return 1;
0655 }
0656
0657 auto
0658 object::
0659 find(string_view key) noexcept ->
0660     iterator
0661 {
0662     if(empty())
0663         return end();
0664     auto const p =
0665         detail::find_in_object(*this, key).first;
0666     if(p)
0667         return p;
0668     return end();
0669 }
0670
0671 auto
0672 object::
0673 find(string_view key) const noexcept ->
0674     const_iterator
0675 {
0676     if(empty())
0677         return end();
0678     auto const p =
0679         detail::find_in_object(*this, key).first;
0680     if(p)
0681         return p;
0682     return end();
0683 }
0684
0685 bool
0686 object::
0687 contains(
0688     string_view key) const noexcept
0689 {
0690     if(empty())
0691         return false;
0692     return detail::find_in_object(*this, key).first
0693         != nullptr;
0694 }
0695
0696 value const*
0697 object::
0698 if_contains(
0699     string_view key) const noexcept
0700 {
0701     auto const it = find(key);
0702     if(it != end())
0703         return &it->value();
0704     return nullptr;
0705 }
0706
0707 value*
0708 object::
0709 if_contains(
0710     string_view key) noexcept
0711 {
0712     auto const it = find(key);
0713     if(it != end())
0714         return &it->value();
0715     return nullptr;
0716 }
0717
0718 //----------------------------------------------------------
0719 //
0720 // (private)
0721 //
0722 //----------------------------------------------------------
0723
0724 key_value_pair*
0725 object::
0726 insert_impl(
0727     pilfered<key_value_pair> p,
0728     std::size_t hash)
0729 {
0730     BOOST_ASSERT(
0731         capacity() > size());
0732     if(t_->is_small())
0733     {
0734         auto const pv = ::new(end())
0735             key_value_pair(p);
0736         ++t_->size;
0737         return pv;
0738     }
0739     auto& head =
0740         t_->bucket(hash);
0741     auto const pv = ::new(end())
0742         key_value_pair(p);
0743     access::next(*pv) = head;
0744     head = t_->size;
0745     ++t_->size;
0746     return pv;
0747 }
0748
0749 // allocate new table, copy elements there, and rehash them
0750 object::table*
0751 object::
0752 reserve_impl(std::size_t new_capacity)
0753 {
0754     BOOST_ASSERT(
0755         new_capacity > t_->capacity);
0756     auto t = table::allocate(
0757         growth(new_capacity),
0758             t_->salt, sp_);
0759     if(! empty())
0760         std::memcpy(
0761             static_cast<
0762                 void*>(&(*t)[0]),
0763             begin(),
0764             size() * sizeof(
0765                 key_value_pair));
0766     t->size = t_->size;
0767     std::swap(t_, t);
0768
0769     if(! t_->is_small())
0770     {
0771         // rebuild hash table,
0772         // without dup checks
0773         auto p = end();
0774         index_t i = t_->size;
0775         while(i-- > 0)
0776         {
0777             --p;
0778             auto& head =
0779                 t_->bucket(p->key());
0780             access::next(*p) = head;
0781             head = i;
0782         }
0783     }
0784
0785     return t;
0786 }
0787
0788 bool
0789 object::
0790 equal(object const& other) const noexcept
0791 {
0792     if(size() != other.size())
0793         return false;
0794     auto const end_ = other.end();
0795     for(auto e : *this)
0796     {
0797         auto it = other.find(e.key());
0798         if(it == end_)
0799             return false;
0800         if(it->value() != e.value())
0801             return false;
0802     }
0803     return true;
0804 }
0805
0806 std::size_t
0807 object::
0808 growth(
0809     std::size_t new_size) const
0810 {
0811     if(new_size > max_size())
0812     {
0813         BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
0814         detail::throw_system_error( error::object_too_large, &loc );
0815     }
0816     std::size_t const old = capacity();
0817     if(old > max_size() - old / 2)
0818         return new_size;
0819     std::size_t const g =
0820         old + old / 2; // 1.5x
0821     if(g < new_size)
0822         return new_size;
0823     return g;
0824 }
0825
0826 void
0827 object::
0828 remove(
0829     index_t& head,
0830     key_value_pair& v) noexcept
0831 {
0832     BOOST_ASSERT(! t_->is_small());
0833     auto const i = static_cast<
0834         index_t>(&v - begin());
0835     if(head == i)
0836     {
0837         head = access::next(v);
0838         return;
0839     }
0840     auto* pn =
0841         &access::next((*t_)[head]);
0842     while(*pn != i)
0843         pn = &access::next((*t_)[*pn]);
0844     *pn = access::next(v);
0845 }
0846
0847 void
0848 object::
0849 destroy() noexcept
0850 {
0851     BOOST_ASSERT(t_->capacity > 0);
0852     BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
0853     destroy(begin(), end());
0854     table::deallocate(t_, sp_);
0855 }
0856
0857 void
0858 object::
0859 destroy(
0860     key_value_pair* first,
0861     key_value_pair* last) noexcept
0862 {
0863     BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
0864     while(last != first)
0865         (--last)->~key_value_pair();
0866 }
0867
0868 template<class FS, class FB>
0869 auto
0870 object::
0871 do_erase(
0872     const_iterator pos,
0873     FS small_reloc,
0874     FB big_reloc) noexcept
0875     -> iterator
0876 {
0877     auto p = begin() + (pos - begin());
0878     if(t_->is_small())
0879     {
0880         p->~value_type();
0881         --t_->size;
0882         if(p != end())
0883         {
0884             small_reloc(p);
0885         }
0886         return p;
0887     }
0888     remove(t_->bucket(p->key()), *p);
0889     p->~value_type();
0890     --t_->size;
0891     if(p != end())
0892     {
0893         big_reloc(p);
0894     }
0895     return p;
0896 }
0897
0898 void
0899 object::
0900 reindex_relocate(
0901     key_value_pair* src,
0902     key_value_pair* dst) noexcept
0903 {
0904     BOOST_ASSERT(! t_->is_small());
0905     auto& head = t_->bucket(src->key());
0906     remove(head, *src);
0907     // the casts silence warnings
0908     std::memcpy(
0909         static_cast<void*>(dst),
0910         static_cast<void const*>(src),
0911         sizeof(*dst));
0912     access::next(*dst) = head;
0913     head = static_cast<
0914         index_t>(dst - begin());
0915 }
0916
0917 } // namespace json
0918 } // namespace boost
0919
0920 //----------------------------------------------------------
0921 //
0922 // std::hash specialization
0923 //
0924 //----------------------------------------------------------
0925
0926 std::size_t
0927 std::hash<::boost::json::object>::operator()(
0928     ::boost::json::object const& jo) const noexcept
0929 {
0930     return ::boost::hash< ::boost::json::object >()( jo );
0931 }
0932
0933 //----------------------------------------------------------
0934
0935
0936 #endif