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