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 
347 
364  template<typename T>
365  iterator set(size_type pos, const T& value);
366 
399  template<typename T>
400  iterator set(const iterator& pos_hint, size_type pos, const T& value);
401 
423  template<typename T>
424  iterator set(size_type pos, const T& it_begin, const T& it_end);
425 
463  template<typename T>
464  iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
465 
475  template<typename T>
476  iterator push_back(const T& value);
477 
486 
508  template<typename T>
509  iterator insert(size_type pos, const T& it_begin, const T& it_end);
510 
548  template<typename T>
549  iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
550 
561  template<typename T>
562  void get(size_type pos, T& value) const;
563 
575  template<typename T>
576  T get(size_type pos) const;
577 
592  template<typename T>
593  T release(size_type pos);
594 
611  template<typename T>
612  iterator release(size_type pos, T& value);
613 
633  template<typename T>
634  iterator release(const iterator& pos_hint, size_type pos, T& value);
635 
644  void release();
645 
661  iterator release_range(size_type start_pos, size_type end_pos);
662 
687  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
688 
705  position_type position(size_type pos);
706 
726  position_type position(const iterator& pos_hint, size_type pos);
727 
741  const_position_type position(size_type pos) const;
742 
759  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
760 
785  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
786 
814  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
815 
823  mtv::element_t get_type(size_type pos) const;
824 
836  bool is_empty(size_type pos) const;
837 
851  iterator set_empty(size_type start_pos, size_type end_pos);
852 
882  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
883 
899  void erase(size_type start_pos, size_type end_pos);
900 
919  iterator insert_empty(size_type pos, size_type length);
920 
955  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
956 
961  void clear();
962 
968  size_type size() const;
969 
987  size_type block_size() const;
988 
994  bool empty() const;
995 
1003  void resize(size_type new_size);
1004 
1010  void swap(multi_type_vector& other);
1011 
1020  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1021 
1026 
1027  bool operator== (const multi_type_vector& other) const;
1028  bool operator!= (const multi_type_vector& other) const;
1029 
1030  multi_type_vector& operator= (const multi_type_vector& other);
1031 
1039  template<typename T>
1040  static mtv::element_t get_element_type(const T& elem);
1041 
1042 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1043  void dump_blocks(std::ostream& os) const;
1044 
1045  void check_block_integrity() const;
1046 #endif
1047 
1048 private:
1049 
1056  void delete_element_block(block& blk);
1057 
1065  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1066 
1067  template<typename T>
1068  iterator set_impl(size_type pos, size_type block_index, const T& value);
1069 
1070  template<typename T>
1071  iterator release_impl(size_type pos, size_type block_index, T& value);
1072 
1073  template<typename T>
1074  iterator push_back_impl(const T& value);
1075 
1085  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1086 
1091  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1092 
1093  void resize_impl(size_type new_size);
1094 
1095  template<typename T>
1096  void create_new_block_with_new_cell(element_block_type*& data, const T& cell);
1097 
1098  template<typename T>
1099  iterator set_cell_to_middle_of_block(
1100  size_type block_index, size_type pos_in_block, const T& cell);
1101 
1102  template<typename T>
1103  void append_cell_to_block(size_type block_index, const T& cell);
1104 
1105  template<typename T>
1106  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1107 
1108  template<typename T>
1109  iterator set_cell_to_block_of_size_one(
1110  size_type block_index, const T& cell);
1111 
1112  template<typename T>
1113  void set_cell_to_top_of_data_block(
1114  size_type block_index, const T& cell);
1115 
1116  template<typename T>
1117  void set_cell_to_bottom_of_data_block(
1118  size_type block_index, const T& cell);
1119 
1120  iterator transfer_impl(
1121  size_type start_pos, size_type end_pos, size_type block_index1,
1122  multi_type_vector& dest, size_type dest_pos);
1123 
1127  iterator transfer_single_block(
1128  size_type start_pos, size_type end_pos, size_type block_index1,
1129  multi_type_vector& dest, size_type dest_pos);
1130 
1135  iterator transfer_multi_blocks(
1136  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1137  multi_type_vector& dest, size_type dest_pos);
1138 
1147  iterator set_empty_impl(
1148  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1149 
1150  void swap_impl(
1151  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1152  size_type block_index1, 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,
1156  size_type block_index, 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,
1160  size_type block_index, 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,
1164  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1165 
1166  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1167 
1168  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1169 
1170  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1171 
1172  iterator set_empty_in_single_block(
1173  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1174 
1184  iterator set_empty_in_multi_blocks(
1185  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1186  bool overwrite);
1187 
1188  void erase_impl(size_type start_pos, size_type end_pos);
1189  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1190 
1196  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1197 
1198  template<typename T>
1199  iterator set_cells_impl(
1200  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1201 
1202  template<typename T>
1203  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1204 
1205  template<typename T>
1206  iterator set_cells_to_single_block(
1207  size_type start_row, size_type end_row, size_type block_index,
1208  const T& it_begin, const T& it_end);
1209 
1210  template<typename T>
1211  iterator set_cells_to_multi_blocks(
1212  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1213  const T& it_begin, const T& it_end);
1214 
1215  template<typename T>
1216  iterator set_cells_to_multi_blocks_block1_non_equal(
1217  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1218  const T& it_begin, const T& it_end);
1219 
1220  template<typename T>
1221  iterator set_cells_to_multi_blocks_block1_non_empty(
1222  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1223  const T& it_begin, const T& it_end);
1224 
1233  size_type merge_with_adjacent_blocks(size_type block_index);
1234 
1242  bool merge_with_next_block(size_type block_index);
1243 
1244  template<typename T>
1245  bool append_to_prev_block(
1246  size_type block_index, element_category_type cat, size_type length,
1247  const T& it_begin, const T& it_end);
1248 
1249  template<typename T>
1250  void insert_cells_to_middle(
1251  size_type row, size_type block_index, const T& it_begin, const T& it_end);
1252 
1266  block& set_new_block_to_middle(
1267  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1268 
1269  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1270 
1278  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1279 
1297  element_block_type* exchange_elements(
1298  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1299 
1300  void exchange_elements(
1301  const element_block_type& src_data, size_type src_offset,
1302  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1303  size_type len, blocks_type& new_blocks);
1304 
1305  bool append_empty(size_type len);
1306 
1307  inline iterator get_iterator(size_type block_index)
1308  {
1309  typename blocks_type::iterator block_pos = m_blocks.begin();
1310  std::advance(block_pos, block_index);
1311  return iterator(block_pos, m_blocks.end(), block_index);
1312  }
1313 
1314  inline const_iterator get_const_iterator(size_type block_index) const
1315  {
1316  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1317  std::advance(block_pos, block_index);
1318  return const_iterator(block_pos, m_blocks.end(), block_index);
1319  }
1320 
1321 private:
1322  using adjust_block_positions_func =
1323  detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1324 
1325  event_func m_hdl_event;
1326  blocks_type m_blocks;
1327  size_type m_cur_size;
1328 };
1329 
1330 }}}
1331 
1332 #include "main_def.inl"
1333 
1334 #endif
1335 
1336 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1337 
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(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