~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/glob.c

Version: ~ [ linux-6.11.5 ] ~ [ linux-6.10.14 ] ~ [ linux-6.9.12 ] ~ [ linux-6.8.12 ] ~ [ linux-6.7.12 ] ~ [ linux-6.6.58 ] ~ [ linux-6.5.13 ] ~ [ linux-6.4.16 ] ~ [ linux-6.3.13 ] ~ [ linux-6.2.16 ] ~ [ linux-6.1.114 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.169 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.228 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.284 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.322 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.336 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.4.302 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

Diff markup

Differences between /lib/glob.c (Version linux-6.11.5) and /lib/glob.c (Version linux-5.17.15)


  1 #include <linux/module.h>                           1 #include <linux/module.h>
  2 #include <linux/glob.h>                             2 #include <linux/glob.h>
  3                                                     3 
  4 /*                                                  4 /*
  5  * The only reason this code can be compiled a      5  * The only reason this code can be compiled as a module is because the
  6  * ATA code that depends on it can be as well.      6  * ATA code that depends on it can be as well.  In practice, they're
  7  * both usually compiled in and the module ove      7  * both usually compiled in and the module overhead goes away.
  8  */                                                 8  */
  9 MODULE_DESCRIPTION("glob(7) matching");             9 MODULE_DESCRIPTION("glob(7) matching");
 10 MODULE_LICENSE("Dual MIT/GPL");                    10 MODULE_LICENSE("Dual MIT/GPL");
 11                                                    11 
 12 /**                                                12 /**
 13  * glob_match - Shell-style pattern matching,      13  * glob_match - Shell-style pattern matching, like !fnmatch(pat, str, 0)
 14  * @pat: Shell-style pattern to match, e.g. "*     14  * @pat: Shell-style pattern to match, e.g. "*.[ch]".
 15  * @str: String to match.  The pattern must ma     15  * @str: String to match.  The pattern must match the entire string.
 16  *                                                 16  *
 17  * Perform shell-style glob matching, returnin     17  * Perform shell-style glob matching, returning true (1) if the match
 18  * succeeds, or false (0) if it fails.  Equiva     18  * succeeds, or false (0) if it fails.  Equivalent to !fnmatch(@pat, @str, 0).
 19  *                                                 19  *
 20  * Pattern metacharacters are ?, *, [ and \.       20  * Pattern metacharacters are ?, *, [ and \.
 21  * (And, inside character classes, !, - and ].     21  * (And, inside character classes, !, - and ].)
 22  *                                                 22  *
 23  * This is small and simple implementation int     23  * This is small and simple implementation intended for device blacklists
 24  * where a string is matched against a number      24  * where a string is matched against a number of patterns.  Thus, it
 25  * does not preprocess the patterns.  It is no     25  * does not preprocess the patterns.  It is non-recursive, and run-time
 26  * is at most quadratic: strlen(@str)*strlen(@     26  * is at most quadratic: strlen(@str)*strlen(@pat).
 27  *                                                 27  *
 28  * An example of the worst case is glob_match(     28  * An example of the worst case is glob_match("*aaaaa", "aaaaaaaaaa");
 29  * it takes 6 passes over the pattern before m     29  * it takes 6 passes over the pattern before matching the string.
 30  *                                                 30  *
 31  * Like !fnmatch(@pat, @str, 0) and unlike the     31  * Like !fnmatch(@pat, @str, 0) and unlike the shell, this does NOT
 32  * treat / or leading . specially; it isn't ac     32  * treat / or leading . specially; it isn't actually used for pathnames.
 33  *                                                 33  *
 34  * Note that according to glob(7) (and unlike      34  * Note that according to glob(7) (and unlike bash), character classes
 35  * are complemented by a leading !; this does      35  * are complemented by a leading !; this does not support the regex-style
 36  * [^a-z] syntax.                                  36  * [^a-z] syntax.
 37  *                                                 37  *
 38  * An opening bracket without a matching close     38  * An opening bracket without a matching close is matched literally.
 39  */                                                39  */
 40 bool __pure glob_match(char const *pat, char c     40 bool __pure glob_match(char const *pat, char const *str)
 41 {                                                  41 {
 42         /*                                         42         /*
 43          * Backtrack to previous * on mismatch     43          * Backtrack to previous * on mismatch and retry starting one
 44          * character later in the string.  Bec     44          * character later in the string.  Because * matches all characters
 45          * (no exception for /), it can be eas     45          * (no exception for /), it can be easily proved that there's
 46          * never a need to backtrack multiple      46          * never a need to backtrack multiple levels.
 47          */                                        47          */
 48         char const *back_pat = NULL, *back_str !!  48         char const *back_pat = NULL, *back_str = back_str;
 49                                                    49 
 50         /*                                         50         /*
 51          * Loop over each token (character or      51          * Loop over each token (character or class) in pat, matching
 52          * it against the remaining unmatched      52          * it against the remaining unmatched tail of str.  Return false
 53          * on mismatch, or true after matching     53          * on mismatch, or true after matching the trailing nul bytes.
 54          */                                        54          */
 55         for (;;) {                                 55         for (;;) {
 56                 unsigned char c = *str++;          56                 unsigned char c = *str++;
 57                 unsigned char d = *pat++;          57                 unsigned char d = *pat++;
 58                                                    58 
 59                 switch (d) {                       59                 switch (d) {
 60                 case '?':       /* Wildcard: a     60                 case '?':       /* Wildcard: anything but nul */
 61                         if (c == '\0')             61                         if (c == '\0')
 62                                 return false;      62                                 return false;
 63                         break;                     63                         break;
 64                 case '*':       /* Any-length      64                 case '*':       /* Any-length wildcard */
 65                         if (*pat == '\0')          65                         if (*pat == '\0')       /* Optimize trailing * case */
 66                                 return true;       66                                 return true;
 67                         back_pat = pat;            67                         back_pat = pat;
 68                         back_str = --str;          68                         back_str = --str;       /* Allow zero-length match */
 69                         break;                     69                         break;
 70                 case '[': {     /* Character c     70                 case '[': {     /* Character class */
 71                         bool match = false, in     71                         bool match = false, inverted = (*pat == '!');
 72                         char const *class = pa     72                         char const *class = pat + inverted;
 73                         unsigned char a = *cla     73                         unsigned char a = *class++;
 74                                                    74 
 75                         /*                         75                         /*
 76                          * Iterate over each s     76                          * Iterate over each span in the character class.
 77                          * A span is either a      77                          * A span is either a single character a, or a
 78                          * range a-b.  The fir     78                          * range a-b.  The first span may begin with ']'.
 79                          */                        79                          */
 80                         do {                       80                         do {
 81                                 unsigned char      81                                 unsigned char b = a;
 82                                                    82 
 83                                 if (a == '\0')     83                                 if (a == '\0')  /* Malformed */
 84                                         goto l     84                                         goto literal;
 85                                                    85 
 86                                 if (class[0] =     86                                 if (class[0] == '-' && class[1] != ']') {
 87                                         b = cl     87                                         b = class[1];
 88                                                    88 
 89                                         if (b      89                                         if (b == '\0')
 90                                                    90                                                 goto literal;
 91                                                    91 
 92                                         class      92                                         class += 2;
 93                                         /* Any     93                                         /* Any special action if a > b? */
 94                                 }                  94                                 }
 95                                 match |= (a <=     95                                 match |= (a <= c && c <= b);
 96                         } while ((a = *class++     96                         } while ((a = *class++) != ']');
 97                                                    97 
 98                         if (match == inverted)     98                         if (match == inverted)
 99                                 goto backtrack     99                                 goto backtrack;
100                         pat = class;              100                         pat = class;
101                         }                         101                         }
102                         break;                    102                         break;
103                 case '\\':                        103                 case '\\':
104                         d = *pat++;               104                         d = *pat++;
105                         fallthrough;              105                         fallthrough;
106                 default:        /* Literal cha    106                 default:        /* Literal character */
107 literal:                                          107 literal:
108                         if (c == d) {             108                         if (c == d) {
109                                 if (d == '\0')    109                                 if (d == '\0')
110                                         return    110                                         return true;
111                                 break;            111                                 break;
112                         }                         112                         }
113 backtrack:                                        113 backtrack:
114                         if (c == '\0' || !back    114                         if (c == '\0' || !back_pat)
115                                 return false;     115                                 return false;   /* No point continuing */
116                         /* Try again from last    116                         /* Try again from last *, one character later in str. */
117                         pat = back_pat;           117                         pat = back_pat;
118                         str = ++back_str;         118                         str = ++back_str;
119                         break;                    119                         break;
120                 }                                 120                 }
121         }                                         121         }
122 }                                                 122 }
123 EXPORT_SYMBOL(glob_match);                        123 EXPORT_SYMBOL(glob_match);
124                                                   124 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

sflogo.php