Index: base/strings/string_util.cc |
diff --git a/base/strings/string_util.cc b/base/strings/string_util.cc |
index 8f334da1890cfcfebd5213f80a7f0945b9e5d111..e084cb5597da6cbdcb50d0c3ce958bbc8dbc220e 100644 |
--- a/base/strings/string_util.cc |
+++ b/base/strings/string_util.cc |
@@ -454,8 +454,8 @@ bool LowerCaseEqualsASCII(string16::const_iterator a_begin, |
return DoLowerCaseEqualsASCII(a_begin, a_end, b); |
} |
-// TODO(jdduke): Remove guards after complete adoption of libc++ on Android. |
-#if !defined(OS_ANDROID) || !defined(USE_STLPORT) |
+// TODO(port): Resolve wchar_t/iterator issues that require OS_ANDROID here. |
+#if !defined(OS_ANDROID) |
bool LowerCaseEqualsASCII(const char* a_begin, |
const char* a_end, |
const char* b) { |
@@ -467,7 +467,8 @@ bool LowerCaseEqualsASCII(const char16* a_begin, |
const char* b) { |
return DoLowerCaseEqualsASCII(a_begin, a_end, b); |
} |
-#endif // !defined(OS_ANDROID) || !defined(USE_STLPORT) |
+ |
+#endif // !defined(OS_ANDROID) |
bool EqualsASCII(const string16& a, const base::StringPiece& b) { |
if (a.length() != b.length()) |
@@ -555,23 +556,103 @@ string16 FormatBytesUnlocalized(int64 bytes) { |
return base::ASCIIToUTF16(buf); |
} |
+// Runs in O(n) time in the length of |str|. |
template<class StringType> |
void DoReplaceSubstringsAfterOffset(StringType* str, |
- size_t start_offset, |
+ size_t offset, |
const StringType& find_this, |
const StringType& replace_with, |
bool replace_all) { |
- if ((start_offset == StringType::npos) || (start_offset >= str->length())) |
+ DCHECK(!find_this.empty()); |
+ |
+ // If the find string doesn't appear, there's nothing to do. |
+ offset = str->find(find_this, offset); |
+ if (offset == StringType::npos) |
return; |
- DCHECK(!find_this.empty()); |
- for (size_t offs(str->find(find_this, start_offset)); |
- offs != StringType::npos; offs = str->find(find_this, offs)) { |
- str->replace(offs, find_this.length(), replace_with); |
- offs += replace_with.length(); |
+ // If we're only replacing one instance, there's no need to do anything |
+ // complicated. |
+ size_t find_length = find_this.length(); |
+ if (!replace_all) { |
+ str->replace(offset, find_length, replace_with); |
+ return; |
+ } |
- if (!replace_all) |
- break; |
+ // If the find and replace strings are the same length, we can simply use |
+ // replace() on each instance, and finish the entire operation in O(n) time. |
+ size_t replace_length = replace_with.length(); |
+ if (find_length == replace_length) { |
+ do { |
+ str->replace(offset, find_length, replace_with); |
+ offset = str->find(find_this, offset + replace_length); |
+ } while (offset != StringType::npos); |
+ return; |
+ } |
+ |
+ // Since the find and replace strings aren't the same length, a loop like the |
+ // one above would be O(n^2) in the worst case, as replace() will shift the |
+ // entire remaining string each time. We need to be more clever to keep |
+ // things O(n). |
+ // |
+ // If we're shortening the string, we can alternate replacements with shifting |
+ // forward the intervening characters using memmove(). |
+ size_t str_length = str->length(); |
+ if (find_length > replace_length) { |
+ size_t write_offset = offset; |
+ do { |
+ if (replace_length) { |
+ str->replace(write_offset, replace_length, replace_with); |
+ write_offset += replace_length; |
+ } |
+ size_t read_offset = offset + find_length; |
+ offset = std::min(str->find(find_this, read_offset), str_length); |
+ size_t length = offset - read_offset; |
+ if (length) { |
+ memmove(&(*str)[write_offset], &(*str)[read_offset], |
+ length * sizeof(typename StringType::value_type)); |
+ write_offset += length; |
+ } |
+ } while (offset < str_length); |
+ str->resize(write_offset); |
+ return; |
+ } |
+ |
+ // We're lengthening the string. We can use alternating replacements and |
+ // memmove() calls like above, but we need to precalculate the final string |
+ // length and then expand from back-to-front to avoid overwriting the string |
+ // as we're reading it, needing to shift, or having to copy to a second string |
+ // temporarily. |
+ size_t first_match = offset; |
+ |
+ // First, calculate the final length and resize the string. |
+ size_t final_length = str_length; |
+ size_t expansion = replace_length - find_length; |
+ size_t current_match; |
+ do { |
+ final_length += expansion; |
+ // Minor optimization: save this offset into |current_match|, so that on |
+ // exit from the loop, |current_match| will point at the last instance of |
+ // the find string, and we won't need to find() it again immediately. |
+ current_match = offset; |
+ offset = str->find(find_this, offset + find_length); |
+ } while (offset != StringType::npos); |
+ str->resize(final_length); |
+ |
+ // Now do the replacement loop, working backwards through the string. |
+ for (size_t prev_match = str_length, write_offset = final_length; ; |
+ current_match = str->rfind(find_this, current_match - 1)) { |
+ size_t read_offset = current_match + find_length; |
+ size_t length = prev_match - read_offset; |
+ if (length) { |
+ write_offset -= length; |
+ memmove(&(*str)[write_offset], &(*str)[read_offset], |
+ length * sizeof(typename StringType::value_type)); |
+ } |
+ write_offset -= replace_length; |
+ str->replace(write_offset, replace_length, replace_with); |
+ if (current_match == first_match) |
+ return; |
+ prev_match = current_match; |
} |
} |