Lightweight read-only string implementation (C++)

Question

In C++, currently we have few possibilities to work with strings:

1. by using plain old C-strings - unfortunately, we have penalty for getting length of string each time, and we should manually control life time of array, which actually contains data...

2. we can use std::string, but again, unfortunately this is not very efficient class: it's relatively large (32 bytes on 64-bit platform) and it always copies data;

3. modern C++ gives new opportunity: std::string_view class, which is quite effective, but unfortunately it doesn't own strings, on which it references: again we should control life time of the containers in which strings really stored.

In Java or C# we have more reasonable solution, when class implementing strings divided on two:

• StringBuilder which behaves like std::string and can be used to construct and edit strings;

• String which is lightweight and always read-only, and can be used to access previously created strings -- this class can be stored in arrays, passed in functions, etc...

I think, same solution might be perfect for C++, but this requires lot of work...

I want to present solution, which behaves like string in C# (in sense, that it is read-only and only can be created and reassigned). No counterpart, like StringBuffer was created, but my solution has very basic functions to create new strings.

I want to see some comments about my solution and suggestions how can I improve it.

Basic requirements when I design my own string-class implementation was following:

• it should be very lightweight;

• copying and passing by value should be almost free;

• multiple instances of same string should share its representation (and memory);

• strings cant be created from string literals and shouldn't require memory allocation or copying in that case;

• strings should be freely convertible to/from std::string_view class.

You can see the code on Coliru.

#include <new>
#include <string_view>
#include <atomic>
#include <stdexcept>
#include <stdarg.h>

// Some implementation of class similar to `string_view' should be available in global namespace
// (CString class requires this)
using std::string_view;


// Class `CString' implements lightweight constant read-only string suitable
// for storing in arrays, for passing by value, etc...
//
// Main essential properties of `CString' class are following:
//
//    * it has extremelly small size (1 pointer);
//
//    * copying (and passing by value) is almost free of cost;
//
//    * multiple instances of CString can share internal representation;
//
//    * if CString created from string literal it doesn't require
//      neither memory allocation, nor data copying (so constant strings
//      are really weightless).
//
// Some negative properties:
//
//    * size of stored string limited to 65536 bytes;
//
//    * nul-symbol can't be stored inside string;
//
//    * program can crash in runtime when constructing CString from string literal,
//      if .rodata segment is larger than 8 MBytes (this is limit for 32-bit platform,
//      for 64-bit platform limit is hardly noticeable);
//
//    * computing string size, when string was created from string literal and size
//      is larger than 128 bytes, isn't performed in constant time: for each next
//      128 bytes small additional penalty added (so computing size of large string
//      created from string literals isn't free).
//
// This class can be modified, it represents only read-only strings, and can be
// created in one of the following ways:
//
//    1) from literal string: CString text("some text...");
//
//    2) from `string_view' and from const char* (implicitly, via string_view);
//
//    3) as result of calling static printf-like functions `printf' and `vprintf';
//
//    4) as result of concatenation of any string-like objects convertible to string_view,
//       via static concat(...) function;
//
//    5) as result of calling constructor with specifying desired string size and
//       initializer function, which then creates string contents.
//
// CString class supports following operations:
//
//    * strings can be reassigned (but not modified);
//
//    * conversion to C-string or string_view (CString always stores zero-terminated
//      representation of the string, nul-symbol can't be stored in the string);
//
//    * size of the string computed in constant time for most practical cases (see note above);
//
//    * characters can be accessed by index (implemented operator[]).
//
class CString
{
public:
    typedef unsigned short size_type;  // first major limit: string sizes

private:
    // This structure contains shared representation of the string, when string 
    // is stored in allocated memory.
    struct Shared
    {
        std::atomic<unsigned short> count;  // second major limit: the number of shared copies
        const size_type  size;              // size of the string (not including terminating zero)
        char             data[1];

        Shared(size_type size) : count{1}, size{size} {}
    };

    // This constant determines how many bits of variable `ptr' used for storing offset
    // from `Base' to string literal, and how many bits used for encoding string literal length.
    // Actually for string length ConstSizeBits-1 bits used (only lower bits of the length are
    // stored, upper bits restored in runtime).
    constexpr static const unsigned ConstSizeBits = 8;

    // Address of this variable used to compute offset in .rodata segment, for storing string literals.
    static const char Base[1];

    // this variable might contain one of the three variants:
    //     1) nullptr -- when CString contains empty string;
    //     2) pointer to struct Shared -- when CString holds string in allocated memory;
    //     3) offset between `Base' and string literal (offset in .rodata segment)
    //        combined with lowest 7 bits of string length.
    intptr_t ptr;

    // returns `true' if current instance of CString stores string literal.
    bool is_const() const noexcept        { return ptr & 1; }

    Shared *get_shared() const noexcept   { return reinterpret_cast<Shared*>(ptr); }

    // returns string literal address from offset stored in `ptr'
    const char* const_data() const noexcept
    {
        intptr_t offset = ptr >> ConstSizeBits;
        return reinterpret_cast<const char*>(offset + Base);
    }

    // function called in case, when offset can't be encoded in `ptr' (when offset is too large)
    __attribute__((noreturn, noinline))
    void runtime_error(const char *msg) const
    {
        throw std::runtime_error(msg);
    }

public:
    // create empty string (no memory allocation)
    CString() noexcept : ptr{0} {}

    // create string with specified size and initialize it by given functior (memory allocated)
    template <typename Initializer> CString(size_t size, Initializer init)
    {
        if (!size) new (this) CString;
        else {
            if (size > size_type(-1))
                runtime_error("CString overflow");

            Shared *shared = static_cast<Shared*>(operator new(size + sizeof(Shared)));
            new (shared) Shared(size_type(size));
            init(shared->data);
            shared->data[size] = 0;
            ptr = intptr_t(shared);
        }
    }

    // create string from string_view class (memory allocated and string copy created)
    explicit CString(string_view str)
    {
        new (this) CString(str.size(), [&str](char *data){ str.copy(data, str.size()); });
    }

    // Note: constructor like CString(const char *str) and operator= with same argument
    // not implemented intentionally -- string should be created or assigned via intermediate
    // string_view class. Existence of constructor or assigne operator with "const char *"
    // argument prevents implementation of constructor or assign operators wich works with
    // string literals (see below).

    // create constant string from string literal (i.e. CString const_string("text")...)
    // memory will not be allocated, instead size and pointer  will be saved (as offset from Base symbol)
    template <size_t Size>
    constexpr explicit CString(const char (&literal)[Size])
    {
        if (!Size) new (this) CString;
        else {         
            // compute offset from `Base'
            const intptr_t offset = literal - Base;
            const intptr_t MaxOffset = uintptr_t(-1) >> (ConstSizeBits + 1);
            const intptr_t MinOffset = uintptr_t(-1) << (sizeof(intptr_t)*8 - ConstSizeBits);
            if (offset > MaxOffset || offset < MinOffset)
                runtime_error("CString offset in too large");

            // compute low bits of size
            constexpr size_t size = Size - 1;  // don't count terminating zero
            constexpr uintptr_t short_size = size & ((1<<(ConstSizeBits - 1)) - 1);

            // combine result
            ptr = offset << ConstSizeBits | (short_size<<1) | 1;
        }
    }

    // create copy of the string (by increasing reference count)
    CString(const CString& other) noexcept : ptr{other.ptr}
    {
        if (ptr) {
            if (! is_const())
                get_shared()->count++;
        }
    }

    // move constructor just makes string empty
    CString(CString&& other) noexcept : ptr{other.ptr} { other.ptr = 0; }


    ~CString()
    {
        if (ptr && !is_const())
        {
            // free memory only in case if CString holds string in allocated memory
            Shared *shared = get_shared();
            if (--shared->count == 0)
                operator delete(shared);
        }
    }

    // These functions used to create CString as result of calling printf-like function...
    static CString vprintf(const char *fmt, va_list args);
    static CString printf(const char *fmt, ...);

    // Create CString as result of concatenation of given arguments
    // (all shold be convertible to string_view).
    template <typename... Args>
    static CString concat(Args&&... args)
    {
            string_view parts[] = { args... };
            size_t len = 0;
            for (const string_view& s : parts)
                len += s.size();

            return CString(len, [&parts](char *data){
                            for(const string_view& s : parts)
                                data += s.copy(data, s.size());
                        });
    }

    // Assign new value.
    CString& operator=(const CString& other)
    {
            this->~CString();
            return *new (this) CString(other);
    }

    // This function also handles case, when assigning "const char*" to CString,
    // see comment in CString(string_view) above.
    CString operator=(string_view str)
    {
        this->~CString();
        return *new (this) CString(str);
    }

    // Assign string literal.
    template <size_t Size> CString& operator=(const char (&literal)[Size])
    {
        this->~CString();
        return *new (this) CString(literal);
    }

    // Get zero-terminated C-string representation.
    const char *c_str() const noexcept
    {
        if (! ptr)  // empty string (returns pointer to nul-symbol)
        {
            return reinterpret_cast<const char*>(&ptr);
        }
        else if (! is_const())  // data in allocated memory
        {
            return get_shared()->data;
        }
        else {
            return const_data(); // return string literal
        }
    }

    // Return size of the stored string.
    size_t size() const noexcept
    {
        if (! ptr)  // empty string
        {
            return 0;
        }
        else if (! is_const())  // data in allocated memory
        {
            return get_shared()->size;
        }
        else {
            // decode `ptr' to lowest bits of string size and offset
            const uintptr_t short_size = (ptr & ((1<<ConstSizeBits) - 1)) >> 1;
            const char *start = const_data();
            // start searching end of string
            const char *end = &start[short_size];
            while (*end) end += 1<<(ConstSizeBits - 1);
            // compute length
            return end - start;
        }
    }

    // return `true' if CString is empty
    bool empty() const noexcept { return !ptr; }

    // access particular character by index
    const char& operator[](int i) const noexcept { return c_str()[i]; }

    // conversion to string_view
    operator string_view() const noexcept { return string_view(c_str(), size()); }
};

// these functions allow CString comparison with string_view or string literals
template <typename T> bool operator==(const CString& s, T other) { return static_cast<string_view>(s) == static_cast<string_view>(other); }
template <typename T> bool operator!=(const CString& s, T other) { return static_cast<string_view>(s) != static_cast<string_view>(other); }
template <typename T> bool operator<(const CString& s, T other)  { return static_cast<string_view>(s) < static_cast<string_view>(other); }
template <typename T> bool operator>(const CString& s, T other)  { return static_cast<string_view>(s) > static_cast<string_view>(other); }
template <typename T> bool operator<=(const CString& s, T other) { return static_cast<string_view>(s) <= static_cast<string_view>(other); }
template <typename T> bool operator>=(const CString& s, T other) { return static_cast<string_view>(s) >= static_cast<string_view>(other); }

template <typename T> bool operator==(T other, const CString& s) { return static_cast<string_view>(other) == static_cast<string_view>(s); }
template <typename T> bool operator!=(T other, const CString& s) { return static_cast<string_view>(other) != static_cast<string_view>(s); }
template <typename T> bool operator<(T other, const CString& s)  { return static_cast<string_view>(other) < static_cast<string_view>(s); }
template <typename T> bool operator>(T other, const CString& s)  { return static_cast<string_view>(other) > static_cast<string_view>(s); }
template <typename T> bool operator<=(T other, const CString& s) { return static_cast<string_view>(other) <= static_cast<string_view>(s); }
template <typename T> bool operator>=(T other, const CString& s) { return static_cast<string_view>(other) >= static_cast<string_view>(s); }

bool operator==(const CString& s, const CString& other) { return static_cast<string_view>(s) == static_cast<string_view>(other); }
bool operator!=(const CString& s, const CString& other) { return static_cast<string_view>(s) != static_cast<string_view>(other); }
bool operator<(const CString& s, const CString& other)  { return static_cast<string_view>(s) < static_cast<string_view>(other); }
bool operator>(const CString& s, const CString& other)  { return static_cast<string_view>(s) > static_cast<string_view>(other); }
bool operator<=(const CString& s, const CString& other) { return static_cast<string_view>(s) <= static_cast<string_view>(other); }
bool operator>=(const CString& s, const CString& other) { return static_cast<string_view>(s) >= static_cast<string_view>(other); }


////////////////////////////// CString.cpp file //////////////////////////////////////

#include <stdio.h>

const char CString::Base[1] = "";

CString CString::vprintf(const char *fmt, va_list args)
{
    int len = vsnprintf(NULL, 0, fmt, args);
    if (len <= 0) return CString(string_view());
    return CString(len, [&](char *data){ vsnprintf(data, len + 1, fmt, args); });
}

CString CString::printf(const char *fmt, ...)
{
    va_list args;
    va_start(args, fmt);
    CString result = CString::vprintf(fmt, args);
    va_end(args);
    return result;
}


/////////////////////// Usage examples ////////////////////////////////////////////////

int main()
{
    // create CString from literal
    CString lit("1234");

    // create CString by contatenating multiple strings
    string_view sv = "ccc";
    CString a = CString::concat("a", "bb", sv, lit);

    // create CString by using printf-function
    CString b = CString::printf("%d %s %d %s\n", int(lit.size()), lit.c_str(), a.size(), a.c_str());

    // comparing CStrings
    a == b;
    a < b;
    b >= a;
    a == "xxx";
    "yyy" != b;
    a == sv;
    sv != b;

    string_view(a).data();

    return 0;
}

Answer 1

All assignment operators contain the same bug - not checking for self assignment. This bug will lead to undefined behavior, or a SEGFAULT.