segment_vector.hpp

Go to the documentation of this file.

/*
 * Copyright 2019, Intel Corporation
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in
 *       the documentation and/or other materials provided with the
 *       distribution.
 *
 *     * Neither the name of the copyright holder nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef LIBPMEMOBJ_SEGMENT_VECTOR_HPP
#define LIBPMEMOBJ_SEGMENT_VECTOR_HPP

#include <libpmemobj++/container/array.hpp>
#include <libpmemobj++/container/vector.hpp>
#include <libpmemobj++/detail/common.hpp>
#include <libpmemobj++/detail/life.hpp>
#include <libpmemobj++/detail/temp_value.hpp>
#include <libpmemobj++/detail/template_helpers.hpp>
#include <libpmemobj++/make_persistent.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/transaction.hpp>

#include <vector>

namespace pmem
{
namespace obj
{
namespace experimental
{

namespace segment_vector_internal
{
template <typename Container, bool is_const>
class segment_iterator {
public:
    /* Traits */
    using iterator_category = std::random_access_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using table_type = Container;
    using size_type = typename table_type::size_type;
    using value_type = typename table_type::value_type;
    /* Constant dependent traits */
    using table_ptr =
        typename std::conditional<is_const, const table_type *,
                      table_type *>::type;
    using reference =
        typename std::conditional<is_const,
                      typename table_type::const_reference,
                      typename table_type::reference>::type;
    using pointer =
        typename std::conditional<is_const,
                      typename table_type::const_pointer,
                      typename table_type::pointer>::type;

    /* To implement methods where operands differ in constancy */
    friend class segment_iterator<Container, true>;
    friend class segment_iterator<Container, false>;

private:
    /* Pointer to container for iteration */
    table_ptr table;
    /* Index of element in the container */
    size_type index;

public:
    /* Сonstructors */
    segment_iterator() noexcept;
    explicit segment_iterator(table_ptr tab, size_type idx) noexcept;
    segment_iterator(const segment_iterator &other);

    /* Copy ctor to enable conversion from non-const to const
     * iterator */
    template <typename U = void,
          typename = typename std::enable_if<is_const, U>::type>
    segment_iterator(const segment_iterator<Container, false> &other);

    /* In(de)crement methods */
    segment_iterator &operator++();
    segment_iterator operator++(int);
    segment_iterator operator+(difference_type idx) const;
    segment_iterator &operator+=(difference_type idx);
    segment_iterator &operator--();
    segment_iterator operator--(int);
    segment_iterator operator-(difference_type idx) const;
    segment_iterator &operator-=(difference_type idx);
    template <bool C>
    difference_type
    operator+(const segment_iterator<Container, C> &rhs) const;
    template <bool C>
    difference_type
    operator-(const segment_iterator<Container, C> &rhs) const;

    template <bool C>
    bool operator==(const segment_iterator<Container, C> &rhs) const;
    template <bool C>
    bool operator!=(const segment_iterator<Container, C> &rhs) const;
    template <bool C>
    bool operator<(const segment_iterator<Container, C> &rhs) const;
    template <bool C>
    bool operator>(const segment_iterator<Container, C> &rhs) const;
    template <bool C>
    bool operator<=(const segment_iterator<Container, C> &rhs) const;
    template <bool C>
    bool operator>=(const segment_iterator<Container, C> &rhs) const;

    /* Access methods */
    reference operator*() const;
    pointer operator->() const;
};

template <typename Container, bool is_const>
segment_iterator<Container, is_const>::segment_iterator() noexcept
    : table(nullptr), index()
{
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const>::segment_iterator(table_ptr tab,
                            size_type idx) noexcept
    : table(tab), index(idx)
{
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const>::segment_iterator(
    const segment_iterator &other)
    : table(other.table), index(other.index)
{
}

template <typename Container, bool is_const>
template <typename U, typename>
segment_iterator<Container, is_const>::segment_iterator(
    const segment_iterator<Container, false> &other)
    : table(other.table), index(other.index)
{
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const> &
segment_iterator<Container, is_const>::operator++()
{
    ++index;
    return *this;
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const>
segment_iterator<Container, is_const>::operator++(int)
{
    auto iterator = *this;
    ++*this;
    return iterator;
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const>
segment_iterator<Container, is_const>::operator+(difference_type idx) const
{
    return segment_iterator(table, index + static_cast<size_type>(idx));
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const> &
segment_iterator<Container, is_const>::operator+=(difference_type idx)
{
    index += static_cast<size_type>(idx);
    return *this;
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const> &
segment_iterator<Container, is_const>::operator--()
{
    --index;
    return *this;
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const>
segment_iterator<Container, is_const>::operator--(int)
{
    auto iterator = *this;
    --*this;
    return iterator;
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const>
segment_iterator<Container, is_const>::operator-(difference_type idx) const
{
    return segment_iterator(table, index - static_cast<size_type>(idx));
}

template <typename Container, bool is_const>
segment_iterator<Container, is_const> &
segment_iterator<Container, is_const>::operator-=(difference_type idx)
{
    index -= static_cast<size_type>(idx);
    return *this;
}

template <typename Container, bool is_const>
template <bool C>
typename segment_iterator<Container, is_const>::difference_type
segment_iterator<Container, is_const>::
operator+(const segment_iterator<Container, C> &rhs) const
{
    return static_cast<difference_type>(index + rhs.index);
}

template <typename Container, bool is_const>
template <bool C>
typename segment_iterator<Container, is_const>::difference_type
segment_iterator<Container, is_const>::
operator-(const segment_iterator<Container, C> &rhs) const
{
    return static_cast<difference_type>(index - rhs.index);
}

template <typename Container, bool is_const>
template <bool C>
bool
segment_iterator<Container, is_const>::
operator==(const segment_iterator<Container, C> &rhs) const
{
    return (table == rhs.table) && (index == rhs.index);
}

template <typename Container, bool is_const>
template <bool C>
bool
segment_iterator<Container, is_const>::
operator!=(const segment_iterator<Container, C> &rhs) const
{
    return (table != rhs.table) || (index != rhs.index);
}

template <typename Container, bool is_const>
template <bool C>
bool
segment_iterator<Container, is_const>::
operator<(const segment_iterator<Container, C> &rhs) const
{
    if (table != rhs.table)
        throw std::invalid_argument("segment_iterator::operator<");

    return index < rhs.index;
}

template <typename Container, bool is_const>
template <bool C>
bool
segment_iterator<Container, is_const>::
operator>(const segment_iterator<Container, C> &rhs) const
{
    if (table != rhs.table)
        throw std::invalid_argument("segment_iterator::operator<");

    return index > rhs.index;
}

template <typename Container, bool is_const>
template <bool C>
bool
segment_iterator<Container, is_const>::
operator<=(const segment_iterator<Container, C> &rhs) const
{
    if (table != rhs.table)
        throw std::invalid_argument("segment_iterator::operator<");

    return index <= rhs.index;
}

template <typename Container, bool is_const>
template <bool C>
bool
segment_iterator<Container, is_const>::
operator>=(const segment_iterator<Container, C> &rhs) const
{
    if (table != rhs.table)
        throw std::invalid_argument("segment_iterator::operator<");

    return index >= rhs.index;
}

template <typename Container, bool is_const>
typename segment_iterator<Container, is_const>::reference
    segment_iterator<Container, is_const>::operator*() const
{
    return table->operator[](index);
}

template <typename Container, bool is_const>
typename segment_iterator<Container, is_const>::pointer
    segment_iterator<Container, is_const>::operator->() const
{
    return &operator*();
}

template <typename Container>
using resize_method =
    decltype(std::declval<Container>().resize(std::declval<size_t>()));

template <typename Container>
using container_has_resize = detail::supports<Container, resize_method>;

template <typename Container, bool = container_has_resize<Container>::value>
struct segment_vector_resize {
    using segment_vector_type = Container;

    static void
    resize(segment_vector_type &c, size_t n)
    {
        c.resize(n);
    }
};

template <typename Container>
struct segment_vector_resize<Container, false> {
    using segment_vector_type = Container;

    static void
    resize(segment_vector_type &c, size_t n)
    {
    }
};

template <typename SegmentVectorType, size_t SegmentSize>
class fixed_size_policy {
public:
    /* Traits */
    using segment_vector_type = SegmentVectorType;
    using segment_type = typename segment_vector_type::value_type;
    using value_type = typename segment_type::value_type;
    using size_type = std::size_t;

    using segment_vector_resize_type =
        segment_vector_resize<segment_vector_type>;

    static constexpr size_type Size = SegmentSize;

    static void
    resize(segment_vector_type &c, size_type n)
    {
        segment_vector_resize_type::resize(c, n);
    }

    static size_type
    get_segment(size_type index)
    {
        return index / Size;
    }
    static size_type
    segment_top(size_type segment_index)
    {
        return segment_index * Size;
    }
    static size_type
    segment_size(size_type segment_index)
    {
        return Size;
    }
    static size_type
    index_in_segment(size_type index)
    {
        return index % Size;
    }

    static size_type
    max_size(const SegmentVectorType &seg_storage)
    {
        return seg_storage.max_size() * SegmentSize;
    }

    static size_type
    capacity(size_type segment_index)
    {
        return (segment_index + 1) * Size;
    }
};

template <typename SegmentVectorType>
class exponential_size_policy {
public:
    /* Traits */
    using segment_vector_type = SegmentVectorType;
    using segment_type = typename segment_vector_type::value_type;
    using value_type = typename segment_type::value_type;
    using size_type = std::size_t;

    using segment_vector_resize_type =
        segment_vector_resize<segment_vector_type>;

    static void
    resize(segment_vector_type &c, size_type n)
    {
        segment_vector_resize_type::resize(c, n);
    }

    static size_type
    get_segment(size_type index)
    {
        return static_cast<size_type>(detail::Log2(index | 1));
    }
    static size_type
    segment_top(size_type segment_index)
    {
        return (size_type(1) << segment_index) & ~size_type(1);
    }
    static size_type
    segment_size(size_type segment_index)
    {
        return (segment_index == 0) ? 2 : segment_top(segment_index);
    }
    static size_type
    index_in_segment(size_type index)
    {
        return index - segment_top(get_segment(index));
    }

    static size_t
    max_size(const SegmentVectorType &)
    {
        return segment_size(get_segment(PMEMOBJ_MAX_ALLOC_SIZE /
                        sizeof(value_type)) +
                    1);
    }

    static size_type
    capacity(size_type segment_index)
    {
        if (segment_index == 0)
            return 2;
        return segment_size(segment_index) * 2;
    }
};

} /* segment_vector_internal namespace */

template <typename SegmentType>
using exponential_size_array_policy =
    segment_vector_internal::exponential_size_policy<
        pmem::obj::array<SegmentType, 64>>;

template <typename SegmentType, size_t SegmentSize>
using fixed_size_array_policy = segment_vector_internal::fixed_size_policy<
    pmem::obj::array<SegmentType, 255>, SegmentSize>;

template <typename SegmentType, size_t SegmentSize>
using fixed_size_vector_policy = segment_vector_internal::fixed_size_policy<
    pmem::obj::vector<SegmentType>, SegmentSize>;

template <typename SegmentType>
using exponential_size_vector_policy =
    segment_vector_internal::exponential_size_policy<
        pmem::obj::vector<SegmentType>>;

template <typename T, typename Segment = pmem::obj::vector<T>,
      typename Policy = exponential_size_array_policy<Segment>>
class segment_vector {
public:
    /* Specific traits*/
    using policy_type = Policy;
    using segment_type = typename policy_type::segment_type;
    using segment_vector_type = typename policy_type::segment_vector_type;
    /* Simple access to methods */
    using policy = policy_type;
    using storage = policy_type;

    /* Traits */
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = value_type &;
    using const_reference = const value_type &;
    using pointer = value_type *;
    using const_pointer = const value_type *;
    using iterator =
        segment_vector_internal::segment_iterator<segment_vector,
                              false>;
    using const_iterator =
        segment_vector_internal::segment_iterator<segment_vector, true>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    /* Constructors */
    segment_vector();
    segment_vector(size_type count, const value_type &value);
    explicit segment_vector(size_type count);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value,
              InputIt>::type * = nullptr>
    segment_vector(InputIt first, InputIt last);
    segment_vector(const segment_vector &other);
    segment_vector(segment_vector &&other);
    segment_vector(std::initializer_list<T> init);
    segment_vector(const std::vector<T> &other);

    /* Assign operators */
    segment_vector &operator=(const segment_vector &other);
    segment_vector &operator=(segment_vector &&other);
    segment_vector &operator=(std::initializer_list<T> ilist);
    segment_vector &operator=(const std::vector<T> &other);

    /* Assign methods */
    void assign(size_type count, const_reference value);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value,
              InputIt>::type * = nullptr>
    void assign(InputIt first, InputIt last);
    void assign(std::initializer_list<T> ilist);
    void assign(const segment_vector &other);
    void assign(segment_vector &&other);
    void assign(const std::vector<T> &other);

    /* Destructor */
    ~segment_vector();

    /* Element access */
    reference at(size_type n);
    const_reference at(size_type n) const;
    const_reference const_at(size_type n) const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference front();
    const_reference front() const;
    const_reference cfront() const;
    reference back();
    const_reference back() const;
    const_reference cback() const;

    /* Iterators */
    iterator begin();
    const_iterator begin() const noexcept;
    const_iterator cbegin() const noexcept;
    iterator end();
    const_iterator end() const noexcept;
    const_iterator cend() const noexcept;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend();
    const_reverse_iterator rend() const noexcept;
    const_reverse_iterator crend() const noexcept;

    /* Range */
    slice<iterator> range(size_type start, size_type n);
    slice<const_iterator> range(size_type start, size_type n) const;
    slice<const_iterator> crange(size_type start, size_type n) const;

    /* Capacity */
    constexpr bool empty() const noexcept;
    size_type size() const noexcept;
    constexpr size_type max_size() const noexcept;
    void reserve(size_type capacity_new);
    size_type capacity() const noexcept;
    void shrink_to_fit();

    /* Modifiers */
    void clear();
    void free_data();
    iterator insert(const_iterator pos, const T &value);
    iterator insert(const_iterator pos, T &&value);
    iterator insert(const_iterator pos, size_type count, const T &value);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value,
              InputIt>::type * = nullptr>
    iterator insert(const_iterator pos, InputIt first, InputIt last);
    iterator insert(const_iterator pos, std::initializer_list<T> ilist);
    template <class... Args>
    iterator emplace(const_iterator pos, Args &&... args);
    template <class... Args>
    reference emplace_back(Args &&... args);
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    void push_back(const T &value);
    void push_back(T &&value);
    void pop_back();
    void resize(size_type count);
    void resize(size_type count, const value_type &value);
    void swap(segment_vector &other);

private:
    /* Helper functions */
    void internal_reserve(size_type new_capacity);
    template <typename... Args>
    void construct(size_type idx, size_type count, Args &&... args);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value,
              InputIt>::type * = nullptr>
    void construct_range(size_type idx, InputIt first, InputIt last);
    void insert_gap(size_type idx, size_type count);
    void shrink(size_type size_new);
    pool_base get_pool() const noexcept;
    void snapshot_data(size_type idx_first, size_type idx_last);

    /* Data structure specific helper functions */
    reference get(size_type n);
    const_reference get(size_type n) const;
    const_reference cget(size_type n) const;
    bool segment_capacity_validation() const;

    /* Number of segments that currently enabled */
    p<size_type> _segments_used = 0;
    /* Segments storage */
    segment_vector_type _data;
};

/* Non-member swap */
template <typename T, typename Segment, typename Policy>
void swap(segment_vector<T, Segment, Policy> &lhs,
      segment_vector<T, Segment, Policy> &rhs);

/*
 * Comparison operators between
 * pmem::obj::experimental::segment_vector<T, Segment, Policy> and
 * pmem::obj::experimental::segment_vector<T, Segment, Policy>
 */
template <typename T, typename Segment, typename Policy>
bool operator==(const segment_vector<T, Segment, Policy> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator!=(const segment_vector<T, Segment, Policy> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator<(const segment_vector<T, Segment, Policy> &lhs,
           const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator<=(const segment_vector<T, Segment, Policy> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator>(const segment_vector<T, Segment, Policy> &lhs,
           const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator>=(const segment_vector<T, Segment, Policy> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);

/*
 * Comparison operators between
 * pmem::obj::experimental::segment_vector<T, Segment, Policy> and
 * std::vector<T>
 */
template <typename T, typename Segment, typename Policy>
bool operator==(const segment_vector<T, Segment, Policy> &lhs,
        const std::vector<T> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator!=(const segment_vector<T, Segment, Policy> &lhs,
        const std::vector<T> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator<(const segment_vector<T, Segment, Policy> &lhs,
           const std::vector<T> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator<=(const segment_vector<T, Segment, Policy> &lhs,
        const std::vector<T> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator>(const segment_vector<T, Segment, Policy> &lhs,
           const std::vector<T> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator>=(const segment_vector<T, Segment, Policy> &lhs,
        const std::vector<T> &rhs);

/*
 * Comparison operators between std::vector<T> and
 * pmem::obj::experimental::segment_vector<T, Segment, Policy>
 */
template <typename T, typename Segment, typename Policy>
bool operator==(const std::vector<T> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator!=(const std::vector<T> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator<(const std::vector<T> &lhs,
           const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator<=(const std::vector<T> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator>(const std::vector<T> &lhs,
           const segment_vector<T, Segment, Policy> &rhs);
template <typename T, typename Segment, typename Policy>
bool operator>=(const std::vector<T> &lhs,
        const segment_vector<T, Segment, Policy> &rhs);

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector()
{
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector(size_type count,
                           const value_type &value)
{
    internal_reserve(count);
    construct(0, count, value);
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector(size_type count)
{
    internal_reserve(count);
    construct(0, count);
}

template <typename T, typename Segment, typename Policy>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
segment_vector<T, Segment, Policy>::segment_vector(InputIt first, InputIt last)
{
    internal_reserve(static_cast<size_type>(std::distance(first, last)));
    construct_range(0, first, last);
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector(const segment_vector &other)
{
    internal_reserve(other.capacity());
    construct_range(0, other.cbegin(), other.cend());
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector(segment_vector &&other)
{
    _data = std::move(other._data);
    _segments_used = other._segments_used;
    other._segments_used = 0;
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector(
    std::initializer_list<T> init)
    : segment_vector(init.begin(), init.end())
{
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::segment_vector(const std::vector<T> &other)
    : segment_vector(other.cbegin(), other.cend())
{
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy> &
segment_vector<T, Segment, Policy>::operator=(const segment_vector &other)
{
    assign(other);
    return *this;
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy> &
segment_vector<T, Segment, Policy>::operator=(segment_vector &&other)
{
    assign(std::move(other));
    return *this;
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy> &
segment_vector<T, Segment, Policy>::operator=(std::initializer_list<T> ilist)
{
    assign(ilist.begin(), ilist.end());
    return *this;
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy> &
segment_vector<T, Segment, Policy>::operator=(const std::vector<T> &other)
{
    assign(other);
    return *this;
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::assign(size_type count,
                       const_reference value)
{
    if (count > max_size())
        throw std::length_error("Assignable range exceeds max size.");

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        if (count > capacity())
            internal_reserve(count);
        else if (count < size())
            shrink(count);

        size_type end = policy::get_segment(count - 1);
        for (size_type i = 0; i < end; ++i)
            _data[i].assign(policy::segment_size(i), value);
        _data[end].assign(count - policy::segment_top(end), value);

        _segments_used = end + 1;
    });
    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
void
segment_vector<T, Segment, Policy>::assign(InputIt first, InputIt last)
{
    size_type count = static_cast<size_type>(std::distance(first, last));
    if (count > max_size())
        throw std::length_error("Assignable range exceeds max size.");

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        if (count > capacity())
            internal_reserve(count);
        else if (count < size())
            shrink(count);

        difference_type num;
        size_type end = policy::get_segment(count - 1);
        for (size_type i = 0; i < end; ++i) {
            size_type size = policy::segment_size(i);
            num = static_cast<difference_type>(size);
            _data[i].assign(first, std::next(first, num));
            std::advance(first, num);
        }
        num = static_cast<difference_type>(std::distance(first, last));
        _data[end].assign(first, std::next(first, num));

        _segments_used = end + 1;
    });
    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::assign(std::initializer_list<T> ilist)
{
    assign(ilist.begin(), ilist.end());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::assign(const segment_vector &other)
{
    if (this != &other)
        assign(other.cbegin(), other.cend());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::assign(segment_vector &&other)
{
    if (this == &other)
        return;

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        _data = std::move(other._data);
        _segments_used = other._segments_used;
        other._segments_used = 0;
    });
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::assign(const std::vector<T> &other)
{
    assign(other.cbegin(), other.cend());
}

template <typename T, typename Segment, typename Policy>
segment_vector<T, Segment, Policy>::~segment_vector()
{
    free_data();
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reference
segment_vector<T, Segment, Policy>::at(size_type n)
{
    if (n >= size())
        throw std::out_of_range("segment_vector::at");

    detail::conditional_add_to_tx(&get(n), 1, POBJ_XADD_ASSUME_INITIALIZED);

    return get(n);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::at(size_type n) const
{
    if (n >= size())
        throw std::out_of_range("segment_vector::at");
    return get(n);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::const_at(size_type n) const
{
    if (n >= size())
        throw std::out_of_range("segment_vector::const_at");
    return get(n);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reference
    segment_vector<T, Segment, Policy>::operator[](size_type n)
{
    reference element = get(n);

    detail::conditional_add_to_tx(&element, 1,
                      POBJ_XADD_ASSUME_INITIALIZED);

    return element;
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
    segment_vector<T, Segment, Policy>::operator[](size_type n) const
{
    return get(n);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reference
segment_vector<T, Segment, Policy>::front()
{
    detail::conditional_add_to_tx(&_data[0][0], 1,
                      POBJ_XADD_ASSUME_INITIALIZED);

    return _data[0][0];
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::front() const
{
    return _data[0][0];
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::cfront() const
{
    return _data[0][0];
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reference
segment_vector<T, Segment, Policy>::back()
{
    reference element = get(size() - 1);

    detail::conditional_add_to_tx(&element, 1,
                      POBJ_XADD_ASSUME_INITIALIZED);

    return element;
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::back() const
{
    return get(size() - 1);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::cback() const
{
    return get(size() - 1);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::begin()
{
    return iterator(this, 0);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_iterator
segment_vector<T, Segment, Policy>::begin() const noexcept
{
    return const_iterator(this, 0);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_iterator
segment_vector<T, Segment, Policy>::cbegin() const noexcept
{
    return const_iterator(this, 0);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::end()
{
    return iterator(this, size());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_iterator
segment_vector<T, Segment, Policy>::end() const noexcept
{
    return const_iterator(this, size());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_iterator
segment_vector<T, Segment, Policy>::cend() const noexcept
{
    return const_iterator(this, size());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reverse_iterator
segment_vector<T, Segment, Policy>::rbegin()
{
    return reverse_iterator(end());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reverse_iterator
segment_vector<T, Segment, Policy>::rbegin() const noexcept
{
    return const_reverse_iterator(end());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reverse_iterator
segment_vector<T, Segment, Policy>::crbegin() const noexcept
{
    return rbegin();
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reverse_iterator
segment_vector<T, Segment, Policy>::rend()
{
    return reverse_iterator(begin());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reverse_iterator
segment_vector<T, Segment, Policy>::rend() const noexcept
{
    return const_reverse_iterator(begin());
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reverse_iterator
segment_vector<T, Segment, Policy>::crend() const noexcept
{
    return rend();
}

template <typename T, typename Segment, typename Policy>
slice<typename segment_vector<T, Segment, Policy>::iterator>
segment_vector<T, Segment, Policy>::range(size_type start, size_type n)
{
    if (start + n > size())
        throw std::out_of_range("segment_vector::range");

    snapshot_data(start, start + n);

    return {iterator(this, start), iterator(this, start + n)};
}

template <typename T, typename Segment, typename Policy>
slice<typename segment_vector<T, Segment, Policy>::const_iterator>
segment_vector<T, Segment, Policy>::range(size_type start, size_type n) const
{
    if (start + n > size())
        throw std::out_of_range("segment_vector::range");

    return {const_iterator(this, start), const_iterator(this, start + n)};
}

template <typename T, typename Segment, typename Policy>
slice<typename segment_vector<T, Segment, Policy>::const_iterator>
segment_vector<T, Segment, Policy>::crange(size_type start, size_type n) const
{
    if (start + n > size())
        throw std::out_of_range("segment_vector::range");

    return {const_iterator(this, start), const_iterator(this, start + n)};
}

template <typename T, typename Segment, typename Policy>
constexpr bool
segment_vector<T, Segment, Policy>::empty() const noexcept
{
    return size() == 0;
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::size_type
segment_vector<T, Segment, Policy>::size() const noexcept
{
    size_type result = 0;
    for (size_type i = 0; i < _segments_used; ++i)
        result += _data.const_at(i).size();
    return result;
}

template <typename T, typename Segment, typename Policy>
constexpr typename segment_vector<T, Segment, Policy>::size_type
segment_vector<T, Segment, Policy>::max_size() const noexcept
{
    return policy::max_size(_data);
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::reserve(size_type capacity_new)
{
    if (capacity_new <= capacity())
        return;

    pool_base pb = get_pool();
    transaction::run(pb, [&] { internal_reserve(capacity_new); });
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::size_type
segment_vector<T, Segment, Policy>::capacity() const noexcept
{
    if (_segments_used == 0)
        return 0;
    return policy::capacity(_segments_used - 1);
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::shrink_to_fit()
{
    size_type new_last = policy::get_segment(size() - 1);
    if (_segments_used - 1 == new_last)
        return;

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        for (size_type i = new_last + 1; i < _segments_used; ++i)
            _data[i].free_data();
        _segments_used = new_last + 1;
        storage::resize(_data, _segments_used);
    });
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::clear()
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] { shrink(0); });
    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::free_data()
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        for (size_type i = 0; i < _segments_used; ++i)
            _data[i].free_data();
        _segments_used = 0;
    });
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::insert(const_iterator pos, const T &value)
{
    return insert(pos, 1, value);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::insert(const_iterator pos, T &&value)
{
    size_type idx = static_cast<size_type>(pos - cbegin());

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        insert_gap(idx, 1);
        get(idx) = std::move(value);
    });

    return iterator(this, idx);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::insert(const_iterator pos, size_type count,
                       const T &value)
{
    size_type idx = static_cast<size_type>(pos - cbegin());

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        insert_gap(idx, count);
        for (size_type i = idx; i < idx + count; ++i)
            get(i) = std::move(value);
    });

    return iterator(this, idx);
}

template <typename T, typename Segment, typename Policy>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::insert(const_iterator pos, InputIt first,
                       InputIt last)
{
    size_type idx = static_cast<size_type>(pos - cbegin());
    size_type gap_size = static_cast<size_type>(std::distance(first, last));

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        insert_gap(idx, gap_size);
        for (size_type i = idx; i < idx + gap_size; ++i, ++first)
            get(i) = *first;
    });

    return iterator(this, idx);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::insert(const_iterator pos,
                       std::initializer_list<T> ilist)
{
    return insert(pos, ilist.begin(), ilist.end());
}

template <typename T, typename Segment, typename Policy>
template <class... Args>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::emplace(const_iterator pos, Args &&... args)
{
    size_type idx = static_cast<size_type>(pos - cbegin());

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        detail::temp_value<value_type,
                   noexcept(T(std::forward<Args>(args)...))>
        tmp(std::forward<Args>(args)...);
        insert_gap(idx, 1);
        get(idx) = std::move(tmp.get());
    });

    return iterator(this, idx);
}

template <typename T, typename Segment, typename Policy>
template <class... Args>
typename segment_vector<T, Segment, Policy>::reference
segment_vector<T, Segment, Policy>::emplace_back(Args &&... args)
{
    assert(size() < max_size());

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        if (size() == capacity())
            internal_reserve(capacity() + 1);

        size_type segment = policy::get_segment(size());
        _data[segment].emplace_back(std::forward<Args>(args)...);
    });

    return back();
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::erase(const_iterator pos)
{
    return erase(pos, pos + 1);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::iterator
segment_vector<T, Segment, Policy>::erase(const_iterator first,
                      const_iterator last)
{
    size_type count = static_cast<size_type>(std::distance(first, last));
    size_type idx = static_cast<size_type>(first - cbegin());

    if (count == 0)
        return iterator(this, idx);

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        size_type _size = size();

        snapshot_data(idx, _size);

        /* Moving after-range elements to the place of deleted
         */
        iterator dest = iterator(this, idx);
        iterator begin = iterator(this, idx + count);
        iterator end = iterator(this, _size);
        std::move(begin, end, dest);

        /* Clearing the range where the elements were moved from
         */
        size_type middle = policy::get_segment(_size - count);
        size_type last = policy::get_segment(_size - 1);
        size_type middle_size = policy::index_in_segment(_size - count);
        for (size_type s = last; s > middle; --s)
            _data[s].clear();
        _data[middle].resize(middle_size);

        _segments_used = middle + 1;
    });

    assert(segment_capacity_validation());

    return iterator(this, idx);
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::push_back(const T &value)
{
    emplace_back(value);
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::push_back(T &&value)
{
    emplace_back(std::move(value));
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::pop_back()
{
    if (empty())
        return;

    pool_base pb = get_pool();
    transaction::run(pb, [&] { shrink(size() - 1); });
    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::resize(size_type count)
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        size_type _size = size();
        if (count < _size)
            shrink(count);
        else {
            if (capacity() < count)
                internal_reserve(count);
            construct(_size, count - _size);
        }
    });
    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::resize(size_type count,
                       const value_type &value)
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        size_type _size = size();
        if (count < _size)
            shrink(count);
        else {
            if (capacity() < count)
                internal_reserve(count);
            construct(_size, count - _size, value);
        }
    });
    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::swap(segment_vector &other)
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        _data.swap(other._data);
        std::swap(_segments_used, other._segments_used);
    });
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::internal_reserve(size_type new_capacity)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    if (new_capacity > max_size())
        throw std::length_error("New capacity exceeds max size.");

    if (new_capacity == 0)
        return;

    size_type old_idx = policy::get_segment(capacity());
    size_type new_idx = policy::get_segment(new_capacity - 1);
    storage::resize(_data, new_idx + 1);
    for (size_type i = old_idx; i <= new_idx; ++i) {
        size_type segment_capacity = policy::segment_size(i);
        _data[i].reserve(segment_capacity);
    }
    _segments_used = new_idx + 1;

    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
template <typename... Args>
void
segment_vector<T, Segment, Policy>::construct(size_type idx, size_type count,
                          Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(_segments_used - 1 >= policy::get_segment(size() + count - 1));

    for (size_type i = idx; i < idx + count; ++i) {
        size_type segment = policy::get_segment(i);
        _data[segment].emplace_back(std::forward<Args>(args)...);
    }
}

template <typename T, typename Segment, typename Policy>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
void
segment_vector<T, Segment, Policy>::construct_range(size_type idx,
                            InputIt first, InputIt last)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    size_type count = static_cast<size_type>(std::distance(first, last));
    assert(count >= 0);
    assert(_segments_used - 1 >= policy::get_segment(size() + count - 1));

    for (size_type i = idx; i < idx + count; ++i, ++first) {
        size_type segment = policy::get_segment(i);
        _data[segment].emplace_back(*first);
    }
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::insert_gap(size_type idx, size_type count)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    size_type _size = size();

    if (capacity() < _size + count)
        internal_reserve(_size + count);

    iterator dest = iterator(this, _size + count);
    iterator begin = iterator(this, idx);
    iterator end = iterator(this, _size);

    snapshot_data(idx, _size);

    resize(_size + count);
    std::move_backward(begin, end, dest);

    assert(segment_capacity_validation());
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::shrink(size_type size_new)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(size_new <= size());

    snapshot_data(size_new, size());

    size_type begin = policy::get_segment(size() - 1);
    size_type end = policy::get_segment(size_new);
    for (; begin > end; --begin) {
        _data[begin].clear();
    }
    size_type residue = policy::index_in_segment(size_new);
    _data[end].erase(_data[end].cbegin() + residue, _data[end].cend());
}

template <typename T, typename Segment, typename Policy>
pool_base
segment_vector<T, Segment, Policy>::get_pool() const noexcept
{
    auto pop = pmemobj_pool_by_ptr(this);
    assert(pop != nullptr);
    return pool_base(pop);
}

template <typename T, typename Segment, typename Policy>
void
segment_vector<T, Segment, Policy>::snapshot_data(size_type first,
                          size_type last)
{
    if (first == last)
        return;

    size_type segment = policy::get_segment(first);
    size_type end = policy::get_segment(last - 1);
    size_type count = policy::segment_top(segment + 1) - first;

    while (segment != end) {
        detail::conditional_add_to_tx(&cget(first), count,
                          POBJ_XADD_ASSUME_INITIALIZED);
        first = policy::segment_top(++segment);
        count = policy::segment_size(segment);
    }
    detail::conditional_add_to_tx(&cget(first), last - first,
                      POBJ_XADD_ASSUME_INITIALIZED);
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::reference
segment_vector<T, Segment, Policy>::get(size_type n)
{
    size_type s_idx = policy::get_segment(n);
    size_type local_idx = policy::index_in_segment(n);

    return _data[s_idx][local_idx];
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::get(size_type n) const
{
    size_type s_idx = policy::get_segment(n);
    size_type local_idx = policy::index_in_segment(n);

    return _data[s_idx][local_idx];
}

template <typename T, typename Segment, typename Policy>
typename segment_vector<T, Segment, Policy>::const_reference
segment_vector<T, Segment, Policy>::cget(size_type n) const
{
    size_type s_idx = policy::get_segment(n);
    size_type local_idx = policy::index_in_segment(n);

    return _data[s_idx][local_idx];
}

template <typename T, typename Segment, typename Policy>
bool
segment_vector<T, Segment, Policy>::segment_capacity_validation() const
{
    for (size_type i = 0; i < _segments_used; ++i)
        if (_data.const_at(i).capacity() != policy::segment_size(i))
            return false;
    return true;
}

template <typename T, typename Segment, typename Policy>
void
swap(segment_vector<T, Segment, Policy> &lhs,
     segment_vector<T, Segment, Policy> &rhs)
{
    lhs.swap(rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator==(const segment_vector<T, Segment, Policy> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return lhs.size() == rhs.size() &&
        std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template <typename T, typename Segment, typename Policy>
bool
operator!=(const segment_vector<T, Segment, Policy> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return !(lhs == rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator<(const segment_vector<T, Segment, Policy> &lhs,
      const segment_vector<T, Segment, Policy> &rhs)
{
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
                        rhs.end());
}

template <typename T, typename Segment, typename Policy>
bool
operator<=(const segment_vector<T, Segment, Policy> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return !(rhs < lhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator>(const segment_vector<T, Segment, Policy> &lhs,
      const segment_vector<T, Segment, Policy> &rhs)
{
    return rhs < lhs;
}

template <typename T, typename Segment, typename Policy>
bool
operator>=(const segment_vector<T, Segment, Policy> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return !(lhs < rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator==(const segment_vector<T, Segment, Policy> &lhs,
       const std::vector<T> &rhs)
{
    return lhs.size() == rhs.size() &&
        std::equal(lhs.begin(), lhs.end(), rhs.begin());
}

template <typename T, typename Segment, typename Policy>
bool
operator!=(const segment_vector<T, Segment, Policy> &lhs,
       const std::vector<T> &rhs)
{
    return !(lhs == rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator<(const segment_vector<T, Segment, Policy> &lhs,
      const std::vector<T> &rhs)
{
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(),
                        rhs.end());
}

template <typename T, typename Segment, typename Policy>
bool
operator<=(const segment_vector<T, Segment, Policy> &lhs,
       const std::vector<T> &rhs)
{
    return !(std::lexicographical_compare(rhs.begin(), rhs.end(),
                          lhs.begin(), lhs.end()));
}

template <typename T, typename Segment, typename Policy>
bool
operator>(const segment_vector<T, Segment, Policy> &lhs,
      const std::vector<T> &rhs)
{
    return !(lhs <= rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator>=(const segment_vector<T, Segment, Policy> &lhs,
       const std::vector<T> &rhs)
{
    return !(lhs < rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator==(const std::vector<T> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return rhs == lhs;
}

template <typename T, typename Segment, typename Policy>
bool
operator!=(const std::vector<T> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return !(lhs == rhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator<(const std::vector<T> &lhs,
      const segment_vector<T, Segment, Policy> &rhs)
{
    return rhs > lhs;
}

template <typename T, typename Segment, typename Policy>
bool
operator<=(const std::vector<T> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return !(rhs < lhs);
}

template <typename T, typename Segment, typename Policy>
bool
operator>(const std::vector<T> &lhs,
      const segment_vector<T, Segment, Policy> &rhs)
{
    return rhs < lhs;
}

template <typename T, typename Segment, typename Policy>
bool
operator>=(const std::vector<T> &lhs,
       const segment_vector<T, Segment, Policy> &rhs)
{
    return !(lhs < rhs);
}

} /* namespace experimental */
} /* namespace obj */
} /* namespace pmem */

#endif /* LIBPMEMOBJ_SEGMENT_VECTOR_HPP */