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  struct block
102  {
103  size_type position;
104  size_type size;
105  element_block_type* data;
106 
107  block();
108  block(size_type _position, size_type _size);
109  block(size_type _position, size_type _size, element_block_type* _data);
110  block(const block& other) = default;
111  block(block&& other) = default;
112  ~block() = default;
113  void swap(block& other);
114  void clone_to(block& other) const;
115 
116  block& operator=(const block&) = default;
117  };
118 
119  struct element_block_deleter
120  {
121  void operator()(const element_block_type* p)
122  {
123  element_block_func::delete_block(p);
124  }
125  };
126 
127  typedef std::vector<block> blocks_type;
128 
129  struct blocks_to_transfer
130  {
131  blocks_type blocks;
132  size_type insert_index;
133 
134  blocks_to_transfer();
135  };
136 
137  struct iterator_trait
138  {
139  typedef multi_type_vector parent;
140  typedef blocks_type blocks;
141  typedef typename blocks_type::iterator base_iterator;
142  };
143 
144  struct reverse_iterator_trait
145  {
146  typedef multi_type_vector parent;
147  typedef blocks_type blocks;
148  typedef typename blocks_type::reverse_iterator base_iterator;
149  };
150 
151  struct const_iterator_trait
152  {
153  typedef multi_type_vector parent;
154  typedef blocks_type blocks;
155  typedef typename blocks_type::const_iterator base_iterator;
156  };
157 
158  struct const_reverse_iterator_trait
159  {
160  typedef multi_type_vector parent;
161  typedef blocks_type blocks;
162  typedef typename blocks_type::const_reverse_iterator base_iterator;
163  };
164 
168 
169 public:
170  typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
171  typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
172 
173  typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
174  typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator>
175  const_reverse_iterator;
176 
193 
194  typedef std::pair<iterator, size_type> position_type;
195  typedef std::pair<const_iterator, size_type> const_position_type;
196 
205  static position_type next_position(const position_type& pos);
206 
216  static position_type advance_position(const position_type& pos, int steps);
217 
226  static const_position_type next_position(const const_position_type& pos);
227 
237  static const_position_type advance_position(const const_position_type& pos, int steps);
238 
247  static size_type logical_position(const const_position_type& pos);
248 
257  template<typename Blk>
258  static typename Blk::value_type get(const const_position_type& pos);
259 
260  iterator begin();
261  iterator end();
262 
263  const_iterator begin() const;
264  const_iterator end() const;
265 
266  const_iterator cbegin() const;
267  const_iterator cend() const;
268 
269  reverse_iterator rbegin();
270  reverse_iterator rend();
271 
272  const_reverse_iterator rbegin() const;
273  const_reverse_iterator rend() const;
274 
275  const_reverse_iterator crbegin() const;
276  const_reverse_iterator crend() const;
277 
278  event_func& event_handler();
279  const event_func& event_handler() const;
280 
285 
293 
301 
309  multi_type_vector(size_type init_size);
310 
320  template<typename T>
321  multi_type_vector(size_type init_size, const T& value);
322 
336  template<typename T>
337  multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);
338 
345 
352 
357 
374  template<typename T>
375  iterator set(size_type pos, const T& value);
376 
409  template<typename T>
410  iterator set(const iterator& pos_hint, size_type pos, const T& value);
411 
433  template<typename T>
434  iterator set(size_type pos, const T& it_begin, const T& it_end);
435 
473  template<typename T>
474  iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
475 
485  template<typename T>
486  iterator push_back(const T& value);
487 
496 
518  template<typename T>
519  iterator insert(size_type pos, const T& it_begin, const T& it_end);
520 
558  template<typename T>
559  iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
560 
571  template<typename T>
572  void get(size_type pos, T& value) const;
573 
585  template<typename T>
586  T get(size_type pos) const;
587 
602  template<typename T>
603  T release(size_type pos);
604 
621  template<typename T>
622  iterator release(size_type pos, T& value);
623 
643  template<typename T>
644  iterator release(const iterator& pos_hint, size_type pos, T& value);
645 
654  void release();
655 
671  iterator release_range(size_type start_pos, size_type end_pos);
672 
697  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
698 
715  position_type position(size_type pos);
716 
736  position_type position(const iterator& pos_hint, size_type pos);
737 
751  const_position_type position(size_type pos) const;
752 
769  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
770 
795  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
796 
825  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:
1067  void delete_element_block(block& blk);
1068 
1076  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1077 
1078  template<typename T>
1079  iterator set_impl(size_type pos, size_type block_index, const T& value);
1080 
1081  template<typename T>
1082  iterator release_impl(size_type pos, size_type block_index, T& value);
1083 
1084  template<typename T>
1085  iterator push_back_impl(const T& value);
1086 
1096  size_type get_block_position(size_type row, size_type start_block_index = 0) const;
1097 
1102  size_type get_block_position(const typename value_type::private_data& pos_data, size_type row) const;
1103 
1104  void resize_impl(size_type new_size);
1105 
1106  template<typename T>
1107  void create_new_block_with_new_cell(element_block_type*& data, const T& cell);
1108 
1109  template<typename T>
1110  iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
1111 
1112  template<typename T>
1113  void append_cell_to_block(size_type block_index, const T& cell);
1114 
1115  template<typename T>
1116  iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1117 
1118  template<typename T>
1119  iterator set_cell_to_block_of_size_one(size_type block_index, const T& cell);
1120 
1121  template<typename T>
1122  void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1123 
1124  template<typename T>
1125  void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1126 
1127  iterator transfer_impl(
1128  size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1129 
1133  iterator transfer_single_block(
1134  size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1135 
1140  iterator transfer_multi_blocks(
1141  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1142  size_type dest_pos);
1143 
1152  iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1153 
1154  void swap_impl(
1155  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1156  size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1157 
1158  void swap_single_block(
1159  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1160  size_type other_block_index);
1161 
1162  void swap_single_to_multi_blocks(
1163  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1164  size_type dst_block_index1, size_type dst_block_index2);
1165 
1166  void swap_multi_to_multi_blocks(
1167  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1168  size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1169 
1170  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1171 
1172  void prepare_blocks_to_transfer(
1173  blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1174  size_type offset2);
1175 
1176  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1177 
1178  iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1179 
1189  iterator set_empty_in_multi_blocks(
1190  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
1191 
1192  void erase_impl(size_type start_pos, size_type end_pos);
1193  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1194 
1200  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1201 
1202  template<typename T>
1203  iterator set_cells_impl(
1204  size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1205 
1206  template<typename T>
1207  iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1208 
1209  template<typename T>
1210  iterator set_cells_to_single_block(
1211  size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
1212 
1213  template<typename T>
1214  iterator set_cells_to_multi_blocks(
1215  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1216  const T& it_end);
1217 
1218  template<typename T>
1219  iterator set_cells_to_multi_blocks_block1_non_equal(
1220  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1221  const T& it_end);
1222 
1223  template<typename T>
1224  iterator set_cells_to_multi_blocks_block1_non_empty(
1225  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1226  const T& it_end);
1227 
1236  size_type merge_with_adjacent_blocks(size_type block_index);
1237 
1245  bool merge_with_next_block(size_type block_index);
1246 
1247  template<typename T>
1248  bool append_to_prev_block(
1249  size_type block_index, element_category_type cat, size_type length, const T& it_begin, const T& it_end);
1250 
1251  template<typename T>
1252  void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1253 
1267  block& set_new_block_to_middle(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,
1299  size_type len);
1300 
1301  void exchange_elements(
1302  const element_block_type& src_data, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1303  size_type dst_index2, size_type dst_offset2, 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(), this, 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(), this, block_index);
1319  }
1320 
1321 private:
1322  using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Trait::loop_unrolling>;
1323 
1324  event_func m_hdl_event;
1325  blocks_type m_blocks;
1326  size_type m_cur_size;
1327 };
1328 
1329 }}} // namespace mdds::mtv::aos
1330 
1331 #include "main_def.inl"
1332 
1333 #endif
1334 
1335 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: aos/iterator.hpp:224
Definition: aos/iterator.hpp:156
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:192
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:174
Definition: iterator_node.hpp:42
Definition: iterator_node.hpp:109
Definition: iterator_node.hpp:98