source: trunk/libtransmission/wildmat.c @ 12918

Last change on this file since 12918 was 12204, checked in by jordan, 11 years ago

(trunk) #4138 "use stdbool.h instead of tr_bool" -- done.

File size: 3.8 KB
RevLine 
[6798]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-"
[11599]6**  could cause a segmentation violation. It is 8bit clean.
[6798]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.
[11599]14**  This can greatly speed up failing wildcard patterns. For example:
[6798]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
[11599]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
[6798]20**  explanation is from Lars:
21**  The precondition that must be fulfilled is that DoMatch will consume
[11599]22**  at least one character in text. This is true if *p is neither '*' nor
[12204]23**  '\0'.)  The last return has ABORT instead of false to avoid quadratic
[11599]24**  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx". With
[12204]25**  false, each star-loop has to run to the end of the text; with ABORT
[6798]26**  only the last one does.
27**
28**  Once the control of one instance of DoMatch enters the star-loop, that
[12204]29**  instance will return either true or ABORT, and any calling instance
[6798]30**  will therefore return immediately after (without calling recursively
[11599]31**  again). In effect, only one star-loop is ever active. It would be
[6798]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
[11599]35**  itself). I think it would be unwise to try to get this into a
[6798]36**  released version unless you have a good test data base to try it out
37**  on.
38*/
39
[10521]40#include "transmission.h"
[6798]41#include "utils.h"
42
[10521]43#define ABORT -1
[6798]44
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
51
52
53/*
[12204]54**  Match text and p, return true, false, or ABORT.
[6798]55*/
56static int
57DoMatch( const char * text, const char * p )
58{
59    register int        last;
60    register int        matched;
61    register int        reverse;
62
63    for ( ; *p; text++, p++) {
64        if (*text == '\0' && *p != '*')
65            return ABORT;
66        switch (*p) {
67        case '\\':
68            /* Literal match with following character. */
69            p++;
70            /* FALLTHROUGH */
71        default:
72            if (*text != *p)
[12204]73                return false;
[6798]74            continue;
75        case '?':
76            /* Match anything. */
77            continue;
78        case '*':
79            while (*++p == '*')
80                /* Consecutive stars act just like one. */
81                continue;
82            if (*p == '\0')
83                /* Trailing star matches everything. */
[12204]84                return true;
[6798]85            while (*text)
[12204]86                if ((matched = DoMatch(text++, p)) != false)
[6798]87                    return matched;
88            return ABORT;
89        case '[':
[12204]90            reverse = p[1] == NEGATE_CLASS ? true : false;
[6798]91            if (reverse)
92                /* Inverted character class. */
93                p++;
[12204]94            for (last = 0400, matched = false; *++p && *p != ']'; last = *p)
[6798]95                /* This next line requires a good C compiler. */
96                if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
[12204]97                    matched = true;
[6798]98            if (matched == reverse)
[12204]99                return false;
[6798]100            continue;
101        }
102    }
103
104#ifdef  MATCH_TAR_PATTERN
105    if (*text == '/')
[12204]106        return true;
[6798]107#endif  /* MATCH_TAR_ATTERN */
108    return *text == '\0';
109}
110
111
[12204]112/* User-level routine. returns whether or not 'text' and 'p' matched */
113bool
[6798]114tr_wildmat(const char * text, const char * p )
115{
116    if (p[0] == '*' && p[1] == '\0')
[12204]117        return true;
[6798]118
[12204]119    return DoMatch(text, p) == true;
[6798]120}
Note: See TracBrowser for help on using the repository browser.