"Fossies" - the Fresh Open Source Software Archive

Member "tin-2.4.1/src/wildmat.c" (12 Oct 2016, 5453 Bytes) of package /linux/misc/tin-2.4.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "wildmat.c" see the Fossies "Dox" file reference documentation.

    1 /*  @Revision: 1.9 @
    2 **
    3 **  Do shell-style pattern matching for ?, \, [], and * characters.
    4 **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
    5 **  could cause a segmentation violation.  It is 8bit clean.
    6 **
    7 **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
    8 **  Rich $alz is now <rsalz@osf.org>.
    9 **  April, 1991:  Replaced mutually-recursive calls with in-line code
   10 **  for the star character.
   11 **
   12 **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
   13 **  This can greatly speed up failing wildcard patterns.  For example:
   14 **  pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
   15 **  text 1:  -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
   16 **  text 2:  -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
   17 **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
   18 **  the ABORT code, it takes 22310 calls to fail.  Ugh.  The following
   19 **  explanation is from Lars:
   20 **  The precondition that must be fulfilled is that DoMatch will consume
   21 **  at least one character in text.  This is true if *p is neither '*' nor
   22 **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
   23 **  behavior in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
   24 **  FALSE, each star-loop has to run to the end of the text; with ABORT
   25 **  only the last one does.
   26 **
   27 **  Once the control of one instance of DoMatch enters the star-loop, that
   28 **  instance will return either TRUE or ABORT, and any calling instance
   29 **  will therefore return immediately after (without calling recursively
   30 **  again).  In effect, only one star-loop is ever active.  It would be
   31 **  possible to modify the code to maintain this context explicitly,
   32 **  eliminating all recursive calls at the cost of some complication and
   33 **  loss of clarity (and the ABORT stuff seems to be unclear enough by
   34 **  itself).  I think it would be unwise to try to get this into a
   35 **  released version unless you have a good test data base to try it out
   36 **  on.
   37 */
   38 
   39 #ifndef TIN_H
   40 #   include "tin.h"
   41 #endif /* !TIN_H */
   42 
   43 #define ABORT   -1
   44 
   45 /* What character marks an inverted character class? */
   46 #define NEGATE_CLASS    '^'
   47 
   48 /* Is "*" a common pattern? */
   49 #define OPTIMIZE_JUST_STAR 1
   50 
   51 /* Do tar(1) matching rules, which ignore a trailing slash? */
   52 #undef MATCH_TAR_PATTERN
   53 
   54 /*
   55  * local prototypes
   56  */
   57 static int DoMatch(const char *text, char *p);
   58 
   59 /*
   60  *  Match text and p, return 1 (TRUE), 0 (FALSE), or -1 (ABORT).
   61  */
   62 
   63 static int
   64 DoMatch(
   65     const char *text,
   66     char *p)
   67 {
   68     int last;
   69     int matched;
   70     int reverse;
   71 
   72     for (; *p; text++, p++) {
   73         if (*text == '\0' && *p != '*')
   74             return ABORT;
   75         switch (*p) {
   76             case '\\':
   77                 /* Literal match with following character. */
   78                 p++;
   79                 /* FALLTHROUGH */
   80             default:
   81                 if (*text != *p)
   82                     return 0;
   83                 continue;
   84             case '?':
   85                 /* Match anything. */
   86                 continue;
   87             case '*':
   88                 while (*++p == '*')
   89                     /* Consecutive stars act just like one. */
   90                     continue;
   91                 if (*p == '\0')
   92                     /* Trailing star matches everything. */
   93                     return 1;
   94                 while (*text)
   95                     if ((matched = DoMatch(text++, p)) != 0)
   96                         return matched;
   97                 return ABORT;
   98             case '[':
   99                 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
  100                 if (reverse)
  101                     /* Inverted character class. */
  102                     p++;
  103                 matched = FALSE;
  104                 if (p[1] == ']' || p[1] == '-')
  105                     if (*++p == *text)
  106                         matched = TRUE;
  107                 for (last = *p; *++p && *p != ']'; last = *p)
  108                     /* This next line requires a good C compiler. */
  109                     if (*p == '-' && p[1] != ']' ? *text <= *++p && *text >= last : *text == *p)
  110                         matched = TRUE;
  111                 if (matched == reverse)
  112                     return 0;
  113                 continue;
  114             }
  115         }
  116 #ifdef MATCH_TAR_PATTERN
  117         if (*text == '/')
  118             return 1;
  119 #endif /* MATCH_TAR_ATTERN */
  120     return *text == '\0';
  121 }
  122 
  123 
  124 /*
  125  * User-level routine. Returns TRUE or FALSE.
  126  */
  127 t_bool
  128 wildmat(
  129     const char *text,
  130     char *p,
  131     t_bool icase)
  132 {
  133     char *txt;
  134     t_bool ret;
  135 
  136     /*
  137      * Make sure the pattern is not NULL
  138      */
  139     if (p == NULL || text == NULL)
  140         return FALSE;
  141 #ifdef OPTIMIZE_JUST_STAR
  142     if (p[0] == '*' && p[1] == '\0')
  143         return TRUE;
  144 #endif /* OPTIMIZE_JUST_STAR */
  145 
  146     if (icase) {
  147         txt = my_strdup(text);
  148         str_lwr(txt);
  149         str_lwr(p);
  150         ret = (DoMatch(txt, p) == TRUE);
  151         free(txt);
  152     } else
  153         ret = (DoMatch(text, p) == TRUE);
  154 
  155     return ret;
  156 }
  157 
  158 
  159 /*
  160  * User-level routine. Calculates position of a match within a line.
  161  * Returns TRUE or FALSE.
  162  */
  163 t_bool
  164 wildmatpos(
  165     const char *text,
  166     char *p,
  167     t_bool icase,
  168     int *srch_offsets,
  169     int srch_offsets_size)
  170 {
  171     char *txt, *t, *px;
  172     int i;
  173     t_bool ret = FALSE;
  174 
  175     if (srch_offsets_size >= 2)
  176         srch_offsets[0] = srch_offsets[1] = 0;
  177 
  178     /*
  179      * Make sure the pattern is not NULL
  180      */
  181     if (p == NULL || text == NULL)
  182         return FALSE;
  183 #ifdef OPTIMIZE_JUST_STAR
  184     if (p[0] == '*' && p[1] == '\0') {
  185         if (srch_offsets_size >= 2) {
  186             srch_offsets[0] = 0;
  187             srch_offsets[1] = strlen(text);
  188         }
  189         return TRUE;
  190     }
  191 #endif /* OPTIMIZE_JUST_STAR */
  192 
  193     txt = my_strdup(text);
  194     if (icase) {
  195         str_lwr(txt);
  196         str_lwr(p);
  197     }
  198 
  199     /* remove the leading '*' */
  200     px = my_strdup(p + 1);
  201 
  202     for (t = txt; *t; t++)
  203         if ((ret = (DoMatch(t, px))) == TRUE) {
  204             /* remove the trailing '*' */
  205             px[strlen(px) - 1] = '\0';
  206             for (i = strlen(t); i > 0; i--) {
  207                 t[i] = '\0';
  208                 if ((ret = (DoMatch(t, px))) == TRUE) {
  209                     if (srch_offsets_size >= 2) {
  210                         srch_offsets[0] = t - txt;
  211                         srch_offsets[1] = srch_offsets[0] + i;
  212                     }
  213                     break;
  214                 }
  215             }
  216             break;
  217         }
  218     free(px);
  219     free(txt);
  220 
  221     return ret;
  222 }