home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / basic_string.tcc < prev    next >
Text File  |  2005-01-29  |  34KB  |  969 lines
  1. // Components for manipulating sequences of characters -*- C++ -*-
  2.  
  3. // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
  4. // Free Software Foundation, Inc.
  5. //
  6. // This file is part of the GNU ISO C++ Library.  This library is free
  7. // software; you can redistribute it and/or modify it under the
  8. // terms of the GNU General Public License as published by the
  9. // Free Software Foundation; either version 2, or (at your option)
  10. // any later version.
  11.  
  12. // This library is distributed in the hope that it will be useful,
  13. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. // GNU General Public License for more details.
  16.  
  17. // You should have received a copy of the GNU General Public License along
  18. // with this library; see the file COPYING.  If not, write to the Free
  19. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20. // USA.
  21.  
  22. // As a special exception, you may use this file as part of a free software
  23. // library without restriction.  Specifically, if other files instantiate
  24. // templates or use macros or inline functions from this file, or you compile
  25. // this file and link it with other files to produce an executable, this
  26. // file does not by itself cause the resulting executable to be covered by
  27. // the GNU General Public License.  This exception does not however
  28. // invalidate any other reasons why the executable file might be covered by
  29. // the GNU General Public License.
  30.  
  31. //
  32. // ISO C++ 14882: 21  Strings library
  33. //
  34.  
  35. // This file is included by <string>.  It is not meant to be included
  36. // separately.
  37.  
  38. // Written by Jason Merrill based upon the specification by Takanori Adachi
  39. // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  40.  
  41. #ifndef _BASIC_STRING_TCC
  42. #define _BASIC_STRING_TCC 1
  43.  
  44. #pragma GCC system_header
  45.  
  46. namespace std
  47. {
  48.   template<typename _Type>
  49.     inline bool
  50.     __is_null_pointer(_Type* __ptr)
  51.     { return __ptr == 0; }
  52.  
  53.   template<typename _Type>
  54.     inline bool
  55.     __is_null_pointer(_Type)
  56.     { return false; }
  57.  
  58.   template<typename _CharT, typename _Traits, typename _Alloc>
  59.     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  60.     basic_string<_CharT, _Traits, _Alloc>::
  61.     _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
  62.  
  63.   template<typename _CharT, typename _Traits, typename _Alloc>
  64.     const _CharT
  65.     basic_string<_CharT, _Traits, _Alloc>::
  66.     _Rep::_S_terminal = _CharT();
  67.  
  68.   template<typename _CharT, typename _Traits, typename _Alloc>
  69.     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  70.     basic_string<_CharT, _Traits, _Alloc>::npos;
  71.  
  72.   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
  73.   // at static init time (before static ctors are run).
  74.   template<typename _CharT, typename _Traits, typename _Alloc>
  75.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  76.     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
  77.     (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
  78.       sizeof(size_type)];
  79.  
  80.   // NB: This is the special case for Input Iterators, used in
  81.   // istreambuf_iterators, etc.
  82.   // Input Iterators have a cost structure very different from
  83.   // pointers, calling for a different coding style.
  84.   template<typename _CharT, typename _Traits, typename _Alloc>
  85.     template<typename _InIterator>
  86.       _CharT*
  87.       basic_string<_CharT, _Traits, _Alloc>::
  88.       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
  89.            input_iterator_tag)
  90.       {
  91.     if (__beg == __end && __a == _Alloc())
  92.       return _S_empty_rep()._M_refdata();
  93.     // Avoid reallocation for common case.
  94.     _CharT __buf[128];
  95.     size_type __len = 0;
  96.     while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
  97.       {
  98.         __buf[__len++] = *__beg;
  99.         ++__beg;
  100.       }
  101.     _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
  102.     traits_type::copy(__r->_M_refdata(), __buf, __len);
  103.     try
  104.       {
  105.         while (__beg != __end)
  106.           {
  107.         if (__len == __r->_M_capacity)
  108.           {
  109.             // Allocate more space.
  110.             _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
  111.             traits_type::copy(__another->_M_refdata(),
  112.                       __r->_M_refdata(), __len);
  113.             __r->_M_destroy(__a);
  114.             __r = __another;
  115.           }
  116.         __r->_M_refdata()[__len++] = *__beg;
  117.         ++__beg;
  118.           }
  119.       }
  120.     catch(...)
  121.       {
  122.         __r->_M_destroy(__a);
  123.         __throw_exception_again;
  124.       }
  125.     __r->_M_length = __len;
  126.     __r->_M_refdata()[__len] = _Rep::_S_terminal;       // grrr.
  127.     return __r->_M_refdata();
  128.       }
  129.  
  130.   template<typename _CharT, typename _Traits, typename _Alloc>
  131.     template <typename _InIterator>
  132.       _CharT*
  133.       basic_string<_CharT, _Traits, _Alloc>::
  134.       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
  135.            forward_iterator_tag)
  136.       {
  137.     if (__beg == __end && __a == _Alloc())
  138.       return _S_empty_rep()._M_refdata();
  139.  
  140.     // NB: Not required, but considered best practice.
  141.     if (__builtin_expect(__is_null_pointer(__beg), 0))
  142.       __throw_logic_error(__N("basic_string::_S_construct NULL not valid"));
  143.  
  144.     const size_type __dnew = static_cast<size_type>(std::distance(__beg,
  145.                                       __end));
  146.     // Check for out_of_range and length_error exceptions.
  147.     _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
  148.     try
  149.       { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
  150.     catch(...)
  151.       {
  152.         __r->_M_destroy(__a);
  153.         __throw_exception_again;
  154.       }
  155.     __r->_M_length = __dnew;
  156.     __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
  157.     return __r->_M_refdata();
  158.       }
  159.  
  160.   template<typename _CharT, typename _Traits, typename _Alloc>
  161.     _CharT*
  162.     basic_string<_CharT, _Traits, _Alloc>::
  163.     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
  164.     {
  165.       if (__n == 0 && __a == _Alloc())
  166.     return _S_empty_rep()._M_refdata();
  167.  
  168.       // Check for out_of_range and length_error exceptions.
  169.       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
  170.       if (__n)
  171.     traits_type::assign(__r->_M_refdata(), __n, __c);
  172.  
  173.       __r->_M_length = __n;
  174.       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
  175.       return __r->_M_refdata();
  176.     }
  177.  
  178.   template<typename _CharT, typename _Traits, typename _Alloc>
  179.     basic_string<_CharT, _Traits, _Alloc>::
  180.     basic_string(const basic_string& __str)
  181.     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
  182.                       __str.get_allocator()),
  183.           __str.get_allocator())
  184.     { }
  185.  
  186.   template<typename _CharT, typename _Traits, typename _Alloc>
  187.     basic_string<_CharT, _Traits, _Alloc>::
  188.     basic_string(const _Alloc& __a)
  189.     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
  190.     { }
  191.  
  192.   template<typename _CharT, typename _Traits, typename _Alloc>
  193.     basic_string<_CharT, _Traits, _Alloc>::
  194.     basic_string(const basic_string& __str, size_type __pos, size_type __n)
  195.     : _M_dataplus(_S_construct(__str._M_data()
  196.                    + __str._M_check(__pos,
  197.                         "basic_string::basic_string"),
  198.                    __str._M_data() + __str._M_limit(__pos, __n)
  199.                    + __pos, _Alloc()), _Alloc())
  200.     { }
  201.  
  202.   template<typename _CharT, typename _Traits, typename _Alloc>
  203.     basic_string<_CharT, _Traits, _Alloc>::
  204.     basic_string(const basic_string& __str, size_type __pos,
  205.          size_type __n, const _Alloc& __a)
  206.     : _M_dataplus(_S_construct(__str._M_data()
  207.                    + __str._M_check(__pos,
  208.                         "basic_string::basic_string"),
  209.                    __str._M_data() + __str._M_limit(__pos, __n)
  210.                    + __pos, __a), __a)
  211.     { }
  212.  
  213.   // TBD: DPG annotate
  214.   template<typename _CharT, typename _Traits, typename _Alloc>
  215.     basic_string<_CharT, _Traits, _Alloc>::
  216.     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
  217.     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
  218.     { }
  219.  
  220.   // TBD: DPG annotate
  221.   template<typename _CharT, typename _Traits, typename _Alloc>
  222.     basic_string<_CharT, _Traits, _Alloc>::
  223.     basic_string(const _CharT* __s, const _Alloc& __a)
  224.     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
  225.                    __s + npos, __a), __a)
  226.     { }
  227.  
  228.   template<typename _CharT, typename _Traits, typename _Alloc>
  229.     basic_string<_CharT, _Traits, _Alloc>::
  230.     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
  231.     : _M_dataplus(_S_construct(__n, __c, __a), __a)
  232.     { }
  233.  
  234.   // TBD: DPG annotate
  235.   template<typename _CharT, typename _Traits, typename _Alloc>
  236.     template<typename _InputIterator>
  237.     basic_string<_CharT, _Traits, _Alloc>::
  238.     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
  239.     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
  240.     { }
  241.  
  242.   template<typename _CharT, typename _Traits, typename _Alloc>
  243.     basic_string<_CharT, _Traits, _Alloc>&
  244.     basic_string<_CharT, _Traits, _Alloc>::
  245.     assign(const basic_string& __str)
  246.     {
  247.       if (_M_rep() != __str._M_rep())
  248.     {
  249.       // XXX MT
  250.       const allocator_type __a = this->get_allocator();
  251.       _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
  252.       _M_rep()->_M_dispose(__a);
  253.       _M_data(__tmp);
  254.     }
  255.       return *this;
  256.     }
  257.  
  258.    template<typename _CharT, typename _Traits, typename _Alloc>
  259.      basic_string<_CharT, _Traits, _Alloc>&
  260.      basic_string<_CharT, _Traits, _Alloc>::
  261.      assign(const _CharT* __s, size_type __n)
  262.      {
  263.        __glibcxx_requires_string_len(__s, __n);
  264.        if (__n > this->max_size())
  265.      __throw_length_error(__N("basic_string::assign"));
  266.        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
  267.        || less<const _CharT*>()(_M_data() + this->size(), __s))
  268.      return _M_replace_safe(size_type(0), this->size(), __s, __n);
  269.        else
  270.      {
  271.        // Work in-place
  272.        const size_type __pos = __s - _M_data();
  273.        if (__pos >= __n)
  274.          traits_type::copy(_M_data(), __s, __n);
  275.        else if (__pos)
  276.          traits_type::move(_M_data(), __s, __n);
  277.        _M_rep()->_M_set_sharable();
  278.        _M_rep()->_M_length = __n;
  279.        _M_data()[__n] = _Rep::_S_terminal;  // grr.
  280.        return *this;
  281.      }
  282.      }
  283.  
  284.    template<typename _CharT, typename _Traits, typename _Alloc>
  285.      basic_string<_CharT, _Traits, _Alloc>&
  286.      basic_string<_CharT, _Traits, _Alloc>::
  287.      insert(size_type __pos, const _CharT* __s, size_type __n)
  288.      {
  289.        __glibcxx_requires_string_len(__s, __n);
  290.        _M_check(__pos, "basic_string::insert");
  291.        if (this->max_size() - this->size() < __n)
  292.      __throw_length_error(__N("basic_string::insert"));
  293.        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
  294.            || less<const _CharT*>()(_M_data() + this->size(), __s))
  295.          return _M_replace_safe(__pos, size_type(0), __s, __n);
  296.        else
  297.          {
  298.            // Work in-place. If _M_mutate reallocates the string, __s
  299.            // does not point anymore to valid data, therefore we save its
  300.            // offset, then we restore it.
  301.            const size_type __off = __s - _M_data();
  302.            _M_mutate(__pos, 0, __n);
  303.            __s = _M_data() + __off;
  304.            _CharT* __p = _M_data() + __pos;
  305.            if (__s  + __n <= __p)
  306.              traits_type::copy(__p, __s, __n);
  307.            else if (__s >= __p)
  308.              traits_type::copy(__p, __s + __n, __n);
  309.            else
  310.              {
  311.            const size_type __nleft = __p - __s;
  312.                traits_type::copy(__p, __s, __nleft);
  313.                traits_type::copy(__p + __nleft, __p + __n, __n - __nleft);
  314.              }
  315.            return *this;
  316.          }
  317.      }
  318.  
  319.    template<typename _CharT, typename _Traits, typename _Alloc>
  320.      basic_string<_CharT, _Traits, _Alloc>&
  321.      basic_string<_CharT, _Traits, _Alloc>::
  322.      replace(size_type __pos, size_type __n1, const _CharT* __s,
  323.          size_type __n2)
  324.      {
  325.        __glibcxx_requires_string_len(__s, __n2);
  326.        _M_check(__pos, "basic_string::replace");
  327.        __n1 = _M_limit(__pos, __n1);
  328.        if (this->max_size() - (this->size() - __n1) < __n2)
  329.          __throw_length_error(__N("basic_string::replace"));
  330.        bool __left;
  331.        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
  332.        || less<const _CharT*>()(_M_data() + this->size(), __s))
  333.          return _M_replace_safe(__pos, __n1, __s, __n2);
  334.        else if ((__left = __s + __n2 <= _M_data() + __pos)
  335.         || _M_data() + __pos + __n1 <= __s)
  336.      {
  337.        // Work in-place: non-overlapping case.
  338.        const size_type __off = __s - _M_data();
  339.        _M_mutate(__pos, __n1, __n2);
  340.        if (__left)
  341.          traits_type::copy(_M_data() + __pos,
  342.                    _M_data() + __off, __n2);
  343.        else
  344.          traits_type::copy(_M_data() + __pos,
  345.                    _M_data() + __off + __n2 - __n1, __n2);
  346.        return *this;
  347.      }
  348.        else
  349.      {
  350.        // Todo: overlapping case.
  351.        const basic_string __tmp(__s, __n2);
  352.        return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
  353.      }
  354.      }
  355.  
  356.   template<typename _CharT, typename _Traits, typename _Alloc>
  357.     void
  358.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  359.     _M_destroy(const _Alloc& __a) throw ()
  360.     {
  361.       if (this == &_S_empty_rep())
  362.         return;
  363.       const size_type __size = sizeof(_Rep_base) +
  364.                            (this->_M_capacity + 1) * sizeof(_CharT);
  365.       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
  366.     }
  367.  
  368.   template<typename _CharT, typename _Traits, typename _Alloc>
  369.     void
  370.     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
  371.     {
  372.       if (_M_rep() == &_S_empty_rep())
  373.         return;
  374.       if (_M_rep()->_M_is_shared())
  375.     _M_mutate(0, 0, 0);
  376.       _M_rep()->_M_set_leaked();
  377.     }
  378.  
  379.   template<typename _CharT, typename _Traits, typename _Alloc>
  380.     void
  381.     basic_string<_CharT, _Traits, _Alloc>::
  382.     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
  383.     {
  384.       const size_type __old_size = this->size();
  385.       const size_type __new_size = __old_size + __len2 - __len1;
  386.       const size_type __how_much = __old_size - __pos - __len1;
  387.  
  388.       if (_M_rep() == &_S_empty_rep()
  389.       || _M_rep()->_M_is_shared() || __new_size > capacity())
  390.     {
  391.       // Must reallocate.
  392.       const allocator_type __a = get_allocator();
  393.       _Rep* __r = _Rep::_S_create(__new_size, capacity(), __a);
  394.  
  395.       if (__pos)
  396.         traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
  397.       if (__how_much)
  398.         traits_type::copy(__r->_M_refdata() + __pos + __len2,
  399.                   _M_data() + __pos + __len1, __how_much);
  400.  
  401.       _M_rep()->_M_dispose(__a);
  402.       _M_data(__r->_M_refdata());
  403.     }
  404.       else if (__how_much && __len1 != __len2)
  405.     {
  406.       // Work in-place
  407.       traits_type::move(_M_data() + __pos + __len2,
  408.                 _M_data() + __pos + __len1, __how_much);
  409.     }
  410.       _M_rep()->_M_set_sharable();
  411.       _M_rep()->_M_length = __new_size;
  412.       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
  413.       // You cannot leave those LWG people alone for a second.
  414.     }
  415.  
  416.   template<typename _CharT, typename _Traits, typename _Alloc>
  417.     void
  418.     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
  419.     {
  420.       if (__res != this->capacity() || _M_rep()->_M_is_shared())
  421.         {
  422.       if (__res > this->max_size())
  423.         __throw_length_error(__N("basic_string::reserve"));
  424.       // Make sure we don't shrink below the current size
  425.       if (__res < this->size())
  426.         __res = this->size();
  427.       const allocator_type __a = get_allocator();
  428.       _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
  429.       _M_rep()->_M_dispose(__a);
  430.       _M_data(__tmp);
  431.         }
  432.     }
  433.  
  434.   template<typename _CharT, typename _Traits, typename _Alloc>
  435.     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
  436.     {
  437.       if (_M_rep()->_M_is_leaked())
  438.     _M_rep()->_M_set_sharable();
  439.       if (__s._M_rep()->_M_is_leaked())
  440.     __s._M_rep()->_M_set_sharable();
  441.       if (this->get_allocator() == __s.get_allocator())
  442.     {
  443.       _CharT* __tmp = _M_data();
  444.       _M_data(__s._M_data());
  445.       __s._M_data(__tmp);
  446.     }
  447.       // The code below can usually be optimized away.
  448.       else
  449.     {
  450.       const basic_string __tmp1(_M_ibegin(), _M_iend(),
  451.                     __s.get_allocator());
  452.       const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
  453.                     this->get_allocator());
  454.       *this = __tmp2;
  455.       __s = __tmp1;
  456.     }
  457.     }
  458.  
  459.   template<typename _CharT, typename _Traits, typename _Alloc>
  460.     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
  461.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  462.     _S_create(size_type __capacity, size_type __old_capacity,
  463.           const _Alloc& __alloc)
  464.     {
  465.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  466.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  467.       // 83.  String::npos vs. string::max_size()
  468.       if (__capacity > _S_max_size)
  469.     __throw_length_error(__N("basic_string::_S_create"));
  470.  
  471.       // The standard places no restriction on allocating more memory
  472.       // than is strictly needed within this layer at the moment or as
  473.       // requested by an explicit application call to reserve().
  474.  
  475.       // Many malloc implementations perform quite poorly when an
  476.       // application attempts to allocate memory in a stepwise fashion
  477.       // growing each allocation size by only 1 char.  Additionally,
  478.       // it makes little sense to allocate less linear memory than the
  479.       // natural blocking size of the malloc implementation.
  480.       // Unfortunately, we would need a somewhat low-level calculation
  481.       // with tuned parameters to get this perfect for any particular
  482.       // malloc implementation.  Fortunately, generalizations about
  483.       // common features seen among implementations seems to suffice.
  484.  
  485.       // __pagesize need not match the actual VM page size for good
  486.       // results in practice, thus we pick a common value on the low
  487.       // side.  __malloc_header_size is an estimate of the amount of
  488.       // overhead per memory allocation (in practice seen N * sizeof
  489.       // (void*) where N is 0, 2 or 4).  According to folklore,
  490.       // picking this value on the high side is better than
  491.       // low-balling it (especially when this algorithm is used with
  492.       // malloc implementations that allocate memory blocks rounded up
  493.       // to a size which is a power of 2).
  494.       const size_type __pagesize = 4096; // must be 2^i * __subpagesize
  495.       const size_type __subpagesize = 128; // should be >> __malloc_header_size
  496.       const size_type __malloc_header_size = 4 * sizeof (void*);
  497.  
  498.       // The below implements an exponential growth policy, necessary to
  499.       // meet amortized linear time requirements of the library: see
  500.       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
  501.       // It's active for allocations requiring an amount of memory above
  502.       // system pagesize. This is consistent with the requirements of the
  503.       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
  504.  
  505.       // The biggest string which fits in a memory page
  506.       const size_type __page_capacity = ((__pagesize - __malloc_header_size
  507.                       - sizeof(_Rep) - sizeof(_CharT))
  508.                      / sizeof(_CharT));
  509.  
  510.       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity
  511.       && __capacity > __page_capacity)
  512.     __capacity = 2 * __old_capacity;
  513.  
  514.       // NB: Need an array of char_type[__capacity], plus a terminating
  515.       // null char_type() element, plus enough for the _Rep data structure.
  516.       // Whew. Seemingly so needy, yet so elemental.
  517.       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  518.  
  519.       const size_type __adj_size = __size + __malloc_header_size;
  520.       if (__adj_size > __pagesize)
  521.     {
  522.       const size_type __extra = __pagesize - __adj_size % __pagesize;
  523.       __capacity += __extra / sizeof(_CharT);
  524.       // Never allocate a string bigger than _S_max_size.
  525.       if (__capacity > _S_max_size)
  526.         __capacity = _S_max_size;
  527.       __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  528.     }
  529.       else if (__size > __subpagesize)
  530.     {
  531.       const size_type __extra = __subpagesize - __adj_size % __subpagesize;
  532.       __capacity += __extra / sizeof(_CharT);
  533.       __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  534.     }
  535.  
  536.       // NB: Might throw, but no worries about a leak, mate: _Rep()
  537.       // does not throw.
  538.       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
  539.       _Rep *__p = new (__place) _Rep;
  540.       __p->_M_capacity = __capacity;
  541.       __p->_M_set_sharable();  // One reference.
  542.       __p->_M_length = 0;
  543.       return __p;
  544.     }
  545.  
  546.   template<typename _CharT, typename _Traits, typename _Alloc>
  547.     _CharT*
  548.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  549.     _M_clone(const _Alloc& __alloc, size_type __res)
  550.     {
  551.       // Requested capacity of the clone.
  552.       const size_type __requested_cap = this->_M_length + __res;
  553.       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
  554.                   __alloc);
  555.       if (this->_M_length)
  556.     traits_type::copy(__r->_M_refdata(), _M_refdata(),
  557.               this->_M_length);
  558.  
  559.       __r->_M_length = this->_M_length;
  560.       __r->_M_refdata()[this->_M_length] = _Rep::_S_terminal;
  561.       return __r->_M_refdata();
  562.     }
  563.  
  564.   template<typename _CharT, typename _Traits, typename _Alloc>
  565.     void
  566.     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
  567.     {
  568.       if (__n > max_size())
  569.     __throw_length_error(__N("basic_string::resize"));
  570.       const size_type __size = this->size();
  571.       if (__size < __n)
  572.     this->append(__n - __size, __c);
  573.       else if (__n < __size)
  574.     this->erase(__n);
  575.       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
  576.     }
  577.  
  578.   template<typename _CharT, typename _Traits, typename _Alloc>
  579.     template<typename _InputIterator>
  580.       basic_string<_CharT, _Traits, _Alloc>&
  581.       basic_string<_CharT, _Traits, _Alloc>::
  582.       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
  583.               _InputIterator __k2, __false_type)
  584.       {
  585.     const basic_string __s(__k1, __k2);
  586.     const size_type __n1 = __i2 - __i1;
  587.     if (this->max_size() - (this->size() - __n1) < __s.size())
  588.       __throw_length_error(__N("basic_string::_M_replace_dispatch"));
  589.     return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
  590.                    __s.size());
  591.       }
  592.  
  593.   template<typename _CharT, typename _Traits, typename _Alloc>
  594.     basic_string<_CharT, _Traits, _Alloc>&
  595.     basic_string<_CharT, _Traits, _Alloc>::
  596.     append(const basic_string& __str)
  597.     {
  598.       // Iff appending itself, string needs to pre-reserve the
  599.       // correct size so that _M_mutate does not clobber the
  600.       // pointer __str._M_data() formed here.
  601.       const size_type __size = __str.size();
  602.       const size_type __len = __size + this->size();
  603.       if (__len > this->capacity())
  604.     this->reserve(__len);
  605.       return _M_replace_safe(this->size(), size_type(0), __str._M_data(),
  606.                  __str.size());
  607.     }
  608.  
  609.   template<typename _CharT, typename _Traits, typename _Alloc>
  610.     basic_string<_CharT, _Traits, _Alloc>&
  611.     basic_string<_CharT, _Traits, _Alloc>::
  612.     append(const basic_string& __str, size_type __pos, size_type __n)
  613.     {
  614.       // Iff appending itself, string needs to pre-reserve the
  615.       // correct size so that _M_mutate does not clobber the
  616.       // pointer __str._M_data() formed here.
  617.       __str._M_check(__pos, "basic_string::append");
  618.       __n = __str._M_limit(__pos, __n);
  619.       const size_type __len = __n + this->size();
  620.       if (__len > this->capacity())
  621.     this->reserve(__len);
  622.       return _M_replace_safe(this->size(), size_type(0), __str._M_data()
  623.                  + __pos, __n);
  624.     }
  625.  
  626.   template<typename _CharT, typename _Traits, typename _Alloc>
  627.     basic_string<_CharT, _Traits, _Alloc>&
  628.     basic_string<_CharT, _Traits, _Alloc>::
  629.     append(const _CharT* __s, size_type __n)
  630.     {
  631.       __glibcxx_requires_string_len(__s, __n);
  632.       const size_type __len = __n + this->size();
  633.       if (__len > this->capacity())
  634.     this->reserve(__len);
  635.       return _M_replace_safe(this->size(), size_type(0), __s, __n);
  636.     }
  637.  
  638.   template<typename _CharT, typename _Traits, typename _Alloc>
  639.     basic_string<_CharT, _Traits, _Alloc>
  640.     operator+(const _CharT* __lhs,
  641.           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  642.     {
  643.       __glibcxx_requires_string(__lhs);
  644.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  645.       typedef typename __string_type::size_type      __size_type;
  646.       const __size_type __len = _Traits::length(__lhs);
  647.       __string_type __str;
  648.       __str.reserve(__len + __rhs.size());
  649.       __str.append(__lhs, __len);
  650.       __str.append(__rhs);
  651.       return __str;
  652.     }
  653.  
  654.   template<typename _CharT, typename _Traits, typename _Alloc>
  655.     basic_string<_CharT, _Traits, _Alloc>
  656.     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  657.     {
  658.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  659.       typedef typename __string_type::size_type      __size_type;
  660.       __string_type __str;
  661.       const __size_type __len = __rhs.size();
  662.       __str.reserve(__len + 1);
  663.       __str.append(__size_type(1), __lhs);
  664.       __str.append(__rhs);
  665.       return __str;
  666.     }
  667.  
  668.   template<typename _CharT, typename _Traits, typename _Alloc>
  669.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  670.     basic_string<_CharT, _Traits, _Alloc>::
  671.     copy(_CharT* __s, size_type __n, size_type __pos) const
  672.     {
  673.       _M_check(__pos, "basic_string::copy");
  674.       __n = _M_limit(__pos, __n);
  675.       __glibcxx_requires_string_len(__s, __n);
  676.       if (__n)
  677.     traits_type::copy(__s, _M_data() + __pos, __n);
  678.       // 21.3.5.7 par 3: do not append null.  (good.)
  679.       return __n;
  680.     }
  681.  
  682.   template<typename _CharT, typename _Traits, typename _Alloc>
  683.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  684.     basic_string<_CharT, _Traits, _Alloc>::
  685.     find(const _CharT* __s, size_type __pos, size_type __n) const
  686.     {
  687.       __glibcxx_requires_string_len(__s, __n);
  688.       const size_type __size = this->size();
  689.       const _CharT* __data = _M_data();
  690.       for (; __pos + __n <= __size; ++__pos)
  691.     if (traits_type::compare(__data + __pos, __s, __n) == 0)
  692.       return __pos;
  693.       return npos;
  694.     }
  695.  
  696.   template<typename _CharT, typename _Traits, typename _Alloc>
  697.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  698.     basic_string<_CharT, _Traits, _Alloc>::
  699.     find(_CharT __c, size_type __pos) const
  700.     {
  701.       const size_type __size = this->size();
  702.       size_type __ret = npos;
  703.       if (__pos < __size)
  704.     {
  705.       const _CharT* __data = _M_data();
  706.       const size_type __n = __size - __pos;
  707.       const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
  708.       if (__p)
  709.         __ret = __p - __data;
  710.     }
  711.       return __ret;
  712.     }
  713.  
  714.   template<typename _CharT, typename _Traits, typename _Alloc>
  715.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  716.     basic_string<_CharT, _Traits, _Alloc>::
  717.     rfind(const _CharT* __s, size_type __pos, size_type __n) const
  718.     {
  719.       __glibcxx_requires_string_len(__s, __n);
  720.       const size_type __size = this->size();
  721.       if (__n <= __size)
  722.     {
  723.       __pos = std::min(size_type(__size - __n), __pos);
  724.       const _CharT* __data = _M_data();
  725.       do
  726.         {
  727.           if (traits_type::compare(__data + __pos, __s, __n) == 0)
  728.         return __pos;
  729.         }
  730.       while (__pos-- > 0);
  731.     }
  732.       return npos;
  733.     }
  734.  
  735.   template<typename _CharT, typename _Traits, typename _Alloc>
  736.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  737.     basic_string<_CharT, _Traits, _Alloc>::
  738.     rfind(_CharT __c, size_type __pos) const
  739.     {
  740.       size_type __size = this->size();
  741.       if (__size)
  742.     {
  743.       if (--__size > __pos)
  744.         __size = __pos;
  745.       for (++__size; __size-- > 0; )
  746.         if (traits_type::eq(_M_data()[__size], __c))
  747.           return __size;
  748.     }
  749.       return npos;
  750.     }
  751.  
  752.   template<typename _CharT, typename _Traits, typename _Alloc>
  753.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  754.     basic_string<_CharT, _Traits, _Alloc>::
  755.     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
  756.     {
  757.       __glibcxx_requires_string_len(__s, __n);
  758.       for (; __n && __pos < this->size(); ++__pos)
  759.     {
  760.       const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
  761.       if (__p)
  762.         return __pos;
  763.     }
  764.       return npos;
  765.     }
  766.  
  767.   template<typename _CharT, typename _Traits, typename _Alloc>
  768.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  769.     basic_string<_CharT, _Traits, _Alloc>::
  770.     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
  771.     {
  772.       __glibcxx_requires_string_len(__s, __n);
  773.       size_type __size = this->size();
  774.       if (__size && __n)
  775.     {
  776.       if (--__size > __pos)
  777.         __size = __pos;
  778.       do
  779.         {
  780.           if (traits_type::find(__s, __n, _M_data()[__size]))
  781.         return __size;
  782.         }
  783.       while (__size-- != 0);
  784.     }
  785.       return npos;
  786.     }
  787.  
  788.   template<typename _CharT, typename _Traits, typename _Alloc>
  789.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  790.     basic_string<_CharT, _Traits, _Alloc>::
  791.     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  792.     {
  793.       __glibcxx_requires_string_len(__s, __n);
  794.       for (; __pos < this->size(); ++__pos)
  795.     if (!traits_type::find(__s, __n, _M_data()[__pos]))
  796.       return __pos;
  797.       return npos;
  798.     }
  799.  
  800.   template<typename _CharT, typename _Traits, typename _Alloc>
  801.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  802.     basic_string<_CharT, _Traits, _Alloc>::
  803.     find_first_not_of(_CharT __c, size_type __pos) const
  804.     {
  805.       for (; __pos < this->size(); ++__pos)
  806.     if (!traits_type::eq(_M_data()[__pos], __c))
  807.       return __pos;
  808.       return npos;
  809.     }
  810.  
  811.   template<typename _CharT, typename _Traits, typename _Alloc>
  812.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  813.     basic_string<_CharT, _Traits, _Alloc>::
  814.     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  815.     {
  816.       __glibcxx_requires_string_len(__s, __n);
  817.       size_type __size = this->size();
  818.       if (__size)
  819.     {
  820.       if (--__size > __pos)
  821.         __size = __pos;
  822.       do
  823.         {
  824.           if (!traits_type::find(__s, __n, _M_data()[__size]))
  825.         return __size;
  826.         }
  827.       while (__size--);
  828.     }
  829.       return npos;
  830.     }
  831.  
  832.   template<typename _CharT, typename _Traits, typename _Alloc>
  833.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  834.     basic_string<_CharT, _Traits, _Alloc>::
  835.     find_last_not_of(_CharT __c, size_type __pos) const
  836.     {
  837.       size_type __size = this->size();
  838.       if (__size)
  839.     {
  840.       if (--__size > __pos)
  841.         __size = __pos;
  842.       do
  843.         {
  844.           if (!traits_type::eq(_M_data()[__size], __c))
  845.         return __size;
  846.         }
  847.       while (__size--);
  848.     }
  849.       return npos;
  850.     }
  851.  
  852.   template<typename _CharT, typename _Traits, typename _Alloc>
  853.     int
  854.     basic_string<_CharT, _Traits, _Alloc>::
  855.     compare(size_type __pos, size_type __n, const basic_string& __str) const
  856.     {
  857.       _M_check(__pos, "basic_string::compare");
  858.       __n = _M_limit(__pos, __n);
  859.       const size_type __osize = __str.size();
  860.       const size_type __len = std::min(__n, __osize);
  861.       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
  862.       if (!__r)
  863.     __r = __n - __osize;
  864.       return __r;
  865.     }
  866.  
  867.   template<typename _CharT, typename _Traits, typename _Alloc>
  868.     int
  869.     basic_string<_CharT, _Traits, _Alloc>::
  870.     compare(size_type __pos1, size_type __n1, const basic_string& __str,
  871.         size_type __pos2, size_type __n2) const
  872.     {
  873.       _M_check(__pos1, "basic_string::compare");
  874.       __str._M_check(__pos2, "basic_string::compare");
  875.       __n1 = _M_limit(__pos1, __n1);
  876.       __n2 = __str._M_limit(__pos2, __n2);
  877.       const size_type __len = std::min(__n1, __n2);
  878.       int __r = traits_type::compare(_M_data() + __pos1,
  879.                      __str.data() + __pos2, __len);
  880.       if (!__r)
  881.     __r = __n1 - __n2;
  882.       return __r;
  883.     }
  884.  
  885.   template<typename _CharT, typename _Traits, typename _Alloc>
  886.     int
  887.     basic_string<_CharT, _Traits, _Alloc>::
  888.     compare(const _CharT* __s) const
  889.     {
  890.       __glibcxx_requires_string(__s);
  891.       const size_type __size = this->size();
  892.       const size_type __osize = traits_type::length(__s);
  893.       const size_type __len = std::min(__size, __osize);
  894.       int __r = traits_type::compare(_M_data(), __s, __len);
  895.       if (!__r)
  896.     __r = __size - __osize;
  897.       return __r;
  898.     }
  899.  
  900.   template<typename _CharT, typename _Traits, typename _Alloc>
  901.     int
  902.     basic_string <_CharT, _Traits, _Alloc>::
  903.     compare(size_type __pos, size_type __n1, const _CharT* __s) const
  904.     {
  905.       __glibcxx_requires_string(__s);
  906.       _M_check(__pos, "basic_string::compare");
  907.       __n1 = _M_limit(__pos, __n1);
  908.       const size_type __osize = traits_type::length(__s);
  909.       const size_type __len = std::min(__n1, __osize);
  910.       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  911.       if (!__r)
  912.     __r = __n1 - __osize;
  913.       return __r;
  914.     }
  915.  
  916.   template<typename _CharT, typename _Traits, typename _Alloc>
  917.     int
  918.     basic_string <_CharT, _Traits, _Alloc>::
  919.     compare(size_type __pos, size_type __n1, const _CharT* __s,
  920.         size_type __n2) const
  921.     {
  922.       __glibcxx_requires_string_len(__s, __n2);
  923.       _M_check(__pos, "basic_string::compare");
  924.       __n1 = _M_limit(__pos, __n1);
  925.       const size_type __len = std::min(__n1, __n2);
  926.       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  927.       if (!__r)
  928.     __r = __n1 - __n2;
  929.       return __r;
  930.     }
  931.  
  932.   // Inhibit implicit instantiations for required instantiations,
  933.   // which are defined via explicit instantiations elsewhere.
  934.   // NB: This syntax is a GNU extension.
  935. #if _GLIBCXX_EXTERN_TEMPLATE
  936.   extern template class basic_string<char>;
  937.   extern template
  938.     basic_istream<char>&
  939.     operator>>(basic_istream<char>&, string&);
  940.   extern template
  941.     basic_ostream<char>&
  942.     operator<<(basic_ostream<char>&, const string&);
  943.   extern template
  944.     basic_istream<char>&
  945.     getline(basic_istream<char>&, string&, char);
  946.   extern template
  947.     basic_istream<char>&
  948.     getline(basic_istream<char>&, string&);
  949.  
  950. #ifdef _GLIBCXX_USE_WCHAR_T
  951.   extern template class basic_string<wchar_t>;
  952.   extern template
  953.     basic_istream<wchar_t>&
  954.     operator>>(basic_istream<wchar_t>&, wstring&);
  955.   extern template
  956.     basic_ostream<wchar_t>&
  957.     operator<<(basic_ostream<wchar_t>&, const wstring&);
  958.   extern template
  959.     basic_istream<wchar_t>&
  960.     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
  961.   extern template
  962.     basic_istream<wchar_t>&
  963.     getline(basic_istream<wchar_t>&, wstring&);
  964. #endif
  965. #endif
  966. } // namespace std
  967.  
  968. #endif
  969.