From 250eb005d91e80b05a61345394bae9e9528151ac Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Mon, 23 Aug 2010 18:16:08 +0000 Subject: Avoid O(n*m) complexity in StringRef::find_first(_not)_of(StringRef). - Cache used characters in a bitset to reduce memory overhead to just 32 bytes. - On my core2 this code is faster except when the checked string was very short (smaller than the list of delimiters). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111817 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/StringRef.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'include/llvm/ADT/StringRef.h') diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index a1be1e70c2..8386d3ee42 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -238,7 +238,7 @@ namespace llvm { /// find_first_of - Find the first character in the string that is in \arg /// Chars, or npos if not found. /// - /// Note: O(size() * Chars.size()) + /// Note: O(size() + Chars.size()) size_type find_first_of(StringRef Chars, size_t From = 0) const; /// find_first_not_of - Find the first character in the string that is not @@ -248,7 +248,7 @@ namespace llvm { /// find_first_not_of - Find the first character in the string that is not /// in the string \arg Chars, or npos if not found. /// - /// Note: O(size() * Chars.size()) + /// Note: O(size() + Chars.size()) size_type find_first_not_of(StringRef Chars, size_t From = 0) const; /// @} -- cgit v1.2.3