// Components for manipulating sequences of characters -*- C++ -*-// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005// Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library.  This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING.  If not, write to the Free// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,// USA.// As a special exception, you may use this file as part of a free software// library without restriction.  Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License.  This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License.//// ISO C++ 14882: 21 Strings library///** @file basic_string.h *  This is an internal header file, included by other library headers. *  You should not attempt to use it directly. */#ifndef _BASIC_STRING_H#define _BASIC_STRING_H 1#pragma GCC system_header#include <bits/atomicity.h>#include <debug/debug.h>namespace std{  /**   *  @class basic_string basic_string.h <string>   *  @brief  Managing sequences of characters and character-like objects.   *   *  @ingroup Containers   *  @ingroup Sequences   *   *  Meets the requirements of a <a href="tables.html#65">container</a>, a   *  <a href="tables.html#66">reversible container</a>, and a   *  <a href="tables.html#67">sequence</a>.  Of the   *  <a href="tables.html#68">optional sequence requirements</a>, only   *  @c push_back, @c at, and array access are supported.   *   *  @doctodo   *   *   *  @if maint   *  Documentation?  What's that?   *  Nathan Myers <ncm@cantrip.org>.   *   *  A string looks like this:   *   *  @code   *                                        [_Rep]   *                                        _M_length   *   [basic_string<char_type>]            _M_capacity   *   _M_dataplus                          _M_refcount   *   _M_p ---------------->               unnamed array of char_type   *  @endcode   *   *  Where the _M_p points to the first character in the string, and   *  you cast it to a pointer-to-_Rep and subtract 1 to get a   *  pointer to the header.   *   *  This approach has the enormous advantage that a string object   *  requires only one allocation.  All the ugliness is confined   *  within a single pair of inline functions, which each compile to   *  a single "add" instruction: _Rep::_M_data(), and   *  string::_M_rep(); and the allocation function which gets a   *  block of raw bytes and with room enough and constructs a _Rep   *  object at the front.   *   *  The reason you want _M_data pointing to the character array and   *  not the _Rep is so that the debugger can see the string   *  contents. (Probably we should add a non-inline member to get   *  the _Rep for the debugger to use, so users can check the actual   *  string length.)   *   *  Note that the _Rep object is a POD so that you can have a   *  static "empty string" _Rep object already "constructed" before   *  static constructors have run.  The reference-count encoding is   *  chosen so that a 0 indicates one reference, so you never try to   *  destroy the empty-string _Rep object.   *   *  All but the last paragraph is considered pretty conventional   *  for a C++ string implementation.   *  @endif  */  // 21.3  Template class basic_string  template<typename _CharT, typename _Traits, typename _Alloc>    class basic_string    {      typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;      // Types:    public:      typedef _Traits					    traits_type;      typedef typename _Traits::char_type		    value_type;      typedef _Alloc					    allocator_type;      typedef typename _CharT_alloc_type::size_type	    size_type;      typedef typename _CharT_alloc_type::difference_type   difference_type;      typedef typename _CharT_alloc_type::reference	    reference;      typedef typename _CharT_alloc_type::const_reference   const_reference;      typedef typename _CharT_alloc_type::pointer	    pointer;      typedef typename _CharT_alloc_type::const_pointer	    const_pointer;      typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;      typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>                                                            const_iterator;      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;      typedef std::reverse_iterator<iterator>		    reverse_iterator;    private:      // _Rep: string representation      //   Invariants:      //   1. String really contains _M_length + 1 characters: due to 21.3.4      //      must be kept null-terminated.      //   2. _M_capacity >= _M_length      //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).      //   3. _M_refcount has three states:      //      -1: leaked, one reference, no ref-copies allowed, non-const.      //       0: one reference, non-const.      //     n>0: n + 1 references, operations require a lock, const.      //   4. All fields==0 is an empty string, given the extra storage      //      beyond-the-end for a null terminator; thus, the shared      //      empty string representation needs no constructor.      struct _Rep_base      {	size_type		_M_length;	size_type		_M_capacity;	_Atomic_word		_M_refcount;      };      struct _Rep : _Rep_base      {	// Types:	typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;	// (Public) Data members:	// The maximum number of individual char_type elements of an	// individual string is determined by _S_max_size. This is the	// value that will be returned by max_size().  (Whereas npos	// is the maximum number of bytes the allocator can allocate.)	// If one was to divvy up the theoretical largest size string,	// with a terminating character and m _CharT elements, it'd	// look like this:	// npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)	// Solving for m:	// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1	// In addition, this implementation quarters this amount.	static const size_type	_S_max_size;	static const _CharT	_S_terminal;	// The following storage is init'd to 0 by the linker, resulting        // (carefully) in an empty string with one reference.        static size_type _S_empty_rep_storage[];        static _Rep&        _S_empty_rep()        {	  void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);	  return *reinterpret_cast<_Rep*>(__p);	}        bool	_M_is_leaked() const        { return this->_M_refcount < 0; }        bool	_M_is_shared() const        { return this->_M_refcount > 0; }        void	_M_set_leaked()        { this->_M_refcount = -1; }        void	_M_set_sharable()        { this->_M_refcount = 0; }	void	_M_set_length_and_sharable(size_type __n)	{ 	  this->_M_set_sharable();  // One reference.	  this->_M_length = __n;	  traits_type::assign(this->_M_refdata()[__n], _S_terminal);	  // grrr. (per 21.3.4)	  // You cannot leave those LWG people alone for a second.	}	_CharT*	_M_refdata() throw()	{ return reinterpret_cast<_CharT*>(this + 1); }	_CharT*	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)	{	  return (!_M_is_leaked() && __alloc1 == __alloc2)	          ? _M_refcopy() : _M_clone(__alloc1);	}	// Create & Destroy	static _Rep*	_S_create(size_type, size_type, const _Alloc&);	void	_M_dispose(const _Alloc& __a)	{#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING	  if (__builtin_expect(this != &_S_empty_rep(), false))#endif	    if (__gnu_cxx::__exchange_and_add(&this->_M_refcount, -1) <= 0)	      _M_destroy(__a);	}  // XXX MT	void	_M_destroy(const _Alloc&) throw();	_CharT*	_M_refcopy() throw()	{#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING	  if (__builtin_expect(this != &_S_empty_rep(), false))#endif            __gnu_cxx::__atomic_add(&this->_M_refcount, 1);	  return _M_refdata();	}  // XXX MT	_CharT*	_M_clone(const _Alloc&, size_type __res = 0);      };      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html      struct _Alloc_hider : _Alloc      {	_Alloc_hider(_CharT* __dat, const _Alloc& __a)	: _Alloc(__a), _M_p(__dat) { }	_CharT* _M_p; // The actual data.      };    public:      // Data Members (public):      // NB: This is an unsigned type, and thus represents the maximum      // size that the allocator can hold.      ///  Value returned by various member functions when they fail.      static const size_type	npos = static_cast<size_type>(-1);    private:      // Data Members (private):      mutable _Alloc_hider	_M_dataplus;      _CharT*      _M_data() const      { return  _M_dataplus._M_p; }      _CharT*      _M_data(_CharT* __p)      { return (_M_dataplus._M_p = __p); }      _Rep*      _M_rep() const      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }      // For the internal use we have functions similar to `begin'/`end'      // but they do not call _M_leak.      iterator      _M_ibegin() const      { return iterator(_M_data()); }      iterator      _M_iend() const      { return iterator(_M_data() + this->size()); }      void      _M_leak()    // for use in begin() & non-const op[]      {	if (!_M_rep()->_M_is_leaked())	  _M_leak_hard();      }      size_type      _M_check(size_type __pos, const char* __s) const      {	if (__pos > this->size())	  __throw_out_of_range(__N(__s));	return __pos;      }      void      _M_check_length(size_type __n1, size_type __n2, const char* __s) const      {	if (this->max_size() - (this->size() - __n1) < __n2)	  __throw_length_error(__N(__s));      }      // NB: _M_limit doesn't check for a bad __pos value.      size_type      _M_limit(size_type __pos, size_type __off) const      {	const bool __testoff =  __off < this->size() - __pos;	return __testoff ? __off : this->size() - __pos;      }      // True if _Rep and source do not overlap.      bool      _M_disjunct(const _CharT* __s) const      {	return (less<const _CharT*>()(__s, _M_data())		|| less<const _CharT*>()(_M_data() + this->size(), __s));      }      // When __n = 1 way faster than the general multichar      // traits_type::copy/move/assign.      static void      _M_copy(_CharT* __d, const _CharT* __s, size_type __n)      {	if (__n == 1)	  traits_type::assign(*__d, *__s);	else	  traits_type::copy(__d, __s, __n);      }      static void      _M_move(_CharT* __d, const _CharT* __s, size_type __n)      {	if (__n == 1)	  traits_type::assign(*__d, *__s);	else	  traits_type::move(__d, __s, __n);	        }      static void      _M_assign(_CharT* __d, size_type __n, _CharT __c)      {	if (__n == 1)	  traits_type::assign(*__d, __c);