mdds
Loading...
Searching...
No Matches
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
42namespace mdds { namespace mtv { namespace aos {
43
71template<typename Traits = mdds::mtv::default_traits>
73{
74public:
75 typedef size_t size_type;
76
78 typedef mdds::mtv::element_t element_category_type;
79 using block_funcs = typename Traits::block_funcs;
80
98 using event_func = typename Traits::event_func;
99
100private:
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 block_funcs::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
169public:
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
492 template<typename T>
493 iterator push_back(T&& value);
494
503
521 template<typename T, typename... Args>
522 iterator emplace_back(Args&&... args);
523
545 template<typename T>
546 iterator insert(size_type pos, const T& it_begin, const T& it_end);
547
585 template<typename T>
586 iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);
587
598 template<typename T>
599 void get(size_type pos, T& value) const;
600
612 template<typename T>
613 T get(size_type pos) const;
614
629 template<typename T>
630 T release(size_type pos);
631
648 template<typename T>
649 iterator release(size_type pos, T& value);
650
670 template<typename T>
671 iterator release(const iterator& pos_hint, size_type pos, T& value);
672
681 void release();
682
698 iterator release_range(size_type start_pos, size_type end_pos);
699
724 iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
725
742 position_type position(size_type pos);
743
763 position_type position(const iterator& pos_hint, size_type pos);
764
778 const_position_type position(size_type pos) const;
779
796 const_position_type position(const const_iterator& pos_hint, size_type pos) const;
797
822 iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
823
852 const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
853
861 mtv::element_t get_type(size_type pos) const;
862
874 bool is_empty(size_type pos) const;
875
889 iterator set_empty(size_type start_pos, size_type end_pos);
890
920 iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
921
937 void erase(size_type start_pos, size_type end_pos);
938
957 iterator insert_empty(size_type pos, size_type length);
958
993 iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
994
999 void clear();
1000
1006 size_type size() const;
1007
1025 size_type block_size() const;
1026
1032 bool empty() const;
1033
1041 void resize(size_type new_size);
1042
1049
1058 void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1059
1064
1065 bool operator==(const multi_type_vector& other) const;
1066 bool operator!=(const multi_type_vector& other) const;
1067
1068 multi_type_vector& operator=(const multi_type_vector& other);
1069 multi_type_vector& operator=(multi_type_vector&& other);
1070
1078 template<typename T>
1079 static mtv::element_t get_element_type(const T& elem);
1080
1081#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1082 void dump_blocks(std::ostream& os) const;
1083
1084 void check_block_integrity() const;
1085#endif
1086
1087private:
1094 void delete_element_block(block& blk);
1095
1103 void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1104
1105 template<typename T>
1106 iterator set_impl(size_type pos, size_type block_index, const T& value);
1107
1108 template<typename T>
1109 iterator release_impl(size_type pos, size_type block_index, T& value);
1110
1111 template<typename T>
1112 iterator push_back_impl(T&& value);
1113
1114 template<typename T, typename... Args>
1115 iterator emplace_back_impl(Args&&... args);
1116
1126 size_type get_block_position(size_type row, size_type start_block_index = 0) const;
1127
1132 size_type get_block_position(const typename value_type::private_data& pos_data, size_type row) const;
1133
1134 void resize_impl(size_type new_size);
1135
1136 template<typename T>
1137 void create_new_block_with_new_cell(element_block_type*& data, T&& cell);
1138
1139 template<typename T, typename... Args>
1140 void create_new_block_with_emplace_back(element_block_type*& data, const T& t, Args&&... args);
1141
1142 template<typename T>
1143 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);
1144
1145 template<typename T>
1146 void append_cell_to_block(size_type block_index, const T& cell);
1147
1148 template<typename T>
1149 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);
1150
1151 template<typename T>
1152 iterator set_cell_to_block_of_size_one(size_type block_index, const T& cell);
1153
1154 template<typename T>
1155 void set_cell_to_top_of_data_block(size_type block_index, const T& cell);
1156
1157 template<typename T>
1158 void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);
1159
1160 iterator transfer_impl(
1161 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1162
1166 iterator transfer_single_block(
1167 size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);
1168
1173 iterator transfer_multi_blocks(
1174 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
1175 size_type dest_pos);
1176
1185 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1186
1187 void swap_impl(
1188 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1189 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1190
1191 void swap_single_block(
1192 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1193 size_type other_block_index);
1194
1195 void swap_single_to_multi_blocks(
1196 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1197 size_type dst_block_index1, size_type dst_block_index2);
1198
1199 void swap_multi_to_multi_blocks(
1200 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1201 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1202
1203 void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1204
1205 void prepare_blocks_to_transfer(
1206 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1207 size_type offset2);
1208
1209 iterator set_whole_block_empty(size_type block_index, bool overwrite);
1210
1211 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1212
1222 iterator set_empty_in_multi_blocks(
1223 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);
1224
1225 void erase_impl(size_type start_pos, size_type end_pos);
1226 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1227
1233 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1234
1235 template<typename T>
1236 iterator set_cells_impl(
1237 size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);
1238
1239 template<typename T>
1240 iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1241
1242 template<typename T>
1243 iterator set_cells_to_single_block(
1244 size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);
1245
1246 template<typename T>
1247 iterator set_cells_to_multi_blocks(
1248 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1249 const T& it_end);
1250
1251 template<typename T>
1252 iterator set_cells_to_multi_blocks_block1_non_equal(
1253 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1254 const T& it_end);
1255
1256 template<typename T>
1257 iterator set_cells_to_multi_blocks_block1_non_empty(
1258 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
1259 const T& it_end);
1260
1269 size_type merge_with_adjacent_blocks(size_type block_index);
1270
1278 bool merge_with_next_block(size_type block_index);
1279
1280 template<typename T>
1281 bool append_to_prev_block(
1282 size_type block_index, element_category_type cat, size_type length, const T& it_begin, const T& it_end);
1283
1284 template<typename T>
1285 void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);
1286
1300 block& set_new_block_to_middle(size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1301
1302 block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1303
1311 block* get_next_block_of_type(size_type block_index, element_category_type cat);
1312
1330 element_block_type* exchange_elements(
1331 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1332 size_type len);
1333
1334 void exchange_elements(
1335 const element_block_type& src_data, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1336 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1337
1338 bool append_empty(size_type len);
1339
1340 inline iterator get_iterator(size_type block_index)
1341 {
1342 typename blocks_type::iterator block_pos = m_blocks.begin();
1343 std::advance(block_pos, block_index);
1344 return iterator(block_pos, m_blocks.end(), this, block_index);
1345 }
1346
1347 inline const_iterator get_const_iterator(size_type block_index) const
1348 {
1349 typename blocks_type::const_iterator block_pos = m_blocks.begin();
1350 std::advance(block_pos, block_index);
1351 return const_iterator(block_pos, m_blocks.end(), this, block_index);
1352 }
1353
1354private:
1355 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1356
1357 event_func m_hdl_event;
1358 blocks_type m_blocks;
1359 size_type m_cur_size;
1360};
1361
1362}}} // namespace mdds::mtv::aos
1363
1364#include "main_def.inl"
1365
1366#endif
1367
1368/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition aos/iterator.hpp:224
Definition aos/iterator.hpp:156
Definition aos/main.hpp:73
static const_position_type next_position(const const_position_type &pos)
static mtv::element_t get_element_type(const T &elem)
position_type position(const iterator &pos_hint, size_type 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 set(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
iterator set_empty(const iterator &pos_hint, size_type start_pos, size_type end_pos)
iterator insert(const iterator &pos_hint, size_type pos, const T &it_begin, const T &it_end)
multi_type_vector(const event_func &hdl)
multi_type_vector(event_func &&hdl)
const_position_type position(const const_iterator &pos_hint, size_type pos) const
bool is_empty(size_type pos) const
void swap(size_type start_pos, size_type end_pos, multi_type_vector &other, size_type other_pos)
typename Traits::event_func event_func
Definition aos/main.hpp:98
position_type position(size_type pos)
static position_type next_position(const position_type &pos)
itr_node value_type
Definition aos/main.hpp:192
iterator set(size_type pos, const T &value)
multi_type_vector(const multi_type_vector &other)
static Blk::value_type get(const const_position_type &pos)
iterator release(size_type pos, T &value)
static position_type advance_position(const position_type &pos, int steps)
T get(size_type pos) const
void get(size_type pos, T &value) const
multi_type_vector(size_type init_size, const T &value)
iterator set(size_type pos, const T &it_begin, const T &it_end)
iterator set_empty(size_type start_pos, size_type end_pos)
iterator set(const iterator &pos_hint, size_type pos, const T &value)
static size_type logical_position(const const_position_type &pos)
multi_type_vector(size_type init_size)
iterator insert(size_type pos, const T &it_begin, const T &it_end)
iterator insert_empty(const iterator &pos_hint, size_type pos, size_type length)
static const_position_type advance_position(const const_position_type &pos, int steps)
void resize(size_type new_size)
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
iterator transfer(const iterator &pos_hint, size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
mtv::element_t get_type(size_type pos) const
iterator emplace_back(Args &&... args)
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 insert_empty(size_type pos, size_type length)
void swap(multi_type_vector &other)
const_position_type position(size_type pos) const
iterator release_range(size_type start_pos, size_type end_pos)
multi_type_vector(multi_type_vector &&other)
Definition types.hpp:157
Definition iterator_node.hpp:42
Definition iterator_node.hpp:109
Definition iterator_node.hpp:98