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

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

// Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file ext/sso_string_base.h
 *  This 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_aux_2(static_cast<size_type>(__beg), __end); }

      void
      _M_construct_aux_2(size_type __req, _CharT __c)
      { _M_construct(__req, __c); }

      template<typename _InIterator>
        void
        _M_construct(_InIterator __beg, _InIterator __end)
	{
	  typedef typename std::__is_integer<_InIterator>::__type _Integral;
	  _M_construct_aux(__beg, __end, _Integral());
        }

      // For Input Iterators, used in istreambuf_iterators, etc.
      template<typename _InIterator>
        void
        _M_construct(_InIterator __beg, _InIterator __end,
		     std::input_iterator_tag);
      
      // For forward_iterators up to random_access_iterators, used for
      // string::iterator, _CharT*, etc.
      template<typename _FwdIterator>
        void
        _M_construct(_FwdIterator __beg, _FwdIterator __end,
		     std::forward_iterator_tag);

      void
      _M_construct(size_type __req, _CharT __c);

    public:
      size_type
      _M_max_size() const
      { return (_M_get_allocator().max_size() - 1) / 2; }

      _CharT*
      _M_data() const
      { return _M_dataplus._M_p; }

      size_type
      _M_length() const
      { return _M_string_length; }

      size_type
      _M_capacity() const
      {
	return _M_is_local() ? size_type(_S_local_capacity)
	                     : _M_allocated_capacity; 
      }

      bool
      _M_is_shared() const
      { return false; }

      void
      _M_set_leaked() { }

      void
      _M_leak() { }

      void
      _M_set_length(size_type __n)
      {
	_M_length(__n);
	traits_type::assign(_M_data()[__n], _CharT());
      }

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

      __sso_string_base(const _Alloc& __a);

      __sso_string_base(const __sso_string_base& __rcs);

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      __sso_string_base(__sso_string_base&& __rcs);
#endif

      __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);

      template<typename _InputIterator>
        __sso_string_base(_InputIterator __beg, _InputIterator __end,
			  const _Alloc& __a);

      ~__sso_string_base()
      { _M_dispose(); }

      _CharT_alloc_type&
      _M_get_allocator()
      { return _M_dataplus; }

      const _CharT_alloc_type&
      _M_get_allocator() const
      { return _M_dataplus; }

      void
      _M_swap(__sso_string_base& __rcs);

      void
      _M_assign(const __sso_string_base& __rcs);

      void
      _M_reserve(size_type __res);

      void
      _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
		size_type __len2);

      void
      _M_erase(size_type __pos, size_type __n);

      void
      _M_clear()
      { _M_set_length(0); }

      bool
      _M_compare(const __sso_string_base&) const
      { return false; }
    };

  template<typename _CharT, typename _Traits, typename _Alloc>
    void
    __sso_string_base<_CharT, _Traits, _Alloc>::
    _M_swap(__sso_string_base& __rcs)
    {
      // _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()); }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
  template<typename _CharT, typename _Traits, typename _Alloc>
    __sso_string_base<_CharT, _Traits, _Alloc>::
    __sso_string_base(__sso_string_base&& __rcs)
    : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
    {
      if (__rcs._M_is_local())
	{
	  if (__rcs._M_length())
	    traits_type::copy(_M_local_data, __rcs._M_local_data,
			      _S_local_capacity + 1);
	}
      else
	{
	  _M_data(__rcs._M_data());
	  _M_capacity(__rcs._M_allocated_capacity);
	}

      _M_length(__rcs._M_length());
      __rcs._M_length(0);
      __rcs._M_data(__rcs._M_local_data);
    }
#endif

  template<typename _CharT, typename _Traits, typename _Alloc>
    __sso_string_base<_CharT, _Traits, _Alloc>::
    __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
    : _M_dataplus(__a, _M_local_data)
    { _M_construct(__n, __c); }

  template<typename _CharT, typename _Traits, typename _Alloc>
    template<typename _InputIterator>
    __sso_string_base<_CharT, _Traits, _Alloc>::
    __sso_string_base(_InputIterator __beg, _InputIterator __end,
		      const _Alloc& __a)
    : _M_dataplus(__a, _M_local_data)
    { _M_construct(__beg, __end); }

  // NB: This is the special case for Input Iterators, used in
  // istreambuf_iterators, etc.
  // Input Iterators have a cost structure very different from
  // pointers, calling for a different coding style.
  template<typename _CharT, typename _Traits, typename _Alloc>
    template<typename _InIterator>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_construct(_InIterator __beg, _InIterator __end,
		   std::input_iterator_tag)
      {
	size_type __len = 0;
	size_type __capacity = size_type(_S_local_capacity);

	while (__beg != __end && __len < __capacity)
	  {
	    _M_data()[__len++] = *__beg;
	    ++__beg;
	  }
	
	__try
	  {
	    while (__beg != __end)
	      {
		if (__len == __capacity)
		  {
		    // Allocate more space.
		    __capacity = __len + 1;
		    _CharT* __another = _M_create(__capacity, __len);
		    _S_copy(__another, _M_data(), __len);
		    _M_dispose();
		    _M_data(__another);
		    _M_capacity(__capacity);
		  }
		_M_data()[__len++] = *__beg;
		++__beg;
	      }
	  }
	__catch(...)
	  {
	    _M_dispose();
	    __throw_exception_again;
	  }

	_M_set_length(__len);
      }

  template<typename _CharT, typename _Traits, typename _Alloc>
    template<typename _InIterator>
      void
      __sso_string_base<_CharT, _Traits, _Alloc>::
      _M_construct(_InIterator __beg, _InIterator __end,
		   std::forward_iterator_tag)
      {
	// NB: Not required, but considered best practice.
	if (__is_null_pointer(__beg) && __beg != __end)
	  std::__throw_logic_error(__N("__sso_string_base::"
				       "_M_construct NULL not valid"));

	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));

	if (__dnew > size_type(_S_local_capacity))
	  {
	    _M_data(_M_create(__dnew, size_type(0)));
	    _M_capacity(__dnew);
	  }

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