strings.hpp

strings.hpp

#include <atomic>
#include <cstdlib>
#include <vector>
#include <stdlib.h>

//#define PRINT(...) printf(__VA_ARGS__)
#define PRINT(...)

/*
so you can get mutable slices to edit a string, const slices when the string can't be edited, and strings can be composed from strings, or stringslices.
I might go so far as to say strings are immutable, unless they have a mutable slice, and mutable slices have a lock so there can only ever be one, and the string is immortal until all slices are retired (edited) 
so a string can have one mutable slice outstanding, or any number of immutable slices.
*/

struct Allocator
{
    template <typename CharType>
    CharType* alloc(int count) {
        return (CharType*) malloc(count);
    }

    template <typename CharType>
    void free(CharType* p) {
        ::free(p);
    }
};

template <typename CharType>
struct StringSlice
{
protected:
    CharType* _begin = nullptr;
    CharType* _end = nullptr;

public:
    struct iterator {
        CharType* _curr;
        StringSlice& _slice;

        iterator& operator++() {
            if (_curr < _slice.end()) {
                ++_curr;
            }
            return *this;
        }
    };

    CharType* begin() { return { _begin }; }
    CharType* end() { return { _end }; }

    int length() const {
        if (_end < _begin)
            return 0;
        return _end - _begin;
    }
};

template <typename CharType>
struct String
{
    CharType* _intern = nullptr;
    ptrdiff_t _len = 0;
    Allocator* _alloc = nullptr;

    typedef StringSlice<CharType> StringSlice;
    struct MutableLock {
        std::atomic<int> _count;
        String& _str;
        explicit MutableLock(String& str) : _str(str) {
            _count = 0;
        }
        bool try_lock()
        {
            int curr = 0;
            int next = 1;
            return _count.compare_exchange_weak(curr, next, std::memory_order_release, std::memory_order_relaxed);
        }
        bool try_release()
        {
            int released = _count.exchange(0);
            return released != 0;
        }
        int likely_count() const { return _count; }
    };

    struct ConstLock {
        std::atomic<int> _count;
        String& _str;
        explicit ConstLock(String& str) : _str(str) {
            _count = 0;
        }
        bool try_lock()
        {
            int curr = _count;
            int next = curr + 1;
            // returns true if curr was incremented.
            // if not, it means that some other thread acquired a lock.
            return _count.compare_exchange_weak(curr, next, std::memory_order_release, std::memory_order_relaxed);
        }
        bool try_release()
        {
            int curr = _count;
            if (curr <= 0)
                return false;

            int next = curr - 1;
            // returns true if curr was decremented.
            // if not, it means that some other thread acquired a lock.
            return _count.compare_exchange_weak(curr, next, std::memory_order_release, std::memory_order_relaxed);
        }
        int likely_count() const { return _count; }
    };

    MutableLock _mutableLock;
    ConstLock _constLock;

    bool try_const_lock()
    {
        // can't acquire a const lock if the mutable lock is held
        if (!_mutableLock.try_lock())
            return false;
        
        // attempt to get the const lock, release the mutable lock if it failed
        if (!_constLock.try_lock())
        {
            _mutableLock.try_release(); // always succeeds
            return false;
        }

        // release the mutable lock, leaving the const lock
        _mutableLock.try_release(); // always succeeds
        return true;
    }

    bool try_const_release()
    {
        if (!_mutableLock.try_lock())
            return false;

        bool ret = _constLock.try_release();
        _mutableLock.try_release(); // always succeeds
        return ret;
    }

    bool try_mutable_lock()
    {
        return _mutableLock.try_lock();
    }

    bool try_mutable_release()
    {
        return _mutableLock.try_release();
    }

    explicit String(char const*const str, Allocator& alloc)
    : _mutableLock(*this)
    , _constLock(*this)
    , _alloc(&alloc)
    {
        _len = strlen(str);
        _intern = alloc.alloc<CharType>(_len + 1);
        memcpy(_intern, str, _len);
        _intern[_len] = '\0';
    }

    ~String() {
        if (_alloc && _intern)
            _alloc->free<CharType>(_intern);
    }

    Allocator& allocator() const { return _alloc; }

    explicit String(String&&) = default;
    explicit String(const String&, Allocator&);
    explicit String(const StringSlice&, Allocator&);

    template <typename Iter>
    explicit String(Iter begin, Iter end, Allocator& alloc)
    : _mutableLock(*this)
    , _constLock(*this)
    , _alloc(&alloc)
    , _len(0)
    {
        for (Iter i = begin; i != end; ++i)
        {
            _len += i->length();
        }
        _intern = alloc.alloc<CharType>(_len + 1);
        CharType* curr = _intern;
        for (Iter i = begin; i != end; ++i)
        {
            memcpy(curr, i->begin(), i->length());
            curr += i->length();
        }
        _intern[_len] = '\0';        
    }

    CharType * begin() { return _intern; }
    CharType * end() { return _intern + _len; }
};

template <typename CharType>
struct MutableStringSlice : public StringSlice<CharType>
{
private:
    typename String<CharType>::MutableLock _lock;

public:
    explicit MutableStringSlice() = default;
    explicit MutableStringSlice(MutableStringSlice&&) = default;
    CharType operator[](int index);

    CharType* ptr(int index);

    bool try_lock(String<CharType>& s)
    {
        if (!s.try_mutable_lock())
            return false;

        this->_begin = s.begin();
        this->_end = s.end();
        return true;
    }
};

template <typename CharType>
struct ConstStringSlice : public StringSlice<CharType>
{
    String<CharType>* _str = nullptr;

public:
    explicit ConstStringSlice() : StringSlice<CharType>() {
        PRINT("empty slice\n");
    }
    explicit ConstStringSlice(const ConstStringSlice& s)
    {
        PRINT("copied %s\n", s._str->begin());
        while (s._str && !s._str->try_const_lock()) {}
        this->_str = s._str;
        this->_begin = s._begin;
        this->_end = s._end;
    }

    explicit ConstStringSlice(ConstStringSlice&& s)
    {
        PRINT("YO DAWG\n");
        this->_str = std::move(s._str);
        this->_begin = s._begin;
        this->_end = s._end;
    }

    ~ConstStringSlice()
    {
        PRINT("dealloc slice %s\n", _str->begin());
        if (this->_str != nullptr)
            while (!this->_str->try_const_release()) {}
        PRINT("dealloc'd slice\n");
    }

    ConstStringSlice& operator=(const ConstStringSlice& s)
    {
        PRINT("=constcopied %s\n", s._str->begin());
        while (s._str && !s._str->try_const_lock()) {}
        this->_str = s._str;
        this->_begin = s._begin;
        this->_end = s._end;
    }
    ConstStringSlice& operator=(ConstStringSlice& s)
    {
        PRINT("=copied %s\n", s._str->begin());
        while (s._str && !s._str->try_const_lock()) {}
        this->_str = s._str;
        this->_begin = s._begin;
        this->_end = s._end;
    }

    ConstStringSlice& operator=(ConstStringSlice&&) = delete;

    CharType operator[](int index);


    bool try_lock(String<CharType>& s)
    {
        PRINT("A\n");
        if (!s.try_const_lock())
            return false;
        PRINT("B\n");

        this->_str = &s;
        this->_begin = s.begin();
        this->_end = s.end();
        PRINT("C\n");
        return true;
    }

    bool try_lock(String<CharType>& s, int first, int count)
    {
        if (!s.try_const_lock())
            return false;

        this->_str = &s;
        this->_begin = s.begin() + first;
        this->_end = s.end() + first + count;
        return true;
    }
};

int main(int argc, char** argv)
{
    Allocator alloc;
    {
        String<char> test("test", alloc);
        PRINT("a\n");
        printf("String1 is %s\n", test.begin());
        PRINT("b\n");

        ConstStringSlice<char> s1;
        PRINT("c\n");
        if (!s1.try_lock(test)) {
            printf("test string not locked\n");
            return 0;
        }
        
        String<char> n123("123", alloc);
        printf("String2 is %s\n", n123.begin());

        ConstStringSlice<char> s2;
        if (!s2.try_lock(n123)) {
            printf("n123 string not locked\n");
            return 0;
        }

        std::vector<ConstStringSlice<char> > slices;
        PRINT("X\n");
        slices.push_back(s1);
        PRINT("Y\n");
        slices.push_back(s2);
        PRINT("Z\n");
        slices.push_back(s2);
        PRINT("W\n");

        String<char> cat(slices.begin(), slices.end(), alloc);
        printf("Concatenated string is %s\n", cat.begin());
    }
    return 1;
}