libstdc++
basic_string.tcc
Go to the documentation of this file.
00001 // Components for manipulating sequences of characters -*- C++ -*-
00002 
00003 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
00004 // 2006, 2007, 2008, 2009, 2010, 2011
00005 // Free Software Foundation, Inc.
00006 //
00007 // This file is part of the GNU ISO C++ Library.  This library is free
00008 // software; you can redistribute it and/or modify it under the
00009 // terms of the GNU General Public License as published by the
00010 // Free Software Foundation; either version 3, or (at your option)
00011 // any later version.
00012 
00013 // This library is distributed in the hope that it will be useful,
00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 // GNU General Public License for more details.
00017 
00018 // Under Section 7 of GPL version 3, you are granted additional
00019 // permissions described in the GCC Runtime Library Exception, version
00020 // 3.1, as published by the Free Software Foundation.
00021 
00022 // You should have received a copy of the GNU General Public License and
00023 // a copy of the GCC Runtime Library Exception along with this program;
00024 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00025 // <http://www.gnu.org/licenses/>.
00026 
00027 /** @file bits/basic_string.tcc
00028  *  This is an internal header file, included by other library headers.
00029  *  Do not attempt to use it directly. @headername{string}
00030  */
00031 
00032 //
00033 // ISO C++ 14882: 21  Strings library
00034 //
00035 
00036 // Written by Jason Merrill based upon the specification by Takanori Adachi
00037 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
00038 
00039 #ifndef _BASIC_STRING_TCC
00040 #define _BASIC_STRING_TCC 1
00041 
00042 #pragma GCC system_header
00043 
00044 #include <bits/cxxabi_forced.h>
00045 
00046 namespace std _GLIBCXX_VISIBILITY(default)
00047 {
00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00049 
00050   template<typename _CharT, typename _Traits, typename _Alloc>
00051     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
00052     basic_string<_CharT, _Traits, _Alloc>::
00053     _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
00054 
00055   template<typename _CharT, typename _Traits, typename _Alloc>
00056     const _CharT
00057     basic_string<_CharT, _Traits, _Alloc>::
00058     _Rep::_S_terminal = _CharT();
00059 
00060   template<typename _CharT, typename _Traits, typename _Alloc>
00061     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
00062     basic_string<_CharT, _Traits, _Alloc>::npos;
00063 
00064   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
00065   // at static init time (before static ctors are run).
00066   template<typename _CharT, typename _Traits, typename _Alloc>
00067     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00068     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
00069     (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
00070       sizeof(size_type)];
00071 
00072   // NB: This is the special case for Input Iterators, used in
00073   // istreambuf_iterators, etc.
00074   // Input Iterators have a cost structure very different from
00075   // pointers, calling for a different coding style.
00076   template<typename _CharT, typename _Traits, typename _Alloc>
00077     template<typename _InIterator>
00078       _CharT*
00079       basic_string<_CharT, _Traits, _Alloc>::
00080       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00081            input_iterator_tag)
00082       {
00083 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
00084     if (__beg == __end && __a == _Alloc())
00085       return _S_empty_rep()._M_refdata();
00086 #endif
00087     // Avoid reallocation for common case.
00088     _CharT __buf[128];
00089     size_type __len = 0;
00090     while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
00091       {
00092         __buf[__len++] = *__beg;
00093         ++__beg;
00094       }
00095     _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
00096     _M_copy(__r->_M_refdata(), __buf, __len);
00097     __try
00098       {
00099         while (__beg != __end)
00100           {
00101         if (__len == __r->_M_capacity)
00102           {
00103             // Allocate more space.
00104             _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
00105             _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
00106             __r->_M_destroy(__a);
00107             __r = __another;
00108           }
00109         __r->_M_refdata()[__len++] = *__beg;
00110         ++__beg;
00111           }
00112       }
00113     __catch(...)
00114       {
00115         __r->_M_destroy(__a);
00116         __throw_exception_again;
00117       }
00118     __r->_M_set_length_and_sharable(__len);
00119     return __r->_M_refdata();
00120       }
00121 
00122   template<typename _CharT, typename _Traits, typename _Alloc>
00123     template <typename _InIterator>
00124       _CharT*
00125       basic_string<_CharT, _Traits, _Alloc>::
00126       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00127            forward_iterator_tag)
00128       {
00129 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
00130     if (__beg == __end && __a == _Alloc())
00131       return _S_empty_rep()._M_refdata();
00132 #endif
00133     // NB: Not required, but considered best practice.
00134     if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
00135       __throw_logic_error(__N("basic_string::_S_construct null not valid"));
00136 
00137     const size_type __dnew = static_cast<size_type>(std::distance(__beg,
00138                                       __end));
00139     // Check for out_of_range and length_error exceptions.
00140     _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
00141     __try
00142       { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
00143     __catch(...)
00144       {
00145         __r->_M_destroy(__a);
00146         __throw_exception_again;
00147       }
00148     __r->_M_set_length_and_sharable(__dnew);
00149     return __r->_M_refdata();
00150       }
00151 
00152   template<typename _CharT, typename _Traits, typename _Alloc>
00153     _CharT*
00154     basic_string<_CharT, _Traits, _Alloc>::
00155     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
00156     {
00157 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
00158       if (__n == 0 && __a == _Alloc())
00159     return _S_empty_rep()._M_refdata();
00160 #endif
00161       // Check for out_of_range and length_error exceptions.
00162       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
00163       if (__n)
00164     _M_assign(__r->_M_refdata(), __n, __c);
00165 
00166       __r->_M_set_length_and_sharable(__n);
00167       return __r->_M_refdata();
00168     }
00169 
00170   template<typename _CharT, typename _Traits, typename _Alloc>
00171     basic_string<_CharT, _Traits, _Alloc>::
00172     basic_string(const basic_string& __str)
00173     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
00174                       __str.get_allocator()),
00175           __str.get_allocator())
00176     { }
00177 
00178   template<typename _CharT, typename _Traits, typename _Alloc>
00179     basic_string<_CharT, _Traits, _Alloc>::
00180     basic_string(const _Alloc& __a)
00181     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
00182     { }
00183 
00184   template<typename _CharT, typename _Traits, typename _Alloc>
00185     basic_string<_CharT, _Traits, _Alloc>::
00186     basic_string(const basic_string& __str, size_type __pos, size_type __n)
00187     : _M_dataplus(_S_construct(__str._M_data()
00188                    + __str._M_check(__pos,
00189                         "basic_string::basic_string"),
00190                    __str._M_data() + __str._M_limit(__pos, __n)
00191                    + __pos, _Alloc()), _Alloc())
00192     { }
00193 
00194   template<typename _CharT, typename _Traits, typename _Alloc>
00195     basic_string<_CharT, _Traits, _Alloc>::
00196     basic_string(const basic_string& __str, size_type __pos,
00197          size_type __n, const _Alloc& __a)
00198     : _M_dataplus(_S_construct(__str._M_data()
00199                    + __str._M_check(__pos,
00200                         "basic_string::basic_string"),
00201                    __str._M_data() + __str._M_limit(__pos, __n)
00202                    + __pos, __a), __a)
00203     { }
00204 
00205   // TBD: DPG annotate
00206   template<typename _CharT, typename _Traits, typename _Alloc>
00207     basic_string<_CharT, _Traits, _Alloc>::
00208     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
00209     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
00210     { }
00211 
00212   // TBD: DPG annotate
00213   template<typename _CharT, typename _Traits, typename _Alloc>
00214     basic_string<_CharT, _Traits, _Alloc>::
00215     basic_string(const _CharT* __s, const _Alloc& __a)
00216     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
00217                    __s + npos, __a), __a)
00218     { }
00219 
00220   template<typename _CharT, typename _Traits, typename _Alloc>
00221     basic_string<_CharT, _Traits, _Alloc>::
00222     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
00223     : _M_dataplus(_S_construct(__n, __c, __a), __a)
00224     { }
00225 
00226   // TBD: DPG annotate
00227   template<typename _CharT, typename _Traits, typename _Alloc>
00228     template<typename _InputIterator>
00229     basic_string<_CharT, _Traits, _Alloc>::
00230     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
00231     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
00232     { }
00233 
00234 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00235   template<typename _CharT, typename _Traits, typename _Alloc>
00236     basic_string<_CharT, _Traits, _Alloc>::
00237     basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
00238     : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
00239     { }
00240 #endif
00241 
00242   template<typename _CharT, typename _Traits, typename _Alloc>
00243     basic_string<_CharT, _Traits, _Alloc>&
00244     basic_string<_CharT, _Traits, _Alloc>::
00245     assign(const basic_string& __str)
00246     {
00247       if (_M_rep() != __str._M_rep())
00248     {
00249       // XXX MT
00250       const allocator_type __a = this->get_allocator();
00251       _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
00252       _M_rep()->_M_dispose(__a);
00253       _M_data(__tmp);
00254     }
00255       return *this;
00256     }
00257 
00258   template<typename _CharT, typename _Traits, typename _Alloc>
00259     basic_string<_CharT, _Traits, _Alloc>&
00260     basic_string<_CharT, _Traits, _Alloc>::
00261     assign(const _CharT* __s, size_type __n)
00262     {
00263       __glibcxx_requires_string_len(__s, __n);
00264       _M_check_length(this->size(), __n, "basic_string::assign");
00265       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00266     return _M_replace_safe(size_type(0), this->size(), __s, __n);
00267       else
00268     {
00269       // Work in-place.
00270       const size_type __pos = __s - _M_data();
00271       if (__pos >= __n)
00272         _M_copy(_M_data(), __s, __n);
00273       else if (__pos)
00274         _M_move(_M_data(), __s, __n);
00275       _M_rep()->_M_set_length_and_sharable(__n);
00276       return *this;
00277     }
00278      }
00279 
00280   template<typename _CharT, typename _Traits, typename _Alloc>
00281     basic_string<_CharT, _Traits, _Alloc>&
00282     basic_string<_CharT, _Traits, _Alloc>::
00283     append(size_type __n, _CharT __c)
00284     {
00285       if (__n)
00286     {
00287       _M_check_length(size_type(0), __n, "basic_string::append");     
00288       const size_type __len = __n + this->size();
00289       if (__len > this->capacity() || _M_rep()->_M_is_shared())
00290         this->reserve(__len);
00291       _M_assign(_M_data() + this->size(), __n, __c);
00292       _M_rep()->_M_set_length_and_sharable(__len);
00293     }
00294       return *this;
00295     }
00296 
00297   template<typename _CharT, typename _Traits, typename _Alloc>
00298     basic_string<_CharT, _Traits, _Alloc>&
00299     basic_string<_CharT, _Traits, _Alloc>::
00300     append(const _CharT* __s, size_type __n)
00301     {
00302       __glibcxx_requires_string_len(__s, __n);
00303       if (__n)
00304     {
00305       _M_check_length(size_type(0), __n, "basic_string::append");
00306       const size_type __len = __n + this->size();
00307       if (__len > this->capacity() || _M_rep()->_M_is_shared())
00308         {
00309           if (_M_disjunct(__s))
00310         this->reserve(__len);
00311           else
00312         {
00313           const size_type __off = __s - _M_data();
00314           this->reserve(__len);
00315           __s = _M_data() + __off;
00316         }
00317         }
00318       _M_copy(_M_data() + this->size(), __s, __n);
00319       _M_rep()->_M_set_length_and_sharable(__len);
00320     }
00321       return *this;
00322     }
00323 
00324   template<typename _CharT, typename _Traits, typename _Alloc>
00325     basic_string<_CharT, _Traits, _Alloc>&
00326     basic_string<_CharT, _Traits, _Alloc>::
00327     append(const basic_string& __str)
00328     {
00329       const size_type __size = __str.size();
00330       if (__size)
00331     {
00332       const size_type __len = __size + this->size();
00333       if (__len > this->capacity() || _M_rep()->_M_is_shared())
00334         this->reserve(__len);
00335       _M_copy(_M_data() + this->size(), __str._M_data(), __size);
00336       _M_rep()->_M_set_length_and_sharable(__len);
00337     }
00338       return *this;
00339     }    
00340 
00341   template<typename _CharT, typename _Traits, typename _Alloc>
00342     basic_string<_CharT, _Traits, _Alloc>&
00343     basic_string<_CharT, _Traits, _Alloc>::
00344     append(const basic_string& __str, size_type __pos, size_type __n)
00345     {
00346       __str._M_check(__pos, "basic_string::append");
00347       __n = __str._M_limit(__pos, __n);
00348       if (__n)
00349     {
00350       const size_type __len = __n + this->size();
00351       if (__len > this->capacity() || _M_rep()->_M_is_shared())
00352         this->reserve(__len);
00353       _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
00354       _M_rep()->_M_set_length_and_sharable(__len);    
00355     }
00356       return *this;
00357     }
00358 
00359    template<typename _CharT, typename _Traits, typename _Alloc>
00360      basic_string<_CharT, _Traits, _Alloc>&
00361      basic_string<_CharT, _Traits, _Alloc>::
00362      insert(size_type __pos, const _CharT* __s, size_type __n)
00363      {
00364        __glibcxx_requires_string_len(__s, __n);
00365        _M_check(__pos, "basic_string::insert");
00366        _M_check_length(size_type(0), __n, "basic_string::insert");
00367        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00368          return _M_replace_safe(__pos, size_type(0), __s, __n);
00369        else
00370          {
00371            // Work in-place.
00372            const size_type __off = __s - _M_data();
00373            _M_mutate(__pos, 0, __n);
00374            __s = _M_data() + __off;
00375            _CharT* __p = _M_data() + __pos;
00376            if (__s  + __n <= __p)
00377              _M_copy(__p, __s, __n);
00378            else if (__s >= __p)
00379              _M_copy(__p, __s + __n, __n);
00380            else
00381              {
00382            const size_type __nleft = __p - __s;
00383                _M_copy(__p, __s, __nleft);
00384                _M_copy(__p + __nleft, __p + __n, __n - __nleft);
00385              }
00386            return *this;
00387          }
00388      }
00389 
00390    template<typename _CharT, typename _Traits, typename _Alloc>
00391      typename basic_string<_CharT, _Traits, _Alloc>::iterator
00392      basic_string<_CharT, _Traits, _Alloc>::
00393      erase(iterator __first, iterator __last)
00394      {
00395        _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
00396                 && __last <= _M_iend());
00397 
00398        // NB: This isn't just an optimization (bail out early when
00399        // there is nothing to do, really), it's also a correctness
00400        // issue vs MT, see libstdc++/40518.
00401        const size_type __size = __last - __first;
00402        if (__size)
00403      {
00404        const size_type __pos = __first - _M_ibegin();
00405        _M_mutate(__pos, __size, size_type(0));
00406        _M_rep()->_M_set_leaked();
00407        return iterator(_M_data() + __pos);
00408      }
00409        else
00410      return __first;
00411      }
00412 
00413    template<typename _CharT, typename _Traits, typename _Alloc>
00414      basic_string<_CharT, _Traits, _Alloc>&
00415      basic_string<_CharT, _Traits, _Alloc>::
00416      replace(size_type __pos, size_type __n1, const _CharT* __s,
00417          size_type __n2)
00418      {
00419        __glibcxx_requires_string_len(__s, __n2);
00420        _M_check(__pos, "basic_string::replace");
00421        __n1 = _M_limit(__pos, __n1);
00422        _M_check_length(__n1, __n2, "basic_string::replace");
00423        bool __left;
00424        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00425          return _M_replace_safe(__pos, __n1, __s, __n2);
00426        else if ((__left = __s + __n2 <= _M_data() + __pos)
00427         || _M_data() + __pos + __n1 <= __s)
00428      {
00429        // Work in-place: non-overlapping case.
00430        size_type __off = __s - _M_data();
00431        __left ? __off : (__off += __n2 - __n1);
00432        _M_mutate(__pos, __n1, __n2);
00433        _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
00434        return *this;
00435      }
00436        else
00437      {
00438        // Todo: overlapping case.
00439        const basic_string __tmp(__s, __n2);
00440        return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
00441      }
00442      }
00443 
00444   template<typename _CharT, typename _Traits, typename _Alloc>
00445     void
00446     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00447     _M_destroy(const _Alloc& __a) throw ()
00448     {
00449       const size_type __size = sizeof(_Rep_base) +
00450                            (this->_M_capacity + 1) * sizeof(_CharT);
00451       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
00452     }
00453 
00454   template<typename _CharT, typename _Traits, typename _Alloc>
00455     void
00456     basic_string<_CharT, _Traits, _Alloc>::
00457     _M_leak_hard()
00458     {
00459 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
00460       if (_M_rep() == &_S_empty_rep())
00461     return;
00462 #endif
00463       if (_M_rep()->_M_is_shared())
00464     _M_mutate(0, 0, 0);
00465       _M_rep()->_M_set_leaked();
00466     }
00467 
00468   template<typename _CharT, typename _Traits, typename _Alloc>
00469     void
00470     basic_string<_CharT, _Traits, _Alloc>::
00471     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
00472     {
00473       const size_type __old_size = this->size();
00474       const size_type __new_size = __old_size + __len2 - __len1;
00475       const size_type __how_much = __old_size - __pos - __len1;
00476 
00477       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
00478     {
00479       // Must reallocate.
00480       const allocator_type __a = get_allocator();
00481       _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
00482 
00483       if (__pos)
00484         _M_copy(__r->_M_refdata(), _M_data(), __pos);
00485       if (__how_much)
00486         _M_copy(__r->_M_refdata() + __pos + __len2,
00487             _M_data() + __pos + __len1, __how_much);
00488 
00489       _M_rep()->_M_dispose(__a);
00490       _M_data(__r->_M_refdata());
00491     }
00492       else if (__how_much && __len1 != __len2)
00493     {
00494       // Work in-place.
00495       _M_move(_M_data() + __pos + __len2,
00496           _M_data() + __pos + __len1, __how_much);
00497     }
00498       _M_rep()->_M_set_length_and_sharable(__new_size);
00499     }
00500 
00501   template<typename _CharT, typename _Traits, typename _Alloc>
00502     void
00503     basic_string<_CharT, _Traits, _Alloc>::
00504     reserve(size_type __res)
00505     {
00506       if (__res != this->capacity() || _M_rep()->_M_is_shared())
00507         {
00508       // Make sure we don't shrink below the current size
00509       if (__res < this->size())
00510         __res = this->size();
00511       const allocator_type __a = get_allocator();
00512       _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
00513       _M_rep()->_M_dispose(__a);
00514       _M_data(__tmp);
00515         }
00516     }
00517 
00518   template<typename _CharT, typename _Traits, typename _Alloc>
00519     void
00520     basic_string<_CharT, _Traits, _Alloc>::
00521     swap(basic_string& __s)
00522     {
00523       if (_M_rep()->_M_is_leaked())
00524     _M_rep()->_M_set_sharable();
00525       if (__s._M_rep()->_M_is_leaked())
00526     __s._M_rep()->_M_set_sharable();
00527       if (this->get_allocator() == __s.get_allocator())
00528     {
00529       _CharT* __tmp = _M_data();
00530       _M_data(__s._M_data());
00531       __s._M_data(__tmp);
00532     }
00533       // The code below can usually be optimized away.
00534       else
00535     {
00536       const basic_string __tmp1(_M_ibegin(), _M_iend(),
00537                     __s.get_allocator());
00538       const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
00539                     this->get_allocator());
00540       *this = __tmp2;
00541       __s = __tmp1;
00542     }
00543     }
00544 
00545   template<typename _CharT, typename _Traits, typename _Alloc>
00546     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
00547     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00548     _S_create(size_type __capacity, size_type __old_capacity,
00549           const _Alloc& __alloc)
00550     {
00551       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00552       // 83.  String::npos vs. string::max_size()
00553       if (__capacity > _S_max_size)
00554     __throw_length_error(__N("basic_string::_S_create"));
00555 
00556       // The standard places no restriction on allocating more memory
00557       // than is strictly needed within this layer at the moment or as
00558       // requested by an explicit application call to reserve().
00559 
00560       // Many malloc implementations perform quite poorly when an
00561       // application attempts to allocate memory in a stepwise fashion
00562       // growing each allocation size by only 1 char.  Additionally,
00563       // it makes little sense to allocate less linear memory than the
00564       // natural blocking size of the malloc implementation.
00565       // Unfortunately, we would need a somewhat low-level calculation
00566       // with tuned parameters to get this perfect for any particular
00567       // malloc implementation.  Fortunately, generalizations about
00568       // common features seen among implementations seems to suffice.
00569 
00570       // __pagesize need not match the actual VM page size for good
00571       // results in practice, thus we pick a common value on the low
00572       // side.  __malloc_header_size is an estimate of the amount of
00573       // overhead per memory allocation (in practice seen N * sizeof
00574       // (void*) where N is 0, 2 or 4).  According to folklore,
00575       // picking this value on the high side is better than
00576       // low-balling it (especially when this algorithm is used with
00577       // malloc implementations that allocate memory blocks rounded up
00578       // to a size which is a power of 2).
00579       const size_type __pagesize = 4096;
00580       const size_type __malloc_header_size = 4 * sizeof(void*);
00581 
00582       // The below implements an exponential growth policy, necessary to
00583       // meet amortized linear time requirements of the library: see
00584       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
00585       // It's active for allocations requiring an amount of memory above
00586       // system pagesize. This is consistent with the requirements of the
00587       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
00588       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
00589     __capacity = 2 * __old_capacity;
00590 
00591       // NB: Need an array of char_type[__capacity], plus a terminating
00592       // null char_type() element, plus enough for the _Rep data structure.
00593       // Whew. Seemingly so needy, yet so elemental.
00594       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
00595 
00596       const size_type __adj_size = __size + __malloc_header_size;
00597       if (__adj_size > __pagesize && __capacity > __old_capacity)
00598     {
00599       const size_type __extra = __pagesize - __adj_size % __pagesize;
00600       __capacity += __extra / sizeof(_CharT);
00601       // Never allocate a string bigger than _S_max_size.
00602       if (__capacity > _S_max_size)
00603         __capacity = _S_max_size;
00604       __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
00605     }
00606 
00607       // NB: Might throw, but no worries about a leak, mate: _Rep()
00608       // does not throw.
00609       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
00610       _Rep *__p = new (__place) _Rep;
00611       __p->_M_capacity = __capacity;
00612       // ABI compatibility - 3.4.x set in _S_create both
00613       // _M_refcount and _M_length.  All callers of _S_create
00614       // in basic_string.tcc then set just _M_length.
00615       // In 4.0.x and later both _M_refcount and _M_length
00616       // are initialized in the callers, unfortunately we can
00617       // have 3.4.x compiled code with _S_create callers inlined
00618       // calling 4.0.x+ _S_create.
00619       __p->_M_set_sharable();
00620       return __p;
00621     }
00622 
00623   template<typename _CharT, typename _Traits, typename _Alloc>
00624     _CharT*
00625     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00626     _M_clone(const _Alloc& __alloc, size_type __res)
00627     {
00628       // Requested capacity of the clone.
00629       const size_type __requested_cap = this->_M_length + __res;
00630       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
00631                   __alloc);
00632       if (this->_M_length)
00633     _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
00634 
00635       __r->_M_set_length_and_sharable(this->_M_length);
00636       return __r->_M_refdata();
00637     }
00638 
00639   template<typename _CharT, typename _Traits, typename _Alloc>
00640     void
00641     basic_string<_CharT, _Traits, _Alloc>::
00642     resize(size_type __n, _CharT __c)
00643     {
00644       const size_type __size = this->size();
00645       _M_check_length(__size, __n, "basic_string::resize");
00646       if (__size < __n)
00647     this->append(__n - __size, __c);
00648       else if (__n < __size)
00649     this->erase(__n);
00650       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
00651     }
00652 
00653   template<typename _CharT, typename _Traits, typename _Alloc>
00654     template<typename _InputIterator>
00655       basic_string<_CharT, _Traits, _Alloc>&
00656       basic_string<_CharT, _Traits, _Alloc>::
00657       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
00658               _InputIterator __k2, __false_type)
00659       {
00660     const basic_string __s(__k1, __k2);
00661     const size_type __n1 = __i2 - __i1;
00662     _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
00663     return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
00664                    __s.size());
00665       }
00666 
00667   template<typename _CharT, typename _Traits, typename _Alloc>
00668     basic_string<_CharT, _Traits, _Alloc>&
00669     basic_string<_CharT, _Traits, _Alloc>::
00670     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
00671            _CharT __c)
00672     {
00673       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
00674       _M_mutate(__pos1, __n1, __n2);
00675       if (__n2)
00676     _M_assign(_M_data() + __pos1, __n2, __c);
00677       return *this;
00678     }
00679 
00680   template<typename _CharT, typename _Traits, typename _Alloc>
00681     basic_string<_CharT, _Traits, _Alloc>&
00682     basic_string<_CharT, _Traits, _Alloc>::
00683     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
00684             size_type __n2)
00685     {
00686       _M_mutate(__pos1, __n1, __n2);
00687       if (__n2)
00688     _M_copy(_M_data() + __pos1, __s, __n2);
00689       return *this;
00690     }
00691    
00692   template<typename _CharT, typename _Traits, typename _Alloc>
00693     basic_string<_CharT, _Traits, _Alloc>
00694     operator+(const _CharT* __lhs,
00695           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00696     {
00697       __glibcxx_requires_string(__lhs);
00698       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
00699       typedef typename __string_type::size_type   __size_type;
00700       const __size_type __len = _Traits::length(__lhs);
00701       __string_type __str;
00702       __str.reserve(__len + __rhs.size());
00703       __str.append(__lhs, __len);
00704       __str.append(__rhs);
00705       return __str;
00706     }
00707 
00708   template<typename _CharT, typename _Traits, typename _Alloc>
00709     basic_string<_CharT, _Traits, _Alloc>
00710     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00711     {
00712       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
00713       typedef typename __string_type::size_type   __size_type;
00714       __string_type __str;
00715       const __size_type __len = __rhs.size();
00716       __str.reserve(__len + 1);
00717       __str.append(__size_type(1), __lhs);
00718       __str.append(__rhs);
00719       return __str;
00720     }
00721 
00722   template<typename _CharT, typename _Traits, typename _Alloc>
00723     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00724     basic_string<_CharT, _Traits, _Alloc>::
00725     copy(_CharT* __s, size_type __n, size_type __pos) const
00726     {
00727       _M_check(__pos, "basic_string::copy");
00728       __n = _M_limit(__pos, __n);
00729       __glibcxx_requires_string_len(__s, __n);
00730       if (__n)
00731     _M_copy(__s, _M_data() + __pos, __n);
00732       // 21.3.5.7 par 3: do not append null.  (good.)
00733       return __n;
00734     }
00735 
00736   template<typename _CharT, typename _Traits, typename _Alloc>
00737     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00738     basic_string<_CharT, _Traits, _Alloc>::
00739     find(const _CharT* __s, size_type __pos, size_type __n) const
00740     {
00741       __glibcxx_requires_string_len(__s, __n);
00742       const size_type __size = this->size();
00743       const _CharT* __data = _M_data();
00744 
00745       if (__n == 0)
00746     return __pos <= __size ? __pos : npos;
00747 
00748       if (__n <= __size)
00749     {
00750       for (; __pos <= __size - __n; ++__pos)
00751         if (traits_type::eq(__data[__pos], __s[0])
00752         && traits_type::compare(__data + __pos + 1,
00753                     __s + 1, __n - 1) == 0)
00754           return __pos;
00755     }
00756       return npos;
00757     }
00758 
00759   template<typename _CharT, typename _Traits, typename _Alloc>
00760     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00761     basic_string<_CharT, _Traits, _Alloc>::
00762     find(_CharT __c, size_type __pos) const
00763     {
00764       size_type __ret = npos;
00765       const size_type __size = this->size();
00766       if (__pos < __size)
00767     {
00768       const _CharT* __data = _M_data();
00769       const size_type __n = __size - __pos;
00770       const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
00771       if (__p)
00772         __ret = __p - __data;
00773     }
00774       return __ret;
00775     }
00776 
00777   template<typename _CharT, typename _Traits, typename _Alloc>
00778     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00779     basic_string<_CharT, _Traits, _Alloc>::
00780     rfind(const _CharT* __s, size_type __pos, size_type __n) const
00781     {
00782       __glibcxx_requires_string_len(__s, __n);
00783       const size_type __size = this->size();
00784       if (__n <= __size)
00785     {
00786       __pos = std::min(size_type(__size - __n), __pos);
00787       const _CharT* __data = _M_data();
00788       do
00789         {
00790           if (traits_type::compare(__data + __pos, __s, __n) == 0)
00791         return __pos;
00792         }
00793       while (__pos-- > 0);
00794     }
00795       return npos;
00796     }
00797 
00798   template<typename _CharT, typename _Traits, typename _Alloc>
00799     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00800     basic_string<_CharT, _Traits, _Alloc>::
00801     rfind(_CharT __c, size_type __pos) const
00802     {
00803       size_type __size = this->size();
00804       if (__size)
00805     {
00806       if (--__size > __pos)
00807         __size = __pos;
00808       for (++__size; __size-- > 0; )
00809         if (traits_type::eq(_M_data()[__size], __c))
00810           return __size;
00811     }
00812       return npos;
00813     }
00814 
00815   template<typename _CharT, typename _Traits, typename _Alloc>
00816     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00817     basic_string<_CharT, _Traits, _Alloc>::
00818     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
00819     {
00820       __glibcxx_requires_string_len(__s, __n);
00821       for (; __n && __pos < this->size(); ++__pos)
00822     {
00823       const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
00824       if (__p)
00825         return __pos;
00826     }
00827       return npos;
00828     }
00829 
00830   template<typename _CharT, typename _Traits, typename _Alloc>
00831     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00832     basic_string<_CharT, _Traits, _Alloc>::
00833     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
00834     {
00835       __glibcxx_requires_string_len(__s, __n);
00836       size_type __size = this->size();
00837       if (__size && __n)
00838     {
00839       if (--__size > __pos)
00840         __size = __pos;
00841       do
00842         {
00843           if (traits_type::find(__s, __n, _M_data()[__size]))
00844         return __size;
00845         }
00846       while (__size-- != 0);
00847     }
00848       return npos;
00849     }
00850 
00851   template<typename _CharT, typename _Traits, typename _Alloc>
00852     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00853     basic_string<_CharT, _Traits, _Alloc>::
00854     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
00855     {
00856       __glibcxx_requires_string_len(__s, __n);
00857       for (; __pos < this->size(); ++__pos)
00858     if (!traits_type::find(__s, __n, _M_data()[__pos]))
00859       return __pos;
00860       return npos;
00861     }
00862 
00863   template<typename _CharT, typename _Traits, typename _Alloc>
00864     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00865     basic_string<_CharT, _Traits, _Alloc>::
00866     find_first_not_of(_CharT __c, size_type __pos) const
00867     {
00868       for (; __pos < this->size(); ++__pos)
00869     if (!traits_type::eq(_M_data()[__pos], __c))
00870       return __pos;
00871       return npos;
00872     }
00873 
00874   template<typename _CharT, typename _Traits, typename _Alloc>
00875     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00876     basic_string<_CharT, _Traits, _Alloc>::
00877     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
00878     {
00879       __glibcxx_requires_string_len(__s, __n);
00880       size_type __size = this->size();
00881       if (__size)
00882     {
00883       if (--__size > __pos)
00884         __size = __pos;
00885       do
00886         {
00887           if (!traits_type::find(__s, __n, _M_data()[__size]))
00888         return __size;
00889         }
00890       while (__size--);
00891     }
00892       return npos;
00893     }
00894 
00895   template<typename _CharT, typename _Traits, typename _Alloc>
00896     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00897     basic_string<_CharT, _Traits, _Alloc>::
00898     find_last_not_of(_CharT __c, size_type __pos) const
00899     {
00900       size_type __size = this->size();
00901       if (__size)
00902     {
00903       if (--__size > __pos)
00904         __size = __pos;
00905       do
00906         {
00907           if (!traits_type::eq(_M_data()[__size], __c))
00908         return __size;
00909         }
00910       while (__size--);
00911     }
00912       return npos;
00913     }
00914 
00915   template<typename _CharT, typename _Traits, typename _Alloc>
00916     int
00917     basic_string<_CharT, _Traits, _Alloc>::
00918     compare(size_type __pos, size_type __n, const basic_string& __str) const
00919     {
00920       _M_check(__pos, "basic_string::compare");
00921       __n = _M_limit(__pos, __n);
00922       const size_type __osize = __str.size();
00923       const size_type __len = std::min(__n, __osize);
00924       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
00925       if (!__r)
00926     __r = _S_compare(__n, __osize);
00927       return __r;
00928     }
00929 
00930   template<typename _CharT, typename _Traits, typename _Alloc>
00931     int
00932     basic_string<_CharT, _Traits, _Alloc>::
00933     compare(size_type __pos1, size_type __n1, const basic_string& __str,
00934         size_type __pos2, size_type __n2) const
00935     {
00936       _M_check(__pos1, "basic_string::compare");
00937       __str._M_check(__pos2, "basic_string::compare");
00938       __n1 = _M_limit(__pos1, __n1);
00939       __n2 = __str._M_limit(__pos2, __n2);
00940       const size_type __len = std::min(__n1, __n2);
00941       int __r = traits_type::compare(_M_data() + __pos1,
00942                      __str.data() + __pos2, __len);
00943       if (!__r)
00944     __r = _S_compare(__n1, __n2);
00945       return __r;
00946     }
00947 
00948   template<typename _CharT, typename _Traits, typename _Alloc>
00949     int
00950     basic_string<_CharT, _Traits, _Alloc>::
00951     compare(const _CharT* __s) const
00952     {
00953       __glibcxx_requires_string(__s);
00954       const size_type __size = this->size();
00955       const size_type __osize = traits_type::length(__s);
00956       const size_type __len = std::min(__size, __osize);
00957       int __r = traits_type::compare(_M_data(), __s, __len);
00958       if (!__r)
00959     __r = _S_compare(__size, __osize);
00960       return __r;
00961     }
00962 
00963   template<typename _CharT, typename _Traits, typename _Alloc>
00964     int
00965     basic_string <_CharT, _Traits, _Alloc>::
00966     compare(size_type __pos, size_type __n1, const _CharT* __s) const
00967     {
00968       __glibcxx_requires_string(__s);
00969       _M_check(__pos, "basic_string::compare");
00970       __n1 = _M_limit(__pos, __n1);
00971       const size_type __osize = traits_type::length(__s);
00972       const size_type __len = std::min(__n1, __osize);
00973       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
00974       if (!__r)
00975     __r = _S_compare(__n1, __osize);
00976       return __r;
00977     }
00978 
00979   template<typename _CharT, typename _Traits, typename _Alloc>
00980     int
00981     basic_string <_CharT, _Traits, _Alloc>::
00982     compare(size_type __pos, size_type __n1, const _CharT* __s,
00983         size_type __n2) const
00984     {
00985       __glibcxx_requires_string_len(__s, __n2);
00986       _M_check(__pos, "basic_string::compare");
00987       __n1 = _M_limit(__pos, __n1);
00988       const size_type __len = std::min(__n1, __n2);
00989       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
00990       if (!__r)
00991     __r = _S_compare(__n1, __n2);
00992       return __r;
00993     }
00994 
00995   // 21.3.7.9 basic_string::getline and operators
00996   template<typename _CharT, typename _Traits, typename _Alloc>
00997     basic_istream<_CharT, _Traits>&
00998     operator>>(basic_istream<_CharT, _Traits>& __in,
00999            basic_string<_CharT, _Traits, _Alloc>& __str)
01000     {
01001       typedef basic_istream<_CharT, _Traits>        __istream_type;
01002       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
01003       typedef typename __istream_type::ios_base         __ios_base;
01004       typedef typename __istream_type::int_type     __int_type;
01005       typedef typename __string_type::size_type     __size_type;
01006       typedef ctype<_CharT>             __ctype_type;
01007       typedef typename __ctype_type::ctype_base         __ctype_base;
01008 
01009       __size_type __extracted = 0;
01010       typename __ios_base::iostate __err = __ios_base::goodbit;
01011       typename __istream_type::sentry __cerb(__in, false);
01012       if (__cerb)
01013     {
01014       __try
01015         {
01016           // Avoid reallocation for common case.
01017           __str.erase();
01018           _CharT __buf[128];
01019           __size_type __len = 0;          
01020           const streamsize __w = __in.width();
01021           const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
01022                                       : __str.max_size();
01023           const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
01024           const __int_type __eof = _Traits::eof();
01025           __int_type __c = __in.rdbuf()->sgetc();
01026 
01027           while (__extracted < __n
01028              && !_Traits::eq_int_type(__c, __eof)
01029              && !__ct.is(__ctype_base::space,
01030                  _Traits::to_char_type(__c)))
01031         {
01032           if (__len == sizeof(__buf) / sizeof(_CharT))
01033             {
01034               __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
01035               __len = 0;
01036             }
01037           __buf[__len++] = _Traits::to_char_type(__c);
01038           ++__extracted;
01039           __c = __in.rdbuf()->snextc();
01040         }
01041           __str.append(__buf, __len);
01042 
01043           if (_Traits::eq_int_type(__c, __eof))
01044         __err |= __ios_base::eofbit;
01045           __in.width(0);
01046         }
01047       __catch(__cxxabiv1::__forced_unwind&)
01048         {
01049           __in._M_setstate(__ios_base::badbit);
01050           __throw_exception_again;
01051         }
01052       __catch(...)
01053         {
01054           // _GLIBCXX_RESOLVE_LIB_DEFECTS
01055           // 91. Description of operator>> and getline() for string<>
01056           // might cause endless loop
01057           __in._M_setstate(__ios_base::badbit);
01058         }
01059     }
01060       // 211.  operator>>(istream&, string&) doesn't set failbit
01061       if (!__extracted)
01062     __err |= __ios_base::failbit;
01063       if (__err)
01064     __in.setstate(__err);
01065       return __in;
01066     }
01067 
01068   template<typename _CharT, typename _Traits, typename _Alloc>
01069     basic_istream<_CharT, _Traits>&
01070     getline(basic_istream<_CharT, _Traits>& __in,
01071         basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
01072     {
01073       typedef basic_istream<_CharT, _Traits>        __istream_type;
01074       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
01075       typedef typename __istream_type::ios_base         __ios_base;
01076       typedef typename __istream_type::int_type     __int_type;
01077       typedef typename __string_type::size_type     __size_type;
01078 
01079       __size_type __extracted = 0;
01080       const __size_type __n = __str.max_size();
01081       typename __ios_base::iostate __err = __ios_base::goodbit;
01082       typename __istream_type::sentry __cerb(__in, true);
01083       if (__cerb)
01084     {
01085       __try
01086         {
01087           __str.erase();
01088           const __int_type __idelim = _Traits::to_int_type(__delim);
01089           const __int_type __eof = _Traits::eof();
01090           __int_type __c = __in.rdbuf()->sgetc();
01091 
01092           while (__extracted < __n
01093              && !_Traits::eq_int_type(__c, __eof)
01094              && !_Traits::eq_int_type(__c, __idelim))
01095         {
01096           __str += _Traits::to_char_type(__c);
01097           ++__extracted;
01098           __c = __in.rdbuf()->snextc();
01099         }
01100 
01101           if (_Traits::eq_int_type(__c, __eof))
01102         __err |= __ios_base::eofbit;
01103           else if (_Traits::eq_int_type(__c, __idelim))
01104         {
01105           ++__extracted;          
01106           __in.rdbuf()->sbumpc();
01107         }
01108           else
01109         __err |= __ios_base::failbit;
01110         }
01111       __catch(__cxxabiv1::__forced_unwind&)
01112         {
01113           __in._M_setstate(__ios_base::badbit);
01114           __throw_exception_again;
01115         }
01116       __catch(...)
01117         {
01118           // _GLIBCXX_RESOLVE_LIB_DEFECTS
01119           // 91. Description of operator>> and getline() for string<>
01120           // might cause endless loop
01121           __in._M_setstate(__ios_base::badbit);
01122         }
01123     }
01124       if (!__extracted)
01125     __err |= __ios_base::failbit;
01126       if (__err)
01127     __in.setstate(__err);
01128       return __in;
01129     }
01130 
01131   // Inhibit implicit instantiations for required instantiations,
01132   // which are defined via explicit instantiations elsewhere.
01133 #if _GLIBCXX_EXTERN_TEMPLATE > 0
01134   extern template class basic_string<char>;
01135   extern template
01136     basic_istream<char>&
01137     operator>>(basic_istream<char>&, string&);
01138   extern template
01139     basic_ostream<char>&
01140     operator<<(basic_ostream<char>&, const string&);
01141   extern template
01142     basic_istream<char>&
01143     getline(basic_istream<char>&, string&, char);
01144   extern template
01145     basic_istream<char>&
01146     getline(basic_istream<char>&, string&);
01147 
01148 #ifdef _GLIBCXX_USE_WCHAR_T
01149   extern template class basic_string<wchar_t>;
01150   extern template
01151     basic_istream<wchar_t>&
01152     operator>>(basic_istream<wchar_t>&, wstring&);
01153   extern template
01154     basic_ostream<wchar_t>&
01155     operator<<(basic_ostream<wchar_t>&, const wstring&);
01156   extern template
01157     basic_istream<wchar_t>&
01158     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
01159   extern template
01160     basic_istream<wchar_t>&
01161     getline(basic_istream<wchar_t>&, wstring&);
01162 #endif
01163 #endif
01164 
01165 _GLIBCXX_END_NAMESPACE_VERSION
01166 } // namespace std
01167 
01168 #endif