source: trunk/libtransmission/wildmat.c @ 8050

Last change on this file since 8050 was 6798, checked in by charles, 13 years ago

rpc-server cleanups. add true wildmat control. break the Mac build a little harder.

File size: 3.8 KB
Line 
1/* $XConsortium: wildmat.c,v 1.2 94/04/13 18:40:59 rws Exp $ */
2/*
3**
4**  Do shell-style pattern matching for ?, \, [], and * characters.
5**  Might not be robust in face of malformed patterns; e.g., "foo[a-"
6**  could cause a segmentation violation.  It is 8bit clean.
7**
8**  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
9**  Rich $alz is now <rsalz@bbn.com>.
10**  April, 1991:  Replaced mutually-recursive calls with in-line code
11**  for the star character.
12**
13**  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
14**  This can greatly speed up failing wildcard patterns.  For example:
15**      pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
16**      text 1:  -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
17**      text 2:  -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
18**  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
19**  the ABORT, then it takes 22310 calls to fail.  Ugh.  The following
20**  explanation is from Lars:
21**  The precondition that must be fulfilled is that DoMatch will consume
22**  at least one character in text.  This is true if *p is neither '*' nor
23**  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
24**  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
25**  FALSE, each star-loop has to run to the end of the text; with ABORT
26**  only the last one does.
27**
28**  Once the control of one instance of DoMatch enters the star-loop, that
29**  instance will return either TRUE or ABORT, and any calling instance
30**  will therefore return immediately after (without calling recursively
31**  again).  In effect, only one star-loop is ever active.  It would be
32**  possible to modify the code to maintain this context explicitly,
33**  eliminating all recursive calls at the cost of some complication and
34**  loss of clarity (and the ABORT stuff seems to be unclear enough by
35**  itself).  I think it would be unwise to try to get this into a
36**  released version unless you have a good test data base to try it out
37**  on.
38*/
39
40#include "utils.h"
41
42#define TRUE                    1
43#define FALSE                   0
44#define ABORT                   -1
45
46
47    /* What character marks an inverted character class? */
48#define NEGATE_CLASS            '^'
49    /* Is "*" a common pattern? */
50#define OPTIMIZE_JUST_STAR
51    /* Do tar(1) matching rules, which ignore a trailing slash? */
52#undef MATCH_TAR_PATTERN
53
54
55/*
56**  Match text and p, return TRUE, FALSE, or ABORT.
57*/
58static int
59DoMatch( const char * text, const char * p )
60{
61    register int        last;
62    register int        matched;
63    register int        reverse;
64
65    for ( ; *p; text++, p++) {
66        if (*text == '\0' && *p != '*')
67            return ABORT;
68        switch (*p) {
69        case '\\':
70            /* Literal match with following character. */
71            p++;
72            /* FALLTHROUGH */
73        default:
74            if (*text != *p)
75                return FALSE;
76            continue;
77        case '?':
78            /* Match anything. */
79            continue;
80        case '*':
81            while (*++p == '*')
82                /* Consecutive stars act just like one. */
83                continue;
84            if (*p == '\0')
85                /* Trailing star matches everything. */
86                return TRUE;
87            while (*text)
88                if ((matched = DoMatch(text++, p)) != FALSE)
89                    return matched;
90            return ABORT;
91        case '[':
92            reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
93            if (reverse)
94                /* Inverted character class. */
95                p++;
96            for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
97                /* This next line requires a good C compiler. */
98                if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
99                    matched = TRUE;
100            if (matched == reverse)
101                return FALSE;
102            continue;
103        }
104    }
105
106#ifdef  MATCH_TAR_PATTERN
107    if (*text == '/')
108        return TRUE;
109#endif  /* MATCH_TAR_ATTERN */
110    return *text == '\0';
111}
112
113
114/*
115**  User-level routine.  Returns TRUE or FALSE.
116*/
117int
118tr_wildmat(const char * text, const char * p )
119{
120    if (p[0] == '*' && p[1] == '\0')
121        return TRUE;
122
123    return DoMatch(text, p) == TRUE;
124}
Note: See TracBrowser for help on using the repository browser.