mdds
aos/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_DIR_AOS_MAIN_HPP
30 #define INCLUDED_MDDS_MULTI_TYPE_VECTOR_DIR_AOS_MAIN_HPP
31 
32 #include "../../global.hpp"
33 #include "../types.hpp"
34 #include "../util.hpp"
35 #include "./iterator.hpp"
36 #include "./block_util.hpp"
37 
38 namespace mdds { namespace mtv { namespace aos {
39 
67 template<typename ElemBlockFunc, typename Trait = mdds::mtv::default_trait>
69 {
70 public:
71  typedef size_t size_type;
72 
74  typedef mdds::mtv::element_t element_category_type;
75  typedef ElemBlockFunc element_block_func;
76 
94  using event_func = typename Trait::event_func;
95 
96 private:
97 
98  struct block
99  {
100  size_type position;
101  size_type size;
102  element_block_type* data;
103 
104  block();
105  block(size_type _position, size_type _size);
106  block(size_type _position, size_type _size, element_block_type* _data);
107  block(const block& other) = default;
108  block(block&& other) = default;
109  ~block() = default;
110  void swap(block& other);
111  void clone_to(block& other) const;
112 
113  block& operator=(const block&) = default;
114  };
115 
116  struct element_block_deleter
117  {
118  void operator() (const element_block_type* p)
119  {
120  element_block_func::delete_block(p);
121  }
122  };
123 
124  typedef std::vector<block> blocks_type;
125 
126  struct blocks_to_transfer
127  {
128  blocks_type blocks;
129  size_type insert_index;
130 
131  blocks_to_transfer();
132  };
133 
134  struct iterator_trait
135  {
136  typedef multi_type_vector parent;
137  typedef blocks_type blocks;
138  typedef typename blocks_type::iterator base_iterator;
139  };
140 
141  struct reverse_iterator_trait
142  {
143  typedef multi_type_vector parent;
144  typedef blocks_type blocks;
145  typedef typename blocks_type::reverse_iterator base_iterator;
146  };
147 
148  struct const_iterator_trait
149  {
150  typedef multi_type_vector parent;
151  typedef blocks_type blocks;
152  typedef typename blocks_type::const_iterator base_iterator;
153  };
154 
155  struct const_reverse_iterator_trait
156  {
157  typedef multi_type_vector parent;
158  typedef blocks_type blocks;
159  typedef typename blocks_type::const_reverse_iterator base_iterator;
160  };
161 
165 
166 public:
167 
168  typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
169  typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
170 
171  typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
172  typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator> const_reverse_iterator;
173 
190 
191  typedef std::pair<iterator, size_type> position_type;
192  typedef std::pair<const_iterator, size_type> const_position_type;
193 
202  static position_type next_position(const position_type& pos);
203 
213  static position_type advance_position(const position_type& pos, int steps);
214 
223  static const_position_type next_position(const const_position_type& pos);
224 
234  static const_position_type advance_position(const const_position_type& pos, int steps);
235 
244  static size_type logical_position(const const_position_type& pos);
245 
254  template<typename Blk>
255  static typename Blk::value_type get(const const_position_type& pos);
256 
257  iterator begin();
258  iterator end();
259 
260  const_iterator begin() const;
261  const_iterator end() const;
262 
263  const_iterator cbegin() const;
264  const_iterator cend() const;
265 
266  reverse_iterator rbegin();
267  reverse_iterator rend();
268 
269  const_reverse_iterator rbegin() const;
270  const_reverse_iterator rend() const;
271 
272  const_reverse_iterator crbegin() const;
273  const_reverse_iterator crend() const;
274 
275  event_func& event_handler();
276  const event_func& event_handler() const;
277 
282 
290 
298 
306  multi_type_vector(size_type init_size);
307 
317  template<typename T>
318  multi_type_vector(size_type init_size, const T& value);
319 
333  template<typename T>
334  multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
335 
342 
349 
354 
371  template<typename T>
372  iterator set(size_type pos, const T& value);
373 
406  template<typename T>
407  iterator set(const iterator& pos_hint, size_type pos, const T& value);
408 
430  template<typename T>
431  iterator set(size_type pos, const T& it_begin, const T& it_end);
432 
470  template<typename T>
471  iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
472 
482  template<typename T>
483  iterator push_back(const T& value);
484 
493 
515  template<typename T>
516  iterator insert(size_type pos, const T& it_begin, const T& it_end);
517 
555  template<typename T>
556  iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
557 
568  template<typename T>
569  void get(size_type pos, T& value) const;
570 
582  template<typename T>
583  T get(size_type pos) const;
584 
599  template<typename T>
600  T release(size_type pos);
601 
618  template<typename T>
619  iterator release(size_type pos, T& value);
620 
640  template<typename T>
641  iterator release(const iterator& pos_hint, size_type pos, T& value);
642 
651  void release();
652 
668  iterator release_range(size_type start_pos, size_type end_pos);
669 
694  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
695 
712  position_type position(size_type pos);
713 
733  position_type position(const iterator& pos_hint, size_type pos);
734 
748  const_position_type position(size_type pos) const;
749 
766  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
767 
792  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
793 
821  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
822 
830  mtv::element_t get_type(size_type pos) const;
831 
843  bool is_empty(size_type pos) const;
844 
858  iterator set_empty(size_type start_pos, size_type end_pos);
859 
889  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
890 
906  void erase(size_type start_pos, size_type end_pos);
907 
926  iterator insert_empty(size_type pos, size_type length);
927 
962  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
963 
968  void clear();
969 
975  size_type size() const;
976 
994  size_type block_size() const;
995 
1001  bool empty() const;
1002 
1010  void resize(size_type new_size);
1011 
1017  void swap(multi_type_vector& other);
1018 
1027  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1028 
1033 
1034  bool operator== (const multi_type_vector& other) const;
1035  bool operator!= (const multi_type_vector& other) const;
1036 
1037  multi_type_vector& operator= (const multi_type_vector& other);
1038  multi_type_vector& operator= (multi_type_vector&& other);
1039 
1047  template<typename T>
1048  static mtv::element_t get_element_type(const T& elem);
1049 
1050 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1051  void dump_blocks(std::ostream& os) const;
1052 
1053  void check_block_integrity() const;
1054 #endif
1055 
1056 private:
1057 
1064  void delete_element_block(block& blk);
1065 
1073  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1074 
1075  template<typename T>
1076  iterator set_impl(size_type pos, size_type block_index, const T& value);
1077 
1078  template<typename T>
1079  iterator release_impl(size_type pos, size_type block_index, T& value);
1080 
1081  template<typename T>
1082  iterator push_back_impl(const T& value);
1083 
1093  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1094 
1099  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1100 
1101  void resize_impl(size_type new_size);
1102 
1103  template<typename T>
1104  void create_new_block_with_new_cell(element_block_type*& data, const T& cell);
1105 
1106  template<typename T>
1107  iterator set_cell_to_middle_of_block(
1108  size_type block_index, size_type pos_in_block, const T& cell);
1109 
1110  template<typename T>
1111  void append_cell_to_block(size_type block_index, const T& cell);
1112 
1113  template<typename T>
1114  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1115 
1116  template<typename T>
1117  iterator set_cell_to_block_of_size_one(
1118  size_type block_index, const T& cell);
1119 
1120  template<typename T>
1121  void set_cell_to_top_of_data_block(
1122  size_type block_index, const T& cell);
1123 
1124  template<typename T>
1125  void set_cell_to_bottom_of_data_block(
1126  size_type block_index, const T& cell);
1127 
1128  iterator transfer_impl(
1129  size_type start_pos, size_type end_pos, size_type block_index1,
1130  multi_type_vector& dest, size_type dest_pos);
1131 
1135  iterator transfer_single_block(
1136  size_type start_pos, size_type end_pos, size_type block_index1,
1137  multi_type_vector& dest, size_type dest_pos);
1138 
1143  iterator transfer_multi_blocks(
1144  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1145  multi_type_vector& dest, size_type dest_pos);
1146 
1155  iterator set_empty_impl(
1156  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1157 
1158  void swap_impl(
1159  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1160  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1161 
1162  void swap_single_block(
1163  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1164  size_type block_index, size_type other_block_index);
1165 
1166  void swap_single_to_multi_blocks(
1167  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1168  size_type block_index, size_type dst_block_index1, size_type dst_block_index2);
1169 
1170  void swap_multi_to_multi_blocks(
1171  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1172  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1173 
1174  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1175 
1176  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1177 
1178  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1179 
1180  iterator set_empty_in_single_block(
1181  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1182 
1192  iterator set_empty_in_multi_blocks(
1193  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1194  bool overwrite);
1195 
1196  void erase_impl(size_type start_pos, size_type end_pos);
1197  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1198 
1204  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1205 
1206  template<typename T>
1207  iterator set_cells_impl(
1208  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1209 
1210  template<typename T>
1211  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1212 
1213  template<typename T>
1214  iterator set_cells_to_single_block(
1215  size_type start_row, size_type end_row, size_type block_index,
1216  const T& it_begin, const T& it_end);
1217 
1218  template<typename T>
1219  iterator set_cells_to_multi_blocks(
1220  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1221  const T& it_begin, const T& it_end);
1222 
1223  template<typename T>
1224  iterator set_cells_to_multi_blocks_block1_non_equal(
1225  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1226  const T& it_begin, const T& it_end);
1227 
1228  template<typename T>
1229  iterator set_cells_to_multi_blocks_block1_non_empty(
1230  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1231  const T& it_begin, const T& it_end);
1232 
1241  size_type merge_with_adjacent_blocks(size_type block_index);
1242 
1250  bool merge_with_next_block(size_type block_index);
1251 
1252  template<typename T>
1253  bool append_to_prev_block(
1254  size_type block_index, element_category_type cat, size_type length,
1255  const T& it_begin, const T& it_end);
1256 
1257  template<typename T>
1258  void insert_cells_to_middle(
1259  size_type row, size_type block_index, const T& it_begin, const T& it_end);
1260 
1274  block& set_new_block_to_middle(
1275  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1276 
1277  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1278 
1286  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1287 
1305  element_block_type* exchange_elements(
1306  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1307 
1308  void exchange_elements(
1309  const element_block_type& src_data, size_type src_offset,
1310  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1311  size_type len, blocks_type& new_blocks);
1312 
1313  bool append_empty(size_type len);
1314 
1315  inline iterator get_iterator(size_type block_index)
1316  {
1317  typename blocks_type::iterator block_pos = m_blocks.begin();
1318  std::advance(block_pos, block_index);
1319  return iterator(block_pos, m_blocks.end(), block_index);
1320  }
1321 
1322  inline const_iterator get_const_iterator(size_type block_index) const
1323  {
1324  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1325  std::advance(block_pos, block_index);
1326  return const_iterator(block_pos, m_blocks.end(), block_index);
1327  }
1328 
1329 private:
1330  using adjust_block_positions_func =
1331  detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1332 
1333  event_func m_hdl_event;
1334  blocks_type m_blocks;
1335  size_type m_cur_size;
1336 };
1337 
1338 }}}
1339 
1340 #include "main_def.inl"
1341 
1342 #endif
1343 
1344 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1345 
Definition: aos/iterator.hpp:218
Definition: aos/iterator.hpp:151
Definition: aos/main.hpp:69
iterator set(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
static const_position_type advance_position(const const_position_type &pos, int steps)
const_position_type position(const const_iterator &pos_hint, size_type pos) const
iterator set(size_type pos, const T &value)
itr_node value_type
Definition: aos/main.hpp:189
iterator insert_empty(size_type pos, size_type length)
typename Trait::event_func event_func
Definition: aos/main.hpp:94
void get(size_type pos, T &value) const
position_type position(const iterator &pos_hint, size_type pos)
iterator set_empty(size_type start_pos, size_type end_pos)
multi_type_vector(multi_type_vector &&other)
multi_type_vector(size_type init_size, const T &value)
mtv::element_t get_type(size_type pos) const
iterator transfer(const iterator &pos_hint, size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
static Blk::value_type get(const const_position_type &pos)
static const_position_type next_position(const const_position_type &pos)
iterator set(size_type pos, const T &it_begin, const T &it_end)
multi_type_vector(const event_func &hdl)
void swap(multi_type_vector &other)
multi_type_vector(event_func &&hdl)
position_type position(size_type pos)
static size_type logical_position(const const_position_type &pos)
iterator push_back(const T &value)
void resize(size_type new_size)
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)
bool is_empty(size_type pos) const
multi_type_vector(size_type init_size)
const_position_type position(size_type pos) const
static mtv::element_t get_element_type(const T &elem)
multi_type_vector(const multi_type_vector &other)
iterator release(const iterator &pos_hint, size_type pos, T &value)
multi_type_vector(size_type init_size, const T &it_begin, const T &it_end)
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
static position_type next_position(const position_type &pos)
iterator insert_empty(const iterator &pos_hint, size_type pos, size_type length)
iterator release(size_type pos, T &value)
T get(size_type pos) const
static position_type advance_position(const position_type &pos, int steps)
iterator set(const iterator &pos_hint, size_type pos, const T &value)
iterator insert(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
iterator release_range(size_type start_pos, size_type end_pos)
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)
iterator insert(size_type pos, const T &it_begin, const T &it_end)
Definition: types.hpp:113
Definition: iterator_node.hpp:101
Definition: iterator_node.hpp:92