Path: utzoo!attcan!uunet!allbery
From: gwyn@smoke.brl.mil (Doug Gwyn)
Newsgroups: comp.sources.misc
Subject: v14i096: patch to strstr.c
Summary: speedup patch for posted source code
Keywords: strstr C library source code patch
Message-ID: <105000@uunet.UU.NET>
Date: 16 Sep 90 01:08:09 GMT
Sender: allbery@uunet.UU.NET
Organization: U.S. Army Ballistic Research Laboratory (BRL), APG, MD.
Lines: 66
Approved: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
X-UNIX-From: gwyn@smoke.brl.mil

Posting-number: Volume 14, Issue 96
Submitted-by: Doug Gwyn <gwyn@smoke.brl.mil>
Archive-name: strstr/patch01

The following is an "official" patch for the implementation of strstr.c
I recently posted.  It removes an avoidable inefficiency in the algorithm.
Thanks to Arthur David Olson for discovering this improvement.

*** /usr/src/s5/src/libc/port/gen/strstr.c	Fri Aug 24 17:08:10 1990
--- strstr.c	Sun Sep  2 01:46:31 1990
***************
*** 1,7 ****
  /*
  	strstr - public-domain implementation of standard C library function
  
! 	last edit:	24-Aug-1990	D A Gwyn
  
  	This is an original implementation based on an idea by D M Sunday,
  	essentially the "quick search" algorithm described in CACM V33 N8.
--- 1,7 ----
  /*
  	strstr - public-domain implementation of standard C library function
  
! 	last edit:	02-Sep-1990	D A Gwyn
  
  	This is an original implementation based on an idea by D M Sunday,
  	essentially the "quick search" algorithm described in CACM V33 N8.
***************
*** 72,77 ****
--- 72,78 ----
  	register cuc	*p;		/* -> pattern char being tested */
  	register cuc	*tx;		/* -> possible start of match */
  	register size_t	m;		/* length of pattern */
+ 	register cuc	*top;		/* -> high water mark in text */
  #if UCHAR_MAX > 255			/* too large for auto allocation */
  	static				/* not malloc()ed; that can fail! */
  #endif					/* else allocate shift[] on stack */
***************
*** 121,127 ****
  
  	/* Try to find the pattern in the text string: */
  
! 	for ( tx = (cuc *)s1; ; tx += shift[*t] )
  		{
  		for ( t = tx, p = (cuc *)s2; ; ++t, ++p )
  			{
--- 122,128 ----
  
  	/* Try to find the pattern in the text string: */
  
! 	for ( top = tx = (cuc *)s1; ; tx += shift[*(top = t)] )
  		{
  		for ( t = tx, p = (cuc *)s2; ; ++t, ++p )
  			{
***************
*** 131,136 ****
--- 132,140 ----
  			if ( *p != *t )
  				break;
  			}
+ 
+ 		if ( t < top )		/* idea due to ado@elsie.nci.nih.gov */
+ 			t = top;	/* already scanned this far for EOS */
  
  		do	{
  			assert(m > 0);