From 701e127f7d892909a58c6f3333e23588ccef9e22 Mon Sep 17 00:00:00 2001
From: Denys Vlasenko <dvlasenk@redhat.com>
Date: Sat, 4 Sep 2010 21:21:07 +0200
Subject: hush: optimize #[#] and %[%] for speed. size -2 bytes.

Signed-off-by: Denys Vlasenko <dvlasenk@redhat.com>
---
 shell/match.c | 106 ++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 62 insertions(+), 44 deletions(-)

(limited to 'shell/match.c')

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 <stdlib.h>
 # include <string.h>
 # include <unistd.h>
+# 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> [test...]\n\n"
 			"Where a <test> is the form: <string><op><match>\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;
-- 
cgit v1.2.3