From 231b5333103e13e81c22caa5dc9410ac688c538d Mon Sep 17 00:00:00 2001 From: Philippe Proulx Date: Sat, 18 Feb 2017 20:00:33 -0500 Subject: [PATCH] Add string utilities The new lttng-string-utils.c file has a few utility functions to manipulate and check strings. See lttng-string-utils.c for more details. Signed-off-by: Philippe Proulx Signed-off-by: Mathieu Desnoyers --- Makefile | 2 +- lttng-string-utils.c | 368 +++++++++++++++++++++++++++++++++++++++++++ lttng-string-utils.h | 36 +++++ 3 files changed, 405 insertions(+), 1 deletion(-) create mode 100644 lttng-string-utils.c create mode 100644 lttng-string-utils.h diff --git a/Makefile b/Makefile index f377874a..f65e4632 100644 --- a/Makefile +++ b/Makefile @@ -43,7 +43,7 @@ ifneq ($(KERNELRELEASE),) obj-$(CONFIG_LTTNG) += lttng-tracer.o - lttng-tracer-objs := lttng-events.o lttng-abi.o \ + lttng-tracer-objs := lttng-events.o lttng-abi.o lttng-string-utils.o \ lttng-probes.o lttng-context.o \ lttng-context-pid.o lttng-context-procname.o \ lttng-context-prio.o lttng-context-nice.o \ diff --git a/lttng-string-utils.c b/lttng-string-utils.c new file mode 100644 index 00000000..94de1cf8 --- /dev/null +++ b/lttng-string-utils.c @@ -0,0 +1,368 @@ +/* + * Copyright (C) 2017 Philippe Proulx + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; only + * version 2.1 of the License. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include + +#include + +enum star_glob_pattern_type_flags { + STAR_GLOB_PATTERN_TYPE_FLAG_NONE = 0, + STAR_GLOB_PATTERN_TYPE_FLAG_PATTERN = (1U << 0), + STAR_GLOB_PATTERN_TYPE_FLAG_END_ONLY = (1U << 1), +}; + +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; + + 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; +} + +struct string_with_len { + const char *str; + size_t len; +}; + +static +char string_get_char_at_cb(size_t at, void *data) +{ + struct string_with_len *string_with_len = data; + + if (at >= string_with_len->len) { + return '\0'; + } + + return string_with_len->str[at]; +} + +/* + * 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) { + struct string_with_len pattern_with_len = { + pattern, pattern_len + }; + struct string_with_len candidate_with_len = { + candidate, candidate_len + }; + + return strutils_star_glob_match_char_cb(string_get_char_at_cb, + &pattern_with_len, string_get_char_at_cb, + &candidate_with_len); +} + +bool strutils_star_glob_match_char_cb( + strutils_get_char_at_cb pattern_get_char_at_cb, + void *pattern_get_char_at_cb_data, + strutils_get_char_at_cb candidate_get_char_at_cb, + void *candidate_get_char_at_cb_data) +{ + size_t retry_p_at = 0, retry_c_at = 0, c_at, p_at; + char c, p, prev_p; + bool got_a_star = false; + +retry: + c_at = retry_c_at; + c = candidate_get_char_at_cb(c_at, candidate_get_char_at_cb_data); + p_at = retry_p_at; + p = pattern_get_char_at_cb(p_at, pattern_get_char_at_cb_data); + + /* + * 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 != '\0') { + if (p == '\0') { + goto end_of_pattern; + } + + switch (p) { + case '*': + { + char retry_p; + got_a_star = true; + + /* + * Our first try starts at the current candidate + * character and after the star in the pattern. + */ + retry_c_at = c_at; + retry_p_at = p_at + 1; + retry_p = pattern_get_char_at_cb(retry_p_at, + pattern_get_char_at_cb_data); + + if (retry_p == '\0') { + /* + * Star at the end of the pattern at + * this point: automatic match. + */ + return true; + } + + goto retry; + } + case '\\': + /* Go to escaped character. */ + p_at++; + p = pattern_get_char_at_cb(p_at, + pattern_get_char_at_cb_data); + + /* + * Fall through the default case which will + * compare the escaped character now. + */ + default: + if (p == '\0' || 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_at++; + goto retry; + } + break; + } + + /* Next pattern and candidate characters. */ + c_at++; + c = candidate_get_char_at_cb(c_at, + candidate_get_char_at_cb_data); + p_at++; + p = pattern_get_char_at_cb(p_at, pattern_get_char_at_cb_data); + } + + /* + * We checked every candidate character and we're still in a + * success state: the only pattern character allowed to remain + * is a star. + */ + if (p == '\0') { + return true; + } + + prev_p = p; + p_at++; + p = pattern_get_char_at_cb(p_at, pattern_get_char_at_cb_data); + return prev_p == '*' && p == '\0'; +} diff --git a/lttng-string-utils.h b/lttng-string-utils.h new file mode 100644 index 00000000..1a193761 --- /dev/null +++ b/lttng-string-utils.h @@ -0,0 +1,36 @@ +#ifndef _LTTNG_STRING_UTILS_H +#define _LTTNG_STRING_UTILS_H + +/* + * Copyright (C) 2017 Philippe Proulx + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; only + * version 2.1 of the License. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include + +typedef char (*strutils_get_char_at_cb)(size_t, void *); + +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); +bool strutils_star_glob_match_char_cb( + strutils_get_char_at_cb pattern_get_char_at_cb, + void *pattern_get_char_at_cb_data, + strutils_get_char_at_cb candidate_get_char_at_cb, + void *candidate_get_char_at_cb_data); + +#endif /* _LTTNG_STRING_UTILS_H */ -- 2.34.1