[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 __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:
      // 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.
      enum { _S_max_size = (((static_cast<size_type>(-1)
			      / sizeof(_CharT)) - 1) / 4) };

      // Data Members (private):
      typename _Util_Base::template _Alloc_hider<_Alloc>    _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() 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 _InIterator 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:
      size_type
      _M_max_size() const
      { return size_type(_S_max_size); }

      _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(_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)
    {
      // NB: Implement Option 3 of DR 431 (see N1599).
      _M_dataplus._M_alloc_swap(__rcs._M_dataplus);

      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 > size_type(_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.
      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)
      {
	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(_S_is_null_pointer(__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
7697e6c6 PC	50	typedef __vstring_utility<_CharT, _Traits, _Alloc> _Util_Base;
7697e6c6 PC	51	typedef typename _Util_Base::_CharT_alloc_type _CharT_alloc_type;
872d8fea PC	52	typedef typename _CharT_alloc_type::size_type size_type;
872d8fea PC	53
486516b6	54	private:
872d8fea PC	55	// The maximum number of individual char_type elements of an
	56	// individual string is determined by _S_max_size. This is the
	57	// value that will be returned by max_size(). (Whereas npos
	58	// is the maximum number of bytes the allocator can allocate.)
	59	// If one was to divvy up the theoretical largest size string,
	60	// with a terminating character and m _CharT elements, it'd
	61	// look like this:
	62	// npos = m * sizeof(_CharT) + sizeof(_CharT)
	63	// Solving for m:
486516b6	64	// m = npos / sizeof(_CharT) - 1
872d8fea	65	// In addition, this implementation quarters this amount.
486516b6 PC	66	enum { _S_max_size = (((static_cast<size_type>(-1)
486516b6 PC	67	/ sizeof(_CharT)) - 1) / 4) };
872d8fea	68
872d8fea	69	// Data Members (private):
7697e6c6 PC	70	typename _Util_Base::template _Alloc_hider<_Alloc> _M_dataplus;
7697e6c6 PC	71	size_type _M_string_length;
872d8fea	72
c54c1b2b PC	73	enum { _S_local_capacity = 15 };
	74
	75	union
	76	{
	77	_CharT _M_local_data[_S_local_capacity + 1];
	78	size_type _M_allocated_capacity;
	79	};
	80
7697e6c6	81	void
872d8fea	82	_M_data(_CharT* __p)
7697e6c6	83	{ _M_dataplus._M_p = __p; }
872d8fea PC	84
	85	void
	86	_M_length(size_type __length)
	87	{ _M_string_length = __length; }
	88
	89	void
	90	_M_capacity(size_type __capacity)
	91	{ _M_allocated_capacity = __capacity; }
	92
	93	bool
	94	_M_is_local() const
	95	{ return _M_data() == _M_local_data; }
	96
c54c1b2b PC	97	// Create & Destroy
	98	_CharT*
	99	_M_create(size_type&, size_type);
	100
	101	void
	102	_M_dispose() throw()
	103	{
	104	if (!_M_is_local())
	105	_M_destroy(_M_allocated_capacity + 1);
	106	}
	107
	108	void
	109	_M_destroy(size_type) throw();
	110
872d8fea	111	// _M_construct_aux is used to implement the 21.3.1 para 15 which
7697e6c6	112	// requires special behaviour if _InIterator is an integral type
872d8fea PC	113	template<class _InIterator>
	114	void
	115	_M_construct_aux(_InIterator __beg, _InIterator __end, __false_type)
	116	{
	117	typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
	118	_M_construct(__beg, __end, _Tag());
	119	}
	120
	121	template<class _InIterator>
	122	void
	123	_M_construct_aux(_InIterator __beg, _InIterator __end, __true_type)
	124	{ _M_construct(static_cast<size_type>(__beg),
	125	static_cast<value_type>(__end)); }
	126
	127	template<class _InIterator>
	128	void
	129	_M_construct(_InIterator __beg, _InIterator __end)
	130	{
	131	typedef typename std::__is_integer<_InIterator>::__type _Integral;
	132	_M_construct_aux(__beg, __end, _Integral());
	133	}
	134
	135	// For Input Iterators, used in istreambuf_iterators, etc.
	136	template<class _InIterator>
	137	void
	138	_M_construct(_InIterator __beg, _InIterator __end,
	139	std::input_iterator_tag);
	140
	141	// For forward_iterators up to random_access_iterators, used for
	142	// string::iterator, _CharT*, etc.
	143	template<class _FwdIterator>
	144	void
	145	_M_construct(_FwdIterator __beg, _FwdIterator __end,
	146	std::forward_iterator_tag);
	147
	148	void
	149	_M_construct(size_type __req, _CharT __c);
	150
	151	public:
486516b6 PC	152	size_type
	153	_M_max_size() const
	154	{ return size_type(_S_max_size); }
	155
872d8fea PC	156	_CharT*
	157	_M_data() const
	158	{ return _M_dataplus._M_p; }
	159
	160	size_type
	161	_M_length() const
	162	{ return _M_string_length; }
	163
	164	size_type
	165	_M_capacity() const
	166	{
	167	return _M_is_local() ? size_type(_S_local_capacity)
	168	: _M_allocated_capacity;
	169	}
	170
	171	bool
	172	_M_is_shared() const
	173	{ return false; }
	174
872d8fea	175	void
7697e6c6	176	_M_set_leaked() { }
872d8fea PC	177
872d8fea PC	178	void
7697e6c6	179	_M_leak() { }
872d8fea PC	180
	181	void
	182	_M_set_length(size_type __n)
	183	{
	184	_M_length(__n);
486516b6	185	traits_type::assign(_M_data()[__n], _CharT());
872d8fea PC	186	}
872d8fea PC	187
872d8fea PC	188	__sso_string_base()
	189	: _M_dataplus(_Alloc(), _M_local_data)
	190	{ _M_set_length(0); }
	191
	192	__sso_string_base(const _Alloc& __a);
	193
	194	__sso_string_base(const __sso_string_base& __rcs);
	195
	196	__sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
	197
	198	template<typename _InputIterator>
	199	__sso_string_base(_InputIterator __beg, _InputIterator __end,
	200	const _Alloc& __a);
	201
	202	~__sso_string_base()
	203	{ _M_dispose(); }
	204
	205	allocator_type
	206	_M_get_allocator() const
	207	{ return _M_dataplus; }
	208
	209	void
	210	_M_swap(__sso_string_base& __rcs);
	211
	212	void
	213	_M_assign(const __sso_string_base& __rcs);
	214
	215	void
	216	_M_reserve(size_type __res);
	217
	218	void
	219	_M_mutate(size_type __pos, size_type __len1, size_type __len2);
	220	};
	221
	222	template<typename _CharT, typename _Traits, typename _Alloc>
	223	void
	224	__sso_string_base<_CharT, _Traits, _Alloc>::
	225	_M_destroy(size_type __size) throw()
	226	{ _CharT_alloc_type(_M_get_allocator()).deallocate(_M_data(), __size); }
	227
	228	template<typename _CharT, typename _Traits, typename _Alloc>
	229	void
	230	__sso_string_base<_CharT, _Traits, _Alloc>::
	231	_M_swap(__sso_string_base& __rcs)
	232	{
7697e6c6 PC	233	// NB: Implement Option 3 of DR 431 (see N1599).
	234	_M_dataplus._M_alloc_swap(__rcs._M_dataplus);
	235
7058c3be PC	236	if (_M_is_local())
	237	if (__rcs._M_is_local())
	238	{
	239	if (_M_length() && __rcs._M_length())
	240	{
	241	_CharT __tmp_data[_S_local_capacity + 1];
	242	traits_type::copy(__tmp_data, __rcs._M_local_data,
f9c4ee6d	243	_S_local_capacity + 1);
7058c3be	244	traits_type::copy(__rcs._M_local_data, _M_local_data,
f9c4ee6d	245	_S_local_capacity + 1);
7058c3be	246	traits_type::copy(_M_local_data, __tmp_data,
f9c4ee6d	247	_S_local_capacity + 1);
7058c3be PC	248	}
	249	else if (__rcs._M_length())
	250	{
	251	traits_type::copy(_M_local_data, __rcs._M_local_data,
f9c4ee6d PC	252	_S_local_capacity + 1);
	253	_M_length(__rcs._M_length());
	254	__rcs._M_set_length(0);
	255	return;
7058c3be PC	256	}
	257	else if (_M_length())
	258	{
	259	traits_type::copy(__rcs._M_local_data, _M_local_data,
f9c4ee6d PC	260	_S_local_capacity + 1);
	261	__rcs._M_length(_M_length());
	262	_M_set_length(0);
	263	return;
7058c3be PC	264	}
	265	}
	266	else
	267	{
	268	const size_type __tmp_capacity = __rcs._M_allocated_capacity;
f9c4ee6d PC	269	traits_type::copy(__rcs._M_local_data, _M_local_data,
f9c4ee6d PC	270	_S_local_capacity + 1);
7058c3be PC	271	_M_data(__rcs._M_data());
	272	__rcs._M_data(__rcs._M_local_data);
	273	_M_capacity(__tmp_capacity);
	274	}
872d8fea PC	275	else
	276	{
	277	const size_type __tmp_capacity = _M_allocated_capacity;
7058c3be PC	278	if (__rcs._M_is_local())
7058c3be PC	279	{
f9c4ee6d PC	280	traits_type::copy(_M_local_data, __rcs._M_local_data,
f9c4ee6d PC	281	_S_local_capacity + 1);
7058c3be PC	282	__rcs._M_data(_M_data());
	283	_M_data(_M_local_data);
	284	}
	285	else
	286	{
	287	_CharT* __tmp_ptr = _M_data();
	288	_M_data(__rcs._M_data());
	289	__rcs._M_data(__tmp_ptr);
	290	_M_capacity(__rcs._M_allocated_capacity);
	291	}
872d8fea PC	292	__rcs._M_capacity(__tmp_capacity);
872d8fea PC	293	}
7058c3be PC	294
	295	const size_type __tmp_length = _M_length();
	296	_M_length(__rcs._M_length());
	297	__rcs._M_length(__tmp_length);
872d8fea PC	298	}
872d8fea PC	299
872d8fea PC	300	template<typename _CharT, typename _Traits, typename _Alloc>
	301	_CharT*
	302	__sso_string_base<_CharT, _Traits, _Alloc>::
	303	_M_create(size_type& __capacity, size_type __old_capacity)
	304	{
	305	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	306	// 83. String::npos vs. string::max_size()
486516b6	307	if (__capacity > size_type(_S_max_size))
872d8fea PC	308	std::__throw_length_error(__N("__sso_string_base::_M_create"));
	309
	310	// The below implements an exponential growth policy, necessary to
	311	// meet amortized linear time requirements of the library: see
	312	// http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
872d8fea PC	313	if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
	314	__capacity = 2 * __old_capacity;
	315
	316	// NB: Need an array of char_type[__capacity], plus a terminating
	317	// null char_type() element.
	318	return _CharT_alloc_type(_M_get_allocator()).allocate(__capacity + 1);
	319	}
	320
	321	template<typename _CharT, typename _Traits, typename _Alloc>
	322	__sso_string_base<_CharT, _Traits, _Alloc>::
	323	__sso_string_base(const _Alloc& __a)
	324	: _M_dataplus(__a, _M_local_data)
	325	{ _M_set_length(0); }
	326
	327	template<typename _CharT, typename _Traits, typename _Alloc>
	328	__sso_string_base<_CharT, _Traits, _Alloc>::
	329	__sso_string_base(const __sso_string_base& __rcs)
	330	: _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
	331	{ _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
	332
	333	template<typename _CharT, typename _Traits, typename _Alloc>
	334	__sso_string_base<_CharT, _Traits, _Alloc>::
	335	__sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
	336	: _M_dataplus(__a, _M_local_data)
	337	{ _M_construct(__n, __c); }
	338
	339	template<typename _CharT, typename _Traits, typename _Alloc>
	340	template<typename _InputIterator>
	341	__sso_string_base<_CharT, _Traits, _Alloc>::
	342	__sso_string_base(_InputIterator __beg, _InputIterator __end,
	343	const _Alloc& __a)
	344	: _M_dataplus(__a, _M_local_data)
	345	{ _M_construct(__beg, __end); }
	346
	347	// NB: This is the special case for Input Iterators, used in
	348	// istreambuf_iterators, etc.
	349	// Input Iterators have a cost structure very different from
	350	// pointers, calling for a different coding style.
	351	template<typename _CharT, typename _Traits, typename _Alloc>
	352	template<typename _InIterator>
	353	void
	354	__sso_string_base<_CharT, _Traits, _Alloc>::
	355	_M_construct(_InIterator __beg, _InIterator __end,
	356	std::input_iterator_tag)
	357	{
872d8fea PC	358	size_type __len = 0;
	359	size_type __capacity = size_type(_S_local_capacity);
	360
	361	while (__beg != __end && __len < __capacity)
	362	{
	363	_M_data()[__len++] = *__beg;
	364	++__beg;
	365	}
	366
	367	try
	368	{
	369	while (__beg != __end)
	370	{
	371	if (__len == __capacity)
	372	{
	373	// Allocate more space.
	374	__capacity = __len + 1;
	375	_CharT* __another = _M_create(__capacity, __len);
	376	_S_copy(__another, _M_data(), __len);
	377	_M_dispose();
	378	_M_data(__another);
	379	_M_capacity(__capacity);
	380	}
	381	_M_data()[__len++] = *__beg;
	382	++__beg;
	383	}
	384	}
	385	catch(...)
	386	{
	387	_M_dispose();
	388	__throw_exception_again;
	389	}
	390
	391	_M_set_length(__len);
	392	}
	393
	394	template<typename _CharT, typename _Traits, typename _Alloc>
	395	template <typename _InIterator>
	396	void
	397	__sso_string_base<_CharT, _Traits, _Alloc>::
	398	_M_construct(_InIterator __beg, _InIterator __end,
	399	std::forward_iterator_tag)
	400	{
	401	// NB: Not required, but considered best practice.
7697e6c6	402	if (__builtin_expect(_S_is_null_pointer(__beg) && __beg != __end, 0))
872d8fea PC	403	std::__throw_logic_error(__N("__sso_string_base::"
	404	"_M_construct NULL not valid"));
	405
	406	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
	407
	408	if (__dnew > size_type(_S_local_capacity))
	409	{
	410	_M_data(_M_create(__dnew, size_type(0)));
	411	_M_capacity(__dnew);
	412	}
	413
	414	// Check for out_of_range and length_error exceptions.
	415	try
	416	{ _S_copy_chars(_M_data(), __beg, __end); }
	417	catch(...)
	418	{
	419	_M_dispose();
	420	__throw_exception_again;
	421	}
	422
	423	_M_set_length(__dnew);
	424	}
	425
	426	template<typename _CharT, typename _Traits, typename _Alloc>
	427	void
	428	__sso_string_base<_CharT, _Traits, _Alloc>::
	429	_M_construct(size_type __n, _CharT __c)
	430	{
	431	if (__n > size_type(_S_local_capacity))
	432	{
	433	_M_data(_M_create(__n, size_type(0)));
	434	_M_capacity(__n);
	435	}
	436
	437	if (__n)
	438	_S_assign(_M_data(), __n, __c);
	439
	440	_M_set_length(__n);
	441	}
	442
	443	template<typename _CharT, typename _Traits, typename _Alloc>
	444	void
	445	__sso_string_base<_CharT, _Traits, _Alloc>::
	446	_M_assign(const __sso_string_base& __rcs)
	447	{
	448	if (this != &__rcs)
	449	{
	450	size_type __size = __rcs._M_length();
	451
	452	_CharT* __tmp = _M_local_data;
	453	if (__size > size_type(_S_local_capacity))
	454	__tmp = _M_create(__size, size_type(0));
	455
	456	_M_dispose();
	457	_M_data(__tmp);
	458
	459	if (__size)
	460	_S_copy(_M_data(), __rcs._M_data(), __size);
	461
	462	if (!_M_is_local())
	463	_M_capacity(__size);
	464
	465	_M_set_length(__size);
	466	}
467	}
468
469	template<typename _CharT, typename _Traits, typename _Alloc>
470	void
471	__sso_string_base<_CharT, _Traits, _Alloc>::
472	_M_reserve(size_type __res)
473	{
474	const size_type __capacity = _M_capacity();
475	if (__res != __capacity)
476	{
477	// Make sure we don't shrink below the current size.
478	if (__res < _M_length())
479	__res = _M_length();
480
481	if (__res > __capacity
482	\|\| __res > size_type(_S_local_capacity))
483	{
484	_CharT* __tmp = _M_create(__res, __capacity);
485	if (_M_length())
486	_S_copy(__tmp, _M_data(), _M_length());
487	_M_dispose();
488	_M_data(__tmp);
489	_M_capacity(__res);
490	}
491	else if (!_M_is_local())
492	{
493	const size_type __tmp_capacity = _M_allocated_capacity;
494	if (_M_length())
495	_S_copy(_M_local_data, _M_data(), _M_length());
496	_M_destroy(__tmp_capacity + 1);
497	_M_data(_M_local_data);
498	}
499
500	_M_set_length(_M_length());
501	}
502	}
503
504	template<typename _CharT, typename _Traits, typename _Alloc>
505	void
506	__sso_string_base<_CharT, _Traits, _Alloc>::
507	_M_mutate(size_type __pos, size_type __len1, size_type __len2)
508	{
509	const size_type __old_size = _M_length();
510	const size_type __new_size = __old_size + __len2 - __len1;
511	const size_type __how_much = __old_size - __pos - __len1;
512
513	if (__new_size > _M_capacity())
514	{
515	// Must reallocate.
516	size_type __new_capacity = __new_size;
517	_CharT* __r = _M_create(__new_capacity, _M_capacity());
518
519	if (__pos)
520	_S_copy(__r, _M_data(), __pos);
521	if (__how_much)
522	_S_copy(__r + __pos + __len2,
523	_M_data() + __pos + __len1, __how_much);
524
525	_M_dispose();
526	_M_data(__r);
527	_M_capacity(__new_capacity);
528	}
529	else if (__how_much && __len1 != __len2)
530	{
531	// Work in-place.
532	_S_move(_M_data() + __pos + __len2,
533	_M_data() + __pos + __len1, __how_much);
534	}
535
536	_M_set_length(__new_size);
537	}
538	} // namespace __gnu_cxx
539
540	#endif /* _SSO_STRING_BASE_H */