flex_string.hpp

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

/*=============================================================================
    Boost.Wave: A Standard compliant C++ preprocessor library
    http://www.boost.org/

    Copyright (c) 2001 by Andrei Alexandrescu. Distributed under the Boost
    Software License, Version 1.0. (See accompanying file
    LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/

// This code is taken from: 
// Andrei Alexandrescu, Generic<Programming>: A Policy-Based basic_string 
// Implementation. http://www.cuj.com/documents/s=7994/cujcexp1906alexandr/
//
// #HK030306: 
//      - Moved into the namespace boost::wave::util 
//      - Added a bunch of missing typename(s) 
//      - Integrated with boost config
//      - Added a missing header include
//      - Added special constructors and operator= to allow CowString to be 
//        a real COW-string (removed unnecessary data copying)
//      - Fixed a string terminating bug in append
//
// #HK040109:
//      - Incorporated the changes from Andrei's latest version of this class
//
// #HK070307:
//      - Once again incorporated the changes from Andrei's latest version of 
//        this class

#ifndef FLEX_STRING_INC_
#define FLEX_STRING_INC_

/*
////////////////////////////////////////////////////////////////////////////////
template <typename E, class A = @>
class StoragePolicy
{
    typedef E value_type;
    typedef @ iterator;
    typedef @ const_iterator;
    typedef A allocator_type;
    typedef @ size_type;
    
    StoragePolicy(const StoragePolicy& s);
    StoragePolicy(const A&);
    StoragePolicy(const E* s, size_type len, const A&);
    StoragePolicy(size_type len, E c, const A&);
    ~StoragePolicy();

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    
    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;

    void reserve(size_type res_arg);

    void append(const E* s, size_type sz);
    
    template <class InputIterator>
    void append(InputIterator b, InputIterator e);

    void resize(size_type newSize, E fill);

    void swap(StoragePolicy& rhs);
    
    const E* c_str() const;
    const E* data() const;
    
    A get_allocator() const;
};
////////////////////////////////////////////////////////////////////////////////
*/

#include <boost/config.hpp>
#include <boost/assert.hpp>
#include <boost/throw_exception.hpp>

#include <boost/iterator/reverse_iterator.hpp>

#include <boost/wave/wave_config.hpp>
#if BOOST_WAVE_SERIALIZATION != 0
#include <boost/serialization/serialization.hpp>
#include <boost/serialization/split_free.hpp>
#include <boost/serialization/collections_save_imp.hpp>
#include <boost/serialization/collections_load_imp.hpp>
#define BOOST_WAVE_FLEX_STRING_SERIALIZATION_HACK 1
#endif

#include <memory>
#include <new>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <limits>
#include <stdexcept>
#include <iosfwd>
#include <cstddef>
#include <cstring>
#include <cstdlib>

// this must occur after all of the includes and before any code appears
#ifdef BOOST_HAS_ABI_HEADERS
#include BOOST_ABI_PREFIX
#endif

///////////////////////////////////////////////////////////////////////////////
namespace boost {
namespace wave {
namespace util {

namespace flex_string_details
{
    template <class InIt, class OutIt>
    OutIt copy_n(InIt b, 
        typename std::iterator_traits<InIt>::difference_type n, OutIt d)
    {
        for (/**/; n != 0; --n, ++b, ++d)
        {
            *d = *b;
        }
        return d;
    }

    template <class Pod, class T>
    inline void pod_fill(Pod* b, Pod* e, T c)
    {
        switch ((e - b) & 7)
        {
        case 0:
            while (b != e)
            {
                *b = c; ++b;
        case 7: *b = c; ++b;
        case 6: *b = c; ++b;
        case 5: *b = c; ++b;
        case 4: *b = c; ++b;
        case 3: *b = c; ++b;
        case 2: *b = c; ++b;
        case 1: *b = c; ++b;
            }
        }
    }

    template <class Pod>
    inline void pod_move(const Pod* b, const Pod* e, Pod* d)
    {
        using namespace std;
        memmove(d, b, (e - b) * sizeof(*b));
    }

    template <class Pod>
    inline Pod* pod_copy(const Pod* b, const Pod* e, Pod* d)
    {
        const std::size_t s = e - b;
        using namespace std;
        memcpy(d, b, s * sizeof(*b));
        return d + s;
    }

    template <typename T> struct get_unsigned
    {
        typedef T result;
    };

    template <> struct get_unsigned<char>
    {
        typedef unsigned char result;
    };

    template <> struct get_unsigned<signed char>
    {
        typedef unsigned char result;
    };

    template <> struct get_unsigned<short int>
    {
        typedef unsigned short int result;
    };

    template <> struct get_unsigned<int>
    {
        typedef unsigned int result;
    };

    template <> struct get_unsigned<long int>
    {
        typedef unsigned long int result;
    };

    enum Shallow {};
}

template <class T> class mallocator
{
public:
    typedef T                 value_type;
    typedef value_type*       pointer;
    typedef const value_type* const_pointer;
    typedef value_type&       reference;
    typedef const value_type& const_reference;
    typedef std::size_t       size_type;
    //typedef unsigned int      size_type;
    //typedef std::ptrdiff_t    difference_type;
    typedef int               difference_type;

    template <class U> 
    struct rebind { typedef mallocator<U> other; };

    mallocator() {}
    mallocator(const mallocator&) {}
    //template <class U> 
    //mallocator(const mallocator<U>&) {}
    ~mallocator() {}

    pointer address(reference x) const { return &x; }
    const_pointer address(const_reference x) const 
    { 
        return x;
    }

    pointer allocate(size_type n, const_pointer = 0) 
    {
        using namespace std;
        void* p = malloc(n * sizeof(T));
        if (!p) boost::throw_exception(std::bad_alloc());
        return static_cast<pointer>(p);
    }

    void deallocate(pointer p, size_type) 
    { 
        using namespace std;
        free(p); 
    }

    size_type max_size() const 
    { 
        return static_cast<size_type>(-1) / sizeof(T);
    }

    void construct(pointer p, const value_type& x) 
    { 
        new(p) value_type(x); 
    }

    void destroy(pointer p) 
    { 
        p->~value_type(); 
    }

private:
    void operator=(const mallocator&);
};

template<> class mallocator<void>
{
  typedef void        value_type;
  typedef void*       pointer;
  typedef const void* const_pointer;

  template <class U> 
  struct rebind { typedef mallocator<U> other; };
};

template <class T>
inline bool operator==(const mallocator<T>&, 
                       const mallocator<T>&) {
  return true;
}

template <class T>
inline bool operator!=(const mallocator<T>&, 
                       const mallocator<T>&) {
  return false;
}

template <class Allocator>
typename Allocator::pointer Reallocate(
    Allocator& alloc,
    typename Allocator::pointer p, 
    typename Allocator::size_type oldObjCount,
    typename Allocator::size_type newObjCount,
    void*)
{
    // @@@ not implemented
    return NULL;
}

template <class Allocator>
typename Allocator::pointer Reallocate(
    Allocator& alloc,
    typename Allocator::pointer p, 
    typename Allocator::size_type oldObjCount,
    typename Allocator::size_type newObjCount,
    mallocator<void>*)
{
    // @@@ not implemented
    return NULL;
}

////////////////////////////////////////////////////////////////////////////////
// class template SimpleStringStorage
// Allocates memory with malloc
////////////////////////////////////////////////////////////////////////////////

template <typename E, class A = std::allocator<E> >
class SimpleStringStorage
{
    // The "public" below exists because MSVC can't do template typedefs
public:
    struct Data
    {
        Data() : pEnd_(buffer_), pEndOfMem_(buffer_) { buffer_[0] = E(0); }

        E* pEnd_;
        E* pEndOfMem_;
        E buffer_[1];
    };
    static const Data emptyString_;
    
    typedef typename A::size_type size_type;

private:
    Data* pData_;

    void Init(size_type size, size_type capacity)
    {
        BOOST_ASSERT(size <= capacity);
        if (capacity == 0) 
        {
            pData_ = const_cast<Data*>(&emptyString_);
        }
        else
        {
            // 11-17-2000: comment added: 
            //     No need to allocate (capacity + 1) to 
            //     accomodate the terminating 0, because Data already
            //     has one one character in there
            pData_ = static_cast<Data*>(
                malloc(sizeof(Data) + capacity * sizeof(E)));
            if (!pData_) boost::throw_exception(std::bad_alloc());
            pData_->pEnd_ = pData_->buffer_ + size;
            pData_->pEndOfMem_ = pData_->buffer_ + capacity;
        }
    }
    
private:
    // Warning - this doesn't initialize pData_. Used in reserve()
    SimpleStringStorage()
    { }
    
public:
    typedef E value_type;
    typedef E* iterator;
    typedef const E* const_iterator;
    typedef A allocator_type;
    
    SimpleStringStorage(const SimpleStringStorage& rhs) 
    {
        const size_type sz = rhs.size();
        Init(sz, sz);
        if (sz) flex_string_details::pod_copy(rhs.begin(), rhs.end(), begin());
    }
    
    SimpleStringStorage(const SimpleStringStorage& s, 
        flex_string_details::Shallow) 
        : pData_(s.pData_)
    {
    }
    
    SimpleStringStorage(const A&)
    { pData_ = const_cast<Data*>(&emptyString_); }
    
    SimpleStringStorage(const E* s, size_type len, const A&)
    {
        Init(len, len);
        flex_string_details::pod_copy(s, s + len, begin());
    }

    SimpleStringStorage(size_type len, E c, const A&)
    {
        Init(len, len);
        flex_string_details::pod_fill(begin(), end(), c);
    }
    
    SimpleStringStorage& operator=(const SimpleStringStorage& rhs)
    {
        const size_type sz = rhs.size();
        reserve(sz);
        flex_string_details::pod_copy(&*rhs.begin(), &*rhs.end(), begin());
        pData_->pEnd_ = &*begin() + sz;
        return *this;
    }

    ~SimpleStringStorage()
    {
        BOOST_ASSERT(begin() <= end());
        if (pData_ != &emptyString_) free(pData_);
    }

    iterator begin()
    { return pData_->buffer_; }
    
    const_iterator begin() const
    { return pData_->buffer_; }
    
    iterator end()
    { return pData_->pEnd_; }
    
    const_iterator end() const
    { return pData_->pEnd_; }
    
    size_type size() const
    { return pData_->pEnd_ - pData_->buffer_; }

    size_type max_size() const
    { return std::size_t(-1) / sizeof(E) - sizeof(Data) - 1; }

    size_type capacity() const
    { return pData_->pEndOfMem_ - pData_->buffer_; }

    void reserve(size_type res_arg)
    {
        if (res_arg <= capacity())
        {
            // @@@ insert shrinkage here if you wish
            return;
        }

        if (pData_ == &emptyString_) 
        {
            Init(0, res_arg);
        }
        else
        {
            const size_type sz = size();

            void* p = realloc(pData_, 
                sizeof(Data) + res_arg * sizeof(E));
            if (!p) boost::throw_exception(std::bad_alloc());
        
            if (p != pData_)
            {
                pData_ = static_cast<Data*>(p);
                pData_->pEnd_ = pData_->buffer_ + sz;
            }
            pData_->pEndOfMem_ = pData_->buffer_ + res_arg;
        }
    }

    void append(const E* s, size_type sz)
    {
        const size_type neededCapacity = size() + sz;

        if (capacity() < neededCapacity)
        {
            const iterator b = begin();
            static std::less_equal<const E*> le;
            if (le(b, s) && le(s, end()))
            {
               // aliased
                const size_type offset = s - b;
                reserve(neededCapacity);
                s = begin() + offset;
            }
            else
            {
                reserve(neededCapacity);
            }
        }