From 701e127f7d892909a58c6f3333e23588ccef9e22 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Sat, 4 Sep 2010 21:21:07 +0200 Subject: [PATCH] hush: optimize #[#] and %[%] for speed. size -2 bytes. Signed-off-by: Denys Vlasenko --- shell/hush.c | 22 +++++------ shell/match.c | 106 +++++++++++++++++++++++++++++--------------------- shell/match.h | 29 +++++++------- 3 files changed, 87 insertions(+), 70 deletions(-) diff --git a/shell/hush.c b/shell/hush.c index d3dab5863..4f80b7d83 100644 --- a/shell/hush.c +++ b/shell/hush.c @@ -2829,23 +2829,21 @@ static NOINLINE int expand_vars_to_list(o_string *output, int n, char *arg, char * Then var's value is matched to it and matching part removed. */ if (val) { - bool match_at_left; + char *exp_exp_word; char *loc; - scan_t scan = pick_scan(exp_op, *exp_word, &match_at_left); + unsigned scan_flags = pick_scan(exp_op, *exp_word); if (exp_op == *exp_word) /* ## or %% */ exp_word++; val = to_be_freed = xstrdup(val); - { - char *exp_exp_word = expand_pseudo_dquoted(exp_word); - if (exp_exp_word) - exp_word = exp_exp_word; - loc = scan(to_be_freed, exp_word, match_at_left); - //bb_error_msg("op:%c str:'%s' pat:'%s' res:'%s'", - // exp_op, to_be_freed, exp_word, loc); - free(exp_exp_word); - } + exp_exp_word = expand_pseudo_dquoted(exp_word); + if (exp_exp_word) + exp_word = exp_exp_word; + loc = scan_and_match(to_be_freed, exp_word, scan_flags); + //bb_error_msg("op:%c str:'%s' pat:'%s' res:'%s'", + // exp_op, to_be_freed, exp_word, loc); + free(exp_exp_word); if (loc) { /* match was found */ - if (match_at_left) /* # or ## */ + if (scan_flags & SCAN_MATCH_LEFT_HALF) /* # or ## */ val = loc; else /* % or %% */ *loc = '\0'; diff --git a/shell/match.c b/shell/match.c index 01b843918..e77c5d732 100644 --- a/shell/match.c +++ b/shell/match.c @@ -18,6 +18,9 @@ # include # include # include +# define FAST_FUNC /* nothing */ +# define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */ +# define POP_SAVED_FUNCTION_VISIBILITY /* nothing */ #else # include "libbb.h" #endif @@ -26,16 +29,48 @@ #define pmatch(a, b) !fnmatch((a), (b), 0) -char *scanleft(char *string, char *pattern, bool match_at_left) +char* FAST_FUNC scan_and_match(char *string, const char *pattern, unsigned flags) { - char c; - char *loc = string; + char *loc; + char *end; + unsigned len = strlen(string); + int early_exit; + + /* We can stop the scan early only if the string part + * we are matching against is shrinking, and the pattern has + * an unquoted "star" at the corresponding end. There are two cases. + * Case 1: + * "qwerty" does not match against pattern "*zy", + * no point in trying to match "werty", "erty" etc: + */ + early_exit = (flags == (SCAN_MOVE_FROM_LEFT + SCAN_MATCH_RIGHT_HALF) && pattern[0] == '*'); + + if (flags & SCAN_MOVE_FROM_LEFT) { + loc = string; + end = string + len + 1; + } else { + loc = string + len; + end = string - 1; + if (flags == (SCAN_MOVE_FROM_RIGHT + SCAN_MATCH_LEFT_HALF)) { + /* Case 2: + * "qwerty" does not match against pattern "qz*", + * no point in trying to match "qwert", "qwer" etc: + */ + const char *p = pattern + strlen(pattern); + if (--p >= pattern && *p == '*') { + early_exit = 1; + while (--p >= pattern && *p == '\\') + early_exit ^= 1; + } + } + } - while (1) { + while (loc != end) { + char c; int match; c = *loc; - if (match_at_left) { + if (flags & SCAN_MATCH_LEFT_HALF) { *loc = '\0'; match = pmatch(pattern, string); *loc = c; @@ -44,33 +79,19 @@ char *scanleft(char *string, char *pattern, bool match_at_left) } if (match) return loc; - if (!c) - return NULL; - loc++; - } -} - -char *scanright(char *string, char *pattern, bool match_at_left) -{ - char c; - char *loc = string + strlen(string); - - while (loc >= string) { - int match; + if (early_exit) { +#ifdef STANDALONE + printf("(early exit) "); +#endif + break; + } - c = *loc; - if (match_at_left) { - *loc = '\0'; - match = pmatch(pattern, string); - *loc = c; + if (flags & SCAN_MOVE_FROM_LEFT) { + loc++; } else { - match = pmatch(pattern, loc); + loc--; } - if (match) - return loc; - loc--; } - return NULL; } @@ -80,12 +101,11 @@ int main(int argc, char *argv[]) char *string; char *op; char *pattern; - bool match_at_left; char *loc; - int i; + setvbuf(stdout, NULL, _IONBF, 0); - if (argc == 1) { + if (!argv[1]) { puts( "Usage: match [test...]\n\n" "Where a is the form: \n" @@ -95,36 +115,34 @@ int main(int argc, char *argv[]) return 1; } - for (i = 1; i < argc; ++i) { + while (*++argv) { size_t off; - scan_t scan; - - printf("'%s': ", argv[i]); + unsigned scan_flags; - string = strdup(argv[i]); + string = *argv; off = strcspn(string, "#%"); if (!off) { printf("invalid format\n"); - free(string); continue; } op = string + off; - scan = pick_scan(op[0], op[1], &match_at_left); + scan_flags = pick_scan(op[0], op[1]); + + printf("'%s': flags:%x, ", string, scan_flags); pattern = op + 1; if (op[0] == op[1]) - op[1] = '\0', ++pattern; + pattern++; op[0] = '\0'; - loc = scan(string, pattern, match_at_left); + loc = scan_and_match(string, pattern, scan_flags); - if (match_at_left) { + if (scan_flags & SCAN_MATCH_LEFT_HALF) { printf("'%s'\n", loc); } else { - *loc = '\0'; + if (loc) + *loc = '\0'; printf("'%s'\n", string); } - - free(string); } return 0; diff --git a/shell/match.h b/shell/match.h index c022ceb25..aa393ed1a 100644 --- a/shell/match.h +++ b/shell/match.h @@ -7,25 +7,26 @@ PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN //TODO! Why ash.c still uses internal version?! -typedef char *(*scan_t)(char *string, char *match, bool match_at_left); +enum { + SCAN_MOVE_FROM_LEFT = (1 << 0), + SCAN_MOVE_FROM_RIGHT = (1 << 1), + SCAN_MATCH_LEFT_HALF = (1 << 2), + SCAN_MATCH_RIGHT_HALF = (1 << 3), +}; -char *scanleft(char *string, char *match, bool match_at_left); -char *scanright(char *string, char *match, bool match_at_left); +char* FAST_FUNC scan_and_match(char *string, const char *pattern, unsigned flags); -static inline scan_t pick_scan(char op1, char op2, bool *match_at_left) +static inline unsigned pick_scan(char op1, char op2) { - /* # - scanleft - * ## - scanright - * % - scanright - * %% - scanleft - */ + unsigned scan_flags; if (op1 == '#') { - *match_at_left = true; - return op1 == op2 ? scanright : scanleft; - } else { - *match_at_left = false; - return op1 == op2 ? scanleft : scanright; + scan_flags = SCAN_MATCH_LEFT_HALF + + (op1 == op2 ? SCAN_MOVE_FROM_RIGHT : SCAN_MOVE_FROM_LEFT); + } else { /* % */ + scan_flags = SCAN_MATCH_RIGHT_HALF + + (op1 == op2 ? SCAN_MOVE_FROM_LEFT : SCAN_MOVE_FROM_RIGHT); } + return scan_flags; } POP_SAVED_FUNCTION_VISIBILITY -- 2.25.1