From 6e6a558ebce556476d8fd659b419a2760f2ab154 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Sat, 15 Oct 2011 10:08:31 +0000 Subject: 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142061 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/ADT/StringRefTest.cpp | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'unittests') diff --git a/unittests/ADT/StringRefTest.cpp b/unittests/ADT/StringRefTest.cpp index 8364eac827..d91084381e 100644 --- a/unittests/ADT/StringRefTest.cpp +++ b/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')); -- cgit v1.2.3