Loading...
Searching...
No Matches
aos/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 "./iterator.hpp"
#include "./block_util.hpp"
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
#include <iostream>
#endif
namespace mdds { namespace mtv { namespace aos {
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
{
size_type position;
size_type size;
base_element_block* data;
block() noexcept(std::is_fundamental_v<size_type>);
block(size_type _position, size_type _size) noexcept(std::is_fundamental_v<size_type>);
block(size_type _position, size_type _size, base_element_block* _data) noexcept(
std::is_fundamental_v<size_type>);
block(const block& other) = default;
block(block&& other) = default;
~block() = default;
block& operator=(const block&) = default;
block& operator=(block&&) = default;
void swap(block& other) noexcept(std::is_fundamental_v<size_type>);
};
struct element_block_deleter
{
void operator()(const base_element_block* p)
{
block_funcs::delete_block(p);
}
};
typedef std::vector<block> blocks_type;
struct blocks_to_transfer
{
blocks_type blocks;
size_type insert_index;
blocks_to_transfer();
};
struct iterator_trait
{
typedef multi_type_vector parent;
typedef blocks_type blocks;
typedef typename blocks_type::iterator base_iterator;
};
struct reverse_iterator_trait
{
typedef multi_type_vector parent;
typedef blocks_type blocks;
typedef typename blocks_type::reverse_iterator base_iterator;
};
struct const_iterator_trait
{
typedef multi_type_vector parent;
typedef blocks_type blocks;
typedef typename blocks_type::const_iterator base_iterator;
};
struct const_reverse_iterator_trait
{
typedef multi_type_vector parent;
typedef blocks_type blocks;
typedef typename blocks_type::const_reverse_iterator base_iterator;
};
typedef mdds::detail::mtv::iterator_value_node<multi_type_vector, size_type> itr_node;
typedef mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type> itr_forward_update;
typedef mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type> itr_no_update;
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:
typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator>
const_reverse_iterator;
typedef itr_node value_type;
typedef std::pair<iterator, size_type> position_type;
typedef std::pair<const_iterator, size_type> const_position_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);
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;
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;
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);
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);
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);
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 noexcept(std::is_nothrow_copy_constructible_v<size_type>);
size_type block_size() const noexcept;
bool empty() const noexcept;
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(block& blk);
void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
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);
template<typename T>
iterator push_back_impl(T&& value);
template<typename T, typename... Args>
iterator emplace_back_impl(Args&&... args);
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;
void resize_impl(size_type new_size);
template<typename T>
void create_new_block_with_new_cell(base_element_block*& data, T&& cell);
template<typename T, typename... Args>
void create_new_block_with_emplace_back(base_element_block*& data, const T& t, Args&&... args);
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 append_cell_to_block(size_type block_index, const T& cell);
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_block_of_size_one(size_type block_index, 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);
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);
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);
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);
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_pos);
iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
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 insert_cells_impl(size_type row, size_type block_index, 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);
size_type merge_with_adjacent_blocks(size_type block_index);
bool merge_with_next_block(size_type block_index);
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);
block& set_new_block_to_middle(size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
block* get_previous_block_of_type(size_type block_index, element_t cat);
block* get_next_block_of_type(size_type block_index, element_t cat);
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_data, 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)
{
typename blocks_type::iterator block_pos = m_blocks.begin();
std::advance(block_pos, block_index);
return iterator(block_pos, m_blocks.end(), this, block_index);
}
inline const_iterator get_const_iterator(size_type block_index) const
{
typename blocks_type::const_iterator block_pos = m_blocks.begin();
std::advance(block_pos, block_index);
return const_iterator(block_pos, m_blocks.end(), 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_blocks;
size_type m_cur_size;
};
}}} // namespace mdds::mtv::aos
#include "main_def.inl"
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
mdds::mtv::aos::multi_type_vector::next_position
static const_position_type next_position(const const_position_type &pos)
mdds::mtv::aos::multi_type_vector::get_element_type
static mtv::element_t get_element_type(const T &elem)
mdds::mtv::aos::multi_type_vector::empty
bool empty() const noexcept
mdds::mtv::aos::multi_type_vector::erase
void erase(size_type start_pos, size_type end_pos)
mdds::mtv::aos::multi_type_vector::logical_position
static size_type logical_position(const const_position_type &pos) noexcept(std::is_fundamental_v< size_type >)
mdds::mtv::aos::multi_type_vector::push_back_empty
iterator push_back_empty()
mdds::mtv::aos::multi_type_vector::release
T release(size_type pos)
mdds::mtv::aos::multi_type_vector::is_empty
bool is_empty(size_type pos) const
mdds::mtv::aos::multi_type_vector::clone
multi_type_vector clone() const
mdds::mtv::aos::multi_type_vector::multi_type_vector
multi_type_vector() noexcept(nothrow_default_constructible_v)
mdds::mtv::aos::multi_type_vector::event_func
typename Traits::event_func event_func
Definition aos/main.hpp:72
mdds::mtv::aos::multi_type_vector::position
position_type position(size_type pos)
mdds::mtv::aos::multi_type_vector::next_position
static position_type next_position(const position_type &pos)
mdds::mtv::aos::multi_type_vector::value_type
itr_node value_type
Definition aos/main.hpp:184
mdds::mtv::aos::multi_type_vector::set
iterator set(size_type pos, const T &value)
mdds::mtv::aos::multi_type_vector::get
static Blk::value_type get(const const_position_type &pos)
mdds::mtv::aos::multi_type_vector::advance_position
static position_type advance_position(const position_type &pos, int steps)
mdds::mtv::aos::multi_type_vector::clear
void clear()
mdds::mtv::aos::multi_type_vector::set_empty
iterator set_empty(size_type start_pos, size_type end_pos)
mdds::mtv::aos::multi_type_vector::size
size_type size() const noexcept(std::is_nothrow_copy_constructible_v< size_type >)
mdds::mtv::aos::multi_type_vector::block_size
size_type block_size() const noexcept
mdds::mtv::aos::multi_type_vector::insert
iterator insert(size_type pos, const T &it_begin, const T &it_end)
mdds::mtv::aos::multi_type_vector::advance_position
static const_position_type advance_position(const const_position_type &pos, int steps)
mdds::mtv::aos::multi_type_vector::resize
void resize(size_type new_size)
mdds::mtv::aos::multi_type_vector::push_back
iterator push_back(T &&value)
mdds::mtv::aos::multi_type_vector::transfer
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
mdds::mtv::aos::multi_type_vector::get_type
mtv::element_t get_type(size_type pos) const
mdds::mtv::aos::multi_type_vector::emplace_back
iterator emplace_back(Args &&... args)
mdds::mtv::aos::multi_type_vector::insert_empty
iterator insert_empty(size_type pos, size_type length)
mdds::mtv::aos::multi_type_vector::shrink_to_fit
void shrink_to_fit()
mdds::mtv::aos::multi_type_vector::release_range
iterator release_range(size_type start_pos, size_type end_pos)
mdds::mtv::aos::multi_type_vector::swap
void swap(multi_type_vector &other) noexcept(nothrow_swappable_v)
mdds::mtv::base_element_block
Definition types.hpp:135
mdds::mtv::soa::multi_type_vector< Traits >::multi_type_vector
multi_type_vector() noexcept(nothrow_default_constructible_v)