flex_string.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

    SmallStringOpt(size_type len, value_type c, const allocator_type& a)
    {
        if (len <= maxSmallString)
        {
            flex_string_details::pod_fill(buf_, buf_ + len, c);
            buf_[maxSmallString] = value_type(maxSmallString - len);
        }
        else
        {
            new(buf_) Storage(len, c, a);
            buf_[maxSmallString] = magic;
        }
    }
    
    SmallStringOpt& operator=(const SmallStringOpt& rhs)
    {
        reserve(rhs.size());
        resize(0, 0);
        append(rhs.data(), rhs.size());
        return *this;
    }

    ~SmallStringOpt()
    {
        if (!Small()) GetStorage().~Storage();
    }

    iterator begin()
    {
        if (Small()) return buf_;
        return &*GetStorage().begin(); 
    }
    
    const_iterator begin() const
    {
        if (Small()) return buf_;
        return &*GetStorage().begin(); 
    }
    
    iterator end()
    {
        if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
        return &*GetStorage().end(); 
    }
    
    const_iterator end() const
    {
        if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
        return &*GetStorage().end(); 
    }
    
    size_type size() const
    {
        BOOST_ASSERT(!Small() || maxSmallString >= buf_[maxSmallString]);
        return Small() 
            ? maxSmallString - buf_[maxSmallString] 
            : GetStorage().size();
    }

    size_type max_size() const
    { return get_allocator().max_size(); }

    size_type capacity() const
    { return Small() ? maxSmallString : GetStorage().capacity(); }

    void reserve(size_type res_arg)
    {
        if (Small())
        {
            if (res_arg <= maxSmallString) return;
            SmallStringOpt temp(*this);
            this->~SmallStringOpt();
            new(buf_) Storage(temp.data(), temp.size(), 
                temp.get_allocator());
            buf_[maxSmallString] = magic;
            GetStorage().reserve(res_arg);
        }
        else
        {
            GetStorage().reserve(res_arg);
        }
        BOOST_ASSERT(capacity() >= res_arg);
    }
    
    void append(const value_type* s, size_type sz)
    {
        if (!Small())
        {
            GetStorage().append(s, sz);
        }
        else
        {
            // append to a small string
            const size_type neededCapacity = 
                maxSmallString - buf_[maxSmallString] + sz;

            if (maxSmallString < neededCapacity)
            {
                // need to change storage strategy
                allocator_type alloc;
                Storage temp(alloc);
                temp.reserve(neededCapacity);
                temp.append(buf_, maxSmallString - buf_[maxSmallString]);
                temp.append(s, sz);
                buf_[maxSmallString] = magic;
                new(buf_) Storage(temp.get_allocator());
                GetStorage().swap(temp);
            }
            else
            {
                flex_string_details::pod_move(s, s + sz, 
                    buf_ + maxSmallString - buf_[maxSmallString]);
                buf_[maxSmallString] -= value_type(sz);
            }
        }
    }
    
    template <class InputIterator>
    void append(InputIterator b, InputIterator e)
    {
        // @@@ todo: optimize this depending on iterator type
        for (; b != e; ++b)
        {
            *this += *b;
        }
    }

    void resize(size_type n, value_type c)
    {
        if (Small())
        {
            if (n > maxSmallString)
            {
                // Small string resized to big string
                SmallStringOpt temp(*this); // can't throw
                // 11-17-2001: correct exception safety bug
                Storage newString(temp.data(), temp.size(), 
                    temp.get_allocator());
                newString.resize(n, c);
                // We make the reasonable assumption that an empty Storage
                //     constructor won't throw
                this->~SmallStringOpt();
                new(&buf_[0]) Storage(temp.get_allocator());
                buf_[maxSmallString] = value_type(magic);
                GetStorage().swap(newString);
            }
            else
            {
                // Small string resized to small string
                // 11-17-2001: bug fix: terminating zero not copied
                size_type toFill = n > size() ? n - size() : 0;
                flex_string_details::pod_fill(end(), end() + toFill, c);
                buf_[maxSmallString] = value_type(maxSmallString - n);
            }
        }
        else
        {
            if (n > maxSmallString)
            {
                // Big string resized to big string
                GetStorage().resize(n, c);
            }
            else
            {
                // Big string resized to small string
                // 11-17=2001: bug fix in the BOOST_ASSERTion below
                BOOST_ASSERT(capacity() > n);
                SmallStringOpt newObj(data(), n, get_allocator());
                newObj.swap(*this);
            }
        }
    }

    void swap(SmallStringOpt& rhs)
    {
        if (Small())
        {
            if (rhs.Small())
            {
                // Small swapped with small
                std::swap_ranges(buf_, buf_ + maxSmallString + 1, 
                    rhs.buf_);
            }
            else
            {
                // Small swapped with big
                // Make a copy of myself - can't throw
                SmallStringOpt temp(*this);
                // Nuke myself
                this->~SmallStringOpt();
                // Make an empty storage for myself (likely won't throw)
                new(buf_) Storage(0, value_type(), rhs.get_allocator());
                buf_[maxSmallString] = magic;
                // Recurse to this same function
                swap(rhs);
                // Nuke rhs
                rhs.~SmallStringOpt();
                // Build the new small string into rhs
                new(&rhs) SmallStringOpt(temp);
            }
        }
        else
        {
            if (rhs.Small())
            {
                // Big swapped with small
                // Already implemented, recurse with reversed args
                rhs.swap(*this);
            }
            else
            {
                // Big swapped with big
                GetStorage().swap(rhs.GetStorage());
            }
        }
    }
    
    const value_type* c_str() const
    { 
        if (!Small()) return GetStorage().c_str(); 
        buf_[maxSmallString - buf_[maxSmallString]] = value_type();
        return buf_;
    }

    const value_type* data() const
    { return Small() ? buf_ : GetStorage().data(); }
    
    allocator_type get_allocator() const
    { return allocator_type(); }
};

////////////////////////////////////////////////////////////////////////////////
// class template CowString
// Implements Copy on Write over any storage
////////////////////////////////////////////////////////////////////////////////

template <
    typename Storage, 
    typename Align = BOOST_DEDUCED_TYPENAME Storage::value_type*
>
class CowString
{
    typedef typename Storage::value_type E;
    typedef typename flex_string_details::get_unsigned<E>::result RefCountType;

public:
    typedef E value_type;
    typedef typename Storage::iterator iterator;
    typedef typename Storage::const_iterator const_iterator;
    typedef typename Storage::allocator_type allocator_type;
    typedef typename allocator_type::size_type size_type;
    typedef typename Storage::reference reference;
    
private:
    union
    {
        mutable char buf_[sizeof(Storage)];
        Align align_;
    };

    Storage& Data() const
    { return *reinterpret_cast<Storage*>(buf_); }

    RefCountType GetRefs() const
    {
        const Storage& d = Data();
        BOOST_ASSERT(d.size() > 0);
        BOOST_ASSERT(static_cast<RefCountType>(*d.begin()) != 0);
        return *d.begin();
    }
    
    RefCountType& Refs()
    {
        Storage& d = Data();
        BOOST_ASSERT(d.size() > 0);
        return reinterpret_cast<RefCountType&>(*d.begin());
    }
    
    void MakeUnique() const
    {
        BOOST_ASSERT(GetRefs() >= 1);
        if (GetRefs() == 1) return;

        union
        {
            char buf_[sizeof(Storage)];
            Align align_;
        } temp;

        --(*Data().begin()); // decrement the use count of the remaining object
        new(buf_) Storage(
            *new(temp.buf_) Storage(Data()), 
            flex_string_details::Shallow());
        *Data().begin() = 1;
    }

public:
    CowString(const CowString& s)
    {
        if (s.GetRefs() == (std::numeric_limits<RefCountType>::max)())
        {
            // must make a brand new copy
            new(buf_) Storage(s.Data()); // non shallow
            Refs() = 1;
        }
        else
        {
            new(buf_) Storage(s.Data(), flex_string_details::Shallow());
            ++Refs();
        }
        BOOST_ASSERT(Data().size() > 0);
    }
    
    CowString(const allocator_type& a)
    {
        new(buf_) Storage(1, 1, a);
    }
    
    CowString(const E* s, size_type len, const allocator_type& a)
    {
        // Warning - MSVC's debugger has trouble tracing through the code below.
        // It seems to be a const-correctness issue
        //
        new(buf_) Storage(a);
        Data().reserve(len + 1);
        Data().resize(1, 1);
        Data().append(s, s + len);
    }

    CowString(size_type len, E c, const allocator_type& a)
    {
        new(buf_) Storage(len + 1, c, a);
        Refs() = 1;
    }
    
    CowString& operator=(const CowString& rhs)
    {
//        CowString(rhs).swap(*this);
        if (--Refs() == 0) 
            Data().~Storage();
        if (rhs.GetRefs() == (std::numeric_limits<RefCountType>::max)())
        {
            // must make a brand new copy
            new(buf_) Storage(rhs.Data()); // non shallow
            Refs() = 1;
        }
        else
        {
            new(buf_) Storage(rhs.Data(), flex_string_details::Shallow());
            ++Refs();
        }
        BOOST_ASSERT(Data().size() > 0);
        return *this;
    }

    ~CowString()
    {
        BOOST_ASSERT(Data().size() > 0);
        if (--Refs() == 0) 
            Data().~Storage();
    }

    iterator begin()
    {
        BOOST_ASSERT(Data().size() > 0);
        MakeUnique();
        return Data().begin() + 1; 
    }
    
    const_iterator begin() const
    {
        BOOST_ASSERT(Data().size() > 0);
        return Data().begin() + 1; 
    }
    
    iterator end()
    {
        MakeUnique();
        return Data().end(); 
    }
    
    const_iterator end() const
    {
        return Data().end(); 
    }
    
    size_type size() const
    {
        BOOST_ASSERT(Data().size() > 0);
        return Data().size() - 1;
    }

    size_type max_size() const
    { 
        BOOST_ASSERT(Data().max_size() > 0);
        return Data().max_size() - 1;
    }

    size_type capacity() const
    { 
        BOOST_ASSERT(Data().capacity() > 0);
        return Data().capacity() - 1;
    }

    void resize(size_type n, E c)
    {
        BOOST_ASSERT(Data().size() > 0);
        MakeUnique();
        Data().resize(n + 1, c);
    }

    template <class FwdIterator>
    void append(FwdIterator b, FwdIterator e)
    {
        MakeUnique();
        Data().append(b, e);
    }
    
    void reserve(size_type res_arg)
    {
        if (capacity() > res_arg) return;
        MakeUnique();
        Data().reserve(res_arg + 1);
    }
    
    void swap(CowString& rhs)
    {
        Data().swap(rhs.Data());
    }
    
    const E* c_str() const
    { 
        BOOST_ASSERT(Data().size() > 0);
        return Data().c_str() + 1;
    }

    const E* data() const
    { 
        BOOST_ASSERT(Data().size() > 0);
        return Data().data() + 1;
    }
    
    allocator_type get_allocator() const
    { 
        return Data().get_allocator();
    }
};

////////////////////////////////////////////////////////////////////////////////
// class template flex_string
// a std::basic_string compatible implementation 
// Uses a Storage policy 
////////////////////////////////////////////////////////////////////////////////

template <typename E,
    class T = std::char_traits<E>,
    class A = std::allocator<E>,
    class Storage = AllocatorStringStorage<E, A> >
class flex_string : private Storage
{
#if defined(BOOST_WAVE_FLEXSTRING_THROW_ON_ENFORCE)
    template <typename Exception>
    static void Enforce(bool condition, Exception*, const char* msg)
    { if (!condition) boost::throw_exception(Exception(msg)); }
#else
    template <typename Exception>
    static inline void Enforce(bool condition, Exception*, const char* msg)
    { BOOST_ASSERT(condition && msg); }
#endif // defined(BOOST_WAVE_FLEXSTRING_THROW_ON_ENFORCE)

#ifndef NDEBUG
    bool Sane() const
    {
        return