EIC code displayed by LXR master/​include/​boost/​json/​impl/​object.ipp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-30 09:44:42

 //
 // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
 //
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 //
 // Official repository: https://github.com/boostorg/json
 //
 
 #ifndef BOOST_JSON_IMPL_OBJECT_IPP
 #define BOOST_JSON_IMPL_OBJECT_IPP
 
 #include <boost/container_hash/hash.hpp>
 #include <boost/json/object.hpp>
 #include <boost/json/detail/digest.hpp>
 #include <boost/json/detail/except.hpp>
 #include <algorithm>
 #include <cmath>
 #include <cstdlib>
 #include <cstring>
 #include <new>
 #include <stdexcept>
 #include <type_traits>
 
 namespace boost {
 namespace json {
 namespace detail {
 
 template<class CharRange>
 std::pair<key_value_pair*, std::size_t>
 find_in_object(
     object const& obj,
     CharRange key) noexcept
 {
     BOOST_ASSERT(obj.t_->capacity > 0);
     if(obj.t_->is_small())
     {
         auto it = &(*obj.t_)[0];
         auto const last =
             &(*obj.t_)[obj.t_->size];
         for(;it != last; ++it)
             if( key == it->key() )
                 return { it, 0 };
         return { nullptr, 0 };
     }
     std::pair<
         key_value_pair*,
         std::size_t> result;
     BOOST_ASSERT(obj.t_->salt != 0);
     result.second = detail::digest(key.begin(), key.end(), obj.t_->salt);
     auto i = obj.t_->bucket(
         result.second);
     while(i != object::null_index_)
     {
         auto& v = (*obj.t_)[i];
         if( key == v.key() )
         {
             result.first = &v;
             return result;
         }
         i = access::next(v);
     }
     result.first = nullptr;
     return result;
 }
 
 
 template
 std::pair<key_value_pair*, std::size_t>
 find_in_object<string_view>(
     object const& obj,
     string_view key) noexcept;
 
 } // namespace detail
 
 //----------------------------------------------------------
 
 constexpr object::table::table() = default;
 
 // empty objects point here
 BOOST_JSON_REQUIRE_CONST_INIT
 object::table object::empty_;
 
 std::size_t
 object::table::
 digest(string_view key) const noexcept
 {
     BOOST_ASSERT(salt != 0);
     return detail::digest(
         key.begin(), key.end(), salt);
 }
 
 auto
 object::table::
 bucket(std::size_t hash) noexcept ->
     index_t&
 {
     return reinterpret_cast<
         index_t*>(&(*this)[capacity])[
             hash % capacity];
 }
 
 auto
 object::table::
 bucket(string_view key) noexcept ->
     index_t&
 {
     return bucket(digest(key));
 }
 
 void
 object::table::
 clear() noexcept
 {
     BOOST_ASSERT(! is_small());
     // initialize buckets
     std::memset(
         reinterpret_cast<index_t*>(
             &(*this)[capacity]),
         0xff, // null_index_
         capacity * sizeof(index_t));
 }
 
 object::table*
 object::table::
 allocate(
     std::size_t capacity,
     std::uintptr_t salt,
     storage_ptr const& sp)
 {
     BOOST_STATIC_ASSERT(
         alignof(key_value_pair) >=
         alignof(index_t));
     BOOST_ASSERT(capacity > 0);
     BOOST_ASSERT(capacity <= max_size());
     table* p;
     if(capacity <= detail::small_object_size_)
     {
         p = reinterpret_cast<
             table*>(sp->allocate(
                 sizeof(table) + capacity *
                     sizeof(key_value_pair)));
         p->capacity = static_cast<
             std::uint32_t>(capacity);
     }
     else
     {
         p = reinterpret_cast<
             table*>(sp->allocate(
                 sizeof(table) + capacity * (
                     sizeof(key_value_pair) +
                     sizeof(index_t))));
         p->capacity = static_cast<
             std::uint32_t>(capacity);
         p->clear();
     }
     if(salt)
     {
         p->salt = salt;
     }
     else
     {
         // VFALCO This would be better if it
         //        was random, but maybe this
         //        is good enough.
         p->salt = reinterpret_cast<
             std::uintptr_t>(p);
     }
     return p;
 }
 
 //----------------------------------------------------------
 
 void
 object::
 revert_construct::
 destroy() noexcept
 {
     obj_->destroy();
 }
 
 //----------------------------------------------------------
 
 void
 object::
 revert_insert::
 destroy() noexcept
 {
     obj_->destroy(
         &(*obj_->t_)[size_],
         obj_->end());
 }
 
 //----------------------------------------------------------
 //
 // Construction
 //
 //----------------------------------------------------------
 
 object::
 object(detail::unchecked_object&& uo)
     : sp_(uo.storage())
 {
     if(uo.size() == 0)
     {
         t_ = &empty_;
         return;
     }
     // should already be checked
     BOOST_ASSERT(
         uo.size() <= max_size());
     t_ = table::allocate(
         uo.size(), 0, sp_);
 
     // insert all elements, keeping
     // the last of any duplicate keys.
     auto dest = begin();
     auto src = uo.release();
     auto const end = src + 2 * uo.size();
     if(t_->is_small())
     {
         t_->size = 0;
         while(src != end)
         {
             access::construct_key_value_pair(
                 dest, pilfer(src[0]), pilfer(src[1]));
             src += 2;
             auto result = detail::find_in_object(*this, dest->key());
             if(! result.first)
             {
                 ++dest;
                 ++t_->size;
                 continue;
             }
             // handle duplicate
             auto& v = *result.first;
             // don't bother to check if
             // storage deallocate is trivial
             v.~key_value_pair();
             // trivial relocate
             std::memcpy(
                 static_cast<void*>(&v),
                     dest, sizeof(v));
         }
         return;
     }
     while(src != end)
     {
         access::construct_key_value_pair(
             dest, pilfer(src[0]), pilfer(src[1]));
         src += 2;
         auto& head = t_->bucket(dest->key());
         auto i = head;
         for(;;)
         {
             if(i == null_index_)
             {
                 // end of bucket
                 access::next(
                     *dest) = head;
                 head = static_cast<index_t>(
                     dest - begin());
                 ++dest;
                 break;
             }
             auto& v = (*t_)[i];
             if(v.key() != dest->key())
             {
                 i = access::next(v);
                 continue;
             }
 
             // handle duplicate
             access::next(*dest) =
                 access::next(v);
             // don't bother to check if
             // storage deallocate is trivial
             v.~key_value_pair();
             // trivial relocate
             std::memcpy(
                 static_cast<void*>(&v),
                     dest, sizeof(v));
             break;
         }
     }
     t_->size = static_cast<
         index_t>(dest - begin());
 }
 
 object::
 ~object() noexcept
 {
     if(sp_.is_not_shared_and_deallocate_is_trivial())
         return;
     if(t_->capacity == 0)
         return;
     destroy();
 }
 
 object::
 object(
     std::size_t min_capacity,
     storage_ptr sp)
     : sp_(std::move(sp))
     , t_(&empty_)
 {
     reserve(min_capacity);
 }
 
 object::
 object(object&& other) noexcept
     : sp_(other.sp_)
     , t_(detail::exchange(
         other.t_, &empty_))
 {
 }
 
 object::
 object(
     object&& other,
     storage_ptr sp)
     : sp_(std::move(sp))
 {
     if(*sp_ == *other.sp_)
     {
         t_ = detail::exchange(
             other.t_, &empty_);
         return;
     }
 
     t_ = &empty_;
     object(other, sp_).swap(*this);
 }
 
 object::
 object(
     object const& other,
     storage_ptr sp)
     : sp_(std::move(sp))
     , t_(&empty_)
 {
     reserve(other.size());
     revert_construct r(*this);
     if(t_->is_small())
     {
         for(auto const& v : other)
         {
             ::new(end())
                 key_value_pair(v, sp_);
             ++t_->size;
         }
         r.commit();
         return;
     }
     for(auto const& v : other)
     {
         // skip duplicate checking
         auto& head =
             t_->bucket(v.key());
         auto pv = ::new(end())
             key_value_pair(v, sp_);
         access::next(*pv) = head;
         head = t_->size;
         ++t_->size;
     }
     r.commit();
 }
 
 object::
 object(
     std::initializer_list<std::pair<
         string_view, value_ref>> init,
     std::size_t min_capacity,
     storage_ptr sp)
     : sp_(std::move(sp))
     , t_(&empty_)
 {
     if( min_capacity < init.size())
         min_capacity = init.size();
     reserve(min_capacity);
     revert_construct r(*this);
     insert(init);
     r.commit();
 }
 
 //----------------------------------------------------------
 //
 // Assignment
 //
 //----------------------------------------------------------
 
 object&
 object::
 operator=(object const& other)
 {
     object tmp(other, sp_);
     this->~object();
     ::new(this) object(pilfer(tmp));
     return *this;
 }
 
 object&
 object::
 operator=(object&& other)
 {
     object tmp(std::move(other), sp_);
     this->~object();
     ::new(this) object(pilfer(tmp));
     return *this;
 }
 
 object&
 object::
 operator=(
     std::initializer_list<std::pair<
         string_view, value_ref>> init)
 {
     object tmp(init, sp_);
     this->~object();
     ::new(this) object(pilfer(tmp));
     return *this;
 }
 
 //----------------------------------------------------------
 //
 // Modifiers
 //
 //----------------------------------------------------------
 
 void
 object::
 clear() noexcept
 {
     if(empty())
         return;
     if(! sp_.is_not_shared_and_deallocate_is_trivial())
         destroy(begin(), end());
     if(! t_->is_small())
         t_->clear();
     t_->size = 0;
 }
 
 void
 object::
 insert(
     std::initializer_list<std::pair<
         string_view, value_ref>> init)
 {
     auto const n0 = size();
     if(init.size() > max_size() - n0)
     {
         BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
         detail::throw_system_error( error::object_too_large, &loc );
     }
     revert_insert r( *this, n0 + init.size() );
     if(t_->is_small())
     {
         for(auto& iv : init)
         {
             auto result =
                 detail::find_in_object(*this, iv.first);
             if(result.first)
             {
                 // ignore duplicate
                 continue;
             }
             ::new(end()) key_value_pair(
                 iv.first,
                 iv.second.make_value(sp_));
             ++t_->size;
         }
         r.commit();
         return;
     }
     for(auto& iv : init)
     {
         auto& head = t_->bucket(iv.first);
         auto i = head;
         for(;;)
         {
             if(i == null_index_)
             {
                 // VFALCO value_ref should construct
                 // a key_value_pair using placement
                 auto& v = *::new(end())
                     key_value_pair(
                         iv.first,
                         iv.second.make_value(sp_));
                 access::next(v) = head;
                 head = static_cast<index_t>(
                     t_->size);
                 ++t_->size;
                 break;
             }
             auto& v = (*t_)[i];
             if(v.key() == iv.first)
             {
                 // ignore duplicate
                 break;
             }
             i = access::next(v);
         }
     }
     r.commit();
 }
 
 auto
 object::
 erase(const_iterator pos) noexcept ->
     iterator
 {
     return do_erase(pos,
         [this](iterator p) {
             // the casts silence warnings
             std::memcpy(
                 static_cast<void*>(p),
                 static_cast<void const*>(end()),
                 sizeof(*p));
         },
         [this](iterator p) {
             reindex_relocate(end(), p);
         });
 }
 
 auto
 object::
 erase(string_view key) noexcept ->
     std::size_t
 {
     auto it = find(key);
     if(it == end())
         return 0;
     erase(it);
     return 1;
 }
 
 auto
 object::
 stable_erase(const_iterator pos) noexcept ->
     iterator
 {
     return do_erase(pos,
         [this](iterator p) {
             // the casts silence warnings
             std::memmove(
                 static_cast<void*>(p),
                 static_cast<void const*>(p + 1),
                 sizeof(*p) * (end() - p));
         },
         [this](iterator p) {
             for (; p != end(); ++p)
             {
                 reindex_relocate(p + 1, p);
             }
         });
 }
 
 auto
 object::
 stable_erase(string_view key) noexcept ->
     std::size_t
 {
     auto it = find(key);
     if(it == end())
         return 0;
     stable_erase(it);
     return 1;
 }
 
 void
 object::
 swap(object& other)
 {
     if(*sp_ == *other.sp_)
     {
         t_ = detail::exchange(
             other.t_, t_);
         return;
     }
     object temp1(
         std::move(*this),
         other.storage());
     object temp2(
         std::move(other),
         this->storage());
     other.~object();
     ::new(&other) object(pilfer(temp1));
     this->~object();
     ::new(this) object(pilfer(temp2));
 }
 
 //----------------------------------------------------------
 //
 // Lookup
 //
 //----------------------------------------------------------
 
 auto
 object::
 operator[](string_view key) ->
     value&
 {
     auto const result =
         emplace(key, nullptr);
     return result.first->value();
 }
 
 auto
 object::
 count(string_view key) const noexcept ->
     std::size_t
 {
     if(find(key) == end())
         return 0;
     return 1;
 }
 
 auto
 object::
 find(string_view key) noexcept ->
     iterator
 {
     if(empty())
         return end();
     auto const p =
         detail::find_in_object(*this, key).first;
     if(p)
         return p;
     return end();
 }
 
 auto
 object::
 find(string_view key) const noexcept ->
     const_iterator
 {
     if(empty())
         return end();
     auto const p =
         detail::find_in_object(*this, key).first;
     if(p)
         return p;
     return end();
 }
 
 bool
 object::
 contains(
     string_view key) const noexcept
 {
     if(empty())
         return false;
     return detail::find_in_object(*this, key).first
         != nullptr;
 }
 
 value const*
 object::
 if_contains(
     string_view key) const noexcept
 {
     auto const it = find(key);
     if(it != end())
         return &it->value();
     return nullptr;
 }
 
 value*
 object::
 if_contains(
     string_view key) noexcept
 {
     auto const it = find(key);
     if(it != end())
         return &it->value();
     return nullptr;
 }
 
 //----------------------------------------------------------
 //
 // (private)
 //
 //----------------------------------------------------------
 
 key_value_pair*
 object::
 insert_impl(
     pilfered<key_value_pair> p,
     std::size_t hash)
 {
     BOOST_ASSERT(
         capacity() > size());
     if(t_->is_small())
     {
         auto const pv = ::new(end())
             key_value_pair(p);
         ++t_->size;
         return pv;
     }
     auto& head =
         t_->bucket(hash);
     auto const pv = ::new(end())
         key_value_pair(p);
     access::next(*pv) = head;
     head = t_->size;
     ++t_->size;
     return pv;
 }
 
 // allocate new table, copy elements there, and rehash them
 object::table*
 object::
 reserve_impl(std::size_t new_capacity)
 {
     BOOST_ASSERT(
         new_capacity > t_->capacity);
     auto t = table::allocate(
         growth(new_capacity),
             t_->salt, sp_);
     if(! empty())
         std::memcpy(
             static_cast<
                 void*>(&(*t)[0]),
             begin(),
             size() * sizeof(
                 key_value_pair));
     t->size = t_->size;
     std::swap(t_, t);
 
     if(! t_->is_small())
     {
         // rebuild hash table,
         // without dup checks
         auto p = end();
         index_t i = t_->size;
         while(i-- > 0)
         {
             --p;
             auto& head =
                 t_->bucket(p->key());
             access::next(*p) = head;
             head = i;
         }
     }
 
     return t;
 }
 
 bool
 object::
 equal(object const& other) const noexcept
 {
     if(size() != other.size())
         return false;
     auto const end_ = other.end();
     for(auto e : *this)
     {
         auto it = other.find(e.key());
         if(it == end_)
             return false;
         if(it->value() != e.value())
             return false;
     }
     return true;
 }
 
 std::size_t
 object::
 growth(
     std::size_t new_size) const
 {
     if(new_size > max_size())
     {
         BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
         detail::throw_system_error( error::object_too_large, &loc );
     }
     std::size_t const old = capacity();
     if(old > max_size() - old / 2)
         return new_size;
     std::size_t const g =
         old + old / 2; // 1.5x
     if(g < new_size)
         return new_size;
     return g;
 }
 
 void
 object::
 remove(
     index_t& head,
     key_value_pair& v) noexcept
 {
     BOOST_ASSERT(! t_->is_small());
     auto const i = static_cast<
         index_t>(&v - begin());
     if(head == i)
     {
         head = access::next(v);
         return;
     }
     auto* pn =
         &access::next((*t_)[head]);
     while(*pn != i)
         pn = &access::next((*t_)[*pn]);
     *pn = access::next(v);
 }
 
 void
 object::
 destroy() noexcept
 {
     BOOST_ASSERT(t_->capacity > 0);
     BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
     destroy(begin(), end());
     table::deallocate(t_, sp_);
 }
 
 void
 object::
 destroy(
     key_value_pair* first,
     key_value_pair* last) noexcept
 {
     BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
     while(last != first)
         (--last)->~key_value_pair();
 }
 
 template<class FS, class FB>
 auto
 object::
 do_erase(
     const_iterator pos,
     FS small_reloc,
     FB big_reloc) noexcept
     -> iterator
 {
     auto p = begin() + (pos - begin());
     if(t_->is_small())
     {
         p->~value_type();
         --t_->size;
         if(p != end())
         {
             small_reloc(p);
         }
         return p;
     }
     remove(t_->bucket(p->key()), *p);
     p->~value_type();
     --t_->size;
     if(p != end())
     {
         big_reloc(p);
     }
     return p;
 }
 
 void
 object::
 reindex_relocate(
     key_value_pair* src,
     key_value_pair* dst) noexcept
 {
     BOOST_ASSERT(! t_->is_small());
     auto& head = t_->bucket(src->key());
     remove(head, *src);
     // the casts silence warnings
     std::memcpy(
         static_cast<void*>(dst),
         static_cast<void const*>(src),
         sizeof(*dst));
     access::next(*dst) = head;
     head = static_cast<
         index_t>(dst - begin());
 }
 
 } // namespace json
 } // namespace boost
 
 //----------------------------------------------------------
 //
 // std::hash specialization
 //
 //----------------------------------------------------------
 
 std::size_t
 std::hash<::boost::json::object>::operator()(
     ::boost::json::object const& jo) const noexcept
 {
     return ::boost::hash< ::boost::json::object >()( jo );
 }
 
 //----------------------------------------------------------
 
 
 #endif

This page was automatically generated by the 2.3.7 LXR engine. The LXR team