Sierra Toolkit Version of the Day
string_eastl.h
00001 /*
00002 Copyright (C) 2005,2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/string.h
00031 // Written and maintained by Paul Pedriana - 2005.
00033 
00035 // Implements a basic_string class, much like the C++ std::basic_string.
00036 // The primary distinctions between basic_string and std::basic_string are:
00037 //    - basic_string has a few extension functions that allow for increased performance.
00038 //    - basic_string has a few extension functions that make use easier,
00039 //      such as a member sprintf function and member tolower/toupper functions.
00040 //    - basic_string supports debug memory naming natively.
00041 //    - basic_string is easier to read, debug, and visualize.
00042 //    - basic_string internally manually expands basic functions such as begin(),
00043 //      size(), etc. in order to improve debug performance and optimizer success.
00044 //    - basic_string is savvy to an environment that doesn't have exception handling,
00045 //      as is sometimes the case with console or embedded environments.
00046 //    - basic_string has less deeply nested function calls and allows the user to
00047 //      enable forced inlining in debug builds in order to reduce bloat.
00048 //    - basic_string doesn't use char traits. As a result, EASTL assumes that
00049 //      strings will hold characters and not exotic things like widgets. At the
00050 //      very least, basic_string assumes that the value_type is a POD.
00051 //    - basic_string::size_type is defined as eastl_size_t instead of size_t in
00052 //      order to save memory and run faster on 64 bit systems.
00053 //    - basic_string data is guaranteed to be contiguous.
00054 //    - basic_string data is guaranteed to be 0-terminated, and the c_str() function
00055 //      is guaranteed to return the same pointer as the data() which is guaranteed
00056 //      to be the same value as &string[0].
00057 //    - basic_string has a set_capacity() function which frees excess capacity.
00058 //      The only way to do this with std::basic_string is via the cryptic non-obvious
00059 //      trick of using: basic_string<char>(x).swap(x);
00060 //    - basic_string has a force_size() function, which unilaterally moves the string
00061 //      end position (mpEnd) to the given location. Useful for when the user writes
00062 //      into the string via some extenal means such as C strcpy or sprintf.
00064 
00066 // Copy on Write (cow)
00067 //
00068 // This string implementation does not do copy on write (cow). This is by design,
00069 // as cow penalizes 95% of string uses for the benefit of only 5% of the uses
00070 // (these percentages are qualitative, not quantitative). The primary benefit of
00071 // cow is that it allows for the sharing of string data between two string objects.
00072 // Thus if you say this:
00073 //    string a("hello");
00074 //    string b(a);
00075 // the "hello" will be shared between a and b. If you then say this:
00076 //    a = "world";
00077 // then a will release its reference to "hello" and leave b with the only reference
00078 // to it. Normally this functionality is accomplished via reference counting and
00079 // with atomic operations or mutexes.
00080 //
00081 // The C++ standard does not say anything about basic_string and cow. However,
00082 // for a basic_string implementation to be standards-conforming, a number of
00083 // issues arise which dictate some things about how one would have to implement
00084 // a cow string. The discussion of these issues will not be rehashed here, as you
00085 // can read the references below for better detail than can be provided in the
00086 // space we have here. However, we can say that the C++ standard is sensible and
00087 // that anything we try to do here to allow for an efficient cow implementation
00088 // would result in a generally unacceptable string interface.
00089 //
00090 // The disadvantages of cow strings are:
00091 //    - A reference count needs to exist with the string, which increases string memory usage.
00092 //    - With thread safety, atomic operations and mutex locks are expensive, especially
00093 //      on weaker memory systems such as console gaming platforms.
00094 //    - All non-const string accessor functions need to do a sharing check the the
00095 //      first such check needs to detach the string. Similarly, all string assignments
00096 //      need to do a sharing check as well. If you access the string before doing an
00097 //      assignment, the assignment doesn't result in a shared string, because the string
00098 //      has already been detached.
00099 //    - String sharing doesn't happen the large majority of the time. In some cases,
00100 //      the total sum of the reference count memory can exceed any memory savings
00101 //      gained by the strings that share representations.
00102 //
00103 // The addition of a string_cow class is under consideration for this library.
00104 // There are conceivably some systems which have string usage patterns which would
00105 // benefit from cow sharing. Such functionality is best saved for a separate string
00106 // implementation so that the other string uses aren't penalized.
00107 //
00108 // References:
00109 //    This is a good starting HTML reference on the topic:
00110 //       http://www.gotw.ca/publications/optimizations.htm
00111 //    Here is a Usenet discussion on the topic:
00112 //       http://groups-beta.google.com/group/comp.lang.c++.moderated/browse_thread/thread/3dc6af5198d0bf7/886c8642cb06e03d
00113 //
00115 
00116 
00117 #ifndef EASTL_STRING_H
00118 #define EASTL_STRING_H
00119 
00120 
00121 #include <stk_util/util/config_eastl.h>
00122 #if EASTL_ABSTRACT_STRING_ENABLED
00123     #include <EASTL/bonus/string_abstract.h>
00124 #else // 'else' encompasses the entire rest of this file.
00125 #include <stk_util/util/allocator_eastl.h>
00126 #include <stk_util/util/iterator_eastl.h>
00127 #include <stk_util/util/algorithm_eastl.h>
00128 
00129 #ifdef _MSC_VER
00130     #pragma warning(push, 0)
00131 #endif
00132 #include <stddef.h>             // size_t, ptrdiff_t, etc.
00133 #include <stdarg.h>             // vararg functionality.
00134 #include <stdlib.h>             // malloc, free.
00135 #include <stdio.h>              // snprintf, etc.
00136 #include <ctype.h>              // toupper, etc.
00137 #include <wchar.h>              // toupper, etc.
00138 #ifdef __MWERKS__
00139     #include <../Include/string.h> // Force the compiler to use the std lib header.
00140 #else
00141     #include <string.h> // strlen, etc.
00142 #endif
00143 #ifdef _MSC_VER
00144     #pragma warning(pop)
00145 #endif
00146 
00147 #if EASTL_EXCEPTIONS_ENABLED
00148     #ifdef _MSC_VER
00149         #pragma warning(push, 0)
00150     #endif
00151     #include <stdexcept> // std::out_of_range, std::length_error.
00152     #ifdef _MSC_VER
00153         #pragma warning(pop)
00154     #endif
00155 #endif
00156 
00157 #ifdef _MSC_VER
00158     #pragma warning(push)
00159     #pragma warning(disable: 4530)  // C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc
00160     #pragma warning(disable: 4267)  // 'argument' : conversion from 'size_t' to 'const uint32_t', possible loss of data. This is a bogus warning resulting from a bug in VC++.
00161     #pragma warning(disable: 4480)  // nonstandard extension used: specifying underlying type for enum
00162 #endif
00163 
00164 
00166 // EASTL_STRING_EXPLICIT
00167 //
00168 // See EASTL_STRING_OPT_EXPLICIT_CTORS for documentation.
00169 //
00170 #if EASTL_STRING_OPT_EXPLICIT_CTORS
00171     #define EASTL_STRING_EXPLICIT explicit
00172 #else
00173     #define EASTL_STRING_EXPLICIT
00174 #endif
00175 
00176 
00177 
00178 
00180 // EASTL_STRING_INITIAL_CAPACITY
00181 //
00182 // As of this writing, this must be > 0. Note that an initially empty string
00183 // has a capacity of zero (it allocates no memory).
00184 //
00185 const eastl_size_t EASTL_STRING_INITIAL_CAPACITY = 8;
00187 
00188 
00190 // Vsnprintf8 / Vsnprintf16
00191 //
00192 // The user is expected to supply these functions. Note that these functions
00193 // are expected to accept parameters as per the C99 standard. These functions
00194 // can deal with C99 standard return values or Microsoft non-standard return
00195 // values but act more efficiently if implemented via the C99 style.
00196 
00197 extern int Vsnprintf8 (char8_t*  pDestination, size_t n, const char8_t*  pFormat, va_list arguments);
00198 extern int Vsnprintf16(char16_t* pDestination, size_t n, const char16_t* pFormat, va_list arguments);
00199 extern int Vsnprintf32(char32_t* pDestination, size_t n, const char32_t* pFormat, va_list arguments);
00200 
00201 namespace eastl
00202 {
00203     inline int Vsnprintf(char8_t* pDestination, size_t n, const char8_t* pFormat, va_list arguments)
00204         { return Vsnprintf8(pDestination, n, pFormat, arguments); }
00205 
00206     inline int Vsnprintf(char16_t* pDestination, size_t n, const char16_t* pFormat, va_list arguments)
00207         { return Vsnprintf16(pDestination, n, pFormat, arguments); }
00208 
00209     inline int Vsnprintf(char32_t* pDestination, size_t n, const char32_t* pFormat, va_list arguments)
00210         { return Vsnprintf32(pDestination, n, pFormat, arguments); }
00211 }
00213 
00214 
00215 
00216 namespace eastl
00217 {
00218 
00223     #ifndef EASTL_BASIC_STRING_DEFAULT_NAME
00224         #define EASTL_BASIC_STRING_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " basic_string" // Unless the user overrides something, this is "EASTL basic_string".
00225     #endif
00226 
00227 
00230     #ifndef EASTL_BASIC_STRING_DEFAULT_ALLOCATOR
00231         #define EASTL_BASIC_STRING_DEFAULT_ALLOCATOR allocator_type(EASTL_BASIC_STRING_DEFAULT_NAME)
00232     #endif
00233 
00234 
00235 
00240     union EmptyString
00241     {
00242         uint32_t       mUint32;
00243         char           mEmpty8[1];
00244         unsigned char  mEmptyU8[1];
00245         signed char    mEmptyS8[1];
00246         char16_t       mEmpty16[1];
00247         char32_t       mEmpty32[1];
00248     };
00249     extern EASTL_API EmptyString gEmptyString;
00250 
00251     inline const signed char*   GetEmptyString(signed char)   { return gEmptyString.mEmptyS8;  }
00252     inline const unsigned char* GetEmptyString(unsigned char) { return gEmptyString.mEmptyU8;  }
00253     inline const char*          GetEmptyString(char)          { return gEmptyString.mEmpty8;  }
00254     inline const char16_t*      GetEmptyString(char16_t)      { return gEmptyString.mEmpty16; }
00255     inline const char32_t*      GetEmptyString(char32_t)      { return gEmptyString.mEmpty32; }
00256 
00257 
00271     template <typename T, typename Allocator = EASTLAllocatorType>
00272     class basic_string
00273     {
00274     public:
00275         typedef basic_string<T, Allocator>                      this_type;
00276         typedef T                                               value_type;
00277         typedef T*                                              pointer;
00278         typedef const T*                                        const_pointer;
00279         typedef T&                                              reference;
00280         typedef const T&                                        const_reference;
00281         typedef T*                                              iterator;           // Maintainer note: We want to leave iterator defined as T* -- at least in release builds -- as this gives some algorithms an advantage that optimizers cannot get around.
00282         typedef const T*                                        const_iterator;
00283         typedef eastl::reverse_iterator<iterator>               reverse_iterator;
00284         typedef eastl::reverse_iterator<const_iterator>         const_reverse_iterator;
00285         typedef eastl_size_t                                    size_type;          // See config.h for the definition of eastl_size_t, which defaults to uint32_t.
00286         typedef ptrdiff_t                                       difference_type;
00287         typedef Allocator                                       allocator_type;
00288 
00289         #if defined(_MSC_VER) && (_MSC_VER >= 1400) // _MSC_VER of 1400 means VC8 (VS2005), 1500 means VC9 (VS2008)
00290             enum : size_type {                      // Use Microsoft enum language extension, allowing for smaller debug symbols than using a static const. Users have been affected by this.
00291                 npos     = (size_type)-1,
00292                 kMaxSize = (size_type)-2
00293             };
00294         #else
00295             static const size_type npos     = (size_type)-1;      
00296             static const size_type kMaxSize = (size_type)-2;      
00297         #endif
00298 
00299         enum
00300         {
00301             kAlignment       = EASTL_ALIGN_OF(T),
00302             kAlignmentOffset = 0
00303         };
00304 
00305     public:
00306         // CtorDoNotInitialize exists so that we can create a constructor that allocates but doesn't
00307         // initialize and also doesn't collide with any other constructor declaration.
00308         struct CtorDoNotInitialize{};
00309 
00310         // CtorSprintf exists so that we can create a constructor that accepts printf-style
00311         // arguments but also doesn't collide with any other constructor declaration.
00312         struct CtorSprintf{};
00313 
00314     protected:
00315         value_type*       mpBegin;      // Begin of string.
00316         value_type*       mpEnd;        // End of string. *mpEnd is always '0', as we 0-terminate our string. mpEnd is always < mpCapacity.
00317         value_type*       mpCapacity;   // End of allocated space, including the space needed to store the trailing '0' char. mpCapacity is always at least mpEnd + 1.
00318         allocator_type    mAllocator;   // To do: Use base class optimization to make this go away.
00319 
00320     public:
00321         // Constructor, destructor
00322         basic_string();
00323         explicit basic_string(const allocator_type& allocator);
00324         basic_string(const this_type& x, size_type position, size_type n = npos);
00325         basic_string(const value_type* p, size_type n, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
00326         EASTL_STRING_EXPLICIT basic_string(const value_type* p, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
00327         basic_string(size_type n, value_type c, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
00328         basic_string(const this_type& x);
00329         basic_string(const value_type* pBegin, const value_type* pEnd, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
00330         basic_string(CtorDoNotInitialize, size_type n, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
00331         basic_string(CtorSprintf, const value_type* pFormat, ...);
00332 
00333        ~basic_string();
00334 
00335         // Allocator
00336         const allocator_type& get_allocator() const;
00337         allocator_type&       get_allocator();
00338         void                  set_allocator(const allocator_type& allocator);
00339 
00340         // Operator =
00341         this_type& operator=(const this_type& x);
00342         this_type& operator=(const value_type* p);
00343         this_type& operator=(value_type c);
00344 
00345         void          swap(this_type& x);
00346 
00347         // Assignment operations
00348         basic_string& assign(const basic_string& x);
00349         basic_string& assign(const basic_string& x, size_type position, size_type n);
00350         basic_string& assign(const value_type* p, size_type n);
00351         basic_string& assign(const value_type* p);
00352         basic_string& assign(size_type n, value_type c);
00353         basic_string& assign(const value_type* pBegin, const value_type* pEnd);
00354 
00355         // Iterators.
00356         iterator       begin();                 // Expanded in source code as: mpBegin
00357         const_iterator begin() const;           // Expanded in source code as: mpBegin
00358         iterator       end();                   // Expanded in source code as: mpEnd
00359         const_iterator end() const;             // Expanded in source code as: mpEnd
00360 
00361         reverse_iterator       rbegin();
00362         const_reverse_iterator rbegin() const;
00363         reverse_iterator       rend();
00364         const_reverse_iterator rend() const;
00365 
00366         // Size-related functionality
00367         bool      empty() const;                // Expanded in source code as: (mpBegin == mpEnd) or (mpBegin != mpEnd)
00368         size_type size() const;                 // Expanded in source code as: (size_type)(mpEnd - mpBegin)
00369         size_type length() const;               // Expanded in source code as: (size_type)(mpEnd - mpBegin)
00370         size_type max_size() const;             // Expanded in source code as: kMaxSize
00371         size_type capacity() const;             // Expanded in source code as: (size_type)((mpCapacity - mpBegin) - 1)
00372         void      resize(size_type n, value_type c);
00373         void      resize(size_type n);
00374         void      reserve(size_type = 0);
00375         void      set_capacity(size_type n = npos); // Revises the capacity to the user-specified value. Resizes the container to match the capacity if the requested capacity n is less than the current size. If n == npos then the capacity is reallocated (if necessary) such that capacity == size.
00376         void      force_size(size_type n);          // Unilaterally moves the string end position (mpEnd) to the given location. Useful for when the user writes into the string via some extenal means such as C strcpy or sprintf. This allows for more efficient use than using resize to achieve this.
00377 
00378         // Raw access
00379         const value_type* data() const;
00380         const value_type* c_str() const;
00381 
00382         // Element access
00383         reference       operator[](size_type n);
00384         const_reference operator[](size_type n) const;
00385         reference       at(size_type n);
00386         const_reference at(size_type n) const;
00387         reference       front();
00388         const_reference front() const;
00389         reference       back();
00390         const_reference back() const;
00391 
00392         // Append operations
00393         basic_string& operator+=(const basic_string& x);
00394         basic_string& operator+=(const value_type* p);
00395         basic_string& operator+=(value_type c);
00396 
00397         basic_string& append(const basic_string& x);
00398         basic_string& append(const basic_string& x, size_type position, size_type n);
00399         basic_string& append(const value_type* p, size_type n);
00400         basic_string& append(const value_type* p);
00401         basic_string& append(size_type n, value_type c);
00402         basic_string& append(const value_type* pBegin, const value_type* pEnd);
00403 
00404         basic_string& append_sprintf_va_list(const value_type* pFormat, va_list arguments);
00405         basic_string& append_sprintf(const value_type* pFormat, ...);
00406 
00407         void push_back(value_type c);
00408         void pop_back();
00409 
00410         // Insertion operations
00411         basic_string& insert(size_type position, const basic_string& x);
00412         basic_string& insert(size_type position, const basic_string& x, size_type beg, size_type n);
00413         basic_string& insert(size_type position, const value_type* p, size_type n);
00414         basic_string& insert(size_type position, const value_type* p);
00415         basic_string& insert(size_type position, size_type n, value_type c);
00416         iterator      insert(iterator p, value_type c);
00417         void          insert(iterator p, size_type n, value_type c);
00418         void          insert(iterator p, const value_type* pBegin, const value_type* pEnd);
00419 
00420         // Erase operations
00421         basic_string&    erase(size_type position = 0, size_type n = npos);
00422         iterator         erase(iterator p);
00423         iterator         erase(iterator pBegin, iterator pEnd);
00424         reverse_iterator erase(reverse_iterator position);
00425         reverse_iterator erase(reverse_iterator first, reverse_iterator last);
00426         void             clear();
00427         void             reset();                      // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs.
00428 
00429         //Replacement operations
00430         basic_string&  replace(size_type position, size_type n, const basic_string& x);
00431         basic_string&  replace(size_type pos1, size_type n1, const basic_string& x, size_type pos2, size_type n2);
00432         basic_string&  replace(size_type position, size_type n1, const value_type* p, size_type n2);
00433         basic_string&  replace(size_type position, size_type n1, const value_type* p);
00434         basic_string&  replace(size_type position, size_type n1, size_type n2, value_type c);
00435         basic_string&  replace(iterator first, iterator last, const basic_string& x);
00436         basic_string&  replace(iterator first, iterator last, const value_type* p, size_type n);
00437         basic_string&  replace(iterator first, iterator last, const value_type* p);
00438         basic_string&  replace(iterator first, iterator last, size_type n, value_type c);
00439         basic_string&  replace(iterator first, iterator last, const value_type* pBegin, const value_type* pEnd);
00440         size_type      copy(value_type* p, size_type n, size_type position = 0) const;
00441 
00442         // Find operations
00443         size_type find(const basic_string& x, size_type position = 0) const;
00444         size_type find(const value_type* p, size_type position = 0) const;
00445         size_type find(const value_type* p, size_type position, size_type n) const;
00446         size_type find(value_type c, size_type position = 0) const;
00447 
00448         // Reverse find operations
00449         size_type rfind(const basic_string& x, size_type position = npos) const;
00450         size_type rfind(const value_type* p, size_type position = npos) const;
00451         size_type rfind(const value_type* p, size_type position, size_type n) const;
00452         size_type rfind(value_type c, size_type position = npos) const;
00453 
00454         // Find first-of operations
00455         size_type find_first_of(const basic_string& x, size_type position = 0) const;
00456         size_type find_first_of(const value_type* p, size_type position = 0) const;
00457         size_type find_first_of(const value_type* p, size_type position, size_type n) const;
00458         size_type find_first_of(value_type c, size_type position = 0) const;
00459 
00460         // Find last-of operations
00461         size_type find_last_of(const basic_string& x, size_type position = npos) const;
00462         size_type find_last_of(const value_type* p, size_type position = npos) const;
00463         size_type find_last_of(const value_type* p, size_type position, size_type n) const;
00464         size_type find_last_of(value_type c, size_type position = npos) const;
00465 
00466         // Find first not-of operations
00467         size_type find_first_not_of(const basic_string& x, size_type position = 0) const;
00468         size_type find_first_not_of(const value_type* p, size_type position = 0) const;
00469         size_type find_first_not_of(const value_type* p, size_type position, size_type n) const;
00470         size_type find_first_not_of(value_type c, size_type position = 0) const;
00471 
00472         // Find last not-of operations
00473         size_type find_last_not_of(const basic_string& x,  size_type position = npos) const;
00474         size_type find_last_not_of(const value_type* p, size_type position = npos) const;
00475         size_type find_last_not_of(const value_type* p, size_type position, size_type n) const;
00476         size_type find_last_not_of(value_type c, size_type position = npos) const;
00477 
00478         // Substring functionality
00479         basic_string substr(size_type position = 0, size_type n = npos) const;
00480 
00481         // Comparison operations
00482         int        compare(const basic_string& x) const;
00483         int        compare(size_type pos1, size_type n1, const basic_string& x) const;
00484         int        compare(size_type pos1, size_type n1, const basic_string& x, size_type pos2, size_type n2) const;
00485         int        compare(const value_type* p) const;
00486         int        compare(size_type pos1, size_type n1, const value_type* p) const;
00487         int        compare(size_type pos1, size_type n1, const value_type* p, size_type n2) const;
00488         static int compare(const value_type* pBegin1, const value_type* pEnd1, const value_type* pBegin2, const value_type* pEnd2);
00489 
00490         // Case-insensitive comparison functions. Not part of C++ basic_string. Only ASCII-level locale functionality is supported. Thus this is not suitable for localization purposes.
00491         int        comparei(const basic_string& x) const;
00492         int        comparei(const value_type* p) const;
00493         static int comparei(const value_type* pBegin1, const value_type* pEnd1, const value_type* pBegin2, const value_type* pEnd2);
00494 
00495         // Misc functionality, not part of C++ basic_string.
00496         void            make_lower();
00497         void            make_upper();
00498         void            ltrim();
00499         void            rtrim();
00500         void            trim();
00501         basic_string    left(size_type n) const;
00502         basic_string    right(size_type n) const;
00503         basic_string&   sprintf_va_list(const value_type* pFormat, va_list arguments);
00504         basic_string&   sprintf(const value_type* pFormat, ...);
00505 
00506         bool validate() const;
00507         int  validate_iterator(const_iterator i) const;
00508 
00509     protected:
00510         // Helper functions for initialization/insertion operations.
00511         value_type* DoAllocate(size_type n);
00512         void        DoFree(value_type* p, size_type n);
00513         size_type   GetNewCapacity(size_type currentCapacity);
00514 
00515         void        AllocateSelf();
00516         void        AllocateSelf(size_type n);
00517         void        DeallocateSelf();
00518         iterator    InsertInternal(iterator p, value_type c);
00519         void        RangeInitialize(const value_type* pBegin, const value_type* pEnd);
00520         void        RangeInitialize(const value_type* pBegin);
00521         void        SizeInitialize(size_type n, value_type c);
00522         void        ThrowLengthException() const;
00523         void        ThrowRangeException() const;
00524         void        ThrowInvalidArgumentException() const;
00525 
00526         // Replacements for STL template functions.
00527         static const value_type* CharTypeStringFindEnd(const value_type* pBegin, const value_type* pEnd, value_type c);
00528         static const value_type* CharTypeStringRFind(const value_type* pRBegin, const value_type* pREnd, const value_type c);
00529         static const value_type* CharTypeStringSearch(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
00530         static const value_type* CharTypeStringRSearch(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
00531         static const value_type* CharTypeStringFindFirstOf(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
00532         static const value_type* CharTypeStringRFindFirstOf(const value_type* p1RBegin, const value_type* p1REnd, const value_type* p2Begin, const value_type* p2End);
00533         static const value_type* CharTypeStringFindFirstNotOf(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
00534         static const value_type* CharTypeStringRFindFirstNotOf(const value_type* p1RBegin, const value_type* p1REnd, const value_type* p2Begin, const value_type* p2End);
00535 
00536     }; // basic_string
00537 
00538 
00539 
00540 
00542     // 'char traits' functionality
00543     //
00544     inline char8_t CharToLower(char8_t c)
00545         { return (char8_t)tolower((uint8_t)c); }
00546 
00547     inline char16_t CharToLower(char16_t c)
00548         { if((unsigned)c <= 0xff) return (char16_t)tolower((uint8_t)c); return c; }
00549 
00550     inline char32_t CharToLower(char32_t c)
00551         { if((unsigned)c <= 0xff) return (char32_t)tolower((uint8_t)c); return c; }
00552 
00553 
00554 
00555     inline char8_t CharToUpper(char8_t c)
00556         { return (char8_t)toupper((uint8_t)c); }
00557 
00558     inline char16_t CharToUpper(char16_t c)
00559         { if((unsigned)c <= 0xff) return (char16_t)toupper((uint8_t)c); return c; }
00560 
00561     inline char32_t CharToUpper(char32_t c)
00562         { if((unsigned)c <= 0xff) return (char32_t)toupper((uint8_t)c); return c; }
00563 
00564 
00565 
00566     template <typename T>
00567     int Compare(const T* p1, const T* p2, size_t n)
00568     {
00569         for(; n > 0; ++p1, ++p2, --n)
00570         {
00571             if(*p1 != *p2)
00572                 return (*p1 < *p2) ? -1 : 1;
00573         }
00574         return 0;
00575     }
00576 
00577     inline int Compare(const char8_t* p1, const char8_t* p2, size_t n)
00578     {
00579         return memcmp(p1, p2, n);
00580     }
00581 
00582     template <typename T>
00583     inline int CompareI(const T* p1, const T* p2, size_t n)
00584     {
00585         for(; n > 0; ++p1, ++p2, --n)
00586         {
00587             const T c1 = CharToLower(*p1);
00588             const T c2 = CharToLower(*p2);
00589 
00590             if(c1 != c2)
00591                 return (c1 < c2) ? -1 : 1;
00592         }
00593         return 0;
00594     }
00595 
00596 
00597     inline const char8_t* Find(const char8_t* p, char8_t c, size_t n)
00598     {
00599         return (const char8_t*)memchr(p, c, n);
00600     }
00601 
00602     inline const char16_t* Find(const char16_t* p, char16_t c, size_t n)
00603     {
00604         for(; n > 0; --n, ++p)
00605         {
00606             if(*p == c)
00607                 return p;
00608         }
00609 
00610         return NULL;
00611     }
00612 
00613     inline const char32_t* Find(const char32_t* p, char32_t c, size_t n)
00614     {
00615         for(; n > 0; --n, ++p)
00616         {
00617             if(*p == c)
00618                 return p;
00619         }
00620 
00621         return NULL;
00622     }
00623 
00624 
00625     inline size_t CharStrlen(const char8_t* p)
00626     {
00627         #ifdef _MSC_VER // VC++ can implement an instrinsic here.
00628             return strlen(p);
00629         #else
00630             const char8_t* pCurrent = p;
00631             while(*pCurrent)
00632                 ++pCurrent;
00633             return (size_t)(pCurrent - p);
00634         #endif
00635     }
00636 
00637     inline size_t CharStrlen(const char16_t* p)
00638     {
00639         const char16_t* pCurrent = p;
00640         while(*pCurrent)
00641             ++pCurrent;
00642         return (size_t)(pCurrent - p);
00643     }
00644 
00645     inline size_t CharStrlen(const char32_t* p)
00646     {
00647         const char32_t* pCurrent = p;
00648         while(*pCurrent)
00649             ++pCurrent;
00650         return (size_t)(pCurrent - p);
00651     }
00652 
00653 
00654     template <typename T>
00655     inline T* CharStringUninitializedCopy(const T* pSource, const T* pSourceEnd, T* pDestination)
00656     {
00657         memmove(pDestination, pSource, (size_t)(pSourceEnd - pSource) * sizeof(T));
00658         return pDestination + (pSourceEnd - pSource);
00659     }
00660 
00661 
00662 
00663 
00664     inline char8_t* CharStringUninitializedFillN(char8_t* pDestination, size_t n, const char8_t c)
00665     {
00666         if(n) // Some compilers (e.g. GCC 4.3+) generate a warning (which can't be disabled) if you call memset with a size of 0.
00667             memset(pDestination, (uint8_t)c, (size_t)n);
00668         return pDestination + n;
00669     }
00670 
00671     inline char16_t* CharStringUninitializedFillN(char16_t* pDestination, size_t n, const char16_t c)
00672     {
00673         char16_t* pDest16          = pDestination;
00674         const char16_t* const pEnd = pDestination + n;
00675         while(pDest16 < pEnd)
00676             *pDest16++ = c;
00677         return pDestination + n;
00678     }
00679 
00680     inline char32_t* CharStringUninitializedFillN(char32_t* pDestination, size_t n, const char32_t c)
00681     {
00682         char32_t* pDest32          = pDestination;
00683         const char32_t* const pEnd = pDestination + n;
00684         while(pDest32 < pEnd)
00685             *pDest32++ = c;
00686         return pDestination + n;
00687     }
00688 
00689 
00690 
00691     inline char8_t* CharTypeAssignN(char8_t* pDestination, size_t n, char8_t c)
00692     {
00693         if(n) // Some compilers (e.g. GCC 4.3+) generate a warning (which can't be disabled) if you call memset with a size of 0.
00694             return (char8_t*)memset(pDestination, c, (size_t)n);
00695         return pDestination;
00696     }
00697 
00698     inline char16_t* CharTypeAssignN(char16_t* pDestination, size_t n, char16_t c)
00699     {
00700         char16_t* pDest16          = pDestination;
00701         const char16_t* const pEnd = pDestination + n;
00702         while(pDest16 < pEnd)
00703             *pDest16++ = c;
00704         return pDestination;
00705     }
00706 
00707     inline char32_t* CharTypeAssignN(char32_t* pDestination, size_t n, char32_t c)
00708     {
00709         char32_t* pDest32          = pDestination;
00710         const char32_t* const pEnd = pDestination + n;
00711         while(pDest32 < pEnd)
00712             *pDest32++ = c;
00713         return pDestination;
00714     }
00715 
00716 
00717 
00719     // basic_string
00721 
00722     template <typename T, typename Allocator>
00723     inline basic_string<T, Allocator>::basic_string()
00724         : mpBegin(NULL),
00725           mpEnd(NULL),
00726           mpCapacity(NULL),
00727           mAllocator(EASTL_BASIC_STRING_DEFAULT_NAME)
00728     {
00729         AllocateSelf();
00730     }
00731 
00732 
00733     template <typename T, typename Allocator>
00734     inline basic_string<T, Allocator>::basic_string(const allocator_type& allocator)
00735         : mpBegin(NULL),
00736           mpEnd(NULL),
00737           mpCapacity(NULL),
00738           mAllocator(allocator)
00739     {
00740         AllocateSelf();
00741     }
00742 
00743 
00744     template <typename T, typename Allocator>
00745     inline basic_string<T, Allocator>::basic_string(const this_type& x)
00746         : mpBegin(NULL),
00747           mpEnd(NULL),
00748           mpCapacity(NULL),
00749           mAllocator(x.mAllocator)
00750     {
00751         RangeInitialize(x.mpBegin, x.mpEnd);
00752     }
00753 
00754 
00755     template <typename T, typename Allocator>
00756     basic_string<T, Allocator>::basic_string(const this_type& x, size_type position, size_type n)
00757         : mpBegin(NULL),
00758           mpEnd(NULL),
00759           mpCapacity(NULL),
00760           mAllocator(x.mAllocator)
00761     {
00762         #if EASTL_STRING_OPT_RANGE_ERRORS
00763             if(EASTL_UNLIKELY(position > (size_type)(x.mpEnd - x.mpBegin)))
00764             {
00765                 ThrowRangeException();
00766                 AllocateSelf();
00767             }
00768             else
00769                 RangeInitialize(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
00770         #else
00771             RangeInitialize(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
00772         #endif
00773     }
00774 
00775 
00776     template <typename T, typename Allocator>
00777     inline basic_string<T, Allocator>::basic_string(const value_type* p, size_type n, const allocator_type& allocator)
00778         : mpBegin(NULL),
00779           mpEnd(NULL),
00780           mpCapacity(NULL),
00781           mAllocator(allocator)
00782     {
00783         RangeInitialize(p, p + n);
00784     }
00785 
00786 
00787     template <typename T, typename Allocator>
00788     inline basic_string<T, Allocator>::basic_string(const value_type* p, const allocator_type& allocator)
00789         : mpBegin(NULL),
00790           mpEnd(NULL),
00791           mpCapacity(NULL),
00792           mAllocator(allocator)
00793     {
00794         RangeInitialize(p);
00795     }
00796 
00797 
00798     template <typename T, typename Allocator>
00799     inline basic_string<T, Allocator>::basic_string(size_type n, value_type c, const allocator_type& allocator)
00800         : mpBegin(NULL),
00801           mpEnd(NULL),
00802           mpCapacity(NULL),
00803           mAllocator(allocator)
00804     {
00805         SizeInitialize(n, c);
00806     }
00807 
00808 
00809     template <typename T, typename Allocator>
00810     inline basic_string<T, Allocator>::basic_string(const value_type* pBegin, const value_type* pEnd, const allocator_type& allocator)
00811         : mpBegin(NULL),
00812           mpEnd(NULL),
00813           mpCapacity(NULL),
00814           mAllocator(allocator)
00815     {
00816         RangeInitialize(pBegin, pEnd);
00817     }
00818 
00819 
00820     // CtorDoNotInitialize exists so that we can create a version that allocates but doesn't
00821     // initialize but also doesn't collide with any other constructor declaration.
00822     template <typename T, typename Allocator>
00823     basic_string<T, Allocator>::basic_string(CtorDoNotInitialize /*unused*/, size_type n, const allocator_type& allocator)
00824         : mpBegin(NULL),
00825           mpEnd(NULL),
00826           mpCapacity(NULL),
00827           mAllocator(allocator)
00828     {
00829         // Note that we do not call SizeInitialize here.
00830         AllocateSelf(n + 1); // '+1' so that we have room for the terminating 0.
00831         *mpEnd = 0;
00832     }
00833 
00834 
00835     // CtorSprintf exists so that we can create a version that does a variable argument
00836     // sprintf but also doesn't collide with any other constructor declaration.
00837     template <typename T, typename Allocator>
00838     basic_string<T, Allocator>::basic_string(CtorSprintf /*unused*/, const value_type* pFormat, ...)
00839         : mpBegin(NULL),
00840           mpEnd(NULL),
00841           mpCapacity(NULL),
00842           mAllocator()
00843     {
00844         const size_type n = (size_type)CharStrlen(pFormat) + 1; // We'll need at least this much. '+1' so that we have room for the terminating 0.
00845         AllocateSelf(n);
00846 
00847         va_list arguments;
00848         va_start(arguments, pFormat);
00849         append_sprintf_va_list(pFormat, arguments);
00850         va_end(arguments);
00851     }
00852 
00853 
00854     template <typename T, typename Allocator>
00855     inline basic_string<T, Allocator>::~basic_string()
00856     {
00857         DeallocateSelf();
00858     }
00859 
00860 
00861     template <typename T, typename Allocator>
00862     inline const typename basic_string<T, Allocator>::allocator_type&
00863     basic_string<T, Allocator>::get_allocator() const
00864     {
00865         return mAllocator;
00866     }
00867 
00868 
00869     template <typename T, typename Allocator>
00870     inline typename basic_string<T, Allocator>::allocator_type&
00871     basic_string<T, Allocator>::get_allocator()
00872     {
00873         return mAllocator;
00874     }
00875 
00876 
00877     template <typename T, typename Allocator>
00878     inline void basic_string<T, Allocator>::set_allocator(const allocator_type& allocator)
00879     {
00880         mAllocator = allocator;
00881     }
00882 
00883 
00884     template <typename T, typename Allocator>
00885     inline const typename basic_string<T, Allocator>::value_type*
00886     basic_string<T, Allocator>::data()  const
00887     {
00888         return mpBegin;
00889     }
00890 
00891 
00892     template <typename T, typename Allocator>
00893     inline const typename basic_string<T, Allocator>::value_type*
00894     basic_string<T, Allocator>::c_str() const
00895     {
00896         return mpBegin;
00897     }
00898 
00899 
00900     template <typename T, typename Allocator>
00901     inline typename basic_string<T, Allocator>::iterator
00902     basic_string<T, Allocator>::begin()
00903     {
00904         return mpBegin;
00905     }
00906 
00907 
00908     template <typename T, typename Allocator>
00909     inline typename basic_string<T, Allocator>::iterator
00910     basic_string<T, Allocator>::end()
00911     {
00912         return mpEnd;
00913     }
00914 
00915 
00916     template <typename T, typename Allocator>
00917     inline typename basic_string<T, Allocator>::const_iterator
00918     basic_string<T, Allocator>::begin() const
00919     {
00920         return mpBegin;
00921     }
00922 
00923 
00924     template <typename T, typename Allocator>
00925     inline typename basic_string<T, Allocator>::const_iterator
00926     basic_string<T, Allocator>::end() const
00927     {
00928         return mpEnd;
00929     }
00930 
00931 
00932     template <typename T, typename Allocator>
00933     inline typename basic_string<T, Allocator>::reverse_iterator
00934     basic_string<T, Allocator>::rbegin()
00935     {
00936         return reverse_iterator(mpEnd);
00937     }
00938 
00939 
00940     template <typename T, typename Allocator>
00941     inline typename basic_string<T, Allocator>::reverse_iterator
00942     basic_string<T, Allocator>::rend()
00943     {
00944         return reverse_iterator(mpBegin);
00945     }
00946 
00947 
00948     template <typename T, typename Allocator>
00949     inline typename basic_string<T, Allocator>::const_reverse_iterator
00950     basic_string<T, Allocator>::rbegin() const
00951     {
00952         return const_reverse_iterator(mpEnd);
00953     }
00954 
00955 
00956     template <typename T, typename Allocator>
00957     inline typename basic_string<T, Allocator>::const_reverse_iterator
00958     basic_string<T, Allocator>::rend() const
00959     {
00960         return const_reverse_iterator(mpBegin);
00961     }
00962 
00963 
00964     template <typename T, typename Allocator>
00965     inline bool basic_string<T, Allocator>::empty() const
00966     {
00967         return (mpBegin == mpEnd);
00968     }
00969 
00970 
00971     template <typename T, typename Allocator>
00972     inline typename basic_string<T, Allocator>::size_type
00973     basic_string<T, Allocator>::size() const
00974     {
00975         return (size_type)(mpEnd - mpBegin);
00976     }
00977 
00978 
00979     template <typename T, typename Allocator>
00980     inline typename basic_string<T, Allocator>::size_type
00981     basic_string<T, Allocator>::length() const
00982     {
00983         return (size_type)(mpEnd - mpBegin);
00984     }
00985 
00986 
00987     template <typename T, typename Allocator>
00988     inline typename basic_string<T, Allocator>::size_type
00989     basic_string<T, Allocator>::max_size() const
00990     {
00991         return kMaxSize;
00992     }
00993 
00994 
00995     template <typename T, typename Allocator>
00996     inline typename basic_string<T, Allocator>::size_type
00997     basic_string<T, Allocator>::capacity() const
00998     {
00999         return (size_type)((mpCapacity - mpBegin) - 1); // '-1' because we pretend that we didn't allocate memory for the terminating 0.
01000     }
01001 
01002 
01003     template <typename T, typename Allocator>
01004     inline typename basic_string<T, Allocator>::const_reference
01005     basic_string<T, Allocator>::operator[](size_type n) const
01006     {
01007         #if EASTL_ASSERT_ENABLED // We allow the user to reference the trailing 0 char without asserting. Perhaps we shouldn't.
01008             if(EASTL_UNLIKELY(n > (static_cast<size_type>(mpEnd - mpBegin))))
01009                 EASTL_FAIL_MSG("basic_string::operator[] -- out of range");
01010         #endif
01011 
01012         return mpBegin[n]; // Sometimes done as *(mpBegin + n)
01013     }
01014 
01015 
01016     template <typename T, typename Allocator>
01017     inline typename basic_string<T, Allocator>::reference
01018     basic_string<T, Allocator>::operator[](size_type n)
01019     {
01020         #if EASTL_ASSERT_ENABLED // We allow the user to reference the trailing 0 char without asserting. Perhaps we shouldn't.
01021             if(EASTL_UNLIKELY(n > (static_cast<size_type>(mpEnd - mpBegin))))
01022                 EASTL_FAIL_MSG("basic_string::operator[] -- out of range");
01023         #endif
01024 
01025         return mpBegin[n]; // Sometimes done as *(mpBegin + n)
01026     }
01027 
01028 
01029     template <typename T, typename Allocator>
01030     inline typename basic_string<T, Allocator>::this_type& basic_string<T, Allocator>::operator=(const basic_string<T, Allocator>& x)
01031     {
01032         if(&x != this)
01033         {
01034             #if EASTL_ALLOCATOR_COPY_ENABLED
01035                 mAllocator = x.mAllocator;
01036             #endif
01037 
01038             assign(x.mpBegin, x.mpEnd);
01039         }
01040         return *this;
01041     }
01042 
01043 
01044     template <typename T, typename Allocator>
01045     inline typename basic_string<T, Allocator>::this_type& basic_string<T, Allocator>::operator=(const value_type* p)
01046     {
01047         return assign(p, p + CharStrlen(p));
01048     }
01049 
01050 
01051     template <typename T, typename Allocator>
01052     inline typename basic_string<T, Allocator>::this_type& basic_string<T, Allocator>::operator=(value_type c)
01053     {
01054         return assign((size_type)1, c);
01055     }
01056 
01057 
01058     template <typename T, typename Allocator>
01059     void basic_string<T, Allocator>::resize(size_type n, value_type c)
01060     {
01061         const size_type s = (size_type)(mpEnd - mpBegin);
01062 
01063         if(n < s)
01064             erase(mpBegin + n, mpEnd);
01065         else if(n > s)
01066             append(n - s, c);
01067     }
01068 
01069 
01070     template <typename T, typename Allocator>
01071     void basic_string<T, Allocator>::resize(size_type n)
01072     {
01073         // C++ basic_string specifies that resize(n) is equivalent to resize(n, value_type()).
01074         // For built-in types, value_type() is the same as zero (value_type(0)).
01075         // We can improve the efficiency (especially for long strings) of this
01076         // string class by resizing without assigning to anything.
01077 
01078         const size_type s = (size_type)(mpEnd - mpBegin);
01079 
01080         if(n < s)
01081             erase(mpBegin + n, mpEnd);
01082         else if(n > s)
01083         {
01084             #if EASTL_STRING_OPT_CHAR_INIT
01085                 append(n - s, value_type());
01086             #else
01087                 append(n - s);
01088             #endif
01089         }
01090     }
01091 
01092 
01093     template <typename T, typename Allocator>
01094     void basic_string<T, Allocator>::reserve(size_type n)
01095     {
01096         #if EASTL_STRING_OPT_LENGTH_ERRORS
01097             if(EASTL_UNLIKELY(n > kMaxSize))
01098                 ThrowLengthException();
01099         #endif
01100 
01101         // The C++ standard for basic_string doesn't specify if we should or shouldn't
01102         // downsize the container. The standard is overly vague in its description of reserve:
01103         //    The member function reserve() is a directive that informs a
01104         //    basic_string object of a planned change in size, so that it
01105         //    can manage the storage allocation accordingly.
01106         // We will act like the vector container and preserve the contents of
01107         // the container and only reallocate if increasing the size. The user
01108         // can use the set_capacity function to reduce the capacity.
01109 
01110         n = eastl::max_alt(n, (size_type)(mpEnd - mpBegin)); // Calculate the new capacity, which needs to be >= container size.
01111 
01112         if(n >= (size_type)(mpCapacity - mpBegin))  // If there is something to do... // We use >= because mpCapacity accounts for the trailing zero.
01113             set_capacity(n);
01114     }
01115 
01116 
01117     template <typename T, typename Allocator>
01118     inline void basic_string<T, Allocator>::set_capacity(size_type n)
01119     {
01120         if(n == npos) // If the user wants to set the capacity to equal the current size... // '-1' because we pretend that we didn't allocate memory for the terminating 0.
01121             n = (size_type)(mpEnd - mpBegin);
01122         else if(n < (size_type)(mpEnd - mpBegin))
01123             mpEnd = mpBegin + n;
01124 
01125         if(n != (size_type)((mpCapacity - mpBegin) - 1)) // If there is any capacity change...
01126         {
01127             if(n)
01128             {
01129                 pointer pNewBegin = DoAllocate(n + 1); // We need the + 1 to accomodate the trailing 0.
01130                 pointer pNewEnd   = pNewBegin;
01131 
01132                 pNewEnd = CharStringUninitializedCopy(mpBegin, mpEnd, pNewBegin);
01133                *pNewEnd = 0;
01134 
01135                 DeallocateSelf();
01136                 mpBegin    = pNewBegin;
01137                 mpEnd      = pNewEnd;
01138                 mpCapacity = pNewBegin + (n + 1);
01139             }
01140             else
01141             {
01142                 DeallocateSelf();
01143                 AllocateSelf();
01144             }
01145         }
01146     }
01147 
01148 
01149     template <typename T, typename Allocator>
01150     inline void basic_string<T, Allocator>::force_size(size_type n)
01151     {
01152         #if EASTL_STRING_OPT_RANGE_ERRORS
01153             if(EASTL_UNLIKELY(n >= (size_type)(mpCapacity - mpBegin)))
01154                 ThrowRangeException();
01155         #elif EASTL_ASSERT_ENABLED
01156             if(EASTL_UNLIKELY(n >= (size_type)(mpCapacity - mpBegin)))
01157                 EASTL_FAIL_MSG("basic_string::force_size -- out of range");
01158         #endif
01159 
01160         mpEnd = mpBegin + n;
01161     }
01162 
01163 
01164     template <typename T, typename Allocator>
01165     inline void basic_string<T, Allocator>::clear()
01166     {
01167         if(mpBegin != mpEnd)
01168         {
01169            *mpBegin = value_type(0);
01170             mpEnd   = mpBegin;
01171         }
01172     }
01173 
01174 
01175     template <typename T, typename Allocator>
01176     inline void basic_string<T, Allocator>::reset()
01177     {
01178         // The reset function is a special extension function which unilaterally
01179         // resets the container to an empty state without freeing the memory of
01180         // the contained objects. This is useful for very quickly tearing down a
01181         // container built into scratch memory.
01182         AllocateSelf();
01183     }
01184 
01185 
01186     template <typename T, typename Allocator>
01187     inline typename basic_string<T, Allocator>::const_reference
01188     basic_string<T, Allocator>::at(size_type n) const
01189     {
01190         #if EASTL_STRING_OPT_RANGE_ERRORS
01191             if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
01192                 ThrowRangeException();
01193         #elif EASTL_ASSERT_ENABLED                  // We assert if the user references the trailing 0 char.
01194             if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
01195                 EASTL_FAIL_MSG("basic_string::at -- out of range");
01196         #endif
01197 
01198         return mpBegin[n];
01199     }
01200 
01201 
01202     template <typename T, typename Allocator>
01203     inline typename basic_string<T, Allocator>::reference
01204     basic_string<T, Allocator>::at(size_type n)
01205     {
01206         #if EASTL_STRING_OPT_RANGE_ERRORS
01207             if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
01208                 ThrowRangeException();
01209         #elif EASTL_ASSERT_ENABLED                  // We assert if the user references the trailing 0 char.
01210             if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
01211                 EASTL_FAIL_MSG("basic_string::at -- out of range");
01212         #endif
01213 
01214         return mpBegin[n];
01215     }
01216 
01217 
01218     template <typename T, typename Allocator>
01219     inline typename basic_string<T, Allocator>::reference
01220     basic_string<T, Allocator>::front()
01221     {
01222         #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
01223             // We allow the user to reference the trailing 0 char without asserting.
01224         #elif EASTL_ASSERT_ENABLED
01225             if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
01226                 EASTL_FAIL_MSG("basic_string::front -- empty string");
01227         #endif
01228 
01229         return *mpBegin;
01230     }
01231 
01232 
01233     template <typename T, typename Allocator>
01234     inline typename basic_string<T, Allocator>::const_reference
01235     basic_string<T, Allocator>::front() const
01236     {
01237         #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
01238             // We allow the user to reference the trailing 0 char without asserting.
01239         #elif EASTL_ASSERT_ENABLED
01240             if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
01241                 EASTL_FAIL_MSG("basic_string::front -- empty string");
01242         #endif
01243 
01244         return *mpBegin;
01245     }
01246 
01247 
01248     template <typename T, typename Allocator>
01249     inline typename basic_string<T, Allocator>::reference
01250     basic_string<T, Allocator>::back()
01251     {
01252         #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
01253             // We allow the user to reference the trailing 0 char without asserting.
01254         #elif EASTL_ASSERT_ENABLED
01255             if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
01256                 EASTL_FAIL_MSG("basic_string::back -- empty string");
01257         #endif
01258 
01259         return *(mpEnd - 1);
01260     }
01261 
01262 
01263     template <typename T, typename Allocator>
01264     inline typename basic_string<T, Allocator>::const_reference
01265     basic_string<T, Allocator>::back() const
01266     {
01267         #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
01268             // We allow the user to reference the trailing 0 char without asserting.
01269         #elif EASTL_ASSERT_ENABLED
01270             if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
01271                 EASTL_FAIL_MSG("basic_string::back -- empty string");
01272         #endif
01273 
01274         return *(mpEnd - 1);
01275     }
01276 
01277 
01278     template <typename T, typename Allocator>
01279     inline basic_string<T, Allocator>& basic_string<T, Allocator>::operator+=(const basic_string<T, Allocator>& x)
01280     {
01281         return append(x);
01282     }
01283 
01284 
01285     template <typename T, typename Allocator>
01286     inline basic_string<T, Allocator>& basic_string<T, Allocator>::operator+=(const value_type* p)
01287     {
01288         return append(p);
01289     }
01290 
01291 
01292     template <typename T, typename Allocator>
01293     inline basic_string<T, Allocator>& basic_string<T, Allocator>::operator+=(value_type c)
01294     {
01295         push_back(c);
01296         return *this;
01297     }
01298 
01299 
01300     template <typename T, typename Allocator>
01301     inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const basic_string<T, Allocator>& x)
01302     {
01303         return append(x.mpBegin, x.mpEnd);
01304     }
01305 
01306 
01307     template <typename T, typename Allocator>
01308     inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const basic_string<T, Allocator>& x, size_type position, size_type n)
01309     {
01310         #if EASTL_STRING_OPT_RANGE_ERRORS
01311             if(EASTL_UNLIKELY(position > (size_type)(x.mpEnd - x.mpBegin)))
01312                 ThrowRangeException();
01313         #endif
01314 
01315         return append(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
01316     }
01317 
01318 
01319     template <typename T, typename Allocator>
01320     inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const value_type* p, size_type n)
01321     {
01322         return append(p, p + n);
01323     }
01324 
01325 
01326     template <typename T, typename Allocator>
01327     inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const value_type* p)
01328     {
01329         return append(p, p + CharStrlen(p));
01330     }
01331 
01332 
01333     template <typename T, typename Allocator>
01334     basic_string<T, Allocator>& basic_string<T, Allocator>::append(size_type n, value_type c)
01335     {
01336         const size_type s = (size_type)(mpEnd - mpBegin);
01337 
01338         #if EASTL_STRING_OPT_LENGTH_ERRORS
01339             if(EASTL_UNLIKELY((n > kMaxSize) || (s > (kMaxSize - n))))
01340                 ThrowLengthException();
01341         #endif
01342 
01343         const size_type nCapacity = (size_type)((mpCapacity - mpBegin) - 1);
01344 
01345         if((s + n) > nCapacity)
01346             reserve(eastl::max_alt((size_type)GetNewCapacity(nCapacity), (size_type)(s + n)));
01347 
01348         if(n > 0)
01349         {
01350             CharStringUninitializedFillN(mpEnd + 1, n - 1, c);
01351            *mpEnd  = c;
01352             mpEnd += n;
01353            *mpEnd  = 0;
01354         }
01355 
01356         return *this;
01357     }
01358 
01359 
01360     template <typename T, typename Allocator>
01361     basic_string<T, Allocator>& basic_string<T, Allocator>::append(const value_type* pBegin, const value_type* pEnd)
01362     {
01363         if(pBegin != pEnd)
01364         {
01365             const size_type nOldSize = (size_type)(mpEnd - mpBegin);
01366             const size_type n        = (size_type)(pEnd - pBegin);
01367 
01368             #if EASTL_STRING_OPT_LENGTH_ERRORS
01369                 if(EASTL_UNLIKELY(((size_t)n > kMaxSize) || (nOldSize > (kMaxSize - n))))
01370                     ThrowLengthException();
01371             #endif
01372 
01373             const size_type nCapacity = (size_type)((mpCapacity - mpBegin) - 1);
01374 
01375             if((nOldSize + n) > nCapacity)
01376             {
01377                 const size_type nLength = eastl::max_alt((size_type)GetNewCapacity(nCapacity), (size_type)(nOldSize + n)) + 1; // + 1 to accomodate the trailing 0.
01378 
01379                 pointer pNewBegin = DoAllocate(nLength);
01380                 pointer pNewEnd   = pNewBegin;
01381 
01382                 pNewEnd = CharStringUninitializedCopy(mpBegin, mpEnd, pNewBegin);
01383                 pNewEnd = CharStringUninitializedCopy(pBegin,  pEnd,  pNewEnd);
01384                *pNewEnd = 0;
01385 
01386                 DeallocateSelf();
01387                 mpBegin    = pNewBegin;
01388                 mpEnd      = pNewEnd;
01389                 mpCapacity = pNewBegin + nLength;
01390             }
01391             else
01392             {
01393                 const value_type* pTemp = pBegin;
01394                 ++pTemp;
01395                 CharStringUninitializedCopy(pTemp, pEnd, mpEnd + 1);
01396                 mpEnd[n] = 0;
01397                *mpEnd    = *pBegin;
01398                 mpEnd   += n;
01399             }
01400         }
01401 
01402         return *this;
01403     }
01404 
01405 
01406     template <typename T, typename Allocator>
01407     basic_string<T, Allocator>& basic_string<T, Allocator>::append_sprintf_va_list(const value_type* pFormat, va_list arguments)
01408     {
01409         // From unofficial C89 extension documentation:
01410         // The vsnprintf returns the number of characters written into the array,
01411         // not counting the terminating null character, or a negative value
01412         // if count or more characters are requested to be generated.
01413         // An error can occur while converting a value for output.
01414 
01415         // From the C99 standard:
01416         // The vsnprintf function returns the number of characters that would have
01417         // been written had n been sufficiently large, not counting the terminating
01418         // null character, or a negative value if an encoding error occurred.
01419         // Thus, the null-terminated output has been completely written if and only
01420         // if the returned value is nonnegative and less than n.
01421         size_type nInitialSize = (size_type)(mpEnd - mpBegin);
01422         int       nReturnValue;
01423 
01424         #if EASTL_VA_COPY_ENABLED
01425             va_list argumentsSaved;
01426             va_copy(argumentsSaved, arguments);
01427         #endif
01428 
01429         if(mpBegin == GetEmptyString(value_type())) // We need to do this because non-standard vsnprintf implementations will otherwise overwrite gEmptyString with a non-zero char.
01430             nReturnValue = eastl::Vsnprintf(mpEnd, 0, pFormat, arguments);
01431         else
01432             nReturnValue = eastl::Vsnprintf(mpEnd, (size_t)(mpCapacity - mpEnd), pFormat, arguments);
01433 
01434         if(nReturnValue >= (int)(mpCapacity - mpEnd))  // If there wasn't enough capacity...
01435         {
01436             // In this case we definitely have C99 Vsnprintf behaviour.
01437             #if EASTL_VA_COPY_ENABLED
01438                 va_copy(arguments, argumentsSaved);
01439             #endif
01440             resize(nInitialSize + nReturnValue);
01441             nReturnValue = eastl::Vsnprintf(mpBegin + nInitialSize, (size_t)(nReturnValue + 1), pFormat, arguments); // '+1' because vsnprintf wants to know the size of the buffer including the terminating zero.
01442         }
01443         else if(nReturnValue < 0) // If vsnprintf is non-C99-standard (e.g. it is VC++ _vsnprintf)...
01444         {
01445             // In this case we either have C89 extension behaviour or C99 behaviour.
01446             size_type n = eastl::max_alt((size_type)(EASTL_STRING_INITIAL_CAPACITY - 1), (size_type)(size() * 2)); // '-1' because the resize call below will add one for NULL terminator and we want to keep allocations on fixed block sizes.
01447 
01448             for(; (nReturnValue < 0) && (n < 1000000); n *= 2)
01449             {
01450                 #if EASTL_VA_COPY_ENABLED
01451                     va_copy(arguments, argumentsSaved);
01452                 #endif
01453                 resize(n);
01454 
01455                 const size_t nCapacity = (size_t)((n + 1) - nInitialSize);
01456                 nReturnValue = eastl::Vsnprintf(mpBegin + nInitialSize, nCapacity, pFormat, arguments); // '+1' because vsnprintf wants to know the size of the buffer including the terminating zero.
01457 
01458                 if(nReturnValue == (int)(unsigned)nCapacity)
01459                 {
01460                     resize(++n);
01461                     nReturnValue = eastl::Vsnprintf(mpBegin + nInitialSize, nCapacity + 1, pFormat, arguments);
01462                 }
01463             }
01464         }
01465 
01466         if(nReturnValue >= 0)
01467             mpEnd = mpBegin + nInitialSize + nReturnValue; // We are guaranteed from the above logic that mpEnd <= mpCapacity.
01468 
01469         return *this;
01470     }
01471 
01472     template <typename T, typename Allocator>
01473     basic_string<T, Allocator>& basic_string<T, Allocator>::append_sprintf(const value_type* pFormat, ...)
01474     {
01475         va_list arguments;
01476         va_start(arguments, pFormat);
01477         append_sprintf_va_list(pFormat, arguments);
01478         va_end(arguments);
01479 
01480         return *this;
01481     }
01482 
01483 
01484     template <typename T, typename Allocator>
01485     inline void basic_string<T, Allocator>::push_back(value_type c)
01486     {
01487         if((mpEnd + 1) == mpCapacity) // If we are out of space... (note that we test for + 1 because we have a trailing 0)
01488             reserve(eastl::max_alt(GetNewCapacity((size_type)((mpCapacity - mpBegin) - 1)), (size_type)(mpEnd - mpBegin) + 1));
01489         *mpEnd++ = c;
01490         *mpEnd   = 0;
01491     }
01492 
01493 
01494     template <typename T, typename Allocator>
01495     inline void basic_string<T, Allocator>::pop_back()
01496     {
01497         #if EASTL_ASSERT_ENABLED
01498             if(EASTL_UNLIKELY(mpEnd <= mpBegin))
01499                 EASTL_FAIL_MSG("basic_string::pop_back -- empty string");
01500         #endif
01501 
01502         mpEnd[-1] = value_type(0);
01503         --mpEnd;
01504     }
01505 
01506 
01507     template <typename T, typename Allocator>
01508     inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const basic_string<T, Allocator>& x)
01509     {
01510         return assign(x.mpBegin, x.mpEnd);
01511     }
01512 
01513 
01514     template <typename T, typename Allocator>
01515     inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const basic_string<T, Allocator>& x, size_type position, size_type n)
01516     {
01517         #if EASTL_STRING_OPT_RANGE_ERRORS
01518             if(EASTL_UNLIKELY(position > (size_type)(x.mpEnd - x.mpBegin)))
01519                 ThrowRangeException();
01520         #endif
01521 
01522         return assign(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
01523     }
01524 
01525 
01526     template <typename T, typename Allocator>
01527     inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const value_type* p, size_type n)
01528     {
01529         return assign(p, p + n);
01530     }
01531 
01532 
01533     template <typename T, typename Allocator>
01534     inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const value_type* p)
01535     {
01536         return assign(p, p + CharStrlen(p));
01537     }
01538 
01539 
01540     template <typename T, typename Allocator>
01541     basic_string<T, Allocator>& basic_string<T, Allocator>::assign(size_type n, value_type c)
01542     {
01543         if(n <= (size_type)(mpEnd - mpBegin))
01544         {
01545             CharTypeAssignN(mpBegin, n, c);
01546             erase(mpBegin + n, mpEnd);
01547         }
01548         else
01549         {
01550             CharTypeAssignN(mpBegin, (size_type)(mpEnd - mpBegin), c);
01551             append(n - (size_type)(mpEnd - mpBegin), c);
01552         }
01553         return *this;
01554     }
01555 
01556 
01557     template <typename T, typename Allocator>
01558     basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const value_type* pBegin, const value_type* pEnd)
01559     {
01560         const ptrdiff_t n = pEnd - pBegin;
01561         if(static_cast<size_type>(n) <= (size_type)(mpEnd - mpBegin))
01562         {
01563             memmove(mpBegin, pBegin, (size_t)n * sizeof(value_type));
01564             erase(mpBegin + n, mpEnd);
01565         }
01566         else
01567         {
01568             memmove(mpBegin, pBegin, (size_t)(mpEnd - mpBegin) * sizeof(value_type));
01569             append(pBegin + (size_type)(mpEnd - mpBegin), pEnd);
01570         }
01571         return *this;
01572     }
01573 
01574 
01575     template <typename T, typename Allocator>
01576     basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const basic_string<T, Allocator>& x)
01577     {
01578         #if EASTL_STRING_OPT_RANGE_ERRORS
01579             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01580                 ThrowRangeException();
01581         #endif
01582 
01583         #if EASTL_STRING_OPT_LENGTH_ERRORS
01584             if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - (size_type)(x.mpEnd - x.mpBegin))))
01585                 ThrowLengthException();
01586         #endif
01587 
01588         insert(mpBegin + position, x.mpBegin, x.mpEnd);
01589         return *this;
01590     }
01591 
01592 
01593     template <typename T, typename Allocator>
01594     basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const basic_string<T, Allocator>& x, size_type beg, size_type n)
01595     {
01596         #if EASTL_STRING_OPT_RANGE_ERRORS
01597             if(EASTL_UNLIKELY((position > (size_type)(mpEnd - mpBegin)) || (beg > (size_type)(x.mpEnd - x.mpBegin))))
01598                 ThrowRangeException();
01599         #endif
01600 
01601         size_type nLength = eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - beg);
01602 
01603         #if EASTL_STRING_OPT_LENGTH_ERRORS
01604             if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - nLength)))
01605                 ThrowLengthException();
01606         #endif
01607 
01608         insert(mpBegin + position, x.mpBegin + beg, x.mpBegin + beg + nLength);
01609         return *this;
01610     }
01611 
01612 
01613     template <typename T, typename Allocator>
01614     basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const value_type* p, size_type n)
01615     {
01616         #if EASTL_STRING_OPT_RANGE_ERRORS
01617             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01618                 ThrowRangeException();
01619         #endif
01620 
01621         #if EASTL_STRING_OPT_LENGTH_ERRORS
01622             if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - n)))
01623                 ThrowLengthException();
01624         #endif
01625 
01626         insert(mpBegin + position, p, p + n);
01627         return *this;
01628     }
01629 
01630 
01631     template <typename T, typename Allocator>
01632     basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const value_type* p)
01633     {
01634         #if EASTL_STRING_OPT_RANGE_ERRORS
01635             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01636                 ThrowRangeException();
01637         #endif
01638 
01639         size_type nLength = (size_type)CharStrlen(p);
01640 
01641         #if EASTL_STRING_OPT_LENGTH_ERRORS
01642             if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - nLength)))
01643                 ThrowLengthException();
01644         #endif
01645 
01646         insert(mpBegin + position, p, p + nLength);
01647         return *this;
01648     }
01649 
01650 
01651     template <typename T, typename Allocator>
01652     basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, size_type n, value_type c)
01653     {
01654         #if EASTL_STRING_OPT_RANGE_ERRORS
01655             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01656                 ThrowRangeException();
01657         #endif
01658 
01659         #if EASTL_STRING_OPT_LENGTH_ERRORS
01660             if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - n)))
01661                 ThrowLengthException();
01662         #endif
01663 
01664         insert(mpBegin + position, n, c);
01665         return *this;
01666     }
01667 
01668 
01669     template <typename T, typename Allocator>
01670     inline typename basic_string<T, Allocator>::iterator
01671     basic_string<T, Allocator>::insert(iterator p, value_type c)
01672     {
01673         if(p == mpEnd)
01674         {
01675             push_back(c);
01676             return mpEnd - 1;
01677         }
01678         return InsertInternal(p, c);
01679     }
01680 
01681 
01682     template <typename T, typename Allocator>
01683     void basic_string<T, Allocator>::insert(iterator p, size_type n, value_type c)
01684     {
01685         #if EASTL_ASSERT_ENABLED
01686             if(EASTL_UNLIKELY((p < mpBegin) || (p > mpEnd)))
01687                 EASTL_FAIL_MSG("basic_string::insert -- invalid position");
01688         #endif
01689 
01690         if(n) // If there is anything to insert...
01691         {
01692             if(size_type(mpCapacity - mpEnd) >= (n + 1)) // If we have enough capacity...
01693             {
01694                 const size_type nElementsAfter = (size_type)(mpEnd - p);
01695                 iterator pOldEnd = mpEnd;
01696 
01697                 if(nElementsAfter >= n) // If there's enough space for the new chars between the insert position and the end...
01698                 {
01699                     CharStringUninitializedCopy((mpEnd - n) + 1, mpEnd + 1, mpEnd + 1);
01700                     mpEnd += n;
01701                     memmove(p + n, p, (size_t)((nElementsAfter - n) + 1) * sizeof(value_type));
01702                     CharTypeAssignN(p, n, c);
01703                 }
01704                 else
01705                 {
01706                     CharStringUninitializedFillN(mpEnd + 1, n - nElementsAfter - 1, c);
01707                     mpEnd += n - nElementsAfter;
01708 
01709                     #if EASTL_EXCEPTIONS_ENABLED
01710                         try
01711                         {
01712                     #endif
01713                             CharStringUninitializedCopy(p, pOldEnd + 1, mpEnd);
01714                             mpEnd += nElementsAfter;
01715                     #if EASTL_EXCEPTIONS_ENABLED
01716                         }
01717                         catch(...)
01718                         {
01719                             mpEnd = pOldEnd;
01720                             throw;
01721                         }
01722                     #endif
01723 
01724                     CharTypeAssignN(p, nElementsAfter + 1, c);
01725                 }
01726             }
01727             else
01728             {
01729                 const size_type nOldSize = (size_type)(mpEnd - mpBegin);
01730                 const size_type nOldCap  = (size_type)((mpCapacity - mpBegin) - 1);
01731                 const size_type nLength  = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + n)) + 1; // + 1 to accomodate the trailing 0.
01732 
01733                 iterator pNewBegin = DoAllocate(nLength);
01734                 iterator pNewEnd   = pNewBegin;
01735 
01736                 pNewEnd = CharStringUninitializedCopy(mpBegin, p, pNewBegin);
01737                 pNewEnd = CharStringUninitializedFillN(pNewEnd, n, c);
01738                 pNewEnd = CharStringUninitializedCopy(p, mpEnd, pNewEnd);
01739                *pNewEnd = 0;
01740 
01741                 DeallocateSelf();
01742                 mpBegin    = pNewBegin;
01743                 mpEnd      = pNewEnd;
01744                 mpCapacity = pNewBegin + nLength;
01745             }
01746         }
01747     }
01748 
01749 
01750     template <typename T, typename Allocator>
01751     void basic_string<T, Allocator>::insert(iterator p, const value_type* pBegin, const value_type* pEnd)
01752     {
01753         #if EASTL_ASSERT_ENABLED
01754             if(EASTL_UNLIKELY((p < mpBegin) || (p > mpEnd)))
01755                 EASTL_FAIL_MSG("basic_string::insert -- invalid position");
01756         #endif
01757 
01758         const size_type n = (size_type)(pEnd - pBegin);
01759 
01760         if(n)
01761         {
01762             const bool bCapacityIsSufficient = ((mpCapacity - mpEnd) >= (difference_type)(n + 1));
01763             const bool bSourceIsFromSelf     = ((pEnd >= mpBegin) && (pBegin <= mpEnd));
01764 
01765             // If bSourceIsFromSelf is true, then we reallocate. This is because we are
01766             // inserting ourself into ourself and thus both the source and destination
01767             // be modified, making it rather tricky to attempt to do in place. The simplest
01768             // resolution is to reallocate. To consider: there may be a way to implement this
01769             // whereby we don't need to reallocate or can often avoid reallocating.
01770             if(bCapacityIsSufficient && !bSourceIsFromSelf)
01771             {
01772                 const ptrdiff_t nElementsAfter = (mpEnd - p);
01773                 iterator        pOldEnd        = mpEnd;
01774 
01775                 if(nElementsAfter >= (ptrdiff_t)n) // If the newly inserted characters entirely fit within the size of the original string...
01776                 {
01777                     memmove(mpEnd + 1, mpEnd - n + 1, (size_t)n * sizeof(value_type));
01778                     mpEnd += n;
01779                     memmove(p + n, p, (size_t)((nElementsAfter - n) + 1) * sizeof(value_type));
01780                     memmove(p, pBegin, (size_t)(pEnd - pBegin) * sizeof(value_type));
01781                 }
01782                 else
01783                 {
01784                     const value_type* const pMid = pBegin + (nElementsAfter + 1);
01785 
01786                     memmove(mpEnd + 1, pMid, (size_t)(pEnd - pMid) * sizeof(value_type));
01787                     mpEnd += n - nElementsAfter;
01788 
01789                     #if EASTL_EXCEPTIONS_ENABLED
01790                         try
01791                         {
01792                     #endif
01793                             memmove(mpEnd, p, (size_t)(pOldEnd - p + 1) * sizeof(value_type));
01794                             mpEnd += nElementsAfter;
01795                     #if EASTL_EXCEPTIONS_ENABLED
01796                         }
01797                         catch(...)
01798                         {
01799                             mpEnd = pOldEnd;
01800                             throw;
01801                         }
01802                     #endif
01803 
01804                     memmove(p, pBegin, (size_t)(pMid - pBegin) * sizeof(value_type));
01805                 }
01806             }
01807             else // Else we need to reallocate to implement this.
01808             {
01809                 const size_type nOldSize = (size_type)(mpEnd - mpBegin);
01810                 const size_type nOldCap  = (size_type)((mpCapacity - mpBegin) - 1);
01811                 size_type nLength;
01812 
01813                 if(bCapacityIsSufficient) // If bCapacityIsSufficient is true, then bSourceIsFromSelf must be false.
01814                     nLength = nOldSize + n + 1; // + 1 to accomodate the trailing 0.
01815                 else
01816                     nLength = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + n)) + 1; // + 1 to accomodate the trailing 0.
01817 
01818                 pointer pNewBegin = DoAllocate(nLength);
01819                 pointer pNewEnd   = pNewBegin;
01820 
01821                 pNewEnd = CharStringUninitializedCopy(mpBegin, p,     pNewBegin);
01822                 pNewEnd = CharStringUninitializedCopy(pBegin,  pEnd,  pNewEnd);
01823                 pNewEnd = CharStringUninitializedCopy(p,       mpEnd, pNewEnd);
01824                *pNewEnd = 0;
01825 
01826                 DeallocateSelf();
01827                 mpBegin    = pNewBegin;
01828                 mpEnd      = pNewEnd;
01829                 mpCapacity = pNewBegin + nLength;
01830             }
01831         }
01832     }
01833 
01834 
01835     template <typename T, typename Allocator>
01836     inline basic_string<T, Allocator>& basic_string<T, Allocator>::erase(size_type position, size_type n)
01837     {
01838         #if EASTL_STRING_OPT_RANGE_ERRORS
01839             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01840                 ThrowRangeException();
01841         #endif
01842 
01843         #if EASTL_ASSERT_ENABLED
01844             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01845                 EASTL_FAIL_MSG("basic_string::erase -- invalid position");
01846         #endif
01847 
01848         erase(mpBegin + position, mpBegin + position + eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position));
01849         return *this;
01850     }
01851 
01852 
01853     template <typename T, typename Allocator>
01854     inline typename basic_string<T, Allocator>::iterator
01855     basic_string<T, Allocator>::erase(iterator p)
01856     {
01857         #if EASTL_ASSERT_ENABLED
01858             if(EASTL_UNLIKELY((p < mpBegin) || (p >= mpEnd)))
01859                 EASTL_FAIL_MSG("basic_string::erase -- invalid position");
01860         #endif
01861 
01862         memmove(p, p + 1, (size_t)(mpEnd - p) * sizeof(value_type));
01863         --mpEnd;
01864         return p;
01865     }
01866 
01867 
01868     template <typename T, typename Allocator>
01869     typename basic_string<T, Allocator>::iterator
01870     basic_string<T, Allocator>::erase(iterator pBegin, iterator pEnd)
01871     {
01872         #if EASTL_ASSERT_ENABLED
01873             if(EASTL_UNLIKELY((pBegin < mpBegin) || (pBegin > mpEnd) || (pEnd < mpBegin) || (pEnd > mpEnd) || (pEnd < pBegin)))
01874                 EASTL_FAIL_MSG("basic_string::erase -- invalid position");
01875         #endif
01876 
01877         if(pBegin != pEnd)
01878         {
01879             memmove(pBegin, pEnd, (size_t)((mpEnd - pEnd) + 1) * sizeof(value_type));
01880             const iterator pNewEnd = (mpEnd - (pEnd - pBegin));
01881             mpEnd = pNewEnd;
01882         }
01883         return pBegin;
01884     }
01885 
01886 
01887     template <typename T, typename Allocator>
01888     inline typename basic_string<T, Allocator>::reverse_iterator
01889     basic_string<T, Allocator>::erase(reverse_iterator position)
01890     {
01891         return reverse_iterator(erase((++position).base()));
01892     }
01893 
01894 
01895     template <typename T, typename Allocator>
01896     typename basic_string<T, Allocator>::reverse_iterator
01897     basic_string<T, Allocator>::erase(reverse_iterator first, reverse_iterator last)
01898     {
01899         return reverse_iterator(erase((++last).base(), (++first).base()));
01900     }
01901 
01902 
01903     template <typename T, typename Allocator>
01904     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n, const basic_string<T, Allocator>& x)
01905     {
01906         #if EASTL_STRING_OPT_RANGE_ERRORS
01907             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01908                 ThrowRangeException();
01909         #endif
01910 
01911         const size_type nLength = eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position);
01912 
01913         #if EASTL_STRING_OPT_LENGTH_ERRORS
01914             if(EASTL_UNLIKELY(((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - (size_type)(x.mpEnd - x.mpBegin))))
01915                 ThrowLengthException();
01916         #endif
01917 
01918         return replace(mpBegin + position, mpBegin + position + nLength, x.mpBegin, x.mpEnd);
01919     }
01920 
01921 
01922     template <typename T, typename Allocator>
01923     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type pos1, size_type n1, const basic_string<T, Allocator>& x, size_type pos2, size_type n2)
01924     {
01925         #if EASTL_STRING_OPT_RANGE_ERRORS
01926             if(EASTL_UNLIKELY((pos1 > (size_type)(mpEnd - mpBegin)) || (pos2 > (size_type)(x.mpEnd - x.mpBegin))))
01927                 ThrowRangeException();
01928         #endif
01929 
01930         const size_type nLength1 = eastl::min_alt(n1, (size_type)(  mpEnd -   mpBegin) - pos1);
01931         const size_type nLength2 = eastl::min_alt(n2, (size_type)(x.mpEnd - x.mpBegin) - pos2);
01932 
01933         #if EASTL_STRING_OPT_LENGTH_ERRORS
01934             if(EASTL_UNLIKELY(((size_type)(mpEnd - mpBegin) - nLength1) >= (kMaxSize - nLength2)))
01935                 ThrowLengthException();
01936         #endif
01937 
01938         return replace(mpBegin + pos1, mpBegin + pos1 + nLength1, x.mpBegin + pos2, x.mpBegin + pos2 + nLength2);
01939     }
01940 
01941 
01942     template <typename T, typename Allocator>
01943     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n1, const value_type* p, size_type n2)
01944     {
01945         #if EASTL_STRING_OPT_RANGE_ERRORS
01946             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01947                 ThrowRangeException();
01948         #endif
01949 
01950         const size_type nLength = eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - position);
01951 
01952         #if EASTL_STRING_OPT_LENGTH_ERRORS
01953             if(EASTL_UNLIKELY((n2 > kMaxSize) || (((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - n2))))
01954                 ThrowLengthException();
01955         #endif
01956 
01957         return replace(mpBegin + position, mpBegin + position + nLength, p, p + n2);
01958     }
01959 
01960 
01961     template <typename T, typename Allocator>
01962     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n1, const value_type* p)
01963     {
01964         #if EASTL_STRING_OPT_RANGE_ERRORS
01965             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01966                 ThrowRangeException();
01967         #endif
01968 
01969         const size_type nLength = eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - position);
01970 
01971         #if EASTL_STRING_OPT_LENGTH_ERRORS
01972             const size_type n2 = (size_type)CharStrlen(p);
01973             if(EASTL_UNLIKELY((n2 > kMaxSize) || (((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - n2))))
01974                 ThrowLengthException();
01975         #endif
01976 
01977         return replace(mpBegin + position, mpBegin + position + nLength, p, p + CharStrlen(p));
01978     }
01979 
01980 
01981     template <typename T, typename Allocator>
01982     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n1, size_type n2, value_type c)
01983     {
01984         #if EASTL_STRING_OPT_RANGE_ERRORS
01985             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
01986                 ThrowRangeException();
01987         #endif
01988 
01989         const size_type nLength = eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - position);
01990 
01991         #if EASTL_STRING_OPT_LENGTH_ERRORS
01992             if(EASTL_UNLIKELY((n2 > kMaxSize) || ((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - n2)))
01993                 ThrowLengthException();
01994         #endif
01995 
01996         return replace(mpBegin + position, mpBegin + position + nLength, n2, c);
01997     }
01998 
01999 
02000     template <typename T, typename Allocator>
02001     inline basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, const basic_string<T, Allocator>& x)
02002     {
02003         return replace(pBegin, pEnd, x.mpBegin, x.mpEnd);
02004     }
02005 
02006 
02007     template <typename T, typename Allocator>
02008     inline basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, const value_type* p, size_type n)
02009     {
02010         return replace(pBegin, pEnd, p, p + n);
02011     }
02012 
02013 
02014     template <typename T, typename Allocator>
02015     inline basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, const value_type* p)
02016     {
02017         return replace(pBegin, pEnd, p, p + CharStrlen(p));
02018     }
02019 
02020 
02021     template <typename T, typename Allocator>
02022     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, size_type n, value_type c)
02023     {
02024         #if EASTL_ASSERT_ENABLED
02025             if(EASTL_UNLIKELY((pBegin < mpBegin) || (pBegin > mpEnd) || (pEnd < mpBegin) || (pEnd > mpEnd) || (pEnd < pBegin)))
02026                 EASTL_FAIL_MSG("basic_string::replace -- invalid position");
02027         #endif
02028 
02029         const size_type nLength = static_cast<size_type>(pEnd - pBegin);
02030 
02031         if(nLength >= n)
02032         {
02033             CharTypeAssignN(pBegin, n, c);
02034             erase(pBegin + n, pEnd);
02035         }
02036         else
02037         {
02038             CharTypeAssignN(pBegin, nLength, c);
02039             insert(pEnd, n - nLength, c);
02040         }
02041         return *this;
02042     }
02043 
02044 
02045     template <typename T, typename Allocator>
02046     basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin1, iterator pEnd1, const value_type* pBegin2, const value_type* pEnd2)
02047     {
02048         #if EASTL_ASSERT_ENABLED
02049             if(EASTL_UNLIKELY((pBegin1 < mpBegin) || (pBegin1 > mpEnd) || (pEnd1 < mpBegin) || (pEnd1 > mpEnd) || (pEnd1 < pBegin1)))
02050                 EASTL_FAIL_MSG("basic_string::replace -- invalid position");
02051         #endif
02052 
02053         const size_type nLength1 = (size_type)(pEnd1 - pBegin1);
02054         const size_type nLength2 = (size_type)(pEnd2 - pBegin2);
02055 
02056         if(nLength1 >= nLength2) // If we have a non-expanding operation...
02057         {
02058             if((pBegin2 > pEnd1) || (pEnd2 <= pBegin1))  // If we have a non-overlapping operation...
02059                 memcpy(pBegin1, pBegin2, (size_t)(pEnd2 - pBegin2) * sizeof(value_type));
02060             else
02061                 memmove(pBegin1, pBegin2, (size_t)(pEnd2 - pBegin2) * sizeof(value_type));
02062             erase(pBegin1 + nLength2, pEnd1);
02063         }
02064         else // Else we are expanding.
02065         {
02066             if((pBegin2 > pEnd1) || (pEnd2 <= pBegin1)) // If we have a non-overlapping operation...
02067             {
02068                 const value_type* const pMid2 = pBegin2 + nLength1;
02069 
02070                 if((pEnd2 <= pBegin1) || (pBegin2 > pEnd1))
02071                     memcpy(pBegin1, pBegin2, (size_t)(pMid2 - pBegin2) * sizeof(value_type));
02072                 else
02073                     memmove(pBegin1, pBegin2, (size_t)(pMid2 - pBegin2) * sizeof(value_type));
02074                 insert(pEnd1, pMid2, pEnd2);
02075             }
02076             else // else we have an overlapping operation.
02077             {
02078                 // I can't think of any easy way of doing this without allocating temporary memory.
02079                 const size_type nOldSize     = (size_type)(mpEnd - mpBegin);
02080                 const size_type nOldCap      = (size_type)((mpCapacity - mpBegin) - 1);
02081                 const size_type nNewCapacity = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + (nLength2 - nLength1))) + 1; // + 1 to accomodate the trailing 0.
02082 
02083                 pointer pNewBegin = DoAllocate(nNewCapacity);
02084                 pointer pNewEnd   = pNewBegin;
02085 
02086                 pNewEnd = CharStringUninitializedCopy(mpBegin, pBegin1, pNewBegin);
02087                 pNewEnd = CharStringUninitializedCopy(pBegin2, pEnd2,   pNewEnd);
02088                 pNewEnd = CharStringUninitializedCopy(pEnd1,   mpEnd,   pNewEnd);
02089                *pNewEnd = 0;
02090 
02091                 DeallocateSelf();
02092                 mpBegin    = pNewBegin;
02093                 mpEnd      = pNewEnd;
02094                 mpCapacity = pNewBegin + nNewCapacity;
02095             }
02096         }
02097         return *this;
02098     }
02099 
02100 
02101     template <typename T, typename Allocator>
02102     typename basic_string<T, Allocator>::size_type
02103     basic_string<T, Allocator>::copy(value_type* p, size_type n, size_type position) const
02104     {
02105         #if EASTL_STRING_OPT_RANGE_ERRORS
02106             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
02107                 ThrowRangeException();
02108         #endif
02109 
02110         // It is not clear from the C++ standard if 'p' destination pointer is allowed to
02111         // refer to memory from within the string itself. We assume so and use memmove
02112         // instead of memcpy until we find otherwise.
02113         const size_type nLength = eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position);
02114         memmove(p, mpBegin + position, (size_t)nLength * sizeof(value_type));
02115         return nLength;
02116     }
02117 
02118 
02119     template <typename T, typename Allocator>
02120     void basic_string<T, Allocator>::swap(basic_string<T, Allocator>& x)
02121     {
02122         if(mAllocator == x.mAllocator) // If allocators are equivalent...
02123         {
02124             // We leave mAllocator as-is.
02125             eastl::swap(mpBegin,     x.mpBegin);
02126             eastl::swap(mpEnd,       x.mpEnd);
02127             eastl::swap(mpCapacity,  x.mpCapacity);
02128         }
02129         else // else swap the contents.
02130         {
02131             const this_type temp(*this); // Can't call eastl::swap because that would
02132             *this = x;                   // itself call this member swap function.
02133             x     = temp;
02134         }
02135     }
02136 
02137 
02138     template <typename T, typename Allocator>
02139     inline typename basic_string<T, Allocator>::size_type
02140     basic_string<T, Allocator>::find(const basic_string<T, Allocator>& x, size_type position) const
02141     {
02142         return find(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
02143     }
02144 
02145 
02146     template <typename T, typename Allocator>
02147     inline typename basic_string<T, Allocator>::size_type
02148     basic_string<T, Allocator>::find(const value_type* p, size_type position) const
02149     {
02150         return find(p, position, (size_type)CharStrlen(p));
02151     }
02152 
02153 
02154     #if defined(EA_PLATFORM_XENON) // If XBox 360...
02155 
02156         template <typename T, typename Allocator>
02157         typename basic_string<T, Allocator>::size_type
02158         basic_string<T, Allocator>::find(const value_type* p, size_type position, size_type n) const
02159         {
02160             const size_type nLength = (size_type)(mpEnd - mpBegin);
02161 
02162             if(n || (position > nLength))
02163             {
02164                 if(position < nLength)
02165                 {
02166                     size_type nRemain = nLength - position;
02167 
02168                     if(n <= nRemain)
02169                     {
02170                         nRemain -= (n - 1);
02171 
02172                         for(const value_type* p1, *p2 = mpBegin + position;
02173                             (p1 = Find(p2, *p, nRemain)) != 0;
02174                             nRemain -= (p1 - p2) + 1, p2 = (p1 + 1))
02175                         {
02176                             if(Compare(p1, p, n) == 0)
02177                                 return (size_type)(p1 - mpBegin);
02178                         }
02179                     }
02180                 }
02181 
02182                 return npos;
02183             }
02184 
02185             return position;
02186         }
02187     #else
02188         template <typename T, typename Allocator>
02189         typename basic_string<T, Allocator>::size_type
02190         basic_string<T, Allocator>::find(const value_type* p, size_type position, size_type n) const
02191         {
02192             // It is not clear what the requirements are for position, but since the C++ standard
02193             // appears to be silent it is assumed for now that position can be any value.
02194             //#if EASTL_ASSERT_ENABLED
02195             //    if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
02196             //        EASTL_FAIL_MSG("basic_string::find -- invalid position");
02197             //#endif
02198 
02199             if(EASTL_LIKELY((position + n) <= (size_type)(mpEnd - mpBegin))) // If the range is valid...
02200             {
02201                 const value_type* const pTemp = eastl::search(mpBegin + position, mpEnd, p, p + n);
02202 
02203                 if((pTemp != mpEnd) || (n == 0))
02204                     return (size_type)(pTemp - mpBegin);
02205             }
02206             return npos;
02207         }
02208     #endif
02209 
02210 
02211     template <typename T, typename Allocator>
02212     typename basic_string<T, Allocator>::size_type
02213     basic_string<T, Allocator>::find(value_type c, size_type position) const
02214     {
02215         // It is not clear what the requirements are for position, but since the C++ standard
02216         // appears to be silent it is assumed for now that position can be any value.
02217         //#if EASTL_ASSERT_ENABLED
02218         //    if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
02219         //        EASTL_FAIL_MSG("basic_string::find -- invalid position");
02220         //#endif
02221 
02222         if(EASTL_LIKELY(position < (size_type)(mpEnd - mpBegin))) // If the position is valid...
02223         {
02224             const const_iterator pResult = eastl::find(mpBegin + position, mpEnd, c);
02225 
02226             if(pResult != mpEnd)
02227                 return (size_type)(pResult - mpBegin);
02228         }
02229         return npos;
02230     }
02231 
02232 
02233     template <typename T, typename Allocator>
02234     inline typename basic_string<T, Allocator>::size_type
02235     basic_string<T, Allocator>::rfind(const basic_string<T, Allocator>& x, size_type position) const
02236     {
02237         return rfind(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
02238     }
02239 
02240 
02241     template <typename T, typename Allocator>
02242     inline typename basic_string<T, Allocator>::size_type
02243     basic_string<T, Allocator>::rfind(const value_type* p, size_type position) const
02244     {
02245         return rfind(p, position, (size_type)CharStrlen(p));
02246     }
02247 
02248 
02249     template <typename T, typename Allocator>
02250     typename basic_string<T, Allocator>::size_type
02251     basic_string<T, Allocator>::rfind(const value_type* p, size_type position, size_type n) const
02252     {
02253         // Disabled because it's not clear what values are valid for position.
02254         // It is documented that npos is a valid value, though. We return npos and
02255         // don't crash if postion is any invalid value.
02256         //#if EASTL_ASSERT_ENABLED
02257         //    if(EASTL_UNLIKELY((position != npos) && (position > (size_type)(mpEnd - mpBegin))))
02258         //        EASTL_FAIL_MSG("basic_string::rfind -- invalid position");
02259         //#endif
02260 
02261         // Note that a search for a zero length string starting at position = end() returns end() and not npos.
02262         // Note by Paul Pedriana: I am not sure how this should behave in the case of n == 0 and position > size.
02263         // The standard seems to suggest that rfind doesn't act exactly the same as find in that input position
02264         // can be > size and the return value can still be other than npos. Thus, if n == 0 then you can
02265         // never return npos, unlike the case with find.
02266         const size_type nLength = (size_type)(mpEnd - mpBegin);
02267 
02268         if(EASTL_LIKELY(n <= nLength))
02269         {
02270             if(EASTL_LIKELY(n))
02271             {
02272                 const const_iterator pEnd    = mpBegin + eastl::min_alt(nLength - n, position) + n;
02273                 const const_iterator pResult = CharTypeStringRSearch(mpBegin, pEnd, p, p + n);
02274 
02275                 if(pResult != pEnd)
02276                     return (size_type)(pResult - mpBegin);
02277             }
02278             else
02279                 return eastl::min_alt(nLength, position);
02280         }
02281         return npos;
02282     }
02283 
02284 
02285     template <typename T, typename Allocator>
02286     typename basic_string<T, Allocator>::size_type
02287     basic_string<T, Allocator>::rfind(value_type c, size_type position) const
02288     {
02289         // If n is zero or position is >= size, we return npos.
02290         const size_type nLength = (size_type)(mpEnd - mpBegin);
02291 
02292         if(EASTL_LIKELY(nLength))
02293         {
02294             const value_type* const pEnd    = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
02295             const value_type* const pResult = CharTypeStringRFind(pEnd, mpBegin, c);
02296 
02297             if(pResult != mpBegin)
02298                 return (size_type)((pResult - 1) - mpBegin);
02299         }
02300         return npos;
02301     }
02302 
02303 
02304     template <typename T, typename Allocator>
02305     inline typename basic_string<T, Allocator>::size_type
02306     basic_string<T, Allocator>::find_first_of(const basic_string<T, Allocator>& x, size_type position) const
02307     {
02308         return find_first_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
02309     }
02310 
02311 
02312     template <typename T, typename Allocator>
02313     inline typename basic_string<T, Allocator>::size_type
02314     basic_string<T, Allocator>::find_first_of(const value_type* p, size_type position) const
02315     {
02316         return find_first_of(p, position, (size_type)CharStrlen(p));
02317     }
02318 
02319 
02320     #if defined(EA_PLATFORM_XENON) // If XBox 360...
02321 
02322         template <typename T, typename Allocator>
02323         typename basic_string<T, Allocator>::size_type
02324         basic_string<T, Allocator>::find_first_of(const value_type* p, size_type position, size_type n) const
02325         {
02326             // If position is >= size, we return npos.
02327             if(n && (position < (size_type)(mpEnd - mpBegin)))
02328             {
02329                 for(const value_type* p1 = (mpBegin + position); p1 < mpEnd; ++p1)
02330                 {
02331                     if(Find(p, *p1, n) != 0)
02332                         return (size_type)(p1 - mpBegin);
02333                 }
02334             }
02335             return npos;
02336         }
02337     #else
02338         template <typename T, typename Allocator>
02339         typename basic_string<T, Allocator>::size_type
02340         basic_string<T, Allocator>::find_first_of(const value_type* p, size_type position, size_type n) const
02341         {
02342             // If position is >= size, we return npos.
02343             if(EASTL_LIKELY((position < (size_type)(mpEnd - mpBegin))))
02344             {
02345                 const value_type* const pBegin = mpBegin + position;
02346                 const const_iterator pResult   = CharTypeStringFindFirstOf(pBegin, mpEnd, p, p + n);
02347 
02348                 if(pResult != mpEnd)
02349                     return (size_type)(pResult - mpBegin);
02350             }
02351             return npos;
02352         }
02353     #endif
02354 
02355 
02356     template <typename T, typename Allocator>
02357     inline typename basic_string<T, Allocator>::size_type
02358     basic_string<T, Allocator>::find_first_of(value_type c, size_type position) const
02359     {
02360         return find(c, position);
02361     }
02362 
02363 
02364     template <typename T, typename Allocator>
02365     inline typename basic_string<T, Allocator>::size_type
02366     basic_string<T, Allocator>::find_last_of(const basic_string<T, Allocator>& x, size_type position) const
02367     {
02368         return find_last_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
02369     }
02370 
02371 
02372     template <typename T, typename Allocator>
02373     inline typename basic_string<T, Allocator>::size_type
02374     basic_string<T, Allocator>::find_last_of(const value_type* p, size_type position) const
02375     {
02376         return find_last_of(p, position, (size_type)CharStrlen(p));
02377     }
02378 
02379 
02380     #if defined(EA_PLATFORM_XENON) // If XBox 360...
02381 
02382         template <typename T, typename Allocator>
02383         typename basic_string<T, Allocator>::size_type
02384         basic_string<T, Allocator>::find_last_of(const value_type* p, size_type position, size_type n) const
02385         {
02386             // If n is zero or position is >= size, we return npos.
02387             const size_type nLength = (size_type)(mpEnd - mpBegin);
02388 
02389             if(n && nLength)
02390             {
02391                 const value_type* p1;
02392 
02393                 if(position < nLength)
02394                     p1 = mpBegin + position;
02395                 else
02396                     p1 = mpEnd - 1;
02397 
02398                 for(;;)
02399                 {
02400                     if(Find(p, *p1, n))
02401                         return (size_type)(p1 - mpBegin);
02402 
02403                     if(p1-- == mpBegin)
02404                         break;
02405                 }
02406             }
02407 
02408             return npos;
02409         }
02410     #else
02411         template <typename T, typename Allocator>
02412         typename basic_string<T, Allocator>::size_type
02413         basic_string<T, Allocator>::find_last_of(const value_type* p, size_type position, size_type n) const
02414         {
02415             // If n is zero or position is >= size, we return npos.
02416             const size_type nLength = (size_type)(mpEnd - mpBegin);
02417 
02418             if(EASTL_LIKELY(nLength))
02419             {
02420                 const value_type* const pEnd    = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
02421                 const value_type* const pResult = CharTypeStringRFindFirstOf(pEnd, mpBegin, p, p + n);
02422 
02423                 if(pResult != mpBegin)
02424                     return (size_type)((pResult - 1) - mpBegin);
02425             }
02426             return npos;
02427         }
02428     #endif
02429 
02430 
02431     template <typename T, typename Allocator>
02432     inline typename basic_string<T, Allocator>::size_type
02433     basic_string<T, Allocator>::find_last_of(value_type c, size_type position) const
02434     {
02435         return rfind(c, position);
02436     }
02437 
02438 
02439     template <typename T, typename Allocator>
02440     inline typename basic_string<T, Allocator>::size_type
02441     basic_string<T, Allocator>::find_first_not_of(const basic_string<T, Allocator>& x, size_type position) const
02442     {
02443         return find_first_not_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
02444     }
02445 
02446 
02447     template <typename T, typename Allocator>
02448     inline typename basic_string<T, Allocator>::size_type
02449     basic_string<T, Allocator>::find_first_not_of(const value_type* p, size_type position) const
02450     {
02451         return find_first_not_of(p, position, (size_type)CharStrlen(p));
02452     }
02453 
02454 
02455     template <typename T, typename Allocator>
02456     typename basic_string<T, Allocator>::size_type
02457     basic_string<T, Allocator>::find_first_not_of(const value_type* p, size_type position, size_type n) const
02458     {
02459         if(EASTL_LIKELY(position <= (size_type)(mpEnd - mpBegin)))
02460         {
02461             const const_iterator pResult = CharTypeStringFindFirstNotOf(mpBegin + position, mpEnd, p, p + n);
02462 
02463             if(pResult != mpEnd)
02464                 return (size_type)(pResult - mpBegin);
02465         }
02466         return npos;
02467     }
02468 
02469 
02470     template <typename T, typename Allocator>
02471     typename basic_string<T, Allocator>::size_type
02472     basic_string<T, Allocator>::find_first_not_of(value_type c, size_type position) const
02473     {
02474         if(EASTL_LIKELY(position <= (size_type)(mpEnd - mpBegin)))
02475         {
02476             // Todo: Possibly make a specialized version of CharTypeStringFindFirstNotOf(pBegin, pEnd, c).
02477             const const_iterator pResult = CharTypeStringFindFirstNotOf(mpBegin + position, mpEnd, &c, &c + 1);
02478 
02479             if(pResult != mpEnd)
02480                 return (size_type)(pResult - mpBegin);
02481         }
02482         return npos;
02483     }
02484 
02485 
02486     template <typename T, typename Allocator>
02487     inline typename basic_string<T, Allocator>::size_type
02488     basic_string<T, Allocator>::find_last_not_of(const basic_string<T, Allocator>& x, size_type position) const
02489     {
02490         return find_last_not_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
02491     }
02492 
02493 
02494     template <typename T, typename Allocator>
02495     inline typename basic_string<T, Allocator>::size_type
02496     basic_string<T, Allocator>::find_last_not_of(const value_type* p, size_type position) const
02497     {
02498         return find_last_not_of(p, position, (size_type)CharStrlen(p));
02499     }
02500 
02501 
02502     template <typename T, typename Allocator>
02503     typename basic_string<T, Allocator>::size_type
02504     basic_string<T, Allocator>::find_last_not_of(const value_type* p, size_type position, size_type n) const
02505     {
02506         const size_type nLength = (size_type)(mpEnd - mpBegin);
02507 
02508         if(EASTL_LIKELY(nLength))
02509         {
02510             const value_type* const pEnd    = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
02511             const value_type* const pResult = CharTypeStringRFindFirstNotOf(pEnd, mpBegin, p, p + n);
02512 
02513             if(pResult != mpBegin)
02514                 return (size_type)((pResult - 1) - mpBegin);
02515         }
02516         return npos;
02517     }
02518 
02519 
02520     template <typename T, typename Allocator>
02521     typename basic_string<T, Allocator>::size_type
02522     basic_string<T, Allocator>::find_last_not_of(value_type c, size_type position) const
02523     {
02524         const size_type nLength = (size_type)(mpEnd - mpBegin);
02525 
02526         if(EASTL_LIKELY(nLength))
02527         {
02528             // Todo: Possibly make a specialized version of CharTypeStringRFindFirstNotOf(pBegin, pEnd, c).
02529             const value_type* const pEnd    = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
02530             const value_type* const pResult = CharTypeStringRFindFirstNotOf(pEnd, mpBegin, &c, &c + 1);
02531 
02532             if(pResult != mpBegin)
02533                 return (size_type)((pResult - 1) - mpBegin);
02534         }
02535         return npos;
02536     }
02537 
02538 
02539     template <typename T, typename Allocator>
02540     inline basic_string<T, Allocator> basic_string<T, Allocator>::substr(size_type position, size_type n) const
02541     {
02542         #if EASTL_STRING_OPT_RANGE_ERRORS
02543             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
02544                 ThrowRangeException();
02545         #elif EASTL_ASSERT_ENABLED
02546             if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
02547                 EASTL_FAIL_MSG("basic_string::substr -- invalid position");
02548         #endif
02549 
02550         return basic_string(mpBegin + position, mpBegin + position + eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position), mAllocator);
02551     }
02552 
02553 
02554     template <typename T, typename Allocator>
02555     inline int basic_string<T, Allocator>::compare(const basic_string<T, Allocator>& x) const
02556     {
02557         return compare(mpBegin, mpEnd, x.mpBegin, x.mpEnd);
02558     }
02559 
02560 
02561     template <typename T, typename Allocator>
02562     inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const basic_string<T, Allocator>& x) const
02563     {
02564         #if EASTL_STRING_OPT_RANGE_ERRORS
02565             if(EASTL_UNLIKELY(pos1 > (size_type)(mpEnd - mpBegin)))
02566                 ThrowRangeException();
02567         #endif
02568 
02569         return compare(mpBegin + pos1,
02570                        mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
02571                        x.mpBegin,
02572                        x.mpEnd);
02573     }
02574 
02575 
02576     template <typename T, typename Allocator>
02577     inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const basic_string<T, Allocator>& x, size_type pos2, size_type n2) const
02578     {
02579         #if EASTL_STRING_OPT_RANGE_ERRORS
02580             if(EASTL_UNLIKELY((pos1 > (size_type)(mpEnd - mpBegin)) || (pos2 > (size_type)(x.mpEnd - x.mpBegin))))
02581                 ThrowRangeException();
02582         #endif
02583 
02584         return compare(mpBegin + pos1,
02585                        mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
02586                        x.mpBegin + pos2,
02587                        x.mpBegin + pos2 + eastl::min_alt(n2, (size_type)(mpEnd - mpBegin) - pos2));
02588     }
02589 
02590 
02591     template <typename T, typename Allocator>
02592     inline int basic_string<T, Allocator>::compare(const value_type* p) const
02593     {
02594         return compare(mpBegin, mpEnd, p, p + CharStrlen(p));
02595     }
02596 
02597 
02598     template <typename T, typename Allocator>
02599     inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const value_type* p) const
02600     {
02601         #if EASTL_STRING_OPT_RANGE_ERRORS
02602             if(EASTL_UNLIKELY(pos1 > (size_type)(mpEnd - mpBegin)))
02603                 ThrowRangeException();
02604         #endif
02605 
02606         return compare(mpBegin + pos1,
02607                        mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
02608                        p,
02609                        p + CharStrlen(p));
02610     }
02611 
02612 
02613     template <typename T, typename Allocator>
02614     inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const value_type* p, size_type n2) const
02615     {
02616         #if EASTL_STRING_OPT_RANGE_ERRORS
02617             if(EASTL_UNLIKELY(pos1 > (size_type)(mpEnd - mpBegin)))
02618                 ThrowRangeException();
02619         #endif
02620 
02621         return compare(mpBegin + pos1,
02622                        mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
02623                        p,
02624                        p + n2);
02625     }
02626 
02627 
02628     // make_lower
02629     // This is a very simple ASCII-only case conversion function
02630     // Anything more complicated should use a more powerful separate library.
02631     template <typename T, typename Allocator>
02632     inline void basic_string<T, Allocator>::make_lower()
02633     {
02634         for(pointer p = mpBegin; p < mpEnd; ++p)
02635             *p = (value_type)CharToLower(*p);
02636     }
02637 
02638 
02639     // make_upper
02640     // This is a very simple ASCII-only case conversion function
02641     // Anything more complicated should use a more powerful separate library.
02642     template <typename T, typename Allocator>
02643     inline void basic_string<T, Allocator>::make_upper()
02644     {
02645         for(pointer p = mpBegin; p < mpEnd; ++p)
02646             *p = (value_type)CharToUpper(*p);
02647     }
02648 
02649 
02650     template <typename T, typename Allocator>
02651     inline void basic_string<T, Allocator>::ltrim()
02652     {
02653         const value_type array[] = { ' ', '\t', 0 }; // This is a pretty simplistic view of whitespace.
02654         erase(0, find_first_not_of(array));
02655     }
02656 
02657 
02658     template <typename T, typename Allocator>
02659     inline void basic_string<T, Allocator>::rtrim()
02660     {
02661         const value_type array[] = { ' ', '\t', 0 }; // This is a pretty simplistic view of whitespace.
02662         erase(find_last_not_of(array) + 1);
02663     }
02664 
02665 
02666     template <typename T, typename Allocator>
02667     inline void basic_string<T, Allocator>::trim()
02668     {
02669         ltrim();
02670         rtrim();
02671     }
02672 
02673 
02674     template <typename T, typename Allocator>
02675     inline basic_string<T, Allocator> basic_string<T, Allocator>::left(size_type n) const
02676     {
02677         const size_type nLength = length();
02678         if(n < nLength)
02679             return substr(0, n);
02680         return *this;
02681     }
02682 
02683 
02684     template <typename T, typename Allocator>
02685     inline basic_string<T, Allocator> basic_string<T, Allocator>::right(size_type n) const
02686     {
02687         const size_type nLength = length();
02688         if(n < nLength)
02689             return substr(nLength - n, n);
02690         return *this;
02691     }
02692 
02693 
02694     template <typename T, typename Allocator>
02695     inline basic_string<T, Allocator>& basic_string<T, Allocator>::sprintf(const value_type* pFormat, ...)
02696     {
02697         va_list arguments;
02698         va_start(arguments, pFormat);
02699         mpEnd = mpBegin; // Fast truncate to zero length.
02700         append_sprintf_va_list(pFormat, arguments);
02701         va_end(arguments);
02702 
02703         return *this;
02704     }
02705 
02706 
02707     template <typename T, typename Allocator>
02708     basic_string<T, Allocator>& basic_string<T, Allocator>::sprintf_va_list(const value_type* pFormat, va_list arguments)
02709     {
02710         mpEnd = mpBegin; // Fast truncate to zero length.
02711 
02712         return append_sprintf_va_list(pFormat, arguments);
02713     }
02714 
02715 
02716     template <typename T, typename Allocator>
02717     int basic_string<T, Allocator>::compare(const value_type* pBegin1, const value_type* pEnd1,
02718                                             const value_type* pBegin2, const value_type* pEnd2)
02719     {
02720         const ptrdiff_t n1   = pEnd1 - pBegin1;
02721         const ptrdiff_t n2   = pEnd2 - pBegin2;
02722         const ptrdiff_t nMin = eastl::min_alt(n1, n2);
02723         const int       cmp  = Compare(pBegin1, pBegin2, (size_t)nMin);
02724 
02725         return (cmp != 0 ? cmp : (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)));
02726     }
02727 
02728 
02729     template <typename T, typename Allocator>
02730     int basic_string<T, Allocator>::comparei(const value_type* pBegin1, const value_type* pEnd1,
02731                                              const value_type* pBegin2, const value_type* pEnd2)
02732     {
02733         const ptrdiff_t n1   = pEnd1 - pBegin1;
02734         const ptrdiff_t n2   = pEnd2 - pBegin2;
02735         const ptrdiff_t nMin = eastl::min_alt(n1, n2);
02736         const int       cmp  = CompareI(pBegin1, pBegin2, (size_t)nMin);
02737 
02738         return (cmp != 0 ? cmp : (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)));
02739     }
02740 
02741 
02742     template <typename T, typename Allocator>
02743     inline int basic_string<T, Allocator>::comparei(const basic_string<T, Allocator>& x) const
02744     {
02745         return comparei(mpBegin, mpEnd, x.mpBegin, x.mpEnd);
02746     }
02747 
02748 
02749     template <typename T, typename Allocator>
02750     inline int basic_string<T, Allocator>::comparei(const value_type* p) const
02751     {
02752         return comparei(mpBegin, mpEnd, p, p + CharStrlen(p));
02753     }
02754 
02755 
02756     template <typename T, typename Allocator>
02757     typename basic_string<T, Allocator>::iterator
02758     basic_string<T, Allocator>::InsertInternal(iterator p, value_type c)
02759     {
02760         iterator pNewPosition = p;
02761 
02762         if((mpEnd + 1) < mpCapacity)
02763         {
02764             *(mpEnd + 1) = 0;
02765             memmove(p + 1, p, (size_t)(mpEnd - p) * sizeof(value_type));
02766             *p = c;
02767             ++mpEnd;
02768         }
02769         else
02770         {
02771             const size_type nOldSize = (size_type)(mpEnd - mpBegin);
02772             const size_type nOldCap  = (size_type)((mpCapacity - mpBegin) - 1);
02773             const size_type nLength  = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + 1)) + 1; // The second + 1 is to accomodate the trailing 0.
02774 
02775             iterator pNewBegin = DoAllocate(nLength);
02776             iterator pNewEnd   = pNewBegin;
02777 
02778             pNewPosition = CharStringUninitializedCopy(mpBegin, p, pNewBegin);
02779            *pNewPosition = c;
02780 
02781             pNewEnd = pNewPosition + 1;
02782             pNewEnd = CharStringUninitializedCopy(p, mpEnd, pNewEnd);
02783            *pNewEnd = 0;
02784 
02785             DeallocateSelf();
02786             mpBegin    = pNewBegin;
02787             mpEnd      = pNewEnd;
02788             mpCapacity = pNewBegin + nLength;
02789         }
02790         return pNewPosition;
02791     }
02792 
02793 
02794     template <typename T, typename Allocator>
02795     void basic_string<T, Allocator>::SizeInitialize(size_type n, value_type c)
02796     {
02797         AllocateSelf((size_type)(n + 1)); // '+1' so that we have room for the terminating 0.
02798 
02799         mpEnd = CharStringUninitializedFillN(mpBegin, n, c);
02800        *mpEnd = 0;
02801     }
02802 
02803 
02804     template <typename T, typename Allocator>
02805     void basic_string<T, Allocator>::RangeInitialize(const value_type* pBegin, const value_type* pEnd)
02806     {
02807         const size_type n = (size_type)(pEnd - pBegin);
02808 
02809         #if EASTL_STRING_OPT_ARGUMENT_ERRORS
02810             if(EASTL_UNLIKELY(!pBegin && (n != 0)))
02811                 ThrowInvalidArgumentException();
02812         #endif
02813 
02814         AllocateSelf((size_type)(n + 1)); // '+1' so that we have room for the terminating 0.
02815 
02816         mpEnd = CharStringUninitializedCopy(pBegin, pEnd, mpBegin);
02817        *mpEnd = 0;
02818     }
02819 
02820 
02821     template <typename T, typename Allocator>
02822     inline void basic_string<T, Allocator>::RangeInitialize(const value_type* pBegin)
02823     {
02824         #if EASTL_STRING_OPT_ARGUMENT_ERRORS
02825             if(EASTL_UNLIKELY(!pBegin))
02826                 ThrowInvalidArgumentException();
02827         #endif
02828 
02829         RangeInitialize(pBegin, pBegin + CharStrlen(pBegin));
02830     }
02831 
02832 
02833     template <typename T, typename Allocator>
02834     inline typename basic_string<T, Allocator>::value_type*
02835     basic_string<T, Allocator>::DoAllocate(size_type n)
02836     {
02837         EASTL_ASSERT(n > 1); // We want n > 1 because n == 1 is reserved for empty capacity and usage of gEmptyString.
02838         return (value_type*)EASTLAlloc(mAllocator, n * sizeof(value_type));
02839     }
02840 
02841 
02842     template <typename T, typename Allocator>
02843     inline void basic_string<T, Allocator>::DoFree(value_type* p, size_type n)
02844     {
02845         if(p)
02846             EASTLFree(mAllocator, p, n * sizeof(value_type));
02847     }
02848 
02849 
02850     template <typename T, typename Allocator>
02851     inline typename basic_string<T, Allocator>::size_type
02852     basic_string<T, Allocator>::GetNewCapacity(size_type currentCapacity) // This needs to return a value of at least currentCapacity and at least 1.
02853     {
02854         return (currentCapacity > EASTL_STRING_INITIAL_CAPACITY) ? (2 * currentCapacity) : EASTL_STRING_INITIAL_CAPACITY;
02855     }
02856 
02857 
02858     template <typename T, typename Allocator>
02859     inline void basic_string<T, Allocator>::AllocateSelf()
02860     {
02861         EASTL_ASSERT(gEmptyString.mUint32 == 0);
02862         mpBegin     = const_cast<value_type*>(GetEmptyString(value_type()));  // In const_cast-int this, we promise not to modify it.
02863         mpEnd       = mpBegin;
02864         mpCapacity  = mpBegin + 1; // When we are using gEmptyString, mpCapacity is always mpEnd + 1. This is an important distinguising characteristic.
02865     }
02866 
02867 
02868     template <typename T, typename Allocator>
02869     void basic_string<T, Allocator>::AllocateSelf(size_type n)
02870     {
02871         #if EASTL_ASSERT_ENABLED
02872             if(EASTL_UNLIKELY(n >= 0x40000000))
02873                 EASTL_FAIL_MSG("basic_string::AllocateSelf -- improbably large request.");
02874         #endif
02875 
02876         #if EASTL_STRING_OPT_LENGTH_ERRORS
02877             if(EASTL_UNLIKELY(n > kMaxSize))
02878                 ThrowLengthException();
02879         #endif
02880 
02881         if(n > 1)
02882         {
02883             mpBegin    = DoAllocate(n);
02884             mpEnd      = mpBegin;
02885             mpCapacity = mpBegin + n;
02886         }
02887         else
02888             AllocateSelf();
02889     }
02890 
02891 
02892     template <typename T, typename Allocator>
02893     inline void basic_string<T, Allocator>::DeallocateSelf()
02894     {
02895         // Note that we compare mpCapacity to mpEnd instead of comparing
02896         // mpBegin to &gEmptyString. This is important because we may have
02897         // a case whereby one library passes a string to another library to
02898         // deallocate and the two libraries have idependent versions of gEmptyString.
02899         if((mpCapacity - mpBegin) > 1) // If we are not using gEmptyString as our memory...
02900             DoFree(mpBegin, (size_type)(mpCapacity - mpBegin));
02901     }
02902 
02903 
02904     template <typename T, typename Allocator>
02905     inline void basic_string<T, Allocator>::ThrowLengthException() const
02906     {
02907         #if EASTL_EXCEPTIONS_ENABLED
02908             throw std::length_error("basic_string -- length_error");
02909         #elif EASTL_ASSERT_ENABLED
02910             EASTL_FAIL_MSG("basic_string -- length_error");
02911         #endif
02912     }
02913 
02914 
02915     template <typename T, typename Allocator>
02916     inline void basic_string<T, Allocator>::ThrowRangeException() const
02917     {
02918         #if EASTL_EXCEPTIONS_ENABLED
02919             throw std::out_of_range("basic_string -- out of range");
02920         #elif EASTL_ASSERT_ENABLED
02921             EASTL_FAIL_MSG("basic_string -- out of range");
02922         #endif
02923     }
02924 
02925 
02926     template <typename T, typename Allocator>
02927     inline void basic_string<T, Allocator>::ThrowInvalidArgumentException() const
02928     {
02929         #if EASTL_EXCEPTIONS_ENABLED
02930             throw std::invalid_argument("basic_string -- invalid argument");
02931         #elif EASTL_ASSERT_ENABLED
02932             EASTL_FAIL_MSG("basic_string -- invalid argument");
02933         #endif
02934     }
02935 
02936 
02937     // CharTypeStringFindEnd
02938     // Specialized char version of STL find() from back function.
02939     // Not the same as RFind because search range is specified as forward iterators.
02940     template <typename T, typename Allocator>
02941     const typename basic_string<T, Allocator>::value_type*
02942     basic_string<T, Allocator>::CharTypeStringFindEnd(const value_type* pBegin, const value_type* pEnd, value_type c)
02943     {
02944         const value_type* pTemp = pEnd;
02945         while(--pTemp >= pBegin)
02946         {
02947             if(*pTemp == c)
02948                 return pTemp;
02949         }
02950 
02951         return pEnd;
02952     }
02953 
02954 
02955     // CharTypeStringRFind
02956     // Specialized value_type version of STL find() function in reverse.
02957     template <typename T, typename Allocator>
02958     const typename basic_string<T, Allocator>::value_type*
02959     basic_string<T, Allocator>::CharTypeStringRFind(const value_type* pRBegin, const value_type* pREnd, const value_type c)
02960     {
02961         while(pRBegin > pREnd)
02962         {
02963             if(*(pRBegin - 1) == c)
02964                 return pRBegin;
02965             --pRBegin;
02966         }
02967         return pREnd;
02968     }
02969 
02970 
02971     // CharTypeStringSearch
02972     // Specialized value_type version of STL search() function.
02973     // Purpose: find p2 within p1. Return p1End if not found or if either string is zero length.
02974     template <typename T, typename Allocator>
02975     const typename basic_string<T, Allocator>::value_type*
02976     basic_string<T, Allocator>::CharTypeStringSearch(const value_type* p1Begin, const value_type* p1End,
02977                                                      const value_type* p2Begin, const value_type* p2End)
02978     {
02979         // Test for zero length strings, in which case we have a match or a failure,
02980         // but the return value is the same either way.
02981         if((p1Begin == p1End) || (p2Begin == p2End))
02982             return p1Begin;
02983 
02984         // Test for a pattern of length 1.
02985         if((p2Begin + 1) == p2End)
02986             return eastl::find(p1Begin, p1End, *p2Begin);
02987 
02988         // General case.
02989         const value_type* pTemp;
02990         const value_type* pTemp1 = (p2Begin + 1);
02991         const value_type* pCurrent = p1Begin;
02992 
02993         while(p1Begin != p1End)
02994         {
02995             p1Begin = eastl::find(p1Begin, p1End, *p2Begin);
02996             if(p1Begin == p1End)
02997                 return p1End;
02998 
02999             pTemp = pTemp1;
03000             pCurrent = p1Begin;
03001             if(++pCurrent == p1End)
03002                 return p1End;
03003 
03004             while(*pCurrent == *pTemp)
03005             {
03006                 if(++pTemp == p2End)
03007                     return p1Begin;
03008                 if(++pCurrent == p1End)
03009                     return p1End;
03010             }
03011 
03012             ++p1Begin;
03013         }
03014 
03015         return p1Begin;
03016     }
03017 
03018 
03019     // CharTypeStringRSearch
03020     // Specialized value_type version of STL find_end() function (which really is a reverse search function).
03021     // Purpose: find last instance of p2 within p1. Return p1End if not found or if either string is zero length.
03022     template <typename T, typename Allocator>
03023     const typename basic_string<T, Allocator>::value_type*
03024     basic_string<T, Allocator>::CharTypeStringRSearch(const value_type* p1Begin, const value_type* p1End,
03025                                                       const value_type* p2Begin, const value_type* p2End)
03026     {
03027         // Test for zero length strings, in which case we have a match or a failure,
03028         // but the return value is the same either way.
03029         if((p1Begin == p1End) || (p2Begin == p2End))
03030             return p1Begin;
03031 
03032         // Test for a pattern of length 1.
03033         if((p2Begin + 1) == p2End)
03034             return CharTypeStringFindEnd(p1Begin, p1End, *p2Begin);
03035 
03036         // Test for search string length being longer than string length.
03037         if((p2End - p2Begin) > (p1End - p1Begin))
03038             return p1End;
03039 
03040         // General case.
03041         const value_type* pSearchEnd = (p1End - (p2End - p2Begin) + 1);
03042         const value_type* pCurrent1;
03043         const value_type* pCurrent2;
03044 
03045         while(pSearchEnd != p1Begin)
03046         {
03047             // Search for the last occurrence of *p2Begin.
03048             pCurrent1 = CharTypeStringFindEnd(p1Begin, pSearchEnd, *p2Begin);
03049             if(pCurrent1 == pSearchEnd) // If the first char of p2 wasn't found,
03050                 return p1End;           // then we immediately have failure.
03051 
03052             // In this case, *pTemp == *p2Begin. So compare the rest.
03053             pCurrent2 = p2Begin;
03054             while(*pCurrent1++ == *pCurrent2++)
03055             {
03056                 if(pCurrent2 == p2End)
03057                     return (pCurrent1 - (p2End - p2Begin));
03058             }
03059 
03060             // A smarter algorithm might know to subtract more than just one,
03061             // but in most cases it won't make much difference anyway.
03062             --pSearchEnd;
03063         }
03064 
03065         return p1End;
03066     }
03067 
03068 
03069     // CharTypeStringFindFirstOf
03070     // Specialized value_type version of STL find_first_of() function.
03071     // This function is much like the C runtime strtok function, except the strings aren't null-terminated.
03072     template <typename T, typename Allocator>
03073     const typename basic_string<T, Allocator>::value_type*
03074     basic_string<T, Allocator>::CharTypeStringFindFirstOf(const value_type* p1Begin, const value_type* p1End,
03075                                                           const value_type* p2Begin, const value_type* p2End)
03076     {
03077         for( ; p1Begin != p1End; ++p1Begin)
03078         {
03079             for(const value_type* pTemp = p2Begin; pTemp != p2End; ++pTemp)
03080             {
03081                 if(*p1Begin == *pTemp)
03082                     return p1Begin;
03083             }
03084         }
03085         return p1End;
03086     }
03087 
03088 
03089     // CharTypeStringRFindFirstOf
03090     // Specialized value_type version of STL find_first_of() function in reverse.
03091     // This function is much like the C runtime strtok function, except the strings aren't null-terminated.
03092     template <typename T, typename Allocator>
03093     const typename basic_string<T, Allocator>::value_type*
03094     basic_string<T, Allocator>::CharTypeStringRFindFirstOf(const value_type* p1RBegin, const value_type* p1REnd,
03095                                                            const value_type* p2Begin,  const value_type* p2End)
03096     {
03097         for( ; p1RBegin != p1REnd; --p1RBegin)
03098         {
03099             for(const value_type* pTemp = p2Begin; pTemp != p2End; ++pTemp)
03100             {
03101                 if(*(p1RBegin - 1) == *pTemp)
03102                     return p1RBegin;
03103             }
03104         }
03105         return p1REnd;
03106     }
03107 
03108 
03109 
03110     // CharTypeStringFindFirstNotOf
03111     // Specialized value_type version of STL find_first_not_of() function.
03112     template <typename T, typename Allocator>
03113     const typename basic_string<T, Allocator>::value_type*
03114     basic_string<T, Allocator>::CharTypeStringFindFirstNotOf(const value_type* p1Begin, const value_type* p1End,
03115                                                              const value_type* p2Begin, const value_type* p2End)
03116     {
03117         for( ; p1Begin != p1End; ++p1Begin)
03118         {
03119             const value_type* pTemp;
03120             for(pTemp = p2Begin; pTemp != p2End; ++pTemp)
03121             {
03122                 if(*p1Begin == *pTemp)
03123                     break;
03124             }
03125             if(pTemp == p2End)
03126                 return p1Begin;
03127         }
03128         return p1End;
03129     }
03130 
03131 
03132     // CharTypeStringRFindFirstNotOf
03133     // Specialized value_type version of STL find_first_not_of() function in reverse.
03134     template <typename T, typename Allocator>
03135     const typename basic_string<T, Allocator>::value_type*
03136     basic_string<T, Allocator>::CharTypeStringRFindFirstNotOf(const value_type* p1RBegin, const value_type* p1REnd,
03137                                                               const value_type* p2Begin,  const value_type* p2End)
03138     {
03139         for( ; p1RBegin != p1REnd; --p1RBegin)
03140         {
03141             const value_type* pTemp;
03142             for(pTemp = p2Begin; pTemp != p2End; ++pTemp)
03143             {
03144                 if(*(p1RBegin-1) == *pTemp)
03145                     break;
03146             }
03147             if(pTemp == p2End)
03148                 return p1RBegin;
03149         }
03150         return p1REnd;
03151     }
03152 
03153 
03154 
03155 
03156     // iterator operators
03157     template <typename T, typename Allocator>
03158     inline bool operator==(const typename basic_string<T, Allocator>::reverse_iterator& r1,
03159                            const typename basic_string<T, Allocator>::reverse_iterator& r2)
03160     {
03161         return r1.mpCurrent == r2.mpCurrent;
03162     }
03163 
03164 
03165     template <typename T, typename Allocator>
03166     inline bool operator!=(const typename basic_string<T, Allocator>::reverse_iterator& r1,
03167                            const typename basic_string<T, Allocator>::reverse_iterator& r2)
03168     {
03169         return r1.mpCurrent != r2.mpCurrent;
03170     }
03171 
03172 
03173     // Operator +
03174     template <typename T, typename Allocator>
03175     basic_string<T, Allocator> operator+(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03176     {
03177         typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
03178         CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
03179         basic_string<T, Allocator> result(cDNI, a.size() + b.size(), const_cast<basic_string<T, Allocator>&>(a).get_allocator()); // Note that we choose to assign a's allocator.
03180         result.append(a);
03181         result.append(b);
03182         return result;
03183     }
03184 
03185 
03186     template <typename T, typename Allocator>
03187     basic_string<T, Allocator> operator+(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03188     {
03189         typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
03190         CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
03191         const typename basic_string<T, Allocator>::size_type n = (typename basic_string<T, Allocator>::size_type)CharStrlen(p);
03192         basic_string<T, Allocator> result(cDNI, n + b.size(), const_cast<basic_string<T, Allocator>&>(b).get_allocator());
03193         result.append(p, p + n);
03194         result.append(b);
03195         return result;
03196     }
03197 
03198 
03199     template <typename T, typename Allocator>
03200     basic_string<T, Allocator> operator+(typename basic_string<T, Allocator>::value_type c, const basic_string<T, Allocator>& b)
03201     {
03202         typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
03203         CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
03204         basic_string<T, Allocator> result(cDNI, 1 + b.size(), const_cast<basic_string<T, Allocator>&>(b).get_allocator());
03205         result.push_back(c);
03206         result.append(b);
03207         return result;
03208     }
03209 
03210 
03211     template <typename T, typename Allocator>
03212     basic_string<T, Allocator> operator+(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03213     {
03214         typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
03215         CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
03216         const typename basic_string<T, Allocator>::size_type n = (typename basic_string<T, Allocator>::size_type)CharStrlen(p);
03217         basic_string<T, Allocator> result(cDNI, a.size() + n, const_cast<basic_string<T, Allocator>&>(a).get_allocator());
03218         result.append(a);
03219         result.append(p, p + n);
03220         return result;
03221     }
03222 
03223 
03224     template <typename T, typename Allocator>
03225     basic_string<T, Allocator> operator+(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type c)
03226     {
03227         typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
03228         CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
03229         basic_string<T, Allocator> result(cDNI, a.size() + 1, const_cast<basic_string<T, Allocator>&>(a).get_allocator());
03230         result.append(a);
03231         result.push_back(c);
03232         return result;
03233     }
03234 
03235 
03236     template <typename T, typename Allocator>
03237     inline bool basic_string<T, Allocator>::validate() const
03238     {
03239         if((mpBegin == NULL) || (mpEnd == NULL))
03240             return false;
03241         if(mpEnd < mpBegin)
03242             return false;
03243         if(mpCapacity < mpEnd)
03244             return false;
03245         return true;
03246     }
03247 
03248 
03249     template <typename T, typename Allocator>
03250     inline int basic_string<T, Allocator>::validate_iterator(const_iterator i) const
03251     {
03252         if(i >= mpBegin)
03253         {
03254             if(i < mpEnd)
03255                 return (isf_valid | isf_current | isf_can_dereference);
03256 
03257             if(i <= mpEnd)
03258                 return (isf_valid | isf_current);
03259         }
03260 
03261         return isf_none;
03262     }
03263 
03264 
03266     // global operators
03268 
03269     // Operator== and operator!=
03270     template <typename T, typename Allocator>
03271     inline bool operator==(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03272     {
03273         return ((a.size() == b.size()) && (memcmp(a.data(), b.data(), (size_t)a.size() * sizeof(typename basic_string<T, Allocator>::value_type)) == 0));
03274     }
03275 
03276 
03277     template <typename T, typename Allocator>
03278     inline bool operator==(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03279     {
03280         typedef typename basic_string<T, Allocator>::size_type size_type;
03281         const size_type n = (size_type)CharStrlen(p);
03282         return ((n == b.size()) && (memcmp(p, b.data(), (size_t)n * sizeof(*p)) == 0));
03283     }
03284 
03285 
03286     template <typename T, typename Allocator>
03287     inline bool operator==(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03288     {
03289         typedef typename basic_string<T, Allocator>::size_type size_type;
03290         const size_type n = (size_type)CharStrlen(p);
03291         return ((a.size() == n) && (memcmp(a.data(), p, (size_t)n * sizeof(*p)) == 0));
03292     }
03293 
03294 
03295     template <typename T, typename Allocator>
03296     inline bool operator!=(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03297     {
03298         return !(a == b);
03299     }
03300 
03301 
03302     template <typename T, typename Allocator>
03303     inline bool operator!=(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03304     {
03305         return !(p == b);
03306     }
03307 
03308 
03309     template <typename T, typename Allocator>
03310     inline bool operator!=(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03311     {
03312         return !(a == p);
03313     }
03314 
03315 
03316     // Operator< (and also >, <=, and >=).
03317     template <typename T, typename Allocator>
03318     inline bool operator<(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03319     {
03320         return basic_string<T, Allocator>::compare(a.begin(), a.end(), b.begin(), b.end()) < 0; }
03321 
03322 
03323     template <typename T, typename Allocator>
03324     inline bool operator<(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03325     {
03326         typedef typename basic_string<T, Allocator>::size_type size_type;
03327         const size_type n = (size_type)CharStrlen(p);
03328         return basic_string<T, Allocator>::compare(p, p + n, b.begin(), b.end()) < 0;
03329     }
03330 
03331 
03332     template <typename T, typename Allocator>
03333     inline bool operator<(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03334     {
03335         typedef typename basic_string<T, Allocator>::size_type size_type;
03336         const size_type n = (size_type)CharStrlen(p);
03337         return basic_string<T, Allocator>::compare(a.begin(), a.end(), p, p + n) < 0;
03338     }
03339 
03340 
03341     template <typename T, typename Allocator>
03342     inline bool operator>(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03343     {
03344         return b < a;
03345     }
03346 
03347 
03348     template <typename T, typename Allocator>
03349     inline bool operator>(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03350     {
03351         return b < p;
03352     }
03353 
03354 
03355     template <typename T, typename Allocator>
03356     inline bool operator>(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03357     {
03358         return p < a;
03359     }
03360 
03361 
03362     template <typename T, typename Allocator>
03363     inline bool operator<=(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03364     {
03365         return !(b < a);
03366     }
03367 
03368 
03369     template <typename T, typename Allocator>
03370     inline bool operator<=(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03371     {
03372         return !(b < p);
03373     }
03374 
03375 
03376     template <typename T, typename Allocator>
03377     inline bool operator<=(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03378     {
03379         return !(p < a);
03380     }
03381 
03382 
03383     template <typename T, typename Allocator>
03384     inline bool operator>=(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
03385     {
03386         return !(a < b);
03387     }
03388 
03389 
03390     template <typename T, typename Allocator>
03391     inline bool operator>=(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
03392     {
03393         return !(p < b);
03394     }
03395 
03396 
03397     template <typename T, typename Allocator>
03398     inline bool operator>=(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
03399     {
03400         return !(a < p);
03401     }
03402 
03403 
03404     template <typename T, typename Allocator>
03405     inline void swap(basic_string<T, Allocator>& a, basic_string<T, Allocator>& b)
03406     {
03407         a.swap(b);
03408     }
03409 
03410 
03412     typedef basic_string<char>    string;
03413     typedef basic_string<wchar_t> wstring;
03414 
03416     typedef basic_string<char8_t>  string8;
03417     typedef basic_string<char16_t> string16;
03418     typedef basic_string<char32_t> string32;
03419 
03420 
03421 
03430     template <typename T> struct hash;
03431 
03432     template <>
03433     struct hash<string>
03434     {
03435         size_t operator()(const string& x) const
03436         {
03437             const unsigned char* p = (const unsigned char*)x.c_str(); // To consider: limit p to at most 256 chars.
03438             unsigned int c, result = 2166136261U; // We implement an FNV-like string hash.
03439             while((c = *p++) != 0) // Using '!=' disables compiler warnings.
03440                 result = (result * 16777619) ^ c;
03441             return (size_t)result;
03442         }
03443     };
03444 
03447     template <>
03448     struct hash<wstring>
03449     {
03450         size_t operator()(const wstring& x) const
03451         {
03452             const wchar_t* p = (const wchar_t*)x.c_str(); // To consider: limit p to at most 256 chars.
03453             unsigned int c, result = 2166136261U; // We implement an FNV-like string hash.
03454             while((c = *p++) != 0) // Using '!=' disables compiler warnings.
03455                 result = (result * 16777619) ^ c;
03456             return (size_t)result;
03457         }
03458     };
03459 
03460 
03461 } // namespace eastl
03462 
03463 
03464 #ifdef _MSC_VER
03465     #pragma warning(pop)
03466 #endif
03467 
03468 #endif // EASTL_ABSTRACT_STRING_ENABLED
03469 
03470 #endif // Header include guard
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines