include/c++/stl/stl/_string.c

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