return x >= '0' && x <= '9';
}
-/// compare - Compare two strings; the result is -1, 0, or 1 if this string
-/// is lexicographically less than, equal to, or greater than the \arg RHS.
-/// This is different than compare with no size specified as it only
-/// compares at most the first n bytes.
-int StringRef::compare(StringRef RHS, size_t n) const {
- // Check the prefix for a mismatch.
- size_t maxToCmp = min(Length, RHS.Length);
- maxToCmp = min(maxToCmp, n);
- if (int Res = memcmp(Data, RHS.Data, maxToCmp))
- return Res < 0 ? -1 : 1;
-
- // Otherwise the prefixes match, so we only need to check the lengths.
- // Be mindful that if the n is less than or equal to the length of either
- // string, that is the same as the strings matching because in that case
- // we only care about the prefix.
- if (((n <= Length) && (n <= RHS.Length)) ||
- (Length == RHS.Length))
- return 0;
- return Length < RHS.Length ? -1 : 1;
-}
-
/// 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) {
/// 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)
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 (unsigned char)Data[I] < (unsigned char)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;
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;
}