Add a bad char heuristic to StringRef::find.

Based on Horspool's simplified version of Boyer-Moore. We use a constant-sized table of
uint8_ts to keep cache thrashing low, needles bigger than 255 bytes are uncommon anyways.

The worst case is still O(n*m) but we do a lot better on the average case now.

llvm-svn: 142061

1 files changed, 6 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/StringRefTest.cpp b/llvm/unittests/ADT/StringRefTest.cpp
index 8364eac8274..d91084381ec 100644
--- a/llvm/unittests/ADT/StringRefTest.cpp
+++ b/llvm/unittests/ADT/StringRefTest.cpp
@@ -245,6 +245,12 @@ TEST(StringRefTest, Find) {
   EXPECT_EQ(StringRef::npos, Str.find("zz"));
   EXPECT_EQ(2U, Str.find("ll", 2));
   EXPECT_EQ(StringRef::npos, Str.find("ll", 3));
+  EXPECT_EQ(0U, Str.find(""));
+  StringRef LongStr("hellx xello hell ello world foo bar hello");
+  EXPECT_EQ(36U, LongStr.find("hello"));
+  EXPECT_EQ(28U, LongStr.find("foo"));
+  EXPECT_EQ(12U, LongStr.find("hell", 2));
+  EXPECT_EQ(0U, LongStr.find(""));
 
   EXPECT_EQ(3U, Str.rfind('l'));
   EXPECT_EQ(StringRef::npos, Str.rfind('z'));