citadel
About: Citadel is an advanced messaging and collaboration system for groupware and BBS applications (preferred OS: Linux).
  Fossies Dox: citadel.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

Loading...
Searching...
No Matches
wildmat.c
Go to the documentation of this file.
1/* wildmat.h - NNTP wildmat processing functions
2 *
3 * Copyright (c) 1994-2008 Carnegie Mellon University. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. The name "Carnegie Mellon University" must not be used to
18 * endorse or promote products derived from this software without
19 * prior written permission. For permission or any legal
20 * details, please contact
21 * Carnegie Mellon University
22 * Center for Technology Transfer and Enterprise Creation
23 * 4615 Forbes Avenue
24 * Suite 302
25 * Pittsburgh, PA 15213
26 * (412) 268-7393, fax: (412) 268-7395
27 * innovation@andrew.cmu.edu
28 *
29 * 4. Redistributions of any form whatsoever must retain the following
30 * acknowledgment:
31 * "This product includes software developed by Computing Services
32 * at Carnegie Mellon University (http://www.cmu.edu/computing/)."
33 *
34 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
35 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
36 * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
37 * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
38 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
39 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
40 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
41 *
42 * $Id: wildmat.c,v 1.4 2010/01/06 17:01:47 murch Exp $
43 */
44
45/*
46**
47** Do shell-style pattern matching for ?, \, [], and * characters.
48** Might not be robust in face of malformed patterns; e.g., "foo[a-"
49** could cause a segmentation violation. It is 8bit clean.
50**
51** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
52** Rich $alz is now <rsalz@osf.org>.
53** April, 1991: Replaced mutually-recursive calls with in-line code
54** for the star character.
55**
56** Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
57** This can greatly speed up failing wildcard patterns. For example:
58** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
59** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
60** text 2: -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
61** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without
62** the ABORT code, it takes 22310 calls to fail. Ugh. The following
63** explanation is from Lars:
64** The precondition that must be fulfilled is that DoMatch will consume
65** at least one character in text. This is true if *p is neither '*' nor
66** '\0'.) The last return has ABORT instead of FALSE to avoid quadratic
67** behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx". With
68** FALSE, each star-loop has to run to the end of the text; with ABORT
69** only the last one does.
70**
71** Once the control of one instance of DoMatch enters the star-loop, that
72** instance will return either TRUE or ABORT, and any calling instance
73** will therefore return immediately after (without calling recursively
74** again). In effect, only one star-loop is ever active. It would be
75** possible to modify the code to maintain this context explicitly,
76** eliminating all recursive calls at the cost of some complication and
77** loss of clarity (and the ABORT stuff seems to be unclear enough by
78** itself). I think it would be unwise to try to get this into a
79** released version unless you have a good test data base to try it out
80** on.
81*/
82#include <stdio.h>
83#include <sys/types.h>
84
85
86
87#define TRUE 1
88#define FALSE 0
89#define ABORT -1
90
91
92 /* What character marks an inverted character class? */
93#define NEGATE_CLASS '^'
94 /* Is "*" a common pattern? */
95#define OPTIMIZE_JUST_STAR
96 /* Do tar(1) matching rules, which ignore a trailing slash? */
97#undef MATCH_TAR_PATTERN
98
99
100/*
101** Match text and p, return TRUE, FALSE, or ABORT.
102*/
103static int DoMatch(const char *text, const char *p)
104{
105 int last;
106 int matched;
107 int reverse;
108
109 for ( ; *p; text++, p++) {
110 if (*text == '\0' && *p != '*')
111 return ABORT;
112 switch (*p) {
113 case '\\':
114 /* Literal match with following character. */
115 p++;
116 /* FALLTHROUGH */
117 default:
118 if (*text != *p)
119 return FALSE;
120 continue;
121 case '?':
122 /* Match anything. */
123 continue;
124 case '*':
125 while (*++p == '*')
126 /* Consecutive stars act just like one. */
127 continue;
128 if (*p == '\0')
129 /* Trailing star matches everything. */
130 return TRUE;
131 while (*text)
132 if ((matched = DoMatch(text++, p)) != FALSE)
133 return matched;
134 return ABORT;
135 case '[':
136 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
137 if (reverse)
138 /* Inverted character class. */
139 p++;
140 matched = FALSE;
141 if (p[1] == ']' || p[1] == '-')
142 if (*++p == *text)
143 matched = TRUE;
144 for (last = *p; *++p && *p != ']'; last = *p)
145 /* This next line requires a good C compiler. */
146 if (*p == '-' && p[1] != ']'
147 ? *text <= *++p && *text >= last : *text == *p)
148 matched = TRUE;
149 if (matched == reverse)
150 return FALSE;
151 continue;
152 }
153 }
154
155#ifdef MATCH_TAR_PATTERN
156 if (*text == '/')
157 return TRUE;
158#endif /* MATCH_TAR_ATTERN */
159 return *text == '\0';
160}
161
162
163/*
164** User-level routine. Returns TRUE or FALSE.
165*/
166int wildmat(const char *text, const char *p)
167{
168#ifdef OPTIMIZE_JUST_STAR
169 if (p[0] == '*' && p[1] == '\0')
170 return TRUE;
171#endif /* OPTIMIZE_JUST_STAR */
172 return DoMatch(text, p) == TRUE;
173}
#define NEGATE_CLASS
Definition: wildmat.c:93
int wildmat(const char *text, const char *p)
Definition: wildmat.c:166
#define ABORT
Definition: wildmat.c:89
static int DoMatch(const char *text, const char *p)
Definition: wildmat.c:103
#define TRUE
Definition: wildmat.c:87
#define FALSE
Definition: wildmat.c:88