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