"Fossies" - the Fresh Open Source Software Archive

Member "leafnode-1.12.0/wildmat.c" (30 Jan 2009, 5133 Bytes) of package /linux/misc/leafnode-1.12.0.tar.xz:


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 #include "leafnode.h"
    2 
    3 #ifdef WITH_DMALLOC
    4 #include <dmalloc.h>
    5 #endif
    6 
    7 /**************************************************************************/
    8 /*
    9  * The following routines comprise the wildmat routine. Written by
   10  * Rich $alz, taken vom INN 2.2.2
   11  */
   12 
   13 /*
   14 **
   15 **  Do shell-style pattern matching for ?, \, [], and * characters.
   16 **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
   17 **  could cause a segmentation violation.  It is 8bit clean.
   18 **
   19 **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
   20 **  Rich $alz is now <rsalz@osf.org>.
   21 **  April, 1991:  Replaced mutually-recursive calls with in-line code
   22 **  for the star character.
   23 **
   24 **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
   25 **  This can greatly speed up failing wildcard patterns.  For example:
   26 **  pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
   27 **  text 1:  -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
   28 **  text 2:  -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
   29 **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
   30 **  the ABORT code, it takes 22310 calls to fail.  Ugh.  The following
   31 **  explanation is from Lars:
   32 **  The precondition that must be fulfilled is that DoMatch will consume
   33 **  at least one character in text.  This is true if *p is neither '*' nor
   34 **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
   35 **  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
   36 **  FALSE, each star-loop has to run to the end of the text; with ABORT
   37 **  only the last one does.
   38 **
   39 **  Once the control of one instance of DoMatch enters the star-loop, that
   40 **  instance will return either TRUE or ABORT, and any calling instance
   41 **  will therefore return immediately after (without calling recursively
   42 **  again).  In effect, only one star-loop is ever active.  It would be
   43 **  possible to modify the code to maintain this context explicitly,
   44 **  eliminating all recursive calls at the cost of some complication and
   45 **  loss of clarity (and the ABORT stuff seems to be unclear enough by
   46 **  itself).  I think it would be unwise to try to get this into a
   47 **  released version unless you have a good test data base to try it out
   48 **  on.
   49 */
   50 /* YOU MUST NOT DEFINE ABORT TO 1, LEAVE AT -1 (would collide with TRUE)
   51  */
   52 #define ABORT           -1
   53     /* What character marks an inverted character class? */
   54 #define NEGATE_CLASS        '^'
   55     /* Is "*" a common pattern? */
   56 #define OPTIMIZE_JUST_STAR
   57     /* Do tar(1) matching rules, which ignore a trailing slash? */
   58 #undef MATCH_TAR_PATTERN
   59 /*
   60  *  Match text and p, return TRUE (match), FALSE (no match), or ABORT
   61  *  (quick, no match).  */
   62 static int
   63 DoMatch(const char *text, const char *p)
   64 {
   65     int last;
   66     int matched;
   67     int reverse;
   68 
   69     for (; *p; text++, p++) {
   70     if (*text == '\0' && *p != '*')
   71         return ABORT;
   72     switch (*p) {
   73     case '\\':
   74         /* Literal match with following character. */
   75         p++;
   76         /* FALLTHROUGH */
   77     default:
   78         if (*text != *p)
   79         return FALSE;
   80         continue;
   81     case '?':
   82         /* Match anything. */
   83         continue;
   84     case '*':
   85         while (*++p == '*')
   86         /* Consecutive stars act just like one. */
   87         continue;
   88         if (*p == '\0')
   89         /* Trailing star matches everything. */
   90         return TRUE;
   91         while (*text)
   92         if ((matched = DoMatch(text++, p)))
   93             return matched;
   94         return ABORT;
   95     case '[':
   96         reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
   97         if (reverse)
   98         /* Inverted character class. */
   99         p++;
  100         matched = FALSE;
  101         if (p[1] == ']' || p[1] == '-')
  102         if (*++p == *text)
  103             matched = TRUE;
  104         for (last = *p; *++p && *p != ']'; last = *p)
  105         /* This next line requires a good C compiler. */
  106         if (*p == '-' && p[1] != ']'
  107             ? *text <= *++p && *text >= last : *text == *p)
  108             matched = TRUE;
  109         if (matched == reverse)
  110         return FALSE;
  111         continue;
  112     }
  113     }
  114 #ifdef  MATCH_TAR_PATTERN
  115     if (*text == '/')
  116     return TRUE;
  117 #endif              /* MATCH_TAR_PATTERN */
  118     return *text == '\0';
  119 }
  120 
  121 /*
  122 **  User-level routine.  Returns TRUE or FALSE.
  123 **  This routine was borrowed from Rich Salz and appeared first in INN.
  124 */
  125 int
  126 wildmat(const char *text, const char *p)
  127 {
  128 #ifdef  OPTIMIZE_JUST_STAR
  129     if (p[0] == '*' && p[1] == '\0')
  130     return TRUE;
  131 #endif              /* OPTIMIZE_JUST_STAR */
  132     return (DoMatch(text, p) == TRUE) ? TRUE : FALSE;
  133 }
  134 
  135 #ifdef  TEST
  136 #include <stdio.h>
  137 
  138 int main(void)
  139 {
  140     char     p[8000]; /* RATS: ignore */
  141     char     text[8000]; /* RATS: ignore */
  142 
  143     printf("Wildmat tester.  Enter pattern, then strings to test.\n");
  144     printf("A blank line gets prompts for a new pattern; a blank pattern\n");
  145     printf("exits the program.\n");
  146 
  147     for ( ; ; ) {
  148     printf("\nEnter pattern:  ");
  149     (void)fflush(stdout);
  150     if (fgets(p, sizeof(p), stdin) == NULL || p[0] == '\n' || !*p)
  151         break;
  152     for ( ; ; ) {
  153         printf("Enter text:  ");
  154         (void)fflush(stdout);
  155         if (fgets(text, sizeof(text), stdin) == NULL)
  156         exit(0);
  157         if (text[0] == '\n' || !*p)
  158         /* Blank line; go back and get a new pattern. */
  159         break;
  160         printf("      %s\n", wildmat(text, p) ? "YES" : "NO");
  161     }
  162     }
  163 
  164     exit(0);
  165     /* NOTREACHED */
  166 }
  167 #endif  /* TEST */