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  blocks_type(blocks_type&& other);
117 
118  void pop_back()
119  {
120  positions.pop_back();
121  sizes.pop_back();
122  element_blocks.pop_back();
123  }
124 
125  void push_back(size_type pos, size_type size, element_block_type* data)
126  {
127  positions.push_back(pos);
128  sizes.push_back(size);
129  element_blocks.push_back(data);
130  }
131 
132  void push_back(const block_slot_type& slot)
133  {
134  positions.push_back(slot.position);
135  sizes.push_back(slot.size);
136  element_blocks.push_back(slot.element_block);
137  }
138 
139  void erase(size_type index);
140  void erase(size_type index, size_type size);
141  void insert(size_type index, size_type size);
142  void insert(size_type index, size_type pos, size_type size, element_block_type* data);
143  void insert(size_type index, const blocks_type& new_blocks);
144 
151  void calc_block_position(size_type index);
152 
153  size_type calc_next_block_position(size_type index);
154 
155  void swap(size_type index1, size_type index2);
156 
157  void swap(blocks_type& other);
158 
159  void reserve(size_type n);
160 
161  bool equals(const blocks_type& other) const;
162 
163  void clear();
164 
165  void check_integrity() const;
166  };
167 
168  struct blocks_to_transfer
169  {
170  blocks_type blocks;
171  size_type insert_index = 0;
172  };
173 
174  struct iterator_trait
175  {
176  using parent = multi_type_vector;
177  using positions_type = std::vector<size_type>;
178  using sizes_type = std::vector<size_type>;
179  using element_blocks_type = std::vector<element_block_type*>;
180 
181  using positions_iterator_type = typename positions_type::iterator;
182  using sizes_iterator_type = typename sizes_type::iterator;
183  using element_blocks_iterator_type = typename element_blocks_type::iterator;
184 
186  };
187 
188  struct const_iterator_trait
189  {
190  using parent = multi_type_vector;
191  using positions_type = std::vector<size_type>;
192  using sizes_type = std::vector<size_type>;
193  using element_blocks_type = std::vector<element_block_type*>;
194 
195  using positions_iterator_type = typename positions_type::const_iterator;
196  using sizes_iterator_type = typename sizes_type::const_iterator;
197  using element_blocks_iterator_type = typename element_blocks_type::const_iterator;
198 
200  };
201 
202  struct reverse_iterator_trait
203  {
204  using parent = multi_type_vector;
205  using positions_type = std::vector<size_type>;
206  using sizes_type = std::vector<size_type>;
207  using element_blocks_type = std::vector<element_block_type*>;
208 
209  using positions_iterator_type = typename positions_type::reverse_iterator;
210  using sizes_iterator_type = typename sizes_type::reverse_iterator;
211  using element_blocks_iterator_type = typename element_blocks_type::reverse_iterator;
212 
213  using private_data_update = mdds::detail::mtv::private_data_no_update<size_type>;
214  };
215 
216  struct const_reverse_iterator_trait
217  {
218  using parent = multi_type_vector;
219  using positions_type = std::vector<size_type>;
220  using sizes_type = std::vector<size_type>;
221  using element_blocks_type = std::vector<element_block_type*>;
222 
223  using positions_iterator_type = typename positions_type::const_reverse_iterator;
224  using sizes_iterator_type = typename sizes_type::const_reverse_iterator;
225  using element_blocks_iterator_type = typename element_blocks_type::const_reverse_iterator;
226 
227  using private_data_update = mdds::detail::mtv::private_data_no_update<size_type>;
228  };
229 
230  struct element_block_deleter
231  {
232  void operator() (const element_block_type* p)
233  {
234  element_block_func::delete_block(p);
235  }
236  };
237 
238 public:
239 
240  using iterator = detail::iterator_base<iterator_trait>;
241  using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;
242 
243  using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
244  using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;
245 
246  using position_type = std::pair<iterator, size_type>;
247  using const_position_type = std::pair<const_iterator, size_type>;
248 
265 
274  static position_type next_position(const position_type& pos);
275 
285  static position_type advance_position(const position_type& pos, int steps);
286 
295  static const_position_type next_position(const const_position_type& pos);
296 
306  static const_position_type advance_position(const const_position_type& pos, int steps);
307 
316  static size_type logical_position(const const_position_type& pos);
317 
326  template<typename _Blk>
327  static typename _Blk::value_type get(const const_position_type& pos);
328 
329  event_func& event_handler();
330  const event_func& event_handler() const;
331 
336 
337 
345 
353 
361  multi_type_vector(size_type init_size);
362 
372  template<typename T>
373  multi_type_vector(size_type init_size, const T& value);
374 
388  template<typename T>
389  multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
390 
397 
404 
409 
426  position_type position(size_type pos);
427 
447  position_type position(const iterator& pos_hint, size_type pos);
448 
462  const_position_type position(size_type pos) const;
463 
480  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
481 
506  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
507 
535  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
536 
553  template<typename T>
554  iterator set(size_type pos, const T& value);
555 
588  template<typename T>
589  iterator set(const iterator& pos_hint, size_type pos, const T& value);
590 
612  template<typename T>
613  iterator set(size_type pos, const T& it_begin, const T& it_end);
614 
652  template<typename T>
653  iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
654 
664  template<typename T>
665  iterator push_back(const T& value);
666 
675 
697  template<typename T>
698  iterator insert(size_type pos, const T& it_begin, const T& it_end);
699 
737  template<typename T>
738  iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
739 
747  mtv::element_t get_type(size_type pos) const;
748 
760  bool is_empty(size_type pos) const;
761 
775  iterator set_empty(size_type start_pos, size_type end_pos);
776 
806  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
807 
823  void erase(size_type start_pos, size_type end_pos);
824 
843  iterator insert_empty(size_type pos, size_type length);
844 
879  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
880 
885  void clear();
886 
892  size_type size() const;
893 
911  size_type block_size() const;
912 
918  bool empty() const;
919 
930  template<typename T>
931  void get(size_type pos, T& value) const;
932 
944  template<typename T>
945  T get(size_type pos) const;
946 
961  template<typename T>
962  T release(size_type pos);
963 
980  template<typename T>
981  iterator release(size_type pos, T& value);
982 
1002  template<typename T>
1003  iterator release(const iterator& pos_hint, size_type pos, T& value);
1004 
1013  void release();
1014 
1030  iterator release_range(size_type start_pos, size_type end_pos);
1031 
1056  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
1057 
1058  iterator begin();
1059  iterator end();
1060 
1061  const_iterator begin() const;
1062  const_iterator end() const;
1063 
1064  const_iterator cbegin() const;
1065  const_iterator cend() const;
1066 
1067  reverse_iterator rbegin();
1068  reverse_iterator rend();
1069 
1070  const_reverse_iterator rbegin() const;
1071  const_reverse_iterator rend() const;
1072 
1073  const_reverse_iterator crbegin() const;
1074  const_reverse_iterator crend() const;
1075 
1083  void resize(size_type new_size);
1084 
1090  void swap(multi_type_vector& other);
1091 
1100  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1101 
1106 
1107  bool operator== (const multi_type_vector& other) const;
1108  bool operator!= (const multi_type_vector& other) const;
1109 
1110  multi_type_vector& operator= (const multi_type_vector& other);
1111  multi_type_vector& operator= (multi_type_vector&& other);
1112 
1120  template<typename T>
1121  static mtv::element_t get_element_type(const T& elem);
1122 
1123 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1124  void dump_blocks(std::ostream& os) const;
1125 
1126  void check_block_integrity() const;
1127 #endif
1128 
1129 private:
1130  void delete_element_block(size_type block_index);
1131 
1132  void delete_element_blocks(size_type start, size_type end);
1133 
1134  template<typename T>
1135  bool set_cells_precheck(
1136  size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
1137 
1138  template<typename T>
1139  iterator set_impl(size_type pos, size_type block_index, const T& value);
1140 
1141  template<typename T>
1142  iterator release_impl(size_type pos, size_type block_index, T& value);
1143 
1144  void swap_impl(
1145  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1146  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1147 
1148  void swap_single_block(
1149  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1150  size_type block_index, size_type other_block_index);
1151 
1152  void swap_single_to_multi_blocks(
1153  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1154  size_type block_index, size_type dst_block_index1, size_type dst_block_index2);
1155 
1156  void swap_multi_to_multi_blocks(
1157  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1158  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1159 
1160  template<typename T>
1161  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1162 
1163  void resize_impl(size_type new_size);
1164 
1169  iterator transfer_multi_blocks(
1170  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1171  multi_type_vector& dest, size_type dest_pos);
1172 
1181  iterator set_empty_impl(
1182  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1183 
1184  iterator set_empty_in_single_block(
1185  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1186 
1196  iterator set_empty_in_multi_blocks(
1197  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1198  bool overwrite);
1199 
1200  void erase_impl(size_type start_pos, size_type end_pos);
1201  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1202 
1208  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1209 
1210  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1211 
1212  void prepare_blocks_to_transfer(
1213  blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1214 
1215  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1216 
1217  template<typename T>
1218  iterator push_back_impl(const T& value);
1219 
1220  template<typename T>
1221  iterator set_cells_impl(
1222  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1223 
1224  template<typename T>
1225  iterator set_cells_to_single_block(
1226  size_type start_row, size_type end_row, size_type block_index,
1227  const T& it_begin, const T& it_end);
1228 
1229  template<typename T>
1230  iterator set_cells_to_multi_blocks(
1231  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1232  const T& it_begin, const T& it_end);
1233 
1234  template<typename T>
1235  iterator set_cells_to_multi_blocks_block1_non_equal(
1236  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1237  const T& it_begin, const T& it_end);
1238 
1239  template<typename T>
1240  iterator set_cells_to_multi_blocks_block1_non_empty(
1241  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1242  const T& it_begin, const T& it_end);
1243 
1244  template<typename T>
1245  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1246 
1247  template<typename T>
1248  iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
1249 
1259  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1260 
1265  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1266 
1267  template<typename T>
1268  void create_new_block_with_new_cell(size_type block_index, const T& cell);
1269 
1270  template<typename T>
1271  void append_cell_to_block(size_type block_index, const T& cell);
1272 
1280  template<typename T>
1281  bool append_to_prev_block(
1282  size_type block_index, element_category_type cat, size_type length,
1283  const T& it_begin, const T& it_end);
1284 
1285  template<typename T>
1286  void insert_cells_to_middle(
1287  size_type row, size_type block_index, const T& it_begin, const T& it_end);
1288 
1289  template<typename T>
1290  iterator set_cell_to_middle_of_block(
1291  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,
1306  multi_type_vector& dest, size_type dest_pos);
1307 
1311  iterator transfer_single_block(
1312  size_type start_pos, size_type end_pos, size_type block_index1,
1313  multi_type_vector& dest, size_type dest_pos);
1314 
1323  size_type merge_with_adjacent_blocks(size_type block_index);
1324 
1332  bool merge_with_next_block(size_type block_index);
1333 
1347  size_type set_new_block_to_middle(
1348  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1349 
1359  bool is_previous_block_of_type(size_type block_index, element_category_type cat) const;
1360 
1370  bool is_next_block_of_type(size_type block_index, element_category_type cat) const;
1371 
1393  element_block_type* exchange_elements(
1394  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1395 
1396  void exchange_elements(
1397  const element_block_type& src_blk, size_type src_offset,
1398  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1399  size_type len, blocks_type& new_blocks);
1400 
1401  bool append_empty(size_type len);
1402 
1403  inline iterator get_iterator(size_type block_index)
1404  {
1405  auto iter_pos = m_block_store.positions.begin();
1406  std::advance(iter_pos, block_index);
1407  auto iter_size = m_block_store.sizes.begin();
1408  std::advance(iter_size, block_index);
1409  auto iter_elem = m_block_store.element_blocks.begin();
1410  std::advance(iter_elem, block_index);
1411 
1412  return iterator(
1413  { iter_pos, iter_size, iter_elem },
1414  { m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end() },
1415  block_index
1416  );
1417  }
1418 
1419  inline const_iterator get_const_iterator(size_type block_index) const
1420  {
1421  auto iter_pos = m_block_store.positions.cbegin();
1422  std::advance(iter_pos, block_index);
1423  auto iter_size = m_block_store.sizes.cbegin();
1424  std::advance(iter_size, block_index);
1425  auto iter_elem = m_block_store.element_blocks.cbegin();
1426  std::advance(iter_elem, block_index);
1427 
1428  return const_iterator(
1429  { iter_pos, iter_size, iter_elem },
1430  { m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend() },
1431  block_index
1432  );
1433  }
1434 
1435 private:
1436  using adjust_block_positions_func =
1437  detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1438 
1439  event_func m_hdl_event;
1440  blocks_type m_block_store;
1441  size_type m_cur_size;
1442 };
1443 
1444 }}}
1445 
1446 #include "main_def.inl"
1447 
1448 #endif
1449 
1450 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1451 
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
multi_type_vector(multi_type_vector &&other)
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