OLD | NEW |
1 // Copyright 2013 The Chromium Authors. All rights reserved. | 1 // Copyright 2013 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/strings/string_util.h" | 5 #include "base/strings/string_util.h" |
6 | 6 |
7 #include <ctype.h> | 7 #include <ctype.h> |
8 #include <errno.h> | 8 #include <errno.h> |
9 #include <math.h> | 9 #include <math.h> |
10 #include <stdarg.h> | 10 #include <stdarg.h> |
(...skipping 641 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
652 base::snprintf(buf, arraysize(buf), "%.1lf%s", unit_amount, | 652 base::snprintf(buf, arraysize(buf), "%.1lf%s", unit_amount, |
653 kByteStringsUnlocalized[dimension]); | 653 kByteStringsUnlocalized[dimension]); |
654 } else { | 654 } else { |
655 base::snprintf(buf, arraysize(buf), "%.0lf%s", unit_amount, | 655 base::snprintf(buf, arraysize(buf), "%.0lf%s", unit_amount, |
656 kByteStringsUnlocalized[dimension]); | 656 kByteStringsUnlocalized[dimension]); |
657 } | 657 } |
658 | 658 |
659 return ASCIIToUTF16(buf); | 659 return ASCIIToUTF16(buf); |
660 } | 660 } |
661 | 661 |
662 } // namespace base | |
663 | |
664 // Runs in O(n) time in the length of |str|. | 662 // Runs in O(n) time in the length of |str|. |
665 template<class StringType> | 663 template<class StringType> |
666 void DoReplaceSubstringsAfterOffset(StringType* str, | 664 void DoReplaceSubstringsAfterOffset(StringType* str, |
667 size_t offset, | 665 size_t offset, |
668 const StringType& find_this, | 666 BasicStringPiece<StringType> find_this, |
669 const StringType& replace_with, | 667 BasicStringPiece<StringType> replace_with, |
670 bool replace_all) { | 668 bool replace_all) { |
671 DCHECK(!find_this.empty()); | 669 DCHECK(!find_this.empty()); |
672 | 670 |
673 // If the find string doesn't appear, there's nothing to do. | 671 // If the find string doesn't appear, there's nothing to do. |
674 offset = str->find(find_this, offset); | 672 offset = str->find(find_this.data(), offset, find_this.size()); |
675 if (offset == StringType::npos) | 673 if (offset == StringType::npos) |
676 return; | 674 return; |
677 | 675 |
678 // If we're only replacing one instance, there's no need to do anything | 676 // If we're only replacing one instance, there's no need to do anything |
679 // complicated. | 677 // complicated. |
680 size_t find_length = find_this.length(); | 678 size_t find_length = find_this.length(); |
681 if (!replace_all) { | 679 if (!replace_all) { |
682 str->replace(offset, find_length, replace_with); | 680 str->replace(offset, find_length, replace_with.data(), replace_with.size()); |
683 return; | 681 return; |
684 } | 682 } |
685 | 683 |
686 // If the find and replace strings are the same length, we can simply use | 684 // If the find and replace strings are the same length, we can simply use |
687 // replace() on each instance, and finish the entire operation in O(n) time. | 685 // replace() on each instance, and finish the entire operation in O(n) time. |
688 size_t replace_length = replace_with.length(); | 686 size_t replace_length = replace_with.length(); |
689 if (find_length == replace_length) { | 687 if (find_length == replace_length) { |
690 do { | 688 do { |
691 str->replace(offset, find_length, replace_with); | 689 str->replace(offset, find_length, |
692 offset = str->find(find_this, offset + replace_length); | 690 replace_with.data(), replace_with.size()); |
| 691 offset = str->find(find_this.data(), offset + replace_length, |
| 692 find_this.size()); |
693 } while (offset != StringType::npos); | 693 } while (offset != StringType::npos); |
694 return; | 694 return; |
695 } | 695 } |
696 | 696 |
697 // Since the find and replace strings aren't the same length, a loop like the | 697 // Since the find and replace strings aren't the same length, a loop like the |
698 // one above would be O(n^2) in the worst case, as replace() will shift the | 698 // one above would be O(n^2) in the worst case, as replace() will shift the |
699 // entire remaining string each time. We need to be more clever to keep | 699 // entire remaining string each time. We need to be more clever to keep |
700 // things O(n). | 700 // things O(n). |
701 // | 701 // |
702 // If we're shortening the string, we can alternate replacements with shifting | 702 // If we're shortening the string, we can alternate replacements with shifting |
703 // forward the intervening characters using memmove(). | 703 // forward the intervening characters using memmove(). |
704 size_t str_length = str->length(); | 704 size_t str_length = str->length(); |
705 if (find_length > replace_length) { | 705 if (find_length > replace_length) { |
706 size_t write_offset = offset; | 706 size_t write_offset = offset; |
707 do { | 707 do { |
708 if (replace_length) { | 708 if (replace_length) { |
709 str->replace(write_offset, replace_length, replace_with); | 709 str->replace(write_offset, replace_length, |
| 710 replace_with.data(), replace_with.size()); |
710 write_offset += replace_length; | 711 write_offset += replace_length; |
711 } | 712 } |
712 size_t read_offset = offset + find_length; | 713 size_t read_offset = offset + find_length; |
713 offset = std::min(str->find(find_this, read_offset), str_length); | 714 offset = std::min( |
| 715 str->find(find_this.data(), read_offset, find_this.size()), |
| 716 str_length); |
714 size_t length = offset - read_offset; | 717 size_t length = offset - read_offset; |
715 if (length) { | 718 if (length) { |
716 memmove(&(*str)[write_offset], &(*str)[read_offset], | 719 memmove(&(*str)[write_offset], &(*str)[read_offset], |
717 length * sizeof(typename StringType::value_type)); | 720 length * sizeof(typename StringType::value_type)); |
718 write_offset += length; | 721 write_offset += length; |
719 } | 722 } |
720 } while (offset < str_length); | 723 } while (offset < str_length); |
721 str->resize(write_offset); | 724 str->resize(write_offset); |
722 return; | 725 return; |
723 } | 726 } |
724 | 727 |
725 // We're lengthening the string. We can use alternating replacements and | 728 // We're lengthening the string. We can use alternating replacements and |
726 // memmove() calls like above, but we need to precalculate the final string | 729 // memmove() calls like above, but we need to precalculate the final string |
727 // length and then expand from back-to-front to avoid overwriting the string | 730 // length and then expand from back-to-front to avoid overwriting the string |
728 // as we're reading it, needing to shift, or having to copy to a second string | 731 // as we're reading it, needing to shift, or having to copy to a second string |
729 // temporarily. | 732 // temporarily. |
730 size_t first_match = offset; | 733 size_t first_match = offset; |
731 | 734 |
732 // First, calculate the final length and resize the string. | 735 // First, calculate the final length and resize the string. |
733 size_t final_length = str_length; | 736 size_t final_length = str_length; |
734 size_t expansion = replace_length - find_length; | 737 size_t expansion = replace_length - find_length; |
735 size_t current_match; | 738 size_t current_match; |
736 do { | 739 do { |
737 final_length += expansion; | 740 final_length += expansion; |
738 // Minor optimization: save this offset into |current_match|, so that on | 741 // Minor optimization: save this offset into |current_match|, so that on |
739 // exit from the loop, |current_match| will point at the last instance of | 742 // exit from the loop, |current_match| will point at the last instance of |
740 // the find string, and we won't need to find() it again immediately. | 743 // the find string, and we won't need to find() it again immediately. |
741 current_match = offset; | 744 current_match = offset; |
742 offset = str->find(find_this, offset + find_length); | 745 offset = str->find(find_this.data(), offset + find_length, |
| 746 find_this.size()); |
743 } while (offset != StringType::npos); | 747 } while (offset != StringType::npos); |
744 str->resize(final_length); | 748 str->resize(final_length); |
745 | 749 |
746 // Now do the replacement loop, working backwards through the string. | 750 // Now do the replacement loop, working backwards through the string. |
747 for (size_t prev_match = str_length, write_offset = final_length; ; | 751 for (size_t prev_match = str_length, write_offset = final_length; ; |
748 current_match = str->rfind(find_this, current_match - 1)) { | 752 current_match = str->rfind(find_this.data(), current_match - 1, |
| 753 find_this.size())) { |
749 size_t read_offset = current_match + find_length; | 754 size_t read_offset = current_match + find_length; |
750 size_t length = prev_match - read_offset; | 755 size_t length = prev_match - read_offset; |
751 if (length) { | 756 if (length) { |
752 write_offset -= length; | 757 write_offset -= length; |
753 memmove(&(*str)[write_offset], &(*str)[read_offset], | 758 memmove(&(*str)[write_offset], &(*str)[read_offset], |
754 length * sizeof(typename StringType::value_type)); | 759 length * sizeof(typename StringType::value_type)); |
755 } | 760 } |
756 write_offset -= replace_length; | 761 write_offset -= replace_length; |
757 str->replace(write_offset, replace_length, replace_with); | 762 str->replace(write_offset, replace_length, |
| 763 replace_with.data(), replace_with.size()); |
758 if (current_match == first_match) | 764 if (current_match == first_match) |
759 return; | 765 return; |
760 prev_match = current_match; | 766 prev_match = current_match; |
761 } | 767 } |
762 } | 768 } |
763 | 769 |
764 void ReplaceFirstSubstringAfterOffset(string16* str, | 770 void ReplaceFirstSubstringAfterOffset(string16* str, |
765 size_t start_offset, | 771 size_t start_offset, |
766 const string16& find_this, | 772 StringPiece16 find_this, |
767 const string16& replace_with) { | 773 StringPiece16 replace_with) { |
768 DoReplaceSubstringsAfterOffset(str, start_offset, find_this, replace_with, | 774 DoReplaceSubstringsAfterOffset<string16>( |
769 false); // replace first instance | 775 str, start_offset, find_this, replace_with, false); // Replace first. |
770 } | 776 } |
771 | 777 |
772 void ReplaceFirstSubstringAfterOffset(std::string* str, | 778 void ReplaceFirstSubstringAfterOffset(std::string* str, |
773 size_t start_offset, | 779 size_t start_offset, |
774 const std::string& find_this, | 780 StringPiece find_this, |
775 const std::string& replace_with) { | 781 StringPiece replace_with) { |
776 DoReplaceSubstringsAfterOffset(str, start_offset, find_this, replace_with, | 782 DoReplaceSubstringsAfterOffset<std::string>( |
777 false); // replace first instance | 783 str, start_offset, find_this, replace_with, false); // Replace first. |
778 } | 784 } |
779 | 785 |
780 void ReplaceSubstringsAfterOffset(string16* str, | 786 void ReplaceSubstringsAfterOffset(string16* str, |
781 size_t start_offset, | 787 size_t start_offset, |
782 const string16& find_this, | 788 StringPiece16 find_this, |
783 const string16& replace_with) { | 789 StringPiece16 replace_with) { |
784 DoReplaceSubstringsAfterOffset(str, start_offset, find_this, replace_with, | 790 DoReplaceSubstringsAfterOffset<string16>( |
785 true); // replace all instances | 791 str, start_offset, find_this, replace_with, true); // Replace all. |
786 } | 792 } |
787 | 793 |
788 void ReplaceSubstringsAfterOffset(std::string* str, | 794 void ReplaceSubstringsAfterOffset(std::string* str, |
789 size_t start_offset, | 795 size_t start_offset, |
790 const std::string& find_this, | 796 StringPiece find_this, |
791 const std::string& replace_with) { | 797 StringPiece replace_with) { |
792 DoReplaceSubstringsAfterOffset(str, start_offset, find_this, replace_with, | 798 DoReplaceSubstringsAfterOffset<std::string>( |
793 true); // replace all instances | 799 str, start_offset, find_this, replace_with, true); // Replace all. |
794 } | 800 } |
795 | 801 |
| 802 } // namespace base |
| 803 |
796 size_t Tokenize(const base::string16& str, | 804 size_t Tokenize(const base::string16& str, |
797 const base::string16& delimiters, | 805 const base::string16& delimiters, |
798 std::vector<base::string16>* tokens) { | 806 std::vector<base::string16>* tokens) { |
799 *tokens = base::SplitString( | 807 *tokens = base::SplitString( |
800 str, delimiters, base::KEEP_WHITESPACE, base::SPLIT_WANT_NONEMPTY); | 808 str, delimiters, base::KEEP_WHITESPACE, base::SPLIT_WANT_NONEMPTY); |
801 return tokens->size(); | 809 return tokens->size(); |
802 } | 810 } |
803 | 811 |
804 size_t Tokenize(const std::string& str, | 812 size_t Tokenize(const std::string& str, |
805 const std::string& delimiters, | 813 const std::string& delimiters, |
(...skipping 312 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1118 } | 1126 } |
1119 | 1127 |
1120 } // namespace | 1128 } // namespace |
1121 | 1129 |
1122 size_t base::strlcpy(char* dst, const char* src, size_t dst_size) { | 1130 size_t base::strlcpy(char* dst, const char* src, size_t dst_size) { |
1123 return lcpyT<char>(dst, src, dst_size); | 1131 return lcpyT<char>(dst, src, dst_size); |
1124 } | 1132 } |
1125 size_t base::wcslcpy(wchar_t* dst, const wchar_t* src, size_t dst_size) { | 1133 size_t base::wcslcpy(wchar_t* dst, const wchar_t* src, size_t dst_size) { |
1126 return lcpyT<wchar_t>(dst, src, dst_size); | 1134 return lcpyT<wchar_t>(dst, src, dst_size); |
1127 } | 1135 } |
OLD | NEW |