gwyn@smoke.brl.mil (Doug Gwyn) (09/16/90)
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);