[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(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(_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 (__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
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 PC	108	_M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
25959e29 PC	109	{ _M_construct(static_cast<size_type>(__beg), __end); }
872d8fea	110
b6cb8dc2	111	template<typename _InIterator>
872d8fea PC	112	void
	113	_M_construct(_InIterator __beg, _InIterator __end)
	114	{
	115	typedef typename std::__is_integer<_InIterator>::__type _Integral;
	116	_M_construct_aux(__beg, __end, _Integral());
	117	}
	118
	119	// For Input Iterators, used in istreambuf_iterators, etc.
b6cb8dc2	120	template<typename _InIterator>
872d8fea PC	121	void
	122	_M_construct(_InIterator __beg, _InIterator __end,
	123	std::input_iterator_tag);
	124
	125	// For forward_iterators up to random_access_iterators, used for
	126	// string::iterator, _CharT*, etc.
b6cb8dc2	127	template<typename _FwdIterator>
872d8fea PC	128	void
	129	_M_construct(_FwdIterator __beg, _FwdIterator __end,
	130	std::forward_iterator_tag);
	131
	132	void
	133	_M_construct(size_type __req, _CharT __c);
	134
	135	public:
486516b6 PC	136	size_type
486516b6 PC	137	_M_max_size() const
6c331f73	138	{ return (_M_get_allocator().max_size() - 1) / 2; }
486516b6	139
872d8fea PC	140	_CharT*
	141	_M_data() const
	142	{ return _M_dataplus._M_p; }
	143
	144	size_type
	145	_M_length() const
	146	{ return _M_string_length; }
	147
	148	size_type
	149	_M_capacity() const
	150	{
	151	return _M_is_local() ? size_type(_S_local_capacity)
	152	: _M_allocated_capacity;
	153	}
	154
	155	bool
	156	_M_is_shared() const
	157	{ return false; }
	158
872d8fea	159	void
7697e6c6	160	_M_set_leaked() { }
872d8fea PC	161
872d8fea PC	162	void
7697e6c6	163	_M_leak() { }
872d8fea PC	164
	165	void
	166	_M_set_length(size_type __n)
	167	{
	168	_M_length(__n);
486516b6	169	traits_type::assign(_M_data()[__n], _CharT());
872d8fea PC	170	}
872d8fea PC	171
872d8fea	172	__sso_string_base()
053cc380	173	: _M_dataplus(_M_local_data)
872d8fea PC	174	{ _M_set_length(0); }
	175
	176	__sso_string_base(const _Alloc& __a);
	177
	178	__sso_string_base(const __sso_string_base& __rcs);
	179
053cc380 PC	180	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	181	__sso_string_base(__sso_string_base&& __rcs);
	182	#endif
	183
872d8fea PC	184	__sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
	185
	186	template<typename _InputIterator>
	187	__sso_string_base(_InputIterator __beg, _InputIterator __end,
	188	const _Alloc& __a);
	189
	190	~__sso_string_base()
	191	{ _M_dispose(); }
	192
f7ace77f	193	_CharT_alloc_type&
cf882919 PC	194	_M_get_allocator()
	195	{ return _M_dataplus; }
	196
f7ace77f	197	const _CharT_alloc_type&
872d8fea PC	198	_M_get_allocator() const
	199	{ return _M_dataplus; }
	200
	201	void
	202	_M_swap(__sso_string_base& __rcs);
	203
	204	void
	205	_M_assign(const __sso_string_base& __rcs);
	206
	207	void
	208	_M_reserve(size_type __res);
	209
	210	void
cf882919 PC	211	_M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
	212	size_type __len2);
	213
	214	void
	215	_M_erase(size_type __pos, size_type __n);
b6105bf2	216
7867a3f7 PC	217	void
	218	_M_clear()
	219	{ _M_set_length(0); }
	220
b6105bf2 PC	221	bool
	222	_M_compare(const __sso_string_base&) const
	223	{ return false; }
872d8fea PC	224	};
872d8fea PC	225
872d8fea PC	226	template<typename _CharT, typename _Traits, typename _Alloc>
	227	void
	228	__sso_string_base<_CharT, _Traits, _Alloc>::
	229	_M_swap(__sso_string_base& __rcs)
	230	{
f7ace77f PC	231	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	232	// 431. Swapping containers with unequal allocators.
	233	std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(),
	234	__rcs._M_get_allocator());
7697e6c6	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()
3ad70747	307	if (__capacity > _M_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	313	if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
7aa6ba76 PC	314	{
7aa6ba76 PC	315	__capacity = 2 * __old_capacity;
3ad70747 PC	316	// Never allocate a string bigger than max_size.
	317	if (__capacity > _M_max_size())
	318	__capacity = _M_max_size();
7aa6ba76	319	}
872d8fea PC	320
	321	// NB: Need an array of char_type[__capacity], plus a terminating
	322	// null char_type() element.
6c331f73	323	return _M_get_allocator().allocate(__capacity + 1);
872d8fea PC	324	}
	325
	326	template<typename _CharT, typename _Traits, typename _Alloc>
	327	__sso_string_base<_CharT, _Traits, _Alloc>::
	328	__sso_string_base(const _Alloc& __a)
	329	: _M_dataplus(__a, _M_local_data)
	330	{ _M_set_length(0); }
	331
	332	template<typename _CharT, typename _Traits, typename _Alloc>
	333	__sso_string_base<_CharT, _Traits, _Alloc>::
	334	__sso_string_base(const __sso_string_base& __rcs)
	335	: _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
	336	{ _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
	337
053cc380 PC	338	#ifdef __GXX_EXPERIMENTAL_CXX0X__
	339	template<typename _CharT, typename _Traits, typename _Alloc>
	340	__sso_string_base<_CharT, _Traits, _Alloc>::
	341	__sso_string_base(__sso_string_base&& __rcs)
	342	: _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
	343	{
	344	if (__rcs._M_is_local())
	345	{
	346	if (__rcs._M_length())
	347	traits_type::copy(_M_local_data, __rcs._M_local_data,
	348	_S_local_capacity + 1);
	349	}
	350	else
	351	{
	352	_M_data(__rcs._M_data());
	353	_M_capacity(__rcs._M_allocated_capacity);
	354	}
	355
	356	_M_length(__rcs._M_length());
	357	__rcs._M_length(0);
	358	__rcs._M_data(__rcs._M_local_data);
	359	}
	360	#endif
	361
872d8fea PC	362	template<typename _CharT, typename _Traits, typename _Alloc>
	363	__sso_string_base<_CharT, _Traits, _Alloc>::
	364	__sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
	365	: _M_dataplus(__a, _M_local_data)
	366	{ _M_construct(__n, __c); }
	367
	368	template<typename _CharT, typename _Traits, typename _Alloc>
	369	template<typename _InputIterator>
	370	__sso_string_base<_CharT, _Traits, _Alloc>::
	371	__sso_string_base(_InputIterator __beg, _InputIterator __end,
	372	const _Alloc& __a)
	373	: _M_dataplus(__a, _M_local_data)
	374	{ _M_construct(__beg, __end); }
	375
	376	// NB: This is the special case for Input Iterators, used in
	377	// istreambuf_iterators, etc.
	378	// Input Iterators have a cost structure very different from
	379	// pointers, calling for a different coding style.
	380	template<typename _CharT, typename _Traits, typename _Alloc>
	381	template<typename _InIterator>
	382	void
	383	__sso_string_base<_CharT, _Traits, _Alloc>::
	384	_M_construct(_InIterator __beg, _InIterator __end,
	385	std::input_iterator_tag)
	386	{
872d8fea PC	387	size_type __len = 0;
	388	size_type __capacity = size_type(_S_local_capacity);
	389
	390	while (__beg != __end && __len < __capacity)
	391	{
	392	_M_data()[__len++] = *__beg;
	393	++__beg;
	394	}
	395
bc2631e0	396	__try
872d8fea PC	397	{
	398	while (__beg != __end)
	399	{
	400	if (__len == __capacity)
	401	{
	402	// Allocate more space.
	403	__capacity = __len + 1;
	404	_CharT* __another = _M_create(__capacity, __len);
	405	_S_copy(__another, _M_data(), __len);
	406	_M_dispose();
	407	_M_data(__another);
	408	_M_capacity(__capacity);
	409	}
	410	_M_data()[__len++] = *__beg;
	411	++__beg;
	412	}
	413	}
bc2631e0	414	__catch(...)
872d8fea PC	415	{
	416	_M_dispose();
	417	__throw_exception_again;
	418	}
	419
	420	_M_set_length(__len);
	421	}
	422
	423	template<typename _CharT, typename _Traits, typename _Alloc>
b6cb8dc2	424	template<typename _InIterator>
872d8fea PC	425	void
	426	__sso_string_base<_CharT, _Traits, _Alloc>::
	427	_M_construct(_InIterator __beg, _InIterator __end,
	428	std::forward_iterator_tag)
	429	{
	430	// NB: Not required, but considered best practice.
11202768	431	if (__builtin_expect(__is_null_pointer(__beg) && __beg != __end, 0))
872d8fea PC	432	std::__throw_logic_error(__N("__sso_string_base::"
	433	"_M_construct NULL not valid"));
	434
	435	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
	436
	437	if (__dnew > size_type(_S_local_capacity))
	438	{
	439	_M_data(_M_create(__dnew, size_type(0)));
	440	_M_capacity(__dnew);
	441	}
	442
	443	// Check for out_of_range and length_error exceptions.
bc2631e0	444	__try
872d8fea	445	{ _S_copy_chars(_M_data(), __beg, __end); }
bc2631e0	446	__catch(...)
872d8fea PC	447	{
	448	_M_dispose();
	449	__throw_exception_again;
	450	}
	451
	452	_M_set_length(__dnew);
	453	}
	454
	455	template<typename _CharT, typename _Traits, typename _Alloc>
	456	void
	457	__sso_string_base<_CharT, _Traits, _Alloc>::
	458	_M_construct(size_type __n, _CharT __c)
	459	{
	460	if (__n > size_type(_S_local_capacity))
	461	{
	462	_M_data(_M_create(__n, size_type(0)));
	463	_M_capacity(__n);
	464	}
	465
	466	if (__n)
	467	_S_assign(_M_data(), __n, __c);
	468
	469	_M_set_length(__n);
	470	}
	471
	472	template<typename _CharT, typename _Traits, typename _Alloc>
	473	void
	474	__sso_string_base<_CharT, _Traits, _Alloc>::
	475	_M_assign(const __sso_string_base& __rcs)
	476	{
	477	if (this != &__rcs)
	478	{
afe6d705 PC	479	const size_type __rsize = __rcs._M_length();
afe6d705 PC	480	const size_type __capacity = _M_capacity();
872d8fea	481
afe6d705 PC	482	if (__rsize > __capacity)
	483	{
	484	size_type __new_capacity = __rsize;
	485	_CharT* __tmp = _M_create(__new_capacity, __capacity);
	486	_M_dispose();
	487	_M_data(__tmp);
	488	_M_capacity(__new_capacity);
	489	}
872d8fea	490
afe6d705 PC	491	if (__rsize)
afe6d705 PC	492	_S_copy(_M_data(), __rcs._M_data(), __rsize);
872d8fea	493
afe6d705	494	_M_set_length(__rsize);
872d8fea PC	495	}
	496	}
	497
	498	template<typename _CharT, typename _Traits, typename _Alloc>
	499	void
	500	__sso_string_base<_CharT, _Traits, _Alloc>::
	501	_M_reserve(size_type __res)
	502	{
cf882919 PC	503	// Make sure we don't shrink below the current size.
	504	if (__res < _M_length())
	505	__res = _M_length();
	506
872d8fea PC	507	const size_type __capacity = _M_capacity();
	508	if (__res != __capacity)
	509	{
872d8fea PC	510	if (__res > __capacity
	511	\|\| __res > size_type(_S_local_capacity))
	512	{
	513	_CharT* __tmp = _M_create(__res, __capacity);
cf882919	514	_S_copy(__tmp, _M_data(), _M_length() + 1);
872d8fea PC	515	_M_dispose();
	516	_M_data(__tmp);
	517	_M_capacity(__res);
	518	}
	519	else if (!_M_is_local())
	520	{
cf882919	521	_S_copy(_M_local_data, _M_data(), _M_length() + 1);
b6105bf2	522	_M_destroy(__capacity);
872d8fea	523	_M_data(_M_local_data);
cf882919	524	}
872d8fea PC	525	}
	526	}
	527
	528	template<typename _CharT, typename _Traits, typename _Alloc>
	529	void
	530	__sso_string_base<_CharT, _Traits, _Alloc>::
cf882919 PC	531	_M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
cf882919 PC	532	const size_type __len2)
872d8fea	533	{
cf882919	534	const size_type __how_much = _M_length() - __pos - __len1;
872d8fea	535
cf882919 PC	536	size_type __new_capacity = _M_length() + __len2 - __len1;
	537	_CharT* __r = _M_create(__new_capacity, _M_capacity());
	538
	539	if (__pos)
	540	_S_copy(__r, _M_data(), __pos);
	541	if (__s && __len2)
	542	_S_copy(__r + __pos, __s, __len2);
	543	if (__how_much)
	544	_S_copy(__r + __pos + __len2,
	545	_M_data() + __pos + __len1, __how_much);
	546
	547	_M_dispose();
	548	_M_data(__r);
	549	_M_capacity(__new_capacity);
	550	}
872d8fea	551
cf882919 PC	552	template<typename _CharT, typename _Traits, typename _Alloc>
	553	void
	554	__sso_string_base<_CharT, _Traits, _Alloc>::
	555	_M_erase(size_type __pos, size_type __n)
	556	{
	557	const size_type __how_much = _M_length() - __pos - __n;
872d8fea	558
cf882919 PC	559	if (__how_much && __n)
	560	_S_move(_M_data() + __pos, _M_data() + __pos + __n,
	561	__how_much);
872d8fea	562
cf882919	563	_M_set_length(_M_length() - __n);
872d8fea	564	}
b6105bf2	565
3cbc7af0	566	_GLIBCXX_END_NAMESPACE
872d8fea PC	567
872d8fea PC	568	#endif /* _SSO_STRING_BASE_H */