[patch, so_7] : search_n optimization

[random at bubblescope dot net]

After quite a long time, an optimized version of search_n :)

Blame me for any mistakes in the formatting and delegation, Dimitris for
any mistakes in the optimised random_access algorithm :) Already plenty
of testcases for this, hence the lack of testcase :) This algorithm can
be very slightly (~5%) slower in some cases, but is almost always much
faster.

This patch is against so_7. If it's too late in the day to merge the
large-scale changes to stl_algo.h and friends to mainline, but there is
still time to submit this patch, I'll knock up a mainline version to
(which would just require duplicating the code for the non-predicated
version as well).

Chris

Attachment: changelog-search_n
Description: application/text

Index: stl_algo.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.47.6.15
diff -u -3 -r1.47.6.15 stl_algo.h
--- stl_algo.h	15 Jul 2005 21:09:42 -0000	1.47.6.15
+++ stl_algo.h	1 Sep 2005 22:22:00 -0000
@@ -604,6 +604,106 @@
  
 
   /**
+   *  @if maint
+   *  This is an uglified
+   *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
+   *	       _BinaryPredicate)
+   *  overloaded for forward iterators.
+   *  @endif
+  */
+  template<typename _ForwardIterator, typename _Integer, typename _Tp,
+           typename _BinaryPredicate>
+    _ForwardIterator
+    __search_n(_ForwardIterator __first, _ForwardIterator __last,
+	     _Integer __count, const _Tp& __val,
+	     _BinaryPredicate __binary_pred, std::forward_iterator_tag)
+    {
+      // concept requirements
+      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+      __glibcxx_requires_valid_range(__first, __last);
+      
+      __first = std::find_if(__first, __last,
+			     __gnu_cxx::__ops::bind2nd(__binary_pred,
+						       __val));
+      while (__first != __last)
+      {
+	typename iterator_traits<_ForwardIterator>::difference_type
+	  __n = __count;
+	_ForwardIterator __i = __first;
+	++__i;
+	while (__i != __last && __n != 1 && *__i == __val)
+	{
+	  ++__i;
+	  --__n;
+	}
+	if (__n == 1)
+	  return __first;
+	if (__i == __last)
+	  return __last;
+	__first = std::find_if(++__i, __last,
+	  		       __gnu_cxx::__ops::bind2nd(__binary_pred,
+	  						 __val));
+      }
+      return __last;
+    }
+
+  /**
+   *  @if maint
+   *  This is an uglified
+   *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
+   *	       _BinaryPredicate)
+   *  overloaded for random access iterators.
+   *  @endif
+  */
+  template<typename _RandomAccessIter, typename _Integer, typename _Tp,
+	   typename _BinaryPredicate>
+    _RandomAccessIter
+    __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
+	       _Integer __count, const _Tp& __val,
+	       _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
+    {
+      
+      typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
+	_DistanceType;
+
+      _DistanceType __tailSize = __last - __first;
+      const _DistanceType __pattSize = __count;
+
+      if (__tailSize < __pattSize)
+        return __last;
+
+      const _DistanceType __skipOffset = __pattSize - 1;
+      _RandomAccessIter __lookAhead = __first + __skipOffset;
+      __tailSize -= __pattSize;
+
+      while (1) // the main loop...
+      {
+        // __lookAhead here is always pointing to the last element of next 
+	// possible match.
+	while (!__binary_pred(*__lookAhead, __val)) // the skip loop...
+	{
+	  if (__tailSize < __pattSize)
+	    return __last;  // Failure
+	  __lookAhead += __pattSize;
+	  __tailSize -= __pattSize;
+	}
+	_DistanceType __remainder = __skipOffset;
+	for (_RandomAccessIter __backTrack = __lookAhead - 1; 
+	     __binary_pred(*__backTrack, __val); --__backTrack)
+	{
+	  if (--__remainder == 0)
+	    return (__lookAhead - __skipOffset); // Success
+	}
+	if (__remainder > __tailSize)
+	  return __last; // Failure
+	__lookAhead += __remainder;
+	__tailSize -= __remainder;
+      }
+    }
+    
+  /**
    *  @brief Search a sequence for a number of consecutive values using a
    *         predicate.
    *  @param  first        A forward iterator.
@@ -625,48 +725,14 @@
 	     _Integer __count, const _Tp& __val,
 	     _BinaryPredicate __binary_pred)
     {
-      // concept requirements
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
-      __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
-	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
-      __glibcxx_requires_valid_range(__first, __last);
-
       if (__count <= 0)
 	return __first;
-      else
-	{
-	  while (__first != __last)
-	    {
-	      if (__binary_pred(*__first, __val))
-		break;
-	      ++__first;
-	    }
-	  while (__first != __last)
-	    {
-	      typename iterator_traits<_ForwardIterator>::difference_type
-		__n = __count;
-	      _ForwardIterator __i = __first;
-	      ++__i;
-	      while (__i != __last && __n != 1 && __binary_pred(*__i, __val))
-		{
-		  ++__i;
-		  --__n;
-		}
-	      if (__n == 1)
-		return __first;
-	      else
-		{
-		  while (__i != __last)
-		    {
-		      if (__binary_pred(*__i, __val))
-			break;
-		      ++__i;
-		    }
-		  __first = __i;
-		}
-	    }
-	  return __last;
-	}
+      if (__count == 1)
+	return std::find_if(__first, __last,
+	  		    __gnu_cxx::__ops::bind2nd(__binary_pred,
+	  					      __val));
+      return std::__search_n(__first, __last, __count, __val, __binary_pred,
+			     std::__iterator_category(__first));
     }
 
   /**