vector.hpp

Go to the documentation of this file.

/*
 * Copyright 2018-2021, 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++/container/detail/contiguous_iterator.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++/make_persistent.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/slice.hpp>
#include <libpmemobj++/transaction.hpp>
#include <libpmemobj/base.h>
 
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
 
namespace pmem
{
 
namespace obj
{
 
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 = pmem::detail::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>;
    using range_snapshotting_iterator =
        pmem::detail::range_snapshotting_iterator<T>;
    /* func argument type definition for 'for_each_ptr' method */
    using for_each_ptr_function =
        std::function<void(persistent_ptr_base &)>;
 
    /* 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> 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;
    void for_each_ptr(for_each_ptr_function func);
 
    /* 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 iterator */
    template <typename P>
    struct single_element_iterator {
        using iterator_category = std::input_iterator_tag;
        using value_type = P;
        using difference_type = std::ptrdiff_t;
        using pointer = const P *;
        using reference = const P &;
 
        const P *ptr;
        std::size_t count;
 
        single_element_iterator(const P *ptr, std::size_t count = 0)
            : ptr(ptr), count(count)
        {
        }
 
        reference operator*()
        {
            return *ptr;
        }
 
        pointer operator->()
        {
            return ptr;
        }
 
        single_element_iterator &
        operator++()
        {
            count++;
            return *this;
        }
 
        single_element_iterator
        operator++(int)
        {
            single_element_iterator tmp =
                single_element_iterator(ptr, count);
            count++;
            return tmp;
        }
 
        difference_type
        operator-(const single_element_iterator &rhs)
        {
            return count - rhs.count;
        }
 
        bool
        operator!=(const single_element_iterator &rhs)
        {
            return ptr != rhs.ptr || count != rhs.count;
        }
    };
 
    /* helper functions */
    void alloc(size_type size);
    void check_pmem();
    void check_tx_stage_work();
    template <typename... Args>
    void construct_at_end(size_type count, Args &&... args);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value,
              InputIt>::type * = nullptr>
    void construct_at_end(InputIt first, InputIt last);
    void dealloc();
    pool_base get_pool() const noexcept;
    template <typename InputIt>
    void internal_insert(size_type idx, InputIt first, InputIt last);
    void realloc(size_type size);
    size_type get_recommended_capacity(size_type at_least) const;
    void shrink(size_type size_new);
    void add_data_to_tx(size_type idx_first, size_type num);
    template <typename InputIt>
    void construct_or_assign(size_type idx, InputIt first, InputIt last);
    void move_elements_backward(pointer first, pointer last,
                    pointer d_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::vector<T> and
 * pmem::obj::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::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::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_at_end(count, value);
}
 
template <typename T>
vector<T>::vector(size_type count)
{
    check_pmem();
    check_tx_stage_work();
 
    _data = nullptr;
    _size = 0;
    alloc(count);
    construct_at_end(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_at_end(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_at_end(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;
            add_data_to_tx(0, size_old);
 
            std::fill_n(
                _data.get(),
                (std::min)(count,
                       static_cast<size_type>(size_old)),
                value);
 
            if (count > size_old) {
                add_data_to_tx(size_old, count - size_old);
                construct_at_end(count - size_old, value);
            } else {
                shrink(count);
            }
        } else {
            dealloc();
            alloc(count);
            construct_at_end(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;
            add_data_to_tx(0, size_old);
 
            InputIt mid = last;
            bool growing = size_new > size_old;
 
            if (growing) {
                add_data_to_tx(size_old, size_new - size_old);
 
                mid = first;
                std::advance(mid, size_old);
            }
 
            iterator shrink_to = std::copy(first, mid, &_data[0]);
 
            if (growing) {
                construct_at_end(mid, last);
            } else {
                shrink(static_cast<size_type>(std::distance(
                    iterator(&_data[0]), shrink_to)));
            }
        } else {
            dealloc();
            alloc(size_new);
            construct_at_end(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)],
                      1, POBJ_XADD_ASSUME_INITIALIZED);
 
    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)],
                      1, POBJ_XADD_ASSUME_INITIALIZED);
 
    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], 1,
                      POBJ_XADD_ASSUME_INITIALIZED);
 
    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)], 1,
        POBJ_XADD_ASSUME_INITIALIZED);
 
    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()
{
    add_data_to_tx(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,
                      POBJ_XADD_ASSUME_INITIALIZED);
 
    return {_data.get() + start, _data.get() + start + n};
}
 
template <typename T>
slice<typename vector<T>::range_snapshotting_iterator>
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(_data.get() + start,
                        _data.get() + start, n,
                        snapshot_size),
        range_snapshotting_iterator(_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, [&] {
        internal_insert(idx, std::make_move_iterator(&value),
                std::make_move_iterator(&value + 1));
    });
 
    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, [&] {
        internal_insert(
            idx, single_element_iterator<value_type>(&value, 0),
            single_element_iterator<value_type>(&value, count));
    });
 
    return iterator(_data.get() + 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));
 
    transaction::run(pb, [&] { internal_insert(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 internal_insert() 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)...);
 
        auto &tmp_ref = tmp.get();
 
        internal_insert(idx, std::make_move_iterator(&tmp_ref),
                std::make_move_iterator(&tmp_ref + 1));
    });
 
    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 {
            add_data_to_tx(size(), 1);
        }
 
        construct_at_end(1, std::forward<Args>(args)...);
    });
 
    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.get()), 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
         */
        add_data_to_tx(idx, _size - idx);
 
        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_at_end(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_at_end(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>::for_each_ptr(for_each_ptr_function func)
{
    func(_data);
}
 
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) {
        if (errno == ENOMEM)
            throw pmem::transaction_out_of_memory(
                "Failed to allocate persistent memory object")
                .with_pmemobj_errormsg();
        else
            throw pmem::transaction_alloc_error(
                "Failed to allocate persistent memory object")
                .with_pmemobj_errormsg();
    }
 
    _data = res;
}
 
template <typename T>
void
vector<T>::check_pmem()
{
    if (nullptr == pmemobj_pool_by_ptr(this))
        throw pmem::pool_error("Invalid pool handle.");
}
 
template <typename T>
void
vector<T>::check_tx_stage_work()
{
    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw pmem::transaction_scope_error(
            "Function called out of transaction scope.");
}
 
template <typename T>
template <typename... Args>
void
vector<T>::construct_at_end(size_type count, Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(_capacity >= count + _size);
 
    pointer dest = _data.get() + size();
    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_at_end(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() + size();
    _size += static_cast<size_type>(range_size);
    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 pmem::transaction_free_error(
                "failed to delete persistent memory object")
                .with_pmemobj_errormsg();
        _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>::move_elements_backward(pointer first, pointer last, pointer d_last)
{
    while (first != last && d_last >= cend())
        detail::create<value_type>(--d_last, std::move(*(--last)));
 
    if (first != last)
        std::move_backward(first, last, d_last);
}
 
template <typename T>
template <typename InputIt>
void
vector<T>::construct_or_assign(size_type idx, InputIt first, InputIt last)
{
    auto count = static_cast<size_type>(std::distance(first, last));
    auto dest = _data.get() + idx;
    auto initialized_slots = static_cast<size_type>(cend() - dest);
 
    /* Assign new elements to initialized memory */
    if (dest < cend())
        dest = std::copy_n(first, (std::min)(initialized_slots, count),
                   dest);
 
    std::advance(first, (std::min)(initialized_slots, count));
 
    /* Rest of the elements will be created in uninitialized memory */
    while (first != last)
        detail::create<value_type>(dest++, *first++);
 
    _size += count;
}
 
template <typename T>
template <typename InputIt>
void
vector<T>::internal_insert(size_type idx, InputIt first, InputIt last)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    auto count = static_cast<size_type>(std::distance(first, last));
 
    if (_capacity >= size() + count) {
        pointer dest = _data.get() +
            static_cast<difference_type>(size() + count);
        pointer begin = _data.get() + static_cast<difference_type>(idx);
        pointer end =
            _data.get() + static_cast<difference_type>(size());
 
        add_data_to_tx(idx, size() - idx + count);
 
        /* Make a gap for new elements */
        move_elements_backward(begin, end, dest);
 
        /* Construct new elements in the gap */
        construct_or_assign(idx, first, last);
    } else {
        /*
         * XXX: future optimization: we don't have to snapshot data
         * which we will copy (only snapshot for move)
         */
        add_data_to_tx(0, _size);
 
        auto old_data = _data;
        auto old_size = _size;
        pointer old_begin = _data.get();
        pointer old_mid =
            _data.get() + static_cast<difference_type>(idx);
        pointer old_end =
            _data.get() + static_cast<difference_type>(size());
 
        _data = nullptr;
        _size = _capacity = 0;
 
        alloc(get_recommended_capacity(old_size + count));
 
        /* Move range before the idx to new array */
        construct_at_end(std::make_move_iterator(old_begin),
                 std::make_move_iterator(old_mid));
 
        /* Insert (first, last) range to the new array */
        construct_at_end(first, last);
 
        /* Move remaining element to the new array */
        construct_at_end(std::make_move_iterator(old_mid),
                 std::make_move_iterator(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 pmem::transaction_free_error(
                "failed to delete persistent memory object")
                .with_pmemobj_errormsg();
    }
}
 
template <typename T>
void
vector<T>::realloc(size_type capacity_new)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
 
    /*
     * If _data == nullptr this object has never allocated any memory
     * so we need to behave as alloc instead.
     */
    if (_data == nullptr)
        return alloc(capacity_new);
 
    /*
     * XXX: future optimization: we don't have to snapshot data
     * which we will not overwrite
     */
    add_data_to_tx(0, _size);
 
    auto old_data = _data;
    auto old_size = _size;
    pointer old_begin = _data.get();
    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_at_end(std::make_move_iterator(old_begin),
             std::make_move_iterator(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 pmem::transaction_free_error(
            "failed to delete persistent memory object")
            .with_pmemobj_errormsg();
}
 
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);
 
    add_data_to_tx(size_new, _size - size_new);
 
    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>::add_data_to_tx(size_type idx_first, size_type num)
{
    assert(idx_first + num <= capacity());
 
#if LIBPMEMOBJ_CPP_VG_MEMCHECK_ENABLED
    /* Make sure that only data allocated by this vector is accessed */
    assert(VALGRIND_CHECK_MEM_IS_ADDRESSABLE(_data.get() + idx_first,
                         num * sizeof(T)) == 0);
#endif
 
    auto initialized_num = size() - idx_first;
 
    /* Snapshot elements in range [idx_first,size()) */
    detail::conditional_add_to_tx(_data.get() + idx_first,
                      (std::min)(initialized_num, num),
                      POBJ_XADD_ASSUME_INITIALIZED);
 
    if (num > initialized_num) {
        /* Elements after size() do not have to be snapshotted */
        detail::conditional_add_to_tx(_data.get() + size(),
                          num - initialized_num,
                          POBJ_XADD_NO_SNAPSHOT);
    }
}
 
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 obj */
 
} /* namespace pmem */
 
#endif /* LIBPMEMOBJ_CPP_VECTOR_HPP */