X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FSupport%2FStringRef.cpp;h=4d20903e84b8a6a35c9be59c371e085df7ad748d;hp=40b732c62db6249d816994e3f8ef29b19a52c113;hb=507329912aa343b8a430a97cf2d8f92eecb6dc01;hpb=250eb005d91e80b05a61345394bae9e9528151ac diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp index 40b732c62db..4d20903e84b 100644 --- a/lib/Support/StringRef.cpp +++ b/lib/Support/StringRef.cpp @@ -9,6 +9,8 @@ #include "llvm/ADT/StringRef.h" #include "llvm/ADT/APInt.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/edit_distance.h" #include using namespace llvm; @@ -24,6 +26,12 @@ static char ascii_tolower(char x) { return x; } +static char ascii_toupper(char x) { + if (x >= 'a' && x <= 'z') + return x - 'a' + 'A'; + return x; +} + static bool ascii_isdigit(char x) { return x >= '0' && x <= '9'; } @@ -31,26 +39,26 @@ static bool ascii_isdigit(char x) { /// compare_lower - Compare strings, ignoring case. int StringRef::compare_lower(StringRef RHS) const { for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { - char LHC = ascii_tolower(Data[I]); - char RHC = ascii_tolower(RHS.Data[I]); + unsigned char LHC = ascii_tolower(Data[I]); + unsigned char RHC = ascii_tolower(RHS.Data[I]); if (LHC != RHC) return LHC < RHC ? -1 : 1; } if (Length == RHS.Length) - return 0; + return 0; return Length < RHS.Length ? -1 : 1; } /// compare_numeric - Compare strings, handle embedded numbers. int StringRef::compare_numeric(StringRef RHS) const { for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { - if (Data[I] == RHS.Data[I]) - continue; + // Check for sequences of digits. if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) { - // The longer sequence of numbers is larger. This doesn't really handle - // prefixed zeros well. - for (size_t J = I+1; J != E+1; ++J) { + // The longer sequence of numbers is considered larger. + // This doesn't really handle prefixed zeros well. + size_t J; + for (J = I + 1; J != E + 1; ++J) { bool ld = J < Length && ascii_isdigit(Data[J]); bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]); if (ld != rd) @@ -58,61 +66,48 @@ int StringRef::compare_numeric(StringRef RHS) const { if (!rd) break; } + // The two number sequences have the same length (J-I), just memcmp them. + if (int Res = compareMemory(Data + I, RHS.Data + I, J - I)) + return Res < 0 ? -1 : 1; + // Identical number sequences, continue search after the numbers. + I = J - 1; + continue; } - return Data[I] < RHS.Data[I] ? -1 : 1; + if (Data[I] != RHS.Data[I]) + return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; } if (Length == RHS.Length) - return 0; + return 0; return Length < RHS.Length ? -1 : 1; } // Compute the edit distance between the two given strings. -unsigned StringRef::edit_distance(llvm::StringRef Other, - bool AllowReplacements) { - // The algorithm implemented below is the "classic" - // dynamic-programming algorithm for computing the Levenshtein - // distance, which is described here: - // - // http://en.wikipedia.org/wiki/Levenshtein_distance - // - // Although the algorithm is typically described using an m x n - // array, only two rows are used at a time, so this implemenation - // just keeps two separate vectors for those two rows. - size_type m = size(); - size_type n = Other.size(); - - const unsigned SmallBufferSize = 64; - unsigned SmallBuffer[SmallBufferSize]; - unsigned *Allocated = 0; - unsigned *previous = SmallBuffer; - if (2*(n + 1) > SmallBufferSize) - Allocated = previous = new unsigned [2*(n+1)]; - unsigned *current = previous + (n + 1); - - for (unsigned i = 0; i <= n; ++i) - previous[i] = i; - - for (size_type y = 1; y <= m; ++y) { - current[0] = y; - for (size_type x = 1; x <= n; ++x) { - if (AllowReplacements) { - current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u), - min(current[x-1], previous[x])+1); - } - else { - if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1]; - else current[x] = min(current[x-1], previous[x]) + 1; - } - } - - unsigned *tmp = current; - current = previous; - previous = tmp; +unsigned StringRef::edit_distance(llvm::StringRef Other, + bool AllowReplacements, + unsigned MaxEditDistance) { + return llvm::ComputeEditDistance( + llvm::ArrayRef(data(), size()), + llvm::ArrayRef(Other.data(), Other.size()), + AllowReplacements, MaxEditDistance); +} + +//===----------------------------------------------------------------------===// +// String Operations +//===----------------------------------------------------------------------===// + +std::string StringRef::lower() const { + std::string Result(size(), char()); + for (size_type i = 0, e = size(); i != e; ++i) { + Result[i] = ascii_tolower(Data[i]); } + return Result; +} - unsigned Result = previous[n]; - delete [] Allocated; - +std::string StringRef::upper() const { + std::string Result(size(), char()); + for (size_type i = 0, e = size(); i != e; ++i) { + Result[i] = ascii_toupper(Data[i]); + } return Result; } @@ -123,21 +118,47 @@ unsigned StringRef::edit_distance(llvm::StringRef Other, /// find - Search for the first string \arg Str in the string. /// -/// \return - The index of the first occurence of \arg Str, or npos if not +/// \return - The index of the first occurrence of \arg Str, or npos if not /// found. size_t StringRef::find(StringRef Str, size_t From) const { size_t N = Str.size(); if (N > Length) return npos; - for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i) - if (substr(i, N).equals(Str)) - return i; + + // For short haystacks or unsupported needles fall back to the naive algorithm + if (Length < 16 || N > 255 || N == 0) { + for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i) + if (substr(i, N).equals(Str)) + return i; + return npos; + } + + if (From >= Length) + return npos; + + // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. + uint8_t BadCharSkip[256]; + std::memset(BadCharSkip, N, 256); + for (unsigned i = 0; i != N-1; ++i) + BadCharSkip[(uint8_t)Str[i]] = N-1-i; + + unsigned Len = Length-From, Pos = From; + while (Len >= N) { + if (substr(Pos, N).equals(Str)) // See if this is the correct substring. + return Pos; + + // Otherwise skip the appropriate number of bytes. + uint8_t Skip = BadCharSkip[(uint8_t)(*this)[Pos+N-1]]; + Len -= Skip; + Pos += Skip; + } + return npos; } /// rfind - Search for the last string \arg Str in the string. /// -/// \return - The index of the last occurence of \arg Str, or npos if not +/// \return - The index of the last occurrence of \arg Str, or npos if not /// found. size_t StringRef::rfind(StringRef Str) const { size_t N = Str.size(); @@ -192,6 +213,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 +268,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 +284,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 +311,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 +321,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 +329,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 +350,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 +360,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 +384,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 +405,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 +423,6 @@ bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { Str = Str.substr(1); } - + return false; }