diff options
| author | Benjamin Kramer <benny.kra@googlemail.com> | 2011-10-15 10:08:31 +0000 |
|---|---|---|
| committer | Benjamin Kramer <benny.kra@googlemail.com> | 2011-10-15 10:08:31 +0000 |
| commit | 4d681d7dc4904f64073d5bbcaab43a2efccd5a33 (patch) | |
| tree | 07ffa6754ef55b80f2e1dbf9d65fe26073e30041 /llvm/unittests/ADT/StringRefTest.cpp | |
| parent | ebe13bc3f14ba5e05a443326073de2a9b401bcc7 (diff) | |
| download | llvm-4d681d7dc4904f64073d5bbcaab43a2efccd5a33.zip llvm-4d681d7dc4904f64073d5bbcaab43a2efccd5a33.tar.gz llvm-4d681d7dc4904f64073d5bbcaab43a2efccd5a33.tar.bz2 | |
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
Diffstat (limited to 'llvm/unittests/ADT/StringRefTest.cpp')
| -rw-r--r-- | llvm/unittests/ADT/StringRefTest.cpp | 6 |
1 files changed, 6 insertions, 0 deletions
diff --git a/llvm/unittests/ADT/StringRefTest.cpp b/llvm/unittests/ADT/StringRefTest.cpp index 8364eac..d910843 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')); |