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++/experimental/contiguous_iterator.hpp>
#include <libpmemobj++/experimental/slice.hpp>
#include <libpmemobj++/make_persistent_array.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/transaction.hpp>
#include <libpmemobj.h>

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

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_contiguous_iterator<T>;
    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 &&
                  std::is_constructible<
                      value_type,
                      typename std::iterator_traits<
                          InputIt>::reference>::value,
              InputIt>::type * = nullptr>
    vector(InputIt first, InputIt last);
    vector(const vector &other);
    vector(vector &&other);
    vector(std::initializer_list<T> init);

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

    /* Assign methods */
    // void assign(size_type count, const T &value);
    // template <typename InputIt>
    // void assign(InputIt first, typename
    // std::enable_if<detail::is_input_iterator<InputIt>::value &&
    // std::is_constructible<value_type, typename
    // std::iterator_traits<InputIt>::reference>::value, InputIt>::type
    // last); void assign(std::initializer_list<T> ilist);

    /* 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;

    /* 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() noexcept;
    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>
    // iterator insert(const_iterator pos, InputIt first, typename
    // std::enable_if<detail::is_input_iterator<InputIt>::value,
    // InputIt>::type last); iterator insert(const_iterator pos,
    // std::initializer_list<T> ilist); template <class... Args> iterator
    // emplace(const_iterator pos, Args&&... args); template< class... Args
    // > void emplace_back(Args&&... args); iterator erase(iterator pos);
    // iterator erase(const_iterator pos);
    // iterator erase(iterator first, iterator last);
    // 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, T value = T());
    // 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 _dealloc();
    void _grow(size_type count, const_reference value);
    template <typename InputIt,
          typename std::enable_if<
              detail::is_input_iterator<InputIt>::value &&
                  std::is_constructible<
                      value_type,
                      typename std::iterator_traits<
                          InputIt>::reference>::value,
              InputIt>::type * = nullptr>
    void _grow(InputIt first, InputIt last);
    void _shrink(size_type size_new) noexcept;

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

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

/* Comparison operators */
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);

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

    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Default constructor called out of transaction scope.");

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

template <typename T>
vector<T>::vector(size_type count, const value_type &value)
{
    auto pop = pmemobj_pool_by_ptr(this);
    if (pop == nullptr)
        throw pool_error("Invalid pool handle.");

    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Fill constructor called out of transaction scope.");

    _data = nullptr;
    _size = 0;
    _alloc(count);
    _grow(count, value);
}

template <typename T>
vector<T>::vector(size_type count)
{
    auto pop = pmemobj_pool_by_ptr(this);
    if (pop == nullptr)
        throw pool_error("Invalid pool handle.");

    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Fill constructor called out of transaction scope.");

    _data = nullptr;
    _size = 0;
    _alloc(count);
    // XXX: after "capacity" methods will be merged, _grow() overload
    // without parameters will be available. After that, following lines
    // should be replaced with _grow()
    pointer dest = _data.get();
    const_pointer end = dest + count;
    for (; dest != end; ++dest)
        detail::create<value_type>(dest);
    _size = count;
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<
          detail::is_input_iterator<InputIt>::value &&
              std::is_constructible<
                  T,
                  typename std::iterator_traits<
                      InputIt>::reference>::value,
          InputIt>::type *>
vector<T>::vector(InputIt first, InputIt last)
{
    auto pop = pmemobj_pool_by_ptr(this);
    if (pop == nullptr)
        throw pool_error("Invalid pool handle.");

    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Range constructor called out of transaction scope.");

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

template <typename T>
vector<T>::vector(const vector &other)
{
    auto pop = pmemobj_pool_by_ptr(this);
    if (pop == nullptr)
        throw pool_error("Invalid pool handle.");

    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Copy constructor called out of transaction scope.");

    _data = nullptr;
    _size = 0;
    _alloc(other.capacity());
    _grow(other.begin(), other.end());
}

template <typename T>
vector<T>::vector(vector &&other)
{
    auto pop = pmemobj_pool_by_ptr(this);
    if (pop == nullptr)
        throw pool_error("Invalid pool handle.");

    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw transaction_error(
            "Move constructor called out of transaction scope.");

    _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()
{
    free_data();
}

template <typename T>
typename vector<T>::reference
vector<T>::at(size_type n)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    if (n >= _size)
        throw std::out_of_range("vector::at");
    detail::conditional_add_to_tx(&_data[n]);
    return _data[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[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[n];
}

template <typename T>
typename vector<T>::reference vector<T>::operator[](size_type n)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    detail::conditional_add_to_tx(&_data[n]);
    return _data[n];
}

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

template <typename T>
typename vector<T>::reference
vector<T>::front()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    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()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    detail::conditional_add_to_tx(&_data[size() - 1]);
    return _data[size() - 1];
}

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

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

template <typename T>
typename vector<T>::value_type *
vector<T>::data()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    detail::conditional_add_to_tx(_data.get(), 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()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    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()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    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()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    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()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    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>
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>
typename vector<T>::size_type
vector<T>::capacity() const noexcept
{
    return _capacity;
}

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

    auto pop = pmemobj_pool_by_ptr(this);
    assert(pop != nullptr);

    pool_base pb = pool_base(pop);
    transaction::run(pb, [&] {
        detail::conditional_add_to_tx(_data.get(), _size);
        _dealloc();
    });
}

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>::_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>
void
vector<T>::_grow(size_type count, const_reference value)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(_capacity >= count + _size);

    pointer dest = _data.get() + static_cast<size_type>(_size);
    const_pointer end = dest + count;
    for (; dest != end; ++dest)
        detail::create<value_type, const_reference>(dest, value);
    _size += count;
}

template <typename T>
template <typename InputIt,
      typename std::enable_if<
          detail::is_input_iterator<InputIt>::value &&
              std::is_constructible<
                  T,
                  typename std::iterator_traits<
                      InputIt>::reference>::value,
          InputIt>::type *>
void
vector<T>::_grow(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() + static_cast<size_type>(_size);
    _size += static_cast<size_type>(diff);
    while (first != last)
        detail::create<value_type>(dest++, *first++);
}

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

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

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);
}

} /* namespace experimental */

} /* namespace obj */

} /* namespace pmem */

#endif /* LIBPMEMOBJ_CPP_VECTOR_HPP */