include/nlohmann/detail/view/lookup.hpp

//     __ _____ _____ _____
//  __|  |   __|     |   | |  JSON for Modern C++
// |  |  |__   |  |  | | | |  version 3.12.0
// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
//
// SPDX-FileCopyrightText: 2013-2026 Niels Lohmann <https://nlohmann.me>
// SPDX-License-Identifier: MIT

#pragma once

#include <cstddef> // size_t
#include <cstdint> // uint16_t, uint32_t, uint64_t
#include <cstring> // memcmp, memcpy
#include <limits> // numeric_limits
#include <type_traits> // integral_constant, is_integral, is_same

#include <nlohmann/json.hpp>
#include <nlohmann/detail/view/document_data.hpp>
#include <nlohmann/detail/view/macro_scope.hpp>
#include <nlohmann/detail/view/node.hpp>
#include <nlohmann/detail/view/object_index.hpp>

NLOHMANN_JSON_NAMESPACE_BEGIN
namespace detail
{
namespace view
{

/// equality test for strings of one length n <= 16: two overlapping loads per
/// string (the first and the last 8, 4, or 2 bytes) replace a memcmp, and no
/// byte outside [s, s + n) is read
class short_key
{
  public:
    short_key(const unsigned char* k, std::size_t n) noexcept
        : m_n(n)
    {
        load(k, m_a, m_b);
    }

    NLOHMANN_VIEW_ALWAYS_INLINE bool matches(const unsigned char* s) const noexcept
    {
        std::uint64_t a = 0;
        std::uint64_t b = 0;
        load(s, a, b);
        return a == m_a && b == m_b;
    }

  private:
    template<typename T>
    static NLOHMANN_VIEW_ALWAYS_INLINE std::uint64_t load_word(const unsigned char* s) noexcept
    {
        T w = 0;
        std::memcpy(&w, s, sizeof(T));
        return w;
    }

    NLOHMANN_VIEW_ALWAYS_INLINE void load(const unsigned char* s, std::uint64_t& a, std::uint64_t& b) const noexcept
    {
        if (m_n >= 8)
        {
            a = load_word<std::uint64_t>(s);
            b = load_word<std::uint64_t>(s + m_n - 8);
        }
        else if (m_n >= 4)
        {
            a = load_word<std::uint32_t>(s);
            b = load_word<std::uint32_t>(s + m_n - 4);
        }
        else if (m_n >= 2)
        {
            a = load_word<std::uint16_t>(s);
            b = load_word<std::uint16_t>(s + m_n - 2);
        }
        else
        {
            a = m_n == 1 ? s[0] : 0;
            b = 0;
        }
    }

    std::size_t m_n;
    std::uint64_t m_a = 0;
    std::uint64_t m_b = 0;
};

/// the key node of the first member of an object with the given key, or
/// nullptr (the search stops at the first match; materialize() and parse()
/// keep the last value of a duplicate key instead); most keys are rejected by
/// their length, from the index alone
template<bool Editable>
const node* find_member(const document_data& d, const node* object, const char* key, std::size_t n) noexcept
{
    using nav = navigation<Editable>;
    if (NLOHMANN_VIEW_UNLIKELY(object->extra != 0) && (!nav::editable() || (object->flags & node_flags::moved) == 0))
    {
        return find_indexed(d, object, key, n); // a large object (whose members have not been edited)
    }
    const node* const end = nav::end(d, object);
    const auto* const k = reinterpret_cast<const unsigned char*>(key); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
    if (NLOHMANN_VIEW_LIKELY(n <= 16))
    {
        const short_key probe(k, n);
        for (const node* m = nav::first(d, object); m != end; m = document_data::after(m + 1))
        {
            if (m->len == n && probe.matches(reinterpret_cast<const unsigned char*>(d.str(*m)))) // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast)
            {
                return m;
            }
        }
        return nullptr;
    }
    for (const node* m = nav::first(d, object); m != end; m = document_data::after(m + 1))
    {
        if (d.key_equals(*m, key, n))
        {
            return m;
        }
    }
    return nullptr;
}

/// the number of members of an object with this key (duplicates included)
template<bool Editable>
std::size_t count_members(const document_data& d, const node* object, const char* key, std::size_t n) noexcept
{
    using nav = navigation<Editable>;
    std::size_t result = 0;
    const node* const end = nav::end(d, object);
    for (const node* m = nav::first(d, object); m != end; m = document_data::after(m + 1))
    {
        if (d.key_equals(*m, key, n))
        {
            ++result;
        }
    }
    return result;
}

/// whether an integer type is accepted as an array index by the view's
/// operator[] and at(): every integer type but bool and size_t, which has its
/// own overload
template<typename T>
struct is_index_type : std::integral_constant < bool,
    std::is_integral<T>::value && !std::is_same<T, bool>::value && !std::is_same<T, std::size_t>::value >
{};

/// an integer as an index: negative values, and values that do not fit a
/// size_t, map to the largest size_t (out of range for every array)
template<typename SizeType, typename IntegerType>
SizeType to_index(IntegerType idx) noexcept
{
    const IntegerType zero = 0;
    const auto result = static_cast<SizeType>(idx); // NOLINT(bugprone-signed-char-misuse,cert-str34-c): negative values are mapped below
    return (idx < zero || static_cast<IntegerType>(result) != idx) ? (std::numeric_limits<SizeType>::max)() : result;
}

/// the entry of the element of an array at an index below its size (a link
/// in the moved sequences of editable documents)
template<bool Editable>
const node* element_at(const document_data& d, const node* array, std::size_t idx) noexcept
{
    using nav = navigation<Editable>;
    const node* e = nav::first(d, array);
    if (nav::editable() && (array->flags & node_flags::moved) != 0 && d.edits->moved_cap[array->off] != 0)
    {
        return e + idx; // a growable block: one link per element
    }
    if (array->next == array->len + 1u && (!nav::editable() || (array->flags & node_flags::moved) == 0))
    {
        return e + idx; // no element has a subtree: the elements are the nodes after the array
    }
    for (std::size_t i = 0; i < idx; ++i)
    {
        e = document_data::after(e);
    }
    return e;
}

/// the entry of the last element of a non-empty array, or the key of the
/// last member of a non-empty object
template<bool Editable>
const node* last_child(const document_data& d, const node* container) noexcept
{
    const std::size_t value_offset = container->kind == node_kind::object ? 1 : 0;
    const node* const end = navigation<Editable>::end(d, container);
    const node* last = navigation<Editable>::first(d, container);
    if (value_offset == 0 && container->next == container->len + 1u && (!navigation<Editable>::editable() || (container->flags & node_flags::moved) == 0))
    {
        return last + (container->len - 1u); // an array without subtrees: the elements are the nodes after it
    }
    for (const node* c = document_data::after(last + value_offset); c != end; c = document_data::after(c + value_offset))
    {
        last = c;
    }
    return last;
}

}  // namespace view
}  // namespace detail
NLOHMANN_JSON_NAMESPACE_END