text: // Short-string-optimized versatile string base -*- C++ -*-
  
  // Copyright (C) 2005-2013 Free Software Foundation, Inc.
  //
  // This file is part of the GNU ISO C++ Library.  This library is free
  // software; you can redistribute it and/or modify it under the
  // terms of the GNU General Public License as published by the
  // Free Software Foundation; either version 3, or (at your option)
  // any later version.
  
  // This library is distributed in the hope that it will be useful,
  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  // GNU General Public License for more details.
  
  // Under Section 7 of GPL version 3, you are granted additional
  // permissions described in the GCC Runtime Library Exception, version
  // 3.1, as published by the Free Software Foundation.
  
  // You should have received a copy of the GNU General Public License and
  // a copy of the GCC Runtime Library Exception along with this program;
  // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  // <http://www.gnu.org/licenses/>.
  
  /** @file ext/sso_string_base.h
   *  This is an internal header file, included by other library headers.
   *  Do not attempt to use it directly. @headername{ext/vstring.h}
   */
  
  #ifndef _SSO_STRING_BASE_H
  #define _SSO_STRING_BASE_H 1
  
  namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  {
  _GLIBCXX_BEGIN_NAMESPACE_VERSION
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      class __sso_string_base
      : protected __vstring_utility<_CharT, _Traits, _Alloc>
      {
      public:
        typedef _Traits					    traits_type;
        typedef typename _Traits::char_type		    value_type;
  
        typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
        typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
        typedef typename _CharT_alloc_type::size_type	    size_type;
        
      private:
        // Data Members:
        typename _Util_Base::template _Alloc_hider<_CharT_alloc_type>
                                                              _M_dataplus;
        size_type                                             _M_string_length;
  
        enum { _S_local_capacity = 15 };
        
        union
        {
  	_CharT           _M_local_data[_S_local_capacity + 1];
  	size_type        _M_allocated_capacity;
        };
  
        void
        _M_data(_CharT* __p)
        { _M_dataplus._M_p = __p; }
  
        void
        _M_length(size_type __length)
        { _M_string_length = __length; }
  
        void
        _M_capacity(size_type __capacity)
        { _M_allocated_capacity = __capacity; }
  
        bool
        _M_is_local() const
        { return _M_data() == _M_local_data; }
  
        // Create & Destroy
        _CharT*
        _M_create(size_type&, size_type);
        
        void
        _M_dispose()
        {
  	if (!_M_is_local())
  	  _M_destroy(_M_allocated_capacity);
        }
  
        void
        _M_destroy(size_type __size) throw()
        { _M_get_allocator().deallocate(_M_data(), __size + 1); }
  
        // _M_construct_aux is used to implement the 21.3.1 para 15 which
        // requires special behaviour if _InIterator is an integral type
        template<typename _InIterator>
          void
          _M_construct_aux(_InIterator __beg, _InIterator __end, 
  			 std::__false_type)
  	{
            typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
            _M_construct(__beg, __end, _Tag());
  	}
  
        // _GLIBCXX_RESOLVE_LIB_DEFECTS
        // 438. Ambiguity in the "do the right thing" clause
        template<typename _Integer>
          void
          _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
  	{ _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
  
        void
        _M_construct_aux_2(size_type __req, _CharT __c)
        { _M_construct(__req, __c); }
  
        template<typename _InIterator>
          void
          _M_construct(_InIterator __beg, _InIterator __end)
  	{
  	  typedef typename std::__is_integer<_InIterator>::__type _Integral;
  	  _M_construct_aux(__beg, __end, _Integral());
          }
  
        // For Input Iterators, used in istreambuf_iterators, etc.
        template<typename _InIterator>
          void
          _M_construct(_InIterator __beg, _InIterator __end,
  		     std::input_iterator_tag);
        
        // For forward_iterators up to random_access_iterators, used for
        // string::iterator, _CharT*, etc.
        template<typename _FwdIterator>
          void
          _M_construct(_FwdIterator __beg, _FwdIterator __end,
  		     std::forward_iterator_tag);
  
        void
        _M_construct(size_type __req, _CharT __c);
  
      public:
        size_type
        _M_max_size() const
        { return (_M_get_allocator().max_size() - 1) / 2; }
  
        _CharT*
        _M_data() const
        { return _M_dataplus._M_p; }
  
        size_type
        _M_length() const
        { return _M_string_length; }
  
        size_type
        _M_capacity() const
        {
  	return _M_is_local() ? size_type(_S_local_capacity)
  	                     : _M_allocated_capacity; 
        }
  
        bool
        _M_is_shared() const
        { return false; }
  
        void
        _M_set_leaked() { }
  
        void
        _M_leak() { }
  
        void
        _M_set_length(size_type __n)
        {
  	_M_length(__n);
  	traits_type::assign(_M_data()[__n], _CharT());
        }
  
        __sso_string_base()
        : _M_dataplus(_M_local_data)
        { _M_set_length(0); }
  
        __sso_string_base(const _Alloc& __a);
  
        __sso_string_base(const __sso_string_base& __rcs);
  
  #if __cplusplus >= 201103L
        __sso_string_base(__sso_string_base&& __rcs);
  #endif
  
        __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
  
        template<typename _InputIterator>
          __sso_string_base(_InputIterator __beg, _InputIterator __end,
  			  const _Alloc& __a);
  
        ~__sso_string_base()
        { _M_dispose(); }
  
        _CharT_alloc_type&
        _M_get_allocator()
        { return _M_dataplus; }
  
        const _CharT_alloc_type&
        _M_get_allocator() const
        { return _M_dataplus; }
  
        void
        _M_swap(__sso_string_base& __rcs);
  
        void
        _M_assign(const __sso_string_base& __rcs);
  
        void
        _M_reserve(size_type __res);
  
        void
        _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
  		size_type __len2);
  
        void
        _M_erase(size_type __pos, size_type __n);
  
        void
        _M_clear()
        { _M_set_length(0); }
  
        bool
        _M_compare(const __sso_string_base&) const
        { return false; }
      };
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_swap(__sso_string_base& __rcs)
      {
        if (this == &__rcs)
  	return;
  
        // _GLIBCXX_RESOLVE_LIB_DEFECTS
        // 431. Swapping containers with unequal allocators.
        std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(),
  						     __rcs._M_get_allocator());
  
        if (_M_is_local())
  	if (__rcs._M_is_local())
  	  {
  	    if (_M_length() && __rcs._M_length())
  	      {
  		_CharT __tmp_data[_S_local_capacity + 1];
  		traits_type::copy(__tmp_data, __rcs._M_local_data,
  				  _S_local_capacity + 1);
  		traits_type::copy(__rcs._M_local_data, _M_local_data,
  				  _S_local_capacity + 1);
  		traits_type::copy(_M_local_data, __tmp_data,
  				  _S_local_capacity + 1);
  	      }
  	    else if (__rcs._M_length())
  	      {
  		traits_type::copy(_M_local_data, __rcs._M_local_data,
  				  _S_local_capacity + 1);
  		_M_length(__rcs._M_length());
  		__rcs._M_set_length(0);
  		return;
  	      }
  	    else if (_M_length())
  	      {
  		traits_type::copy(__rcs._M_local_data, _M_local_data,
  				  _S_local_capacity + 1);
  		__rcs._M_length(_M_length());
  		_M_set_length(0);
  		return;
  	      }
  	  }
  	else
  	  {
  	    const size_type __tmp_capacity = __rcs._M_allocated_capacity;
  	    traits_type::copy(__rcs._M_local_data, _M_local_data,
  			      _S_local_capacity + 1);
  	    _M_data(__rcs._M_data());
  	    __rcs._M_data(__rcs._M_local_data);
  	    _M_capacity(__tmp_capacity);
  	  }
        else
  	{
  	  const size_type __tmp_capacity = _M_allocated_capacity;
  	  if (__rcs._M_is_local())
  	    {
  	      traits_type::copy(_M_local_data, __rcs._M_local_data,
  				_S_local_capacity + 1);
  	      __rcs._M_data(_M_data());
  	      _M_data(_M_local_data);
  	    }
  	  else
  	    {
  	      _CharT* __tmp_ptr = _M_data();
  	      _M_data(__rcs._M_data());
  	      __rcs._M_data(__tmp_ptr);
  	      _M_capacity(__rcs._M_allocated_capacity);
  	    }
  	  __rcs._M_capacity(__tmp_capacity);
  	}
  
        const size_type __tmp_length = _M_length();
        _M_length(__rcs._M_length());
        __rcs._M_length(__tmp_length);
      }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      _CharT*
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_create(size_type& __capacity, size_type __old_capacity)
      {
        // _GLIBCXX_RESOLVE_LIB_DEFECTS
        // 83.  String::npos vs. string::max_size()
        if (__capacity > _M_max_size())
  	std::__throw_length_error(__N("__sso_string_base::_M_create"));
  
        // The below implements an exponential growth policy, necessary to
        // meet amortized linear time requirements of the library: see
        // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
        if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
  	{
  	  __capacity = 2 * __old_capacity;
  	  // Never allocate a string bigger than max_size.
  	  if (__capacity > _M_max_size())
  	    __capacity = _M_max_size();
  	}
  
        // NB: Need an array of char_type[__capacity], plus a terminating
        // null char_type() element.
        return _M_get_allocator().allocate(__capacity + 1);
      }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      __sso_string_base<_CharT, _Traits, _Alloc>::
      __sso_string_base(const _Alloc& __a)
      : _M_dataplus(__a, _M_local_data)
      { _M_set_length(0); }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      __sso_string_base<_CharT, _Traits, _Alloc>::
      __sso_string_base(const __sso_string_base& __rcs)
      : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
      { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
  
  #if __cplusplus >= 201103L
    template<typename _CharT, typename _Traits, typename _Alloc>
      __sso_string_base<_CharT, _Traits, _Alloc>::
      __sso_string_base(__sso_string_base&& __rcs)
      : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
      {
        if (__rcs._M_is_local())
  	{
  	  if (__rcs._M_length())
  	    traits_type::copy(_M_local_data, __rcs._M_local_data,
  			      _S_local_capacity + 1);
  	}
        else
  	{
  	  _M_data(__rcs._M_data());
  	  _M_capacity(__rcs._M_allocated_capacity);
  	}
  
        _M_set_length(__rcs._M_length());
        __rcs._M_data(__rcs._M_local_data);
        __rcs._M_set_length(0);
      }
  #endif
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      __sso_string_base<_CharT, _Traits, _Alloc>::
      __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
      : _M_dataplus(__a, _M_local_data)
      { _M_construct(__n, __c); }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      template<typename _InputIterator>
      __sso_string_base<_CharT, _Traits, _Alloc>::
      __sso_string_base(_InputIterator __beg, _InputIterator __end,
  		      const _Alloc& __a)
      : _M_dataplus(__a, _M_local_data)
      { _M_construct(__beg, __end); }
  
    // NB: This is the special case for Input Iterators, used in
    // istreambuf_iterators, etc.
    // Input Iterators have a cost structure very different from
    // pointers, calling for a different coding style.
    template<typename _CharT, typename _Traits, typename _Alloc>
      template<typename _InIterator>
        void
        __sso_string_base<_CharT, _Traits, _Alloc>::
        _M_construct(_InIterator __beg, _InIterator __end,
  		   std::input_iterator_tag)
        {
  	size_type __len = 0;
  	size_type __capacity = size_type(_S_local_capacity);
  
  	while (__beg != __end && __len < __capacity)
  	  {
  	    _M_data()[__len++] = *__beg;
  	    ++__beg;
  	  }
  	
  	__try
  	  {
  	    while (__beg != __end)
  	      {
  		if (__len == __capacity)
  		  {
  		    // Allocate more space.
  		    __capacity = __len + 1;
  		    _CharT* __another = _M_create(__capacity, __len);
  		    this->_S_copy(__another, _M_data(), __len);
  		    _M_dispose();
  		    _M_data(__another);
  		    _M_capacity(__capacity);
  		  }
  		_M_data()[__len++] = *__beg;
  		++__beg;
  	      }
  	  }
  	__catch(...)
  	  {
  	    _M_dispose();
  	    __throw_exception_again;
  	  }
  
  	_M_set_length(__len);
        }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      template<typename _InIterator>
        void
        __sso_string_base<_CharT, _Traits, _Alloc>::
        _M_construct(_InIterator __beg, _InIterator __end,
  		   std::forward_iterator_tag)
        {
  	// NB: Not required, but considered best practice.
  	if (__is_null_pointer(__beg) && __beg != __end)
  	  std::__throw_logic_error(__N("__sso_string_base::"
  				       "_M_construct null not valid"));
  
  	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
  
  	if (__dnew > size_type(_S_local_capacity))
  	  {
  	    _M_data(_M_create(__dnew, size_type(0)));
  	    _M_capacity(__dnew);
  	  }
  
  	// Check for out_of_range and length_error exceptions.
  	__try
  	  { this->_S_copy_chars(_M_data(), __beg, __end); }
  	__catch(...)
  	  {
  	    _M_dispose();
  	    __throw_exception_again;
  	  }
  
  	_M_set_length(__dnew);
        }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_construct(size_type __n, _CharT __c)
      {
        if (__n > size_type(_S_local_capacity))
  	{
  	  _M_data(_M_create(__n, size_type(0)));
  	  _M_capacity(__n);
  	}
  
        if (__n)
  	this->_S_assign(_M_data(), __n, __c);
  
        _M_set_length(__n);
      }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_assign(const __sso_string_base& __rcs)
      {
        if (this != &__rcs)
  	{
  	  const size_type __rsize = __rcs._M_length();
  	  const size_type __capacity = _M_capacity();
  
  	  if (__rsize > __capacity)
  	    {
  	      size_type __new_capacity = __rsize;
  	      _CharT* __tmp = _M_create(__new_capacity, __capacity);
  	      _M_dispose();
  	      _M_data(__tmp);
  	      _M_capacity(__new_capacity);
  	    }
  
  	  if (__rsize)
  	    this->_S_copy(_M_data(), __rcs._M_data(), __rsize);
  
  	  _M_set_length(__rsize);
  	}
      }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_reserve(size_type __res)
      {
        // Make sure we don't shrink below the current size.
        if (__res < _M_length())
  	__res = _M_length();
  
        const size_type __capacity = _M_capacity();
        if (__res != __capacity)
  	{
  	  if (__res > __capacity
  	      || __res > size_type(_S_local_capacity))
  	    {
  	      _CharT* __tmp = _M_create(__res, __capacity);
  	      this->_S_copy(__tmp, _M_data(), _M_length() + 1);
  	      _M_dispose();
  	      _M_data(__tmp);
  	      _M_capacity(__res);
  	    }
  	  else if (!_M_is_local())
  	    {
  	      this->_S_copy(_M_local_data, _M_data(), _M_length() + 1);
  	      _M_destroy(__capacity);
  	      _M_data(_M_local_data);
  	    }
  	}
      }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
  	      size_type __len2)
      {
        const size_type __how_much = _M_length() - __pos - __len1;
        
        size_type __new_capacity = _M_length() + __len2 - __len1;
        _CharT* __r = _M_create(__new_capacity, _M_capacity());
  
        if (__pos)
  	this->_S_copy(__r, _M_data(), __pos);
        if (__s && __len2)
  	this->_S_copy(__r + __pos, __s, __len2);
        if (__how_much)
  	this->_S_copy(__r + __pos + __len2,
  		      _M_data() + __pos + __len1, __how_much);
        
        _M_dispose();
        _M_data(__r);
        _M_capacity(__new_capacity);
      }
  
    template<typename _CharT, typename _Traits, typename _Alloc>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_erase(size_type __pos, size_type __n)
      {
        const size_type __how_much = _M_length() - __pos - __n;
  
        if (__how_much && __n)
  	this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
  
        _M_set_length(_M_length() - __n);
      }
  
  _GLIBCXX_END_NAMESPACE_VERSION
  } // namespace
  
  #endif /* _SSO_STRING_BASE_H */
  