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

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

// Copyright (C) 2005, 2006, 2007 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

_GLIBCXX_BEGIN_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 __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(static_cast<size_type>(__beg), __end); }

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

      _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)
    {
      // _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()); }

  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(__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)
	{
	  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)
	    _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);
	      _S_copy(__tmp, _M_data(), _M_length() + 1);
	      _M_dispose();
	      _M_data(__tmp);
	      _M_capacity(__res);
	    }
	  else if (!_M_is_local())
	    {
	      _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,
	      const 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)
	_S_copy(__r, _M_data(), __pos);
      if (__s && __len2)
	_S_copy(__r + __pos, __s, __len2);
      if (__how_much)
	_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)
	_S_move(_M_data() + __pos, _M_data() + __pos + __n,
		__how_much);

      _M_set_length(_M_length() - __n);
    }

_GLIBCXX_END_NAMESPACE

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