This is the matching change for the data structure name changes for the

[oota-llvm.git] / lib / Support / StringRef.cpp

diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp
index b5b4f9476026ee9a4e48eb2d1dd7212ee2d2e2ee..e73c6e38e2f41146209b290d88326fce25a22d9e 100644 (file)
--- a/lib/Support/StringRef.cpp
+++ b/lib/Support/StringRef.cpp
@@ -25,6 +25,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';
 }
@@ -131,6 +137,26 @@ unsigned StringRef::edit_distance(llvm::StringRef Other,
   return Result;
 }
 
+//===----------------------------------------------------------------------===//
+// 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;
+}
+
+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;
+}
+
 //===----------------------------------------------------------------------===//
 // String Searching
 //===----------------------------------------------------------------------===//
@@ -144,9 +170,35 @@ 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;
 }