//

// 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_HPP

#define BOOST_JSON_IMPL_OBJECT_HPP

#include <boost/json/value.hpp>

#include <iterator>

#include <cmath>

#include <type_traits>

#include <utility>

namespace boost {

namespace json {

namespace detail {

// Objects with size less than or equal

// to this number will use a linear search

// instead of the more expensive hash function.

static

constexpr

std::size_t

small_object_size_ = 18;

BOOST_STATIC_ASSERT(

    small_object_size_ <

    BOOST_JSON_MAX_STRUCTURED_SIZE);

} // detail

//----------------------------------------------------------

struct alignas(key_value_pair)

    object::table

{

    std::uint32_t size = 0;

    std::uint32_t capacity = 0;

    std::uintptr_t salt = 0;

#if defined(_MSC_VER) && BOOST_JSON_ARCH == 32

    // VFALCO If we make key_value_pair smaller,

    //        then we might want to revisit this

    //        padding.

    BOOST_STATIC_ASSERT(

        sizeof(key_value_pair) == 32);

    char pad[4] = {}; // silence warnings

#endif

    constexpr table();

    // returns true if we use a linear

    // search instead of the hash table.

    bool is_small() const noexcept

    {

        return capacity <=

            detail::small_object_size_;

    }

    key_value_pair&

    operator[](

        std::size_t pos) noexcept

    {

        return reinterpret_cast<

            key_value_pair*>(

                this + 1)[pos];

    }

    // VFALCO This is exported for tests

    BOOST_JSON_DECL

    std::size_t

    digest(string_view key) const noexcept;

    inline

    index_t&

    bucket(std::size_t hash) noexcept;

    inline

    index_t&

    bucket(string_view key) noexcept;

    inline

    void

    clear() noexcept;

    static

    inline

    table*

    allocate(

        std::size_t capacity,

        std::uintptr_t salt,

        storage_ptr const& sp);

    static

    void

    deallocate(

        table* p,

        storage_ptr const& sp) noexcept

    {

        if(p->capacity == 0)

            return;

        if(! p->is_small())

            sp->deallocate(p,

                sizeof(table) + p->capacity * (

                    sizeof(key_value_pair) +

                    sizeof(index_t)));

        else

            sp->deallocate(p,

                sizeof(table) + p->capacity *

                    sizeof(key_value_pair));

    }

};

//----------------------------------------------------------

class object::revert_construct

{

    object* obj_;

    BOOST_JSON_DECL

    void

    destroy() noexcept;

public:

    explicit

    revert_construct(

        object& obj) noexcept

        : obj_(&obj)

    {

    }

    ~revert_construct()

    {

        if(! obj_)

            return;

        destroy();

    }

    void

    commit() noexcept

    {

        obj_ = nullptr;

    }

};

//----------------------------------------------------------

class object::revert_insert

{

    object* obj_;

    table* t_ = nullptr;

    std::size_t size_;

    BOOST_JSON_DECL

    void

    destroy() noexcept;

public:

    explicit

    revert_insert(

        object& obj,

        std::size_t capacity)

        : obj_(&obj)

        , size_(obj_->size())

    {

        if( capacity > obj_->capacity() )

            t_ = obj_->reserve_impl(capacity);

    }

    ~revert_insert()

    {

        if(! obj_)

            return;

        destroy();

        if( t_ )

        {

            table::deallocate( obj_->t_, obj_->sp_ );

            obj_->t_ = t_;

        }

        else

        {

            obj_->t_->size = static_cast<index_t>(size_);

        }

    }

    void

    commit() noexcept

    {

        BOOST_ASSERT(obj_);

        if( t_ )

            table::deallocate( t_, obj_->sp_ );

        obj_ = nullptr;

    }

};

//----------------------------------------------------------

//

// Iterators

//

//----------------------------------------------------------

auto

object::

begin() noexcept ->

    iterator

{

    return &(*t_)[0];

}

auto

object::

begin() const noexcept ->

    const_iterator

{

    return &(*t_)[0];

}

auto

object::

cbegin() const noexcept ->

    const_iterator

{

    return &(*t_)[0];

}

auto

object::

end() noexcept ->

    iterator

{

    return &(*t_)[t_->size];

}

auto

object::

end() const noexcept ->

    const_iterator

{

    return &(*t_)[t_->size];

}

auto

object::

cend() const noexcept ->

    const_iterator

{

    return &(*t_)[t_->size];

}

auto

object::

rbegin() noexcept ->

    reverse_iterator

{

    return reverse_iterator(end());

}

auto

object::

rbegin() const noexcept ->

    const_reverse_iterator

{

    return const_reverse_iterator(end());

}

auto

object::

crbegin() const noexcept ->

    const_reverse_iterator

{

    return const_reverse_iterator(end());

}

auto

object::

rend() noexcept ->

    reverse_iterator

{

    return reverse_iterator(begin());

}

auto

object::

rend() const noexcept ->

    const_reverse_iterator

{

    return const_reverse_iterator(begin());

}

auto

object::

crend() const noexcept ->

    const_reverse_iterator

{

    return const_reverse_iterator(begin());

}

//----------------------------------------------------------

//

// Capacity

//

//----------------------------------------------------------

bool

object::

empty() const noexcept

{

    return t_->size == 0;

}

auto

object::

size() const noexcept ->

    std::size_t

{

    return t_->size;

}

constexpr

std::size_t

object::

max_size() noexcept

{

    // max_size depends on the address model

    using min = std::integral_constant<std::size_t,

        (std::size_t(-1) - sizeof(table)) /

            (sizeof(key_value_pair) + sizeof(index_t))>;

    return min::value < BOOST_JSON_MAX_STRUCTURED_SIZE ?

        min::value : BOOST_JSON_MAX_STRUCTURED_SIZE;

}

auto

object::

capacity() const noexcept ->

    std::size_t

{

    return t_->capacity;

}

void

object::

reserve(std::size_t new_capacity)

{

    if( new_capacity <= capacity() )

        return;

    table* const old_table = reserve_impl(new_capacity);

    table::deallocate( old_table, sp_ );

}

//----------------------------------------------------------

//

// Lookup

//

//----------------------------------------------------------

value&

object::

at(string_view key, source_location const& loc) &

{

    auto const& self = *this;

    return const_cast< value& >( self.at(key, loc) );

}

value&&

object::

at(string_view key, source_location const& loc) &&

{

    return std::move( at(key, loc) );

}

//----------------------------------------------------------

template<class P, class>

auto

object::

insert(P&& p) ->

    std::pair<iterator, bool>

{

    key_value_pair v(

        std::forward<P>(p), sp_);

    return emplace_impl( v.key(), pilfer(v) );

}

template<class M>

auto

object::

insert_or_assign(

    string_view key, M&& m) ->

        std::pair<iterator, bool>

{

    std::pair<iterator, bool> result = emplace_impl(

        key, key, static_cast<M&&>(m) );

    if( !result.second )

    {

        value(static_cast<M>(m), sp_).swap(

            result.first->value());

    }

    return result;

}

template<class Arg>

auto

object::

emplace(

    string_view key,

    Arg&& arg) ->

        std::pair<iterator, bool>

{

    return emplace_impl( key, key, static_cast<Arg&&>(arg) );

}

Unexecuted instantiation: std::__1::pair<boost::json::key_value_pair*, bool> boost::json::object::emplace<decltype(nullptr)>(boost::core::basic_string_view<char>, decltype(nullptr)&&)

Unexecuted instantiation: std::__1::pair<boost::json::key_value_pair*, bool> boost::json::object::emplace<boost::json::value>(boost::core::basic_string_view<char>, boost::json::value&&)

//----------------------------------------------------------

//

// (private)

//

//----------------------------------------------------------

template<class InputIt>

void

object::

construct(

    InputIt first,

    InputIt last,

    std::size_t min_capacity,

    std::input_iterator_tag)

{

    reserve(min_capacity);

    revert_construct r(*this);

    while(first != last)

    {

        insert(*first);

        ++first;

    }

    r.commit();

}

template<class InputIt>

void

object::

construct(

    InputIt first,

    InputIt last,

    std::size_t min_capacity,

    std::forward_iterator_tag)

{

    auto n = static_cast<

        std::size_t>(std::distance(

            first, last));

    if( n < min_capacity)

        n = min_capacity;

    reserve(n);

    revert_construct r(*this);

    while(first != last)

    {

        insert(*first);

        ++first;

    }

    r.commit();

}

template<class InputIt>

void

object::

insert(

    InputIt first,

    InputIt last,

    std::input_iterator_tag)

{

    // Since input iterators cannot be rewound,

    // we keep inserted elements on an exception.

    //

    while(first != last)

    {

        insert(*first);

        ++first;

    }

}

template<class InputIt>

void

object::

insert(

    InputIt first,

    InputIt last,

    std::forward_iterator_tag)

{

    auto const n =

        static_cast<std::size_t>(

            std::distance(first, last));

    auto const n0 = size();

    if(n > 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 + n );

    while(first != last)

    {

        insert(*first);

        ++first;

    }

    r.commit();

}

template< class... Args >

std::pair<object::iterator, bool>

object::

emplace_impl( string_view key, Args&& ... args )

{

    std::pair<iterator, std::size_t> search_result(nullptr, 0);

    if( !empty() )

    {

        search_result = detail::find_in_object(*this, key);

        if( search_result.first )

            return { search_result.first, false };

    }

    // we create the new value before reserving, in case it is a reference to

    // a subobject of the current object

    key_value_pair kv( static_cast<Args&&>(args)..., sp_ );

    // the key might get deallocated too

    key = kv.key();

    std::size_t const old_capacity = capacity();

    reserve(size() + 1);

    if( (empty() && capacity() > detail::small_object_size_)

            || (capacity() != old_capacity) )

        search_result.second = detail::digest(

            key.begin(), key.end(), t_->salt);

    BOOST_ASSERT(

        t_->is_small() ||

        (search_result.second ==

            detail::digest(key.begin(), key.end(), t_->salt)) );

    return { insert_impl(pilfer(kv), search_result.second), true };

}

Unexecuted instantiation: std::__1::pair<boost::json::key_value_pair*, bool> boost::json::object::emplace_impl<boost::core::basic_string_view<char>&, decltype(nullptr)>(boost::core::basic_string_view<char>, boost::core::basic_string_view<char>&, decltype(nullptr)&&)

Unexecuted instantiation: std::__1::pair<boost::json::key_value_pair*, bool> boost::json::object::emplace_impl<boost::core::basic_string_view<char>&, boost::json::value>(boost::core::basic_string_view<char>, boost::core::basic_string_view<char>&, boost::json::value&&)

//----------------------------------------------------------

namespace detail {

unchecked_object::

~unchecked_object()

{

    if(! data_)

        return;

    if(sp_.is_not_shared_and_deallocate_is_trivial())

        return;

    value* p = data_;

    while(size_--)

    {

        p[0].~value();

        p[1].~value();

        p += 2;

    }

}

} // detail

} // namespace json

} // namespace boost

#endif