38 #ifndef LIBPMEMOBJ_SEGMENT_VECTOR_HPP 39 #define LIBPMEMOBJ_SEGMENT_VECTOR_HPP 58 namespace experimental
61 namespace segment_vector_internal
70 template <
typename Container,
bool is_const>
74 using iterator_category = std::random_access_iterator_tag;
75 using difference_type = std::ptrdiff_t;
76 using table_type = Container;
77 using size_type =
typename table_type::size_type;
78 using value_type =
typename table_type::value_type;
81 typename std::conditional<is_const,
const table_type *,
84 typename std::conditional<is_const,
85 typename table_type::const_reference,
86 typename table_type::reference>::type;
88 typename std::conditional<is_const,
89 typename table_type::const_pointer,
90 typename table_type::pointer>::type;
110 template <
typename U = void,
111 typename =
typename std::enable_if<is_const, U>::type>
117 segment_iterator
operator+(difference_type idx)
const;
118 segment_iterator &
operator+=(difference_type idx);
121 segment_iterator
operator-(difference_type idx)
const;
122 segment_iterator &
operator-=(difference_type idx);
138 bool operator<(const segment_iterator<Container, C> &rhs);
142 bool operator<=(const segment_iterator<Container, C> &rhs);
154 template <
typename Container,
bool is_const>
156 : table(
nullptr), index()
164 template <
typename Container,
bool is_const>
166 size_type idx) noexcept
167 : table(tab), index(idx)
175 template <
typename Container,
bool is_const>
184 template <
typename Container,
bool is_const>
185 template <
typename U,
typename>
188 : table(other.table), index(other.index)
197 template <
typename Container,
bool is_const>
210 template <
typename Container,
bool is_const>
214 auto iterator = *
this;
224 template <
typename Container,
bool is_const>
236 template <
typename Container,
bool is_const>
240 index +=
static_cast<size_type
>(idx);
249 template <
typename Container,
bool is_const>
262 template <
typename Container,
bool is_const>
266 auto iterator = *
this;
276 template <
typename Container,
bool is_const>
288 template <
typename Container,
bool is_const>
292 index -=
static_cast<size_type
>(idx);
301 template <
typename Container,
bool is_const>
303 typename segment_iterator<Container, is_const>::difference_type
307 return static_cast<difference_type
>(index + rhs.index);
315 template <
typename Container,
bool is_const>
317 typename segment_iterator<Container, is_const>::difference_type
321 return static_cast<difference_type
>(index - rhs.index);
331 template <
typename Container,
bool is_const>
337 return (table == rhs.table) && (index == rhs.index);
348 template <
typename Container,
bool is_const>
354 return (table != rhs.table) || (index != rhs.index);
367 template <
typename Container,
bool is_const>
373 if (table != rhs.table)
374 throw std::invalid_argument(
"segment_iterator::operator<");
376 return index < rhs.index;
390 template <
typename Container,
bool is_const>
396 if (table != rhs.table)
397 throw std::invalid_argument(
"segment_iterator::operator<");
399 return index > rhs.index;
413 template <
typename Container,
bool is_const>
419 if (table != rhs.table)
420 throw std::invalid_argument(
"segment_iterator::operator<");
422 return index <= rhs.index;
436 template <
typename Container,
bool is_const>
442 if (table != rhs.table)
443 throw std::invalid_argument(
"segment_iterator::operator<");
445 return index >= rhs.index;
451 template <
typename Container,
bool is_const>
452 typename segment_iterator<Container, is_const>::reference
455 return table->operator[](index);
461 template <
typename Container,
bool is_const>
462 typename segment_iterator<Container, is_const>::pointer
468 template <
typename Container>
469 using resize_method =
470 decltype(std::declval<Container>().resize(std::declval<size_t>()));
472 template <
typename Container>
473 using container_has_resize = detail::supports<Container, resize_method>;
475 template <typename Container, bool = container_has_resize<Container>::value>
476 struct segment_vector_resize {
477 using segment_vector_type = Container;
480 resize(segment_vector_type &c,
size_t n)
486 template <
typename Container>
487 struct segment_vector_resize<Container, false> {
488 using segment_vector_type = Container;
491 resize(segment_vector_type &c,
size_t n)
496 template <
typename SegmentVectorType,
size_t SegmentSize>
497 class fixed_size_policy {
500 using segment_vector_type = SegmentVectorType;
501 using segment_type =
typename segment_vector_type::value_type;
502 using value_type =
typename segment_type::value_type;
503 using size_type = std::size_t;
505 using segment_vector_resize_type =
506 segment_vector_resize<segment_vector_type>;
508 static constexpr size_type Size = SegmentSize;
511 resize(segment_vector_type &c, size_type n)
513 segment_vector_resize_type::resize(c, n);
522 get_segment(size_type index)
532 segment_top(size_type segment_index)
534 return segment_index * Size;
542 segment_size(size_type segment_index)
552 index_in_segment(size_type index)
561 max_size(
const SegmentVectorType &seg_storage)
563 return seg_storage.max_size() * SegmentSize;
570 capacity(size_type segment_index)
572 return (segment_index + 1) * Size;
576 template <
typename SegmentVectorType>
577 class exponential_size_policy {
580 using segment_vector_type = SegmentVectorType;
581 using segment_type =
typename segment_vector_type::value_type;
582 using value_type =
typename segment_type::value_type;
583 using size_type = std::size_t;
585 using segment_vector_resize_type =
586 segment_vector_resize<segment_vector_type>;
589 resize(segment_vector_type &c, size_type n)
591 segment_vector_resize_type::resize(c, n);
600 get_segment(size_type index)
602 return static_cast<size_type
>(detail::Log2(index | 1));
610 segment_top(size_type segment_index)
612 return (size_type(1) << segment_index) & ~size_type(1);
620 segment_size(size_type segment_index)
622 return (segment_index == 0) ? 2 : segment_top(segment_index);
630 index_in_segment(size_type index)
632 return index - segment_top(get_segment(index));
639 max_size(
const SegmentVectorType &)
641 return segment_size(get_segment(PMEMOBJ_MAX_ALLOC_SIZE /
642 sizeof(value_type)) +
650 capacity(size_type segment_index)
652 if (segment_index == 0)
654 return segment_size(segment_index) * 2;
660 template <
typename SegmentType>
661 using exponential_size_array_policy =
662 segment_vector_internal::exponential_size_policy<
669 template <
typename SegmentType,
size_t SegmentSize>
673 template <
typename SegmentType,
size_t SegmentSize>
674 using fixed_size_vector_policy = segment_vector_internal::fixed_size_policy<
677 template <
typename SegmentType>
678 using exponential_size_vector_policy =
679 segment_vector_internal::exponential_size_policy<
680 pmem::obj::vector<SegmentType>>;
708 template <
typename T,
typename Segment = pmem::obj::vector<T>,
709 typename Policy = exponential_size_array_policy<Segment>>
713 using policy_type = Policy;
714 using segment_type =
typename policy_type::segment_type;
715 using segment_vector_type =
typename policy_type::segment_vector_type;
717 using policy = policy_type;
718 using storage = policy_type;
721 using value_type = T;
722 using size_type = std::size_t;
723 using difference_type = std::ptrdiff_t;
724 using reference = value_type &;
725 using const_reference =
const value_type &;
726 using pointer = value_type *;
727 using const_pointer =
const value_type *;
733 using reverse_iterator = std::reverse_iterator<iterator>;
734 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
738 segment_vector(size_type count,
const value_type &value);
739 explicit segment_vector(size_type count);
740 template <
typename InputIt,
741 typename std::enable_if<
743 InputIt>::type * =
nullptr>
744 segment_vector(InputIt first, InputIt last);
745 segment_vector(
const segment_vector &other);
746 segment_vector(segment_vector &&other);
747 segment_vector(std::initializer_list<T> init);
748 segment_vector(
const std::vector<T> &other);
751 segment_vector &operator=(
const segment_vector &other);
752 segment_vector &operator=(segment_vector &&other);
753 segment_vector &operator=(std::initializer_list<T> ilist);
754 segment_vector &operator=(
const std::vector<T> &other);
757 void assign(size_type count, const_reference value);
758 template <
typename InputIt,
759 typename std::enable_if<
760 detail::is_input_iterator<InputIt>::value,
761 InputIt>::type * =
nullptr>
762 void assign(InputIt first, InputIt last);
763 void assign(std::initializer_list<T> ilist);
764 void assign(
const segment_vector &other);
765 void assign(segment_vector &&other);
766 void assign(
const std::vector<T> &other);
772 reference at(size_type n);
773 const_reference at(size_type n)
const;
774 const_reference const_at(size_type n)
const;
775 reference operator[](size_type n);
776 const_reference operator[](size_type n)
const;
778 const_reference front()
const;
779 const_reference cfront()
const;
781 const_reference back()
const;
782 const_reference cback()
const;
791 reverse_iterator
rbegin();
792 const_reverse_iterator rbegin()
const noexcept;
793 const_reverse_iterator
crbegin()
const noexcept;
794 reverse_iterator
rend();
795 const_reverse_iterator rend()
const noexcept;
796 const_reverse_iterator
crend()
const noexcept;
804 constexpr
bool empty()
const noexcept;
805 size_type size()
const noexcept;
806 constexpr size_type max_size()
const noexcept;
807 void reserve(size_type capacity_new);
808 size_type capacity()
const noexcept;
809 void shrink_to_fit();
817 template <
typename InputIt,
818 typename std::enable_if<
819 detail::is_input_iterator<InputIt>::value,
820 InputIt>::type * =
nullptr>
823 template <
class... Args>
825 template <
class... Args>
826 reference emplace_back(Args &&... args);
829 void push_back(
const T &value);
830 void push_back(T &&value);
832 void resize(size_type count);
833 void resize(size_type count,
const value_type &value);
834 void swap(segment_vector &other);
838 void internal_reserve(size_type new_capacity);
839 template <
typename... Args>
840 void construct(size_type idx, size_type count, Args &&... args);
841 template <
typename InputIt,
842 typename std::enable_if<
843 detail::is_input_iterator<InputIt>::value,
844 InputIt>::type * =
nullptr>
845 void construct_range(size_type idx, InputIt first, InputIt last);
846 void insert_gap(size_type idx, size_type count);
847 void shrink(size_type size_new);
849 void snapshot_data(size_type idx_first, size_type idx_last);
852 reference
get(size_type n);
853 const_reference
get(size_type n)
const;
854 const_reference cget(size_type n)
const;
855 bool segment_capacity_validation()
const;
860 segment_vector_type _data;
864 template <
typename T,
typename Segment,
typename Policy>
873 template <
typename T,
typename Segment,
typename Policy>
876 template <
typename T,
typename Segment,
typename Policy>
879 template <
typename T,
typename Segment,
typename Policy>
880 bool operator<(const segment_vector<T, Segment, Policy> &lhs,
882 template <
typename T,
typename Segment,
typename Policy>
883 bool operator<=(const segment_vector<T, Segment, Policy> &lhs,
885 template <
typename T,
typename Segment,
typename Policy>
888 template <
typename T,
typename Segment,
typename Policy>
897 template <
typename T,
typename Segment,
typename Policy>
899 const std::vector<T> &rhs);
900 template <
typename T,
typename Segment,
typename Policy>
902 const std::vector<T> &rhs);
903 template <
typename T,
typename Segment,
typename Policy>
904 bool operator<(const segment_vector<T, Segment, Policy> &lhs,
905 const std::vector<T> &rhs);
906 template <
typename T,
typename Segment,
typename Policy>
907 bool operator<=(const segment_vector<T, Segment, Policy> &lhs,
908 const std::vector<T> &rhs);
909 template <
typename T,
typename Segment,
typename Policy>
911 const std::vector<T> &rhs);
912 template <
typename T,
typename Segment,
typename Policy>
914 const std::vector<T> &rhs);
920 template <
typename T,
typename Segment,
typename Policy>
923 template <
typename T,
typename Segment,
typename Policy>
926 template <
typename T,
typename Segment,
typename Policy>
927 bool operator<(const std::vector<T> &lhs,
929 template <
typename T,
typename Segment,
typename Policy>
930 bool operator<=(const std::vector<T> &lhs,
932 template <
typename T,
typename Segment,
typename Policy>
933 bool operator>(
const std::vector<T> &lhs,
935 template <
typename T,
typename Segment,
typename Policy>
947 template <
typename T,
typename Segment,
typename Policy>
974 template <
typename T,
typename Segment,
typename Policy>
976 const value_type &value)
978 internal_reserve(count);
979 construct(0, count, value);
1003 template <
typename T,
typename Segment,
typename Policy>
1006 internal_reserve(count);
1007 construct(0, count);
1036 template <
typename T,
typename Segment,
typename Policy>
1037 template <
typename InputIt,
1038 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
1042 internal_reserve(static_cast<size_type>(std::distance(first, last)));
1043 construct_range(0, first, last);
1067 template <
typename T,
typename Segment,
typename Policy>
1070 internal_reserve(other.
capacity());
1071 construct_range(0, other.
cbegin(), other.
cend());
1094 template <
typename T,
typename Segment,
typename Policy>
1097 _data = std::move(other._data);
1098 _segments_used = other._segments_used;
1099 other._segments_used = 0;
1123 template <
typename T,
typename Segment,
typename Policy>
1125 std::initializer_list<T> init)
1151 template <
typename T,
typename Segment,
typename Policy>
1174 template <
typename T,
typename Segment,
typename Policy>
1197 template <
typename T,
typename Segment,
typename Policy>
1201 assign(std::move(other));
1222 template <
typename T,
typename Segment,
typename Policy>
1226 assign(ilist.begin(), ilist.end());
1247 template <
typename T,
typename Segment,
typename Policy>
1277 template <
typename T,
typename Segment,
typename Policy>
1280 const_reference value)
1283 throw std::length_error(
"Assignable range exceeds max size.");
1289 else if (count <
size())
1292 size_type
end = policy::get_segment(count - 1);
1293 for (size_type i = 0; i <
end; ++i)
1294 _data[i].
assign(policy::segment_size(i), value);
1295 _data[
end].assign(count - policy::segment_top(end), value);
1297 _segments_used = end + 1;
1324 template <
typename T,
typename Segment,
typename Policy>
1325 template <
typename InputIt,
1326 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
1331 size_type count =
static_cast<size_type
>(std::distance(first, last));
1333 throw std::length_error(
"Assignable range exceeds max size.");
1339 else if (count <
size())
1342 difference_type num;
1343 size_type
end = policy::get_segment(count - 1);
1344 for (size_type i = 0; i <
end; ++i) {
1345 size_type
size = policy::segment_size(i);
1346 num =
static_cast<difference_type
>(
size);
1347 _data[i].assign(first, std::next(first, num));
1348 std::advance(first, num);
1350 num =
static_cast<difference_type
>(std::distance(first, last));
1351 _data[
end].assign(first, std::next(first, num));
1353 _segments_used = end + 1;
1378 template <
typename T,
typename Segment,
typename Policy>
1382 assign(ilist.begin(), ilist.end());
1401 template <
typename T,
typename Segment,
typename Policy>
1424 template <
typename T,
typename Segment,
typename Policy>
1433 _data = std::move(other._data);
1434 _segments_used = other._segments_used;
1435 other._segments_used = 0;
1455 template <
typename T,
typename Segment,
typename Policy>
1459 assign(other.cbegin(), other.cend());
1473 template <
typename T,
typename Segment,
typename Policy>
1492 template <
typename T,
typename Segment,
typename Policy>
1493 typename segment_vector<T, Segment, Policy>::reference
1497 throw std::out_of_range(
"segment_vector::at");
1499 detail::conditional_add_to_tx(&
get(n), 1, POBJ_XADD_ASSUME_INITIALIZED);
1514 template <
typename T,
typename Segment,
typename Policy>
1515 typename segment_vector<T, Segment, Policy>::const_reference
1519 throw std::out_of_range(
"segment_vector::at");
1535 template <
typename T,
typename Segment,
typename Policy>
1536 typename segment_vector<T, Segment, Policy>::const_reference
1540 throw std::out_of_range(
"segment_vector::const_at");
1555 template <
typename T,
typename Segment,
typename Policy>
1556 typename segment_vector<T, Segment, Policy>::reference
1559 reference element =
get(n);
1561 detail::conditional_add_to_tx(&element, 1,
1562 POBJ_XADD_ASSUME_INITIALIZED);
1574 template <
typename T,
typename Segment,
typename Policy>
1575 typename segment_vector<T, Segment, Policy>::const_reference
1589 template <
typename T,
typename Segment,
typename Policy>
1590 typename segment_vector<T, Segment, Policy>::reference
1593 detail::conditional_add_to_tx(&_data[0][0], 1,
1594 POBJ_XADD_ASSUME_INITIALIZED);
1604 template <
typename T,
typename Segment,
typename Policy>
1605 typename segment_vector<T, Segment, Policy>::const_reference
1618 template <
typename T,
typename Segment,
typename Policy>
1619 typename segment_vector<T, Segment, Policy>::const_reference
1633 template <
typename T,
typename Segment,
typename Policy>
1634 typename segment_vector<T, Segment, Policy>::reference
1637 reference element =
get(
size() - 1);
1639 detail::conditional_add_to_tx(&element, 1,
1640 POBJ_XADD_ASSUME_INITIALIZED);
1650 template <
typename T,
typename Segment,
typename Policy>
1651 typename segment_vector<T, Segment, Policy>::const_reference
1654 return get(
size() - 1);
1664 template <
typename T,
typename Segment,
typename Policy>
1665 typename segment_vector<T, Segment, Policy>::const_reference
1668 return get(
size() - 1);
1676 template <
typename T,
typename Segment,
typename Policy>
1689 template <
typename T,
typename Segment,
typename Policy>
1704 template <
typename T,
typename Segment,
typename Policy>
1717 template <
typename T,
typename Segment,
typename Policy>
1730 template <
typename T,
typename Segment,
typename Policy>
1745 template <
typename T,
typename Segment,
typename Policy>
1758 template <
typename T,
typename Segment,
typename Policy>
1759 typename segment_vector<T, Segment, Policy>::reverse_iterator
1762 return reverse_iterator(
end());
1771 template <
typename T,
typename Segment,
typename Policy>
1772 typename segment_vector<T, Segment, Policy>::const_reverse_iterator
1775 return const_reverse_iterator(
end());
1786 template <
typename T,
typename Segment,
typename Policy>
1787 typename segment_vector<T, Segment, Policy>::const_reverse_iterator
1799 template <
typename T,
typename Segment,
typename Policy>
1800 typename segment_vector<T, Segment, Policy>::reverse_iterator
1803 return reverse_iterator(
begin());
1812 template <
typename T,
typename Segment,
typename Policy>
1813 typename segment_vector<T, Segment, Policy>::const_reverse_iterator
1816 return const_reverse_iterator(
begin());
1827 template <
typename T,
typename Segment,
typename Policy>
1828 typename segment_vector<T, Segment, Policy>::const_reverse_iterator
1847 template <
typename T,
typename Segment,
typename Policy>
1851 if (start + n >
size())
1852 throw std::out_of_range(
"segment_vector::range");
1870 template <
typename T,
typename Segment,
typename Policy>
1874 if (start + n >
size())
1875 throw std::out_of_range(
"segment_vector::range");
1891 template <
typename T,
typename Segment,
typename Policy>
1895 if (start + n >
size())
1896 throw std::out_of_range(
"segment_vector::range");
1906 template <
typename T,
typename Segment,
typename Policy>
1916 template <
typename T,
typename Segment,
typename Policy>
1917 typename segment_vector<T, Segment, Policy>::size_type
1920 size_type result = 0;
1921 for (size_type i = 0; i < _segments_used; ++i)
1922 result += _data.const_at(i).size();
1930 template <
typename T,
typename Segment,
typename Policy>
1931 constexpr
typename segment_vector<T, Segment, Policy>::size_type
1934 return policy::max_size(_data);
1953 template <
typename T,
typename Segment,
typename Policy>
1968 template <
typename T,
typename Segment,
typename Policy>
1969 typename segment_vector<T, Segment, Policy>::size_type
1972 if (_segments_used == 0)
1974 return policy::capacity(_segments_used - 1);
1988 template <
typename T,
typename Segment,
typename Policy>
1992 size_type new_last = policy::get_segment(
size() - 1);
1993 if (_segments_used - 1 == new_last)
1998 for (size_type i = new_last + 1; i < _segments_used; ++i)
2000 _segments_used = new_last + 1;
2001 storage::resize(_data, _segments_used);
2016 template <
typename T,
typename Segment,
typename Policy>
2037 template <
typename T,
typename Segment,
typename Policy>
2043 for (size_type i = 0; i < _segments_used; ++i)
2072 template <
typename T,
typename Segment,
typename Policy>
2076 return insert(pos, 1, value);
2102 template <
typename T,
typename Segment,
typename Policy>
2106 size_type idx =
static_cast<size_type
>(pos -
cbegin());
2111 get(idx) = std::move(value);
2143 template <
typename T,
typename Segment,
typename Policy>
2148 size_type idx =
static_cast<size_type
>(pos -
cbegin());
2153 for (size_type i = idx; i < idx + count; ++i)
2154 get(i) = std::move(value);
2193 template <
typename T,
typename Segment,
typename Policy>
2194 template <
typename InputIt,
2195 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
2201 size_type idx =
static_cast<size_type
>(pos -
cbegin());
2202 size_type gap_size =
static_cast<size_type
>(std::distance(first, last));
2207 for (size_type i = idx; i < idx + gap_size; ++i, ++first)
2240 template <
typename T,
typename Segment,
typename Policy>
2243 std::initializer_list<T> ilist)
2245 return insert(pos, ilist.begin(), ilist.end());
2276 template <
typename T,
typename Segment,
typename Policy>
2277 template <
class... Args>
2281 size_type idx =
static_cast<size_type
>(pos -
cbegin());
2286 noexcept(T(std::forward<Args>(args)...))>
2287 tmp(std::forward<Args>(args)...);
2289 get(idx) = std::move(tmp.get());
2319 template <
typename T,
typename Segment,
typename Policy>
2320 template <
class... Args>
2321 typename segment_vector<T, Segment, Policy>::reference
2331 size_type segment = policy::get_segment(
size());
2332 _data[segment].emplace_back(std::forward<Args>(args)...);
2359 template <
typename T,
typename Segment,
typename Policy>
2363 return erase(pos, pos + 1);
2390 template <
typename T,
typename Segment,
typename Policy>
2395 size_type count =
static_cast<size_type
>(std::distance(first, last));
2396 size_type idx =
static_cast<size_type
>(first -
cbegin());
2403 size_type _size =
size();
2412 std::move(begin, end, dest);
2416 size_type middle = policy::get_segment(_size - count);
2417 size_type last = policy::get_segment(_size - 1);
2418 size_type middle_size = policy::index_in_segment(_size - count);
2419 for (size_type s = last; s > middle; --s)
2421 _data[middle].resize(middle_size);
2423 _segments_used = middle + 1;
2449 template <
typename T,
typename Segment,
typename Policy>
2474 template <
typename T,
typename Segment,
typename Policy>
2494 template <
typename T,
typename Segment,
typename Policy>
2529 template <
typename T,
typename Segment,
typename Policy>
2535 size_type _size =
size();
2571 template <
typename T,
typename Segment,
typename Policy>
2574 const value_type &value)
2578 size_type _size =
size();
2593 template <
typename T,
typename Segment,
typename Policy>
2599 _data.swap(other._data);
2600 std::swap(_segments_used, other._segments_used);
2620 template <
typename T,
typename Segment,
typename Policy>
2624 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2627 throw std::length_error(
"New capacity exceeds max size.");
2629 if (new_capacity == 0)
2632 size_type old_idx = policy::get_segment(
capacity());
2633 size_type new_idx = policy::get_segment(new_capacity - 1);
2634 storage::resize(_data, new_idx + 1);
2635 for (size_type i = old_idx; i <= new_idx; ++i) {
2636 size_type segment_capacity = policy::segment_size(i);
2637 _data[i].reserve(segment_capacity);
2639 _segments_used = new_idx + 1;
2670 template <
typename T,
typename Segment,
typename Policy>
2671 template <
typename... Args>
2676 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2677 assert(_segments_used - 1 >= policy::get_segment(
size() + count - 1));
2679 for (size_type i = idx; i < idx + count; ++i) {
2680 size_type segment = policy::get_segment(i);
2681 _data[segment].emplace_back(std::forward<Args>(args)...);
2715 template <
typename T,
typename Segment,
typename Policy>
2716 template <
typename InputIt,
2717 typename std::enable_if<detail::is_input_iterator<InputIt>::value,
2721 InputIt first, InputIt last)
2723 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2724 size_type count =
static_cast<size_type
>(std::distance(first, last));
2726 assert(_segments_used - 1 >= policy::get_segment(
size() + count - 1));
2728 for (size_type i = idx; i < idx + count; ++i, ++first) {
2729 size_type segment = policy::get_segment(i);
2730 _data[segment].emplace_back(*first);
2755 template <
typename T,
typename Segment,
typename Policy>
2759 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2761 size_type _size =
size();
2773 std::move_backward(begin, end, dest);
2797 template <
typename T,
typename Segment,
typename Policy>
2801 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2802 assert(size_new <=
size());
2806 size_type
begin = policy::get_segment(
size() - 1);
2807 size_type
end = policy::get_segment(size_new);
2809 _data[
begin].clear();
2811 size_type residue = policy::index_in_segment(size_new);
2812 _data[
end].erase(_data[end].
cbegin() + residue, _data[end].
cend());
2822 template <
typename T,
typename Segment,
typename Policy>
2826 auto pop = pmemobj_pool_by_ptr(
this);
2827 assert(pop !=
nullptr);
2840 template <
typename T,
typename Segment,
typename Policy>
2848 size_type segment = policy::get_segment(first);
2849 size_type
end = policy::get_segment(last - 1);
2850 size_type count = policy::segment_top(segment + 1) - first;
2852 while (segment != end) {
2853 detail::conditional_add_to_tx(&
cget(first), count,
2854 POBJ_XADD_ASSUME_INITIALIZED);
2855 first = policy::segment_top(++segment);
2856 count = policy::segment_size(segment);
2858 detail::conditional_add_to_tx(&
cget(first), last - first,
2859 POBJ_XADD_ASSUME_INITIALIZED);
2867 template <
typename T,
typename Segment,
typename Policy>
2868 typename segment_vector<T, Segment, Policy>::reference
2871 size_type s_idx = policy::get_segment(n);
2872 size_type local_idx = policy::index_in_segment(n);
2874 return _data[s_idx][local_idx];
2882 template <
typename T,
typename Segment,
typename Policy>
2883 typename segment_vector<T, Segment, Policy>::const_reference
2886 size_type s_idx = policy::get_segment(n);
2887 size_type local_idx = policy::index_in_segment(n);
2889 return _data[s_idx][local_idx];
2897 template <
typename T,
typename Segment,
typename Policy>
2898 typename segment_vector<T, Segment, Policy>::const_reference
2901 size_type s_idx = policy::get_segment(n);
2902 size_type local_idx = policy::index_in_segment(n);
2904 return _data[s_idx][local_idx];
2914 template <
typename T,
typename Segment,
typename Policy>
2918 for (size_type i = 0; i < _segments_used; ++i)
2919 if (_data.const_at(i).capacity() != policy::segment_size(i))
2930 template <
typename T,
typename Segment,
typename Policy>
2952 template <
typename T,
typename Segment,
typename Policy>
2976 template <
typename T,
typename Segment,
typename Policy>
2981 return !(lhs == rhs);
2996 template <
typename T,
typename Segment,
typename Policy>
2998 operator<(const segment_vector<T, Segment, Policy> &lhs,
3001 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.
begin(),
3017 template <
typename T,
typename Segment,
typename Policy>
3019 operator<=(const segment_vector<T, Segment, Policy> &lhs,
3022 return !(rhs < lhs);
3037 template <
typename T,
typename Segment,
typename Policy>
3057 template <
typename T,
typename Segment,
typename Policy>
3062 return !(lhs < rhs);
3078 template <
typename T,
typename Segment,
typename Policy>
3081 const std::vector<T> &rhs)
3083 return lhs.
size() == rhs.size() &&
3084 std::equal(lhs.
begin(), lhs.
end(), rhs.begin());
3100 template <
typename T,
typename Segment,
typename Policy>
3103 const std::vector<T> &rhs)
3105 return !(lhs == rhs);
3119 template <
typename T,
typename Segment,
typename Policy>
3121 operator<(const segment_vector<T, Segment, Policy> &lhs,
3122 const std::vector<T> &rhs)
3124 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.
begin(),
3139 template <
typename T,
typename Segment,
typename Policy>
3141 operator<=(const segment_vector<T, Segment, Policy> &lhs,
3142 const std::vector<T> &rhs)
3144 return !(std::lexicographical_compare(rhs.
begin(), rhs.
end(),
3145 lhs.begin(), lhs.end()));
3160 template <
typename T,
typename Segment,
typename Policy>
3163 const std::vector<T> &rhs)
3165 return !(lhs <= rhs);
3179 template <
typename T,
typename Segment,
typename Policy>
3182 const std::vector<T> &rhs)
3184 return !(lhs < rhs);
3200 template <
typename T,
typename Segment,
typename Policy>
3202 operator==(
const std::vector<T> &lhs,
3221 template <
typename T,
typename Segment,
typename Policy>
3223 operator!=(
const std::vector<T> &lhs,
3226 return !(lhs == rhs);
3240 template <
typename T,
typename Segment,
typename Policy>
3242 operator<(const std::vector<T> &lhs,
3259 template <
typename T,
typename Segment,
typename Policy>
3261 operator<=(const std::vector<T> &lhs,
3264 return !(rhs < lhs);
3279 template <
typename T,
typename Segment,
typename Policy>
3281 operator>(
const std::vector<T> &lhs,
3298 template <
typename T,
typename Segment,
typename Policy>
3300 operator>=(
const std::vector<T> &lhs,
3303 return !(lhs < rhs);
void construct_range(size_type idx, InputIt first, InputIt last)
Private helper function.
Definition: segment_vector.hpp:2720
iterator insert(const_iterator pos, const T &value)
Inserts value before pos in the container transactionally.
Definition: segment_vector.hpp:2074
size_type capacity() const noexcept
Definition: segment_vector.hpp:1970
reference get(size_type n)
Private helper function.
Definition: segment_vector.hpp:2869
bool operator>(const segment_iterator< Container, C > &rhs)
Greater operator.
Definition: segment_vector.hpp:394
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:913
reference front()
Access the first element and add this element to a transaction.
Definition: segment_vector.hpp:1591
pool_base get_pool() const noexcept
Private helper function.
Definition: segment_vector.hpp:2824
const_reference cback() const
Access the last element.
Definition: segment_vector.hpp:1666
Persistent_ptr transactional allocation functions for objects.
pmem::obj::array< T, N >::reverse_iterator rend(pmem::obj::array< T, N > &a)
Non-member rend.
Definition: array.hpp:893
pmem::obj::array< T, N >::const_reverse_iterator crend(const pmem::obj::array< T, N > &a)
Non-member crend.
Definition: array.hpp:823
const_iterator cend() const noexcept
Returns a const iterator to the end.
Definition: segment_vector.hpp:1747
segment_iterator & operator--()
Prefix decrement.
Definition: segment_vector.hpp:251
The non-template pool base class.
Definition: pool.hpp:67
temp_value template class for caching objects.
~segment_vector()
Destructor.
Definition: segment_vector.hpp:1474
Segment table is a data type with a vector-like interface The difference is that it does not do reall...
Definition: segment_vector.hpp:710
iterator begin()
Returns an iterator to the beginning.
Definition: segment_vector.hpp:1678
void free_data()
Clears the content of a segment_vector and frees all allocated persistent memory for data transaction...
Definition: segment_vector.hpp:2039
void pop_back()
Removes the last element of the container transactionally.
Definition: segment_vector.hpp:2496
constexpr bool empty() const noexcept
Checks whether the container is empty.
Definition: segment_vector.hpp:1908
pmem::obj::slice - provides interface to access sequence of objects.
Definition: slice.hpp:56
segment_vector_internal::fixed_size_policy< pmem::obj::array< SegmentType, 255 >, SegmentSize > fixed_size_array_policy
XXX: In case of array of segments with fixed segments size we can allocate as much memory as we want...
Definition: segment_vector.hpp:671
void shrink_to_fit()
Requests transactional removal of unused capacity.
Definition: segment_vector.hpp:1990
segment_iterator & operator-=(difference_type idx)
Random access decrementing with assignment.
Definition: segment_vector.hpp:290
C++ pmemobj transactions.
Convenience extensions for the resides on pmem property template.
const_reference cfront() const
Access the first element.
Definition: segment_vector.hpp:1620
void construct(size_type idx, size_type count, Args &&... args)
Private helper function.
Definition: segment_vector.hpp:2673
void push_back(const T &value)
Appends the given element value to the end of the container transactionally.
Definition: segment_vector.hpp:2451
Functions for destroying arrays.
Commonly used functionality.
iterator end()
Returns an iterator to past the end.
Definition: segment_vector.hpp:1719
pmem::obj::array< T, N >::const_reverse_iterator crbegin(const pmem::obj::array< T, N > &a)
Non-member crbegin.
Definition: array.hpp:813
Iterator for segment_vector Since a constant iterator differs only in the type of references and poin...
Definition: segment_vector.hpp:71
void shrink(size_type size_new)
Private helper function.
Definition: segment_vector.hpp:2799
segment_iterator & operator+=(difference_type idx)
Random access incrementing with assignment.
Definition: segment_vector.hpp:238
void reserve(size_type capacity_new)
Increases the capacity of the segment_vector to capacity_new transactionally.
Definition: segment_vector.hpp:1955
iterator emplace(const_iterator pos, Args &&... args)
Inserts a new element into the container directly before pos.
Definition: segment_vector.hpp:2279
void swap(segment_vector &other)
Exchanges the contents of the container with other transactionally.
Definition: segment_vector.hpp:2595
const_reverse_iterator crbegin() const noexcept
Returns a const reverse iterator to the beginning.
Definition: segment_vector.hpp:1788
bool operator==(const segment_iterator< Container, C > &rhs)
Compare methods Template parameter is needed to enable this methods work with non-constant and consta...
Definition: segment_vector.hpp:335
const_reference const_at(size_type n) const
Access element at specific index with bounds checking.
Definition: segment_vector.hpp:1537
slice< iterator > range(size_type start, size_type n)
Returns slice and snapshots requested range.
Definition: segment_vector.hpp:1849
void assign(size_type count, const_reference value)
Replaces the contents with count copies of value value transactionally.
Definition: segment_vector.hpp:1279
bool operator>=(const segment_iterator< Container, C > &rhs)
Greater or equal operator.
Definition: segment_vector.hpp:440
reference at(size_type n)
Access element at specific index with bounds checking and add it to a transaction.
Definition: segment_vector.hpp:1494
Array container with std::array compatible interface.
reference emplace_back(Args &&... args)
Appends a new element to the end of the container transactionally.
Definition: segment_vector.hpp:2322
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:853
constexpr size_type max_size() const noexcept
Definition: segment_vector.hpp:1932
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:833
const_reference cget(size_type n) const
Private helper function.
Definition: segment_vector.hpp:2899
segment_iterator & operator++()
Prefix increment.
Definition: segment_vector.hpp:199
Template class for caching objects based on constructor's variadic template arguments and LIBPMEMOBJ_...
Definition: temp_value.hpp:64
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: segment_vector.hpp:1760
pmem::obj::vector - persistent container with std::vector compatible interface.
Definition: vector.hpp:69
void internal_reserve(size_type new_capacity)
Private helper method.
Definition: segment_vector.hpp:2622
reference operator*() const
Indirection (dereference).
Definition: segment_vector.hpp:453
segment_vector & operator=(const segment_vector &other)
Copy assignment operator.
Definition: segment_vector.hpp:1176
bool segment_capacity_validation() const
Private helper function.
Definition: segment_vector.hpp:2916
segment_iterator operator-(difference_type idx) const
Random access decrementing.
Definition: segment_vector.hpp:278
Vector container with std::vector compatible interface.
Commonly used SFINAE helpers.
Persistent smart pointer.
const_iterator cbegin() const noexcept
Returns const iterator to the beginning.
Definition: segment_vector.hpp:1706
size_type size() const noexcept
Definition: segment_vector.hpp:1918
iterator erase(const_iterator pos)
Removes the element at pos.
Definition: segment_vector.hpp:2361
const_reverse_iterator crend() const noexcept
Returns a const reverse iterator to the beginning.
Definition: segment_vector.hpp:1829
segment_vector()
Default constructor.
Definition: segment_vector.hpp:948
pmem::obj::array< T, N >::const_iterator cbegin(const pmem::obj::array< T, N > &a)
Non-member cbegin.
Definition: array.hpp:793
segment_iterator operator+(difference_type idx) const
Random access incrementing.
Definition: segment_vector.hpp:226
void insert_gap(size_type idx, size_type count)
Private helper function.
Definition: segment_vector.hpp:2757
reference back()
Access the last element and add this element to a transaction.
Definition: segment_vector.hpp:1635
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: segment_vector.hpp:1801
bool operator<(const segment_iterator< Container, C > &rhs)
Less operator.
Definition: segment_vector.hpp:371
bool operator!=(const segment_iterator< Container, C > &rhs)
Not equal operator.
Definition: segment_vector.hpp:352
pointer operator->() const
Member access.
Definition: segment_vector.hpp:463
void clear()
Clears the content of a segment_vector transactionally.
Definition: segment_vector.hpp:2018
A persistent version of concurrent hash map implementation Ref: https://arxiv.org/abs/1509.02235.
Definition: allocation_flag.hpp:43
reference operator[](size_type n)
Access element at specific index and add it to a transaction.
Definition: segment_vector.hpp:1557
pmem::obj::array< T, N >::reverse_iterator rbegin(pmem::obj::array< T, N > &a)
Non-member rbegin.
Definition: array.hpp:873
segment_iterator() noexcept
Default constructor.
Definition: segment_vector.hpp:155
void snapshot_data(size_type idx_first, size_type idx_last)
Private helper function.
Definition: segment_vector.hpp:2842
pmem::obj::array< T, N >::const_iterator cend(const pmem::obj::array< T, N > &a)
Non-member cend.
Definition: array.hpp:803
bool operator<=(const segment_iterator< Container, C > &rhs)
Less or equal operator.
Definition: segment_vector.hpp:417
slice< const_iterator > crange(size_type start, size_type n) const
Returns const slice.
Definition: segment_vector.hpp:1893
void resize(size_type count)
Resizes the container to count elements transactionally.
Definition: segment_vector.hpp:2531
pmem::obj::array - persistent container with std::array compatible interface.
Definition: array.hpp:74
static void run(pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:403