vector.hpp

Go to the documentation of this file.

/*
 * Copyright 2018-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_CPP_VECTOR_HPP
#define LIBPMEMOBJ_CPP_VECTOR_HPP

#include <libpmemobj++/detail/common.hpp>
#include <libpmemobj++/detail/iterator_traits.hpp>
#include <libpmemobj++/detail/life.hpp>
#include <libpmemobj++/detail/temp_value.hpp>
#include <libpmemobj++/experimental/contiguous_iterator.hpp>
#include <libpmemobj++/experimental/slice.hpp>
#include <libpmemobj++/make_persistent.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/transaction.hpp>
#include <libpmemobj.h>

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace pmem
{

namespace obj
{

namespace experimental
{

template <typename T>
class vector {
public:
    /* Member types */
    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 = basic_contiguous_iterator<T>;
    using const_iterator = const_pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

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

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

    /* Assign methods */
    void assign(size_type count, const T &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 vector &other);
    void assign(vector &&other);
    void assign(const std::vector<T> &other);

    /* Destructor */
    ~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;
    value_type *data();
    const value_type *data() const noexcept;
    const value_type *cdata() const noexcept;

    /* 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<pointer> range(size_type start, size_type n);
    slice<range_snapshotting_iterator<T>>
    range(size_type start, size_type n, size_type snapshot_size);
    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(vector &other);

private:
    /* helper functions */
    void alloc(size_type size);
    void check_pmem();
    void check_tx_stage_work();
    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);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value,
              InputIt>::type * = nullptr>
    void construct_range_copy(size_type idx, InputIt first, InputIt last);
    void dealloc();
    pool_base get_pool() const noexcept;
    void insert_gap(size_type idx, size_type count);
    void realloc(size_type size);
    size_type get_recommended_capacity(size_type at_least) const;
    void shrink(size_type size_new);
    void snapshot_data(size_type idx_first, size_type idx_last);

    p<size_type> _size;
    p<size_type> _capacity;

    /* Underlying array */
    persistent_ptr<T[]> _data;
};

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

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

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

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

template <typename T>
vector<T>::vector()
{
    check_pmem();
    check_tx_stage_work();

    _data = nullptr;
    _size = 0;
    _capacity = 0;
}

template <typename T>
vector<T>::vector(size_type count, const value_type &value)
{
    check_pmem();
    check_tx_stage_work();

    _data = nullptr;
    _size = 0;
    alloc(count);
    construct(0, count, value);
}

template <typename T>
vector<T>::vector(size_type count)
{
    check_pmem();
    check_tx_stage_work();

    _data = nullptr;
    _size = 0;
    alloc(count);
    construct(0, count);
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
vector<T>::vector(InputIt first, InputIt last)
{
    check_pmem();
    check_tx_stage_work();

    _data = nullptr;
    _size = 0;
    alloc(static_cast<size_type>(std::distance(first, last)));
    construct_range_copy(0, first, last);
}

template <typename T>
vector<T>::vector(const vector &other)
{
    check_pmem();
    check_tx_stage_work();

    _data = nullptr;
    _size = 0;
    alloc(other.capacity());
    construct_range_copy(0, other.cbegin(), other.cend());
}

template <typename T>
vector<T>::vector(vector &&other)
{
    check_pmem();
    check_tx_stage_work();

    _data = other._data;
    _capacity = other.capacity();
    _size = other.size();
    other._data = nullptr;
    other._capacity = other._size = 0;
}

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

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

template <typename T>
vector<T> &
vector<T>::operator=(const vector &other)
{
    assign(other);

    return *this;
}

template <typename T>
vector<T> &
vector<T>::operator=(vector &&other)
{
    assign(std::move(other));

    return *this;
}

template <typename T>
vector<T> &
vector<T>::operator=(std::initializer_list<T> ilist)
{
    assign(ilist.begin(), ilist.end());

    return *this;
}

template <typename T>
vector<T> &
vector<T>::operator=(const std::vector<T> &other)
{
    assign(other);

    return *this;
}

template <typename T>
void
vector<T>::assign(size_type count, const_reference value)
{
    pool_base pb = get_pool();

    transaction::run(pb, [&] {
        if (count <= capacity()) {
            /*
             * Reallocation is not needed. First, replace old
             * elements with new ones in range [0, size()).
             * Depending on count, either call remaining old
             * elements destructors, or append more new elements.
             */
            size_type size_old = _size;
            snapshot_data(0, size_old);

            std::fill_n(
                &_data[0],
                (std::min)(count,
                       static_cast<size_type>(size_old)),
                value);

            if (count > size_old) {
#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
                /*
                 * Range of memory:
                 * [&_data[size_old], &_data[count])
                 * is undefined, there is no need to snapshot
                 * and eventually rollback old data.
                 */
                VALGRIND_PMC_ADD_TO_TX(
                    &_data[static_cast<difference_type>(
                        size_old)],
                    sizeof(T) * (count - size_old));
#endif

                construct(size_old, count - size_old, value);
                /*
                 * XXX: explicit persist is required here
                 * because given range wasn't snapshotted and
                 * won't be persisted automatically on tx
                 * commit. This can be changed once we will have
                 * implemented "uninitialized" flag for
                 * pmemobj_tx_xadd in libpmemobj.
                 */
                pb.persist(&_data[static_cast<difference_type>(
                           size_old)],
                       sizeof(T) * (count - size_old));
            } else {
                shrink(count);
            }
        } else {
            dealloc();
            alloc(count);
            construct(0, count, value);
        }
    });
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
void
vector<T>::assign(InputIt first, InputIt last)
{
    pool_base pb = get_pool();

    size_type size_new = static_cast<size_type>(std::distance(first, last));

    transaction::run(pb, [&] {
        if (size_new <= capacity()) {
            /*
             * Reallocation is not needed. First, replace old
             * elements with new ones in range [0, size()).
             * Depending on size_new, either call remaining old
             * elements destructors, or append more new elements.
             */
            size_type size_old = _size;
            snapshot_data(0, size_old);

            InputIt mid = last;
            bool growing = size_new > size_old;

            if (growing) {
#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
                /*
                 * Range of memory:
                 * [&_data[size_old], &_data[size_new])
                 * is undefined, there is no need to snapshot
                 * and eventually rollback old data.
                 */
                VALGRIND_PMC_ADD_TO_TX(
                    &_data[static_cast<difference_type>(
                        size_old)],
                    sizeof(T) * (size_new - size_old));
#endif

                mid = first;
                std::advance(mid, size_old);
            }

            iterator shrink_to = std::copy(first, mid, &_data[0]);

            if (growing) {
                construct_range_copy(size_old, mid, last);
                /*
                 * XXX: explicit persist is required here
                 * because given range wasn't snapshotted and
                 * won't be persisted automatically on tx
                 * commit. This can be changed once we will have
                 * implemented "uninitialized" flag for
                 * pmemobj_tx_xadd in libpmemobj.
                 */
                pb.persist(&_data[static_cast<difference_type>(
                           size_old)],
                       sizeof(T) * (size_new - size_old));
            } else {
                shrink(static_cast<size_type>(std::distance(
                    iterator(&_data[0]), shrink_to)));
            }
        } else {
            dealloc();
            alloc(size_new);
            construct_range_copy(0, first, last);
        }
    });
}

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

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

template <typename T>
void
vector<T>::assign(vector &&other)
{
    if (this == &other)
        return;

    pool_base pb = get_pool();

    transaction::run(pb, [&] {
        dealloc();

        _data = other._data;
        _capacity = other._capacity;
        _size = other._size;

        other._data = nullptr;
        other._capacity = other._size = 0;
    });
}

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

template <typename T>
vector<T>::~vector()
{
    free_data();
}

template <typename T>
typename vector<T>::reference
vector<T>::at(size_type n)
{
    if (n >= _size)
        throw std::out_of_range("vector::at");

    detail::conditional_add_to_tx(&_data[static_cast<difference_type>(n)]);

    return _data[static_cast<difference_type>(n)];
}

template <typename T>
typename vector<T>::const_reference
vector<T>::at(size_type n) const
{
    if (n >= _size)
        throw std::out_of_range("vector::at");

    return _data[static_cast<difference_type>(n)];
}

template <typename T>
typename vector<T>::const_reference
vector<T>::const_at(size_type n) const
{
    if (n >= _size)
        throw std::out_of_range("vector::const_at");

    return _data[static_cast<difference_type>(n)];
}

template <typename T>
typename vector<T>::reference vector<T>::operator[](size_type n)
{
    detail::conditional_add_to_tx(&_data[static_cast<difference_type>(n)]);

    return _data[static_cast<difference_type>(n)];
}

template <typename T>
typename vector<T>::const_reference vector<T>::operator[](size_type n) const
{
    return _data[static_cast<difference_type>(n)];
}

template <typename T>
typename vector<T>::reference
vector<T>::front()
{
    detail::conditional_add_to_tx(&_data[0]);

    return _data[0];
}

template <typename T>
typename vector<T>::const_reference
vector<T>::front() const
{
    return _data[0];
}

template <typename T>
typename vector<T>::const_reference
vector<T>::cfront() const
{
    return _data[0];
}

template <typename T>
typename vector<T>::reference
vector<T>::back()
{
    detail::conditional_add_to_tx(
        &_data[static_cast<difference_type>(size() - 1)]);

    return _data[static_cast<difference_type>(size() - 1)];
}

template <typename T>
typename vector<T>::const_reference
vector<T>::back() const
{
    return _data[static_cast<difference_type>(size() - 1)];
}

template <typename T>
typename vector<T>::const_reference
vector<T>::cback() const
{
    return _data[static_cast<difference_type>(size() - 1)];
}

template <typename T>
typename vector<T>::value_type *
vector<T>::data()
{
    snapshot_data(0, _size);

    return _data.get();
}

template <typename T>
const typename vector<T>::value_type *
vector<T>::data() const noexcept
{
    return _data.get();
}

template <typename T>
const typename vector<T>::value_type *
vector<T>::cdata() const noexcept
{
    return _data.get();
}

template <typename T>
typename vector<T>::iterator
vector<T>::begin()
{
    return iterator(_data.get());
}

template <typename T>
typename vector<T>::const_iterator
vector<T>::begin() const noexcept
{
    return const_iterator(_data.get());
}

template <typename T>
typename vector<T>::const_iterator
vector<T>::cbegin() const noexcept
{
    return const_iterator(_data.get());
}

template <typename T>
typename vector<T>::iterator
vector<T>::end()
{
    return iterator(_data.get() + static_cast<std::ptrdiff_t>(_size));
}

template <typename T>
typename vector<T>::const_iterator
vector<T>::end() const noexcept
{
    return const_iterator(_data.get() + static_cast<std::ptrdiff_t>(_size));
}

template <typename T>
typename vector<T>::const_iterator
vector<T>::cend() const noexcept
{
    return const_iterator(_data.get() + static_cast<std::ptrdiff_t>(_size));
}

template <typename T>
typename vector<T>::reverse_iterator
vector<T>::rbegin()
{
    return reverse_iterator(end());
}

template <typename T>
typename vector<T>::const_reverse_iterator
vector<T>::rbegin() const noexcept
{
    return const_reverse_iterator(cend());
}

template <typename T>
typename vector<T>::const_reverse_iterator
vector<T>::crbegin() const noexcept
{
    return const_reverse_iterator(cend());
}

template <typename T>
typename vector<T>::reverse_iterator
vector<T>::rend()
{
    return reverse_iterator(begin());
}

template <typename T>
typename vector<T>::const_reverse_iterator
vector<T>::rend() const noexcept
{
    return const_reverse_iterator(cbegin());
}

template <typename T>
typename vector<T>::const_reverse_iterator
vector<T>::crend() const noexcept
{
    return const_reverse_iterator(cbegin());
}

template <typename T>
slice<typename vector<T>::pointer>
vector<T>::range(size_type start, size_type n)
{
    if (start + n > size())
        throw std::out_of_range("vector::range");

    detail::conditional_add_to_tx(cdata() + start, n);

    return {_data.get() + start, _data.get() + start + n};
}

template <typename T>
slice<range_snapshotting_iterator<T>>
vector<T>::range(size_type start, size_type n, size_type snapshot_size)
{
    if (start + n > size())
        throw std::out_of_range("vector::range");

    if (snapshot_size > n)
        snapshot_size = n;

    return {range_snapshotting_iterator<T>(_data.get() + start,
                           _data.get() + start, n,
                           snapshot_size),
        range_snapshotting_iterator<T>(_data.get() + start + n,
                           _data.get() + start, n,
                           snapshot_size)};
}

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

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

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

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

template <typename T>
constexpr bool
vector<T>::empty() const noexcept
{
    return _size == 0;
}

template <typename T>
typename vector<T>::size_type
vector<T>::size() const noexcept
{
    return _size;
}

template <typename T>
constexpr typename vector<T>::size_type
vector<T>::max_size() const noexcept
{
    return PMEMOBJ_MAX_ALLOC_SIZE / sizeof(value_type);
}

template <typename T>
void
vector<T>::reserve(size_type capacity_new)
{
    if (capacity_new <= _capacity)
        return;

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

template <typename T>
typename vector<T>::size_type
vector<T>::capacity() const noexcept
{
    return _capacity;
}

template <typename T>
void
vector<T>::shrink_to_fit()
{
    size_type capacity_new = size();
    if (capacity() == capacity_new)
        return;

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

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

template <typename T>
void
vector<T>::free_data()
{
    if (_data == nullptr)
        return;

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

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

template <typename T>
typename vector<T>::iterator
vector<T>::insert(const_iterator pos, value_type &&value)
{
    pool_base pb = get_pool();

    size_type idx = static_cast<size_type>(std::distance(cbegin(), pos));

    transaction::run(pb, [&] {
        insert_gap(idx, 1);
        construct(idx, 1, std::move(value));
    });

    return iterator(&_data[static_cast<difference_type>(idx)]);
}

template <typename T>
typename vector<T>::iterator
vector<T>::insert(const_iterator pos, size_type count, const value_type &value)
{
    pool_base pb = get_pool();

    size_type idx = static_cast<size_type>(std::distance(cbegin(), pos));

    transaction::run(pb, [&] {
        insert_gap(idx, count);
        construct(idx, count, value);
    });

    return iterator(&_data[static_cast<difference_type>(idx)]);
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
typename vector<T>::iterator
vector<T>::insert(const_iterator pos, InputIt first, InputIt last)
{
    pool_base pb = get_pool();

    size_type idx = static_cast<size_type>(std::distance(cbegin(), pos));
    size_type gap_size = static_cast<size_type>(std::distance(first, last));

    transaction::run(pb, [&] {
        insert_gap(idx, gap_size);
        construct_range_copy(idx, first, last);
    });

    return iterator(&_data[static_cast<difference_type>(idx)]);
}

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

template <typename T>
template <class... Args>
typename vector<T>::iterator
vector<T>::emplace(const_iterator pos, Args &&... args)
{
    pool_base pb = get_pool();

    size_type idx = static_cast<size_type>(std::distance(cbegin(), pos));

    transaction::run(pb, [&] {
        /*
         * args might be a reference to underlying array element. This
         * reference can be invalidated after insert_gap() call. Hence,
         * we must cache value_type object in temp_value.
         */
        detail::temp_value<value_type,
                   noexcept(T(std::forward<Args>(args)...))>
        tmp(std::forward<Args>(args)...);

        insert_gap(idx, 1);
        construct(idx, 1, std::move(tmp.get()));
    });

    return iterator(&_data[static_cast<difference_type>(idx)]);
}

template <typename T>
template <class... Args>
typename vector<T>::reference
vector<T>::emplace_back(Args &&... args)
{
    /*
     * emplace() cannot be used here, because emplace_back() doesn't require
     * element_type to be MoveAssignable and emplace() uses
     * std::move_backward() function.
     */
    pool_base pb = get_pool();

    transaction::run(pb, [&] {
        if (_size == _capacity) {
            realloc(get_recommended_capacity(_size + 1));
        } else {
#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
            /*
             * Range of memory: [&_data[_size], &_data[_size + 1])
             * is undefined, there is no need to snapshot and
             * eventually rollback old data.
             */
            VALGRIND_PMC_ADD_TO_TX(
                &_data[static_cast<difference_type>(size())],
                sizeof(T));
#endif
        }

        construct(size(), 1, std::forward<Args>(args)...);
        /*
         * XXX: explicit persist is required here because given range
         * wasn't snapshotted and won't be persisted automatically on tx
         * commit. This can be changed once we will have implemented
         * "uninitialized" flag for pmemobj_tx_xadd in libpmemobj.
         */
        pb.persist(&_data[static_cast<difference_type>(size() - 1)],
               sizeof(T));
    });

    return back();
}

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

template <typename T>
typename vector<T>::iterator
vector<T>::erase(const_iterator first, const_iterator last)
{
    size_type idx = static_cast<size_type>(
        std::distance(const_iterator(&_data[0]), first));
    size_type count = static_cast<size_type>(std::distance(first, last));

    if (count == 0)
        return iterator(&_data[static_cast<difference_type>(idx)]);

    pool_base pb = get_pool();

    transaction::run(pb, [&] {
        /*
         * XXX: future optimization: no need to snapshot trivial types,
         * if idx + count = _size
         */
        snapshot_data(idx, _size);

        pointer move_begin =
            &_data[static_cast<difference_type>(idx + count)];
        pointer move_end = &_data[static_cast<difference_type>(size())];
        pointer dest = &_data[static_cast<difference_type>(idx)];

        std::move(move_begin, move_end, dest);

        _size -= count;
    });

    return iterator(&_data[static_cast<difference_type>(idx)]);
}

template <typename T>
void
vector<T>::push_back(const value_type &value)
{
    emplace_back(value);
}

template <typename T>
void
vector<T>::push_back(value_type &&value)
{
    emplace_back(std::move(value));
}

template <typename T>
void
vector<T>::pop_back()
{
    if (empty())
        return;

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

template <typename T>
void
vector<T>::resize(size_type count)
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        if (count <= _size)
            shrink(count);
        else {
            if (_capacity < count)
                realloc(count);
            construct(_size, count - _size);
        }
    });
}

template <typename T>
void
vector<T>::resize(size_type count, const value_type &value)
{
    if (_capacity == count)
        return;

    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        if (count <= _size)
            shrink(count);
        else {
            if (_capacity < count)
                realloc(count);
            construct(_size, count - _size, value);
        }
    });
}

template <typename T>
void
vector<T>::swap(vector &other)
{
    pool_base pb = get_pool();
    transaction::run(pb, [&] {
        std::swap(this->_data, other._data);
        std::swap(this->_size, other._size);
        std::swap(this->_capacity, other._capacity);
    });
}

template <typename T>
void
vector<T>::alloc(size_type capacity_new)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(_data == nullptr);
    assert(_size == 0);

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

    _capacity = capacity_new;

    if (capacity_new == 0)
        return;

    /*
     * We need to cache pmemobj_tx_alloc return value and only after that
     * assign it to _data, because when pmemobj_tx_alloc fails, it aborts
     * transaction.
     */
    persistent_ptr<T[]> res =
        pmemobj_tx_alloc(sizeof(value_type) * capacity_new,
                 detail::type_num<value_type>());

    if (res == nullptr)
        throw transaction_alloc_error(
            "Failed to allocate persistent memory object");

    _data = res;
}

template <typename T>
void
vector<T>::check_pmem()
{
    if (nullptr == pmemobj_pool_by_ptr(this))
        throw pool_error("Invalid pool handle.");
}

template <typename T>
void
vector<T>::check_tx_stage_work()
{
    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Function called out of transaction scope.");
}

template <typename T>
template <typename... Args>
void
vector<T>::construct(size_type idx, size_type count, Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(_capacity >= count + _size);

    pointer dest = _data.get() + idx;
    const_pointer end = dest + count;
    for (; dest != end; ++dest)
        detail::create<value_type, Args...>(
            dest, std::forward<Args>(args)...);
    _size += count;
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
void
vector<T>::construct_range(size_type idx, InputIt first, InputIt last)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    difference_type range_size = std::distance(first, last);
    assert(range_size >= 0);
    assert(_capacity >= static_cast<size_type>(range_size) + _size);

    pointer dest = _data.get() + idx;
    _size += static_cast<size_type>(range_size);
    while (first != last)
        detail::create<value_type>(dest++, std::move(*first++));
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<detail::is_input_iterator<InputIt>::value,
                  InputIt>::type *>
void
vector<T>::construct_range_copy(size_type idx, InputIt first, InputIt last)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    difference_type diff = std::distance(first, last);
    assert(diff >= 0);
    assert(_capacity >= static_cast<size_type>(diff) + _size);

    pointer dest = _data.get() + idx;
    _size += static_cast<size_type>(diff);
    while (first != last)
        detail::create<value_type>(dest++, *first++);
}

template <typename T>
void
vector<T>::dealloc()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    if (_data != nullptr) {
        shrink(0);
        if (pmemobj_tx_free(*_data.raw_ptr()) != 0)
            throw transaction_free_error(
                "failed to delete persistent memory object");
        _data = nullptr;
        _capacity = 0;
    }
}

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

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

    if (_capacity >= _size + count) {
        pointer dest =
            &_data[static_cast<difference_type>(size() + count)];
        pointer begin = &_data[static_cast<difference_type>(idx)];
        pointer end = &_data[static_cast<difference_type>(size())];

        /*
         * XXX: There is no necessity to snapshot uninitialized data, so
         * we can optimize it by calling:
         * transaction::snapshot<T>(begin, size() - idx).
         * However, we need libpmemobj support for that, because right
         * now pmemcheck will report an error (uninitialized part of
         * data not added to tx).
         *
         * XXX: future optimization: we don't have to snapshot data
         * which we will not overwrite
         */
#if LIBPMEMOBJ_CPP_VG_MEMCHECK_ENABLED
        VALGRIND_MAKE_MEM_DEFINED(end, sizeof(T) * count);
#endif
        snapshot_data(idx, _size + count);

        std::move_backward(begin, end, dest);
    } else {
        /*
         * XXX: future optimization: we don't have to snapshot data
         * which we will not overwrite
         */
        snapshot_data(0, _size);

        auto old_data = _data;
        auto old_size = _size;
        pointer old_begin = &_data[0];
        pointer old_mid = &_data[static_cast<difference_type>(idx)];
        pointer old_end = &_data[static_cast<difference_type>(size())];

        _data = nullptr;
        _size = _capacity = 0;

        alloc(get_recommended_capacity(old_size + count));

        construct_range(0, old_begin, old_mid);
        construct_range(idx + count, old_mid, old_end);

        /* destroy and free old data */
        for (size_type i = 0; i < old_size; ++i)
            detail::destroy<value_type>(
                old_data[static_cast<difference_type>(i)]);
        if (pmemobj_tx_free(old_data.raw()) != 0)
            throw transaction_free_error(
                "failed to delete persistent memory object");
    }
}

template <typename T>
void
vector<T>::realloc(size_type capacity_new)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    /*
     * XXX: future optimization: we don't have to snapshot data
     * which we will not overwrite
     */
    snapshot_data(0, _size);

    auto old_data = _data;
    auto old_size = _size;
    pointer old_begin = &_data[0];
    pointer old_end = capacity_new < _size
        ? &_data[static_cast<difference_type>(capacity_new)]
        : &_data[static_cast<difference_type>(size())];

    _data = nullptr;
    _size = _capacity = 0;

    alloc(capacity_new);

    construct_range(0, old_begin, old_end);

    /* destroy and free old data */
    for (size_type i = 0; i < old_size; ++i)
        detail::destroy<value_type>(
            old_data[static_cast<difference_type>(i)]);
    if (pmemobj_tx_free(old_data.raw()) != 0)
        throw transaction_free_error(
            "failed to delete persistent memory object");
}

template <typename T>
typename vector<T>::size_type
vector<T>::get_recommended_capacity(size_type at_least) const
{
    return detail::next_pow_2(at_least);
}

template <typename T>
void
vector<T>::shrink(size_type size_new)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(size_new <= _size);

    snapshot_data(size_new, _size);

    for (size_type i = size_new; i < _size; ++i)
        detail::destroy<value_type>(
            _data[static_cast<difference_type>(i)]);
    _size = size_new;
}

template <typename T>
void
vector<T>::snapshot_data(size_type idx_first, size_type idx_last)
{
    detail::conditional_add_to_tx(_data.get() + idx_first,
                      idx_last - idx_first);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

} /* namespace experimental */

} /* namespace obj */

} /* namespace pmem */

#endif /* LIBPMEMOBJ_CPP_VECTOR_HPP */