libstdc++
basic_string.tcc
Go to the documentation of this file.
1 // Components for manipulating sequences of characters -*- C++ -*-
2 
3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
4 // 2006, 2007, 2008, 2009, 2010, 2011
5 // Free Software Foundation, Inc.
6 //
7 // This file is part of the GNU ISO C++ Library. This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
11 // any later version.
12 
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
17 
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
21 
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 // <http://www.gnu.org/licenses/>.
26 
27 /** @file bits/basic_string.tcc
28  * This is an internal header file, included by other library headers.
29  * Do not attempt to use it directly. @headername{string}
30  */
31 
32 //
33 // ISO C++ 14882: 21 Strings library
34 //
35 
36 // Written by Jason Merrill based upon the specification by Takanori Adachi
37 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882.
38 
39 #ifndef _BASIC_STRING_TCC
40 #define _BASIC_STRING_TCC 1
41 
42 #pragma GCC system_header
43 
44 #include <bits/cxxabi_forced.h>
45 
46 namespace std _GLIBCXX_VISIBILITY(default)
47 {
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
49 
50  template<typename _CharT, typename _Traits, typename _Alloc>
51  const typename basic_string<_CharT, _Traits, _Alloc>::size_type
52  basic_string<_CharT, _Traits, _Alloc>::
53  _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
54 
55  template<typename _CharT, typename _Traits, typename _Alloc>
56  const _CharT
57  basic_string<_CharT, _Traits, _Alloc>::
58  _Rep::_S_terminal = _CharT();
59 
60  template<typename _CharT, typename _Traits, typename _Alloc>
61  const typename basic_string<_CharT, _Traits, _Alloc>::size_type
62  basic_string<_CharT, _Traits, _Alloc>::npos;
63 
64  // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
65  // at static init time (before static ctors are run).
66  template<typename _CharT, typename _Traits, typename _Alloc>
67  typename basic_string<_CharT, _Traits, _Alloc>::size_type
68  basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
69  (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
70  sizeof(size_type)];
71 
72  // NB: This is the special case for Input Iterators, used in
73  // istreambuf_iterators, etc.
74  // Input Iterators have a cost structure very different from
75  // pointers, calling for a different coding style.
76  template<typename _CharT, typename _Traits, typename _Alloc>
77  template<typename _InIterator>
78  _CharT*
79  basic_string<_CharT, _Traits, _Alloc>::
80  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
81  input_iterator_tag)
82  {
83 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
84  if (__beg == __end && __a == _Alloc())
85  return _S_empty_rep()._M_refdata();
86 #endif
87  // Avoid reallocation for common case.
88  _CharT __buf[128];
89  size_type __len = 0;
90  while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
91  {
92  __buf[__len++] = *__beg;
93  ++__beg;
94  }
95  _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
96  _M_copy(__r->_M_refdata(), __buf, __len);
97  __try
98  {
99  while (__beg != __end)
100  {
101  if (__len == __r->_M_capacity)
102  {
103  // Allocate more space.
104  _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
105  _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
106  __r->_M_destroy(__a);
107  __r = __another;
108  }
109  __r->_M_refdata()[__len++] = *__beg;
110  ++__beg;
111  }
112  }
113  __catch(...)
114  {
115  __r->_M_destroy(__a);
116  __throw_exception_again;
117  }
118  __r->_M_set_length_and_sharable(__len);
119  return __r->_M_refdata();
120  }
121 
122  template<typename _CharT, typename _Traits, typename _Alloc>
123  template <typename _InIterator>
124  _CharT*
125  basic_string<_CharT, _Traits, _Alloc>::
126  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
127  forward_iterator_tag)
128  {
129 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
130  if (__beg == __end && __a == _Alloc())
131  return _S_empty_rep()._M_refdata();
132 #endif
133  // NB: Not required, but considered best practice.
134  if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
135  __throw_logic_error(__N("basic_string::_S_construct null not valid"));
136 
137  const size_type __dnew = static_cast<size_type>(std::distance(__beg,
138  __end));
139  // Check for out_of_range and length_error exceptions.
140  _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
141  __try
142  { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
143  __catch(...)
144  {
145  __r->_M_destroy(__a);
146  __throw_exception_again;
147  }
148  __r->_M_set_length_and_sharable(__dnew);
149  return __r->_M_refdata();
150  }
151 
152  template<typename _CharT, typename _Traits, typename _Alloc>
153  _CharT*
154  basic_string<_CharT, _Traits, _Alloc>::
155  _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
156  {
157 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
158  if (__n == 0 && __a == _Alloc())
159  return _S_empty_rep()._M_refdata();
160 #endif
161  // Check for out_of_range and length_error exceptions.
162  _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
163  if (__n)
164  _M_assign(__r->_M_refdata(), __n, __c);
165 
166  __r->_M_set_length_and_sharable(__n);
167  return __r->_M_refdata();
168  }
169 
170  template<typename _CharT, typename _Traits, typename _Alloc>
171  basic_string<_CharT, _Traits, _Alloc>::
172  basic_string(const basic_string& __str)
173  : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
174  __str.get_allocator()),
175  __str.get_allocator())
176  { }
177 
178  template<typename _CharT, typename _Traits, typename _Alloc>
179  basic_string<_CharT, _Traits, _Alloc>::
180  basic_string(const _Alloc& __a)
181  : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
182  { }
183 
184  template<typename _CharT, typename _Traits, typename _Alloc>
185  basic_string<_CharT, _Traits, _Alloc>::
186  basic_string(const basic_string& __str, size_type __pos, size_type __n)
187  : _M_dataplus(_S_construct(__str._M_data()
188  + __str._M_check(__pos,
189  "basic_string::basic_string"),
190  __str._M_data() + __str._M_limit(__pos, __n)
191  + __pos, _Alloc()), _Alloc())
192  { }
193 
194  template<typename _CharT, typename _Traits, typename _Alloc>
195  basic_string<_CharT, _Traits, _Alloc>::
196  basic_string(const basic_string& __str, size_type __pos,
197  size_type __n, const _Alloc& __a)
198  : _M_dataplus(_S_construct(__str._M_data()
199  + __str._M_check(__pos,
200  "basic_string::basic_string"),
201  __str._M_data() + __str._M_limit(__pos, __n)
202  + __pos, __a), __a)
203  { }
204 
205  // TBD: DPG annotate
206  template<typename _CharT, typename _Traits, typename _Alloc>
207  basic_string<_CharT, _Traits, _Alloc>::
208  basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
209  : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
210  { }
211 
212  // TBD: DPG annotate
213  template<typename _CharT, typename _Traits, typename _Alloc>
214  basic_string<_CharT, _Traits, _Alloc>::
215  basic_string(const _CharT* __s, const _Alloc& __a)
216  : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
217  __s + npos, __a), __a)
218  { }
219 
220  template<typename _CharT, typename _Traits, typename _Alloc>
221  basic_string<_CharT, _Traits, _Alloc>::
222  basic_string(size_type __n, _CharT __c, const _Alloc& __a)
223  : _M_dataplus(_S_construct(__n, __c, __a), __a)
224  { }
225 
226  // TBD: DPG annotate
227  template<typename _CharT, typename _Traits, typename _Alloc>
228  template<typename _InputIterator>
229  basic_string<_CharT, _Traits, _Alloc>::
230  basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
231  : _M_dataplus(_S_construct(__beg, __end, __a), __a)
232  { }
233 
234 #ifdef __GXX_EXPERIMENTAL_CXX0X__
235  template<typename _CharT, typename _Traits, typename _Alloc>
236  basic_string<_CharT, _Traits, _Alloc>::
237  basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
238  : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
239  { }
240 #endif
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  _M_check_length(this->size(), __n, "basic_string::assign");
265  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
266  return _M_replace_safe(size_type(0), this->size(), __s, __n);
267  else
268  {
269  // Work in-place.
270  const size_type __pos = __s - _M_data();
271  if (__pos >= __n)
272  _M_copy(_M_data(), __s, __n);
273  else if (__pos)
274  _M_move(_M_data(), __s, __n);
275  _M_rep()->_M_set_length_and_sharable(__n);
276  return *this;
277  }
278  }
279 
280  template<typename _CharT, typename _Traits, typename _Alloc>
281  basic_string<_CharT, _Traits, _Alloc>&
282  basic_string<_CharT, _Traits, _Alloc>::
283  append(size_type __n, _CharT __c)
284  {
285  if (__n)
286  {
287  _M_check_length(size_type(0), __n, "basic_string::append");
288  const size_type __len = __n + this->size();
289  if (__len > this->capacity() || _M_rep()->_M_is_shared())
290  this->reserve(__len);
291  _M_assign(_M_data() + this->size(), __n, __c);
292  _M_rep()->_M_set_length_and_sharable(__len);
293  }
294  return *this;
295  }
296 
297  template<typename _CharT, typename _Traits, typename _Alloc>
298  basic_string<_CharT, _Traits, _Alloc>&
299  basic_string<_CharT, _Traits, _Alloc>::
300  append(const _CharT* __s, size_type __n)
301  {
302  __glibcxx_requires_string_len(__s, __n);
303  if (__n)
304  {
305  _M_check_length(size_type(0), __n, "basic_string::append");
306  const size_type __len = __n + this->size();
307  if (__len > this->capacity() || _M_rep()->_M_is_shared())
308  {
309  if (_M_disjunct(__s))
310  this->reserve(__len);
311  else
312  {
313  const size_type __off = __s - _M_data();
314  this->reserve(__len);
315  __s = _M_data() + __off;
316  }
317  }
318  _M_copy(_M_data() + this->size(), __s, __n);
319  _M_rep()->_M_set_length_and_sharable(__len);
320  }
321  return *this;
322  }
323 
324  template<typename _CharT, typename _Traits, typename _Alloc>
325  basic_string<_CharT, _Traits, _Alloc>&
326  basic_string<_CharT, _Traits, _Alloc>::
327  append(const basic_string& __str)
328  {
329  const size_type __size = __str.size();
330  if (__size)
331  {
332  const size_type __len = __size + this->size();
333  if (__len > this->capacity() || _M_rep()->_M_is_shared())
334  this->reserve(__len);
335  _M_copy(_M_data() + this->size(), __str._M_data(), __size);
336  _M_rep()->_M_set_length_and_sharable(__len);
337  }
338  return *this;
339  }
340 
341  template<typename _CharT, typename _Traits, typename _Alloc>
342  basic_string<_CharT, _Traits, _Alloc>&
343  basic_string<_CharT, _Traits, _Alloc>::
344  append(const basic_string& __str, size_type __pos, size_type __n)
345  {
346  __str._M_check(__pos, "basic_string::append");
347  __n = __str._M_limit(__pos, __n);
348  if (__n)
349  {
350  const size_type __len = __n + this->size();
351  if (__len > this->capacity() || _M_rep()->_M_is_shared())
352  this->reserve(__len);
353  _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
354  _M_rep()->_M_set_length_and_sharable(__len);
355  }
356  return *this;
357  }
358 
359  template<typename _CharT, typename _Traits, typename _Alloc>
360  basic_string<_CharT, _Traits, _Alloc>&
361  basic_string<_CharT, _Traits, _Alloc>::
362  insert(size_type __pos, const _CharT* __s, size_type __n)
363  {
364  __glibcxx_requires_string_len(__s, __n);
365  _M_check(__pos, "basic_string::insert");
366  _M_check_length(size_type(0), __n, "basic_string::insert");
367  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
368  return _M_replace_safe(__pos, size_type(0), __s, __n);
369  else
370  {
371  // Work in-place.
372  const size_type __off = __s - _M_data();
373  _M_mutate(__pos, 0, __n);
374  __s = _M_data() + __off;
375  _CharT* __p = _M_data() + __pos;
376  if (__s + __n <= __p)
377  _M_copy(__p, __s, __n);
378  else if (__s >= __p)
379  _M_copy(__p, __s + __n, __n);
380  else
381  {
382  const size_type __nleft = __p - __s;
383  _M_copy(__p, __s, __nleft);
384  _M_copy(__p + __nleft, __p + __n, __n - __nleft);
385  }
386  return *this;
387  }
388  }
389 
390  template<typename _CharT, typename _Traits, typename _Alloc>
391  typename basic_string<_CharT, _Traits, _Alloc>::iterator
392  basic_string<_CharT, _Traits, _Alloc>::
393  erase(iterator __first, iterator __last)
394  {
395  _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
396  && __last <= _M_iend());
397 
398  // NB: This isn't just an optimization (bail out early when
399  // there is nothing to do, really), it's also a correctness
400  // issue vs MT, see libstdc++/40518.
401  const size_type __size = __last - __first;
402  if (__size)
403  {
404  const size_type __pos = __first - _M_ibegin();
405  _M_mutate(__pos, __size, size_type(0));
406  _M_rep()->_M_set_leaked();
407  return iterator(_M_data() + __pos);
408  }
409  else
410  return __first;
411  }
412 
413  template<typename _CharT, typename _Traits, typename _Alloc>
414  basic_string<_CharT, _Traits, _Alloc>&
415  basic_string<_CharT, _Traits, _Alloc>::
416  replace(size_type __pos, size_type __n1, const _CharT* __s,
417  size_type __n2)
418  {
419  __glibcxx_requires_string_len(__s, __n2);
420  _M_check(__pos, "basic_string::replace");
421  __n1 = _M_limit(__pos, __n1);
422  _M_check_length(__n1, __n2, "basic_string::replace");
423  bool __left;
424  if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
425  return _M_replace_safe(__pos, __n1, __s, __n2);
426  else if ((__left = __s + __n2 <= _M_data() + __pos)
427  || _M_data() + __pos + __n1 <= __s)
428  {
429  // Work in-place: non-overlapping case.
430  size_type __off = __s - _M_data();
431  __left ? __off : (__off += __n2 - __n1);
432  _M_mutate(__pos, __n1, __n2);
433  _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
434  return *this;
435  }
436  else
437  {
438  // Todo: overlapping case.
439  const basic_string __tmp(__s, __n2);
440  return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
441  }
442  }
443 
444  template<typename _CharT, typename _Traits, typename _Alloc>
445  void
446  basic_string<_CharT, _Traits, _Alloc>::_Rep::
447  _M_destroy(const _Alloc& __a) throw ()
448  {
449  const size_type __size = sizeof(_Rep_base) +
450  (this->_M_capacity + 1) * sizeof(_CharT);
451  _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
452  }
453 
454  template<typename _CharT, typename _Traits, typename _Alloc>
455  void
456  basic_string<_CharT, _Traits, _Alloc>::
457  _M_leak_hard()
458  {
459 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
460  if (_M_rep() == &_S_empty_rep())
461  return;
462 #endif
463  if (_M_rep()->_M_is_shared())
464  _M_mutate(0, 0, 0);
465  _M_rep()->_M_set_leaked();
466  }
467 
468  template<typename _CharT, typename _Traits, typename _Alloc>
469  void
470  basic_string<_CharT, _Traits, _Alloc>::
471  _M_mutate(size_type __pos, size_type __len1, size_type __len2)
472  {
473  const size_type __old_size = this->size();
474  const size_type __new_size = __old_size + __len2 - __len1;
475  const size_type __how_much = __old_size - __pos - __len1;
476 
477  if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
478  {
479  // Must reallocate.
480  const allocator_type __a = get_allocator();
481  _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
482 
483  if (__pos)
484  _M_copy(__r->_M_refdata(), _M_data(), __pos);
485  if (__how_much)
486  _M_copy(__r->_M_refdata() + __pos + __len2,
487  _M_data() + __pos + __len1, __how_much);
488 
489  _M_rep()->_M_dispose(__a);
490  _M_data(__r->_M_refdata());
491  }
492  else if (__how_much && __len1 != __len2)
493  {
494  // Work in-place.
495  _M_move(_M_data() + __pos + __len2,
496  _M_data() + __pos + __len1, __how_much);
497  }
498  _M_rep()->_M_set_length_and_sharable(__new_size);
499  }
500 
501  template<typename _CharT, typename _Traits, typename _Alloc>
502  void
503  basic_string<_CharT, _Traits, _Alloc>::
504  reserve(size_type __res)
505  {
506  if (__res != this->capacity() || _M_rep()->_M_is_shared())
507  {
508  // Make sure we don't shrink below the current size
509  if (__res < this->size())
510  __res = this->size();
511  const allocator_type __a = get_allocator();
512  _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
513  _M_rep()->_M_dispose(__a);
514  _M_data(__tmp);
515  }
516  }
517 
518  template<typename _CharT, typename _Traits, typename _Alloc>
519  void
520  basic_string<_CharT, _Traits, _Alloc>::
521  swap(basic_string& __s)
522  {
523  if (_M_rep()->_M_is_leaked())
524  _M_rep()->_M_set_sharable();
525  if (__s._M_rep()->_M_is_leaked())
526  __s._M_rep()->_M_set_sharable();
527  if (this->get_allocator() == __s.get_allocator())
528  {
529  _CharT* __tmp = _M_data();
530  _M_data(__s._M_data());
531  __s._M_data(__tmp);
532  }
533  // The code below can usually be optimized away.
534  else
535  {
536  const basic_string __tmp1(_M_ibegin(), _M_iend(),
537  __s.get_allocator());
538  const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
539  this->get_allocator());
540  *this = __tmp2;
541  __s = __tmp1;
542  }
543  }
544 
545  template<typename _CharT, typename _Traits, typename _Alloc>
546  typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
547  basic_string<_CharT, _Traits, _Alloc>::_Rep::
548  _S_create(size_type __capacity, size_type __old_capacity,
549  const _Alloc& __alloc)
550  {
551  // _GLIBCXX_RESOLVE_LIB_DEFECTS
552  // 83. String::npos vs. string::max_size()
553  if (__capacity > _S_max_size)
554  __throw_length_error(__N("basic_string::_S_create"));
555 
556  // The standard places no restriction on allocating more memory
557  // than is strictly needed within this layer at the moment or as
558  // requested by an explicit application call to reserve().
559 
560  // Many malloc implementations perform quite poorly when an
561  // application attempts to allocate memory in a stepwise fashion
562  // growing each allocation size by only 1 char. Additionally,
563  // it makes little sense to allocate less linear memory than the
564  // natural blocking size of the malloc implementation.
565  // Unfortunately, we would need a somewhat low-level calculation
566  // with tuned parameters to get this perfect for any particular
567  // malloc implementation. Fortunately, generalizations about
568  // common features seen among implementations seems to suffice.
569 
570  // __pagesize need not match the actual VM page size for good
571  // results in practice, thus we pick a common value on the low
572  // side. __malloc_header_size is an estimate of the amount of
573  // overhead per memory allocation (in practice seen N * sizeof
574  // (void*) where N is 0, 2 or 4). According to folklore,
575  // picking this value on the high side is better than
576  // low-balling it (especially when this algorithm is used with
577  // malloc implementations that allocate memory blocks rounded up
578  // to a size which is a power of 2).
579  const size_type __pagesize = 4096;
580  const size_type __malloc_header_size = 4 * sizeof(void*);
581 
582  // The below implements an exponential growth policy, necessary to
583  // meet amortized linear time requirements of the library: see
584  // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
585  // It's active for allocations requiring an amount of memory above
586  // system pagesize. This is consistent with the requirements of the
587  // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
588  if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
589  __capacity = 2 * __old_capacity;
590 
591  // NB: Need an array of char_type[__capacity], plus a terminating
592  // null char_type() element, plus enough for the _Rep data structure.
593  // Whew. Seemingly so needy, yet so elemental.
594  size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
595 
596  const size_type __adj_size = __size + __malloc_header_size;
597  if (__adj_size > __pagesize && __capacity > __old_capacity)
598  {
599  const size_type __extra = __pagesize - __adj_size % __pagesize;
600  __capacity += __extra / sizeof(_CharT);
601  // Never allocate a string bigger than _S_max_size.
602  if (__capacity > _S_max_size)
603  __capacity = _S_max_size;
604  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
605  }
606 
607  // NB: Might throw, but no worries about a leak, mate: _Rep()
608  // does not throw.
609  void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
610  _Rep *__p = new (__place) _Rep;
611  __p->_M_capacity = __capacity;
612  // ABI compatibility - 3.4.x set in _S_create both
613  // _M_refcount and _M_length. All callers of _S_create
614  // in basic_string.tcc then set just _M_length.
615  // In 4.0.x and later both _M_refcount and _M_length
616  // are initialized in the callers, unfortunately we can
617  // have 3.4.x compiled code with _S_create callers inlined
618  // calling 4.0.x+ _S_create.
619  __p->_M_set_sharable();
620  return __p;
621  }
622 
623  template<typename _CharT, typename _Traits, typename _Alloc>
624  _CharT*
625  basic_string<_CharT, _Traits, _Alloc>::_Rep::
626  _M_clone(const _Alloc& __alloc, size_type __res)
627  {
628  // Requested capacity of the clone.
629  const size_type __requested_cap = this->_M_length + __res;
630  _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
631  __alloc);
632  if (this->_M_length)
633  _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
634 
635  __r->_M_set_length_and_sharable(this->_M_length);
636  return __r->_M_refdata();
637  }
638 
639  template<typename _CharT, typename _Traits, typename _Alloc>
640  void
641  basic_string<_CharT, _Traits, _Alloc>::
642  resize(size_type __n, _CharT __c)
643  {
644  const size_type __size = this->size();
645  _M_check_length(__size, __n, "basic_string::resize");
646  if (__size < __n)
647  this->append(__n - __size, __c);
648  else if (__n < __size)
649  this->erase(__n);
650  // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
651  }
652 
653  template<typename _CharT, typename _Traits, typename _Alloc>
654  template<typename _InputIterator>
655  basic_string<_CharT, _Traits, _Alloc>&
656  basic_string<_CharT, _Traits, _Alloc>::
657  _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
658  _InputIterator __k2, __false_type)
659  {
660  const basic_string __s(__k1, __k2);
661  const size_type __n1 = __i2 - __i1;
662  _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
663  return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
664  __s.size());
665  }
666 
667  template<typename _CharT, typename _Traits, typename _Alloc>
668  basic_string<_CharT, _Traits, _Alloc>&
669  basic_string<_CharT, _Traits, _Alloc>::
670  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
671  _CharT __c)
672  {
673  _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
674  _M_mutate(__pos1, __n1, __n2);
675  if (__n2)
676  _M_assign(_M_data() + __pos1, __n2, __c);
677  return *this;
678  }
679 
680  template<typename _CharT, typename _Traits, typename _Alloc>
681  basic_string<_CharT, _Traits, _Alloc>&
682  basic_string<_CharT, _Traits, _Alloc>::
683  _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
684  size_type __n2)
685  {
686  _M_mutate(__pos1, __n1, __n2);
687  if (__n2)
688  _M_copy(_M_data() + __pos1, __s, __n2);
689  return *this;
690  }
691 
692  template<typename _CharT, typename _Traits, typename _Alloc>
693  basic_string<_CharT, _Traits, _Alloc>
694  operator+(const _CharT* __lhs,
695  const basic_string<_CharT, _Traits, _Alloc>& __rhs)
696  {
697  __glibcxx_requires_string(__lhs);
698  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
699  typedef typename __string_type::size_type __size_type;
700  const __size_type __len = _Traits::length(__lhs);
701  __string_type __str;
702  __str.reserve(__len + __rhs.size());
703  __str.append(__lhs, __len);
704  __str.append(__rhs);
705  return __str;
706  }
707 
708  template<typename _CharT, typename _Traits, typename _Alloc>
709  basic_string<_CharT, _Traits, _Alloc>
710  operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
711  {
712  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
713  typedef typename __string_type::size_type __size_type;
714  __string_type __str;
715  const __size_type __len = __rhs.size();
716  __str.reserve(__len + 1);
717  __str.append(__size_type(1), __lhs);
718  __str.append(__rhs);
719  return __str;
720  }
721 
722  template<typename _CharT, typename _Traits, typename _Alloc>
723  typename basic_string<_CharT, _Traits, _Alloc>::size_type
724  basic_string<_CharT, _Traits, _Alloc>::
725  copy(_CharT* __s, size_type __n, size_type __pos) const
726  {
727  _M_check(__pos, "basic_string::copy");
728  __n = _M_limit(__pos, __n);
729  __glibcxx_requires_string_len(__s, __n);
730  if (__n)
731  _M_copy(__s, _M_data() + __pos, __n);
732  // 21.3.5.7 par 3: do not append null. (good.)
733  return __n;
734  }
735 
736  template<typename _CharT, typename _Traits, typename _Alloc>
737  typename basic_string<_CharT, _Traits, _Alloc>::size_type
738  basic_string<_CharT, _Traits, _Alloc>::
739  find(const _CharT* __s, size_type __pos, size_type __n) const
740  {
741  __glibcxx_requires_string_len(__s, __n);
742  const size_type __size = this->size();
743  const _CharT* __data = _M_data();
744 
745  if (__n == 0)
746  return __pos <= __size ? __pos : npos;
747 
748  if (__n <= __size)
749  {
750  for (; __pos <= __size - __n; ++__pos)
751  if (traits_type::eq(__data[__pos], __s[0])
752  && traits_type::compare(__data + __pos + 1,
753  __s + 1, __n - 1) == 0)
754  return __pos;
755  }
756  return npos;
757  }
758 
759  template<typename _CharT, typename _Traits, typename _Alloc>
760  typename basic_string<_CharT, _Traits, _Alloc>::size_type
761  basic_string<_CharT, _Traits, _Alloc>::
762  find(_CharT __c, size_type __pos) const
763  {
764  size_type __ret = npos;
765  const size_type __size = this->size();
766  if (__pos < __size)
767  {
768  const _CharT* __data = _M_data();
769  const size_type __n = __size - __pos;
770  const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
771  if (__p)
772  __ret = __p - __data;
773  }
774  return __ret;
775  }
776 
777  template<typename _CharT, typename _Traits, typename _Alloc>
778  typename basic_string<_CharT, _Traits, _Alloc>::size_type
779  basic_string<_CharT, _Traits, _Alloc>::
780  rfind(const _CharT* __s, size_type __pos, size_type __n) const
781  {
782  __glibcxx_requires_string_len(__s, __n);
783  const size_type __size = this->size();
784  if (__n <= __size)
785  {
786  __pos = std::min(size_type(__size - __n), __pos);
787  const _CharT* __data = _M_data();
788  do
789  {
790  if (traits_type::compare(__data + __pos, __s, __n) == 0)
791  return __pos;
792  }
793  while (__pos-- > 0);
794  }
795  return npos;
796  }
797 
798  template<typename _CharT, typename _Traits, typename _Alloc>
799  typename basic_string<_CharT, _Traits, _Alloc>::size_type
800  basic_string<_CharT, _Traits, _Alloc>::
801  rfind(_CharT __c, size_type __pos) const
802  {
803  size_type __size = this->size();
804  if (__size)
805  {
806  if (--__size > __pos)
807  __size = __pos;
808  for (++__size; __size-- > 0; )
809  if (traits_type::eq(_M_data()[__size], __c))
810  return __size;
811  }
812  return npos;
813  }
814 
815  template<typename _CharT, typename _Traits, typename _Alloc>
816  typename basic_string<_CharT, _Traits, _Alloc>::size_type
817  basic_string<_CharT, _Traits, _Alloc>::
818  find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
819  {
820  __glibcxx_requires_string_len(__s, __n);
821  for (; __n && __pos < this->size(); ++__pos)
822  {
823  const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
824  if (__p)
825  return __pos;
826  }
827  return npos;
828  }
829 
830  template<typename _CharT, typename _Traits, typename _Alloc>
831  typename basic_string<_CharT, _Traits, _Alloc>::size_type
832  basic_string<_CharT, _Traits, _Alloc>::
833  find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
834  {
835  __glibcxx_requires_string_len(__s, __n);
836  size_type __size = this->size();
837  if (__size && __n)
838  {
839  if (--__size > __pos)
840  __size = __pos;
841  do
842  {
843  if (traits_type::find(__s, __n, _M_data()[__size]))
844  return __size;
845  }
846  while (__size-- != 0);
847  }
848  return npos;
849  }
850 
851  template<typename _CharT, typename _Traits, typename _Alloc>
852  typename basic_string<_CharT, _Traits, _Alloc>::size_type
853  basic_string<_CharT, _Traits, _Alloc>::
854  find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
855  {
856  __glibcxx_requires_string_len(__s, __n);
857  for (; __pos < this->size(); ++__pos)
858  if (!traits_type::find(__s, __n, _M_data()[__pos]))
859  return __pos;
860  return npos;
861  }
862 
863  template<typename _CharT, typename _Traits, typename _Alloc>
864  typename basic_string<_CharT, _Traits, _Alloc>::size_type
865  basic_string<_CharT, _Traits, _Alloc>::
866  find_first_not_of(_CharT __c, size_type __pos) const
867  {
868  for (; __pos < this->size(); ++__pos)
869  if (!traits_type::eq(_M_data()[__pos], __c))
870  return __pos;
871  return npos;
872  }
873 
874  template<typename _CharT, typename _Traits, typename _Alloc>
875  typename basic_string<_CharT, _Traits, _Alloc>::size_type
876  basic_string<_CharT, _Traits, _Alloc>::
877  find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
878  {
879  __glibcxx_requires_string_len(__s, __n);
880  size_type __size = this->size();
881  if (__size)
882  {
883  if (--__size > __pos)
884  __size = __pos;
885  do
886  {
887  if (!traits_type::find(__s, __n, _M_data()[__size]))
888  return __size;
889  }
890  while (__size--);
891  }
892  return npos;
893  }
894 
895  template<typename _CharT, typename _Traits, typename _Alloc>
896  typename basic_string<_CharT, _Traits, _Alloc>::size_type
897  basic_string<_CharT, _Traits, _Alloc>::
898  find_last_not_of(_CharT __c, size_type __pos) const
899  {
900  size_type __size = this->size();
901  if (__size)
902  {
903  if (--__size > __pos)
904  __size = __pos;
905  do
906  {
907  if (!traits_type::eq(_M_data()[__size], __c))
908  return __size;
909  }
910  while (__size--);
911  }
912  return npos;
913  }
914 
915  template<typename _CharT, typename _Traits, typename _Alloc>
916  int
917  basic_string<_CharT, _Traits, _Alloc>::
918  compare(size_type __pos, size_type __n, const basic_string& __str) const
919  {
920  _M_check(__pos, "basic_string::compare");
921  __n = _M_limit(__pos, __n);
922  const size_type __osize = __str.size();
923  const size_type __len = std::min(__n, __osize);
924  int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
925  if (!__r)
926  __r = _S_compare(__n, __osize);
927  return __r;
928  }
929 
930  template<typename _CharT, typename _Traits, typename _Alloc>
931  int
932  basic_string<_CharT, _Traits, _Alloc>::
933  compare(size_type __pos1, size_type __n1, const basic_string& __str,
934  size_type __pos2, size_type __n2) const
935  {
936  _M_check(__pos1, "basic_string::compare");
937  __str._M_check(__pos2, "basic_string::compare");
938  __n1 = _M_limit(__pos1, __n1);
939  __n2 = __str._M_limit(__pos2, __n2);
940  const size_type __len = std::min(__n1, __n2);
941  int __r = traits_type::compare(_M_data() + __pos1,
942  __str.data() + __pos2, __len);
943  if (!__r)
944  __r = _S_compare(__n1, __n2);
945  return __r;
946  }
947 
948  template<typename _CharT, typename _Traits, typename _Alloc>
949  int
950  basic_string<_CharT, _Traits, _Alloc>::
951  compare(const _CharT* __s) const
952  {
953  __glibcxx_requires_string(__s);
954  const size_type __size = this->size();
955  const size_type __osize = traits_type::length(__s);
956  const size_type __len = std::min(__size, __osize);
957  int __r = traits_type::compare(_M_data(), __s, __len);
958  if (!__r)
959  __r = _S_compare(__size, __osize);
960  return __r;
961  }
962 
963  template<typename _CharT, typename _Traits, typename _Alloc>
964  int
965  basic_string <_CharT, _Traits, _Alloc>::
966  compare(size_type __pos, size_type __n1, const _CharT* __s) const
967  {
968  __glibcxx_requires_string(__s);
969  _M_check(__pos, "basic_string::compare");
970  __n1 = _M_limit(__pos, __n1);
971  const size_type __osize = traits_type::length(__s);
972  const size_type __len = std::min(__n1, __osize);
973  int __r = traits_type::compare(_M_data() + __pos, __s, __len);
974  if (!__r)
975  __r = _S_compare(__n1, __osize);
976  return __r;
977  }
978 
979  template<typename _CharT, typename _Traits, typename _Alloc>
980  int
981  basic_string <_CharT, _Traits, _Alloc>::
982  compare(size_type __pos, size_type __n1, const _CharT* __s,
983  size_type __n2) const
984  {
985  __glibcxx_requires_string_len(__s, __n2);
986  _M_check(__pos, "basic_string::compare");
987  __n1 = _M_limit(__pos, __n1);
988  const size_type __len = std::min(__n1, __n2);
989  int __r = traits_type::compare(_M_data() + __pos, __s, __len);
990  if (!__r)
991  __r = _S_compare(__n1, __n2);
992  return __r;
993  }
994 
995  // 21.3.7.9 basic_string::getline and operators
996  template<typename _CharT, typename _Traits, typename _Alloc>
997  basic_istream<_CharT, _Traits>&
998  operator>>(basic_istream<_CharT, _Traits>& __in,
999  basic_string<_CharT, _Traits, _Alloc>& __str)
1000  {
1001  typedef basic_istream<_CharT, _Traits> __istream_type;
1002  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1003  typedef typename __istream_type::ios_base __ios_base;
1004  typedef typename __istream_type::int_type __int_type;
1005  typedef typename __string_type::size_type __size_type;
1006  typedef ctype<_CharT> __ctype_type;
1007  typedef typename __ctype_type::ctype_base __ctype_base;
1008 
1009  __size_type __extracted = 0;
1010  typename __ios_base::iostate __err = __ios_base::goodbit;
1011  typename __istream_type::sentry __cerb(__in, false);
1012  if (__cerb)
1013  {
1014  __try
1015  {
1016  // Avoid reallocation for common case.
1017  __str.erase();
1018  _CharT __buf[128];
1019  __size_type __len = 0;
1020  const streamsize __w = __in.width();
1021  const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
1022  : __str.max_size();
1023  const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
1024  const __int_type __eof = _Traits::eof();
1025  __int_type __c = __in.rdbuf()->sgetc();
1026 
1027  while (__extracted < __n
1028  && !_Traits::eq_int_type(__c, __eof)
1029  && !__ct.is(__ctype_base::space,
1030  _Traits::to_char_type(__c)))
1031  {
1032  if (__len == sizeof(__buf) / sizeof(_CharT))
1033  {
1034  __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
1035  __len = 0;
1036  }
1037  __buf[__len++] = _Traits::to_char_type(__c);
1038  ++__extracted;
1039  __c = __in.rdbuf()->snextc();
1040  }
1041  __str.append(__buf, __len);
1042 
1043  if (_Traits::eq_int_type(__c, __eof))
1044  __err |= __ios_base::eofbit;
1045  __in.width(0);
1046  }
1047  __catch(__cxxabiv1::__forced_unwind&)
1048  {
1049  __in._M_setstate(__ios_base::badbit);
1050  __throw_exception_again;
1051  }
1052  __catch(...)
1053  {
1054  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1055  // 91. Description of operator>> and getline() for string<>
1056  // might cause endless loop
1057  __in._M_setstate(__ios_base::badbit);
1058  }
1059  }
1060  // 211. operator>>(istream&, string&) doesn't set failbit
1061  if (!__extracted)
1062  __err |= __ios_base::failbit;
1063  if (__err)
1064  __in.setstate(__err);
1065  return __in;
1066  }
1067 
1068  template<typename _CharT, typename _Traits, typename _Alloc>
1069  basic_istream<_CharT, _Traits>&
1070  getline(basic_istream<_CharT, _Traits>& __in,
1071  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1072  {
1073  typedef basic_istream<_CharT, _Traits> __istream_type;
1074  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1075  typedef typename __istream_type::ios_base __ios_base;
1076  typedef typename __istream_type::int_type __int_type;
1077  typedef typename __string_type::size_type __size_type;
1078 
1079  __size_type __extracted = 0;
1080  const __size_type __n = __str.max_size();
1081  typename __ios_base::iostate __err = __ios_base::goodbit;
1082  typename __istream_type::sentry __cerb(__in, true);
1083  if (__cerb)
1084  {
1085  __try
1086  {
1087  __str.erase();
1088  const __int_type __idelim = _Traits::to_int_type(__delim);
1089  const __int_type __eof = _Traits::eof();
1090  __int_type __c = __in.rdbuf()->sgetc();
1091 
1092  while (__extracted < __n
1093  && !_Traits::eq_int_type(__c, __eof)
1094  && !_Traits::eq_int_type(__c, __idelim))
1095  {
1096  __str += _Traits::to_char_type(__c);
1097  ++__extracted;
1098  __c = __in.rdbuf()->snextc();
1099  }
1100 
1101  if (_Traits::eq_int_type(__c, __eof))
1102  __err |= __ios_base::eofbit;
1103  else if (_Traits::eq_int_type(__c, __idelim))
1104  {
1105  ++__extracted;
1106  __in.rdbuf()->sbumpc();
1107  }
1108  else
1109  __err |= __ios_base::failbit;
1110  }
1111  __catch(__cxxabiv1::__forced_unwind&)
1112  {
1113  __in._M_setstate(__ios_base::badbit);
1114  __throw_exception_again;
1115  }
1116  __catch(...)
1117  {
1118  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1119  // 91. Description of operator>> and getline() for string<>
1120  // might cause endless loop
1121  __in._M_setstate(__ios_base::badbit);
1122  }
1123  }
1124  if (!__extracted)
1125  __err |= __ios_base::failbit;
1126  if (__err)
1127  __in.setstate(__err);
1128  return __in;
1129  }
1130 
1131  // Inhibit implicit instantiations for required instantiations,
1132  // which are defined via explicit instantiations elsewhere.
1133 #if _GLIBCXX_EXTERN_TEMPLATE > 0
1134  extern template class basic_string<char>;
1135  extern template
1136  basic_istream<char>&
1137  operator>>(basic_istream<char>&, string&);
1138  extern template
1139  basic_ostream<char>&
1140  operator<<(basic_ostream<char>&, const string&);
1141  extern template
1142  basic_istream<char>&
1143  getline(basic_istream<char>&, string&, char);
1144  extern template
1145  basic_istream<char>&
1146  getline(basic_istream<char>&, string&);
1147 
1148 #ifdef _GLIBCXX_USE_WCHAR_T
1149  extern template class basic_string<wchar_t>;
1150  extern template
1151  basic_istream<wchar_t>&
1152  operator>>(basic_istream<wchar_t>&, wstring&);
1153  extern template
1154  basic_ostream<wchar_t>&
1155  operator<<(basic_ostream<wchar_t>&, const wstring&);
1156  extern template
1157  basic_istream<wchar_t>&
1158  getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1159  extern template
1160  basic_istream<wchar_t>&
1161  getline(basic_istream<wchar_t>&, wstring&);
1162 #endif
1163 #endif
1164 
1165 _GLIBCXX_END_NAMESPACE_VERSION
1166 } // namespace std
1167 
1168 #endif