"Fossies" - the Fresh Open Source Software Archive

Member "citadel/modules/nntp/wildmat.c" (5 Jun 2021, 5918 Bytes) of package /linux/www/citadel.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "wildmat.c" see the Fossies "Dox" file reference documentation.

    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 */
  103 static 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 */
  166 int 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 }