basic_string.hpp

Go to the documentation of this file.

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

#ifndef LIBPMEMOBJ_CPP_BASIC_STRING_HPP
#define LIBPMEMOBJ_CPP_BASIC_STRING_HPP

#include <algorithm>
#include <limits>
#include <string>

#include <libpmemobj++/container/array.hpp>
#include <libpmemobj++/container/detail/contiguous_iterator.hpp>
#include <libpmemobj++/container/vector.hpp>
#include <libpmemobj++/detail/common.hpp>
#include <libpmemobj++/detail/iterator_traits.hpp>
#include <libpmemobj++/detail/life.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/slice.hpp>
#include <libpmemobj++/transaction.hpp>

namespace pmem
{

namespace obj
{

template <typename CharT, typename Traits = std::char_traits<CharT>>
class basic_string {
public:
    /* Member types */
    using traits_type = Traits;
    using value_type = CharT;
    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<CharT>;
    using const_iterator = const_pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    /* Number of characters which can be stored using sso */
    static constexpr size_type sso_capacity = (32 - 8) / sizeof(CharT) - 1;

    /* Constructors */
    basic_string();
    basic_string(size_type count, CharT ch);
    basic_string(const basic_string &other, size_type pos,
             size_type count = npos);
    basic_string(const std::basic_string<CharT> &other, size_type pos,
             size_type count = npos);
    basic_string(const CharT *s, size_type count);
    basic_string(const CharT *s);
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    basic_string(InputIt first, InputIt last);
    basic_string(const basic_string &other);
    basic_string(const std::basic_string<CharT> &other);
    basic_string(basic_string &&other);
    basic_string(std::initializer_list<CharT> ilist);

    /* Destructor */
    ~basic_string();

    /* Assignment operators */
    basic_string &operator=(const basic_string &other);
    basic_string &operator=(const std::basic_string<CharT> &other);
    basic_string &operator=(basic_string &&other);
    basic_string &operator=(const CharT *s);
    basic_string &operator=(CharT ch);
    basic_string &operator=(std::initializer_list<CharT> ilist);

    /* Assignment methods */
    basic_string &assign(size_type count, CharT ch);
    basic_string &assign(const basic_string &other);
    basic_string &assign(const std::basic_string<CharT> &other);
    basic_string &assign(const basic_string &other, size_type pos,
                 size_type count = npos);
    basic_string &assign(const std::basic_string<CharT> &other,
                 size_type pos, size_type count = npos);
    basic_string &assign(const CharT *s, size_type count);
    basic_string &assign(const CharT *s);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    basic_string &assign(InputIt first, InputIt last);
    basic_string &assign(basic_string &&other);
    basic_string &assign(std::initializer_list<CharT> ilist);

    /* 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;
    CharT &front();
    const CharT &front() const;
    const CharT &cfront() const;
    CharT &back();
    const CharT &back() const;
    const CharT &cback() const;
    CharT *data();
    const CharT *data() const noexcept;
    const CharT *cdata() const noexcept;
    const CharT *c_str() 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 */
    bool empty() const noexcept;
    size_type size() const noexcept;
    size_type length() const noexcept;
    size_type max_size() const noexcept;
    size_type capacity() const noexcept;
    void resize(size_type count, CharT ch);
    void resize(size_type n);
    void reserve(size_type new_cap = 0);
    void shrink_to_fit();
    void clear();

    /* Modifiers */
    basic_string &erase(size_type index = 0, size_type count = npos);
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    /* We add following overloads to resolve erase(0) ambiguity */
    template <typename T,
          typename Enable = typename std::enable_if<
              std::is_convertible<T, size_type>::value>::type>
    basic_string &erase(T param);
    template <typename T,
          typename Enable = typename std::enable_if<
              !std::is_convertible<T, size_type>::value>::type>
    iterator erase(T param);
    void pop_back();

    basic_string &append(size_type count, CharT ch);
    basic_string &append(const basic_string &str);
    basic_string &append(const basic_string &str, size_type pos,
                 size_type count = npos);
    basic_string &append(const CharT *s, size_type count);
    basic_string &append(const CharT *s);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    basic_string &append(InputIt first, InputIt last);
    basic_string &append(std::initializer_list<CharT> ilist);
    void push_back(CharT ch);
    basic_string &operator+=(const basic_string &str);
    basic_string &operator+=(const CharT *s);
    basic_string &operator+=(CharT c);
    basic_string &operator+=(std::initializer_list<CharT> ilist);

    basic_string &insert(size_type index, size_type count, CharT ch);
    basic_string &insert(size_type index, const CharT *s);
    basic_string &insert(size_type index, const CharT *s, size_type count);
    basic_string &insert(size_type index, const basic_string &str);
    basic_string &insert(size_type index1, const basic_string &str,
                 size_type index2, size_type count = npos);
    iterator insert(const_iterator pos, CharT ch);
    iterator insert(const_iterator pos, size_type count, CharT ch);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    iterator insert(const_iterator pos, InputIt first, InputIt last);
    iterator insert(const_iterator pos, std::initializer_list<CharT> ilist);
    template <typename T,
          typename Enable = typename std::enable_if<
              std::is_convertible<T, size_type>::value>::type>
    basic_string &insert(T param, size_type count, CharT ch);
    template <typename T,
          typename Enable = typename std::enable_if<
              !std::is_convertible<T, size_type>::value>::type>
    iterator insert(T param, size_type count, CharT ch);

    basic_string &replace(size_type index, size_type count,
                  const basic_string &str);
    basic_string &replace(const_iterator first, const_iterator last,
                  const basic_string &str);
    basic_string &replace(size_type index, size_type count,
                  const basic_string &str, size_type index2,
                  size_type count2 = npos);
    template <typename InputIt,
          typename Enable = typename pmem::detail::is_input_iterator<
              InputIt>::type>
    basic_string &replace(const_iterator first, const_iterator last,
                  InputIt first2, InputIt last2);
    basic_string &replace(const_iterator first, const_iterator last,
                  const CharT *s, size_type count2);
    basic_string &replace(const_iterator first, const_iterator last,
                  const CharT *s);
    basic_string &replace(size_type index, size_type count,
                  size_type count2, CharT ch);
    basic_string &replace(const_iterator first, const_iterator last,
                  size_type count2, CharT ch);
    basic_string &replace(size_type index, size_type count, const CharT *s,
                  size_type count2);
    basic_string &replace(size_type index, size_type count, const CharT *s);
    basic_string &replace(const_iterator first, const_iterator last,
                  std::initializer_list<CharT> ilist);

    size_type copy(CharT *s, size_type count, size_type index = 0) const;

    int compare(const basic_string &other) const;
    int compare(const std::basic_string<CharT> &other) const;
    int compare(size_type pos, size_type count,
            const basic_string &other) const;
    int compare(size_type pos, size_type count,
            const std::basic_string<CharT> &other) const;
    int compare(size_type pos1, size_type count1, const basic_string &other,
            size_type pos2, size_type count2 = npos) const;
    int compare(size_type pos1, size_type count1,
            const std::basic_string<CharT> &other, size_type pos2,
            size_type count2 = npos) const;
    int compare(const CharT *s) const;
    int compare(size_type pos, size_type count, const CharT *s) const;
    int compare(size_type pos, size_type count1, const CharT *s,
            size_type count2) const;

    /* Special value. The exact meaning depends on the context. */
    static const size_type npos = static_cast<size_type>(-1);

private:
    using sso_type = array<value_type, sso_capacity + 1>;
    using non_sso_type = vector<value_type>;

    union {
        struct {
            /*
             * EXACTLY the same type as first member in vector
             * Holds size for sso string, bit specified by _sso_mask
             * indicates if sso is used.
             */
            p<size_type> _size;

            sso_type _data;
        } sso;

        struct {
            non_sso_type _data;
        } non_sso;
    };

    /*
     * MSB is used because vector is known not to use entire range of
     * size_type.
     */
    static constexpr size_type _sso_mask = 1ULL
        << (std::numeric_limits<size_type>::digits - 1);

    /* helper functions */
    bool is_sso_used() const;
    void destroy_data();
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    size_type get_size(InputIt first, InputIt last) const;
    size_type get_size(size_type count, value_type ch) const;
    size_type get_size(const basic_string &other) const;
    template <typename... Args>
    pointer replace_content(Args &&... args);
    template <typename... Args>
    pointer initialize(Args &&... args);
    void allocate(size_type capacity);
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    pointer assign_sso_data(InputIt first, InputIt last);
    pointer assign_sso_data(size_type count, value_type ch);
    pointer assign_sso_data(basic_string &&other);
    template <
        typename InputIt,
        typename Enable = typename std::enable_if<
            pmem::detail::is_input_iterator<InputIt>::value>::type>
    pointer assign_large_data(InputIt first, InputIt last);
    pointer assign_large_data(size_type count, value_type ch);
    pointer assign_large_data(basic_string &&other);
    pool_base get_pool() const;
    void check_pmem() const;
    void check_tx_stage_work() const;
    void check_pmem_tx() const;
    void add_sso_to_tx(size_type first, size_type num) const;
    size_type get_sso_size() const;
    void enable_sso();
    void disable_sso();
    void set_sso_size(size_type new_size);
    void sso_to_large(size_t new_capacity);
    void large_to_sso();
    typename basic_string<CharT, Traits>::non_sso_type &non_sso_data();
    typename basic_string<CharT, Traits>::sso_type &sso_data();
    const typename basic_string<CharT, Traits>::non_sso_type &
    non_sso_data() const;
    const typename basic_string<CharT, Traits>::sso_type &sso_data() const;
};

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string()
{
    check_pmem_tx();
    sso._size = 0;

    allocate(0);
    initialize(0U, value_type('\0'));
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(size_type count, CharT ch)
{
    check_pmem_tx();
    sso._size = 0;

    allocate(count);
    initialize(count, ch);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const basic_string &other,
                      size_type pos, size_type count)
{
    check_pmem_tx();
    sso._size = 0;

    if (pos > other.size())
        throw std::out_of_range("Index out of range.");

    if (count == npos || pos + count > other.size())
        count = other.size() - pos;

    auto first = static_cast<difference_type>(pos);
    auto last = first + static_cast<difference_type>(count);

    allocate(count);
    initialize(other.cbegin() + first, other.cbegin() + last);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const std::basic_string<CharT> &other,
                      size_type pos, size_type count)
{
    check_pmem_tx();
    sso._size = 0;

    if (pos > other.size())
        throw std::out_of_range("Index out of range.");

    if (count == npos || pos + count > other.size())
        count = other.size() - pos;

    auto first = static_cast<difference_type>(pos);
    auto last = first + static_cast<difference_type>(count);

    allocate(count);
    initialize(other.cbegin() + first, other.cbegin() + last);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const CharT *s, size_type count)
{
    check_pmem_tx();
    sso._size = 0;

    allocate(count);
    initialize(s, s + count);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const CharT *s)
{
    check_pmem_tx();
    sso._size = 0;

    auto length = traits_type::length(s);

    allocate(length);
    initialize(s, s + length);
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits>::basic_string(InputIt first, InputIt last)
{
    auto len = std::distance(first, last);
    assert(len >= 0);

    check_pmem_tx();
    sso._size = 0;

    allocate(static_cast<size_type>(len));
    initialize(first, last);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const basic_string &other)
{
    check_pmem_tx();
    sso._size = 0;

    allocate(other.size());
    initialize(other.cbegin(), other.cend());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(const std::basic_string<CharT> &other)
    : basic_string(other.cbegin(), other.cend())
{
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(basic_string &&other)
{
    check_pmem_tx();
    sso._size = 0;

    allocate(other.size());
    initialize(std::move(other));

    if (other.is_sso_used())
        other.initialize(0U, value_type('\0'));
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::basic_string(std::initializer_list<CharT> ilist)
{
    check_pmem_tx();
    sso._size = 0;

    allocate(ilist.size());
    initialize(ilist.begin(), ilist.end());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits>::~basic_string()
{
    if (!is_sso_used())
        detail::destroy<non_sso_type>(non_sso_data());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(const basic_string &other)
{
    return assign(other);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(const std::basic_string<CharT> &other)
{
    return assign(other);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(basic_string &&other)
{
    return assign(std::move(other));
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(const CharT *s)
{
    return assign(s);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(CharT ch)
{
    return assign(1, ch);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator=(std::initializer_list<CharT> ilist)
{
    return assign(ilist);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(size_type count, CharT ch)
{
    auto pop = get_pool();

    transaction::run(pop, [&] { replace_content(count, ch); });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const basic_string &other)
{
    if (&other == this)
        return *this;

    auto pop = get_pool();

    transaction::run(
        pop, [&] { replace_content(other.cbegin(), other.cend()); });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const std::basic_string<CharT> &other)
{
    return assign(other.cbegin(), other.cend());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const basic_string &other, size_type pos,
                    size_type count)
{
    if (pos > other.size())
        throw std::out_of_range("Index out of range.");

    if (count == npos || pos + count > other.size())
        count = other.size() - pos;

    auto pop = get_pool();
    auto first = static_cast<difference_type>(pos);
    auto last = first + static_cast<difference_type>(count);

    transaction::run(pop, [&] {
        replace_content(other.cbegin() + first, other.cbegin() + last);
    });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const std::basic_string<CharT> &other,
                    size_type pos, size_type count)
{
    if (pos > other.size())
        throw std::out_of_range("Index out of range.");

    if (count == npos || pos + count > other.size())
        count = other.size() - pos;

    return assign(other.c_str() + pos, count);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const CharT *s, size_type count)
{
    auto pop = get_pool();

    transaction::run(pop, [&] { replace_content(s, s + count); });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(const CharT *s)
{
    auto pop = get_pool();

    auto length = traits_type::length(s);

    transaction::run(pop, [&] { replace_content(s, s + length); });

    return *this;
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(InputIt first, InputIt last)
{
    auto pop = get_pool();

    transaction::run(pop, [&] { replace_content(first, last); });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(basic_string &&other)
{
    if (&other == this)
        return *this;

    auto pop = get_pool();

    transaction::run(pop, [&] {
        replace_content(std::move(other));

        if (other.is_sso_used())
            other.initialize(0U, value_type('\0'));
    });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::assign(std::initializer_list<CharT> ilist)
{
    return assign(ilist.begin(), ilist.end());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::begin()
{
    return is_sso_used() ? iterator(&*sso_data().begin())
                 : iterator(&*non_sso_data().begin());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::begin() const noexcept
{
    return cbegin();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::cbegin() const noexcept
{
    return is_sso_used() ? const_iterator(&*sso_data().cbegin())
                 : const_iterator(&*non_sso_data().cbegin());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::end()
{
    return begin() + static_cast<difference_type>(size());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::end() const noexcept
{
    return cbegin() + static_cast<difference_type>(size());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_iterator
basic_string<CharT, Traits>::cend() const noexcept
{
    return cbegin() + static_cast<difference_type>(size());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reverse_iterator
basic_string<CharT, Traits>::rbegin()
{
    return reverse_iterator(end());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::rbegin() const noexcept
{
    return crbegin();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::crbegin() const noexcept
{
    return const_reverse_iterator(cend());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reverse_iterator
basic_string<CharT, Traits>::rend()
{
    return reverse_iterator(begin());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::rend() const noexcept
{
    return crend();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reverse_iterator
basic_string<CharT, Traits>::crend() const noexcept
{
    return const_reverse_iterator(cbegin());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reference
basic_string<CharT, Traits>::at(size_type n)
{
    if (n >= size())
        throw std::out_of_range("string::at");

    return is_sso_used() ? sso_data()[n] : non_sso_data()[n];
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reference
basic_string<CharT, Traits>::at(size_type n) const
{
    return const_at(n);
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reference
basic_string<CharT, Traits>::const_at(size_type n) const
{
    if (n >= size())
        throw std::out_of_range("string::const_at");

    return is_sso_used()
        ? static_cast<const sso_type &>(sso_data())[n]
        : static_cast<const non_sso_type &>(non_sso_data())[n];
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::reference basic_string<CharT, Traits>::
operator[](size_type n)
{
    return is_sso_used() ? sso_data()[n] : non_sso_data()[n];
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::const_reference
    basic_string<CharT, Traits>::operator[](size_type n) const
{
    return is_sso_used() ? sso_data()[n] : non_sso_data()[n];
}

template <typename CharT, typename Traits>
CharT &
basic_string<CharT, Traits>::front()
{
    return (*this)[0];
}

template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::front() const
{
    return cfront();
}

template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::cfront() const
{
    return static_cast<const basic_string &>(*this)[0];
}

template <typename CharT, typename Traits>
CharT &
basic_string<CharT, Traits>::back()
{
    return (*this)[size() - 1];
}

template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::back() const
{
    return cback();
}

template <typename CharT, typename Traits>
const CharT &
basic_string<CharT, Traits>::cback() const
{
    return static_cast<const basic_string &>(*this)[size() - 1];
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::size() const noexcept
{
    if (is_sso_used())
        return get_sso_size();
    else if (non_sso_data().size() == 0)
        return 0;
    else
        return non_sso_data().size() - 1;
}

template <typename CharT, typename Traits>
CharT *
basic_string<CharT, Traits>::data()
{
    return is_sso_used() ? sso_data().range(0, get_sso_size() + 1).begin()
                 : non_sso_data().data();
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::erase(size_type index, size_type count)
{
    auto sz = size();

    if (index > sz)
        throw std::out_of_range("Index exceeds size.");

    count = (std::min)(count, sz - index);

    auto pop = get_pool();

    auto first = begin() + static_cast<difference_type>(index);
    auto last = first + static_cast<difference_type>(count);

    if (is_sso_used()) {
        transaction::run(pop, [&] {
            auto move_len = sz - index - count;
            auto new_size = sz - count;

            auto range = sso_data().range(index, move_len + 1);

            traits_type::move(range.begin(), &*last, move_len);

            set_sso_size(new_size);

            assert(range.end() - 1 ==
                   &sso_data()._data[index + move_len]);
            *(range.end() - 1) = value_type('\0');
        });
    } else {
        non_sso_data().erase(first, last);
    }

    return *this;
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::erase(const_iterator pos)
{
    return erase(pos, pos + 1);
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::erase(const_iterator first, const_iterator last)
{
    size_type index =
        static_cast<size_type>(std::distance(cbegin(), first));
    size_type len = static_cast<size_type>(std::distance(first, last));

    erase(index, len);

    return begin() + static_cast<difference_type>(index);
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::pop_back()
{
    erase(size() - 1, 1);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(size_type count, CharT ch)
{
    auto sz = size();
    auto new_size = sz + count;

    if (new_size > max_size())
        throw std::length_error("Size exceeds max size.");

    if (is_sso_used()) {
        auto pop = get_pool();

        transaction::run(pop, [&] {
            if (new_size > sso_capacity) {
                sso_to_large(new_size);

                non_sso_data().insert(
                    non_sso_data().cbegin() +
                        static_cast<difference_type>(
                            sz),
                    count, ch);
            } else {
                add_sso_to_tx(sz, count + 1);
                traits_type::assign(&sso_data()._data[sz],
                            count, ch);

                assert(new_size == sz + count);
                set_sso_size(new_size);
                sso_data()._data[new_size] = value_type('\0');
            }
        });
    } else {
        non_sso_data().insert(non_sso_data().cbegin() +
                          static_cast<difference_type>(sz),
                      count, ch);
    }

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const basic_string &str)
{
    return append(str.data(), str.size());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const basic_string &str, size_type pos,
                    size_type count)
{
    auto sz = str.size();

    if (pos > sz)
        throw std::out_of_range("Index out of range.");

    count = (std::min)(count, sz - pos);

    append(str.data() + pos, count);

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const CharT *s, size_type count)
{
    return append(s, s + count);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(const CharT *s)
{
    return append(s, traits_type::length(s));
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(InputIt first, InputIt last)
{
    auto sz = size();
    auto count = static_cast<size_type>(std::distance(first, last));
    auto new_size = sz + count;

    if (new_size > max_size())
        throw std::length_error("Size exceeds max size.");

    if (is_sso_used()) {
        auto pop = get_pool();

        transaction::run(pop, [&] {
            if (new_size > sso_capacity) {
                /* 1) Cache C-style string in case of
                 * self-append, because it will be destroyed
                 * when switching from sso to large string.
                 *
                 * 2) We cache in std::vector instead of
                 * std::string because of overload deduction
                 * ambiguity on Windows
                 */
                std::vector<value_type> str(first, last);

                sso_to_large(new_size);
                non_sso_data().insert(
                    non_sso_data().cbegin() +
                        static_cast<difference_type>(
                            sz),
                    str.begin(), str.end());
            } else {
                add_sso_to_tx(sz, count + 1);
                std::copy(first, last, &sso_data()._data[sz]);

                assert(new_size == sz + count);
                set_sso_size(new_size);
                sso_data()._data[new_size] = value_type('\0');
            }
        });
    } else {
        non_sso_data().insert(non_sso_data().cbegin() +
                          static_cast<difference_type>(sz),
                      first, last);
    }

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::append(std::initializer_list<CharT> ilist)
{
    return append(ilist.begin(), ilist.end());
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::push_back(CharT ch)
{
    append(static_cast<size_type>(1), ch);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(const basic_string &str)
{
    return append(str);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(const CharT *s)
{
    return append(s);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(CharT ch)
{
    push_back(ch);

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::operator+=(std::initializer_list<CharT> ilist)
{
    return append(ilist);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, size_type count, CharT ch)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");

    auto pos = cbegin() + static_cast<difference_type>(index);

    insert(pos, count, ch);

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, const CharT *s)
{
    return insert(index, s, traits_type::length(s));
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, const CharT *s,
                    size_type count)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");

    auto pos = cbegin() + static_cast<difference_type>(index);

    insert(pos, s, s + count);

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index, const basic_string &str)
{
    return insert(index, str.data(), str.size());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(size_type index1, const basic_string &str,
                    size_type index2, size_type count)
{
    auto sz = str.size();

    if (index1 > size() || index2 > sz)
        throw std::out_of_range("Index out of range.");

    count = (std::min)(count, sz - index2);

    return insert(index1, str.data() + index2, count);
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos, CharT ch)
{
    return insert(pos, 1, ch);
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos, size_type count,
                    CharT ch)
{
    auto sz = size();

    if (sz + count > max_size())
        throw std::length_error("Count exceeds max size.");

    auto new_size = sz + count;

    auto pop = get_pool();

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

    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            auto len = sz - index;

            add_sso_to_tx(index, len + count + 1);

            traits_type::move(&sso_data()._data[index + count],
                      &sso_data()._data[index], len);
            traits_type::assign(&sso_data()._data[index], count,
                        ch);

            assert(new_size == index + len + count);
            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            if (is_sso_used())
                sso_to_large(new_size);

            non_sso_data().insert(
                non_sso_data().begin() +
                    static_cast<difference_type>(index),
                count, ch);
        }
    });

    return iterator(&data()[static_cast<difference_type>(index)]);
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos, InputIt first,
                    InputIt last)
{
    auto sz = size();

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

    if (sz + count > max_size())
        throw std::length_error("Count exceeds max size.");

    auto pop = get_pool();

    auto new_size = sz + count;

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

    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            auto len = sz - index;

            add_sso_to_tx(index, len + count + 1);

            traits_type::move(&sso_data()._data[index + count],
                      &sso_data()._data[index], len);
            std::copy(first, last, &sso_data()._data[index]);

            assert(new_size == index + len + count);
            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            if (is_sso_used()) {
                /* 1) Cache C-style string in case of
                 * self-insert, because it will be destroyed
                 * when switching from sso to large string.
                 *
                 * 2) We cache in std::vector instead of
                 * std::string because of overload deduction
                 * ambiguity on Windows
                 */
                std::vector<value_type> str(first, last);

                sso_to_large(new_size);
                non_sso_data().insert(
                    non_sso_data().begin() +
                        static_cast<difference_type>(
                            index),
                    str.begin(), str.end());
            } else {
                non_sso_data().insert(
                    non_sso_data().begin() +
                        static_cast<difference_type>(
                            index),
                    first, last);
            }
        }
    });

    return iterator(&data()[static_cast<difference_type>(index)]);
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(const_iterator pos,
                    std::initializer_list<CharT> ilist)
{
    return insert(pos, ilist.begin(), ilist.end());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const basic_string &str)
{
    return replace(index, count, str.data(), str.size());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     const basic_string &str)
{
    return replace(first, last, str.data(), str.data() + str.size());
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const basic_string &str, size_type index2,
                     size_type count2)
{
    auto sz = str.size();

    if (index2 > sz)
        throw std::out_of_range("Index out of range.");

    count2 = (std::min)(count2, sz - index2);

    return replace(index, count, str.data() + index2, count2);
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     InputIt first2, InputIt last2)
{
    auto sz = size();
    auto index = static_cast<size_type>(std::distance(cbegin(), first));
    auto count = static_cast<size_type>(std::distance(first, last));
    auto count2 = static_cast<size_type>(std::distance(first2, last2));

    count = (std::min)(count, sz - index);

    if (sz - count + count2 > max_size())
        throw std::length_error("Count exceeds max size.");

    auto new_size = sz - count + count2;

    auto pop = get_pool();

    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            add_sso_to_tx(index, new_size - index + 1);

            assert(count2 < new_size + 1);
            traits_type::move(&sso_data()._data[index + count2],
                      &sso_data()._data[index + count],
                      sz - index - count);
            std::copy(first2, last2, &sso_data()._data[index]);

            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            /* 1) Cache C-style string in case of
             * self-replace, because it will be destroyed
             * when switching from sso to large string.
             *
             * 2) We cache in std::vector instead of
             * std::string because of overload deduction
             * ambiguity on Windows
             */
            std::vector<value_type> str(first2, last2);

            if (is_sso_used()) {
                sso_to_large(new_size);
            }

            auto beg =
                begin() + static_cast<difference_type>(index);
            auto end = beg + static_cast<difference_type>(count);
            non_sso_data().erase(beg, end);
            non_sso_data().insert(beg, str.begin(), str.end());
        }

        if (!is_sso_used() && new_size <= sso_capacity)
            large_to_sso();
    });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     const CharT *s, size_type count2)
{
    return replace(first, last, s, s + count2);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const CharT *s, size_type count2)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");

    auto first = cbegin() + static_cast<difference_type>(index);
    auto last = first + static_cast<difference_type>(count);

    return replace(first, last, s, s + count2);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     const CharT *s)
{
    return replace(index, count, s, traits_type::length(s));
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(size_type index, size_type count,
                     size_type count2, CharT ch)
{
    if (index > size())
        throw std::out_of_range("Index out of range.");

    auto first = cbegin() + static_cast<difference_type>(index);
    auto last = first + static_cast<difference_type>(count);

    return replace(first, last, count2, ch);
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     size_type count2, CharT ch)
{
    auto sz = size();
    auto index = static_cast<size_type>(std::distance(cbegin(), first));
    auto count = static_cast<size_type>(std::distance(first, last));

    count = (std::min)(count, sz - index);

    if (sz - count + count2 > max_size())
        throw std::length_error("Count exceeds max size.");

    auto new_size = sz - count + count2;

    auto pop = get_pool();

    transaction::run(pop, [&] {
        if (is_sso_used() && new_size <= sso_capacity) {
            add_sso_to_tx(index, new_size - index + 1);

            assert(count2 < new_size + 1);
            traits_type::move(&sso_data()._data[index + count2],
                      &sso_data()._data[index + count],
                      sz - index - count);
            traits_type::assign(&sso_data()._data[index], count2,
                        ch);

            set_sso_size(new_size);
            sso_data()._data[new_size] = value_type('\0');
        } else {
            if (is_sso_used()) {
                sso_to_large(new_size);
            }

            auto beg =
                begin() + static_cast<difference_type>(index);
            auto end = beg + static_cast<difference_type>(count);
            non_sso_data().erase(beg, end);
            non_sso_data().insert(beg, count2, ch);
        }

        if (!is_sso_used() && new_size <= sso_capacity)
            large_to_sso();
    });

    return *this;
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     const CharT *s)
{
    return replace(first, last, s, traits_type::length(s));
}

template <typename CharT, typename Traits>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::replace(const_iterator first, const_iterator last,
                     std::initializer_list<CharT> ilist)
{
    return replace(first, last, ilist.begin(), ilist.end());
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::copy(CharT *s, size_type count,
                  size_type index) const
{
    auto sz = size();

    if (index > sz)
        throw std::out_of_range("Index out of range.");

    auto len = (std::min)(count, sz - index);

    traits_type::copy(s, data() + index, len);

    return len;
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos, size_type count1,
                     const CharT *s, size_type count2) const
{
    if (pos > size())
        throw std::out_of_range("Index out of range.");

    if (count1 > size() - pos)
        count1 = size() - pos;

    auto ret = traits_type::compare(cdata() + pos, s,
                    std::min<size_type>(count1, count2));

    if (ret != 0)
        return ret;

    if (count1 < count2)
        return -1;
    else if (count1 == count2)
        return 0;
    else
        return 1;
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(const basic_string &other) const
{
    return compare(0, size(), other.cdata(), other.size());
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(
    const std::basic_string<CharT> &other) const
{
    return compare(0, size(), other.data(), other.size());
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos, size_type count,
                     const basic_string &other) const
{
    return compare(pos, count, other.cdata(), other.size());
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(
    size_type pos, size_type count,
    const std::basic_string<CharT> &other) const
{
    return compare(pos, count, other.data(), other.size());
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos1, size_type count1,
                     const basic_string &other, size_type pos2,
                     size_type count2) const
{
    if (pos2 > other.size())
        throw std::out_of_range("Index out of range.");

    if (count2 > other.size() - pos2)
        count2 = other.size() - pos2;

    return compare(pos1, count1, other.cdata() + pos2, count2);
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos1, size_type count1,
                     const std::basic_string<CharT> &other,
                     size_type pos2, size_type count2) const
{
    if (pos2 > other.size())
        throw std::out_of_range("Index out of range.");

    if (count2 > other.size() - pos2)
        count2 = other.size() - pos2;

    return compare(pos1, count1, other.data() + pos2, count2);
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(const CharT *s) const
{
    return compare(0, size(), s, traits_type::length(s));
}

template <typename CharT, typename Traits>
int
basic_string<CharT, Traits>::compare(size_type pos, size_type count,
                     const CharT *s) const
{
    return compare(pos, count, s, traits_type::length(s));
}

template <typename CharT, typename Traits>
const CharT *
basic_string<CharT, Traits>::cdata() const noexcept
{
    return is_sso_used() ? sso_data().cdata() : non_sso_data().cdata();
}

template <typename CharT, typename Traits>
const CharT *
basic_string<CharT, Traits>::data() const noexcept
{
    return cdata();
}

template <typename CharT, typename Traits>
const CharT *
basic_string<CharT, Traits>::c_str() const noexcept
{
    return cdata();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::length() const noexcept
{
    return size();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::max_size() const noexcept
{
    return PMEMOBJ_MAX_ALLOC_SIZE / sizeof(CharT) - 1;
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::capacity() const noexcept
{
    return is_sso_used() ? sso_capacity : non_sso_data().capacity() - 1;
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::resize(size_type count, CharT ch)
{
    if (count > max_size())
        throw std::length_error("Count exceeds max size.");

    auto sz = size();

    auto pop = get_pool();

    transaction::run(pop, [&] {
        if (count > sz) {
            append(count - sz, ch);
        } else if (is_sso_used()) {
            set_sso_size(count);
            sso_data()[count] = value_type('\0');
        } else {
            non_sso_data().resize(count + 1, ch);
            non_sso_data().back() = value_type('\0');
        }
    });
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::resize(size_type count)
{
    resize(count, CharT());
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::reserve(size_type new_cap)
{
    if (new_cap > max_size())
        throw std::length_error("New capacity exceeds max size.");

    if (new_cap < capacity() || new_cap <= sso_capacity)
        return;

    if (is_sso_used()) {
        auto pop = get_pool();

        transaction::run(pop, [&] { sso_to_large(new_cap); });
    } else {
        non_sso_data().reserve(new_cap + 1);
    }
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::shrink_to_fit()
{
    if (is_sso_used())
        return;

    if (size() <= sso_capacity) {
        auto pop = get_pool();

        transaction::run(pop, [&] { large_to_sso(); });
    } else {
        non_sso_data().shrink_to_fit();
    }
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::clear()
{
    erase(begin(), end());
}

template <typename CharT, typename Traits>
bool
basic_string<CharT, Traits>::empty() const noexcept
{
    return size() == 0;
}

template <typename CharT, typename Traits>
bool
basic_string<CharT, Traits>::is_sso_used() const
{
    return (sso._size & _sso_mask) != 0;
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::destroy_data()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    if (is_sso_used()) {
        add_sso_to_tx(0, get_sso_size() + 1);
        /* sso.data destructor does not have to be called */
    } else {
        non_sso_data().free_data();
        detail::destroy<non_sso_type>(non_sso_data());
    }
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_size(InputIt first, InputIt last) const
{
    return static_cast<size_type>(std::distance(first, last));
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_size(size_type count, value_type ch) const
{
    return count;
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_size(const basic_string &other) const
{
    return other.size();
}

template <typename CharT, typename Traits>
template <typename... Args>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::replace_content(Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    auto new_size = get_size(std::forward<Args>(args)...);

    /* If non_sso.data is used and there is enough capacity */
    if (!is_sso_used() && new_size <= capacity())
        return assign_large_data(std::forward<Args>(args)...);

    destroy_data();

    allocate(new_size);
    return initialize(std::forward<Args>(args)...);
}

template <typename CharT, typename Traits>
template <typename... Args>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::initialize(Args &&... args)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    auto size = get_size(std::forward<Args>(args)...);

    if (is_sso_used()) {
        auto ptr = assign_sso_data(std::forward<Args>(args)...);
        set_sso_size(size);

        return ptr;
    } else {
        return assign_large_data(std::forward<Args>(args)...);
    }
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::allocate(size_type capacity)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    if (capacity <= sso_capacity) {
        enable_sso();
    } else {
        disable_sso();
    }

    /*
     * array is aggregate type so it's not required to call
     * a constructor.
     */
    if (!is_sso_used()) {
        detail::conditional_add_to_tx(&non_sso_data(), 1,
                          POBJ_XADD_NO_SNAPSHOT);
        detail::create<non_sso_type>(&non_sso_data());
        non_sso_data().reserve(capacity + 1);
    }
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_sso_data(InputIt first, InputIt last)
{
    auto size = static_cast<size_type>(std::distance(first, last));

    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(size <= sso_capacity);

    add_sso_to_tx(0, size + 1);
    std::copy(first, last, &sso_data()._data[0]);

    sso_data()._data[size] = value_type('\0');

    return &sso_data()[0];
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_sso_data(size_type count, value_type ch)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(count <= sso_capacity);

    add_sso_to_tx(0, count + 1);
    traits_type::assign(&sso_data()._data[0], count, ch);

    sso_data()._data[count] = value_type('\0');

    return &sso_data()[0];
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_sso_data(basic_string &&other)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    return assign_sso_data(other.cbegin(), other.cend());
}

template <typename CharT, typename Traits>
template <typename InputIt, typename Enable>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_large_data(InputIt first, InputIt last)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

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

    non_sso_data().reserve(size + 1);
    non_sso_data().assign(first, last);
    non_sso_data().push_back(value_type('\0'));

    return non_sso_data().data();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_large_data(size_type count, value_type ch)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    non_sso_data().reserve(count + 1);
    non_sso_data().assign(count, ch);
    non_sso_data().push_back(value_type('\0'));

    return non_sso_data().data();
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::pointer
basic_string<CharT, Traits>::assign_large_data(basic_string &&other)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);

    if (other.is_sso_used())
        return assign_large_data(other.cbegin(), other.cend());

    non_sso_data() = std::move(other.non_sso_data());

    return non_sso_data().data();
}

template <typename CharT, typename Traits>
pool_base
basic_string<CharT, Traits>::get_pool() const
{
    auto pop = pmemobj_pool_by_ptr(this);
    assert(pop != nullptr);

    return pool_base(pop);
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::check_pmem() const
{
    if (pmemobj_pool_by_ptr(this) == nullptr)
        throw pmem::pool_error("Object is not on pmem.");
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::check_tx_stage_work() const
{
    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw pmem::transaction_scope_error(
            "Call made out of transaction scope.");
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::check_pmem_tx() const
{
    check_pmem();
    check_tx_stage_work();
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::add_sso_to_tx(size_type idx_first,
                       size_type num) const
{
    assert(idx_first + num <= sso_capacity + 1);
    assert(is_sso_used());

    auto initialized_num = get_sso_size() + 1 - idx_first;

    /* Snapshot elements in range [idx_first, sso_size + 1 (null)) */
    detail::conditional_add_to_tx(&sso_data()._data[0] + idx_first,
                      (std::min)(initialized_num, num));

    if (num > initialized_num) {
        /* Elements after sso_size + 1 do not have to be snapshotted */
        detail::conditional_add_to_tx(
            &sso_data()._data[0] + get_sso_size() + 1,
            num - initialized_num, POBJ_XADD_NO_SNAPSHOT);
    }
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::size_type
basic_string<CharT, Traits>::get_sso_size() const
{
    return sso._size & ~_sso_mask;
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::enable_sso()
{
    /* temporary size_type must be created to avoid undefined reference
     * linker error */
    sso._size |= (size_type)(_sso_mask);
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::disable_sso()
{
    sso._size &= ~_sso_mask;
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::set_sso_size(size_type new_size)
{
    sso._size = new_size | _sso_mask;
}

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::sso_to_large(size_t new_capacity)
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(new_capacity > sso_capacity);
    assert(is_sso_used());

    auto sz = size();

    sso_type tmp;
    std::copy(cbegin(), cend(), tmp.data());
    tmp[sz] = value_type('\0');

    destroy_data();
    allocate(new_capacity);

    auto begin = tmp.cbegin();
    auto end = begin + sz;

    initialize(begin, end);

    assert(!is_sso_used());
};

template <typename CharT, typename Traits>
void
basic_string<CharT, Traits>::large_to_sso()
{
    assert(pmemobj_tx_stage() == TX_STAGE_WORK);
    assert(!is_sso_used());

    auto sz = size();

    assert(sz <= sso_capacity);

    sso_type tmp;
    std::copy(cbegin(), cbegin() + sz, tmp.data());
    tmp[sz] = value_type('\0');

    destroy_data();
    allocate(sz);

    auto begin = tmp.cbegin();
    auto end = begin + sz;

    initialize(begin, end);

    assert(is_sso_used());
};

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::non_sso_type &
basic_string<CharT, Traits>::non_sso_data()
{
    assert(!is_sso_used());
    return non_sso._data;
}

template <typename CharT, typename Traits>
typename basic_string<CharT, Traits>::sso_type &
basic_string<CharT, Traits>::sso_data()
{
    assert(is_sso_used());
    return sso._data;
}

template <typename CharT, typename Traits>
const typename basic_string<CharT, Traits>::non_sso_type &
basic_string<CharT, Traits>::non_sso_data() const
{
    assert(!is_sso_used());
    return non_sso._data;
}

template <typename CharT, typename Traits>
const typename basic_string<CharT, Traits>::sso_type &
basic_string<CharT, Traits>::sso_data() const
{
    assert(is_sso_used());
    return sso._data;
}

template <typename CharT, typename Traits>
template <typename T, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::erase(T param)
{
    return erase(static_cast<size_type>(param));
}

template <typename CharT, typename Traits>
template <typename T, typename Enable>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::erase(T param)
{
    return erase(static_cast<const_iterator>(param));
}

template <typename CharT, typename Traits>
template <typename T, typename Enable>
basic_string<CharT, Traits> &
basic_string<CharT, Traits>::insert(T param, size_type count, CharT ch)
{
    return insert(static_cast<size_type>(param), count, ch);
}

template <typename CharT, typename Traits>
template <typename T, typename Enable>
typename basic_string<CharT, Traits>::iterator
basic_string<CharT, Traits>::insert(T param, size_type count, CharT ch)
{
    return insert(static_cast<const_iterator>(param), count, ch);
}

template <class CharT, class Traits>
bool
operator==(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) == 0;
}

template <class CharT, class Traits>
bool
operator!=(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) != 0;
}

template <class CharT, class Traits>
bool
operator<(const basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) < 0;
}

template <class CharT, class Traits>
bool
operator<=(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) <= 0;
}

template <class CharT, class Traits>
bool
operator>(const basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) > 0;
}

template <class CharT, class Traits>
bool
operator>=(const basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) >= 0;
}

template <class CharT, class Traits>
bool
operator==(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) == 0;
}

template <class CharT, class Traits>
bool
operator!=(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) != 0;
}

template <class CharT, class Traits>
bool
operator<(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) > 0;
}

template <class CharT, class Traits>
bool
operator<=(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) >= 0;
}

template <class CharT, class Traits>
bool
operator>(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) < 0;
}

template <class CharT, class Traits>
bool
operator>=(const CharT *lhs, const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) <= 0;
}

template <class CharT, class Traits>
bool
operator==(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) == 0;
}

template <class CharT, class Traits>
bool
operator!=(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) != 0;
}

template <class CharT, class Traits>
bool
operator<(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) < 0;
}

template <class CharT, class Traits>
bool
operator<=(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) <= 0;
}

template <class CharT, class Traits>
bool
operator>(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) > 0;
}

template <class CharT, class Traits>
bool
operator>=(const basic_string<CharT, Traits> &lhs, const CharT *rhs)
{
    return lhs.compare(rhs) >= 0;
}

template <class CharT, class Traits>
bool
operator==(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) == 0;
}

template <class CharT, class Traits>
bool
operator!=(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) != 0;
}

template <class CharT, class Traits>
bool
operator<(const std::basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) > 0;
}

template <class CharT, class Traits>
bool
operator<=(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) >= 0;
}

template <class CharT, class Traits>
bool
operator>(const std::basic_string<CharT, Traits> &lhs,
      const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) < 0;
}

template <class CharT, class Traits>
bool
operator>=(const std::basic_string<CharT, Traits> &lhs,
       const basic_string<CharT, Traits> &rhs)
{
    return rhs.compare(lhs) <= 0;
}

template <class CharT, class Traits>
bool
operator==(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) == 0;
}

template <class CharT, class Traits>
bool
operator!=(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) != 0;
}

template <class CharT, class Traits>
bool
operator<(const basic_string<CharT, Traits> &lhs,
      const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) < 0;
}

template <class CharT, class Traits>
bool
operator<=(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) <= 0;
}

template <class CharT, class Traits>
bool
operator>(const basic_string<CharT, Traits> &lhs,
      const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) > 0;
}

template <class CharT, class Traits>
bool
operator>=(const basic_string<CharT, Traits> &lhs,
       const std::basic_string<CharT, Traits> &rhs)
{
    return lhs.compare(rhs) >= 0;
}

} /* namespace obj */

} /* namespace pmem */

#endif /* LIBPMEMOBJ_CPP_BASIC_STRING_HPP */