1 // Components for manipulating sequences of characters -*- C++ -*-
2 
3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
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 _CPP_BITS_STRING_TCC
42 #define _CPP_BITS_STRING_TCC 1
43 
44 #pragma GCC system_header
45 
46 namespace std
47 {
48   template<typename _CharT, typename _Traits, typename _Alloc>
49     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
50     basic_string<_CharT, _Traits, _Alloc>::
51     _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
52 
53   template<typename _CharT, typename _Traits, typename _Alloc>
54     const _CharT
55     basic_string<_CharT, _Traits, _Alloc>::
56     _Rep::_S_terminal = _CharT();
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>::npos;
61 
62   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
63   // at static init time (before static ctors are run).
64   template<typename _CharT, typename _Traits, typename _Alloc>
65     typename basic_string<_CharT, _Traits, _Alloc>::size_type
66     basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
67     (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
68 
69   // NB: This is the special case for Input Iterators, used in
70   // istreambuf_iterators, etc.
71   // Input Iterators have a cost structure very different from
72   // pointers, calling for a different coding style.
73   template<typename _CharT, typename _Traits, typename _Alloc>
74     template<typename _InIter>
75       _CharT*
76       basic_string<_CharT, _Traits, _Alloc>::
77       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
78 		   input_iterator_tag)
79       {
80 	if (__beg == __end && __a == _Alloc())
81 	  return _S_empty_rep()._M_refcopy();
82 	// Avoid reallocation for common case.
83 	_CharT __buf[100];
84 	size_type __i = 0;
85 	while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
86 	  {
87 	    __buf[__i++] = *__beg;
88 	    ++__beg;
89 	  }
90 	_Rep* __r = _Rep::_S_create(__i, __a);
91 	traits_type::copy(__r->_M_refdata(), __buf, __i);
92 	__r->_M_length = __i;
93 	try
94 	  {
95 	    // NB: this loop looks precisely this way because
96 	    // it avoids comparing __beg != __end any more
97 	    // than strictly necessary; != might be expensive!
98 	    for (;;)
99 	      {
100 		_CharT* __p = __r->_M_refdata() + __r->_M_length;
101 		_CharT* __last = __r->_M_refdata() + __r->_M_capacity;
102 		for (;;)
103 		  {
104 		    if (__beg == __end)
105 		      {
106 			__r->_M_length = __p - __r->_M_refdata();
107 			*__p = _Rep::_S_terminal;       // grrr.
108 			return __r->_M_refdata();
109 		      }
110 		    if (__p == __last)
111 		      break;
112 		    *__p++ = *__beg;
113 		    ++__beg;
114 		  }
115 		// Allocate more space.
116 		size_type __len = __p - __r->_M_refdata();
117 		_Rep* __another = _Rep::_S_create(__len + 1, __a);
118 		traits_type::copy(__another->_M_refdata(),
119 				  __r->_M_refdata(), __len);
120 		__r->_M_destroy(__a);
121 		__r = __another;
122 		__r->_M_length = __len;
123 	      }
124 	  }
125 	catch(...)
126 	  {
127 	    __r->_M_destroy(__a);
128 	    __throw_exception_again;
129 	  }
130 	return 0;
131       }
132 
133   template<typename _CharT, typename _Traits, typename _Alloc>
134     template <class _InIter>
135       _CharT*
136       basic_string<_CharT, _Traits, _Alloc>::
137       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
138 		   forward_iterator_tag)
139       {
140 	if (__beg == __end && __a == _Alloc())
141 	  return _S_empty_rep()._M_refcopy();
142 
143 	// NB: Not required, but considered best practice.
144 	if (__builtin_expect(__beg == _InIter(), 0))
145 	  __throw_logic_error("attempt to create string with null pointer");
146 
147 	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
148 
149 	// Check for out_of_range and length_error exceptions.
150 	_Rep* __r = _Rep::_S_create(__dnew, __a);
151 	try
152 	  { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
153 	catch(...)
154 	  {
155 	    __r->_M_destroy(__a);
156 	    __throw_exception_again;
157 	  }
158 	__r->_M_length = __dnew;
159 
160 	__r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
161 	return __r->_M_refdata();
162       }
163 
164   template<typename _CharT, typename _Traits, typename _Alloc>
165     _CharT*
166     basic_string<_CharT, _Traits, _Alloc>::
167     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
168     {
169       if (__n == 0 && __a == _Alloc())
170 	return _S_empty_rep()._M_refcopy();
171 
172       // Check for out_of_range and length_error exceptions.
173       _Rep* __r = _Rep::_S_create(__n, __a);
174       try
175 	{
176 	  if (__n)
177 	    traits_type::assign(__r->_M_refdata(), __n, __c);
178 	}
179       catch(...)
180 	{
181 	  __r->_M_destroy(__a);
182 	  __throw_exception_again;
183 	}
184       __r->_M_length = __n;
185       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
186       return __r->_M_refdata();
187     }
188 
189   template<typename _CharT, typename _Traits, typename _Alloc>
190     basic_string<_CharT, _Traits, _Alloc>::
191     basic_string(const basic_string& __str)
192     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
193 		 __str.get_allocator())
194     { }
195 
196   template<typename _CharT, typename _Traits, typename _Alloc>
197     basic_string<_CharT, _Traits, _Alloc>::
198     basic_string(const _Alloc& __a)
199     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
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, size_type __n)
205     : _M_dataplus(_S_construct(__str._M_check(__pos),
206 			       __str._M_fold(__pos, __n), _Alloc()), _Alloc())
207     { }
208 
209   template<typename _CharT, typename _Traits, typename _Alloc>
210     basic_string<_CharT, _Traits, _Alloc>::
211     basic_string(const basic_string& __str, size_type __pos,
212 		 size_type __n, const _Alloc& __a)
213     : _M_dataplus(_S_construct(__str._M_check(__pos),
214 			       __str._M_fold(__pos, __n), __a), __a)
215     { }
216 
217   template<typename _CharT, typename _Traits, typename _Alloc>
218     basic_string<_CharT, _Traits, _Alloc>::
219     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
220     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
221     { }
222 
223   template<typename _CharT, typename _Traits, typename _Alloc>
224     basic_string<_CharT, _Traits, _Alloc>::
225     basic_string(const _CharT* __s, const _Alloc& __a)
226     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
227 			       __s + npos, __a), __a)
228     { }
229 
230   template<typename _CharT, typename _Traits, typename _Alloc>
231     basic_string<_CharT, _Traits, _Alloc>::
232     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
233     : _M_dataplus(_S_construct(__n, __c, __a), __a)
234     { }
235 
236   template<typename _CharT, typename _Traits, typename _Alloc>
237     template<typename _InputIter>
238     basic_string<_CharT, _Traits, _Alloc>::
239     basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
240     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
241     { }
242 
243   template<typename _CharT, typename _Traits, typename _Alloc>
244     basic_string<_CharT, _Traits, _Alloc>&
245     basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
246     {
247       if (_M_rep() != __str._M_rep())
248 	{
249 	  // XXX MT
250 	  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 basic_string& __str, size_type __pos, size_type __n)
262      {
263        const size_type __strsize = __str.size();
264        if (__pos > __strsize)
265 	 __throw_out_of_range("basic_string::assign");
266        const bool __testn = __n < __strsize - __pos;
267        const size_type __newsize = __testn ? __n : __strsize - __pos;
268        return this->assign(__str._M_data() + __pos, __newsize);
269      }
270 
271    template<typename _CharT, typename _Traits, typename _Alloc>
272      basic_string<_CharT, _Traits, _Alloc>&
273      basic_string<_CharT, _Traits, _Alloc>::
274      assign(const _CharT* __s, size_type __n)
275      {
276        if (__n > this->max_size())
277 	 __throw_length_error("basic_string::assign");
278        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
279 	   || less<const _CharT*>()(_M_data() + this->size(), __s))
280 	 return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
281        else
282 	 {
283 	   // Work in-place
284 	   const size_type __pos = __s - _M_data();
285 	   if (__pos >= __n)
286 	     traits_type::copy(_M_data(), __s, __n);
287 	   else if (__pos)
288 	     traits_type::move(_M_data(), __s, __n);
289 	   _M_rep()->_M_length = __n;
290 	   _M_data()[__n] = _Rep::_S_terminal;  // grr.
291 	   return *this;
292 	 }
293      }
294 
295    template<typename _CharT, typename _Traits, typename _Alloc>
296      basic_string<_CharT, _Traits, _Alloc>&
297      basic_string<_CharT, _Traits, _Alloc>::
298      insert(size_type __pos1, const basic_string& __str,
299             size_type __pos2, size_type __n)
300      {
301        const size_type __strsize = __str.size();
302        if (__pos2 > __strsize)
303 	 __throw_out_of_range("basic_string::insert");
304        const bool __testn = __n < __strsize - __pos2;
305        const size_type __newsize = __testn ? __n : __strsize - __pos2;
306        return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
307      }
308 
309    template<typename _CharT, typename _Traits, typename _Alloc>
310      basic_string<_CharT, _Traits, _Alloc>&
311      basic_string<_CharT, _Traits, _Alloc>::
312      insert(size_type __pos, const _CharT* __s, size_type __n)
313      {
314        const size_type __size = this->size();
315        if (__pos > __size)
316          __throw_out_of_range("basic_string::insert");
317        if (__size > this->max_size() - __n)
318          __throw_length_error("basic_string::insert");
319        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
320            || less<const _CharT*>()(_M_data() + __size, __s))
321          return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
322                                 __s, __s + __n);
323        else
324          {
325            // Work in-place. If _M_mutate reallocates the string, __s
326            // does not point anymore to valid data, therefore we save its
327            // offset, then we restore it.
328            const size_type __off = __s - _M_data();
329            _M_mutate(__pos, 0, __n);
330            __s = _M_data() + __off;
331            _CharT* __p = _M_data() + __pos;
332            if (__s  + __n <= __p)
333              traits_type::copy(__p, __s, __n);
334            else if (__s >= __p)
335              traits_type::copy(__p, __s + __n, __n);
336            else
337              {
338                traits_type::copy(__p, __s, __p - __s);
339                traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s));
340              }
341            return *this;
342          }
343      }
344 
345    template<typename _CharT, typename _Traits, typename _Alloc>
346      basic_string<_CharT, _Traits, _Alloc>&
347      basic_string<_CharT, _Traits, _Alloc>::
348      replace(size_type __pos, size_type __n1, const _CharT* __s,
349 	     size_type __n2)
350      {
351        const size_type __size = this->size();
352        if (__pos > __size)
353          __throw_out_of_range("basic_string::replace");
354        const bool __testn1 = __n1 < __size - __pos;
355        const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
356        if (__size - __foldn1 > this->max_size() - __n2)
357          __throw_length_error("basic_string::replace");
358        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
359            || less<const _CharT*>()(_M_data() + __size, __s))
360          return _M_replace_safe(_M_ibegin() + __pos,
361 				_M_ibegin() + __pos + __foldn1, __s, __s + __n2);
362        // Todo: optimized in-place replace.
363        else
364 	 return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
365 			   __s, __s + __n2,
366 			   typename iterator_traits<const _CharT*>::iterator_category());
367      }
368 
369   template<typename _CharT, typename _Traits, typename _Alloc>
370     void
371     basic_string<_CharT, _Traits, _Alloc>::_Rep::
372     _M_destroy(const _Alloc& __a) throw ()
373     {
374       size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
375       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
376     }
377 
378   template<typename _CharT, typename _Traits, typename _Alloc>
379     void
380     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
381     {
382       if (_M_rep()->_M_is_shared())
383 	_M_mutate(0, 0, 0);
384       _M_rep()->_M_set_leaked();
385     }
386 
387   // _M_mutate and, below, _M_clone, include, in the same form, an exponential
388   // growth policy, necessary to meet amortized linear time requirements of
389   // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
390   // The policy is active for allocations requiring an amount of memory above
391   // system pagesize. This is consistent with the requirements of the standard:
392   // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
393   template<typename _CharT, typename _Traits, typename _Alloc>
394     void
395     basic_string<_CharT, _Traits, _Alloc>::
396     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
397     {
398       size_type       __old_size = this->size();
399       const size_type __new_size = __old_size + __len2 - __len1;
400       const _CharT*        __src = _M_data()  + __pos + __len1;
401       const size_type __how_much = __old_size - __pos - __len1;
402 
403       if (_M_rep()->_M_is_shared() || __new_size > capacity())
404 	{
405 	  // Must reallocate.
406 	  allocator_type __a = get_allocator();
407 	  // See below (_S_create) for the meaning and value of these
408 	  // constants.
409 	  const size_type __pagesize = 4096;
410 	  const size_type __malloc_header_size = 4 * sizeof (void*);
411 	  // The biggest string which fits in a memory page
412 	  const size_type __page_capacity = (__pagesize - __malloc_header_size
413 					     - sizeof(_Rep) - sizeof(_CharT))
414 	    				     / sizeof(_CharT);
415 	  _Rep* __r;
416 	  if (__new_size > capacity() && __new_size > __page_capacity)
417 	    // Growing exponentially.
418 	    __r = _Rep::_S_create(__new_size > 2*capacity() ?
419 				  __new_size : 2*capacity(), __a);
420 	  else
421 	    __r = _Rep::_S_create(__new_size, __a);
422 	  try
423 	    {
424 	      if (__pos)
425 		traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
426 	      if (__how_much)
427 		traits_type::copy(__r->_M_refdata() + __pos + __len2,
428 				  __src, __how_much);
429 	    }
430 	  catch(...)
431 	    {
432 	      __r->_M_dispose(get_allocator());
433 	      __throw_exception_again;
434 	    }
435 	  _M_rep()->_M_dispose(__a);
436 	  _M_data(__r->_M_refdata());
437       }
438       else if (__how_much && __len1 != __len2)
439 	{
440 	  // Work in-place
441 	  traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
442 	}
443       _M_rep()->_M_set_sharable();
444       _M_rep()->_M_length = __new_size;
445       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
446     // You cannot leave those LWG people alone for a second.
447     }
448 
449   template<typename _CharT, typename _Traits, typename _Alloc>
450     void
451     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
452     {
453       if (__res > this->capacity() || _M_rep()->_M_is_shared())
454         {
455 	  if (__res > this->max_size())
456 	    __throw_length_error("basic_string::reserve");
457 	  // Make sure we don't shrink below the current size
458 	  if (__res < this->size())
459 	    __res = this->size();
460 	  allocator_type __a = get_allocator();
461 	  _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
462 	  _M_rep()->_M_dispose(__a);
463 	  _M_data(__tmp);
464         }
465     }
466 
467   template<typename _CharT, typename _Traits, typename _Alloc>
468     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
469     {
470       if (_M_rep()->_M_is_leaked())
471 	_M_rep()->_M_set_sharable();
472       if (__s._M_rep()->_M_is_leaked())
473 	__s._M_rep()->_M_set_sharable();
474       if (this->get_allocator() == __s.get_allocator())
475 	{
476 	  _CharT* __tmp = _M_data();
477 	  _M_data(__s._M_data());
478 	  __s._M_data(__tmp);
479 	}
480       // The code below can usually be optimized away.
481       else
482 	{
483 	  basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
484 	  basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
485 			      this->get_allocator());
486 	  *this = __tmp2;
487 	  __s = __tmp1;
488 	}
489     }
490 
491   template<typename _CharT, typename _Traits, typename _Alloc>
492     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
493     basic_string<_CharT, _Traits, _Alloc>::_Rep::
494     _S_create(size_t __capacity, const _Alloc& __alloc)
495     {
496       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
497 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
498       // 83.  String::npos vs. string::max_size()
499       if (__capacity > _S_max_size)
500 #else
501       if (__capacity == npos)
502 #endif
503 	__throw_length_error("basic_string::_S_create");
504 
505       // NB: Need an array of char_type[__capacity], plus a
506       // terminating null char_type() element, plus enough for the
507       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
508       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
509 
510       // The standard places no restriction on allocating more memory
511       // than is strictly needed within this layer at the moment or as
512       // requested by an explicit application call to reserve().  Many
513       // malloc implementations perform quite poorly when an
514       // application attempts to allocate memory in a stepwise fashion
515       // growing each allocation size by only 1 char.  Additionally,
516       // it makes little sense to allocate less linear memory than the
517       // natural blocking size of the malloc implementation.
518       // Unfortunately, we would need a somewhat low-level calculation
519       // with tuned parameters to get this perfect for any particular
520       // malloc implementation.  Fortunately, generalizations about
521       // common features seen among implementations seems to suffice.
522 
523       // __pagesize need not match the actual VM page size for good
524       // results in practice, thus we pick a common value on the low
525       // side.  __malloc_header_size is an estimate of the amount of
526       // overhead per memory allocation (in practice seen N * sizeof
527       // (void*) where N is 0, 2 or 4).  According to folklore,
528       // picking this value on the high side is better than
529       // low-balling it (especially when this algorithm is used with
530       // malloc implementations that allocate memory blocks rounded up
531       // to a size which is a power of 2).
532       const size_t __pagesize = 4096; // must be 2^i * __subpagesize
533       const size_t __subpagesize = 128; // should be >> __malloc_header_size
534       const size_t __malloc_header_size = 4 * sizeof (void*);
535       if ((__size + __malloc_header_size) > __pagesize)
536 	{
537 	  size_t __extra =
538 	    (__pagesize - ((__size + __malloc_header_size) % __pagesize))
539 	    % __pagesize;
540 	  __capacity += __extra / sizeof(_CharT);
541 	  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
542 	}
543       else if (__size > __subpagesize)
544 	{
545 	  size_t __extra =
546 	    (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
547 	    % __subpagesize;
548 	  __capacity += __extra / sizeof(_CharT);
549 	  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
550 	}
551 
552       // NB: Might throw, but no worries about a leak, mate: _Rep()
553       // does not throw.
554       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
555       _Rep *__p = new (__place) _Rep;
556       __p->_M_capacity = __capacity;
557       __p->_M_set_sharable();  // One reference.
558       __p->_M_length = 0;
559       return __p;
560     }
561 
562   template<typename _CharT, typename _Traits, typename _Alloc>
563     _CharT*
564     basic_string<_CharT, _Traits, _Alloc>::_Rep::
565     _M_clone(const _Alloc& __alloc, size_type __res)
566     {
567       // Requested capacity of the clone.
568       const size_type __requested_cap = _M_length + __res;
569       // See above (_S_create) for the meaning and value of these constants.
570       const size_type __pagesize = 4096;
571       const size_type __malloc_header_size = 4 * sizeof (void*);
572       // The biggest string which fits in a memory page.
573       const size_type __page_capacity =
574         (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
575         / sizeof(_CharT);
576       _Rep* __r;
577       if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
578         // Growing exponentially.
579         __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
580                               __requested_cap : 2*_M_capacity, __alloc);
581       else
582         __r = _Rep::_S_create(__requested_cap, __alloc);
583 
584       if (_M_length)
585 	{
586 	  try
587 	    { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
588 	  catch(...)
589 	    {
590 	      __r->_M_destroy(__alloc);
591 	      __throw_exception_again;
592 	    }
593 	}
594       __r->_M_length = _M_length;
595       return __r->_M_refdata();
596     }
597 
598   template<typename _CharT, typename _Traits, typename _Alloc>
599     void
600     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
601     {
602       if (__n > max_size())
603 	__throw_length_error("basic_string::resize");
604       size_type __size = this->size();
605       if (__size < __n)
606 	this->append(__n - __size, __c);
607       else if (__n < __size)
608 	this->erase(__n);
609       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
610     }
611 
612   // This is the general replace helper, which currently gets instantiated both
613   // for input iterators and reverse iterators. It buffers internally and then
614   // calls _M_replace_safe.
615   template<typename _CharT, typename _Traits, typename _Alloc>
616     template<typename _InputIter>
617       basic_string<_CharT, _Traits, _Alloc>&
618       basic_string<_CharT, _Traits, _Alloc>::
619       _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
620 		 _InputIter __k2, input_iterator_tag)
621       {
622 	// Save concerned source string data in a temporary.
623 	basic_string __s(__k1, __k2);
624 	return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
625       }
626 
627   // This is a special replace helper, which does not buffer internally
628   // and can be used in "safe" situations involving forward iterators,
629   // i.e., when source and destination ranges are known to not overlap.
630   template<typename _CharT, typename _Traits, typename _Alloc>
631     template<typename _ForwardIter>
632       basic_string<_CharT, _Traits, _Alloc>&
633       basic_string<_CharT, _Traits, _Alloc>::
634       _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
635 		      _ForwardIter __k2)
636       {
637 	size_type __dnew = static_cast<size_type>(std::distance(__k1, __k2));
638 	size_type __dold = __i2 - __i1;
639 	size_type __dmax = this->max_size();
640 
641 	if (__dmax <= __dnew)
642 	  __throw_length_error("basic_string::_M_replace");
643 	size_type __off = __i1 - _M_ibegin();
644 	_M_mutate(__off, __dold, __dnew);
645 
646 	// Invalidated __i1, __i2
647         if (__dnew)
648 	  _S_copy_chars(_M_data() + __off, __k1, __k2);
649 
650 	return *this;
651       }
652 
653   template<typename _CharT, typename _Traits, typename _Alloc>
654     basic_string<_CharT, _Traits, _Alloc>&
655     basic_string<_CharT, _Traits, _Alloc>::
656     replace(size_type __pos1, size_type __n1, const basic_string& __str,
657 	    size_type __pos2, size_type __n2)
658     {
659       const size_type __strsize = __str.size();
660       if (__pos2 > __strsize)
661 	__throw_out_of_range("basic_string::replace");
662       const bool __testn2 = __n2 < __strsize - __pos2;
663       const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
664       return this->replace(__pos1, __n1,
665 			   __str._M_data() + __pos2, __foldn2);
666     }
667 
668   template<typename _CharT, typename _Traits, typename _Alloc>
669     basic_string<_CharT, _Traits, _Alloc>&
670     basic_string<_CharT, _Traits, _Alloc>::
671     append(const basic_string& __str)
672     {
673       // Iff appending itself, string needs to pre-reserve the
674       // correct size so that _M_mutate does not clobber the
675       // iterators formed here.
676       size_type __size = __str.size();
677       size_type __len = __size + this->size();
678       if (__len > this->capacity())
679 	this->reserve(__len);
680       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
681 			     __str._M_iend());
682     }
683 
684   template<typename _CharT, typename _Traits, typename _Alloc>
685     basic_string<_CharT, _Traits, _Alloc>&
686     basic_string<_CharT, _Traits, _Alloc>::
687     append(const basic_string& __str, size_type __pos, size_type __n)
688     {
689       // Iff appending itself, string needs to pre-reserve the
690       // correct size so that _M_mutate does not clobber the
691       // iterators formed here.
692       size_type __len = std::min(size_type(__str.size() - __pos),
693 				 __n) + this->size();
694       if (__len > this->capacity())
695 	this->reserve(__len);
696       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
697 			     __str._M_fold(__pos, __n));
698     }
699 
700   template<typename _CharT, typename _Traits, typename _Alloc>
701     basic_string<_CharT, _Traits, _Alloc>&
702     basic_string<_CharT, _Traits, _Alloc>::
703     append(const _CharT* __s, size_type __n)
704     {
705       size_type __len = __n + this->size();
706       if (__len > this->capacity())
707 	this->reserve(__len);
708       return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
709     }
710 
711   template<typename _CharT, typename _Traits, typename _Alloc>
712     basic_string<_CharT, _Traits, _Alloc>&
713     basic_string<_CharT, _Traits, _Alloc>::
714     append(size_type __n, _CharT __c)
715     {
716       size_type __len = __n + this->size();
717       if (__len > this->capacity())
718 	this->reserve(__len);
719        return this->replace(_M_iend(), _M_iend(), __n, __c);
720     }
721 
722   template<typename _CharT, typename _Traits, typename _Alloc>
723     basic_string<_CharT, _Traits, _Alloc>
724     operator+(const _CharT* __lhs,
725 	      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
726     {
727       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
728       typedef typename __string_type::size_type	  __size_type;
729       __size_type __len = _Traits::length(__lhs);
730       __string_type __str;
731       __str.reserve(__len + __rhs.size());
732       __str.append(__lhs, __lhs + __len);
733       __str.append(__rhs);
734       return __str;
735     }
736 
737   template<typename _CharT, typename _Traits, typename _Alloc>
738     basic_string<_CharT, _Traits, _Alloc>
739     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
740     {
741       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
742       typedef typename __string_type::size_type	  __size_type;
743       __string_type __str;
744       __size_type __len = __rhs.size();
745       __str.reserve(__len + 1);
746       __str.append(__size_type(1), __lhs);
747       __str.append(__rhs);
748       return __str;
749     }
750 
751   template<typename _CharT, typename _Traits, typename _Alloc>
752     basic_string<_CharT, _Traits, _Alloc>&
753     basic_string<_CharT, _Traits, _Alloc>::
754     replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
755     {
756       size_type __n1 = __i2 - __i1;
757       size_type __off1 = __i1 - _M_ibegin();
758       if (max_size() - (this->size() - __n1) <= __n2)
759 	__throw_length_error("basic_string::replace");
760       _M_mutate (__off1, __n1, __n2);
761       // Invalidated __i1, __i2
762       if (__n2)
763 	traits_type::assign(_M_data() + __off1, __n2, __c);
764       return *this;
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     copy(_CharT* __s, size_type __n, size_type __pos) const
771     {
772       if (__pos > this->size())
773 	__throw_out_of_range("basic_string::copy");
774 
775       if (__n > this->size() - __pos)
776 	__n = this->size() - __pos;
777 
778       traits_type::copy(__s, _M_data() + __pos, __n);
779       // 21.3.5.7 par 3: do not append null.  (good.)
780       return __n;
781     }
782 
783   template<typename _CharT, typename _Traits, typename _Alloc>
784     typename basic_string<_CharT, _Traits, _Alloc>::size_type
785     basic_string<_CharT, _Traits, _Alloc>::
786     find(const _CharT* __s, size_type __pos, size_type __n) const
787     {
788       size_type __size = this->size();
789       size_t __xpos = __pos;
790       const _CharT* __data = _M_data();
791       for (; __xpos + __n <= __size; ++__xpos)
792 	if (traits_type::compare(__data + __xpos, __s, __n) == 0)
793 	  return __xpos;
794       return npos;
795     }
796 
797   template<typename _CharT, typename _Traits, typename _Alloc>
798     typename basic_string<_CharT, _Traits, _Alloc>::size_type
799     basic_string<_CharT, _Traits, _Alloc>::
800     find(_CharT __c, size_type __pos) const
801     {
802       size_type __size = this->size();
803       size_type __ret = npos;
804       if (__pos < __size)
805 	{
806 	  const _CharT* __data = _M_data();
807 	  size_type __n = __size - __pos;
808 	  const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
809 	  if (__p)
810 	    __ret = __p - __data;
811 	}
812       return __ret;
813     }
814 
815 
816   template<typename _CharT, typename _Traits, typename _Alloc>
817     typename basic_string<_CharT, _Traits, _Alloc>::size_type
818     basic_string<_CharT, _Traits, _Alloc>::
819     rfind(const _CharT* __s, size_type __pos, size_type __n) const
820     {
821       size_type __size = this->size();
822       if (__n <= __size)
823 	{
824 	  __pos = std::min(size_type(__size - __n), __pos);
825 	  const _CharT* __data = _M_data();
826 	  do
827 	    {
828 	      if (traits_type::compare(__data + __pos, __s, __n) == 0)
829 		return __pos;
830 	    }
831 	  while (__pos-- > 0);
832 	}
833       return npos;
834     }
835 
836   template<typename _CharT, typename _Traits, typename _Alloc>
837     typename basic_string<_CharT, _Traits, _Alloc>::size_type
838     basic_string<_CharT, _Traits, _Alloc>::
839     rfind(_CharT __c, size_type __pos) const
840     {
841       size_type __size = this->size();
842       if (__size)
843 	{
844 	  size_t __xpos = __size - 1;
845 	  if (__xpos > __pos)
846 	    __xpos = __pos;
847 
848 	  for (++__xpos; __xpos-- > 0; )
849 	    if (traits_type::eq(_M_data()[__xpos], __c))
850 	      return __xpos;
851 	}
852       return npos;
853     }
854 
855   template<typename _CharT, typename _Traits, typename _Alloc>
856     typename basic_string<_CharT, _Traits, _Alloc>::size_type
857     basic_string<_CharT, _Traits, _Alloc>::
858     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
859     {
860       for (; __n && __pos < this->size(); ++__pos)
861 	{
862 	  const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
863 	  if (__p)
864 	    return __pos;
865 	}
866       return npos;
867     }
868 
869   template<typename _CharT, typename _Traits, typename _Alloc>
870     typename basic_string<_CharT, _Traits, _Alloc>::size_type
871     basic_string<_CharT, _Traits, _Alloc>::
872     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
873     {
874       size_type __size = this->size();
875       if (__size && __n)
876 	{
877 	  if (--__size > __pos)
878 	    __size = __pos;
879 	  do
880 	    {
881 	      if (traits_type::find(__s, __n, _M_data()[__size]))
882 		return __size;
883 	    }
884 	  while (__size-- != 0);
885 	}
886       return npos;
887     }
888 
889   template<typename _CharT, typename _Traits, typename _Alloc>
890     typename basic_string<_CharT, _Traits, _Alloc>::size_type
891     basic_string<_CharT, _Traits, _Alloc>::
892     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
893     {
894       size_t __xpos = __pos;
895       for (; __xpos < this->size(); ++__xpos)
896 	if (!traits_type::find(__s, __n, _M_data()[__xpos]))
897 	  return __xpos;
898       return npos;
899     }
900 
901   template<typename _CharT, typename _Traits, typename _Alloc>
902     typename basic_string<_CharT, _Traits, _Alloc>::size_type
903     basic_string<_CharT, _Traits, _Alloc>::
904     find_first_not_of(_CharT __c, size_type __pos) const
905     {
906       size_t __xpos = __pos;
907       for (; __xpos < this->size(); ++__xpos)
908 	if (!traits_type::eq(_M_data()[__xpos], __c))
909 	  return __xpos;
910       return npos;
911     }
912 
913   template<typename _CharT, typename _Traits, typename _Alloc>
914     typename basic_string<_CharT, _Traits, _Alloc>::size_type
915     basic_string<_CharT, _Traits, _Alloc>::
916     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
917     {
918       size_type __size = this->size();
919       if (__size)
920 	{
921 	  if (--__size > __pos)
922 	    __size = __pos;
923 	  do
924 	    {
925 	      if (!traits_type::find(__s, __n, _M_data()[__size]))
926 		return __size;
927 	    }
928 	  while (__size--);
929 	}
930       return npos;
931     }
932 
933   template<typename _CharT, typename _Traits, typename _Alloc>
934     typename basic_string<_CharT, _Traits, _Alloc>::size_type
935     basic_string<_CharT, _Traits, _Alloc>::
936     find_last_not_of(_CharT __c, size_type __pos) const
937     {
938       size_type __size = this->size();
939       if (__size)
940 	{
941 	  if (--__size > __pos)
942 	    __size = __pos;
943 	  do
944 	    {
945 	      if (!traits_type::eq(_M_data()[__size], __c))
946 		return __size;
947 	    }
948 	  while (__size--);
949 	}
950       return npos;
951     }
952 
953   template<typename _CharT, typename _Traits, typename _Alloc>
954     int
955     basic_string<_CharT, _Traits, _Alloc>::
956     compare(size_type __pos, size_type __n, const basic_string& __str) const
957     {
958       size_type __size = this->size();
959       size_type __osize = __str.size();
960       if (__pos > __size)
961 	__throw_out_of_range("basic_string::compare");
962 
963       size_type __rsize= std::min(size_type(__size - __pos), __n);
964       size_type __len = std::min(__rsize, __osize);
965       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
966       if (!__r)
967 	__r = __rsize - __osize;
968       return __r;
969     }
970 
971   template<typename _CharT, typename _Traits, typename _Alloc>
972     int
973     basic_string<_CharT, _Traits, _Alloc>::
974     compare(size_type __pos1, size_type __n1, const basic_string& __str,
975 	    size_type __pos2, size_type __n2) const
976     {
977       size_type __size = this->size();
978       size_type __osize = __str.size();
979       if (__pos1 > __size || __pos2 > __osize)
980 	__throw_out_of_range("basic_string::compare");
981 
982       size_type __rsize = std::min(size_type(__size - __pos1), __n1);
983       size_type __rosize = std::min(size_type(__osize - __pos2), __n2);
984       size_type __len = std::min(__rsize, __rosize);
985       int __r = traits_type::compare(_M_data() + __pos1,
986 				     __str.data() + __pos2, __len);
987       if (!__r)
988 	__r = __rsize - __rosize;
989       return __r;
990     }
991 
992 
993   template<typename _CharT, typename _Traits, typename _Alloc>
994     int
995     basic_string<_CharT, _Traits, _Alloc>::
996     compare(const _CharT* __s) const
997     {
998       size_type __size = this->size();
999       size_type __osize = traits_type::length(__s);
1000       size_type __len = std::min(__size, __osize);
1001       int __r = traits_type::compare(_M_data(), __s, __len);
1002       if (!__r)
1003 	__r = __size - __osize;
1004       return __r;
1005     }
1006 
1007 
1008   template<typename _CharT, typename _Traits, typename _Alloc>
1009     int
1010     basic_string <_CharT, _Traits, _Alloc>::
1011     compare(size_type __pos, size_type __n1, const _CharT* __s) const
1012     {
1013       size_type __size = this->size();
1014       if (__pos > __size)
1015 	__throw_out_of_range("basic_string::compare");
1016 
1017       size_type __osize = traits_type::length(__s);
1018       size_type __rsize = std::min(size_type(__size - __pos), __n1);
1019       size_type __len = std::min(__rsize, __osize);
1020       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1021       if (!__r)
1022 	__r = __rsize - __osize;
1023       return __r;
1024     }
1025 
1026   template<typename _CharT, typename _Traits, typename _Alloc>
1027     int
1028     basic_string <_CharT, _Traits, _Alloc>::
1029     compare(size_type __pos, size_type __n1, const _CharT* __s,
1030 	    size_type __n2) const
1031     {
1032       size_type __size = this->size();
1033       if (__pos > __size)
1034 	__throw_out_of_range("basic_string::compare");
1035 
1036       size_type __osize = std::min(traits_type::length(__s), __n2);
1037       size_type __rsize = std::min(size_type(__size - __pos), __n1);
1038       size_type __len = std::min(__rsize, __osize);
1039       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1040       if (!__r)
1041 	__r = __rsize - __osize;
1042       return __r;
1043     }
1044 
1045   template <class _CharT, class _Traits, class _Alloc>
1046     void
1047     _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
1048 		   _CharT* __buf, typename _Alloc::size_type __bufsiz)
1049     {
1050       typedef typename _Alloc::size_type size_type;
1051       size_type __strsize = __str.size();
1052       size_type __bytes = std::min(__strsize, __bufsiz - 1);
1053       _Traits::copy(__buf, __str.data(), __bytes);
1054       __buf[__bytes] = _CharT();
1055     }
1056 
1057   // Inhibit implicit instantiations for required instantiations,
1058   // which are defined via explicit instantiations elsewhere.
1059   // NB: This syntax is a GNU extension.
1060 #if _GLIBCPP_EXTERN_TEMPLATE
1061   extern template class basic_string<char>;
1062   extern template
1063     basic_istream<char>&
1064     operator>>(basic_istream<char>&, string&);
1065   extern template
1066     basic_ostream<char>&
1067     operator<<(basic_ostream<char>&, const string&);
1068   extern template
1069     basic_istream<char>&
1070     getline(basic_istream<char>&, string&, char);
1071   extern template
1072     basic_istream<char>&
1073     getline(basic_istream<char>&, string&);
1074 
1075 #ifdef _GLIBCPP_USE_WCHAR_T
1076   extern template class basic_string<wchar_t>;
1077   extern template
1078     basic_istream<wchar_t>&
1079     operator>>(basic_istream<wchar_t>&, wstring&);
1080   extern template
1081     basic_ostream<wchar_t>&
1082     operator<<(basic_ostream<wchar_t>&, const wstring&);
1083   extern template
1084     basic_istream<wchar_t>&
1085     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1086   extern template
1087     basic_istream<wchar_t>&
1088     getline(basic_istream<wchar_t>&, wstring&);
1089 #endif
1090 #endif
1091 } // namespace std
1092 
1093 #endif
1094