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