v14i096: patch to strstr.c

[Doug Gwyn]

Posting-number: Volume 14, Issue 96
Submitted-by: Doug Gwyn <gwyn at 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 at elsie.nci.nih.gov */
+ 			t = top;	/* already scanned this far for EOS */
  
  		do	{
  			assert(m > 0);