#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/OwningPtr.h"
#include <bitset>
using namespace llvm;
}
// Compute the edit distance between the two given strings.
-unsigned StringRef::edit_distance(llvm::StringRef Other,
+unsigned StringRef::edit_distance(llvm::StringRef Other,
bool AllowReplacements,
unsigned MaxEditDistance) {
// The algorithm implemented below is the "classic"
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),
}
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;
}
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
// 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()) {
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;
}
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) ||
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
// on signed overflow.
(long long)-ULLVal > 0)
return true;
-
+
Result = -ULLVal;
return false;
}
return true;
Result = Val;
return false;
-}
+}
bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const {
StringRef Str = *this;
Radix = GetAutoSenseRadix(Str);
assert(Radix > 1 && Radix <= 36);
-
+
// Empty strings (after the radix autosense) are invalid.
if (Str.empty()) return true;
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) {
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;
Str = Str.substr(1);
}
-
+
return false;
}