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 namespace mdds { namespace mtv { namespace soa {
39 
67 template<typename ElemBlockFunc, typename Trait = mdds::mtv::default_trait>
69 {
70 public:
71  using size_type = std::size_t;
72 
74  using element_category_type = mdds::mtv::element_t;
75  using element_block_func = ElemBlockFunc;
76 
94  using event_func = typename Trait::event_func;
95 
96 private:
97  struct block_slot_type
98  {
99  size_type position = 0;
100  size_type size = 0;
102 
103  block_slot_type() {}
104  block_slot_type(size_type _position, size_type _size) :
105  position(_position), size(_size) {}
106  };
107 
108  struct blocks_type
109  {
110  std::vector<size_type> positions;
111  std::vector<size_type> sizes;
112  std::vector<element_block_type*> element_blocks;
113 
114  blocks_type();
115  blocks_type(const blocks_type& other);
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, element_block_type* 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, element_block_type* 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);
155 
156  void swap(blocks_type& other);
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<element_block_type*>;
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 
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<element_block_type*>;
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 
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<element_block_type*>;
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<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<element_block_type*>;
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<size_type>;
227  };
228 
229  struct element_block_deleter
230  {
231  void operator() (const element_block_type* p)
232  {
233  element_block_func::delete_block(p);
234  }
235  };
236 
237 public:
238 
239  using iterator = detail::iterator_base<iterator_trait>;
240  using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
241 
242  using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
243  using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
244 
245  using position_type = std::pair<iterator, size_type>;
246  using const_position_type = std::pair<const_iterator, size_type>;
247 
264 
273  static position_type next_position(const position_type& pos);
274 
284  static position_type advance_position(const position_type& pos, int steps);
285 
294  static const_position_type next_position(const const_position_type& pos);
295 
305  static const_position_type advance_position(const const_position_type& pos, int steps);
306 
315  static size_type logical_position(const const_position_type& pos);
316 
325  template<typename _Blk>
326  static typename _Blk::value_type get(const const_position_type& pos);
327 
328  event_func& event_handler();
329  const event_func& event_handler() const;
330 
335 
336 
344 
352 
360  multi_type_vector(size_type init_size);
361 
371  template<typename T>
372  multi_type_vector(size_type init_size, const T& value);
373 
387  template<typename T>
388  multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
389 
396 
401 
418  position_type position(size_type pos);
419 
439  position_type position(const iterator& pos_hint, size_type pos);
440 
454  const_position_type position(size_type pos) const;
455 
472  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
473 
498  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
499 
527  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
528 
545  template<typename T>
546  iterator set(size_type pos, const T& value);
547 
580  template<typename T>
581  iterator set(const iterator& pos_hint, size_type pos, const T& value);
582 
604  template<typename T>
605  iterator set(size_type pos, const T& it_begin, const T& it_end);
606 
644  template<typename T>
645  iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
646 
656  template<typename T>
657  iterator push_back(const T& value);
658 
667 
689  template<typename T>
690  iterator insert(size_type pos, const T& it_begin, const T& it_end);
691 
729  template<typename T>
730  iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
731 
739  mtv::element_t get_type(size_type pos) const;
740 
752  bool is_empty(size_type pos) const;
753 
767  iterator set_empty(size_type start_pos, size_type end_pos);
768 
798  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
799 
815  void erase(size_type start_pos, size_type end_pos);
816 
835  iterator insert_empty(size_type pos, size_type length);
836 
871  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
872 
877  void clear();
878 
884  size_type size() const;
885 
903  size_type block_size() const;
904 
910  bool empty() const;
911 
922  template<typename T>
923  void get(size_type pos, T& value) const;
924 
936  template<typename T>
937  T get(size_type pos) const;
938 
953  template<typename T>
954  T release(size_type pos);
955 
972  template<typename T>
973  iterator release(size_type pos, T& value);
974 
994  template<typename T>
995  iterator release(const iterator& pos_hint, size_type pos, T& value);
996 
1005  void release();
1006 
1022  iterator release_range(size_type start_pos, size_type end_pos);
1023 
1048  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
1049 
1050  iterator begin();
1051  iterator end();
1052 
1053  const_iterator begin() const;
1054  const_iterator end() const;
1055 
1056  const_iterator cbegin() const;
1057  const_iterator cend() const;
1058 
1059  reverse_iterator rbegin();
1060  reverse_iterator rend();
1061 
1062  const_reverse_iterator rbegin() const;
1063  const_reverse_iterator rend() const;
1064 
1065  const_reverse_iterator crbegin() const;
1066  const_reverse_iterator crend() const;
1067 
1075  void resize(size_type new_size);
1076 
1082  void swap(multi_type_vector& other);
1083 
1092  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1093 
1098 
1099  bool operator== (const multi_type_vector& other) const;
1100  bool operator!= (const multi_type_vector& other) const;
1101 
1102  multi_type_vector& operator= (const multi_type_vector& other);
1103 
1111  template<typename T>
1112  static mtv::element_t get_element_type(const T& elem);
1113 
1114 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1115  void dump_blocks(std::ostream& os) const;
1116 
1117  void check_block_integrity() const;
1118 #endif
1119 
1120 private:
1121  void delete_element_block(size_type block_index);
1122 
1123  void delete_element_blocks(size_type start, size_type end);
1124 
1125  template<typename T>
1126  bool set_cells_precheck(
1127  size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
1128 
1129  template<typename T>
1130  iterator set_impl(size_type pos, size_type block_index, const T& value);
1131 
1132  template<typename T>
1133  iterator release_impl(size_type pos, size_type block_index, T& value);
1134 
1135  void swap_impl(
1136  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1137  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1138 
1139  void swap_single_block(
1140  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1141  size_type block_index, size_type other_block_index);
1142 
1143  void swap_single_to_multi_blocks(
1144  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1145  size_type block_index, size_type dst_block_index1, size_type dst_block_index2);
1146 
1147  void swap_multi_to_multi_blocks(
1148  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1149  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1150 
1151  template<typename T>
1152  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1153 
1154  void resize_impl(size_type new_size);
1155 
1160  iterator transfer_multi_blocks(
1161  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1162  multi_type_vector& dest, size_type dest_pos);
1163 
1172  iterator set_empty_impl(
1173  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1174 
1175  iterator set_empty_in_single_block(
1176  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1177 
1187  iterator set_empty_in_multi_blocks(
1188  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1189  bool overwrite);
1190 
1191  void erase_impl(size_type start_pos, size_type end_pos);
1192  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1193 
1199  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1200 
1201  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1202 
1203  void prepare_blocks_to_transfer(
1204  blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1205 
1206  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1207 
1208  template<typename T>
1209  iterator push_back_impl(const T& value);
1210 
1211  template<typename T>
1212  iterator set_cells_impl(
1213  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1214 
1215  template<typename T>
1216  iterator set_cells_to_single_block(
1217  size_type start_row, size_type end_row, size_type block_index,
1218  const T& it_begin, const T& it_end);
1219 
1220  template<typename T>
1221  iterator set_cells_to_multi_blocks(
1222  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1223  const T& it_begin, const T& it_end);
1224 
1225  template<typename T>
1226  iterator set_cells_to_multi_blocks_block1_non_equal(
1227  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1228  const T& it_begin, const T& it_end);
1229 
1230  template<typename T>
1231  iterator set_cells_to_multi_blocks_block1_non_empty(
1232  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1233  const T& it_begin, const T& it_end);
1234 
1235  template<typename T>
1236  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1237 
1238  template<typename T>
1239  iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
1240 
1250  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1251 
1256  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1257 
1258  template<typename T>
1259  void create_new_block_with_new_cell(size_type block_index, const T& cell);
1260 
1261  template<typename T>
1262  void append_cell_to_block(size_type block_index, const T& cell);
1263 
1271  template<typename T>
1272  bool append_to_prev_block(
1273  size_type block_index, element_category_type cat, size_type length,
1274  const T& it_begin, const T& it_end);
1275 
1276  template<typename T>
1277  void insert_cells_to_middle(
1278  size_type row, size_type block_index, const T& it_begin, const T& it_end);
1279 
1280  template<typename T>
1281  iterator set_cell_to_middle_of_block(
1282  size_type block_index, size_type pos_in_block, const T& cell);
1283 
1289  template<typename T>
1290  void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1291 
1292  template<typename T>
1293  void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1294 
1295  iterator transfer_impl(
1296  size_type start_pos, size_type end_pos, size_type block_index1,
1297  multi_type_vector& dest, size_type dest_pos);
1298 
1302  iterator transfer_single_block(
1303  size_type start_pos, size_type end_pos, size_type block_index1,
1304  multi_type_vector& dest, size_type dest_pos);
1305 
1314  size_type merge_with_adjacent_blocks(size_type block_index);
1315 
1323  bool merge_with_next_block(size_type block_index);
1324 
1338  size_type set_new_block_to_middle(
1339  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1340 
1350  bool is_previous_block_of_type(size_type block_index, element_category_type cat) const;
1351 
1361  bool is_next_block_of_type(size_type block_index, element_category_type cat) const;
1362 
1384  element_block_type* exchange_elements(
1385  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1386 
1387  void exchange_elements(
1388  const element_block_type& src_blk, size_type src_offset,
1389  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1390  size_type len, blocks_type& new_blocks);
1391 
1392  bool append_empty(size_type len);
1393 
1394  inline iterator get_iterator(size_type block_index)
1395  {
1396  auto iter_pos = m_block_store.positions.begin();
1397  std::advance(iter_pos, block_index);
1398  auto iter_size = m_block_store.sizes.begin();
1399  std::advance(iter_size, block_index);
1400  auto iter_elem = m_block_store.element_blocks.begin();
1401  std::advance(iter_elem, block_index);
1402 
1403  return iterator(
1404  { iter_pos, iter_size, iter_elem },
1405  { m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end() },
1406  block_index
1407  );
1408  }
1409 
1410  inline const_iterator get_const_iterator(size_type block_index) const
1411  {
1412  auto iter_pos = m_block_store.positions.cbegin();
1413  std::advance(iter_pos, block_index);
1414  auto iter_size = m_block_store.sizes.cbegin();
1415  std::advance(iter_size, block_index);
1416  auto iter_elem = m_block_store.element_blocks.cbegin();
1417  std::advance(iter_elem, block_index);
1418 
1419  return const_iterator(
1420  { iter_pos, iter_size, iter_elem },
1421  { m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend() },
1422  block_index
1423  );
1424  }
1425 
1426 private:
1427  using adjust_block_positions_func =
1428  detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1429 
1430  event_func m_hdl_event;
1431  blocks_type m_block_store;
1432  size_type m_cur_size;
1433 };
1434 
1435 }}}
1436 
1437 #include "main_def.inl"
1438 
1439 #endif
1440 
1441 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1442 
Definition: types.hpp:113
Definition: types.hpp:122
Definition: soa/iterator.hpp:314
Definition: soa/iterator.hpp:241
Definition: soa/main.hpp:69
iterator set(size_type pos, const T &value)
iterator release_range(const iterator &pos_hint, size_type start_pos, size_type end_pos)
multi_type_vector(event_func &&hdl)
iterator set_empty(const iterator &pos_hint, size_type start_pos, size_type end_pos)
void swap(size_type start_pos, size_type end_pos, multi_type_vector &other, size_type other_pos)
void swap(multi_type_vector &other)
multi_type_vector(const multi_type_vector &other)
static mtv::element_t get_element_type(const T &elem)
iterator set_empty(size_type start_pos, size_type end_pos)
static const_position_type advance_position(const const_position_type &pos, int steps)
const_position_type position(size_type pos) const
const_position_type position(const const_iterator &pos_hint, size_type pos) const
position_type position(size_type pos)
iterator set(size_type pos, const T &it_begin, const T &it_end)
static position_type advance_position(const position_type &pos, int steps)
multi_type_vector(size_type init_size)
iterator set(const iterator &pos_hint, size_type pos, const T &value)
iterator release(size_type pos, T &value)
mtv::element_t get_type(size_type pos) const
bool is_empty(size_type pos) const
iterator release(const iterator &pos_hint, size_type pos, T &value)
typename Trait::event_func event_func
Definition: soa/main.hpp:94
static position_type next_position(const position_type &pos)
iterator set(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
static size_type logical_position(const const_position_type &pos)
iterator insert_empty(const iterator &pos_hint, size_type pos, size_type length)
multi_type_vector(const event_func &hdl)
multi_type_vector(size_type init_size, const T &value)
iterator insert(size_type pos, const T &it_begin, const T &it_end)
multi_type_vector(size_type init_size, const T &it_begin, const T &it_end)
void get(size_type pos, T &value) const
void resize(size_type new_size)
iterator transfer(const iterator &pos_hint, size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
iterator insert_empty(size_type pos, size_type length)
iterator release_range(size_type start_pos, size_type end_pos)
T get(size_type pos) const
position_type position(const iterator &pos_hint, size_type pos)
iterator transfer(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)
iterator push_back(const T &value)
void erase(size_type start_pos, size_type end_pos)
iterator insert(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
static _Blk::value_type get(const const_position_type &pos)
Definition: iterator_node.hpp:101
Definition: iterator_node.hpp:92