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 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
39 #include <iostream>
40 #endif
41 
42 namespace mdds { namespace mtv { namespace aos {
43 
71 template<typename ElemBlockFunc, typename Trait = mdds::mtv::default_trait>
73 {
74 public:
75  typedef size_t size_type;
76 
78  typedef mdds::mtv::element_t element_category_type;
79  typedef ElemBlockFunc element_block_func;
80 
98  using event_func = typename Trait::event_func;
99 
100 private:
101 
102  struct block
103  {
104  size_type position;
105  size_type size;
106  element_block_type* data;
107 
108  block();
109  block(size_type _position, size_type _size);
110  block(size_type _position, size_type _size, element_block_type* _data);
111  block(const block& other) = default;
112  block(block&& other) = default;
113  ~block() = default;
114  void swap(block& other);
115  void clone_to(block& other) const;
116 
117  block& operator=(const block&) = default;
118  };
119 
120  struct element_block_deleter
121  {
122  void operator() (const element_block_type* p)
123  {
124  element_block_func::delete_block(p);
125  }
126  };
127 
128  typedef std::vector<block> blocks_type;
129 
130  struct blocks_to_transfer
131  {
132  blocks_type blocks;
133  size_type insert_index;
134 
135  blocks_to_transfer();
136  };
137 
138  struct iterator_trait
139  {
140  typedef multi_type_vector parent;
141  typedef blocks_type blocks;
142  typedef typename blocks_type::iterator base_iterator;
143  };
144 
145  struct reverse_iterator_trait
146  {
147  typedef multi_type_vector parent;
148  typedef blocks_type blocks;
149  typedef typename blocks_type::reverse_iterator base_iterator;
150  };
151 
152  struct const_iterator_trait
153  {
154  typedef multi_type_vector parent;
155  typedef blocks_type blocks;
156  typedef typename blocks_type::const_iterator base_iterator;
157  };
158 
159  struct const_reverse_iterator_trait
160  {
161  typedef multi_type_vector parent;
162  typedef blocks_type blocks;
163  typedef typename blocks_type::const_reverse_iterator base_iterator;
164  };
165 
169 
170 public:
171 
172  typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
173  typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
174 
175  typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
176  typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator> const_reverse_iterator;
177 
194 
195  typedef std::pair<iterator, size_type> position_type;
196  typedef std::pair<const_iterator, size_type> const_position_type;
197 
206  static position_type next_position(const position_type& pos);
207 
217  static position_type advance_position(const position_type& pos, int steps);
218 
227  static const_position_type next_position(const const_position_type& pos);
228 
238  static const_position_type advance_position(const const_position_type& pos, int steps);
239 
248  static size_type logical_position(const const_position_type& pos);
249 
258  template<typename Blk>
259  static typename Blk::value_type get(const const_position_type& pos);
260 
261  iterator begin();
262  iterator end();
263 
264  const_iterator begin() const;
265  const_iterator end() const;
266 
267  const_iterator cbegin() const;
268  const_iterator cend() const;
269 
270  reverse_iterator rbegin();
271  reverse_iterator rend();
272 
273  const_reverse_iterator rbegin() const;
274  const_reverse_iterator rend() const;
275 
276  const_reverse_iterator crbegin() const;
277  const_reverse_iterator crend() const;
278 
279  event_func& event_handler();
280  const event_func& event_handler() const;
281 
286 
294 
302 
310  multi_type_vector(size_type init_size);
311 
321  template<typename T>
322  multi_type_vector(size_type init_size, const T& value);
323 
337  template<typename T>
338  multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
339 
346 
353 
358 
375  template<typename T>
376  iterator set(size_type pos, const T& value);
377 
410  template<typename T>
411  iterator set(const iterator& pos_hint, size_type pos, const T& value);
412 
434  template<typename T>
435  iterator set(size_type pos, const T& it_begin, const T& it_end);
436 
474  template<typename T>
475  iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
476 
486  template<typename T>
487  iterator push_back(const T& value);
488 
497 
519  template<typename T>
520  iterator insert(size_type pos, const T& it_begin, const T& it_end);
521 
559  template<typename T>
560  iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
561 
572  template<typename T>
573  void get(size_type pos, T& value) const;
574 
586  template<typename T>
587  T get(size_type pos) const;
588 
603  template<typename T>
604  T release(size_type pos);
605 
622  template<typename T>
623  iterator release(size_type pos, T& value);
624 
644  template<typename T>
645  iterator release(const iterator& pos_hint, size_type pos, T& value);
646 
655  void release();
656 
672  iterator release_range(size_type start_pos, size_type end_pos);
673 
698  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
699 
716  position_type position(size_type pos);
717 
737  position_type position(const iterator& pos_hint, size_type pos);
738 
752  const_position_type position(size_type pos) const;
753 
770  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
771 
796  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
797 
825  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
826 
834  mtv::element_t get_type(size_type pos) const;
835 
847  bool is_empty(size_type pos) const;
848 
862  iterator set_empty(size_type start_pos, size_type end_pos);
863 
893  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
894 
910  void erase(size_type start_pos, size_type end_pos);
911 
930  iterator insert_empty(size_type pos, size_type length);
931 
966  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
967 
972  void clear();
973 
979  size_type size() const;
980 
998  size_type block_size() const;
999 
1005  bool empty() const;
1006 
1014  void resize(size_type new_size);
1015 
1021  void swap(multi_type_vector& other);
1022 
1031  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1032 
1037 
1038  bool operator== (const multi_type_vector& other) const;
1039  bool operator!= (const multi_type_vector& other) const;
1040 
1041  multi_type_vector& operator= (const multi_type_vector& other);
1042  multi_type_vector& operator= (multi_type_vector&& other);
1043 
1051  template<typename T>
1052  static mtv::element_t get_element_type(const T& elem);
1053 
1054 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1055  void dump_blocks(std::ostream& os) const;
1056 
1057  void check_block_integrity() const;
1058 #endif
1059 
1060 private:
1061 
1068  void delete_element_block(block& blk);
1069 
1077  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1078 
1079  template<typename T>
1080  iterator set_impl(size_type pos, size_type block_index, const T& value);
1081 
1082  template<typename T>
1083  iterator release_impl(size_type pos, size_type block_index, T& value);
1084 
1085  template<typename T>
1086  iterator push_back_impl(const T& value);
1087 
1097  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1098 
1103  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1104 
1105  void resize_impl(size_type new_size);
1106 
1107  template<typename T>
1108  void create_new_block_with_new_cell(element_block_type*& data, const T& cell);
1109 
1110  template<typename T>
1111  iterator set_cell_to_middle_of_block(
1112  size_type block_index, size_type pos_in_block, const T& cell);
1113 
1114  template<typename T>
1115  void append_cell_to_block(size_type block_index, const T& cell);
1116 
1117  template<typename T>
1118  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1119 
1120  template<typename T>
1121  iterator set_cell_to_block_of_size_one(
1122  size_type block_index, const T& cell);
1123 
1124  template<typename T>
1125  void set_cell_to_top_of_data_block(
1126  size_type block_index, const T& cell);
1127 
1128  template<typename T>
1129  void set_cell_to_bottom_of_data_block(
1130  size_type block_index, const T& cell);
1131 
1132  iterator transfer_impl(
1133  size_type start_pos, size_type end_pos, size_type block_index1,
1134  multi_type_vector& dest, size_type dest_pos);
1135 
1139  iterator transfer_single_block(
1140  size_type start_pos, size_type end_pos, size_type block_index1,
1141  multi_type_vector& dest, size_type dest_pos);
1142 
1147  iterator transfer_multi_blocks(
1148  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1149  multi_type_vector& dest, size_type dest_pos);
1150 
1159  iterator set_empty_impl(
1160  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1161 
1162  void swap_impl(
1163  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1164  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1165 
1166  void swap_single_block(
1167  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1168  size_type block_index, size_type other_block_index);
1169 
1170  void swap_single_to_multi_blocks(
1171  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1172  size_type block_index, size_type dst_block_index1, size_type dst_block_index2);
1173 
1174  void swap_multi_to_multi_blocks(
1175  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1176  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1177 
1178  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1179 
1180  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1181 
1182  iterator set_whole_block_empty(size_type block_index, 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_pos);
1202 
1208  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1209 
1210  template<typename T>
1211  iterator set_cells_impl(
1212  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1213 
1214  template<typename T>
1215  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1216 
1217  template<typename T>
1218  iterator set_cells_to_single_block(
1219  size_type start_row, size_type end_row, size_type block_index,
1220  const T& it_begin, const T& it_end);
1221 
1222  template<typename T>
1223  iterator set_cells_to_multi_blocks(
1224  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1225  const T& it_begin, const T& it_end);
1226 
1227  template<typename T>
1228  iterator set_cells_to_multi_blocks_block1_non_equal(
1229  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1230  const T& it_begin, const T& it_end);
1231 
1232  template<typename T>
1233  iterator set_cells_to_multi_blocks_block1_non_empty(
1234  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1235  const T& it_begin, const T& it_end);
1236 
1245  size_type merge_with_adjacent_blocks(size_type block_index);
1246 
1254  bool merge_with_next_block(size_type block_index);
1255 
1256  template<typename T>
1257  bool append_to_prev_block(
1258  size_type block_index, element_category_type cat, size_type length,
1259  const T& it_begin, const T& it_end);
1260 
1261  template<typename T>
1262  void insert_cells_to_middle(
1263  size_type row, size_type block_index, const T& it_begin, const T& it_end);
1264 
1278  block& set_new_block_to_middle(
1279  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1280 
1281  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1282 
1290  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1291 
1309  element_block_type* exchange_elements(
1310  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1311 
1312  void exchange_elements(
1313  const element_block_type& src_data, size_type src_offset,
1314  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1315  size_type len, blocks_type& new_blocks);
1316 
1317  bool append_empty(size_type len);
1318 
1319  inline iterator get_iterator(size_type block_index)
1320  {
1321  typename blocks_type::iterator block_pos = m_blocks.begin();
1322  std::advance(block_pos, block_index);
1323  return iterator(block_pos, m_blocks.end(), block_index);
1324  }
1325 
1326  inline const_iterator get_const_iterator(size_type block_index) const
1327  {
1328  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1329  std::advance(block_pos, block_index);
1330  return const_iterator(block_pos, m_blocks.end(), block_index);
1331  }
1332 
1333 private:
1334  using adjust_block_positions_func =
1335  detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1336 
1337  event_func m_hdl_event;
1338  blocks_type m_blocks;
1339  size_type m_cur_size;
1340 };
1341 
1342 }}}
1343 
1344 #include "main_def.inl"
1345 
1346 #endif
1347 
1348 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1349 
Definition: aos/iterator.hpp:218
Definition: aos/iterator.hpp:151
Definition: aos/main.hpp:73
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:193
iterator insert_empty(size_type pos, size_type length)
typename Trait::event_func event_func
Definition: aos/main.hpp:98
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:173
Definition: iterator_node.hpp:101
Definition: iterator_node.hpp:92