diff options
Diffstat (limited to 'contrib/llvm/lib/Support/StringRef.cpp')
| -rw-r--r-- | contrib/llvm/lib/Support/StringRef.cpp | 73 |
1 files changed, 48 insertions, 25 deletions
diff --git a/contrib/llvm/lib/Support/StringRef.cpp b/contrib/llvm/lib/Support/StringRef.cpp index 46f26b2..5398051 100644 --- a/contrib/llvm/lib/Support/StringRef.cpp +++ b/contrib/llvm/lib/Support/StringRef.cpp @@ -9,6 +9,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/ADT/APInt.h" +#include "llvm/ADT/OwningPtr.h" #include <bitset> using namespace llvm; @@ -67,8 +68,9 @@ int StringRef::compare_numeric(StringRef RHS) const { } // Compute the edit distance between the two given strings. -unsigned StringRef::edit_distance(llvm::StringRef Other, - bool AllowReplacements) { +unsigned StringRef::edit_distance(llvm::StringRef Other, + bool AllowReplacements, + unsigned MaxEditDistance) { // The algorithm implemented below is the "classic" // dynamic-programming algorithm for computing the Levenshtein // distance, which is described here: @@ -83,17 +85,21 @@ unsigned StringRef::edit_distance(llvm::StringRef Other, const unsigned SmallBufferSize = 64; unsigned SmallBuffer[SmallBufferSize]; - unsigned *Allocated = 0; + llvm::OwningArrayPtr<unsigned> Allocated; unsigned *previous = SmallBuffer; - if (2*(n + 1) > SmallBufferSize) - Allocated = previous = new unsigned [2*(n+1)]; + if (2*(n + 1) > SmallBufferSize) { + previous = new unsigned [2*(n+1)]; + Allocated.reset(previous); + } unsigned *current = previous + (n + 1); - - for (unsigned i = 0; i <= n; ++i) + + for (unsigned i = 0; i <= n; ++i) previous[i] = i; for (size_type y = 1; y <= m; ++y) { current[0] = y; + unsigned BestThisRow = current[0]; + for (size_type x = 1; x <= n; ++x) { if (AllowReplacements) { current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u), @@ -103,16 +109,18 @@ unsigned StringRef::edit_distance(llvm::StringRef Other, if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1]; else current[x] = min(current[x-1], previous[x]) + 1; } + BestThisRow = min(BestThisRow, current[x]); } - + + if (MaxEditDistance && BestThisRow > MaxEditDistance) + return MaxEditDistance + 1; + unsigned *tmp = current; current = previous; previous = tmp; } unsigned Result = previous[n]; - delete [] Allocated; - return Result; } @@ -192,6 +200,21 @@ StringRef::size_type StringRef::find_first_not_of(StringRef Chars, return npos; } +/// find_last_of - Find the last character in the string that is in \arg C, +/// or npos if not found. +/// +/// Note: O(size() + Chars.size()) +StringRef::size_type StringRef::find_last_of(StringRef Chars, + size_t From) const { + std::bitset<1 << CHAR_BIT> CharBits; + for (size_type i = 0; i != Chars.size(); ++i) + CharBits.set((unsigned char)Chars[i]); + + for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) + if (CharBits.test((unsigned char)Data[i])) + return i; + return npos; +} //===----------------------------------------------------------------------===// // Helpful Algorithms @@ -232,10 +255,10 @@ static bool GetAsUnsignedInteger(StringRef Str, unsigned Radix, // Autosense radix if not specified. if (Radix == 0) Radix = GetAutoSenseRadix(Str); - + // Empty strings (after the radix autosense) are invalid. if (Str.empty()) return true; - + // Parse all the bytes of the string given this radix. Watch for overflow. Result = 0; while (!Str.empty()) { @@ -248,23 +271,23 @@ static bool GetAsUnsignedInteger(StringRef Str, unsigned Radix, CharVal = Str[0]-'A'+10; else return true; - + // If the parsed value is larger than the integer radix, the string is // invalid. if (CharVal >= Radix) return true; - + // Add in this character. unsigned long long PrevResult = Result; Result = Result*Radix+CharVal; - + // Check for overflow. if (Result < PrevResult) return true; Str = Str.substr(1); } - + return false; } @@ -275,7 +298,7 @@ bool StringRef::getAsInteger(unsigned Radix, unsigned long long &Result) const { bool StringRef::getAsInteger(unsigned Radix, long long &Result) const { unsigned long long ULLVal; - + // Handle positive strings first. if (empty() || front() != '-') { if (GetAsUnsignedInteger(*this, Radix, ULLVal) || @@ -285,7 +308,7 @@ bool StringRef::getAsInteger(unsigned Radix, long long &Result) const { Result = ULLVal; return false; } - + // Get the positive part of the value. if (GetAsUnsignedInteger(substr(1), Radix, ULLVal) || // Reject values so large they'd overflow as negative signed, but allow @@ -293,7 +316,7 @@ bool StringRef::getAsInteger(unsigned Radix, long long &Result) const { // on signed overflow. (long long)-ULLVal > 0) return true; - + Result = -ULLVal; return false; } @@ -314,7 +337,7 @@ bool StringRef::getAsInteger(unsigned Radix, unsigned &Result) const { return true; Result = Val; return false; -} +} bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { StringRef Str = *this; @@ -324,7 +347,7 @@ bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { Radix = GetAutoSenseRadix(Str); assert(Radix > 1 && Radix <= 36); - + // Empty strings (after the radix autosense) are invalid. if (Str.empty()) return true; @@ -348,7 +371,7 @@ bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { if (BitWidth < Result.getBitWidth()) BitWidth = Result.getBitWidth(); // don't shrink the result else - Result.zext(BitWidth); + Result = Result.zext(BitWidth); APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix if (!IsPowerOf2Radix) { @@ -369,12 +392,12 @@ bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { CharVal = Str[0]-'A'+10; else return true; - + // If the parsed value is larger than the integer radix, the string is // invalid. if (CharVal >= Radix) return true; - + // Add in this character. if (IsPowerOf2Radix) { Result <<= Log2Radix; @@ -387,6 +410,6 @@ bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { Str = Str.substr(1); } - + return false; } |
