diff options
Diffstat (limited to 'globmatch.c')
| -rw-r--r-- | globmatch.c | 187 |
1 files changed, 187 insertions, 0 deletions
diff --git a/globmatch.c b/globmatch.c new file mode 100644 index 0000000..75f52d9 --- /dev/null +++ b/globmatch.c @@ -0,0 +1,187 @@ +/* This file is part of "reprepro" + * Copyright (C) 2009 Bernhard R. Link + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301 USA + */ +#include <config.h> + +#include <assert.h> +#include <limits.h> +#include <stdint.h> +#include <string.h> +#ifdef TEST_GLOBMATCH +#include <stdio.h> +#include <stdlib.h> +#endif +#include "error.h" +#include "globmatch.h" + +#ifdef NOPARANOIA +#define Assert(a) /* */ +#else +#define Assert(a) assert(a) +#endif + +/* check if a string matches a pattern, the pattern may + contain * and ?. + + This algorithm should be in O( strlen(pattern) * strlen(string) ) +*/ + +bool globmatch(const char *string, const char *pattern) { + int i, l = strlen(pattern); + int smallest_possible = 0, largest_possible = 0; + bool possible[ l + 1 ]; + const char *p; + + if (strlen(pattern) > (size_t)INT_MAX) + return false; + + memset(possible, 0, sizeof(possible)); + /* the first character must match the first pattern character + or the first one after the first star */ + possible[smallest_possible] = true; + while (pattern[largest_possible] == '*') + largest_possible++; + Assert (largest_possible <= l); + possible[largest_possible] = true; + + for (p = string ; *p != '\0' ; p++) { + Assert (largest_possible >= smallest_possible); + for (i = largest_possible ; i >= smallest_possible ; i--) { + if (!possible[i]) + continue; + /* no character matches the end of the pattern: */ + if (pattern[i] == '\0') { + Assert (i == l); + possible[i] = false; + do { + if (largest_possible <= + smallest_possible) + return false; + largest_possible--; + } while (!possible[largest_possible]); + i = largest_possible + 1; + continue; + } + Assert (i < l); + if (pattern[i] == '*') { + int j = i + 1; + + while (pattern[j] == '*') + j++; + /* all the '*' match one character: */ + Assert (j <= l); + possible[j] = true; + if (j > largest_possible) + largest_possible = j; + /* or more than one */ + continue; + } + if (pattern[i] == '[') { + int j = i+1; + bool matches = false, negate = false; + + if (pattern[j] == '!' || pattern[j] == '^') { + j++; + negate = true; + } + if (pattern[j] == '\0') + return false; + do { + if (pattern[j+1] == '-' && + pattern[j+2] != ']' && + pattern[j+2] != '\0') { + if (*p >= pattern[j] && + *p <= pattern[j+2]) + matches = true; + j += 3; + } else { + if (*p == pattern[j]) + matches = true; + j++; + } + if (pattern[j] == '\0') { + /* stray [ matches nothing */ + return false; + } + } while (pattern[j] != ']'); + j++; + Assert (j <= l); + if (negate) + matches = !matches; + if (matches) { + possible[j] = true; + /* if the next character is a star, + that might also match 0 characters */ + while (pattern[j] == '*') + j++; + Assert (j <= l); + possible[j] = true; + if (j > largest_possible) + largest_possible = j; + } + } else if (pattern[i] == '?' || pattern[i] == *p) { + int j = i + 1; + possible[j] = true; + /* if the next character is a star, + that might also match 0 characters */ + while (pattern[j] == '*') + j++; + Assert (j <= l); + possible[j] = true; + if (j > largest_possible) + largest_possible = j; + } + possible[i] = false; + if (i == smallest_possible) { + smallest_possible++; + while (!possible[smallest_possible]) { + if (smallest_possible >= + largest_possible) + return false; + smallest_possible++; + } + Assert (smallest_possible <= l); + } + if (i == largest_possible) { + do { + if (largest_possible <= + smallest_possible) + return false; + largest_possible--; + } while (!possible[largest_possible]); + Assert (largest_possible >= 0); + } + } + } + /* end of string matches end of pattern, + if largest got < smallest, then this is also false */ + return possible[l]; +} + +#ifdef TEST_GLOBMATCH +int main(int argc, const char *argv[]) { + if (argc != 3) { + fputs("Wrong number of arguments!\n", stderr); + exit(EXIT_FAILURE); + } + if (globmatch(argv[2], argv[1])) { + puts("true"); + return 0; + } else { + puts("false"); + return 0; + } +} +#endif |