Thanks for the correction and updating the comments. -Aditya -----Original Message----- From: Jonathan Wakely [mailto:jwak...@redhat.com] Sent: Friday, January 06, 2017 2:21 PM To: Aditya Kumar Cc: libstd...@gcc.gnu.org; gcc-patches@gcc.gnu.org; hiradi...@msn.com Subject: Re: [PATCH] improve string find algorithm
On 06/01/17 08:42 -0600, Aditya Kumar wrote: >Yes, we do. >Sorry for the mistake, it happened because I first wrote this for >libcxx (https://reviews.llvm.org/D27068) and while porting that line >got missed. > >Thanks, >-Aditya > > >diff --git a/libstdc++-v3/include/bits/basic_string.tcc >b/libstdc++-v3/include/bits/basic_string.tcc >index df1e8dd..7942ee6 100644 >--- a/libstdc++-v3/include/bits/basic_string.tcc >+++ b/libstdc++-v3/include/bits/basic_string.tcc >@@ -1194,14 +1194,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > if (__n == 0) > return __pos <= __size ? __pos : npos; > >- if (__n <= __size) >- { >- for (; __pos <= __size - __n; ++__pos) >- if (traits_type::eq(__data[__pos], __s[0]) >- && traits_type::compare(__data + __pos + 1, >- __s + 1, __n - 1) == 0) >- return __pos; >- } >+ if (__n > __size) >+ return npos; >+ >+ const _CharT __elem0 = __s[0]; >+ const _CharT* __first1 = __data; >+ const _CharT* __first2 = __s; >+ const _CharT* __last1 = __data + __size; >+ ptrdiff_t __len2 = __n - __pos; What's this variable for? >+ while (true) { >+ ptrdiff_t __len1 = __last1 - __first1; >+ if (__len1 < __len2) >+ return npos; >+ >+ // Find the first match. >+ __first1 = traits_type::find(__first1, __len1 - __len2 + 1, __elem0); >+ if (__first1 == 0) >+ return npos; >+ // Compare the full string when first match is found. >+ if (traits_type::compare(__first1, __first2, __len2) == 0) >+ return __first1 - __data; >+ >+ ++__first1; >+ } >+ > return npos; > } This is still wrong, consider std::string("abcd").find("ab", 2) This should return npos, but you return 0. The postcondition for the function is that the return value is not less than the pos argument. The attached patch should be a correct version of the improved algorithm.
