[v3] Use std::search in string::find

[v3] Use std::search in string::find

[Paolo Carlini]

[-- Attachment #1: Type: text/plain, Size: 77 bytes --]

Hi,

tested x86/x86_64-linux, committed to mainline.

Paolo.

//////////////

[-- Attachment #2: CL_find --]
[-- Type: text/plain, Size: 326 bytes --]

2004-06-12  Paolo Carlini  <pcarlini@suse.de>

	* include/bits/basic_string.tcc (find(const _CharT*, size_type,
	size_type)): Reimplement using std::search.
	* src/string-inst.cc: Instantiate std::search for char/wchar_t.

2004-06-12  Dhruv Matani  <dhruvbird@gmx.net>

	* testsuite/performance/21_strings/string_find.cc: New.

[-- Attachment #3: patch_find --]
[-- Type: text/plain, Size: 5767 bytes --]

diff -urN libstdc++-v3-orig/include/bits/basic_string.tcc libstdc++-v3/include/bits/basic_string.tcc
--- libstdc++-v3-orig/include/bits/basic_string.tcc	2004-04-25 17:45:13.000000000 +0200
+++ libstdc++-v3/include/bits/basic_string.tcc	2004-06-11 16:39:13.000000000 +0200
@@ -685,12 +685,17 @@
     find(const _CharT* __s, size_type __pos, size_type __n) const
     {
       __glibcxx_requires_string_len(__s, __n);
+      size_type __ret = npos;
       const size_type __size = this->size();
-      const _CharT* __data = _M_data();
-      for (; __pos + __n <= __size; ++__pos)
-	if (traits_type::compare(__data + __pos, __s, __n) == 0)
-	  return __pos;
-      return npos;
+      if (__pos + __n <= __size)
+	{
+	  const _CharT* __data = _M_data();
+	  const _CharT* __p = std::search(__data + __pos, __data + __size,
+					  __s, __s + __n, traits_type::eq);
+	  if (__p != __data + __size || __n == 0)
+	    __ret = __p - __data;
+	}
+      return __ret;
     }
 
   template<typename _CharT, typename _Traits, typename _Alloc>
@@ -698,8 +703,8 @@
     basic_string<_CharT, _Traits, _Alloc>::
     find(_CharT __c, size_type __pos) const
     {
-      const size_type __size = this->size();
       size_type __ret = npos;
+      const size_type __size = this->size();
       if (__pos < __size)
 	{
 	  const _CharT* __data = _M_data();
diff -urN libstdc++-v3-orig/src/string-inst.cc libstdc++-v3/src/string-inst.cc
--- libstdc++-v3-orig/src/string-inst.cc	2004-01-24 12:34:06.000000000 +0100
+++ libstdc++-v3/src/string-inst.cc	2004-06-11 19:07:25.000000000 +0200
@@ -76,6 +76,11 @@
     C*
     S::_S_construct(const C*, const C*, const allocator<C>&,
 		    forward_iterator_tag);
+
+  // Used in str::find.
+  template
+    const C*
+    search(const C*, const C*, const C*, const C*, bool(*)(const C&, const C&));
 } // namespace std
 
 namespace __gnu_cxx
diff -urN libstdc++-v3-orig/testsuite/performance/21_strings/string_find.cc libstdc++-v3/testsuite/performance/21_strings/string_find.cc
--- libstdc++-v3-orig/testsuite/performance/21_strings/string_find.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/performance/21_strings/string_find.cc	2004-06-11 19:25:06.000000000 +0200
@@ -0,0 +1,105 @@
+ // Copyright (C) 2004 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <string>
+#include <testsuite_performance.h>
+
+void
+test_pair(const std::string& s, const std::string& f, int n)
+{
+  std::string::size_type sz = 0;
+
+  for (int i = 0; i < n; ++i)
+    sz = s.find(f);
+}
+
+int main()
+{
+  using namespace std;
+  using namespace __gnu_test;
+
+  time_counter time;
+  resource_counter resource;
+
+  const unsigned int iterations = 2000000;
+
+  string s, f;
+  s = "aabbaabbaaxd adbffdadgaxaabbbddhatyaaaabbbaabbaabbcsy";
+  f = "aabbaabbc";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "1", time, resource);
+  clear_counters(time, resource);
+
+  f = "aabbb";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "2", time, resource);
+  clear_counters(time, resource);
+
+  f = "xd";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "3", time, resource);
+  clear_counters(time, resource);
+
+  s = "dhruv is a very very good boy ;-)";
+  f = "very";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "4", time, resource);
+  clear_counters(time, resource);
+
+  f = "bad";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "5", time, resource);
+  clear_counters(time, resource);
+
+  f = "extra irritating";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "6", time, resource);
+  clear_counters(time, resource);
+
+  s = "this is a very this is a very this is a verty this is a very "
+      "this is a very long sentence";
+  f = "this is a very long sentence";
+  start_counters(time, resource);
+  test_pair(s, f, iterations);
+  stop_counters(time, resource);
+  report_performance(__FILE__, "7", time, resource);
+  clear_counters(time, resource);
+
+  return 0;
+}