[PATCH 4/5] Use kwset in pickaxe

From

Fredrik Kuivinen <frekui@gmail.com>

Date

Feb 13, 2010, 14:21 UTC

Message-ID

<20100213142100.GE9543@fredrik-laptop>

In-Reply-To

<20100213141558.22851.13660.stgit@fredrik-laptop>

Best of five runs in the git repository:

before:

$ time git log -Sqwerty

after:

$ time git log -Sqwerty

So the kwset code is about 25% faster.

Signed-off-by: Fredrik Kuivinen <frekui@gmail.com>
---

 Makefile           |    2 ++
 diffcore-pickaxe.c |   34 +++++++++++++++++++++++-----------
 2 files changed, 25 insertions(+), 11 deletions(-)

diff --git a/Makefile b/Makefile
index 7bf2fca..5687b99 100644
--- a/Makefile
+++ b/Makefile
@@ -479,6 +479,7 @@ LIB_H += unpack-trees.h
 LIB_H += userdiff.h
 LIB_H += utf8.h
 LIB_H += wt-status.h
+LIB_H += kwset.h
 
 LIB_OBJS += abspath.o
 LIB_OBJS += advice.o
@@ -591,6 +592,7 @@ LIB_OBJS += write_or_die.o
 LIB_OBJS += ws.o
 LIB_OBJS += wt-status.o
 LIB_OBJS += xdiff-interface.o
+LIB_OBJS += kwset.o
 
 BUILTIN_OBJS += builtin-add.o
 BUILTIN_OBJS += builtin-annotate.o
diff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c
index d0ef839..6563a4e 100644
--- a/diffcore-pickaxe.c
+++ b/diffcore-pickaxe.c
@@ -4,10 +4,11 @@
 #include "cache.h"
 #include "diff.h"
 #include "diffcore.h"
+#include "kwset.h"
 
 static unsigned int contains(struct diff_filespec *one,
 			     const char *needle, unsigned long len,
-			     regex_t *regexp)
+			     regex_t *regexp, kwset_t kws)
 {
 	unsigned int cnt;
 	unsigned long sz;
@@ -36,9 +37,12 @@ static unsigned int contains(struct diff_filespec *one,
 
 	} else { /* Classic exact string match */
 		while (sz) {
-			const char *found = memmem(data, sz, needle, len);
-			if (!found)
+			size_t offset = kwsexec(kws, data, sz, NULL);
+			const char *found;
+			if (offset == -1)
 				break;
+			else
+				found = data + offset;
 			sz -= found - data + len;
 			data = found + len;
 			cnt++;
@@ -54,6 +58,7 @@ void diffcore_pickaxe(const char *needle, int opts)
 	unsigned long len = strlen(needle);
 	int i, has_changes;
 	regex_t regex, *regexp = NULL;
+	kwset_t kws = NULL;
 	struct diff_queue_struct outq;
 	outq.queue = NULL;
 	outq.nr = outq.alloc = 0;
@@ -69,6 +74,10 @@ void diffcore_pickaxe(const char *needle, int opts)
 			die("invalid pickaxe regex: %s", errbuf);
 		}
 		regexp = &regex;
+	} else {
+		kws = kwsalloc(NULL);
+		kwsincr(kws, needle, len);
+		kwsprep(kws);
 	}
 
 	if (opts & DIFF_PICKAXE_ALL) {
@@ -79,16 +88,16 @@ void diffcore_pickaxe(const char *needle, int opts)
 				if (!DIFF_FILE_VALID(p->two))
 					continue; /* ignore unmerged */
 				/* created */
-				if (contains(p->two, needle, len, regexp))
+				if (contains(p->two, needle, len, regexp, kws))
 					has_changes++;
 			}
 			else if (!DIFF_FILE_VALID(p->two)) {
-				if (contains(p->one, needle, len, regexp))
+				if (contains(p->one, needle, len, regexp, kws))
 					has_changes++;
 			}
 			else if (!diff_unmodified_pair(p) &&
-				 contains(p->one, needle, len, regexp) !=
-				 contains(p->two, needle, len, regexp))
+				contains(p->one, needle, len, regexp, kws) !=
+				contains(p->two, needle, len, regexp, kws))
 				has_changes++;
 		}
 		if (has_changes)
@@ -111,16 +120,17 @@ void diffcore_pickaxe(const char *needle, int opts)
 				if (!DIFF_FILE_VALID(p->two))
 					; /* ignore unmerged */
 				/* created */
-				else if (contains(p->two, needle, len, regexp))
+				else if (contains(p->two, needle, len, regexp,
+						  kws))
 					has_changes = 1;
 			}
 			else if (!DIFF_FILE_VALID(p->two)) {
-				if (contains(p->one, needle, len, regexp))
+				if (contains(p->one, needle, len, regexp, kws))
 					has_changes = 1;
 			}
 			else if (!diff_unmodified_pair(p) &&
-				 contains(p->one, needle, len, regexp) !=
-				 contains(p->two, needle, len, regexp))
+				contains(p->one, needle, len, regexp, kws) !=
+				contains(p->two, needle, len, regexp, kws))
 				has_changes = 1;
 
 			if (has_changes)
@@ -131,6 +141,8 @@ void diffcore_pickaxe(const char *needle, int opts)
 
 	if (opts & DIFF_PICKAXE_REGEX) {
 		regfree(&regex);
+	} else {
+		kwsfree(kws);
 	}
 
 	free(q->queue);