1 /* $XConsortium: wildmat.c,v 1.2 94/04/13 18:40:59 rws Exp $ */
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.
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.
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.
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
40 #include "transmission.h"
45 /* What character marks an inverted character class? */
46 #define NEGATE_CLASS '^'
47 /* Is "*" a common pattern? */
48 #define OPTIMIZE_JUST_STAR
49 /* Do tar(1) matching rules, which ignore a trailing slash? */
50 #undef MATCH_TAR_PATTERN
54 ** Match text and p, return TRUE, FALSE, or ABORT.
57 DoMatch( const char * text
, const char * p
)
63 for ( ; *p
; text
++, p
++) {
64 if (*text
== '\0' && *p
!= '*')
68 /* Literal match with following character. */
80 /* Consecutive stars act just like one. */
83 /* Trailing star matches everything. */
86 if ((matched
= DoMatch(text
++, p
)) != FALSE
)
90 reverse
= p
[1] == NEGATE_CLASS
? TRUE
: FALSE
;
92 /* Inverted character class. */
94 for (last
= 0400, matched
= FALSE
; *++p
&& *p
!= ']'; last
= *p
)
95 /* This next line requires a good C compiler. */
96 if (*p
== '-' ? *text
<= *++p
&& *text
>= last
: *text
== *p
)
98 if (matched
== reverse
)
104 #ifdef MATCH_TAR_PATTERN
107 #endif /* MATCH_TAR_ATTERN */
108 return *text
== '\0';
113 ** User-level routine. Returns TRUE or FALSE.
116 tr_wildmat(const char * text
, const char * p
)
118 if (p
[0] == '*' && p
[1] == '\0')
121 return DoMatch(text
, p
) == TRUE
;