home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume14 / strstr / patch01 < prev    next >
Encoding:
Text File  |  1990-09-15  |  2.3 KB  |  77 lines
  1. Newsgroups: comp.sources.misc
  2. X-UNIX-From: gwyn@smoke.brl.mil
  3. organization: U.S. Army Ballistic Research Laboratory (BRL), APG, MD.
  4. keywords: strstr C library source code patch
  5. summary: speedup patch for posted source code
  6. subject: v14i096: patch to strstr.c
  7. from: Doug Gwyn <gwyn@smoke.brl.mil>
  8. Sender: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
  9.  
  10. Posting-number: Volume 14, Issue 96
  11. Submitted-by: Doug Gwyn <gwyn@smoke.brl.mil>
  12. Archive-name: strstr/patch01
  13.  
  14. The following is an "official" patch for the implementation of strstr.c
  15. I recently posted.  It removes an avoidable inefficiency in the algorithm.
  16. Thanks to Arthur David Olson for discovering this improvement.
  17.  
  18. *** /usr/src/s5/src/libc/port/gen/strstr.c    Fri Aug 24 17:08:10 1990
  19. --- strstr.c    Sun Sep  2 01:46:31 1990
  20. ***************
  21. *** 1,7 ****
  22.   /*
  23.       strstr - public-domain implementation of standard C library function
  24.   
  25. !     last edit:    24-Aug-1990    D A Gwyn
  26.   
  27.       This is an original implementation based on an idea by D M Sunday,
  28.       essentially the "quick search" algorithm described in CACM V33 N8.
  29. --- 1,7 ----
  30.   /*
  31.       strstr - public-domain implementation of standard C library function
  32.   
  33. !     last edit:    02-Sep-1990    D A Gwyn
  34.   
  35.       This is an original implementation based on an idea by D M Sunday,
  36.       essentially the "quick search" algorithm described in CACM V33 N8.
  37. ***************
  38. *** 72,77 ****
  39. --- 72,78 ----
  40.       register cuc    *p;        /* -> pattern char being tested */
  41.       register cuc    *tx;        /* -> possible start of match */
  42.       register size_t    m;        /* length of pattern */
  43. +     register cuc    *top;        /* -> high water mark in text */
  44.   #if UCHAR_MAX > 255            /* too large for auto allocation */
  45.       static                /* not malloc()ed; that can fail! */
  46.   #endif                    /* else allocate shift[] on stack */
  47. ***************
  48. *** 121,127 ****
  49.   
  50.       /* Try to find the pattern in the text string: */
  51.   
  52. !     for ( tx = (cuc *)s1; ; tx += shift[*t] )
  53.           {
  54.           for ( t = tx, p = (cuc *)s2; ; ++t, ++p )
  55.               {
  56. --- 122,128 ----
  57.   
  58.       /* Try to find the pattern in the text string: */
  59.   
  60. !     for ( top = tx = (cuc *)s1; ; tx += shift[*(top = t)] )
  61.           {
  62.           for ( t = tx, p = (cuc *)s2; ; ++t, ++p )
  63.               {
  64. ***************
  65. *** 131,136 ****
  66. --- 132,140 ----
  67.               if ( *p != *t )
  68.                   break;
  69.               }
  70. + 
  71. +         if ( t < top )        /* idea due to ado@elsie.nci.nih.gov */
  72. +             t = top;    /* already scanned this far for EOS */
  73.   
  74.           do    {
  75.               assert(m > 0);
  76.  
  77.