Adding upstream version 5.4.4.upstream/5.4.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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