RE: [PATCH] improve string find algorithm

[Aditya Kumar <aditya dot k7 at samsung dot com>]

Thanks for the correction and updating the comments.
-Aditya

-----Original Message-----
From: Jonathan Wakely [mailto:jwakely@redhat.com] 
Sent: Friday, January 06, 2017 2:21 PM
To: Aditya Kumar
Cc: libstdc++@gcc.gnu.org; gcc-patches@gcc.gnu.org; hiraditya@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.