An immutable C++ string with ref-counting

Question

Class intended to be used as main type in a key-value database where keys and values are strings. Searched features:

• It is a const char *
• Behaves like a std::string
• Reference counting integrated reducing the number of indirections
• Vampirizes string_view using ptr + len
• Some additional methods (contains(), trim(), etc)

Basically, it is a pointer to chars where pointed memory is prefixed by the ref-counter (4-bytes) and the string length (4-bytes).

An example of usage and the unit tests can be found at:
https://github.com/torrentg/cstring

Not 100% sure on memory alignment and thread-safety.
I will appreciate your comments and suggestions.

Here is cstring.hpp

#pragma once

#include <memory>
#include <string>
#include <limits>
#include <atomic>
#include <utility>
#include <cassert>
#include <cstdint>
#include <stdexcept>
#include <string_view>
#include <type_traits>

namespace gto {

/**
 * @brief Immutable string based on a plain C-string (char *) with ref-counting.
 * @details
 *   - Shared content between multiple instances (using ref counting).
 *   - Automatic mem dealloc (when no refs point to content).
 *   - Same sizeof than a 'char *'.
 *   - Null not allowed (equals to empty string).
 *   - Empty string don't require alloc.
 *   - String content available on debug.
 *   - Mimics the STL basic_string class.
 * @details Memory layout:
 * 
 *       ----|----|-----------0
 *        ^   ^    ^
 *        |   |    |-- string content (0-ended)
 *        |   |-- string length (4-bytes)
 *        |-- ref counter (4-bytes)
 * 
 *   mStr (cstring pointer) points to the string content (to allow view content on debug).
 *   Allocated memory is aligned to ref counter type size.
 *   Allocated memory is a multiple of ref counter type size.
 * @todo
 *   - Validate assumption that sizeof(atomic<uint32_t>) == sizeof(uint32_t)
 *   - Check that processor assumes memory alignment or we need to add __builtin_assume_aligned(a)) or __attribute((aligned(4)))
 *   - Check that std::atomic is enough to grant integrity in a multi-threaded usage
 *   - Explore cache invalidation impact on multi-threaded code
 *   - Performance tests
 * @see https://en.cppreference.com/w/cpp/string/basic_string
 * @see https://github.com/torrentg/cstring
 * @note This class is immutable.
 * @version 0.9.0
 */
template<typename Char,
         typename Traits = std::char_traits<Char>,
         typename Allocator = std::allocator<Char>>
class basic_cstring
{
  public: // declarations

    using prefix_type = std::uint32_t;
    using atomic_prefix_type = std::atomic<prefix_type>;

    using allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<prefix_type>;
    using allocator_traits = std::allocator_traits<allocator_type>;

    using traits_type = Traits;
    using size_type = typename std::allocator_traits<Allocator>::size_type;
    using difference_type = typename std::allocator_traits<Allocator>::difference_type;

    using value_type = Char;
    using const_reference = const value_type &;
    using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
    using const_iterator = const_pointer;
    using const_reverse_iterator = typename std::reverse_iterator<const_iterator>;
    using basic_cstring_view = std::basic_string_view<value_type, traits_type>;

  private: // declarations

    using pointer = typename std::allocator_traits<Allocator>::pointer;

  public: // static members

    static constexpr size_type npos = std::numeric_limits<size_type>::max();

  private: // static members

    static allocator_type alloc;
    static constexpr prefix_type mEmpty[3] = {0, 0, static_cast<prefix_type>(value_type())};

  private: // members

    //! Memory buffer with prefix_type alignment.
    const_pointer mStr = nullptr;

  private: // static methods

    //! Sanitize a char array pointer avoiding nulls.
    static inline constexpr const_pointer sanitize(const_pointer str) {
      return (str == nullptr ? getPtrToString(mEmpty) : str);
    }

    //! Return pointer to counter from pointer to string.
    static inline constexpr atomic_prefix_type * getPtrToCounter(const_pointer str) {
      assert(str != nullptr);
      pointer ptr = const_cast<pointer>(str) - 2 * sizeof(prefix_type);
      return reinterpret_cast<atomic_prefix_type *>(ptr);
    }

    //! Return pointer to string length from pointer to string.
    static inline constexpr prefix_type * getPtrToLength(const_pointer str) {
      assert(str != nullptr);
      pointer ptr = const_cast<pointer>(str) - sizeof(prefix_type);
      return reinterpret_cast<prefix_type *>(ptr);
    }

    //! Return pointer to string from pointer to counter.
    static inline constexpr const_pointer getPtrToString(const prefix_type *ptr) {
      assert(ptr != nullptr);
      return reinterpret_cast<const_pointer>(ptr + 2);
    }

    //! Returns the allocated array length (of prefix_type values).
    //! @details It is granted that there is place for the ending '\0'.
    static size_type getAllocatedLength(size_type len) {
      return (3 + (len * sizeof(value_type)) / sizeof(prefix_type));
    }

    //! Allocate memory for the counter + length + string + eof. Returns a pointer to string.
    static pointer allocate(size_type len) {
      assert(len > 0);
      assert(len <= std::numeric_limits<prefix_type>::max());
      size_type n = getAllocatedLength(len);
      prefix_type *ptr = allocator_traits::allocate(alloc, n);
      assert(reinterpret_cast<std::size_t>(ptr) % alignof(prefix_type) == 0);
      allocator_traits::construct(alloc, ptr, 1);
      ptr[1] = static_cast<prefix_type>(len);
      return const_cast<pointer>(getPtrToString(ptr));
    }

    //! Deallocate string memory if no more references.
    static void deallocate(const_pointer str) {
      atomic_prefix_type *ptr = getPtrToCounter(str);
      switch(ptr[0]) {
        case 0: // constant
          break;
        case 1: { // there are no more references
          prefix_type len = *getPtrToLength(str);
          size_type n = getAllocatedLength(len);
          allocator_traits::destroy(alloc, ptr);
          allocator_traits::deallocate(alloc, reinterpret_cast<prefix_type *>(ptr), n);
          break;
        }
        default:
          ptr[0]--;
      }
    }

    //! Increment the reference counter (except for constants).
    static void incrementRefCounter(const_pointer str) {
      atomic_prefix_type *ptr = getPtrToCounter(str);
      if (ptr[0] > 0) {
        ptr[0]++;
      }
    }

  public: // methods

    //! Default constructor.
    basic_cstring() : basic_cstring(nullptr) {}
    //! Constructor.
    basic_cstring(const_pointer str) : basic_cstring(str, (str == nullptr ? 0 : traits_type::length(str))) {}
    //! Constructor.
    basic_cstring(const_pointer str, size_type len) {
      if (str == nullptr || len == 0) {
        mStr = getPtrToString(mEmpty);
        return;
      } else {
        pointer content = allocate(len);
        traits_type::copy(content, str, len);
        content[len] = value_type();
        mStr = content;
      }
    }
    //! Destructor.
    ~basic_cstring() { deallocate(mStr); }

    //! Copy constructor.
    basic_cstring(const basic_cstring &other) noexcept : mStr(other.mStr) { incrementRefCounter(mStr); }
    //! Move constructor.
    basic_cstring(basic_cstring &&other) noexcept : mStr(std::exchange(other.mStr, getPtrToString(mEmpty))) {}

    //! Copy assignment.
    basic_cstring & operator=(const basic_cstring &other) { 
      if (mStr == other.mStr) return *this;
      deallocate(mStr);
      mStr = other.mStr;
      incrementRefCounter(mStr);
      return *this;
    }
    //! Move assignment.
    basic_cstring & operator=(basic_cstring &&other) noexcept { std::swap(mStr, other.mStr); return *this; }

    //! Return length of string.
    size_type size() const noexcept { return *(getPtrToLength(mStr)); }
    //! Return length of string.
    size_type length() const noexcept { return *(getPtrToLength(mStr)); }
    //! Test if string is empty.
    bool empty() const noexcept { return (length() == 0); }

    //! Get character of string.
    const_reference operator[](size_type pos) const { return mStr[pos]; }
    //! Get character of string checking for out_of_range.
    const_reference at(size_type pos) const { return (empty() || pos >= length() ? throw std::out_of_range("cstring::at") : mStr[pos]); }
    //! Get last character of the string.
    const_reference back() const { return (empty() ? throw std::out_of_range("cstring::back") : mStr[length()-1]); }
    //! Get first character of the string.
    const_reference front() const { return (empty() ? throw std::out_of_range("cstring::front") : mStr[0]); }

    //! Returns a non-null pointer to a null-terminated character array.
    inline const_pointer data() const noexcept { assert(mStr != nullptr); return mStr; }
    //! Returns a non-null pointer to a null-terminated character array.
    inline const_pointer c_str() const noexcept { return data(); }
    //! Returns a string_view of content.
    inline basic_cstring_view view() const { return basic_cstring_view(mStr, length()); }

    // Const iterator to the begin.
    const_iterator cbegin() const noexcept { return view().cbegin(); }
    // Const iterator to the end.
    const_iterator cend() const noexcept { return view().cend(); }
    // Const reverse iterator to the begin.
    const_reverse_iterator crbegin() const noexcept { return view().crbegin(); }
    // Const reverse iterator to the end.
    const_reverse_iterator crend() const noexcept { return view().crend(); }

    //! Exchanges the contents of the string with those of other.
    void swap(basic_cstring &other) noexcept { std::swap(mStr, other.mStr); }

    //! Returns the substring [pos, pos+len).
    basic_cstring_view substr(size_type pos=0, size_type len=npos) const { return view().substr(pos, len); }

    //! Compare contents.
    int compare(const basic_cstring &other) const noexcept {
      return view().compare(other.view());
    }
    int compare(size_type pos, size_type len, const basic_cstring &other) const noexcept { 
      return substr(pos, len).compare(other.view());
    }
    int compare(size_type pos1, size_type len1, const basic_cstring &other, size_type pos2, size_type len2=npos) const {
      return substr(pos1, len1).compare(other.substr(pos2, len2));
    }
    int compare(const_pointer str) const {
      return view().compare(sanitize(str));
    }
    int compare(size_type pos, size_type len, const_pointer str) const {
      return substr(pos, len).compare(sanitize(str));
    }
    int compare(size_type pos, size_type len, const_pointer str, size_type len2) const {
      return substr(pos, len).compare(basic_cstring_view(sanitize(str), len2));
    }
    int compare(const basic_cstring_view other) const noexcept {
      return view().compare(other);
    }

    //! Checks if the string view begins with the given prefix.
    bool starts_with(const basic_cstring &other) const noexcept {
      size_type len = other.length();
      return (compare(0, len, other) == 0);
    }
    bool starts_with(const basic_cstring_view sv) const noexcept {
      auto len = sv.length();
      return (compare(0, len, sv.data()) == 0);
    }
    bool starts_with(const_pointer str) const noexcept {
      return starts_with(basic_cstring_view(sanitize(str)));
    }

    //! Checks if the string ends with the given suffix.
    bool ends_with(const basic_cstring &other) const noexcept {
      auto len1 = length();
      auto len2 = other.length();
      return (len1 >= len2 && compare(len1-len2, len2, other) == 0);
    }
    bool ends_with(const basic_cstring_view sv) const noexcept {
      size_type len1 = length();
      size_type len2 = sv.length();
      return (len1 >= len2 && compare(len1-len2, len2, sv.data()) == 0);
    }
    bool ends_with(const_pointer str) const noexcept {
      return ends_with(basic_cstring_view(sanitize(str)));
    }

    //! Find the first ocurrence of a substring.
    auto find(const basic_cstring &other, size_type pos=0) const noexcept{
      return view().find(other.view(), pos);
    }
    auto find(const_pointer str, size_type pos, size_type len) const {
      return view().find(sanitize(str), pos, len);
    }
    auto find(const_pointer str, size_type pos=0) const {
      return view().find(sanitize(str), pos);
    }
    auto find(value_type c, size_type pos=0) const noexcept {
      return view().find(c, pos);
    }

    //! Find the last occurrence of a substring.
    auto rfind(const basic_cstring &other, size_type pos=npos) const noexcept{
      return view().rfind(other.view(), pos);
    }
    auto rfind(const_pointer str, size_type pos, size_type len) const {
      return view().rfind(sanitize(str), pos, len);
    }
    auto rfind(const_pointer str, size_type pos=npos) const {
      return view().rfind(sanitize(str), pos);
    }
    auto rfind(value_type c, size_type pos=npos) const noexcept {
      return view().rfind(c, pos);
    }

    //! Finds the first character equal to one of the given characters.
    auto find_first_of(const basic_cstring &other, size_type pos=0) const noexcept {
      return view().find_first_of(other.view(), pos);
    }
    auto find_first_of(const_pointer str, size_type pos, size_type len) const {
      return view().find_first_of(sanitize(str), pos, len);
    }
    auto find_first_of(const_pointer str, size_type pos=0) const {
      return view().find_first_of(sanitize(str), pos);
    }
    auto find_first_of(value_type c, size_type pos=0) const noexcept {
      return view().find_first_of(c, pos);
    }

    //! Finds the first character equal to none of the given characters.
    auto find_first_not_of(const basic_cstring &other, size_type pos=0) const noexcept {
      return view().find_first_not_of(other.view(), pos);
    }
    auto find_first_not_of(const_pointer str, size_type pos, size_type len) const {
      return view().find_first_not_of(sanitize(str), pos, len);
    }
    auto find_first_not_of(const_pointer str, size_type pos=0) const {
      return view().find_first_not_of(sanitize(str), pos);
    }
    auto find_first_not_of(value_type c, size_type pos=0) const noexcept {
      return view().find_first_not_of(c, pos);
    }

    //! Finds the last character equal to one of given characters.
    auto find_last_of(const basic_cstring &other, size_type pos=npos) const noexcept {
      return view().find_last_of(other.view(), pos);
    }
    auto find_last_of(const_pointer str, size_type pos, size_type len) const {
      return view().find_last_of(sanitize(str), pos, len);
    }
    auto find_last_of(const_pointer str, size_type pos=npos) const {
      return view().find_last_of(sanitize(str), pos);
    }
    auto find_last_of(value_type c, size_type pos=npos) const noexcept {
      return view().find_last_of(c, pos);
    }

    //! Finds the last character equal to none of the given characters.
    auto find_last_not_of(const basic_cstring &other, size_type pos=npos) const noexcept {
      return view().find_last_not_of(other.view(), pos);
    }
    auto find_last_not_of(const_pointer str, size_type pos, size_type len) const {
      return view().find_last_not_of(sanitize(str), pos, len);
    }
    auto find_last_not_of(const_pointer str, size_type pos=npos) const {
      return view().find_last_not_of(sanitize(str), pos);
    }
    auto find_last_not_of(value_type c, size_type pos=npos) const noexcept {
      return view().find_last_not_of(c, pos);
    }

    //! Checks if the string contains the given substring.
    bool contains(basic_cstring_view sv) const noexcept {
      return (view().find(sv) != npos);
    }
    bool contains(value_type c) const noexcept {
      return (find(c) != npos);
    }
    bool contains(const_pointer str) const noexcept {
      return (find(str) != npos);
    }

    //! Left trim spaces.
    basic_cstring_view ltrim() const {
      const_pointer ptr = mStr;
      while (std::isspace(*ptr)) ptr++;
      return basic_cstring_view(ptr);
    }

    //! Right trim spaces.
    basic_cstring_view rtrim() const {
      const_pointer ptr = mStr + length() - 1;
      while (ptr >= mStr && std::isspace(*ptr)) ptr--;
      ptr++;
      return basic_cstring_view(mStr, static_cast<size_type>(ptr - mStr));
    }

    //! Trim spaces.
    basic_cstring_view trim() const {
      const_pointer ptr1 = mStr;
      const_pointer ptr2 = mStr + length() - 1;
      while (std::isspace(*ptr1)) ptr1++;
      while (ptr2 >= ptr1 && std::isspace(*ptr2)) ptr2--;
      ptr2++;
      return basic_cstring_view(ptr1, static_cast<size_type>(ptr2 - ptr1));
    }

}; // namespace gto

//! Static variable declaration
template<typename Char, typename Traits, typename Allocator>
typename gto::basic_cstring<Char, Traits, Allocator>::allocator_type gto::basic_cstring<Char, Traits, Allocator>::alloc{};

//! Comparison operators (between basic_cstring)
template<typename Char, typename Traits, typename Allocator>
inline bool operator==(const basic_cstring<Char,Traits,Allocator> &lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (lhs.compare(rhs) == 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator!=(const basic_cstring<Char,Traits,Allocator> &lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (lhs.compare(rhs) != 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator<(const basic_cstring<Char,Traits,Allocator> &lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (lhs.compare(rhs) < 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator<=(const basic_cstring<Char,Traits,Allocator> &lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (lhs.compare(rhs) <= 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator>(const basic_cstring<Char,Traits,Allocator> &lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (lhs.compare(rhs) > 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator>=(const basic_cstring<Char,Traits,Allocator> &lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (lhs.compare(rhs) >= 0);
}

//! Comparison operators (between basic_cstring and Char*)
template<typename Char, typename Traits, typename Allocator>
inline bool operator==(const basic_cstring<Char,Traits,Allocator> &lhs, const Char *rhs) noexcept {
  return (lhs.compare(rhs) == 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator!=(const basic_cstring<Char,Traits,Allocator> &lhs, const Char *rhs) noexcept {
  return (lhs.compare(rhs) != 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator<(const basic_cstring<Char,Traits,Allocator> &lhs, const Char *rhs) noexcept {
  return (lhs.compare(rhs) < 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator<=(const basic_cstring<Char,Traits,Allocator> &lhs, const Char *rhs) noexcept {
  return (lhs.compare(rhs) <= 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator>(const basic_cstring<Char,Traits,Allocator> &lhs, const Char *rhs) noexcept {
  return (lhs.compare(rhs) > 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator>=(const basic_cstring<Char,Traits,Allocator> &lhs, const Char *rhs) noexcept {
  return (lhs.compare(rhs) >= 0);
}

//! Comparison operators (between Char * and basic_cstring)
template<typename Char, typename Traits, typename Allocator>
inline bool operator==(const Char *lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (rhs.compare(lhs) == 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator!=(const Char *lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (rhs.compare(lhs) != 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator<(const Char *lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (rhs.compare(lhs) > 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator<=(const Char *lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (rhs.compare(lhs) >= 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator>(const Char *lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (rhs.compare(lhs) < 0);
}
template<typename Char, typename Traits, typename Allocator>
inline bool operator>=(const Char *lhs, const basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  return (rhs.compare(lhs) <= 0);
}

// template incarnations
typedef basic_cstring<char> cstring;
typedef basic_cstring<wchar_t> wcstring;
typedef basic_cstring<char>::basic_cstring_view cstring_view;
typedef basic_cstring<wchar_t>::basic_cstring_view wcstring_view;

} // namespace gto

namespace std {

//! Specializes the std::swap algorithm for std::basic_cstring.
template<typename Char, typename Traits, typename Allocator>
inline void swap(gto::basic_cstring<Char,Traits,Allocator> &lhs, gto::basic_cstring<Char,Traits,Allocator> &rhs) noexcept {
  lhs.swap(rhs);
}

//! Performs stream output on basic_cstring.
template<typename Char, typename Traits, typename Allocator>
inline basic_ostream<Char,Traits> & operator<<(std::basic_ostream<Char,Traits> &os, const gto::basic_cstring<Char,Traits,Allocator> &str) {
  return operator<<(os, str.view());
}

//! The template specializations of std::hash for gto::cstring.
template<>
struct hash<gto::cstring> {
  std::size_t operator()(const gto::cstring &str) const {
    return hash<std::string_view>()(str.view());
  }
};

//! The template specializations of std::hash for gto::wcstring.
template<>
struct hash<gto::wcstring> {
  std::size_t operator()(const gto::wcstring &str) const {
    return hash<std::wstring_view>()(str.view());
  }
};

} // namespace std
```

Answer 1

In no particular order.

NUL-termination

The ASCII character with a value of 0 is the NUL character. C Strings are thus NUL-terminated strings. I would advise changing the comment 0-ended to NUL-terminated.

Public and Private API

The repeated switch between public and private declarations at the top of the class is fairly annoying. If possible, try to put first all public declarations (user API) and then all private ones. Worst comes to worst, an initial private section can be used.

The prefix_type and atomic_prefix_type have no reason to be public.

Size and Alignment assumptions

The memory layout you use makes a number of assumptions, for example that the alignment of Char is less than or equal to that of prefix_type, and that the size of prefix_type is equal to that of atomic_prefix_type.

Those are reasonable assumptions, but they ought to be checked.

You can add static_assert(alignof(Char) <= alignof(prefix_type)), etc... to validate (and document) each assumption that is made.

I recommend putting those static_assert where the assumptions are used, such as in the getPtrToCounter and getPtrToLength.

Do not worry about duplicated them. Any time an assumption is used, check the assumption. This allows locally reasoning that all assumptions are checked when reading the code.

Thread safety

Your use of atomics is correct, in fact it's even over the top.

By directly using = and ++/-- you are using the Sequentially Consistent memory ordering -- the strongest of all -- which is overkill here.

Since you have no synchronization with another piece of memory, you can instead use the Relaxed memory ordering.

Strict-aliasing woes.

Your definition of mEmpty violates strict-aliasing.

In general, you cannot store a value as type A, then read it as type B. An exception is made for char, signed char, unsigned char, and std::byte, but as your class is templated on Char you cannot rely on this -- and indeed it fails when used with wchar_t.

Instead, you should be defining a struct with the exact layout that you want:

struct EmptyString { atomic_prefix_type r; prefix_type s; value_type z; };

static constexpr EmptyString mEmpty = {};

Weird mix of case style

In order to present a STL-like interface, your public interface uses snake_case.

Yet, your private interface uses camelCase.

The dissonance is annoying for the reader. Pick one, stick to it.

Allocation and deallocation

The getAllocatedLength function could benefit from a comment explaining what is going on, because that's quite unclear. It may be clever maths, if so I'm missing it. The obvious formula would be: 2 * sizeof(prefix_type) / sizeof(value_type) + sizeof(value_type) * (len + 1).

In allocate, you never check that n > len. On 32-bits platforms, with len close to the maximum, the computation in getAllocatedLength will overflow. You should at least assert against that.

allocate and deallocate are asymmetric: allocate just allocates, whereas deallocate both decrements the counter and deallocates. It would be better for deallocate just to deallocate, and to have a decrementRefCounter function instead.

Documentation

Your documentation comments are mostly pointless, either get rid of them, or make them useful.

For example, //! Default constructor. is useless. I can see perfectly in the signature that this is the default constructor, thank you very much. At the same time, there's important information that's not conveyed: that the default-constructed string is empty.

The same holds true for //! Constructor (and co), they're just paraphrasing the signature without providing any useful information.

Good documentation comments should:

• Clearly indicate the functionality, even if obvious. operator[](size_type pos) returns a reference to the character at index pos, not just any character. empty returns whether the string is empty (not just "test" it...).
• Clearly indicate any pre-condition. The first //! Constructor requires that the string be NUL-terminated. operator[] requires that pos be within [0, length()] (and not [0, length())).
• Clearly indicate any post-condition. The //! Default Constructor returns an empty string.
• Clearly indicate what happens when a pre-condition is violated: is it undefined behavior? Is an exception thrown?

Examples:

//! Constructs an empty string.
basic_cstring() : basic_cstring(nullptr) {}

//! Returns a reference to the character at index `pos`.
//!
//! # Pre-conditions
//!
//! - `pos` must be in the `[0, length()]` range.
//!
//! # Undefined Behavior
//!
//! If `pos` is outside `length()`, Undefined Behavior occurs.
const_reference operator[](size_type pos) const { return mStr[pos]; }

Noexcept

Mark noexcept functions that cannot throw an exception, such as your default constructor, operator[], etc... Some of your functions are marked, but not all that could be.

If and else.

If an if block ends with return, there is no need for an else. This will save you one degree of indentation, and make it clearer to the reader.

Also, even when an if has a single statement in its block, do use {} around it.

Front and back.

Your front and back functions throw an out_of_range exception, which is not the case of std::basic_string. I do prefer throwing, although it may affect performance.

Performance hint: even though it's getting better, inline throw statements tend to bloat the code of the functions they appear in. It is better to manually outline them behind functions that are marked as no-inline, cold, and no-return.

Prefer non-member non-friend functions

I advise you to read Monolith Unstrung, though at the same time I do understand wanting to provide as close to std::string as possible an interface.

I do note, however, that in such cases you may want to delegate to std::string-view more often, rather than re-implement the functionality yourself.

Free-functions and ADL

Your operator== and friends are declared in the global namespace, instead of being declared in the gto namespace. For ADL to find them, they need to be in the namespace of one of their arguments.

(Might be a copy/paste mistake? As I see the namespace being closed a second time afterwards)

Specialization

It is better to specialize std algorithms in the global namespace, rather than open the std namespace. The namespace you are in affects name-lookup, and you may accidentally refer to a std entity.

Specialization IS NOT Overloading

The definitions of swap and operator<< are NOT specializations, they're overloading.

They should be in the gto namespace, instead.

TODO

With regard to your todo list:

• The assumption should be encoded as static_assert, then you can be sure it either holds, or that the user will get a compile-time error on their weird platform.
• __builtin_assume_aligned(...) may help indeed.
• std::atomic is enough, your use of it is even overkill.
• Atomic operations have two impacts on code:
  • They are slower than non-atomic operations in general, with a slight exception for pure reads/writes in non SeqCst mode on x86.
  • Writes imply cache invalidation on other cores.
• Beware that benchmarks lie ;)

Conclusion

A fairly nice read, you did a good job overall!

Answer 2

Possible memory leak

On the deallocate() method, counter is decremented in two phases. In the first phase you read the current counter value. In the second one you decrement the counter if it is bigger than 1. When two cstrings are deallocated simultaneously, then an ordering can occur such that both instances read 2 and then both instances decrement the counter resulting a final value of 0 and a memory leak.

This can be solved modifying the deallocate() function like this:

static void deallocate(const_pointer str) {
  atomic_prefix_type *ptr = getPtrToCounter(str);
  prefix_type counts = ptr[0];

  if (counts == 0) { // constant
    return;
  } else if (counts > 1) {
    counts = ptr[0]--;
  }

  if (counts == 1) {
    prefix_type len = *getPtrToLength(str);
    size_type n = getAllocatedLength(len);
    allocator_traits::destroy(alloc, ptr);
    allocator_traits::deallocate(alloc, reinterpret_cast<prefix_type *>(ptr), n);
  }
}

Address sanitizer fails

Running tests after compiling them with the -fsanitize=address option reports an error. This error is not directly attributable to cstring but can be removed by slightly modifying the sanitize() method.

static inline constexpr const_pointer sanitize(const_pointer str) {
  return ((str == nullptr || str[0] == value_type()) ? getPtrToString(mEmpty) : str);
}

Answer 3

Inherit from std::basic_string_view

A large part of your code is recreating the API of std::basic_string_view. Wouldn't it be nice if you could avoid all of that? Consider publicly inherting from std::basic_string_view, and you get all that for free!

With this, you no longer need mPtr, as a string view already contains a pointer to the string. The length is now also moved into your class, and is no longer needed in the allocated storage. For cstrings allocated on the stack this is actually preferrable; less heap memory is used and less indirection is needed to get to the length. There might be some overhead though if you have a std::vector<gto::cstring> and many of those strings are duplicates of each other, so this is a trade-off.

The only issue would be to delete any member functions that modify a string view, like remove_suffix() and remove_prefix(), although swap() is probably still safe.

Use std::size_t for sizes and counts

Using 32-bit integers might save you a tiny bit of memory on 64-bit platforms, but now you have to deal with the fact that the STL uses std::size_t for strings sizes and add additional checks, and at the same time you prevent large strings from being used. At the same time, on 16-bit platforms your code would store sizes in unnecessarily large integers. I would avoid all these issues and use std::size_t everywhere you have sizes, counts and indices.

Thread safety and memory alignment

It doesn't look very nice with all the pointer arithmetic and atomics, but I can't see anything wrong with it. I'm assuming it will never happen that Char is larger than two times the size of prefix_type.

Answer 4

Edit: Edited in response to comments. Original response remains unaltered (excepting some fixes), additional details added following original answer.

In addition to the notes made by others:

Structured Memory

You are imposing a structure on memory (as you note in your comments!), you should make this explicit by using a struct, for example:

struct storage_type {
    atomic_prefix_type mRef = 0;
    size_type mSize = 0;
    const value_type mStr[1] = { nullptr }; // I prefer this to const_pointer mStr, but either work
};
// …
storage_type* mStr{};
// …
using allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<storage_type>;
// …
static size_type getAllocatedLength(size_type len) {
      return (((len - 1) * sizeof(value_type)) / sizeof(storage_type)); // - 1 since one char in struct already
}

This provides a number of important advantages:

• makes the intent absolutely clear
• simplifies a lot of the code and (importantly) removes a lot of reinterpret_cast expressions
• ensures the alignment of types is optimal for the platform

(Note that this may allocate a few additional bytes each time, if this is an issue it is possible to avoid but requires more complex code.)

Alignment

Using a packed buffer (i.e. without padding between stored values) for data saves memory, but can cause poor performance if the types are not aligned correctly. If std::atomic<prefix_type> does not have the same alignment requirements as size_type (which may be true for 64-bit platforms) accessing the size will be slower than it needs to be. Compilers automatically pad structures and classes with unused bytes to ensure every member is aligned correctly for the hardware.

Again, using a structure as noted above fixes this.

Type choice

Although the “obvious” choice for a counter, std::uint32_t is not normally the right choice.

Firstly, unlike fixed width signed integral types fixed width unsigned integral types are optional and are only provided if the implementation supports them (and not all do).

Secondly, unsigned integral types are often second class citizens in hardware, even if it is not true for non-atomic operations, it is often true with atomic operations (and the differences can be relatively significant).

A general rule of thumb is that a signed integral type is normally the right choice, unless you know for certain you need the full range of an unsigned integral type.

Further, where atomic operations are concerned it is often better to use simply either int or long - these types are most likely to be mapped to the best hardware implementation regardless of platform, while specific sized types may artificially place restrictions on the performance of your algorithms. (Clearly the size of these types should be checked with static_assert to ensure they have sufficient range.)

A reference counted string_view

It seems like what you want is actually a reference counted string_view that owns the data it views. At the cost of a few bytes this can be achieved more easily, with potentially better performance in all cases, and without needing much of the complicated code you have now by simply storing a string_view:

struct storage_type {
    atomic_prefix_type mRef = 0;
    const value_type mStr[1] = { nullptr }; // I prefer this to const_pointer mStr, but either works
};
// …
basic_cstring_view mView{};
storage_type mStr{};
// …
basic_cstring(const_pointer str, size_type len) {
    if (str == nullptr || len == 0) { return; }
    mStr = allocate(len);
    traits_type::copy(mStr.mStr, str, len);
    mView = { mStr.mStr, len };
}

(This code is a little simplified to highlight the basic idea.)

With a little pointer arithmetic it would actually be possible to use the pointer in string_view as your data pointer, removing the need to store an additional pointer.

Types

Finally, the type definitions are not ideal, the names are often confusing also it is generally better to delegate definitions to other types if those types are to be used extensively. Additionally it is a good idea to include all types the standard container uses as it will better ensure compatibility with other templated entities. For example:

// using prefix_type
using counter_underlying_type = std::uint32_t; // Better says what it is
// using atomic_prefix_type
using counter_type = std::atomic<prefix_type>; // Likewise

using allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<counter_underlying_type>; 
using allocator_traits_type = std::allocator_traits<allocator_type>; // Avoids potential clash with std::allocator_traits if someone does something silly

// using basic_cstring_view = std::basic_string_view<value_type, traits_type>;
using view_type = std::basic_string_view<Char, Traits>;

// Delegated Types
using traits_type = typename view_type::traits_type; 
using value_type = typename view_type::value_type; 
using pointer = typename view_type::pointer;
using const_pointer = typename view_type::const_pointer;
using reference = typename view_type::reference;
using const_reference = typename view_type::const_reference;
using const_iterator = typename view_type::const_iterator;
using iterator = typename view_type::iterator;
using const_reverse_iterator = typename view_type::const_reverse_iterator;
using reverse_iterator = typename view_type::reverse_iterator;

// These should use std::common_type_t to ensure the correct type is used
using size_type = std::common_type_t<typename view_type::size_type, typename allocator_traits_type::size_type>;
using difference_type = std::common_type_t<typename view_type::difference_type, typename allocator_traits_type::difference_type>;

//using pointer = typename std::allocator_traits<Allocator>::pointer;
using data_pointer = typename allocator_traits_type::pointer;

---

Edit:

Ah! It appears the code in your question is not the same as the code on github (understandable given this is an older question) and I see that you have made changes that cause some of my comments to be less relevant - sorry for missing that. I standby most of the comments made for the posted code so I am leaving it unedited above, with the exception I missed a pointer in my initial code, which drastically alters the meaning. I have fixed that.

To address the comments:

The data structure (counter + length + content) is not stored directly within the object, as your initial comment suggests.Instead, it is stored in the heap memory. This data structure is accessed using the pointer mStr stored within the cstring object (the size of cstring is 8 bytes). This pointer points to the string content, not at the beginning of the data structure, enabling the use of the cstring object much like a char pointer. This requires using reinterpret_cast to access the length and counter.

I did not mean to suggest “counter + length + content” is stored directly in the object, sorry that I did make this clear. Part of the confusion here is because I missed a pointer in my code, which I have now fixed. Additionally I was trying to limit somewhat the length of my response and this may also have caused confusion.

To be clear reinterpret_cast will always be necessary for this type of code. However, it is possible to reduce how often it is required, while also making the code more robust and easier to follow:

template<typename Char,
    typename Traits = std::char_traits<Char>,
    typename Allocator = std::allocator<Char>>
class basic_cstring {
private:
    using prefix_type = std::uint32_t;
    using atomic_prefix_type = std::atomic<prefix_type>;

    struct storage_type {
        storage_type(prefix_type len) : 
            mSize{ len } {}

        atomic_prefix_type mRef = 1;
        const prefix_type mSize = 0;
        const Char mStr[1] = { Char{} };
    };

public:
    using value_type = Char;
    using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;

    using allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<storage_type>;
    using allocator_traits = std::allocator_traits<allocator_type>;

    using size_type = typename std::allocator_traits<Allocator>::size_type;

    static allocator_type mAllocator;

    static storage_type* getData(const value_type* str) noexcept {
        const auto* raw = reinterpret_cast<std::byte*>(str); // cast to std::byte not strictly required (could simply use char)
        return reinterpret_cast<storage_type*>(raw - offsetof(storage_type, mStr));
    }

    static const value_type* getStr(storage_type* ptr) noexcept {
        const auto* raw = reinterpret_cast<std::byte*>(ptr); // cast to std::byte not strictly required (could simply use char)
        return reinterpret_cast<const value_type*>(raw + offsetof(storage_type, mStr));
    }

    static storage_type* getAllocCount(size_type len) {
        return (sizeof(storage_type) + ((len - 1) * sizeof(Char))) / sizeof(storage_type);
    }

    static storage_type* allocate(size_type len) {
        auto* ptr = allocator_traits::allocate(mAllocator, getAllocCount(len));
        allocator_traits::construct(mAllocator, ptr, len);
        return ptr;
    }

    static void deallocate(const value_type* str) noexcept {
        const auto* ptr = getData(str);
        ptr->~storage_type();
        allocator_traits::deallocate(mAllocator, ptr, getAllocCount(ptr.mSize));
    }

    basic_cstring(const value_type str, size_type len) {
        auto* ptr = allocate(len);
        ptr.mSize = len;
        traits_type::copy(ptr.mStr, str, len);
        mStorage = getStr(ptr);
    }

    const value_type* mStorage = nullptr;
};

Although I have omitted a great many details, hopefully that makes what I was trying to explain more clear.

This does not change the size of the class, but provides some benefits, including:

• easier to understand
• more robust (immune to errors caused by type sizes, for example)
• reinterpret_cast only needed in two places

(1) Suggested storage_type is essentially an EmptyCString

Indeed it is!

(2) Correct alignment is ensured because the length and counter have the same type, and this type has a size greater than or equal to Char (see the static asserts in the code).

Yes, I see you have changed the type used for length, however you are now mixing the use of size_type and prefix_type for something that is supposed to represent the same value - it’s highly confusing to try to understand what’s going on. Additionally you are now likely to be causing unnecessary type promotion when switching between the two types if any of the size_type types are of different (notably, with any implementation with a std::size_t that is not 32-bits this will occur every time a view is constructed, which is frequently).

Generally however the defined types are confusing and poorly defined. For example, the definition of const_pointer is delegated to the allocator, but value_type is not, you use basic_string_view extensively, but none of the return values from delegated functions are types taken from basic_string_view, you define allocator_traits as the traits for the rebound allocator and then use std::allocator_traits<Allocator> to define any delegated types (while this makes sense, it is confusing because of the name), etc.

(3) You have the freedom to change the type used as prefix_type (e.g., long, int, int32_t, etc.). std::uint32_t was chosen because the string prefix occupies 8 bytes on x86-64 architecture.

If this is intended to be changed by users it should be templated. The point I was making, however, was that for portability unless you know for certain that you need the extra range, then signed types are a better choice, specifically int or long, as for some platforms alternative types are less optimal. If you look at the code of many implementations of reference counters they use these types (e.g. Chromium)

(4) Adding a string_view to the object would increase the object's size by 16 bytes, effectively tripling its current size. I had not appreciated the size of the type was a primary design goal; a contained view was a performance improvement at the cost of space, so clearly not applicable.

I hope that makes what I was trying to say more clear. Apologies again for the errors!