libstdc++-v3/bits/string.tcc

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 2000, 1999, 1998, 1997 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 //
  31 // ISO C++ 14882: 21  Strings library
  32 //
  33
  34 // This file is included by <string>.  It is not meant to be included
  35 // separately.
  36
  37 // Written by Jason Merrill based upon the specification by Takanori Adachi
  38 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  39
  40 #ifndef _CPP_BITS_STRING_TCC
  41 #define _CPP_BITS_STRING_TCC 1
  42
  43 namespace std
  44 {
  45
  46   template<typename _CharT, typename _Traits, typename _Alloc>
  47     _CharT
  48     basic_string<_CharT, _Traits, _Alloc>::
  49     _Rep::_S_terminal = _CharT();
  50
  51   template<typename _CharT, typename _Traits, typename _Alloc>
  52     basic_string<_CharT, _Traits, _Alloc>::size_type
  53     basic_string<_CharT, _Traits, _Alloc>::
  54     _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
  55
  56   // NB: This is the special case for Input Iterators, used in
  57   // istreambuf_iterators, etc.
  58   // Input Iterators have a cost structure very different from
  59   // pointers, calling for a different coding style.
  60   template<typename _CharT, typename _Traits, typename _Alloc>
  61     template<typename _InIter>
  62       _CharT*
  63       basic_string<_CharT, _Traits, _Alloc>::
  64       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
  65                    input_iterator_tag)
  66       {
  67         if (__beg == __end && __a == _Alloc())
  68           return _S_empty_rep()._M_refcopy();
  69         // Avoid reallocation for common case.
  70         _CharT __buf[100];
  71         size_type __i = 0;
  72         while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
  73           {
  74             __buf[__i++] = *__beg;
  75             ++__beg;
  76           }
  77         _Rep* __r = _Rep::_S_create(__i, __a);
  78         traits_type::copy(__r->_M_refdata(), __buf, __i);
  79         __r->_M_length = __i;
  80         try {
  81           // NB: this loop looks precisely this way because
  82           // it avoids comparing __beg != __end any more
  83           // than strictly necessary; != might be expensive!
  84           for (;;)
  85             {
  86               _CharT* __p = __r->_M_refdata() + __r->_M_length;
  87               _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
  88               for (;;)
  89                 {
  90                   if (__beg == __end)
  91                     {
  92                       __r->_M_length = __p - __r->_M_refdata();
  93                       *__p = _Rep::_S_terminal;       // grrr.
  94                       return __r->_M_refdata();
  95                     }
  96                   if (__p == __last)
  97                     break;
  98                   *__p++ = *__beg;
  99                   ++__beg;
 100                 }
 101               // Allocate more space.
 102               size_type __len = __p - __r->_M_refdata();
 103               _Rep* __another = _Rep::_S_create(__len + 1, __a);
 104               traits_type::copy(__another->_M_refdata(),
 105                                 __r->_M_refdata(), __len);
 106               __r->_M_destroy(__a);
 107               __r = __another;
 108               __r->_M_length = __len;
 109             }
 110         }
 111         catch (...) {
 112             __r->_M_destroy(__a);
 113             throw;
 114         }
 115         return 0;
 116       }
 117
 118   template<typename _CharT, typename _Traits, typename _Alloc>
 119     template <class _InIter>
 120       _CharT*
 121       basic_string<_CharT,_Traits,_Alloc>::
 122       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
 123                    forward_iterator_tag)
 124       {
 125         size_type __dnew = static_cast<size_type>(distance(__beg, __end));
 126
 127         if (__beg == __end && __a == _Alloc())
 128           return _S_empty_rep()._M_refcopy();
 129
 130         // Check for out_of_range and length_error exceptions.
 131         _Rep* __r = _Rep::_S_create(__dnew, __a);
 132         try {
 133           _S_copy_chars(__r->_M_refdata(), __beg, __end);
 134         }
 135         catch (...) {
 136           __r->_M_destroy(__a);
 137           throw;
 138         }
 139         __r->_M_length = __dnew;
 140
 141         __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
 142         return __r->_M_refdata();
 143       }
 144
 145   template<typename _CharT, typename _Traits, typename _Alloc>
 146     _CharT*
 147     basic_string<_CharT,_Traits, _Alloc>::
 148     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 149     {
 150       if (__n == 0 && __a == _Alloc())
 151         return _S_empty_rep()._M_refcopy();
 152
 153       // Check for out_of_range and length_error exceptions.
 154       _Rep* __r = _Rep::_S_create(__n, __a);
 155       try {
 156         if (__n)
 157           traits_type::assign(__r->_M_refdata(), __n, __c);
 158       }
 159       catch (...) {
 160         __r->_M_destroy(__a);
 161         throw;
 162       }
 163       __r->_M_length = __n;
 164       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
 165       return __r->_M_refdata();
 166     }
 167
 168   template<typename _CharT, typename _Traits, typename _Alloc>
 169     basic_string<_CharT, _Traits, _Alloc>::
 170     basic_string(const basic_string& __str)
 171     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
 172                  __str.get_allocator())
 173     { }
 174
 175   template<typename _CharT, typename _Traits, typename _Alloc>
 176     basic_string<_CharT, _Traits, _Alloc>::
 177     basic_string(const _Alloc& __a)
 178     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
 179     { }
 180
 181   template<typename _CharT, typename _Traits, typename _Alloc>
 182     basic_string<_CharT, _Traits, _Alloc>::
 183     basic_string(const basic_string& __str, size_type __pos, size_type __n)
 184     : _M_dataplus(_S_construct(__str._M_check(__pos),
 185                                __str._M_fold(__pos, __n), _Alloc()), _Alloc())
 186     { }
 187
 188   template<typename _CharT, typename _Traits, typename _Alloc>
 189     basic_string<_CharT, _Traits, _Alloc>::
 190     basic_string(const basic_string& __str, size_type __pos,
 191                  size_type __n, const _Alloc& __a)
 192     : _M_dataplus(_S_construct(__str._M_check(__pos),
 193                                __str._M_fold(__pos, __n), __a), __a)
 194     { }
 195
 196   template<typename _CharT, typename _Traits, typename _Alloc>
 197     basic_string<_CharT, _Traits, _Alloc>::
 198     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 199     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 200     { }
 201
 202   template<typename _CharT, typename _Traits, typename _Alloc>
 203     basic_string<_CharT, _Traits, _Alloc>::
 204     basic_string(const _CharT* __s, const _Alloc& __a)
 205     : _M_dataplus(_S_construct(__s, __s + traits_type::length(__s), __a), __a)
 206     { }
 207
 208   template<typename _CharT, typename _Traits, typename _Alloc>
 209     basic_string<_CharT, _Traits, _Alloc>::
 210     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 211     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 212     { }
 213
 214   template<typename _CharT, typename _Traits, typename _Alloc>
 215     template<typename _InputIter>
 216     basic_string<_CharT, _Traits, _Alloc>::
 217     basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
 218     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 219     { }
 220
 221   template<typename _CharT, typename _Traits, typename _Alloc>
 222     basic_string<_CharT, _Traits, _Alloc>&
 223     basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
 224     {
 225       if (_M_rep() != __str._M_rep())
 226         {
 227           // XXX MT
 228           allocator_type __a = this->get_allocator();
 229           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 230           _M_rep()->_M_dispose(__a);
 231           _M_data(__tmp);
 232         }
 233       return *this;
 234     }
 235
 236   template<typename _CharT, typename _Traits, typename _Alloc>
 237     void
 238     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 239     _M_destroy(const _Alloc& __a) throw ()
 240     {
 241       size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
 242       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 243     }
 244
 245   template<typename _CharT, typename _Traits, typename _Alloc>
 246     void
 247     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
 248     {
 249       if (_M_rep()->_M_is_shared())
 250         _M_mutate(0, 0, 0);
 251       _M_rep()->_M_set_leaked();
 252     }
 253
 254   template<typename _CharT, typename _Traits, typename _Alloc>
 255     void
 256     basic_string<_CharT, _Traits, _Alloc>::
 257     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 258     {
 259       size_type       __old_size = this->size();
 260       const size_type __new_size = __old_size + __len2 - __len1;
 261       const _CharT*        __src = _M_data()  + __pos + __len1;
 262       const size_type __how_much = __old_size - __pos - __len1;
 263
 264       if (_M_rep()->_M_is_shared() || __new_size > capacity())
 265         {
 266           // Must reallocate.
 267           allocator_type __a = get_allocator();
 268           _Rep* __r = _Rep::_S_create(__new_size, __a);
 269           try {
 270             if (__pos)
 271               traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
 272             if (__how_much)
 273               traits_type::copy(__r->_M_refdata() + __pos + __len2,
 274                                 __src, __how_much);
 275           }
 276           catch (...) {
 277             __r->_M_dispose(get_allocator());
 278             throw;
 279           }
 280           _M_rep()->_M_dispose(__a);
 281           _M_data(__r->_M_refdata());
 282       }
 283       else if (__how_much)
 284         {
 285           // Work in-place
 286           traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
 287         }
 288       _M_rep()->_M_set_sharable();
 289       _M_rep()->_M_length = __new_size;
 290       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
 291     // You cannot leave those LWG people alone for a second.
 292     }
 293
 294   template<typename _CharT, typename _Traits, typename _Alloc>
 295     void
 296     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
 297     {
 298       if (__res > this->capacity() || _M_rep()->_M_is_shared())
 299         {
 300           __LENGTHERROR(__res > this->max_size());
 301           allocator_type __a = get_allocator();
 302           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 303           _M_rep()->_M_dispose(__a);
 304           _M_data(__tmp);
 305         }
 306     }
 307
 308   template<typename _CharT, typename _Traits, typename _Alloc>
 309     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
 310     {
 311       if (_M_rep()->_M_is_leaked())
 312         _M_rep()->_M_set_sharable();
 313       if (__s._M_rep()->_M_is_leaked())
 314         __s._M_rep()->_M_set_sharable();
 315       if (this->get_allocator() == __s.get_allocator())
 316         {
 317           _CharT* __tmp = _M_data();
 318           _M_data(__s._M_data());
 319           __s._M_data(__tmp);
 320         }
 321       // The code below can usually be optimized away.
 322       else
 323         {
 324           basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
 325           basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 326                               this->get_allocator());
 327           *this = __tmp2;
 328           __s = __tmp1;
 329         }
 330     }
 331
 332 #ifdef _GLIBCPP_ALLOC_CONTROL
 333   template<typename _CharT, typename _Traits, typename _Alloc>
 334     bool (*basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_excess_slop)
 335     (size_t, size_t) =
 336     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_default_excess;
 337 #endif
 338
 339   template<typename _CharT, typename _Traits, typename _Alloc>
 340     basic_string<_CharT, _Traits, _Alloc>::_Rep*
 341     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 342     _S_create(size_t __capacity, const _Alloc& __alloc)
 343     {
 344 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
 345       // 83.  String::npos vs. string::max_size()
 346       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 347       __LENGTHERROR(__capacity > _S_max_size);
 348 #else
 349       __LENGTHERROR(__capacity == npos);
 350 #endif
 351
 352       // NB: Need an array of char_type[__capacity], plus a
 353       // terminating null char_type() element, plus enough for the
 354       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
 355       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 356       // NB: Might throw, but no worries about a leak, mate: _Rep()
 357       // does not throw.
 358       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
 359       _Rep *__p = new (__place) _Rep;
 360       __p->_M_capacity = __capacity;
 361       __p->_M_set_sharable();  // one reference
 362       __p->_M_length = 0;
 363       return __p;
 364     }
 365
 366   template<typename _CharT, typename _Traits, typename _Alloc>
 367     _CharT*
 368     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 369     _M_clone(const _Alloc& __alloc, size_type __res)
 370     {
 371       _Rep* __r = _Rep::_S_create(_M_length + __res, __alloc);
 372       if (_M_length)
 373         {
 374           try {
 375             traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length);
 376           }
 377           catch (...)  {
 378             __r->_M_destroy(__alloc);
 379             throw;
 380           }
 381         }
 382       __r->_M_length = _M_length;
 383       return __r->_M_refdata();
 384     }
 385
 386   template<typename _CharT, typename _Traits, typename _Alloc>
 387   inline bool
 388 #ifdef _GLIBCPP_ALLOC_CONTROL
 389     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 390     _S_default_excess(size_t __s, size_t __r)
 391 #else
 392     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 393     _S_excess_slop(size_t __s, size_t __r)
 394 #endif
 395     {
 396       return 2 * (__s <= 16 ? 16 : __s) < __r;
 397     }
 398
 399   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
 400   // at static init time (before static ctors are run).
 401   template<typename _CharT, typename _Traits, typename _Alloc>
 402     typename _Alloc::size_type
 403     basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
 404     (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
 405
 406   template<typename _CharT, typename _Traits, typename _Alloc>
 407     void
 408     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
 409     {
 410       __LENGTHERROR(__n > max_size());
 411       size_type __size = this->size();
 412       if (__size < __n)
 413         this->append(__n - __size, __c);
 414       else if (__n < __size)
 415         this->erase(__n);
 416       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 417     }
 418
 419   template<typename _CharT, typename _Traits, typename _Alloc>
 420     template<typename _InputIter>
 421       basic_string<_CharT, _Traits, _Alloc>&
 422       basic_string<_CharT, _Traits, _Alloc>::
 423       _M_replace(iterator __i1, iterator __i2, _InputIter __j1,
 424                  _InputIter __j2, input_iterator_tag)
 425       {
 426         basic_string __s(__j1, __j2);
 427         return this->replace(__i1, __i2, __s._M_ibegin(), __s._M_iend());
 428       }
 429
 430   template<typename _CharT, typename _Traits, typename _Alloc>
 431     template<typename _ForwardIter>
 432       basic_string<_CharT, _Traits, _Alloc>&
 433       basic_string<_CharT, _Traits, _Alloc>::
 434       _M_replace(iterator __i1, iterator __i2, _ForwardIter __j1,
 435                  _ForwardIter __j2, forward_iterator_tag)
 436       {
 437         size_type __dold = __i2 - __i1;
 438         size_type __dmax = this->max_size();
 439         size_type __dnew = static_cast<size_type>(distance(__j1, __j2));
 440
 441         __LENGTHERROR(__dmax <= __dnew);
 442         size_type __off = __i1 - _M_ibegin();
 443         _M_mutate(__off, __dold, __dnew);
 444         // Invalidated __i1, __i2
 445         if (__dnew)
 446           _S_copy_chars(_M_data() + __off, __j1, __j2);
 447
 448         return *this;
 449       }
 450
 451   template<typename _CharT, typename _Traits, typename _Alloc>
 452     basic_string<_CharT, _Traits, _Alloc>&
 453     basic_string<_CharT, _Traits, _Alloc>::
 454     replace(size_type __pos1, size_type __n1, const basic_string& __str,
 455             size_type __pos2, size_type __n2)
 456     {
 457       return this->replace(_M_check(__pos1), _M_fold(__pos1, __n1),
 458                            __str._M_check(__pos2),
 459                            __str._M_fold(__pos2, __n2));
 460     }
 461
 462   template<typename _CharT, typename _Traits, typename _Alloc>
 463     basic_string<_CharT,_Traits,_Alloc>&
 464     basic_string<_CharT,_Traits,_Alloc>::
 465     append(const basic_string& __str)
 466     {
 467       // Iff appending itself, string needs to pre-reserve the
 468       // correct size so that _M_mutate does not clobber the
 469       // iterators formed here.
 470       size_type __size = __str.size();
 471       size_type __len = __size + this->size();
 472       if (__len > this->capacity())
 473         this->reserve(__len);
 474       return this->replace(_M_iend(), _M_iend(), __str._M_ibegin(),
 475                            __str._M_iend());
 476     }
 477
 478   template<typename _CharT, typename _Traits, typename _Alloc>
 479     basic_string<_CharT,_Traits,_Alloc>&
 480     basic_string<_CharT,_Traits,_Alloc>::
 481     append(const basic_string& __str, size_type __pos, size_type __n)
 482     {
 483       // Iff appending itself, string needs to pre-reserve the
 484       // correct size so that _M_mutate does not clobber the
 485       // iterators formed here.
 486       size_type __len = min(__str.size() - __pos, __n) + this->size();
 487       if (__len > this->capacity())
 488         this->reserve(__len);
 489       return this->replace(_M_iend(), _M_iend(), __str._M_check(__pos),
 490                            __str._M_fold(__pos, __n));
 491     }
 492
 493   template<typename _CharT, typename _Traits, typename _Alloc>
 494     basic_string<_CharT,_Traits,_Alloc>&
 495     basic_string<_CharT,_Traits,_Alloc>::
 496     append(const _CharT* __s, size_type __n)
 497     {
 498       size_type __len = __n + this->size();
 499       if (__len > this->capacity())
 500         this->reserve(__len);
 501       return this->replace(_M_iend(), _M_iend(), __s, __s + __n);
 502     }
 503
 504   template<typename _CharT, typename _Traits, typename _Alloc>
 505     basic_string<_CharT,_Traits,_Alloc>&
 506     basic_string<_CharT,_Traits,_Alloc>::
 507     append(size_type __n, _CharT __c)
 508     {
 509       size_type __len = __n + this->size();
 510       if (__len > this->capacity())
 511         this->reserve(__len);
 512        return this->replace(_M_iend(), _M_iend(), __n, __c);
 513     }
 514
 515   template<typename _CharT, typename _Traits, typename _Alloc>
 516     basic_string<_CharT,_Traits,_Alloc>
 517     operator+(const _CharT* __lhs,
 518              const basic_string<_CharT,_Traits,_Alloc>& __rhs)
 519     {
 520       typedef basic_string<_CharT,_Traits,_Alloc> __string_type;
 521       __string_type::size_type __len = _Traits::length(__lhs);
 522       __string_type __str;
 523       __str.reserve(__len + __rhs.size());
 524       __str.append(__lhs, __lhs + __len);
 525       __str.append(__rhs);
 526       return __str;
 527     }
 528
 529   template<typename _CharT, typename _Traits, typename _Alloc>
 530     basic_string<_CharT,_Traits,_Alloc>
 531     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs)
 532     {
 533       typedef basic_string<_CharT,_Traits,_Alloc> __string_type;
 534       __string_type __str;
 535       __string_type::size_type __len = __rhs.size();
 536       __str.reserve(__len + 1);
 537       __str.append(__string_type::size_type(1), __lhs);
 538       __str.append(__rhs);
 539       return __str;
 540     }
 541
 542
 543
 544   template<typename _CharT, typename _Traits, typename _Alloc>
 545     basic_string<_CharT, _Traits, _Alloc>&
 546     basic_string<_CharT, _Traits, _Alloc>::
 547     replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
 548     {
 549       size_type __n1 = __i2 - __i1;
 550       size_type __off1 = __i1 - _M_ibegin();
 551       __LENGTHERROR(max_size() - (this->size() - __n1) <= __n2);
 552       _M_mutate (__off1, __n1, __n2);
 553       // Invalidated __i1, __i2
 554       if (__n2)
 555         traits_type::assign(_M_data() + __off1, __n2, __c);
 556       return *this;
 557     }
 558
 559
 560   template<typename _CharT, typename _Traits, typename _Alloc>
 561     basic_string<_CharT, _Traits, _Alloc>::size_type
 562     basic_string<_CharT, _Traits, _Alloc>::
 563     copy(_CharT* __s, size_type __n, size_type __pos) const
 564     {
 565       __OUTOFRANGE(__pos > this->size());
 566
 567       if (__n > this->size() - __pos)
 568         __n = this->size() - __pos;
 569
 570       traits_type::copy(__s, _M_data() + __pos, __n);
 571       // 21.3.5.7 par 3: do not append null.  (good.)
 572       return __n;
 573     }
 574
 575   // String operations
 576   // NB: This is specialized for the standard char_traits<char>
 577   // specialization to use the same optimizations as strchr.
 578   template<typename _CharT, typename _Traits, typename _Alloc>
 579     const _CharT*
 580     basic_string<_CharT, _Traits, _Alloc>::
 581     _S_find(const _CharT* __beg, const _CharT* __end, _CharT __c)
 582     {
 583       return find_if(__beg, __end, _Char_traits_match<_CharT, _Traits>(__c));
 584     }
 585
 586   // Specialization for char, definitions in src/string-inst.cc.
 587   template<>
 588     const char*
 589     string::_S_find(const char* __beg, const char* __end, char __c);
 590
 591   // Specialization for wchar_t.
 592 #ifdef _GLIBCPP_USE_WCHAR_T
 593   template<>
 594     const wchar_t*
 595     wstring::_S_find(const wchar_t* __beg, const wchar_t* __end, wchar_t __c);
 596 #endif
 597
 598   template<typename _CharT, typename _Traits, typename _Alloc>
 599     basic_string<_CharT, _Traits, _Alloc>::size_type
 600     basic_string<_CharT, _Traits, _Alloc>::
 601     find(const _CharT* __s, size_type __pos, size_type __n) const
 602     {
 603       size_t __xpos = __pos;
 604       const _CharT* __data = _M_data();
 605       for (; __xpos + __n <= this->size(); ++__xpos)
 606         if (traits_type::eq(__data[__xpos], *__s)
 607             && traits_type::compare(__data + __xpos, __s, __n) == 0)
 608           return __xpos;
 609       return npos;
 610     }
 611
 612   template<typename _CharT, typename _Traits, typename _Alloc>
 613     basic_string<_CharT, _Traits, _Alloc>::size_type
 614     basic_string<_CharT, _Traits, _Alloc>::
 615     find(_CharT __c, size_type __pos) const
 616     {
 617       size_type __size = this->size();
 618       size_type __retval = npos;
 619       if (__pos < __size)
 620         {
 621           const _CharT* __data = _M_data();
 622           const _CharT* __end = __data + __size;
 623           const _CharT* __p = _S_find(__data + __pos, __end, __c);
 624           if (__p != __end)
 625             __retval = __p - __data;
 626         }
 627       return __retval;
 628     }
 629
 630
 631   template<typename _CharT, typename _Traits, typename _Alloc>
 632     basic_string<_CharT, _Traits, _Alloc>::size_type
 633     basic_string<_CharT, _Traits, _Alloc>::
 634     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 635     {
 636       size_type __size = this->size();
 637       if (__n <= __size)
 638         {
 639           size_t __xpos = __size - __n;
 640           if (__xpos > __pos)
 641             __xpos = __pos;
 642
 643           for (++__xpos; __xpos-- > 0; )
 644             if (traits_type::eq(_M_data()[__xpos], *__s)
 645                 && traits_type::compare(_M_data() + __xpos, __s, __n) == 0)
 646               return __xpos;
 647         }
 648       return npos;
 649     }
 650
 651   template<typename _CharT, typename _Traits, typename _Alloc>
 652     basic_string<_CharT, _Traits, _Alloc>::size_type
 653     basic_string<_CharT, _Traits, _Alloc>::
 654     rfind(_CharT __c, size_type __pos) const
 655     {
 656       size_type __size = this->size();
 657       if (__size)
 658         {
 659           size_t __xpos = __size - 1;
 660           if (__xpos > __pos)
 661             __xpos = __pos;
 662
 663           for (++__xpos; __xpos-- > 0; )
 664             if (traits_type::eq(_M_data()[__xpos], __c))
 665               return __xpos;
 666         }
 667       return npos;
 668     }
 669
 670   template<typename _CharT, typename _Traits, typename _Alloc>
 671     basic_string<_CharT, _Traits, _Alloc>::size_type
 672     basic_string<_CharT, _Traits, _Alloc>::
 673     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 674     {
 675       const _CharT* __end = __s + __n;
 676       for (; __n && __pos < this->size(); ++__pos)
 677         {
 678           const _CharT* __p = _S_find(__s, __end, _M_data()[__pos]);
 679           if (__p != __end)
 680             return __pos;
 681         }
 682       return npos;
 683     }
 684
 685   template<typename _CharT, typename _Traits, typename _Alloc>
 686     basic_string<_CharT, _Traits, _Alloc>::size_type
 687     basic_string<_CharT, _Traits, _Alloc>::
 688     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 689     {
 690       size_type __size = this->size();
 691       if (__size && __n)
 692         {
 693           if (--__size > __pos)
 694             __size = __pos;
 695           do
 696             {
 697               const _CharT* __p = _S_find(__s, __s + __n, _M_data()[__size]);
 698               if (__p  != __s + __n)
 699                 return __size;
 700             }
 701           while (__size-- != 0);
 702         }
 703       return npos;
 704     }
 705
 706   template<typename _CharT, typename _Traits, typename _Alloc>
 707     basic_string<_CharT, _Traits, _Alloc>::size_type
 708     basic_string<_CharT, _Traits, _Alloc>::
 709     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 710     {
 711       size_t __xpos = __pos;
 712       for (; __n && __xpos < this->size(); ++__xpos)
 713         if (_S_find(__s, __s + __n, _M_data()[__xpos]) == __s + __n)
 714           return __xpos;
 715       return npos;
 716     }
 717
 718   template<typename _CharT, typename _Traits, typename _Alloc>
 719     basic_string<_CharT, _Traits, _Alloc>::size_type
 720     basic_string<_CharT, _Traits, _Alloc>::
 721     find_first_not_of(_CharT __c, size_type __pos) const
 722     {
 723       size_t __xpos = __pos;
 724       for (; __xpos < size(); ++__xpos)
 725         if (!traits_type::eq(_M_data()[__xpos], __c))
 726           return __xpos;
 727       return npos;
 728     }
 729
 730   template<typename _CharT, typename _Traits, typename _Alloc>
 731     basic_string<_CharT, _Traits, _Alloc>::size_type
 732     basic_string<_CharT, _Traits, _Alloc>::
 733     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 734     {
 735       size_type __size = this->size();
 736       if (__size && __n)
 737         {
 738           if (--__size > __pos)
 739             __size = __pos;
 740           do
 741             {
 742               if (_S_find(__s, __s + __n, _M_data()[__size]) == __s + __n)
 743                 return __size;
 744             }
 745           while (__size--);
 746         }
 747       return npos;
 748     }
 749
 750   template<typename _CharT, typename _Traits, typename _Alloc>
 751     basic_string<_CharT, _Traits, _Alloc>::size_type
 752     basic_string<_CharT, _Traits, _Alloc>::
 753     find_last_not_of(_CharT __c, size_type __pos) const
 754     {
 755       size_type __size = this->size();
 756       if (__size)
 757         {
 758           if (--__size > __pos)
 759             __size = __pos;
 760           do
 761             {
 762               if (!traits_type::eq(_M_data()[__size], __c))
 763                 return __size;
 764             }
 765           while (__size--);
 766         }
 767       return npos;
 768     }
 769
 770   template<typename _CharT, typename _Traits, typename _Alloc>
 771     int
 772     basic_string<_CharT, _Traits, _Alloc>::
 773     compare(size_type __pos, size_type __n, const basic_string& __str) const
 774     {
 775       size_type __size = this->size();
 776       size_type __osize = __str.size();
 777       __OUTOFRANGE(__pos > __size);
 778
 779       size_type __rsize= min(__size - __pos, __n);
 780       size_type __len = min(__rsize, __osize);
 781       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 782       if (!__r)
 783         __r = __rsize - __osize;
 784       return __r;
 785     }
 786
 787   template<typename _CharT, typename _Traits, typename _Alloc>
 788     int
 789     basic_string<_CharT, _Traits, _Alloc>::
 790     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 791             size_type __pos2, size_type __n2) const
 792     {
 793       size_type __size = this->size();
 794       size_type __osize = __str.size();
 795       __OUTOFRANGE(__pos1 > __size);
 796       __OUTOFRANGE(__pos2 > __osize);
 797
 798       size_type __rsize = min(__size - __pos1, __n1);
 799       size_type __rosize = min(__osize - __pos2, __n2);
 800       size_type __len = min(__rsize, __rosize);
 801       int __r = traits_type::compare(_M_data() + __pos1,
 802                                      __str.data() + __pos2, __len);
 803       if (!__r)
 804         __r = __rsize - __rosize;
 805       return __r;
 806     }
 807
 808
 809   template<typename _CharT, typename _Traits, typename _Alloc>
 810     int
 811     basic_string<_CharT, _Traits, _Alloc>::
 812     compare(const _CharT* __s) const
 813     {
 814       size_type __size = this->size();
 815       int __r = traits_type::compare(_M_data(), __s, __size);
 816       if (!__r)
 817         __r = __size - traits_type::length(__s);
 818       return __r;
 819     }
 820
 821
 822   template<typename _CharT, typename _Traits, typename _Alloc>
 823     int
 824     basic_string <_CharT,_Traits,_Alloc>::
 825     compare(size_type __pos, size_type __n1, const _CharT* __s,
 826             size_type __n2) const
 827     {
 828       size_type __size = this->size();
 829       __OUTOFRANGE(__pos > __size);
 830
 831       size_type __osize = min(traits_type::length(__s), __n2);
 832       size_type __rsize = min(__size - __pos, __n1);
 833       size_type __len = min(__rsize, __osize);
 834       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 835       if (!__r)
 836         __r = __rsize - __osize;
 837       return __r;
 838     }
 839
 840   template <class _CharT, class _Traits, class _Alloc>
 841     void
 842     _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
 843                    _CharT* __buf, typename _Alloc::size_type __bufsiz)
 844     {
 845       typedef typename _Alloc::size_type size_type;
 846       size_type __strsize = __str.size();
 847       size_type __bytes = min(__strsize, __bufsiz - 1);
 848       _Traits::copy(__buf, __str.data(), __bytes);
 849       __buf[__bytes] = _CharT();
 850     }
 851
 852 } // std::
 853
 854 #endif /* _CPP_BITS_STRING_TCC */
 855
 856 // Local Variables:
 857 // mode:c++
 858 // End: