9 #ifndef LIBPMEMOBJ_CPP_VECTOR_HPP
10 #define LIBPMEMOBJ_CPP_VECTOR_HPP
22 #include <libpmemobj/base.h>
44 using size_type = std::size_t;
45 using difference_type = std::ptrdiff_t;
46 using reference = value_type &;
47 using const_reference =
const value_type &;
48 using pointer = value_type *;
49 using const_pointer =
const value_type *;
51 using const_iterator = const_pointer;
52 using reverse_iterator = std::reverse_iterator<iterator>;
53 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
57 using for_each_ptr_function =
62 vector(size_type count,
const value_type &value);
63 explicit vector(size_type count);
64 template <
typename InputIt,
65 typename std::enable_if<
67 InputIt>::type * =
nullptr>
68 vector(InputIt first, InputIt last);
71 vector(std::initializer_list<T> init);
72 vector(
const std::vector<T> &other);
81 void assign(size_type count,
const T &value);
82 template <
typename InputIt,
83 typename std::enable_if<
85 InputIt>::type * =
nullptr>
86 void assign(InputIt first, InputIt last);
87 void assign(std::initializer_list<T> ilist);
88 void assign(
const vector &other);
89 void assign(
vector &&other);
90 void assign(
const std::vector<T> &other);
96 reference
at(size_type n);
97 const_reference
at(size_type n)
const;
98 const_reference
const_at(size_type n)
const;
100 const_reference
operator[](size_type n)
const;
102 const_reference
front()
const;
103 const_reference
cfront()
const;
105 const_reference
back()
const;
106 const_reference
cback()
const;
108 const value_type *
data()
const noexcept;
109 const value_type *
cdata()
const noexcept;
113 const_iterator
begin()
const noexcept;
114 const_iterator
cbegin()
const noexcept;
116 const_iterator
end()
const noexcept;
117 const_iterator
cend()
const noexcept;
118 reverse_iterator
rbegin();
119 const_reverse_iterator
rbegin()
const noexcept;
120 const_reverse_iterator
crbegin()
const noexcept;
121 reverse_iterator
rend();
122 const_reverse_iterator
rend()
const noexcept;
123 const_reverse_iterator
crend()
const noexcept;
128 size_type snapshot_size);
134 constexpr
bool empty()
const noexcept;
135 size_type
size()
const noexcept;
136 constexpr size_type
max_size()
const noexcept;
137 void reserve(size_type capacity_new);
138 size_type
capacity()
const noexcept;
146 iterator insert(const_iterator pos, size_type count,
const T &value);
147 template <
typename InputIt,
148 typename std::enable_if<
150 InputIt>::type * =
nullptr>
152 iterator insert(const_iterator pos, std::initializer_list<T> ilist);
153 template <
class... Args>
155 template <
class... Args>
162 void resize(size_type count);
163 void resize(size_type count,
const value_type &value);
168 template <
typename P>
169 struct single_element_iterator {
170 using iterator_category = std::input_iterator_tag;
171 using value_type = P;
172 using difference_type = std::ptrdiff_t;
173 using pointer =
const P *;
174 using reference =
const P &;
179 single_element_iterator(
const P *ptr, std::size_t count = 0)
180 : ptr(ptr), count(count)
184 reference operator*()
194 single_element_iterator &
201 single_element_iterator
204 single_element_iterator tmp =
205 single_element_iterator(ptr, count);
211 operator-(
const single_element_iterator &rhs)
213 return count - rhs.count;
217 operator!=(
const single_element_iterator &rhs)
219 return ptr != rhs.ptr || count != rhs.count;
227 template <
typename... Args>
229 template <
typename InputIt,
230 typename std::enable_if<
232 InputIt>::type * =
nullptr>
236 template <
typename InputIt>
240 void shrink(size_type size_new);
242 template <
typename InputIt>
255 template <
typename T>
262 template <
typename T>
264 template <
typename T>
266 template <
typename T>
268 template <
typename T>
270 template <
typename T>
272 template <
typename T>
279 template <
typename T>
281 template <
typename T>
283 template <
typename T>
285 template <
typename T>
287 template <
typename T>
289 template <
typename T>
296 template <
typename T>
298 template <
typename T>
300 template <
typename T>
302 template <
typename T>
304 template <
typename T>
306 template <
typename T>
318 template <
typename T>
322 check_tx_stage_work();
347 template <
typename T>
351 check_tx_stage_work();
356 construct_at_end(count, value);
376 template <
typename T>
380 check_tx_stage_work();
385 construct_at_end(count);
410 template <
typename T>
411 template <
typename InputIt,
412 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
417 check_tx_stage_work();
421 alloc(
static_cast<size_type
>(std::distance(first, last)));
422 construct_at_end(first, last);
443 template <
typename T>
447 check_tx_stage_work();
452 construct_at_end(other.
cbegin(), other.
cend());
474 template <
typename T>
478 check_tx_stage_work();
481 _capacity = other.capacity();
482 _size = other.size();
483 other._data =
nullptr;
484 other._capacity = other._size = 0;
504 template <
typename T>
528 template <
typename T>
545 template <
typename T>
564 template <
typename T>
568 assign(std::move(other));
582 template <
typename T>
586 assign(ilist.begin(), ilist.end());
603 template <
typename T>
628 template <
typename T>
634 transaction::run(pb, [&] {
635 if (count <= capacity()) {
642 size_type size_old = _size;
643 add_data_to_tx(0, size_old);
648 static_cast<size_type
>(size_old)),
651 if (count > size_old) {
652 add_data_to_tx(size_old, count - size_old);
653 construct_at_end(count - size_old, value);
660 construct_at_end(count, value);
683 template <
typename T>
684 template <
typename InputIt,
685 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
692 size_type size_new =
static_cast<size_type
>(std::distance(first, last));
694 transaction::run(pb, [&] {
695 if (size_new <= capacity()) {
702 size_type size_old = _size;
703 add_data_to_tx(0, size_old);
706 bool growing = size_new > size_old;
709 add_data_to_tx(size_old, size_new - size_old);
712 std::advance(mid, size_old);
715 iterator shrink_to = std::copy(first, mid, &_data[0]);
718 construct_at_end(mid, last);
720 shrink(
static_cast<size_type
>(std::distance(
726 construct_at_end(first, last);
746 template <
typename T>
750 assign(ilist.begin(), ilist.end());
764 template <
typename T>
783 template <
typename T>
792 transaction::run(pb, [&] {
796 _capacity = other._capacity;
799 other._data =
nullptr;
800 other._capacity = other._size = 0;
816 template <
typename T>
820 assign(other.cbegin(), other.cend());
830 template <
typename T>
852 template <
typename T>
853 typename vector<T>::reference
857 throw std::out_of_range(
"vector::at");
859 detail::conditional_add_to_tx(&_data[
static_cast<difference_type
>(n)],
860 1, POBJ_XADD_ASSUME_INITIALIZED);
862 return _data[
static_cast<difference_type
>(n)];
874 template <
typename T>
875 typename vector<T>::const_reference
879 throw std::out_of_range(
"vector::at");
881 return _data[
static_cast<difference_type
>(n)];
896 template <
typename T>
897 typename vector<T>::const_reference
901 throw std::out_of_range(
"vector::const_at");
903 return _data[
static_cast<difference_type
>(n)];
917 template <
typename T>
920 detail::conditional_add_to_tx(&_data[
static_cast<difference_type
>(n)],
921 1, POBJ_XADD_ASSUME_INITIALIZED);
923 return _data[
static_cast<difference_type
>(n)];
933 template <
typename T>
936 return _data[
static_cast<difference_type
>(n)];
947 template <
typename T>
948 typename vector<T>::reference
951 detail::conditional_add_to_tx(&_data[0], 1,
952 POBJ_XADD_ASSUME_INITIALIZED);
962 template <
typename T>
963 typename vector<T>::const_reference
976 template <
typename T>
977 typename vector<T>::const_reference
991 template <
typename T>
992 typename vector<T>::reference
995 detail::conditional_add_to_tx(
996 &_data[
static_cast<difference_type
>(size() - 1)], 1,
997 POBJ_XADD_ASSUME_INITIALIZED);
999 return _data[
static_cast<difference_type
>(size() - 1)];
1007 template <
typename T>
1008 typename vector<T>::const_reference
1011 return _data[
static_cast<difference_type
>(size() - 1)];
1021 template <
typename T>
1022 typename vector<T>::const_reference
1025 return _data[
static_cast<difference_type
>(size() - 1)];
1037 template <
typename T>
1038 typename vector<T>::value_type *
1041 add_data_to_tx(0, _size);
1051 template <
typename T>
1052 const typename vector<T>::value_type *
1065 template <
typename T>
1066 const typename vector<T>::value_type *
1077 template <
typename T>
1089 template <
typename T>
1090 typename vector<T>::const_iterator
1093 return const_iterator(_data.get());
1103 template <
typename T>
1104 typename vector<T>::const_iterator
1107 return const_iterator(_data.get());
1115 template <
typename T>
1119 return iterator(_data.get() +
static_cast<std::ptrdiff_t
>(_size));
1127 template <
typename T>
1128 typename vector<T>::const_iterator
1131 return const_iterator(_data.get() +
static_cast<std::ptrdiff_t
>(_size));
1141 template <
typename T>
1142 typename vector<T>::const_iterator
1145 return const_iterator(_data.get() +
static_cast<std::ptrdiff_t
>(_size));
1153 template <
typename T>
1154 typename vector<T>::reverse_iterator
1157 return reverse_iterator(
end());
1165 template <
typename T>
1166 typename vector<T>::const_reverse_iterator
1169 return const_reverse_iterator(
cend());
1179 template <
typename T>
1180 typename vector<T>::const_reverse_iterator
1183 return const_reverse_iterator(
cend());
1192 template <
typename T>
1193 typename vector<T>::reverse_iterator
1196 return reverse_iterator(
begin());
1205 template <
typename T>
1206 typename vector<T>::const_reverse_iterator
1209 return const_reverse_iterator(
cbegin());
1220 template <
typename T>
1221 typename vector<T>::const_reverse_iterator
1224 return const_reverse_iterator(
cbegin());
1240 template <
typename T>
1244 if (start + n > size())
1245 throw std::out_of_range(
"vector::range");
1247 detail::conditional_add_to_tx(cdata() + start, n,
1248 POBJ_XADD_ASSUME_INITIALIZED);
1250 return {_data.get() + start, _data.get() + start + n};
1268 template <
typename T>
1272 if (start + n > size())
1273 throw std::out_of_range(
"vector::range");
1275 if (snapshot_size > n)
1279 _data.get() + start, n,
1282 _data.get() + start, n,
1297 template <
typename T>
1301 if (start + n > size())
1302 throw std::out_of_range(
"vector::range");
1304 return {const_iterator(cdata() + start),
1305 const_iterator(cdata() + start + n)};
1319 template <
typename T>
1323 if (start + n > size())
1324 throw std::out_of_range(
"vector::crange");
1326 return {const_iterator(cdata() + start),
1327 const_iterator(cdata() + start + n)};
1335 template <
typename T>
1345 template <
typename T>
1346 typename vector<T>::size_type
1356 template <
typename T>
1357 constexpr
typename vector<T>::size_type
1360 return PMEMOBJ_MAX_ALLOC_SIZE /
sizeof(value_type);
1381 template <
typename T>
1385 if (capacity_new <= _capacity)
1389 transaction::run(pb, [&] { realloc(capacity_new); });
1395 template <
typename T>
1396 typename vector<T>::size_type
1416 template <
typename T>
1420 size_type capacity_new = size();
1421 if (capacity() == capacity_new)
1425 transaction::run(pb, [&] { realloc(capacity_new); });
1436 template <
typename T>
1441 transaction::run(pb, [&] { shrink(0); });
1456 template <
typename T>
1460 if (_data ==
nullptr)
1464 transaction::run(pb, [&] { dealloc(); });
1491 template <
typename T>
1495 return insert(pos, 1, value);
1522 template <
typename T>
1528 size_type idx =
static_cast<size_type
>(std::distance(
cbegin(), pos));
1530 transaction::run(pb, [&] {
1531 internal_insert(idx, std::make_move_iterator(&value),
1532 std::make_move_iterator(&value + 1));
1535 return iterator(&_data[
static_cast<difference_type
>(idx)]);
1566 template <
typename T>
1572 size_type idx =
static_cast<size_type
>(std::distance(
cbegin(), pos));
1574 transaction::run(pb, [&] {
1576 idx, single_element_iterator<value_type>(&value, 0),
1577 single_element_iterator<value_type>(&value, count));
1580 return iterator(&_data[
static_cast<difference_type
>(idx)]);
1617 template <
typename T>
1618 template <
typename InputIt,
1619 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
1626 size_type idx =
static_cast<size_type
>(std::distance(
cbegin(), pos));
1628 transaction::run(pb, [&] { internal_insert(idx, first, last); });
1630 return iterator(&_data[
static_cast<difference_type
>(idx)]);
1661 template <
typename T>
1665 return insert(pos, ilist.begin(), ilist.end());
1695 template <
typename T>
1696 template <
class... Args>
1702 size_type idx =
static_cast<size_type
>(std::distance(
cbegin(), pos));
1704 transaction::run(pb, [&] {
1711 noexcept(T(std::forward<Args>(args)...))>
1712 tmp(std::forward<Args>(args)...);
1714 auto &tmp_ref = tmp.get();
1716 internal_insert(idx, std::make_move_iterator(&tmp_ref),
1717 std::make_move_iterator(&tmp_ref + 1));
1720 return iterator(&_data[
static_cast<difference_type
>(idx)]);
1745 template <
typename T>
1746 template <
class... Args>
1747 typename vector<T>::reference
1757 transaction::run(pb, [&] {
1758 if (_size == _capacity) {
1759 realloc(get_recommended_capacity(_size + 1));
1761 add_data_to_tx(size(), 1);
1764 construct_at_end(1, std::forward<Args>(args)...);
1789 template <
typename T>
1793 return erase(pos, pos + 1);
1818 template <
typename T>
1822 size_type idx =
static_cast<size_type
>(
1823 std::distance(const_iterator(&_data[0]), first));
1824 size_type count =
static_cast<size_type
>(std::distance(first, last));
1827 return iterator(&_data[
static_cast<difference_type
>(idx)]);
1831 transaction::run(pb, [&] {
1832 if (!std::is_trivially_destructible<T>::value ||
1833 idx + count < _size)
1834 add_data_to_tx(idx, _size - idx);
1836 pointer move_begin =
1837 &_data[
static_cast<difference_type
>(idx + count)];
1838 pointer move_end = &_data[
static_cast<difference_type
>(size())];
1839 pointer dest = &_data[
static_cast<difference_type
>(idx)];
1841 std::move(move_begin, move_end, dest);
1846 return iterator(&_data[
static_cast<difference_type
>(idx)]);
1864 template <
typename T>
1868 emplace_back(value);
1887 template <
typename T>
1891 emplace_back(std::move(value));
1904 template <
typename T>
1912 transaction::run(pb, [&] { shrink(size() - 1); });
1931 template <
typename T>
1936 transaction::run(pb, [&] {
1940 if (_capacity < count)
1942 construct_at_end(count - _size);
1964 template <
typename T>
1968 if (_capacity == count)
1972 transaction::run(pb, [&] {
1976 if (_capacity < count)
1978 construct_at_end(count - _size, value);
1986 template <
typename T>
1991 transaction::run(pb, [&] {
1994 std::swap(this->_capacity, other._capacity);
2004 template <
typename T>
2028 template <
typename T>
2032 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2033 assert(_data ==
nullptr);
2036 if (capacity_new > max_size())
2037 throw std::length_error(
"New capacity exceeds max size.");
2039 _capacity = capacity_new;
2041 if (capacity_new == 0)
2050 pmemobj_tx_alloc(
sizeof(value_type) * capacity_new,
2051 detail::type_num<value_type>());
2053 if (res ==
nullptr) {
2054 if (errno == ENOMEM)
2056 "Failed to allocate persistent memory object")
2057 .with_pmemobj_errormsg();
2060 "Failed to allocate persistent memory object")
2061 .with_pmemobj_errormsg();
2073 template <
typename T>
2077 if (
nullptr == pmemobj_pool_by_ptr(
this))
2088 template <
typename T>
2092 if (pmemobj_tx_stage() != TX_STAGE_WORK)
2094 "Function called out of transaction scope.");
2115 template <
typename T>
2116 template <
typename... Args>
2120 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2121 assert(_capacity >= count + _size);
2123 pointer dest = _data.get() + size();
2124 const_pointer
end = dest + count;
2125 for (; dest !=
end; ++dest)
2126 detail::create<value_type, Args...>(
2127 dest, std::forward<Args>(args)...);
2153 template <
typename T>
2154 template <
typename InputIt,
2155 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
2160 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2161 difference_type range_size = std::distance(first, last);
2162 assert(range_size >= 0);
2163 assert(_capacity >=
static_cast<size_type
>(range_size) + _size);
2165 pointer dest = _data.get() + size();
2166 _size +=
static_cast<size_type
>(range_size);
2167 while (first != last)
2168 detail::create<value_type>(dest++, *first++);
2186 template <
typename T>
2190 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2192 if (_data !=
nullptr) {
2194 if (pmemobj_tx_free(*_data.raw_ptr()) != 0)
2196 "failed to delete persistent memory object")
2197 .with_pmemobj_errormsg();
2210 template <
typename T>
2214 auto pop = pmemobj_pool_by_ptr(
this);
2215 assert(pop !=
nullptr);
2226 template <
typename T>
2230 while (first != last && d_last >=
cend())
2231 detail::create<value_type>(--d_last, std::move(*(--last)));
2234 std::move_backward(first, last, d_last);
2244 template <
typename T>
2245 template <
typename InputIt>
2249 auto count =
static_cast<size_type
>(std::distance(first, last));
2250 auto dest = _data.get() + idx;
2251 auto initialized_slots =
static_cast<size_type
>(
cend() - dest);
2255 dest = std::copy_n(first, (std::min)(initialized_slots, count),
2258 std::advance(first, (std::min)(initialized_slots, count));
2261 while (first != last)
2262 detail::create<value_type>(dest++, *first++);
2287 template <
typename T>
2288 template <
typename InputIt>
2292 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2294 auto count =
static_cast<size_type
>(std::distance(first, last));
2296 if (_capacity >= size() + count) {
2298 &_data[
static_cast<difference_type
>(size() + count)];
2299 pointer
begin = &_data[
static_cast<difference_type
>(idx)];
2300 pointer
end = &_data[
static_cast<difference_type
>(size())];
2302 add_data_to_tx(idx, size() - idx + count);
2305 move_elements_backward(
begin,
end, dest);
2308 construct_or_assign(idx, first, last);
2314 add_data_to_tx(0, _size);
2316 auto old_data = _data;
2317 auto old_size = _size;
2318 pointer old_begin = &_data[0];
2319 pointer old_mid = &_data[
static_cast<difference_type
>(idx)];
2320 pointer old_end = &_data[
static_cast<difference_type
>(size())];
2323 _size = _capacity = 0;
2325 alloc(get_recommended_capacity(old_size + count));
2328 construct_at_end(std::make_move_iterator(old_begin),
2329 std::make_move_iterator(old_mid));
2332 construct_at_end(first, last);
2335 construct_at_end(std::make_move_iterator(old_mid),
2336 std::make_move_iterator(old_end));
2339 for (size_type i = 0; i < old_size; ++i)
2340 detail::destroy<value_type>(
2341 old_data[
static_cast<difference_type
>(i)]);
2342 if (pmemobj_tx_free(old_data.raw()) != 0)
2344 "failed to delete persistent memory object")
2345 .with_pmemobj_errormsg();
2366 template <
typename T>
2370 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2376 add_data_to_tx(0, _size);
2378 auto old_data = _data;
2379 auto old_size = _size;
2380 pointer old_begin = &_data[0];
2381 pointer old_end = capacity_new < _size
2382 ? &_data[
static_cast<difference_type
>(capacity_new)]
2383 : &_data[
static_cast<difference_type
>(size())];
2386 _size = _capacity = 0;
2388 alloc(capacity_new);
2390 construct_at_end(std::make_move_iterator(old_begin),
2391 std::make_move_iterator(old_end));
2394 for (size_type i = 0; i < old_size; ++i)
2395 detail::destroy<value_type>(
2396 old_data[
static_cast<difference_type
>(i)]);
2397 if (pmemobj_tx_free(old_data.raw()) != 0)
2399 "failed to delete persistent memory object")
2400 .with_pmemobj_errormsg();
2409 template <
typename T>
2410 typename vector<T>::size_type
2432 template <
typename T>
2436 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2437 assert(size_new <= _size);
2439 if (!std::is_trivially_destructible<T>::value)
2440 add_data_to_tx(size_new, _size - size_new);
2442 for (size_type i = size_new; i < _size; ++i)
2443 detail::destroy<value_type>(
2444 _data[
static_cast<difference_type
>(i)]);
2457 template <
typename T>
2461 assert(idx_first + num <= capacity());
2463 #if LIBPMEMOBJ_CPP_VG_MEMCHECK_ENABLED
2465 assert(VALGRIND_CHECK_MEM_IS_ADDRESSABLE(_data.get() + idx_first,
2466 num *
sizeof(T)) == 0);
2469 auto initialized_num = size() - idx_first;
2472 detail::conditional_add_to_tx(_data.get() + idx_first,
2473 (std::min)(initialized_num, num),
2474 POBJ_XADD_ASSUME_INITIALIZED);
2476 if (num > initialized_num) {
2478 detail::conditional_add_to_tx(_data.get() + size(),
2479 num - initialized_num,
2480 POBJ_XADD_NO_SNAPSHOT);
2495 template <
typename T>
2514 template <
typename T>
2518 return !(lhs == rhs);
2531 template <
typename T>
2535 return std::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(),
2549 template <
typename T>
2553 return !(rhs < lhs);
2567 template <
typename T>
2584 template <
typename T>
2588 return !(lhs < rhs);
2602 template <
typename T>
2606 return lhs.
size() == rhs.size() &&
2607 std::equal(lhs.
begin(), lhs.
end(), rhs.begin());
2621 template <
typename T>
2625 return !(lhs == rhs);
2638 template <
typename T>
2642 return std::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.begin(),
2656 template <
typename T>
2660 return !(std::lexicographical_compare(rhs.begin(), rhs.end(),
2675 template <
typename T>
2679 return !(lhs <= rhs);
2692 template <
typename T>
2696 return !(lhs < rhs);
2710 template <
typename T>
2728 template <
typename T>
2732 return !(lhs == rhs);
2745 template <
typename T>
2762 template <
typename T>
2766 return !(rhs < lhs);
2780 template <
typename T>
2797 template <
typename T>
2801 return !(lhs < rhs);
2810 template <
typename T>