[multiple changes]

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

	* include/ext/algorithm: Trivial formatting fixes.
	* include/ext/functional: Likewise.
	* include/ext/hash_fun.h: Likewise.
	* include/ext/iterator: Likewise.

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.

From-SVN: r83022

8 files changed, 670 insertions, 443 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 703fef9..d1cde4b 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,20 @@
+2004-06-12  Paolo Carlini  <pcarlini@suse.de>
+
+	* include/ext/algorithm: Trivial formatting fixes.
+	* include/ext/functional: Likewise.
+	* include/ext/hash_fun.h: Likewise.
+	* include/ext/iterator: Likewise.
+
+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.
+
 2004-06-10  Aaron W. LaFramboise  <aaronraolete36@aaronwl.com>
 
 	* include/bits/istream.tcc (istream::ignore): Fix for -Wuninitialized.
diff --git a/libstdc++-v3/include/bits/basic_string.tcc b/libstdc++-v3/include/bits/basic_string.tcc
index 7034778..7d27aab 100644
--- a/libstdc++-v3/include/bits/basic_string.tcc
+++ b/libstdc++-v3/include/bits/basic_string.tcc
@@ -685,12 +685,17 @@ namespace std
     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 @@ namespace std
     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 --git a/libstdc++-v3/include/ext/algorithm b/libstdc++-v3/include/ext/algorithm
index 07ac4cb..5cf001b 100644
--- a/libstdc++-v3/include/ext/algorithm
+++ b/libstdc++-v3/include/ext/algorithm
@@ -1,6 +1,6 @@
 // Algorithm extensions -*- C++ -*-
 
-// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 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
@@ -84,11 +84,12 @@ namespace __gnu_cxx
 	     _OutputIterator __result,
 	     input_iterator_tag)
     {
-      for ( ; __count > 0; --__count) {
-	*__result = *__first;
-	++__first;
-	++__result;
-      }
+      for ( ; __count > 0; --__count)
+	{
+	  *__result = *__first;
+	  ++__first;
+	  ++__result;
+	}
       return pair<_InputIterator, _OutputIterator>(__first, __result);
     }
 
@@ -99,8 +100,9 @@ namespace __gnu_cxx
 	     random_access_iterator_tag)
     {
       _RAIterator __last = __first + __count;
-      return pair<_RAIterator, _OutputIterator>(__last,
-					std::copy(__first, __last, __result));
+      return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
+								  __last,
+								  __result));
     }
 
   /**
@@ -132,23 +134,24 @@ namespace __gnu_cxx
 
   template<typename _InputIterator1, typename _InputIterator2>
     int
-    __lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1,
-				   _InputIterator2 __first2, _InputIterator2 __last2)
+    __lexicographical_compare_3way(_InputIterator1 __first1,
+				   _InputIterator1 __last1,
+				   _InputIterator2 __first2,
+				   _InputIterator2 __last2)
     {
-      while (__first1 != __last1 && __first2 != __last2) {
-	if (*__first1 < *__first2)
-	  return -1;
-	if (*__first2 < *__first1)
-	  return 1;
-	++__first1;
-	++__first2;
-      }
-      if (__first2 == __last2) {
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (*__first1 < *__first2)
+	    return -1;
+	  if (*__first2 < *__first1)
+	    return 1;
+	  ++__first1;
+	  ++__first2;
+	}
+      if (__first2 == __last2)
 	return !(__first1 == __last1);
-      }
-      else {
+      else
 	return -1;
-      }
     }
 
   inline int
@@ -169,11 +172,10 @@ namespace __gnu_cxx
 				 const char* __first2, const char* __last2)
   {
 #if CHAR_MAX == SCHAR_MAX
-    return __lexicographical_compare_3way(
-				  (const signed char*) __first1,
-				  (const signed char*) __last1,
-				  (const signed char*) __first2,
-				  (const signed char*) __last2);
+    return __lexicographical_compare_3way((const signed char*) __first1,
+					  (const signed char*) __last1,
+					  (const signed char*) __first2,
+					  (const signed char*) __last2);
 #else
     return __lexicographical_compare_3way((const unsigned char*) __first1,
 					  (const unsigned char*) __last1,
@@ -198,8 +200,10 @@ namespace __gnu_cxx
   */
   template<typename _InputIterator1, typename _InputIterator2>
     int
-    lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1,
-				 _InputIterator2 __first2, _InputIterator2 __last2)
+    lexicographical_compare_3way(_InputIterator1 __first1,
+				 _InputIterator1 __last1,
+				 _InputIterator2 __first2,
+				 _InputIterator2 __last2)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
@@ -211,12 +215,12 @@ namespace __gnu_cxx
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
-      return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
+      return __lexicographical_compare_3way(__first1, __last1, __first2,
+					    __last2);
     }
 
   // count and count_if: this version, whose return type is void, was present
   // in the HP STL, and is retained as an extension for backward compatibility.
-
   template<typename _InputIterator, typename _Tp, typename _Size>
     void
     count(_InputIterator __first, _InputIterator __last,
@@ -259,7 +263,8 @@ namespace __gnu_cxx
    *  @ingroup SGIextensions
    *  @doctodo
   */
-  template<typename _ForwardIterator, typename _OutputIterator, typename _Distance>
+  template<typename _ForwardIterator, typename _OutputIterator,
+	   typename _Distance>
     _OutputIterator
     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
                     _OutputIterator __out, const _Distance __n)
@@ -273,16 +278,17 @@ namespace __gnu_cxx
       _Distance __remaining = std::distance(__first, __last);
       _Distance __m = min(__n, __remaining);
 
-      while (__m > 0) {
-	if ((std::rand() % __remaining) < __m) {
+      while (__m > 0)
+	{
+	  if ((std::rand() % __remaining) < __m)
+	    {
 	      *__out = *__first;
 	      ++__out;
 	      --__m;
+	    }
+	  --__remaining;
+	  ++__first;
 	}
-
-	--__remaining;
-	++__first;
-      }
       return __out;
     }
 
@@ -291,8 +297,8 @@ namespace __gnu_cxx
    *  @ingroup SGIextensions
    *  @doctodo
   */
-  template<typename _ForwardIterator, typename _OutputIterator, typename _Distance,
-	   typename _RandomNumberGenerator>
+  template<typename _ForwardIterator, typename _OutputIterator,
+	   typename _Distance, typename _RandomNumberGenerator>
     _OutputIterator
     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
                    _OutputIterator __out, const _Distance __n,
@@ -309,20 +315,22 @@ namespace __gnu_cxx
       _Distance __remaining = std::distance(__first, __last);
       _Distance __m = min(__n, __remaining);
 
-      while (__m > 0) {
-	if (__rand(__remaining) < __m) {
+      while (__m > 0)
+	{
+	  if (__rand(__remaining) < __m)
+	    {
 	      *__out = *__first;
 	      ++__out;
 	      --__m;
+	    }
+	  --__remaining;
+	  ++__first;
 	}
-
-	--__remaining;
-	++__first;
-      }
       return __out;
     }
 
-  template<typename _InputIterator, typename _RandomAccessIterator, typename _Distance>
+  template<typename _InputIterator, typename _RandomAccessIterator,
+	   typename _Distance>
     _RandomAccessIterator
     __random_sample(_InputIterator __first, _InputIterator __last,
 		    _RandomAccessIterator __out,
@@ -333,14 +341,14 @@ namespace __gnu_cxx
       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 	__out[__m] = *__first;
 
-      while (__first != __last) {
-	++__t;
-	_Distance __M = std::rand() % (__t);
-	if (__M < __n)
-	  __out[__M] = *__first;
-	++__first;
-      }
-
+      while (__first != __last)
+	{
+	  ++__t;
+	  _Distance __M = std::rand() % (__t);
+	  if (__M < __n)
+	    __out[__M] = *__first;
+	  ++__first;
+	}
       return __out + __m;
     }
 
@@ -361,14 +369,14 @@ namespace __gnu_cxx
       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 	__out[__m] = *__first;
 
-      while (__first != __last) {
-	++__t;
-	_Distance __M = __rand(__t);
-	if (__M < __n)
-	  __out[__M] = *__first;
-	++__first;
-      }
-
+      while (__first != __last)
+	{
+	  ++__t;
+	  _Distance __M = __rand(__t);
+	  if (__M < __n)
+	    __out[__M] = *__first;
+	  ++__first;
+	}
       return __out + __m;
     }
 
@@ -380,7 +388,8 @@ namespace __gnu_cxx
   template<typename _InputIterator, typename _RandomAccessIterator>
     inline _RandomAccessIterator
     random_sample(_InputIterator __first, _InputIterator __last,
-		  _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
+		  _RandomAccessIterator __out_first,
+		  _RandomAccessIterator __out_last)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
@@ -402,7 +411,8 @@ namespace __gnu_cxx
 	   typename _RandomNumberGenerator>
     inline _RandomAccessIterator
     random_sample(_InputIterator __first, _InputIterator __last,
-		  _RandomAccessIterator __out_first, _RandomAccessIterator __out_last,
+		  _RandomAccessIterator __out_first,
+		  _RandomAccessIterator __out_last,
 		  _RandomNumberGenerator& __rand)
     {
       // concept requirements
@@ -427,7 +437,8 @@ namespace __gnu_cxx
     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
       // concept requirements
-      __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
+      __glibcxx_function_requires(_RandomAccessIteratorConcept<
+				  _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
@@ -446,7 +457,8 @@ namespace __gnu_cxx
 	    _StrictWeakOrdering __comp)
     {
       // concept requirements
-      __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
+      __glibcxx_function_requires(_RandomAccessIteratorConcept<
+				  _RandomAccessIterator>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 	    typename iterator_traits<_RandomAccessIterator>::value_type,
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
@@ -478,11 +490,9 @@ namespace __gnu_cxx
 	return true;
 
       _ForwardIterator __next = __first;
-      for (++__next; __next != __last; __first = __next, ++__next) {
+      for (++__next; __next != __last; __first = __next, ++__next)
 	if (*__next < *__first)
 	  return false;
-      }
-
       return true;
     }
 
@@ -493,7 +503,8 @@ namespace __gnu_cxx
   */
   template<typename _ForwardIterator, typename _StrictWeakOrdering>
     bool
-    is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp)
+    is_sorted(_ForwardIterator __first, _ForwardIterator __last,
+	      _StrictWeakOrdering __comp)
     {
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -506,11 +517,9 @@ namespace __gnu_cxx
 	return true;
 
       _ForwardIterator __next = __first;
-      for (++__next; __next != __last; __first = __next, ++__next) {
+      for (++__next; __next != __last; __first = __next, ++__next)
 	if (__comp(*__next, *__first))
 	  return false;
-      }
-
       return true;
     }
 } // namespace __gnu_cxx
diff --git a/libstdc++-v3/include/ext/functional b/libstdc++-v3/include/ext/functional
index 1a37817..e57d871 100644
--- a/libstdc++-v3/include/ext/functional
+++ b/libstdc++-v3/include/ext/functional
@@ -1,6 +1,6 @@
 // Functional extensions -*- C++ -*-
 
-// Copyright (C) 2002 Free Software Foundation, Inc.
+// Copyright (C) 2002, 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
@@ -68,328 +68,359 @@
 
 namespace __gnu_cxx
 {
-using std::unary_function;
-using std::binary_function;
-using std::mem_fun1_t;
-using std::const_mem_fun1_t;
-using std::mem_fun1_ref_t;
-using std::const_mem_fun1_ref_t;
-
-/** The @c identity_element functions are not part of the C++ standard; SGI
- *  provided them as an extension.  Its argument is an operation, and its
- *  return value is the identity element for that operation.  It is overloaded
- *  for addition and multiplication, and you can overload it for your own
- *  nefarious operations.
- *
- *  @addtogroup SGIextensions
- *  @{
-*/
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Tp> inline _Tp identity_element(std::plus<_Tp>) {
-  return _Tp(0);
-}
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Tp> inline _Tp identity_element(std::multiplies<_Tp>) {
-  return _Tp(1);
-}
-/** @}  */
-
-/** As an extension to the binders, SGI provided composition functors and
- *  wrapper functions to aid in their creation.  The @c unary_compose
- *  functor is constructed from two functions/functors, @c f and @c g.
- *  Calling @c operator() with a single argument @c x returns @c f(g(x)).
- *  The function @c compose1 takes the two functions and constructs a
- *  @c unary_compose variable for you.
- *
- *  @c binary_compose is constructed from three functors, @c f, @c g1,
- *  and @c g2.  Its @c operator() returns @c f(g1(x),g2(x)).  The function
- *  @compose2 takes f, g1, and g2, and constructs the @c binary_compose
- *  instance for you.  For example, if @c f returns an int, then
- *  \code
- *  int answer = (compose2(f,g1,g2))(x);
- *  \endcode
- *  is equivalent to
- *  \code
- *  int temp1 = g1(x);
- *  int temp2 = g2(x);
- *  int answer = f(temp1,temp2);
- *  \endcode
- *  But the first form is more compact, and can be passed around as a
- *  functor to other algorithms.
- *
- *  @addtogroup SGIextensions
- *  @{
-*/
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Operation1, class _Operation2>
-class unary_compose
-  : public unary_function<typename _Operation2::argument_type,
-		       typename _Operation1::result_type>
-{
-protected:
-  _Operation1 _M_fn1;
-  _Operation2 _M_fn2;
-public:
-  unary_compose(const _Operation1& __x, const _Operation2& __y)
-    : _M_fn1(__x), _M_fn2(__y) {}
-  typename _Operation1::result_type
-  operator()(const typename _Operation2::argument_type& __x) const {
-    return _M_fn1(_M_fn2(__x));
-  }
-};
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Operation1, class _Operation2>
-inline unary_compose<_Operation1,_Operation2>
-compose1(const _Operation1& __fn1, const _Operation2& __fn2)
-{
-  return unary_compose<_Operation1,_Operation2>(__fn1, __fn2);
-}
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Operation1, class _Operation2, class _Operation3>
-class binary_compose
-  : public unary_function<typename _Operation2::argument_type,
-                          typename _Operation1::result_type> {
-protected:
-  _Operation1 _M_fn1;
-  _Operation2 _M_fn2;
-  _Operation3 _M_fn3;
-public:
-  binary_compose(const _Operation1& __x, const _Operation2& __y,
-                 const _Operation3& __z)
-    : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { }
-  typename _Operation1::result_type
-  operator()(const typename _Operation2::argument_type& __x) const {
-    return _M_fn1(_M_fn2(__x), _M_fn3(__x));
-  }
-};
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Operation1, class _Operation2, class _Operation3>
-inline binary_compose<_Operation1, _Operation2, _Operation3>
-compose2(const _Operation1& __fn1, const _Operation2& __fn2,
-         const _Operation3& __fn3)
-{
-  return binary_compose<_Operation1,_Operation2,_Operation3>
-    (__fn1, __fn2, __fn3);
-}
-/** @}  */
-
-/** As an extension, SGI provided a functor called @c identity.  When a
- *  functor is required but no operations are desired, this can be used as a
- *  pass-through.  Its @c operator() returns its argument unchanged.
- *
- *  @addtogroup SGIextensions
-*/
-template <class _Tp> struct identity : public std::_Identity<_Tp> {};
-
-/** @c select1st and @c select2nd are extensions provided by SGI.  Their
- *  @c operator()s
- *  take a @c std::pair as an argument, and return either the first member
- *  or the second member, respectively.  They can be used (especially with
- *  the composition functors) to "strip" data from a sequence before
- *  performing the remainder of an algorithm.
- *
- *  @addtogroup SGIextensions
- *  @{
-*/
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Pair> struct select1st : public std::_Select1st<_Pair> {};
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Pair> struct select2nd : public std::_Select2nd<_Pair> {};
-/** @}  */
-
-// extension documented next
-template <class _Arg1, class _Arg2>
-struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1> {
-  _Arg1 operator()(const _Arg1& __x, const _Arg2&) const { return __x; }
-};
-
-template <class _Arg1, class _Arg2>
-struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> {
-  _Arg2 operator()(const _Arg1&, const _Arg2& __y) const { return __y; }
-};
-
-/** The @c operator() of the @c project1st functor takes two arbitrary
- *  arguments and returns the first one, while @c project2nd returns the
- *  second one.  They are extensions provided by SGI.
- *
- *  @addtogroup SGIextensions
- *  @{
-*/
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Arg1, class _Arg2>
-struct project1st : public _Project1st<_Arg1, _Arg2> {};
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Arg1, class _Arg2>
-struct project2nd : public _Project2nd<_Arg1, _Arg2> {};
-/** @}  */
-
-// extension documented next
-template <class _Result>
-struct _Constant_void_fun {
-  typedef _Result result_type;
-  result_type _M_val;
-
-  _Constant_void_fun(const result_type& __v) : _M_val(__v) {}
-  const result_type& operator()() const { return _M_val; }
-};
-
-template <class _Result, class _Argument>
-struct _Constant_unary_fun {
-  typedef _Argument argument_type;
-  typedef  _Result  result_type;
-  result_type _M_val;
-
-  _Constant_unary_fun(const result_type& __v) : _M_val(__v) {}
-  const result_type& operator()(const _Argument&) const { return _M_val; }
-};
-
-template <class _Result, class _Arg1, class _Arg2>
-struct _Constant_binary_fun {
-  typedef  _Arg1   first_argument_type;
-  typedef  _Arg2   second_argument_type;
-  typedef  _Result result_type;
-  _Result _M_val;
-
-  _Constant_binary_fun(const _Result& __v) : _M_val(__v) {}
-  const result_type& operator()(const _Arg1&, const _Arg2&) const {
-    return _M_val;
-  }
-};
-
-/** These three functors are each constructed from a single arbitrary
- *  variable/value.  Later, their @c operator()s completely ignore any
- *  arguments passed, and return the stored value.
- *  - @c constant_void_fun's @c operator() takes no arguments
- *  - @c constant_unary_fun's @c operator() takes one argument (ignored)
- *  - @c constant_binary_fun's @c operator() takes two arguments (ignored)
- *
- *  The helper creator functions @c constant0, @c constant1, and
- *  @c constant2 each take a "result" argument and construct variables of
- *  the appropriate functor type.
- *
- *  @addtogroup SGIextensions
- *  @{
-*/
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Result>
-struct constant_void_fun : public _Constant_void_fun<_Result> {
-  constant_void_fun(const _Result& __v) : _Constant_void_fun<_Result>(__v) {}
-};
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Result,
-          class _Argument = _Result>
-struct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument>
-{
-  constant_unary_fun(const _Result& __v)
-    : _Constant_unary_fun<_Result, _Argument>(__v) {}
-};
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Result,
-          class _Arg1 = _Result,
-          class _Arg2 = _Arg1>
-struct constant_binary_fun
-  : public _Constant_binary_fun<_Result, _Arg1, _Arg2>
-{
-  constant_binary_fun(const _Result& __v)
-    : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {}
-};
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Result>
-inline constant_void_fun<_Result> constant0(const _Result& __val)
-{
-  return constant_void_fun<_Result>(__val);
-}
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Result>
-inline constant_unary_fun<_Result,_Result> constant1(const _Result& __val)
-{
-  return constant_unary_fun<_Result,_Result>(__val);
-}
-
-/// An \link SGIextensions SGI extension \endlink.
-template <class _Result>
-inline constant_binary_fun<_Result,_Result,_Result>
-constant2(const _Result& __val)
-{
-  return constant_binary_fun<_Result,_Result,_Result>(__val);
-}
-/** @}  */
-
-/** The @c subtractive_rng class is documented on
- *  <a href="http://www.sgi.com/tech/stl/">SGI's site</a>.
- *  Note that this code assumes that @c int is 32 bits.
- *
- *  @ingroup SGIextensions
-*/
-class subtractive_rng : public unary_function<unsigned int, unsigned int> {
-private:
-  unsigned int _M_table[55];
-  size_t _M_index1;
-  size_t _M_index2;
-public:
-  /// Returns a number less than the argument.
-  unsigned int operator()(unsigned int __limit) {
-    _M_index1 = (_M_index1 + 1) % 55;
-    _M_index2 = (_M_index2 + 1) % 55;
-    _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2];
-    return _M_table[_M_index1] % __limit;
-  }
-
-  void _M_initialize(unsigned int __seed)
+  using std::unary_function;
+  using std::binary_function;
+  using std::mem_fun1_t;
+  using std::const_mem_fun1_t;
+  using std::mem_fun1_ref_t;
+  using std::const_mem_fun1_ref_t;
+
+  /** The @c identity_element functions are not part of the C++ standard; SGI
+   *  provided them as an extension.  Its argument is an operation, and its
+   *  return value is the identity element for that operation.  It is overloaded
+   *  for addition and multiplication, and you can overload it for your own
+   *  nefarious operations.
+   *
+   *  @addtogroup SGIextensions
+   *  @{
+   */
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Tp>
+    inline _Tp
+    identity_element(std::plus<_Tp>)
+    { return _Tp(0); }
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Tp>
+    inline _Tp
+    identity_element(std::multiplies<_Tp>)
+    { return _Tp(1); }
+  /** @}  */
+  
+  /** As an extension to the binders, SGI provided composition functors and
+   *  wrapper functions to aid in their creation.  The @c unary_compose
+   *  functor is constructed from two functions/functors, @c f and @c g.
+   *  Calling @c operator() with a single argument @c x returns @c f(g(x)).
+   *  The function @c compose1 takes the two functions and constructs a
+   *  @c unary_compose variable for you.
+   *
+   *  @c binary_compose is constructed from three functors, @c f, @c g1,
+   *  and @c g2.  Its @c operator() returns @c f(g1(x),g2(x)).  The function
+   *  @compose2 takes f, g1, and g2, and constructs the @c binary_compose
+   *  instance for you.  For example, if @c f returns an int, then
+   *  \code
+   *  int answer = (compose2(f,g1,g2))(x);
+   *  \endcode
+   *  is equivalent to
+   *  \code
+   *  int temp1 = g1(x);
+   *  int temp2 = g2(x);
+   *  int answer = f(temp1,temp2);
+   *  \endcode
+   *  But the first form is more compact, and can be passed around as a
+   *  functor to other algorithms.
+   *
+   *  @addtogroup SGIextensions
+   *  @{
+   */
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Operation1, class _Operation2>
+    class unary_compose
+    : public unary_function<typename _Operation2::argument_type,
+			    typename _Operation1::result_type>
+    {
+    protected:
+      _Operation1 _M_fn1;
+      _Operation2 _M_fn2;
+
+    public:
+      unary_compose(const _Operation1& __x, const _Operation2& __y)
+      : _M_fn1(__x), _M_fn2(__y) {}
+
+      typename _Operation1::result_type
+      operator()(const typename _Operation2::argument_type& __x) const
+      { return _M_fn1(_M_fn2(__x)); }
+    };
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Operation1, class _Operation2>
+    inline unary_compose<_Operation1, _Operation2>
+    compose1(const _Operation1& __fn1, const _Operation2& __fn2)
+    { return unary_compose<_Operation1,_Operation2>(__fn1, __fn2); }
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Operation1, class _Operation2, class _Operation3>
+    class binary_compose
+    : public unary_function<typename _Operation2::argument_type,
+			    typename _Operation1::result_type>
+    {
+    protected:
+      _Operation1 _M_fn1;
+      _Operation2 _M_fn2;
+      _Operation3 _M_fn3;
+      
+    public:
+      binary_compose(const _Operation1& __x, const _Operation2& __y,
+		     const _Operation3& __z)
+      : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { }
+
+      typename _Operation1::result_type
+      operator()(const typename _Operation2::argument_type& __x) const
+      { return _M_fn1(_M_fn2(__x), _M_fn3(__x)); }
+    };
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Operation1, class _Operation2, class _Operation3>
+    inline binary_compose<_Operation1, _Operation2, _Operation3>
+    compose2(const _Operation1& __fn1, const _Operation2& __fn2,
+	     const _Operation3& __fn3)
+    { return binary_compose<_Operation1, _Operation2, _Operation3>
+	(__fn1, __fn2, __fn3); }
+  /** @}  */
+
+  /** As an extension, SGI provided a functor called @c identity.  When a
+   *  functor is required but no operations are desired, this can be used as a
+   *  pass-through.  Its @c operator() returns its argument unchanged.
+   *
+   *  @addtogroup SGIextensions
+   */
+  template <class _Tp>
+    struct identity : public std::_Identity<_Tp> {};
+
+  /** @c select1st and @c select2nd are extensions provided by SGI.  Their
+   *  @c operator()s
+   *  take a @c std::pair as an argument, and return either the first member
+   *  or the second member, respectively.  They can be used (especially with
+   *  the composition functors) to "strip" data from a sequence before
+   *  performing the remainder of an algorithm.
+   *
+   *  @addtogroup SGIextensions
+   *  @{
+   */
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Pair>
+    struct select1st : public std::_Select1st<_Pair> {};
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Pair>
+    struct select2nd : public std::_Select2nd<_Pair> {};
+  /** @}  */
+
+  // extension documented next
+  template <class _Arg1, class _Arg2>
+    struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1>
+    {
+      _Arg1
+      operator()(const _Arg1& __x, const _Arg2&) const
+      { return __x; }
+    };
+
+  template <class _Arg1, class _Arg2>
+    struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2>
+    {
+      _Arg2
+      operator()(const _Arg1&, const _Arg2& __y) const
+      { return __y; }
+    };
+
+  /** The @c operator() of the @c project1st functor takes two arbitrary
+   *  arguments and returns the first one, while @c project2nd returns the
+   *  second one.  They are extensions provided by SGI.
+   *
+   *  @addtogroup SGIextensions
+   *  @{
+   */
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Arg1, class _Arg2>
+    struct project1st : public _Project1st<_Arg1, _Arg2> {};
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Arg1, class _Arg2>
+    struct project2nd : public _Project2nd<_Arg1, _Arg2> {};
+  /** @}  */
+
+  // extension documented next
+  template <class _Result>
+    struct _Constant_void_fun
+    {
+      typedef _Result result_type;
+      result_type _M_val;
+
+      _Constant_void_fun(const result_type& __v) : _M_val(__v) {}
+
+      const result_type&
+      operator()() const
+      { return _M_val; }
+    };
+
+  template <class _Result, class _Argument>
+    struct _Constant_unary_fun
+    {
+      typedef _Argument argument_type;
+      typedef  _Result  result_type;
+      result_type _M_val;
+      
+      _Constant_unary_fun(const result_type& __v) : _M_val(__v) {}
+
+      const result_type&
+      operator()(const _Argument&) const
+      { return _M_val; }
+    };
+
+  template <class _Result, class _Arg1, class _Arg2>
+    struct _Constant_binary_fun
+    {
+      typedef  _Arg1   first_argument_type;
+      typedef  _Arg2   second_argument_type;
+      typedef  _Result result_type;
+      _Result _M_val;
+
+      _Constant_binary_fun(const _Result& __v) : _M_val(__v) {}
+      
+      const result_type&
+      operator()(const _Arg1&, const _Arg2&) const
+      { return _M_val; }
+    };
+
+  /** These three functors are each constructed from a single arbitrary
+   *  variable/value.  Later, their @c operator()s completely ignore any
+   *  arguments passed, and return the stored value.
+   *  - @c constant_void_fun's @c operator() takes no arguments
+   *  - @c constant_unary_fun's @c operator() takes one argument (ignored)
+   *  - @c constant_binary_fun's @c operator() takes two arguments (ignored)
+   *
+   *  The helper creator functions @c constant0, @c constant1, and
+   *  @c constant2 each take a "result" argument and construct variables of
+   *  the appropriate functor type.
+   *
+   *  @addtogroup SGIextensions
+   *  @{
+   */
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Result>
+    struct constant_void_fun
+    : public _Constant_void_fun<_Result>
+    {
+      constant_void_fun(const _Result& __v)
+      : _Constant_void_fun<_Result>(__v) {}
+    };
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Result, class _Argument = _Result>
+    struct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument>
+    {
+      constant_unary_fun(const _Result& __v)
+      : _Constant_unary_fun<_Result, _Argument>(__v) {}
+    };
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Result, class _Arg1 = _Result, class _Arg2 = _Arg1>
+    struct constant_binary_fun
+    : public _Constant_binary_fun<_Result, _Arg1, _Arg2>
+    {
+      constant_binary_fun(const _Result& __v)
+      : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {}
+    };
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Result>
+    inline constant_void_fun<_Result>
+    constant0(const _Result& __val)
+    { return constant_void_fun<_Result>(__val); }
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Result>
+    inline constant_unary_fun<_Result, _Result>
+    constant1(const _Result& __val)
+    { return constant_unary_fun<_Result, _Result>(__val); }
+
+  /// An \link SGIextensions SGI extension \endlink.
+  template <class _Result>
+    inline constant_binary_fun<_Result,_Result,_Result>
+    constant2(const _Result& __val)
+    { return constant_binary_fun<_Result, _Result, _Result>(__val); }
+  /** @}  */
+
+  /** The @c subtractive_rng class is documented on
+   *  <a href="http://www.sgi.com/tech/stl/">SGI's site</a>.
+   *  Note that this code assumes that @c int is 32 bits.
+   *
+   *  @ingroup SGIextensions
+   */
+  class subtractive_rng
+  : public unary_function<unsigned int, unsigned int>
   {
-    unsigned int __k = 1;
-    _M_table[54] = __seed;
-    size_t __i;
-    for (__i = 0; __i < 54; __i++) {
-        size_t __ii = (21 * (__i + 1) % 55) - 1;
-        _M_table[__ii] = __k;
-        __k = __seed - __k;
-        __seed = _M_table[__ii];
+  private:
+    unsigned int _M_table[55];
+    size_t _M_index1;
+    size_t _M_index2;
+
+  public:
+    /// Returns a number less than the argument.
+    unsigned int
+    operator()(unsigned int __limit)
+    {
+      _M_index1 = (_M_index1 + 1) % 55;
+      _M_index2 = (_M_index2 + 1) % 55;
+      _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2];
+      return _M_table[_M_index1] % __limit;
     }
-    for (int __loop = 0; __loop < 4; __loop++) {
-        for (__i = 0; __i < 55; __i++)
+
+    void
+    _M_initialize(unsigned int __seed)
+    {
+      unsigned int __k = 1;
+      _M_table[54] = __seed;
+      size_t __i;
+      for (__i = 0; __i < 54; __i++)
+	{
+	  size_t __ii = (21 * (__i + 1) % 55) - 1;
+	  _M_table[__ii] = __k;
+	  __k = __seed - __k;
+	  __seed = _M_table[__ii];
+	}
+      for (int __loop = 0; __loop < 4; __loop++)
+	{
+	  for (__i = 0; __i < 55; __i++)
             _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55];
+	}
+      _M_index1 = 0;
+      _M_index2 = 31;
     }
-    _M_index1 = 0;
-    _M_index2 = 31;
-  }
-
-  /// Ctor allowing you to initialize the seed.
-  subtractive_rng(unsigned int __seed) { _M_initialize(__seed); }
-  /// Default ctor; initializes its state with some number you don't see.
-  subtractive_rng() { _M_initialize(161803398u); }
-};
-
-// Mem_fun adaptor helper functions mem_fun1 and mem_fun1_ref,
-// provided for backward compatibility, they are no longer part of
-// the C++ standard.
-
-template <class _Ret, class _Tp, class _Arg>
-inline mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg))
-  { return mem_fun1_t<_Ret,_Tp,_Arg>(__f); }
-
-template <class _Ret, class _Tp, class _Arg>
-inline const_mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg) const)
-  { return const_mem_fun1_t<_Ret,_Tp,_Arg>(__f); }
-
-template <class _Ret, class _Tp, class _Arg>
-inline mem_fun1_ref_t<_Ret,_Tp,_Arg> mem_fun1_ref(_Ret (_Tp::*__f)(_Arg))
-  { return mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }
-
-template <class _Ret, class _Tp, class _Arg>
-inline const_mem_fun1_ref_t<_Ret,_Tp,_Arg>
-mem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const)
-  { return const_mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }
-} // namespace __gnu_cxx
 
+    /// Ctor allowing you to initialize the seed.
+    subtractive_rng(unsigned int __seed)
+    { _M_initialize(__seed); }
+
+    /// Default ctor; initializes its state with some number you don't see.
+    subtractive_rng()
+    { _M_initialize(161803398u); }
+  };
+
+  // Mem_fun adaptor helper functions mem_fun1 and mem_fun1_ref,
+  // provided for backward compatibility, they are no longer part of
+  // the C++ standard.
+  
+  template <class _Ret, class _Tp, class _Arg>
+    inline mem_fun1_t<_Ret, _Tp, _Arg>
+    mem_fun1(_Ret (_Tp::*__f)(_Arg))
+    { return mem_fun1_t<_Ret, _Tp, _Arg>(__f); }
+
+  template <class _Ret, class _Tp, class _Arg>
+    inline const_mem_fun1_t<_Ret, _Tp, _Arg>
+    mem_fun1(_Ret (_Tp::*__f)(_Arg) const)
+    { return const_mem_fun1_t<_Ret, _Tp, _Arg>(__f); }
+
+  template <class _Ret, class _Tp, class _Arg>
+    inline mem_fun1_ref_t<_Ret, _Tp, _Arg>
+    mem_fun1_ref(_Ret (_Tp::*__f)(_Arg))
+    { return mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); }
+
+  template <class _Ret, class _Tp, class _Arg>
+    inline const_mem_fun1_ref_t<_Ret, _Tp, _Arg>
+    mem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const)
+    { return const_mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); }
+} // namespace __gnu_cxx
 #endif
 
diff --git a/libstdc++-v3/include/ext/hash_fun.h b/libstdc++-v3/include/ext/hash_fun.h
index 27453a6..65d8a36 100644
--- a/libstdc++-v3/include/ext/hash_fun.h
+++ b/libstdc++-v3/include/ext/hash_fun.h
@@ -1,6 +1,6 @@
 // 'struct hash' from SGI -*- C++ -*-
 
-// Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 2003, 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
@@ -68,55 +68,105 @@ namespace __gnu_cxx
 {
   using std::size_t;
 
-  template <class _Key> struct hash { };
+  template<class _Key>
+    struct hash { };
 
   inline size_t
   __stl_hash_string(const char* __s)
   {
     unsigned long __h = 0;
     for ( ; *__s; ++__s)
-      __h = 5*__h + *__s;
+      __h = 5 * __h + *__s;
     return size_t(__h);
   }
 
-  template<> struct hash<char*>
-  {
-    size_t operator()(const char* __s) const
-    { return __stl_hash_string(__s); }
-  };
-
-  template<> struct hash<const char*>
-  {
-    size_t operator()(const char* __s) const
-    { return __stl_hash_string(__s); }
-  };
-
-  template<> struct hash<char>
-  { size_t operator()(char __x) const { return __x; } };
-
-  template<> struct hash<unsigned char>
-  { size_t operator()(unsigned char __x) const { return __x; } };
-
-  template<> struct hash<signed char>
-  { size_t operator()(unsigned char __x) const { return __x; } };
-
-  template<> struct hash<short>
-  { size_t operator()(short __x) const { return __x; } };
-
-  template<> struct hash<unsigned short>
-  { size_t operator()(unsigned short __x) const { return __x; } };
-
-  template<> struct hash<int>
-  { size_t operator()(int __x) const { return __x; } };
-
-  template<> struct hash<unsigned int>
-  { size_t operator()(unsigned int __x) const { return __x; } };
-
-  template<> struct hash<long>
-  { size_t operator()(long __x) const { return __x; } };
-
-  template<> struct hash<unsigned long>
-  { size_t operator()(unsigned long __x) const { return __x; } };
+  template<>
+    struct hash<char*>
+    {
+      size_t
+      operator()(const char* __s) const
+      { return __stl_hash_string(__s); }
+    };
+
+  template<>
+    struct hash<const char*>
+    {
+      size_t
+      operator()(const char* __s) const
+      { return __stl_hash_string(__s); }
+    };
+
+  template<>
+    struct hash<char>
+    { 
+      size_t
+      operator()(char __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<unsigned char>
+    { 
+      size_t
+      operator()(unsigned char __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<signed char>
+    {
+      size_t
+      operator()(unsigned char __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<short>
+    {
+      size_t
+      operator()(short __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<unsigned short>
+    {
+      size_t
+      operator()(unsigned short __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<int>
+    { 
+      size_t 
+      operator()(int __x) const 
+      { return __x; }
+    };
+
+  template<>
+    struct hash<unsigned int>
+    { 
+      size_t
+      operator()(unsigned int __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<long>
+    {
+      size_t
+      operator()(long __x) const
+      { return __x; }
+    };
+
+  template<>
+    struct hash<unsigned long>
+    {
+      size_t
+      operator()(unsigned long __x) const
+      { return __x; }
+    };
 } // namespace __gnu_cxx
 
 #endif
diff --git a/libstdc++-v3/include/ext/iterator b/libstdc++-v3/include/ext/iterator
index 094313c..12edab969 100644
--- a/libstdc++-v3/include/ext/iterator
+++ b/libstdc++-v3/include/ext/iterator
@@ -1,6 +1,6 @@
 // HP/SGI iterator extensions -*- C++ -*-
 
-// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 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
@@ -81,7 +81,11 @@ namespace __gnu_cxx
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
-      while (__first != __last) { ++__first; ++__n; }
+      while (__first != __last)
+	{
+	  ++__first;
+	  ++__n;
+	}
     }
 
   template<typename _RandomAccessIterator, typename _Distance>
@@ -90,7 +94,8 @@ namespace __gnu_cxx
 	       _Distance& __n, std::random_access_iterator_tag)
     {
       // concept requirements
-      __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
+      __glibcxx_function_requires(_RandomAccessIteratorConcept<
+				  _RandomAccessIterator>)
       __n += __last - __first;
     }
 
diff --git a/libstdc++-v3/src/string-inst.cc b/libstdc++-v3/src/string-inst.cc
index e01dbca..4c49453 100644
--- a/libstdc++-v3/src/string-inst.cc
+++ b/libstdc++-v3/src/string-inst.cc
@@ -76,6 +76,11 @@ namespace std
     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 --git a/libstdc++-v3/testsuite/performance/21_strings/string_find.cc b/libstdc++-v3/testsuite/performance/21_strings/string_find.cc
new file mode 100644
index 0000000..94259fa
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/21_strings/string_find.cc
@@ -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;
+}