mdds
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
668 template<typename T>
669 iterator push_back(const T& value);
670
679
701 template<typename T>
702 iterator insert(size_type pos, const T& it_begin, const T& it_end);
703
741 template<typename T>
742 iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
743
751 mtv::element_t get_type(size_type pos) const;
752
764 bool is_empty(size_type pos) const;
765
779 iterator set_empty(size_type start_pos, size_type end_pos);
780
810 iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
811
827 void erase(size_type start_pos, size_type end_pos);
828
847 iterator insert_empty(size_type pos, size_type length);
848
883 iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
884
889 void clear();
890
896 size_type size() const;
897
915 size_type block_size() const;
916
922 bool empty() const;
923
934 template<typename T>
935 void get(size_type pos, T& value) const;
936
948 template<typename T>
949 T get(size_type pos) const;
950
965 template<typename T>
966 T release(size_type pos);
967
984 template<typename T>
985 iterator release(size_type pos, T& value);
986
1006 template<typename T>
1007 iterator release(const iterator& pos_hint, size_type pos, T& value);
1008
1017 void release();
1018
1034 iterator release_range(size_type start_pos, size_type end_pos);
1035
1060 iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
1061
1062 iterator begin();
1063 iterator end();
1064
1065 const_iterator begin() const;
1066 const_iterator end() const;
1067
1068 const_iterator cbegin() const;
1069 const_iterator cend() const;
1070
1071 reverse_iterator rbegin();
1072 reverse_iterator rend();
1073
1074 const_reverse_iterator rbegin() const;
1075 const_reverse_iterator rend() const;
1076
1077 const_reverse_iterator crbegin() const;
1078 const_reverse_iterator crend() const;
1079
1087 void resize(size_type new_size);
1088
1095
1104 void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1105
1110
1111 bool operator==(const multi_type_vector& other) const;
1112 bool operator!=(const multi_type_vector& other) const;
1113
1114 multi_type_vector& operator=(const multi_type_vector& other);
1115 multi_type_vector& operator=(multi_type_vector&& other);
1116
1124 template<typename T>
1125 static mtv::element_t get_element_type(const T& elem);
1126
1127#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1128 void dump_blocks(std::ostream& os) const;
1129
1130 void check_block_integrity() const;
1131#endif
1132
1133private:
1134 void delete_element_block(size_type block_index);
1135
1136 void delete_element_blocks(size_type start, size_type end);
1137
1138 template<typename T>
1139 void get_impl(size_type pos, T& value) const;
1140
1141 template<typename T>
1142 bool set_cells_precheck(size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
1143
1144 template<typename T>
1145 iterator set_impl(size_type pos, size_type block_index, const T& value);
1146
1147 template<typename T>
1148 iterator release_impl(size_type pos, size_type block_index, T& value);
1149
1150 void swap_impl(
1151 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1152 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1153
1154 void swap_single_block(
1155 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1156 size_type other_block_index);
1157
1158 void swap_single_to_multi_blocks(
1159 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1160 size_type dst_block_index1, size_type dst_block_index2);
1161
1162 void swap_multi_to_multi_blocks(
1163 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1164 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1165
1166 template<typename T>
1167 iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1168
1169 void resize_impl(size_type new_size);
1170
1175 iterator transfer_multi_blocks(
1176 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1177 size_type dest_pos);
1178
1187 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1188
1189 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1190
1200 iterator set_empty_in_multi_blocks(
1201 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
1202
1203 void erase_impl(size_type start_pos, size_type end_pos);
1204 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1205
1211 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1212
1213 void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1214
1215 void prepare_blocks_to_transfer(
1216 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1217 size_type offset2);
1218
1219 iterator set_whole_block_empty(size_type block_index, bool overwrite);
1220
1221 template<typename T>
1222 iterator push_back_impl(const T& value);
1223
1224 template<typename T>
1225 iterator set_cells_impl(
1226 size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1227
1228 template<typename T>
1229 iterator set_cells_to_single_block(
1230 size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
1231
1232 template<typename T>
1233 iterator set_cells_to_multi_blocks(
1234 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1235 const T& it_end);
1236
1237 template<typename T>
1238 iterator set_cells_to_multi_blocks_block1_non_equal(
1239 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1240 const T& it_end);
1241
1242 template<typename T>
1243 iterator set_cells_to_multi_blocks_block1_non_empty(
1244 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1245 const T& it_end);
1246
1247 template<typename T>
1248 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1249
1250 template<typename T>
1251 iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
1252
1262 size_type get_block_position(size_type row, size_type start_block_index = 0) const;
1263
1268 size_type get_block_position(const typename value_type::private_data& pos_data, size_type row) const;
1269
1270 template<typename T>
1271 void create_new_block_with_new_cell(size_type block_index, const T& cell);
1272
1273 template<typename T>
1274 void append_cell_to_block(size_type block_index, const T& cell);
1275
1283 template<typename T>
1284 bool append_to_prev_block(
1285 size_type block_index, element_category_type cat, size_type length, const T& it_begin, const T& it_end);
1286
1287 template<typename T>
1288 void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1289
1290 template<typename T>
1291 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
1292
1298 template<typename T>
1299 void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1300
1301 template<typename T>
1302 void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1303
1304 iterator transfer_impl(
1305 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1306
1310 iterator transfer_single_block(
1311 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1312
1321 size_type merge_with_adjacent_blocks(size_type block_index);
1322
1330 bool merge_with_next_block(size_type block_index);
1331
1345 size_type set_new_block_to_middle(
1346 size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1347
1357 bool is_previous_block_of_type(size_type block_index, element_category_type cat) const;
1358
1368 bool is_next_block_of_type(size_type block_index, element_category_type cat) const;
1369
1391 element_block_type* exchange_elements(
1392 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1393 size_type len);
1394
1395 void exchange_elements(
1396 const element_block_type& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1397 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1398
1399 bool append_empty(size_type len);
1400
1401 inline iterator get_iterator(size_type block_index)
1402 {
1403 auto iter_pos = m_block_store.positions.begin();
1404 std::advance(iter_pos, block_index);
1405 auto iter_size = m_block_store.sizes.begin();
1406 std::advance(iter_size, block_index);
1407 auto iter_elem = m_block_store.element_blocks.begin();
1408 std::advance(iter_elem, block_index);
1409
1410 return iterator(
1411 {iter_pos, iter_size, iter_elem},
1412 {m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()}, this,
1413 block_index);
1414 }
1415
1416 inline const_iterator get_const_iterator(size_type block_index) const
1417 {
1418 auto iter_pos = m_block_store.positions.cbegin();
1419 std::advance(iter_pos, block_index);
1420 auto iter_size = m_block_store.sizes.cbegin();
1421 std::advance(iter_size, block_index);
1422 auto iter_elem = m_block_store.element_blocks.cbegin();
1423 std::advance(iter_elem, block_index);
1424
1425 return const_iterator(
1426 {iter_pos, iter_size, iter_elem},
1427 {m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()}, this,
1428 block_index);
1429 }
1430
1431private:
1432 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1433
1434 event_func m_hdl_event;
1435 blocks_type m_block_store;
1436 size_type m_cur_size;
1437
1438#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1439 mutable int m_trace_call_depth = 0;
1440#endif
1441};
1442
1443}}} // namespace mdds::mtv::soa
1444
1445#include "main_def.inl"
1446
1447#endif
1448
1449/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: types.hpp:160
Definition: types.hpp:374
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)
iterator push_back(const T &value)
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)
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