1 /*

     2  * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

     3  *

     4  * Copyright (c) 1997-1999

     5  * Silicon Graphics Computer Systems, Inc.

     6  *

     7  * Copyright (c) 1999 

     8  * Boris Fomitchev

     9  *

    10  * This material is provided "as is", with absolutely no warranty expressed

    11  * or implied. Any use is at your own risk.

    12  *

    13  * Permission to use or copy this software for any purpose is hereby granted 

    14  * without fee, provided the above notices are retained on all copies.

    15  * Permission to modify the code and to distribute modified code is granted,

    16  * provided the above notices are retained, and a notice that the code was

    17  * modified is included with the above copyright notice.

    18  *

    19  */

    20 

    21 #ifndef _STLP_STRING_H

    22 #define _STLP_STRING_H

    23 

    24 #ifndef _STLP_MEMORY

    25 # include <memory> 

    26 #endif

    27 

    28 # ifndef _STLP_CCTYPE

    29 #  include <cctype> 

    30 # endif

    31 

    32 #ifndef _STLP_STRING_FWD_H

    33 #  include <stl/_string_fwd.h> 

    34 #endif

    35 

    36 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H

    37 # include <stl/_function.h> 

    38 #endif

    39 

    40 # include <stl/_ctraits_fns.h>  

    41 #ifndef _STLP_INTERNAL_ALGOBASE_H

    42 # include <stl/_algobase.h> 

    43 #endif

    44 

    45 #ifndef _STLP_INTERNAL_ITERATOR_H

    46 # include <stl/_iterator.h> 

    47 #endif

    48 

    49 #if defined( __MWERKS__ ) && ! defined (_STLP_USE_OWN_NAMESPACE)

    50 

    51 // MSL implementation classes expect to see the definition of streampos

    52 // when this header is included. We expect this to be fixed in later MSL

    53 // implementations

    54 # if !defined( __MSL_CPP__ ) || __MSL_CPP__ < 0x4105

    55 #  include <stl/msl_string.h> 

    56 # endif

    57 

    58 #endif // __MWERKS__

    59 

    60 // Standard C++ string class.  This class has performance

    61 // characteristics very much like vector<>, meaning, for example, that

    62 // it does not perform reference-count or copy-on-write, and that

    63 // concatenation of two strings is an O(N) operation. 

    64 

    65 // There are three reasons why basic_string is not identical to

    66 // vector.  First, basic_string always stores a null character at the

    67 // end; this makes it possible for c_str to be a fast operation.

    68 // Second, the C++ standard requires basic_string to copy elements

    69 // using char_traits<>::assign, char_traits<>::copy, and

    70 // char_traits<>::move.  This means that all of vector<>'s low-level

    71 // operations must be rewritten.  Third, basic_string<> has a lot of

    72 // extra functions in its interface that are convenient but, strictly

    73 // speaking, redundant.

    74 

    75 // Additionally, the C++ standard imposes a major restriction: according

    76 // to the standard, the character type _CharT must be a POD type.  This

    77 // implementation weakens that restriction, and allows _CharT to be a

    78 // a user-defined non-POD type.  However, _CharT must still have a

    79 // default constructor.

    80 

    81 _STLP_BEGIN_NAMESPACE

    82 

    83 # ifdef _STLP_DEBUG

    84 #  define basic_string _Nondebug_string

    85 # endif

    86 

    87 // A helper class to use a char_traits as a function object.

    88 

    89 template <class _Traits> struct _Not_within_traits

    90   : public unary_function<typename _Traits::char_type, bool> {

    91   typedef typename _Traits::char_type _CharT;

    92   const _CharT* _M_first;

    93   const _CharT* _M_last;

    94 

    95   _Not_within_traits(const typename _Traits::char_type* __f, 

    96 		     const typename _Traits::char_type* __l) 

    97     : _M_first(__f), _M_last(__l) {}

    98 

    99   bool operator()(const typename _Traits::char_type& __x) const {

   100     return find_if(_M_first, _M_last, 

   101                    _Eq_char_bound<_Traits>(__x)) == _M_last;

   102   }

   103 };

   104 

   105 

   106 // -----------------------------------------------------------------------------

   107 //	Symbian string-to-descriptor conversion

   108 // -----------------------------------------------------------------------------

   109 #ifdef _STLP_IMPLICIT_STRING_TO_DESC

   110 template< typename TYPE >

   111 class _DescConv;

   112 

   113 class _DescConv< wchar_t >

   114 {

   115 public:

   116 

   117 	typedef TPtrC16 DescT;

   118 

   119 	static TPtrC16 convert( const wchar_t *ptr, unsigned int len )

   120 	{

   121 		return TPtrC16( ptr, len );

   122 	}

   123 };

   124 

   125 class _DescConv< char >

   126 {

   127 public:

   128 	typedef TPtrC8 DescT;

   129 

   130 	static TPtrC8 convert( const char *ptr, unsigned int len )

   131 	{

   132 		return TPtrC8( (const TUint8 *)ptr, len );

   133 	}

   134 };

   135 #endif	// _STLP_IMPLICIT_STRING_TO_DESC

   136 

   137 

   138 // ------------------------------------------------------------

   139 // Class _String_base.  

   140 

   141 // _String_base is a helper class that makes it it easier to write an

   142 // exception-safe version of basic_string.  The constructor allocates,

   143 // but does not initialize, a block of memory.  The destructor

   144 // deallocates, but does not destroy elements within, a block of

   145 // memory.  The destructor assumes that _M_start either is null, or else

   146 // points to a block of memory that was allocated using _String_base's 

   147 // allocator and whose size is _M_end_of_storage._M_data - _M_start.

   148 

   149 template <class _Tp, class _Alloc> class _String_base 

   150 {

   151 public:

   152   _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)

   153   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;

   154   typedef _String_base<_Tp,_Alloc> _Base;

   155   _Tp*    _M_start;

   156   _Tp*    _M_finish;

   157   _STLP_alloc_proxy<_Tp*, _Tp, allocator_type> _M_end_of_storage;

   158   size_t  _M_stream_pos;

   159                                 // Precondition: 0 < __n <= max_size().

   160   void _M_allocate_block(size_t);

   161   void _M_deallocate_block() 

   162     { _M_end_of_storage.deallocate(_M_start, _M_end_of_storage._M_data - _M_start); }

   163   

   164   size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }

   165 

   166   _String_base(const allocator_type& __a)

   167     : _M_start(0), _M_finish(0), _M_end_of_storage(__a, (_Tp*)0), _M_stream_pos(0) {

   168     _STLP_PUSH_CLEANUP_ITEM(_Base, this)

   169   }

   170   

   171   _String_base(const allocator_type& __a, size_t __n)

   172     : _M_start(0), _M_finish(0), _M_end_of_storage(__a, (_Tp*)0), _M_stream_pos(0)

   173     {

   174       _STLP_PUSH_CLEANUP_ITEM(_Base, this)

   175       _M_allocate_block(__n); 

   176     }

   177 

   178   ~_String_base() { _M_deallocate_block(); }

   179 

   180   void _M_throw_length_error() const;

   181   void _M_throw_out_of_range() const;

   182 };

   183 

   184 # if defined (_STLP_USE_TEMPLATE_EXPORT)

   185 _STLP_EXPORT_TEMPLATE_CLASS _String_base<char, allocator<char> >;

   186 #  if defined (_STLP_HAS_WCHAR_T)

   187 _STLP_EXPORT_TEMPLATE_CLASS _String_base<wchar_t, allocator<wchar_t> >;

   188 #  endif

   189 # endif /* _STLP_USE_TEMPLATE_EXPORT */

   190 

   191 // ------------------------------------------------------------

   192 // Class basic_string.  

   193 

   194 // Class invariants:

   195 // (1) [start, finish) is a valid range.

   196 // (2) Each iterator in [start, finish) points to a valid object

   197 //     of type value_type.

   198 // (3) *finish is a valid object of type value_type; in particular,

   199 //     it is value_type().

   200 // (4) [finish + 1, end_of_storage) is a valid range.

   201 // (5) Each iterator in [finish + 1, end_of_storage) points to 

   202 //     unininitialized memory.

   203 

   204 // Note one important consequence: a string of length n must manage

   205 // a block of memory whose size is at least n + 1.  

   206 

   207 struct _String_reserve_t {};

   208 template <class _CharT, class _Traits, class _Alloc> 

   209 #ifdef __SYMBIAN32__

   210 NONSHARABLE_CLASS ( basic_string ) : public _String_base<_CharT,_Alloc> {

   211 #else

   212 class basic_string : public _String_base<_CharT,_Alloc> {

   213 #endif

   214 private:                        // Protected members inherited from base.

   215   typedef _String_base<_CharT,_Alloc> _Base;

   216   typedef basic_string<_CharT, _Traits, _Alloc> _Self;

   217   // fbp : used to optimize char/wchar_t cases, and to simplify

   218   // _STLP_DEFAULT_CONSTRUCTOR_BUG problem workaround

   219   typedef typename _Is_integer<_CharT>::_Integral _Char_Is_Integral;

   220 public:

   221   typedef _CharT value_type;

   222   typedef _Traits traits_type;

   223 

   224   typedef value_type* pointer;

   225   typedef const value_type* const_pointer;

   226   typedef value_type& reference;

   227   typedef const value_type& const_reference;

   228   typedef size_t size_type;

   229   typedef ptrdiff_t difference_type;

   230   typedef random_access_iterator_tag _Iterator_category;

   231 

   232   typedef const value_type*                const_iterator;

   233   typedef value_type*                      iterator;

   234 

   235   _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;

   236 

   237 # if defined(_STLP_STATIC_CONST_INIT_BUG) && ! defined (__SYMBIAN32__)

   238   enum { npos = -1 };

   239 # elif __GNUC__ == 2 && __GNUC_MINOR__ == 96

   240   // inline initializer conflicts with 'extern template' 

   241   static const size_t npos ;

   242 # else

   243   static const size_t npos = ~(size_t)0;

   244 # endif

   245 

   246   typedef _String_reserve_t _Reserve_t;

   247 # if defined (_STLP_USE_NATIVE_STRING) && ! defined (_STLP_DEBUG)

   248 #  if (defined(__IBMCPP__) && (500 <= __IBMCPP__) && (__IBMCPP__ < 600) )

   249    // this typedef is being used for conversions

   250    typedef typename _STLP_VENDOR_STD::basic_string<_CharT,_Traits, 

   251     typename _STLP_VENDOR_STD::allocator<_CharT> > __std_string;

   252 #  else

   253    // this typedef is being used for conversions

   254    typedef _STLP_VENDOR_STD::basic_string<_CharT,_Traits, 

   255     _STLP_VENDOR_STD::allocator<_CharT> > __std_string;

   256 #  endif

   257 # endif

   258   

   259 public:                         // Constructor, destructor, assignment.

   260   typedef typename _String_base<_CharT,_Alloc>::allocator_type allocator_type;

   261 

   262   allocator_type get_allocator() const {

   263     return _STLP_CONVERT_ALLOCATOR((const allocator_type&)this->_M_end_of_storage, _CharT);

   264   }

   265 

   266   _STLP_DECLSPEC basic_string();

   267 

   268   explicit basic_string(const allocator_type& __a)

   269     : _String_base<_CharT,_Alloc>(__a, 8) {

   270     _M_terminate_string();

   271     _STLP_POP_CLEANUP_ITEM

   272  }

   273 

   274   basic_string(_Reserve_t, size_t __n,

   275                const allocator_type& __a = allocator_type())

   276     : _String_base<_CharT,_Alloc>(__a, __n + 1) { 

   277     _M_terminate_string(); 

   278     _STLP_POP_CLEANUP_ITEM

   279   }

   280 

   281   _STLP_DECLSPEC basic_string(const basic_string<_CharT, _Traits, _Alloc>&);

   282 

   283   basic_string(const _Self& __s, size_type __pos, size_type __n = npos,

   284                const allocator_type& __a = allocator_type()) 

   285     : _String_base<_CharT,_Alloc>(__a) {

   286     if (__pos > __s.size())

   287       this->_M_throw_out_of_range();

   288     else

   289       _M_range_initialize(__s._M_start + __pos,

   290                           __s._M_start + __pos + (min) (__n, __s.size() - __pos));

   291     _STLP_POP_CLEANUP_ITEM

   292   }

   293 

   294   basic_string(const _CharT* __s, size_type __n,

   295                const allocator_type& __a = allocator_type()) 

   296     : _String_base<_CharT,_Alloc>(__a) 

   297     { 

   298       _STLP_FIX_LITERAL_BUG(__s)

   299       _M_range_initialize(__s, __s + __n); 

   300       _STLP_POP_CLEANUP_ITEM

   301     }

   302 

   303   _STLP_DECLSPEC basic_string(const _CharT* __s,

   304                const allocator_type& __a = allocator_type());

   305 

   306   basic_string(size_type __n, _CharT __c,

   307                const allocator_type& __a = allocator_type())

   308     : _String_base<_CharT,_Alloc>(__a, __n + 1)

   309   {

   310     this->_M_finish = uninitialized_fill_n(this->_M_start, __n, __c);

   311     _M_terminate_string();

   312     _STLP_POP_CLEANUP_ITEM

   313   }

   314 

   315   // Check to see if _InputIterator is an integer type.  If so, then

   316   // it can't be an iterator.

   317 #if defined (_STLP_MEMBER_TEMPLATES) && !(defined(__MRC__)||(defined(__SC__) && !defined(__DMC__)))		//*ty 04/30/2001 - mpw compilers choke on this ctor

   318 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS

   319   template <class _InputIterator> basic_string(_InputIterator __f, _InputIterator __l)

   320     : _String_base<_CharT,_Alloc>(allocator_type())

   321   {

   322     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;

   323     _M_initialize_dispatch(__f, __l, _Integral());

   324     _STLP_POP_CLEANUP_ITEM

   325   }

   326 # endif

   327   template <class _InputIterator> basic_string(_InputIterator __f, _InputIterator __l,

   328                const allocator_type & __a _STLP_ALLOCATOR_TYPE_DFL)

   329     : _String_base<_CharT,_Alloc>(__a)

   330   {

   331     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;

   332     _M_initialize_dispatch(__f, __l, _Integral());

   333     _STLP_POP_CLEANUP_ITEM

   334   }

   335 #else /* _STLP_MEMBER_TEMPLATES */

   336 

   337   basic_string(const _CharT* __f, const _CharT* __l,

   338                const allocator_type& __a = allocator_type())

   339     : _String_base<_CharT,_Alloc>(__a)

   340   {

   341     _STLP_FIX_LITERAL_BUG(__f)  _STLP_FIX_LITERAL_BUG(__l)

   342     _M_range_initialize(__f, __l);

   343     _STLP_POP_CLEANUP_ITEM

   344   }

   345 

   346 #endif

   347 

   348 # if defined (_STLP_USE_NATIVE_STRING) && ! defined (_STLP_DEBUG)

   349   // these conversion operations still needed for

   350   // strstream, etc.

   351   basic_string (const __std_string& __x): _String_base<_CharT,_Alloc>(allocator_type())

   352     {

   353       const _CharT* __s = __x.data();

   354       _M_range_initialize(__s, __s + __x.size()); 

   355       _STLP_POP_CLEANUP_ITEM

   356     }

   357   

   358   operator __std_string() const { return __std_string(this->data(), this->size()); }

   359 # endif

   360 

   361   ~basic_string() { _STLP_STD::_Destroy(this->_M_start, this->_M_finish + 1); }

   362     

   363   _Self& operator=(const _Self& __s) {

   364     if (&__s != this) 

   365     	{

   366       	assign(__s._M_start, __s._M_finish);

   367 	this->_M_stream_pos = __s.size();

   368     	}

   369     return *this;

   370   }

   371 

   372   _Self& operator=(const _CharT* __s) { 

   373     _STLP_FIX_LITERAL_BUG(__s)

   374     return assign(__s, __s + traits_type::length(__s)); 

   375   }

   376 

   377   _Self& operator=(_CharT __c)

   378     { return assign(__STATIC_CAST(size_type,1), __c); }

   379 

   380   static _CharT _STLP_CALL _M_null() {

   381     return _STLP_DEFAULT_CONSTRUCTED(_CharT);

   382   }

   383 

   384 private:                        // Helper functions used by constructors

   385                                 // and elsewhere.

   386   // fbp : simplify integer types (char, wchar)

   387   void _M_construct_null_aux(_CharT* __p, const __false_type&) {

   388     _Construct(__p);

   389   }

   390   void _M_construct_null_aux(_CharT* __p, const __true_type&) {

   391     *__p = 0;

   392   }

   393 

   394   void _M_construct_null(_CharT* __p) {

   395     _M_construct_null_aux(__p, _Char_Is_Integral());

   396   }

   397 

   398 private:                        

   399   // Helper functions used by constructors.  It is a severe error for

   400   // any of them to be called anywhere except from within constructors.

   401 

   402   void _M_terminate_string_aux(const __false_type&) {

   403     _STLP_TRY {

   404       _M_construct_null(this->_M_finish);

   405     }

   406     _STLP_UNWIND(_STLP_STD::_Destroy(this->_M_start, this->_M_finish));

   407   }

   408 

   409   void _M_terminate_string_aux(const __true_type&) {

   410     *(this->_M_finish)=0;

   411   }

   412 

   413   void _M_terminate_string() {

   414     _M_terminate_string_aux(_Char_Is_Integral());

   415   }

   416 

   417 #ifndef _STLP_MEMBER_TEMPLATES

   418   bool _M_inside(const _CharT* __s ) const {

   419     return (__s >= this->_M_start) && (__s < this->_M_finish);

   420   }

   421 #else

   422   template <class _InputIter>

   423   bool _M_inside(_InputIter __i) const {

   424     const _CharT* __s = __STATIC_CAST(const _CharT*, &(*__i));

   425     return (__s >= this->_M_start) && (__s < this->_M_finish);

   426   }

   427 #endif /*_STLP_MEMBER_TEMPLATES*/

   428 

   429 #ifdef _STLP_MEMBER_TEMPLATES

   430     

   431   template <class _InputIter> void _M_range_initialize(_InputIter __f, _InputIter __l,

   432                            const input_iterator_tag &) {

   433     this->_M_allocate_block(8);

   434     _M_construct_null(this->_M_finish);

   435     _STLP_TRY {

   436       append(__f, __l);

   437     }

   438     _STLP_UNWIND(_STLP_STD::_Destroy(this->_M_start, this->_M_finish + 1));

   439   }

   440 

   441   template <class _ForwardIter> void _M_range_initialize(_ForwardIter __f, _ForwardIter __l, 

   442                            const forward_iterator_tag &) {

   443     difference_type __n = distance(__f, __l);

   444     this->_M_allocate_block(__n + 1);

   445     this->_M_finish = uninitialized_copy(__f, __l, this->_M_start);

   446     _M_terminate_string();

   447 

   448   }

   449 

   450   template <class _InputIter> void _M_range_initialize(_InputIter __f, _InputIter __l) {

   451     _M_range_initialize(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter));

   452   }

   453 

   454   template <class _Integer> void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {

   455     this->_M_allocate_block(__n + 1);

   456     this->_M_finish = uninitialized_fill_n(this->_M_start, __n, __x);

   457     _M_terminate_string();

   458   }

   459 

   460   template <class _InputIter> void _M_initialize_dispatch(_InputIter __f, _InputIter __l, const __false_type&) {

   461      _M_range_initialize(__f, __l);

   462   }

   463     

   464 #else /* _STLP_MEMBER_TEMPLATES */

   465 

   466   void _M_range_initialize(const _CharT* __f, const _CharT* __l) {

   467     ptrdiff_t __n = __l - __f;

   468     this->_M_allocate_block(__n + 1);

   469     this->_M_finish = uninitialized_copy(__f, __l, this->_M_start);

   470     _M_terminate_string();

   471   }

   472 

   473 #endif /* _STLP_MEMBER_TEMPLATES */

   474 

   475 #ifdef _STLP_USE_TRAP_LEAVE

   476 public:

   477   static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   478   static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   479 #endif

   480 

   481 public:                         // Iterators.

   482   iterator begin()             { return this->_M_start; }

   483   iterator end()               { return this->_M_finish; }

   484   const_iterator begin() const { return this->_M_start; }

   485   const_iterator end()   const { return this->_M_finish; }  

   486 

   487   reverse_iterator rbegin()             

   488     { return reverse_iterator(this->_M_finish); }

   489   reverse_iterator rend()               

   490     { return reverse_iterator(this->_M_start); }

   491   const_reverse_iterator rbegin() const 

   492     { return const_reverse_iterator(this->_M_finish); }

   493   const_reverse_iterator rend()   const 

   494     { return const_reverse_iterator(this->_M_start); }

   495 

   496 public:                         // Size, capacity, etc.

   497   size_type size() const { return this->_M_finish - this->_M_start; }

   498   size_type length() const { return size(); }

   499 

   500   size_t max_size() const { return _Base::max_size(); }

   501 

   502 

   503   void resize(size_type __n, _CharT __c) {

   504     if (__n <= size())

   505       erase(begin() + __n, end());

   506     else

   507       append(__n - size(), __c);

   508   }

   509   void resize(size_type __n) { resize(__n, _M_null()); }

   510 

   511   _STLP_DECLSPEC void reserve(size_type = 0);

   512 

   513   size_type capacity() const { return (this->_M_end_of_storage._M_data - this->_M_start) - 1; }

   514 

   515   void clear() {

   516     if (!empty()) {

   517       _Traits::assign(*(this->_M_start), _M_null());

   518       _STLP_STD::_Destroy(this->_M_start+1, this->_M_finish+1);

   519       this->_M_finish = this->_M_start;

   520     }

   521   } 

   522 

   523   bool empty() const { return this->_M_start == this->_M_finish; }    

   524 

   525 public:                         // Element access.

   526 

   527   const_reference operator[](size_type __n) const

   528     { return *(this->_M_start + __n); }

   529   reference operator[](size_type __n)

   530     { return *(this->_M_start + __n); }

   531 

   532   const_reference at(size_type __n) const {

   533     if (__n >= size())

   534       this->_M_throw_out_of_range();

   535     return *(this->_M_start + __n);

   536   }

   537 

   538   reference at(size_type __n) {

   539     if (__n >= size())

   540       this->_M_throw_out_of_range();

   541     return *(this->_M_start + __n);

   542   }

   543 

   544 public:                         // Append, operator+=, push_back.

   545 

   546   _Self& operator+=(const _Self& __s) { return append(__s); }

   547   _Self& operator+=(const _CharT* __s) { _STLP_FIX_LITERAL_BUG(__s) return append(__s); }

   548   _Self& operator+=(_CharT __c) { push_back(__c); return *this; }

   549 

   550   _Self& append(const _Self& __s) 

   551     { return append(__s._M_start, __s._M_finish); }

   552 

   553   _Self& append(const _Self& __s,

   554                        size_type __pos, size_type __n)

   555   {

   556     if (__pos > __s.size())

   557       this->_M_throw_out_of_range();

   558     return append(__s._M_start + __pos,

   559                   __s._M_start + __pos + (min) (__n, __s.size() - __pos));

   560   }

   561 

   562   _Self& append(const _CharT* __s, size_type __n) 

   563     { _STLP_FIX_LITERAL_BUG(__s) return append(__s, __s+__n); }

   564   _Self& append(const _CharT* __s) 

   565     { _STLP_FIX_LITERAL_BUG(__s) return append(__s, __s + traits_type::length(__s)); }

   566   _Self& append(size_type __n, _CharT __c);

   567 

   568 #ifdef _STLP_MEMBER_TEMPLATES

   569 

   570   // Check to see if _InputIterator is an integer type.  If so, then

   571   // it can't be an iterator.

   572   template <class _InputIter> _Self& append(_InputIter __first, _InputIter __last) {

   573     typedef typename _Is_integer<_InputIter>::_Integral _Integral;

   574     return _M_append_dispatch(__first, __last, _Integral());

   575   }

   576 

   577 #else /* _STLP_MEMBER_TEMPLATES */

   578 

   579   _Self& append(const _CharT* __first, const _CharT* __last);

   580 

   581 #endif /* _STLP_MEMBER_TEMPLATES */

   582 

   583   void push_back(_CharT __c) {

   584     if (this->_M_finish + 1 == this->_M_end_of_storage._M_data)

   585       reserve(size() + (max)(size(), __STATIC_CAST(size_type,1)));

   586     _M_construct_null(this->_M_finish + 1);

   587     _Traits::assign(*(this->_M_finish), __c);

   588     ++this->_M_finish;

   589   }

   590 

   591   void pop_back() {

   592     _Traits::assign(*(this->_M_finish - 1), _M_null());

   593     _STLP_STD::_Destroy(this->_M_finish);

   594     --this->_M_finish;

   595   }

   596 

   597 private:                        // Helper functions for append.

   598 

   599 #ifdef _STLP_MEMBER_TEMPLATES

   600 

   601   template <class _InputIter> _Self& append(_InputIter __first, _InputIter __last, const input_iterator_tag &)

   602   {

   603 	  for ( ; __first != __last ; ++__first)

   604 	    push_back(*__first);

   605 	  return *this;

   606 	}

   607 

   608   template <class _ForwardIter> _Self& append(_ForwardIter __first, _ForwardIter __last, 

   609                        const forward_iterator_tag &)  {

   610     if (__first != __last) {

   611 	    const size_type __old_size = size();

   612 	    difference_type __n = distance(__first, __last);

   613 	    if (__STATIC_CAST(size_type,__n) > max_size() || __old_size > max_size() - __STATIC_CAST(size_type,__n))

   614 	      this->_M_throw_length_error();

   615 	    if (__old_size + __n > capacity()) {

   616 	      const size_type __len = __old_size +

   617 	                            (max)(__old_size, __STATIC_CAST(size_type,__n)) + 1;

   618 	      _STLP_LEAVE_VOLATILE pointer __new_start = this->_M_end_of_storage.allocate(__len);

   619 	      _STLP_LEAVE_VOLATILE pointer __new_finish = __new_start;

   620 	      _STLP_TRY {

   621 	        __new_finish = uninitialized_copy(this->_M_start, this->_M_finish, __new_start);

   622 	        __new_finish = uninitialized_copy(__first, __last, __new_finish);

   623 	        _M_construct_null(__new_finish);

   624 	      }

   625 	      _STLP_UNWIND((_STLP_STD::_Destroy(__new_start,__new_finish),

   626 	                    this->_M_end_of_storage.deallocate(__new_start,__len)));

   627 	      _STLP_STD::_Destroy(this->_M_start, this->_M_finish + 1);

   628 	      this->_M_deallocate_block();

   629 	      this->_M_start = __new_start;

   630 	      this->_M_finish = __new_finish;

   631 	      this->_M_end_of_storage._M_data = __new_start + __len; 

   632 	    }

   633 	    else {

   634 	      _ForwardIter __f1 = __first;

   635 	      ++__f1;

   636 	      uninitialized_copy(__f1, __last, this->_M_finish + 1);

   637 	      _STLP_TRY {

   638 	        _M_construct_null(this->_M_finish + __n);

   639 	      }

   640 	      _STLP_UNWIND(_STLP_STD::_Destroy(this->_M_finish + 1, this->_M_finish + __n));

   641 	      _Traits::assign(*end(), *__first);

   642 	      this->_M_finish += __n;

   643 	    }

   644 	  }

   645 	  return *this;  

   646 	}

   647 

   648   template <class _Integer> _Self& _M_append_dispatch(_Integer __n, _Integer __x, const __true_type&) {

   649     return append((size_type) __n, (_CharT) __x);

   650   }

   651 

   652   template <class _InputIter> _Self& _M_append_dispatch(_InputIter __f, _InputIter __l,

   653                                    const __false_type&) {

   654     return append(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter));

   655   }

   656 

   657 #endif /* _STLP_MEMBER_TEMPLATES */

   658 

   659 public:                         // Assign

   660   

   661   _Self& assign(const _Self& __s) 

   662     { return assign(__s._M_start, __s._M_finish); }

   663 

   664   _Self& assign(const _Self& __s, 

   665                        size_type __pos, size_type __n) {

   666     if (__pos > __s.size())

   667       this->_M_throw_out_of_range();

   668     return assign(__s._M_start + __pos, 

   669                   __s._M_start + __pos + (min) (__n, __s.size() - __pos));

   670   }

   671 

   672   _Self& assign(const _CharT* __s, size_type __n)

   673     { _STLP_FIX_LITERAL_BUG(__s) return assign(__s, __s + __n); }

   674 

   675   _Self& assign(const _CharT* __s)

   676     { _STLP_FIX_LITERAL_BUG(__s) return assign(__s, __s + _Traits::length(__s)); }

   677 

   678   _STLP_DECLSPEC _Self& assign(size_type __n, _CharT __c);

   679 

   680 #ifdef _STLP_MEMBER_TEMPLATES

   681 

   682 private:                        // Helper functions for assign.

   683 

   684   template <class _Integer> 

   685   _Self& _M_assign_dispatch(_Integer __n, _Integer __x, const __true_type&) {

   686     return assign((size_type) __n, (_CharT) __x);

   687   }

   688 

   689   template <class _InputIter> 

   690   _Self& _M_assign_dispatch(_InputIter __f, _InputIter __l,

   691 			    const __false_type&)  {

   692     pointer __cur = this->_M_start;

   693     while (__f != __l && __cur != this->_M_finish) {

   694       _Traits::assign(*__cur, *__f);

   695       ++__f;

   696       ++__cur;

   697     }

   698     if (__f == __l)

   699       erase(__cur, end());

   700     else

   701       append(__f, __l);

   702     return *this;

   703   }

   704   

   705 public:

   706   // Check to see if _InputIterator is an integer type.  If so, then

   707   // it can't be an iterator.

   708   template <class _InputIter> _Self& assign(_InputIter __first, _InputIter __last) {

   709     typedef typename _Is_integer<_InputIter>::_Integral _Integral;

   710     return _M_assign_dispatch(__first, __last, _Integral());

   711   }

   712 #endif  /* _STLP_MEMBER_TEMPLATES */

   713 

   714   // if member templates are on, this works as specialization 

   715   _Self& assign(const _CharT* __f, const _CharT* __l)

   716   {

   717     ptrdiff_t __n = __l - __f;

   718     if (__STATIC_CAST(size_type,__n) <= size()) {

   719       _Traits::copy(this->_M_start, __f, __n);

   720       erase(begin() + __n, end());

   721     }

   722     else {

   723       _Traits::copy(this->_M_start, __f, size());

   724       append(__f + size(), __l);

   725     }

   726     return *this;

   727   }

   728   

   729 public:                         // Insert

   730 

   731   _Self& insert(size_type __pos, const _Self& __s) {

   732     if (__pos > size())

   733       this->_M_throw_out_of_range();

   734     if (size() > max_size() - __s.size())

   735       this->_M_throw_length_error();

   736     insert(begin() + __pos, __s._M_start, __s._M_finish);

   737     return *this;

   738   }

   739 

   740   _Self& insert(size_type __pos, const _Self& __s,

   741                        size_type __beg, size_type __n) {

   742     if (__pos > size() || __beg > __s.size())

   743       this->_M_throw_out_of_range();

   744     size_type __len = (min) (__n, __s.size() - __beg);

   745     if (size() > max_size() - __len)

   746       this->_M_throw_length_error();

   747     insert(begin() + __pos,

   748            __s._M_start + __beg, __s._M_start + __beg + __len);

   749     return *this;

   750   }

   751 

   752   _Self& insert(size_type __pos, const _CharT* __s, size_type __n) {

   753     _STLP_FIX_LITERAL_BUG(__s)

   754     if (__pos > size())

   755       this->_M_throw_out_of_range();

   756     if (size() > max_size() - __n)

   757       this->_M_throw_length_error();

   758     insert(begin() + __pos, __s, __s + __n);

   759     return *this;

   760   }

   761 

   762   _Self& insert(size_type __pos, const _CharT* __s) {

   763     _STLP_FIX_LITERAL_BUG(__s)

   764     if (__pos > size())

   765       this->_M_throw_out_of_range();

   766     size_type __len = _Traits::length(__s);

   767     if (size() > max_size() - __len)

   768       this->_M_throw_length_error();

   769     insert(this->_M_start + __pos, __s, __s + __len);

   770     return *this;

   771   }

   772     

   773   _Self& insert(size_type __pos, size_type __n, _CharT __c) {

   774     if (__pos > size())

   775       this->_M_throw_out_of_range();

   776     if (size() > max_size() - __n)

   777       this->_M_throw_length_error();

   778     insert(begin() + __pos, __n, __c);

   779     return *this;

   780   }

   781 

   782   iterator insert(iterator __p, _CharT __c) {

   783     _STLP_FIX_LITERAL_BUG(__p)

   784     if (__p == end()) {

   785       push_back(__c);

   786       return this->_M_finish - 1;

   787     }

   788     else

   789       return _M_insert_aux(__p, __c);

   790   }

   791 

   792   void insert(iterator __p, size_t __n, _CharT __c);

   793 

   794 #ifdef _STLP_MEMBER_TEMPLATES

   795 

   796   // Check to see if _InputIterator is an integer type.  If so, then

   797   // it can't be an iterator.

   798   template <class _InputIter> void insert(iterator __p, _InputIter __first, _InputIter __last) {

   799     typedef typename _Is_integer<_InputIter>::_Integral _Integral;

   800     _M_insert_dispatch(__p, __first, __last, _Integral());

   801   }

   802 

   803 #else /* _STLP_MEMBER_TEMPLATES */

   804 

   805   _STLP_DECLSPEC void insert(iterator __p, const _CharT* __first, const _CharT* __last);

   806 

   807 #endif /* _STLP_MEMBER_TEMPLATES */

   808 

   809 private:                        // Helper functions for insert.

   810 

   811 #ifdef _STLP_MEMBER_TEMPLATES

   812 

   813   template <class _InputIter> void insert(iterator __p, _InputIter __first, _InputIter __last,

   814 	      const input_iterator_tag &)

   815   {

   816 	  for ( ; __first != __last; ++__first) {

   817 	    __p = insert(__p, *__first);

   818 	    ++__p;

   819 	  }

   820 	}

   821 

   822   template <class _ForwardIter> 

   823   void insert(iterator __position, _ForwardIter __first, _ForwardIter __last, 

   824 	      const forward_iterator_tag &)  {

   825     if (__first != __last) {

   826       difference_type __n = distance(__first, __last);

   827       if (this->_M_end_of_storage._M_data - this->_M_finish >= __n + 1) {

   828 	const difference_type __elems_after = this->_M_finish - __position;

   829 	pointer __old_finish = this->_M_finish;

   830 	if (__elems_after >= __n) {

   831 	  uninitialized_copy((this->_M_finish - __n) + 1, this->_M_finish + 1,

   832 			     this->_M_finish + 1);

   833 	  this->_M_finish += __n;

   834 	  _Traits::move(__position + __n,

   835 			__position, (__elems_after - __n) + 1);

   836 	  _M_move(__first, __last, __position);

   837 	      }

   838 	else {

   839 	  _ForwardIter __mid = __first;

   840 	  advance(__mid, __elems_after + 1);

   841 	  uninitialized_copy(__mid, __last, this->_M_finish + 1);

   842 	  this->_M_finish += __n - __elems_after;

   843 	        _STLP_TRY {

   844 	          uninitialized_copy(__position, __old_finish + 1, this->_M_finish);

   845 	          this->_M_finish += __elems_after;

   846 	        }

   847 	        _STLP_UNWIND((_STLP_STD::_Destroy(__old_finish + 1, this->_M_finish), 

   848 	                      this->_M_finish = __old_finish));

   849 	        _M_move(__first, __mid, __position);

   850 	}

   851       }

   852       else {

   853 	const size_type __old_size = size();        

   854 	const size_type __len

   855 	  = __old_size + (max)(__old_size, __STATIC_CAST(size_type,__n)) + 1;

   856 	      _STLP_LEAVE_VOLATILE pointer __new_start = this->_M_end_of_storage.allocate(__len);

   857 	      _STLP_LEAVE_VOLATILE pointer __new_finish = __new_start;

   858 	      _STLP_TRY {

   859 	        __new_finish = uninitialized_copy(this->_M_start, __position, __new_start);

   860 	        __new_finish = uninitialized_copy(__first, __last, __new_finish);

   861 	        __new_finish

   862 	          = uninitialized_copy(__position, this->_M_finish, __new_finish);

   863 	        _M_construct_null(__new_finish);

   864 	      }

   865 	      _STLP_UNWIND((_STLP_STD::_Destroy(__new_start,__new_finish),

   866 	                    this->_M_end_of_storage.deallocate(__new_start,__len)));

   867 	      _STLP_STD::_Destroy(this->_M_start, this->_M_finish + 1);

   868 	      this->_M_deallocate_block();

   869 	      this->_M_start = __new_start;

   870 	      this->_M_finish = __new_finish;

   871 	      this->_M_end_of_storage._M_data = __new_start + __len; 

   872 	    }

   873     }

   874   }

   875 

   876   template <class _Integer> void _M_insert_dispatch(iterator __p, _Integer __n, _Integer __x,

   877                           const __true_type&) {

   878     insert(__p, (size_type) __n, (_CharT) __x);

   879   }

   880 

   881   template <class _InputIter> void _M_insert_dispatch(iterator __p, _InputIter __first, _InputIter __last,

   882                           const __false_type&) {

   883     insert(__p, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));

   884   }

   885 

   886   template <class _InputIterator> void 

   887   _M_copy(_InputIterator __first, _InputIterator __last, pointer __result) {

   888     for ( ; __first != __last; ++__first, ++__result)

   889       _Traits::assign(*__result, *__first);

   890   }

   891 

   892   template <class _InputIterator>

   893   void _M_move(_InputIterator __first, _InputIterator __last, pointer __result) {

   894     //call _M_copy as being here means that __result is not within [__first, __last)

   895     for ( ; __first != __last; ++__first, ++__result)

   896       _Traits::assign(*__result, *__first);

   897   }

   898 

   899 #endif /* _STLP_MEMBER_TEMPLATES */

   900 

   901   pointer _M_insert_aux(pointer, _CharT);

   902 

   903   void 

   904   _M_copy(const _CharT* __first, const _CharT* __last, _CharT* __result) {

   905     _Traits::copy(__result, __first, __last - __first);

   906   }

   907   void _M_move(const _CharT* __first, const _CharT* __last, _CharT* __result) {

   908     _Traits::move(__result, __first, __last - __first);

   909   }

   910 

   911 public:                         // Erase.

   912 

   913   _Self& erase(size_type __pos = 0, size_type __n = npos) {

   914     if (__pos > size())

   915       this->_M_throw_out_of_range();

   916     erase(begin() + __pos, begin() + __pos + (min) (__n, size() - __pos));

   917     return *this;

   918   }  

   919 

   920   iterator erase(iterator __position) {

   921                                 // The move includes the terminating _CharT().

   922     _Traits::move(__position, __position + 1, this->_M_finish - __position);

   923     _STLP_STD::_Destroy(this->_M_finish);

   924     --this->_M_finish;

   925     return __position;

   926   }

   927 

   928   iterator erase(iterator __first, iterator __last) {

   929     if (__first != __last) {

   930                                 // The move includes the terminating _CharT().

   931       traits_type::move(__first, __last, (this->_M_finish - __last) + 1);

   932       pointer __new_finish = this->_M_finish - (__last - __first);

   933       _STLP_STD::_Destroy(__new_finish + 1, this->_M_finish + 1);

   934       this->_M_finish = __new_finish;

   935     }

   936     return __first;

   937   }

   938 

   939 public:                         // Replace.  (Conceptually equivalent

   940                                 // to erase followed by insert.)

   941   _Self& replace(size_type __pos, size_type __n, 

   942                         const _Self& __s) {

   943     if (__pos > size())

   944       this->_M_throw_out_of_range();

   945     const size_type __len = (min) (__n, size() - __pos);

   946     if (size() - __len >= max_size() - __s.size())

   947       this->_M_throw_length_error();

   948     return replace(begin() + __pos, begin() + __pos + __len, 

   949                    __s._M_start, __s._M_finish);

   950   }

   951 

   952   _Self& replace(size_type __pos1, size_type __n1,

   953                         const _Self& __s,

   954                         size_type __pos2, size_type __n2) {

   955     if (__pos1 > size() || __pos2 > __s.size())

   956       this->_M_throw_out_of_range();

   957     const size_type __len1 = (min) (__n1, size() - __pos1);

   958     const size_type __len2 = (min) (__n2, __s.size() - __pos2);

   959     if (size() - __len1 >= max_size() - __len2)

   960       this->_M_throw_length_error();

   961     return replace(begin() + __pos1, begin() + __pos1 + __len1,

   962                    __s._M_start + __pos2, __s._M_start + __pos2 + __len2);

   963   }

   964 

   965   _Self& replace(size_type __pos, size_type __n1,

   966                         const _CharT* __s, size_type __n2) {

   967     _STLP_FIX_LITERAL_BUG(__s)

   968     if (__pos > size())

   969       this->_M_throw_out_of_range();

   970     const size_type __len = (min) (__n1, size() - __pos);

   971     if (__n2 > max_size() || size() - __len >= max_size() - __n2)

   972       this->_M_throw_length_error();

   973     return replace(begin() + __pos, begin() + __pos + __len,

   974                    __s, __s + __n2);

   975   }

   976 

   977   _Self& replace(size_type __pos, size_type __n1,

   978                         const _CharT* __s) {

   979     _STLP_FIX_LITERAL_BUG(__s)

   980     if (__pos > size())

   981       this->_M_throw_out_of_range();

   982     const size_type __len = (min) (__n1, size() - __pos);

   983     const size_type __n2 = _Traits::length(__s);

   984     if (__n2 > max_size() || size() - __len >= max_size() - __n2)

   985       this->_M_throw_length_error();

   986     return replace(begin() + __pos, begin() + __pos + __len,

   987                    __s, __s + _Traits::length(__s));

   988   }

   989 

   990   _Self& replace(size_type __pos, size_type __n1,

   991                         size_type __n2, _CharT __c) {

   992     if (__pos > size())

   993       this->_M_throw_out_of_range();

   994     const size_type __len = (min) (__n1, size() - __pos);

   995     if (__n2 > max_size() || size() - __len >= max_size() - __n2)

   996       this->_M_throw_length_error();

   997     return replace(begin() + __pos, begin() + __pos + __len, __n2, __c);

   998   }

   999 

  1000   _Self& replace(iterator __first, iterator __last, 

  1001                         const _Self& __s) 

  1002     { return replace(__first, __last, __s._M_start, __s._M_finish); }

  1003 

  1004   _Self& replace(iterator __first, iterator __last,

  1005                         const _CharT* __s, size_type __n) 

  1006     { _STLP_FIX_LITERAL_BUG(__s) return replace(__first, __last, __s, __s + __n); }

  1007 

  1008   _Self& replace(iterator __first, iterator __last,

  1009                         const _CharT* __s) {

  1010     _STLP_FIX_LITERAL_BUG(__s)

  1011     return replace(__first, __last, __s, __s + _Traits::length(__s));

  1012   }

  1013 

  1014   _Self& replace(iterator __first, iterator __last, 

  1015                         size_type __n, _CharT __c);

  1016 

  1017   // Check to see if _InputIterator is an integer type.  If so, then

  1018   // it can't be an iterator.

  1019 #ifdef _STLP_MEMBER_TEMPLATES

  1020   template <class _InputIter> _Self& replace(iterator __first, iterator __last,

  1021                         _InputIter __f, _InputIter __l) {

  1022     typedef typename _Is_integer<_InputIter>::_Integral _Integral;

  1023     return _M_replace_dispatch(__first, __last, __f, __l,  _Integral());

  1024   }

  1025 #else /* _STLP_MEMBER_TEMPLATES */

  1026   _Self& replace(iterator __first, iterator __last,

  1027 		 const _CharT* __f, const _CharT* __l);

  1028 #endif /* _STLP_MEMBER_TEMPLATES */

  1029 

  1030 private:                        // Helper functions for replace.

  1031 

  1032 #ifdef _STLP_MEMBER_TEMPLATES

  1033 

  1034   template <class _Integer> _Self& _M_replace_dispatch(iterator __first, iterator __last,

  1035                                     _Integer __n, _Integer __x,

  1036                                     const __true_type&) {

  1037     return replace(__first, __last, (size_type) __n, (_CharT) __x);

  1038   }

  1039 

  1040   template <class _InputIter> _Self& _M_replace_dispatch(iterator __first, iterator __last,

  1041                                     _InputIter __f, _InputIter __l,

  1042                                     const __false_type&) {

  1043     return replace(__first, __last, __f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIter));

  1044   }

  1045 

  1046   template <class _InputIter> _Self& replace(iterator __first, iterator __last,

  1047                         _InputIter __f, _InputIter __l, const input_iterator_tag &)  {

  1048 	  for ( ; __first != __last && __f != __l; ++__first, ++__f)

  1049 	    _Traits::assign(*__first, *__f);

  1050 

  1051 	  if (__f == __l)

  1052 	    erase(__first, __last);

  1053 	  else

  1054 	    insert(__last, __f, __l);

  1055 	  return *this;

  1056 	}

  1057 

  1058   template <class _InputIter>

  1059   _Self& replace(iterator __first, iterator __last,

  1060                  _InputIter __f, _InputIter __l, const random_access_iterator_tag &) {

  1061     //might be overlapping

  1062     if (_M_inside(__f)) {

  1063       difference_type __n = __l - __f;

  1064       const difference_type __len = __last - __first;

  1065       if (__len >= __n) {

  1066         _M_move(__f, __l, __first);

  1067         erase(__first + __n, __last);

  1068       }

  1069       else {

  1070         _InputIter __m = __f + __len;

  1071         if ((__l <= __first) || (__f >= __last)) {

  1072 				  //no overlap:

  1073           _M_copy(__f, __m, __first);

  1074           insert(__last, __m, __l);

  1075         }

  1076         else {

  1077 				  //we have to take care of reallocation:

  1078 				  const difference_type __off_dest = __first - this->begin();

  1079 				  const difference_type __off_src = __f - this->begin();

  1080 				  insert(__last, __m, __l);

  1081 				  _Traits::move(begin() + __off_dest, begin() + __off_src, __n);

  1082         }

  1083       }

  1084       return *this;

  1085     }

  1086 	  else {

  1087 		  return replace(__first, __last, __f, __l, forward_iterator_tag());

  1088 	  }

  1089   }

  1090 

  1091 

  1092   template <class _ForwardIter> _Self& replace(iterator __first, iterator __last,

  1093                         _ForwardIter __f, _ForwardIter __l, 

  1094                         const forward_iterator_tag &)  {

  1095 	  difference_type __n = distance(__f, __l);

  1096 	  const difference_type __len = __last - __first;

  1097 	  if (__len >= __n) {

  1098 	    _M_copy(__f, __l, __first);

  1099 	    erase(__first + __n, __last);

  1100 	  }

  1101 	  else {

  1102 	    _ForwardIter __m = __f;

  1103 	    advance(__m, __len);

  1104 	    _M_copy(__f, __m, __first);

  1105 	    insert(__last, __m, __l);

  1106 	  }

  1107 	  return *this;

  1108 	}

  1109 

  1110 #endif /* _STLP_MEMBER_TEMPLATES */

  1111 

  1112 public:                         // Other modifier member functions.

  1113 

  1114   size_type copy(_CharT* __s, size_type __n, size_type __pos = 0) const {

  1115     _STLP_FIX_LITERAL_BUG(__s)

  1116     if (__pos > size())

  1117       this->_M_throw_out_of_range();

  1118     const size_type __len = (min) (__n, size() - __pos);

  1119     _Traits::copy(__s, this->_M_start + __pos, __len);

  1120     return __len;

  1121   }

  1122 

  1123   void swap(_Self& __s) {

  1124     _STLP_STD::swap(this->_M_start, __s._M_start);

  1125     _STLP_STD::swap(this->_M_finish, __s._M_finish);

  1126     _STLP_STD::swap(this->_M_end_of_storage, __s._M_end_of_storage);

  1127   }

  1128 

  1129 public:                         // Conversion to C string.

  1130 

  1131   const _CharT* c_str() const { return this->_M_start; }

  1132   const _CharT* data()  const { return this->_M_start; }

  1133 

  1134 public:                         // find.