mdds
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 Traits = mdds::mtv::default_traits>
73 {
74 public:
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 
100 private:
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 
243 public:
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 
347  multi_type_vector(const event_func& hdl);
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 
399  multi_type_vector(const multi_type_vector& other);
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 
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 
1109  void shrink_to_fit();
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(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 
1431 private:
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: */
static mtv::element_t get_element_type(const T &elem)
Definition: iterator_node.hpp:41
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
iterator set_empty(size_type start_pos, size_type end_pos)
Definition: iterator.hpp:233
static position_type next_position(const position_type &pos)
static position_type advance_position(const position_type &pos, int steps)
iterator release_range(size_type start_pos, size_type end_pos)
void swap(multi_type_vector &other)
static size_type logical_position(const const_position_type &pos)
Definition: iterator_node.hpp:108
iterator push_back(const T &value)
iterator set(size_type pos, const T &value)
Definition: types.hpp:373
Definition: iterator_node.hpp:97
void erase(size_type start_pos, size_type end_pos)
void resize(size_type new_size)
mtv::element_t get_type(size_type pos) const
Definition: flat_segment_tree.hpp:46
iterator insert_empty(size_type pos, size_type length)
typename mtv_trait::event_func event_func
Definition: main.hpp:98
position_type position(size_type pos)
bool is_empty(size_type pos) const
Definition: types.hpp:159
iterator insert(size_type pos, const T &it_begin, const T &it_end)
Definition: main.hpp:72