mdds
Loading...
Searching...
No Matches
aos/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 "./iterator.hpp"
13#include "./block_util.hpp"
14
15#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
16#include <iostream>
17#endif
18
19namespace mdds { namespace mtv { namespace aos {
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
76 {
77 size_type position;
78 size_type size;
80
81 block() noexcept(std::is_fundamental_v<size_type>);
82 block(size_type _position, size_type _size) noexcept(std::is_fundamental_v<size_type>);
83 block(size_type _position, size_type _size, base_element_block* _data) noexcept(
84 std::is_fundamental_v<size_type>);
85 block(const block& other) = default;
86 block(block&& other) = default;
87 ~block() = default;
88
89 block& operator=(const block&) = default;
90 block& operator=(block&&) = default;
91
92 void swap(block& other) noexcept(std::is_fundamental_v<size_type>);
93 };
94
95 struct element_block_deleter
96 {
97 void operator()(const base_element_block* p)
98 {
99 block_funcs::delete_block(p);
100 }
101 };
102
103 typedef std::vector<block> blocks_type;
104
105 struct blocks_to_transfer
106 {
107 blocks_type blocks;
108 size_type insert_index;
109
110 blocks_to_transfer();
111 };
112
113 struct iterator_trait
114 {
115 typedef multi_type_vector parent;
116 typedef blocks_type blocks;
117 typedef typename blocks_type::iterator base_iterator;
118 };
119
120 struct reverse_iterator_trait
121 {
122 typedef multi_type_vector parent;
123 typedef blocks_type blocks;
124 typedef typename blocks_type::reverse_iterator base_iterator;
125 };
126
127 struct const_iterator_trait
128 {
129 typedef multi_type_vector parent;
130 typedef blocks_type blocks;
131 typedef typename blocks_type::const_iterator base_iterator;
132 };
133
134 struct const_reverse_iterator_trait
135 {
136 typedef multi_type_vector parent;
137 typedef blocks_type blocks;
138 typedef typename blocks_type::const_reverse_iterator base_iterator;
139 };
140
141 typedef mdds::detail::mtv::iterator_value_node<multi_type_vector, size_type> itr_node;
142 typedef mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type> itr_forward_update;
143 typedef mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type> itr_no_update;
144
145 static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<event_func> &&
146 std::is_nothrow_default_constructible_v<blocks_type> &&
147 std::is_nothrow_default_constructible_v<size_type>;
148
149 static constexpr bool nothrow_move_constructible_v = std::is_nothrow_move_constructible_v<event_func> &&
150 std::is_nothrow_move_constructible_v<blocks_type> &&
151 std::is_nothrow_move_constructible_v<size_type>;
152
153 static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<event_func> &&
154 std::is_nothrow_swappable_v<size_type> &&
155 std::is_nothrow_swappable_v<blocks_type>;
156
157 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
158
159 template<stateful_clone_value... CVs>
160 multi_type_vector(mtv::detail::clone_construction_type, const multi_type_vector& other, CVs&... cloners);
161
162public:
163 typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
164 typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
165
166 typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
167 typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator>
168 const_reverse_iterator;
169
185 typedef itr_node value_type;
186
187 typedef std::pair<iterator, size_type> position_type;
188 typedef std::pair<const_iterator, size_type> const_position_type;
189
198 static position_type next_position(const position_type& pos);
199
209 static position_type advance_position(const position_type& pos, int steps);
210
219 static const_position_type next_position(const const_position_type& pos);
220
230 static const_position_type advance_position(const const_position_type& pos, int steps);
231
240 static size_type logical_position(const const_position_type& pos) noexcept(std::is_fundamental_v<size_type>);
241
250 template<typename Blk>
251 static typename Blk::value_type get(const const_position_type& pos);
252
253 iterator begin();
254 iterator end();
255
256 const_iterator begin() const;
257 const_iterator end() const;
258
259 const_iterator cbegin() const;
260 const_iterator cend() const;
261
262 reverse_iterator rbegin();
263 reverse_iterator rend();
264
265 const_reverse_iterator rbegin() const;
266 const_reverse_iterator rend() const;
267
268 const_reverse_iterator crbegin() const;
269 const_reverse_iterator crend() const;
270
271 event_func& event_handler();
272 const event_func& event_handler() const;
273
283 container_id_t identity() const noexcept;
284
288 multi_type_vector() noexcept(nothrow_default_constructible_v);
289
296 multi_type_vector(const event_func& hdl);
297
304 multi_type_vector(event_func&& hdl);
305
313 multi_type_vector(size_type init_size);
314
324 template<typename T>
325 multi_type_vector(size_type init_size, const T& value);
326
340 template<typename T>
341 multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
342
348 multi_type_vector(const multi_type_vector& other);
349
355 multi_type_vector(multi_type_vector&& other) noexcept(nothrow_move_constructible_v);
356
360 ~multi_type_vector();
361
384 multi_type_vector clone() const;
385
411 template<stateful_clone_value... CVs>
412 multi_type_vector clone(CVs&... cloners) const;
413
430 template<typename T>
431 iterator set(size_type pos, const T& value);
432
469 template<typename T>
470 iterator set(position_hint pos_hint, size_type pos, const T& value);
471
493 template<typename T>
494 iterator set(size_type pos, const T& it_begin, const T& it_end);
495
537 template<typename T>
538 iterator set(position_hint pos_hint, size_type pos, const T& it_begin, const T& it_end);
539
556 template<typename T>
557 iterator push_back(T&& value);
558
566 iterator push_back_empty();
567
585 template<typename T, typename... Args>
586 iterator emplace_back(Args&&... args);
587
609 template<typename T>
610 iterator insert(size_type pos, const T& it_begin, const T& it_end);
611
653 template<typename T>
654 iterator insert(position_hint pos_hint, size_type pos, const T& it_begin, const T& it_end);
655
666 template<typename T>
667 void get(size_type pos, T& value) const;
668
680 template<typename T>
681 T get(size_type pos) const;
682
697 template<typename T>
698 T release(size_type pos);
699
716 template<typename T>
717 iterator release(size_type pos, T& value);
718
742 template<typename T>
743 iterator release(position_hint pos_hint, size_type pos, T& value);
744
753 void release();
754
770 iterator release_range(size_type start_pos, size_type end_pos);
771
803 iterator release_range(position_hint pos_hint, size_type start_pos, size_type end_pos);
804
821 position_type position(size_type pos);
822
846 position_type position(position_hint pos_hint, size_type pos);
847
861 const_position_type position(size_type pos) const;
862
883 const_position_type position(position_hint pos_hint, size_type pos) const;
884
909 iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
910
943 iterator transfer(
944 position_hint pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
945
953 mtv::element_t get_type(size_type pos) const;
954
966 bool is_empty(size_type pos) const;
967
981 iterator set_empty(size_type start_pos, size_type end_pos);
982
1014 iterator set_empty(position_hint pos_hint, size_type start_pos, size_type end_pos);
1015
1031 void erase(size_type start_pos, size_type end_pos);
1032
1051 iterator insert_empty(size_type pos, size_type length);
1052
1091 iterator insert_empty(position_hint pos_hint, size_type pos, size_type length);
1092
1097 void clear();
1098
1104 size_type size() const noexcept(std::is_nothrow_copy_constructible_v<size_type>);
1105
1123 size_type block_size() const noexcept;
1124
1130 bool empty() const noexcept;
1131
1139 void resize(size_type new_size);
1140
1146 void swap(multi_type_vector& other) noexcept(nothrow_swappable_v);
1147
1156 void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1157
1162
1163 bool operator==(const multi_type_vector& other) const;
1164
1165 multi_type_vector& operator=(const multi_type_vector& other);
1166 multi_type_vector& operator=(multi_type_vector&& other) noexcept(nothrow_move_assignable_v);
1167
1175 template<typename T>
1176 static mtv::element_t get_element_type(const T& elem);
1177
1178#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1179 void dump_blocks(std::ostream& os) const;
1180
1181 void check_block_integrity() const;
1182#endif
1183
1184private:
1191 void delete_element_block(block& blk);
1192
1200 void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1201
1202 template<typename T>
1203 iterator set_impl(size_type pos, size_type block_index, const T& value);
1204
1205 template<typename T>
1206 iterator release_impl(size_type pos, size_type block_index, T& value);
1207
1208 template<typename T>
1209 iterator push_back_impl(T&& value);
1210
1211 template<typename T, typename... Args>
1212 iterator emplace_back_impl(Args&&... args);
1213
1223 size_type get_block_position(size_type row, size_type start_block_index = 0) const;
1224
1230 size_type get_block_position(const position_hint& pos_hint, size_type row) const;
1231
1232 void resize_impl(size_type new_size);
1233
1234 template<typename T>
1235 void create_new_block_with_new_cell(base_element_block*& data, T&& cell);
1236
1237 template<typename T, typename... Args>
1238 void create_new_block_with_emplace_back(base_element_block*& data, const T& t, Args&&... args);
1239
1240 template<typename T>
1241 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
1242
1243 template<typename T>
1244 void append_cell_to_block(size_type block_index, const T& cell);
1245
1246 template<typename T>
1247 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1248
1249 template<typename T>
1250 iterator set_cell_to_block_of_size_one(size_type block_index, const T& cell);
1251
1252 template<typename T>
1253 void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1254
1255 template<typename T>
1256 void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1257
1258 iterator transfer_impl(
1259 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1260
1264 iterator transfer_single_block(
1265 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1266
1271 iterator transfer_multi_blocks(
1272 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1273 size_type dest_pos);
1274
1283 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1284
1285 void swap_impl(
1286 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1287 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1288
1289 void swap_single_block(
1290 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1291 size_type other_block_index);
1292
1293 void swap_single_to_multi_blocks(
1294 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1295 size_type dst_block_index1, size_type dst_block_index2);
1296
1297 void swap_multi_to_multi_blocks(
1298 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1299 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1300
1301 void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1302
1303 void prepare_blocks_to_transfer(
1304 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1305 size_type offset2);
1306
1307 iterator set_whole_block_empty(size_type block_index, bool overwrite);
1308
1309 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1310
1320 iterator set_empty_in_multi_blocks(
1321 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
1322
1323 void erase_impl(size_type start_pos, size_type end_pos);
1324 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1325
1331 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1332
1333 template<typename T>
1334 iterator set_cells_impl(
1335 size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1336
1337 template<typename T>
1338 iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1339
1340 template<typename T>
1341 iterator set_cells_to_single_block(
1342 size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
1343
1344 template<typename T>
1345 iterator set_cells_to_multi_blocks(
1346 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1347 const T& it_end);
1348
1349 template<typename T>
1350 iterator set_cells_to_multi_blocks_block1_non_equal(
1351 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1352 const T& it_end);
1353
1354 template<typename T>
1355 iterator set_cells_to_multi_blocks_block1_non_empty(
1356 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1357 const T& it_end);
1358
1367 size_type merge_with_adjacent_blocks(size_type block_index);
1368
1376 bool merge_with_next_block(size_type block_index);
1377
1378 template<typename T>
1379 bool append_to_prev_block(
1380 size_type block_index, element_t cat, size_type length, const T& it_begin, const T& it_end);
1381
1382 template<typename T>
1383 void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1384
1398 block& set_new_block_to_middle(size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1399
1400 block* get_previous_block_of_type(size_type block_index, element_t cat);
1401
1409 block* get_next_block_of_type(size_type block_index, element_t cat);
1410
1428 base_element_block* exchange_elements(
1429 const base_element_block& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1430 size_type len);
1431
1432 void exchange_elements(
1433 const base_element_block& src_data, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1434 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1435
1436 bool append_empty(size_type len);
1437
1438 inline iterator get_iterator(size_type block_index)
1439 {
1440 typename blocks_type::iterator block_pos = m_blocks.begin();
1441 std::advance(block_pos, block_index);
1442 return iterator(block_pos, m_blocks.end(), this, block_index, m_id);
1443 }
1444
1445 inline const_iterator get_const_iterator(size_type block_index) const
1446 {
1447 typename blocks_type::const_iterator block_pos = m_blocks.begin();
1448 std::advance(block_pos, block_index);
1449 return const_iterator(block_pos, m_blocks.end(), this, block_index, m_id);
1450 }
1451
1452#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1453 void debug_check_full(std::string_view location);
1454#endif
1455
1456private:
1457 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1458
1459 event_func m_hdl_event;
1460 blocks_type m_blocks;
1461 size_type m_cur_size;
1462
1463 container_id_t m_id = mtv::detail::next_container_id();
1464};
1465
1466}}} // namespace mdds::mtv::aos
1467
1468#include "main_def.inl"
1469
1470/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
container_id_t identity() const noexcept
static const_position_type next_position(const const_position_type &pos)
static mtv::element_t get_element_type(const T &elem)
bool empty() const noexcept
void erase(size_type start_pos, size_type end_pos)
static size_type logical_position(const const_position_type &pos) noexcept(std::is_fundamental_v< size_type >)
bool is_empty(size_type pos) const
multi_type_vector clone() const
multi_type_vector() noexcept(nothrow_default_constructible_v)
typename Traits::event_func event_func
Definition aos/main.hpp:72
position_type position(size_type pos)
static position_type next_position(const position_type &pos)
itr_node value_type
Definition aos/main.hpp:185
iterator set(size_type pos, const T &value)
static Blk::value_type get(const const_position_type &pos)
static position_type advance_position(const position_type &pos, int steps)
iterator set_empty(size_type start_pos, size_type end_pos)
size_type size() const noexcept(std::is_nothrow_copy_constructible_v< size_type >)
size_type block_size() const noexcept
iterator insert(size_type pos, const T &it_begin, const T &it_end)
static const_position_type advance_position(const const_position_type &pos, int steps)
void resize(size_type new_size)
iterator transfer(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
iterator emplace_back(Args &&... args)
iterator insert_empty(size_type pos, size_type length)
iterator release_range(size_type start_pos, size_type end_pos)
void swap(multi_type_vector &other) noexcept(nothrow_swappable_v)
Definition types.hpp:231
multi_type_vector() noexcept(nothrow_default_constructible_v)
Definition types.hpp:290
Definition types.hpp:200