[PATCH 3/3] exclude: reduce computation cost on checking dirname in patterns

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 dir.h |  3 +++
 2 files changed, 57 insertions(+), 1 deletion(-)

diff --git a/dir.c b/dir.c
index 50d744f..ff5e2d9 100644
--- a/dir.c
+++ b/dir.c
@@ -507,7 +507,7 @@ int excluded_from_list(const char *pathname,
 		       int pathlen, const char *basename, int *dtype,
 		       struct exclude_list *el)
 {
-	int i;
+	int i, baselen = pathlen - (basename - pathname);
 
 	if (!el->nr)
 		return -1;	/* undefined */
@@ -562,6 +562,35 @@ int excluded_from_list(const char *pathname,
 		if (prefix > namelen)
 			continue;
 
+		/*
+		 * it's supposed that the caller throws a series of pathnames of
+		 * the same dirname to this function when el->pruning != 0.
+		 *
+		 * If we could check whether a pattern matches dirname, we could
+		 * save the result and reuse for next pathnames.  The caller
+		 * must reset pruned/dir_matched bits when it moves to a
+		 * different directory.
+		 */
+		if (el->samedir && prefix >= namelen - baselen) {
+			int matched;
+			if (x->flags & EXC_FLAG_DIR_MATCH_VALID)
+				matched = x->flags & EXC_FLAG_DIR_MATCHED;
+			else {
+				matched = !strncmp_icase(exclude, name, namelen - baselen);
+				if (matched)
+					x->flags |= EXC_FLAG_DIR_MATCHED;
+				x->flags |= EXC_FLAG_DIR_MATCH_VALID;
+			}
+
+			if  (!matched)
+				continue;
+
+			prefix  -= namelen - baselen;
+			exclude += namelen - baselen;
+			name     = basename;
+			namelen  = baselen;
+		}
+
 		if (prefix) {
 			if (strncmp_icase(exclude, name, prefix))
 				continue;
@@ -576,6 +605,28 @@ int excluded_from_list(const char *pathname,
 	return -1; /* undecided */
 }
 
+static void prep_exclude_read_directory(struct dir_struct *dir,
+					const struct strbuf *path)
+{
+	int i, st;
+	prep_exclude(dir, path->buf, path->len);
+	for (st = EXC_CMDL; st <= EXC_FILE; st++) {
+		struct exclude_list *el = dir->exclude_list + st;
+		el->samedir = 1;
+		for (i = 0; i < el->nr; i++)
+			el->excludes[i]->flags &= ~EXC_FLAG_DIR_MATCH_VALID;
+	}
+}
+
+static void cleanup_exclude_read_directory(struct dir_struct *dir)
+{
+	int st;
+	for (st = EXC_CMDL; st <= EXC_FILE; st++) {
+		struct exclude_list *el = dir->exclude_list + st;
+		el->samedir = 0;
+	}
+}
+
 int excluded(struct dir_struct *dir, const char *pathname, int *dtype_p)
 {
 	int pathlen = strlen(pathname);
@@ -985,6 +1036,7 @@ static int read_directory_recursive(struct dir_struct *dir,
 		return 0;
 
 	strbuf_add(&path, base, baselen);
+	prep_exclude_read_directory(dir, &path);
 
 	while ((de = readdir(fdir)) != NULL) {
 		switch (treat_path(dir, de, &path, baselen, simplify)) {
@@ -1005,6 +1057,7 @@ static int read_directory_recursive(struct dir_struct *dir,
 			dir_add_name(dir, path.buf, path.len);
 	}
 exit_early:
+	cleanup_exclude_read_directory(dir);
 	closedir(fdir);
 	strbuf_release(&path);
 
diff --git a/dir.h b/dir.h
index 39fc145..003daf4 100644
--- a/dir.h
+++ b/dir.h
@@ -7,12 +7,15 @@ struct dir_entry {
 };
 
 #define EXC_FLAG_NODIR 1
+#define EXC_FLAG_DIR_MATCH_VALID 2
 #define EXC_FLAG_ENDSWITH 4
 #define EXC_FLAG_MUSTBEDIR 8
+#define EXC_FLAG_DIR_MATCHED 16
 
 struct exclude_list {
 	int nr;
 	int alloc;
+	int samedir;
 	struct exclude {
 		const char *pattern;
 		int patternlen;
-- 
1.7.10.2.549.g9354186