mdds
Loading...
Searching...
No Matches
soa/main.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
3// SPDX-FileCopyrightText: 2021 - 2025 Kohei Yoshida
4//
5// SPDX-License-Identifier: MIT
6
7#pragma once
8
9#include "../../global.hpp"
10#include "../types.hpp"
11#include "../util.hpp"
12#include "./block_util.hpp"
13#include "./iterator.hpp"
14
15#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
16#include <iostream>
17#endif
18
19namespace mdds { namespace mtv { namespace soa {
20
48template<typename Traits = mdds::mtv::default_traits>
49class multi_type_vector
50{
51public:
52 using size_type = std::size_t;
53 using block_funcs = typename Traits::block_funcs;
54
72 using event_func = typename Traits::event_func;
73
74private:
75 struct block_slot_type
76 {
77 size_type position = 0;
78 size_type size = 0;
80
81 block_slot_type() noexcept(std::is_fundamental_v<size_type>)
82 {}
83 block_slot_type(size_type _position, size_type _size) noexcept(std::is_fundamental_v<size_type>)
84 : position(_position), size(_size)
85 {}
86 };
87
88 struct blocks_type
89 {
90 std::vector<size_type> positions;
91 std::vector<size_type> sizes;
92 std::vector<base_element_block*> element_blocks;
93
94 static constexpr bool nothrow_default_constructible_v =
95 std::is_nothrow_default_constructible_v<std::vector<size_type>> &&
96 std::is_nothrow_default_constructible_v<std::vector<base_element_block*>>;
97
98 static constexpr bool nothrow_move_constructible_v =
99 std::is_nothrow_move_constructible_v<std::vector<size_type>> &&
100 std::is_nothrow_move_constructible_v<std::vector<base_element_block*>>;
101
102 static constexpr bool nothrow_value_swappable_v =
103 noexcept(std::swap(std::declval<size_type&>(), std::declval<size_type&>())) &&
104 noexcept(std::swap(std::declval<base_element_block*&>(), std::declval<base_element_block*&>()));
105
106 static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<std::vector<size_type>> &&
107 std::is_nothrow_swappable_v<std::vector<base_element_block*>>;
108
109 blocks_type() noexcept(nothrow_default_constructible_v);
110
111 template<stateful_clone_value... CVs>
112 blocks_type(mtv::detail::clone_construction_type, const blocks_type& other, CVs&... cloners);
113
114 blocks_type(const blocks_type& other);
115 blocks_type(blocks_type&& other) noexcept(nothrow_move_constructible_v);
116
117 void pop_back()
118 {
119 positions.pop_back();
120 sizes.pop_back();
121 element_blocks.pop_back();
122 }
123
124 void push_back(size_type pos, size_type size, base_element_block* data)
125 {
126 positions.push_back(pos);
127 sizes.push_back(size);
128 element_blocks.push_back(data);
129 }
130
131 void push_back(const block_slot_type& slot)
132 {
133 positions.push_back(slot.position);
134 sizes.push_back(slot.size);
135 element_blocks.push_back(slot.element_block);
136 }
137
138 void erase(size_type index);
139 void erase(size_type index, size_type size);
140 void insert(size_type index, size_type size);
141 void insert(size_type index, size_type pos, size_type size, base_element_block* data);
142 void insert(size_type index, const blocks_type& new_blocks);
143
150 void calc_block_position(size_type index);
151
152 size_type calc_next_block_position(size_type index);
153
154 void swap(size_type index1, size_type index2) noexcept(nothrow_value_swappable_v);
155
156 void swap(blocks_type& other) noexcept(nothrow_swappable_v);
157
158 void reserve(size_type n);
159
160 bool equals(const blocks_type& other) const;
161
162 void clear();
163
164 void check_integrity() const;
165 };
166
167 struct blocks_to_transfer
168 {
169 blocks_type blocks;
170 size_type insert_index = 0;
171 };
172
173 struct iterator_trait
174 {
175 using parent = multi_type_vector;
176 using positions_type = std::vector<size_type>;
177 using sizes_type = std::vector<size_type>;
178 using element_blocks_type = std::vector<base_element_block*>;
179
180 using positions_iterator_type = typename positions_type::iterator;
181 using sizes_iterator_type = typename sizes_type::iterator;
182 using element_blocks_iterator_type = typename element_blocks_type::iterator;
183
184 using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
185 };
186
187 struct const_iterator_trait
188 {
189 using parent = multi_type_vector;
190 using positions_type = std::vector<size_type>;
191 using sizes_type = std::vector<size_type>;
192 using element_blocks_type = std::vector<base_element_block*>;
193
194 using positions_iterator_type = typename positions_type::const_iterator;
195 using sizes_iterator_type = typename sizes_type::const_iterator;
196 using element_blocks_iterator_type = typename element_blocks_type::const_iterator;
197
198 using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
199 };
200
201 struct reverse_iterator_trait
202 {
203 using parent = multi_type_vector;
204 using positions_type = std::vector<size_type>;
205 using sizes_type = std::vector<size_type>;
206 using element_blocks_type = std::vector<base_element_block*>;
207
208 using positions_iterator_type = typename positions_type::reverse_iterator;
209 using sizes_iterator_type = typename sizes_type::reverse_iterator;
210 using element_blocks_iterator_type = typename element_blocks_type::reverse_iterator;
211
212 using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
213 };
214
215 struct const_reverse_iterator_trait
216 {
217 using parent = multi_type_vector;
218 using positions_type = std::vector<size_type>;
219 using sizes_type = std::vector<size_type>;
220 using element_blocks_type = std::vector<base_element_block*>;
221
222 using positions_iterator_type = typename positions_type::const_reverse_iterator;
223 using sizes_iterator_type = typename sizes_type::const_reverse_iterator;
224 using element_blocks_iterator_type = typename element_blocks_type::const_reverse_iterator;
225
226 using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
227 };
228
229 struct element_block_deleter
230 {
231 void operator()(const base_element_block* p)
232 {
233 block_funcs::delete_block(p);
234 }
235 };
236
237 static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<event_func> &&
238 std::is_nothrow_default_constructible_v<blocks_type> &&
239 std::is_nothrow_default_constructible_v<size_type>;
240
241 static constexpr bool nothrow_move_constructible_v = std::is_nothrow_move_constructible_v<event_func> &&
242 std::is_nothrow_move_constructible_v<blocks_type> &&
243 std::is_nothrow_move_constructible_v<size_type>;
244
245 static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<event_func> &&
246 std::is_nothrow_swappable_v<size_type> &&
247 std::is_nothrow_swappable_v<blocks_type>;
248
249 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
250
251 template<stateful_clone_value... CVs>
252 multi_type_vector(mtv::detail::clone_construction_type, const multi_type_vector& other, CVs&... cloners);
253
254 template<stateful_clone_value... CVs>
256 mtv::detail::clone_construction_type, const multi_type_vector& other, event_func hdl, CVs&... cloners);
257
258public:
259 using iterator = detail::iterator_base<iterator_trait>;
260 using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
261
262 using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
263 using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
264
265 using position_type = std::pair<iterator, size_type>;
266 using const_position_type = std::pair<const_iterator, size_type>;
267
284
293 static position_type next_position(const position_type& pos);
294
304 static position_type advance_position(const position_type& pos, int steps);
305
314 static const_position_type next_position(const const_position_type& pos);
315
325 static const_position_type advance_position(const const_position_type& pos, int steps);
326
335 static size_type logical_position(const const_position_type& pos) noexcept(std::is_fundamental_v<size_type>);
336
345 template<typename _Blk>
346 static typename _Blk::value_type get(const const_position_type& pos);
347
348 event_func& event_handler();
349 const event_func& event_handler() const;
350
360 container_id_t identity() const noexcept;
361
365 multi_type_vector() noexcept(nothrow_default_constructible_v);
366
373 multi_type_vector(const event_func& hdl);
374
381 multi_type_vector(event_func&& hdl);
382
390 multi_type_vector(size_type init_size);
391
401 template<typename T>
402 multi_type_vector(size_type init_size, const T& value);
403
417 template<typename T>
418 multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
419
425 multi_type_vector(const multi_type_vector& other);
426
432 multi_type_vector(multi_type_vector&& other) noexcept(nothrow_move_constructible_v);
433
437 ~multi_type_vector();
438
461 multi_type_vector clone() const;
462
477 multi_type_vector clone(event_func hdl) const;
478
509 template<stateful_clone_value... CVs>
510 multi_type_vector clone(CVs&... cloners) const;
511
529 template<stateful_clone_value... CVs>
530 multi_type_vector clone(event_func hdl, CVs&... cloners) const;
531
559 position_type position(size_type pos);
560
595 position_type position(position_hint pos_hint, size_type pos);
596
610 const_position_type position(size_type pos) const;
611
632 const_position_type position(position_hint pos_hint, size_type pos) const;
633
658 iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
659
692 iterator transfer(
693 position_hint pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
694
711 template<typename T>
712 iterator set(size_type pos, const T& value);
713
750 template<typename T>
751 iterator set(position_hint pos_hint, size_type pos, const T& value);
752
774 template<typename T>
775 iterator set(size_type pos, const T& it_begin, const T& it_end);
776
818 template<typename T>
819 iterator set(position_hint pos_hint, size_type pos, const T& it_begin, const T& it_end);
820
837 template<typename T>
838 iterator push_back(T&& value);
839
847 iterator push_back_empty();
848
866 template<typename T, typename... Args>
867 iterator emplace_back(Args&&... args);
868
890 template<typename T>
891 iterator insert(size_type pos, const T& it_begin, const T& it_end);
892
934 template<typename T>
935 iterator insert(position_hint pos_hint, size_type pos, const T& it_begin, const T& it_end);
936
944 mtv::element_t get_type(size_type pos) const;
945
957 bool is_empty(size_type pos) const;
958
972 iterator set_empty(size_type start_pos, size_type end_pos);
973
1005 iterator set_empty(position_hint pos_hint, size_type start_pos, size_type end_pos);
1006
1022 void erase(size_type start_pos, size_type end_pos);
1023
1042 iterator insert_empty(size_type pos, size_type length);
1043
1082 iterator insert_empty(position_hint pos_hint, size_type pos, size_type length);
1083
1088 void clear();
1089
1095 size_type size() const;
1096
1114 size_type block_size() const;
1115
1121 bool empty() const;
1122
1133 template<typename T>
1134 void get(size_type pos, T& value) const;
1135
1147 template<typename T>
1148 T get(size_type pos) const;
1149
1170 template<typename T>
1171 T release(size_type pos);
1172
1195 template<typename T>
1196 iterator release(size_type pos, T& value);
1197
1227 template<typename T>
1228 iterator release(position_hint pos_hint, size_type pos, T& value);
1229
1250 void release();
1251
1279 iterator release_range(size_type start_pos, size_type end_pos);
1280
1324 iterator release_range(position_hint pos_hint, size_type start_pos, size_type end_pos);
1325
1339 iterator begin();
1340
1355 iterator end();
1356
1357 const_iterator begin() const;
1358 const_iterator end() const;
1359
1360 const_iterator cbegin() const;
1361 const_iterator cend() const;
1362
1376 reverse_iterator rbegin();
1377
1392 reverse_iterator rend();
1393
1394 const_reverse_iterator rbegin() const;
1395 const_reverse_iterator rend() const;
1396
1397 const_reverse_iterator crbegin() const;
1398 const_reverse_iterator crend() const;
1399
1407 void resize(size_type new_size);
1408
1414 void swap(multi_type_vector& other) noexcept(nothrow_swappable_v);
1415
1424 void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1425
1430
1445 bool is_shared() const noexcept;
1446
1469 void detach();
1470
1496 template<stateful_clone_value... CVs>
1497 void detach(CVs&... cloners);
1498
1499 bool operator==(const multi_type_vector& other) const;
1500
1501 multi_type_vector& operator=(const multi_type_vector& other);
1502 multi_type_vector& operator=(multi_type_vector&& other) noexcept(nothrow_move_assignable_v);
1503
1511 template<typename T>
1512 static mtv::element_t get_element_type(const T& elem);
1513
1514#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1515 void dump_blocks(std::ostream& os) const;
1516
1517 void check_block_integrity() const;
1518#endif
1519
1520private:
1521 iterator make_begin();
1522 iterator make_end();
1523 reverse_iterator make_rbegin();
1524 reverse_iterator make_rend();
1525
1526 void delete_element_block(size_type block_index);
1527
1528 void delete_element_blocks(size_type start, size_type end);
1529
1530 template<typename T>
1531 void get_impl(size_type pos, T& value) const;
1532
1533 template<typename T>
1534 bool set_cells_precheck(size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
1535
1536 template<typename T>
1537 iterator set_impl(size_type pos, size_type block_index, const T& value);
1538
1539 template<typename T>
1540 iterator release_impl(size_type pos, size_type block_index, T& value);
1541
1542 void swap_impl(
1543 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1544 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1545
1546 void swap_single_block(
1547 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1548 size_type other_block_index);
1549
1550 void swap_single_to_multi_blocks(
1551 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1552 size_type dst_block_index1, size_type dst_block_index2);
1553
1554 void swap_multi_to_multi_blocks(
1555 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1556 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1557
1558 template<typename T>
1559 iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1560
1561 void resize_impl(size_type new_size);
1562
1567 iterator transfer_multi_blocks(
1568 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1569 size_type dest_pos);
1570
1579 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1580
1581 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1582
1592 iterator set_empty_in_multi_blocks(
1593 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
1594
1595 void erase_impl(size_type start_pos, size_type end_pos);
1596 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1597
1603 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1604
1605 void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1606
1607 void prepare_blocks_to_transfer(
1608 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1609 size_type offset2);
1610
1611 iterator set_whole_block_empty(size_type block_index, bool overwrite);
1612
1613 template<typename T>
1614 iterator push_back_impl(T&& value);
1615
1616 template<typename T, typename... Args>
1617 iterator emplace_back_impl(Args&&... args);
1618
1619 template<typename T>
1620 iterator set_cells_impl(
1621 size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1622
1623 template<typename T>
1624 iterator set_cells_to_single_block(
1625 size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
1626
1627 template<typename T>
1628 iterator set_cells_to_multi_blocks(
1629 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1630 const T& it_end);
1631
1632 template<typename T>
1633 iterator set_cells_to_multi_blocks_block1_non_equal(
1634 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1635 const T& it_end);
1636
1637 template<typename T>
1638 iterator set_cells_to_multi_blocks_block1_non_empty(
1639 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1640 const T& it_end);
1641
1642 template<typename T>
1643 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1644
1645 template<typename T>
1646 iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
1647
1657 size_type get_block_position(size_type row, size_type start_block_index = 0) const;
1658
1664 size_type get_block_position(const position_hint& pos_hint, size_type row) const;
1665
1666 template<typename T>
1667 void create_new_block_with_new_cell(size_type block_index, T&& cell);
1668
1669 template<typename T, typename... Args>
1670 void create_new_block_with_emplace_back(size_type block_index, const T& t, Args&&... args);
1671
1672 template<typename T>
1673 void append_cell_to_block(size_type block_index, const T& cell);
1674
1682 template<typename T>
1683 bool append_to_prev_block(
1684 size_type block_index, element_t cat, size_type length, const T& it_begin, const T& it_end);
1685
1686 template<typename T>
1687 void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1688
1689 template<typename T>
1690 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
1691
1697 template<typename T>
1698 void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1699
1700 template<typename T>
1701 void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1702
1703 iterator transfer_impl(
1704 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1705
1709 iterator transfer_single_block(
1710 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1711
1720 size_type merge_with_adjacent_blocks(size_type block_index);
1721
1729 bool merge_with_next_block(size_type block_index);
1730
1744 size_type set_new_block_to_middle(
1745 size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1746
1756 bool is_previous_block_of_type(size_type block_index, element_t cat) const;
1757
1767 bool is_next_block_of_type(size_type block_index, element_t cat) const;
1768
1790 base_element_block* exchange_elements(
1791 const base_element_block& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1792 size_type len);
1793
1794 void exchange_elements(
1795 const base_element_block& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1796 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1797
1798 bool append_empty(size_type len);
1799
1800 inline iterator get_iterator(size_type block_index)
1801 {
1802 auto iter_pos = m_block_store.positions.begin();
1803 std::advance(iter_pos, block_index);
1804 auto iter_size = m_block_store.sizes.begin();
1805 std::advance(iter_size, block_index);
1806 auto iter_elem = m_block_store.element_blocks.begin();
1807 std::advance(iter_elem, block_index);
1808
1809 return iterator(
1810 {iter_pos, iter_size, iter_elem},
1811 {m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()}, this,
1812 block_index, m_id);
1813 }
1814
1815 inline const_iterator get_const_iterator(size_type block_index) const
1816 {
1817 auto iter_pos = m_block_store.positions.cbegin();
1818 std::advance(iter_pos, block_index);
1819 auto iter_size = m_block_store.sizes.cbegin();
1820 std::advance(iter_size, block_index);
1821 auto iter_elem = m_block_store.element_blocks.cbegin();
1822 std::advance(iter_elem, block_index);
1823
1824 return const_iterator(
1825 {iter_pos, iter_size, iter_elem},
1826 {m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()}, this,
1827 block_index, m_id);
1828 }
1829
1830#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1831 void debug_check_full(std::string_view location);
1832#endif
1833
1834private:
1841 struct shared_element_blocks
1842 {
1843 std::vector<base_element_block*> blocks;
1844
1845 ~shared_element_blocks()
1846 {
1847 for (base_element_block* p : blocks)
1848 block_funcs::delete_block(p);
1849 }
1850 };
1851
1856 void share() const;
1857
1861 template<stateful_clone_value... CVs>
1862 void detach_impl(CVs&... cloners);
1863
1864 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1865
1866 event_func m_hdl_event;
1867 blocks_type m_block_store;
1868 size_type m_cur_size;
1869
1870 container_id_t m_id = mtv::detail::next_container_id();
1871
1878 [[no_unique_address]] mutable std::conditional_t<
1879 Traits::enable_cow, std::shared_ptr<shared_element_blocks>, mtv::detail::empty_cow_store> m_cow_store;
1880
1881#ifdef MDDS_MULTI_TYPE_VECTOR_TRACE
1882 mutable int m_trace_call_depth = 0;
1883#endif
1884};
1885
1886}}} // namespace mdds::mtv::soa
1887
1888#include "main_def.inl"
1889
1890/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition types.hpp:231
Definition types.hpp:415
iterator set(size_type pos, const T &value)
iterator release_range(size_type start_pos, size_type end_pos)
static const_position_type advance_position(const const_position_type &pos, int steps)
static position_type advance_position(const position_type &pos, int steps)
container_id_t identity() const noexcept
iterator insert_empty(size_type pos, size_type length)
static const_position_type next_position(const const_position_type &pos)
position_type position(size_type pos)
iterator insert(size_type pos, const T &it_begin, const T &it_end)
static _Blk::value_type get(const const_position_type &pos)
typename Traits::event_func event_func
Definition soa/main.hpp:72
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
void erase(size_type start_pos, size_type end_pos)
void swap(multi_type_vector &other) noexcept(nothrow_swappable_v)
iterator emplace_back(Args &&... args)
mdds::detail::mtv::iterator_value_node< multi_type_vector, size_type > value_type
Definition soa/main.hpp:283
static position_type next_position(const position_type &pos)
mtv::element_t get_type(size_type pos) const
static mtv::element_t get_element_type(const T &elem)
static size_type logical_position(const const_position_type &pos) noexcept(std::is_fundamental_v< size_type >)
iterator set_empty(size_type start_pos, size_type end_pos)
multi_type_vector() noexcept(nothrow_default_constructible_v)
Definition types.hpp:290
Definition iterator_node.hpp:19
Definition types.hpp:200