Sierra Toolkit  Version of the Day
string_eastl.h
1 /*
2 Copyright (C) 2005,2009-2010 Electronic Arts, Inc. All rights reserved.
3 
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 
8 1. Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of
14  its contributors may be used to endorse or promote products derived
15  from this software without specific prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 
30 // EASTL/string.h
31 // Written and maintained by Paul Pedriana - 2005.
33 
35 // Implements a basic_string class, much like the C++ std::basic_string.
36 // The primary distinctions between basic_string and std::basic_string are:
37 // - basic_string has a few extension functions that allow for increased performance.
38 // - basic_string has a few extension functions that make use easier,
39 // such as a member sprintf function and member tolower/toupper functions.
40 // - basic_string supports debug memory naming natively.
41 // - basic_string is easier to read, debug, and visualize.
42 // - basic_string internally manually expands basic functions such as begin(),
43 // size(), etc. in order to improve debug performance and optimizer success.
44 // - basic_string is savvy to an environment that doesn't have exception handling,
45 // as is sometimes the case with console or embedded environments.
46 // - basic_string has less deeply nested function calls and allows the user to
47 // enable forced inlining in debug builds in order to reduce bloat.
48 // - basic_string doesn't use char traits. As a result, EASTL assumes that
49 // strings will hold characters and not exotic things like widgets. At the
50 // very least, basic_string assumes that the value_type is a POD.
51 // - basic_string::size_type is defined as eastl_size_t instead of size_t in
52 // order to save memory and run faster on 64 bit systems.
53 // - basic_string data is guaranteed to be contiguous.
54 // - basic_string data is guaranteed to be 0-terminated, and the c_str() function
55 // is guaranteed to return the same pointer as the data() which is guaranteed
56 // to be the same value as &string[0].
57 // - basic_string has a set_capacity() function which frees excess capacity.
58 // The only way to do this with std::basic_string is via the cryptic non-obvious
59 // trick of using: basic_string<char>(x).swap(x);
60 // - basic_string has a force_size() function, which unilaterally moves the string
61 // end position (mpEnd) to the given location. Useful for when the user writes
62 // into the string via some extenal means such as C strcpy or sprintf.
64 
66 // Copy on Write (cow)
67 //
68 // This string implementation does not do copy on write (cow). This is by design,
69 // as cow penalizes 95% of string uses for the benefit of only 5% of the uses
70 // (these percentages are qualitative, not quantitative). The primary benefit of
71 // cow is that it allows for the sharing of string data between two string objects.
72 // Thus if you say this:
73 // string a("hello");
74 // string b(a);
75 // the "hello" will be shared between a and b. If you then say this:
76 // a = "world";
77 // then a will release its reference to "hello" and leave b with the only reference
78 // to it. Normally this functionality is accomplished via reference counting and
79 // with atomic operations or mutexes.
80 //
81 // The C++ standard does not say anything about basic_string and cow. However,
82 // for a basic_string implementation to be standards-conforming, a number of
83 // issues arise which dictate some things about how one would have to implement
84 // a cow string. The discussion of these issues will not be rehashed here, as you
85 // can read the references below for better detail than can be provided in the
86 // space we have here. However, we can say that the C++ standard is sensible and
87 // that anything we try to do here to allow for an efficient cow implementation
88 // would result in a generally unacceptable string interface.
89 //
90 // The disadvantages of cow strings are:
91 // - A reference count needs to exist with the string, which increases string memory usage.
92 // - With thread safety, atomic operations and mutex locks are expensive, especially
93 // on weaker memory systems such as console gaming platforms.
94 // - All non-const string accessor functions need to do a sharing check the the
95 // first such check needs to detach the string. Similarly, all string assignments
96 // need to do a sharing check as well. If you access the string before doing an
97 // assignment, the assignment doesn't result in a shared string, because the string
98 // has already been detached.
99 // - String sharing doesn't happen the large majority of the time. In some cases,
100 // the total sum of the reference count memory can exceed any memory savings
101 // gained by the strings that share representations.
102 //
103 // The addition of a string_cow class is under consideration for this library.
104 // There are conceivably some systems which have string usage patterns which would
105 // benefit from cow sharing. Such functionality is best saved for a separate string
106 // implementation so that the other string uses aren't penalized.
107 //
108 // References:
109 // This is a good starting HTML reference on the topic:
110 // http://www.gotw.ca/publications/optimizations.htm
111 // Here is a Usenet discussion on the topic:
112 // http://groups-beta.google.com/group/comp.lang.c++.moderated/browse_thread/thread/3dc6af5198d0bf7/886c8642cb06e03d
113 //
115 
116 
117 #ifndef EASTL_STRING_H
118 #define EASTL_STRING_H
119 
120 
121 #include <stk_util/util/config_eastl.h>
122 #if EASTL_ABSTRACT_STRING_ENABLED
123  #include <EASTL/bonus/string_abstract.h>
124 #else // 'else' encompasses the entire rest of this file.
125 #include <stk_util/util/allocator_eastl.h>
126 #include <stk_util/util/iterator_eastl.h>
127 #include <stk_util/util/algorithm_eastl.h>
128 
129 #ifdef _MSC_VER
130  #pragma warning(push, 0)
131 #endif
132 #include <stddef.h> // size_t, ptrdiff_t, etc.
133 #include <stdarg.h> // vararg functionality.
134 #include <stdlib.h> // malloc, free.
135 #include <stdio.h> // snprintf, etc.
136 #include <ctype.h> // toupper, etc.
137 #include <wchar.h> // toupper, etc.
138 #ifdef __MWERKS__
139  #include <../Include/string.h> // Force the compiler to use the std lib header.
140 #else
141  #include <string.h> // strlen, etc.
142 #endif
143 #ifdef _MSC_VER
144  #pragma warning(pop)
145 #endif
146 
147 #if EASTL_EXCEPTIONS_ENABLED
148  #ifdef _MSC_VER
149  #pragma warning(push, 0)
150  #endif
151  #include <stdexcept> // std::out_of_range, std::length_error.
152  #ifdef _MSC_VER
153  #pragma warning(pop)
154  #endif
155 #endif
156 
157 #ifdef _MSC_VER
158  #pragma warning(push)
159  #pragma warning(disable: 4530) // C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc
160  #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++.
161  #pragma warning(disable: 4480) // nonstandard extension used: specifying underlying type for enum
162 #endif
163 
164 
166 // EASTL_STRING_EXPLICIT
167 //
168 // See EASTL_STRING_OPT_EXPLICIT_CTORS for documentation.
169 //
170 #if EASTL_STRING_OPT_EXPLICIT_CTORS
171  #define EASTL_STRING_EXPLICIT explicit
172 #else
173  #define EASTL_STRING_EXPLICIT
174 #endif
175 
177 
178 
180 // EASTL_STRING_INITIAL_CAPACITY
181 //
182 // As of this writing, this must be > 0. Note that an initially empty string
183 // has a capacity of zero (it allocates no memory).
184 //
185 const eastl_size_t EASTL_STRING_INITIAL_CAPACITY = 8;
187 
188 
190 // Vsnprintf8 / Vsnprintf16
191 //
192 // The user is expected to supply these functions. Note that these functions
193 // are expected to accept parameters as per the C99 standard. These functions
194 // can deal with C99 standard return values or Microsoft non-standard return
195 // values but act more efficiently if implemented via the C99 style.
196 
197 extern int Vsnprintf8 (char8_t* pDestination, size_t n, const char8_t* pFormat, va_list arguments);
198 extern int Vsnprintf16(char16_t* pDestination, size_t n, const char16_t* pFormat, va_list arguments);
199 extern int Vsnprintf32(char32_t* pDestination, size_t n, const char32_t* pFormat, va_list arguments);
200 
201 namespace eastl
202 {
203  inline int Vsnprintf(char8_t* pDestination, size_t n, const char8_t* pFormat, va_list arguments)
204  { return Vsnprintf8(pDestination, n, pFormat, arguments); }
205 
206  inline int Vsnprintf(char16_t* pDestination, size_t n, const char16_t* pFormat, va_list arguments)
207  { return Vsnprintf16(pDestination, n, pFormat, arguments); }
208 
209  inline int Vsnprintf(char32_t* pDestination, size_t n, const char32_t* pFormat, va_list arguments)
210  { return Vsnprintf32(pDestination, n, pFormat, arguments); }
211 }
213 
214 
215 
216 namespace eastl
217 {
218 
223  #ifndef EASTL_BASIC_STRING_DEFAULT_NAME
224  #define EASTL_BASIC_STRING_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " basic_string" // Unless the user overrides something, this is "EASTL basic_string".
225  #endif
226 
227 
230  #ifndef EASTL_BASIC_STRING_DEFAULT_ALLOCATOR
231  #define EASTL_BASIC_STRING_DEFAULT_ALLOCATOR allocator_type(EASTL_BASIC_STRING_DEFAULT_NAME)
232  #endif
233 
234 
235 
241  {
242  uint32_t mUint32;
243  char mEmpty8[1];
244  unsigned char mEmptyU8[1];
245  signed char mEmptyS8[1];
246  char16_t mEmpty16[1];
247  char32_t mEmpty32[1];
248  };
249  extern EASTL_API EmptyString gEmptyString;
250 
251  inline const signed char* GetEmptyString(signed char) { return gEmptyString.mEmptyS8; }
252  inline const unsigned char* GetEmptyString(unsigned char) { return gEmptyString.mEmptyU8; }
253  inline const char* GetEmptyString(char) { return gEmptyString.mEmpty8; }
254  inline const char16_t* GetEmptyString(char16_t) { return gEmptyString.mEmpty16; }
255  inline const char32_t* GetEmptyString(char32_t) { return gEmptyString.mEmpty32; }
256 
257 
271  template <typename T, typename Allocator = EASTLAllocatorType>
273  {
274  public:
276  typedef T value_type;
277  typedef T* pointer;
278  typedef const T* const_pointer;
279  typedef T& reference;
280  typedef const T& const_reference;
281  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.
282  typedef const T* const_iterator;
285  typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to uint32_t.
286  typedef ptrdiff_t difference_type;
287  typedef Allocator allocator_type;
288 
289  #if defined(_MSC_VER) && (_MSC_VER >= 1400) // _MSC_VER of 1400 means VC8 (VS2005), 1500 means VC9 (VS2008)
290  enum : size_type { // Use Microsoft enum language extension, allowing for smaller debug symbols than using a static const. Users have been affected by this.
291  npos = (size_type)-1,
292  kMaxSize = (size_type)-2
293  };
294  #else
295  static const size_type npos = (size_type)-1;
296  static const size_type kMaxSize = (size_type)-2;
297  #endif
298 
299  enum
300  {
301  kAlignment = EASTL_ALIGN_OF(T),
302  kAlignmentOffset = 0
303  };
304 
305  public:
306  // CtorDoNotInitialize exists so that we can create a constructor that allocates but doesn't
307  // initialize and also doesn't collide with any other constructor declaration.
308  struct CtorDoNotInitialize{};
309 
310  // CtorSprintf exists so that we can create a constructor that accepts printf-style
311  // arguments but also doesn't collide with any other constructor declaration.
312  struct CtorSprintf{};
313 
314  protected:
315  value_type* mpBegin; // Begin of string.
316  value_type* mpEnd; // End of string. *mpEnd is always '0', as we 0-terminate our string. mpEnd is always < mpCapacity.
317  value_type* mpCapacity; // End of allocated space, including the space needed to store the trailing '0' char. mpCapacity is always at least mpEnd + 1.
318  allocator_type mAllocator; // To do: Use base class optimization to make this go away.
319 
320  public:
321  // Constructor, destructor
322  basic_string();
323  explicit basic_string(const allocator_type& allocator);
324  basic_string(const this_type& x, size_type position, size_type n = npos);
325  basic_string(const value_type* p, size_type n, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
326  EASTL_STRING_EXPLICIT basic_string(const value_type* p, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
327  basic_string(size_type n, value_type c, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
328  basic_string(const this_type& x);
329  basic_string(const value_type* pBegin, const value_type* pEnd, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
330  basic_string(CtorDoNotInitialize, size_type n, const allocator_type& allocator = EASTL_BASIC_STRING_DEFAULT_ALLOCATOR);
331  basic_string(CtorSprintf, const value_type* pFormat, ...);
332 
333  ~basic_string();
334 
335  // Allocator
336  const allocator_type& get_allocator() const;
337  allocator_type& get_allocator();
338  void set_allocator(const allocator_type& allocator);
339 
340  // Operator =
341  this_type& operator=(const this_type& x);
342  this_type& operator=(const value_type* p);
343  this_type& operator=(value_type c);
344 
345  void swap(this_type& x);
346 
347  // Assignment operations
348  basic_string& assign(const basic_string& x);
349  basic_string& assign(const basic_string& x, size_type position, size_type n);
350  basic_string& assign(const value_type* p, size_type n);
351  basic_string& assign(const value_type* p);
352  basic_string& assign(size_type n, value_type c);
353  basic_string& assign(const value_type* pBegin, const value_type* pEnd);
354 
355  // Iterators.
356  iterator begin(); // Expanded in source code as: mpBegin
357  const_iterator begin() const; // Expanded in source code as: mpBegin
358  iterator end(); // Expanded in source code as: mpEnd
359  const_iterator end() const; // Expanded in source code as: mpEnd
360 
361  reverse_iterator rbegin();
362  const_reverse_iterator rbegin() const;
363  reverse_iterator rend();
364  const_reverse_iterator rend() const;
365 
366  // Size-related functionality
367  bool empty() const; // Expanded in source code as: (mpBegin == mpEnd) or (mpBegin != mpEnd)
368  size_type size() const; // Expanded in source code as: (size_type)(mpEnd - mpBegin)
369  size_type length() const; // Expanded in source code as: (size_type)(mpEnd - mpBegin)
370  size_type max_size() const; // Expanded in source code as: kMaxSize
371  size_type capacity() const; // Expanded in source code as: (size_type)((mpCapacity - mpBegin) - 1)
372  void resize(size_type n, value_type c);
373  void resize(size_type n);
374  void reserve(size_type = 0);
375  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.
376  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.
377 
378  // Raw access
379  const value_type* data() const;
380  const value_type* c_str() const;
381 
382  // Element access
383  reference operator[](size_type n);
384  const_reference operator[](size_type n) const;
385  reference at(size_type n);
386  const_reference at(size_type n) const;
387  reference front();
388  const_reference front() const;
389  reference back();
390  const_reference back() const;
391 
392  // Append operations
393  basic_string& operator+=(const basic_string& x);
394  basic_string& operator+=(const value_type* p);
395  basic_string& operator+=(value_type c);
396 
397  basic_string& append(const basic_string& x);
398  basic_string& append(const basic_string& x, size_type position, size_type n);
399  basic_string& append(const value_type* p, size_type n);
400  basic_string& append(const value_type* p);
401  basic_string& append(size_type n, value_type c);
402  basic_string& append(const value_type* pBegin, const value_type* pEnd);
403 
404  basic_string& append_sprintf_va_list(const value_type* pFormat, va_list arguments);
405  basic_string& append_sprintf(const value_type* pFormat, ...);
406 
407  void push_back(value_type c);
408  void pop_back();
409 
410  // Insertion operations
411  basic_string& insert(size_type position, const basic_string& x);
412  basic_string& insert(size_type position, const basic_string& x, size_type beg, size_type n);
413  basic_string& insert(size_type position, const value_type* p, size_type n);
414  basic_string& insert(size_type position, const value_type* p);
415  basic_string& insert(size_type position, size_type n, value_type c);
416  iterator insert(iterator p, value_type c);
417  void insert(iterator p, size_type n, value_type c);
418  void insert(iterator p, const value_type* pBegin, const value_type* pEnd);
419 
420  // Erase operations
421  basic_string& erase(size_type position = 0, size_type n = npos);
422  iterator erase(iterator p);
423  iterator erase(iterator pBegin, iterator pEnd);
424  reverse_iterator erase(reverse_iterator position);
425  reverse_iterator erase(reverse_iterator first, reverse_iterator last);
426  void clear();
427  void reset(); // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs.
428 
429  //Replacement operations
430  basic_string& replace(size_type position, size_type n, const basic_string& x);
431  basic_string& replace(size_type pos1, size_type n1, const basic_string& x, size_type pos2, size_type n2);
432  basic_string& replace(size_type position, size_type n1, const value_type* p, size_type n2);
433  basic_string& replace(size_type position, size_type n1, const value_type* p);
434  basic_string& replace(size_type position, size_type n1, size_type n2, value_type c);
435  basic_string& replace(iterator first, iterator last, const basic_string& x);
436  basic_string& replace(iterator first, iterator last, const value_type* p, size_type n);
437  basic_string& replace(iterator first, iterator last, const value_type* p);
438  basic_string& replace(iterator first, iterator last, size_type n, value_type c);
439  basic_string& replace(iterator first, iterator last, const value_type* pBegin, const value_type* pEnd);
440  size_type copy(value_type* p, size_type n, size_type position = 0) const;
441 
442  // Find operations
443  size_type find(const basic_string& x, size_type position = 0) const;
444  size_type find(const value_type* p, size_type position = 0) const;
445  size_type find(const value_type* p, size_type position, size_type n) const;
446  size_type find(value_type c, size_type position = 0) const;
447 
448  // Reverse find operations
449  size_type rfind(const basic_string& x, size_type position = npos) const;
450  size_type rfind(const value_type* p, size_type position = npos) const;
451  size_type rfind(const value_type* p, size_type position, size_type n) const;
452  size_type rfind(value_type c, size_type position = npos) const;
453 
454  // Find first-of operations
455  size_type find_first_of(const basic_string& x, size_type position = 0) const;
456  size_type find_first_of(const value_type* p, size_type position = 0) const;
457  size_type find_first_of(const value_type* p, size_type position, size_type n) const;
458  size_type find_first_of(value_type c, size_type position = 0) const;
459 
460  // Find last-of operations
461  size_type find_last_of(const basic_string& x, size_type position = npos) const;
462  size_type find_last_of(const value_type* p, size_type position = npos) const;
463  size_type find_last_of(const value_type* p, size_type position, size_type n) const;
464  size_type find_last_of(value_type c, size_type position = npos) const;
465 
466  // Find first not-of operations
467  size_type find_first_not_of(const basic_string& x, size_type position = 0) const;
468  size_type find_first_not_of(const value_type* p, size_type position = 0) const;
469  size_type find_first_not_of(const value_type* p, size_type position, size_type n) const;
470  size_type find_first_not_of(value_type c, size_type position = 0) const;
471 
472  // Find last not-of operations
473  size_type find_last_not_of(const basic_string& x, size_type position = npos) const;
474  size_type find_last_not_of(const value_type* p, size_type position = npos) const;
475  size_type find_last_not_of(const value_type* p, size_type position, size_type n) const;
476  size_type find_last_not_of(value_type c, size_type position = npos) const;
477 
478  // Substring functionality
479  basic_string substr(size_type position = 0, size_type n = npos) const;
480 
481  // Comparison operations
482  int compare(const basic_string& x) const;
483  int compare(size_type pos1, size_type n1, const basic_string& x) const;
484  int compare(size_type pos1, size_type n1, const basic_string& x, size_type pos2, size_type n2) const;
485  int compare(const value_type* p) const;
486  int compare(size_type pos1, size_type n1, const value_type* p) const;
487  int compare(size_type pos1, size_type n1, const value_type* p, size_type n2) const;
488  static int compare(const value_type* pBegin1, const value_type* pEnd1, const value_type* pBegin2, const value_type* pEnd2);
489 
490  // 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.
491  int comparei(const basic_string& x) const;
492  int comparei(const value_type* p) const;
493  static int comparei(const value_type* pBegin1, const value_type* pEnd1, const value_type* pBegin2, const value_type* pEnd2);
494 
495  // Misc functionality, not part of C++ basic_string.
496  void make_lower();
497  void make_upper();
498  void ltrim();
499  void rtrim();
500  void trim();
501  basic_string left(size_type n) const;
502  basic_string right(size_type n) const;
503  basic_string& sprintf_va_list(const value_type* pFormat, va_list arguments);
504  basic_string& sprintf(const value_type* pFormat, ...);
505 
506  bool validate() const;
507  int validate_iterator(const_iterator i) const;
508 
509  protected:
510  // Helper functions for initialization/insertion operations.
511  value_type* DoAllocate(size_type n);
512  void DoFree(value_type* p, size_type n);
513  size_type GetNewCapacity(size_type currentCapacity);
514 
515  void AllocateSelf();
516  void AllocateSelf(size_type n);
517  void DeallocateSelf();
518  iterator InsertInternal(iterator p, value_type c);
519  void RangeInitialize(const value_type* pBegin, const value_type* pEnd);
520  void RangeInitialize(const value_type* pBegin);
521  void SizeInitialize(size_type n, value_type c);
522  void ThrowLengthException() const;
523  void ThrowRangeException() const;
524  void ThrowInvalidArgumentException() const;
525 
526  // Replacements for STL template functions.
527  static const value_type* CharTypeStringFindEnd(const value_type* pBegin, const value_type* pEnd, value_type c);
528  static const value_type* CharTypeStringRFind(const value_type* pRBegin, const value_type* pREnd, const value_type c);
529  static const value_type* CharTypeStringSearch(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
530  static const value_type* CharTypeStringRSearch(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
531  static const value_type* CharTypeStringFindFirstOf(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
532  static const value_type* CharTypeStringRFindFirstOf(const value_type* p1RBegin, const value_type* p1REnd, const value_type* p2Begin, const value_type* p2End);
533  static const value_type* CharTypeStringFindFirstNotOf(const value_type* p1Begin, const value_type* p1End, const value_type* p2Begin, const value_type* p2End);
534  static const value_type* CharTypeStringRFindFirstNotOf(const value_type* p1RBegin, const value_type* p1REnd, const value_type* p2Begin, const value_type* p2End);
535 
536  }; // basic_string
537 
538 
539 
540 
542  // 'char traits' functionality
543  //
544  inline char8_t CharToLower(char8_t c)
545  { return (char8_t)tolower((uint8_t)c); }
546 
547  inline char16_t CharToLower(char16_t c)
548  { if((unsigned)c <= 0xff) return (char16_t)tolower((uint8_t)c); return c; }
549 
550  inline char32_t CharToLower(char32_t c)
551  { if((unsigned)c <= 0xff) return (char32_t)tolower((uint8_t)c); return c; }
552 
553 
554 
555  inline char8_t CharToUpper(char8_t c)
556  { return (char8_t)toupper((uint8_t)c); }
557 
558  inline char16_t CharToUpper(char16_t c)
559  { if((unsigned)c <= 0xff) return (char16_t)toupper((uint8_t)c); return c; }
560 
561  inline char32_t CharToUpper(char32_t c)
562  { if((unsigned)c <= 0xff) return (char32_t)toupper((uint8_t)c); return c; }
563 
564 
565 
566  template <typename T>
567  int Compare(const T* p1, const T* p2, size_t n)
568  {
569  for(; n > 0; ++p1, ++p2, --n)
570  {
571  if(*p1 != *p2)
572  return (*p1 < *p2) ? -1 : 1;
573  }
574  return 0;
575  }
576 
577  inline int Compare(const char8_t* p1, const char8_t* p2, size_t n)
578  {
579  return memcmp(p1, p2, n);
580  }
581 
582  template <typename T>
583  inline int CompareI(const T* p1, const T* p2, size_t n)
584  {
585  for(; n > 0; ++p1, ++p2, --n)
586  {
587  const T c1 = CharToLower(*p1);
588  const T c2 = CharToLower(*p2);
589 
590  if(c1 != c2)
591  return (c1 < c2) ? -1 : 1;
592  }
593  return 0;
594  }
595 
596 
597  inline const char8_t* Find(const char8_t* p, char8_t c, size_t n)
598  {
599  return (const char8_t*)memchr(p, c, n);
600  }
601 
602  inline const char16_t* Find(const char16_t* p, char16_t c, size_t n)
603  {
604  for(; n > 0; --n, ++p)
605  {
606  if(*p == c)
607  return p;
608  }
609 
610  return NULL;
611  }
612 
613  inline const char32_t* Find(const char32_t* p, char32_t c, size_t n)
614  {
615  for(; n > 0; --n, ++p)
616  {
617  if(*p == c)
618  return p;
619  }
620 
621  return NULL;
622  }
623 
624 
625  inline size_t CharStrlen(const char8_t* p)
626  {
627  #ifdef _MSC_VER // VC++ can implement an instrinsic here.
628  return strlen(p);
629  #else
630  const char8_t* pCurrent = p;
631  while(*pCurrent)
632  ++pCurrent;
633  return (size_t)(pCurrent - p);
634  #endif
635  }
636 
637  inline size_t CharStrlen(const char16_t* p)
638  {
639  const char16_t* pCurrent = p;
640  while(*pCurrent)
641  ++pCurrent;
642  return (size_t)(pCurrent - p);
643  }
644 
645  inline size_t CharStrlen(const char32_t* p)
646  {
647  const char32_t* pCurrent = p;
648  while(*pCurrent)
649  ++pCurrent;
650  return (size_t)(pCurrent - p);
651  }
652 
653 
654  template <typename T>
655  inline T* CharStringUninitializedCopy(const T* pSource, const T* pSourceEnd, T* pDestination)
656  {
657  memmove(pDestination, pSource, (size_t)(pSourceEnd - pSource) * sizeof(T));
658  return pDestination + (pSourceEnd - pSource);
659  }
660 
661 
662 
663 
664  inline char8_t* CharStringUninitializedFillN(char8_t* pDestination, size_t n, const char8_t c)
665  {
666  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.
667  memset(pDestination, (uint8_t)c, (size_t)n);
668  return pDestination + n;
669  }
670 
671  inline char16_t* CharStringUninitializedFillN(char16_t* pDestination, size_t n, const char16_t c)
672  {
673  char16_t* pDest16 = pDestination;
674  const char16_t* const pEnd = pDestination + n;
675  while(pDest16 < pEnd)
676  *pDest16++ = c;
677  return pDestination + n;
678  }
679 
680  inline char32_t* CharStringUninitializedFillN(char32_t* pDestination, size_t n, const char32_t c)
681  {
682  char32_t* pDest32 = pDestination;
683  const char32_t* const pEnd = pDestination + n;
684  while(pDest32 < pEnd)
685  *pDest32++ = c;
686  return pDestination + n;
687  }
688 
689 
690 
691  inline char8_t* CharTypeAssignN(char8_t* pDestination, size_t n, char8_t c)
692  {
693  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.
694  return (char8_t*)memset(pDestination, c, (size_t)n);
695  return pDestination;
696  }
697 
698  inline char16_t* CharTypeAssignN(char16_t* pDestination, size_t n, char16_t c)
699  {
700  char16_t* pDest16 = pDestination;
701  const char16_t* const pEnd = pDestination + n;
702  while(pDest16 < pEnd)
703  *pDest16++ = c;
704  return pDestination;
705  }
706 
707  inline char32_t* CharTypeAssignN(char32_t* pDestination, size_t n, char32_t c)
708  {
709  char32_t* pDest32 = pDestination;
710  const char32_t* const pEnd = pDestination + n;
711  while(pDest32 < pEnd)
712  *pDest32++ = c;
713  return pDestination;
714  }
715 
716 
717 
719  // basic_string
721 
722  template <typename T, typename Allocator>
723  inline basic_string<T, Allocator>::basic_string()
724  : mpBegin(NULL),
725  mpEnd(NULL),
726  mpCapacity(NULL),
727  mAllocator(EASTL_BASIC_STRING_DEFAULT_NAME)
728  {
729  AllocateSelf();
730  }
731 
732 
733  template <typename T, typename Allocator>
734  inline basic_string<T, Allocator>::basic_string(const allocator_type& allocator)
735  : mpBegin(NULL),
736  mpEnd(NULL),
737  mpCapacity(NULL),
738  mAllocator(allocator)
739  {
740  AllocateSelf();
741  }
742 
743 
744  template <typename T, typename Allocator>
745  inline basic_string<T, Allocator>::basic_string(const this_type& x)
746  : mpBegin(NULL),
747  mpEnd(NULL),
748  mpCapacity(NULL),
749  mAllocator(x.mAllocator)
750  {
751  RangeInitialize(x.mpBegin, x.mpEnd);
752  }
753 
754 
755  template <typename T, typename Allocator>
756  basic_string<T, Allocator>::basic_string(const this_type& x, size_type position, size_type n)
757  : mpBegin(NULL),
758  mpEnd(NULL),
759  mpCapacity(NULL),
760  mAllocator(x.mAllocator)
761  {
762  #if EASTL_STRING_OPT_RANGE_ERRORS
763  if(EASTL_UNLIKELY(position > (size_type)(x.mpEnd - x.mpBegin)))
764  {
765  ThrowRangeException();
766  AllocateSelf();
767  }
768  else
769  RangeInitialize(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
770  #else
771  RangeInitialize(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
772  #endif
773  }
774 
775 
776  template <typename T, typename Allocator>
777  inline basic_string<T, Allocator>::basic_string(const value_type* p, size_type n, const allocator_type& allocator)
778  : mpBegin(NULL),
779  mpEnd(NULL),
780  mpCapacity(NULL),
781  mAllocator(allocator)
782  {
783  RangeInitialize(p, p + n);
784  }
785 
786 
787  template <typename T, typename Allocator>
788  inline basic_string<T, Allocator>::basic_string(const value_type* p, const allocator_type& allocator)
789  : mpBegin(NULL),
790  mpEnd(NULL),
791  mpCapacity(NULL),
792  mAllocator(allocator)
793  {
794  RangeInitialize(p);
795  }
796 
797 
798  template <typename T, typename Allocator>
799  inline basic_string<T, Allocator>::basic_string(size_type n, value_type c, const allocator_type& allocator)
800  : mpBegin(NULL),
801  mpEnd(NULL),
802  mpCapacity(NULL),
803  mAllocator(allocator)
804  {
805  SizeInitialize(n, c);
806  }
807 
808 
809  template <typename T, typename Allocator>
810  inline basic_string<T, Allocator>::basic_string(const value_type* pBegin, const value_type* pEnd, const allocator_type& allocator)
811  : mpBegin(NULL),
812  mpEnd(NULL),
813  mpCapacity(NULL),
814  mAllocator(allocator)
815  {
816  RangeInitialize(pBegin, pEnd);
817  }
818 
819 
820  // CtorDoNotInitialize exists so that we can create a version that allocates but doesn't
821  // initialize but also doesn't collide with any other constructor declaration.
822  template <typename T, typename Allocator>
823  basic_string<T, Allocator>::basic_string(CtorDoNotInitialize /*unused*/, size_type n, const allocator_type& allocator)
824  : mpBegin(NULL),
825  mpEnd(NULL),
826  mpCapacity(NULL),
827  mAllocator(allocator)
828  {
829  // Note that we do not call SizeInitialize here.
830  AllocateSelf(n + 1); // '+1' so that we have room for the terminating 0.
831  *mpEnd = 0;
832  }
833 
834 
835  // CtorSprintf exists so that we can create a version that does a variable argument
836  // sprintf but also doesn't collide with any other constructor declaration.
837  template <typename T, typename Allocator>
838  basic_string<T, Allocator>::basic_string(CtorSprintf /*unused*/, const value_type* pFormat, ...)
839  : mpBegin(NULL),
840  mpEnd(NULL),
841  mpCapacity(NULL),
842  mAllocator()
843  {
844  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.
845  AllocateSelf(n);
846 
847  va_list arguments;
848  va_start(arguments, pFormat);
849  append_sprintf_va_list(pFormat, arguments);
850  va_end(arguments);
851  }
852 
853 
854  template <typename T, typename Allocator>
855  inline basic_string<T, Allocator>::~basic_string()
856  {
857  DeallocateSelf();
858  }
859 
860 
861  template <typename T, typename Allocator>
862  inline const typename basic_string<T, Allocator>::allocator_type&
863  basic_string<T, Allocator>::get_allocator() const
864  {
865  return mAllocator;
866  }
867 
868 
869  template <typename T, typename Allocator>
870  inline typename basic_string<T, Allocator>::allocator_type&
871  basic_string<T, Allocator>::get_allocator()
872  {
873  return mAllocator;
874  }
875 
876 
877  template <typename T, typename Allocator>
878  inline void basic_string<T, Allocator>::set_allocator(const allocator_type& allocator)
879  {
880  mAllocator = allocator;
881  }
882 
883 
884  template <typename T, typename Allocator>
885  inline const typename basic_string<T, Allocator>::value_type*
886  basic_string<T, Allocator>::data() const
887  {
888  return mpBegin;
889  }
890 
891 
892  template <typename T, typename Allocator>
893  inline const typename basic_string<T, Allocator>::value_type*
894  basic_string<T, Allocator>::c_str() const
895  {
896  return mpBegin;
897  }
898 
899 
900  template <typename T, typename Allocator>
901  inline typename basic_string<T, Allocator>::iterator
902  basic_string<T, Allocator>::begin()
903  {
904  return mpBegin;
905  }
906 
907 
908  template <typename T, typename Allocator>
909  inline typename basic_string<T, Allocator>::iterator
910  basic_string<T, Allocator>::end()
911  {
912  return mpEnd;
913  }
914 
915 
916  template <typename T, typename Allocator>
917  inline typename basic_string<T, Allocator>::const_iterator
918  basic_string<T, Allocator>::begin() const
919  {
920  return mpBegin;
921  }
922 
923 
924  template <typename T, typename Allocator>
925  inline typename basic_string<T, Allocator>::const_iterator
926  basic_string<T, Allocator>::end() const
927  {
928  return mpEnd;
929  }
930 
931 
932  template <typename T, typename Allocator>
933  inline typename basic_string<T, Allocator>::reverse_iterator
934  basic_string<T, Allocator>::rbegin()
935  {
936  return reverse_iterator(mpEnd);
937  }
938 
939 
940  template <typename T, typename Allocator>
941  inline typename basic_string<T, Allocator>::reverse_iterator
942  basic_string<T, Allocator>::rend()
943  {
944  return reverse_iterator(mpBegin);
945  }
946 
947 
948  template <typename T, typename Allocator>
949  inline typename basic_string<T, Allocator>::const_reverse_iterator
950  basic_string<T, Allocator>::rbegin() const
951  {
952  return const_reverse_iterator(mpEnd);
953  }
954 
955 
956  template <typename T, typename Allocator>
957  inline typename basic_string<T, Allocator>::const_reverse_iterator
958  basic_string<T, Allocator>::rend() const
959  {
960  return const_reverse_iterator(mpBegin);
961  }
962 
963 
964  template <typename T, typename Allocator>
965  inline bool basic_string<T, Allocator>::empty() const
966  {
967  return (mpBegin == mpEnd);
968  }
969 
970 
971  template <typename T, typename Allocator>
972  inline typename basic_string<T, Allocator>::size_type
973  basic_string<T, Allocator>::size() const
974  {
975  return (size_type)(mpEnd - mpBegin);
976  }
977 
978 
979  template <typename T, typename Allocator>
980  inline typename basic_string<T, Allocator>::size_type
981  basic_string<T, Allocator>::length() const
982  {
983  return (size_type)(mpEnd - mpBegin);
984  }
985 
986 
987  template <typename T, typename Allocator>
988  inline typename basic_string<T, Allocator>::size_type
989  basic_string<T, Allocator>::max_size() const
990  {
991  return kMaxSize;
992  }
993 
994 
995  template <typename T, typename Allocator>
996  inline typename basic_string<T, Allocator>::size_type
997  basic_string<T, Allocator>::capacity() const
998  {
999  return (size_type)((mpCapacity - mpBegin) - 1); // '-1' because we pretend that we didn't allocate memory for the terminating 0.
1000  }
1001 
1002 
1003  template <typename T, typename Allocator>
1004  inline typename basic_string<T, Allocator>::const_reference
1005  basic_string<T, Allocator>::operator[](size_type n) const
1006  {
1007  #if EASTL_ASSERT_ENABLED // We allow the user to reference the trailing 0 char without asserting. Perhaps we shouldn't.
1008  if(EASTL_UNLIKELY(n > (static_cast<size_type>(mpEnd - mpBegin))))
1009  EASTL_FAIL_MSG("basic_string::operator[] -- out of range");
1010  #endif
1011 
1012  return mpBegin[n]; // Sometimes done as *(mpBegin + n)
1013  }
1014 
1015 
1016  template <typename T, typename Allocator>
1017  inline typename basic_string<T, Allocator>::reference
1018  basic_string<T, Allocator>::operator[](size_type n)
1019  {
1020  #if EASTL_ASSERT_ENABLED // We allow the user to reference the trailing 0 char without asserting. Perhaps we shouldn't.
1021  if(EASTL_UNLIKELY(n > (static_cast<size_type>(mpEnd - mpBegin))))
1022  EASTL_FAIL_MSG("basic_string::operator[] -- out of range");
1023  #endif
1024 
1025  return mpBegin[n]; // Sometimes done as *(mpBegin + n)
1026  }
1027 
1028 
1029  template <typename T, typename Allocator>
1030  inline typename basic_string<T, Allocator>::this_type& basic_string<T, Allocator>::operator=(const basic_string<T, Allocator>& x)
1031  {
1032  if(&x != this)
1033  {
1034  #if EASTL_ALLOCATOR_COPY_ENABLED
1035  mAllocator = x.mAllocator;
1036  #endif
1037 
1038  assign(x.mpBegin, x.mpEnd);
1039  }
1040  return *this;
1041  }
1042 
1043 
1044  template <typename T, typename Allocator>
1045  inline typename basic_string<T, Allocator>::this_type& basic_string<T, Allocator>::operator=(const value_type* p)
1046  {
1047  return assign(p, p + CharStrlen(p));
1048  }
1049 
1050 
1051  template <typename T, typename Allocator>
1052  inline typename basic_string<T, Allocator>::this_type& basic_string<T, Allocator>::operator=(value_type c)
1053  {
1054  return assign((size_type)1, c);
1055  }
1056 
1057 
1058  template <typename T, typename Allocator>
1059  void basic_string<T, Allocator>::resize(size_type n, value_type c)
1060  {
1061  const size_type s = (size_type)(mpEnd - mpBegin);
1062 
1063  if(n < s)
1064  erase(mpBegin + n, mpEnd);
1065  else if(n > s)
1066  append(n - s, c);
1067  }
1068 
1069 
1070  template <typename T, typename Allocator>
1071  void basic_string<T, Allocator>::resize(size_type n)
1072  {
1073  // C++ basic_string specifies that resize(n) is equivalent to resize(n, value_type()).
1074  // For built-in types, value_type() is the same as zero (value_type(0)).
1075  // We can improve the efficiency (especially for long strings) of this
1076  // string class by resizing without assigning to anything.
1077 
1078  const size_type s = (size_type)(mpEnd - mpBegin);
1079 
1080  if(n < s)
1081  erase(mpBegin + n, mpEnd);
1082  else if(n > s)
1083  {
1084  #if EASTL_STRING_OPT_CHAR_INIT
1085  append(n - s, value_type());
1086  #else
1087  append(n - s);
1088  #endif
1089  }
1090  }
1091 
1092 
1093  template <typename T, typename Allocator>
1094  void basic_string<T, Allocator>::reserve(size_type n)
1095  {
1096  #if EASTL_STRING_OPT_LENGTH_ERRORS
1097  if(EASTL_UNLIKELY(n > kMaxSize))
1098  ThrowLengthException();
1099  #endif
1100 
1101  // The C++ standard for basic_string doesn't specify if we should or shouldn't
1102  // downsize the container. The standard is overly vague in its description of reserve:
1103  // The member function reserve() is a directive that informs a
1104  // basic_string object of a planned change in size, so that it
1105  // can manage the storage allocation accordingly.
1106  // We will act like the vector container and preserve the contents of
1107  // the container and only reallocate if increasing the size. The user
1108  // can use the set_capacity function to reduce the capacity.
1109 
1110  n = eastl::max_alt(n, (size_type)(mpEnd - mpBegin)); // Calculate the new capacity, which needs to be >= container size.
1111 
1112  if(n >= (size_type)(mpCapacity - mpBegin)) // If there is something to do... // We use >= because mpCapacity accounts for the trailing zero.
1113  set_capacity(n);
1114  }
1115 
1116 
1117  template <typename T, typename Allocator>
1118  inline void basic_string<T, Allocator>::set_capacity(size_type n)
1119  {
1120  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.
1121  n = (size_type)(mpEnd - mpBegin);
1122  else if(n < (size_type)(mpEnd - mpBegin))
1123  mpEnd = mpBegin + n;
1124 
1125  if(n != (size_type)((mpCapacity - mpBegin) - 1)) // If there is any capacity change...
1126  {
1127  if(n)
1128  {
1129  pointer pNewBegin = DoAllocate(n + 1); // We need the + 1 to accomodate the trailing 0.
1130  pointer pNewEnd = pNewBegin;
1131 
1132  pNewEnd = CharStringUninitializedCopy(mpBegin, mpEnd, pNewBegin);
1133  *pNewEnd = 0;
1134 
1135  DeallocateSelf();
1136  mpBegin = pNewBegin;
1137  mpEnd = pNewEnd;
1138  mpCapacity = pNewBegin + (n + 1);
1139  }
1140  else
1141  {
1142  DeallocateSelf();
1143  AllocateSelf();
1144  }
1145  }
1146  }
1147 
1148 
1149  template <typename T, typename Allocator>
1150  inline void basic_string<T, Allocator>::force_size(size_type n)
1151  {
1152  #if EASTL_STRING_OPT_RANGE_ERRORS
1153  if(EASTL_UNLIKELY(n >= (size_type)(mpCapacity - mpBegin)))
1154  ThrowRangeException();
1155  #elif EASTL_ASSERT_ENABLED
1156  if(EASTL_UNLIKELY(n >= (size_type)(mpCapacity - mpBegin)))
1157  EASTL_FAIL_MSG("basic_string::force_size -- out of range");
1158  #endif
1159 
1160  mpEnd = mpBegin + n;
1161  }
1162 
1163 
1164  template <typename T, typename Allocator>
1165  inline void basic_string<T, Allocator>::clear()
1166  {
1167  if(mpBegin != mpEnd)
1168  {
1169  *mpBegin = value_type(0);
1170  mpEnd = mpBegin;
1171  }
1172  }
1173 
1174 
1175  template <typename T, typename Allocator>
1176  inline void basic_string<T, Allocator>::reset()
1177  {
1178  // The reset function is a special extension function which unilaterally
1179  // resets the container to an empty state without freeing the memory of
1180  // the contained objects. This is useful for very quickly tearing down a
1181  // container built into scratch memory.
1182  AllocateSelf();
1183  }
1184 
1185 
1186  template <typename T, typename Allocator>
1187  inline typename basic_string<T, Allocator>::const_reference
1188  basic_string<T, Allocator>::at(size_type n) const
1189  {
1190  #if EASTL_STRING_OPT_RANGE_ERRORS
1191  if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
1192  ThrowRangeException();
1193  #elif EASTL_ASSERT_ENABLED // We assert if the user references the trailing 0 char.
1194  if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
1195  EASTL_FAIL_MSG("basic_string::at -- out of range");
1196  #endif
1197 
1198  return mpBegin[n];
1199  }
1200 
1201 
1202  template <typename T, typename Allocator>
1203  inline typename basic_string<T, Allocator>::reference
1204  basic_string<T, Allocator>::at(size_type n)
1205  {
1206  #if EASTL_STRING_OPT_RANGE_ERRORS
1207  if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
1208  ThrowRangeException();
1209  #elif EASTL_ASSERT_ENABLED // We assert if the user references the trailing 0 char.
1210  if(EASTL_UNLIKELY(n >= (size_type)(mpEnd - mpBegin)))
1211  EASTL_FAIL_MSG("basic_string::at -- out of range");
1212  #endif
1213 
1214  return mpBegin[n];
1215  }
1216 
1217 
1218  template <typename T, typename Allocator>
1219  inline typename basic_string<T, Allocator>::reference
1220  basic_string<T, Allocator>::front()
1221  {
1222  #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1223  // We allow the user to reference the trailing 0 char without asserting.
1224  #elif EASTL_ASSERT_ENABLED
1225  if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
1226  EASTL_FAIL_MSG("basic_string::front -- empty string");
1227  #endif
1228 
1229  return *mpBegin;
1230  }
1231 
1232 
1233  template <typename T, typename Allocator>
1234  inline typename basic_string<T, Allocator>::const_reference
1235  basic_string<T, Allocator>::front() const
1236  {
1237  #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1238  // We allow the user to reference the trailing 0 char without asserting.
1239  #elif EASTL_ASSERT_ENABLED
1240  if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
1241  EASTL_FAIL_MSG("basic_string::front -- empty string");
1242  #endif
1243 
1244  return *mpBegin;
1245  }
1246 
1247 
1248  template <typename T, typename Allocator>
1249  inline typename basic_string<T, Allocator>::reference
1250  basic_string<T, Allocator>::back()
1251  {
1252  #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1253  // We allow the user to reference the trailing 0 char without asserting.
1254  #elif EASTL_ASSERT_ENABLED
1255  if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
1256  EASTL_FAIL_MSG("basic_string::back -- empty string");
1257  #endif
1258 
1259  return *(mpEnd - 1);
1260  }
1261 
1262 
1263  template <typename T, typename Allocator>
1264  inline typename basic_string<T, Allocator>::const_reference
1265  basic_string<T, Allocator>::back() const
1266  {
1267  #if EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1268  // We allow the user to reference the trailing 0 char without asserting.
1269  #elif EASTL_ASSERT_ENABLED
1270  if(EASTL_UNLIKELY(mpEnd <= mpBegin)) // We assert if the user references the trailing 0 char.
1271  EASTL_FAIL_MSG("basic_string::back -- empty string");
1272  #endif
1273 
1274  return *(mpEnd - 1);
1275  }
1276 
1277 
1278  template <typename T, typename Allocator>
1279  inline basic_string<T, Allocator>& basic_string<T, Allocator>::operator+=(const basic_string<T, Allocator>& x)
1280  {
1281  return append(x);
1282  }
1283 
1284 
1285  template <typename T, typename Allocator>
1286  inline basic_string<T, Allocator>& basic_string<T, Allocator>::operator+=(const value_type* p)
1287  {
1288  return append(p);
1289  }
1290 
1291 
1292  template <typename T, typename Allocator>
1293  inline basic_string<T, Allocator>& basic_string<T, Allocator>::operator+=(value_type c)
1294  {
1295  push_back(c);
1296  return *this;
1297  }
1298 
1299 
1300  template <typename T, typename Allocator>
1301  inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const basic_string<T, Allocator>& x)
1302  {
1303  return append(x.mpBegin, x.mpEnd);
1304  }
1305 
1306 
1307  template <typename T, typename Allocator>
1308  inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const basic_string<T, Allocator>& x, size_type position, size_type n)
1309  {
1310  #if EASTL_STRING_OPT_RANGE_ERRORS
1311  if(EASTL_UNLIKELY(position > (size_type)(x.mpEnd - x.mpBegin)))
1312  ThrowRangeException();
1313  #endif
1314 
1315  return append(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
1316  }
1317 
1318 
1319  template <typename T, typename Allocator>
1320  inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const value_type* p, size_type n)
1321  {
1322  return append(p, p + n);
1323  }
1324 
1325 
1326  template <typename T, typename Allocator>
1327  inline basic_string<T, Allocator>& basic_string<T, Allocator>::append(const value_type* p)
1328  {
1329  return append(p, p + CharStrlen(p));
1330  }
1331 
1332 
1333  template <typename T, typename Allocator>
1334  basic_string<T, Allocator>& basic_string<T, Allocator>::append(size_type n, value_type c)
1335  {
1336  const size_type s = (size_type)(mpEnd - mpBegin);
1337 
1338  #if EASTL_STRING_OPT_LENGTH_ERRORS
1339  if(EASTL_UNLIKELY((n > kMaxSize) || (s > (kMaxSize - n))))
1340  ThrowLengthException();
1341  #endif
1342 
1343  const size_type nCapacity = (size_type)((mpCapacity - mpBegin) - 1);
1344 
1345  if((s + n) > nCapacity)
1346  reserve(eastl::max_alt((size_type)GetNewCapacity(nCapacity), (size_type)(s + n)));
1347 
1348  if(n > 0)
1349  {
1350  CharStringUninitializedFillN(mpEnd + 1, n - 1, c);
1351  *mpEnd = c;
1352  mpEnd += n;
1353  *mpEnd = 0;
1354  }
1355 
1356  return *this;
1357  }
1358 
1359 
1360  template <typename T, typename Allocator>
1361  basic_string<T, Allocator>& basic_string<T, Allocator>::append(const value_type* pBegin, const value_type* pEnd)
1362  {
1363  if(pBegin != pEnd)
1364  {
1365  const size_type nOldSize = (size_type)(mpEnd - mpBegin);
1366  const size_type n = (size_type)(pEnd - pBegin);
1367 
1368  #if EASTL_STRING_OPT_LENGTH_ERRORS
1369  if(EASTL_UNLIKELY(((size_t)n > kMaxSize) || (nOldSize > (kMaxSize - n))))
1370  ThrowLengthException();
1371  #endif
1372 
1373  const size_type nCapacity = (size_type)((mpCapacity - mpBegin) - 1);
1374 
1375  if((nOldSize + n) > nCapacity)
1376  {
1377  const size_type nLength = eastl::max_alt((size_type)GetNewCapacity(nCapacity), (size_type)(nOldSize + n)) + 1; // + 1 to accomodate the trailing 0.
1378 
1379  pointer pNewBegin = DoAllocate(nLength);
1380  pointer pNewEnd = pNewBegin;
1381 
1382  pNewEnd = CharStringUninitializedCopy(mpBegin, mpEnd, pNewBegin);
1383  pNewEnd = CharStringUninitializedCopy(pBegin, pEnd, pNewEnd);
1384  *pNewEnd = 0;
1385 
1386  DeallocateSelf();
1387  mpBegin = pNewBegin;
1388  mpEnd = pNewEnd;
1389  mpCapacity = pNewBegin + nLength;
1390  }
1391  else
1392  {
1393  const value_type* pTemp = pBegin;
1394  ++pTemp;
1395  CharStringUninitializedCopy(pTemp, pEnd, mpEnd + 1);
1396  mpEnd[n] = 0;
1397  *mpEnd = *pBegin;
1398  mpEnd += n;
1399  }
1400  }
1401 
1402  return *this;
1403  }
1404 
1405 
1406  template <typename T, typename Allocator>
1407  basic_string<T, Allocator>& basic_string<T, Allocator>::append_sprintf_va_list(const value_type* pFormat, va_list arguments)
1408  {
1409  // From unofficial C89 extension documentation:
1410  // The vsnprintf returns the number of characters written into the array,
1411  // not counting the terminating null character, or a negative value
1412  // if count or more characters are requested to be generated.
1413  // An error can occur while converting a value for output.
1414 
1415  // From the C99 standard:
1416  // The vsnprintf function returns the number of characters that would have
1417  // been written had n been sufficiently large, not counting the terminating
1418  // null character, or a negative value if an encoding error occurred.
1419  // Thus, the null-terminated output has been completely written if and only
1420  // if the returned value is nonnegative and less than n.
1421  size_type nInitialSize = (size_type)(mpEnd - mpBegin);
1422  int nReturnValue;
1423 
1424  #if EASTL_VA_COPY_ENABLED
1425  va_list argumentsSaved;
1426  va_copy(argumentsSaved, arguments);
1427  #endif
1428 
1429  if(mpBegin == GetEmptyString(value_type())) // We need to do this because non-standard vsnprintf implementations will otherwise overwrite gEmptyString with a non-zero char.
1430  nReturnValue = eastl::Vsnprintf(mpEnd, 0, pFormat, arguments);
1431  else
1432  nReturnValue = eastl::Vsnprintf(mpEnd, (size_t)(mpCapacity - mpEnd), pFormat, arguments);
1433 
1434  if(nReturnValue >= (int)(mpCapacity - mpEnd)) // If there wasn't enough capacity...
1435  {
1436  // In this case we definitely have C99 Vsnprintf behaviour.
1437  #if EASTL_VA_COPY_ENABLED
1438  va_copy(arguments, argumentsSaved);
1439  #endif
1440  resize(nInitialSize + nReturnValue);
1441  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.
1442  }
1443  else if(nReturnValue < 0) // If vsnprintf is non-C99-standard (e.g. it is VC++ _vsnprintf)...
1444  {
1445  // In this case we either have C89 extension behaviour or C99 behaviour.
1446  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.
1447 
1448  for(; (nReturnValue < 0) && (n < 1000000); n *= 2)
1449  {
1450  #if EASTL_VA_COPY_ENABLED
1451  va_copy(arguments, argumentsSaved);
1452  #endif
1453  resize(n);
1454 
1455  const size_t nCapacity = (size_t)((n + 1) - nInitialSize);
1456  nReturnValue = eastl::Vsnprintf(mpBegin + nInitialSize, nCapacity, pFormat, arguments); // '+1' because vsnprintf wants to know the size of the buffer including the terminating zero.
1457 
1458  if(nReturnValue == (int)(unsigned)nCapacity)
1459  {
1460  resize(++n);
1461  nReturnValue = eastl::Vsnprintf(mpBegin + nInitialSize, nCapacity + 1, pFormat, arguments);
1462  }
1463  }
1464  }
1465 
1466  if(nReturnValue >= 0)
1467  mpEnd = mpBegin + nInitialSize + nReturnValue; // We are guaranteed from the above logic that mpEnd <= mpCapacity.
1468 
1469  return *this;
1470  }
1471 
1472  template <typename T, typename Allocator>
1473  basic_string<T, Allocator>& basic_string<T, Allocator>::append_sprintf(const value_type* pFormat, ...)
1474  {
1475  va_list arguments;
1476  va_start(arguments, pFormat);
1477  append_sprintf_va_list(pFormat, arguments);
1478  va_end(arguments);
1479 
1480  return *this;
1481  }
1482 
1483 
1484  template <typename T, typename Allocator>
1485  inline void basic_string<T, Allocator>::push_back(value_type c)
1486  {
1487  if((mpEnd + 1) == mpCapacity) // If we are out of space... (note that we test for + 1 because we have a trailing 0)
1488  reserve(eastl::max_alt(GetNewCapacity((size_type)((mpCapacity - mpBegin) - 1)), (size_type)(mpEnd - mpBegin) + 1));
1489  *mpEnd++ = c;
1490  *mpEnd = 0;
1491  }
1492 
1493 
1494  template <typename T, typename Allocator>
1495  inline void basic_string<T, Allocator>::pop_back()
1496  {
1497  #if EASTL_ASSERT_ENABLED
1498  if(EASTL_UNLIKELY(mpEnd <= mpBegin))
1499  EASTL_FAIL_MSG("basic_string::pop_back -- empty string");
1500  #endif
1501 
1502  mpEnd[-1] = value_type(0);
1503  --mpEnd;
1504  }
1505 
1506 
1507  template <typename T, typename Allocator>
1508  inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const basic_string<T, Allocator>& x)
1509  {
1510  return assign(x.mpBegin, x.mpEnd);
1511  }
1512 
1513 
1514  template <typename T, typename Allocator>
1515  inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const basic_string<T, Allocator>& x, size_type position, size_type n)
1516  {
1517  #if EASTL_STRING_OPT_RANGE_ERRORS
1518  if(EASTL_UNLIKELY(position > (size_type)(x.mpEnd - x.mpBegin)))
1519  ThrowRangeException();
1520  #endif
1521 
1522  return assign(x.mpBegin + position, x.mpBegin + position + eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - position));
1523  }
1524 
1525 
1526  template <typename T, typename Allocator>
1527  inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const value_type* p, size_type n)
1528  {
1529  return assign(p, p + n);
1530  }
1531 
1532 
1533  template <typename T, typename Allocator>
1534  inline basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const value_type* p)
1535  {
1536  return assign(p, p + CharStrlen(p));
1537  }
1538 
1539 
1540  template <typename T, typename Allocator>
1541  basic_string<T, Allocator>& basic_string<T, Allocator>::assign(size_type n, value_type c)
1542  {
1543  if(n <= (size_type)(mpEnd - mpBegin))
1544  {
1545  CharTypeAssignN(mpBegin, n, c);
1546  erase(mpBegin + n, mpEnd);
1547  }
1548  else
1549  {
1550  CharTypeAssignN(mpBegin, (size_type)(mpEnd - mpBegin), c);
1551  append(n - (size_type)(mpEnd - mpBegin), c);
1552  }
1553  return *this;
1554  }
1555 
1556 
1557  template <typename T, typename Allocator>
1558  basic_string<T, Allocator>& basic_string<T, Allocator>::assign(const value_type* pBegin, const value_type* pEnd)
1559  {
1560  const ptrdiff_t n = pEnd - pBegin;
1561  if(static_cast<size_type>(n) <= (size_type)(mpEnd - mpBegin))
1562  {
1563  memmove(mpBegin, pBegin, (size_t)n * sizeof(value_type));
1564  erase(mpBegin + n, mpEnd);
1565  }
1566  else
1567  {
1568  memmove(mpBegin, pBegin, (size_t)(mpEnd - mpBegin) * sizeof(value_type));
1569  append(pBegin + (size_type)(mpEnd - mpBegin), pEnd);
1570  }
1571  return *this;
1572  }
1573 
1574 
1575  template <typename T, typename Allocator>
1576  basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const basic_string<T, Allocator>& x)
1577  {
1578  #if EASTL_STRING_OPT_RANGE_ERRORS
1579  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1580  ThrowRangeException();
1581  #endif
1582 
1583  #if EASTL_STRING_OPT_LENGTH_ERRORS
1584  if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - (size_type)(x.mpEnd - x.mpBegin))))
1585  ThrowLengthException();
1586  #endif
1587 
1588  insert(mpBegin + position, x.mpBegin, x.mpEnd);
1589  return *this;
1590  }
1591 
1592 
1593  template <typename T, typename Allocator>
1594  basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const basic_string<T, Allocator>& x, size_type beg, size_type n)
1595  {
1596  #if EASTL_STRING_OPT_RANGE_ERRORS
1597  if(EASTL_UNLIKELY((position > (size_type)(mpEnd - mpBegin)) || (beg > (size_type)(x.mpEnd - x.mpBegin))))
1598  ThrowRangeException();
1599  #endif
1600 
1601  size_type nLength = eastl::min_alt(n, (size_type)(x.mpEnd - x.mpBegin) - beg);
1602 
1603  #if EASTL_STRING_OPT_LENGTH_ERRORS
1604  if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - nLength)))
1605  ThrowLengthException();
1606  #endif
1607 
1608  insert(mpBegin + position, x.mpBegin + beg, x.mpBegin + beg + nLength);
1609  return *this;
1610  }
1611 
1612 
1613  template <typename T, typename Allocator>
1614  basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const value_type* p, size_type n)
1615  {
1616  #if EASTL_STRING_OPT_RANGE_ERRORS
1617  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1618  ThrowRangeException();
1619  #endif
1620 
1621  #if EASTL_STRING_OPT_LENGTH_ERRORS
1622  if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - n)))
1623  ThrowLengthException();
1624  #endif
1625 
1626  insert(mpBegin + position, p, p + n);
1627  return *this;
1628  }
1629 
1630 
1631  template <typename T, typename Allocator>
1632  basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, const value_type* p)
1633  {
1634  #if EASTL_STRING_OPT_RANGE_ERRORS
1635  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1636  ThrowRangeException();
1637  #endif
1638 
1639  size_type nLength = (size_type)CharStrlen(p);
1640 
1641  #if EASTL_STRING_OPT_LENGTH_ERRORS
1642  if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - nLength)))
1643  ThrowLengthException();
1644  #endif
1645 
1646  insert(mpBegin + position, p, p + nLength);
1647  return *this;
1648  }
1649 
1650 
1651  template <typename T, typename Allocator>
1652  basic_string<T, Allocator>& basic_string<T, Allocator>::insert(size_type position, size_type n, value_type c)
1653  {
1654  #if EASTL_STRING_OPT_RANGE_ERRORS
1655  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1656  ThrowRangeException();
1657  #endif
1658 
1659  #if EASTL_STRING_OPT_LENGTH_ERRORS
1660  if(EASTL_UNLIKELY((size_type)(mpEnd - mpBegin) > (kMaxSize - n)))
1661  ThrowLengthException();
1662  #endif
1663 
1664  insert(mpBegin + position, n, c);
1665  return *this;
1666  }
1667 
1668 
1669  template <typename T, typename Allocator>
1670  inline typename basic_string<T, Allocator>::iterator
1671  basic_string<T, Allocator>::insert(iterator p, value_type c)
1672  {
1673  if(p == mpEnd)
1674  {
1675  push_back(c);
1676  return mpEnd - 1;
1677  }
1678  return InsertInternal(p, c);
1679  }
1680 
1681 
1682  template <typename T, typename Allocator>
1683  void basic_string<T, Allocator>::insert(iterator p, size_type n, value_type c)
1684  {
1685  #if EASTL_ASSERT_ENABLED
1686  if(EASTL_UNLIKELY((p < mpBegin) || (p > mpEnd)))
1687  EASTL_FAIL_MSG("basic_string::insert -- invalid position");
1688  #endif
1689 
1690  if(n) // If there is anything to insert...
1691  {
1692  if(size_type(mpCapacity - mpEnd) >= (n + 1)) // If we have enough capacity...
1693  {
1694  const size_type nElementsAfter = (size_type)(mpEnd - p);
1695  iterator pOldEnd = mpEnd;
1696 
1697  if(nElementsAfter >= n) // If there's enough space for the new chars between the insert position and the end...
1698  {
1699  CharStringUninitializedCopy((mpEnd - n) + 1, mpEnd + 1, mpEnd + 1);
1700  mpEnd += n;
1701  memmove(p + n, p, (size_t)((nElementsAfter - n) + 1) * sizeof(value_type));
1702  CharTypeAssignN(p, n, c);
1703  }
1704  else
1705  {
1706  CharStringUninitializedFillN(mpEnd + 1, n - nElementsAfter - 1, c);
1707  mpEnd += n - nElementsAfter;
1708 
1709  #if EASTL_EXCEPTIONS_ENABLED
1710  try
1711  {
1712  #endif
1713  CharStringUninitializedCopy(p, pOldEnd + 1, mpEnd);
1714  mpEnd += nElementsAfter;
1715  #if EASTL_EXCEPTIONS_ENABLED
1716  }
1717  catch(...)
1718  {
1719  mpEnd = pOldEnd;
1720  throw;
1721  }
1722  #endif
1723 
1724  CharTypeAssignN(p, nElementsAfter + 1, c);
1725  }
1726  }
1727  else
1728  {
1729  const size_type nOldSize = (size_type)(mpEnd - mpBegin);
1730  const size_type nOldCap = (size_type)((mpCapacity - mpBegin) - 1);
1731  const size_type nLength = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + n)) + 1; // + 1 to accomodate the trailing 0.
1732 
1733  iterator pNewBegin = DoAllocate(nLength);
1734  iterator pNewEnd = pNewBegin;
1735 
1736  pNewEnd = CharStringUninitializedCopy(mpBegin, p, pNewBegin);
1737  pNewEnd = CharStringUninitializedFillN(pNewEnd, n, c);
1738  pNewEnd = CharStringUninitializedCopy(p, mpEnd, pNewEnd);
1739  *pNewEnd = 0;
1740 
1741  DeallocateSelf();
1742  mpBegin = pNewBegin;
1743  mpEnd = pNewEnd;
1744  mpCapacity = pNewBegin + nLength;
1745  }
1746  }
1747  }
1748 
1749 
1750  template <typename T, typename Allocator>
1751  void basic_string<T, Allocator>::insert(iterator p, const value_type* pBegin, const value_type* pEnd)
1752  {
1753  #if EASTL_ASSERT_ENABLED
1754  if(EASTL_UNLIKELY((p < mpBegin) || (p > mpEnd)))
1755  EASTL_FAIL_MSG("basic_string::insert -- invalid position");
1756  #endif
1757 
1758  const size_type n = (size_type)(pEnd - pBegin);
1759 
1760  if(n)
1761  {
1762  const bool bCapacityIsSufficient = ((mpCapacity - mpEnd) >= (difference_type)(n + 1));
1763  const bool bSourceIsFromSelf = ((pEnd >= mpBegin) && (pBegin <= mpEnd));
1764 
1765  // If bSourceIsFromSelf is true, then we reallocate. This is because we are
1766  // inserting ourself into ourself and thus both the source and destination
1767  // be modified, making it rather tricky to attempt to do in place. The simplest
1768  // resolution is to reallocate. To consider: there may be a way to implement this
1769  // whereby we don't need to reallocate or can often avoid reallocating.
1770  if(bCapacityIsSufficient && !bSourceIsFromSelf)
1771  {
1772  const ptrdiff_t nElementsAfter = (mpEnd - p);
1773  iterator pOldEnd = mpEnd;
1774 
1775  if(nElementsAfter >= (ptrdiff_t)n) // If the newly inserted characters entirely fit within the size of the original string...
1776  {
1777  memmove(mpEnd + 1, mpEnd - n + 1, (size_t)n * sizeof(value_type));
1778  mpEnd += n;
1779  memmove(p + n, p, (size_t)((nElementsAfter - n) + 1) * sizeof(value_type));
1780  memmove(p, pBegin, (size_t)(pEnd - pBegin) * sizeof(value_type));
1781  }
1782  else
1783  {
1784  const value_type* const pMid = pBegin + (nElementsAfter + 1);
1785 
1786  memmove(mpEnd + 1, pMid, (size_t)(pEnd - pMid) * sizeof(value_type));
1787  mpEnd += n - nElementsAfter;
1788 
1789  #if EASTL_EXCEPTIONS_ENABLED
1790  try
1791  {
1792  #endif
1793  memmove(mpEnd, p, (size_t)(pOldEnd - p + 1) * sizeof(value_type));
1794  mpEnd += nElementsAfter;
1795  #if EASTL_EXCEPTIONS_ENABLED
1796  }
1797  catch(...)
1798  {
1799  mpEnd = pOldEnd;
1800  throw;
1801  }
1802  #endif
1803 
1804  memmove(p, pBegin, (size_t)(pMid - pBegin) * sizeof(value_type));
1805  }
1806  }
1807  else // Else we need to reallocate to implement this.
1808  {
1809  const size_type nOldSize = (size_type)(mpEnd - mpBegin);
1810  const size_type nOldCap = (size_type)((mpCapacity - mpBegin) - 1);
1811  size_type nLength;
1812 
1813  if(bCapacityIsSufficient) // If bCapacityIsSufficient is true, then bSourceIsFromSelf must be false.
1814  nLength = nOldSize + n + 1; // + 1 to accomodate the trailing 0.
1815  else
1816  nLength = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + n)) + 1; // + 1 to accomodate the trailing 0.
1817 
1818  pointer pNewBegin = DoAllocate(nLength);
1819  pointer pNewEnd = pNewBegin;
1820 
1821  pNewEnd = CharStringUninitializedCopy(mpBegin, p, pNewBegin);
1822  pNewEnd = CharStringUninitializedCopy(pBegin, pEnd, pNewEnd);
1823  pNewEnd = CharStringUninitializedCopy(p, mpEnd, pNewEnd);
1824  *pNewEnd = 0;
1825 
1826  DeallocateSelf();
1827  mpBegin = pNewBegin;
1828  mpEnd = pNewEnd;
1829  mpCapacity = pNewBegin + nLength;
1830  }
1831  }
1832  }
1833 
1834 
1835  template <typename T, typename Allocator>
1836  inline basic_string<T, Allocator>& basic_string<T, Allocator>::erase(size_type position, size_type n)
1837  {
1838  #if EASTL_STRING_OPT_RANGE_ERRORS
1839  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1840  ThrowRangeException();
1841  #endif
1842 
1843  #if EASTL_ASSERT_ENABLED
1844  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1845  EASTL_FAIL_MSG("basic_string::erase -- invalid position");
1846  #endif
1847 
1848  erase(mpBegin + position, mpBegin + position + eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position));
1849  return *this;
1850  }
1851 
1852 
1853  template <typename T, typename Allocator>
1854  inline typename basic_string<T, Allocator>::iterator
1855  basic_string<T, Allocator>::erase(iterator p)
1856  {
1857  #if EASTL_ASSERT_ENABLED
1858  if(EASTL_UNLIKELY((p < mpBegin) || (p >= mpEnd)))
1859  EASTL_FAIL_MSG("basic_string::erase -- invalid position");
1860  #endif
1861 
1862  memmove(p, p + 1, (size_t)(mpEnd - p) * sizeof(value_type));
1863  --mpEnd;
1864  return p;
1865  }
1866 
1867 
1868  template <typename T, typename Allocator>
1869  typename basic_string<T, Allocator>::iterator
1870  basic_string<T, Allocator>::erase(iterator pBegin, iterator pEnd)
1871  {
1872  #if EASTL_ASSERT_ENABLED
1873  if(EASTL_UNLIKELY((pBegin < mpBegin) || (pBegin > mpEnd) || (pEnd < mpBegin) || (pEnd > mpEnd) || (pEnd < pBegin)))
1874  EASTL_FAIL_MSG("basic_string::erase -- invalid position");
1875  #endif
1876 
1877  if(pBegin != pEnd)
1878  {
1879  memmove(pBegin, pEnd, (size_t)((mpEnd - pEnd) + 1) * sizeof(value_type));
1880  const iterator pNewEnd = (mpEnd - (pEnd - pBegin));
1881  mpEnd = pNewEnd;
1882  }
1883  return pBegin;
1884  }
1885 
1886 
1887  template <typename T, typename Allocator>
1888  inline typename basic_string<T, Allocator>::reverse_iterator
1889  basic_string<T, Allocator>::erase(reverse_iterator position)
1890  {
1891  return reverse_iterator(erase((++position).base()));
1892  }
1893 
1894 
1895  template <typename T, typename Allocator>
1896  typename basic_string<T, Allocator>::reverse_iterator
1897  basic_string<T, Allocator>::erase(reverse_iterator first, reverse_iterator last)
1898  {
1899  return reverse_iterator(erase((++last).base(), (++first).base()));
1900  }
1901 
1902 
1903  template <typename T, typename Allocator>
1904  basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n, const basic_string<T, Allocator>& x)
1905  {
1906  #if EASTL_STRING_OPT_RANGE_ERRORS
1907  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1908  ThrowRangeException();
1909  #endif
1910 
1911  const size_type nLength = eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position);
1912 
1913  #if EASTL_STRING_OPT_LENGTH_ERRORS
1914  if(EASTL_UNLIKELY(((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - (size_type)(x.mpEnd - x.mpBegin))))
1915  ThrowLengthException();
1916  #endif
1917 
1918  return replace(mpBegin + position, mpBegin + position + nLength, x.mpBegin, x.mpEnd);
1919  }
1920 
1921 
1922  template <typename T, typename Allocator>
1923  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)
1924  {
1925  #if EASTL_STRING_OPT_RANGE_ERRORS
1926  if(EASTL_UNLIKELY((pos1 > (size_type)(mpEnd - mpBegin)) || (pos2 > (size_type)(x.mpEnd - x.mpBegin))))
1927  ThrowRangeException();
1928  #endif
1929 
1930  const size_type nLength1 = eastl::min_alt(n1, (size_type)( mpEnd - mpBegin) - pos1);
1931  const size_type nLength2 = eastl::min_alt(n2, (size_type)(x.mpEnd - x.mpBegin) - pos2);
1932 
1933  #if EASTL_STRING_OPT_LENGTH_ERRORS
1934  if(EASTL_UNLIKELY(((size_type)(mpEnd - mpBegin) - nLength1) >= (kMaxSize - nLength2)))
1935  ThrowLengthException();
1936  #endif
1937 
1938  return replace(mpBegin + pos1, mpBegin + pos1 + nLength1, x.mpBegin + pos2, x.mpBegin + pos2 + nLength2);
1939  }
1940 
1941 
1942  template <typename T, typename Allocator>
1943  basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n1, const value_type* p, size_type n2)
1944  {
1945  #if EASTL_STRING_OPT_RANGE_ERRORS
1946  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1947  ThrowRangeException();
1948  #endif
1949 
1950  const size_type nLength = eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - position);
1951 
1952  #if EASTL_STRING_OPT_LENGTH_ERRORS
1953  if(EASTL_UNLIKELY((n2 > kMaxSize) || (((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - n2))))
1954  ThrowLengthException();
1955  #endif
1956 
1957  return replace(mpBegin + position, mpBegin + position + nLength, p, p + n2);
1958  }
1959 
1960 
1961  template <typename T, typename Allocator>
1962  basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n1, const value_type* p)
1963  {
1964  #if EASTL_STRING_OPT_RANGE_ERRORS
1965  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1966  ThrowRangeException();
1967  #endif
1968 
1969  const size_type nLength = eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - position);
1970 
1971  #if EASTL_STRING_OPT_LENGTH_ERRORS
1972  const size_type n2 = (size_type)CharStrlen(p);
1973  if(EASTL_UNLIKELY((n2 > kMaxSize) || (((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - n2))))
1974  ThrowLengthException();
1975  #endif
1976 
1977  return replace(mpBegin + position, mpBegin + position + nLength, p, p + CharStrlen(p));
1978  }
1979 
1980 
1981  template <typename T, typename Allocator>
1982  basic_string<T, Allocator>& basic_string<T, Allocator>::replace(size_type position, size_type n1, size_type n2, value_type c)
1983  {
1984  #if EASTL_STRING_OPT_RANGE_ERRORS
1985  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
1986  ThrowRangeException();
1987  #endif
1988 
1989  const size_type nLength = eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - position);
1990 
1991  #if EASTL_STRING_OPT_LENGTH_ERRORS
1992  if(EASTL_UNLIKELY((n2 > kMaxSize) || ((size_type)(mpEnd - mpBegin) - nLength) >= (kMaxSize - n2)))
1993  ThrowLengthException();
1994  #endif
1995 
1996  return replace(mpBegin + position, mpBegin + position + nLength, n2, c);
1997  }
1998 
1999 
2000  template <typename T, typename Allocator>
2001  inline basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, const basic_string<T, Allocator>& x)
2002  {
2003  return replace(pBegin, pEnd, x.mpBegin, x.mpEnd);
2004  }
2005 
2006 
2007  template <typename T, typename Allocator>
2008  inline basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, const value_type* p, size_type n)
2009  {
2010  return replace(pBegin, pEnd, p, p + n);
2011  }
2012 
2013 
2014  template <typename T, typename Allocator>
2015  inline basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, const value_type* p)
2016  {
2017  return replace(pBegin, pEnd, p, p + CharStrlen(p));
2018  }
2019 
2020 
2021  template <typename T, typename Allocator>
2022  basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin, iterator pEnd, size_type n, value_type c)
2023  {
2024  #if EASTL_ASSERT_ENABLED
2025  if(EASTL_UNLIKELY((pBegin < mpBegin) || (pBegin > mpEnd) || (pEnd < mpBegin) || (pEnd > mpEnd) || (pEnd < pBegin)))
2026  EASTL_FAIL_MSG("basic_string::replace -- invalid position");
2027  #endif
2028 
2029  const size_type nLength = static_cast<size_type>(pEnd - pBegin);
2030 
2031  if(nLength >= n)
2032  {
2033  CharTypeAssignN(pBegin, n, c);
2034  erase(pBegin + n, pEnd);
2035  }
2036  else
2037  {
2038  CharTypeAssignN(pBegin, nLength, c);
2039  insert(pEnd, n - nLength, c);
2040  }
2041  return *this;
2042  }
2043 
2044 
2045  template <typename T, typename Allocator>
2046  basic_string<T, Allocator>& basic_string<T, Allocator>::replace(iterator pBegin1, iterator pEnd1, const value_type* pBegin2, const value_type* pEnd2)
2047  {
2048  #if EASTL_ASSERT_ENABLED
2049  if(EASTL_UNLIKELY((pBegin1 < mpBegin) || (pBegin1 > mpEnd) || (pEnd1 < mpBegin) || (pEnd1 > mpEnd) || (pEnd1 < pBegin1)))
2050  EASTL_FAIL_MSG("basic_string::replace -- invalid position");
2051  #endif
2052 
2053  const size_type nLength1 = (size_type)(pEnd1 - pBegin1);
2054  const size_type nLength2 = (size_type)(pEnd2 - pBegin2);
2055 
2056  if(nLength1 >= nLength2) // If we have a non-expanding operation...
2057  {
2058  if((pBegin2 > pEnd1) || (pEnd2 <= pBegin1)) // If we have a non-overlapping operation...
2059  memcpy(pBegin1, pBegin2, (size_t)(pEnd2 - pBegin2) * sizeof(value_type));
2060  else
2061  memmove(pBegin1, pBegin2, (size_t)(pEnd2 - pBegin2) * sizeof(value_type));
2062  erase(pBegin1 + nLength2, pEnd1);
2063  }
2064  else // Else we are expanding.
2065  {
2066  if((pBegin2 > pEnd1) || (pEnd2 <= pBegin1)) // If we have a non-overlapping operation...
2067  {
2068  const value_type* const pMid2 = pBegin2 + nLength1;
2069 
2070  if((pEnd2 <= pBegin1) || (pBegin2 > pEnd1))
2071  memcpy(pBegin1, pBegin2, (size_t)(pMid2 - pBegin2) * sizeof(value_type));
2072  else
2073  memmove(pBegin1, pBegin2, (size_t)(pMid2 - pBegin2) * sizeof(value_type));
2074  insert(pEnd1, pMid2, pEnd2);
2075  }
2076  else // else we have an overlapping operation.
2077  {
2078  // I can't think of any easy way of doing this without allocating temporary memory.
2079  const size_type nOldSize = (size_type)(mpEnd - mpBegin);
2080  const size_type nOldCap = (size_type)((mpCapacity - mpBegin) - 1);
2081  const size_type nNewCapacity = eastl::max_alt((size_type)GetNewCapacity(nOldCap), (size_type)(nOldSize + (nLength2 - nLength1))) + 1; // + 1 to accomodate the trailing 0.
2082 
2083  pointer pNewBegin = DoAllocate(nNewCapacity);
2084  pointer pNewEnd = pNewBegin;
2085 
2086  pNewEnd = CharStringUninitializedCopy(mpBegin, pBegin1, pNewBegin);
2087  pNewEnd = CharStringUninitializedCopy(pBegin2, pEnd2, pNewEnd);
2088  pNewEnd = CharStringUninitializedCopy(pEnd1, mpEnd, pNewEnd);
2089  *pNewEnd = 0;
2090 
2091  DeallocateSelf();
2092  mpBegin = pNewBegin;
2093  mpEnd = pNewEnd;
2094  mpCapacity = pNewBegin + nNewCapacity;
2095  }
2096  }
2097  return *this;
2098  }
2099 
2100 
2101  template <typename T, typename Allocator>
2102  typename basic_string<T, Allocator>::size_type
2103  basic_string<T, Allocator>::copy(value_type* p, size_type n, size_type position) const
2104  {
2105  #if EASTL_STRING_OPT_RANGE_ERRORS
2106  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
2107  ThrowRangeException();
2108  #endif
2109 
2110  // It is not clear from the C++ standard if 'p' destination pointer is allowed to
2111  // refer to memory from within the string itself. We assume so and use memmove
2112  // instead of memcpy until we find otherwise.
2113  const size_type nLength = eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position);
2114  memmove(p, mpBegin + position, (size_t)nLength * sizeof(value_type));
2115  return nLength;
2116  }
2117 
2118 
2119  template <typename T, typename Allocator>
2120  void basic_string<T, Allocator>::swap(basic_string<T, Allocator>& x)
2121  {
2122  if(mAllocator == x.mAllocator) // If allocators are equivalent...
2123  {
2124  // We leave mAllocator as-is.
2125  eastl::swap(mpBegin, x.mpBegin);
2126  eastl::swap(mpEnd, x.mpEnd);
2127  eastl::swap(mpCapacity, x.mpCapacity);
2128  }
2129  else // else swap the contents.
2130  {
2131  const this_type temp(*this); // Can't call eastl::swap because that would
2132  *this = x; // itself call this member swap function.
2133  x = temp;
2134  }
2135  }
2136 
2137 
2138  template <typename T, typename Allocator>
2139  inline typename basic_string<T, Allocator>::size_type
2140  basic_string<T, Allocator>::find(const basic_string<T, Allocator>& x, size_type position) const
2141  {
2142  return find(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
2143  }
2144 
2145 
2146  template <typename T, typename Allocator>
2147  inline typename basic_string<T, Allocator>::size_type
2148  basic_string<T, Allocator>::find(const value_type* p, size_type position) const
2149  {
2150  return find(p, position, (size_type)CharStrlen(p));
2151  }
2152 
2153 
2154  #if defined(EA_PLATFORM_XENON) // If XBox 360...
2155 
2156  template <typename T, typename Allocator>
2157  typename basic_string<T, Allocator>::size_type
2158  basic_string<T, Allocator>::find(const value_type* p, size_type position, size_type n) const
2159  {
2160  const size_type nLength = (size_type)(mpEnd - mpBegin);
2161 
2162  if(n || (position > nLength))
2163  {
2164  if(position < nLength)
2165  {
2166  size_type nRemain = nLength - position;
2167 
2168  if(n <= nRemain)
2169  {
2170  nRemain -= (n - 1);
2171 
2172  for(const value_type* p1, *p2 = mpBegin + position;
2173  (p1 = Find(p2, *p, nRemain)) != 0;
2174  nRemain -= (p1 - p2) + 1, p2 = (p1 + 1))
2175  {
2176  if(Compare(p1, p, n) == 0)
2177  return (size_type)(p1 - mpBegin);
2178  }
2179  }
2180  }
2181 
2182  return npos;
2183  }
2184 
2185  return position;
2186  }
2187  #else
2188  template <typename T, typename Allocator>
2189  typename basic_string<T, Allocator>::size_type
2190  basic_string<T, Allocator>::find(const value_type* p, size_type position, size_type n) const
2191  {
2192  // It is not clear what the requirements are for position, but since the C++ standard
2193  // appears to be silent it is assumed for now that position can be any value.
2194  //#if EASTL_ASSERT_ENABLED
2195  // if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
2196  // EASTL_FAIL_MSG("basic_string::find -- invalid position");
2197  //#endif
2198 
2199  if(EASTL_LIKELY((position + n) <= (size_type)(mpEnd - mpBegin))) // If the range is valid...
2200  {
2201  const value_type* const pTemp = eastl::search(mpBegin + position, mpEnd, p, p + n);
2202 
2203  if((pTemp != mpEnd) || (n == 0))
2204  return (size_type)(pTemp - mpBegin);
2205  }
2206  return npos;
2207  }
2208  #endif
2209 
2210 
2211  template <typename T, typename Allocator>
2212  typename basic_string<T, Allocator>::size_type
2213  basic_string<T, Allocator>::find(value_type c, size_type position) const
2214  {
2215  // It is not clear what the requirements are for position, but since the C++ standard
2216  // appears to be silent it is assumed for now that position can be any value.
2217  //#if EASTL_ASSERT_ENABLED
2218  // if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
2219  // EASTL_FAIL_MSG("basic_string::find -- invalid position");
2220  //#endif
2221 
2222  if(EASTL_LIKELY(position < (size_type)(mpEnd - mpBegin))) // If the position is valid...
2223  {
2224  const const_iterator pResult = eastl::find(mpBegin + position, mpEnd, c);
2225 
2226  if(pResult != mpEnd)
2227  return (size_type)(pResult - mpBegin);
2228  }
2229  return npos;
2230  }
2231 
2232 
2233  template <typename T, typename Allocator>
2234  inline typename basic_string<T, Allocator>::size_type
2235  basic_string<T, Allocator>::rfind(const basic_string<T, Allocator>& x, size_type position) const
2236  {
2237  return rfind(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
2238  }
2239 
2240 
2241  template <typename T, typename Allocator>
2242  inline typename basic_string<T, Allocator>::size_type
2243  basic_string<T, Allocator>::rfind(const value_type* p, size_type position) const
2244  {
2245  return rfind(p, position, (size_type)CharStrlen(p));
2246  }
2247 
2248 
2249  template <typename T, typename Allocator>
2250  typename basic_string<T, Allocator>::size_type
2251  basic_string<T, Allocator>::rfind(const value_type* p, size_type position, size_type n) const
2252  {
2253  // Disabled because it's not clear what values are valid for position.
2254  // It is documented that npos is a valid value, though. We return npos and
2255  // don't crash if postion is any invalid value.
2256  //#if EASTL_ASSERT_ENABLED
2257  // if(EASTL_UNLIKELY((position != npos) && (position > (size_type)(mpEnd - mpBegin))))
2258  // EASTL_FAIL_MSG("basic_string::rfind -- invalid position");
2259  //#endif
2260 
2261  // Note that a search for a zero length string starting at position = end() returns end() and not npos.
2262  // Note by Paul Pedriana: I am not sure how this should behave in the case of n == 0 and position > size.
2263  // The standard seems to suggest that rfind doesn't act exactly the same as find in that input position
2264  // can be > size and the return value can still be other than npos. Thus, if n == 0 then you can
2265  // never return npos, unlike the case with find.
2266  const size_type nLength = (size_type)(mpEnd - mpBegin);
2267 
2268  if(EASTL_LIKELY(n <= nLength))
2269  {
2270  if(EASTL_LIKELY(n))
2271  {
2272  const const_iterator pEnd = mpBegin + eastl::min_alt(nLength - n, position) + n;
2273  const const_iterator pResult = CharTypeStringRSearch(mpBegin, pEnd, p, p + n);
2274 
2275  if(pResult != pEnd)
2276  return (size_type)(pResult - mpBegin);
2277  }
2278  else
2279  return eastl::min_alt(nLength, position);
2280  }
2281  return npos;
2282  }
2283 
2284 
2285  template <typename T, typename Allocator>
2286  typename basic_string<T, Allocator>::size_type
2287  basic_string<T, Allocator>::rfind(value_type c, size_type position) const
2288  {
2289  // If n is zero or position is >= size, we return npos.
2290  const size_type nLength = (size_type)(mpEnd - mpBegin);
2291 
2292  if(EASTL_LIKELY(nLength))
2293  {
2294  const value_type* const pEnd = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
2295  const value_type* const pResult = CharTypeStringRFind(pEnd, mpBegin, c);
2296 
2297  if(pResult != mpBegin)
2298  return (size_type)((pResult - 1) - mpBegin);
2299  }
2300  return npos;
2301  }
2302 
2303 
2304  template <typename T, typename Allocator>
2305  inline typename basic_string<T, Allocator>::size_type
2306  basic_string<T, Allocator>::find_first_of(const basic_string<T, Allocator>& x, size_type position) const
2307  {
2308  return find_first_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
2309  }
2310 
2311 
2312  template <typename T, typename Allocator>
2313  inline typename basic_string<T, Allocator>::size_type
2314  basic_string<T, Allocator>::find_first_of(const value_type* p, size_type position) const
2315  {
2316  return find_first_of(p, position, (size_type)CharStrlen(p));
2317  }
2318 
2319 
2320  #if defined(EA_PLATFORM_XENON) // If XBox 360...
2321 
2322  template <typename T, typename Allocator>
2323  typename basic_string<T, Allocator>::size_type
2324  basic_string<T, Allocator>::find_first_of(const value_type* p, size_type position, size_type n) const
2325  {
2326  // If position is >= size, we return npos.
2327  if(n && (position < (size_type)(mpEnd - mpBegin)))
2328  {
2329  for(const value_type* p1 = (mpBegin + position); p1 < mpEnd; ++p1)
2330  {
2331  if(Find(p, *p1, n) != 0)
2332  return (size_type)(p1 - mpBegin);
2333  }
2334  }
2335  return npos;
2336  }
2337  #else
2338  template <typename T, typename Allocator>
2339  typename basic_string<T, Allocator>::size_type
2340  basic_string<T, Allocator>::find_first_of(const value_type* p, size_type position, size_type n) const
2341  {
2342  // If position is >= size, we return npos.
2343  if(EASTL_LIKELY((position < (size_type)(mpEnd - mpBegin))))
2344  {
2345  const value_type* const pBegin = mpBegin + position;
2346  const const_iterator pResult = CharTypeStringFindFirstOf(pBegin, mpEnd, p, p + n);
2347 
2348  if(pResult != mpEnd)
2349  return (size_type)(pResult - mpBegin);
2350  }
2351  return npos;
2352  }
2353  #endif
2354 
2355 
2356  template <typename T, typename Allocator>
2357  inline typename basic_string<T, Allocator>::size_type
2358  basic_string<T, Allocator>::find_first_of(value_type c, size_type position) const
2359  {
2360  return find(c, position);
2361  }
2362 
2363 
2364  template <typename T, typename Allocator>
2365  inline typename basic_string<T, Allocator>::size_type
2366  basic_string<T, Allocator>::find_last_of(const basic_string<T, Allocator>& x, size_type position) const
2367  {
2368  return find_last_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
2369  }
2370 
2371 
2372  template <typename T, typename Allocator>
2373  inline typename basic_string<T, Allocator>::size_type
2374  basic_string<T, Allocator>::find_last_of(const value_type* p, size_type position) const
2375  {
2376  return find_last_of(p, position, (size_type)CharStrlen(p));
2377  }
2378 
2379 
2380  #if defined(EA_PLATFORM_XENON) // If XBox 360...
2381 
2382  template <typename T, typename Allocator>
2383  typename basic_string<T, Allocator>::size_type
2384  basic_string<T, Allocator>::find_last_of(const value_type* p, size_type position, size_type n) const
2385  {
2386  // If n is zero or position is >= size, we return npos.
2387  const size_type nLength = (size_type)(mpEnd - mpBegin);
2388 
2389  if(n && nLength)
2390  {
2391  const value_type* p1;
2392 
2393  if(position < nLength)
2394  p1 = mpBegin + position;
2395  else
2396  p1 = mpEnd - 1;
2397 
2398  for(;;)
2399  {
2400  if(Find(p, *p1, n))
2401  return (size_type)(p1 - mpBegin);
2402 
2403  if(p1-- == mpBegin)
2404  break;
2405  }
2406  }
2407 
2408  return npos;
2409  }
2410  #else
2411  template <typename T, typename Allocator>
2412  typename basic_string<T, Allocator>::size_type
2413  basic_string<T, Allocator>::find_last_of(const value_type* p, size_type position, size_type n) const
2414  {
2415  // If n is zero or position is >= size, we return npos.
2416  const size_type nLength = (size_type)(mpEnd - mpBegin);
2417 
2418  if(EASTL_LIKELY(nLength))
2419  {
2420  const value_type* const pEnd = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
2421  const value_type* const pResult = CharTypeStringRFindFirstOf(pEnd, mpBegin, p, p + n);
2422 
2423  if(pResult != mpBegin)
2424  return (size_type)((pResult - 1) - mpBegin);
2425  }
2426  return npos;
2427  }
2428  #endif
2429 
2430 
2431  template <typename T, typename Allocator>
2432  inline typename basic_string<T, Allocator>::size_type
2433  basic_string<T, Allocator>::find_last_of(value_type c, size_type position) const
2434  {
2435  return rfind(c, position);
2436  }
2437 
2438 
2439  template <typename T, typename Allocator>
2440  inline typename basic_string<T, Allocator>::size_type
2441  basic_string<T, Allocator>::find_first_not_of(const basic_string<T, Allocator>& x, size_type position) const
2442  {
2443  return find_first_not_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
2444  }
2445 
2446 
2447  template <typename T, typename Allocator>
2448  inline typename basic_string<T, Allocator>::size_type
2449  basic_string<T, Allocator>::find_first_not_of(const value_type* p, size_type position) const
2450  {
2451  return find_first_not_of(p, position, (size_type)CharStrlen(p));
2452  }
2453 
2454 
2455  template <typename T, typename Allocator>
2456  typename basic_string<T, Allocator>::size_type
2457  basic_string<T, Allocator>::find_first_not_of(const value_type* p, size_type position, size_type n) const
2458  {
2459  if(EASTL_LIKELY(position <= (size_type)(mpEnd - mpBegin)))
2460  {
2461  const const_iterator pResult = CharTypeStringFindFirstNotOf(mpBegin + position, mpEnd, p, p + n);
2462 
2463  if(pResult != mpEnd)
2464  return (size_type)(pResult - mpBegin);
2465  }
2466  return npos;
2467  }
2468 
2469 
2470  template <typename T, typename Allocator>
2471  typename basic_string<T, Allocator>::size_type
2472  basic_string<T, Allocator>::find_first_not_of(value_type c, size_type position) const
2473  {
2474  if(EASTL_LIKELY(position <= (size_type)(mpEnd - mpBegin)))
2475  {
2476  // Todo: Possibly make a specialized version of CharTypeStringFindFirstNotOf(pBegin, pEnd, c).
2477  const const_iterator pResult = CharTypeStringFindFirstNotOf(mpBegin + position, mpEnd, &c, &c + 1);
2478 
2479  if(pResult != mpEnd)
2480  return (size_type)(pResult - mpBegin);
2481  }
2482  return npos;
2483  }
2484 
2485 
2486  template <typename T, typename Allocator>
2487  inline typename basic_string<T, Allocator>::size_type
2488  basic_string<T, Allocator>::find_last_not_of(const basic_string<T, Allocator>& x, size_type position) const
2489  {
2490  return find_last_not_of(x.mpBegin, position, (size_type)(x.mpEnd - x.mpBegin));
2491  }
2492 
2493 
2494  template <typename T, typename Allocator>
2495  inline typename basic_string<T, Allocator>::size_type
2496  basic_string<T, Allocator>::find_last_not_of(const value_type* p, size_type position) const
2497  {
2498  return find_last_not_of(p, position, (size_type)CharStrlen(p));
2499  }
2500 
2501 
2502  template <typename T, typename Allocator>
2503  typename basic_string<T, Allocator>::size_type
2504  basic_string<T, Allocator>::find_last_not_of(const value_type* p, size_type position, size_type n) const
2505  {
2506  const size_type nLength = (size_type)(mpEnd - mpBegin);
2507 
2508  if(EASTL_LIKELY(nLength))
2509  {
2510  const value_type* const pEnd = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
2511  const value_type* const pResult = CharTypeStringRFindFirstNotOf(pEnd, mpBegin, p, p + n);
2512 
2513  if(pResult != mpBegin)
2514  return (size_type)((pResult - 1) - mpBegin);
2515  }
2516  return npos;
2517  }
2518 
2519 
2520  template <typename T, typename Allocator>
2521  typename basic_string<T, Allocator>::size_type
2522  basic_string<T, Allocator>::find_last_not_of(value_type c, size_type position) const
2523  {
2524  const size_type nLength = (size_type)(mpEnd - mpBegin);
2525 
2526  if(EASTL_LIKELY(nLength))
2527  {
2528  // Todo: Possibly make a specialized version of CharTypeStringRFindFirstNotOf(pBegin, pEnd, c).
2529  const value_type* const pEnd = mpBegin + eastl::min_alt(nLength - 1, position) + 1;
2530  const value_type* const pResult = CharTypeStringRFindFirstNotOf(pEnd, mpBegin, &c, &c + 1);
2531 
2532  if(pResult != mpBegin)
2533  return (size_type)((pResult - 1) - mpBegin);
2534  }
2535  return npos;
2536  }
2537 
2538 
2539  template <typename T, typename Allocator>
2540  inline basic_string<T, Allocator> basic_string<T, Allocator>::substr(size_type position, size_type n) const
2541  {
2542  #if EASTL_STRING_OPT_RANGE_ERRORS
2543  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
2544  ThrowRangeException();
2545  #elif EASTL_ASSERT_ENABLED
2546  if(EASTL_UNLIKELY(position > (size_type)(mpEnd - mpBegin)))
2547  EASTL_FAIL_MSG("basic_string::substr -- invalid position");
2548  #endif
2549 
2550  return basic_string(mpBegin + position, mpBegin + position + eastl::min_alt(n, (size_type)(mpEnd - mpBegin) - position), mAllocator);
2551  }
2552 
2553 
2554  template <typename T, typename Allocator>
2555  inline int basic_string<T, Allocator>::compare(const basic_string<T, Allocator>& x) const
2556  {
2557  return compare(mpBegin, mpEnd, x.mpBegin, x.mpEnd);
2558  }
2559 
2560 
2561  template <typename T, typename Allocator>
2562  inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const basic_string<T, Allocator>& x) const
2563  {
2564  #if EASTL_STRING_OPT_RANGE_ERRORS
2565  if(EASTL_UNLIKELY(pos1 > (size_type)(mpEnd - mpBegin)))
2566  ThrowRangeException();
2567  #endif
2568 
2569  return compare(mpBegin + pos1,
2570  mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
2571  x.mpBegin,
2572  x.mpEnd);
2573  }
2574 
2575 
2576  template <typename T, typename Allocator>
2577  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
2578  {
2579  #if EASTL_STRING_OPT_RANGE_ERRORS
2580  if(EASTL_UNLIKELY((pos1 > (size_type)(mpEnd - mpBegin)) || (pos2 > (size_type)(x.mpEnd - x.mpBegin))))
2581  ThrowRangeException();
2582  #endif
2583 
2584  return compare(mpBegin + pos1,
2585  mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
2586  x.mpBegin + pos2,
2587  x.mpBegin + pos2 + eastl::min_alt(n2, (size_type)(mpEnd - mpBegin) - pos2));
2588  }
2589 
2590 
2591  template <typename T, typename Allocator>
2592  inline int basic_string<T, Allocator>::compare(const value_type* p) const
2593  {
2594  return compare(mpBegin, mpEnd, p, p + CharStrlen(p));
2595  }
2596 
2597 
2598  template <typename T, typename Allocator>
2599  inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const value_type* p) const
2600  {
2601  #if EASTL_STRING_OPT_RANGE_ERRORS
2602  if(EASTL_UNLIKELY(pos1 > (size_type)(mpEnd - mpBegin)))
2603  ThrowRangeException();
2604  #endif
2605 
2606  return compare(mpBegin + pos1,
2607  mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
2608  p,
2609  p + CharStrlen(p));
2610  }
2611 
2612 
2613  template <typename T, typename Allocator>
2614  inline int basic_string<T, Allocator>::compare(size_type pos1, size_type n1, const value_type* p, size_type n2) const
2615  {
2616  #if EASTL_STRING_OPT_RANGE_ERRORS
2617  if(EASTL_UNLIKELY(pos1 > (size_type)(mpEnd - mpBegin)))
2618  ThrowRangeException();
2619  #endif
2620 
2621  return compare(mpBegin + pos1,
2622  mpBegin + pos1 + eastl::min_alt(n1, (size_type)(mpEnd - mpBegin) - pos1),
2623  p,
2624  p + n2);
2625  }
2626 
2627 
2628  // make_lower
2629  // This is a very simple ASCII-only case conversion function
2630  // Anything more complicated should use a more powerful separate library.
2631  template <typename T, typename Allocator>
2632  inline void basic_string<T, Allocator>::make_lower()
2633  {
2634  for(pointer p = mpBegin; p < mpEnd; ++p)
2635  *p = (value_type)CharToLower(*p);
2636  }
2637 
2638 
2639  // make_upper
2640  // This is a very simple ASCII-only case conversion function
2641  // Anything more complicated should use a more powerful separate library.
2642  template <typename T, typename Allocator>
2643  inline void basic_string<T, Allocator>::make_upper()
2644  {
2645  for(pointer p = mpBegin; p < mpEnd; ++p)
2646  *p = (value_type)CharToUpper(*p);
2647  }
2648 
2649 
2650  template <typename T, typename Allocator>
2651  inline void basic_string<T, Allocator>::ltrim()
2652  {
2653  const value_type array[] = { ' ', '\t', 0 }; // This is a pretty simplistic view of whitespace.
2654  erase(0, find_first_not_of(array));
2655  }
2656 
2657 
2658  template <typename T, typename Allocator>
2659  inline void basic_string<T, Allocator>::rtrim()
2660  {
2661  const value_type array[] = { ' ', '\t', 0 }; // This is a pretty simplistic view of whitespace.
2662  erase(find_last_not_of(array) + 1);
2663  }
2664 
2665 
2666  template <typename T, typename Allocator>
2667  inline void basic_string<T, Allocator>::trim()
2668  {
2669  ltrim();
2670  rtrim();
2671  }
2672 
2673 
2674  template <typename T, typename Allocator>
2675  inline basic_string<T, Allocator> basic_string<T, Allocator>::left(size_type n) const
2676  {
2677  const size_type nLength = length();
2678  if(n < nLength)
2679  return substr(0, n);
2680  return *this;
2681  }
2682 
2683 
2684  template <typename T, typename Allocator>
2685  inline basic_string<T, Allocator> basic_string<T, Allocator>::right(size_type n) const
2686  {
2687  const size_type nLength = length();
2688  if(n < nLength)
2689  return substr(nLength - n, n);
2690  return *this;
2691  }
2692 
2693 
2694  template <typename T, typename Allocator>
2695  inline basic_string<T, Allocator>& basic_string<T, Allocator>::sprintf(const value_type* pFormat, ...)
2696  {
2697  va_list arguments;
2698  va_start(arguments, pFormat);
2699  mpEnd = mpBegin; // Fast truncate to zero length.
2700  append_sprintf_va_list(pFormat, arguments);
2701  va_end(arguments);
2702 
2703  return *this;
2704  }
2705 
2706 
2707  template <typename T, typename Allocator>
2708  basic_string<T, Allocator>& basic_string<T, Allocator>::sprintf_va_list(const value_type* pFormat, va_list arguments)
2709  {
2710  mpEnd = mpBegin; // Fast truncate to zero length.
2711 
2712  return append_sprintf_va_list(pFormat, arguments);
2713  }
2714 
2715 
2716  template <typename T, typename Allocator>
2717  int basic_string<T, Allocator>::compare(const value_type* pBegin1, const value_type* pEnd1,
2718  const value_type* pBegin2, const value_type* pEnd2)
2719  {
2720  const ptrdiff_t n1 = pEnd1 - pBegin1;
2721  const ptrdiff_t n2 = pEnd2 - pBegin2;
2722  const ptrdiff_t nMin = eastl::min_alt(n1, n2);
2723  const int cmp = Compare(pBegin1, pBegin2, (size_t)nMin);
2724 
2725  return (cmp != 0 ? cmp : (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)));
2726  }
2727 
2728 
2729  template <typename T, typename Allocator>
2730  int basic_string<T, Allocator>::comparei(const value_type* pBegin1, const value_type* pEnd1,
2731  const value_type* pBegin2, const value_type* pEnd2)
2732  {
2733  const ptrdiff_t n1 = pEnd1 - pBegin1;
2734  const ptrdiff_t n2 = pEnd2 - pBegin2;
2735  const ptrdiff_t nMin = eastl::min_alt(n1, n2);
2736  const int cmp = CompareI(pBegin1, pBegin2, (size_t)nMin);
2737 
2738  return (cmp != 0 ? cmp : (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)));
2739  }
2740 
2741 
2742  template <typename T, typename Allocator>
2743  inline int basic_string<T, Allocator>::comparei(const basic_string<T, Allocator>& x) const
2744  {
2745  return comparei(mpBegin, mpEnd, x.mpBegin, x.mpEnd);
2746  }
2747 
2748 
2749  template <typename T, typename Allocator>
2750  inline int basic_string<T, Allocator>::comparei(const value_type* p) const
2751  {
2752  return comparei(mpBegin, mpEnd, p, p + CharStrlen(p));
2753  }
2754 
2755 
2756  template <typename T, typename Allocator>
2757  typename basic_string<T, Allocator>::iterator
2758  basic_string<T, Allocator>::InsertInternal(iterator p, value_type c)
2759  {
2760  iterator pNewPosition = p;
2761 
2762  if((mpEnd + 1) < mpCapacity)
2763  {
2764  *(mpEnd + 1) = 0;
2765  memmove(p + 1, p, (size_t)(mpEnd - p) * sizeof(value_type));
2766  *p = c;
2767  ++mpEnd;
2768  }
2769  else
2770  {
2771  const size_type nOldSize = (size_type)(mpEnd - mpBegin);
2772  const size_type nOldCap = (size_type)((mpCapacity - mpBegin) - 1);
2773  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.
2774 
2775  iterator pNewBegin = DoAllocate(nLength);
2776  iterator pNewEnd = pNewBegin;
2777 
2778  pNewPosition = CharStringUninitializedCopy(mpBegin, p, pNewBegin);
2779  *pNewPosition = c;
2780 
2781  pNewEnd = pNewPosition + 1;
2782  pNewEnd = CharStringUninitializedCopy(p, mpEnd, pNewEnd);
2783  *pNewEnd = 0;
2784 
2785  DeallocateSelf();
2786  mpBegin = pNewBegin;
2787  mpEnd = pNewEnd;
2788  mpCapacity = pNewBegin + nLength;
2789  }
2790  return pNewPosition;
2791  }
2792 
2793 
2794  template <typename T, typename Allocator>
2795  void basic_string<T, Allocator>::SizeInitialize(size_type n, value_type c)
2796  {
2797  AllocateSelf((size_type)(n + 1)); // '+1' so that we have room for the terminating 0.
2798 
2799  mpEnd = CharStringUninitializedFillN(mpBegin, n, c);
2800  *mpEnd = 0;
2801  }
2802 
2803 
2804  template <typename T, typename Allocator>
2805  void basic_string<T, Allocator>::RangeInitialize(const value_type* pBegin, const value_type* pEnd)
2806  {
2807  const size_type n = (size_type)(pEnd - pBegin);
2808 
2809  #if EASTL_STRING_OPT_ARGUMENT_ERRORS
2810  if(EASTL_UNLIKELY(!pBegin && (n != 0)))
2811  ThrowInvalidArgumentException();
2812  #endif
2813 
2814  AllocateSelf((size_type)(n + 1)); // '+1' so that we have room for the terminating 0.
2815 
2816  mpEnd = CharStringUninitializedCopy(pBegin, pEnd, mpBegin);
2817  *mpEnd = 0;
2818  }
2819 
2820 
2821  template <typename T, typename Allocator>
2822  inline void basic_string<T, Allocator>::RangeInitialize(const value_type* pBegin)
2823  {
2824  #if EASTL_STRING_OPT_ARGUMENT_ERRORS
2825  if(EASTL_UNLIKELY(!pBegin))
2826  ThrowInvalidArgumentException();
2827  #endif
2828 
2829  RangeInitialize(pBegin, pBegin + CharStrlen(pBegin));
2830  }
2831 
2832 
2833  template <typename T, typename Allocator>
2834  inline typename basic_string<T, Allocator>::value_type*
2835  basic_string<T, Allocator>::DoAllocate(size_type n)
2836  {
2837  EASTL_ASSERT(n > 1); // We want n > 1 because n == 1 is reserved for empty capacity and usage of gEmptyString.
2838  return (value_type*)EASTLAlloc(mAllocator, n * sizeof(value_type));
2839  }
2840 
2841 
2842  template <typename T, typename Allocator>
2843  inline void basic_string<T, Allocator>::DoFree(value_type* p, size_type n)
2844  {
2845  if(p)
2846  EASTLFree(mAllocator, p, n * sizeof(value_type));
2847  }
2848 
2849 
2850  template <typename T, typename Allocator>
2851  inline typename basic_string<T, Allocator>::size_type
2852  basic_string<T, Allocator>::GetNewCapacity(size_type currentCapacity) // This needs to return a value of at least currentCapacity and at least 1.
2853  {
2854  return (currentCapacity > EASTL_STRING_INITIAL_CAPACITY) ? (2 * currentCapacity) : EASTL_STRING_INITIAL_CAPACITY;
2855  }
2856 
2857 
2858  template <typename T, typename Allocator>
2859  inline void basic_string<T, Allocator>::AllocateSelf()
2860  {
2861  EASTL_ASSERT(gEmptyString.mUint32 == 0);
2862  mpBegin = const_cast<value_type*>(GetEmptyString(value_type())); // In const_cast-int this, we promise not to modify it.
2863  mpEnd = mpBegin;
2864  mpCapacity = mpBegin + 1; // When we are using gEmptyString, mpCapacity is always mpEnd + 1. This is an important distinguising characteristic.
2865  }
2866 
2867 
2868  template <typename T, typename Allocator>
2869  void basic_string<T, Allocator>::AllocateSelf(size_type n)
2870  {
2871  #if EASTL_ASSERT_ENABLED
2872  if(EASTL_UNLIKELY(n >= 0x40000000))
2873  EASTL_FAIL_MSG("basic_string::AllocateSelf -- improbably large request.");
2874  #endif
2875 
2876  #if EASTL_STRING_OPT_LENGTH_ERRORS
2877  if(EASTL_UNLIKELY(n > kMaxSize))
2878  ThrowLengthException();
2879  #endif
2880 
2881  if(n > 1)
2882  {
2883  mpBegin = DoAllocate(n);
2884  mpEnd = mpBegin;
2885  mpCapacity = mpBegin + n;
2886  }
2887  else
2888  AllocateSelf();
2889  }
2890 
2891 
2892  template <typename T, typename Allocator>
2893  inline void basic_string<T, Allocator>::DeallocateSelf()
2894  {
2895  // Note that we compare mpCapacity to mpEnd instead of comparing
2896  // mpBegin to &gEmptyString. This is important because we may have
2897  // a case whereby one library passes a string to another library to
2898  // deallocate and the two libraries have idependent versions of gEmptyString.
2899  if((mpCapacity - mpBegin) > 1) // If we are not using gEmptyString as our memory...
2900  DoFree(mpBegin, (size_type)(mpCapacity - mpBegin));
2901  }
2902 
2903 
2904  template <typename T, typename Allocator>
2905  inline void basic_string<T, Allocator>::ThrowLengthException() const
2906  {
2907  #if EASTL_EXCEPTIONS_ENABLED
2908  throw std::length_error("basic_string -- length_error");
2909  #elif EASTL_ASSERT_ENABLED
2910  EASTL_FAIL_MSG("basic_string -- length_error");
2911  #endif
2912  }
2913 
2914 
2915  template <typename T, typename Allocator>
2916  inline void basic_string<T, Allocator>::ThrowRangeException() const
2917  {
2918  #if EASTL_EXCEPTIONS_ENABLED
2919  throw std::out_of_range("basic_string -- out of range");
2920  #elif EASTL_ASSERT_ENABLED
2921  EASTL_FAIL_MSG("basic_string -- out of range");
2922  #endif
2923  }
2924 
2925 
2926  template <typename T, typename Allocator>
2927  inline void basic_string<T, Allocator>::ThrowInvalidArgumentException() const
2928  {
2929  #if EASTL_EXCEPTIONS_ENABLED
2930  throw std::invalid_argument("basic_string -- invalid argument");
2931  #elif EASTL_ASSERT_ENABLED
2932  EASTL_FAIL_MSG("basic_string -- invalid argument");
2933  #endif
2934  }
2935 
2936 
2937  // CharTypeStringFindEnd
2938  // Specialized char version of STL find() from back function.
2939  // Not the same as RFind because search range is specified as forward iterators.
2940  template <typename T, typename Allocator>
2941  const typename basic_string<T, Allocator>::value_type*
2942  basic_string<T, Allocator>::CharTypeStringFindEnd(const value_type* pBegin, const value_type* pEnd, value_type c)
2943  {
2944  const value_type* pTemp = pEnd;
2945  while(--pTemp >= pBegin)
2946  {
2947  if(*pTemp == c)
2948  return pTemp;
2949  }
2950 
2951  return pEnd;
2952  }
2953 
2954 
2955  // CharTypeStringRFind
2956  // Specialized value_type version of STL find() function in reverse.
2957  template <typename T, typename Allocator>
2958  const typename basic_string<T, Allocator>::value_type*
2959  basic_string<T, Allocator>::CharTypeStringRFind(const value_type* pRBegin, const value_type* pREnd, const value_type c)
2960  {
2961  while(pRBegin > pREnd)
2962  {
2963  if(*(pRBegin - 1) == c)
2964  return pRBegin;
2965  --pRBegin;
2966  }
2967  return pREnd;
2968  }
2969 
2970 
2971  // CharTypeStringSearch
2972  // Specialized value_type version of STL search() function.
2973  // Purpose: find p2 within p1. Return p1End if not found or if either string is zero length.
2974  template <typename T, typename Allocator>
2975  const typename basic_string<T, Allocator>::value_type*
2976  basic_string<T, Allocator>::CharTypeStringSearch(const value_type* p1Begin, const value_type* p1End,
2977  const value_type* p2Begin, const value_type* p2End)
2978  {
2979  // Test for zero length strings, in which case we have a match or a failure,
2980  // but the return value is the same either way.
2981  if((p1Begin == p1End) || (p2Begin == p2End))
2982  return p1Begin;
2983 
2984  // Test for a pattern of length 1.
2985  if((p2Begin + 1) == p2End)
2986  return eastl::find(p1Begin, p1End, *p2Begin);
2987 
2988  // General case.
2989  const value_type* pTemp;
2990  const value_type* pTemp1 = (p2Begin + 1);
2991  const value_type* pCurrent = p1Begin;
2992 
2993  while(p1Begin != p1End)
2994  {
2995  p1Begin = eastl::find(p1Begin, p1End, *p2Begin);
2996  if(p1Begin == p1End)
2997  return p1End;
2998 
2999  pTemp = pTemp1;
3000  pCurrent = p1Begin;
3001  if(++pCurrent == p1End)
3002  return p1End;
3003 
3004  while(*pCurrent == *pTemp)
3005  {
3006  if(++pTemp == p2End)
3007  return p1Begin;
3008  if(++pCurrent == p1End)
3009  return p1End;
3010  }
3011 
3012  ++p1Begin;
3013  }
3014 
3015  return p1Begin;
3016  }
3017 
3018 
3019  // CharTypeStringRSearch
3020  // Specialized value_type version of STL find_end() function (which really is a reverse search function).
3021  // Purpose: find last instance of p2 within p1. Return p1End if not found or if either string is zero length.
3022  template <typename T, typename Allocator>
3023  const typename basic_string<T, Allocator>::value_type*
3024  basic_string<T, Allocator>::CharTypeStringRSearch(const value_type* p1Begin, const value_type* p1End,
3025  const value_type* p2Begin, const value_type* p2End)
3026  {
3027  // Test for zero length strings, in which case we have a match or a failure,
3028  // but the return value is the same either way.
3029  if((p1Begin == p1End) || (p2Begin == p2End))
3030  return p1Begin;
3031 
3032  // Test for a pattern of length 1.
3033  if((p2Begin + 1) == p2End)
3034  return CharTypeStringFindEnd(p1Begin, p1End, *p2Begin);
3035 
3036  // Test for search string length being longer than string length.
3037  if((p2End - p2Begin) > (p1End - p1Begin))
3038  return p1End;
3039 
3040  // General case.
3041  const value_type* pSearchEnd = (p1End - (p2End - p2Begin) + 1);
3042  const value_type* pCurrent1;
3043  const value_type* pCurrent2;
3044 
3045  while(pSearchEnd != p1Begin)
3046  {
3047  // Search for the last occurrence of *p2Begin.
3048  pCurrent1 = CharTypeStringFindEnd(p1Begin, pSearchEnd, *p2Begin);
3049  if(pCurrent1 == pSearchEnd) // If the first char of p2 wasn't found,
3050  return p1End; // then we immediately have failure.
3051 
3052  // In this case, *pTemp == *p2Begin. So compare the rest.
3053  pCurrent2 = p2Begin;
3054  while(*pCurrent1++ == *pCurrent2++)
3055  {
3056  if(pCurrent2 == p2End)
3057  return (pCurrent1 - (p2End - p2Begin));
3058  }
3059 
3060  // A smarter algorithm might know to subtract more than just one,
3061  // but in most cases it won't make much difference anyway.
3062  --pSearchEnd;
3063  }
3064 
3065  return p1End;
3066  }
3067 
3068 
3069  // CharTypeStringFindFirstOf
3070  // Specialized value_type version of STL find_first_of() function.
3071  // This function is much like the C runtime strtok function, except the strings aren't null-terminated.
3072  template <typename T, typename Allocator>
3073  const typename basic_string<T, Allocator>::value_type*
3074  basic_string<T, Allocator>::CharTypeStringFindFirstOf(const value_type* p1Begin, const value_type* p1End,
3075  const value_type* p2Begin, const value_type* p2End)
3076  {
3077  for( ; p1Begin != p1End; ++p1Begin)
3078  {
3079  for(const value_type* pTemp = p2Begin; pTemp != p2End; ++pTemp)
3080  {
3081  if(*p1Begin == *pTemp)
3082  return p1Begin;
3083  }
3084  }
3085  return p1End;
3086  }
3087 
3088 
3089  // CharTypeStringRFindFirstOf
3090  // Specialized value_type version of STL find_first_of() function in reverse.
3091  // This function is much like the C runtime strtok function, except the strings aren't null-terminated.
3092  template <typename T, typename Allocator>
3093  const typename basic_string<T, Allocator>::value_type*
3094  basic_string<T, Allocator>::CharTypeStringRFindFirstOf(const value_type* p1RBegin, const value_type* p1REnd,
3095  const value_type* p2Begin, const value_type* p2End)
3096  {
3097  for( ; p1RBegin != p1REnd; --p1RBegin)
3098  {
3099  for(const value_type* pTemp = p2Begin; pTemp != p2End; ++pTemp)
3100  {
3101  if(*(p1RBegin - 1) == *pTemp)
3102  return p1RBegin;
3103  }
3104  }
3105  return p1REnd;
3106  }
3107 
3108 
3109 
3110  // CharTypeStringFindFirstNotOf
3111  // Specialized value_type version of STL find_first_not_of() function.
3112  template <typename T, typename Allocator>
3113  const typename basic_string<T, Allocator>::value_type*
3114  basic_string<T, Allocator>::CharTypeStringFindFirstNotOf(const value_type* p1Begin, const value_type* p1End,
3115  const value_type* p2Begin, const value_type* p2End)
3116  {
3117  for( ; p1Begin != p1End; ++p1Begin)
3118  {
3119  const value_type* pTemp;
3120  for(pTemp = p2Begin; pTemp != p2End; ++pTemp)
3121  {
3122  if(*p1Begin == *pTemp)
3123  break;
3124  }
3125  if(pTemp == p2End)
3126  return p1Begin;
3127  }
3128  return p1End;
3129  }
3130 
3131 
3132  // CharTypeStringRFindFirstNotOf
3133  // Specialized value_type version of STL find_first_not_of() function in reverse.
3134  template <typename T, typename Allocator>
3135  const typename basic_string<T, Allocator>::value_type*
3136  basic_string<T, Allocator>::CharTypeStringRFindFirstNotOf(const value_type* p1RBegin, const value_type* p1REnd,
3137  const value_type* p2Begin, const value_type* p2End)
3138  {
3139  for( ; p1RBegin != p1REnd; --p1RBegin)
3140  {
3141  const value_type* pTemp;
3142  for(pTemp = p2Begin; pTemp != p2End; ++pTemp)
3143  {
3144  if(*(p1RBegin-1) == *pTemp)
3145  break;
3146  }
3147  if(pTemp == p2End)
3148  return p1RBegin;
3149  }
3150  return p1REnd;
3151  }
3152 
3153 
3154 
3155 
3156  // iterator operators
3157  template <typename T, typename Allocator>
3158  inline bool operator==(const typename basic_string<T, Allocator>::reverse_iterator& r1,
3159  const typename basic_string<T, Allocator>::reverse_iterator& r2)
3160  {
3161  return r1.mpCurrent == r2.mpCurrent;
3162  }
3163 
3164 
3165  template <typename T, typename Allocator>
3166  inline bool operator!=(const typename basic_string<T, Allocator>::reverse_iterator& r1,
3167  const typename basic_string<T, Allocator>::reverse_iterator& r2)
3168  {
3169  return r1.mpCurrent != r2.mpCurrent;
3170  }
3171 
3172 
3173  // Operator +
3174  template <typename T, typename Allocator>
3175  basic_string<T, Allocator> operator+(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3176  {
3177  typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
3178  CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
3179  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.
3180  result.append(a);
3181  result.append(b);
3182  return result;
3183  }
3184 
3185 
3186  template <typename T, typename Allocator>
3187  basic_string<T, Allocator> operator+(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3188  {
3189  typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
3190  CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
3191  const typename basic_string<T, Allocator>::size_type n = (typename basic_string<T, Allocator>::size_type)CharStrlen(p);
3192  basic_string<T, Allocator> result(cDNI, n + b.size(), const_cast<basic_string<T, Allocator>&>(b).get_allocator());
3193  result.append(p, p + n);
3194  result.append(b);
3195  return result;
3196  }
3197 
3198 
3199  template <typename T, typename Allocator>
3200  basic_string<T, Allocator> operator+(typename basic_string<T, Allocator>::value_type c, const basic_string<T, Allocator>& b)
3201  {
3202  typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
3203  CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
3204  basic_string<T, Allocator> result(cDNI, 1 + b.size(), const_cast<basic_string<T, Allocator>&>(b).get_allocator());
3205  result.push_back(c);
3206  result.append(b);
3207  return result;
3208  }
3209 
3210 
3211  template <typename T, typename Allocator>
3212  basic_string<T, Allocator> operator+(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3213  {
3214  typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
3215  CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
3216  const typename basic_string<T, Allocator>::size_type n = (typename basic_string<T, Allocator>::size_type)CharStrlen(p);
3217  basic_string<T, Allocator> result(cDNI, a.size() + n, const_cast<basic_string<T, Allocator>&>(a).get_allocator());
3218  result.append(a);
3219  result.append(p, p + n);
3220  return result;
3221  }
3222 
3223 
3224  template <typename T, typename Allocator>
3225  basic_string<T, Allocator> operator+(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type c)
3226  {
3227  typedef typename basic_string<T, Allocator>::CtorDoNotInitialize CtorDoNotInitialize;
3228  CtorDoNotInitialize cDNI; // GCC 2.x forces us to declare a named temporary like this.
3229  basic_string<T, Allocator> result(cDNI, a.size() + 1, const_cast<basic_string<T, Allocator>&>(a).get_allocator());
3230  result.append(a);
3231  result.push_back(c);
3232  return result;
3233  }
3234 
3235 
3236  template <typename T, typename Allocator>
3237  inline bool basic_string<T, Allocator>::validate() const
3238  {
3239  if((mpBegin == NULL) || (mpEnd == NULL))
3240  return false;
3241  if(mpEnd < mpBegin)
3242  return false;
3243  if(mpCapacity < mpEnd)
3244  return false;
3245  return true;
3246  }
3247 
3248 
3249  template <typename T, typename Allocator>
3250  inline int basic_string<T, Allocator>::validate_iterator(const_iterator i) const
3251  {
3252  if(i >= mpBegin)
3253  {
3254  if(i < mpEnd)
3256 
3257  if(i <= mpEnd)
3258  return (isf_valid | isf_current);
3259  }
3260 
3261  return isf_none;
3262  }
3263 
3264 
3266  // global operators
3268 
3269  // Operator== and operator!=
3270  template <typename T, typename Allocator>
3271  inline bool operator==(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3272  {
3273  return ((a.size() == b.size()) && (memcmp(a.data(), b.data(), (size_t)a.size() * sizeof(typename basic_string<T, Allocator>::value_type)) == 0));
3274  }
3275 
3276 
3277  template <typename T, typename Allocator>
3278  inline bool operator==(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3279  {
3280  typedef typename basic_string<T, Allocator>::size_type size_type;
3281  const size_type n = (size_type)CharStrlen(p);
3282  return ((n == b.size()) && (memcmp(p, b.data(), (size_t)n * sizeof(*p)) == 0));
3283  }
3284 
3285 
3286  template <typename T, typename Allocator>
3287  inline bool operator==(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3288  {
3289  typedef typename basic_string<T, Allocator>::size_type size_type;
3290  const size_type n = (size_type)CharStrlen(p);
3291  return ((a.size() == n) && (memcmp(a.data(), p, (size_t)n * sizeof(*p)) == 0));
3292  }
3293 
3294 
3295  template <typename T, typename Allocator>
3296  inline bool operator!=(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3297  {
3298  return !(a == b);
3299  }
3300 
3301 
3302  template <typename T, typename Allocator>
3303  inline bool operator!=(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3304  {
3305  return !(p == b);
3306  }
3307 
3308 
3309  template <typename T, typename Allocator>
3310  inline bool operator!=(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3311  {
3312  return !(a == p);
3313  }
3314 
3315 
3316  // Operator< (and also >, <=, and >=).
3317  template <typename T, typename Allocator>
3318  inline bool operator<(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3319  {
3320  return basic_string<T, Allocator>::compare(a.begin(), a.end(), b.begin(), b.end()) < 0; }
3321 
3322 
3323  template <typename T, typename Allocator>
3324  inline bool operator<(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3325  {
3326  typedef typename basic_string<T, Allocator>::size_type size_type;
3327  const size_type n = (size_type)CharStrlen(p);
3328  return basic_string<T, Allocator>::compare(p, p + n, b.begin(), b.end()) < 0;
3329  }
3330 
3331 
3332  template <typename T, typename Allocator>
3333  inline bool operator<(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3334  {
3335  typedef typename basic_string<T, Allocator>::size_type size_type;
3336  const size_type n = (size_type)CharStrlen(p);
3337  return basic_string<T, Allocator>::compare(a.begin(), a.end(), p, p + n) < 0;
3338  }
3339 
3340 
3341  template <typename T, typename Allocator>
3342  inline bool operator>(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3343  {
3344  return b < a;
3345  }
3346 
3347 
3348  template <typename T, typename Allocator>
3349  inline bool operator>(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3350  {
3351  return b < p;
3352  }
3353 
3354 
3355  template <typename T, typename Allocator>
3356  inline bool operator>(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3357  {
3358  return p < a;
3359  }
3360 
3361 
3362  template <typename T, typename Allocator>
3363  inline bool operator<=(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3364  {
3365  return !(b < a);
3366  }
3367 
3368 
3369  template <typename T, typename Allocator>
3370  inline bool operator<=(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3371  {
3372  return !(b < p);
3373  }
3374 
3375 
3376  template <typename T, typename Allocator>
3377  inline bool operator<=(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3378  {
3379  return !(p < a);
3380  }
3381 
3382 
3383  template <typename T, typename Allocator>
3384  inline bool operator>=(const basic_string<T, Allocator>& a, const basic_string<T, Allocator>& b)
3385  {
3386  return !(a < b);
3387  }
3388 
3389 
3390  template <typename T, typename Allocator>
3391  inline bool operator>=(const typename basic_string<T, Allocator>::value_type* p, const basic_string<T, Allocator>& b)
3392  {
3393  return !(p < b);
3394  }
3395 
3396 
3397  template <typename T, typename Allocator>
3398  inline bool operator>=(const basic_string<T, Allocator>& a, const typename basic_string<T, Allocator>::value_type* p)
3399  {
3400  return !(a < p);
3401  }
3402 
3403 
3404  template <typename T, typename Allocator>
3405  inline void swap(basic_string<T, Allocator>& a, basic_string<T, Allocator>& b)
3406  {
3407  a.swap(b);
3408  }
3409 
3410 
3414 
3419 
3420 
3421 
3430  template <typename T> struct hash;
3431 
3432  template <>
3433  struct hash<string>
3434  {
3435  size_t operator()(const string& x) const
3436  {
3437  const unsigned char* p = (const unsigned char*)x.c_str(); // To consider: limit p to at most 256 chars.
3438  unsigned int c, result = 2166136261U; // We implement an FNV-like string hash.
3439  while((c = *p++) != 0) // Using '!=' disables compiler warnings.
3440  result = (result * 16777619) ^ c;
3441  return (size_t)result;
3442  }
3443  };
3444 
3447  template <>
3448  struct hash<wstring>
3449  {
3450  size_t operator()(const wstring& x) const
3451  {
3452  const wchar_t* p = (const wchar_t*)x.c_str(); // To consider: limit p to at most 256 chars.
3453  unsigned int c, result = 2166136261U; // We implement an FNV-like string hash.
3454  while((c = *p++) != 0) // Using '!=' disables compiler warnings.
3455  result = (result * 16777619) ^ c;
3456  return (size_t)result;
3457  }
3458  };
3459 
3460 
3461 } // namespace eastl
3462 
3463 
3464 #ifdef _MSC_VER
3465  #pragma warning(pop)
3466 #endif
3467 
3468 #endif // EASTL_ABSTRACT_STRING_ENABLED
3469 
3470 #endif // Header include guard
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
The iterator is valid and points to the same element it did when created. For example, if an iterator points to vector::begin() but an element is inserted at the front, the iterator is valid but not current. Modification of elements in place do not make iterators non-current.
void replace(ForwardIterator first, ForwardIterator last, const T &old_value, const T &new_value)
ForwardIterator1 find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
basic_string< char > string
string / wstring
const T & min_alt(const T &a, const T &b)
void swap(T &a, T &b)
basic_string< char8_t > string8
string8 / string16 / string32
static const size_type kMaxSize
&#39;npos&#39; means non-valid position or simply non-position.
Definition: string_eastl.h:296
const T & max_alt(const T &a, const T &b)
InputIterator find(InputIterator first, InputIterator last, const T &value)
The iterator is valid, which means it is in the range of [begin, end].
This is called none and not called invalid because it is not strictly the opposite of invalid...
EASTL_API EmptyString gEmptyString
EA Standard Template Library.
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...
Definition: Part.cpp:85