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