[thirdparty/gcc.git] / libstdc++-v3 / include / ext / sso_string_base.h

// Short-string-optimized versatile string base -*- C++ -*-

// Copyright (C) 2005 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 2, 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.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file ext/sso_string_base.h
 *  This file is a GNU extension to the Standard C++ Library.
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef _SSO_STRING_BASE_H
#define _SSO_STRING_BASE_H 1

namespace __gnu_cxx
{
  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 _Alloc					    allocator_type;

      typedef typename __vstring_utility<_CharT, _Traits, _Alloc>::
        _CharT_alloc_type                                   _CharT_alloc_type;
      typedef typename _CharT_alloc_type::size_type	    size_type;
      
      // The maximum number of individual char_type elements of an
      // individual string is determined by _S_max_size. This is the
      // value that will be returned by max_size().  (Whereas npos
      // is the maximum number of bytes the allocator can allocate.)
      // If one was to divvy up the theoretical largest size string,
      // with a terminating character and m _CharT elements, it'd
      // look like this:
      // npos = m * sizeof(_CharT) + sizeof(_CharT)
      // Solving for m:
      // m = npos / sizeof(CharT) - 1
      // In addition, this implementation quarters this amount.
      static const size_type	_S_max_size;

    private:
      static const _CharT	_S_terminal;
      
      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
      struct _Alloc_hider : _Alloc
      {
	_Alloc_hider(const _Alloc& __a, _CharT* __ptr)
	: _Alloc(__a), _M_p(__ptr) { }

	_CharT* _M_p; // The actual data.
      };

      // Data Members (private):
      _Alloc_hider	        _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;
      };

      _CharT*
      _M_data(_CharT* __p)
      { return (_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() throw()
      {
	if (!_M_is_local())
	  _M_destroy(_M_allocated_capacity + 1);
      }

      void
      _M_destroy(size_type) throw();

      // _M_construct_aux is used to implement the 21.3.1 para 15 which
      // requires special behaviour if _InIter is an integral type
      template<class _InIterator>
        void
        _M_construct_aux(_InIterator __beg, _InIterator __end, __false_type)
	{
          typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
          _M_construct(__beg, __end, _Tag());
	}

      template<class _InIterator>
        void
        _M_construct_aux(_InIterator __beg, _InIterator __end, __true_type)
	{ _M_construct(static_cast<size_type>(__beg),
		       static_cast<value_type>(__end)); }

      template<class _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<class _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<class _FwdIterator>
        void
        _M_construct(_FwdIterator __beg, _FwdIterator __end,
		     std::forward_iterator_tag);

      void
      _M_construct(size_type __req, _CharT __c);

    public:
      _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; }

      bool
      _M_is_leaked() const
      { return false; }

      void
      _M_set_sharable() { }

      void
      _M_set_leaked() { }

      void
      _M_set_length(size_type __n)
      {
	_M_length(__n);
	// grrr. (per 21.3.4)
	// You cannot leave those LWG people alone for a second.
	traits_type::assign(_M_data()[__n], _S_terminal);
      }

      void
      _M_leak() { }

      __sso_string_base()
      : _M_dataplus(_Alloc(), _M_local_data)
      { _M_set_length(0); }

      __sso_string_base(const _Alloc& __a);

      __sso_string_base(const __sso_string_base& __rcs);

      __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(); }

      allocator_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, size_type __len2);
    };

  template<typename _CharT, typename _Traits, typename _Alloc>
    void
    __sso_string_base<_CharT, _Traits, _Alloc>::
    _M_destroy(size_type __size) throw()
    { _CharT_alloc_type(_M_get_allocator()).deallocate(_M_data(), __size); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    void
    __sso_string_base<_CharT, _Traits, _Alloc>::
    _M_swap(__sso_string_base& __rcs)
    {
      const bool __local = _M_is_local();
      const bool __rcs_local = __rcs._M_is_local();
      
      if (__local && __rcs_local)
	{
	  _CharT __tmp_data[_S_local_capacity + 1];
	  const size_type __tmp_length = __rcs._M_length();
	  _S_copy(__tmp_data, __rcs._M_data(), __rcs._M_length() + 1);
	  __rcs._M_length(_M_length());
	  _S_copy(__rcs._M_data(), _M_data(), _M_length() + 1);
	  _M_length(__tmp_length);
	  _S_copy(_M_data(), __tmp_data, __tmp_length + 1);
	}
      else if (__local && !__rcs_local)
	{
	  const size_type __tmp_capacity = __rcs._M_allocated_capacity;
	  const size_type __tmp_length = __rcs._M_length();
	  _CharT* __tmp_ptr = __rcs._M_data();
	  __rcs._M_data(__rcs._M_local_data);
	  _S_copy(__rcs._M_data(), _M_data(), _M_length() + 1);
	  __rcs._M_length(_M_length());
	  _M_data(__tmp_ptr);
	  _M_length(__tmp_length);
	  _M_capacity(__tmp_capacity);
	}
      else if (!__local && __rcs_local)
	{
	  const size_type __tmp_capacity = _M_allocated_capacity;
	  const size_type __tmp_length = _M_length();
	  _CharT* __tmp_ptr = _M_data();
	  _M_data(_M_local_data);
	  _S_copy(_M_data(), __rcs._M_data(), __rcs._M_length() + 1);
	  _M_length(__rcs._M_length());
	  __rcs._M_data(__tmp_ptr);
	  __rcs._M_length(__tmp_length);
	  __rcs._M_capacity(__tmp_capacity);
	}
      else
	{
	  const size_type __tmp_capacity = _M_allocated_capacity;
	  const size_type __tmp_length = _M_length();
	  _CharT* __tmp_ptr = _M_data();
	  _M_data(__rcs._M_data());
	  _M_length(__rcs._M_length());
	  _M_capacity(__rcs._M_allocated_capacity);
	  __rcs._M_data(__tmp_ptr);
	  __rcs._M_length(__tmp_length);
	  __rcs._M_capacity(__tmp_capacity);
	}
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    const typename __sso_string_base<_CharT, _Traits, _Alloc>::size_type
    __sso_string_base<_CharT, _Traits, _Alloc>::
    _S_max_size = ((static_cast<size_type>(-1) / sizeof(_CharT)) - 1) / 4;

  template<typename _CharT, typename _Traits, typename _Alloc>
    const _CharT
    __sso_string_base<_CharT, _Traits, _Alloc>::_S_terminal = _CharT();

  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 > _S_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.
      // It's active for allocations requiring an amount of memory above
      // system pagesize. This is consistent with the requirements of the
      // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
      if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
	__capacity = 2 * __old_capacity;

      // NB: Need an array of char_type[__capacity], plus a terminating
      // null char_type() element.
      return _CharT_alloc_type(_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()); }

  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)
      {
	// Avoid reallocation for common case.
	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);
		    _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 (__builtin_expect(__is_null_p(__beg) && __beg != __end, 0))
	  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
	  { _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)
	_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)
	{
	  size_type __size = __rcs._M_length();

	  _CharT* __tmp = _M_local_data;
	  if (__size > size_type(_S_local_capacity))
	    __tmp = _M_create(__size, size_type(0));

	  _M_dispose();
	  _M_data(__tmp);

	  if (__size)
	    _S_copy(_M_data(), __rcs._M_data(), __size);

	  if (!_M_is_local())
	    _M_capacity(__size);

	  _M_set_length(__size);
	}
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    void
    __sso_string_base<_CharT, _Traits, _Alloc>::
    _M_reserve(size_type __res)
    {
      const size_type __capacity = _M_capacity();
      if (__res != __capacity)
	{
	  // Make sure we don't shrink below the current size.
	  if (__res < _M_length())
	    __res = _M_length();

	  if (__res > __capacity
	      || __res > size_type(_S_local_capacity))
	    {
	      _CharT* __tmp = _M_create(__res, __capacity);
	      if (_M_length())
		_S_copy(__tmp, _M_data(), _M_length());
	      _M_dispose();
	      _M_data(__tmp);
	      _M_capacity(__res);
	    }
	  else if (!_M_is_local())
	    {
	      const size_type __tmp_capacity = _M_allocated_capacity;
	      if (_M_length())
		_S_copy(_M_local_data, _M_data(), _M_length());
	      _M_destroy(__tmp_capacity + 1);
	      _M_data(_M_local_data);
	    }	  
	  
	  _M_set_length(_M_length());
	}
    }

  template<typename _CharT, typename _Traits, typename _Alloc>
    void
    __sso_string_base<_CharT, _Traits, _Alloc>::
    _M_mutate(size_type __pos, size_type __len1, size_type __len2)
    {
      const size_type __old_size = _M_length();
      const size_type __new_size = __old_size + __len2 - __len1;
      const size_type __how_much = __old_size - __pos - __len1;
      
      if (__new_size > _M_capacity())
	{
	  // Must reallocate.
	  size_type __new_capacity = __new_size;
	  _CharT* __r = _M_create(__new_capacity, _M_capacity());

	  if (__pos)
	    _S_copy(__r, _M_data(), __pos);
	  if (__how_much)
	    _S_copy(__r + __pos + __len2,
		    _M_data() + __pos + __len1, __how_much);

	  _M_dispose();
	  _M_data(__r);
	  _M_capacity(__new_capacity);
	}
      else if (__how_much && __len1 != __len2)
	{
	  // Work in-place.
	  _S_move(_M_data() + __pos + __len2,
		  _M_data() + __pos + __len1, __how_much);
	}

      _M_set_length(__new_size);
    }
} // namespace __gnu_cxx

#endif /* _SSO_STRING_BASE_H */
Commit	Line	Data
872d8fea PC	1	// Short-string-optimized versatile string base -- C++ --
	2
	3	// Copyright (C) 2005 Free Software Foundation, Inc.
	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 2, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// You should have received a copy of the GNU General Public License along
	17	// with this library; see the file COPYING. If not, write to the Free
83f51799	18	// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
872d8fea PC	19	// USA.
	20
	21	// As a special exception, you may use this file as part of a free software
	22	// library without restriction. Specifically, if other files instantiate
	23	// templates or use macros or inline functions from this file, or you compile
	24	// this file and link it with other files to produce an executable, this
	25	// file does not by itself cause the resulting executable to be covered by
	26	// the GNU General Public License. This exception does not however
	27	// invalidate any other reasons why the executable file might be covered by
	28	// the GNU General Public License.
	29
	30	/** @file ext/sso_string_base.h
	31	* This file is a GNU extension to the Standard C++ Library.
	32	* This is an internal header file, included by other library headers.
	33	* You should not attempt to use it directly.
	34	*/
	35
	36	#ifndef _SSO_STRING_BASE_H
	37	#define _SSO_STRING_BASE_H 1
	38
	39	namespace __gnu_cxx
	40	{
872d8fea PC	41	template<typename _CharT, typename _Traits, typename _Alloc>
872d8fea PC	42	class __sso_string_base
c54c1b2b	43	: protected __vstring_utility<_CharT, _Traits, _Alloc>
872d8fea	44	{
872d8fea PC	45	public:
	46	typedef _Traits traits_type;
	47	typedef typename _Traits::char_type value_type;
	48	typedef _Alloc allocator_type;
	49
	50	typedef typename __vstring_utility<_CharT, _Traits, _Alloc>::
	51	_CharT_alloc_type _CharT_alloc_type;
	52	typedef typename _CharT_alloc_type::size_type size_type;
	53
	54	// The maximum number of individual char_type elements of an
	55	// individual string is determined by _S_max_size. This is the
	56	// value that will be returned by max_size(). (Whereas npos
	57	// is the maximum number of bytes the allocator can allocate.)
	58	// If one was to divvy up the theoretical largest size string,
	59	// with a terminating character and m _CharT elements, it'd
	60	// look like this:
	61	// npos = m * sizeof(_CharT) + sizeof(_CharT)
	62	// Solving for m:
	63	// m = npos / sizeof(CharT) - 1
	64	// In addition, this implementation quarters this amount.
	65	static const size_type _S_max_size;
	66
	67	private:
	68	static const _CharT _S_terminal;
872d8fea	69
872d8fea PC	70	// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
	71	struct _Alloc_hider : _Alloc
	72	{
	73	_Alloc_hider(const _Alloc& __a, _CharT* __ptr)
	74	: _Alloc(__a), _M_p(__ptr) { }
	75
	76	_CharT* _M_p; // The actual data.
	77	};
	78
	79	// Data Members (private):
	80	_Alloc_hider _M_dataplus;
	81	size_type _M_string_length;
	82
c54c1b2b PC	83	enum { _S_local_capacity = 15 };
	84
	85	union
	86	{
	87	_CharT _M_local_data[_S_local_capacity + 1];
	88	size_type _M_allocated_capacity;
	89	};
	90
872d8fea PC	91	_CharT*
	92	_M_data(_CharT* __p)
	93	{ return (_M_dataplus._M_p = __p); }
	94
	95	void
	96	_M_length(size_type __length)
	97	{ _M_string_length = __length; }
	98
	99	void
	100	_M_capacity(size_type __capacity)
	101	{ _M_allocated_capacity = __capacity; }
	102
	103	bool
	104	_M_is_local() const
	105	{ return _M_data() == _M_local_data; }
	106
c54c1b2b PC	107	// Create & Destroy
	108	_CharT*
	109	_M_create(size_type&, size_type);
	110
	111	void
	112	_M_dispose() throw()
	113	{
	114	if (!_M_is_local())
	115	_M_destroy(_M_allocated_capacity + 1);
	116	}
	117
	118	void
	119	_M_destroy(size_type) throw();
	120
872d8fea PC	121	// _M_construct_aux is used to implement the 21.3.1 para 15 which
	122	// requires special behaviour if _InIter is an integral type
	123	template<class _InIterator>
	124	void
	125	_M_construct_aux(_InIterator __beg, _InIterator __end, __false_type)
	126	{
	127	typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
	128	_M_construct(__beg, __end, _Tag());
	129	}
	130
	131	template<class _InIterator>
	132	void
	133	_M_construct_aux(_InIterator __beg, _InIterator __end, __true_type)
	134	{ _M_construct(static_cast<size_type>(__beg),
	135	static_cast<value_type>(__end)); }
	136
	137	template<class _InIterator>
	138	void
	139	_M_construct(_InIterator __beg, _InIterator __end)
	140	{
	141	typedef typename std::__is_integer<_InIterator>::__type _Integral;
	142	_M_construct_aux(__beg, __end, _Integral());
	143	}
	144
	145	// For Input Iterators, used in istreambuf_iterators, etc.
	146	template<class _InIterator>
	147	void
	148	_M_construct(_InIterator __beg, _InIterator __end,
	149	std::input_iterator_tag);
	150
	151	// For forward_iterators up to random_access_iterators, used for
	152	// string::iterator, _CharT*, etc.
	153	template<class _FwdIterator>
	154	void
	155	_M_construct(_FwdIterator __beg, _FwdIterator __end,
	156	std::forward_iterator_tag);
	157
	158	void
	159	_M_construct(size_type __req, _CharT __c);
	160
	161	public:
	162	_CharT*
	163	_M_data() const
	164	{ return _M_dataplus._M_p; }
	165
	166	size_type
	167	_M_length() const
	168	{ return _M_string_length; }
	169
	170	size_type
	171	_M_capacity() const
	172	{
	173	return _M_is_local() ? size_type(_S_local_capacity)
	174	: _M_allocated_capacity;
	175	}
	176
	177	bool
	178	_M_is_shared() const
	179	{ return false; }
	180
	181	bool
	182	_M_is_leaked() const
	183	{ return false; }
	184
185	void
186	_M_set_sharable() { }
187
188	void
189	_M_set_leaked() { }
190
191	void
192	_M_set_length(size_type __n)
193	{
194	_M_length(__n);
195	// grrr. (per 21.3.4)
196	// You cannot leave those LWG people alone for a second.
197	traits_type::assign(_M_data()[__n], _S_terminal);
198	}
199
200	void
201	_M_leak() { }
202
203	__sso_string_base()
204	: _M_dataplus(_Alloc(), _M_local_data)
205	{ _M_set_length(0); }
206
207	__sso_string_base(const _Alloc& __a);
208
209	__sso_string_base(const __sso_string_base& __rcs);
210
211	__sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
212
213	template<typename _InputIterator>
214	__sso_string_base(_InputIterator __beg, _InputIterator __end,
215	const _Alloc& __a);
216
217	~__sso_string_base()
218	{ _M_dispose(); }
219
220	allocator_type
221	_M_get_allocator() const
222	{ return _M_dataplus; }
223
224	void
225	_M_swap(__sso_string_base& __rcs);
226
227	void
228	_M_assign(const __sso_string_base& __rcs);
229
230	void
231	_M_reserve(size_type __res);
232
233	void
234	_M_mutate(size_type __pos, size_type __len1, size_type __len2);
235	};
236
237	template<typename _CharT, typename _Traits, typename _Alloc>
238	void
239	__sso_string_base<_CharT, _Traits, _Alloc>::
240	_M_destroy(size_type __size) throw()
241	{ _CharT_alloc_type(_M_get_allocator()).deallocate(_M_data(), __size); }
242
243	template<typename _CharT, typename _Traits, typename _Alloc>
244	void
245	__sso_string_base<_CharT, _Traits, _Alloc>::
246	_M_swap(__sso_string_base& __rcs)
247	{
248	const bool __local = _M_is_local();
249	const bool __rcs_local = __rcs._M_is_local();
250
251	if (__local && __rcs_local)
252	{
253	_CharT __tmp_data[_S_local_capacity + 1];
254	const size_type __tmp_length = __rcs._M_length();
255	_S_copy(__tmp_data, __rcs._M_data(), __rcs._M_length() + 1);
256	__rcs._M_length(_M_length());
257	_S_copy(__rcs._M_data(), _M_data(), _M_length() + 1);
258	_M_length(__tmp_length);
259	_S_copy(_M_data(), __tmp_data, __tmp_length + 1);
260	}
261	else if (__local && !__rcs_local)
262	{
263	const size_type __tmp_capacity = __rcs._M_allocated_capacity;
264	const size_type __tmp_length = __rcs._M_length();
265	_CharT* __tmp_ptr = __rcs._M_data();
266	__rcs._M_data(__rcs._M_local_data);
267	_S_copy(__rcs._M_data(), _M_data(), _M_length() + 1);
268	__rcs._M_length(_M_length());
269	_M_data(__tmp_ptr);
270	_M_length(__tmp_length);
271	_M_capacity(__tmp_capacity);
272	}
273	else if (!__local && __rcs_local)
274	{
275	const size_type __tmp_capacity = _M_allocated_capacity;
276	const size_type __tmp_length = _M_length();
277	_CharT* __tmp_ptr = _M_data();
278	_M_data(_M_local_data);
279	_S_copy(_M_data(), __rcs._M_data(), __rcs._M_length() + 1);
280	_M_length(__rcs._M_length());
281	__rcs._M_data(__tmp_ptr);
282	__rcs._M_length(__tmp_length);
283	__rcs._M_capacity(__tmp_capacity);
284	}
285	else
286	{
287	const size_type __tmp_capacity = _M_allocated_capacity;
288	const size_type __tmp_length = _M_length();
289	_CharT* __tmp_ptr = _M_data();
290	_M_data(__rcs._M_data());
291	_M_length(__rcs._M_length());
292	_M_capacity(__rcs._M_allocated_capacity);
293	__rcs._M_data(__tmp_ptr);
294	__rcs._M_length(__tmp_length);
295	__rcs._M_capacity(__tmp_capacity);
296	}
297	}
298
299	template<typename _CharT, typename _Traits, typename _Alloc>
300	const typename __sso_string_base<_CharT, _Traits, _Alloc>::size_type
301	__sso_string_base<_CharT, _Traits, _Alloc>::
302	_S_max_size = ((static_cast<size_type>(-1) / sizeof(_CharT)) - 1) / 4;
303
304	template<typename _CharT, typename _Traits, typename _Alloc>
305	const _CharT
306	__sso_string_base<_CharT, _Traits, _Alloc>::_S_terminal = _CharT();
307
308	template<typename _CharT, typename _Traits, typename _Alloc>
309	_CharT*
310	__sso_string_base<_CharT, _Traits, _Alloc>::
311	_M_create(size_type& __capacity, size_type __old_capacity)
312	{
313	// _GLIBCXX_RESOLVE_LIB_DEFECTS
314	// 83. String::npos vs. string::max_size()
315	if (__capacity > _S_max_size)
316	std::__throw_length_error(__N("__sso_string_base::_M_create"));
317
318	// The below implements an exponential growth policy, necessary to
319	// meet amortized linear time requirements of the library: see
320	// http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
321	// It's active for allocations requiring an amount of memory above
322	// system pagesize. This is consistent with the requirements of the
323	// standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
324	if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
325	__capacity = 2 * __old_capacity;
326
327	// NB: Need an array of char_type[__capacity], plus a terminating
328	// null char_type() element.
329	return _CharT_alloc_type(_M_get_allocator()).allocate(__capacity + 1);
330	}
331
332	template<typename _CharT, typename _Traits, typename _Alloc>
333	__sso_string_base<_CharT, _Traits, _Alloc>::
334	__sso_string_base(const _Alloc& __a)
335	: _M_dataplus(__a, _M_local_data)
336	{ _M_set_length(0); }
337
338	template<typename _CharT, typename _Traits, typename _Alloc>
339	__sso_string_base<_CharT, _Traits, _Alloc>::
340	__sso_string_base(const __sso_string_base& __rcs)
341	: _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
342	{ _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
343
344	template<typename _CharT, typename _Traits, typename _Alloc>
345	__sso_string_base<_CharT, _Traits, _Alloc>::
346	__sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
347	: _M_dataplus(__a, _M_local_data)
348	{ _M_construct(__n, __c); }
349
350	template<typename _CharT, typename _Traits, typename _Alloc>
351	template<typename _InputIterator>
352	__sso_string_base<_CharT, _Traits, _Alloc>::
353	__sso_string_base(_InputIterator __beg, _InputIterator __end,
354	const _Alloc& __a)
355	: _M_dataplus(__a, _M_local_data)
356	{ _M_construct(__beg, __end); }
357
358	// NB: This is the special case for Input Iterators, used in
359	// istreambuf_iterators, etc.
360	// Input Iterators have a cost structure very different from
361	// pointers, calling for a different coding style.
362	template<typename _CharT, typename _Traits, typename _Alloc>
363	template<typename _InIterator>
364	void
365	__sso_string_base<_CharT, _Traits, _Alloc>::
366	_M_construct(_InIterator __beg, _InIterator __end,
367	std::input_iterator_tag)
368	{
369	// Avoid reallocation for common case.
370	size_type __len = 0;
371	size_type __capacity = size_type(_S_local_capacity);
372
373	while (__beg != __end && __len < __capacity)
374	{
375	_M_data()[__len++] = *__beg;
376	++__beg;
377	}
378
379	try
380	{
381	while (__beg != __end)
382	{
383	if (__len == __capacity)
384	{
385	// Allocate more space.
386	__capacity = __len + 1;
387	_CharT* __another = _M_create(__capacity, __len);
388	_S_copy(__another, _M_data(), __len);
389	_M_dispose();
390	_M_data(__another);
391	_M_capacity(__capacity);
392	}
393	_M_data()[__len++] = *__beg;
394	++__beg;
395	}
396	}
397	catch(...)
398	{
399	_M_dispose();
400	__throw_exception_again;
401	}
402
403	_M_set_length(__len);
404	}
405
406	template<typename _CharT, typename _Traits, typename _Alloc>
407	template <typename _InIterator>
408	void
409	__sso_string_base<_CharT, _Traits, _Alloc>::
410	_M_construct(_InIterator __beg, _InIterator __end,
411	std::forward_iterator_tag)
412	{
413	// NB: Not required, but considered best practice.
414	if (__builtin_expect(__is_null_p(__beg) && __beg != __end, 0))
415	std::__throw_logic_error(__N("__sso_string_base::"
416	"_M_construct NULL not valid"));
417
418	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
419
420	if (__dnew > size_type(_S_local_capacity))
421	{
422	_M_data(_M_create(__dnew, size_type(0)));
423	_M_capacity(__dnew);
424	}
425
426	// Check for out_of_range and length_error exceptions.
427	try
428	{ _S_copy_chars(_M_data(), __beg, __end); }
429	catch(...)
430	{
431	_M_dispose();
432	__throw_exception_again;
433	}
434
435	_M_set_length(__dnew);
436	}
437
438	template<typename _CharT, typename _Traits, typename _Alloc>
439	void
440	__sso_string_base<_CharT, _Traits, _Alloc>::
441	_M_construct(size_type __n, _CharT __c)
442	{
443	if (__n > size_type(_S_local_capacity))
444	{
445	_M_data(_M_create(__n, size_type(0)));
446	_M_capacity(__n);
447	}
448
449	if (__n)
450	_S_assign(_M_data(), __n, __c);
451
452	_M_set_length(__n);
453	}
454
455	template<typename _CharT, typename _Traits, typename _Alloc>
456	void
457	__sso_string_base<_CharT, _Traits, _Alloc>::
458	_M_assign(const __sso_string_base& __rcs)
459	{
460	if (this != &__rcs)
461	{
462	size_type __size = __rcs._M_length();
463
464	_CharT* __tmp = _M_local_data;
465	if (__size > size_type(_S_local_capacity))
466	__tmp = _M_create(__size, size_type(0));
467
468	_M_dispose();
469	_M_data(__tmp);
470
471	if (__size)
472	_S_copy(_M_data(), __rcs._M_data(), __size);
473
474	if (!_M_is_local())
475	_M_capacity(__size);
476
477	_M_set_length(__size);
478	}
479	}
480
481	template<typename _CharT, typename _Traits, typename _Alloc>
482	void
483	__sso_string_base<_CharT, _Traits, _Alloc>::
484	_M_reserve(size_type __res)
485	{
486	const size_type __capacity = _M_capacity();
487	if (__res != __capacity)
488	{
489	// Make sure we don't shrink below the current size.
490	if (__res < _M_length())
491	__res = _M_length();
492
493	if (__res > __capacity
494	\|\| __res > size_type(_S_local_capacity))
495	{
496	_CharT* __tmp = _M_create(__res, __capacity);
497	if (_M_length())
498	_S_copy(__tmp, _M_data(), _M_length());
499	_M_dispose();
500	_M_data(__tmp);
501	_M_capacity(__res);
502	}
503	else if (!_M_is_local())
504	{
505	const size_type __tmp_capacity = _M_allocated_capacity;
506	if (_M_length())
507	_S_copy(_M_local_data, _M_data(), _M_length());
508	_M_destroy(__tmp_capacity + 1);
509	_M_data(_M_local_data);
510	}
511
512	_M_set_length(_M_length());
513	}
514	}
515
516	template<typename _CharT, typename _Traits, typename _Alloc>
517	void
518	__sso_string_base<_CharT, _Traits, _Alloc>::
519	_M_mutate(size_type __pos, size_type __len1, size_type __len2)
520	{
521	const size_type __old_size = _M_length();
522	const size_type __new_size = __old_size + __len2 - __len1;
523	const size_type __how_much = __old_size - __pos - __len1;
524
525	if (__new_size > _M_capacity())
526	{
527	// Must reallocate.
528	size_type __new_capacity = __new_size;
529	_CharT* __r = _M_create(__new_capacity, _M_capacity());
530
531	if (__pos)
532	_S_copy(__r, _M_data(), __pos);
533	if (__how_much)
534	_S_copy(__r + __pos + __len2,
535	_M_data() + __pos + __len1, __how_much);
536
537	_M_dispose();
538	_M_data(__r);
539	_M_capacity(__new_capacity);
540	}
541	else if (__how_much && __len1 != __len2)
542	{
543	// Work in-place.
544	_S_move(_M_data() + __pos + __len2,
545	_M_data() + __pos + __len1, __how_much);
546	}
547
548	_M_set_length(__new_size);
549	}
550	} // namespace __gnu_cxx
551
552	#endif /* _SSO_STRING_BASE_H */