1/*
2 * Copyright (c) 1994
3 * Hewlett-Packard Company
4 *
5 * Copyright (c) 1996,1997
6 * Silicon Graphics Computer Systems, Inc.
7 *
8 * Copyright (c) 1997
9 * Moscow Center for SPARC Technology
10 *
11 * Copyright (c) 1999
12 * Boris Fomitchev
13 *
14 * This material is provided "as is", with absolutely no warranty expressed
15 * or implied. Any use is at your own risk.
16 *
17 * Permission to use or copy this software for any purpose is hereby granted
18 * without fee, provided the above notices are retained on all copies.
19 * Permission to modify the code and to distribute modified code is granted,
20 * provided the above notices are retained, and a notice that the code was
21 * modified is included with the above copyright notice.
22 */
23
24#ifndef _STLP_STRING_C
25#define _STLP_STRING_C
26
27#ifndef _STLP_INTERNAL_STRING_H
28#  include <stl/_string.h>
29#endif
30
31#ifndef _STLP_INTERNAL_CTRAITS_FUNCTIONS_H
32#  include <stl/_ctraits_fns.h>
33#endif
34
35#ifndef _STLP_INTERNAL_FUNCTION_H
36#  include <stl/_function.h>
37#endif
38
39#if defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND)
40#  define basic_string _STLP_NO_MEM_T_NAME(str)
41#elif defined (_STLP_DEBUG)
42#  define basic_string _STLP_NON_DBG_NAME(str)
43#endif
44
45#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
46#  define __size_type__ size_t
47#  define size_type size_t
48#  define iterator _CharT*
49#else
50#  define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE basic_string<_CharT,_Traits,_Alloc>::size_type
51#endif
52
53_STLP_BEGIN_NAMESPACE
54
55_STLP_MOVE_TO_PRIV_NAMESPACE
56
57// A helper class to use a char_traits as a function object.
58template <class _Traits>
59struct _Not_within_traits : public unary_function<typename _Traits::char_type, bool> {
60  typedef typename _Traits::char_type _CharT;
61  const _CharT* _M_first;
62  const _CharT* _M_last;
63
64  _Not_within_traits(const _CharT* __f, const _CharT* __l)
65    : _M_first(__f), _M_last(__l) {}
66
67  bool operator()(const _CharT& __x) const {
68    return find_if(_M_first, _M_last,
69                   _STLP_PRIV _Eq_char_bound<_Traits>(__x)) == _M_last;
70  }
71};
72
73template <class _InputIter, class _CharT, class _Traits>
74inline _InputIter __str_find_first_of_aux(_InputIter __first1, _InputIter __last1,
75                                          const _CharT* __first2, const _CharT* __last2,
76                                          _Traits*, const __true_type& /* _STLportTraits */)
77{ return __find_first_of(__first1, __last1, __first2, __last2); }
78
79template <class _InputIter, class _CharT, class _Traits>
80inline _InputIter __str_find_first_of_aux(_InputIter __first1, _InputIter __last1,
81                                          const _CharT* __first2, const _CharT* __last2,
82                                          _Traits*, const __false_type& /* _STLportTraits */)
83{ return __find_first_of(__first1, __last1, __first2, __last2, _STLP_PRIV _Eq_traits<_Traits>()); }
84
85template <class _InputIter, class _CharT, class _Traits>
86inline _InputIter __str_find_first_of(_InputIter __first1, _InputIter __last1,
87                                      const _CharT* __first2, const _CharT* __last2,
88                                      _Traits* __traits) {
89#if !defined (__BORLANDC__)
90  typedef typename _IsSTLportClass<_Traits>::_Ret _STLportTraits;
91#else
92  enum { _Is = _IsSTLportClass<_Traits>::_Is };
93  typedef typename __bool2type<_Is>::_Ret _STLportTraits;
94#endif
95  return __str_find_first_of_aux(__first1, __last1, __first2, __last2, __traits, _STLportTraits());
96}
97
98template <class _InputIter, class _CharT, class _Traits>
99inline _InputIter __str_find_first_not_of_aux3(_InputIter __first1, _InputIter __last1,
100                                               const _CharT* __first2, const _CharT* __last2,
101                                               _Traits* /* __traits */, const __true_type& __useStrcspnLikeAlgo)
102{ return __find_first_of_aux2(__first1, __last1, __first2, __last2, __first2, not1(_Identity<bool>()), __useStrcspnLikeAlgo); }
103
104template <class _InputIter, class _CharT, class _Traits>
105inline _InputIter __str_find_first_not_of_aux3(_InputIter __first1, _InputIter __last1,
106                                               const _CharT* __first2, const _CharT* __last2,
107                                               _Traits* /* __traits */, const __false_type& /* _UseStrcspnLikeAlgo */)
108{ return _STLP_STD::find_if(__first1, __last1, _STLP_PRIV _Not_within_traits<_Traits>(__first2, __last2)); }
109
110template <class _InputIter, class _CharT, class _Tp, class _Traits>
111inline _InputIter __str_find_first_not_of_aux2(_InputIter __first1, _InputIter __last1,
112                                               const _CharT* __first2, const _CharT* __last2,
113                                               _Tp* __pt, _Traits* __traits) {
114  typedef typename _IsIntegral<_Tp>::_Ret _IsIntegral;
115  typedef typename _IsCharLikeType<_CharT>::_Ret _IsCharLike;
116  typedef typename _Land2<_IsIntegral, _IsCharLike>::_Ret _UseStrcspnLikeAlgo;
117  return __str_find_first_not_of_aux3(__first1, __last1, __first2, __last2, __traits, _UseStrcspnLikeAlgo());
118}
119
120template <class _InputIter, class _CharT, class _Traits>
121inline _InputIter __str_find_first_not_of_aux1(_InputIter __first1, _InputIter __last1,
122                                               const _CharT* __first2, const _CharT* __last2,
123                                               _Traits* __traits, const __true_type& /* _STLportTraits */)
124{ return __str_find_first_not_of_aux2(__first1, __last1, __first2, __last2,
125                                      _STLP_VALUE_TYPE(__first1, _InputIter), __traits); }
126
127template <class _InputIter, class _CharT, class _Traits>
128inline _InputIter __str_find_first_not_of_aux1(_InputIter __first1, _InputIter __last1,
129                                               const _CharT* __first2, const _CharT* __last2,
130                                               _Traits*, const __false_type& /* _STLportTraits */)
131{ return _STLP_STD::find_if(__first1, __last1, _STLP_PRIV _Not_within_traits<_Traits>(__first2, __last2)); }
132
133template <class _InputIter, class _CharT, class _Traits>
134inline _InputIter __str_find_first_not_of(_InputIter __first1, _InputIter __last1,
135                                          const _CharT* __first2, const _CharT* __last2,
136                                          _Traits* __traits) {
137#if !defined (__BORLANDC__)
138  typedef typename _IsSTLportClass<_Traits>::_Ret _STLportTraits;
139#else
140  enum { _Is = _IsSTLportClass<_Traits>::_Is };
141  typedef typename __bool2type<_Is>::_Ret _STLportTraits;
142#endif
143  return __str_find_first_not_of_aux1(__first1, __last1, __first2, __last2, __traits, _STLportTraits());
144}
145
146// ------------------------------------------------------------
147// Non-inline declarations.
148
149#if !defined (basic_string)
150_STLP_MOVE_TO_STD_NAMESPACE
151#endif
152
153// Change the string's capacity so that it is large enough to hold
154//  at least __res_arg elements, plus the terminating _CharT().  Note that,
155//  if __res_arg < capacity(), this member function may actually decrease
156//  the string's capacity.
157template <class _CharT, class _Traits, class _Alloc>
158void basic_string<_CharT,_Traits,_Alloc>::reserve(size_type __res_arg) {
159  if (__res_arg > max_size())
160    this->_M_throw_length_error();
161
162  size_type __n = (max)(__res_arg, size()) + 1;
163  if (__n < this->_M_capacity())
164    return;
165
166  _M_reserve(__n);
167}
168
169template <class _CharT, class _Traits, class _Alloc>
170void basic_string<_CharT,_Traits,_Alloc>::_M_reserve(size_type __n) {
171  pointer __new_start = this->_M_start_of_storage.allocate(__n, __n);
172  pointer __new_finish = _STLP_PRIV __ucopy(this->_M_Start(), this->_M_Finish(), __new_start);
173  _M_construct_null(__new_finish);
174  this->_M_deallocate_block();
175  this->_M_reset(__new_start, __new_finish, __new_start + __n);
176}
177
178template <class _CharT, class _Traits, class _Alloc>
179basic_string<_CharT,_Traits,_Alloc>&
180basic_string<_CharT,_Traits,_Alloc>::append(size_type __n, _CharT __c) {
181  if (__n > 0) {
182    if (__n > max_size() - size())
183      this->_M_throw_length_error();
184    if (__n >= this->_M_rest())
185      _M_reserve(_M_compute_next_size(__n));
186    _STLP_PRIV __uninitialized_fill_n(this->_M_finish + 1, __n - 1, __c);
187    _M_construct_null(this->_M_finish + __n);
188    _Traits::assign(*end(), __c);
189    this->_M_finish += __n;
190  }
191  return *this;
192}
193
194template <class _CharT, class _Traits, class _Alloc>
195basic_string<_CharT, _Traits, _Alloc>&
196basic_string<_CharT, _Traits, _Alloc>::_M_append(const _CharT* __first, const _CharT* __last) {
197  if (__first != __last) {
198    size_type __n = __STATIC_CAST(size_type, __last - __first);
199    if (__n >= this->_M_rest()) {
200      size_type __len = _M_compute_next_size(__n);
201      pointer __new_start = this->_M_start_of_storage.allocate(__len, __len);
202      pointer __new_finish = _STLP_PRIV __ucopy(this->_M_Start(), this->_M_Finish(), __new_start);
203      __new_finish = _STLP_PRIV __ucopy(__first, __last, __new_finish);
204      _M_construct_null(__new_finish);
205      this->_M_deallocate_block();
206      this->_M_reset(__new_start, __new_finish, __new_start + __len);
207    }
208    else {
209      const _CharT* __f1 = __first;
210      ++__f1;
211      _STLP_PRIV __ucopy(__f1, __last, this->_M_finish + 1);
212      _M_construct_null(this->_M_finish + __n);
213      _Traits::assign(*end(), *__first);
214      this->_M_finish += __n;
215    }
216  }
217  return *this;
218}
219
220template <class _CharT, class _Traits, class _Alloc>
221basic_string<_CharT,_Traits,_Alloc>&
222basic_string<_CharT,_Traits,_Alloc>::assign(size_type __n, _CharT __c) {
223  if (__n <= size()) {
224    _Traits::assign(this->_M_Start(), __n, __c);
225    erase(begin() + __n, end());
226  }
227  else {
228    if (__n < capacity()) {
229      _Traits::assign(this->_M_Start(), size(), __c);
230      append(__n - size(), __c);
231    }
232    else {
233      _Self __str(__n, __c);
234      this->swap(__str);
235    }
236  }
237  return *this;
238}
239
240template <class _CharT, class _Traits, class _Alloc>
241basic_string<_CharT,_Traits,_Alloc>&
242basic_string<_CharT,_Traits,_Alloc>::_M_assign(const _CharT* __f, const _CharT* __l) {
243  ptrdiff_t __n = __l - __f;
244  if (__STATIC_CAST(size_type, __n) <= size()) {
245    _Traits::move(this->_M_Start(), __f, __n);
246    erase(begin() + __n, end());
247  }
248  else {
249    _Traits::move(this->_M_Start(), __f, size());
250    _M_append(__f + size(), __l);
251  }
252  return *this;
253}
254
255template <class _CharT, class _Traits, class _Alloc>
256_CharT* basic_string<_CharT,_Traits,_Alloc> ::_M_insert_aux(_CharT* __p,
257                                                            _CharT __c) {
258  pointer __new_pos = __p;
259  if (this->_M_rest() > 1 ) {
260    _M_construct_null(this->_M_finish + 1);
261    _Traits::move(__p + 1, __p, this->_M_finish - __p);
262    _Traits::assign(*__p, __c);
263    ++this->_M_finish;
264  }
265  else {
266    size_type __len = _M_compute_next_size(1);
267    pointer __new_start = this->_M_start_of_storage.allocate(__len, __len);
268    __new_pos = _STLP_PRIV __ucopy(this->_M_Start(), __p, __new_start);
269    _Traits::assign(*__new_pos, __c);
270    pointer __new_finish = __new_pos + 1;
271    __new_finish = _STLP_PRIV __ucopy(__p, this->_M_finish, __new_finish);
272    _M_construct_null(__new_finish);
273    this->_M_deallocate_block();
274    this->_M_reset(__new_start, __new_finish, __new_start + __len);
275  }
276  return __new_pos;
277}
278
279template <class _CharT, class _Traits, class _Alloc>
280void basic_string<_CharT,_Traits,_Alloc>::insert(iterator __pos,
281                                                 size_t __n, _CharT __c) {
282  if (__n != 0) {
283    if (this->_M_rest() > __n) {
284      const size_type __elems_after = this->_M_finish - __pos;
285      pointer __old_finish = this->_M_finish;
286      if (__elems_after >= __n) {
287        _STLP_PRIV __ucopy((this->_M_finish - __n) + 1, this->_M_finish + 1, this->_M_finish + 1);
288        this->_M_finish += __n;
289        _Traits::move(__pos + __n, __pos, (__elems_after - __n) + 1);
290        _Traits::assign(__pos, __n, __c);
291      }
292      else {
293        _STLP_PRIV __uninitialized_fill_n(this->_M_finish + 1, __n - __elems_after - 1, __c);
294        this->_M_finish += __n - __elems_after;
295        _STLP_PRIV __ucopy(__pos, __old_finish + 1, this->_M_finish);
296        this->_M_finish += __elems_after;
297        _Traits::assign(__pos, __elems_after + 1, __c);
298      }
299    }
300    else {
301      size_type __len = _M_compute_next_size(__n);
302      pointer __new_start = this->_M_start_of_storage.allocate(__len, __len);
303      pointer __new_finish = _STLP_PRIV __ucopy(this->_M_Start(), __pos, __new_start);
304      __new_finish = _STLP_PRIV __uninitialized_fill_n(__new_finish, __n, __c);
305      __new_finish = _STLP_PRIV __ucopy(__pos, this->_M_finish, __new_finish);
306      _M_construct_null(__new_finish);
307      this->_M_deallocate_block();
308      this->_M_reset(__new_start, __new_finish, __new_start + __len);
309    }
310  }
311}
312
313template <class _CharT, class _Traits, class _Alloc>
314void basic_string<_CharT,_Traits,_Alloc>::_M_insert(iterator __pos,
315                                                    const _CharT* __first, const _CharT* __last,
316                                                    bool __self_ref) {
317  //this version has to take care about the auto referencing
318  if (__first != __last) {
319    const size_t __n = __last - __first;
320    if (this->_M_rest() > __n) {
321      const size_t __elems_after = this->_M_finish - __pos;
322      pointer __old_finish = this->_M_finish;
323      if (__elems_after >= __n) {
324        _STLP_PRIV __ucopy((this->_M_finish - __n) + 1, this->_M_finish + 1, this->_M_finish + 1);
325        this->_M_finish += __n;
326        _Traits::move(__pos + __n, __pos, (__elems_after - __n) + 1);
327        if (!__self_ref || __last < __pos) {
328          _M_copy(__first, __last, __pos);
329        }
330        else {
331          //We have to check that the source buffer hasn't move
332          if (__first >= __pos) {
333            //The source buffer has move
334            __first += __n;
335            __last += __n;
336            _M_copy(__first, __last, __pos);
337          }
338          else {
339            //The source buffer hasn't move, it has been duplicated
340            _M_move(__first, __last, __pos);
341          }
342        }
343      }
344      else {
345        const_iterator __mid = __first;
346        __mid += __elems_after + 1;
347        _STLP_PRIV __ucopy(__mid, __last, this->_M_finish + 1);
348        this->_M_finish += __n - __elems_after;
349        _STLP_PRIV __ucopy(__pos, __old_finish + 1, this->_M_finish);
350        this->_M_finish += __elems_after;
351        if (!__self_ref)
352          _M_copy(__first, __mid, __pos);
353        else
354          _M_move(__first, __mid, __pos);
355      }
356    }
357    else {
358      size_type __len = _M_compute_next_size(__n);
359      pointer __new_start = this->_M_start_of_storage.allocate(__len, __len);
360      pointer __new_finish = _STLP_PRIV __ucopy(this->_M_Start(), __pos, __new_start);
361      __new_finish = _STLP_PRIV __ucopy(__first, __last, __new_finish);
362      __new_finish = _STLP_PRIV __ucopy(__pos, this->_M_finish, __new_finish);
363      _M_construct_null(__new_finish);
364      this->_M_deallocate_block();
365      this->_M_reset(__new_start, __new_finish, __new_start + __len);
366    }
367  }
368}
369
370template <class _CharT, class _Traits, class _Alloc>
371basic_string<_CharT,_Traits,_Alloc>&
372basic_string<_CharT,_Traits,_Alloc> ::replace(iterator __first, iterator __last,
373                                              size_type __n, _CharT __c) {
374  size_type __len = (size_type)(__last - __first);
375
376  if (__len >= __n) {
377    _Traits::assign(__first, __n, __c);
378    erase(__first + __n, __last);
379  }
380  else {
381    _Traits::assign(__first, __len, __c);
382    insert(__last, __n - __len, __c);
383  }
384  return *this;
385}
386
387template <class _CharT, class _Traits, class _Alloc>
388basic_string<_CharT,_Traits,_Alloc>&
389basic_string<_CharT,_Traits,_Alloc> ::_M_replace(iterator __first, iterator __last,
390                                                 const _CharT* __f, const _CharT* __l,
391                                                 bool __self_ref) {
392  const ptrdiff_t       __n = __l - __f;
393  const difference_type __len = __last - __first;
394  if (__len >= __n) {
395    if (!__self_ref || __l < __first || __f >= __last)
396      _M_copy(__f, __l, __first);
397    else
398      _M_move(__f, __l, __first);
399    erase(__first + __n, __last);
400  } else if (!__self_ref || (__f >= __last) || (__l <= __first)) { // no overlap
401    const_iterator __m = __f + __len;
402    _M_copy(__f, __m, __first);
403    _M_insert(__last, __m, __l, __self_ref );
404  } else if (__f < __first) { // we have to take care of overlaping
405    const_iterator __m = __f + __len;
406    // We have to deal with possible reallocation because we do insert first.
407    const difference_type __off_dest = __first - this->begin();
408    const difference_type __off_src = __f - this->begin();
409    _M_insert(__last, __m, __l, true);
410    _Traits::move(begin() + __off_dest, begin() + __off_src, __len);
411  } else {
412    const_iterator __m = __f + __len;
413    _Traits::move(__first, __f, __len);
414    _M_insert(__last, __m, __l, true);
415  }
416  return *this;
417}
418
419template <class _CharT, class _Traits, class _Alloc>
420__size_type__ basic_string<_CharT,_Traits,_Alloc>::find( const _CharT* __s, size_type __pos,
421                                                         size_type __n) const
422{
423  const size_t __len = size();
424  if (__pos >= __len || __pos + __n > __len) {
425    if ( __n == 0 && __pos <= __len ) { // marginal case
426      return __pos;
427    }
428    return npos;
429  }
430
431  const_pointer __result =
432    _STLP_STD::search(this->_M_Start() + __pos, this->_M_Finish(),
433                      __s, __s + __n, _STLP_PRIV _Eq_traits<_Traits>());
434  return __result != this->_M_Finish() ? __result - this->_M_Start() : npos;
435}
436
437template <class _CharT, class _Traits, class _Alloc>
438__size_type__ basic_string<_CharT,_Traits,_Alloc>::find(_CharT __c, size_type __pos) const
439{
440  if (__pos >= size()) { /*__pos + 1 > size()*/
441    return npos;
442  }
443
444  const_pointer __result =
445    _STLP_STD::find_if(this->_M_Start() + __pos, this->_M_Finish(),
446                       _STLP_PRIV _Eq_char_bound<_Traits>(__c));
447  return __result != this->_M_Finish() ? __result - this->_M_Start() : npos;
448}
449
450template <class _CharT, class _Traits, class _Alloc>
451__size_type__ basic_string<_CharT,_Traits,_Alloc>::rfind(const _CharT* __s, size_type __pos,
452                                                         size_type __n) const
453{
454  const size_type __len = size();
455  if ( __len < __n ) {
456    return npos;
457  }
458  const_pointer __last = this->_M_Start() + (min)( __len - __n, __pos) + __n;
459  if ( __n == 0 ) { // marginal case
460    return __last - this->_M_Start();
461  }
462  const_pointer __result = _STLP_STD::find_end(this->_M_Start(), __last,
463                                               __s, __s + __n, _STLP_PRIV _Eq_traits<_Traits>());
464  return __result != __last ? __result - this->_M_Start() : npos;
465}
466
467template <class _CharT, class _Traits, class _Alloc>
468__size_type__ basic_string<_CharT,_Traits,_Alloc>::rfind(_CharT __c, size_type __pos) const
469{
470  const size_type __len = size();
471  if ( __len < 1 ) {
472    return npos;
473  }
474  const_iterator __last = begin() + (min)(__len - 1, __pos) + 1;
475  const_reverse_iterator __rresult =
476    _STLP_STD::find_if(const_reverse_iterator(__last), rend(),
477                       _STLP_PRIV _Eq_char_bound<_Traits>(__c));
478  return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
479}
480
481template <class _CharT, class _Traits, class _Alloc> __size_type__
482basic_string<_CharT,_Traits,_Alloc> ::find_first_of(const _CharT* __s, size_type __pos,
483                                                    size_type __n) const {
484  if (__pos >= size()) /*__pos + 1 > size()*/
485    return npos;
486  else {
487    const_iterator __result = _STLP_PRIV __str_find_first_of(begin() + __pos, end(),
488                                                             __s, __s + __n,
489                                                             __STATIC_CAST(_Traits*, 0));
490    return __result != end() ? __result - begin() : npos;
491  }
492}
493
494template <class _CharT, class _Traits, class _Alloc>
495 __size_type__
496basic_string<_CharT,_Traits,_Alloc> ::find_last_of(const _CharT* __s, size_type __pos,
497                                                   size_type __n) const
498{
499  const size_type __len = size();
500  if ( __len < 1 ) {
501    return npos;
502  }
503  const const_iterator __last = begin() + (min)(__len - 1, __pos) + 1;
504  const const_reverse_iterator __rresult =
505    _STLP_PRIV __str_find_first_of(const_reverse_iterator(__last), rend(),
506                                   __s, __s + __n,
507                                   __STATIC_CAST(_Traits*, 0));
508  return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
509}
510
511
512template <class _CharT, class _Traits, class _Alloc> __size_type__
513basic_string<_CharT,_Traits,_Alloc> ::find_first_not_of(const _CharT* __s, size_type __pos,
514                                                        size_type __n) const {
515  typedef typename _Traits::char_type _CharType;
516  if (__pos >= size()) /*__pos + 1 >= size()*/
517    return npos;
518  else {
519    const_pointer __result = _STLP_PRIV __str_find_first_not_of(this->_M_Start() + __pos, this->_M_Finish(),
520                                                                __STATIC_CAST(const _CharType*, __s),
521                                                                __STATIC_CAST(const _CharType*, __s) + __n,
522                                                                __STATIC_CAST(_Traits*, 0));
523    return __result != this->_M_finish ? __result - this->_M_Start() : npos;
524  }
525}
526
527template <class _CharT, class _Traits, class _Alloc> __size_type__
528basic_string<_CharT,_Traits,_Alloc> ::find_first_not_of(_CharT __c, size_type __pos) const {
529  if (1 > size())
530    return npos;
531  else {
532    const_pointer __result = _STLP_STD::find_if(this->_M_Start() + __pos, this->_M_Finish(),
533                                                _STLP_PRIV _Neq_char_bound<_Traits>(__c));
534    return __result != this->_M_finish ? __result - this->_M_Start() : npos;
535  }
536}
537
538template <class _CharT, class _Traits, class _Alloc>
539__size_type__
540basic_string<_CharT,_Traits,_Alloc>::find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
541{
542  typedef typename _Traits::char_type _CharType;
543  const size_type __len = size();
544  if ( __len < 1 ) {
545    return npos;
546  }
547  const_iterator __last = begin() + (min)(__len - 1, __pos) + 1;
548  const_reverse_iterator __rlast = const_reverse_iterator(__last);
549  const_reverse_iterator __rresult =
550    _STLP_PRIV __str_find_first_not_of(__rlast, rend(),
551                                       __STATIC_CAST(const _CharType*, __s),
552                                       __STATIC_CAST(const _CharType*, __s) + __n,
553                                       __STATIC_CAST(_Traits*, 0));
554  return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
555}
556
557template <class _CharT, class _Traits, class _Alloc>
558__size_type__
559basic_string<_CharT, _Traits, _Alloc>::find_last_not_of(_CharT __c, size_type __pos) const
560{
561  const size_type __len = size();
562  if ( __len < 1 ) {
563    return npos;
564  }
565  const_iterator __last = begin() + (min)(__len - 1, __pos) + 1;
566  const_reverse_iterator __rlast = const_reverse_iterator(__last);
567  const_reverse_iterator __rresult =
568    _STLP_STD::find_if(__rlast, rend(),
569                       _STLP_PRIV _Neq_char_bound<_Traits>(__c));
570  return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
571}
572
573#if !defined (basic_string)
574_STLP_MOVE_TO_PRIV_NAMESPACE
575#endif
576
577template <class _CharT, class _Traits, class _Alloc>
578void _STLP_CALL _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>& __s,
579                               _CharT* __buf, size_t __n) {
580  if (__n > 0) {
581    __n = (min) (__n - 1, __s.size());
582    _STLP_STD::copy(__s.begin(), __s.begin() + __n, __buf);
583    __buf[__n] = _CharT();
584  }
585}
586
587_STLP_MOVE_TO_STD_NAMESPACE
588
589_STLP_END_NAMESPACE
590
591#include <stl/_range_errors.h>
592
593_STLP_BEGIN_NAMESPACE
594
595_STLP_MOVE_TO_PRIV_NAMESPACE
596
597// _String_base methods
598template <class _Tp, class _Alloc>
599void _String_base<_Tp,_Alloc>::_M_throw_length_error() const
600{ __stl_throw_length_error("basic_string"); }
601
602template <class _Tp, class _Alloc>
603void _String_base<_Tp, _Alloc>::_M_throw_out_of_range() const
604{ __stl_throw_out_of_range("basic_string"); }
605
606template <class _Tp, class _Alloc>
607void _String_base<_Tp, _Alloc>::_M_allocate_block(size_t __n) {
608  if ((__n <= (max_size() + 1)) && (__n > 0)) {
609#if defined (_STLP_USE_SHORT_STRING_OPTIM)
610    if (__n > _DEFAULT_SIZE) {
611      this->_M_start_of_storage._M_data = _M_start_of_storage.allocate(__n, __n);
612      this->_M_finish = this->_M_start_of_storage._M_data;
613      this->_M_buffers._M_end_of_storage = this->_M_start_of_storage._M_data + __n;
614    }
615#else
616    this->_M_start_of_storage._M_data = _M_start_of_storage.allocate(__n, __n);
617    this->_M_finish = this->_M_start_of_storage._M_data;
618    this->_M_end_of_storage = this->_M_start_of_storage._M_data + __n;
619#endif
620  } else {
621    this->_M_throw_length_error();
622  }
623}
624
625#if !defined (basic_string)
626_STLP_MOVE_TO_STD_NAMESPACE
627#endif
628
629#if defined (_STLP_DONT_SUP_DFLT_PARAM)
630template <class _CharT, class _Traits, class _Alloc>
631basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT* __s)
632  : _STLP_PRIV _String_base<_CharT,_Alloc>(allocator_type()) {
633  _STLP_FIX_LITERAL_BUG(__s)
634  _M_range_initialize(__s, __s + traits_type::length(__s));
635}
636#endif
637
638template <class _CharT, class _Traits, class _Alloc>
639basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT* __s,
640                                                    const allocator_type& __a)
641  : _STLP_PRIV _String_base<_CharT,_Alloc>(__a) {
642  _STLP_FIX_LITERAL_BUG(__s)
643  _M_range_initialize(__s, __s + traits_type::length(__s));
644}
645
646template <class _CharT, class _Traits, class _Alloc>
647basic_string<_CharT, _Traits, _Alloc>::basic_string(const basic_string<_CharT, _Traits, _Alloc> & __s)
648  : _STLP_PRIV _String_base<_CharT,_Alloc>(__s.get_allocator())
649{ _M_range_initialize(__s._M_Start(), __s._M_Finish()); }
650
651#if defined (basic_string)
652_STLP_MOVE_TO_STD_NAMESPACE
653#  undef basic_string
654#endif
655
656#if !defined (_STLP_STATIC_CONST_INIT_BUG) && !defined (_STLP_NO_STATIC_CONST_DEFINITION)
657template <class _CharT, class _Traits, class _Alloc>
658const size_t basic_string<_CharT, _Traits, _Alloc>::npos;
659#endif
660
661_STLP_END_NAMESPACE
662
663#undef __size_type__
664#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
665#  undef size_type
666#  undef iterator
667#endif
668
669#endif /*  _STLP_STRING_C */
670
671// Local Variables:
672// mode:C++
673// End:
674