Loading...
Searching...
No Matches
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: */
mdds::general_error
Definition global.hpp:60
mdds::mtv::base_element_block
Definition types.hpp:135
mdds::mtv::base_element_block::get_block_type
friend element_t get_block_type(const base_element_block &) noexcept
Definition types.hpp:696
mdds::mtv::delayed_delete_vector
Definition delayed_delete_vector.hpp:22
mdds::mtv::element_block_error
Definition types.hpp:121
mdds::mtv::clone_block
Definition types.hpp:158
mdds::mtv::clone_value
Definition types.hpp:148
mdds::mtv::detail::has_exec_policy
Definition types_util.hpp:143
mdds::mtv::trace_method_properties_t
Definition types.hpp:91
mdds::mtv::trace_method_properties_t::function_args
std::string function_args
Definition types.hpp:108
mdds::mtv::trace_method_properties_t::function_name
const char * function_name
Definition types.hpp:102
mdds::mtv::trace_method_properties_t::line_number
int line_number
Definition types.hpp:114
mdds::mtv::trace_method_properties_t::instance
const void * instance
Definition types.hpp:99
mdds::mtv::trace_method_properties_t::filepath
const char * filepath
Definition types.hpp:111