From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Sat, 28 Feb 2009 01:13:11 GMT
Subject: Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()
Message-ID: <49A88FA7.1020402@lsrfire.ath.cx>
In-Reply-To: <cd73512d11e63554396983ed4e9556b2d18b3e4a.1235629933.git.gitster@pobox.com>

Junio C Hamano schrieb:
> -static unsigned int count_match(int one_or_more,
> -				struct diff_filespec *one,
> -				const char *needle, unsigned long len,
> -				regex_t *regexp)
> +static unsigned int count_match_internal(int one_or_more,
> +					 const char *data, unsigned long sz,
> +					 const char *needle, unsigned long len,
> +					 regex_t *regexp)
>  {

I don't especially like flags like one_or_more.  Having two functions
(which possibly call a common function that does most of the work) is
nicer.  And it's a bit sad here because there already are two functions
with nice names: count_match() and has_match().  But, well, since the
functions are not exported anyway it doesn't matter much.

> @@ -29,16 +20,14 @@ static unsigned int count_match(int one_or_more,
>  		while (*data && !regexec(regexp, data, 1, &regmatch, flags)) {
>  			flags |= REG_NOTBOL;
>  			data += regmatch.rm_so;
> -			if (*data) data++;
> +			if (*data)
> +				data++;
>  			cnt++;
>  			if (one_or_more)
>  				break;
>  		}
> -
> -	} else { /* Classic exact string match */
> -		/* Yes, I've heard of strstr(), but the thing is *data may
> -		 * not be NUL terminated.  Sue me.
> -		 */
> +	} else {
> +		/* data many not be NUL terminated; we cannot use strstr() */

That looks fishy to me.  regexec() expects data to be a NUL-terminated
string, so either the comment is wrong or the regexp case needs to take
better care to add a NUL at the end of the buffer.

In any case, there is also memmem(), which uses the same fast algorithm
as strstr() in recent glibc versions.  Like this?


diff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c
index f4870b4..4c19967 100644
--- a/diffcore-pickaxe.c
+++ b/diffcore-pickaxe.c
@@ -11,7 +11,6 @@ static unsigned int count_match_internal(int one_or_more,
 					 regex_t *regexp)
 {
 	unsigned int cnt = 0;
-	unsigned long offset;
 
 	if (regexp) {
 		regmatch_t regmatch;
@@ -27,15 +26,15 @@ static unsigned int count_match_internal(int one_or_more,
 				break;
 		}
 	} else {
-		/* data many not be NUL terminated; we cannot use strstr() */
-		for (offset = 0; offset + len <= sz; offset++) {
-			/* we count non-overlapping occurrences of needle */
-			if (!memcmp(needle, data + offset, len)) {
-				offset += len - 1;
-				cnt++;
-				if (one_or_more)
-					break;
-			}
+		while (sz) {
+			const char *found = memmem(data, sz, needle, len);
+			if (!found)
+				break;
+			sz -= found - data + len;
+			data = found + len;
+			cnt++;
+			if (one_or_more)
+				break;
 		}
 	}
 	return cnt;