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 0 : 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 0 : if (__beg == __end && __a == _Alloc())
131 0 : return _S_empty_rep()._M_refdata();
132 : #endif
133 : // NB: Not required, but considered best practice.
134 0 : if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
135 0 : __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 0 : __end));
139 : // Check for out_of_range and length_error exceptions.
140 0 : _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
141 : __try
142 0 : { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
143 0 : __catch(...)
144 : {
145 0 : __r->_M_destroy(__a);
146 0 : __throw_exception_again;
147 : }
148 0 : __r->_M_set_length_and_sharable(__dnew);
149 0 : 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 0 : basic_string<_CharT, _Traits, _Alloc>::
230 : basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
231 0 : : _M_dataplus(_S_construct(__beg, __end, __a), __a)
232 0 : { }
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 0 : 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 0 : const __size_type __len = _Traits::length(__lhs);
701 0 : __string_type __str;
702 0 : __str.reserve(__len + __rhs.size());
703 0 : __str.append(__lhs, __len);
704 0 : __str.append(__rhs);
705 0 : 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
|
