Add strglobmatch() for generic wildcard string matching.
This code is originally from perf-tools. For porting in
the kernel, the limitation of the number of wildcards is
introduced, because of the limitation of the stack.
Signed-off-by: Masami Hiramatsu <masami.hiramatsu...@hitachi.com>
Cc: Andrew Morton <a...@linux-foundation.org>
Cc: Akinobu Mita <akinobu.m...@gmail.com>
Cc: "Paul E. McKenney" <paul...@linux.vnet.ibm.com>
Cc: David Howells <dhowe...@redhat.com>
---
include/linux/string.h | 8 ++++
lib/string.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 99 insertions(+)
diff --git a/include/linux/string.h b/include/linux/string.h
index ac889c5..fcb1506 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -122,6 +122,14 @@ extern void argv_free(char **argv);
extern bool sysfs_streq(const char *s1, const char *s2);
extern int strtobool(const char *s, bool *res);
+/*
+ * Maximum number of wildcards in a glob pattern
+ * This limits the number of wildcards in a glob pattern, because
+ * more wildcards consume more kernel stack.
+ */
+#define MAX_GLOB_WILDCARDS 10
+extern bool strglobmatch(const char *glob, const char *str);
+
#ifdef CONFIG_BINARY_PRINTF
int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args);
int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf);
diff --git a/lib/string.c b/lib/string.c
index e5878de..640fb10 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -824,3 +824,94 @@ void *memchr_inv(const void *start, int c, size_t bytes)
return check_bytes8(start, value, bytes % 8);
}
EXPORT_SYMBOL(memchr_inv);
+
+/* Character class matching */
+static bool __match_charclass(const char *pat, char c, const char **npat)
+{
+ bool complement = false, ret = true;
+
+ if (*pat == '!') {
+ complement = true;
+ pat++;
+ }
+ if (*pat++ == c) /* First character is special */
+ goto end;
+
+ while (*pat && *pat != ']') { /* Matching */
+ if (*pat == '-' && *(pat + 1) != ']') { /* Range */
+ if (*(pat - 1) <= c && c <= *(pat + 1))
+ goto end;
+ if (*(pat - 1) > *(pat + 1))
+ goto error;
+ pat += 2;
+ } else if (*pat++ == c)
+ goto end;
+ }
+ if (!*pat)
+ goto error;
+ ret = false;
+
+end:
+ while (*pat && *pat != ']') /* Searching closing */
+ pat++;
+ if (!*pat)
+ goto error;
+ *npat = pat + 1;
+ return complement ? !ret : ret;
+
+error:
+ return false;
+}
+
+/* Glob pattern(wildcard and char-class) matching */
+static bool __match_glob(const char *pat, const char *str, int nest)
+{
+ if (nest > MAX_GLOB_WILDCARDS)
+ return false;
+
+ while (*str && *pat && *pat != '*') {
+ if (*pat == '?') { /* Matches any single character */
+ str++;
+ pat++;
+ continue;
+ } else if (*pat == '[') /* Character classes/Ranges */
+ if (__match_charclass(pat + 1, *str, &pat)) {
+ str++;
+ continue;
+ } else
+ return false;
+ else if (*pat == '\\') /* Escaped char match as normal char */
+ pat++;
+ if (*str++ != *pat++)
+ return false;
+ }
+ /* Check wild card */
+ if (*pat == '*') {
+ while (*pat == '*')
+ pat++;
+ if (!*pat) /* Tail wild card matches all */
+ return true;
+ while (*str)
+ if (__match_glob(pat, str++, nest + 1))
+ return true;
+ }
+ return !*str && !*pat;
+}
+
+/**
+ * strglobmatch - glob expression pattern matching
+ * @pat: the pattern string to match
+ * @str: the target string to match
+ *
+ * This returns true if the @str matches @pat. @pat can includes wildcards
+ * ('*','?') and character classes ([CHARS], complementation and ranges are
+ * also supported). Also, this supports escape character ('\') to use special
+ * characters as normal character.
+ *
+ * Note: if @pat syntax is broken, this always returns false.
+ */
+bool strglobmatch(const char *pat, const char *str)
+{
+ return __match_glob(pat, str, 0);
+}
+EXPORT_SYMBOL(strglobmatch);
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
