[PATCH] improve string find algorithm

[Jonathan Wakely]

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.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.txt
Type: text/x-patch
Size: 1931 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20170106/032cf037/attachment.bin>