types.hpp

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

// SPDX-FileCopyrightText: 2021 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT

#pragma once

#include "../global.hpp"
#include "./types_util.hpp"
#include "./delayed_delete_vector.hpp"

#include <algorithm>
#include <cassert>
#include <memory>
#include <cstdint>
#include <vector>
#include <sstream>

#if defined(MDDS_UNIT_TEST) || defined(MDDS_MULTI_TYPE_VECTOR_DEBUG)
#include <iostream>
#endif

namespace mdds { namespace mtv {

using element_t = int;

constexpr element_t element_type_empty = -1;

constexpr element_t element_type_reserved_start = 0;
constexpr element_t element_type_reserved_end = 49;

constexpr element_t element_type_user_start = 50;

enum class lu_factor_t : int
{
    none = 0,
    lu4 = 4,
    lu8 = 8,
    lu16 = 16,
    lu32 = 32,
    sse2_x64 = 1 << 8,
    sse2_x64_lu4 = 1 << 8 | 4,
    sse2_x64_lu8 = 1 << 8 | 8,
    sse2_x64_lu16 = 1 << 8 | 16,
    avx2_x64 = 2 << 8,
    avx2_x64_lu4 = 2 << 8 | 4,
    avx2_x64_lu8 = 2 << 8 | 8,
};

enum class trace_method_t : int
{
    unspecified = 0,
    accessor = 1,
    accessor_with_pos_hint = 1 << 8 | 1,
    mutator = 2,
    mutator_with_pos_hint = 1 << 8 | 2,
    constructor = 3,
    destructor = 4
};

struct trace_method_properties_t
{
    trace_method_t type = trace_method_t::unspecified;

    const void* instance = nullptr;

    const char* function_name = nullptr;

    std::string function_args;

    const char* filepath = nullptr;

    int line_number = -1;
};

class element_block_error : public mdds::general_error
{
public:
    element_block_error(const std::string& msg) : mdds::general_error(msg)
    {}
};

class base_element_block;
element_t get_block_type(const base_element_block&) noexcept;

class base_element_block
{
    friend element_t get_block_type(const base_element_block&) noexcept;

protected:
    element_t type;
    base_element_block(element_t _t) noexcept : type(_t)
    {}
};

template<typename ValueT>
struct clone_value;

template<typename BlockT, typename = void>
struct clone_block
{
    using store_type = typename BlockT::store_type;

    BlockT* operator()(const BlockT& blk) const
    {
        auto bt = get_block_type(blk);
        std::ostringstream os;
        os << "cloning of this block type is not implemented (type=" << bt << ")";
        throw element_block_error(os.str());
    }
};

template<typename BlockT>
struct clone_block<BlockT, std::enable_if_t<std::is_copy_constructible<BlockT>::value>>
{
    using store_type = typename BlockT::store_type;

    BlockT* operator()(const BlockT& src) const
    {
        return new BlockT(src);
    }
};

template<typename BlockT>
struct clone_block<BlockT, std::void_t<decltype(clone_value<typename BlockT::value_type>{})>>
{
    using store_type = typename BlockT::store_type;
    using value_type = typename BlockT::value_type;
    using CV = clone_value<value_type>;

    BlockT* operator()(const BlockT& src) const
    {
        auto dest_blk = std::make_unique<BlockT>();
        auto cloned(src.store());

        if constexpr (detail::has_exec_policy<CV>::value)
            std::transform(typename CV::exec_policy{}, cloned.begin(), cloned.end(), cloned.begin(), CV{});
        else
            std::transform(cloned.begin(), cloned.end(), cloned.begin(), CV{});

        dest_blk->store().swap(cloned);
        return dest_blk.release();
    }
};

template<typename Self, element_t TypeId, typename ValueT, template<typename, typename> class StoreT>
class element_block : public base_element_block
{
public:
    using store_type = StoreT<ValueT, std::allocator<ValueT>>;
    static constexpr element_t block_type = TypeId;

protected:
    store_type m_array;

    element_block() noexcept(std::is_nothrow_default_constructible_v<store_type>) : base_element_block(TypeId)
    {}
    element_block(size_t n) : base_element_block(TypeId), m_array(n)
    {}
    element_block(size_t n, const ValueT& val) : base_element_block(TypeId), m_array(n, val)
    {}

    template<typename Iter>
    element_block(const Iter& it_begin, const Iter& it_end) : base_element_block(TypeId), m_array(it_begin, it_end)
    {}

public:
    typedef typename store_type::iterator iterator;
    typedef typename store_type::reverse_iterator reverse_iterator;
    typedef typename store_type::const_iterator const_iterator;
    typedef typename store_type::const_reverse_iterator const_reverse_iterator;
    typedef ValueT value_type;

    const store_type& store() const noexcept
    {
        return m_array;
    }

    store_type& store() noexcept
    {
        return m_array;
    }

private:
    template<bool Mutable>
    class base_range_type
    {
        using elem_block_type = mdds::detail::mutable_t<base_element_block, Mutable>;
        elem_block_type& m_blk;

    public:
        using iter_type = std::conditional_t<Mutable, iterator, const_iterator>;

        base_range_type(elem_block_type& blk) : m_blk(blk)
        {}

        iter_type begin()
        {
            return element_block::begin(m_blk);
        }

        iter_type end()
        {
            return element_block::end(m_blk);
        }
    };

    static constexpr bool nothrow_eq_comparable_v = noexcept(std::declval<store_type>() == std::declval<store_type>());

public:
    using range_type = base_range_type<true>;
    using const_range_type = base_range_type<false>;

    bool operator==(const Self& r) const noexcept(nothrow_eq_comparable_v)
    {
        return m_array == r.m_array;
    }

    bool operator!=(const Self& r) const noexcept(nothrow_eq_comparable_v)
    {
        return !operator==(r);
    }

    static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
    {
        return get(block).m_array.at(pos);
    }

    static value_type& at(base_element_block& block, typename store_type::size_type pos)
    {
        return get(block).m_array.at(pos);
    }

    static value_type* data(base_element_block& block)
    {
        return get(block).m_array.data();
    }

    static typename store_type::size_type size(const base_element_block& block)
    {
        return get(block).m_array.size();
    }

    static iterator begin(base_element_block& block)
    {
        return get(block).m_array.begin();
    }

    static iterator end(base_element_block& block)
    {
        return get(block).m_array.end();
    }

    static const_iterator begin(const base_element_block& block)
    {
        return get(block).m_array.begin();
    }

    static const_iterator end(const base_element_block& block)
    {
        return get(block).m_array.end();
    }

    static const_iterator cbegin(const base_element_block& block)
    {
        return get(block).m_array.begin();
    }

    static const_iterator cend(const base_element_block& block)
    {
        return get(block).m_array.end();
    }

    static reverse_iterator rbegin(base_element_block& block)
    {
        return get(block).m_array.rbegin();
    }

    static reverse_iterator rend(base_element_block& block)
    {
        return get(block).m_array.rend();
    }

    static const_reverse_iterator rbegin(const base_element_block& block)
    {
        return get(block).m_array.rbegin();
    }

    static const_reverse_iterator rend(const base_element_block& block)
    {
        return get(block).m_array.rend();
    }

    static const_reverse_iterator crbegin(const base_element_block& block)
    {
        return get(block).m_array.rbegin();
    }

    static const_reverse_iterator crend(const base_element_block& block)
    {
        return get(block).m_array.rend();
    }

    static const_range_type range(const base_element_block& block)
    {
        return const_range_type(block);
    }

    static range_type range(base_element_block& block)
    {
        return range_type(block);
    }

    static Self& get(base_element_block& block)
    {
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
        if (get_block_type(block) != TypeId)
        {
            std::ostringstream os;
            os << "incorrect block type: expected block type=" << TypeId
               << ", passed block type=" << get_block_type(block);
            throw general_error(os.str());
        }
#endif
        return static_cast<Self&>(block);
    }

    static const Self& get(const base_element_block& block)
    {
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
        if (get_block_type(block) != TypeId)
        {
            std::ostringstream os;
            os << "incorrect block type: expected block type=" << TypeId
               << ", passed block type=" << get_block_type(block);
            throw general_error(os.str());
        }
#endif
        return static_cast<const Self&>(block);
    }

    static void set_value(base_element_block& blk, size_t pos, const ValueT& val)
    {
        get(blk).m_array[pos] = val;
    }

    static void get_value(const base_element_block& blk, size_t pos, ValueT& val)
    {
        val = get(blk).m_array[pos];
    }

    static value_type get_value(const base_element_block& blk, size_t pos)
    {
        return get(blk).m_array[pos];
    }

    template<typename T = ValueT>
    static void append_value(base_element_block& blk, T&& val)
    {
        get(blk).m_array.push_back(std::forward<T>(val));
    }

    template<typename... Args>
    static void emplace_back_value(base_element_block& blk, Args&&... args)
    {
        get(blk).m_array.emplace_back(std::forward<Args>(args)...);
    }

    static void prepend_value(base_element_block& blk, const ValueT& val)
    {
        store_type& blk2 = get(blk).m_array;
        blk2.insert(blk2.begin(), val);
    }

    static Self* create_block(size_t init_size)
    {
        return new Self(init_size);
    }

    static void delete_block(const base_element_block* p)
    {
        delete static_cast<const Self*>(p);
    }

    static void resize_block(base_element_block& blk, size_t new_size)
    {
        store_type& st = get(blk).m_array;
        st.resize(new_size);

        // Test if the vector's capacity is larger than twice its current
        // size, and if so, shrink its capacity to free up some memory.
        if (new_size < (detail::get_block_capacity(st) / 2))
            detail::shrink_to_fit(st);
    }

#ifdef MDDS_UNIT_TEST
    static void print_block(const base_element_block& blk)
    {
        const store_type& blk2 = get(blk).m_array;
        for (const auto& val : blk2)
            std::cout << val << " ";

        std::cout << std::endl;
    }
#else
    static void print_block(const base_element_block&)
    {}
#endif

    static void erase_value(base_element_block& blk, size_t pos)
    {
        store_type& blk2 = get(blk).m_array;
        blk2.erase(blk2.begin() + pos);
    }

    static void erase_values(base_element_block& blk, size_t pos, size_t size)
    {
        store_type& blk2 = get(blk).m_array;
        blk2.erase(blk2.begin() + pos, blk2.begin() + pos + size);
    }

    static void append_block(base_element_block& dest, const base_element_block& src)
    {
        store_type& d = get(dest).m_array;
        const store_type& s = get(src).m_array;
        d.insert(d.end(), s.begin(), s.end());
    }

    static void append_values_from_block(
        base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
    {
        store_type& d = get(dest).m_array;
        const store_type& s = get(src).m_array;
        std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
        detail::reserve(d, d.size() + len);
        d.insert(d.end(), its.first, its.second);
    }

    static void assign_values_from_block(
        base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
    {
        store_type& d = get(dest).m_array;
        const store_type& s = get(src).m_array;
        std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
        d.assign(its.first, its.second);
    }

    static void prepend_values_from_block(
        base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
    {
        store_type& d = get(dest).m_array;
        const store_type& s = get(src).m_array;
        std::pair<const_iterator, const_iterator> its = get_iterator_pair(s, begin_pos, len);
        detail::reserve(d, d.size() + len);
        d.insert(d.begin(), its.first, its.second);
    }

    static void swap_values(base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
    {
        store_type& st1 = get(blk1).m_array;
        store_type& st2 = get(blk2).m_array;
        assert(pos1 + len <= st1.size());
        assert(pos2 + len <= st2.size());

        typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
        std::advance(it1, pos1);
        std::advance(it2, pos2);

        for (size_t i = 0; i < len; ++i, ++it1, ++it2)
        {
            value_type v1 = *it1, v2 = *it2;
            *it1 = v2;
            *it2 = v1;
        }
    }

    static bool equal_block(const base_element_block& left, const base_element_block& right)
    {
        return get(left) == get(right);
    }

    template<typename Iter>
    static void set_values(base_element_block& block, size_t pos, const Iter& it_begin, const Iter& it_end)
    {
        store_type& d = get(block).m_array;
        typename store_type::iterator it_dest = d.begin();
        std::advance(it_dest, pos);
        for (Iter it = it_begin; it != it_end; ++it, ++it_dest)
            *it_dest = *it;
    }

    template<typename Iter>
    static void append_values(base_element_block& block, const Iter& it_begin, const Iter& it_end)
    {
        store_type& d = get(block).m_array;
        typename store_type::iterator it = d.end();
        d.insert(it, it_begin, it_end);
    }

    template<typename Iter>
    static void prepend_values(base_element_block& block, const Iter& it_begin, const Iter& it_end)
    {
        store_type& d = get(block).m_array;
        d.insert(d.begin(), it_begin, it_end);
    }

    template<typename Iter>
    static void assign_values(base_element_block& dest, const Iter& it_begin, const Iter& it_end)
    {
        store_type& d = get(dest).m_array;
        d.assign(it_begin, it_end);
    }

    template<typename Iter>
    static void insert_values(base_element_block& block, size_t pos, const Iter& it_begin, const Iter& it_end)
    {
        store_type& blk = get(block).m_array;
        blk.insert(blk.begin() + pos, it_begin, it_end);
    }

    static size_t capacity(const base_element_block& block)
    {
        const store_type& blk = get(block).m_array;
        return detail::get_block_capacity(blk);
    }

    static void reserve(base_element_block& block, std::size_t size)
    {
        store_type& blk = get(block).m_array;
        detail::reserve(blk, size);
    }

    static void shrink_to_fit(base_element_block& block)
    {
        store_type& blk = get(block).m_array;
        detail::shrink_to_fit(blk);
    }

private:
    static std::pair<const_iterator, const_iterator> get_iterator_pair(
        const store_type& array, size_t begin_pos, size_t len)
    {
        assert(begin_pos + len <= array.size());
        const_iterator it = array.begin();
        std::advance(it, begin_pos);
        const_iterator it_end = it;
        std::advance(it_end, len);
        return std::pair<const_iterator, const_iterator>(it, it_end);
    }
};

template<typename Self, element_t TypeId, typename ValueT, template<typename, typename> class StoreT>
class copyable_element_block : public element_block<Self, TypeId, ValueT, StoreT>
{
    using base_type = element_block<Self, TypeId, ValueT, StoreT>;

protected:
    copyable_element_block() noexcept(std::is_nothrow_default_constructible_v<base_type>) : base_type()
    {}
    copyable_element_block(size_t n) : base_type(n)
    {}
    copyable_element_block(size_t n, const ValueT& val) : base_type(n, val)
    {}

    template<typename Iter>
    copyable_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
    {}

public:
    using base_type::get;

    static Self* copy_block(const base_element_block& blk)
    {
        // Use copy constructor to copy the data.
        return new Self(get(blk));
    }

    static Self* clone_block(const base_element_block& src)
    {
        return mdds::mtv::clone_block<Self>{}(get(src));
    }
};

template<typename Self, element_t TypeId, typename ValueT, template<typename, typename> class StoreT>
class noncopyable_element_block : public element_block<Self, TypeId, ValueT, StoreT>
{
    using base_type = element_block<Self, TypeId, ValueT, StoreT>;

protected:
    noncopyable_element_block() noexcept(std::is_nothrow_default_constructible_v<base_type>) : base_type()
    {}
    noncopyable_element_block(size_t n) : base_type(n)
    {}
    noncopyable_element_block(size_t n, const ValueT& val) : base_type(n, val)
    {}

    template<typename Iter>
    noncopyable_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
    {}

public:
    using base_type::get;

    noncopyable_element_block(const noncopyable_element_block&) = delete;
    noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;

    static Self* copy_block(const base_element_block&)
    {
        throw element_block_error("attempted to copy a noncopyable element block.");
    }

    static Self* clone_block(const base_element_block& src)
    {
        return mdds::mtv::clone_block<Self>{}(get(src));
    }
};

inline element_t get_block_type(const base_element_block& blk) noexcept
{
    return blk.type;
}

template<element_t TypeId, typename ValueT, template<typename, typename> class StoreT = delayed_delete_vector>
struct default_element_block
    : public copyable_element_block<default_element_block<TypeId, ValueT, StoreT>, TypeId, ValueT, StoreT>
{
    using self_type = default_element_block<TypeId, ValueT, StoreT>;
    using base_type = copyable_element_block<self_type, TypeId, ValueT, StoreT>;

    default_element_block() noexcept(std::is_nothrow_default_constructible_v<base_type>) : base_type()
    {}
    default_element_block(size_t n) : base_type(n)
    {}
    default_element_block(size_t n, const ValueT& val) : base_type(n, val)
    {}

    template<typename Iter>
    default_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
    {}

    static self_type* create_block_with_value(size_t init_size, const ValueT& val)
    {
        return new self_type(init_size, val);
    }

    template<typename Iter>
    static self_type* create_block_with_values(const Iter& it_begin, const Iter& it_end)
    {
        return new self_type(it_begin, it_end);
    }

    static void overwrite_values(base_element_block&, size_t, size_t)
    {
        // Do nothing.
    }
};

template<element_t TypeId, typename ValueT, template<typename, typename> class StoreT = delayed_delete_vector>
struct managed_element_block
    : public copyable_element_block<managed_element_block<TypeId, ValueT, StoreT>, TypeId, ValueT*, StoreT>
{
    using self_type = managed_element_block<TypeId, ValueT, StoreT>;
    using base_type = copyable_element_block<self_type, TypeId, ValueT*, StoreT>;

    using base_type::get;
    using base_type::m_array;
    using base_type::reserve;
    using base_type::set_value;

    managed_element_block() noexcept(std::is_nothrow_default_constructible_v<base_type>) : base_type()
    {}
    managed_element_block(size_t n) : base_type(n)
    {}
    managed_element_block(const managed_element_block& r) : base_type()
    {
        detail::reserve(m_array, r.m_array.size());
        for (const auto& v : r.m_array)
            m_array.push_back(new ValueT(*v));
    }

    template<typename Iter>
    managed_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
    {}

    ~managed_element_block()
    {
        std::for_each(m_array.begin(), m_array.end(), std::default_delete<ValueT>());
    }

    static self_type* create_block_with_value(size_t init_size, ValueT* val)
    {
        // Managed blocks don't support initialization with value.
        if (init_size > 1)
            throw general_error("You can't create a managed block with initial value.");

        std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
        if (init_size == 1)
            set_value(*blk, 0, val);

        return blk.release();
    }

    template<typename Iter>
    static self_type* create_block_with_values(const Iter& it_begin, const Iter& it_end)
    {
        return new self_type(it_begin, it_end);
    }

    static void overwrite_values(base_element_block& block, size_t pos, size_t len)
    {
        managed_element_block& blk = get(block);
        typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
        typename managed_element_block::store_type::iterator it_end = it + len;
        std::for_each(it, it_end, std::default_delete<ValueT>());
    }
};

template<element_t TypeId, typename ValueT, template<typename, typename> class StoreT = delayed_delete_vector>
struct noncopyable_managed_element_block
    : public noncopyable_element_block<
          noncopyable_managed_element_block<TypeId, ValueT, StoreT>, TypeId, ValueT*, StoreT>
{
    using self_type = noncopyable_managed_element_block<TypeId, ValueT, StoreT>;
    using base_type = noncopyable_element_block<self_type, TypeId, ValueT*, StoreT>;

    using base_type::get;
    using base_type::m_array;
    using base_type::set_value;

    noncopyable_managed_element_block() noexcept(std::is_nothrow_default_constructible_v<base_type>) : base_type()
    {}
    noncopyable_managed_element_block(size_t n) : base_type(n)
    {}

    template<typename Iter>
    noncopyable_managed_element_block(const Iter& it_begin, const Iter& it_end) : base_type(it_begin, it_end)
    {}

    ~noncopyable_managed_element_block()
    {
        std::for_each(m_array.begin(), m_array.end(), std::default_delete<ValueT>());
    }

    static self_type* create_block_with_value(size_t init_size, ValueT* val)
    {
        // Managed blocks don't support initialization with value.
        if (init_size > 1)
            throw general_error("You can't create a managed block with initial value.");

        std::unique_ptr<self_type> blk = std::make_unique<self_type>(init_size);
        if (init_size == 1)
            set_value(*blk, 0, val);

        return blk.release();
    }

    template<typename Iter>
    static self_type* create_block_with_values(const Iter& it_begin, const Iter& it_end)
    {
        return new self_type(it_begin, it_end);
    }

    static void overwrite_values(base_element_block& block, size_t pos, size_t len)
    {
        noncopyable_managed_element_block& blk = get(block);
        typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
        typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
        std::for_each(it, it_end, std::default_delete<ValueT>());
    }

    static bool equal_block(const base_element_block& left, const base_element_block& right)
    {
        const auto& array1 = get(left).m_array;
        const auto& array2 = get(right).m_array;

        if (array1.size() != array2.size())
            return false;

        return std::equal(array1.begin(), array1.end(), array2.begin(), [](const ValueT* p1, const ValueT* p2) {
            return *p1 == *p2;
        });
    }
};

namespace detail {

template<typename Blk>
bool get_block_element_at(const mdds::mtv::base_element_block& data, size_t offset, std::true_type)
{
    auto it = Blk::cbegin(data);
    std::advance(it, offset);
    return *it;
}

template<typename Blk>
typename Blk::value_type get_block_element_at(const mdds::mtv::base_element_block& data, size_t offset, std::false_type)
{
    return Blk::at(data, offset);
}

template<typename Blk>
typename Blk::value_type get_block_element_at(const mdds::mtv::base_element_block& data, size_t offset)
{
    typename mdds::mtv::detail::has_std_vector_bool_store<Blk>::type v;
    return get_block_element_at<Blk>(data, offset, v);
}

} // namespace detail

}} // namespace mdds::mtv

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */