| blob | 23374b3cf81b6405efd50f844838f5cd362286b2 |
1 // Components for manipulating sequences of characters -*- C++ -*-
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.
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.
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.
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.
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 */
36 //
37 // ISO C++ 14882: 21 Strings library
38 //
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.
43 #ifndef _BASIC_STRING_TCC
44 #define _BASIC_STRING_TCC 1
46 #pragma GCC system_header
48 namespace std
49 {
50 template<typename _Type>
51 inline bool
52 __is_null_pointer(_Type* __ptr)
53 { return __ptr == 0; }
55 template<typename _Type>
56 inline bool
57 __is_null_pointer(_Type)
58 { return false; }
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;
65 template<typename _CharT, typename _Traits, typename _Alloc>
66 const _CharT
67 basic_string<_CharT, _Traits, _Alloc>::
68 _Rep::_S_terminal = _CharT();
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;
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)];
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 }
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 forward_iterator_tag)
138 {
139 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
140 if (__beg == __end && __a == _Alloc())
141 return _S_empty_rep()._M_refdata();
142 #endif
143 // NB: Not required, but considered best practice.
144 if (__builtin_expect(__is_null_pointer(__beg) && __beg != __end, 0))
145 __throw_logic_error(__N("basic_string::_S_construct NULL not valid"));
147 const size_type __dnew = static_cast<size_type>(std::distance(__beg,
148 __end));
149 // Check for out_of_range and length_error exceptions.
150 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
151 try
152 { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
153 catch(...)
154 {
155 __r->_M_destroy(__a);
156 __throw_exception_again;
157 }
158 __r->_M_set_length_and_sharable(__dnew);
159 return __r->_M_refdata();
160 }
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);
176 __r->_M_set_length_and_sharable(__n);
177 return __r->_M_refdata();
178 }
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 { }
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 { }
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 { }
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 { }
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 { }
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 { }
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 { }
236 // TBD: DPG annotate
237 template<typename _CharT, typename _Traits, typename _Alloc>
238 template<typename _InputIterator>
239 basic_string<_CharT, _Traits, _Alloc>::
240 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
241 : _M_dataplus(_S_construct(__beg, __end, __a), __a)
242 { }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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;
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);
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);
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 }
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 }
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 }
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"));
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().
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.
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*);
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;
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);
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 }
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 }
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);
614 __r->_M_set_length_and_sharable(this->_M_length);
615 return __r->_M_refdata();
616 }
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 }
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 }
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 }
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 }
671 template<typename _CharT, typename _Traits, typename _Alloc>
672 basic_string<_CharT, _Traits, _Alloc>
673 operator+(const _CharT* __lhs,
674 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 const __size_type __len = _Traits::length(__lhs);
680 __string_type __str;
681 __str.reserve(__len + __rhs.size());
682 __str.append(__lhs, __len);
683 __str.append(__rhs);
684 return __str;
685 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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&);
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
1006 #endif