mdds
Loading...
Searching...
No Matches
soa/main.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*************************************************************************
3 *
4 * Copyright (c) 2021 Kohei Yoshida
5 *
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
13 * conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 *
27 ************************************************************************/
28
29#ifndef INCLUDED_MDDS_MULTI_TYPE_VECTOR_SOA_MAIN_HPP
30#define INCLUDED_MDDS_MULTI_TYPE_VECTOR_SOA_MAIN_HPP
31
32#include "../../global.hpp"
33#include "../types.hpp"
34#include "../util.hpp"
35#include "./block_util.hpp"
36#include "./iterator.hpp"
37
38#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
39#include <iostream>
40#endif
41
42namespace mdds { namespace mtv { namespace soa {
43
71template<typename Traits = mdds::mtv::default_traits>
73{
74public:
75 using size_type = std::size_t;
76
78 using element_category_type = mdds::mtv::element_t;
79 using block_funcs = typename Traits::block_funcs;
80
98 using event_func = typename Traits::event_func;
99
100private:
101 struct block_slot_type
102 {
103 size_type position = 0;
104 size_type size = 0;
106
107 block_slot_type()
108 {}
109 block_slot_type(size_type _position, size_type _size) : position(_position), size(_size)
110 {}
111 };
112
113 struct blocks_type
114 {
115 std::vector<size_type> positions;
116 std::vector<size_type> sizes;
117 std::vector<element_block_type*> element_blocks;
118
119 blocks_type();
120 blocks_type(const blocks_type& other);
121 blocks_type(blocks_type&& other);
122
123 void pop_back()
124 {
125 positions.pop_back();
126 sizes.pop_back();
127 element_blocks.pop_back();
128 }
129
130 void push_back(size_type pos, size_type size, element_block_type* data)
131 {
132 positions.push_back(pos);
133 sizes.push_back(size);
134 element_blocks.push_back(data);
135 }
136
137 void push_back(const block_slot_type& slot)
138 {
139 positions.push_back(slot.position);
140 sizes.push_back(slot.size);
141 element_blocks.push_back(slot.element_block);
142 }
143
144 void erase(size_type index);
145 void erase(size_type index, size_type size);
146 void insert(size_type index, size_type size);
147 void insert(size_type index, size_type pos, size_type size, element_block_type* data);
148 void insert(size_type index, const blocks_type& new_blocks);
149
156 void calc_block_position(size_type index);
157
158 size_type calc_next_block_position(size_type index);
159
160 void swap(size_type index1, size_type index2);
161
162 void swap(blocks_type& other);
163
164 void reserve(size_type n);
165
166 bool equals(const blocks_type& other) const;
167
168 void clear();
169
170 void check_integrity() const;
171 };
172
173 struct blocks_to_transfer
174 {
175 blocks_type blocks;
176 size_type insert_index = 0;
177 };
178
179 struct iterator_trait
180 {
181 using parent = multi_type_vector;
182 using positions_type = std::vector<size_type>;
183 using sizes_type = std::vector<size_type>;
184 using element_blocks_type = std::vector<element_block_type*>;
185
186 using positions_iterator_type = typename positions_type::iterator;
187 using sizes_iterator_type = typename sizes_type::iterator;
188 using element_blocks_iterator_type = typename element_blocks_type::iterator;
189
191 };
192
193 struct const_iterator_trait
194 {
195 using parent = multi_type_vector;
196 using positions_type = std::vector<size_type>;
197 using sizes_type = std::vector<size_type>;
198 using element_blocks_type = std::vector<element_block_type*>;
199
200 using positions_iterator_type = typename positions_type::const_iterator;
201 using sizes_iterator_type = typename sizes_type::const_iterator;
202 using element_blocks_iterator_type = typename element_blocks_type::const_iterator;
203
205 };
206
207 struct reverse_iterator_trait
208 {
209 using parent = multi_type_vector;
210 using positions_type = std::vector<size_type>;
211 using sizes_type = std::vector<size_type>;
212 using element_blocks_type = std::vector<element_block_type*>;
213
214 using positions_iterator_type = typename positions_type::reverse_iterator;
215 using sizes_iterator_type = typename sizes_type::reverse_iterator;
216 using element_blocks_iterator_type = typename element_blocks_type::reverse_iterator;
217
219 };
220
221 struct const_reverse_iterator_trait
222 {
223 using parent = multi_type_vector;
224 using positions_type = std::vector<size_type>;
225 using sizes_type = std::vector<size_type>;
226 using element_blocks_type = std::vector<element_block_type*>;
227
228 using positions_iterator_type = typename positions_type::const_reverse_iterator;
229 using sizes_iterator_type = typename sizes_type::const_reverse_iterator;
230 using element_blocks_iterator_type = typename element_blocks_type::const_reverse_iterator;
231
233 };
234
235 struct element_block_deleter
236 {
237 void operator()(const element_block_type* p)
238 {
239 block_funcs::delete_block(p);
240 }
241 };
242
243public:
244 using iterator = detail::iterator_base<iterator_trait>;
245 using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
246
247 using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
248 using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
249
250 using position_type = std::pair<iterator, size_type>;
251 using const_position_type = std::pair<const_iterator, size_type>;
252
269
278 static position_type next_position(const position_type& pos);
279
289 static position_type advance_position(const position_type& pos, int steps);
290
299 static const_position_type next_position(const const_position_type& pos);
300
310 static const_position_type advance_position(const const_position_type& pos, int steps);
311
320 static size_type logical_position(const const_position_type& pos);
321
330 template<typename _Blk>
331 static typename _Blk::value_type get(const const_position_type& pos);
332
333 event_func& event_handler();
334 const event_func& event_handler() const;
335
340
348
356
364 multi_type_vector(size_type init_size);
365
375 template<typename T>
376 multi_type_vector(size_type init_size, const T& value);
377
391 template<typename T>
392 multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
393
400
407
412
429 position_type position(size_type pos);
430
450 position_type position(const iterator& pos_hint, size_type pos);
451
465 const_position_type position(size_type pos) const;
466
483 const_position_type position(const const_iterator& pos_hint, size_type pos) const;
484
509 iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
510
539 const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
540
557 template<typename T>
558 iterator set(size_type pos, const T& value);
559
592 template<typename T>
593 iterator set(const iterator& pos_hint, size_type pos, const T& value);
594
616 template<typename T>
617 iterator set(size_type pos, const T& it_begin, const T& it_end);
618
656 template<typename T>
657 iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
658
675 template<typename T>
676 iterator push_back(T&& value);
677
686
704 template<typename T, typename... Args>
705 iterator emplace_back(Args&&... args);
706
728 template<typename T>
729 iterator insert(size_type pos, const T& it_begin, const T& it_end);
730
768 template<typename T>
769 iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
770
778 mtv::element_t get_type(size_type pos) const;
779
791 bool is_empty(size_type pos) const;
792
806 iterator set_empty(size_type start_pos, size_type end_pos);
807
837 iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
838
854 void erase(size_type start_pos, size_type end_pos);
855
874 iterator insert_empty(size_type pos, size_type length);
875
910 iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
911
916 void clear();
917
923 size_type size() const;
924
942 size_type block_size() const;
943
949 bool empty() const;
950
961 template<typename T>
962 void get(size_type pos, T& value) const;
963
975 template<typename T>
976 T get(size_type pos) const;
977
992 template<typename T>
993 T release(size_type pos);
994
1011 template<typename T>
1012 iterator release(size_type pos, T& value);
1013
1033 template<typename T>
1034 iterator release(const iterator& pos_hint, size_type pos, T& value);
1035
1044 void release();
1045
1061 iterator release_range(size_type start_pos, size_type end_pos);
1062
1087 iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
1088
1089 iterator begin();
1090 iterator end();
1091
1092 const_iterator begin() const;
1093 const_iterator end() const;
1094
1095 const_iterator cbegin() const;
1096 const_iterator cend() const;
1097
1098 reverse_iterator rbegin();
1099 reverse_iterator rend();
1100
1101 const_reverse_iterator rbegin() const;
1102 const_reverse_iterator rend() const;
1103
1104 const_reverse_iterator crbegin() const;
1105 const_reverse_iterator crend() const;
1106
1114 void resize(size_type new_size);
1115
1122
1131 void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1132
1137
1138 bool operator==(const multi_type_vector& other) const;
1139 bool operator!=(const multi_type_vector& other) const;
1140
1141 multi_type_vector& operator=(const multi_type_vector& other);
1142 multi_type_vector& operator=(multi_type_vector&& other);
1143
1151 template<typename T>
1152 static mtv::element_t get_element_type(const T& elem);
1153
1154#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1155 void dump_blocks(std::ostream& os) const;
1156
1157 void check_block_integrity() const;
1158#endif
1159
1160private:
1161 void delete_element_block(size_type block_index);
1162
1163 void delete_element_blocks(size_type start, size_type end);
1164
1165 template<typename T>
1166 void get_impl(size_type pos, T& value) const;
1167
1168 template<typename T>
1169 bool set_cells_precheck(size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
1170
1171 template<typename T>
1172 iterator set_impl(size_type pos, size_type block_index, const T& value);
1173
1174 template<typename T>
1175 iterator release_impl(size_type pos, size_type block_index, T& value);
1176
1177 void swap_impl(
1178 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1179 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1180
1181 void swap_single_block(
1182 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1183 size_type other_block_index);
1184
1185 void swap_single_to_multi_blocks(
1186 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1187 size_type dst_block_index1, size_type dst_block_index2);
1188
1189 void swap_multi_to_multi_blocks(
1190 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1191 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1192
1193 template<typename T>
1194 iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1195
1196 void resize_impl(size_type new_size);
1197
1202 iterator transfer_multi_blocks(
1203 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1204 size_type dest_pos);
1205
1214 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1215
1216 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1217
1227 iterator set_empty_in_multi_blocks(
1228 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
1229
1230 void erase_impl(size_type start_pos, size_type end_pos);
1231 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1232
1238 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1239
1240 void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1241
1242 void prepare_blocks_to_transfer(
1243 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1244 size_type offset2);
1245
1246 iterator set_whole_block_empty(size_type block_index, bool overwrite);
1247
1248 template<typename T>
1249 iterator push_back_impl(T&& value);
1250
1251 template<typename T, typename... Args>
1252 iterator emplace_back_impl(Args&&... args);
1253
1254 template<typename T>
1255 iterator set_cells_impl(
1256 size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1257
1258 template<typename T>
1259 iterator set_cells_to_single_block(
1260 size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
1261
1262 template<typename T>
1263 iterator set_cells_to_multi_blocks(
1264 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1265 const T& it_end);
1266
1267 template<typename T>
1268 iterator set_cells_to_multi_blocks_block1_non_equal(
1269 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1270 const T& it_end);
1271
1272 template<typename T>
1273 iterator set_cells_to_multi_blocks_block1_non_empty(
1274 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1275 const T& it_end);
1276
1277 template<typename T>
1278 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1279
1280 template<typename T>
1281 iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
1282
1292 size_type get_block_position(size_type row, size_type start_block_index = 0) const;
1293
1298 size_type get_block_position(const typename value_type::private_data& pos_data, size_type row) const;
1299
1300 template<typename T>
1301 void create_new_block_with_new_cell(size_type block_index, T&& cell);
1302
1303 template<typename T, typename... Args>
1304 void create_new_block_with_emplace_back(size_type block_index, const T& t, Args&&... args);
1305
1306 template<typename T>
1307 void append_cell_to_block(size_type block_index, const T& cell);
1308
1316 template<typename T>
1317 bool append_to_prev_block(
1318 size_type block_index, element_category_type cat, size_type length, const T& it_begin, const T& it_end);
1319
1320 template<typename T>
1321 void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1322
1323 template<typename T>
1324 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
1325
1331 template<typename T>
1332 void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1333
1334 template<typename T>
1335 void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1336
1337 iterator transfer_impl(
1338 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1339
1343 iterator transfer_single_block(
1344 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1345
1354 size_type merge_with_adjacent_blocks(size_type block_index);
1355
1363 bool merge_with_next_block(size_type block_index);
1364
1378 size_type set_new_block_to_middle(
1379 size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1380
1390 bool is_previous_block_of_type(size_type block_index, element_category_type cat) const;
1391
1401 bool is_next_block_of_type(size_type block_index, element_category_type cat) const;
1402
1424 element_block_type* exchange_elements(
1425 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1426 size_type len);
1427
1428 void exchange_elements(
1429 const element_block_type& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1430 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1431
1432 bool append_empty(size_type len);
1433
1434 inline iterator get_iterator(size_type block_index)
1435 {
1436 auto iter_pos = m_block_store.positions.begin();
1437 std::advance(iter_pos, block_index);
1438 auto iter_size = m_block_store.sizes.begin();
1439 std::advance(iter_size, block_index);
1440 auto iter_elem = m_block_store.element_blocks.begin();
1441 std::advance(iter_elem, block_index);
1442
1443 return iterator(
1444 {iter_pos, iter_size, iter_elem},
1445 {m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()}, this,
1446 block_index);
1447 }
1448
1449 inline const_iterator get_const_iterator(size_type block_index) const
1450 {
1451 auto iter_pos = m_block_store.positions.cbegin();
1452 std::advance(iter_pos, block_index);
1453 auto iter_size = m_block_store.sizes.cbegin();
1454 std::advance(iter_size, block_index);
1455 auto iter_elem = m_block_store.element_blocks.cbegin();
1456 std::advance(iter_elem, block_index);
1457
1458 return const_iterator(
1459 {iter_pos, iter_size, iter_elem},
1460 {m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()}, this,
1461 block_index);
1462 }
1463
1464private:
1465 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1466
1467 event_func m_hdl_event;
1468 blocks_type m_block_store;
1469 size_type m_cur_size;
1470
1471#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1472 mutable int m_trace_call_depth = 0;
1473#endif
1474};
1475
1476}}} // namespace mdds::mtv::soa
1477
1478#include "main_def.inl"
1479
1480#endif
1481
1482/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition types.hpp:157
Definition types.hpp:168
Definition soa/iterator.hpp:310
Definition soa/iterator.hpp:234
Definition soa/main.hpp:73
iterator set(size_type pos, const T &value)
iterator set(size_type pos, const T &it_begin, const T &it_end)
iterator set(const iterator &pos_hint, size_type pos, const T &value)
multi_type_vector(multi_type_vector &&other)
iterator release_range(size_type start_pos, size_type end_pos)
static const_position_type advance_position(const const_position_type &pos, int steps)
multi_type_vector(size_type init_size, const T &it_begin, const T &it_end)
static position_type advance_position(const position_type &pos, int steps)
const_position_type position(size_type pos) const
multi_type_vector(event_func &&hdl)
multi_type_vector(size_type init_size)
iterator insert_empty(size_type pos, size_type length)
iterator transfer(const iterator &pos_hint, size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
static const_position_type next_position(const const_position_type &pos)
position_type position(size_type pos)
iterator insert(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
void resize(size_type new_size)
static size_type logical_position(const const_position_type &pos)
iterator insert(size_type pos, const T &it_begin, const T &it_end)
T get(size_type pos) const
position_type position(const iterator &pos_hint, size_type pos)
multi_type_vector(const event_func &hdl)
void get(size_type pos, T &value) const
static _Blk::value_type get(const const_position_type &pos)
iterator insert_empty(const iterator &pos_hint, size_type pos, size_type length)
iterator release(const iterator &pos_hint, size_type pos, T &value)
typename Traits::event_func event_func
Definition soa/main.hpp:98
iterator set_empty(const iterator &pos_hint, size_type start_pos, size_type end_pos)
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
multi_type_vector(const multi_type_vector &other)
iterator release_range(const iterator &pos_hint, size_type start_pos, size_type end_pos)
void erase(size_type start_pos, size_type end_pos)
multi_type_vector(size_type init_size, const T &value)
const_position_type position(const const_iterator &pos_hint, size_type pos) const
void swap(size_type start_pos, size_type end_pos, multi_type_vector &other, size_type other_pos)
iterator set(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
iterator release(size_type pos, T &value)
iterator emplace_back(Args &&... args)
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)
iterator set_empty(size_type start_pos, size_type end_pos)
void swap(multi_type_vector &other)
bool is_empty(size_type pos) const
Definition iterator_node.hpp:42
Definition iterator_node.hpp:109
Definition iterator_node.hpp:98