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 
42 namespace mdds { namespace mtv { namespace soa {
43 
71 template<typename ElemBlockFunc, typename Trait = mdds::mtv::default_trait>
73 {
74 public:
75  using size_type = std::size_t;
76 
78  using element_category_type = mdds::mtv::element_t;
79  using element_block_func = ElemBlockFunc;
80 
98  using event_func = typename Trait::event_func;
99 
100 private:
101  struct block_slot_type
102  {
103  size_type position = 0;
104  size_type size = 0;
106 
107  block_slot_type() {}
108  block_slot_type(size_type _position, size_type _size) :
109  position(_position), size(_size) {}
110  };
111 
112  struct blocks_type
113  {
114  std::vector<size_type> positions;
115  std::vector<size_type> sizes;
116  std::vector<element_block_type*> element_blocks;
117 
118  blocks_type();
119  blocks_type(const blocks_type& other);
120  blocks_type(blocks_type&& other);
121 
122  void pop_back()
123  {
124  positions.pop_back();
125  sizes.pop_back();
126  element_blocks.pop_back();
127  }
128 
129  void push_back(size_type pos, size_type size, element_block_type* data)
130  {
131  positions.push_back(pos);
132  sizes.push_back(size);
133  element_blocks.push_back(data);
134  }
135 
136  void push_back(const block_slot_type& slot)
137  {
138  positions.push_back(slot.position);
139  sizes.push_back(slot.size);
140  element_blocks.push_back(slot.element_block);
141  }
142 
143  void erase(size_type index);
144  void erase(size_type index, size_type size);
145  void insert(size_type index, size_type size);
146  void insert(size_type index, size_type pos, size_type size, element_block_type* data);
147  void insert(size_type index, const blocks_type& new_blocks);
148 
155  void calc_block_position(size_type index);
156 
157  size_type calc_next_block_position(size_type index);
158 
159  void swap(size_type index1, size_type index2);
160 
161  void swap(blocks_type& other);
162 
163  void reserve(size_type n);
164 
165  bool equals(const blocks_type& other) const;
166 
167  void clear();
168 
169  void check_integrity() const;
170  };
171 
172  struct blocks_to_transfer
173  {
174  blocks_type blocks;
175  size_type insert_index = 0;
176  };
177 
178  struct iterator_trait
179  {
180  using parent = multi_type_vector;
181  using positions_type = std::vector<size_type>;
182  using sizes_type = std::vector<size_type>;
183  using element_blocks_type = std::vector<element_block_type*>;
184 
185  using positions_iterator_type = typename positions_type::iterator;
186  using sizes_iterator_type = typename sizes_type::iterator;
187  using element_blocks_iterator_type = typename element_blocks_type::iterator;
188 
190  };
191 
192  struct const_iterator_trait
193  {
194  using parent = multi_type_vector;
195  using positions_type = std::vector<size_type>;
196  using sizes_type = std::vector<size_type>;
197  using element_blocks_type = std::vector<element_block_type*>;
198 
199  using positions_iterator_type = typename positions_type::const_iterator;
200  using sizes_iterator_type = typename sizes_type::const_iterator;
201  using element_blocks_iterator_type = typename element_blocks_type::const_iterator;
202 
204  };
205 
206  struct reverse_iterator_trait
207  {
208  using parent = multi_type_vector;
209  using positions_type = std::vector<size_type>;
210  using sizes_type = std::vector<size_type>;
211  using element_blocks_type = std::vector<element_block_type*>;
212 
213  using positions_iterator_type = typename positions_type::reverse_iterator;
214  using sizes_iterator_type = typename sizes_type::reverse_iterator;
215  using element_blocks_iterator_type = typename element_blocks_type::reverse_iterator;
216 
217  using private_data_update = mdds::detail::mtv::private_data_no_update<size_type>;
218  };
219 
220  struct const_reverse_iterator_trait
221  {
222  using parent = multi_type_vector;
223  using positions_type = std::vector<size_type>;
224  using sizes_type = std::vector<size_type>;
225  using element_blocks_type = std::vector<element_block_type*>;
226 
227  using positions_iterator_type = typename positions_type::const_reverse_iterator;
228  using sizes_iterator_type = typename sizes_type::const_reverse_iterator;
229  using element_blocks_iterator_type = typename element_blocks_type::const_reverse_iterator;
230 
231  using private_data_update = mdds::detail::mtv::private_data_no_update<size_type>;
232  };
233 
234  struct element_block_deleter
235  {
236  void operator() (const element_block_type* p)
237  {
238  element_block_func::delete_block(p);
239  }
240  };
241 
242 public:
243 
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 
341 
349 
357 
365  multi_type_vector(size_type init_size);
366 
376  template<typename T>
377  multi_type_vector(size_type init_size, const T& value);
378 
392  template<typename T>
393  multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
394 
401 
408 
413 
430  position_type position(size_type pos);
431 
451  position_type position(const iterator& pos_hint, size_type pos);
452 
466  const_position_type position(size_type pos) const;
467 
484  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
485 
510  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
511 
539  iterator transfer(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 
1094  void swap(multi_type_vector& other);
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 
1133 private:
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(
1143  size_type row, const T& it_begin, const T& it_end, size_type& end_pos);
1144 
1145  template<typename T>
1146  iterator set_impl(size_type pos, size_type block_index, const T& value);
1147 
1148  template<typename T>
1149  iterator release_impl(size_type pos, size_type block_index, T& value);
1150 
1151  void swap_impl(
1152  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1153  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1154 
1155  void swap_single_block(
1156  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1157  size_type block_index, size_type other_block_index);
1158 
1159  void swap_single_to_multi_blocks(
1160  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1161  size_type block_index, size_type dst_block_index1, size_type dst_block_index2);
1162 
1163  void swap_multi_to_multi_blocks(
1164  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1165  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1166 
1167  template<typename T>
1168  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1169 
1170  void resize_impl(size_type new_size);
1171 
1176  iterator transfer_multi_blocks(
1177  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1178  multi_type_vector& dest, size_type dest_pos);
1179 
1188  iterator set_empty_impl(
1189  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1190 
1191  iterator set_empty_in_single_block(
1192  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1193 
1203  iterator set_empty_in_multi_blocks(
1204  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1205  bool overwrite);
1206 
1207  void erase_impl(size_type start_pos, size_type end_pos);
1208  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);
1209 
1215  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1216 
1217  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1218 
1219  void prepare_blocks_to_transfer(
1220  blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1221 
1222  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1223 
1224  template<typename T>
1225  iterator push_back_impl(const T& value);
1226 
1227  template<typename T>
1228  iterator set_cells_impl(
1229  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1230 
1231  template<typename T>
1232  iterator set_cells_to_single_block(
1233  size_type start_row, size_type end_row, size_type block_index,
1234  const T& it_begin, const T& it_end);
1235 
1236  template<typename T>
1237  iterator set_cells_to_multi_blocks(
1238  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1239  const T& it_begin, const T& it_end);
1240 
1241  template<typename T>
1242  iterator set_cells_to_multi_blocks_block1_non_equal(
1243  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1244  const T& it_begin, const T& it_end);
1245 
1246  template<typename T>
1247  iterator set_cells_to_multi_blocks_block1_non_empty(
1248  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1249  const T& it_begin, const T& it_end);
1250 
1251  template<typename T>
1252  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1253 
1254  template<typename T>
1255  iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);
1256 
1266  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1267 
1272  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1273 
1274  template<typename T>
1275  void create_new_block_with_new_cell(size_type block_index, const T& cell);
1276 
1277  template<typename T>
1278  void append_cell_to_block(size_type block_index, const T& cell);
1279 
1287  template<typename T>
1288  bool append_to_prev_block(
1289  size_type block_index, element_category_type cat, size_type length,
1290  const T& it_begin, const T& it_end);
1291 
1292  template<typename T>
1293  void insert_cells_to_middle(
1294  size_type row, size_type block_index, const T& it_begin, const T& it_end);
1295 
1296  template<typename T>
1297  iterator set_cell_to_middle_of_block(
1298  size_type block_index, size_type pos_in_block, const T& cell);
1299 
1305  template<typename T>
1306  void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1307 
1308  template<typename T>
1309  void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1310 
1311  iterator transfer_impl(
1312  size_type start_pos, size_type end_pos, size_type block_index1,
1313  multi_type_vector& dest, size_type dest_pos);
1314 
1318  iterator transfer_single_block(
1319  size_type start_pos, size_type end_pos, size_type block_index1,
1320  multi_type_vector& dest, size_type dest_pos);
1321 
1330  size_type merge_with_adjacent_blocks(size_type block_index);
1331 
1339  bool merge_with_next_block(size_type block_index);
1340 
1354  size_type set_new_block_to_middle(
1355  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1356 
1366  bool is_previous_block_of_type(size_type block_index, element_category_type cat) const;
1367 
1377  bool is_next_block_of_type(size_type block_index, element_category_type cat) const;
1378 
1400  element_block_type* exchange_elements(
1401  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1402 
1403  void exchange_elements(
1404  const element_block_type& src_blk, size_type src_offset,
1405  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1406  size_type len, blocks_type& new_blocks);
1407 
1408  bool append_empty(size_type len);
1409 
1410  inline iterator get_iterator(size_type block_index)
1411  {
1412  auto iter_pos = m_block_store.positions.begin();
1413  std::advance(iter_pos, block_index);
1414  auto iter_size = m_block_store.sizes.begin();
1415  std::advance(iter_size, block_index);
1416  auto iter_elem = m_block_store.element_blocks.begin();
1417  std::advance(iter_elem, block_index);
1418 
1419  return iterator(
1420  { iter_pos, iter_size, iter_elem },
1421  { m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end() },
1422  block_index
1423  );
1424  }
1425 
1426  inline const_iterator get_const_iterator(size_type block_index) const
1427  {
1428  auto iter_pos = m_block_store.positions.cbegin();
1429  std::advance(iter_pos, block_index);
1430  auto iter_size = m_block_store.sizes.cbegin();
1431  std::advance(iter_size, block_index);
1432  auto iter_elem = m_block_store.element_blocks.cbegin();
1433  std::advance(iter_elem, block_index);
1434 
1435  return const_iterator(
1436  { iter_pos, iter_size, iter_elem },
1437  { m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend() },
1438  block_index
1439  );
1440  }
1441 
1442 private:
1443  using adjust_block_positions_func =
1444  detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1445 
1446  event_func m_hdl_event;
1447  blocks_type m_block_store;
1448  size_type m_cur_size;
1449 
1450 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1451  mutable int m_trace_call_depth = 0;
1452 #endif
1453 };
1454 
1455 }}}
1456 
1457 #include "main_def.inl"
1458 
1459 #endif
1460 
1461 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1462 
Definition: types.hpp:173
Definition: types.hpp:182
Definition: soa/iterator.hpp:314
Definition: soa/iterator.hpp:241
Definition: soa/main.hpp:73
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:98
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