dgaudet 97/08/06 13:21:31
Modified: htdocs/manual/mod core.html src CHANGES Makefile.tmpl http_config.c http_config.h http_core.c http_core.h http_request.c Added: src fnmatch.c fnmatch.h Log: directory_walk optimization reducing the core loop from O(N*M) to O(N+M). Plus minor semantic changes. Plus BSD fnmatch.[ch]. Revision Changes Path 1.70 +39 -5 apache/htdocs/manual/mod/core.html Index: core.html =================================================================== RCS file: /export/home/cvs/apache/htdocs/manual/mod/core.html,v retrieving revision 1.69 retrieving revision 1.70 diff -u -r1.69 -r1.70 --- core.html 1997/08/03 20:29:15 1.69 +++ core.html 1997/08/06 20:21:16 1.70 @@ -309,7 +309,11 @@ of that directory. Any directive which is allowed in a directory context may be used. <em>Directory</em> is either the full path to a directory, or a wild-card string. In a wild-card string, `?' matches any single character, -and `*' matches any sequences of characters. Example: +and `*' matches any sequences of characters. As of Apache 1.3, you +may also use `[]' character ranges like in the shell. Also as of Apache 1.3 +none of the wildcards match a `/' character, which more closely mimics the +behaviour of Unix shells. +Example: <pre> <Directory /usr/local/httpd/htdocs> Options Indexes FollowSymLinks @@ -324,11 +328,10 @@ <Directory ~ "^/www/.*/[0-9]{3}"> </pre> -would match directories in /www/ that consisted of three numbers. In -Apache 1.3 and later, it is reccomended to use -<a href="#directorymatch"><DirectoryMatch></a> instead.<p> +would match directories in /www/ that consisted of three numbers.</p> -<p>If multiple directory sections match the directory (or its parents) containing +<p>If multiple (non-regular expression) directory sections match the +directory (or its parents) containing a document, then the directives are applied in the order of shortest match first, interspersed with the directives from the <A HREF="#accessfilename">.htaccess</A> files. For example, with @@ -350,6 +353,33 @@ </menu> <P> +Regular expression directory sections are handled slightly differently +by Apache 1.2 and 1.3. In Apache 1.2 they are interspersed with the normal +directory sections and applied in the order they appear in the configuration +file. They are applied only once, and apply when the shortest match +possible occurs. In Apache 1.3 regular expressions are not considered +until after all of the normal sections have been applied. Then all of +the regular expressions are tested in the order they appeared in the +configuration file. For example, with +<blockquote><code> +<Directory ~ abc$><br> +... directives here ...<br> +</Directory><br> +</code></blockquote> +Suppose that the filename being accessed is +<code>/home/abc/public_html/abc/index.html</code>. The server +considers each of <code>/</code>, <code>/home</code>, <code>/home/abc</code>, +<code>/home/abc/public_html</code>, and <code>/home/abc/public_html/abc</code> +in that order. In Apache 1.2, when +<code>/home/abc</code> is considered, the regular expression will match +and be applied. In Apache 1.3 the regular expression isn't considered +at all at that point in the tree. It won't be considered until after +all normal <Directory>s and <code>.htaccess</code> files have +been applied. Then the regular expression will +match on <code>/home/abc/public_html/abc</code> and be applied. + +<P> + <STRONG> Note that the default Apache access for <Directory /> is <SAMP>Allow from All</SAMP>. This means that Apache will serve any file @@ -395,6 +425,10 @@ </pre> <p>would match directories in /www/ that consisted of three numbers.</p> + +<p><strong>See Also:</strong> +<a href="#directory"><Directory></a> for a description of how +regular expressions are mixed in with normal <Directory>s.</p> <hr> 1.387 +16 -0 apache/src/CHANGES Index: CHANGES =================================================================== RCS file: /export/home/cvs/apache/src/CHANGES,v retrieving revision 1.386 retrieving revision 1.387 diff -u -r1.386 -r1.387 --- CHANGES 1997/08/06 19:53:48 1.386 +++ CHANGES 1997/08/06 20:21:19 1.387 @@ -1,4 +1,20 @@ Changes with Apache 1.3a2 + + *) directory_walk optimization to reduce an O(N*M) loop to O(N+M) where + N is the number of <Directory> sections, and M is the number of + components in the filename of an object. + + To achieve this optimization the following config changes were made: + - Wildcards (* and ?, not the regex forms) in <Directory>s, + <Files>s, and <Location>s now treat a slash as a special + character. For example "/home/*/public_html" previously would + match "/home/a/andrew/public_html", now it only matches things + like "/home/bob/public_html". This mimics /bin/sh behaviour. + - It's possible now to use [] wildcarding in <Directory>, <Files> + or <Location>. + - Regex <Directory>s are applied after all non-regex <Directory>s. + + [Dean Gaudet] *) Fix a bug introduced in 1.3a1 directory_walk regarding .htaccess files and corrupted paths. [Dean Gaudet] 1.54 +13 -8 apache/src/Makefile.tmpl Index: Makefile.tmpl =================================================================== RCS file: /export/home/cvs/apache/src/Makefile.tmpl,v retrieving revision 1.53 retrieving revision 1.54 diff -u -r1.53 -r1.54 --- Makefile.tmpl 1997/07/31 20:56:24 1.53 +++ Makefile.tmpl 1997/08/06 20:21:19 1.54 @@ -11,7 +11,7 @@ OBJS= alloc.o http_main.o http_core.o http_config.o http_request.o \ http_log.o http_protocol.o rfc1413.o util.o util_script.o modules.o buff.o\ md5c.o util_md5.o explain.o http_bprintf.o util_date.o util_snprintf.o\ - $(MODULES) + fnmatch.o $(MODULES) .c.o: $(CC) -c $(INCLUDES) $(CFLAGS) $(SPACER) $< @@ -69,13 +69,15 @@ buff.o: buff.c httpd.h conf.h alloc.h buff.h http_main.h dummy.o: dummy.c explain.o: explain.c explain.h +fnmatch.o: fnmatch.c +gnu-fnmatch.o: gnu-fnmatch.c fnmatch.h http_bprintf.o: http_bprintf.c httpd.h conf.h alloc.h buff.h http_config.o: http_config.c httpd.h conf.h alloc.h buff.h \ http_config.h http_core.h http_log.h http_request.h \ http_conf_globals.h explain.h http_core.o: http_core.c httpd.h conf.h alloc.h buff.h http_config.h \ http_core.h http_protocol.h http_conf_globals.h http_main.h \ - http_log.h rfc1413.h util_md5.h md5.h scoreboard.h + http_log.h rfc1413.h util_md5.h md5.h scoreboard.h fnmatch.h http_log.o: http_log.c httpd.h conf.h alloc.h buff.h http_config.h \ http_core.h http_log.h http_main.o: http_main.c httpd.h conf.h alloc.h buff.h http_main.h \ @@ -86,8 +88,8 @@ util_date.h http_request.o: http_request.c httpd.h conf.h alloc.h buff.h \ http_config.h http_request.h http_core.h http_protocol.h http_log.h \ - http_main.h scoreboard.h -md5c.o: md5c.c md5.h + http_main.h scoreboard.h fnmatch.h +md5c.o: md5c.c conf.h md5.h mod_access.o: mod_access.c httpd.h conf.h alloc.h buff.h http_core.h \ http_config.h http_log.h http_request.h mod_actions.o: mod_actions.c httpd.h conf.h alloc.h buff.h \ @@ -99,7 +101,7 @@ mod_auth.o: mod_auth.c httpd.h conf.h alloc.h buff.h http_config.h \ http_core.h http_log.h http_protocol.h mod_auth_anon.o: mod_auth_anon.c httpd.h conf.h alloc.h buff.h \ - http_config.h http_core.h http_log.h http_protocol.h + http_config.h http_core.h http_log.h http_protocol.h http_request.h mod_auth_db.o: mod_auth_db.c httpd.h conf.h alloc.h buff.h \ http_config.h http_core.h http_log.h http_protocol.h mod_auth_dbm.o: mod_auth_dbm.c httpd.h conf.h alloc.h buff.h \ @@ -109,7 +111,7 @@ mod_autoindex.o: mod_autoindex.c httpd.h conf.h alloc.h buff.h \ http_config.h http_core.h http_request.h http_protocol.h http_log.h \ http_main.h util_script.h -mod_setenvif.o: mod_setenvif.c httpd.h conf.h http_core.h alloc.h buff.h \ +mod_browser.o: mod_browser.c httpd.h conf.h alloc.h buff.h \ http_config.h mod_cern_meta.o: mod_cern_meta.c httpd.h conf.h alloc.h buff.h \ http_config.h util_script.h http_log.h http_request.h @@ -143,13 +145,16 @@ http_config.h http_core.h mod_log_referer.o: mod_log_referer.c httpd.h conf.h alloc.h buff.h \ http_config.h -mod_mime.o: mod_mime.c httpd.h conf.h alloc.h buff.h http_config.h +mod_mime.o: mod_mime.c httpd.h conf.h alloc.h buff.h http_config.h \ + mod_mime.h mod_mime_magic.o: mod_mime_magic.c httpd.h conf.h alloc.h buff.h \ http_config.h http_request.h http_core.h http_log.h http_protocol.h mod_negotiation.o: mod_negotiation.c httpd.h conf.h alloc.h buff.h \ http_config.h http_request.h http_core.h http_log.h util_script.h mod_rewrite.o: mod_rewrite.c httpd.h conf.h alloc.h buff.h \ http_config.h http_request.h http_core.h http_log.h mod_rewrite.h +mod_setenvif.o: mod_setenvif.c httpd.h conf.h alloc.h buff.h \ + http_config.h http_core.h http_log.h mod_status.o: mod_status.c httpd.h conf.h alloc.h buff.h http_config.h \ http_core.h http_protocol.h http_main.h util_script.h scoreboard.h \ http_log.h @@ -161,7 +166,7 @@ rfc1413.o: rfc1413.c httpd.h conf.h alloc.h buff.h http_log.h \ rfc1413.h http_main.h util.o: util.c httpd.h conf.h alloc.h buff.h http_conf_globals.h -util_date.o: util_date.c util_date.h +util_date.o: util_date.c conf.h util_date.h util_md5.o: util_md5.c httpd.h conf.h alloc.h buff.h util_md5.h md5.h util_script.o: util_script.c httpd.h conf.h alloc.h buff.h \ http_config.h http_conf_globals.h http_main.h http_log.h \ 1.72 +5 -0 apache/src/http_config.c Index: http_config.c =================================================================== RCS file: /export/home/cvs/apache/src/http_config.c,v retrieving revision 1.71 retrieving revision 1.72 diff -u -r1.71 -r1.72 --- http_config.c 1997/08/06 19:53:50 1.71 +++ http_config.c 1997/08/06 20:21:21 1.72 @@ -1122,7 +1122,12 @@ if (virt->send_buffer_size == 0) virt->send_buffer_size = main_server->send_buffer_size; + + /* XXX: this is really something that should be dealt with by a + * post-config api phase */ + core_reorder_directories (p, virt); } + core_reorder_directories (p, main_server); } /***************************************************************** 1.43 +2 -0 apache/src/http_config.h Index: http_config.h =================================================================== RCS file: /export/home/cvs/apache/src/http_config.h,v retrieving revision 1.42 retrieving revision 1.43 diff -u -r1.42 -r1.43 --- http_config.h 1997/08/06 19:53:50 1.42 +++ http_config.h 1997/08/06 20:21:23 1.43 @@ -299,6 +299,8 @@ void *create_per_dir_config (pool *p); void *merge_per_dir_configs (pool *p, void *base, void *new); +void core_reorder_directories (pool *, server_rec *); + /* For http_core.c... (<Directory> command and virtual hosts) */ int parse_htaccess(void **result, request_rec *r, int override, 1.109 +77 -5 apache/src/http_core.c Index: http_core.c =================================================================== RCS file: /export/home/cvs/apache/src/http_core.c,v retrieving revision 1.108 retrieving revision 1.109 diff -u -r1.108 -r1.109 --- http_core.c 1997/08/05 08:19:46 1.108 +++ http_core.c 1997/08/06 20:21:24 1.109 @@ -62,6 +62,7 @@ #include "rfc1413.h" #include "util_md5.h" #include "scoreboard.h" +#include "fnmatch.h" /* Server core module... This module provides support for really basic * server operations, including options and commands which control the @@ -84,8 +85,8 @@ if (!dir || dir[strlen(dir) - 1] == '/') conf->d = dir; else if (strncmp(dir,"proxy:",6)==0) conf->d = pstrdup (a, dir); else conf->d = pstrcat (a, dir, "/", NULL); - conf->d_is_matchexp = conf->d ? (is_matchexp( conf->d ) != 0) : 0; - + conf->d_is_fnmatch = conf->d ? (is_fnmatch (conf->d) != 0) : 0; + conf->d_components = conf->d ? count_dirs (conf->d) : 0; conf->opts = dir ? OPT_UNSET : OPT_ALL; conf->opts_add = conf->opts_remove = OPT_NONE; @@ -129,7 +130,8 @@ } conf->d = new->d; - conf->d_is_matchexp = new->d_is_matchexp; + conf->d_is_fnmatch = new->d_is_fnmatch; + conf->d_components = new->d_components; conf->r = new->r; if (new->opts != OPT_UNSET) conf->opts = new->opts; @@ -235,6 +237,76 @@ *new_space = url_config; } +/* This routine reorders the directory sections such that the 1-component + * sections come first, then the 2-component, and so on, finally followed by + * the "special" sections. A section is "special" if it's a regex, or if it + * doesn't start with / -- consider proxy: matching. All movements are + * in-order to preserve the ordering of the sections from the config files. + * See directory_walk(). + */ +void core_reorder_directories (pool *p, server_rec *s) +{ + core_server_config *sconf; + array_header *old_sec; + array_header *new_sec; + int nelts; + unsigned n_components; + unsigned next_n_components; + core_dir_config *entry_core; + int still_more_to_go; + int i; + void **elts; + + sconf = get_module_config (s->module_config, &core_module); + old_sec = sconf->sec; + nelts = old_sec->nelts; + elts = (void **)old_sec->elts; + new_sec = make_array (p, nelts, sizeof(void *)); + + /* First collect all the 1 component names, then the 2 componennt names, + * and so on. We use next_n_components to know what to look for the + * next time around... to deal with weird configs with many many many + * in at least one <Directory>. + */ + n_components = 1; + do { + /* guess there's none left other than ones with exactly n_components */ + still_more_to_go = 0; + /* guess that what's left has infinite components */ + next_n_components = ~0u; + for (i = 0; i < nelts; ++i) { + if (elts[i] == NULL) continue; + entry_core = (core_dir_config *)get_module_config (elts[i], + &core_module); + if (entry_core->r) continue; + if (entry_core->d[0] != '/') continue; + if (entry_core->d_components != n_components) { + /* oops, the guess was wrong */ + still_more_to_go = 1; + if (entry_core->d_components < next_n_components) { + next_n_components = entry_core->d_components; + } + continue; + } + *(void **)push_array (new_sec) = elts[i]; + elts[i] = NULL; + } + n_components = next_n_components; + } while (still_more_to_go); + + /* anything left is a "special" case */ + for (i = 0; i < nelts; ++i) { + if (elts[i] == NULL) continue; + *(void **)push_array (new_sec) = elts[i]; + } + + /* XXX: in theory we could have allocated new_sec from the ptemp + * pool, and then memcpy'd it over top of old_sec ... oh well, + * we're wasting some ram here. + */ + sconf->sec = new_sec; +} + /***************************************************************** * * There are some elements of the core config structures in which @@ -731,7 +803,7 @@ conf = (core_dir_config *)get_module_config(new_url_conf, &core_module); conf->d = pstrdup(cmd->pool, cmd->path); /* No mangling, please */ - conf->d_is_matchexp = is_matchexp( conf->d ) != 0; + conf->d_is_fnmatch = is_fnmatch( conf->d ) != 0; conf->r = r; add_per_url_conf (cmd->server, new_url_conf); @@ -787,7 +859,7 @@ conf = (core_dir_config *)get_module_config(new_file_conf, &core_module); conf->d = pstrdup(cmd->pool, cmd->path); - conf->d_is_matchexp = is_matchexp( conf->d ) != 0; + conf->d_is_fnmatch = is_fnmatch( conf->d ) != 0; conf->r = r; add_file_conf (c, new_file_conf); 1.26 +5 -3 apache/src/http_core.h Index: http_core.h =================================================================== RCS file: /export/home/cvs/apache/src/http_core.h,v retrieving revision 1.25 retrieving revision 1.26 diff -u -r1.25 -r1.26 --- http_core.h 1997/07/30 18:41:51 1.25 +++ http_core.h 1997/08/06 20:21:25 1.26 @@ -129,8 +129,10 @@ typedef unsigned char overrides_t; typedef struct { - /* path of the directory/regex/etc. see also d_is_matchexp below */ + /* path of the directory/regex/etc. see also d_is_fnmatch below */ char *d; + /* the number of slashes in d */ + unsigned d_components; allow_options_t opts; allow_options_t opts_add; @@ -170,11 +172,11 @@ int content_md5 : 2; /* calculate Content-MD5? */ - /* since is_matchexp(conf->d) was being called so frequently in + /* since is_fnmatch(conf->d) was being called so frequently in * directory_walk() and its relatives, this field was created and * is set to the result of that call. */ - int d_is_matchexp : 1; + int d_is_fnmatch : 1; /* System Resource Control */ #ifdef RLIMIT_CPU 1.70 +45 -28 apache/src/http_request.c Index: http_request.c =================================================================== RCS file: /export/home/cvs/apache/src/http_request.c,v retrieving revision 1.69 retrieving revision 1.70 diff -u -r1.69 -r1.70 --- http_request.c 1997/08/06 19:53:51 1.69 +++ http_request.c 1997/08/06 20:21:25 1.70 @@ -69,6 +69,7 @@ #include "http_log.h" #include "http_main.h" #include "scoreboard.h" +#include "fnmatch.h" /***************************************************************** * @@ -253,7 +254,7 @@ char *test_filename = pstrdup (r->pool, r->filename); char *test_dirname; int num_dirs, res; - int i, test_filename_len; + int i, j, test_filename_len; /* Are we dealing with a file? If not, we can (hopefuly) safely assume * we have a handler that doesn't require one, but for safety's sake, @@ -284,7 +285,7 @@ if (test_filename[0] != '/') #endif { -/* fake filenames only match Directory sections */ +/* fake filenames (i.e. proxy:) only match Directory sections */ void *this_conf, *entry_config; core_dir_config *entry_core; char *entry_dir; @@ -304,8 +305,8 @@ if (!regexec(entry_core->r, test_filename, 0, NULL, 0)) this_conf = entry_config; } - else if (entry_core->d_is_matchexp) { - if (!strcmp_match(test_filename, entry_dir)) + else if (entry_core->d_is_fnmatch) { + if (!fnmatch (entry_dir, test_filename, FNM_PATHNAME)) this_conf = entry_config; } else if (!strncmp (test_filename, entry_dir, strlen(entry_dir))) @@ -344,11 +345,12 @@ * function so we try to avoid allocating lots of extra memory here. */ test_dirname = palloc (r->pool, test_filename_len+1); + /* j keeps track of which section we're on, see core_reorder_directories */ + j = 0; for (i = 1; i <= num_dirs; ++i) { core_dir_config *core_dir = (core_dir_config *)get_module_config(per_dir_defaults, &core_module); int overrides_here; - int j; /* XXX: this could be made faster by only copying the next component * rather than copying the entire thing all over. @@ -363,40 +365,32 @@ log_reason("Symbolic link not allowed", test_dirname, r); return res; } - + /* Begin *this* level by looking for matching <Directory> sections from * access.conf. */ - - for (j = 0; j < num_sec; ++j) { + + for (; j < num_sec; ++j) { void *entry_config = sec[j]; core_dir_config *entry_core; char *entry_dir; void *this_conf; - if (!entry_config) continue; - entry_core = (core_dir_config *)get_module_config(entry_config, &core_module); entry_dir = entry_core->d; - + + if (entry_core->r + || entry_dir[0] != '/' + || entry_core->d_components > i) break; + this_conf = NULL; - if (entry_core->r) { - if (!regexec(entry_core->r, test_dirname, 0, NULL, - (j == num_sec) ? 0 : REG_NOTEOL)) { - /* Don't try this wildcard again --- if it ends in '*' - * it'll match again, and subdirectories won't be able to - * override it... - */ - sec[j] = NULL; + if (entry_core->d_is_fnmatch) { + if (!fnmatch(entry_dir, test_dirname, FNM_PATHNAME)) { + sec[j] = NULL; this_conf = entry_config; } } - else if (entry_core->d_is_matchexp && - !strcmp_match(test_dirname, entry_dir)) { - sec[j] = NULL; - this_conf = entry_config; - } else if (!strcmp (test_dirname, entry_dir)) this_conf = entry_config; @@ -420,11 +414,32 @@ res = parse_htaccess (&htaccess_conf, r, overrides_here, test_dirname, sconf->access_name); if (res) return res; + if (htaccess_conf) per_dir_defaults = merge_per_dir_configs (r->pool, per_dir_defaults, htaccess_conf); } + + } + + /* now match the "special" sections (regex, and "proxy:" stuff). But + * note that proxy: stuff doesn't get down this far, it's been handled + * earlier, so we'll just skip it. + */ + for ( ; j < num_sec; ++j) { + void *entry_config = sec[j]; + core_dir_config *entry_core; + + entry_core = + (core_dir_config *)get_module_config(entry_config, &core_module); + if (entry_core->r) { + if (!regexec(entry_core->r, test_dirname, 0, NULL, REG_NOTEOL)) { + per_dir_defaults = + merge_per_dir_configs (r->pool, per_dir_defaults, + entry_config); + } + } } r->per_dir_config = per_dir_defaults; @@ -494,9 +509,10 @@ if (!regexec(entry_core->r, test_location, 0, NULL, 0)) this_conf = entry_config; } - else if( entry_core->d_is_matchexp ) { - if (!strcmp_match(test_location, entry_url)) + else if( entry_core->d_is_fnmatch ) { + if (!fnmatch (entry_url, test_location, FNM_PATHNAME)) { this_conf = entry_config; + } } else if (!strncmp (test_location, entry_url, len) && (entry_url[len - 1] == '/' || @@ -556,9 +572,10 @@ if (!regexec(entry_core->r, test_file, 0, NULL, 0)) this_conf = entry_config; } - else if ( entry_core->d_is_matchexp ) { - if (!strcmp_match(test_file, entry_file)) + else if ( entry_core->d_is_fnmatch ) { + if (!fnmatch(entry_file, test_file, FNM_PATHNAME)) { this_conf = entry_config; + } } else if (!strncmp (test_file, entry_file, len) && (entry_file[len - 1] == '/' || 1.1 apache/src/fnmatch.c Index: fnmatch.c =================================================================== /* * Copyright (c) 1989, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Guido van Rossum. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the University of * California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)fnmatch.c 8.2 (Berkeley) 4/16/94"; #endif /* LIBC_SCCS and not lint */ /* * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6. * Compares a filename or pathname to a pattern. */ #include <fnmatch.h> #include <string.h> #define EOS '\0' static const char *rangematch __P((const char *, int, int)); int fnmatch(pattern, string, flags) const char *pattern, *string; int flags; { const char *stringstart; char c, test; for (stringstart = string;;) switch (c = *pattern++) { case EOS: return (*string == EOS ? 0 : FNM_NOMATCH); case '?': if (*string == EOS) return (FNM_NOMATCH); if (*string == '/' && (flags & FNM_PATHNAME)) return (FNM_NOMATCH); if (*string == '.' && (flags & FNM_PERIOD) && (string == stringstart || ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) return (FNM_NOMATCH); ++string; break; case '*': c = *pattern; /* Collapse multiple stars. */ while (c == '*') c = *++pattern; if (*string == '.' && (flags & FNM_PERIOD) && (string == stringstart || ((flags & FNM_PATHNAME) && *(string - 1) == '/'))) return (FNM_NOMATCH); /* Optimize for pattern with * at end or before /. */ if (c == EOS) if (flags & FNM_PATHNAME) return (strchr(string, '/') == NULL ? 0 : FNM_NOMATCH); else return (0); else if (c == '/' && flags & FNM_PATHNAME) { if ((string = strchr(string, '/')) == NULL) return (FNM_NOMATCH); break; } /* General case, use recursion. */ while ((test = *string) != EOS) { if (!fnmatch(pattern, string, flags & ~FNM_PERIOD)) return (0); if (test == '/' && flags & FNM_PATHNAME) break; ++string; } return (FNM_NOMATCH); case '[': if (*string == EOS) return (FNM_NOMATCH); if (*string == '/' && flags & FNM_PATHNAME) return (FNM_NOMATCH); if ((pattern = rangematch(pattern, *string, flags)) == NULL) return (FNM_NOMATCH); ++string; break; case '\\': if (!(flags & FNM_NOESCAPE)) { if ((c = *pattern++) == EOS) { c = '\\'; --pattern; } } /* FALLTHROUGH */ default: if (c != *string++) return (FNM_NOMATCH); break; } /* NOTREACHED */ } static const char * rangematch(pattern, test, flags) const char *pattern; int test, flags; { int negate, ok; char c, c2; /* * A bracket expression starting with an unquoted circumflex * character produces unspecified results (IEEE 1003.2-1992, * 3.13.2). This implementation treats it like '!', for * consistency with the regular expression syntax. * J.T. Conklin ([EMAIL PROTECTED]) */ if ((negate = (*pattern == '!' || *pattern == '^'))) ++pattern; for (ok = 0; (c = *pattern++) != ']';) { if (c == '\\' && !(flags & FNM_NOESCAPE)) c = *pattern++; if (c == EOS) return (NULL); if (*pattern == '-' && (c2 = *(pattern+1)) != EOS && c2 != ']') { pattern += 2; if (c2 == '\\' && !(flags & FNM_NOESCAPE)) c2 = *pattern++; if (c2 == EOS) return (NULL); if (c <= test && test <= c2) ok = 1; } else if (c == test) ok = 1; } return (ok == negate ? NULL : pattern); } /* This function is an Apache addition */ /* return non-zero if pattern has any glob chars in it */ int is_fnmatch (const char *pattern) { int nesting; nesting = 0; while (*pattern) { switch (*pattern) { case '?': case '*': return 1; case '\\': if (*pattern++ == '\0') { return 0; } break; case '[': /* '[' is only a glob if it has a matching ']' */ ++nesting; break; case ']': if (nesting) return 1; break; } ++pattern; } return 0; } 1.1 apache/src/fnmatch.h Index: fnmatch.h =================================================================== /*- * Copyright (c) 1992, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the University of * California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * @(#)fnmatch.h 8.1 (Berkeley) 6/2/93 */ /* This file has been modified by the Apache Group. */ #ifndef _FNMATCH_H_ #define _FNMATCH_H_ #define FNM_NOMATCH 1 /* Match failed. */ #define FNM_NOESCAPE 0x01 /* Disable backslash escaping. */ #define FNM_PATHNAME 0x02 /* Slash must be matched by slash. */ #define FNM_PERIOD 0x04 /* Period must be matched by period. */ int fnmatch (const char *, const char *, int); /* this function is an Apache addition */ extern int is_fnmatch (const char *); #endif /* !_FNMATCH_H_ */