Loading...
Searching...
No Matches
soa/main.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.hpp"
#include "../util.hpp"
#include "./block_util.hpp"
#include "./iterator.hpp"
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
#include <iostream>
#endif
namespace mdds { namespace mtv { namespace soa {
template<typename Traits = mdds::mtv::default_traits>
class multi_type_vector
{
public:
using size_type = std::size_t;
using block_funcs = typename Traits::block_funcs;
using event_func = typename Traits::event_func;
private:
struct block_slot_type
{
size_type position = 0;
size_type size = 0;
base_element_block* element_block = nullptr;
block_slot_type() noexcept(std::is_fundamental_v<size_type>)
{}
block_slot_type(size_type _position, size_type _size) noexcept(std::is_fundamental_v<size_type>)
: position(_position), size(_size)
{}
};
struct blocks_type
{
std::vector<size_type> positions;
std::vector<size_type> sizes;
std::vector<base_element_block*> element_blocks;
static constexpr bool nothrow_default_constructible_v =
std::is_nothrow_default_constructible_v<std::vector<size_type>> &&
std::is_nothrow_default_constructible_v<std::vector<base_element_block*>>;
static constexpr bool nothrow_move_constructible_v =
std::is_nothrow_move_constructible_v<std::vector<size_type>> &&
std::is_nothrow_move_constructible_v<std::vector<base_element_block*>>;
static constexpr bool nothrow_value_swappable_v =
noexcept(std::swap(std::declval<size_type&>(), std::declval<size_type&>())) &&
noexcept(std::swap(std::declval<base_element_block*&>(), std::declval<base_element_block*&>()));
static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<std::vector<size_type>> &&
std::is_nothrow_swappable_v<std::vector<base_element_block*>>;
blocks_type() noexcept(nothrow_default_constructible_v);
blocks_type(mtv::detail::clone_construction_type, const blocks_type& other);
blocks_type(const blocks_type& other);
blocks_type(blocks_type&& other) noexcept(nothrow_move_constructible_v);
void pop_back()
{
positions.pop_back();
sizes.pop_back();
element_blocks.pop_back();
}
void push_back(size_type pos, size_type size, base_element_block* data)
{
positions.push_back(pos);
sizes.push_back(size);
element_blocks.push_back(data);
}
void push_back(const block_slot_type& slot)
{
positions.push_back(slot.position);
sizes.push_back(slot.size);
element_blocks.push_back(slot.element_block);
}
void erase(size_type index);
void erase(size_type index, size_type size);
void insert(size_type index, size_type size);
void insert(size_type index, size_type pos, size_type size, base_element_block* data);
void insert(size_type index, const blocks_type& new_blocks);
void calc_block_position(size_type index);
size_type calc_next_block_position(size_type index);
void swap(size_type index1, size_type index2) noexcept(nothrow_value_swappable_v);
void swap(blocks_type& other) noexcept(nothrow_swappable_v);
void reserve(size_type n);
bool equals(const blocks_type& other) const;
void clear();
void check_integrity() const;
};
struct blocks_to_transfer
{
blocks_type blocks;
size_type insert_index = 0;
};
struct iterator_trait
{
using parent = multi_type_vector;
using positions_type = std::vector<size_type>;
using sizes_type = std::vector<size_type>;
using element_blocks_type = std::vector<base_element_block*>;
using positions_iterator_type = typename positions_type::iterator;
using sizes_iterator_type = typename sizes_type::iterator;
using element_blocks_iterator_type = typename element_blocks_type::iterator;
using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
};
struct const_iterator_trait
{
using parent = multi_type_vector;
using positions_type = std::vector<size_type>;
using sizes_type = std::vector<size_type>;
using element_blocks_type = std::vector<base_element_block*>;
using positions_iterator_type = typename positions_type::const_iterator;
using sizes_iterator_type = typename sizes_type::const_iterator;
using element_blocks_iterator_type = typename element_blocks_type::const_iterator;
using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
};
struct reverse_iterator_trait
{
using parent = multi_type_vector;
using positions_type = std::vector<size_type>;
using sizes_type = std::vector<size_type>;
using element_blocks_type = std::vector<base_element_block*>;
using positions_iterator_type = typename positions_type::reverse_iterator;
using sizes_iterator_type = typename sizes_type::reverse_iterator;
using element_blocks_iterator_type = typename element_blocks_type::reverse_iterator;
using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
};
struct const_reverse_iterator_trait
{
using parent = multi_type_vector;
using positions_type = std::vector<size_type>;
using sizes_type = std::vector<size_type>;
using element_blocks_type = std::vector<base_element_block*>;
using positions_iterator_type = typename positions_type::const_reverse_iterator;
using sizes_iterator_type = typename sizes_type::const_reverse_iterator;
using element_blocks_iterator_type = typename element_blocks_type::const_reverse_iterator;
using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
};
struct element_block_deleter
{
void operator()(const base_element_block* p)
{
block_funcs::delete_block(p);
}
};
static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<event_func> &&
std::is_nothrow_default_constructible_v<blocks_type> &&
std::is_nothrow_default_constructible_v<size_type>;
static constexpr bool nothrow_move_constructible_v = std::is_nothrow_move_constructible_v<event_func> &&
std::is_nothrow_move_constructible_v<blocks_type> &&
std::is_nothrow_move_constructible_v<size_type>;
static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<event_func> &&
std::is_nothrow_swappable_v<size_type> &&
std::is_nothrow_swappable_v<blocks_type>;
static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
multi_type_vector(mtv::detail::clone_construction_type, const multi_type_vector& other);
public:
using iterator = detail::iterator_base<iterator_trait>;
using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
using position_type = std::pair<iterator, size_type>;
using const_position_type = std::pair<const_iterator, size_type>;
using value_type = mdds::detail::mtv::iterator_value_node<multi_type_vector, size_type>;
static position_type next_position(const position_type& pos);
static position_type advance_position(const position_type& pos, int steps);
static const_position_type next_position(const const_position_type& pos);
static const_position_type advance_position(const const_position_type& pos, int steps);
static size_type logical_position(const const_position_type& pos) noexcept(std::is_fundamental_v<size_type>);
template<typename _Blk>
static typename _Blk::value_type get(const const_position_type& pos);
event_func& event_handler();
const event_func& event_handler() const;
multi_type_vector() noexcept(nothrow_default_constructible_v);
multi_type_vector(const event_func& hdl);
multi_type_vector(event_func&& hdl);
multi_type_vector(size_type init_size);
template<typename T>
multi_type_vector(size_type init_size, const T& value);
template<typename T>
multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
multi_type_vector(const multi_type_vector& other);
multi_type_vector(multi_type_vector&& other) noexcept(nothrow_move_constructible_v);
~multi_type_vector();
multi_type_vector clone() const;
position_type position(size_type pos);
position_type position(const iterator& pos_hint, size_type pos);
const_position_type position(size_type pos) const;
const_position_type position(const const_iterator& pos_hint, size_type pos) const;
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
iterator transfer(
const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
template<typename T>
iterator set(size_type pos, const T& value);
template<typename T>
iterator set(const iterator& pos_hint, size_type pos, const T& value);
template<typename T>
iterator set(size_type pos, const T& it_begin, const T& it_end);
template<typename T>
iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
template<typename T>
iterator push_back(T&& value);
iterator push_back_empty();
template<typename T, typename... Args>
iterator emplace_back(Args&&... args);
template<typename T>
iterator insert(size_type pos, const T& it_begin, const T& it_end);
template<typename T>
iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
mtv::element_t get_type(size_type pos) const;
bool is_empty(size_type pos) const;
iterator set_empty(size_type start_pos, size_type end_pos);
iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
void erase(size_type start_pos, size_type end_pos);
iterator insert_empty(size_type pos, size_type length);
iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
void clear();
size_type size() const;
size_type block_size() const;
bool empty() const;
template<typename T>
void get(size_type pos, T& value) const;
template<typename T>
T get(size_type pos) const;
template<typename T>
T release(size_type pos);
template<typename T>
iterator release(size_type pos, T& value);
template<typename T>
iterator release(const iterator& pos_hint, size_type pos, T& value);
void release();
iterator release_range(size_type start_pos, size_type end_pos);
iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
const_iterator cbegin() const;
const_iterator cend() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
const_reverse_iterator crbegin() const;
const_reverse_iterator crend() const;
void resize(size_type new_size);
void swap(multi_type_vector& other) noexcept(nothrow_swappable_v);
void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
void shrink_to_fit();
bool operator==(const multi_type_vector& other) const;
bool operator!=(const multi_type_vector& other) const;
multi_type_vector& operator=(const multi_type_vector& other);
multi_type_vector& operator=(multi_type_vector&& other) noexcept(nothrow_move_assignable_v);
template<typename T>
static mtv::element_t get_element_type(const T& elem);
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
void dump_blocks(std::ostream& os) const;
void check_block_integrity() const;
#endif
private:
void delete_element_block(size_type block_index);
void delete_element_blocks(size_type start, size_type end);
template<typename T>
void get_impl(size_type pos, T& value) const;
template<typename T>
bool set_cells_precheck(size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
template<typename T>
iterator set_impl(size_type pos, size_type block_index, const T& value);
template<typename T>
iterator release_impl(size_type pos, size_type block_index, T& value);
void swap_impl(
multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
size_type block_index2, size_type dblock_index1, size_type dblock_index2);
void swap_single_block(
multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
size_type other_block_index);
void swap_single_to_multi_blocks(
multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
size_type dst_block_index1, size_type dst_block_index2);
void swap_multi_to_multi_blocks(
multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
size_type block_index2, size_type dblock_index1, size_type dblock_index2);
template<typename T>
iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
void resize_impl(size_type new_size);
iterator transfer_multi_blocks(
size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
size_type dest_pos);
iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
iterator set_empty_in_multi_blocks(
size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
void erase_impl(size_type start_pos, size_type end_pos);
void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
void prepare_blocks_to_transfer(
blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
size_type offset2);
iterator set_whole_block_empty(size_type block_index, bool overwrite);
template<typename T>
iterator push_back_impl(T&& value);
template<typename T, typename... Args>
iterator emplace_back_impl(Args&&... args);
template<typename T>
iterator set_cells_impl(
size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
template<typename T>
iterator set_cells_to_single_block(
size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
template<typename T>
iterator set_cells_to_multi_blocks(
size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
const T& it_end);
template<typename T>
iterator set_cells_to_multi_blocks_block1_non_equal(
size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
const T& it_end);
template<typename T>
iterator set_cells_to_multi_blocks_block1_non_empty(
size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
const T& it_end);
template<typename T>
iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
template<typename T>
iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
size_type get_block_position(size_type row, size_type start_block_index = 0) const;
size_type get_block_position(const typename value_type::private_data& pos_data, size_type row) const;
template<typename T>
void create_new_block_with_new_cell(size_type block_index, T&& cell);
template<typename T, typename... Args>
void create_new_block_with_emplace_back(size_type block_index, const T& t, Args&&... args);
template<typename T>
void append_cell_to_block(size_type block_index, const T& cell);
template<typename T>
bool append_to_prev_block(
size_type block_index, element_t cat, size_type length, const T& it_begin, const T& it_end);
template<typename T>
void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
template<typename T>
iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
template<typename T>
void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
template<typename T>
void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
iterator transfer_impl(
size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
iterator transfer_single_block(
size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
size_type merge_with_adjacent_blocks(size_type block_index);
bool merge_with_next_block(size_type block_index);
size_type set_new_block_to_middle(
size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
bool is_previous_block_of_type(size_type block_index, element_t cat) const;
bool is_next_block_of_type(size_type block_index, element_t cat) const;
base_element_block* exchange_elements(
const base_element_block& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
size_type len);
void exchange_elements(
const base_element_block& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
bool append_empty(size_type len);
inline iterator get_iterator(size_type block_index)
{
auto iter_pos = m_block_store.positions.begin();
std::advance(iter_pos, block_index);
auto iter_size = m_block_store.sizes.begin();
std::advance(iter_size, block_index);
auto iter_elem = m_block_store.element_blocks.begin();
std::advance(iter_elem, block_index);
return iterator(
{iter_pos, iter_size, iter_elem},
{m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()}, this,
block_index);
}
inline const_iterator get_const_iterator(size_type block_index) const
{
auto iter_pos = m_block_store.positions.cbegin();
std::advance(iter_pos, block_index);
auto iter_size = m_block_store.sizes.cbegin();
std::advance(iter_size, block_index);
auto iter_elem = m_block_store.element_blocks.cbegin();
std::advance(iter_elem, block_index);
return const_iterator(
{iter_pos, iter_size, iter_elem},
{m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()}, this,
block_index);
}
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
void debug_check_full(std::string_view location);
#endif
private:
using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
event_func m_hdl_event;
blocks_type m_block_store;
size_type m_cur_size;
#ifdef MDDS_MULTI_TYPE_VECTOR_TRACE
mutable int m_trace_call_depth = 0;
#endif
};
}}} // namespace mdds::mtv::soa
#include "main_def.inl"
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
mdds::mtv::base_element_block
Definition types.hpp:135
mdds::mtv::element_block
Definition types.hpp:216
mdds::mtv::soa::multi_type_vector< Traits >::block_size
size_type block_size() const
mdds::mtv::soa::multi_type_vector< Traits >::set
iterator set(size_type pos, const T &value)
mdds::mtv::soa::multi_type_vector< Traits >::release_range
iterator release_range(size_type start_pos, size_type end_pos)
mdds::mtv::soa::multi_type_vector::advance_position
static const_position_type advance_position(const const_position_type &pos, int steps)
mdds::mtv::soa::multi_type_vector::advance_position
static position_type advance_position(const position_type &pos, int steps)
mdds::mtv::soa::multi_type_vector< Traits >::clone
multi_type_vector clone() const
mdds::mtv::soa::multi_type_vector< Traits >::shrink_to_fit
void shrink_to_fit()
mdds::mtv::soa::multi_type_vector< Traits >::insert_empty
iterator insert_empty(size_type pos, size_type length)
mdds::mtv::soa::multi_type_vector::next_position
static const_position_type next_position(const const_position_type &pos)
mdds::mtv::soa::multi_type_vector< Traits >::position
position_type position(size_type pos)
mdds::mtv::soa::multi_type_vector< Traits >::resize
void resize(size_type new_size)
mdds::mtv::soa::multi_type_vector< Traits >::clear
void clear()
mdds::mtv::soa::multi_type_vector< Traits >::insert
iterator insert(size_type pos, const T &it_begin, const T &it_end)
mdds::mtv::soa::multi_type_vector::get
static _Blk::value_type get(const const_position_type &pos)
mdds::mtv::soa::multi_type_vector< Traits >::empty
bool empty() const
mdds::mtv::soa::multi_type_vector< Traits >::event_func
typename Traits::event_func event_func
Definition soa/main.hpp:72
mdds::mtv::soa::multi_type_vector< Traits >::push_back_empty
iterator push_back_empty()
mdds::mtv::soa::multi_type_vector< Traits >::transfer
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
mdds::mtv::soa::multi_type_vector< Traits >::push_back
iterator push_back(T &&value)
mdds::mtv::soa::multi_type_vector< Traits >::erase
void erase(size_type start_pos, size_type end_pos)
mdds::mtv::soa::multi_type_vector< Traits >::release
T release(size_type pos)
mdds::mtv::soa::multi_type_vector< Traits >::swap
void swap(multi_type_vector &other) noexcept(nothrow_swappable_v)
mdds::mtv::soa::multi_type_vector< Traits >::emplace_back
iterator emplace_back(Args &&... args)
mdds::mtv::soa::multi_type_vector< Traits >::value_type
mdds::detail::mtv::iterator_value_node< multi_type_vector, size_type > value_type
Definition soa/main.hpp:275
mdds::mtv::soa::multi_type_vector< Traits >::size
size_type size() const
mdds::mtv::soa::multi_type_vector::next_position
static position_type next_position(const position_type &pos)
mdds::mtv::soa::multi_type_vector< Traits >::get_type
mtv::element_t get_type(size_type pos) const
mdds::mtv::soa::multi_type_vector< Traits >::get_element_type
static mtv::element_t get_element_type(const T &elem)
mdds::mtv::soa::multi_type_vector::logical_position
static size_type logical_position(const const_position_type &pos) noexcept(std::is_fundamental_v< size_type >)
mdds::mtv::soa::multi_type_vector< Traits >::set_empty
iterator set_empty(size_type start_pos, size_type end_pos)
mdds::mtv::soa::multi_type_vector::multi_type_vector
multi_type_vector() noexcept(nothrow_default_constructible_v)
mdds::mtv::soa::multi_type_vector< Traits >::is_empty
bool is_empty(size_type pos) const
mdds::detail::mtv::iterator_value_node
Definition iterator_node.hpp:19