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