From e85a0294955aee3dfa48d2a8c18646a16d7b8750 Mon Sep 17 00:00:00 2001 From: Philippe Proulx Date: Fri, 17 Feb 2017 04:04:35 -0500 Subject: [PATCH] Add string utilities The new string-utils.c file has a few utility functions to manipulate and check strings. See string-utils.c for more details. Signed-off-by: Philippe Proulx Signed-off-by: Mathieu Desnoyers --- liblttng-ust/Makefile.am | 4 +- liblttng-ust/string-utils.c | 338 ++++++++++++++++++++++++++++++++++++ liblttng-ust/string-utils.h | 33 ++++ 3 files changed, 374 insertions(+), 1 deletion(-) create mode 100644 liblttng-ust/string-utils.c create mode 100644 liblttng-ust/string-utils.h diff --git a/liblttng-ust/Makefile.am b/liblttng-ust/Makefile.am index 27acfec1..7edac266 100644 --- a/liblttng-ust/Makefile.am +++ b/liblttng-ust/Makefile.am @@ -56,7 +56,9 @@ liblttng_ust_runtime_la_SOURCES = \ lttng-ust-tracef-provider.h \ tracelog.c \ lttng-ust-tracelog-provider.h \ - getenv.h + getenv.h \ + string-utils.c \ + string-utils.h if HAVE_PERF_EVENT liblttng_ust_runtime_la_SOURCES += \ diff --git a/liblttng-ust/string-utils.c b/liblttng-ust/string-utils.c new file mode 100644 index 00000000..d597da3d --- /dev/null +++ b/liblttng-ust/string-utils.c @@ -0,0 +1,338 @@ +/* + * Copyright (C) 2017 - Philippe Proulx + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#define _LGPL_SOURCE +#include +#include +#include +#include + +#include "string-utils.h" + +enum star_glob_pattern_type_flags { + STAR_GLOB_PATTERN_TYPE_FLAG_NONE = 0, + STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN = 1, + STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY = 2, +}; + +static +enum star_glob_pattern_type_flags strutils_test_glob_pattern(const char *pattern) +{ + enum star_glob_pattern_type_flags ret = + STAR_GLOB_PATTERN_TYPE_FLAG_NONE; + const char *p; + + assert(pattern); + + for (p = pattern; *p != '\0'; p++) { + switch (*p) { + case '*': + ret = STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN; + + if (p[1] == '\0') { + ret |= STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY; + } + + goto end; + case '\\': + p++; + + if (*p == '\0') { + goto end; + } + break; + default: + break; + } + } + +end: + return ret; +} + +/* + * Returns true if `pattern` is a star-only globbing pattern, that is, + * it contains at least one non-escaped `*`. + */ +bool strutils_is_star_glob_pattern(const char *pattern) +{ + return strutils_test_glob_pattern(pattern) & + STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN; +} + +/* + * Returns true if `pattern` is a globbing pattern with a globbing, + * non-escaped star only at its very end. + */ +bool strutils_is_star_at_the_end_only_glob_pattern(const char *pattern) +{ + return strutils_test_glob_pattern(pattern) & + STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY; +} + +static inline +bool at_end_of_pattern(const char *p, const char *pattern, size_t pattern_len) +{ + return (p - pattern) == pattern_len || *p == '\0'; +} + +/* + * Globbing matching function with the star feature only (`?` and + * character sets are not supported). This matches `candidate` (plain + * string) against `pattern`. A literal star can be escaped with `\` in + * `pattern`. + * + * `pattern_len` or `candidate_len` can be greater than the actual + * string length of `pattern` or `candidate` if the string is + * null-terminated. + */ +bool strutils_star_glob_match(const char *pattern, size_t pattern_len, + const char *candidate, size_t candidate_len) { + const char *retry_c = candidate, *retry_p = pattern, *c, *p; + bool got_a_star = false; + +retry: + c = retry_c; + p = retry_p; + + /* + * The concept here is to retry a match in the specific case + * where we already got a star. The retry position for the + * pattern is just after the most recent star, and the retry + * position for the candidate is the character following the + * last try's first character. + * + * Example: + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^^ + * pattern: hi*every*one + * ^^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^^ + * pattern: hi*every*one + * ^^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^^ + * pattern: hi*every*one + * ^^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ MISMATCH + * + * candidate: hi ev every onyx one + * ^ + * pattern: hi*every*one + * ^ + * + * candidate: hi ev every onyx one + * ^^ + * pattern: hi*every*one + * ^^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ + * + * candidate: hi ev every onyx one + * ^ ^ + * pattern: hi*every*one + * ^ ^ SUCCESS + */ + while ((c - candidate) < candidate_len && *c != '\0') { + assert(*c); + + if (at_end_of_pattern(p, pattern, pattern_len)) { + goto end_of_pattern; + } + + switch (*p) { + case '*': + got_a_star = true; + + /* + * Our first try starts at the current candidate + * character and after the star in the pattern. + */ + retry_c = c; + retry_p = p + 1; + + if (at_end_of_pattern(retry_p, pattern, pattern_len)) { + /* + * Star at the end of the pattern at + * this point: automatic match. + */ + return true; + } + + goto retry; + case '\\': + /* Go to escaped character. */ + p++; + + /* + * Fall through the default case which will + * compare the escaped character now. + */ + default: + if (at_end_of_pattern(p, pattern, pattern_len) || + *c != *p) { +end_of_pattern: + /* Character mismatch OR end of pattern. */ + if (!got_a_star) { + /* + * We didn't get any star yet, + * so this first mismatch + * automatically makes the whole + * test fail. + */ + return false; + } + + /* + * Next try: next candidate character, + * original pattern character (following + * the most recent star). + */ + retry_c++; + goto retry; + } + break; + } + + /* Next pattern and candidate characters. */ + c++; + p++; + } + + /* + * We checked every candidate character and we're still in a + * success state: the only pattern character allowed to remain + * is a star. + */ + if (at_end_of_pattern(p, pattern, pattern_len)) { + return true; + } + + p++; + return p[-1] == '*' && at_end_of_pattern(p, pattern, pattern_len); +} diff --git a/liblttng-ust/string-utils.h b/liblttng-ust/string-utils.h new file mode 100644 index 00000000..94e9a5c1 --- /dev/null +++ b/liblttng-ust/string-utils.h @@ -0,0 +1,33 @@ +#ifndef _STRING_UTILS_H +#define _STRING_UTILS_H + +/* + * Copyright (C) 2017 - Philippe Proulx + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include + +bool strutils_is_star_glob_pattern(const char *pattern); +bool strutils_is_star_at_the_end_only_glob_pattern(const char *pattern); +bool strutils_star_glob_match(const char *pattern, size_t pattern_len, + const char *candidate, size_t candidate_len); + +#endif /* _STRING_UTILS_H */ -- 2.34.1